summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/mbgl/algorithm/generate_clip_ids.cpp81
-rw-r--r--src/mbgl/algorithm/generate_clip_ids.hpp38
-rw-r--r--src/mbgl/algorithm/generate_clip_ids_impl.hpp81
-rw-r--r--src/mbgl/util/clip_id.cpp4
-rw-r--r--src/mbgl/util/clip_id.hpp3
-rw-r--r--test/algorithm/generate_clip_ids.cpp427
-rw-r--r--test/test.gypi1
7 files changed, 635 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
diff --git a/src/mbgl/util/clip_id.cpp b/src/mbgl/util/clip_id.cpp
index 0da8a890ce..6346552962 100644
--- a/src/mbgl/util/clip_id.cpp
+++ b/src/mbgl/util/clip_id.cpp
@@ -15,6 +15,10 @@
namespace mbgl {
+::std::ostream& operator<<(::std::ostream& os, const ClipID& rhs) {
+ return os << "mask=" << rhs.mask << ",ref=" << rhs.reference;
+}
+
ClipIDGenerator::Leaf::Leaf(TileID id_, ClipID& clip_) : id(id_), clip(clip_) {}
void ClipIDGenerator::Leaf::add(const TileID &p) {
diff --git a/src/mbgl/util/clip_id.hpp b/src/mbgl/util/clip_id.hpp
index 2c128d2643..aa16f2d0d6 100644
--- a/src/mbgl/util/clip_id.hpp
+++ b/src/mbgl/util/clip_id.hpp
@@ -9,6 +9,7 @@
#include <set>
#include <vector>
#include <forward_list>
+#include <iosfwd>
#include <map>
namespace mbgl {
@@ -33,6 +34,8 @@ struct ClipID {
}
};
+::std::ostream& operator<<(::std::ostream& os, const ClipID& rhs);
+
class ClipIDGenerator {
private:
struct Leaf {
diff --git a/test/algorithm/generate_clip_ids.cpp b/test/algorithm/generate_clip_ids.cpp
new file mode 100644
index 0000000000..5b7f4afb26
--- /dev/null
+++ b/test/algorithm/generate_clip_ids.cpp
@@ -0,0 +1,427 @@
+#include <mbgl/test/util.hpp>
+
+#include <mbgl/algorithm/generate_clip_ids_impl.hpp>
+
+using namespace mbgl;
+
+struct Renderable {
+ ClipID clip;
+
+ bool operator==(const Renderable& rhs) const {
+ return clip == rhs.clip;
+ }
+};
+
+::std::ostream& operator<<(::std::ostream& os, const Renderable& rhs) {
+ return os << "ClipID(" << rhs.clip << ")";
+}
+
+namespace {
+
+// void print(const std::map<UnwrappedTileID, Renderable>& renderables) {
+// std::cout << " EXPECT_EQ(decltype(renderables)({" << std::endl;
+// for (auto& pair : renderables) {
+// std::cout << " { UnwrappedTileID{ " << int(pair.first.canonical.z) << ", "
+// << (int64_t(pair.first.canonical.x) +
+// pair.first.wrap * (1ll << pair.first.canonical.z))
+// << ", " << pair.first.canonical.y << " }, Renderable{ ClipID{ \""
+// << pair.second.clip.mask << "\", \"" << pair.second.clip.reference << "\" } } },"
+// << std::endl;
+// }
+// std::cout << " })," << std::endl;
+// std::cout << " renderables);" << std::endl;
+// }
+
+// void print(const std::map<UnwrappedTileID, ClipID>& stencils) {
+// std::cout << " EXPECT_EQ(decltype(stencils)({" << std::endl;
+// for (auto& pair : stencils) {
+// std::cout << " { UnwrappedTileID{ " << int(pair.first.canonical.z) << ", "
+// << (int64_t(pair.first.canonical.x) +
+// pair.first.wrap * (1ll << pair.first.canonical.z))
+// << ", " << pair.first.canonical.y << " }, ClipID{ \"" << pair.second.mask
+// << "\", \"" << pair.second.reference << "\" } }," << std::endl;
+// }
+// std::cout << " })," << std::endl;
+// std::cout << " stencils);" << std::endl;
+// }
+
+} // end namespace
+
+TEST(GenerateClipIDs, ParentAndFourChildren) {
+ std::map<UnwrappedTileID, Renderable> renderables{
+ { UnwrappedTileID{ 0, 0, 0 }, Renderable{ {} } },
+ // All four covering children
+ { UnwrappedTileID{ 1, 0, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, 0, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, 1, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, 1, 1 }, Renderable{ {} } },
+ };
+
+ algorithm::ClipIDGenerator generator;
+ generator.update(renderables);
+
+ EXPECT_EQ(decltype(renderables)({
+ { UnwrappedTileID{ 0, 0, 0 }, Renderable{ ClipID{ "00000111", "00000001" } } },
+ { UnwrappedTileID{ 1, 0, 0 }, Renderable{ ClipID{ "00000111", "00000010" } } },
+ { UnwrappedTileID{ 1, 0, 1 }, Renderable{ ClipID{ "00000111", "00000011" } } },
+ { UnwrappedTileID{ 1, 1, 0 }, Renderable{ ClipID{ "00000111", "00000100" } } },
+ { UnwrappedTileID{ 1, 1, 1 }, Renderable{ ClipID{ "00000111", "00000101" } } },
+ }),
+ renderables);
+
+ const auto stencils = generator.getStencils();
+ EXPECT_EQ(decltype(stencils)({
+ // 0/0/0 is missing because it is covered by children.
+ { UnwrappedTileID{ 1, 0, 0 }, ClipID{ "00000111", "00000010" } },
+ { UnwrappedTileID{ 1, 0, 1 }, ClipID{ "00000111", "00000011" } },
+ { UnwrappedTileID{ 1, 1, 0 }, ClipID{ "00000111", "00000100" } },
+ { UnwrappedTileID{ 1, 1, 1 }, ClipID{ "00000111", "00000101" } },
+ }),
+ stencils);
+}
+
+TEST(GenerateClipIDs, ParentAndFourChildrenNegative) {
+ std::map<UnwrappedTileID, Renderable> renderables{
+ { UnwrappedTileID{ 1, -2, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, -2, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, -1, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, -1, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 0, -1, 0 }, Renderable{ {} } },
+ };
+
+ algorithm::ClipIDGenerator generator;
+ generator.update(renderables);
+
+ EXPECT_EQ(decltype(renderables)({
+ { UnwrappedTileID{ 0, -1, 0 }, Renderable{ ClipID{ "00000111", "00000001" } } },
+ { UnwrappedTileID{ 1, -2, 0 }, Renderable{ ClipID{ "00000111", "00000010" } } },
+ { UnwrappedTileID{ 1, -2, 1 }, Renderable{ ClipID{ "00000111", "00000011" } } },
+ { UnwrappedTileID{ 1, -1, 0 }, Renderable{ ClipID{ "00000111", "00000100" } } },
+ { UnwrappedTileID{ 1, -1, 1 }, Renderable{ ClipID{ "00000111", "00000101" } } },
+ }),
+ renderables);
+
+ const auto stencils = generator.getStencils();
+ EXPECT_EQ(decltype(stencils)({
+ { UnwrappedTileID{ 1, -2, 0 }, ClipID{ "00000111", "00000010" } },
+ { UnwrappedTileID{ 1, -2, 1 }, ClipID{ "00000111", "00000011" } },
+ { UnwrappedTileID{ 1, -1, 0 }, ClipID{ "00000111", "00000100" } },
+ { UnwrappedTileID{ 1, -1, 1 }, ClipID{ "00000111", "00000101" } },
+ }),
+ stencils);
+}
+
+TEST(GenerateClipIDs, NegativeParentAndMissingLevel) {
+ std::map<UnwrappedTileID, Renderable> renderables{
+ { UnwrappedTileID{ 1, -1, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, -1, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, -2, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, -1, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, -2, 0 }, Renderable{ {} } },
+ };
+
+ algorithm::ClipIDGenerator generator;
+ generator.update(renderables);
+
+ EXPECT_EQ(decltype(renderables)({
+ { UnwrappedTileID{ 1, -1, 0 }, Renderable{ ClipID{ "00000111", "00000001" } } },
+ { UnwrappedTileID{ 2, -2, 0 }, Renderable{ ClipID{ "00000111", "00000010" } } },
+ { UnwrappedTileID{ 2, -2, 1 }, Renderable{ ClipID{ "00000111", "00000011" } } },
+ { UnwrappedTileID{ 2, -1, 0 }, Renderable{ ClipID{ "00000111", "00000100" } } },
+ { UnwrappedTileID{ 2, -1, 1 }, Renderable{ ClipID{ "00000111", "00000101" } } },
+ }),
+ renderables);
+
+ const auto stencils = generator.getStencils();
+ EXPECT_EQ(decltype(stencils)({
+ { UnwrappedTileID{ 2, -2, 0 }, ClipID{ "00000111", "00000010" } },
+ { UnwrappedTileID{ 2, -2, 1 }, ClipID{ "00000111", "00000011" } },
+ { UnwrappedTileID{ 2, -1, 0 }, ClipID{ "00000111", "00000100" } },
+ { UnwrappedTileID{ 2, -1, 1 }, ClipID{ "00000111", "00000101" } },
+ }),
+ stencils);
+}
+
+TEST(GenerateClipIDs, SevenOnSameLevel) {
+ std::map<UnwrappedTileID, Renderable> renderables{
+ // first column
+ { UnwrappedTileID{ 2, 0, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, 0, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, 0, 2 }, Renderable{ {} } },
+ // second column
+ { UnwrappedTileID{ 2, 1, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, 1, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, 1, 2 }, Renderable{ {} } },
+ // third column
+ { UnwrappedTileID{ 2, 2, 0 }, Renderable{ {} } },
+ };
+
+ algorithm::ClipIDGenerator generator;
+ generator.update(renderables);
+ EXPECT_EQ(decltype(renderables)({
+ { UnwrappedTileID{ 2, 0, 0 }, Renderable{ ClipID{ "00000111", "00000001" } } },
+ { UnwrappedTileID{ 2, 0, 1 }, Renderable{ ClipID{ "00000111", "00000010" } } },
+ { UnwrappedTileID{ 2, 0, 2 }, Renderable{ ClipID{ "00000111", "00000011" } } },
+ { UnwrappedTileID{ 2, 1, 0 }, Renderable{ ClipID{ "00000111", "00000100" } } },
+ { UnwrappedTileID{ 2, 1, 1 }, Renderable{ ClipID{ "00000111", "00000101" } } },
+ { UnwrappedTileID{ 2, 1, 2 }, Renderable{ ClipID{ "00000111", "00000110" } } },
+ { UnwrappedTileID{ 2, 2, 0 }, Renderable{ ClipID{ "00000111", "00000111" } } },
+ }),
+ renderables);
+
+ const auto stencils = generator.getStencils();
+ EXPECT_EQ(decltype(stencils)({
+ { UnwrappedTileID{ 2, 0, 0 }, ClipID{ "00000111", "00000001" } },
+ { UnwrappedTileID{ 2, 0, 1 }, ClipID{ "00000111", "00000010" } },
+ { UnwrappedTileID{ 2, 0, 2 }, ClipID{ "00000111", "00000011" } },
+ { UnwrappedTileID{ 2, 1, 0 }, ClipID{ "00000111", "00000100" } },
+ { UnwrappedTileID{ 2, 1, 1 }, ClipID{ "00000111", "00000101" } },
+ { UnwrappedTileID{ 2, 1, 2 }, ClipID{ "00000111", "00000110" } },
+ { UnwrappedTileID{ 2, 2, 0 }, ClipID{ "00000111", "00000111" } },
+ }),
+ stencils);
+}
+
+TEST(GenerateClipIDs, MultipleLevels) {
+ std::map<UnwrappedTileID, Renderable> renderables{
+ { UnwrappedTileID{ 2, 0, 0 }, Renderable{ {} } },
+ // begin subtiles of (2/0/0)
+ { UnwrappedTileID{ 3, 0, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 3, 0, 1 }, Renderable{ {} } },
+ // begin subtiles of (3/0/1)
+ { UnwrappedTileID{ 4, 0, 2 }, Renderable{ {} } },
+ { UnwrappedTileID{ 4, 1, 2 }, Renderable{ {} } },
+ { UnwrappedTileID{ 4, 0, 3 }, Renderable{ {} } },
+ { UnwrappedTileID{ 4, 1, 3 }, Renderable{ {} } },
+ // end subtiles of (3/0/1)
+ { UnwrappedTileID{ 3, 1, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 3, 1, 1 }, Renderable{ {} } },
+ // end subtiles of (2/0/0)
+ { UnwrappedTileID{ 2, 1, 0 }, Renderable{ {} } },
+ // begin subtiles of (2/1/0)
+ { UnwrappedTileID{ 3, 2, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 3, 2, 1 }, Renderable{ {} } },
+ // end subtiles of (2/1/0)
+ };
+
+ algorithm::ClipIDGenerator generator;
+ generator.update(renderables);
+ ASSERT_EQ(decltype(renderables)({
+ { UnwrappedTileID{ 2, 0, 0 }, Renderable{ ClipID{ "00001111", "00000001" } } },
+ { UnwrappedTileID{ 2, 1, 0 }, Renderable{ ClipID{ "00001111", "00000010" } } },
+ { UnwrappedTileID{ 3, 0, 0 }, Renderable{ ClipID{ "00001111", "00000011" } } },
+ { UnwrappedTileID{ 3, 0, 1 }, Renderable{ ClipID{ "00001111", "00000100" } } },
+ { UnwrappedTileID{ 3, 1, 0 }, Renderable{ ClipID{ "00001111", "00000101" } } },
+ { UnwrappedTileID{ 3, 1, 1 }, Renderable{ ClipID{ "00001111", "00000110" } } },
+ { UnwrappedTileID{ 3, 2, 0 }, Renderable{ ClipID{ "00001111", "00000111" } } },
+ { UnwrappedTileID{ 3, 2, 1 }, Renderable{ ClipID{ "00001111", "00001000" } } },
+ { UnwrappedTileID{ 4, 0, 2 }, Renderable{ ClipID{ "00001111", "00001001" } } },
+ { UnwrappedTileID{ 4, 0, 3 }, Renderable{ ClipID{ "00001111", "00001010" } } },
+ { UnwrappedTileID{ 4, 1, 2 }, Renderable{ ClipID{ "00001111", "00001011" } } },
+ { UnwrappedTileID{ 4, 1, 3 }, Renderable{ ClipID{ "00001111", "00001100" } } },
+ }),
+ renderables);
+
+ const auto stencils = generator.getStencils();
+ EXPECT_EQ(decltype(stencils)({
+ { UnwrappedTileID{ 2, 1, 0 }, ClipID{ "00001111", "00000010" } },
+ { UnwrappedTileID{ 3, 0, 0 }, ClipID{ "00001111", "00000011" } },
+ { UnwrappedTileID{ 3, 1, 0 }, ClipID{ "00001111", "00000101" } },
+ { UnwrappedTileID{ 3, 1, 1 }, ClipID{ "00001111", "00000110" } },
+ { UnwrappedTileID{ 3, 2, 0 }, ClipID{ "00001111", "00000111" } },
+ { UnwrappedTileID{ 3, 2, 1 }, ClipID{ "00001111", "00001000" } },
+ { UnwrappedTileID{ 4, 0, 2 }, ClipID{ "00001111", "00001001" } },
+ { UnwrappedTileID{ 4, 0, 3 }, ClipID{ "00001111", "00001010" } },
+ { UnwrappedTileID{ 4, 1, 2 }, ClipID{ "00001111", "00001011" } },
+ { UnwrappedTileID{ 4, 1, 3 }, ClipID{ "00001111", "00001100" } },
+ }),
+ stencils);
+}
+
+TEST(GenerateClipIDs, Bug206) {
+ std::map<UnwrappedTileID, Renderable> renderables{
+ { UnwrappedTileID{ 10, 162, 395 }, Renderable{ {} } },
+ { UnwrappedTileID{ 10, 162, 396 }, Renderable{ {} } },
+ { UnwrappedTileID{ 10, 163, 395 }, Renderable{ {} } },
+ // begin subtiles of (10/163/395)
+ { UnwrappedTileID{ 11, 326, 791 }, Renderable{ {} } },
+ { UnwrappedTileID{ 12, 654, 1582 }, Renderable{ {} } },
+ { UnwrappedTileID{ 12, 654, 1583 }, Renderable{ {} } },
+ { UnwrappedTileID{ 12, 655, 1582 }, Renderable{ {} } },
+ { UnwrappedTileID{ 12, 655, 1583 }, Renderable{ {} } },
+ // end subtiles of (10/163/395)
+ { UnwrappedTileID{ 10, 163, 396 }, Renderable{ {} } },
+ { UnwrappedTileID{ 10, 164, 395 }, Renderable{ {} } },
+ { UnwrappedTileID{ 10, 164, 396 }, Renderable{ {} } },
+ };
+
+ algorithm::ClipIDGenerator generator;
+ generator.update(renderables);
+ EXPECT_EQ(
+ decltype(renderables)({
+ { UnwrappedTileID{ 10, 162, 395 }, Renderable{ ClipID{ "00001111", "00000001" } } },
+ { UnwrappedTileID{ 10, 162, 396 }, Renderable{ ClipID{ "00001111", "00000010" } } },
+ { UnwrappedTileID{ 10, 163, 395 }, Renderable{ ClipID{ "00001111", "00000011" } } },
+ { UnwrappedTileID{ 10, 163, 396 }, Renderable{ ClipID{ "00001111", "00000100" } } },
+ { UnwrappedTileID{ 10, 164, 395 }, Renderable{ ClipID{ "00001111", "00000101" } } },
+ { UnwrappedTileID{ 10, 164, 396 }, Renderable{ ClipID{ "00001111", "00000110" } } },
+ { UnwrappedTileID{ 11, 326, 791 }, Renderable{ ClipID{ "00001111", "00000111" } } },
+ { UnwrappedTileID{ 12, 654, 1582 }, Renderable{ ClipID{ "00001111", "00001000" } } },
+ { UnwrappedTileID{ 12, 654, 1583 }, Renderable{ ClipID{ "00001111", "00001001" } } },
+ { UnwrappedTileID{ 12, 655, 1582 }, Renderable{ ClipID{ "00001111", "00001010" } } },
+ { UnwrappedTileID{ 12, 655, 1583 }, Renderable{ ClipID{ "00001111", "00001011" } } },
+ }),
+ renderables);
+
+ const auto stencils = generator.getStencils();
+ EXPECT_EQ(decltype(stencils)({
+ { UnwrappedTileID{ 10, 162, 395 }, ClipID{ "00001111", "00000001" } },
+ { UnwrappedTileID{ 10, 162, 396 }, ClipID{ "00001111", "00000010" } },
+ { UnwrappedTileID{ 10, 163, 395 }, ClipID{ "00001111", "00000011" } },
+ { UnwrappedTileID{ 10, 163, 396 }, ClipID{ "00001111", "00000100" } },
+ { UnwrappedTileID{ 10, 164, 395 }, ClipID{ "00001111", "00000101" } },
+ { UnwrappedTileID{ 10, 164, 396 }, ClipID{ "00001111", "00000110" } },
+ { UnwrappedTileID{ 11, 326, 791 }, ClipID{ "00001111", "00000111" } },
+ { UnwrappedTileID{ 12, 654, 1582 }, ClipID{ "00001111", "00001000" } },
+ { UnwrappedTileID{ 12, 654, 1583 }, ClipID{ "00001111", "00001001" } },
+ { UnwrappedTileID{ 12, 655, 1582 }, ClipID{ "00001111", "00001010" } },
+ { UnwrappedTileID{ 12, 655, 1583 }, ClipID{ "00001111", "00001011" } },
+ }),
+ stencils);
+}
+
+TEST(GenerateClipIDs, MultipleSources) {
+ std::map<UnwrappedTileID, Renderable> renderables1{
+ { UnwrappedTileID{ 0, 0, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, 1, 1 }, Renderable{ {} } },
+ // Differing children
+ { UnwrappedTileID{ 2, 2, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, 2, 2 }, Renderable{ {} } },
+ };
+ std::map<UnwrappedTileID, Renderable> renderables2{
+ { UnwrappedTileID{ 0, 0, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, 1, 1 }, Renderable{ {} } },
+ // Differing children
+ { UnwrappedTileID{ 2, 1, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, 2, 2 }, Renderable{ {} } },
+ };
+ std::map<UnwrappedTileID, Renderable> renderables3{
+ { UnwrappedTileID{ 1, 0, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, 0, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, 1, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 1, 1, 1 }, Renderable{ {} } },
+ // Differing children
+ { UnwrappedTileID{ 2, 1, 1 }, Renderable{ {} } },
+ };
+
+ algorithm::ClipIDGenerator generator;
+ generator.update(renderables1);
+ generator.update(renderables2);
+ generator.update(renderables3);
+ EXPECT_EQ(decltype(renderables1)({
+ { UnwrappedTileID{ 0, 0, 0 }, Renderable{ ClipID{ "00000111", "00000001" } } },
+ { UnwrappedTileID{ 1, 1, 1 }, Renderable{ ClipID{ "00000111", "00000010" } } },
+ { UnwrappedTileID{ 2, 2, 1 }, Renderable{ ClipID{ "00000111", "00000011" } } },
+ { UnwrappedTileID{ 2, 2, 2 }, Renderable{ ClipID{ "00000111", "00000100" } } },
+ }),
+ renderables1);
+ EXPECT_EQ(decltype(renderables2)({
+ { UnwrappedTileID{ 0, 0, 0 }, Renderable{ ClipID{ "00011000", "00001000" } } },
+ { UnwrappedTileID{ 1, 1, 1 }, Renderable{ ClipID{ "00011111", "00000010" } } },
+ { UnwrappedTileID{ 2, 1, 1 }, Renderable{ ClipID{ "00011000", "00010000" } } },
+ { UnwrappedTileID{ 2, 2, 2 }, Renderable{ ClipID{ "00011111", "00000100" } } },
+ }),
+ renderables2);
+ EXPECT_EQ(decltype(renderables3)({
+ { UnwrappedTileID{ 1, 0, 0 }, Renderable{ ClipID{ "11100000", "00100000" } } },
+ { UnwrappedTileID{ 1, 0, 1 }, Renderable{ ClipID{ "11100000", "01000000" } } },
+ { UnwrappedTileID{ 1, 1, 0 }, Renderable{ ClipID{ "11100000", "01100000" } } },
+ { UnwrappedTileID{ 1, 1, 1 }, Renderable{ ClipID{ "11100000", "10000000" } } },
+ { UnwrappedTileID{ 2, 1, 1 }, Renderable{ ClipID{ "11111000", "00010000" } } },
+ }),
+ renderables3);
+
+ const auto stencils = generator.getStencils();
+ EXPECT_EQ(decltype(stencils)({
+ { UnwrappedTileID{ 1, 0, 0 }, ClipID{ "11111111", "00101001" } },
+ { UnwrappedTileID{ 1, 0, 1 }, ClipID{ "11111111", "01001001" } },
+ { UnwrappedTileID{ 1, 1, 0 }, ClipID{ "11111111", "01101001" } },
+ { UnwrappedTileID{ 1, 1, 1 }, ClipID{ "11111111", "10000010" } },
+ { UnwrappedTileID{ 2, 1, 1 }, ClipID{ "11111111", "00010001" } },
+ { UnwrappedTileID{ 2, 2, 1 }, ClipID{ "11111111", "01101011" } },
+ { UnwrappedTileID{ 2, 2, 2 }, ClipID{ "11111111", "10000100" } },
+ }),
+ stencils);
+}
+
+TEST(GenerateClipIDs, DuplicateIDs) {
+ std::map<UnwrappedTileID, Renderable> renderables1{
+ { UnwrappedTileID{ 2, 0, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, 0, 1 }, Renderable{ {} } },
+ };
+ std::map<UnwrappedTileID, Renderable> renderables2{
+ { UnwrappedTileID{ 2, 0, 0 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, 0, 1 }, Renderable{ {} } },
+ { UnwrappedTileID{ 2, 0, 1 }, Renderable{ {} } },
+ };
+
+ algorithm::ClipIDGenerator generator;
+ generator.update(renderables1);
+ generator.update(renderables2);
+ EXPECT_EQ(decltype(renderables1)({
+ { UnwrappedTileID{ 2, 0, 0 }, Renderable{ ClipID{ "00000011", "00000001" } } },
+ { UnwrappedTileID{ 2, 0, 1 }, Renderable{ ClipID{ "00000011", "00000010" } } },
+ }),
+ renderables1);
+ EXPECT_EQ(decltype(renderables2)({
+ { UnwrappedTileID{ 2, 0, 0 }, Renderable{ ClipID{ "00000011", "00000001" } } },
+ { UnwrappedTileID{ 2, 0, 1 }, Renderable{ ClipID{ "00000011", "00000010" } } },
+ }),
+ renderables2);
+
+ const auto stencils = generator.getStencils();
+ EXPECT_EQ(decltype(stencils)({
+ { UnwrappedTileID{ 2, 0, 0 }, ClipID{ "00000011", "00000001" } },
+ { UnwrappedTileID{ 2, 0, 1 }, ClipID{ "00000011", "00000010" } },
+ }),
+ stencils);
+}
+
+TEST(GenerateClipIDs, SecondSourceHasParentOfFirstSource) {
+ std::map<UnwrappedTileID, Renderable> renderables1{
+ { UnwrappedTileID{ 1, 0, 0 }, Renderable{ {} } },
+ };
+ std::map<UnwrappedTileID, Renderable> renderables2{
+ { UnwrappedTileID{ 0, 0, 0 }, Renderable{ {} } },
+ // Same as in renderables1, but has a parent that it knocks out.
+ { UnwrappedTileID{ 1, 0, 0 }, Renderable{ {} } },
+ };
+ std::map<UnwrappedTileID, Renderable> renderables3{
+ { UnwrappedTileID{ 0, 0, 0 }, Renderable{ {} } },
+ };
+
+ algorithm::ClipIDGenerator generator;
+ generator.update(renderables1);
+ generator.update(renderables2);
+ generator.update(renderables3);
+ EXPECT_EQ(decltype(renderables1)({
+ { UnwrappedTileID{ 1, 0, 0 }, Renderable{ ClipID{ "00000001", "00000001" } } },
+ }),
+ renderables1);
+ EXPECT_EQ(decltype(renderables2)({
+ { UnwrappedTileID{ 0, 0, 0 }, Renderable{ ClipID{ "00000010", "00000010" } } },
+ { UnwrappedTileID{ 1, 0, 0 }, Renderable{ ClipID{ "00000011", "00000001" } } },
+ }),
+ renderables2);
+ EXPECT_EQ(decltype(renderables3)({
+ { UnwrappedTileID{ 0, 0, 0 }, Renderable{ ClipID{ "00000100", "00000100" } } },
+ }),
+ renderables3);
+
+ const auto stencils = generator.getStencils();
+ EXPECT_EQ(decltype(stencils)({
+ { UnwrappedTileID{ 0, 0, 0 }, ClipID{ "00000110", "00000110" } },
+ { UnwrappedTileID{ 1, 0, 0 }, ClipID{ "00000111", "00000101" } },
+ }),
+ stencils);
+}
diff --git a/test/test.gypi b/test/test.gypi
index 4635c888c3..3a4f965595 100644
--- a/test/test.gypi
+++ b/test/test.gypi
@@ -35,6 +35,7 @@
'util/work_queue.cpp',
'algorithm/covered_by_children.cpp',
+ 'algorithm/generate_clip_ids.cpp',
'api/annotations.cpp',
'api/api_misuse.cpp',
View Lorry Controller Status