Merge pull request #439 from mapbox/clipping

Compute unique clip IDSs per tile

12 files changed, 362 insertions, 452 deletions

diff --git a/include/mbgl/map/source.hpp b/include/mbgl/map/source.hpp
index 5b51268bfe..4bc4c86dd0 100644
--- a/include/mbgl/map/source.hpp
+++ b/include/mbgl/map/source.hpp
@@ -38,6 +38,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);
 
 private:
diff --git a/include/mbgl/map/tile.hpp b/include/mbgl/map/tile.hpp
index 9cf5ff5341..24845c81a0 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 {
@@ -47,6 +51,10 @@ public:
             return w == rhs.w && z == rhs.z && x == rhs.x && y == rhs.y;
         }
 
+        inline bool operator!=(const ID& rhs) const {
+            return !operator==(rhs);
+        }
+
         inline bool operator<(const ID &rhs) const {
             if (w != rhs.w) return w < rhs.w;
             if (z != rhs.z) return z < rhs.z;
diff --git a/include/mbgl/map/tile_data.hpp b/include/mbgl/map/tile_data.hpp
index 3e639fcea1..9aaef84e04 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..5855b16af7 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<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);
+
 }
 }
 
diff --git a/src/map/map.cpp b/src/map/map.cpp
index 55566cb205..86f7f9812a 100644
--- a/src/map/map.cpp
+++ b/src/map/map.cpp
@@ -511,18 +511,12 @@ void Map::updateTiles() {
 }
 
 void Map::updateRenderState() {
-    std::forward_list<Tile::ID> ids;
-
+    // Update all clipping IDs.
+    ClipIDGenerator generator;
     for (const std::shared_ptr<StyleSource> &source : getActiveSources()) {
-        ids.splice_after(ids.before_begin(), source->source->getIDs());
+        generator.update(source->source->getLoadedTiles());
         source->source->updateMatrices(painter.projMatrix, state);
     }
-
-    const std::map<Tile::ID, ClipID> clipIDs = computeClipIDs(ids);
-
-    for (const std::shared_ptr<StyleSource> &source : getActiveSources()) {
-        source->source->updateClipIDs(clipIDs);
-    }
 }
 
 void Map::prepare() {
diff --git a/src/map/source.cpp b/src/map/source.cpp
index b83384f25f..3fe5bf42fa 100644
--- a/src/map/source.cpp
+++ b/src/map/source.cpp
@@ -121,7 +121,6 @@ void Source::finishRender(Painter &painter) {
     }
 }
 
-
 std::forward_list<Tile::ID> Source::getIDs() const {
     std::forward_list<Tile::ID> ptrs;
 
@@ -132,6 +131,18 @@ std::forward_list<Tile::ID> Source::getIDs() const {
     return ptrs;
 }
 
+std::forward_list<Tile *> Source::getLoadedTiles() const {
+    std::forward_list<Tile *> ptrs;
+    auto it = ptrs.before_begin();
+    for (const auto &pair : tiles) {
+        if (pair.second->data->ready()) {
+            it = ptrs.insert_after(it, pair.second.get());
+        }
+    }
+    return ptrs;
+}
+
+
 TileData::State Source::hasTile(const Tile::ID& id) {
     auto it = tiles.find(id);
     if (it != tiles.end()) {
diff --git a/src/renderer/painter.cpp b/src/renderer/painter.cpp
index e813ad24eb..240aff6887 100644
--- a/src/renderer/painter.cpp
+++ b/src/renderer/painter.cpp
@@ -169,9 +169,9 @@ void Painter::setStrata(float value) {
 }
 
 void Painter::prepareTile(const Tile& tile) {
-    GLint id = (GLint)tile.clip.mask.to_ulong();
-    GLuint mask = clipMask[tile.clip.length];
-    glStencilFunc(GL_EQUAL, id, mask);
+    const GLint ref = (GLint)tile.clip.reference.to_ulong();
+    const GLuint mask = (GLuint)tile.clip.mask.to_ulong();
+    glStencilFunc(GL_EQUAL, ref, mask);
 }
 
 void Painter::renderTileLayer(const Tile& tile, std::shared_ptr<StyleLayer> layer_desc, const mat4 &matrix) {
diff --git a/src/renderer/painter_clipping.cpp b/src/renderer/painter_clipping.cpp
index e94646d922..d8fa3693bd 100644
--- a/src/renderer/painter_clipping.cpp
+++ b/src/renderer/painter_clipping.cpp
@@ -14,7 +14,6 @@ void Painter::drawClippingMasks(const std::set<std::shared_ptr<StyleSource>> &so
     depthMask(false);
     glColorMask(false, false, false, false);
     depthRange(1.0f, 1.0f);
-    glStencilMask(0xFF);
 
     coveringPlainArray.bind(*plainShader, tileStencilBuffer, BUFFER_OFFSET(0));
 
@@ -31,9 +30,10 @@ void Painter::drawClippingMasks(const std::set<std::shared_ptr<StyleSource>> &so
 void Painter::drawClippingMask(const mat4& matrix, const ClipID &clip) {
     plainShader->setMatrix(matrix);
 
-    GLint id = static_cast<GLint>(clip.mask.to_ulong());
-    GLuint mask = clipMask[clip.length];
-    glStencilFunc(GL_ALWAYS, id, mask);
+    const GLint ref = (GLint)(clip.reference.to_ulong());
+    const GLuint mask = (GLuint)(clip.mask.to_ulong());
+    glStencilFunc(GL_ALWAYS, ref, mask);
+    glStencilMask(mask);
 
     glDrawArrays(GL_TRIANGLES, 0, (GLsizei)tileStencilBuffer.index());
 }
diff --git a/src/util/clip_ids.cpp b/src/util/clip_ids.cpp
index d815876a06..9c391c38ad 100644
--- a/src/util/clip_ids.cpp
+++ b/src/util/clip_ids.cpp
@@ -12,187 +12,85 @@
 
 namespace mbgl {
 
-struct TileHierarchy {
-    TileHierarchy(Tile::ID id, std::list<TileHierarchy> &&children)
-        : id(id), children(std::move(children)) {}
-
-    const Tile::ID id;
-    ClipID clip;
-    std::list<TileHierarchy> children;
-};
-
-std::list<TileHierarchy> partition(std::forward_list<Tile::ID> &&array) {
-    if (array.empty()) {
-        // We don't have to update the clipping mask because there are no tiles
-        // anyway.
-        return {};
-    }
-
-    int8_t minZ = array.begin()->z;
-
-    std::list<TileHierarchy> result;
-    std::forward_list<Tile::ID> remainder;
-    auto remainder_it = remainder.before_begin();
-
-    while (!array.empty()) {
-        const Tile::ID id = array.front();
-        array.pop_front();
-        if (id.z == minZ) {
-            std::forward_list<Tile::ID> children;
-            auto children_it = children.before_begin();
-
-            array.remove_if([&id, &children, &children_it](const Tile::ID &child) {
-                if (child.isChildOf(id)) {
-                    children_it = children.insert_after(children_it, child);
-                    return true;
-                } else {
-                    return false;
-                }
-            });
-
-            result.emplace_back(id, partition(std::move(children)));
-        } else {
-            remainder_it = remainder.insert_after(remainder_it, id);
+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);
     }
-
-    // Concatenate the remainder.
-    if (!remainder.empty()) {
-        result.splice(result.begin(), partition(std::move(remainder)));
-    }
-
-    return result;
 }
 
-uint8_t prefix(std::list<TileHierarchy> &array, TileHierarchy *parent = nullptr) {
-    if (array.empty()) {
-        return 0;
-    }
-
-    bool all_children_are_immediate = true;
-    uint8_t max_child_prefix_length = 0;
-
-    struct Huffman {
-        explicit Huffman(int prefix_length, TileHierarchy *item)
-            : prefix_length(prefix_length), children(1, item) {}
-        uint8_t prefix_length;
-        std::vector<TileHierarchy *> children;
-    };
-
-    // Create a temporary structure that we use for sorting the prefix tree.
-    std::list<Huffman> huffman;
-    std::transform(array.begin(), array.end(), std::back_inserter(huffman), [parent, &all_children_are_immediate, &max_child_prefix_length](TileHierarchy &item) {
-        uint8_t prefix_length = prefix(item.children, &item);
+bool ClipIDGenerator::Leaf::operator==(const Leaf &other) const {
+    return tile.id == other.tile.id && children == other.children;
+}
 
-        if (prefix_length > max_child_prefix_length) {
-            max_child_prefix_length = prefix_length;
+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;
+}
 
-        if (!parent || item.id.z != parent->id.z + 1) {
-            all_children_are_immediate = false;
-        }
+void ClipIDGenerator::update(std::forward_list<Tile *> tiles) {
+    Pool pool;
 
-        return Huffman { prefix_length + 1, &item };
+    tiles.sort([](const Tile *a, const Tile *b) {
+        return a->id < b->id;
     });
 
-    while (huffman.size() > 1) {
-        huffman.sort([](const Huffman &a, const Huffman &b) {
-            return a.prefix_length < b.prefix_length;
-        });
-
-        Huffman &first = *huffman.begin();
-        Huffman &second = *(++huffman.begin());
-
-        assert(&first != &second);
-
-        // Prefix with 0
-        std::for_each(first.children.begin(), first.children.end(), [](TileHierarchy *child) {
-            child->clip.mask >>= 1;
-            child->clip.mask.set(7, false); // noop
-            child->clip.length++;
-        });
-        first.prefix_length++;
-
-        // Prefix with 1
-        std::for_each(second.children.begin(), second.children.end(), [](TileHierarchy *child) {
-            child->clip.mask >>= 1;
-            child->clip.mask.set(7, true);
-            child->clip.length++;
-        });
-        second.prefix_length++;
-
-        second.children.insert(second.children.end(), first.children.begin(), first.children.end());
-        second.prefix_length = first.prefix_length + second.prefix_length;
-
-        // Remove the first child as we've just merged it into the second version.
-        huffman.erase(huffman.begin());
-    }
-
-    uint8_t prefix_length = 0;
+    const auto end = tiles.end();
+    for (auto it = tiles.begin(); it != end; it++) {
+        if (!*it) {
+            // Handle null pointers.
+            continue;
+        }
 
-    // Filter out all-zero bits
-    bool filter_zero = !all_children_are_immediate || array.size() != 4;
+        Tile &tile = **it;
+        Leaf clip { tile };
 
-    for (TileHierarchy &item : array) {
-        if (filter_zero && !item.clip.mask.any()) {
-            // Make sure we don't have a prefix that is all zeros.
-            // item.clip.mask |= (0x80 >> item.length);
-            item.clip.mask.set(7 - item.clip.length);
-            item.clip.length++;
+        // 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();
 
-        if (item.clip.length > prefix_length) {
-            prefix_length = item.clip.length;
+        // 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));
         }
     }
 
-    return max_child_prefix_length + prefix_length;
-}
-
-void propagate(std::map<Tile::ID, ClipID> &mapping, std::list<TileHierarchy> &array, const ClipID &parent = ClipID{}) {
-    for (auto &item : array) {
-        item.clip.mask >>= parent.length;
-        item.clip.mask |= parent.mask;
-        item.clip.length += parent.length;
-#if defined(DEBUG)
-        auto result = mapping.emplace(item.id, item.clip);
-        assert("Tried to insert a duplicate item" && result.second == true);
-#else
-        mapping.emplace(item.id, item.clip);
-#endif
-        propagate(mapping, item.children, const_cast<const ClipID &>(item.clip));
-    };
-}
-
-void updateClipIDs(const std::list<Tile *> &array) {
-    std::forward_list<Tile::ID> ids;
-    std::transform(array.begin(), array.end(), std::front_inserter(ids), [](Tile *item) {
-        return item->id;
-    });
+    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);
 
-    const std::map<Tile::ID, ClipID> mapping = computeClipIDs(ids);
-
-    std::for_each(array.begin(), array.end(), [&mapping](Tile *item) {
-        auto it = mapping.find(item->id);
-        if (it != mapping.end()) {
-            item->clip = it->second;
-        } else {
-            item->clip = ClipID {};
+        // 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;
         }
-    });
-}
 
-std::map<Tile::ID, ClipID> computeClipIDs(std::forward_list<Tile::ID> array) {
-    // Sort by zoom level and make sure that we don't have duplicate elements.
-    array.sort();
-    array.unique();
-
-    std::list<TileHierarchy> hierarchy = partition(std::move(array));
-    prefix(hierarchy);
+        bit_offset += bit_count;
+        pools.push_front(std::move(pool));
+    }
 
-    std::map<Tile::ID, ClipID> mapping;
-    propagate(mapping, hierarchy);
-    return mapping;
+    if (bit_offset > 8) {
+        fprintf(stderr, "stencil mask overflow\n");
+    }
 }
 
 }
diff --git a/src/util/math.cpp b/src/util/math.cpp
new file mode 100644
index 0000000000..a7eab2d771
--- /dev/null
+++ b/src/util/math.cpp
@@ -0,0 +1,25 @@
+#include <mbgl/util/math.hpp>
+
+namespace mbgl {
+namespace util {
+
+// From http://stackoverflow.com/questions/3272424/compute-fast-log-base-2-ceiling
+uint32_t ceil_log2(uint64_t x) {
+    static const uint64_t t[6] = {0xFFFFFFFF00000000, 0x00000000FFFF0000,
+                                  0x000000000000FF00, 0x00000000000000F0,
+                                  0x000000000000000C, 0x0000000000000002};
+    uint32_t y = (((x & (x - 1)) == 0) ? 0 : 1);
+    uint32_t j = 32;
+
+    for (int32_t i = 0; i < 6; i++) {
+        const uint32_t k = (((x & t[i]) == 0) ? 0 : j);
+        y += k;
+        x >>= k;
+        j >>= 1;
+    }
+
+    return y;
+}
+
+}
+}
\ No newline at end of file
diff --git a/test/clip_ids.cpp b/test/clip_ids.cpp
index f2e8be98bc..18ef9658e5 100644
--- a/test/clip_ids.cpp
+++ b/test/clip_ids.cpp
@@ -8,298 +8,244 @@
 
 using namespace mbgl;
 
-TEST(ClipIDs, ClipMasks) {
-    ASSERT_EQ(0, clipMask[0]);
-    ASSERT_EQ(0x80, clipMask[1]);
-    ASSERT_EQ(0xC0, clipMask[2]);
-    ASSERT_EQ(0xE0, clipMask[3]);
-    ASSERT_EQ(0xF0, clipMask[4]);
-    ASSERT_EQ(0xF8, clipMask[5]);
-    ASSERT_EQ(0xFC, clipMask[6]);
-    ASSERT_EQ(0xFE, clipMask[7]);
-    ASSERT_EQ(0xFF, clipMask[8]);
+template <typename T> void generate(const T &sources) {
+    ClipIDGenerator generator;
+
+    for (size_t j = 0; j < sources.size(); j++) {
+        std::forward_list<Tile *> tile_ptrs;
+        std::transform(sources[j].begin(), sources[j].end(), std::front_inserter(tile_ptrs), [](const std::shared_ptr<Tile> &tile) { return tile.get(); });
+        generator.update(tile_ptrs);
+    }
 }
 
+template <typename T> void print(const T &sources) {
+    for (size_t j = 0; j < sources.size(); j++) {
+        for (size_t i = 0; i < sources[j].size(); i++) {
+            std::cout << "    ASSERT_EQ(ClipID(\"" << sources[j][i]->clip.mask << "\", \"" << sources[j][i]->clip.reference << "\"), sources[" << j << "][" << i << "]->clip);\n";
+        }
+    }
+}
 
 TEST(ClipIDs, ParentAndFourChildren) {
-    std::array<std::unique_ptr<Tile>, 5> tiles {{
-        std::make_unique<Tile>(Tile::ID { 1, 0, 0 }), // 1/0/0: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, 0, 1 }), // 1/0/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, 1, 0 }), // 1/1/0: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, 1, 1 }), // 1/1/1: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 0, 0, 0 }), // 0/0/0: 10000000 (1)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[4]->clip.mask); ASSERT_EQ(1, tiles[4]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 1, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 0, 0, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][4]->clip);
 }
 
 TEST(ClipIDs, ParentAndFourChildrenNegative) {
-    std::array<std::unique_ptr<Tile>, 5> tiles {{
-        std::make_unique<Tile>(Tile::ID { 1, -2, 0 }), // 1/0/0: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, -2, 1 }), // 1/0/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, -1, 0 }), // 1/1/0: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, -1, 1 }), // 1/1/1: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 0, -1, 0 }), // 0/0/0: 10000000 (1)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[4]->clip.mask); ASSERT_EQ(1, tiles[4]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 1, -2, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, -2, 1 }),
+            std::make_shared<Tile>(Tile::ID { 1, -1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, -1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 0, -1, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][4]->clip);
 }
 
 TEST(ClipIDs, NegativeParentAndMissingLevel) {
-    std::array<std::unique_ptr<Tile>, 5> tiles {{
-        std::make_unique<Tile>(Tile::ID { 1, -1, 0 }), // 1/-1/0: 10000000 (1)
-        std::make_unique<Tile>(Tile::ID { 2, -1, 0 }), // 2/-1/0: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, -2, 1 }), // 2/-2/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, -1, 1 }), // 2/-1/1: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, -2, 0 }), // 2/-2/0: 11000000 (3)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask); ASSERT_EQ(1, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[4]->clip.mask); ASSERT_EQ(3, tiles[4]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 1, -1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, -1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, -2, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, -1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, -2, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][4]->clip);
 }
 
 
 TEST(ClipIDs, SevenOnSameLevel) {
-    std::array<std::unique_ptr<Tile>, 7> tiles {{
-        std::make_unique<Tile>(Tile::ID { 2, 0, 0 }), // 2/0/0: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 0, 1 }), // 2/0/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 0, 2 }), // 2/0/2: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 0 }), // 2/1/0: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 1 }), // 2/1/1: 01000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 2 }), // 2/1/2: 01100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 2, 0 }), // 2/2/0: 00100000 (3)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("01000000"), tiles[4]->clip.mask); ASSERT_EQ(3, tiles[4]->clip.length);
-    ASSERT_EQ(std::bitset<8>("01100000"), tiles[5]->clip.mask); ASSERT_EQ(3, tiles[5]->clip.length);
-    ASSERT_EQ(std::bitset<8>("00100000"), tiles[6]->clip.mask); ASSERT_EQ(3, tiles[6]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 2 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 2 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][4]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000110"), sources[0][5]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000111"), sources[0][6]->clip);
 }
 
 TEST(ClipIDs, MultipleLevels) {
-    std::array<std::unique_ptr<Tile>, 12> tiles {{
-        std::make_unique<Tile>(Tile::ID { 2, 0, 0 }),           // 2/0/0: 10000000 (1)
-            std::make_unique<Tile>(Tile::ID { 3, 0, 0 }),       //     3/0/0: 10000000 (3)
-            std::make_unique<Tile>(Tile::ID { 3, 0, 1 }),       //     3/0/1: 11100000 (3)
-                std::make_unique<Tile>(Tile::ID { 4, 0, 2 }),   //         4/0/2: 11110000 (5)
-                std::make_unique<Tile>(Tile::ID { 4, 1, 2 }),   //         4/0/3: 11111000 (5)
-                std::make_unique<Tile>(Tile::ID { 4, 0, 3 }),   //         4/1/2: 11100000 (5)
-                std::make_unique<Tile>(Tile::ID { 4, 1, 3 }),   //         4/1/3: 11101000 (5)
-            std::make_unique<Tile>(Tile::ID { 3, 1, 0 }),       //     3/1/0: 10100000 (3)
-            std::make_unique<Tile>(Tile::ID { 3, 1, 1 }),       //     3/1/1: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 0 }),           // 2/1/0: 01000000 (2)
-            std::make_unique<Tile>(Tile::ID { 3, 2, 0 }),       //     3/2/0: 01010000 (4)
-            std::make_unique<Tile>(Tile::ID { 3, 2, 1 }),       //     3/2/1: 01100000 (3)
-    }};
-
-    // Use a random order to verify that the result of this algorithm is independent of the
-    std::random_shuffle(tiles.begin(), tiles.end());
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // Sort them by tile ID so that we know what order we have to test in.
-    std::sort(tiles.begin(), tiles.end(), [](const std::unique_ptr<Tile> &a, const std::unique_ptr<Tile> &b) {
-        return a->id < b->id;
-    });
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::string("2/0/0"), std::string(tiles[0]->id));
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask);
-    ASSERT_EQ(1, tiles[0]->clip.length);
-
-    ASSERT_EQ(std::string("2/1/0"), std::string(tiles[1]->id));
-    ASSERT_EQ(std::bitset<8>("01000000"), tiles[1]->clip.mask);
-    ASSERT_EQ(2, tiles[1]->clip.length);
-
-    ASSERT_EQ(std::string("3/0/0"), std::string(tiles[2]->id));
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask);
-    ASSERT_EQ(3, tiles[2]->clip.length);
-
-    ASSERT_EQ(std::string("3/0/1"), std::string(tiles[3]->id));
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[3]->clip.mask);
-    ASSERT_EQ(3, tiles[3]->clip.length);
-
-    ASSERT_EQ(std::string("3/1/0"), std::string(tiles[4]->id));
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[4]->clip.mask);
-    ASSERT_EQ(3, tiles[4]->clip.length);
-
-    ASSERT_EQ(std::string("3/1/1"), std::string(tiles[5]->id));
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[5]->clip.mask);
-    ASSERT_EQ(3, tiles[5]->clip.length);
-
-    ASSERT_EQ(std::string("3/2/0"), std::string(tiles[6]->id));
-    ASSERT_EQ(std::bitset<8>("01010000"), tiles[6]->clip.mask);
-    ASSERT_EQ(4, tiles[6]->clip.length);
-
-    ASSERT_EQ(std::string("3/2/1"), std::string(tiles[7]->id));
-    ASSERT_EQ(std::bitset<8>("01100000"), tiles[7]->clip.mask);
-    ASSERT_EQ(3, tiles[7]->clip.length);
-
-    ASSERT_EQ(std::string("4/0/2"), std::string(tiles[8]->id));
-    ASSERT_EQ(std::bitset<8>("11110000"), tiles[8]->clip.mask);
-    ASSERT_EQ(5, tiles[8]->clip.length);
-
-    ASSERT_EQ(std::string("4/0/3"), std::string(tiles[9]->id));
-    ASSERT_EQ(std::bitset<8>("11111000"), tiles[9]->clip.mask);
-    ASSERT_EQ(5, tiles[9]->clip.length);
-
-    ASSERT_EQ(std::string("4/1/2"), std::string(tiles[10]->id));
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[10]->clip.mask);
-    ASSERT_EQ(5, tiles[10]->clip.length);
-
-    ASSERT_EQ(std::string("4/1/3"), std::string(tiles[11]->id));
-    ASSERT_EQ(std::bitset<8>("11101000"), tiles[11]->clip.mask);
-    ASSERT_EQ(5, tiles[11]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 0, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 0, 1 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 0, 2 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 1, 2 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 0, 3 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 1, 3 }),
+                std::make_shared<Tile>(Tile::ID { 3, 1, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 2, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 2, 1 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00001111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000011"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000100"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001001"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001011"), sources[0][4]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001010"), sources[0][5]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001100"), sources[0][6]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000101"), sources[0][7]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000110"), sources[0][8]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000010"), sources[0][9]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000111"), sources[0][10]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001000"), sources[0][11]->clip);
 }
 
 
 TEST(ClipIDs, Bug206) {
-    std::array<std::unique_ptr<Tile>, 11> tiles {{
-        std::make_unique<Tile>(Tile::ID { 10, 162, 395 }),      // 10/162/395: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 162, 396 }),      // 10/162/396: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 163, 395 }),      // 10/163/395: 11000000 (2)
-            std::make_unique<Tile>(Tile::ID { 11, 326, 791 }),  //     11/326/791: 11100000 (4)
-            std::make_unique<Tile>(Tile::ID { 12, 654, 1582 }), //     12/654/1582: 11001000 (5)
-            std::make_unique<Tile>(Tile::ID { 12, 654, 1583 }), //     12/654/1583: 11010000 (4)
-            std::make_unique<Tile>(Tile::ID { 12, 655, 1582 }), //     12/655/1582: 11110000 (5)
-            std::make_unique<Tile>(Tile::ID { 12, 655, 1583 }), //     12/655/1583: 11111000 (5)
-        std::make_unique<Tile>(Tile::ID { 10, 163, 396 }),      // 10/163/396: 01000000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 164, 395 }),      // 10/164/395: 01100000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 164, 396 }),      // 10/164/396: 00100000 (3)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::string("10/162/395"), std::string(tiles[0]->id));
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask);
-    ASSERT_EQ(3, tiles[0]->clip.length);
-
-    ASSERT_EQ(std::string("10/162/396"), std::string(tiles[1]->id));
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[1]->clip.mask);
-    ASSERT_EQ(3, tiles[1]->clip.length);
-
-    ASSERT_EQ(std::string("10/163/395"), std::string(tiles[2]->id));
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[2]->clip.mask);
-    ASSERT_EQ(2, tiles[2]->clip.length);
-
-    ASSERT_EQ(std::string("11/326/791"), std::string(tiles[3]->id));
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[3]->clip.mask);
-    ASSERT_EQ(4, tiles[3]->clip.length);
-
-    ASSERT_EQ(std::string("12/654/1582"), std::string(tiles[4]->id));
-    ASSERT_EQ(std::bitset<8>("11001000"), tiles[4]->clip.mask);
-    ASSERT_EQ(5, tiles[4]->clip.length);
-
-    ASSERT_EQ(std::string("12/654/1583"), std::string(tiles[5]->id));
-    ASSERT_EQ(std::bitset<8>("11010000"), tiles[5]->clip.mask);
-    ASSERT_EQ(4, tiles[5]->clip.length);
-
-    ASSERT_EQ(std::string("12/655/1582"), std::string(tiles[6]->id));
-    ASSERT_EQ(std::bitset<8>("11110000"), tiles[6]->clip.mask);
-    ASSERT_EQ(5, tiles[6]->clip.length);
-
-    ASSERT_EQ(std::string("12/655/1583"), std::string(tiles[7]->id));
-    ASSERT_EQ(std::bitset<8>("11111000"), tiles[7]->clip.mask);
-    ASSERT_EQ(5, tiles[7]->clip.length);
-
-    ASSERT_EQ(std::string("10/163/396"), std::string(tiles[8]->id));
-    ASSERT_EQ(std::bitset<8>("01000000"), tiles[8]->clip.mask);
-    ASSERT_EQ(3, tiles[8]->clip.length);
-
-    ASSERT_EQ(std::string("10/164/395"), std::string(tiles[9]->id));
-    ASSERT_EQ(std::bitset<8>("01100000"), tiles[9]->clip.mask);
-    ASSERT_EQ(3, tiles[9]->clip.length);
-
-    ASSERT_EQ(std::string("10/164/396"), std::string(tiles[10]->id));
-    ASSERT_EQ(std::bitset<8>("00100000"), tiles[10]->clip.mask);
-    ASSERT_EQ(3, tiles[10]->clip.length);
-
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 10, 162, 395 }),
+            std::make_shared<Tile>(Tile::ID { 10, 162, 396 }),
+            std::make_shared<Tile>(Tile::ID { 10, 163, 395 }),
+                std::make_shared<Tile>(Tile::ID { 11, 326, 791 }),
+                std::make_shared<Tile>(Tile::ID { 12, 654, 1582 }),
+                std::make_shared<Tile>(Tile::ID { 12, 654, 1583 }),
+                std::make_shared<Tile>(Tile::ID { 12, 655, 1582 }),
+                std::make_shared<Tile>(Tile::ID { 12, 655, 1583 }),
+            std::make_shared<Tile>(Tile::ID { 10, 163, 396 }),
+            std::make_shared<Tile>(Tile::ID { 10, 164, 395 }),
+            std::make_shared<Tile>(Tile::ID { 10, 164, 396 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00001111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000111"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001000"), sources[0][4]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001001"), sources[0][5]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001010"), sources[0][6]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001011"), sources[0][7]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000100"), sources[0][8]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000101"), sources[0][9]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000110"), sources[0][10]->clip);
 }
 
-TEST(ClipIDs, DuplicateIDs) {
-
-    std::forward_list<Tile::ID> tiles {{
-        Tile::ID { 2, 0, 0 },
-        Tile::ID { 2, 0, 1 },
-        Tile::ID { 2, 0, 0 },
-        Tile::ID { 2, 0, 1 },
-        Tile::ID { 2, 0, 1 },
-    }};
 
-    std::map<Tile::ID, ClipID> mapping = computeClipIDs(tiles);
-
-    ASSERT_EQ(2ull, mapping.size());
-
-    // for (const auto &it : mapping) {
-    //     std::cout << std::string(it.first) << "(" << it.first << ")" << ": " << it.second.mask << " (" << (int)it.second.length << ")" << std::endl;
-    // }
+TEST(ClipIDs, MultipleSources) {
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 0, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 2 }),
+        },
+        {
+            std::make_shared<Tile>(Tile::ID { 0, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 2 }),
+        },
+        {
+            std::make_shared<Tile>(Tile::ID { 1, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 1 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00011000", "00001000"), sources[1][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[1][1]->clip);
+    ASSERT_EQ(ClipID("00011000", "00010000"), sources[1][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[1][3]->clip);
+    ASSERT_EQ(ClipID("11100000", "00100000"), sources[2][0]->clip);
+    ASSERT_EQ(ClipID("11100000", "01000000"), sources[2][1]->clip);
+    ASSERT_EQ(ClipID("11100000", "01100000"), sources[2][2]->clip);
+    ASSERT_EQ(ClipID("11100000", "10000000"), sources[2][3]->clip);
+    ASSERT_EQ(ClipID("00011000", "00010000"), sources[2][4]->clip);
+}
 
-    ASSERT_EQ(std::bitset<8>("01000000"), mapping[Tile::ID(2, 0, 0)].mask);
-    ASSERT_EQ(2, mapping[Tile::ID(2, 0, 0)].length);
 
-    ASSERT_EQ(std::bitset<8>("10000000"), mapping[Tile::ID(2, 0, 1)].mask);
-    ASSERT_EQ(1, mapping[Tile::ID(2, 0, 1)].length);
+TEST(ClipIDs, DuplicateIDs) {
+        const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+        },
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+        }
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000011", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000001"), sources[1][0]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000010"), sources[1][1]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000010"), sources[1][2]->clip);
 }