|
14717
|
1 |
use integral_geometry::{Rect, Size};
|
|
|
2 |
use std::cmp::{max, min, Ordering};
|
|
|
3 |
|
|
14720
|
4 |
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone)]
|
|
14717
|
5 |
struct Fit {
|
|
|
6 |
short_size: u32,
|
|
|
7 |
long_size: u32,
|
|
|
8 |
}
|
|
|
9 |
|
|
|
10 |
impl Fit {
|
|
|
11 |
fn new() -> Self {
|
|
|
12 |
Self {
|
|
|
13 |
short_size: u32::max_value(),
|
|
|
14 |
long_size: u32::max_value(),
|
|
|
15 |
}
|
|
|
16 |
}
|
|
|
17 |
|
|
|
18 |
fn measure(container: Size, size: Size) -> Option<Self> {
|
|
|
19 |
if container.contains(size) {
|
|
|
20 |
let x_leftover = container.width - size.width;
|
|
|
21 |
let y_leftover = container.height - size.height;
|
|
|
22 |
Some(Self {
|
|
|
23 |
short_size: min(x_leftover, y_leftover) as u32,
|
|
|
24 |
long_size: max(x_leftover, y_leftover) as u32,
|
|
|
25 |
})
|
|
|
26 |
} else {
|
|
|
27 |
None
|
|
|
28 |
}
|
|
|
29 |
}
|
|
|
30 |
}
|
|
|
31 |
|
|
14720
|
32 |
pub struct Atlas {
|
|
|
33 |
size: Size,
|
|
|
34 |
free_rects: Vec<Rect>,
|
|
|
35 |
used_rects: Vec<Rect>,
|
|
14717
|
36 |
}
|
|
|
37 |
|
|
|
38 |
impl Atlas {
|
|
|
39 |
pub fn new(size: Size) -> Self {
|
|
|
40 |
Self {
|
|
|
41 |
size,
|
|
|
42 |
free_rects: vec![Rect::at_origin(size)],
|
|
|
43 |
used_rects: vec![],
|
|
|
44 |
}
|
|
|
45 |
}
|
|
|
46 |
|
|
14720
|
47 |
pub fn size(&self) -> Size {
|
|
|
48 |
self.size
|
|
|
49 |
}
|
|
|
50 |
|
|
14717
|
51 |
fn find_position(&self, size: Size) -> Option<(Rect, Fit)> {
|
|
|
52 |
let mut best_rect = Rect::EMPTY;
|
|
|
53 |
let mut best_fit = Fit::new();
|
|
|
54 |
|
|
|
55 |
for rect in &self.free_rects {
|
|
|
56 |
if let Some(fit) = Fit::measure(rect.size(), size) {
|
|
|
57 |
if fit < best_fit {
|
|
|
58 |
best_fit = fit;
|
|
|
59 |
best_rect = Rect::from_size(rect.top_left(), size);
|
|
|
60 |
}
|
|
|
61 |
}
|
|
|
62 |
|
|
|
63 |
if let Some(fit) = Fit::measure(rect.size(), size.transpose()) {
|
|
|
64 |
if fit < best_fit {
|
|
|
65 |
best_fit = fit;
|
|
|
66 |
best_rect = Rect::from_size(rect.top_left(), size.transpose());
|
|
|
67 |
}
|
|
|
68 |
}
|
|
|
69 |
}
|
|
|
70 |
|
|
|
71 |
if best_rect == Rect::EMPTY {
|
|
|
72 |
None
|
|
|
73 |
} else {
|
|
|
74 |
Some((best_rect, best_fit))
|
|
|
75 |
}
|
|
|
76 |
}
|
|
|
77 |
|
|
|
78 |
fn prune(&mut self) {
|
|
|
79 |
self.free_rects = self
|
|
|
80 |
.free_rects
|
|
|
81 |
.iter()
|
|
|
82 |
.filter(|inner| {
|
|
|
83 |
self.free_rects
|
|
|
84 |
.iter()
|
|
|
85 |
.all(|outer| outer == *inner || !outer.contains_rect(inner))
|
|
|
86 |
})
|
|
|
87 |
.cloned()
|
|
|
88 |
.collect();
|
|
|
89 |
}
|
|
|
90 |
|
|
14720
|
91 |
pub fn insert(&mut self, size: Size) -> Option<Rect> {
|
|
|
92 |
let (rect, _) = self.find_position(size)?;
|
|
14717
|
93 |
|
|
|
94 |
let mut rects_to_process = self.free_rects.len();
|
|
|
95 |
let mut i = 0;
|
|
|
96 |
|
|
|
97 |
while i < rects_to_process {
|
|
|
98 |
let rects = split_rect(self.free_rects[i], rect);
|
|
|
99 |
if !rects.is_empty() {
|
|
|
100 |
self.free_rects.remove(i);
|
|
|
101 |
self.free_rects.extend(rects);
|
|
|
102 |
rects_to_process -= 1
|
|
|
103 |
} else {
|
|
|
104 |
i += 1;
|
|
|
105 |
}
|
|
|
106 |
}
|
|
|
107 |
|
|
|
108 |
self.used_rects.push(rect);
|
|
|
109 |
self.prune();
|
|
|
110 |
Some(rect)
|
|
|
111 |
}
|
|
|
112 |
|
|
|
113 |
pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<Rect>
|
|
|
114 |
where
|
|
|
115 |
Iter: Iterator<Item = Size>,
|
|
|
116 |
{
|
|
14720
|
117 |
let mut sizes: Vec<_> = sizes.collect();
|
|
|
118 |
let mut result = vec![];
|
|
|
119 |
|
|
|
120 |
while let Some((index, (rect, _))) = sizes
|
|
|
121 |
.iter()
|
|
|
122 |
.enumerate()
|
|
|
123 |
.filter_map(|(i, s)| self.find_position(*s).map(|res| (i, res)))
|
|
|
124 |
.min_by_key(|(_, (_, fit))| fit.clone())
|
|
|
125 |
{
|
|
|
126 |
result.push(rect);
|
|
|
127 |
sizes.swap_remove(index);
|
|
|
128 |
}
|
|
|
129 |
if sizes.is_empty() {
|
|
|
130 |
self.used_rects.extend_from_slice(&result);
|
|
|
131 |
result
|
|
|
132 |
} else {
|
|
|
133 |
vec![]
|
|
|
134 |
}
|
|
14717
|
135 |
}
|
|
|
136 |
|
|
|
137 |
pub fn reset(&mut self) {
|
|
|
138 |
self.free_rects.clear();
|
|
|
139 |
self.used_rects.clear();
|
|
|
140 |
self.free_rects.push(Rect::at_origin(self.size));
|
|
|
141 |
}
|
|
|
142 |
}
|
|
|
143 |
|
|
14720
|
144 |
pub struct AtlasCollection {
|
|
|
145 |
texture_size: Size,
|
|
|
146 |
atlases: Vec<Atlas>,
|
|
|
147 |
}
|
|
|
148 |
|
|
|
149 |
impl AtlasCollection {
|
|
|
150 |
pub fn new(texture_size: Size) -> Self {
|
|
|
151 |
Self {
|
|
|
152 |
texture_size,
|
|
|
153 |
atlases: vec![],
|
|
|
154 |
}
|
|
|
155 |
}
|
|
|
156 |
|
|
|
157 |
fn repack(&mut self, size: Size) -> bool {
|
|
|
158 |
for atlas in &mut self.atlases {
|
|
|
159 |
let mut temp_atlas = Atlas::new(atlas.size());
|
|
|
160 |
let sizes = atlas
|
|
|
161 |
.used_rects
|
|
|
162 |
.iter()
|
|
|
163 |
.map(|r| r.size())
|
|
|
164 |
.chain(std::iter::once(size));
|
|
|
165 |
if !temp_atlas.insert_set(sizes).is_empty() {
|
|
|
166 |
std::mem::swap(atlas, &mut temp_atlas);
|
|
|
167 |
return true;
|
|
|
168 |
}
|
|
|
169 |
}
|
|
|
170 |
false
|
|
|
171 |
}
|
|
|
172 |
|
|
|
173 |
pub fn insert_sprite(&mut self, size: Size) -> bool {
|
|
|
174 |
if !self.texture_size.contains(size) {
|
|
|
175 |
false
|
|
|
176 |
} else {
|
|
|
177 |
if let Some(rect) = self
|
|
|
178 |
.atlases
|
|
|
179 |
.iter_mut()
|
|
|
180 |
.find_map(|a| a.insert(size))
|
|
|
181 |
{
|
|
|
182 |
|
|
|
183 |
} else if !self.repack(size) {
|
|
|
184 |
let mut atlas = Atlas::new(self.texture_size);
|
|
|
185 |
atlas.insert(size);
|
|
|
186 |
self.atlases.push(atlas);
|
|
|
187 |
}
|
|
|
188 |
true
|
|
|
189 |
}
|
|
|
190 |
}
|
|
|
191 |
}
|
|
|
192 |
|
|
|
193 |
fn split_rect(free_rect: Rect, rect: Rect) -> Vec<Rect> {
|
|
|
194 |
let mut result = vec![];
|
|
|
195 |
if free_rect.intersects(&rect) {
|
|
|
196 |
if rect.left() > free_rect.left() {
|
|
|
197 |
let trim = free_rect.right() - rect.left() + 1;
|
|
|
198 |
result.push(free_rect.with_margins(0, -trim, 0, 0))
|
|
|
199 |
}
|
|
|
200 |
if rect.right() < free_rect.right() {
|
|
|
201 |
let trim = rect.right() - free_rect.left() + 1;
|
|
|
202 |
result.push(free_rect.with_margins(-trim, 0, 0, 0))
|
|
|
203 |
}
|
|
|
204 |
if rect.top() > free_rect.top() {
|
|
|
205 |
let trim = free_rect.bottom() - rect.top() + 1;
|
|
|
206 |
result.push(free_rect.with_margins(0, 0, 0, -trim));
|
|
|
207 |
}
|
|
|
208 |
if rect.bottom() < free_rect.bottom() {
|
|
|
209 |
let trim = rect.bottom() - free_rect.top() + 1;
|
|
|
210 |
result.push(free_rect.with_margins(0, 0, -trim, 0));
|
|
|
211 |
}
|
|
|
212 |
}
|
|
|
213 |
result
|
|
|
214 |
}
|
|
|
215 |
|
|
14717
|
216 |
#[cfg(test)]
|
|
|
217 |
mod tests {
|
|
|
218 |
use super::Atlas;
|
|
|
219 |
use integral_geometry::{Rect, Size};
|
|
|
220 |
|
|
|
221 |
#[test]
|
|
|
222 |
fn insert() {
|
|
|
223 |
let atlas_size = Size::square(16);
|
|
|
224 |
let mut atlas = Atlas::new(atlas_size);
|
|
|
225 |
|
|
14720
|
226 |
assert_eq!(None, atlas.insert(Size::square(20)));
|
|
14717
|
227 |
|
|
|
228 |
let rect_size = Size::new(11, 3);
|
|
14720
|
229 |
let rect = atlas.insert(rect_size).unwrap();
|
|
14717
|
230 |
assert_eq!(rect, Rect::at_origin(rect_size));
|
|
|
231 |
assert_eq!(2, atlas.free_rects.len());
|
|
|
232 |
}
|
|
|
233 |
}
|