tor-browser

rectangle_occlusion.rs (7526B)

---

/* 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;
   }
}