guillotine.rs (10011B)
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 5 use 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 10 const 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. 13 const MIN_RECT_AXIS_SIZES: [i32; NUM_BINS] = [1, 16, 32]; 14 15 #[derive(Debug, Clone, Copy, PartialEq, PartialOrd)] 16 struct FreeListBin(u8); 17 18 #[derive(Debug, Clone, Copy)] 19 struct FreeListIndex(usize); 20 21 impl 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))] 36 pub struct FreeRectSlice(pub u32); 37 38 #[cfg_attr(feature = "capture", derive(Serialize))] 39 #[cfg_attr(feature = "replay", derive(Deserialize))] 40 struct FreeRect { 41 slice: FreeRectSlice, 42 rect: DeviceIntRect, 43 } 44 45 #[cfg_attr(feature = "capture", derive(Serialize))] 46 #[cfg_attr(feature = "replay", derive(Deserialize))] 47 struct FreeRectSize { 48 width: i16, 49 height: i16, 50 } 51 52 #[cfg_attr(feature = "capture", derive(Serialize))] 53 #[cfg_attr(feature = "replay", derive(Deserialize))] 54 struct 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))] 74 pub struct GuillotineAllocator { 75 bins: [Bin; NUM_BINS], 76 } 77 78 impl 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)] 223 fn 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] 277 fn test_small() { 278 random_fill(100, 100); 279 } 280 281 #[test] 282 fn test_large() { 283 random_fill(1000, 10000); 284 }