1#![allow(dead_code)]
2
3struct Node {
4 x: usize,
5 y: usize,
6 width: usize,
7}
8
9/// Represents an atlas for packing rectangles.
10pub struct Atlas {
11 width: usize,
12 height: usize,
13 nodes: Vec<Node>,
14}
15
16impl Atlas {
17 /// Creates a new atlas with the specified width and height.
18 pub fn new(width: usize, height: usize) -> Self {
19 Self {
20 width,
21 height,
22 nodes: vec![Node { x: 0, y: 0, width }],
23 }
24 }
25
26 /// Returns the size (width and height) of the atlas.
27 pub fn size(&self) -> (usize, usize) {
28 (self.width, self.height)
29 }
30
31 /// Expands the atlas to the specified width and height.
32 pub fn expand(&mut self, width: usize, height: usize) {
33 // Insert node for empty space
34
35 if width > self.width {
36 self.insert_node(self.nodes.len(), self.width, 0, width - self.width);
37 }
38
39 self.width = width;
40 self.height = height;
41 }
42
43 /// Resets the atlas to the specified width and height.
44 pub fn reset(&mut self, width: usize, height: usize) {
45 *self = Self::new(width, height);
46 }
47
48 /// Adds a rectangle with the specified width and height to the atlas.
49 ///
50 /// Returns the position (x, y) of the added rectangle, or `None` if the rectangle cannot be added.
51 pub fn add_rect(&mut self, rect_width: usize, rect_height: usize) -> Option<(usize, usize)> {
52 let mut besth = self.height;
53 let mut bestw = self.width;
54 let mut besti = None;
55 let mut bestx = 0;
56 let mut besty = 0;
57
58 // Bottom left fit heuristic.
59 for i in 0..self.nodes.len() {
60 if let Some(y) = self.rect_fits(i, rect_width, rect_height) {
61 if y + rect_height < besth || (y + rect_height == besth && self.nodes[i].width < bestw) {
62 besti = Some(i);
63 bestw = self.nodes[i].width;
64 besth = y + rect_height;
65 bestx = self.nodes[i].x;
66 besty = y;
67 }
68 }
69 }
70
71 if let Some(besti) = besti {
72 // Perform the actual packing.
73 self.add_skyline_level(besti, bestx, besty, rect_width, rect_height);
74 return Some((bestx, besty));
75 }
76
77 None
78 }
79
80 fn insert_node(&mut self, idx: usize, x: usize, y: usize, width: usize) {
81 self.nodes.insert(idx, Node { x, y, width });
82 }
83
84 fn remove_node(&mut self, idx: usize) {
85 self.nodes.remove(idx);
86 }
87
88 fn add_skyline_level(&mut self, idx: usize, x: usize, y: usize, width: usize, height: usize) {
89 // Insert new node
90 self.insert_node(idx, x, y + height, width);
91
92 // Delete skyline segments that fall under the shadow of the new segment.
93 let mut i = idx + 1;
94
95 while i < self.nodes.len() {
96 if self.nodes[i].x < self.nodes[i - 1].x + self.nodes[i - 1].width {
97 let shrink = self.nodes[i - 1].x + self.nodes[i - 1].width - self.nodes[i].x;
98
99 self.nodes[i].x += shrink;
100 let new_width = self.nodes[i].width as isize - shrink as isize;
101
102 if new_width <= 0 {
103 self.remove_node(i);
104 i -= 1;
105 } else {
106 self.nodes[i].width = new_width as usize;
107 break;
108 }
109 } else {
110 break;
111 }
112
113 i += 1;
114 }
115
116 // Merge same height skyline segments that are next to each other.
117 let mut i = 0isize;
118
119 while i < self.nodes.len() as isize - 1 {
120 let index = i as usize;
121
122 if self.nodes[index].y == self.nodes[index + 1].y {
123 self.nodes[index].width += self.nodes[index + 1].width;
124 self.remove_node(index + 1);
125
126 i -= 1;
127 }
128
129 i += 1;
130 }
131 }
132
133 fn rect_fits(&self, mut idx: usize, width: usize, height: usize) -> Option<usize> {
134 // Checks if there is enough space at the location of skyline span 'i',
135 // and return the max height of all skyline spans under that at that location,
136 // (think tetris block being dropped at that position). Or -1 if no space found.
137
138 let x = self.nodes[idx].x;
139 let mut y = self.nodes[idx].y;
140
141 if x + width > self.width {
142 return None;
143 }
144
145 let mut space_left = width as isize;
146
147 while space_left > 0 {
148 if idx == self.nodes.len() {
149 return None;
150 }
151
152 y = y.max(self.nodes[idx].y);
153
154 if y + height > self.height {
155 return None;
156 }
157
158 space_left -= self.nodes[idx].width as isize;
159 idx += 1;
160 }
161
162 Some(y)
163 }
164}
165