webrender/texture_pack/
guillotine.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5use api::units::{DeviceIntPoint, DeviceIntRect, DeviceIntSize};
6
7//TODO: gather real-world statistics on the bin usage in order to assist the decision
8// on where to place the size thresholds.
9
10const NUM_BINS: usize = 3;
11/// The minimum number of pixels on each side that we require for rects to be classified as
12/// particular bin of freelists.
13const MIN_RECT_AXIS_SIZES: [i32; NUM_BINS] = [1, 16, 32];
14
15#[derive(Debug, Clone, Copy, PartialEq, PartialOrd)]
16struct FreeListBin(u8);
17
18#[derive(Debug, Clone, Copy)]
19struct FreeListIndex(usize);
20
21impl FreeListBin {
22    fn for_size(size: &DeviceIntSize) -> Self {
23        MIN_RECT_AXIS_SIZES
24            .iter()
25            .enumerate()
26            .rev()
27            .find(|(_, &min_size)| min_size <= size.width && min_size <= size.height)
28            .map(|(id, _)| FreeListBin(id as u8))
29            .unwrap_or_else(|| panic!("Unable to find a bin for {:?}!", size))
30    }
31}
32
33#[derive(Debug, Clone, Copy, PartialEq)]
34#[cfg_attr(feature = "capture", derive(Serialize))]
35#[cfg_attr(feature = "replay", derive(Deserialize))]
36pub struct FreeRectSlice(pub u32);
37
38#[cfg_attr(feature = "capture", derive(Serialize))]
39#[cfg_attr(feature = "replay", derive(Deserialize))]
40struct FreeRect {
41    slice: FreeRectSlice,
42    rect: DeviceIntRect,
43}
44
45#[cfg_attr(feature = "capture", derive(Serialize))]
46#[cfg_attr(feature = "replay", derive(Deserialize))]
47struct FreeRectSize {
48    width: i16,
49    height: i16,
50}
51
52#[cfg_attr(feature = "capture", derive(Serialize))]
53#[cfg_attr(feature = "replay", derive(Deserialize))]
54struct Bin {
55    // Store sizes with fewer bits per item and in a separate array to speed up
56    // the search.
57    sizes: Vec<FreeRectSize>,
58    rects: Vec<FreeRect>,
59}
60
61/// A texture allocator using the guillotine algorithm.
62///
63/// See sections 2.2 and 2.2.5 in "A Thousand Ways to Pack the Bin - A Practical Approach to Two-
64/// Dimensional Rectangle Bin Packing":
65///
66///    http://clb.demon.fi/files/RectangleBinPack.pdf
67///
68/// This approach was chosen because of its simplicity and good performance.
69///
70/// Note: the allocations are spread across multiple textures, and also are binned
71/// orthogonally in order to speed up the search.
72#[cfg_attr(feature = "capture", derive(Serialize))]
73#[cfg_attr(feature = "replay", derive(Deserialize))]
74pub struct GuillotineAllocator {
75    bins: [Bin; NUM_BINS],
76}
77
78impl GuillotineAllocator {
79    pub fn new(initial_size: Option<DeviceIntSize>) -> Self {
80        let mut allocator = GuillotineAllocator {
81            bins: [
82                Bin { rects: Vec::new(), sizes: Vec::new() },
83                Bin { rects: Vec::new(), sizes: Vec::new() },
84                Bin { rects: Vec::new(), sizes: Vec::new() },
85            ],
86        };
87
88        if let Some(initial_size) = initial_size {
89            allocator.push(
90                FreeRectSlice(0),
91                initial_size.into(),
92            );
93        }
94
95        allocator
96    }
97
98    fn push(&mut self, slice: FreeRectSlice, rect: DeviceIntRect) {
99        let id = FreeListBin::for_size(&rect.size()).0 as usize;
100        self.bins[id].rects.push(FreeRect {
101            slice,
102            rect,
103        });
104        self.bins[id].sizes.push(FreeRectSize {
105            width: rect.width() as i16,
106            height: rect.height() as i16,
107        });
108    }
109
110    /// Find a suitable rect in the free list. We choose the first fit.
111    fn find_index_of_best_rect(
112        &self,
113        requested_dimensions: &DeviceIntSize,
114    ) -> Option<(FreeListBin, FreeListIndex)> {
115
116        let start_bin = FreeListBin::for_size(&requested_dimensions);
117
118        let w = requested_dimensions.width as i16;
119        let h = requested_dimensions.height as i16;
120        (start_bin.0 .. NUM_BINS as u8)
121            .find_map(|id| {
122                self.bins[id as usize].sizes
123                    .iter()
124                    .position(|candidate| w <= candidate.width && h <= candidate.height)
125                    .map(|index| (FreeListBin(id), FreeListIndex(index)))
126            })
127    }
128
129    // Split that results in the single largest area (Min Area Split Rule, MINAS).
130    fn split_guillotine(&mut self, chosen: &FreeRect, requested_dimensions: &DeviceIntSize) {
131        let candidate_free_rect_to_right = DeviceIntRect::from_origin_and_size(
132            DeviceIntPoint::new(
133                chosen.rect.min.x + requested_dimensions.width,
134                chosen.rect.min.y,
135            ),
136            DeviceIntSize::new(
137                chosen.rect.width() - requested_dimensions.width,
138                requested_dimensions.height,
139            ),
140        );
141        let candidate_free_rect_to_bottom = DeviceIntRect::from_origin_and_size(
142            DeviceIntPoint::new(
143                chosen.rect.min.x,
144                chosen.rect.min.y + requested_dimensions.height,
145            ),
146            DeviceIntSize::new(
147                requested_dimensions.width,
148                chosen.rect.height() - requested_dimensions.height,
149            ),
150        );
151
152        // Guillotine the rectangle.
153        let new_free_rect_to_right;
154        let new_free_rect_to_bottom;
155        if candidate_free_rect_to_right.area() > candidate_free_rect_to_bottom.area() {
156            new_free_rect_to_right = DeviceIntRect::from_origin_and_size(
157                candidate_free_rect_to_right.min,
158                DeviceIntSize::new(
159                    candidate_free_rect_to_right.width(),
160                    chosen.rect.height(),
161                ),
162            );
163            new_free_rect_to_bottom = candidate_free_rect_to_bottom
164        } else {
165            new_free_rect_to_right = candidate_free_rect_to_right;
166            new_free_rect_to_bottom = DeviceIntRect::from_origin_and_size(
167                candidate_free_rect_to_bottom.min,
168                DeviceIntSize::new(
169                    chosen.rect.width(),
170                    candidate_free_rect_to_bottom.height(),
171                ),
172            )
173        }
174
175        // Add the guillotined rects back to the free list.
176        if !new_free_rect_to_right.is_empty() {
177            self.push(chosen.slice, new_free_rect_to_right);
178        }
179        if !new_free_rect_to_bottom.is_empty() {
180            self.push(chosen.slice, new_free_rect_to_bottom);
181        }
182    }
183
184    pub fn allocate(
185        &mut self, requested_dimensions: &DeviceIntSize
186    ) -> Option<(FreeRectSlice, DeviceIntPoint)> {
187        let mut requested_dimensions = *requested_dimensions;
188        // Round up the size to a multiple of 8. This reduces the fragmentation
189        // of the atlas.
190        requested_dimensions.width = (requested_dimensions.width + 7) & !7;
191        requested_dimensions.height = (requested_dimensions.height + 7) & !7;
192
193        if requested_dimensions.width == 0 || requested_dimensions.height == 0 {
194            return Some((FreeRectSlice(0), DeviceIntPoint::new(0, 0)));
195        }
196
197        let (bin, index) = self.find_index_of_best_rect(&requested_dimensions)?;
198
199        // Remove the rect from the free list and decide how to guillotine it.
200        let chosen = self.bins[bin.0 as usize].rects.swap_remove(index.0);
201        self.bins[bin.0 as usize].sizes.swap_remove(index.0);
202        self.split_guillotine(&chosen, &requested_dimensions);
203
204        // Return the result.
205        Some((chosen.slice, chosen.rect.min))
206    }
207
208    /// Add a new slice to the allocator, and immediately allocate a rect from it.
209    pub fn extend(
210        &mut self,
211        slice: FreeRectSlice,
212        total_size: DeviceIntSize,
213        requested_dimensions: DeviceIntSize,
214    ) {
215        self.split_guillotine(
216            &FreeRect { slice, rect: total_size.into() },
217            &requested_dimensions
218        );
219    }
220}
221
222#[cfg(test)]
223fn random_fill(count: usize, texture_size: i32) -> f32 {
224    use rand::{thread_rng, Rng};
225
226    let total_rect = DeviceIntRect::from_size(
227        DeviceIntSize::new(texture_size, texture_size),
228    );
229    let mut rng = thread_rng();
230    let mut allocator = GuillotineAllocator::new(None);
231
232    // check for empty allocation
233    assert_eq!(
234        allocator.allocate(&DeviceIntSize::new(0, 12)),
235        Some((FreeRectSlice(0), DeviceIntPoint::zero())),
236    );
237
238    let mut slices: Vec<Vec<DeviceIntRect>> = Vec::new();
239    let mut requested_area = 0f32;
240    // fill up the allocator
241    for _ in 0 .. count {
242        let size = DeviceIntSize::new(
243            rng.gen_range(1, texture_size),
244            rng.gen_range(1, texture_size),
245        );
246        requested_area += size.area() as f32;
247
248        match allocator.allocate(&size) {
249            Some((slice, origin)) => {
250                let rect = DeviceIntRect::from_origin_and_size(origin, size);
251                assert_eq!(None, slices[slice.0 as usize].iter().find(|r| r.intersects(&rect)));
252                assert!(total_rect.contains_box(&rect));
253                slices[slice.0 as usize].push(rect);
254            }
255            None => {
256                allocator.extend(FreeRectSlice(slices.len() as u32), total_rect.size(), size);
257                let rect = DeviceIntRect::from_size(size);
258                slices.push(vec![rect]);
259            }
260        }
261    }
262    // validate the free rects
263    for (i, bin) in allocator.bins.iter().enumerate() {
264        for fr in &bin.rects {
265            assert_eq!(FreeListBin(i as u8), FreeListBin::for_size(&fr.rect.size()));
266            assert_eq!(None, slices[fr.slice.0 as usize].iter().find(|r| r.intersects(&fr.rect)));
267            assert!(total_rect.contains_box(&fr.rect));
268            slices[fr.slice.0 as usize].push(fr.rect);
269        }
270    }
271
272    let allocated_area = slices.len() as f32 * (texture_size * texture_size) as f32;
273    requested_area / allocated_area
274}
275
276#[test]
277fn test_small() {
278    random_fill(100, 100);
279}
280
281#[test]
282fn test_large() {
283    random_fill(1000, 10000);
284}
webrender/texture_pack/guillotine.rs

webrender/texture_pack/
guillotine.rs
