etagere/
lib.rs

1//! Dynamic texture atlas allocation using the shelf packing algorithm.
2//!
3//! ## Texture atlas allocation
4//!
5//! The goal of a texture atlas allocator is to pack multiple rectangles into a larger one.
6//! When rendering 2D or 3D graphics on the GPU, this packing important for draw call batching. 
7//!
8//! This crate provides two implementations of the shelf packing algorithm for *dynamic*
9//! texture atlas allocation (dynamic here means supporting both allocation and deallocation).
10//!
11//! [A thousand ways to pack the bin](https://github.com/juj/RectangleBinPack/blob/master/RectangleBinPack.pdf)
12//! is a good resource to learn about rectangle packing algorithms, although it does not not cover
13//! deallocation which complicates the problem space a fair bit.
14//!
15//! The shelf packing algorithm is explained in the above document. It isn't the most efficient
16//! packing strategy, however its simplicity makes it possible to support reasonably fast deallocation.
17//! Note that the [guillotiere](https://crates.io/crates/guillotiere) crate implements a similar API
18//! using the guillotine packing algorithm and may or may not provide better results depending on the
19//! type of workload.
20//!
21//! ## Two allocators
22//!
23//! - [`AtlasAllocator`] Tracks allocations for each individual item and does a reasonable
24//!   job of dealing with fragmentation, at a runtime cost.
25//! - [`BucketedAtlasAllocator`] groups items by buckets and only reclaim the space occupied
26//!   by a bucket when all of its items are deallocated. In addition, it has limited support
27//!   for merging consecutive empty shelves. These limitations allow faster allocation and
28//!   deallocation, making it an appealing option when the atlas is expected to hold a very
29//!   large amount of small items.
30//!
31//! Both allocators support:
32//! - Requiring an alignment for the items.
33//! - Packing into vertical shelves instead of horizontal ones (might provide a better output
34//!   for some workloads).
35//! - Splitting the allocator into multiple columns in order to make shelves smaller and allow
36//!   more of them.
37//! - Dumping the content of the atlas in SVG format for easy debugging.
38//!
39//! See [`AllocatorOptions`](struct.AllocatorOptions.html)
40//!
41//! In addition, this repository contains a command-line application to experiment with and
42//! test the implementations interactively.
43//!
44//! ## Example
45//!
46//! ```rust
47//! use etagere::*;
48//!
49//! let mut atlas = AtlasAllocator::new(size2(1000, 1000));
50//!
51//! let a = atlas.allocate(size2(100, 100)).unwrap();
52//! let b = atlas.allocate(size2(900, 200)).unwrap();
53//! println!("Allocated {:?} and {:?}", a.rectangle, b.rectangle);
54//!
55//! atlas.deallocate(a.id);
56//!
57//! let c = atlas.allocate(size2(300, 200)).unwrap();
58//!
59//! atlas.deallocate(c.id);
60//! atlas.deallocate(b.id);
61//! ```
62//!
63//! ## License
64//!
65//! Licensed under either of
66//!
67//!  * Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or https://www.apache.org/licenses/LICENSE-2.0)
68//!  * MIT license ([LICENSE-MIT](LICENSE-MIT) or https://opensource.org/licenses/MIT)
69//!
70//! at your option.
71//!
72//!
73//! [`AtlasAllocator`]: struct.AtlasAllocator.html
74//! [`BucketedAtlasAllocator`]: struct.BucketedAtlasAllocator.html
75
76#[cfg(feature = "serde")]
77#[macro_use]
78pub extern crate serde;
79pub extern crate euclid;
80
81mod bucketed;
82mod allocator;
83#[cfg(feature = "ffi")]
84pub mod ffi;
85
86pub use allocator::*;
87pub use bucketed::*;
88pub use euclid::{point2, size2};
89
90pub type Point = euclid::default::Point2D<i32>;
91pub type Size = euclid::default::Size2D<i32>;
92pub type Rectangle = euclid::default::Box2D<i32>;
93
94/// Options to tweak the behavior of the atlas allocator.
95#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
96#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
97pub struct AllocatorOptions {
98    /// Align item sizes to a multiple of this alignment.
99    ///
100    /// Default value: [1, 1] (no alignment).
101    pub alignment: Size,
102    /// Use vertical instead of horizontal shelves.
103    ///
104    /// Default value: false.
105    pub vertical_shelves: bool,
106    /// If possible split the allocator's surface into multiple columns.
107    ///
108    /// Having multiple columns allows having more (smaller shelves).
109    ///
110    /// Default value: 1.
111    pub num_columns: i32,
112}
113
114pub const DEFAULT_OPTIONS: AllocatorOptions = AllocatorOptions {
115    vertical_shelves: false,
116    alignment: size2(1, 1),
117    num_columns: 1,
118};
119
120impl Default for AllocatorOptions {
121    fn default() -> Self {
122        DEFAULT_OPTIONS
123    }
124}
125
126/// The `AllocId` and `Rectangle` resulting from an allocation.
127#[repr(C)]
128#[derive(Copy, Clone, Debug, PartialEq)]
129#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
130pub struct Allocation {
131    pub id: AllocId,
132    pub rectangle: Rectangle,
133}
134
135/// ID referring to an allocated rectangle.
136#[repr(C)]
137#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
138#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
139pub struct AllocId(pub(crate) u32);
140
141impl AllocId {
142    #[inline]
143    pub(crate) fn new(index: u16, gen: u16) -> Self {
144        AllocId(index as u32 | ((gen as u32) << 16))
145    }
146
147    #[inline]
148    pub(crate) fn index(&self) -> u16 {
149        self.0 as u16
150    }
151
152    #[inline]
153    pub(crate) fn generation(&self) -> u16 {
154        (self.0 >> 16) as u16
155    }
156
157    #[inline]
158    pub fn serialize(&self) -> u32 {
159        self.0
160    }
161
162    #[inline]
163    pub fn deserialize(bytes: u32) -> Self {
164        AllocId(bytes)
165    }
166}
167
etagere/lib.rs

etagere/
lib.rs
