summaryrefslogtreecommitdiffstats
path: root/gfx/wr/webrender/src/texture_pack/guillotine.rs
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 19:33:14 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 19:33:14 +0000
commit36d22d82aa202bb199967e9512281e9a53db42c9 (patch)
tree105e8c98ddea1c1e4784a60a5a6410fa416be2de /gfx/wr/webrender/src/texture_pack/guillotine.rs
parentInitial commit. (diff)
downloadfirefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.tar.xz
firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.zip
Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'gfx/wr/webrender/src/texture_pack/guillotine.rs')
-rw-r--r--gfx/wr/webrender/src/texture_pack/guillotine.rs284
1 files changed, 284 insertions, 0 deletions
diff --git a/gfx/wr/webrender/src/texture_pack/guillotine.rs b/gfx/wr/webrender/src/texture_pack/guillotine.rs
new file mode 100644
index 0000000000..68a08caf2f
--- /dev/null
+++ b/gfx/wr/webrender/src/texture_pack/guillotine.rs
@@ -0,0 +1,284 @@
+/* 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/. */
+
+use api::units::{DeviceIntPoint, DeviceIntRect, DeviceIntSize};
+
+//TODO: gather real-world statistics on the bin usage in order to assist the decision
+// on where to place the size thresholds.
+
+const NUM_BINS: usize = 3;
+/// The minimum number of pixels on each side that we require for rects to be classified as
+/// particular bin of freelists.
+const MIN_RECT_AXIS_SIZES: [i32; NUM_BINS] = [1, 16, 32];
+
+#[derive(Debug, Clone, Copy, PartialEq, PartialOrd)]
+struct FreeListBin(u8);
+
+#[derive(Debug, Clone, Copy)]
+struct FreeListIndex(usize);
+
+impl FreeListBin {
+ fn for_size(size: &DeviceIntSize) -> Self {
+ MIN_RECT_AXIS_SIZES
+ .iter()
+ .enumerate()
+ .rev()
+ .find(|(_, &min_size)| min_size <= size.width && min_size <= size.height)
+ .map(|(id, _)| FreeListBin(id as u8))
+ .unwrap_or_else(|| panic!("Unable to find a bin for {:?}!", size))
+ }
+}
+
+#[derive(Debug, Clone, Copy, PartialEq)]
+#[cfg_attr(feature = "capture", derive(Serialize))]
+#[cfg_attr(feature = "replay", derive(Deserialize))]
+pub struct FreeRectSlice(pub u32);
+
+#[cfg_attr(feature = "capture", derive(Serialize))]
+#[cfg_attr(feature = "replay", derive(Deserialize))]
+struct FreeRect {
+ slice: FreeRectSlice,
+ rect: DeviceIntRect,
+}
+
+#[cfg_attr(feature = "capture", derive(Serialize))]
+#[cfg_attr(feature = "replay", derive(Deserialize))]
+struct FreeRectSize {
+ width: i16,
+ height: i16,
+}
+
+#[cfg_attr(feature = "capture", derive(Serialize))]
+#[cfg_attr(feature = "replay", derive(Deserialize))]
+struct Bin {
+ // Store sizes with fewer bits per item and in a separate array to speed up
+ // the search.
+ sizes: Vec<FreeRectSize>,
+ rects: Vec<FreeRect>,
+}
+
+/// A texture allocator using the guillotine algorithm.
+///
+/// See sections 2.2 and 2.2.5 in "A Thousand Ways to Pack the Bin - A Practical Approach to Two-
+/// Dimensional Rectangle Bin Packing":
+///
+/// http://clb.demon.fi/files/RectangleBinPack.pdf
+///
+/// This approach was chosen because of its simplicity and good performance.
+///
+/// Note: the allocations are spread across multiple textures, and also are binned
+/// orthogonally in order to speed up the search.
+#[cfg_attr(feature = "capture", derive(Serialize))]
+#[cfg_attr(feature = "replay", derive(Deserialize))]
+pub struct GuillotineAllocator {
+ bins: [Bin; NUM_BINS],
+}
+
+impl GuillotineAllocator {
+ pub fn new(initial_size: Option<DeviceIntSize>) -> Self {
+ let mut allocator = GuillotineAllocator {
+ bins: [
+ Bin { rects: Vec::new(), sizes: Vec::new() },
+ Bin { rects: Vec::new(), sizes: Vec::new() },
+ Bin { rects: Vec::new(), sizes: Vec::new() },
+ ],
+ };
+
+ if let Some(initial_size) = initial_size {
+ allocator.push(
+ FreeRectSlice(0),
+ initial_size.into(),
+ );
+ }
+
+ allocator
+ }
+
+ fn push(&mut self, slice: FreeRectSlice, rect: DeviceIntRect) {
+ let id = FreeListBin::for_size(&rect.size()).0 as usize;
+ self.bins[id].rects.push(FreeRect {
+ slice,
+ rect,
+ });
+ self.bins[id].sizes.push(FreeRectSize {
+ width: rect.width() as i16,
+ height: rect.height() as i16,
+ });
+ }
+
+ /// Find a suitable rect in the free list. We choose the first fit.
+ fn find_index_of_best_rect(
+ &self,
+ requested_dimensions: &DeviceIntSize,
+ ) -> Option<(FreeListBin, FreeListIndex)> {
+
+ let start_bin = FreeListBin::for_size(&requested_dimensions);
+
+ let w = requested_dimensions.width as i16;
+ let h = requested_dimensions.height as i16;
+ (start_bin.0 .. NUM_BINS as u8)
+ .find_map(|id| {
+ self.bins[id as usize].sizes
+ .iter()
+ .position(|candidate| w <= candidate.width && h <= candidate.height)
+ .map(|index| (FreeListBin(id), FreeListIndex(index)))
+ })
+ }
+
+ // Split that results in the single largest area (Min Area Split Rule, MINAS).
+ fn split_guillotine(&mut self, chosen: &FreeRect, requested_dimensions: &DeviceIntSize) {
+ let candidate_free_rect_to_right = DeviceIntRect::from_origin_and_size(
+ DeviceIntPoint::new(
+ chosen.rect.min.x + requested_dimensions.width,
+ chosen.rect.min.y,
+ ),
+ DeviceIntSize::new(
+ chosen.rect.width() - requested_dimensions.width,
+ requested_dimensions.height,
+ ),
+ );
+ let candidate_free_rect_to_bottom = DeviceIntRect::from_origin_and_size(
+ DeviceIntPoint::new(
+ chosen.rect.min.x,
+ chosen.rect.min.y + requested_dimensions.height,
+ ),
+ DeviceIntSize::new(
+ requested_dimensions.width,
+ chosen.rect.height() - requested_dimensions.height,
+ ),
+ );
+
+ // Guillotine the rectangle.
+ let new_free_rect_to_right;
+ let new_free_rect_to_bottom;
+ if candidate_free_rect_to_right.area() > candidate_free_rect_to_bottom.area() {
+ new_free_rect_to_right = DeviceIntRect::from_origin_and_size(
+ candidate_free_rect_to_right.min,
+ DeviceIntSize::new(
+ candidate_free_rect_to_right.width(),
+ chosen.rect.height(),
+ ),
+ );
+ new_free_rect_to_bottom = candidate_free_rect_to_bottom
+ } else {
+ new_free_rect_to_right = candidate_free_rect_to_right;
+ new_free_rect_to_bottom = DeviceIntRect::from_origin_and_size(
+ candidate_free_rect_to_bottom.min,
+ DeviceIntSize::new(
+ chosen.rect.width(),
+ candidate_free_rect_to_bottom.height(),
+ ),
+ )
+ }
+
+ // Add the guillotined rects back to the free list.
+ if !new_free_rect_to_right.is_empty() {
+ self.push(chosen.slice, new_free_rect_to_right);
+ }
+ if !new_free_rect_to_bottom.is_empty() {
+ self.push(chosen.slice, new_free_rect_to_bottom);
+ }
+ }
+
+ pub fn allocate(
+ &mut self, requested_dimensions: &DeviceIntSize
+ ) -> Option<(FreeRectSlice, DeviceIntPoint)> {
+ let mut requested_dimensions = *requested_dimensions;
+ // Round up the size to a multiple of 8. This reduces the fragmentation
+ // of the atlas.
+ requested_dimensions.width = (requested_dimensions.width + 7) & !7;
+ requested_dimensions.height = (requested_dimensions.height + 7) & !7;
+
+ if requested_dimensions.width == 0 || requested_dimensions.height == 0 {
+ return Some((FreeRectSlice(0), DeviceIntPoint::new(0, 0)));
+ }
+
+ let (bin, index) = self.find_index_of_best_rect(&requested_dimensions)?;
+
+ // Remove the rect from the free list and decide how to guillotine it.
+ let chosen = self.bins[bin.0 as usize].rects.swap_remove(index.0);
+ self.bins[bin.0 as usize].sizes.swap_remove(index.0);
+ self.split_guillotine(&chosen, &requested_dimensions);
+
+ // Return the result.
+ Some((chosen.slice, chosen.rect.min))
+ }
+
+ /// Add a new slice to the allocator, and immediately allocate a rect from it.
+ pub fn extend(
+ &mut self,
+ slice: FreeRectSlice,
+ total_size: DeviceIntSize,
+ requested_dimensions: DeviceIntSize,
+ ) {
+ self.split_guillotine(
+ &FreeRect { slice, rect: total_size.into() },
+ &requested_dimensions
+ );
+ }
+}
+
+#[cfg(test)]
+fn random_fill(count: usize, texture_size: i32) -> f32 {
+ use rand::{thread_rng, Rng};
+
+ let total_rect = DeviceIntRect::from_size(
+ DeviceIntSize::new(texture_size, texture_size),
+ );
+ let mut rng = thread_rng();
+ let mut allocator = GuillotineAllocator::new(None);
+
+ // check for empty allocation
+ assert_eq!(
+ allocator.allocate(&DeviceIntSize::new(0, 12)),
+ Some((FreeRectSlice(0), DeviceIntPoint::zero())),
+ );
+
+ let mut slices: Vec<Vec<DeviceIntRect>> = Vec::new();
+ let mut requested_area = 0f32;
+ // fill up the allocator
+ for _ in 0 .. count {
+ let size = DeviceIntSize::new(
+ rng.gen_range(1, texture_size),
+ rng.gen_range(1, texture_size),
+ );
+ requested_area += size.area() as f32;
+
+ match allocator.allocate(&size) {
+ Some((slice, origin)) => {
+ let rect = DeviceIntRect::from_origin_and_size(origin, size);
+ assert_eq!(None, slices[slice.0 as usize].iter().find(|r| r.intersects(&rect)));
+ assert!(total_rect.contains_box(&rect));
+ slices[slice.0 as usize].push(rect);
+ }
+ None => {
+ allocator.extend(FreeRectSlice(slices.len() as u32), total_rect.size(), size);
+ let rect = DeviceIntRect::from_size(size);
+ slices.push(vec![rect]);
+ }
+ }
+ }
+ // validate the free rects
+ for (i, bin) in allocator.bins.iter().enumerate() {
+ for fr in &bin.rects {
+ assert_eq!(FreeListBin(i as u8), FreeListBin::for_size(&fr.rect.size()));
+ assert_eq!(None, slices[fr.slice.0 as usize].iter().find(|r| r.intersects(&fr.rect)));
+ assert!(total_rect.contains_box(&fr.rect));
+ slices[fr.slice.0 as usize].push(fr.rect);
+ }
+ }
+
+ let allocated_area = slices.len() as f32 * (texture_size * texture_size) as f32;
+ requested_area / allocated_area
+}
+
+#[test]
+fn test_small() {
+ random_fill(100, 100);
+}
+
+#[test]
+fn test_large() {
+ random_fill(1000, 10000);
+}