diff options
| -rw-r--r-- | src/mbgl/algorithm/generate_clip_ids.cpp | 81 | ||||
| -rw-r--r-- | src/mbgl/algorithm/generate_clip_ids.hpp | 38 | ||||
| -rw-r--r-- | src/mbgl/algorithm/generate_clip_ids_impl.hpp | 81 | ||||
| -rw-r--r-- | src/mbgl/util/clip_id.cpp | 4 | ||||
| -rw-r--r-- | src/mbgl/util/clip_id.hpp | 3 | ||||
| -rw-r--r-- | test/algorithm/generate_clip_ids.cpp | 427 | ||||
| -rw-r--r-- | test/test.gypi | 1 |
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', |