From 5b640fb446693c42086489cdaa3066eb172609e6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Konstantin=20K=C3=A4fer?= Date: Tue, 8 Mar 2016 14:00:45 +0100 Subject: [core] add algorithm for generating clip IDs based on the new TileID classes --- src/mbgl/algorithm/generate_clip_ids.cpp | 81 +++++++++++++++++++++++++++ src/mbgl/algorithm/generate_clip_ids.hpp | 38 +++++++++++++ src/mbgl/algorithm/generate_clip_ids_impl.hpp | 81 +++++++++++++++++++++++++++ 3 files changed, 200 insertions(+) create mode 100644 src/mbgl/algorithm/generate_clip_ids.cpp create mode 100644 src/mbgl/algorithm/generate_clip_ids.hpp create mode 100644 src/mbgl/algorithm/generate_clip_ids_impl.hpp (limited to 'src/mbgl/algorithm') 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 +#include + +#include +#include + +#include +#include +#include +#include +#include +#include +#include + +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&); + +std::map ClipIDGenerator::getStencils() const { + std::map 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(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 +#include + +#include +#include +#include + +namespace mbgl { +namespace algorithm { + +class ClipIDGenerator { +private: + struct Leaf { + Leaf(ClipID&); + void add(const CanonicalTileID &p); + bool operator==(const Leaf &other) const; + + std::set children; + ClipID& clip; + }; + + uint8_t bit_offset = 0; + std::multimap pool; + +public: + template + void update(Renderables& renderables); + + std::map 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 +#include +#include + +namespace mbgl { +namespace algorithm { + +template +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(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 -- cgit v1.2.1