diff options
author | Konstantin Käfer <mail@kkaefer.com> | 2019-04-16 17:44:34 +0200 |
---|---|---|
committer | Konstantin Käfer <mail@kkaefer.com> | 2019-04-29 11:37:39 +0200 |
commit | 08163713e239ab7756dc9bbe9b6e2c4986f168d3 (patch) | |
tree | 391c7da104dbe3d12fc0152cddaa7dfc8abbea74 /src/mbgl/algorithm | |
parent | 8f5e1ba20f7a356c5bdabb7cb9d0d10bb4d73e10 (diff) | |
download | qtlocation-mapboxgl-08163713e239ab7756dc9bbe9b6e2c4986f168d3.tar.gz |
[core] change approach to stencil clipping to (almost) match JS
Diffstat (limited to 'src/mbgl/algorithm')
-rw-r--r-- | src/mbgl/algorithm/covered_by_children.hpp | 39 | ||||
-rw-r--r-- | src/mbgl/algorithm/generate_clip_ids.cpp | 76 | ||||
-rw-r--r-- | src/mbgl/algorithm/generate_clip_ids.hpp | 36 | ||||
-rw-r--r-- | src/mbgl/algorithm/generate_clip_ids_impl.hpp | 91 |
4 files changed, 0 insertions, 242 deletions
diff --git a/src/mbgl/algorithm/covered_by_children.hpp b/src/mbgl/algorithm/covered_by_children.hpp deleted file mode 100644 index fe5af3f3db..0000000000 --- a/src/mbgl/algorithm/covered_by_children.hpp +++ /dev/null @@ -1,39 +0,0 @@ -#pragma once - -#include <mbgl/tile/tile_id.hpp> - -namespace mbgl { -namespace algorithm { - -template <typename Iterator> -bool coveredByChildren(const UnwrappedTileID& id, Iterator it, const Iterator& end) { - for (const auto& child : id.children()) { - it = std::lower_bound(it, end, child, [](const auto& a, const auto& b) { return std::get<0>(a) < b; }); - - // Child is not present, neither its grandchildren. - if (it == end) { - return false; - } - - // Child is not present, but its grandchildren are. - if (std::get<0>(*it) != child) { - // This child is not covered by its grandchildren. - if (!coveredByChildren(child, it, end)) { - return false; - } - } - } - - // We looked at all four children (recursively) and verified that they're covered. - return true; -} - -template <typename Container> -bool coveredByChildren(const UnwrappedTileID& id, const Container& container) { - return coveredByChildren( - id, container.upper_bound(id), - container.lower_bound(UnwrappedTileID{ static_cast<int16_t>(id.wrap + 1), { 0, 0, 0 } })); -} - -} // namespace algorithm -} // namespace mbgl diff --git a/src/mbgl/algorithm/generate_clip_ids.cpp b/src/mbgl/algorithm/generate_clip_ids.cpp deleted file mode 100644 index aefa55b929..0000000000 --- a/src/mbgl/algorithm/generate_clip_ids.cpp +++ /dev/null @@ -1,76 +0,0 @@ -#include <mbgl/algorithm/generate_clip_ids_impl.hpp> -#include <mbgl/algorithm/covered_by_children.hpp> - -#include <mbgl/util/std.hpp> - -#include <list> -#include <vector> -#include <bitset> -#include <cassert> -#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; -} - -std::map<UnwrappedTileID, ClipID> ClipIDGenerator::getClipIDs() const { - std::map<UnwrappedTileID, ClipID> clipIDs; - - // Merge everything. - for (auto& pair : pool) { - auto& id = pair.first; - auto& leaf = pair.second; - auto res = clipIDs.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 = clipIDs.begin(); it != clipIDs.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 != clipIDs.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(clipIDs, [&](const auto& stencil) { - return algorithm::coveredByChildren(stencil.first, clipIDs); - }); - - return clipIDs; -} - -} // namespace algorithm -} // namespace mbgl diff --git a/src/mbgl/algorithm/generate_clip_ids.hpp b/src/mbgl/algorithm/generate_clip_ids.hpp deleted file mode 100644 index 6950433578..0000000000 --- a/src/mbgl/algorithm/generate_clip_ids.hpp +++ /dev/null @@ -1,36 +0,0 @@ -#pragma once - -#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: - // The given vector must be sorted by id. - template <typename Renderable> - void update(std::vector<std::reference_wrapper<Renderable>> sortedRenderables); - - std::map<UnwrappedTileID, ClipID> getClipIDs() const; -}; - -} // namespace algorithm -} // namespace mbgl diff --git a/src/mbgl/algorithm/generate_clip_ids_impl.hpp b/src/mbgl/algorithm/generate_clip_ids_impl.hpp deleted file mode 100644 index a4af9c8cbb..0000000000 --- a/src/mbgl/algorithm/generate_clip_ids_impl.hpp +++ /dev/null @@ -1,91 +0,0 @@ -#pragma once - -#include <mbgl/algorithm/generate_clip_ids.hpp> -#include <mbgl/math/log2.hpp> -#include <mbgl/util/logging.hpp> - -namespace mbgl { -namespace algorithm { - -template <typename Renderable> -void ClipIDGenerator::update(std::vector<std::reference_wrapper<Renderable>> renderables) { - std::size_t size = 0; - assert(std::is_sorted(renderables.begin(), renderables.end(), - [](const Renderable& a, const Renderable& b) { return a.id < b.id; })); - - const auto end = renderables.end(); - for (auto it = renderables.begin(); it != end; ++it) { - auto& renderable = it->get(); - if (!renderable.used || !renderable.needsClipping) { - continue; - } - - 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>(renderable.id.wrap + 1), { 0, 0, 0 } }, - [](auto& a, auto& b) { return a.get().id < b; }); - for (; child_it != children_end; ++child_it) { - auto& childTileID = child_it->get().id; - if (childTileID.isChildOf(it->get().id)) { - leaf.add(childTileID.canonical); - } - } - - // Find a leaf with matching children. - for (auto its = pool.equal_range(renderable.id); 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(renderable.id, 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& it : renderables) { - auto& renderable = it.get(); - if (!renderable.used || !renderable.needsClipping) { - continue; - } - 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; - } - - // Prevent this warning from firing on every frame, - // which can be expensive in some platforms. - static bool warned = false; - - if (!warned && bit_offset > 8) { - Log::Error(Event::OpenGL, "stencil mask overflow"); - warned = true; - } -} - -} // namespace algorithm -} // namespace mbgl |