diff options
author | Konstantin Käfer <mail@kkaefer.com> | 2016-03-08 14:00:45 +0100 |
---|---|---|
committer | Konstantin Käfer <mail@kkaefer.com> | 2016-05-10 14:50:56 +0200 |
commit | 5b640fb446693c42086489cdaa3066eb172609e6 (patch) | |
tree | 8ac05980dbaa72c3f46a6e1990c38101e4f9433f /src/mbgl/algorithm | |
parent | ecc8e018faff02e8f0bb2a6c11db361f454c555e (diff) | |
download | qtlocation-mapboxgl-5b640fb446693c42086489cdaa3066eb172609e6.tar.gz |
[core] add algorithm for generating clip IDs based on the new TileID classes
Diffstat (limited to 'src/mbgl/algorithm')
-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 |
3 files changed, 200 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 |