65 |
65 |
66 pub struct Atlas { |
66 pub struct Atlas { |
67 size: Size, |
67 size: Size, |
68 free_rects: Vec<Rect>, |
68 free_rects: Vec<Rect>, |
69 used_rects: Vec<Rect>, |
69 used_rects: Vec<Rect>, |
|
70 splits: Vec<Rect>, |
70 } |
71 } |
71 |
72 |
72 impl Atlas { |
73 impl Atlas { |
73 pub fn new(size: Size) -> Self { |
74 pub fn new(size: Size) -> Self { |
74 Self { |
75 Self { |
75 size, |
76 size, |
76 free_rects: vec![Rect::at_origin(size)], |
77 free_rects: vec![Rect::at_origin(size)], |
77 used_rects: vec![], |
78 used_rects: vec![], |
|
79 splits: vec![], |
78 } |
80 } |
79 } |
81 } |
80 |
82 |
81 pub fn size(&self) -> Size { |
83 pub fn size(&self) -> Size { |
82 self.size |
84 self.size |
112 } else { |
114 } else { |
113 Some((best_rect, best_fit)) |
115 Some((best_rect, best_fit)) |
114 } |
116 } |
115 } |
117 } |
116 |
118 |
117 fn prune(&mut self) { |
|
118 self.free_rects = self |
|
119 .free_rects |
|
120 .iter() |
|
121 .filter(|inner| { |
|
122 self.free_rects |
|
123 .iter() |
|
124 .all(|outer| outer == *inner || !outer.contains_rect(inner)) |
|
125 }) |
|
126 .cloned() |
|
127 .collect(); |
|
128 } |
|
129 |
|
130 fn split_insert(&mut self, rect: Rect) { |
119 fn split_insert(&mut self, rect: Rect) { |
131 let mut splits = vec![]; |
120 let mut splits = std::mem::replace(&mut self.splits, vec![]); |
|
121 let mut buffer = [Rect::EMPTY; 4]; |
132 |
122 |
133 for i in (0..self.free_rects.len()).rev() { |
123 for i in (0..self.free_rects.len()).rev() { |
134 if split_rect(self.free_rects[i], rect, &mut splits) { |
124 if let Some(count) = split_rect(self.free_rects[i], rect, &mut splits, &mut buffer) { |
135 self.free_rects.swap_remove(i as usize); |
125 self.free_rects.swap_remove(i as usize); |
136 } |
126 splits.extend_from_slice(&buffer[0..count]); |
137 } |
127 } |
138 |
128 } |
139 self.free_rects.extend(splits); |
129 |
140 self.prune(); |
130 filter_swap_remove(&mut splits, |s| { |
|
131 self.free_rects.iter().any(|r| r.contains_rect(s)) |
|
132 }); |
|
133 self.free_rects.extend(splits.drain(..)); |
|
134 std::mem::replace(&mut self.splits, splits); |
|
135 |
141 self.used_rects.push(rect); |
136 self.used_rects.push(rect); |
142 } |
137 } |
143 |
138 |
144 pub fn insert(&mut self, size: Size) -> Option<Rect> { |
139 pub fn insert(&mut self, size: Size) -> Option<Rect> { |
145 let (rect, _) = self.find_position(size)?; |
140 let (rect, _) = self.find_position(size)?; |
218 true |
213 true |
219 } |
214 } |
220 } |
215 } |
221 } |
216 } |
222 |
217 |
223 fn split_rect(free_rect: Rect, rect: Rect, output: &mut Vec<Rect>) -> bool { |
218 #[inline] |
|
219 fn filter_swap_remove<T, F>(vec: &mut Vec<T>, predicate: F) |
|
220 where |
|
221 F: Fn(&T) -> bool, |
|
222 { |
|
223 let mut i = 0; |
|
224 while i < vec.len() { |
|
225 if predicate(&vec[i]) { |
|
226 vec.swap_remove(i); |
|
227 } else { |
|
228 i += 1; |
|
229 } |
|
230 } |
|
231 } |
|
232 |
|
233 #[inline] |
|
234 fn prune_push( |
|
235 previous_splits: &mut Vec<Rect>, |
|
236 buffer: &mut [Rect; 4], |
|
237 buffer_size: &mut usize, |
|
238 rect: Rect, |
|
239 ) { |
|
240 if !previous_splits.iter().any(|r| r.contains_rect(&rect)) { |
|
241 filter_swap_remove(previous_splits, |s| rect.contains_rect(s)); |
|
242 buffer[*buffer_size] = rect; |
|
243 *buffer_size += 1; |
|
244 } |
|
245 } |
|
246 |
|
247 fn split_rect( |
|
248 free_rect: Rect, |
|
249 rect: Rect, |
|
250 previous_splits: &mut Vec<Rect>, |
|
251 buffer: &mut [Rect; 4], |
|
252 ) -> Option<usize> { |
|
253 let mut buffer_size = 0usize; |
224 let split = free_rect.intersects(&rect); |
254 let split = free_rect.intersects(&rect); |
225 if split { |
255 if split { |
226 if rect.left() > free_rect.left() { |
256 if rect.left() > free_rect.left() { |
227 let trim = free_rect.right() - rect.left() + 1; |
257 let trim = free_rect.right() - rect.left() + 1; |
228 output.push(free_rect.with_margins(0, -trim, 0, 0)) |
258 prune_push( |
|
259 previous_splits, |
|
260 buffer, |
|
261 &mut buffer_size, |
|
262 free_rect.with_margins(0, -trim, 0, 0), |
|
263 ); |
229 } |
264 } |
230 if rect.right() < free_rect.right() { |
265 if rect.right() < free_rect.right() { |
231 let trim = rect.right() - free_rect.left() + 1; |
266 let trim = rect.right() - free_rect.left() + 1; |
232 output.push(free_rect.with_margins(-trim, 0, 0, 0)) |
267 prune_push( |
|
268 previous_splits, |
|
269 buffer, |
|
270 &mut buffer_size, |
|
271 free_rect.with_margins(-trim, 0, 0, 0), |
|
272 ); |
233 } |
273 } |
234 if rect.top() > free_rect.top() { |
274 if rect.top() > free_rect.top() { |
235 let trim = free_rect.bottom() - rect.top() + 1; |
275 let trim = free_rect.bottom() - rect.top() + 1; |
236 output.push(free_rect.with_margins(0, 0, 0, -trim)); |
276 prune_push( |
|
277 previous_splits, |
|
278 buffer, |
|
279 &mut buffer_size, |
|
280 free_rect.with_margins(0, 0, 0, -trim), |
|
281 );; |
237 } |
282 } |
238 if rect.bottom() < free_rect.bottom() { |
283 if rect.bottom() < free_rect.bottom() { |
239 let trim = rect.bottom() - free_rect.top() + 1; |
284 let trim = rect.bottom() - free_rect.top() + 1; |
240 output.push(free_rect.with_margins(0, 0, -trim, 0)); |
285 prune_push( |
241 } |
286 previous_splits, |
242 } |
287 buffer, |
243 split |
288 &mut buffer_size, |
|
289 free_rect.with_margins(0, 0, -trim, 0), |
|
290 );; |
|
291 } |
|
292 } |
|
293 if split { |
|
294 Some(buffer_size) |
|
295 } else { |
|
296 None |
|
297 } |
244 } |
298 } |
245 |
299 |
246 #[cfg(test)] |
300 #[cfg(test)] |
247 mod tests { |
301 mod tests { |
248 use super::Atlas; |
302 use super::Atlas; |