summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--benchmark/parse/tile_mask.benchmark.cpp38
-rw-r--r--cmake/benchmark-files.cmake1
-rw-r--r--cmake/benchmark.cmake1
-rw-r--r--cmake/core-files.cmake2
-rw-r--r--cmake/test-files.cmake1
-rw-r--r--src/mbgl/algorithm/update_tile_masks.hpp128
-rw-r--r--src/mbgl/renderer/tile_mask.hpp15
-rw-r--r--src/mbgl/tile/tile_id_io.cpp5
-rw-r--r--test/algorithm/update_tile_masks.test.cpp132
9 files changed, 323 insertions, 0 deletions
diff --git a/benchmark/parse/tile_mask.benchmark.cpp b/benchmark/parse/tile_mask.benchmark.cpp
new file mode 100644
index 0000000000..79ab685c28
--- /dev/null
+++ b/benchmark/parse/tile_mask.benchmark.cpp
@@ -0,0 +1,38 @@
+#include <benchmark/benchmark.h>
+
+#include <mbgl/algorithm/update_tile_masks.hpp>
+
+using namespace mbgl;
+
+class MaskedRenderable {
+public:
+ MaskedRenderable(const UnwrappedTileID& id_, TileMask&& mask_)
+ : id(id_), mask(std::move(mask_)) {
+ }
+
+ UnwrappedTileID id;
+ TileMask mask;
+ bool used = true;
+
+ void setMask(TileMask&& mask_) {
+ mask = std::move(mask_);
+ }
+};
+
+static void TileMaskGeneration(benchmark::State& state) {
+ std::vector<MaskedRenderable> renderables = {
+ MaskedRenderable{ UnwrappedTileID{ 12, 1028, 1456 }, {} },
+ MaskedRenderable{ UnwrappedTileID{ 13, 2056, 2912 }, {} },
+ MaskedRenderable{ UnwrappedTileID{ 13, 2056, 2913 }, {} },
+ MaskedRenderable{ UnwrappedTileID{ 14, 4112, 5824 }, {} },
+ MaskedRenderable{ UnwrappedTileID{ 14, 4112, 5827 }, {} },
+ MaskedRenderable{ UnwrappedTileID{ 14, 4114, 5824 }, {} },
+ MaskedRenderable{ UnwrappedTileID{ 14, 4114, 5825 }, {} },
+ };
+
+ while (state.KeepRunning()) {
+ algorithm::updateTileMasks<MaskedRenderable>({ renderables.begin(), renderables.end() });
+ }
+}
+
+BENCHMARK(TileMaskGeneration);
diff --git a/cmake/benchmark-files.cmake b/cmake/benchmark-files.cmake
index 6fb9a80d57..d5364c3e58 100644
--- a/cmake/benchmark-files.cmake
+++ b/cmake/benchmark-files.cmake
@@ -10,6 +10,7 @@ set(MBGL_BENCHMARK_FILES
# parse
benchmark/parse/filter.benchmark.cpp
+ benchmark/parse/tile_mask.benchmark.cpp
benchmark/parse/vector_tile.benchmark.cpp
# src
diff --git a/cmake/benchmark.cmake b/cmake/benchmark.cmake
index f89e034c4a..6f8a7751e4 100644
--- a/cmake/benchmark.cmake
+++ b/cmake/benchmark.cmake
@@ -19,6 +19,7 @@ target_link_libraries(mbgl-benchmark
PRIVATE mbgl-core
)
+target_add_mason_package(mbgl-benchmark PRIVATE boost)
target_add_mason_package(mbgl-benchmark PRIVATE benchmark)
target_add_mason_package(mbgl-benchmark PRIVATE rapidjson)
target_add_mason_package(mbgl-benchmark PRIVATE protozero)
diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake
index 94eb321ddf..93bc8326d4 100644
--- a/cmake/core-files.cmake
+++ b/cmake/core-files.cmake
@@ -15,6 +15,7 @@ set(MBGL_CORE_FILES
src/mbgl/algorithm/generate_clip_ids.hpp
src/mbgl/algorithm/generate_clip_ids_impl.hpp
src/mbgl/algorithm/update_renderables.hpp
+ src/mbgl/algorithm/update_tile_masks.hpp
# annotation
include/mbgl/annotation/annotation.hpp
@@ -205,6 +206,7 @@ set(MBGL_CORE_FILES
src/mbgl/renderer/renderer_observer.hpp
src/mbgl/renderer/style_diff.cpp
src/mbgl/renderer/style_diff.hpp
+ src/mbgl/renderer/tile_mask.hpp
src/mbgl/renderer/tile_parameters.hpp
src/mbgl/renderer/tile_pyramid.cpp
src/mbgl/renderer/tile_pyramid.hpp
diff --git a/cmake/test-files.cmake b/cmake/test-files.cmake
index 2d2ed7d35b..3595233f2a 100644
--- a/cmake/test-files.cmake
+++ b/cmake/test-files.cmake
@@ -10,6 +10,7 @@ set(MBGL_TEST_FILES
test/algorithm/generate_clip_ids.test.cpp
test/algorithm/mock.hpp
test/algorithm/update_renderables.test.cpp
+ test/algorithm/update_tile_masks.test.cpp
# api
test/api/annotations.test.cpp
diff --git a/src/mbgl/algorithm/update_tile_masks.hpp b/src/mbgl/algorithm/update_tile_masks.hpp
new file mode 100644
index 0000000000..a7840cd163
--- /dev/null
+++ b/src/mbgl/algorithm/update_tile_masks.hpp
@@ -0,0 +1,128 @@
+#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.
+template <typename Renderable>
+void updateTileMasks(std::vector<std::reference_wrapper<Renderable>> renderables) {
+ std::sort(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
diff --git a/src/mbgl/renderer/tile_mask.hpp b/src/mbgl/renderer/tile_mask.hpp
new file mode 100644
index 0000000000..5f24d63ba4
--- /dev/null
+++ b/src/mbgl/renderer/tile_mask.hpp
@@ -0,0 +1,15 @@
+#pragma once
+
+#include <mbgl/tile/tile_id.hpp>
+
+#include <set>
+
+namespace mbgl {
+
+// A TileMask is a set of TileIDs that describe what part of a tile should be rendered. It omits
+// those parts of the tile that are covered by other/better tiles. If the entire tile should be
+// rendered, it contains the { 0, 0, 0 } tile. If it's empty, no part of the tile will be rendered.
+// TileMasks are typically generated with algorithm::updateTileMasks().
+using TileMask = std::set<CanonicalTileID>;
+
+} // namespace mbgl
diff --git a/src/mbgl/tile/tile_id_io.cpp b/src/mbgl/tile/tile_id_io.cpp
index f6adbf183f..d8be6b93d6 100644
--- a/src/mbgl/tile/tile_id_io.cpp
+++ b/src/mbgl/tile/tile_id_io.cpp
@@ -6,6 +6,8 @@
namespace mbgl {
::std::ostream& operator<<(::std::ostream& os, const CanonicalTileID& rhs) {
+ // Uncomment this to create code instead of shorthands.
+ // return os << "CanonicalTileID{ " << uint32_t(rhs.z) << ", " << rhs.x << ", " << rhs.y << " }";
return os << uint32_t(rhs.z) << "/" << rhs.x << "/" << rhs.y;
}
@@ -26,6 +28,9 @@ std::string toString(const OverscaledTileID& rhs) {
} // namespace util
::std::ostream& operator<<(::std::ostream& os, const UnwrappedTileID& rhs) {
+ // Uncomment this to create code instead of shorthands.
+ // return os << "UnwrappedTileID{ " << uint32_t(rhs.wrap) << ", { " << uint32_t(rhs.canonical.z)
+ // << ", " << rhs.canonical.x << ", " << rhs.canonical.y << " } }";
return os << rhs.canonical << (rhs.wrap >= 0 ? "+" : "") << rhs.wrap;
}
diff --git a/test/algorithm/update_tile_masks.test.cpp b/test/algorithm/update_tile_masks.test.cpp
new file mode 100644
index 0000000000..3c698eb0cd
--- /dev/null
+++ b/test/algorithm/update_tile_masks.test.cpp
@@ -0,0 +1,132 @@
+#include <mbgl/test/util.hpp>
+
+#include <mbgl/algorithm/update_tile_masks.hpp>
+
+using namespace mbgl;
+
+namespace {
+
+class MaskedRenderable {
+public:
+ MaskedRenderable(const UnwrappedTileID& id_, TileMask&& mask_)
+ : id(id_), mask(std::move(mask_)) {
+ }
+
+ UnwrappedTileID id;
+ TileMask mask;
+ bool used = true;
+
+ void setMask(TileMask&& mask_) {
+ mask = std::move(mask_);
+ }
+};
+
+bool operator==(const MaskedRenderable& lhs, const MaskedRenderable& rhs) {
+ return lhs.id == rhs.id && lhs.mask == rhs.mask;
+}
+
+::std::ostream& operator<<(::std::ostream& os, const MaskedRenderable& rhs) {
+ os << "MaskedRenderable{ " << rhs.id << ", { ";
+ bool first = true;
+ for (auto& id : rhs.mask) {
+ if (!first) {
+ os << ", ";
+ } else {
+ first = false;
+ }
+ os << id;
+ }
+ return os << " } }";
+}
+
+} // namespace
+
+void validate(const std::vector<MaskedRenderable> expected) {
+ std::vector<MaskedRenderable> actual = expected;
+ std::for_each(actual.begin(), actual.end(),
+ [](auto& renderable) { renderable.mask.clear(); });
+ algorithm::updateTileMasks<MaskedRenderable>({ actual.begin(), actual.end() });
+ EXPECT_EQ(expected, actual);
+}
+
+TEST(UpdateTileMasks, NoChildren) {
+ validate({
+ MaskedRenderable{ UnwrappedTileID{ 0, 0, 0 }, { CanonicalTileID{ 0, 0, 0 } } },
+ });
+
+ validate({
+ MaskedRenderable{ UnwrappedTileID{ 4, 3, 8 }, { CanonicalTileID{ 0, 0, 0 } } },
+ });
+
+ validate({
+ MaskedRenderable{ UnwrappedTileID{ 1, 0, 0 }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 1, 1, 1 }, { CanonicalTileID{ 0, 0, 0 } } },
+ });
+
+ validate({
+ MaskedRenderable{ UnwrappedTileID{ 1, 0, 0 }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 2, 2, 3 }, { CanonicalTileID{ 0, 0, 0 } } },
+ });
+}
+
+TEST(UpdateTileMasks, ParentAndFourChildren) {
+ validate({
+ // Mask is empty (== not rendered!) because we have four covering children.
+ MaskedRenderable{ UnwrappedTileID{ 0, 0, 0 }, {} },
+ // All four covering children
+ MaskedRenderable{ UnwrappedTileID{ 1, 0, 0 }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 1, 0, 1 }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 1, 1, 0 }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 1, 1, 1 }, { CanonicalTileID{ 0, 0, 0 } } },
+ });
+}
+
+TEST(UpdateTileMasks, OneChild) {
+ validate({
+ MaskedRenderable{ UnwrappedTileID{ 0, 0, 0 },
+ // Only render the three children that aren't covering the other tile.
+ { CanonicalTileID{ 1, 0, 1 }, CanonicalTileID{ 1, 1, 0 },
+ CanonicalTileID{ 1, 1, 1 } } },
+ MaskedRenderable{ UnwrappedTileID{ 1, 0, 0 }, { CanonicalTileID{ 0, 0, 0 } } },
+ });
+}
+
+TEST(UpdateTileMasks, Complex) {
+ validate({
+ MaskedRenderable{ UnwrappedTileID{ 0, 0, 0 },
+ { CanonicalTileID{ 1, 0, 1 }, CanonicalTileID{ 1, 1, 0 },
+ CanonicalTileID{ 2, 2, 3 }, CanonicalTileID{ 2, 3, 2 },
+ CanonicalTileID{ 3, 6, 7 }, CanonicalTileID{ 3, 7, 6 } } },
+ MaskedRenderable{ UnwrappedTileID{ 0, { 1, 0, 0 } }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 0, { 2, 2, 2 } }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 0, { 3, 7, 7 } }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 0, { 3, 6, 6 } }, { CanonicalTileID{ 0, 0, 0 } } },
+ });
+
+ validate({
+ MaskedRenderable{ UnwrappedTileID{ 0, 0, 0 },
+ { CanonicalTileID{ 1, 0, 1 }, CanonicalTileID{ 1, 1, 0 },
+ CanonicalTileID{ 1, 1, 1 }, CanonicalTileID{ 2, 0, 0 },
+ CanonicalTileID{ 2, 0, 1 }, CanonicalTileID{ 2, 1, 0 },
+ CanonicalTileID{ 3, 2, 3 }, CanonicalTileID{ 3, 3, 2 },
+ CanonicalTileID{ 3, 3, 3 }, CanonicalTileID{ 4, 4, 5 },
+ CanonicalTileID{ 4, 5, 4 }, CanonicalTileID{ 4, 5, 5 } } },
+ MaskedRenderable{ UnwrappedTileID{ 4, 4, 4 }, { CanonicalTileID{ 0, 0, 0 } } },
+ });
+
+ validate({
+ MaskedRenderable{ UnwrappedTileID{ 12, 1028, 1456 },
+ { CanonicalTileID{ 1, 1, 1 }, CanonicalTileID{ 2, 3, 0 },
+ CanonicalTileID{ 2, 3, 1 } } },
+ MaskedRenderable{ UnwrappedTileID{ 13, 2056, 2912 },
+ { CanonicalTileID{ 1, 0, 1 }, CanonicalTileID{ 1, 1, 0 },
+ CanonicalTileID{ 1, 1, 1 } } },
+ MaskedRenderable{ UnwrappedTileID{ 13, 2056, 2913 },
+ { CanonicalTileID{ 1, 0, 0 }, CanonicalTileID{ 1, 1, 0 },
+ CanonicalTileID{ 1, 1, 1 } } },
+ MaskedRenderable{ UnwrappedTileID{ 14, 4112, 5824 }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 14, 4112, 5827 }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 14, 4114, 5824 }, { CanonicalTileID{ 0, 0, 0 } } },
+ MaskedRenderable{ UnwrappedTileID{ 14, 4114, 5825 }, { CanonicalTileID{ 0, 0, 0 } } },
+ });
+}
View Lorry Controller Status