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