blob: 9c391c38add3507f4eaf177cf7f1f52495117267 (
plain)
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
|
#include <mbgl/util/clip_ids.hpp>
#include <mbgl/map/tile.hpp>
#include <mbgl/util/math.hpp>
#include <list>
#include <vector>
#include <bitset>
#include <cassert>
#include <iostream>
#include <algorithm>
namespace mbgl {
ClipIDGenerator::Leaf::Leaf(Tile &tile_) : tile(tile_) {}
void ClipIDGenerator::Leaf::add(const Tile::ID &p) {
if (p.isChildOf(tile.id)) {
// Ensure that no already present child is a parent of the new p.
for (const Tile::ID &child : children) {
if (p.isChildOf(child))
return;
}
children.push_front(p);
}
}
bool ClipIDGenerator::Leaf::operator==(const Leaf &other) const {
return tile.id == other.tile.id && children == other.children;
}
bool ClipIDGenerator::reuseExisting(Leaf &leaf) {
for (const std::vector<Leaf> &pool : pools) {
auto existing = std::find(pool.begin(), pool.end(), leaf);
if (existing != pool.end()) {
leaf.tile.clip = existing->tile.clip;
return true;
}
}
return false;
}
void ClipIDGenerator::update(std::forward_list<Tile *> tiles) {
Pool pool;
tiles.sort([](const Tile *a, const Tile *b) {
return a->id < b->id;
});
const auto end = tiles.end();
for (auto it = tiles.begin(); it != end; it++) {
if (!*it) {
// Handle null pointers.
continue;
}
Tile &tile = **it;
Leaf clip { tile };
// Try to add all remaining ids as children. We sorted the tile list
// by z earlier, so all preceding items cannot be children of the current
// tile.
for (auto child_it = std::next(it); child_it != end; child_it++) {
clip.add((*child_it)->id);
}
clip.children.sort();
// Loop through all existing pools and try to find a matching ClipID.
if (!reuseExisting(clip)) {
// We haven't found an existing clip ID
pool.push_back(std::move(clip));
}
}
if (pool.size()) {
const uint32_t bit_count = util::ceil_log2(pool.size() + 1);
const std::bitset<8> mask = uint64_t(((1 << bit_count) - 1) << bit_offset);
// We are starting our count with 1 since we need at least 1 bit set to distinguish between
// areas without any tiles whatsoever and the current area.
uint8_t count = 1;
for (Leaf &leaf : pool) {
leaf.tile.clip.mask = mask;
leaf.tile.clip.reference = count++ << bit_offset;
}
bit_offset += bit_count;
pools.push_front(std::move(pool));
}
if (bit_offset > 8) {
fprintf(stderr, "stencil mask overflow\n");
}
}
}
|