[core] add algorithm for computing masks for raster tiles

10 files changed, 256 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..5d50d05c22
--- /dev/null
+++ b/benchmark/parse/tile_mask.benchmark.cpp
@@ -0,0 +1,29 @@
+#include <benchmark/benchmark.h>
+
+#include <mbgl/algorithm/update_tile_masks.hpp>
+
+using namespace mbgl;
+
+struct MaskedRenderable {
+    UnwrappedTileID id;
+    TileMask mask;
+    bool used = true;
+};
+
+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 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 <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.
+    mask.emplace(ref.canonical - root);
+}
+
+} // namespace
+
+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; });
+
+    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; });
+
+        renderable.mask.clear();
+        computeTileMasks<Renderable>(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 <mbgl/tile/tile_id.hpp>
+
+#include <set>
+
+namespace mbgl {
+
+using TileMask = std::set<CanonicalTileID>;
+
+} // 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<CanonicalTileID, 4> 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, 4> 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 <mbgl/test/util.hpp>
+
+#include <mbgl/algorithm/update_tile_masks.hpp>
+
+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<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 } } },
+    });
+}