From 47a003b7420b4a1585a647fb71590fbb13813dd5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Konstantin=20K=C3=A4fer?= Date: Wed, 5 Jul 2017 15:38:50 +0200 Subject: [core] add algorithm for computing masks for raster tiles --- benchmark/parse/tile_mask.benchmark.cpp | 29 +++++++ cmake/benchmark-files.cmake | 1 + cmake/benchmark.cmake | 1 + cmake/core-files.cmake | 2 + cmake/test-files.cmake | 1 + src/mbgl/algorithm/update_tile_masks.hpp | 72 +++++++++++++++++ src/mbgl/renderer/tile_mask.hpp | 11 +++ src/mbgl/tile/tile_id.hpp | 10 +++ src/mbgl/tile/tile_id_io.cpp | 5 ++ test/algorithm/update_tile_masks.test.cpp | 124 ++++++++++++++++++++++++++++++ 10 files changed, 256 insertions(+) create mode 100644 benchmark/parse/tile_mask.benchmark.cpp create mode 100644 src/mbgl/algorithm/update_tile_masks.hpp create mode 100644 src/mbgl/renderer/tile_mask.hpp create mode 100644 test/algorithm/update_tile_masks.test.cpp diff --git a/benchmark/parse/tile_mask.benchmark.cpp b/benchmark/parse/tile_mask.benchmark.cpp new file mode 100644 index 0000000000..5d50d05c22 --- /dev/null +++ b/benchmark/parse/tile_mask.benchmark.cpp @@ -0,0 +1,29 @@ +#include + +#include + +using namespace mbgl; + +struct MaskedRenderable { + UnwrappedTileID id; + TileMask mask; + bool used = true; +}; + +static void TileMaskGeneration(benchmark::State& state) { + std::vector 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({ renderables.begin(), renderables.end() }); + } +} + +BENCHMARK(TileMaskGeneration); diff --git a/cmake/benchmark-files.cmake b/cmake/benchmark-files.cmake index 35931a6b52..e8adf66d4c 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 1dfca27e6c..79e87a0b10 100644 --- a/cmake/benchmark.cmake +++ b/cmake/benchmark.cmake @@ -17,6 +17,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 395069bc45..5564b10c73 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 @@ -197,6 +198,7 @@ set(MBGL_CORE_FILES src/mbgl/renderer/render_tile.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 7271887dac..1c2cd76a38 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..5c53f8f379 --- /dev/null +++ b/src/mbgl/algorithm/update_tile_masks.hpp @@ -0,0 +1,72 @@ +#pragma once + +#include + +#include +#include +#include + +namespace mbgl { +namespace algorithm { + +namespace { + +template +void computeTileMasks( + const CanonicalTileID& root, + const UnwrappedTileID ref, + typename std::vector>::const_iterator it, + const typename std::vector>::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(root, child, it, end, mask); + } + return; + } + } + // We couldn't find a child, so it's definitely a masked part. + mask.emplace(ref.canonical - root); +} + +} // namespace + +template +void updateTileMasks(std::vector> renderables) { + std::sort(renderables.begin(), renderables.end(), + [](const Renderable& a, const Renderable& b) { return a.id < b.id; }); + + 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(renderable.id.wrap + 1), { 0, 0, 0 } }, + [](auto& a, auto& b) { return a.get().id < b; }); + + renderable.mask.clear(); + computeTileMasks(renderable.id.canonical, renderable.id, child_it, children_end, + renderable.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..a4cbff864f --- /dev/null +++ b/src/mbgl/renderer/tile_mask.hpp @@ -0,0 +1,11 @@ +#pragma once + +#include + +#include + +namespace mbgl { + +using TileMask = std::set; + +} // namespace mbgl diff --git a/src/mbgl/tile/tile_id.hpp b/src/mbgl/tile/tile_id.hpp index 1ce3eea98e..38adbaa107 100644 --- a/src/mbgl/tile/tile_id.hpp +++ b/src/mbgl/tile/tile_id.hpp @@ -28,6 +28,7 @@ public: bool operator<(const CanonicalTileID&) const; bool isChildOf(const CanonicalTileID&) const; CanonicalTileID scaledTo(uint8_t z) const; + CanonicalTileID operator-(const CanonicalTileID&) const; std::array children() const; const uint8_t z; @@ -125,6 +126,15 @@ inline CanonicalTileID CanonicalTileID::scaledTo(uint8_t targetZ) const { } } +inline CanonicalTileID CanonicalTileID::operator-(const CanonicalTileID& rhs) const { + if (!isChildOf(rhs)) { + return { 0, 0, 0 }; + } else { + const uint8_t diffZ = z - rhs.z; + return { diffZ, x - (rhs.x << diffZ), y - (rhs.y << diffZ) }; + } +} + inline std::array CanonicalTileID::children() const { const uint8_t childZ = z + 1; const uint32_t childX = x * 2; 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..1127c7140c --- /dev/null +++ b/test/algorithm/update_tile_masks.test.cpp @@ -0,0 +1,124 @@ +#include + +#include + +using namespace mbgl; + +namespace { + +struct MaskedRenderable { + UnwrappedTileID id; + TileMask mask; + bool used = true; +}; + +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 expected) { + std::vector actual = expected; + std::for_each(actual.begin(), actual.end(), + [](auto& renderable) { renderable.mask.clear(); }); + algorithm::updateTileMasks({ 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 } } }, + }); +} -- cgit v1.2.1