1 files changed, 96 insertions, 0 deletions
diff --git a/src/mbgl/util/clip_ids.cpp b/src/mbgl/util/clip_ids.cpp
new file mode 100644
index 0000000000..9c391c38ad
--- /dev/null
+++ b/src/mbgl/util/clip_ids.cpp
@@ -0,0 +1,96 @@
+#include <mbgl/util/clip_ids.hpp>
+#include <mbgl/map/tile.hpp>
+
+#include <mbgl/util/math.hpp>
+
+#include <list>
+#include <vector>
+#include <bitset>
+#include <cassert>
+#include <iostream>
+#include <algorithm>
+
+namespace mbgl {
+
+ClipIDGenerator::Leaf::Leaf(Tile &tile_) : tile(tile_) {}
+
+void ClipIDGenerator::Leaf::add(const Tile::ID &p) {
+    if (p.isChildOf(tile.id)) {
+        // Ensure that no already present child is a parent of the new p.
+        for (const Tile::ID &child : children) {
+            if (p.isChildOf(child))
+                return;
+        }
+        children.push_front(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 std::vector<Leaf> &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;
+}
+
+void ClipIDGenerator::update(std::forward_list<Tile *> tiles) {
+    Pool pool;
+
+    tiles.sort([](const Tile *a, const Tile *b) {
+        return a->id < b->id;
+    });
+
+    const auto end = tiles.end();
+    for (auto it = tiles.begin(); it != end; it++) {
+        if (!*it) {
+            // Handle null pointers.
+            continue;
+        }
+
+        Tile &tile = **it;
+        Leaf clip { tile };
+
+        // 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);
+        }
+        clip.children.sort();
+
+        // Loop through all existing pools and try to find a matching ClipID.
+        if (!reuseExisting(clip)) {
+            // We haven't found an existing clip ID
+            pool.push_back(std::move(clip));
+        }
+    }
+
+    if (pool.size()) {
+        const uint32_t bit_count = util::ceil_log2(pool.size() + 1);
+        const std::bitset<8> mask = uint64_t(((1 << 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 (Leaf &leaf : pool) {
+            leaf.tile.clip.mask = mask;
+            leaf.tile.clip.reference = count++ << bit_offset;
+        }
+
+        bit_offset += bit_count;
+        pools.push_front(std::move(pool));
+    }
+
+    if (bit_offset > 8) {
+        fprintf(stderr, "stencil mask overflow\n");
+    }
+}
+
+}