smol_atlas/
lib.rs

1//! Shelf Best Height Fit 2D atlas allocator (Rust port of smol-atlas).
2//!
3//! This crate implements a dynamic 2D atlas allocator using the Shelf Best Height Fit
4//! heuristic. Items are added with `add` and removed with `remove`; shelves are never
5//! merged or resized, and free spans within each shelf are tracked as sorted segments.
6//!
7//! # Example
8//! ```
9//! use smol_atlas::Atlas;
10//!
11//! // Create a 128x128 atlas
12//! let mut atlas = Atlas::new(128, 128);
13//!
14//! // Insert a few items
15//! let a = atlas.add(32, 16).expect("fits");
16//! let b = atlas.add(16, 16).expect("fits");
17//!
18//! // Query positions
19//! let (ax, ay) = (atlas.item_x(a).unwrap(), atlas.item_y(a).unwrap());
20//! let (bx, by) = (atlas.item_x(b).unwrap(), atlas.item_y(b).unwrap());
21//! assert!(ax <= bx || ay <= by);
22//!
23//! // Remove one item and insert another to reuse space
24//! assert!(atlas.remove(a));
25//! let c = atlas.add(32, 16).expect("should reuse free span");
26//! assert_eq!(atlas.item_y(c), Some(ay));
27//! ```
28
29type Dim = u32;
30
31/// Opaque handle to an item stored inside the atlas.
32#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
33pub struct ItemId {
34    idx: u32,
35    generation: u32,
36}
37
38/// Dynamic atlas allocator using the Shelf Best Height Fit heuristic.
39#[derive(Debug)]
40struct ItemSlot {
41    generation: u32,
42    item: Option<Item>,
43}
44
45#[derive(Copy, Clone, Debug)]
46struct Item {
47    x: Dim,
48    y: Dim,
49    width: Dim,
50    height: Dim,
51    shelf_index: usize,
52}
53
54#[derive(Copy, Clone, Debug)]
55struct Span {
56    x: Dim,
57    width: Dim,
58}
59
60#[derive(Debug)]
61struct Shelf {
62    y: Dim,
63    height: Dim,
64    index: usize,
65    free_spans: Vec<Span>,
66}
67
68fn add_dim(a: Dim, b: Dim) -> Dim {
69    a.checked_add(b).expect("dimension overflow")
70}
71
72impl Shelf {
73    fn new(y: Dim, height: Dim, width: Dim, index: usize) -> Self {
74        Shelf {
75            y,
76            height,
77            index,
78            free_spans: vec![Span { x: 0, width }],
79        }
80    }
81
82    fn has_space_for(&self, width: Dim) -> bool {
83        self.free_spans.iter().any(|span| span.width >= width)
84    }
85
86    fn alloc_item(&mut self, width: Dim, height: Dim) -> Option<Item> {
87        if height > self.height {
88            return None;
89        }
90        for i in 0..self.free_spans.len() {
91            if self.free_spans[i].width >= width {
92                let x = self.free_spans[i].x;
93                let rest = self.free_spans[i].width - width;
94                if rest > 0 {
95                    self.free_spans[i].x = add_dim(self.free_spans[i].x, width);
96                    self.free_spans[i].width = rest;
97                } else {
98                    self.free_spans.remove(i);
99                }
100                return Some(Item {
101                    x,
102                    y: self.y,
103                    width,
104                    height,
105                    shelf_index: self.index,
106                });
107            }
108        }
109        None
110    }
111
112    fn free_item(&mut self, item: Item) {
113        self.add_free_span(item.x, item.width);
114    }
115
116    fn add_free_span(&mut self, x: Dim, width: Dim) {
117        if width == 0 {
118            return;
119        }
120        let pos = self.free_spans.partition_point(|span| span.x < x);
121        self.free_spans.insert(pos, Span { x, width });
122        self.merge_free_spans(pos);
123    }
124
125    fn merge_free_spans(&mut self, idx: usize) {
126        if idx + 1 < self.free_spans.len() {
127            let (left, right) = self.free_spans.split_at_mut(idx + 1);
128            let cur = &mut left[idx];
129            let next = &right[0];
130            if add_dim(cur.x, cur.width) == next.x {
131                cur.width = add_dim(cur.width, next.width);
132                self.free_spans.remove(idx + 1);
133            }
134        }
135        if idx > 0 && idx < self.free_spans.len() {
136            let prev_idx = idx - 1;
137            if add_dim(self.free_spans[prev_idx].x, self.free_spans[prev_idx].width)
138                == self.free_spans[idx].x
139            {
140                let width = self.free_spans[idx].width;
141                self.free_spans[prev_idx].width = add_dim(self.free_spans[prev_idx].width, width);
142                self.free_spans.remove(idx);
143            }
144        }
145    }
146}
147
148#[derive(Debug)]
149/// Shelf-based 2D atlas allocator (dimensions are `u32`).
150pub struct Atlas {
151    width: Dim,
152    height: Dim,
153    shelves: Vec<Shelf>,
154    items: Vec<ItemSlot>,
155    free_list: Vec<usize>,
156}
157
158impl Atlas {
159    /// Create a new atlas. Zero dimensions fall back to 64.
160    pub fn new(width: Dim, height: Dim) -> Self {
161        let width = if width > 0 { width } else { 64 };
162        let height = if height > 0 { height } else { 64 };
163        Atlas {
164            width,
165            height,
166            shelves: Vec::with_capacity(8),
167            items: Vec::new(),
168            free_list: Vec::new(),
169        }
170    }
171
172    /// Current atlas width.
173    pub fn width(&self) -> Dim {
174        self.width
175    }
176
177    /// Current atlas height.
178    pub fn height(&self) -> Dim {
179        self.height
180    }
181
182    /// Add a new rectangle of `width` x `height`.
183    ///
184    /// Returns a handle on success, or `None` if it does not fit (even after trying existing free spans).
185    pub fn add(&mut self, width: Dim, height: Dim) -> Option<ItemId> {
186        if width == 0 || height == 0 {
187            return None;
188        }
189
190        let mut best_shelf: Option<usize> = None;
191        let mut best_score = Dim::MAX;
192        let mut top_y: Dim = 0;
193
194        for i in 0..self.shelves.len() {
195            let shelf_height = self.shelves[i].height;
196            top_y = top_y.max(add_dim(self.shelves[i].y, shelf_height));
197            if shelf_height < height {
198                continue;
199            }
200            if shelf_height == height {
201                if let Some(id) = self.alloc_on_shelf(i, width, height) {
202                    return Some(id);
203                }
204            } else {
205                let score = shelf_height - height;
206                if score < best_score && self.shelves[i].has_space_for(width) {
207                    best_score = score;
208                    best_shelf = Some(i);
209                }
210            }
211        }
212
213        if let Some(idx) = best_shelf
214            && let Some(id) = self.alloc_on_shelf(idx, width, height) {
215                return Some(id);
216            }
217
218        if width <= self.width && add_dim(top_y, height) <= self.height {
219            let shelf_index = self.shelves.len();
220            self.shelves
221                .push(Shelf::new(top_y, height, self.width, shelf_index));
222            return self.alloc_on_shelf(shelf_index, width, height);
223        }
224
225        None
226    }
227
228    fn alloc_on_shelf(&mut self, shelf_index: usize, width: Dim, height: Dim) -> Option<ItemId> {
229        let item = {
230            let shelf = &mut self.shelves[shelf_index];
231            shelf.alloc_item(width, height)?
232        };
233        Some(self.store_item(item))
234    }
235
236    fn store_item(&mut self, item: Item) -> ItemId {
237        if let Some(idx) = self.free_list.pop() {
238            let slot = &mut self.items[idx];
239            slot.item = Some(item);
240            slot.generation = slot.generation.wrapping_add(1);
241            ItemId {
242                idx: idx as u32,
243                generation: slot.generation,
244            }
245        } else {
246            let generation = 1;
247            self.items.push(ItemSlot {
248                generation,
249                item: Some(item),
250            });
251            ItemId {
252                idx: (self.items.len() - 1) as u32,
253                generation,
254            }
255        }
256    }
257
258    /// Remove an item by handle. Returns `true` if the handle was valid and the item was removed.
259    pub fn remove(&mut self, id: ItemId) -> bool {
260        let idx = id.idx as usize;
261        if let Some(slot) = self.items.get_mut(idx)
262            && slot.generation == id.generation
263                && let Some(item) = slot.item.take() {
264                    self.shelves[item.shelf_index].free_item(item);
265                    slot.generation = slot.generation.wrapping_add(1);
266                    self.free_list.push(idx);
267                    return true;
268                }
269        false
270    }
271
272    /// Clear the atlas, invalidating all handles, and optionally resize.
273    pub fn clear(&mut self, new_width: Option<Dim>, new_height: Option<Dim>) {
274        if let Some(w) = new_width
275            && w > 0 {
276                self.width = w;
277            }
278        if let Some(h) = new_height
279            && h > 0 {
280                self.height = h;
281            }
282        self.shelves.clear();
283        self.free_list.clear();
284        for (i, slot) in self.items.iter_mut().enumerate() {
285            slot.item = None;
286            slot.generation = slot.generation.wrapping_add(1);
287            self.free_list.push(i);
288        }
289    }
290
291    /// Get item X coordinate for a valid handle.
292    pub fn item_x(&self, id: ItemId) -> Option<Dim> {
293        self.item(id).map(|item| item.x)
294    }
295
296    /// Get item Y coordinate for a valid handle.
297    pub fn item_y(&self, id: ItemId) -> Option<Dim> {
298        self.item(id).map(|item| item.y)
299    }
300
301    /// Get item width for a valid handle.
302    pub fn item_width(&self, id: ItemId) -> Option<Dim> {
303        self.item(id).map(|item| item.width)
304    }
305
306    /// Get item height for a valid handle.
307    pub fn item_height(&self, id: ItemId) -> Option<Dim> {
308        self.item(id).map(|item| item.height)
309    }
310
311    fn item(&self, id: ItemId) -> Option<&Item> {
312        let idx = id.idx as usize;
313        let slot = self.items.get(idx)?;
314        if slot.generation == id.generation {
315            slot.item.as_ref()
316        } else {
317            None
318        }
319    }
320}
321
322#[cfg(test)]
323mod tests {
324    use super::*;
325
326    fn check_item(atlas: &Atlas, id: ItemId, x: Dim, y: Dim, w: Dim, h: Dim) {
327        assert_eq!(Some(x), atlas.item_x(id));
328        assert_eq!(Some(y), atlas.item_y(id));
329        assert_eq!(Some(w), atlas.item_width(id));
330        assert_eq!(Some(h), atlas.item_height(id));
331    }
332
333    #[test]
334    fn invalid_item_when_out_of_space() {
335        let mut atlas = Atlas::new(64, 64);
336        let e1 = atlas.add(40, 16).unwrap();
337        let e2 = atlas.add(24, 16).unwrap();
338        check_item(&atlas, e1, 0, 0, 40, 16);
339        check_item(&atlas, e2, 40, 0, 24, 16);
340
341        let e3 = atlas.add(32, 48).unwrap();
342        let e4 = atlas.add(32, 48).unwrap();
343        check_item(&atlas, e3, 0, 16, 32, 48);
344        check_item(&atlas, e4, 32, 16, 32, 48);
345
346        let e5 = atlas.add(1, 1);
347        assert!(e5.is_none());
348    }
349
350    #[test]
351    fn same_height_on_same_shelf() {
352        let mut atlas = Atlas::new(64, 64);
353        let e1 = atlas.add(10, 10).unwrap();
354        let e2 = atlas.add(10, 10).unwrap();
355        let e3 = atlas.add(10, 10).unwrap();
356        check_item(&atlas, e1, 0, 0, 10, 10);
357        check_item(&atlas, e2, 10, 0, 10, 10);
358        check_item(&atlas, e3, 20, 0, 10, 10);
359    }
360
361    #[test]
362    fn larger_height_new_shelf() {
363        let mut atlas = Atlas::new(64, 64);
364        let e1 = atlas.add(10, 10).unwrap();
365        let e2 = atlas.add(10, 15).unwrap();
366        let e3 = atlas.add(10, 20).unwrap();
367        check_item(&atlas, e1, 0, 0, 10, 10);
368        check_item(&atlas, e2, 0, 10, 10, 15);
369        check_item(&atlas, e3, 0, 25, 10, 20);
370    }
371
372    #[test]
373    fn shorter_height_existing_best_shelf() {
374        let mut atlas = Atlas::new(64, 64);
375        let e1 = atlas.add(10, 10).unwrap();
376        let e2 = atlas.add(10, 15).unwrap();
377        let e3 = atlas.add(10, 20).unwrap();
378        let e4 = atlas.add(10, 9).unwrap();
379        check_item(&atlas, e1, 0, 0, 10, 10);
380        check_item(&atlas, e2, 0, 10, 10, 15);
381        check_item(&atlas, e3, 0, 25, 10, 20);
382        check_item(&atlas, e4, 10, 0, 10, 9);
383    }
384
385    #[test]
386    fn pack_uses_free_space() {
387        let mut atlas = Atlas::new(64, 64);
388        let _e1 = atlas.add(10, 10).unwrap();
389        let e2 = atlas.add(10, 10).unwrap();
390        let _e3 = atlas.add(10, 10).unwrap();
391
392        assert!(atlas.remove(e2));
393        let e4 = atlas.add(10, 10).unwrap();
394        check_item(&atlas, e4, 10, 0, 10, 10);
395    }
396
397    #[test]
398    fn pack_uses_least_wasteful_free_space() {
399        let mut atlas = Atlas::new(64, 64);
400        let e1 = atlas.add(10, 10).unwrap();
401        let e2 = atlas.add(10, 15).unwrap();
402        let e3 = atlas.add(10, 20).unwrap();
403
404        atlas.remove(e3);
405        atlas.remove(e2);
406        atlas.remove(e1);
407
408        let e4 = atlas.add(10, 13).unwrap();
409        check_item(&atlas, e4, 0, 10, 10, 13);
410    }
411
412    #[test]
413    fn pack_makes_new_shelf_if_free_entries_more_wasteful() {
414        let mut atlas = Atlas::new(64, 64);
415        let e1 = atlas.add(10, 10).unwrap();
416        let e2 = atlas.add(10, 15).unwrap();
417        atlas.remove(e2);
418        let e3 = atlas.add(10, 10).unwrap();
419        check_item(&atlas, e1, 0, 0, 10, 10);
420        check_item(&atlas, e3, 10, 0, 10, 10);
421    }
422
423    #[test]
424    fn pack_considers_max_dimensions_for_space_reuse() {
425        let mut atlas = Atlas::new(64, 64);
426        let _ = atlas.add(10, 10).unwrap();
427        let e2 = atlas.add(10, 15).unwrap();
428
429        atlas.remove(e2);
430
431        let e3 = atlas.add(10, 13).unwrap();
432        check_item(&atlas, e3, 0, 10, 10, 13);
433
434        atlas.remove(e3);
435
436        let e4 = atlas.add(10, 14).unwrap();
437        check_item(&atlas, e4, 0, 10, 10, 14);
438    }
439
440    #[test]
441    fn pack_results_minimal_size() {
442        let mut atlas = Atlas::new(30, 45);
443
444        let res0 = atlas.add(10, 10).unwrap();
445        let res1 = atlas.add(5, 15).unwrap();
446        let res2 = atlas.add(25, 15).unwrap();
447        let res3 = atlas.add(10, 20).unwrap();
448
449        check_item(&atlas, res0, 0, 0, 10, 10);
450        check_item(&atlas, res1, 0, 10, 5, 15);
451        check_item(&atlas, res2, 5, 10, 25, 15);
452        check_item(&atlas, res3, 0, 25, 10, 20);
453
454        assert_eq!(30, atlas.width());
455        assert_eq!(45, atlas.height());
456    }
457
458    #[test]
459    fn pack_shelf_coalescing() {
460        let mut atlas = Atlas::new(100, 10);
461
462        let r_a = atlas.add(10, 10).unwrap();
463        let r_b = atlas.add(20, 10).unwrap();
464        let r_c = atlas.add(10, 10).unwrap();
465        let r_d = atlas.add(40, 10).unwrap();
466        check_item(&atlas, r_a, 0, 0, 10, 10);
467        check_item(&atlas, r_b, 10, 0, 20, 10);
468        check_item(&atlas, r_c, 30, 0, 10, 10);
469        check_item(&atlas, r_d, 40, 0, 40, 10);
470
471        atlas.remove(r_a);
472        atlas.remove(r_c);
473        atlas.remove(r_b);
474
475        let r_e = atlas.add(30, 10).unwrap();
476        check_item(&atlas, r_e, 0, 0, 30, 10);
477
478        atlas.remove(r_d);
479        atlas.remove(r_e);
480
481        let r_f = atlas.add(90, 10).unwrap();
482        check_item(&atlas, r_f, 0, 0, 90, 10);
483
484        assert_eq!(100, atlas.width());
485        assert_eq!(10, atlas.height());
486    }
487
488    #[test]
489    fn clear_keeps_size_or_resizes() {
490        let mut atlas = Atlas::new(10, 10);
491        let e1 = atlas.add(10, 10).unwrap();
492        check_item(&atlas, e1, 0, 0, 10, 10);
493
494        atlas.clear(None, None);
495
496        let e2 = atlas.add(10, 5).unwrap();
497        let e3 = atlas.add(5, 5).unwrap();
498        let e4 = atlas.add(5, 5).unwrap();
499        check_item(&atlas, e2, 0, 0, 10, 5);
500        check_item(&atlas, e3, 0, 5, 5, 5);
501        check_item(&atlas, e4, 5, 5, 5, 5);
502        assert!(atlas.add(1, 1).is_none());
503
504        atlas.clear(Some(10), Some(11));
505
506        let e2 = atlas.add(10, 5).unwrap();
507        let e3 = atlas.add(5, 5).unwrap();
508        let e4 = atlas.add(5, 5).unwrap();
509        check_item(&atlas, e2, 0, 0, 10, 5);
510        check_item(&atlas, e3, 0, 5, 5, 5);
511        check_item(&atlas, e4, 5, 5, 5, 5);
512        let e5 = atlas.add(1, 1).unwrap();
513        check_item(&atlas, e5, 0, 10, 1, 1);
514    }
515}
smol_atlas/lib.rs

smol_atlas/
lib.rs
