1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#pragma once
#include <mbgl/util/noncopyable.hpp>
#include <mbgl/util/rect.hpp>
#include <cstdint>
#include <list>
namespace mbgl {
template <typename T>
class BinPack : private util::noncopyable {
public:
BinPack(T width, T height)
: free(1, Rect<uint16_t>{ 0, 0, width, height }) {}
public:
Rect<T> allocate(T width, T height) {
// Find the smallest free rect angle
auto smallest = free.end();
for (auto it = free.begin(); it != free.end(); ++it) {
const Rect<T>& ref = *it;
const Rect<T>& rect = *smallest;
if (width <= ref.w && height <= ref.h) {
if (smallest == free.end() || (ref.y <= rect.y && ref.x <= rect.x)) {
smallest = it;
} else {
// Our current "smallest" rect is already closer to 0/0.
}
} else {
// The rect in the free list is not big enough.
}
}
if (smallest == free.end()) {
// There's no space left for this char.
return Rect<uint16_t>{ 0, 0, 0, 0 };
} else {
Rect<T> rect = *smallest;
free.erase(smallest);
// Shorter/Longer Axis Split Rule (SAS)
// http://clb.demon.fi/files/RectangleBinPack.pdf p. 15
// Ignore the dimension of R and just split long the shorter dimension
// See Also: http://www.cs.princeton.edu/~chazelle/pubs/blbinpacking.pdf
if (rect.w < rect.h) {
// split horizontally
// +--+---+
// |__|___| <-- b1
// +------+ <-- b2
if (rect.w > width) free.emplace_back(rect.x + width, rect.y, rect.w - width, height);
if (rect.h > height) free.emplace_back(rect.x, rect.y + height, rect.w, rect.h - height);
} else {
// split vertically
// +--+---+
// |__| | <-- b1
// +--|---+ <-- b2
if (rect.w > width) free.emplace_back(rect.x + width, rect.y, rect.w - width, rect.h);
if (rect.h > height) free.emplace_back(rect.x, rect.y + height, width, rect.h - height);
}
return Rect<uint16_t>{ rect.x, rect.y, width, height };
}
}
void release(Rect<T> rect) {
// Simple algorithm to recursively merge the newly released cell with its
// neighbor. This doesn't merge more than two cells at a time, and fails
// for complicated merges.
for (auto it = free.begin(); it != free.end(); ++it) {
Rect<T> ref = *it;
if (ref.y == rect.y && ref.h == rect.h && ref.x + ref.w == rect.x) {
ref.w += rect.w;
}
else if (ref.x == rect.x && ref.w == rect.w && ref.y + ref.h == rect.y) {
ref.h += rect.h;
}
else if (rect.y == ref.y && rect.h == ref.h && rect.x + rect.w == ref.x) {
ref.x = rect.x;
ref.w += rect.w;
}
else if (rect.x == ref.x && rect.w == ref.w && rect.y + rect.h == ref.y) {
ref.y = rect.y;
ref.h += rect.h;
} else {
continue;
}
free.erase(it);
release(ref);
return;
}
free.emplace_back(rect);
};
private:
std::list<Rect<T>> free;
};
} // namespace mbgl
|
