compute unique clip ids per tile, taking covering children into account

fixes #206
fixes #220
refs #229

5 files changed, 39 insertions, 7 deletions

diff --git a/include/mbgl/map/source.hpp b/include/mbgl/map/source.hpp
index 4ffd097193..a9ff29e80a 100644
--- a/include/mbgl/map/source.hpp
+++ b/include/mbgl/map/source.hpp
@@ -36,6 +36,7 @@ public:
     void finishRender(Painter &painter);
 
     std::forward_list<Tile::ID> getIDs() const;
+    std::forward_list<Tile *> getLoadedTiles() const;
     void updateClipIDs(const std::map<Tile::ID, ClipID> &mapping);
 
     static std::string normalizeSourceURL(const std::string &url, const std::string &access_token);
diff --git a/include/mbgl/map/tile.hpp b/include/mbgl/map/tile.hpp
index 9cf5ff5341..09462604a7 100644
--- a/include/mbgl/map/tile.hpp
+++ b/include/mbgl/map/tile.hpp
@@ -18,11 +18,15 @@ namespace mbgl {
 class TileData;
 
 struct ClipID {
-    explicit ClipID() {}
-    explicit ClipID(const std::bitset<8> &mask, uint8_t length) : mask(mask), length(length) {}
-    explicit ClipID(const std::string &mask, uint8_t length) : mask(mask), length(length) {}
+    inline ClipID() {}
+    inline ClipID(const std::string &mask_, const std::string &reference_) : mask(mask_), reference(reference_) {}
+
     std::bitset<8> mask;
-    uint8_t length = 0;
+    std::bitset<8> reference;
+
+    inline bool operator==(const ClipID &other) const {
+        return mask == other.mask && reference == other.reference;
+    }
 };
 
 class Tile : private util::noncopyable {
diff --git a/include/mbgl/map/tile_data.hpp b/include/mbgl/map/tile_data.hpp
index 5991613a2d..9bc76727a1 100644
--- a/include/mbgl/map/tile_data.hpp
+++ b/include/mbgl/map/tile_data.hpp
@@ -49,6 +49,10 @@ public:
     void reparse();
     const std::string toString() const;
 
+    inline bool ready() const {
+        return state == State::parsed;
+    }
+
     // Override this in the child class.
     virtual void beforeParse();
     virtual void parse() = 0;
diff --git a/include/mbgl/util/clip_ids.hpp b/include/mbgl/util/clip_ids.hpp
index 748d3d8f5f..52c571d598 100644
--- a/include/mbgl/util/clip_ids.hpp
+++ b/include/mbgl/util/clip_ids.hpp
@@ -4,15 +4,34 @@
 #include <mbgl/map/tile.hpp>
 #include <list>
 #include <set>
+#include <vector>
+#include <forward_list>
 #include <map>
 
 namespace mbgl {
 
-static constexpr uint8_t clipMask[9] { 0x00, 0x80, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC, 0xFE, 0xFF };
+class ClipIDGenerator {
+private:
+    struct Leaf {
+        Leaf(Tile &tile);
+        void add(const Tile::ID &p);
+        bool operator==(const Leaf &other) const;
 
-void updateClipIDs(const std::list<Tile *> &array);
+        Tile &tile;
+        std::forward_list<Tile::ID> children;
+    };
+
+    typedef std::vector<Leaf> Pool;
+    std::forward_list<const Pool> pools;
+    uint8_t bit_offset = 0;
+
+private:
+    bool reuseExisting(Leaf &leaf);
+
+public:
+    void update(std::forward_list<Tile *> tiles);
+};
 
-std::map<Tile::ID, ClipID> computeClipIDs(std::forward_list<Tile::ID> array);
 
 }
 
diff --git a/include/mbgl/util/math.hpp b/include/mbgl/util/math.hpp
index fde2a4720b..2bef5b18e2 100644
--- a/include/mbgl/util/math.hpp
+++ b/include/mbgl/util/math.hpp
@@ -104,6 +104,10 @@ T smoothstep(T edge0, T edge1, T x) {
     return t * t * (T(3) - T(2) * t);
 }
 
+// Computes the log2(x) rounded up to the next integer.
+// (== number of bits required to store x)
+uint32_t ceil_log2(uint64_t x);
+
 }
 }