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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
#pragma once
#include <mbgl/renderer/tile_mask.hpp>
#include <vector>
#include <functional>
#include <algorithm>
namespace mbgl {
namespace algorithm {
namespace {
template <typename Renderable>
void computeTileMasks(
const CanonicalTileID& root,
const UnwrappedTileID ref,
typename std::vector<std::reference_wrapper<Renderable>>::const_iterator it,
const typename std::vector<std::reference_wrapper<Renderable>>::const_iterator end,
TileMask& mask) {
// If the reference or any of its children is found in the list, we need to recurse.
for (; it != end; ++it) {
auto& renderable = it->get();
if (!renderable.used) {
continue;
}
if (ref == renderable.id) {
// The current tile is masked out, so we don't need to add them to the mask set.
return;
} else if (renderable.id.isChildOf(ref)) {
// There's at least one child tile that is masked out, so recursively descend.
for (const auto& child : ref.children()) {
computeTileMasks<Renderable>(root, child, it, end, mask);
}
return;
}
}
// We couldn't find a child, so it's definitely a masked part.
// Compute the difference between the root tile ID and the reference tile ID, since TileMask
// elements are always relative (see below for explanation).
const uint8_t diffZ = ref.canonical.z - root.z;
mask.emplace(diffZ, ref.canonical.x - (root.x << diffZ), ref.canonical.y - (root.y << diffZ));
}
} // namespace
// Updates the TileMasks for all renderables. Renderables are objects that have an UnwrappedTileID
// property indicating where they should be rendered on the screen. A TileMask describes all regions
// within that tile that are *not* covered by other Renderables.
// Example: Renderables in our list are 2/1/3, 3/3/6, and 4/5/13. The schematic for creating the
// TileMask for 2/1/3 looks like this:
//
// ┌────────┬────────┬─────────────────┐
// │ │ │#################│
// │ 4/4/12 │ 4/5/12 │#################│
// │ │ │#################│
// ├──────3/2/6──────┤#####3/3/6#######│
// │ │########│#################│
// │ 4/4/13 │#4/5/13#│#################│
// │ │########│#################│
// ├────────┴──────2/1/3───────────────┤
// │ │ │
// │ │ │
// │ │ │
// │ 3/2/7 │ 3/3/7 │
// │ │ │
// │ │ │
// │ │ │
// └─────────────────┴─────────────────┘
//
// The TileMask for 2/1/3 thus consists of the tiles 4/4/12, 4/5/12, 4/4/13, 3/2/7, and 3/3/7,
// but it does *not* include 4/5/13, and 3/3/6, since these are other Renderables.
// A TileMask always contains TileIDs *relative* to the tile it is generated for, so 2/1/3 is
// "subtracted" from these TileIDs. The final TileMask for 2/1/3 will thus be:
//
// ┌────────┬────────┬─────────────────┐
// │ │ │#################│
// │ 2/0/0 │ 2/1/0 │#################│
// │ │ │#################│
// ├────────┼────────┤#################│
// │ │########│#################│
// │ 2/0/1 │########│#################│
// │ │########│#################│
// ├────────┴────────┼─────────────────┤
// │ │ │
// │ │ │
// │ │ │
// │ 1/0/1 │ 1/1/1 │
// │ │ │
// │ │ │
// │ │ │
// └─────────────────┴─────────────────┘
//
// Only other Renderables that are *children* of the Renderable we are generating the mask for will
// be considered. For example, adding a Renderable with TileID 4/8/13 won't affect the TileMask for
// 2/1/3, since it is not a descendant of it.
//
// The given |renderables| must be sorted by id.
template <typename Renderable>
void updateTileMasks(std::vector<std::reference_wrapper<Renderable>> renderables) {
assert(std::is_sorted(renderables.begin(), renderables.end(),
[](const Renderable& a, const Renderable& b) { return a.id < b.id; }));
TileMask mask;
const auto end = renderables.end();
for (auto it = renderables.begin(); it != end; it++) {
auto& renderable = it->get();
if (!renderable.used) {
continue;
}
// 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. We also compute the lower bound of the next wrap, because items of the next wrap
// can never be children of the current wrap.
auto child_it = std::next(it);
const auto children_end = std::lower_bound(
child_it, end,
UnwrappedTileID{ static_cast<int16_t>(renderable.id.wrap + 1), { 0, 0, 0 } },
[](auto& a, auto& b) { return a.get().id < b; });
mask.clear();
computeTileMasks<Renderable>(renderable.id.canonical, renderable.id, child_it, children_end,
mask);
renderable.setMask(std::move(mask));
}
}
} // namespace algorithm
} // namespace mbgl
|
