graphics/
texture_packer.rs

1//! Texture packing.
2
3use crate::ImageSize;
4
5/// A texture packer using a skyline heuristic.
6///
7/// For offline texture packing, see [texture_packer](https://github.com/pistondevelopers/texture_packer).
8///
9/// Designed for adding textures one by one to current texture atlas.
10/// Packs tiles without backtracking or knowledge about future tiles.
11///
12/// - Perfect at packing tiles of same size
13/// - Good at packing tiles of some unit size
14/// - Decent at packing tiles of similar sizes
15/// - Can be used with pre-sorted tile sizes for better packing
16///
17/// Can also be used as storage for textures.
18///
19/// ### Design
20///
21/// A skyline is a list of non-hole atlas offsets,
22/// used to efficiently determine a good place to put the next tile.
23///
24/// In this texture packer,
25/// only a single skyline is kept track of,
26/// since new texture atlases are created by need.
27///
28/// This texture packer has runtime complexity `O(N^2)` for inserting a new tile,
29/// where `N` is the number of points in the skyline.
30/// Since `N` is usually a low number, the packing is pretty fast.
31///
32/// The algorithm was designed by Sven Nilsen (2019) for Piston-Graphics.
33pub struct TexturePacker<T> {
34    /// Stores current texture atlas and previously created ones.
35    pub textures: Vec<T>,
36    /// The index to the current texture atlas.
37    pub atlas: usize,
38    /// Texture atlas offsets from left to right.
39    ///
40    /// When a new tile is added with same offset,
41    /// it updates the atlas offsets that it overlaps.
42    /// This means that "holes" get filled in over time.
43    pub skyline: Vec<[u32; 2]>,
44}
45
46impl<T: ImageSize> TexturePacker<T> {
47    /// Returns a new `TexturePacker`.
48    pub fn new() -> TexturePacker<T> {
49        TexturePacker {
50            textures: vec![],
51            atlas: 0,
52            skyline: vec![],
53        }
54    }
55
56    /// Create a new texture atlas with an initial tile.
57    ///
58    /// The new texture atlas is made the current one.
59    pub fn create(&mut self, size: [u32; 2], texture: T) -> usize {
60        let id = self.textures.len();
61        if !self.textures.is_empty() {
62            self.atlas += 1;
63        }
64        self.skyline = vec![[0, size[1]], [size[0], 0]];
65        self.textures.push(texture);
66        id
67    }
68
69    /// Update current texture atlas.
70    ///
71    /// - ind: index of atlas offset in the skyline
72    /// - size: size of new tile
73    ///
74    /// Returns the index of the current texture atlas and
75    /// the atlas offset of the new tile.
76    pub fn update(&mut self, ind: usize, size: [u32; 2]) -> (usize, [u32; 2]) {
77        let texture = self.atlas;
78        let offset = self.skyline[ind];
79
80        // Increase y-value of atlas offsets that are matched.
81        let mut w = 0;
82        for i in ind..self.skyline.len() {
83            if self.skyline[i][1] <= offset[1] {
84                self.skyline[i][1] = offset[1] + size[1];
85            }
86            w = self.skyline[i][0] - offset[0];
87            if w >= size[1] {
88                break;
89            }
90        }
91        if w == 0 {
92            // There is no end-point atlas offset.
93            // Add new atlas offset point.
94            self.skyline.push([offset[0] + size[0], offset[1]]);
95            self.skyline.sort();
96        }
97
98        (texture, offset)
99    }
100
101    /// Returns the index of atlas offset in skyline with room for a new tile.
102    ///
103    /// Returns `None` if no room was found in the current texture atlas.
104    pub fn find_space(&self, size: [u32; 2]) -> Option<usize> {
105        if self.textures.is_empty() {
106            return None;
107        };
108
109        let texture = &self.textures[self.atlas];
110        let mut min: Option<(usize, u32)> = None;
111        for i in 0..self.skyline.len() {
112            let a = self.skyline[i];
113            let mut nxt = [texture.get_width(), texture.get_height()];
114            // Ignore next atlas offsets that have smaller y-value,
115            // because they do not interfer.
116            for j in i + 1..self.skyline.len() {
117                let b = self.skyline[j];
118                nxt[0] = b[0];
119                if b[1] > a[1] {
120                    break;
121                };
122            }
123            if nxt[0] - a[0] >= size[0] && nxt[1] - a[1] >= size[1] {
124                // There is room for the glyph.
125                if min.is_none()
126                    || min.unwrap().1 > nxt[0] - a[0]
127                    || self.skyline[min.unwrap().0][1] > a[1]
128                {
129                    // Pick the space with smallest y-value.
130                    min = Some((i, nxt[0] - a[0]));
131                }
132            }
133        }
134        min.map(|n| n.0)
135    }
136}
137
138impl<T: ImageSize> Default for TexturePacker<T> {
139    fn default() -> TexturePacker<T> {
140        TexturePacker::new()
141    }
142}
graphics/texture_packer.rs

graphics/
texture_packer.rs
