etagere/
allocator.rs

1use crate::{AllocId, Allocation, AllocatorOptions, DEFAULT_OPTIONS, Size, Rectangle, point2, size2};
2
3const SHELF_SPLIT_THRESHOLD: u16 = 8;
4const ITEM_SPLIT_THRESHOLD: u16 = 8;
5
6#[repr(transparent)]
7#[derive(Copy, Clone, Debug, PartialEq, Eq)]
8#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
9struct ShelfIndex(u16);
10
11impl ShelfIndex {
12    const NONE: Self = ShelfIndex(std::u16::MAX);
13
14    fn index(self) -> usize { self.0 as usize }
15
16    fn is_some(self) -> bool { self.0 != std::u16::MAX }
17
18    fn is_none(self) -> bool { self.0 == std::u16::MAX }
19}
20
21#[repr(transparent)]
22#[derive(Copy, Clone, Debug, PartialEq, Eq)]
23#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
24struct ItemIndex(u16);
25
26impl ItemIndex {
27    const NONE: Self = ItemIndex(std::u16::MAX);
28
29    fn index(self) -> usize { self.0 as usize }
30
31    fn is_some(self) -> bool { self.0 != std::u16::MAX }
32
33    fn is_none(self) -> bool { self.0 == std::u16::MAX }
34}
35
36#[derive(Clone)]
37#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
38struct Shelf {
39    x: u16,
40    y: u16,
41    height: u16,
42    prev: ShelfIndex,
43    next: ShelfIndex,
44    first_item: ItemIndex,
45    first_unallocated: ItemIndex,
46    is_empty: bool,
47}
48
49#[derive(Clone)]
50#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
51struct Item {
52    x: u16,
53    width: u16,
54    prev: ItemIndex,
55    next: ItemIndex,
56    prev_unallocated: ItemIndex,
57    next_unallocated: ItemIndex,
58    shelf: ShelfIndex,
59    allocated: bool,
60    generation: u16,
61}
62
63// Note: if allocating is slow we can use the guillotiere trick of storing multiple lists of free
64// rects (per shelf height) instead of iterating the shelves and items.
65
66/// A shelf-packing dynamic texture atlas allocator tracking each allocation individually and with support
67/// for coalescing empty shelves.
68#[derive(Clone)]
69#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
70pub struct AtlasAllocator {
71    shelves: Vec<Shelf>,
72    items: Vec<Item>,
73    alignment: Size,
74    flip_xy: bool,
75    size: Size,
76    first_shelf: ShelfIndex,
77    free_items: ItemIndex,
78    free_shelves: ShelfIndex,
79    shelf_width: u16,
80    allocated_space: i32,
81}
82
83impl AtlasAllocator {
84    /// Create an atlas allocator with provided options.
85    pub fn with_options(size: Size, options: &AllocatorOptions) -> Self {
86        let (shelf_alignment, width, height) = if options.vertical_shelves {
87            (options.alignment.height, size.height, size.width)
88        } else {
89            (options.alignment.width, size.width, size.height)
90        };
91        let mut shelf_width = width / options.num_columns;
92        shelf_width -= shelf_width % shelf_alignment;
93
94        let mut atlas = AtlasAllocator {
95            shelves: Vec::new(),
96            items: Vec::new(),
97            size: size2(width, height),
98            alignment: options.alignment,
99            flip_xy: options.vertical_shelves,
100            first_shelf: ShelfIndex(0),
101            free_items: ItemIndex::NONE,
102            free_shelves: ShelfIndex::NONE,
103            shelf_width: shelf_width as u16,
104            allocated_space: 0,
105        };
106
107        atlas.init();
108
109        atlas
110    }
111
112    /// Create an atlas allocator with default options.
113    pub fn new(size: Size) -> Self {
114        Self::with_options(size, &DEFAULT_OPTIONS)
115    }
116
117    pub fn clear(&mut self) {
118        self.init();
119    }
120
121    fn init(&mut self) {
122        assert!(self.size.width > 0);
123        assert!(self.size.height > 0);
124        assert!(self.size.width <= std::u16::MAX as i32);
125        assert!(self.size.height <= std::u16::MAX as i32);
126        assert!(
127            self.size.width.checked_mul(self.size.height).is_some(),
128            "The area of the atlas must fit in a i32 value"
129        );
130
131        assert!(self.alignment.width > 0);
132        assert!(self.alignment.height > 0);
133
134        self.shelves.clear();
135        self.items.clear();
136
137        let num_columns = self.size.width as u16 / self.shelf_width;
138
139        let mut prev = ShelfIndex::NONE;
140        for i in 0..num_columns {
141            let first_item = ItemIndex(self.items.len() as u16);
142            let x = i * self.shelf_width;
143            let current = ShelfIndex(i);
144            let next = if i + 1 < num_columns { ShelfIndex(i + 1) } else { ShelfIndex::NONE };
145
146            self.shelves.push(Shelf {
147                x,
148                y: 0,
149                height: self.size.height as u16,
150                prev,
151                next,
152                is_empty: true,
153                first_item,
154                first_unallocated: first_item,
155            });
156
157            self.items.push(Item {
158                x,
159                width: self.shelf_width,
160                prev: ItemIndex::NONE,
161                next: ItemIndex::NONE,
162                prev_unallocated: ItemIndex::NONE,
163                next_unallocated: ItemIndex::NONE,
164                shelf: current,
165                allocated: false,
166                generation: 1,
167            });
168
169            prev = current;
170        }
171
172        self.first_shelf = ShelfIndex(0);
173        self.free_items = ItemIndex::NONE;
174        self.free_shelves = ShelfIndex::NONE;
175        self.allocated_space = 0;
176    }
177
178    pub fn size(&self) -> Size {
179        if self.flip_xy {
180            size2(self.size.height, self.size.width)
181        } else {
182            self.size
183        }
184    }
185
186    /// Allocate a rectangle in the atlas.
187    pub fn allocate(&mut self, mut size: Size) -> Option<Allocation> {
188        if size.is_empty()
189            || size.width > std::u16::MAX as i32
190            || size.height > std::u16::MAX as i32 {
191            return None;
192        }
193
194        adjust_size(self.alignment.width, &mut size.width);
195        adjust_size(self.alignment.height, &mut size.height);
196
197        let (width, height) = convert_coordinates(self.flip_xy, size.width, size.height);
198
199        if width > self.shelf_width as i32 || height > self.size.height {
200            return None;
201        }
202
203        let height = shelf_height(height, self.size.height);
204
205        let mut width = width as u16;
206        let mut height = height as u16;
207
208        // Shelves that are taller than this threshold are not considered
209        // unless they are empty (since they can bit vertically split) or
210        // if we haven't found a good candidate.
211        let bad_fit_threshold = height.saturating_add(height / 2);
212        let mut selected_shelf_height = std::u16::MAX;
213        let mut selected_shelf = ShelfIndex::NONE;
214        let mut selected_item = ItemIndex::NONE;
215        let mut shelf_idx = self.first_shelf;
216        while shelf_idx.is_some() {
217            let shelf = &self.shelves[shelf_idx.index()];
218
219            if shelf.height < height
220                || shelf.height >= selected_shelf_height {
221                shelf_idx = shelf.next;
222                continue;
223            }
224
225            let bad_fit = !shelf.is_empty && shelf.height > bad_fit_threshold;
226            if bad_fit && selected_shelf.is_some() {
227                // Poor fit. We can't split this shelf vertically and there's a
228                // lot of wasted vertical space). Only consider this one if we
229                // haven't found any other candidate so far.
230                // The current implementation only considers the first bad fit
231                // instead of searching for the "best bad" fit. That's not ideal
232                // but it is simple/fast and hopefully good enough.
233                shelf_idx = shelf.next;
234                continue;
235            }
236
237            let mut item_idx = shelf.first_unallocated;
238            while item_idx.is_some() {
239                let item = &self.items[item_idx.index()];
240                if !item.allocated && item.width >= width {
241                    break;
242                }
243
244                item_idx = item.next_unallocated;
245            }
246
247            if item_idx.is_some() {
248                selected_shelf = shelf_idx;
249                selected_item = item_idx;
250                if !bad_fit {
251                    // Only set the selected height for good fits to avoid
252                    // situations where a tall used shelf is selected over
253                    // a taller empty shelf.
254                    selected_shelf_height = shelf.height;
255                }
256
257                if shelf.height == height {
258                    // Perfect fit, stop searching.
259                    break;
260                }
261            }
262
263            shelf_idx = shelf.next;
264        }
265
266        if selected_shelf.is_none() {
267            return None;
268        }
269
270        let shelf = self.shelves[selected_shelf.index()].clone();
271        if shelf.is_empty {
272            self.shelves[selected_shelf.index()].is_empty = false;
273        }
274
275        if shelf.is_empty && shelf.height > height + SHELF_SPLIT_THRESHOLD {
276            // Split the empty shelf into one of the desired size and a new
277            // empty one with a single empty item.
278
279            let new_shelf_idx =  self.add_shelf(Shelf {
280                x: shelf.x,
281                y: shelf.y + height,
282                height: shelf.height - height,
283                prev: selected_shelf,
284                next: shelf.next,
285                first_item: ItemIndex::NONE,
286                first_unallocated: ItemIndex::NONE,
287                is_empty: true,
288            });
289
290            let new_item_idx = self.add_item(Item {
291                x: shelf.x,
292                width: self.shelf_width,
293                prev: ItemIndex::NONE,
294                next: ItemIndex::NONE,
295                prev_unallocated: ItemIndex::NONE,
296                next_unallocated: ItemIndex::NONE,
297                shelf: new_shelf_idx,
298                allocated: false,
299                generation: 1,
300            });
301
302            self.shelves[new_shelf_idx.index()].first_item = new_item_idx;
303            self.shelves[new_shelf_idx.index()].first_unallocated = new_item_idx;
304
305            let next = self.shelves[selected_shelf.index()].next;
306            self.shelves[selected_shelf.index()].height = height;
307            self.shelves[selected_shelf.index()].next = new_shelf_idx;
308
309            if next.is_some() {
310                self.shelves[next.index()].prev = new_shelf_idx;
311            }
312        } else {
313            height = shelf.height;
314        }
315
316        let item = self.items[selected_item.index()].clone();
317
318        if item.width - width > ITEM_SPLIT_THRESHOLD {
319
320            let new_item_idx = self.add_item(Item {
321                x: item.x + width,
322                width: item.width - width,
323                prev: selected_item,
324                next: item.next,
325                prev_unallocated: item.prev_unallocated,
326                next_unallocated: item.next_unallocated,
327                shelf: item.shelf,
328                allocated: false,
329                generation: 1,
330            });
331
332            self.items[selected_item.index()].width = width;
333            self.items[selected_item.index()].next = new_item_idx;
334
335            if item.next.is_some() {
336                self.items[item.next.index()].prev = new_item_idx;
337            }
338
339            // Replace the item in the "unallocated" list.
340            let shelf = &mut self.shelves[selected_shelf.index()];
341            if shelf.first_unallocated == selected_item {
342                shelf.first_unallocated = new_item_idx;
343            }
344            if item.prev_unallocated.is_some() {
345                self.items[item.prev_unallocated.index()].next_unallocated = new_item_idx;
346            }
347            if item.next_unallocated.is_some() {
348                self.items[item.next_unallocated.index()].prev_unallocated = new_item_idx;
349            }
350        } else {
351            // Remove the item from the "unallocated" list.
352            let shelf = &mut self.shelves[selected_shelf.index()];
353            if shelf.first_unallocated == selected_item {
354                shelf.first_unallocated = item.next_unallocated;
355            }
356            if item.prev_unallocated.is_some() {
357                self.items[item.prev_unallocated.index()].next_unallocated = item.next_unallocated;
358            }
359            if item.next_unallocated.is_some() {
360                self.items[item.next_unallocated.index()].prev_unallocated = item.prev_unallocated;
361            }
362
363            width = item.width;
364        }
365
366        self.items[selected_item.index()].allocated = true;
367        let generation = self.items[selected_item.index()].generation;
368
369        let x0 = item.x;
370        let y0 = shelf.y;
371        let x1 = x0 + width;
372        let y1 = y0 + height;
373
374        let (x0, y0) = convert_coordinates(self.flip_xy, x0 as i32, y0 as i32);
375        let (x1, y1) = convert_coordinates(self.flip_xy, x1 as i32, y1 as i32);
376
377        self.check();
378
379        let rectangle = Rectangle {
380            min: point2(x0, y0),
381            max: point2(x1, y1),
382        };
383
384        self.allocated_space += rectangle.area();
385
386        Some(Allocation {
387            id: AllocId::new(selected_item.0, generation),
388            rectangle,
389        })
390    }
391
392    /// Deallocate a rectangle in the atlas.
393    pub fn deallocate(&mut self, id: AllocId) {
394        let item_idx = ItemIndex(id.index());
395
396        let Item { mut prev, mut next, mut width, allocated, shelf, generation, .. } = self.items[item_idx.index()];
397        assert!(allocated);
398        assert_eq!(generation, id.generation(), "Invalid AllocId");
399
400        self.items[item_idx.index()].allocated = false;
401        self.allocated_space -= width as i32 * self.shelves[shelf.index()].height as i32;
402
403        if next.is_some() && !self.items[next.index()].allocated {
404            // Merge the next item into this one.
405
406            let next_next = self.items[next.index()].next;
407            let next_width = self.items[next.index()].width;
408            // Remove next from the "unallocated" list.
409            let next_unallocated = self.items[next.index()].next_unallocated;
410            let prev_unallocated = self.items[next.index()].prev_unallocated;
411            if self.shelves[shelf.index()].first_unallocated == next {
412                self.shelves[shelf.index()].first_unallocated = next_unallocated;
413            }
414            if prev_unallocated.is_some() {
415                self.items[prev_unallocated.index()].next_unallocated = next_unallocated;
416            }
417            if next_unallocated.is_some() {
418                self.items[next_unallocated.index()].prev_unallocated = prev_unallocated;
419            }
420
421            self.items[item_idx.index()].next = next_next;
422            self.items[item_idx.index()].width += next_width;
423            width = self.items[item_idx.index()].width;
424
425            if next_next.is_some() {
426                self.items[next_next.index()].prev = item_idx;
427            }
428
429            // Add next to the free list.
430            self.remove_item(next);
431
432            next = next_next
433        }
434
435        if prev.is_some() && !self.items[prev.index()].allocated {
436            // Merge the item into the previous one.
437            // No need to add the item_idx to the "unallocated" list since it
438            // is getting merged into an already unallocated item.
439
440            self.items[prev.index()].next = next;
441            self.items[prev.index()].width += width;
442
443            if next.is_some() {
444                self.items[next.index()].prev = prev;
445            }
446
447            // Add item_idx to the free list.
448            self.remove_item(item_idx);
449
450            prev = self.items[prev.index()].prev;
451        } else {
452            // Insert item_idx in the "unallocated" list.
453            let first = self.shelves[shelf.index()].first_unallocated;
454            if first.is_some() {
455                self.items[first.index()].prev_unallocated = item_idx;
456            }
457            self.items[item_idx.index()].next_unallocated = first;
458            self.items[item_idx.index()].prev_unallocated = ItemIndex::NONE;
459            self.shelves[shelf.index()].first_unallocated = item_idx;
460        }
461
462        if prev.is_none() && next.is_none() {
463            let shelf_idx = shelf;
464            // The shelf is now empty.
465            self.shelves[shelf_idx.index()].is_empty = true;
466
467            // Only attempt to merge shelves on the same column.
468            let x = self.shelves[shelf_idx.index()].x;
469
470            let next_shelf = self.shelves[shelf_idx.index()].next;
471            if next_shelf.is_some()
472                && self.shelves[next_shelf.index()].is_empty
473                && self.shelves[next_shelf.index()].x == x {
474                // Merge the next shelf into this one.
475
476                let next_next = self.shelves[next_shelf.index()].next;
477                let next_height = self.shelves[next_shelf.index()].height;
478
479                self.shelves[shelf_idx.index()].next = next_next;
480                self.shelves[shelf_idx.index()].height += next_height;
481
482                if next_next.is_some() {
483                    self.shelves[next_next.index()].prev = shelf_idx;
484                }
485
486                // Add next to the free list.
487                self.remove_shelf(next_shelf);
488            }
489
490            let prev_shelf = self.shelves[shelf_idx.index()].prev;
491            if prev_shelf.is_some()
492                && self.shelves[prev_shelf.index()].is_empty
493                && self.shelves[prev_shelf.index()].x == x {
494                // Merge the shelf into the previous one.
495
496                let next_shelf = self.shelves[shelf_idx.index()].next;
497                self.shelves[prev_shelf.index()].next = next_shelf;
498                self.shelves[prev_shelf.index()].height += self.shelves[shelf_idx.index()].height;
499
500                self.shelves[prev_shelf.index()].next = self.shelves[shelf_idx.index()].next;
501                if next_shelf.is_some() {
502                    self.shelves[next_shelf.index()].prev = prev_shelf;
503                }
504
505                // Add the shelf to the free list.
506                self.remove_shelf(shelf_idx);
507            }
508        }
509
510        self.check();
511    }
512
513    pub fn is_empty(&self) -> bool {
514        let mut shelf_idx = self.first_shelf;
515
516        while shelf_idx.is_some() {
517            let shelf = &self.shelves[shelf_idx.index()];
518            if !shelf.is_empty {
519                return false;
520            }
521
522            shelf_idx = shelf.next;
523        }
524
525        true
526    }
527
528    /// Amount of occupied space in the atlas.
529    pub fn allocated_space(&self) -> i32 {
530        self.allocated_space
531    }
532
533    /// How much space is available for future allocations.
534    pub fn free_space(&self) -> i32 {
535        self.size.area() - self.allocated_space
536    }
537
538    pub fn iter(&self) -> Iter {
539        Iter {
540            atlas: self,
541            idx: 0,
542        }
543    }
544
545    fn remove_item(&mut self, idx: ItemIndex) {
546        self.items[idx.index()].next = self.free_items;
547        self.free_items = idx;
548    }
549
550    fn remove_shelf(&mut self, idx: ShelfIndex) {
551        // Remove the shelf's item.
552        self.remove_item(self.shelves[idx.index()].first_item);
553
554        self.shelves[idx.index()].next = self.free_shelves;
555        self.free_shelves = idx;
556    }
557
558    fn add_item(&mut self, mut item: Item) -> ItemIndex {
559        if self.free_items.is_some() {
560            let idx = self.free_items;
561            item.generation = self.items[idx.index()].generation.wrapping_add(1);
562            self.free_items = self.items[idx.index()].next;
563            self.items[idx.index()] = item;
564
565            return idx;
566        }
567
568        let idx = ItemIndex(self.items.len() as u16);
569        self.items.push(item);
570
571        idx
572    }
573
574    fn add_shelf(&mut self, shelf: Shelf) -> ShelfIndex {
575        if self.free_shelves.is_some() {
576            let idx = self.free_shelves;
577            self.free_shelves = self.shelves[idx.index()].next;
578            self.shelves[idx.index()] = shelf;
579
580            return idx;
581        }
582
583        let idx = ShelfIndex(self.shelves.len() as u16);
584        self.shelves.push(shelf);
585
586        idx
587    }
588
589    #[cfg(not(feature = "checks"))]
590    fn check(&self) {}
591
592    #[cfg(feature = "checks")]
593    fn check(&self) {
594        let mut prev_empty = false;
595        let mut accum_h = 0;
596        let mut shelf_idx = self.first_shelf;
597        let mut shelf_x = 0;
598        while shelf_idx.is_some() {
599            let shelf = &self.shelves[shelf_idx.index()];
600            let new_column = shelf_x != shelf.x;
601            if new_column {
602                assert_eq!(accum_h as i32, self.size.height);
603                accum_h = 0;
604            }
605            shelf_x = shelf.x;
606            accum_h += shelf.height;
607            if prev_empty && !new_column {
608                assert!(!shelf.is_empty);
609            }
610            if shelf.is_empty {
611                assert!(!self.items[shelf.first_item.index()].allocated);
612                assert!(self.items[shelf.first_item.index()].next.is_none());
613            }
614            prev_empty = shelf.is_empty;
615
616            let mut accum_w = 0;
617            let mut accum_unallocated_w = 0;
618            let mut prev_allocated = true;
619            let mut item_idx = shelf.first_item;
620            let mut prev_item_idx = ItemIndex::NONE;
621            while item_idx.is_some() {
622                let item = &self.items[item_idx.index()];
623                accum_w += item.width;
624                if !item.allocated {
625                    accum_unallocated_w += item.width;
626                }
627
628                assert_eq!(item.prev, prev_item_idx);
629
630                if !prev_allocated {
631                    assert!(item.allocated, "item {:?} should be allocated", item_idx.0);
632                }
633                prev_allocated = item.allocated;
634
635                prev_item_idx = item_idx;
636                item_idx = item.next;
637            }
638
639            assert_eq!(accum_w, self.shelf_width);
640
641            // Traverse the shelf's unallocated list, validate it and check that it matches
642            // the amount of unallocated space we found from traversing the whole shelf.
643            accum_w = 0;
644            let mut item_idx = shelf.first_unallocated;
645            let mut prev_unallocated_idx = ItemIndex::NONE;
646            while item_idx.is_some() {
647                let item = &self.items[item_idx.index()];
648                assert!(!item.allocated);
649
650                assert_eq!(item.prev_unallocated, prev_unallocated_idx);
651                accum_w += item.width;
652
653                prev_unallocated_idx = item_idx;
654                item_idx = item.next_unallocated;
655            }
656
657            assert_eq!(accum_w, accum_unallocated_w, "items missing from the unallocated list?");
658
659            shelf_idx = shelf.next;
660        }
661    }
662
663    /// Turn a valid AllocId into an index that can be used as a key for external storage.
664    ///
665    /// The allocator internally stores all items in a single vector. In addition allocations
666    /// stay at the same index in the vector until they are deallocated. As a result the index
667    /// of an item can be used as a key for external storage using vectors. Note that:
668    ///  - The provided ID must correspond to an item that is currently allocated in the atlas.
669    ///  - After an item is deallocated, its index may be reused by a future allocation, so
670    ///    the returned index should only be considered valid during the lifetime of the its
671    ///    associated item.
672    ///  - indices are expected to be "reasonable" with respect to the number of allocated items,
673    ///    in other words it is never larger than the maximum number of allocated items in the
674    ///    atlas (making it a good fit for indexing within a sparsely populated vector).
675    pub fn get_index(&self, id: AllocId) -> u32 {
676        let index = id.index();
677        debug_assert_eq!(self.items[index as usize].generation, id.generation());
678
679        index as u32
680    }
681
682    /// Returns the allocation info associated to the allocation ID.
683    ///
684    /// The id must correspond to an existing allocation in the atlas.
685    pub fn get(&self, id: AllocId) -> Rectangle {
686        let index = id.index()as usize;
687        let item = &self.items[index];
688
689        assert!(item.allocated);
690        assert_eq!(item.generation, id.generation(), "Invalid AllocId");
691
692        let shelf = &self.shelves[item.shelf.index()];
693
694        let mut rectangle = Rectangle {
695            min: point2(
696                item.x as i32,
697                shelf.y as i32,
698            ),
699            max: point2(
700                (item.x + item.width) as i32,
701                (shelf.y + shelf.height) as i32,
702            ),
703        };
704
705        if self.flip_xy {
706            std::mem::swap(&mut rectangle.min.x, &mut rectangle.min.y);
707            std::mem::swap(&mut rectangle.max.x, &mut rectangle.max.y);
708        }
709
710        rectangle
711    }
712
713    /// Dump a visual representation of the atlas in SVG format.
714    pub fn dump_svg(&self, output: &mut dyn std::io::Write) -> std::io::Result<()> {
715        use svg_fmt::*;
716
717        writeln!(
718            output,
719            "{}",
720            BeginSvg {
721                w: self.size.width as f32,
722                h: self.size.height as f32
723            }
724        )?;
725
726        self.dump_into_svg(None, output)?;
727
728        writeln!(output, "{}", EndSvg)
729    }
730
731    /// Dump a visual representation of the atlas in SVG, omitting the beginning and end of the
732    /// SVG document, so that it can be included in a larger document.
733    ///
734    /// If a rectangle is provided, translate and scale the output to fit it.
735    pub fn dump_into_svg(&self, rect: Option<&Rectangle>, output: &mut dyn std::io::Write) -> std::io::Result<()> {
736        use svg_fmt::*;
737
738        let (sx, sy, tx, ty) = if let Some(rect) = rect {
739            (
740                rect.size().width as f32 / self.size.width as f32,
741                rect.size().height as f32 / self.size.height as f32,
742                rect.min.x as f32,
743                rect.min.y as f32,
744            )
745        } else {
746            (1.0, 1.0, 0.0, 0.0)
747        };
748
749        writeln!(
750            output,
751            r#"    {}"#,
752            rectangle(tx, ty, self.size.width as f32 * sx, self.size.height as f32 * sy)
753                .fill(rgb(40, 40, 40))
754                .stroke(Stroke::Color(black(), 1.0))
755        )?;
756
757        let mut shelf_idx = self.first_shelf;
758        while shelf_idx.is_some() {
759            let shelf = &self.shelves[shelf_idx.index()];
760
761            let y = shelf.y as f32 * sy;
762            let h = shelf.height as f32 * sy;
763
764            let mut item_idx = shelf.first_item;
765            while item_idx.is_some() {
766                let item = &self.items[item_idx.index()];
767
768                let x = item.x as f32 * sx;
769                let w = item.width as f32 * sx;
770
771                let color = if item.allocated {
772                    rgb(70, 70, 180)
773                } else {
774                    rgb(50, 50, 50)
775                };
776
777                let (x, y) = if self.flip_xy { (y, x) } else { (x, y) };
778                let (w, h) = if self.flip_xy { (h, w) } else { (w, h) };
779
780                writeln!(
781                    output,
782                    r#"    {}"#,
783                    rectangle(x + tx, y + ty, w, h).fill(color).stroke(Stroke::Color(black(), 1.0))
784                )?;
785
786                item_idx = item.next;
787            }
788
789            shelf_idx = shelf.next;
790        }
791
792        Ok(())
793    }
794
795}
796
797
798fn adjust_size(alignment: i32, size: &mut i32) {
799    let rem = *size % alignment;
800    if rem > 0 {
801        *size += alignment - rem;
802    }
803}
804
805fn convert_coordinates(flip_xy: bool, x: i32, y: i32) -> (i32, i32) {
806    if flip_xy {
807        (y, x)
808    } else {
809        (x, y)
810    }
811}
812
813fn shelf_height(size: i32, atlas_height: i32) -> i32 {
814    let alignment = match size {
815        0 ..= 31 => 8,
816        32 ..= 127 => 16,
817        128 ..= 511 => 32,
818        _ => 64,
819    };
820
821    let mut adjusted_size = size;
822    let rem = size % alignment;
823    if rem > 0 {
824        adjusted_size = size + alignment - rem;
825        if adjusted_size > atlas_height {
826            adjusted_size = size;
827        }
828    }
829
830    adjusted_size
831}
832
833/// Iterator over the allocations of an atlas.
834pub struct Iter<'l> {
835    atlas: &'l AtlasAllocator,
836    idx: usize,
837}
838
839impl<'l> Iterator for Iter<'l> {
840    type Item = Allocation;
841
842    fn next(&mut self) -> Option<Allocation> {
843        if self.idx >= self.atlas.items.len() {
844            return None;
845        }
846
847        while !self.atlas.items[self.idx].allocated {
848            self.idx += 1;
849            if self.idx >= self.atlas.items.len() {
850                return None;
851            }
852        }
853
854        let item = &self.atlas.items[self.idx];
855        let shelf = &self.atlas.shelves[item.shelf.index()];
856
857        let mut alloc = Allocation {
858            rectangle: Rectangle {
859                min: point2(
860                    item.x as i32,
861                    shelf.y as i32,
862                ),
863                max: point2(
864                    (item.x + item.width) as i32,
865                    (shelf.y + shelf.height) as i32,
866                ),
867            },
868            id: AllocId::new(self.idx as u16, item.generation),
869        };
870
871        if self.atlas.flip_xy {
872            std::mem::swap(&mut alloc.rectangle.min.x, &mut alloc.rectangle.min.y);
873            std::mem::swap(&mut alloc.rectangle.max.x, &mut alloc.rectangle.max.y);
874        }
875
876        self.idx += 1;
877
878        Some(alloc)
879    }
880}
881
882impl<'l> std::iter::IntoIterator for &'l AtlasAllocator {
883    type Item = Allocation;
884    type IntoIter = Iter<'l>;
885    fn into_iter(self) -> Iter<'l> {
886        self.iter()
887    }
888}
889
890#[test]
891fn test_simple() {
892    let mut atlas = AtlasAllocator::with_options(
893        size2(2048, 2048),
894        &AllocatorOptions {
895            alignment: size2(4, 8),
896            vertical_shelves: false,
897            num_columns: 2,
898        },
899    );
900
901    assert!(atlas.is_empty());
902    assert_eq!(atlas.allocated_space(), 0);
903
904    let a1 = atlas.allocate(size2(20, 30)).unwrap();
905    let a2 = atlas.allocate(size2(30, 40)).unwrap();
906    let a3 = atlas.allocate(size2(20, 30)).unwrap();
907
908    assert!(a1.id != a2.id);
909    assert!(a1.id != a3.id);
910    assert!(!atlas.is_empty());
911
912    //atlas.dump_svg(&mut std::fs::File::create("tmp.svg").expect("!!")).unwrap();
913
914    atlas.deallocate(a1.id);
915    atlas.deallocate(a2.id);
916    atlas.deallocate(a3.id);
917
918    assert!(atlas.is_empty());
919    assert_eq!(atlas.allocated_space(), 0);
920}
921
922#[test]
923fn test_options() {
924    let alignment = size2(8, 16);
925
926    let mut atlas = AtlasAllocator::with_options(
927        size2(2000, 1000),
928        &AllocatorOptions {
929            alignment,
930            vertical_shelves: true,
931            num_columns: 1,
932        },
933    );
934    assert!(atlas.is_empty());
935    assert_eq!(atlas.allocated_space(), 0);
936
937    let a1 = atlas.allocate(size2(20, 30)).unwrap();
938    let a2 = atlas.allocate(size2(30, 40)).unwrap();
939    let a3 = atlas.allocate(size2(20, 30)).unwrap();
940
941    assert!(a1.id != a2.id);
942    assert!(a1.id != a3.id);
943    assert!(!atlas.is_empty());
944
945    for id in &atlas {
946        assert!(id == a1 || id == a2 || id == a3);
947    }
948
949    assert_eq!(a1.rectangle.min.x % alignment.width, 0);
950    assert_eq!(a1.rectangle.min.y % alignment.height, 0);
951    assert_eq!(a2.rectangle.min.x % alignment.width, 0);
952    assert_eq!(a2.rectangle.min.y % alignment.height, 0);
953    assert_eq!(a3.rectangle.min.x % alignment.width, 0);
954    assert_eq!(a3.rectangle.min.y % alignment.height, 0);
955
956    assert!(a1.rectangle.size().width >= 20);
957    assert!(a1.rectangle.size().height >= 30);
958    assert!(a2.rectangle.size().width >= 30);
959    assert!(a2.rectangle.size().height >= 40);
960    assert!(a3.rectangle.size().width >= 20);
961    assert!(a3.rectangle.size().height >= 30);
962
963
964    //atlas.dump_svg(&mut std::fs::File::create("tmp.svg").expect("!!")).unwrap();
965
966    atlas.deallocate(a1.id);
967    atlas.deallocate(a2.id);
968    atlas.deallocate(a3.id);
969
970    assert!(atlas.is_empty());
971    assert_eq!(atlas.allocated_space(), 0);
972}
973
974#[test]
975fn vertical() {
976    let mut atlas = AtlasAllocator::with_options(size2(128, 256), &AllocatorOptions {
977        num_columns: 2,
978        vertical_shelves: true,
979        ..DEFAULT_OPTIONS
980    });
981
982    assert_eq!(atlas.size(), size2(128, 256));
983
984    let a = atlas.allocate(size2(32, 16)).unwrap();
985    let b = atlas.allocate(size2(16, 32)).unwrap();
986
987    assert!(a.rectangle.size().width >= 32);
988    assert!(a.rectangle.size().height >= 16);
989
990    assert!(b.rectangle.size().width >= 16);
991    assert!(b.rectangle.size().height >= 32);
992
993    let c = atlas.allocate(size2(128, 128)).unwrap();
994
995    for _ in &atlas {}
996
997    atlas.deallocate(a.id);
998    atlas.deallocate(b.id);
999    atlas.deallocate(c.id);
1000
1001    for _ in &atlas {}
1002
1003    assert!(atlas.is_empty());
1004    assert_eq!(atlas.allocated_space(), 0);
1005}
1006
1007
1008#[test]
1009fn clear() {
1010    let mut atlas = AtlasAllocator::new(size2(2048, 2048));
1011
1012    // Run a workload a few hundred times to make sure clearing properly resets everything.
1013    for _ in 0..500 {
1014        atlas.clear();
1015        assert_eq!(atlas.allocated_space(), 0);
1016
1017        atlas.allocate(size2(8, 2)).unwrap();
1018        atlas.allocate(size2(2, 8)).unwrap();
1019        atlas.allocate(size2(16, 512)).unwrap();
1020        atlas.allocate(size2(34, 34)).unwrap();
1021        atlas.allocate(size2(34, 34)).unwrap();
1022        atlas.allocate(size2(34, 34)).unwrap();
1023        atlas.allocate(size2(34, 34)).unwrap();
1024        atlas.allocate(size2(2, 8)).unwrap();
1025        atlas.allocate(size2(2, 8)).unwrap();
1026        atlas.allocate(size2(8, 2)).unwrap();
1027        atlas.allocate(size2(2, 8)).unwrap();
1028        atlas.allocate(size2(8, 2)).unwrap();
1029        atlas.allocate(size2(8, 8)).unwrap();
1030        atlas.allocate(size2(8, 8)).unwrap();
1031        atlas.allocate(size2(8, 8)).unwrap();
1032        atlas.allocate(size2(8, 8)).unwrap();
1033        atlas.allocate(size2(82, 80)).unwrap();
1034        atlas.allocate(size2(56, 56)).unwrap();
1035        atlas.allocate(size2(64, 66)).unwrap();
1036        atlas.allocate(size2(32, 32)).unwrap();
1037        atlas.allocate(size2(32, 32)).unwrap();
1038        atlas.allocate(size2(32, 32)).unwrap();
1039        atlas.allocate(size2(32, 32)).unwrap();
1040        atlas.allocate(size2(32, 32)).unwrap();
1041        atlas.allocate(size2(32, 32)).unwrap();
1042        atlas.allocate(size2(32, 32)).unwrap();
1043        atlas.allocate(size2(32, 32)).unwrap();
1044        atlas.allocate(size2(32, 32)).unwrap();
1045        atlas.allocate(size2(40, 40)).unwrap();
1046        atlas.allocate(size2(32, 32)).unwrap();
1047        atlas.allocate(size2(256, 52)).unwrap();
1048        atlas.allocate(size2(32, 32)).unwrap();
1049        atlas.allocate(size2(256, 52)).unwrap();
1050        atlas.allocate(size2(256, 52)).unwrap();
1051        atlas.allocate(size2(256, 52)).unwrap();
1052        atlas.allocate(size2(256, 52)).unwrap();
1053        atlas.allocate(size2(256, 52)).unwrap();
1054        atlas.allocate(size2(256, 52)).unwrap();
1055        atlas.allocate(size2(155, 52)).unwrap();
1056        atlas.allocate(size2(256, 52)).unwrap();
1057        atlas.allocate(size2(32, 32)).unwrap();
1058        atlas.allocate(size2(32, 32)).unwrap();
1059        atlas.allocate(size2(32, 32)).unwrap();
1060        atlas.allocate(size2(24, 24)).unwrap();
1061        atlas.allocate(size2(64, 64)).unwrap();
1062        atlas.allocate(size2(32, 32)).unwrap();
1063        atlas.allocate(size2(84, 84)).unwrap();
1064        atlas.allocate(size2(32, 32)).unwrap();
1065        atlas.allocate(size2(8, 2)).unwrap();
1066        atlas.allocate(size2(34, 34)).unwrap();
1067        atlas.allocate(size2(34, 34)).unwrap();
1068        atlas.allocate(size2(192, 192)).unwrap();
1069        atlas.allocate(size2(192, 192)).unwrap();
1070        atlas.allocate(size2(52, 52)).unwrap();
1071        atlas.allocate(size2(144, 144)).unwrap();
1072        atlas.allocate(size2(192, 192)).unwrap();
1073        atlas.allocate(size2(32, 32)).unwrap();
1074        atlas.allocate(size2(144, 144)).unwrap();
1075        atlas.allocate(size2(24, 24)).unwrap();
1076        atlas.allocate(size2(192, 192)).unwrap();
1077        atlas.allocate(size2(192, 192)).unwrap();
1078        atlas.allocate(size2(432, 243)).unwrap();
1079        atlas.allocate(size2(32, 32)).unwrap();
1080        atlas.allocate(size2(8, 2)).unwrap();
1081        atlas.allocate(size2(2, 8)).unwrap();
1082        atlas.allocate(size2(9, 9)).unwrap();
1083        atlas.allocate(size2(14, 14)).unwrap();
1084        atlas.allocate(size2(14, 14)).unwrap();
1085        atlas.allocate(size2(14, 14)).unwrap();
1086        atlas.allocate(size2(14, 14)).unwrap();
1087        atlas.allocate(size2(8, 8)).unwrap();
1088        atlas.allocate(size2(27, 27)).unwrap();
1089        atlas.allocate(size2(27, 27)).unwrap();
1090        atlas.allocate(size2(27, 27)).unwrap();
1091        atlas.allocate(size2(27, 27)).unwrap();
1092        atlas.allocate(size2(11, 12)).unwrap();
1093        atlas.allocate(size2(29, 28)).unwrap();
1094        atlas.allocate(size2(32, 32)).unwrap();
1095
1096        for _ in &atlas {}
1097    }
1098}
1099
1100#[test]
1101fn fuzz_01() {
1102    let s = 65472;
1103
1104    let mut atlas = AtlasAllocator::new(size2(s, 64));
1105    let alloc = atlas.allocate(size2(s, 64)).unwrap();
1106    assert_eq!(alloc.rectangle.size().width, s);
1107    assert_eq!(alloc.rectangle.size().height, 64);
1108
1109    let mut atlas = AtlasAllocator::new(size2(64, s));
1110    let alloc = atlas.allocate(size2(64, s)).unwrap();
1111    assert_eq!(alloc.rectangle.size().width, 64);
1112    assert_eq!(alloc.rectangle.size().height, s);
1113
1114    let mut atlas = AtlasAllocator::new(size2(s, 64));
1115    let alloc = atlas.allocate(size2(s - 1, 64)).unwrap();
1116    assert_eq!(alloc.rectangle.size().width, s);
1117    assert_eq!(alloc.rectangle.size().height, 64);
1118
1119    let mut atlas = AtlasAllocator::new(size2(64, s));
1120    let alloc = atlas.allocate(size2(64, s - 1)).unwrap();
1121    assert_eq!(alloc.rectangle.size().width, 64);
1122    assert_eq!(alloc.rectangle.size().height, s);
1123
1124    // Because of potential alignment we won't necessarily
1125    // succeed at allocation something this big
1126    let s = std::u16::MAX as i32;
1127
1128    let mut atlas = AtlasAllocator::new(size2(s, 64));
1129    if let Some(alloc) = atlas.allocate(size2(s, 64)) {
1130        assert_eq!(alloc.rectangle.size().width, s);
1131        assert_eq!(alloc.rectangle.size().height, 64);
1132    }
1133
1134    let mut atlas = AtlasAllocator::new(size2(64, s));
1135    if let Some(alloc) = atlas.allocate(size2(64, s)) {
1136        assert_eq!(alloc.rectangle.size().width, 64);
1137        assert_eq!(alloc.rectangle.size().height, s);
1138    }
1139}
1140
1141
1142#[test]
1143fn fuzz_02() {
1144    let mut atlas = AtlasAllocator::new(size2(1000, 1000));
1145
1146    assert!(atlas.allocate(size2(255, 65599)).is_none());
1147}
1148
1149#[test]
1150fn fuzz_03() {
1151    let mut atlas = AtlasAllocator::new(size2(1000, 1000));
1152
1153    let sizes = &[
1154        size2(999, 128),
1155        size2(168492810, 10),
1156        size2(45, 96),
1157        size2(-16711926, 0),
1158    ];
1159
1160    let mut allocations = Vec::new();
1161    let mut allocated_space = 0;
1162
1163    for size in sizes {
1164        if let Some(alloc) = atlas.allocate(*size) {
1165            allocations.push(alloc);
1166            allocated_space += alloc.rectangle.area();
1167            assert_eq!(allocated_space, atlas.allocated_space());
1168        }
1169    }
1170
1171    for alloc in &allocations {
1172        atlas.deallocate(alloc.id);
1173
1174        allocated_space -= alloc.rectangle.area();
1175        assert_eq!(allocated_space, atlas.allocated_space());
1176    }
1177
1178    assert_eq!(atlas.allocated_space(), 0);
1179}
1180
1181#[test]
1182fn fuzz_04() {
1183    let mut atlas = AtlasAllocator::new(size2(1000, 1000));
1184
1185    assert!(atlas.allocate(size2(2560, 2147483647)).is_none());
1186}
1187
1188#[test]
1189fn issue_17_1() {
1190    let mut atlas = AtlasAllocator::new(size2(1024, 1024));
1191
1192    let a = atlas.allocate(size2(100, 300)).unwrap();
1193    let b = atlas.allocate(size2(500, 200)).unwrap();
1194
1195    assert_eq!(a.rectangle, atlas.get(a.id));
1196    assert_eq!(b.rectangle, atlas.get(b.id));
1197
1198    atlas.deallocate(a.id);
1199
1200    let c = atlas.allocate(size2(300, 200)).unwrap();
1201
1202    assert_eq!(b.rectangle, atlas.get(b.id));
1203    assert_eq!(c.rectangle, atlas.get(c.id));
1204
1205    atlas.deallocate(c.id);
1206    atlas.deallocate(b.id);
1207}
1208
1209#[test]
1210fn issue_17_2() {
1211    let mut atlas = AtlasAllocator::new(size2(1000, 1000));
1212
1213    assert!(atlas.allocate(size2(100, 1001)).is_none());
1214    assert!(atlas.allocate(size2(1001, 1000)).is_none());
1215    let a = atlas.allocate(size2(1000, 1000)).unwrap();
1216
1217    assert_eq!(a.rectangle, atlas.get(a.id));
1218
1219    atlas.deallocate(a.id);
1220}
1221
1222#[test]
1223fn issue_35() {
1224    let mut atlas = AtlasAllocator::new(size2(1000, 1000));
1225    // This creates a shelf that takes the entire height of the
1226    // atlas.
1227    let a = atlas.allocate(size2(100, 1000)).unwrap();
1228    // The atlas's ony shelf would be a poor fit because the height
1229    // is 5 times larger than the allocation, but it is the only
1230    // one so the allocator should take it and manage to allocate.
1231    let b = atlas.allocate(size2(900, 200)).unwrap();
1232
1233    atlas.deallocate(a.id);
1234    atlas.deallocate(b.id);
1235}
1236
1237#[test]
1238fn bad_fit() {
1239    // Allocate items with heights that are far appart and enough vertical
1240    // space in the atlas. All three allocations should end up in their own
1241    // shelf.
1242    let a = size2(100, 300);
1243    let b = size2(100, 100);
1244    let c = size2(100, 30);
1245    // Try multiple permutations of the allocation order.
1246    for (s1, s2, s3) in [(a, b, c), (c, b, a), (a, c, b), (c, a, b), (b, a, c), (b, c, a)] {
1247        let mut atlas = AtlasAllocator::new(size2(1000, 1000));
1248
1249        let a1 = atlas.allocate(s1).unwrap();
1250        let a2 = atlas.allocate(s2).unwrap();
1251        let a3 = atlas.allocate(s3).unwrap();
1252
1253        assert!(a1.rectangle.min.y != a2.rectangle.min.y);
1254        assert!(a2.rectangle.min.y != a3.rectangle.min.y);
1255        assert!(a1.rectangle.min.y != a3.rectangle.min.y);
1256        assert!(a1.rectangle.max.y != a2.rectangle.max.y);
1257        assert!(a2.rectangle.max.y != a3.rectangle.max.y);
1258        assert!(a1.rectangle.max.y != a3.rectangle.max.y);
1259
1260        atlas.deallocate(a1.id);
1261        atlas.deallocate(a2.id);
1262        atlas.deallocate(a3.id);
1263    }
1264}
etagere/allocator.rs

etagere/
allocator.rs
