1 #pragma once
2
3 #include <mbgl/renderer/tile_mask.hpp>
4
5 #include <vector>
6 #include <functional>
7 #include <algorithm>
8
9 namespace mbgl {
10 namespace algorithm {
11
12 namespace {
13
14 template <typename Renderable>
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)15 void computeTileMasks(
16 const CanonicalTileID& root,
17 const UnwrappedTileID ref,
18 typename std::vector<std::reference_wrapper<Renderable>>::const_iterator it,
19 const typename std::vector<std::reference_wrapper<Renderable>>::const_iterator end,
20 TileMask& mask) {
21 // If the reference or any of its children is found in the list, we need to recurse.
22 for (; it != end; ++it) {
23 auto& renderable = it->get();
24 if (!renderable.used) {
25 continue;
26 }
27 if (ref == renderable.id) {
28 // The current tile is masked out, so we don't need to add them to the mask set.
29 return;
30 } else if (renderable.id.isChildOf(ref)) {
31 // There's at least one child tile that is masked out, so recursively descend.
32 for (const auto& child : ref.children()) {
33 computeTileMasks<Renderable>(root, child, it, end, mask);
34 }
35 return;
36 }
37 }
38
39 // We couldn't find a child, so it's definitely a masked part.
40 // Compute the difference between the root tile ID and the reference tile ID, since TileMask
41 // elements are always relative (see below for explanation).
42 const uint8_t diffZ = ref.canonical.z - root.z;
43 mask.emplace(diffZ, ref.canonical.x - (root.x << diffZ), ref.canonical.y - (root.y << diffZ));
44 }
45
46 } // namespace
47
48 // Updates the TileMasks for all renderables. Renderables are objects that have an UnwrappedTileID
49 // property indicating where they should be rendered on the screen. A TileMask describes all regions
50 // within that tile that are *not* covered by other Renderables.
51 // Example: Renderables in our list are 2/1/3, 3/3/6, and 4/5/13. The schematic for creating the
52 // TileMask for 2/1/3 looks like this:
53 //
54 // ┌────────┬────────┬─────────────────┐
55 // │ │ │#################│
56 // │ 4/4/12 │ 4/5/12 │#################│
57 // │ │ │#################│
58 // ├──────3/2/6──────┤#####3/3/6#######│
59 // │ │########│#################│
60 // │ 4/4/13 │#4/5/13#│#################│
61 // │ │########│#################│
62 // ├────────┴──────2/1/3───────────────┤
63 // │ │ │
64 // │ │ │
65 // │ │ │
66 // │ 3/2/7 │ 3/3/7 │
67 // │ │ │
68 // │ │ │
69 // │ │ │
70 // └─────────────────┴─────────────────┘
71 //
72 // 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,
73 // but it does *not* include 4/5/13, and 3/3/6, since these are other Renderables.
74 // A TileMask always contains TileIDs *relative* to the tile it is generated for, so 2/1/3 is
75 // "subtracted" from these TileIDs. The final TileMask for 2/1/3 will thus be:
76 //
77 // ┌────────┬────────┬─────────────────┐
78 // │ │ │#################│
79 // │ 2/0/0 │ 2/1/0 │#################│
80 // │ │ │#################│
81 // ├────────┼────────┤#################│
82 // │ │########│#################│
83 // │ 2/0/1 │########│#################│
84 // │ │########│#################│
85 // ├────────┴────────┼─────────────────┤
86 // │ │ │
87 // │ │ │
88 // │ │ │
89 // │ 1/0/1 │ 1/1/1 │
90 // │ │ │
91 // │ │ │
92 // │ │ │
93 // └─────────────────┴─────────────────┘
94 //
95 // Only other Renderables that are *children* of the Renderable we are generating the mask for will
96 // be considered. For example, adding a Renderable with TileID 4/8/13 won't affect the TileMask for
97 // 2/1/3, since it is not a descendant of it.
98 template <typename Renderable>
updateTileMasks(std::vector<std::reference_wrapper<Renderable>> renderables)99 void updateTileMasks(std::vector<std::reference_wrapper<Renderable>> renderables) {
100 std::sort(renderables.begin(), renderables.end(),
101 [](const Renderable& a, const Renderable& b) { return a.id < b.id; });
102
103 TileMask mask;
104 const auto end = renderables.end();
105 for (auto it = renderables.begin(); it != end; it++) {
106 auto& renderable = it->get();
107 if (!renderable.used) {
108 continue;
109 }
110 // Try to add all remaining ids as children. We sorted the tile list
111 // by z earlier, so all preceding items cannot be children of the current
112 // tile. We also compute the lower bound of the next wrap, because items of the next wrap
113 // can never be children of the current wrap.
114 auto child_it = std::next(it);
115 const auto children_end = std::lower_bound(
116 child_it, end,
117 UnwrappedTileID{ static_cast<int16_t>(renderable.id.wrap + 1), { 0, 0, 0 } },
118 [](auto& a, auto& b) { return a.get().id < b; });
119
120 mask.clear();
121 computeTileMasks<Renderable>(renderable.id.canonical, renderable.id, child_it, children_end,
122 mask);
123 renderable.setMask(std::move(mask));
124 }
125 }
126
127 } // namespace algorithm
128 } // namespace mbgl
129