### Grid Layout Example Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html A visual example of a grid layout that could be generated by different split sequences. ```text +---------+------+ | A | B | | | | +---------+------+ | C | D | | | | +---------+------+ ``` -------------------------------- ### ASCII Tree Coalescing Example Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Visual representation of how deallocating a rectangle can lead to node lifting in the tree structure. ```ascii +-----------+ AB C +-----------+ ABC ``` -------------------------------- ### Get atlas size Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Returns the total size of the atlas. ```rust pub fn size(&self) -> Size { self.size } ``` -------------------------------- ### Grow Atlas and Allocate in Large Bucket Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Demonstrates growing an atlas past the large threshold and verifying that a subsequent allocation successfully searches the large bucket. ```rust // Atlas is a single free root node in SMALL_BUCKET (20 < 32). // Grow it past the large threshold. atlas2.grow(size2(512, 512)); // Allocate something that searches LARGE_BUCKET. assert!( atlas2.allocate(size2(500, 500)).is_some(), "Single-root grow should update the free list bucket" ); } ``` -------------------------------- ### AtlasAllocator Initialization Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Methods for creating a new AtlasAllocator instance with default or custom options. ```rust impl AtlasAllocator { /// Create an atlas allocator. pub fn new(size: Size) -> Self { AtlasAllocator::with_options(size, &DEFAULT_OPTIONS) } /// Create an atlas allocator with the provided options. pub fn with_options(size: Size, options: &AllocatorOptions) -> Self { assert!(options.alignment.width > 0); assert!(options.alignment.height > 0); assert!(size.width > 0); assert!(size.height > 0); assert!(options.large_size_threshold >= options.small_size_threshold); let mut free_lists = [Vec::new(), Vec::new(), Vec::new()]; let bucket = free_list_for_size( options.small_size_threshold, options.large_size_threshold, &size, ); free_lists[bucket].push(AllocIndex(0)); AtlasAllocator { nodes: vec![Node { parent: AllocIndex::NONE, next_sibling: AllocIndex::NONE, prev_sibling: AllocIndex::NONE, rect: size.into(), kind: NodeKind::Free, orientation: Orientation::Vertical, }], free_lists, generations: vec![Wrapping(0)], unused_nodes: AllocIndex::NONE, alignment: options.alignment, small_size_threshold: options.small_size_threshold, large_size_threshold: options.large_size_threshold, size, root_node: AllocIndex(0), } } ``` -------------------------------- ### Node Allocation and Deallocation Methods Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Methods for creating new nodes, marking nodes as unused, and managing free lists. ```rust fn new_node(&mut self) -> AllocIndex { let idx = self.unused_nodes; if idx.index() < self.nodes.len() { self.unused_nodes = self.nodes[idx.index()].next_sibling; self.generations[idx.index()] += Wrapping(1); debug_assert_eq!(self.nodes[idx.index()].kind, NodeKind::Unused); return idx; } self.nodes.push(Node { parent: AllocIndex::NONE, next_sibling: AllocIndex::NONE, prev_sibling: AllocIndex::NONE, rect: Rectangle::zero(), kind: NodeKind::Unused, orientation: Orientation::Horizontal, }); self.generations.push(Wrapping(0)); AllocIndex(self.nodes.len() as u32 - 1) } fn mark_node_unused(&mut self, id: AllocIndex) { debug_assert!(self.nodes[id.index()].kind != NodeKind::Unused); self.nodes[id.index()].kind = NodeKind::Unused; self.nodes[id.index()].next_sibling = self.unused_nodes; self.unused_nodes = id; } ``` ```rust fn add_free_rect(&mut self, id: AllocIndex, size: &Size) { debug_assert_eq!(self.nodes[id.index()].kind, NodeKind::Free); let bucket = free_list_for_size(self.small_size_threshold, self.large_size_threshold, size); self.free_lists[bucket].push(id); } ``` -------------------------------- ### Tree Structure Comparison for Grid Layouts Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html Comparison of tree structures resulting from vertical versus horizontal split sequences for the same layout. ```text Tree | Layout Tree | Layout -----------------+------------ -----------------+------------ # | # | | | | | +---+---+ . .|. Vertical +---+---+ . .|. Horizontal | | | | | | # # | or # # | | | | | | | +-+-+ . +-+-+ .|. Horizontal +-+-+ . +-+-+ .|. Vertical | | | | | | | | | | A B C D | A C B D | ``` -------------------------------- ### SimpleAtlasAllocator Source: https://docs.rs/guillotiere/latest/guillotiere/struct.SimpleAtlasAllocator.html Documentation for the SimpleAtlasAllocator struct and its public methods. ```APIDOC ## SimpleAtlasAllocator ### Description A simpler atlas allocator implementation that can allocate rectangles but not deallocate them. ### Methods #### new ##### Description Create a simple atlas allocator with default options. ##### Signature ```rust pub fn new(size: Size) -> Self ``` ##### Parameters - **size** (Size) - Required - The size of the atlas. #### with_options ##### Description Create a simple atlas allocator with the provided options. ##### Signature ```rust pub fn with_options(size: Size, options: &AllocatorOptions) -> Self ``` ##### Parameters - **size** (Size) - Required - The size of the atlas. - **options** (&AllocatorOptions) - Required - The allocator options. #### clear ##### Description Drop all rectangles, clearing the atlas to its initial state. ##### Signature ```rust pub fn clear(&mut self) ``` #### reset ##### Description Clear the allocator and reset its size and options. ##### Signature ```rust pub fn reset(&mut self, size: Size, options: &AllocatorOptions) ``` ##### Parameters - **size** (Size) - Required - The new size of the atlas. - **options** (&AllocatorOptions) - Required - The new allocator options. #### is_empty ##### Description Returns whether the atlas is empty. ##### Signature ```rust pub fn is_empty(&self) -> bool ``` #### size ##### Description The total size of the atlas. ##### Signature ```rust pub fn size(&self) -> Size ``` #### allocate ##### Description Allocate a rectangle in the atlas. ##### Signature ```rust pub fn allocate(&mut self, requested_size: Size) -> Option ``` ##### Parameters - **requested_size** (Size) - Required - The size of the rectangle to allocate. ##### Returns - **Option** - The allocated rectangle, or `None` if allocation fails. #### grow ##### Description Resize the atlas without changing the allocations. This method is not allowed to shrink the width or height of the atlas. ##### Signature ```rust pub fn grow(&mut self, new_size: Size) ``` ##### Parameters - **new_size** (Size) - Required - The new size of the atlas. #### init_from_allocator ##### Description Initialize this simple allocator with the content of an atlas allocator. ##### Signature ```rust pub fn init_from_allocator(&mut self, src: &AtlasAllocator) ``` ##### Parameters - **src** (&AtlasAllocator) - Required - The source atlas allocator. ``` -------------------------------- ### Initialize from another allocator Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Initializes the current allocator state using data from an existing AtlasAllocator. ```rust pub fn init_from_allocator(&mut self, src: &AtlasAllocator) { self.size = src.size; self.alignment = src.alignment; self.small_size_threshold = src.small_size_threshold; self.large_size_threshold = src.large_size_threshold; for bucket in 0..NUM_BUCKETS { self.free_rects[bucket].clear(); for id in src.free_lists[bucket].iter() { // During tree simplification we don't remove merged nodes from the free list, so we have // to handle it here. // This is a tad awkward, but lets us avoid having to maintain a doubly linked list for // the free list (which would be needed to remove nodes during tree simplification). if src.nodes[id.index()].kind != NodeKind::Free { continue; } self.free_rects[bucket].push(src.nodes[id.index()].rect); } } } ``` -------------------------------- ### ChangeList::empty Source: https://docs.rs/guillotiere/latest/guillotiere/struct.ChangeList.html Creates an empty ChangeList instance. This is a public constructor method for the ChangeList struct. ```APIDOC ## ChangeList::empty ### Description Creates a new empty ChangeList. ### Method pub fn empty() -> Self ### Parameters None ### Returns - **Self** - A new ChangeList instance with empty changes and failures vectors. ### Example ```rust let change_list = ChangeList::empty(); ``` ``` -------------------------------- ### grow method Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Expands the atlas dimensions without moving existing allocations. It requires that the new dimensions are not smaller than the current ones and handles free space expansion or addition. ```rust pub fn grow(&mut self, new_size: Size) { assert!(new_size.width >= self.size.width); assert!(new_size.height >= self.size.height); let old_size = self.size; self.size = new_size; let dx = new_size.width - old_size.width; let dy = new_size.height - old_size.height; // If there is only one node and it is free, just grow it. let root = &mut self.nodes[self.root_node.index()]; if root.kind == NodeKind::Free && root.rect.size() == old_size { root.rect.max = root.rect.min + new_size.to_vector(); // The node's size changed, move it to the correct free list bucket. self.update_free_list_bucket(self.root_node); return; } let root_orientation = root.orientation; let grows_in_root_orientation = match root_orientation { Orientation::Horizontal => dx > 0, Orientation::Vertical => dy > 0, }; // If growing along the orientation of the root node, find the right-or-bottom-most sibling // and either grow it (if it is free) or append a free node next. if grows_in_root_orientation { let mut sibling = self.root_node; while self.nodes[sibling.index()].next_sibling != AllocIndex::NONE { sibling = self.nodes[sibling.index()].next_sibling; } let node = &mut self.nodes[sibling.index()]; if node.kind == NodeKind::Free { node.rect.max += match root_orientation { Orientation::Horizontal => vec2(dx, 0), Orientation::Vertical => vec2(0, dy), }; // The node's size changed, move it to the correct free list bucket. self.update_free_list_bucket(sibling); } else { let rect = match root_orientation { Orientation::Horizontal => { let min = point2(node.rect.max.x, node.rect.min.y); let max = min + vec2(dx, node.rect.height()); Rectangle { min, max } } Orientation::Vertical => { let min = point2(node.rect.min.x, node.rect.max.y); let max = min + vec2(node.rect.width(), dy); Rectangle { min, max } } }; let next = self.new_node(); self.nodes[sibling.index()].next_sibling = next; self.nodes[next.index()] = Node { kind: NodeKind::Free, rect, prev_sibling: sibling, next_sibling: AllocIndex::NONE, parent: AllocIndex::NONE, orientation: root_orientation, }; self.add_free_rect(next, &rect.size()); } } let grows_in_opposite_orientation = match root_orientation { Orientation::Horizontal => dy > 0, Orientation::Vertical => dx > 0, }; if grows_in_opposite_orientation { let free_node = self.new_node(); let new_root = self.new_node(); let old_root = self.root_node; self.root_node = new_root; ``` -------------------------------- ### Subdivision layout visualization Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html A visual representation of a rectangle subdivision layout. ```text +-----------+----------+---+---+--+---------+---+ | | | C | D |E | F | G | | | +---+---+--+---------+---+ | A | B | | | | | H | | | | | +------+----+----------+-+----------------------+ | | J | | | I +-----------------+ L | | | K | | +------+-----------------+----------------------+ ``` -------------------------------- ### atlas_basic test Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html A basic unit test verifying allocation and deallocation sequences in the AtlasAllocator. ```rust #[test] fn atlas_basic() { let mut atlas = AtlasAllocator::new(size2(1000, 1000)); let full = atlas.allocate(size2(1000, 1000)).unwrap().id; assert!(atlas.allocate(size2(1, 1)).is_none()); atlas.deallocate(full); let a = atlas.allocate(size2(100, 1000)).unwrap().id; let b = atlas.allocate(size2(900, 200)).unwrap().id; let c = atlas.allocate(size2(300, 200)).unwrap().id; let d = atlas.allocate(size2(200, 300)).unwrap().id; let e = atlas.allocate(size2(100, 300)).unwrap().id; let f = atlas.allocate(size2(100, 300)).unwrap().id; let g = atlas.allocate(size2(100, 300)).unwrap().id; atlas.deallocate(b); atlas.deallocate(f); atlas.deallocate(c); atlas.deallocate(e); let h = atlas.allocate(size2(500, 200)).unwrap().id; atlas.deallocate(a); let i = atlas.allocate(size2(500, 200)).unwrap().id; atlas.deallocate(g); atlas.deallocate(h); atlas.deallocate(d); atlas.deallocate(i); let full = atlas.allocate(size2(1000, 1000)).unwrap().id; assert!(atlas.allocate(size2(1, 1)).is_none()); atlas.deallocate(full); } ``` -------------------------------- ### resize_and_rearrange method Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Rearranges existing allocations to fit within a new atlas size. It sorts allocations by area, clears the current state, and attempts to reallocate them into the new dimensions. ```rust pub fn resize_and_rearrange(&mut self, new_size: Size) -> ChangeList { let mut allocs = Vec::with_capacity(self.nodes.len()); for (i, node) in self.nodes.iter().enumerate() { if node.kind != NodeKind::Alloc { continue; } let id = self.alloc_id(AllocIndex(i as u32)); allocs.push(Allocation { id, rectangle: node.rect, }); } allocs.sort_by_key(|alloc| safe_area(&alloc.rectangle)); allocs.reverse(); self.size = new_size; self.clear(); let mut changes = Vec::new(); let mut failures = Vec::new(); for old in allocs { let size = old.rectangle.size(); if let Some(new) = self.allocate(size) { changes.push(Change { old, new }); } else { failures.push(old); } } ChangeList { changes, failures } } ``` -------------------------------- ### Allocator Implementation Source Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html The core implementation of the guillotine allocator, including bucket definitions, allocation indices, node structures, and configuration options. ```rust 1#[cfg(test)] 2extern crate std; 3 4use alloc::vec; 5use alloc::vec::Vec; 6use crate::{Rectangle, Size}; 7use euclid::{vec2, point2, size2}; 8 9use core::num::Wrapping; 10 11const LARGE_BUCKET: usize = 2; 12const MEDIUM_BUCKET: usize = 1; 13const SMALL_BUCKET: usize = 0; 14const NUM_BUCKETS: usize = 3; 15 16fn free_list_for_size(small_threshold: i32, large_threshold: i32, size: &Size) -> usize { 17 if size.width >= large_threshold || size.height >= large_threshold { 18 LARGE_BUCKET 19 } else if size.width >= small_threshold || size.height >= small_threshold { 20 MEDIUM_BUCKET 21 } else { 22 SMALL_BUCKET 23 } 24} 25 26#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))] 27#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] 28struct AllocIndex(u32); 29impl AllocIndex { 30 const NONE: AllocIndex = AllocIndex(u32::MAX); 31 32 fn index(self) -> usize { 33 self.0 as usize 34 } 35 36 fn is_none(self) -> bool { 37 self == AllocIndex::NONE 38 } 39 40 fn is_some(self) -> bool { 41 self != AllocIndex::NONE 42 } 43} 44 45/// ID referring to an allocated rectangle. 46#[repr(C)] 47#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))] 48#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] 49pub struct AllocId(pub(crate) u32); 50 51impl AllocId { 52 pub fn serialize(&self) -> u32 { 53 self.0 54 } 55 56 pub fn deserialize(bytes: u32) -> Self { 57 AllocId(bytes) 58 } 59} 60 61const GEN_MASK: u32 = 0xFF000000; 62const IDX_MASK: u32 = 0x00FFFFFF; 63 64#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))] 65#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] 66enum Orientation { 67 Vertical, 68 Horizontal, 69} 70 71impl Orientation { 72 fn flipped(self) -> Self { 73 match self { 74 Orientation::Vertical => Orientation::Horizontal, 75 Orientation::Horizontal => Orientation::Vertical, 76 } 77 } 78} 79 80#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))] 81#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] 82pub enum NodeKind { 83 Container, 84 Alloc, 85 Free, 86 Unused, 87} 88 89#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))] 90#[derive(Clone, Debug)] 91struct Node { 92 parent: AllocIndex, 93 next_sibling: AllocIndex, 94 prev_sibling: AllocIndex, 95 kind: NodeKind, 96 orientation: Orientation, 97 rect: Rectangle, 98} 99 100/// Options to tweak the behavior of the atlas allocator. 101#[repr(C)] 102#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))] 103#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] 104pub struct AllocatorOptions { 105 /// Round the rectangle sizes up to a multiple of this value. 106 /// 107 /// Width and height alignments must be superior to zero. 108 /// 109 /// Default value: (1, 1), 110 pub alignment: Size, 111 112 /// Value below which a size is considered small. 113 /// 114 /// This is value is used to speed up the storage and lookup of free rectangles. 115 /// This value must be inferior or equal to `large_size_threshold` 116 /// 117 /// Default value: 32, 118 pub small_size_threshold: i32, 119 120 /// Value above which a size is considered large. 121 /// 122 /// This is value is used to speed up the storage and lookup of free rectangles. 123 /// This value must be inferior or equal to `large_size_threshold` 124 /// 125 /// Default value: 256, 126 pub large_size_threshold: i32, 127} 128 129pub const DEFAULT_OPTIONS: AllocatorOptions = AllocatorOptions { 130 alignment: size2(1, 1), 131 large_size_threshold: 256, 132 small_size_threshold: 32, 133}; 134 135impl Default for AllocatorOptions { 136 fn default() -> Self { 137 DEFAULT_OPTIONS 138 } 139} ``` -------------------------------- ### Deallocation and Tree Merging Visualization Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html Visual representation of how deallocating a node allows it to merge with siblings and potentially lift up the tree structure. ```text +-------+---+ # +-----------+ # # | | | | | | | | | AB | C | +---+---+ | ABC | +---+---+ +---+---+ | | | | | | | | | | | +-------+---+ # D +-----------+ # D ABC D | D | | -> | D | | -> | | +-+-+ | | + | | | | | | | +-----------+ AB C +-----------+ ABC ``` -------------------------------- ### Finding a Suitable Rectangle Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Searches for a suitable rectangle in the free lists based on the requested size, using either best-fit or worst-fit strategies. ```rust fn find_suitable_rect(&mut self, requested_size: &Size) -> AllocIndex { let ideal_bucket = free_list_for_size( self.small_size_threshold, self.large_size_threshold, requested_size, ); let use_worst_fit = ideal_bucket == LARGE_BUCKET; for bucket in ideal_bucket..NUM_BUCKETS { let mut candidate_score = if use_worst_fit { 0 } else { i32::MAX }; let mut candidate = None; let mut freelist_idx = 0; while freelist_idx < self.free_lists[bucket].len() { let id = self.free_lists[bucket][freelist_idx]; // During tree simplification we don't remove merged nodes from the free list, so we have // to handle it here. // This is a tad awkward, but lets us avoid having to maintain a doubly linked list for // the free list (which would be needed to remove nodes during tree simplification). if self.nodes[id.index()].kind != NodeKind::Free { // remove the element from the free list self.free_lists[bucket].swap_remove(freelist_idx); continue; } let size = self.nodes[id.index()].rect.size(); let dx = size.width - requested_size.width; let dy = size.height - requested_size.height; if dx >= 0 && dy >= 0 { if dx == 0 || dy == 0 { // Perfect fit! candidate = Some((id, freelist_idx)); break; } // Favor the largest minimum dimension, except for small // allocations. let score = i32::min(dx, dy); if (use_worst_fit && score > candidate_score) || (!use_worst_fit && score < candidate_score) { candidate_score = score; ``` -------------------------------- ### AllocatorOptions Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Options to tweak the behavior of the atlas allocator. ```APIDOC ## AllocatorOptions ### Description Options to tweak the behavior of the atlas allocator. ### Fields - **alignment** (Size) - Round the rectangle sizes up to a multiple of this value. Width and height alignments must be superior to zero. Default value: (1, 1). - **small_size_threshold** (i32) - Value below which a size is considered small. Used to speed up storage and lookup of free rectangles. Must be inferior or equal to large_size_threshold. Default value: 32. - **large_size_threshold** (i32) - Value above which a size is considered large. Used to speed up storage and lookup of free rectangles. Must be inferior or equal to large_size_threshold. Default value: 256. ### Default - **DEFAULT_OPTIONS**: AllocatorOptions with alignment (1, 1), large_size_threshold 256, small_size_threshold 32. ``` -------------------------------- ### Reset the allocator with new size and options Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Updates alignment, size thresholds, and size, then calls clear to reset the allocator state. ```rust /// Clear the allocator and reset its size and options. pub fn reset(&mut self, size: Size, options: &AllocatorOptions) { self.alignment = options.alignment; self.small_size_threshold = options.small_size_threshold; self.large_size_threshold = options.large_size_threshold; self.size = size; self.clear(); } ``` -------------------------------- ### Test grow_free_list_bucket Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Regression test ensuring that growing a free node in-place correctly updates its bucket, allowing subsequent large allocations to succeed. ```rust #[test] fn grow_free_list_bucket() { // Regression test: growing a free node in-place must move it to the correct // free list bucket, otherwise allocations searching a higher bucket won't find it. let mut atlas = AtlasAllocator::with_options( size2(100, 100), &AllocatorOptions { small_size_threshold: 32, large_size_threshold: 256, ..DEFAULT_OPTIONS }, ); // Allocate most of the atlas, leaving a thin free strip along the bottom. // The strip's min dimension (10) is below small_size_threshold (32), so it // lands in the SMALL_BUCKET. let a = atlas.allocate(size2(100, 90)).unwrap().id; // Grow the atlas so that the free strip extends from 10 to 1010 pixels tall. // Its min dimension is now 100 (>= small_threshold), so it should move out of // SMALL_BUCKET. Before the fix it stayed in SMALL_BUCKET and large allocations // could not find it. atlas.grow(size2(100, 1100)); // This allocation needs a rect of 100x500. The ideal bucket is LARGE_BUCKET // (500 >= 256). Without the bucket fix the 100x1010 free strip would still be // in SMALL_BUCKET and this allocation would fail. assert!( atlas.allocate(size2(100, 500)).is_some(), "Should find the grown free strip in the correct bucket" ); atlas.deallocate(a); // Also test the single-root early-return path in grow(). let mut atlas2 = AtlasAllocator::with_options( size2(20, 20), &AllocatorOptions { small_size_threshold: 32, large_size_threshold: 256, ..DEFAULT_OPTIONS }, ); } ``` -------------------------------- ### Allocation and Change Structures Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Data structures representing allocations, changes, and lists of changes within the allocator. ```rust #[repr(C)] #[derive(Copy, Clone, Debug, PartialEq)] pub struct Allocation { pub id: AllocId, pub rectangle: Rectangle, } #[repr(C)] #[derive(Copy, Clone, Debug, PartialEq)] pub struct Change { pub old: Allocation, pub new: Allocation, } #[derive(Clone, Debug, PartialEq)] pub struct ChangeList { pub changes: Vec, pub failures: Vec, } impl ChangeList { pub fn empty() -> Self { ChangeList { changes: Vec::new(), failures: Vec::new(), } } } ``` -------------------------------- ### size2 Source: https://docs.rs/guillotiere/latest/guillotiere/fn.size2.html Creates a Size2D value using the provided width and height. This is a convenience function equivalent to Size2D::new(w, h). ```APIDOC ## size2 ### Description Creates a `Size2D` value with the given width and height. This is a shorthand for `Size2D::new(w, h)`. ### Function Signature ```rust pub const fn size2(w: T, h: T) -> Size2D ``` ### Parameters - `w` (T) - The width component of the size. - `h` (T) - The height component of the size. ### Returns - `Size2D` - A new `Size2D` instance with the specified width and height. ### Example ```rust let size = size2(10, 20); ``` ``` -------------------------------- ### Node Splitting and Allocation Logic Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Handles the logic for splitting nodes and updating the allocator tree structure when allocating space, accounting for orientation changes and leftover rectangles. ```rust let leftover_id; if orientation == current_orientation { if !split_rect.is_empty() { let next_sibling = chosen_node.next_sibling; split_id = self.new_node(); self.nodes[split_id.index()] = Node { parent: chosen_node.parent, next_sibling, prev_sibling: chosen_id, rect: split_rect, kind: NodeKind::Free, orientation: current_orientation, }; self.nodes[chosen_id.index()].next_sibling = split_id; if next_sibling.is_some() { self.nodes[next_sibling.index()].prev_sibling = split_id; } } else { split_id = AllocIndex::NONE; } if !leftover_rect.is_empty() { self.nodes[chosen_id.index()].kind = NodeKind::Container; allocated_id = self.new_node(); leftover_id = self.new_node(); self.nodes[allocated_id.index()] = Node { parent: chosen_id, next_sibling: leftover_id, prev_sibling: AllocIndex::NONE, rect: allocated_rect, kind: NodeKind::Alloc, orientation: current_orientation.flipped(), }; self.nodes[leftover_id.index()] = Node { parent: chosen_id, next_sibling: AllocIndex::NONE, prev_sibling: allocated_id, rect: leftover_rect, kind: NodeKind::Free, orientation: current_orientation.flipped(), }; } else { // No need to split for the leftover area, we can allocate directly in the chosen node. allocated_id = chosen_id; let node = &mut self.nodes[chosen_id.index()]; node.kind = NodeKind::Alloc; node.rect = allocated_rect; leftover_id = AllocIndex::NONE } } else { self.nodes[chosen_id.index()].kind = NodeKind::Container; if !split_rect.is_empty() { split_id = self.new_node(); self.nodes[split_id.index()] = Node { parent: chosen_id, next_sibling: AllocIndex::NONE, prev_sibling: AllocIndex::NONE, rect: split_rect, kind: NodeKind::Free, orientation: current_orientation.flipped(), }; } else { split_id = AllocIndex::NONE; } if !leftover_rect.is_empty() { let container_id = self.new_node(); self.nodes[container_id.index()] = Node { parent: chosen_id, next_sibling: split_id, prev_sibling: AllocIndex::NONE, rect: Rectangle::zero(), kind: NodeKind::Container, orientation: current_orientation.flipped(), }; self.nodes[split_id.index()].prev_sibling = container_id; allocated_id = self.new_node(); leftover_id = self.new_node(); self.nodes[allocated_id.index()] = Node { parent: container_id, next_sibling: leftover_id, prev_sibling: AllocIndex::NONE, rect: allocated_rect, kind: NodeKind::Alloc, orientation: current_orientation, }; self.nodes[leftover_id.index()] = Node { parent: container_id, next_sibling: AllocIndex::NONE, prev_sibling: allocated_id, rect: leftover_rect, kind: NodeKind::Free, orientation: current_orientation, }; } else { allocated_id = self.new_node(); self.nodes[allocated_id.index()] = Node { parent: chosen_id, next_sibling: split_id, prev_sibling: AllocIndex::NONE, rect: allocated_rect, kind: NodeKind::Alloc, orientation: current_orientation.flipped(), }; self.nodes[split_id.index()].prev_sibling = allocated_id; } ``` -------------------------------- ### Allocator Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html A dynamic texture atlas allocator using the guillotine algorithm. The guillotine algorithm is assisted by a data structure that keeps track of neighboring rectangles to provide fast deallocation and coalescing. ```APIDOC ## Allocator ### Description A dynamic texture atlas allocator using the guillotine algorithm. The guillotine algorithm is assisted by a data structure that keeps track of neighboring rectangles to provide fast deallocation and coalescing. ### Goals - Coalescing free rectangles can be expensive under real-time constraints; this implementation provides fast (constant time) search for merge candidates at the expense of some bookkeeping overhead. - The subdivision scheme uses the worst fit variant of the guillotine algorithm for simplicity and CPU efficiency. ``` -------------------------------- ### Iteration over Free Rectangles Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Invokes a callback for each free rectangle currently in the atlas. ```rust /// Invoke a callback for each free rectangle in the atlas. pub fn for_each_free_rectangle(&self, mut callback: F) where F: FnMut(&Rectangle), { for node in &self.nodes { if node.kind == NodeKind::Free { callback(&node.rect); } } } ``` -------------------------------- ### Rearrange the atlas to reduce fragmentation Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Calls resize_and_rearrange with the current size, returning a ChangeList. Previous ids and rectangles become invalid after this operation. ```rust /// Recompute the allocations in the atlas and returns a list of the changes. /// /// Previous ids and rectangles are not valid anymore after this operation as each id/rectangle /// pair is assigned to new values which are communicated in the returned change list. /// Rearranging the atlas can help reduce fragmentation. pub fn rearrange(&mut self) -> ChangeList { let size = self.size; self.resize_and_rearrange(size) } ``` -------------------------------- ### test_grow test Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Verifies that the atlas can be grown to a larger size. ```rust #[test] fn test_grow() { let mut atlas = AtlasAllocator::new(size2(1000, 1000)); atlas.grow(size2(2000, 2000)); let full = atlas.allocate(size2(2000, 2000)).unwrap().id; ``` -------------------------------- ### Allocate a rectangle Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Allocates a rectangle of the requested size in the atlas, using bucket-based selection and splitting logic. ```rust pub fn allocate(&mut self, mut requested_size: Size) -> Option { if requested_size.is_empty() { return None; } adjust_size(self.alignment.width, &mut requested_size.width); adjust_size(self.alignment.height, &mut requested_size.height); let ideal_bucket = free_list_for_size( self.small_size_threshold, self.large_size_threshold, &requested_size, ); let use_worst_fit = ideal_bucket == LARGE_BUCKET; let mut chosen_rect = None; for bucket in ideal_bucket..NUM_BUCKETS { let mut candidate_score = if use_worst_fit { 0 } else { i32::MAX }; let mut candidate = None; for (index, rect) in self.free_rects[bucket].iter().enumerate() { let dx = rect.width() - requested_size.width; let dy = rect.height() - requested_size.height; if dx >= 0 && dy >= 0 { if dx == 0 || dy == 0 { // Perfect fit! candidate = Some(index); break; } let score = i32::min(dx, dy); if (use_worst_fit && score > candidate_score) || (!use_worst_fit && score < candidate_score) { candidate_score = score; candidate = Some(index); } } } if let Some(index) = candidate { let rect = self.free_rects[bucket].remove(index); chosen_rect = Some(rect); break; } } if let Some(rect) = chosen_rect { let (split_rect, leftover_rect, _) = guillotine_rect(&rect, requested_size, Orientation::Vertical); self.add_free_rect(&split_rect); self.add_free_rect(&leftover_rect); return Some(Rectangle { min: rect.min, max: rect.min + requested_size.to_vector(), }); } None } ``` -------------------------------- ### AllocId::serialize Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AllocId.html Serializes the AllocId into a u32 value. ```APIDOC ## AllocId::serialize ### Description Serializes the AllocId into a u32 value. ### Method pub fn serialize(&self) -> u32 ### Parameters None. ### Returns u32 - The serialized representation of the AllocId. ``` -------------------------------- ### AllocatorOptions Struct Definition Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AllocatorOptions.html The AllocatorOptions struct definition with its public fields and their descriptions. ```APIDOC ## Struct AllocatorOptions ### Description Options to tweak the behavior of the atlas allocator. ### Definition ```rust #[repr(C)] pub struct AllocatorOptions { pub alignment: Size, pub small_size_threshold: i32, pub large_size_threshold: i32, } ``` ### Fields - **alignment** (Size) - Round the rectangle sizes up to a multiple of this value. Width and height alignments must be superior to zero. Default value: (1, 1). - **small_size_threshold** (i32) - Value below which a size is considered small. This value is used to speed up the storage and lookup of free rectangles. This value must be inferior or equal to `large_size_threshold`. Default value: 32. - **large_size_threshold** (i32) - Value above which a size is considered large. This value is used to speed up the storage and lookup of free rectangles. This value must be inferior or equal to `large_size_threshold`. Default value: 256. ### Trait Implementations - **Clone** - Provides `clone` and `clone_from` methods. - **Copy** - Marker trait for types that can be copied. - **Debug** - Provides `fmt` for formatting. - **Default** - Provides `default` method returning the default value. - **Eq** - Marker trait for equality. - **Hash** - Provides `hash` and `hash_slice` methods. - **PartialEq** - Provides `eq` and `ne` methods. - **StructuralPartialEq** - Marker trait for structural equality. ### Auto Trait Implementations - Freeze - RefUnwindSafe - Send - Sync - Unpin - UnsafeUnpin - UnwindSafe ### Blanket Implementations - Any, Borrow, BorrowMut, CloneToUninit, From, Into, ToOwned, TryFrom, TryInto ``` -------------------------------- ### AtlasAllocator Size Query Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Retrieves the total size of the atlas. ```rust /// The total size of the atlas. pub fn size(&self) -> Size { self.size } ``` -------------------------------- ### Guillotine Splitting Logic Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Determines how to split a chosen rectangle into allocated, split, and leftover regions based on requested size. ```rust fn guillotine_rect( chosen_rect: &Rectangle, requested_size: Size, default_orientation: Orientation, ) -> (Rectangle, Rectangle, Orientation) { let candidate_leftover_rect_to_right = Rectangle { min: chosen_rect.min + vec2(requested_size.width, 0), max: point2(chosen_rect.max.x, chosen_rect.min.y + requested_size.height), }; let candidate_leftover_rect_to_bottom = Rectangle { min: chosen_rect.min + vec2(0, requested_size.height), max: point2(chosen_rect.min.x + requested_size.width, chosen_rect.max.y), }; let split_rect; let leftover_rect; let orientation; if requested_size == chosen_rect.size() { orientation = default_orientation; split_rect = Rectangle::zero(); leftover_rect = Rectangle::zero(); } else if safe_area(&candidate_leftover_rect_to_right) > safe_area(&candidate_leftover_rect_to_bottom) { leftover_rect = candidate_leftover_rect_to_bottom; split_rect = Rectangle { min: candidate_leftover_rect_to_right.min, max: point2(candidate_leftover_rect_to_right.max.x, chosen_rect.max.y), }; orientation = Orientation::Horizontal; } else { leftover_rect = candidate_leftover_rect_to_right; split_rect = Rectangle { min: candidate_leftover_rect_to_bottom.min, max: point2(chosen_rect.max.x, candidate_leftover_rect_to_bottom.max.y), }; orientation = Orientation::Vertical; } (split_rect, leftover_rect, orientation) } ``` -------------------------------- ### Merging siblings visualization Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html Visual representation of the tree update process when deallocating a rectangle and merging siblings. ```text +---+---+---+ # +-------+---+ # | | |///| | | |///| | | A | B |/C/| +---+---+ | AB |/C/| +---+---+ | | |///| | | | |///| | | +---+---+---+ # D +-------+---+ # D | D | | -> | D | | | | +-+-+ | | +-+-+ | | | | | | | | | +-----------+ A B C +-----------+ AB C ``` -------------------------------- ### Test simple_atlas Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Tests basic allocation functionality in SimpleAtlasAllocator and ensures that allocated rectangles do not intersect. ```rust #[test] fn simple_atlas() { let mut atlas = SimpleAtlasAllocator::new(size2(1000, 1000)); assert!(atlas.allocate(size2(1, 1001)).is_none()); assert!(atlas.allocate(size2(1001, 1)).is_none()); let mut rectangles = Vec::new(); rectangles.push(atlas.allocate(size2(100, 1000)).unwrap()); rectangles.push(atlas.allocate(size2(900, 200)).unwrap()); rectangles.push(atlas.allocate(size2(300, 200)).unwrap()); rectangles.push(atlas.allocate(size2(200, 300)).unwrap()); rectangles.push(atlas.allocate(size2(100, 300)).unwrap()); rectangles.push(atlas.allocate(size2(100, 300)).unwrap()); rectangles.push(atlas.allocate(size2(100, 300)).unwrap()); assert!(atlas.allocate(size2(800, 800)).is_none()); for i in 0..rectangles.len() { for j in 0..rectangles.len() { if i == j { continue; } assert!(!rectangles[i].intersects(&rectangles[j])); } } } ``` -------------------------------- ### Test allocate_negative Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Verifies that negative dimensions in allocation requests are rejected by the allocator. ```rust #[test] fn allocate_negative() { let mut atlas = SimpleAtlasAllocator::new(size2(1000, 1000)); assert!(atlas.allocate(size2(-1, 1)).is_none()); assert!(atlas.allocate(size2(1, -1)).is_none()); assert!(atlas.allocate(size2(-1, -1)).is_none()); assert!(atlas.allocate(size2(-167114179, -718142)).is_none()); } ``` -------------------------------- ### dump_into_svg function Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Dumps a visual representation of the atlas in SVG format. If a rectangle is provided, the output is translated and scaled to fit it. ```rust pub fn dump_into_svg(atlas: &AtlasAllocator, rect: Option<&Rectangle>, output: &mut dyn std::io::Write) -> std::io::Result<()> { use svg_fmt::*; let (sx, sy, tx, ty) = if let Some(rect) = rect { ( rect.width() as f32 / atlas.size.width as f32, rect.height() as f32 / atlas.size.height as f32, rect.min.x as f32, rect.min.y as f32, ) } else { (1.0, 1.0, 0.0, 0.0) }; for node in &atlas.nodes { let color = match node.kind { NodeKind::Free => rgb(50, 50, 50), NodeKind::Alloc => rgb(70, 70, 180), _ => { continue; } }; let (x, y) = node.rect.min.to_f32().to_tuple(); let (w, h) = node.rect.size().to_f32().to_tuple(); writeln!( output, r#" {}"#, rectangle(tx + x * sx, ty + y * sy, w * sx, h * sy) .fill(color) .stroke(Stroke::Color(black(), 1.0)) )?; } Ok(()) } ``` -------------------------------- ### Iteration over Allocated Rectangles Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html Invokes a callback for each allocated rectangle in the atlas, providing the allocation ID and the rectangle. ```rust /// Invoke a callback for each allocated rectangle in the atlas. pub fn for_each_allocated_rectangle(&self, mut callback: F) where F: FnMut(AllocId, &Rectangle), { for (i, node) in self.nodes.iter().enumerate() { if node.kind != NodeKind::Alloc { continue; } let id = self.alloc_id(AllocIndex(i as u32)); callback(id, &node.rect); } } ``` -------------------------------- ### AtlasAllocator struct definition Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html The primary structure definition for the AtlasAllocator. ```rust pub struct AtlasAllocator { /* private fields */ } ```