[core] compute the actual clipping masks that we have to draw with getStencils()

3 files changed, 99 insertions, 36 deletions

diff --git a/src/mbgl/map/tile_id.hpp b/src/mbgl/map/tile_id.hpp
index dddbce3bb7..3ecc5c6cef 100644
--- a/src/mbgl/map/tile_id.hpp
+++ b/src/mbgl/map/tile_id.hpp
@@ -6,6 +6,7 @@
 #include <string>
 #include <functional>
 #include <forward_list>
+#include <limits>
 
 namespace mbgl {
 
@@ -48,7 +49,8 @@ public:
 
     TileID parent(int8_t z, int8_t sourceMaxZoom) const;
     TileID normalized() const;
-    std::forward_list<TileID> children(int8_t sourceMaxZoom) const;
+    std::forward_list<TileID>
+    children(int8_t sourceMaxZoom = std::numeric_limits<int8_t>::max()) const;
     bool isChildOf(const TileID&) const;
     operator std::string() const;
 
diff --git a/src/mbgl/util/clip_id.cpp b/src/mbgl/util/clip_id.cpp
index b89315d97b..8274be338d 100644
--- a/src/mbgl/util/clip_id.cpp
+++ b/src/mbgl/util/clip_id.cpp
@@ -2,6 +2,7 @@
 
 #include <mbgl/platform/log.hpp>
 #include <mbgl/util/math.hpp>
+#include <mbgl/util/std.hpp>
 #include <mbgl/map/tile.hpp>
 
 #include <list>
@@ -10,13 +11,14 @@
 #include <cassert>
 #include <iostream>
 #include <algorithm>
+#include <iterator>
 
 namespace mbgl {
 
-ClipIDGenerator::Leaf::Leaf(Tile &tile_) : tile(tile_) {}
+ClipIDGenerator::Leaf::Leaf(TileID id_, ClipID& clip_) : id(id_), clip(clip_) {}
 
 void ClipIDGenerator::Leaf::add(const TileID &p) {
-    if (p.isChildOf(tile.id)) {
+    if (p.isChildOf(id)) {
         // Ensure that no already present child is a parent of the new p.
         for (const auto& child : children) {
             if (p.isChildOf(child))
@@ -27,27 +29,16 @@ void ClipIDGenerator::Leaf::add(const TileID &p) {
 }
 
 bool ClipIDGenerator::Leaf::operator==(const Leaf &other) const {
-    return tile.id == other.tile.id && children == other.children;
-}
-
-bool ClipIDGenerator::reuseExisting(Leaf &leaf) {
-    for (const auto& pool : pools) {
-        auto existing = std::find(pool.begin(), pool.end(), leaf);
-        if (existing != pool.end()) {
-            leaf.tile.clip = existing->tile.clip;
-            return true;
-        }
-    }
-    return false;
+    return id == other.id && children == other.children;
 }
 
 void ClipIDGenerator::update(std::forward_list<Tile *> tiles) {
-    Pool pool;
-
     tiles.sort([](const Tile *a, const Tile *b) {
         return a->id < b->id;
     });
 
+    std::size_t size = 0;
+
     const auto end = tiles.end();
     for (auto it = tiles.begin(); it != end; it++) {
         if (!*it) {
@@ -56,37 +47,49 @@ void ClipIDGenerator::update(std::forward_list<Tile *> tiles) {
         }
 
         Tile &tile = **it;
-        Leaf clip { tile };
+        // Use the actual zoom level for computing the clipping mask.
+        Leaf leaf{ TileID{ tile.id.sourceZ, tile.id.x, tile.id.y, tile.id.sourceZ }, tile.clip };
 
         // 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.
         for (auto child_it = std::next(it); child_it != end; child_it++) {
-            clip.add((*child_it)->id);
+            // Use the actual zoom level for computing the clipping mask.
+            const auto& childID = (*child_it)->id;
+            leaf.add(TileID { childID.sourceZ, childID.x, childID.y, childID.sourceZ });
         }
-        clip.children.sort();
+        leaf.children.sort();
 
         // Loop through all existing pools and try to find a matching ClipID.
-        if (!reuseExisting(clip)) {
+        auto existing = std::find(pool.begin(), pool.end(), leaf);
+        if (existing != pool.end()) {
+            leaf.clip = existing->clip;
+        } else {
             // We haven't found an existing clip ID
-            pool.push_back(std::move(clip));
+            leaf.clip = {};
+            size++;
         }
+
+        pool.emplace_back(std::move(leaf));
     }
 
-    if (!pool.empty()) {
-        const uint32_t bit_count = util::ceil_log2(pool.size() + 1);
+    if (size > 0) {
+        const uint32_t bit_count = util::ceil_log2(size + 1);
         const std::bitset<8> mask = uint64_t(((1ul << bit_count) - 1) << bit_offset);
 
         // We are starting our count with 1 since we need at least 1 bit set to distinguish between
         // areas without any tiles whatsoever and the current area.
         uint8_t count = 1;
-        for (auto& leaf : pool) {
-            leaf.tile.clip.mask = mask;
-            leaf.tile.clip.reference = uint32_t(count++) << bit_offset;
+        for (auto& tile : tiles) {
+            tile->clip.mask |= mask;
+
+            // Assign only to clip IDs that have no value yet.
+            if (tile->clip.reference.none()) {
+                tile->clip.reference = uint32_t(count++) << bit_offset;
+            }
         }
 
         bit_offset += bit_count;
-        pools.push_front(std::move(pool));
     }
 
     if (bit_offset > 8) {
@@ -94,4 +97,58 @@ void ClipIDGenerator::update(std::forward_list<Tile *> tiles) {
     }
 }
 
+template <typename Container>
+bool coveredByChildren(const TileID& id, const Container& container) {
+    for (const auto& child : id.children()) {
+        const auto lower = container.lower_bound(child);
+        if (lower == container.end() ||
+            (lower->first != child && !coveredByChildren(child, container))) {
+            return false;
+        }
+    }
+
+    // We looked at all four immediate children and verified that they're covered.
+    return true;
+}
+
+std::map<TileID, ClipID> ClipIDGenerator::getStencils() const {
+    std::map<TileID, ClipID> stencils;
+
+    // Merge everything.
+    for (auto& leaf : pool) {
+        auto res = stencils.emplace(leaf.id, leaf.clip);
+        if (!res.second) {
+            // Merge with the existing ClipID when there was already an element with the
+            // same tile ID.
+            res.first->second |= leaf.clip;
+        }
+    }
+
+    for (auto it = stencils.begin(); it != stencils.end(); ++it) {
+        auto& childId = it->first;
+        auto& childClip = it->second;
+
+        // Loop through all preceding stencils, and find all parents.
+
+        for (auto parentIt = std::reverse_iterator<std::map<TileID, ClipID>::iterator>(it);
+             parentIt != stencils.rend(); ++parentIt) {
+            auto& parentId = parentIt->first;
+            if (childId.isChildOf(parentId)) {
+                // Once we have a parent, we add the bits  that this ID hasn't set yet.
+                const auto& parentClip = parentIt->second;
+                const auto mask = ~(childClip.mask & parentClip.mask);
+                childClip.reference |= mask & parentClip.reference;
+                childClip.mask |= parentClip.mask;
+            }
+        }
+    }
+
+    // Remove tiles that are entirely covered by children.
+    util::erase_if(stencils, [&] (const auto& stencil) {
+        return coveredByChildren(stencil.first, stencils);
+    });
+
+    return stencils;
+}
+
 } // namespace mbgl
diff --git a/src/mbgl/util/clip_id.hpp b/src/mbgl/util/clip_id.hpp
index 71a07708c9..2c128d2643 100644
--- a/src/mbgl/util/clip_id.hpp
+++ b/src/mbgl/util/clip_id.hpp
@@ -14,7 +14,6 @@
 namespace mbgl {
 
 class Tile;
-class TileID;
 
 struct ClipID {
     inline ClipID() {}
@@ -26,28 +25,33 @@ struct ClipID {
     inline bool operator==(const ClipID &other) const {
         return mask == other.mask && reference == other.reference;
     }
+
+    inline ClipID& operator|=(const ClipID &other) {
+        mask |= other.mask;
+        reference |= other.reference;
+        return *this;
+    }
 };
 
 class ClipIDGenerator {
 private:
     struct Leaf {
-        Leaf(Tile &tile);
+        Leaf(TileID, ClipID&);
         void add(const TileID &p);
         bool operator==(const Leaf &other) const;
 
-        Tile &tile;
+        const TileID id;
         std::forward_list<TileID> children;
+        ClipID& clip;
     };
 
-    typedef std::vector<Leaf> Pool;
-    std::forward_list<Pool> pools;
     uint8_t bit_offset = 0;
-
-private:
-    bool reuseExisting(Leaf &leaf);
+    std::vector<Leaf> pool;
 
 public:
     void update(std::forward_list<Tile *> tiles);
+
+    std::map<TileID, ClipID> getStencils() const;
 };