Source code

Revision control

Other Tools

1
/* This Source Code Form is subject to the terms of the Mozilla Public
2
* License, v. 2.0. If a copy of the MPL was not distributed with this
3
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5
use api::units::{DeviceIntPoint, DeviceIntRect, DeviceIntSize};
6
7
//TODO: gather real-world statistics on the bin usage in order to assist the decision
8
// on where to place the size thresholds.
9
10
/// This is an optimization tweak to enable looking through all the free rectangles in a bin
11
/// and choosing the smallest, as opposed to picking the first match.
12
const FIND_SMALLEST_AREA: bool = false;
13
14
const NUM_BINS: usize = 3;
15
/// The minimum number of pixels on each side that we require for rects to be classified as
16
/// particular bin of freelists.
17
const MIN_RECT_AXIS_SIZES: [i32; NUM_BINS] = [1, 16, 32];
18
19
#[derive(Debug, Clone, Copy, PartialEq, PartialOrd)]
20
struct FreeListBin(u8);
21
22
#[derive(Debug, Clone, Copy)]
23
struct FreeListIndex(usize);
24
25
impl FreeListBin {
26
fn for_size(size: &DeviceIntSize) -> Self {
27
MIN_RECT_AXIS_SIZES
28
.iter()
29
.enumerate()
30
.rev()
31
.find(|(_, &min_size)| min_size <= size.width && min_size <= size.height)
32
.map(|(id, _)| FreeListBin(id as u8))
33
.expect("Unable to find a bin!")
34
}
35
}
36
37
#[derive(Debug, Clone, Copy, PartialEq)]
38
#[cfg_attr(feature = "capture", derive(Serialize))]
39
#[cfg_attr(feature = "replay", derive(Deserialize))]
40
pub struct FreeRectSlice(pub u32);
41
42
#[cfg_attr(feature = "capture", derive(Serialize))]
43
#[cfg_attr(feature = "replay", derive(Deserialize))]
44
pub struct FreeRect {
45
slice: FreeRectSlice,
46
rect: DeviceIntRect,
47
}
48
49
/// A texture allocator using the guillotine algorithm with the rectangle merge improvement. See
50
/// sections 2.2 and 2.2.5 in "A Thousand Ways to Pack the Bin - A Practical Approach to Two-
51
/// Dimensional Rectangle Bin Packing":
52
///
54
///
55
/// This approach was chosen because of its simplicity, good performance, and easy support for
56
/// dynamic texture deallocation.
57
///
58
/// Note: the allocations are spread across multiple textures, and also are binned
59
/// orthogonally in order to speed up the search.
60
#[cfg_attr(feature = "capture", derive(Serialize))]
61
#[cfg_attr(feature = "replay", derive(Deserialize))]
62
pub struct ArrayAllocationTracker {
63
bins: [Vec<FreeRect>; NUM_BINS],
64
}
65
66
impl ArrayAllocationTracker {
67
pub fn new() -> Self {
68
ArrayAllocationTracker {
69
bins: [
70
Vec::new(),
71
Vec::new(),
72
Vec::new(),
73
],
74
}
75
}
76
77
fn push(&mut self, slice: FreeRectSlice, rect: DeviceIntRect) {
78
let id = FreeListBin::for_size(&rect.size).0 as usize;
79
self.bins[id].push(FreeRect {
80
slice,
81
rect,
82
})
83
}
84
85
/// Find a suitable rect in the free list. We choose the smallest such rect
86
/// in terms of area (Best-Area-Fit, BAF).
87
fn find_index_of_best_rect(
88
&self,
89
requested_dimensions: &DeviceIntSize,
90
) -> Option<(FreeListBin, FreeListIndex)> {
91
let start_bin = FreeListBin::for_size(requested_dimensions);
92
(start_bin.0 .. NUM_BINS as u8)
93
.find_map(|id| if FIND_SMALLEST_AREA {
94
let mut smallest_index_and_area = None;
95
for (candidate_index, candidate) in self.bins[id as usize].iter().enumerate() {
96
if requested_dimensions.width > candidate.rect.size.width ||
97
requested_dimensions.height > candidate.rect.size.height
98
{
99
continue;
100
}
101
102
let candidate_area = candidate.rect.size.area();
103
match smallest_index_and_area {
104
Some((_, area)) if candidate_area >= area => continue,
105
_ => smallest_index_and_area = Some((candidate_index, candidate_area)),
106
}
107
}
108
109
smallest_index_and_area
110
.map(|(index, _)| (FreeListBin(id), FreeListIndex(index)))
111
} else {
112
self.bins[id as usize]
113
.iter()
114
.position(|candidate| {
115
requested_dimensions.width <= candidate.rect.size.width &&
116
requested_dimensions.height <= candidate.rect.size.height
117
})
118
.map(|index| (FreeListBin(id), FreeListIndex(index)))
119
})
120
}
121
122
// Split that results in the single largest area (Min Area Split Rule, MINAS).
123
fn split_guillotine(&mut self, chosen: &FreeRect, requested_dimensions: &DeviceIntSize) {
124
let candidate_free_rect_to_right = DeviceIntRect::new(
125
DeviceIntPoint::new(
126
chosen.rect.origin.x + requested_dimensions.width,
127
chosen.rect.origin.y,
128
),
129
DeviceIntSize::new(
130
chosen.rect.size.width - requested_dimensions.width,
131
requested_dimensions.height,
132
),
133
);
134
let candidate_free_rect_to_bottom = DeviceIntRect::new(
135
DeviceIntPoint::new(
136
chosen.rect.origin.x,
137
chosen.rect.origin.y + requested_dimensions.height,
138
),
139
DeviceIntSize::new(
140
requested_dimensions.width,
141
chosen.rect.size.height - requested_dimensions.height,
142
),
143
);
144
145
// Guillotine the rectangle.
146
let new_free_rect_to_right;
147
let new_free_rect_to_bottom;
148
if candidate_free_rect_to_right.size.area() > candidate_free_rect_to_bottom.size.area() {
149
new_free_rect_to_right = DeviceIntRect::new(
150
candidate_free_rect_to_right.origin,
151
DeviceIntSize::new(
152
candidate_free_rect_to_right.size.width,
153
chosen.rect.size.height,
154
),
155
);
156
new_free_rect_to_bottom = candidate_free_rect_to_bottom
157
} else {
158
new_free_rect_to_right = candidate_free_rect_to_right;
159
new_free_rect_to_bottom = DeviceIntRect::new(
160
candidate_free_rect_to_bottom.origin,
161
DeviceIntSize::new(
162
chosen.rect.size.width,
163
candidate_free_rect_to_bottom.size.height,
164
),
165
)
166
}
167
168
// Add the guillotined rects back to the free list.
169
if !new_free_rect_to_right.is_empty() {
170
self.push(chosen.slice, new_free_rect_to_right);
171
}
172
if !new_free_rect_to_bottom.is_empty() {
173
self.push(chosen.slice, new_free_rect_to_bottom);
174
}
175
}
176
177
pub fn allocate(
178
&mut self, requested_dimensions: &DeviceIntSize
179
) -> Option<(FreeRectSlice, DeviceIntPoint)> {
180
if requested_dimensions.width == 0 || requested_dimensions.height == 0 {
181
return Some((FreeRectSlice(0), DeviceIntPoint::new(0, 0)));
182
}
183
let (bin, index) = self.find_index_of_best_rect(requested_dimensions)?;
184
185
// Remove the rect from the free list and decide how to guillotine it.
186
let chosen = self.bins[bin.0 as usize].swap_remove(index.0);
187
self.split_guillotine(&chosen, requested_dimensions);
188
189
// Return the result.
190
Some((chosen.slice, chosen.rect.origin))
191
}
192
193
/// Add a new slice to the allocator, and immediately allocate a rect from it.
194
pub fn extend(
195
&mut self,
196
slice: FreeRectSlice,
197
total_size: DeviceIntSize,
198
requested_dimensions: DeviceIntSize,
199
) {
200
self.split_guillotine(
201
&FreeRect { slice, rect: total_size.into() },
202
&requested_dimensions
203
);
204
}
205
}
206
207
#[cfg(test)]
208
fn random_fill(count: usize, texture_size: i32) -> f32 {
209
use rand::{thread_rng, Rng};
210
211
let total_rect = DeviceIntRect::new(
212
DeviceIntPoint::zero(),
213
DeviceIntSize::new(texture_size, texture_size),
214
);
215
let mut rng = thread_rng();
216
let mut allocator = ArrayAllocationTracker::new();
217
218
// check for empty allocation
219
assert_eq!(
220
allocator.allocate(&DeviceIntSize::new(0, 12)),
221
Some((FreeRectSlice(0), DeviceIntPoint::zero())),
222
);
223
224
let mut slices: Vec<Vec<DeviceIntRect>> = Vec::new();
225
let mut requested_area = 0f32;
226
// fill up the allocator
227
for _ in 0 .. count {
228
let size = DeviceIntSize::new(
229
rng.gen_range(1, texture_size),
230
rng.gen_range(1, texture_size),
231
);
232
requested_area += size.area() as f32;
233
234
match allocator.allocate(&size) {
235
Some((slice, origin)) => {
236
let rect = DeviceIntRect::new(origin, size);
237
assert_eq!(None, slices[slice.0 as usize].iter().find(|r| r.intersects(&rect)));
238
assert!(total_rect.contains_rect(&rect));
239
slices[slice.0 as usize].push(rect);
240
}
241
None => {
242
allocator.extend(FreeRectSlice(slices.len() as u32), total_rect.size, size);
243
let rect = DeviceIntRect::new(DeviceIntPoint::zero(), size);
244
slices.push(vec![rect]);
245
}
246
}
247
}
248
// validate the free rects
249
for (i, free_vecs) in allocator.bins.iter().enumerate() {
250
for fr in free_vecs {
251
assert_eq!(FreeListBin(i as u8), FreeListBin::for_size(&fr.rect.size));
252
assert_eq!(None, slices[fr.slice.0 as usize].iter().find(|r| r.intersects(&fr.rect)));
253
assert!(total_rect.contains_rect(&fr.rect));
254
slices[fr.slice.0 as usize].push(fr.rect);
255
}
256
}
257
258
let allocated_area = slices.len() as f32 * (texture_size * texture_size) as f32;
259
requested_area / allocated_area
260
}
261
262
#[test]
263
fn test_small() {
264
random_fill(100, 100);
265
}
266
267
#[test]
268
fn test_large() {
269
random_fill(1000, 10000);
270
}