1 use integral_geometry::{Rect, Size}; |
1 use integral_geometry::{Rect, Size}; |
2 use std::cmp::{max, min, Ordering}; |
2 use itertools::Itertools; |
|
3 use std::{ |
|
4 cmp::{max, min, Ordering}, |
|
5 ops::Index, |
|
6 }; |
3 |
7 |
4 #[derive(PartialEq, Eq, PartialOrd, Ord, Clone)] |
8 #[derive(PartialEq, Eq, PartialOrd, Ord, Clone)] |
5 struct Fit { |
9 struct Fit { |
6 short_side: u32, |
10 short_side: u32, |
7 long_side: u32, |
11 long_side: u32, |
83 pub fn size(&self) -> Size { |
91 pub fn size(&self) -> Size { |
84 self.size |
92 self.size |
85 } |
93 } |
86 |
94 |
87 pub fn used_space(&self) -> UsedSpace { |
95 pub fn used_space(&self) -> UsedSpace { |
88 let used = self.used_rects.iter().map(|r| r.size().area()).sum(); |
96 let used = self.used_rects.iter().map(|(r, _)| r.size().area()).sum(); |
89 UsedSpace::new(used, self.size.area()) |
97 UsedSpace::new(used, self.size.area()) |
90 } |
98 } |
91 |
99 |
92 fn find_position(&self, size: Size) -> Option<(Rect, Fit)> { |
100 fn find_position(&self, size: Size) -> Option<(Rect, Fit)> { |
93 let mut best_rect = Rect::EMPTY; |
101 let mut best_rect = Rect::EMPTY; |
114 } else { |
122 } else { |
115 Some((best_rect, best_fit)) |
123 Some((best_rect, best_fit)) |
116 } |
124 } |
117 } |
125 } |
118 |
126 |
119 fn split_insert(&mut self, rect: Rect) { |
127 fn split_insert(&mut self, rect: Rect, value: T) { |
120 let mut splits = std::mem::replace(&mut self.splits, vec![]); |
128 let mut splits = std::mem::replace(&mut self.splits, vec![]); |
121 let mut buffer = [Rect::EMPTY; 4]; |
129 let mut buffer = [Rect::EMPTY; 4]; |
122 |
130 |
123 for i in (0..self.free_rects.len()).rev() { |
131 for i in (0..self.free_rects.len()).rev() { |
124 if let Some(count) = split_rect(self.free_rects[i], rect, &mut splits, &mut buffer) { |
132 if let Some(count) = split_rect(self.free_rects[i], rect, &mut splits, &mut buffer) { |
131 self.free_rects.iter().any(|r| r.contains_rect(s)) |
139 self.free_rects.iter().any(|r| r.contains_rect(s)) |
132 }); |
140 }); |
133 self.free_rects.extend(splits.drain(..)); |
141 self.free_rects.extend(splits.drain(..)); |
134 std::mem::replace(&mut self.splits, splits); |
142 std::mem::replace(&mut self.splits, splits); |
135 |
143 |
136 self.used_rects.push(rect); |
144 self.used_rects.push((rect, value)); |
137 } |
145 } |
138 |
146 |
139 pub fn insert(&mut self, size: Size) -> Option<Rect> { |
147 pub fn insert(&mut self, size: Size, value: T) -> Option<Rect> { |
140 let (rect, _) = self.find_position(size)?; |
148 let (rect, _) = self.find_position(size)?; |
141 self.split_insert(rect); |
149 self.split_insert(rect, value); |
142 Some(rect) |
150 Some(rect) |
143 } |
151 } |
144 |
152 |
145 pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<Rect> |
153 pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<(Rect, T)> |
146 where |
154 where |
147 Iter: Iterator<Item = Size>, |
155 Iter: Iterator<Item = (Size, T)>, |
148 { |
156 { |
149 let mut sizes: Vec<_> = sizes.collect(); |
157 let mut sizes: Vec<_> = sizes.collect(); |
150 let mut result = vec![]; |
158 let mut result = Vec::with_capacity(sizes.len()); |
151 |
159 |
152 while let Some((index, (rect, _))) = sizes |
160 while let Some((index, (rect, _), value)) = sizes |
153 .iter() |
161 .iter() |
154 .enumerate() |
162 .enumerate() |
155 .filter_map(|(i, s)| self.find_position(*s).map(|res| (i, res))) |
163 .filter_map(|(i, (s, v))| self.find_position(*s).map(|res| (i, res, v))) |
156 .min_by_key(|(_, (_, fit))| fit.clone()) |
164 .min_by_key(|(_, (_, fit), _)| fit.clone()) |
157 { |
165 { |
158 self.split_insert(rect); |
166 self.split_insert(rect, *value); |
159 |
167 |
160 result.push(rect); |
168 result.push((rect, *value)); |
161 sizes.swap_remove(index); |
169 sizes.swap_remove(index); |
162 } |
170 } |
163 result |
171 result |
164 } |
172 } |
165 |
173 |
168 self.used_rects.clear(); |
176 self.used_rects.clear(); |
169 self.free_rects.push(Rect::at_origin(self.size)); |
177 self.free_rects.push(Rect::at_origin(self.size)); |
170 } |
178 } |
171 } |
179 } |
172 |
180 |
|
181 pub type SpriteIndex = u32; |
|
182 pub type SpriteLocation = (u32, Rect); |
|
183 |
173 pub struct AtlasCollection { |
184 pub struct AtlasCollection { |
|
185 next_index: SpriteIndex, |
174 texture_size: Size, |
186 texture_size: Size, |
175 atlases: Vec<Atlas>, |
187 atlases: Vec<Atlas<SpriteIndex>>, |
|
188 rects: Vec<SpriteLocation>, |
176 } |
189 } |
177 |
190 |
178 impl AtlasCollection { |
191 impl AtlasCollection { |
179 pub fn new(texture_size: Size) -> Self { |
192 pub fn new(texture_size: Size) -> Self { |
180 Self { |
193 Self { |
|
194 next_index: 0, |
181 texture_size, |
195 texture_size, |
182 atlases: vec![], |
196 atlases: vec![], |
|
197 rects: vec![], |
183 } |
198 } |
184 } |
199 } |
185 |
200 |
186 fn repack(&mut self, size: Size) -> bool { |
201 fn repack(&mut self, size: Size) -> bool { |
187 for atlas in &mut self.atlases { |
202 for (atlas_index, atlas) in self.atlases.iter_mut().enumerate() { |
188 let mut temp_atlas = Atlas::new(atlas.size()); |
203 if atlas.used_space().free() >= size.area() { |
189 let sizes = atlas |
204 let mut temp_atlas = Atlas::new(atlas.size()); |
190 .used_rects |
205 let sizes = atlas |
191 .iter() |
206 .used_rects |
192 .map(|r| r.size()) |
207 .iter() |
193 .chain(std::iter::once(size)); |
208 .map(|(r, v)| (r.size(), *v)) |
194 if !temp_atlas.insert_set(sizes).is_empty() { |
209 .chain(std::iter::once((size, self.next_index))); |
195 std::mem::swap(atlas, &mut temp_atlas); |
210 let inserts = temp_atlas.insert_set(sizes); |
196 return true; |
211 if inserts.len() > atlas.used_rects.len() { |
|
212 self.rects.push((0, Rect::EMPTY)); |
|
213 for (rect, index) in inserts { |
|
214 self.rects[index as usize] = (atlas_index as u32, rect); |
|
215 } |
|
216 std::mem::swap(atlas, &mut temp_atlas); |
|
217 return true; |
|
218 } |
197 } |
219 } |
198 } |
220 } |
199 false |
221 false |
200 } |
222 } |
201 |
223 |
202 pub fn insert_sprite(&mut self, size: Size) -> bool { |
224 #[inline] |
|
225 fn consume_index(&mut self) -> Option<SpriteIndex> { |
|
226 let result = Some(self.next_index); |
|
227 self.next_index += 1; |
|
228 result |
|
229 } |
|
230 |
|
231 pub fn insert_sprite(&mut self, size: Size) -> Option<SpriteIndex> { |
203 if !self.texture_size.contains(size) { |
232 if !self.texture_size.contains(size) { |
204 false |
233 None |
205 } else { |
234 } else { |
206 if let Some(rect) = self.atlases.iter_mut().find_map(|a| a.insert(size)) { |
235 let index = self.next_index; |
207 |
236 if let Some(index_rect) = self |
|
237 .atlases |
|
238 .iter_mut() |
|
239 .enumerate() |
|
240 .find_map(|(i, a)| a.insert(size, index).map(|r| (i as u32, r))) |
|
241 { |
|
242 self.rects.push(index_rect); |
208 } else if !self.repack(size) { |
243 } else if !self.repack(size) { |
209 let mut atlas = Atlas::new(self.texture_size); |
244 let mut atlas = Atlas::new(self.texture_size); |
210 atlas.insert(size); |
245 let rect = atlas.insert(size, index)?; |
211 self.atlases.push(atlas); |
246 self.atlases.push(atlas); |
|
247 self.rects.push(((self.atlases.len() - 1) as u32, rect)) |
212 } |
248 } |
213 true |
249 self.consume_index() |
214 } |
250 } |
|
251 } |
|
252 } |
|
253 |
|
254 impl Index<SpriteIndex> for AtlasCollection { |
|
255 type Output = SpriteLocation; |
|
256 |
|
257 #[inline] |
|
258 fn index(&self, index: SpriteIndex) -> &Self::Output { |
|
259 &self.rects[index as usize] |
215 } |
260 } |
216 } |
261 } |
217 |
262 |
218 #[inline] |
263 #[inline] |
219 fn filter_swap_remove<T, F>(vec: &mut Vec<T>, predicate: F) |
264 fn filter_swap_remove<T, F>(vec: &mut Vec<T>, predicate: F) |
307 #[test] |
352 #[test] |
308 fn insert() { |
353 fn insert() { |
309 let atlas_size = Size::square(16); |
354 let atlas_size = Size::square(16); |
310 let mut atlas = Atlas::new(atlas_size); |
355 let mut atlas = Atlas::new(atlas_size); |
311 |
356 |
312 assert_eq!(None, atlas.insert(Size::square(20))); |
357 assert_eq!(None, atlas.insert(Size::square(20), ())); |
313 |
358 |
314 let rect_size = Size::new(11, 3); |
359 let rect_size = Size::new(11, 3); |
315 let rect = atlas.insert(rect_size).unwrap(); |
360 let rect = atlas.insert(rect_size, ()).unwrap(); |
316 |
361 |
317 assert_eq!(rect, Rect::at_origin(rect_size)); |
362 assert_eq!(rect, Rect::at_origin(rect_size)); |
318 assert_eq!(2, atlas.free_rects.len()); |
363 assert_eq!(2, atlas.free_rects.len()); |
319 } |
364 } |
320 |
365 |
363 proptest! { |
414 proptest! { |
364 #[test] |
415 #[test] |
365 fn prop_insert(rects in Vec::<TestRect>::arbitrary()) { |
416 fn prop_insert(rects in Vec::<TestRect>::arbitrary()) { |
366 let container = Rect::at_origin(Size::square(2048)); |
417 let container = Rect::at_origin(Size::square(2048)); |
367 let mut atlas = Atlas::new(container.size()); |
418 let mut atlas = Atlas::new(container.size()); |
368 let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size)).collect(); |
419 let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size, ())).collect(); |
369 |
420 |
370 let mut inserted_pairs = inserted.iter().cartesian_product(inserted.iter()); |
421 let mut inserted_pairs = inserted.iter().cartesian_product(inserted.iter()); |
371 |
422 |
372 assert!(inserted.iter().all(|r| container.contains_rect(r))); |
423 assert!(inserted.iter().all(|r| container.contains_rect(r))); |
373 assert!(inserted_pairs.all(|(r1, r2)| r1 == r2 || r1 != r2 && !r1.intersects(r2))); |
424 assert!(inserted_pairs.all(|(r1, r2)| r1 == r2 || r1 != r2 && !r1.intersects(r2))); |
382 fn prop_insert_set(rects in Vec::<TestRect>::arbitrary()) { |
433 fn prop_insert_set(rects in Vec::<TestRect>::arbitrary()) { |
383 let container = Rect::at_origin(Size::square(2048)); |
434 let container = Rect::at_origin(Size::square(2048)); |
384 let mut atlas = Atlas::new(container.size()); |
435 let mut atlas = Atlas::new(container.size()); |
385 let mut set_atlas = Atlas::new(container.size()); |
436 let mut set_atlas = Atlas::new(container.size()); |
386 |
437 |
387 let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size)).collect(); |
438 let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size, ())).collect(); |
388 let set_inserted: Vec<_> = set_atlas.insert_set(rects.iter().map(|TestRect(size)| *size)); |
439 let set_inserted: Vec<_> = set_atlas.insert_set(rects.iter().map(|TestRect(size)| (*size, ()))); |
389 |
440 |
390 let mut set_inserted_pairs = set_inserted.iter().cartesian_product(set_inserted.iter()); |
441 let mut set_inserted_pairs = set_inserted.iter().cartesian_product(set_inserted.iter()); |
391 |
442 |
392 assert!(set_inserted_pairs.all(|(r1, r2)| r1 == r2 || r1 != r2 && !r1.intersects(r2))); |
443 assert!(set_inserted_pairs.all(|((r1, _), (r2, _))| r1 == r2 || r1 != r2 && !r1.intersects(r2))); |
393 assert!(set_atlas.used_space().used() <= atlas.used_space().used()); |
444 assert!(set_atlas.used_space().used() <= atlas.used_space().used()); |
394 |
445 |
395 assert_eq!(sum_area(&set_inserted), sum_area(&inserted)); |
446 assert_eq!(sum_area(&set_inserted), sum_area(&inserted)); |
396 } |
447 } |
397 } |
448 } |