[core] add algorithm for generating clip IDs based on the new TileID classes

3 files changed, 200 insertions, 0 deletions

diff --git a/src/mbgl/algorithm/generate_clip_ids.cpp b/src/mbgl/algorithm/generate_clip_ids.cpp
new file mode 100644
index 0000000000..369cb35de1
--- /dev/null
+++ b/src/mbgl/algorithm/generate_clip_ids.cpp
@@ -0,0 +1,81 @@
+#include <mbgl/algorithm/generate_clip_ids_impl.hpp>
+#include <mbgl/algorithm/covered_by_children.hpp>
+
+#include <mbgl/util/std.hpp>
+#include <mbgl/tile/tile.hpp>
+
+#include <list>
+#include <vector>
+#include <bitset>
+#include <cassert>
+#include <iostream>
+#include <algorithm>
+#include <iterator>
+
+namespace mbgl {
+namespace algorithm {
+
+ClipIDGenerator::Leaf::Leaf(ClipID& clip_) : clip(clip_) {
+}
+
+void ClipIDGenerator::Leaf::add(const CanonicalTileID& p) {
+    // Ensure that no already present child is a parent of the new p.
+    for (const auto& child : children) {
+        if (p.isChildOf(child)) {
+            return;
+        }
+    }
+    children.emplace(p);
+}
+
+bool ClipIDGenerator::Leaf::operator==(const Leaf& other) const {
+    return children == other.children;
+}
+
+// Instantiate the function for Tile& refs.
+template void ClipIDGenerator::update(std::map<UnwrappedTileID, Tile&>&);
+
+std::map<UnwrappedTileID, ClipID> ClipIDGenerator::getStencils() const {
+    std::map<UnwrappedTileID, ClipID> stencils;
+
+    // Merge everything.
+    for (auto& pair : pool) {
+        auto& id = pair.first;
+        auto& leaf = pair.second;
+        auto res = stencils.emplace(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<decltype(it)>(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 algorithm::coveredByChildren(stencil.first, stencils);
+    });
+
+    return stencils;
+}
+
+} // namespace algorithm
+} // namespace mbgl
diff --git a/src/mbgl/algorithm/generate_clip_ids.hpp b/src/mbgl/algorithm/generate_clip_ids.hpp
new file mode 100644
index 0000000000..8b06354d47
--- /dev/null
+++ b/src/mbgl/algorithm/generate_clip_ids.hpp
@@ -0,0 +1,38 @@
+#ifndef MBGL_ALGORITHM_GENERATE_CLIP_IDS
+#define MBGL_ALGORITHM_GENERATE_CLIP_IDS
+
+#include <mbgl/tile/tile_id.hpp>
+#include <mbgl/util/clip_id.hpp>
+
+#include <set>
+#include <vector>
+#include <map>
+
+namespace mbgl {
+namespace algorithm {
+
+class ClipIDGenerator {
+private:
+    struct Leaf {
+        Leaf(ClipID&);
+        void add(const CanonicalTileID &p);
+        bool operator==(const Leaf &other) const;
+
+        std::set<CanonicalTileID> children;
+        ClipID& clip;
+    };
+
+    uint8_t bit_offset = 0;
+    std::multimap<UnwrappedTileID, Leaf> pool;
+
+public:
+    template <typename Renderables>
+    void update(Renderables& renderables);
+
+    std::map<UnwrappedTileID, ClipID> getStencils() const;
+};
+
+} // namespace algorithm
+} // namespace mbgl
+
+#endif
diff --git a/src/mbgl/algorithm/generate_clip_ids_impl.hpp b/src/mbgl/algorithm/generate_clip_ids_impl.hpp
new file mode 100644
index 0000000000..479061b6cb
--- /dev/null
+++ b/src/mbgl/algorithm/generate_clip_ids_impl.hpp
@@ -0,0 +1,81 @@
+#ifndef MBGL_ALGORITHM_GENERATE_CLIP_IDS_IMPL
+#define MBGL_ALGORITHM_GENERATE_CLIP_IDS_IMPL
+
+#include <mbgl/algorithm/generate_clip_ids.hpp>
+#include <mbgl/util/math.hpp>
+#include <mbgl/platform/log.hpp>
+
+namespace mbgl {
+namespace algorithm {
+
+template <typename Renderables>
+void ClipIDGenerator::update(Renderables& renderables) {
+    std::size_t size = 0;
+
+    const auto end = renderables.end();
+    for (auto it = renderables.begin(); it != end; it++) {
+        auto& tileID = it->first;
+        auto& renderable = it->second;
+        renderable.clip = {};
+        Leaf leaf{ renderable.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. 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>(tileID.wrap + 1), { 0, 0, 0 } },
+            [](auto& a, auto& b) { return a.first < b; });
+        for (; child_it != children_end; ++child_it) {
+            auto& childTileID = child_it->first;
+            if (childTileID.isChildOf(tileID)) {
+                leaf.add(childTileID.canonical);
+            }
+        }
+
+        // Find a leaf with matching children.
+        for (auto its = pool.equal_range(tileID); its.first != its.second; ++its.first) {
+            auto& existing = its.first->second;
+            if (existing == leaf) {
+                leaf.clip = existing.clip;
+                break;
+            }
+        }
+        if (leaf.clip.reference.none()) {
+            // We haven't found an existing clip ID
+            size++;
+        }
+
+        pool.emplace(tileID, std::move(leaf));
+    }
+
+    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& pair : renderables) {
+            auto& renderable = pair.second;
+            renderable.clip.mask |= mask;
+
+            // Assign only to clip IDs that have no value yet.
+            if (renderable.clip.reference.none()) {
+                renderable.clip.reference = uint32_t(count++) << bit_offset;
+            }
+        }
+
+        bit_offset += bit_count;
+    }
+
+    if (bit_offset > 8) {
+        Log::Error(Event::OpenGL, "stencil mask overflow");
+    }
+}
+
+} // namespace algorithm
+} // namespace mbgl
+
+#endif