webrender/

rectangle_occlusion.rs

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

//! A simple occlusion culling algorithm for axis-aligned rectangles.
//!
//! ## Output
//!
//! Occlusion culling results in two lists of rectangles:
//! 
//! - The opaque list should be rendered first. None of its rectangles overlap so order doesn't matter
//!   within the opaque pass.
//! - The non-opaque list (or alpha list) which should be rendered in back-to-front order after the opaque pass.
//!
//! The output has minimal overdraw (no overdraw at all for opaque items and as little as possible for alpha ones).
//!
//! ## Algorithm overview
//!
//! The occlusion culling algorithm works in front-to-back order, accumulating rectangle in opaque and non-opaque lists.
//! Each time a rectangle is added, it is first tested against existing opaque rectangles and potentially split into visible
//! sub-rectangles, or even discarded completely. The front-to-back order ensures that once a rectangle is added it does not
//! have to be modified again, making the underlying data structure trivial (append-only).
//!
//! ## splitting
//!
//! Partially visible rectangles are split into up to 4 visible sub-rectangles by each intersecting occluder.
//!
//! ```ascii
//!  +----------------------+       +----------------------+
//!  | rectangle            |       |                      |
//!  |                      |       |                      |
//!  |  +-----------+       |       +--+-----------+-------+
//!  |  |occluder   |       |  -->  |  |\\\\\\\\\\\|       |
//!  |  +-----------+       |       +--+-----------+-------+
//!  |                      |       |                      |
//!  +----------------------+       +----------------------+
//! ```
//!
//! In the example above the rectangle is split into 4 visible parts with the central occluded part left out.
//!
//! This implementation favors longer horizontal bands instead creating nine-patches to deal with the corners.
//! The advantage is that it produces less rectangles which is good for the performance of the algorithm and
//! for SWGL which likes long horizontal spans, however it would cause artifacts if the resulting rectangles
//! were to be drawn with a non-axis-aligned transformation.
//!
//! ## Performance
//!
//! The cost of the algorithm grows with the number of opaque rectangle as each new rectangle is tested against
//! all previously added opaque rectangles.
//!
//! Note that opaque rectangles can either be added as opaque or non-opaque. This means a trade-off between
//! overdraw and number of rectangles can be explored to adjust performance: Small opaque rectangles, especially
//! towards the front of the scene, could be added as non-opaque to avoid causing many splits while adding only 
//! a small amount of overdraw.
//!
//! This implementation is intended to be used with a small number of (opaque) items. A similar implementation
//! could use a spatial acceleration structure for opaque rectangles to perform better with a large amount of
//! occluders.
//!

use euclid::point2;
use smallvec::SmallVec;
use api::units::*;

/// A visible part of a rectangle after occlusion culling.
#[derive(Debug, PartialEq)]
pub struct Item<K> {
    pub rectangle: DeviceBox2D,
    pub key: K,
}

/// A builder that applies occlusion culling with rectangles provided in front-to-back order.
pub struct FrontToBackBuilder<K> {
    opaque_items: Vec<Item<K>>,
    alpha_items: Vec<Item<K>>,
}

impl<K> FrontToBackBuilder<K> where K: Copy {

    /// Pre-allocating constructor.
    pub fn with_capacity(opaque: usize, alpha: usize) -> Self {
        FrontToBackBuilder {
            opaque_items: Vec::with_capacity(opaque),
            alpha_items: Vec::with_capacity(alpha),
        }
    }

    /// Add a rectangle, potentially splitting it and discarding the occluded parts if any.
    ///
    /// Returns true the rectangle is at least partially visible.
    pub fn add(&mut self, rect: &DeviceBox2D, is_opaque: bool, key: K) -> bool {
        let mut fragments: SmallVec<[DeviceBox2D; 16]> = SmallVec::new();
        fragments.push(*rect);

        for item in &self.opaque_items {
            if fragments.is_empty() {
                break;
            }
            if item.rectangle.intersects(rect) {
                apply_occluder(&item.rectangle, &mut fragments);
            }
        }

        let list = if is_opaque {
            &mut self.opaque_items
        } else {
            &mut self.alpha_items
        };

        for rect in &fragments {
            list.push(Item {
                rectangle: *rect,
                key,
            });
        }

        !fragments.is_empty()
    }

    /// Returns true if the provided rect is at least partially visible, without adding it.
    pub fn test(&self, rect: &DeviceBox2D) -> bool {
        let mut fragments: SmallVec<[DeviceBox2D; 16]> = SmallVec::new();
        fragments.push(*rect);

        for item in &self.opaque_items {
            if item.rectangle.intersects(rect) {
                apply_occluder(&item.rectangle, &mut fragments);
            }
        }

        !fragments.is_empty()
    }

    /// The visible opaque rectangles (front-to-back order).
    pub fn opaque_items(&self) -> &[Item<K>] {
        &self.opaque_items
    }

    /// The visible non-opaque rectangles (front-to-back order).
    pub fn alpha_items(&self) -> &[Item<K>] {
        &self.alpha_items
    }
}


// Split out the parts of the rects in the provided vector
fn apply_occluder(occluder: &DeviceBox2D, rects: &mut SmallVec<[DeviceBox2D; 16]>) {
    // Iterate in reverse order so that we can push new rects at the back without
    // visiting them;
    let mut i = rects.len() - 1;
    loop {
        let r = rects[i];

        if r.intersects(occluder) {
            let top = r.min.y < occluder.min.y;
            let bottom = r.max.y > occluder.max.y;
            let left = r.min.x < occluder.min.x;
            let right = r.max.x > occluder.max.x;

            if top {
                rects.push(DeviceBox2D {
                    min: r.min,
                    max: point2(r.max.x, occluder.min.y),
                });
            }

            if bottom {
                rects.push(DeviceBox2D {
                    min: point2(r.min.x, occluder.max.y),
                    max: r.max,
                });
            }

            if left {
                let min_y = r.min.y.max(occluder.min.y);
                let max_y = r.max.y.min(occluder.max.y);
                rects.push(DeviceBox2D {
                    min: point2(r.min.x, min_y),
                    max: point2(occluder.min.x, max_y),
                });
            }

            if right {
                let min_y = r.min.y.max(occluder.min.y);
                let max_y = r.max.y.min(occluder.max.y);
                rects.push(DeviceBox2D {
                    min: point2(occluder.max.x, min_y),
                    max: point2(r.max.x, max_y),
                });
            }

            // Remove the original rectangle, replacing it with
            // one of the new ones we just added, or popping it
            // if it is the last item.
            if i == rects.len() {
                rects.pop();
            } else {
                rects.swap_remove(i);
            }
        }

        if i == 0 {
            break;
        }

        i -= 1;
    }
}