diff options
Diffstat (limited to 'src/mbgl/util/clip_ids.cpp')
-rw-r--r-- | src/mbgl/util/clip_ids.cpp | 96 |
1 files changed, 96 insertions, 0 deletions
diff --git a/src/mbgl/util/clip_ids.cpp b/src/mbgl/util/clip_ids.cpp new file mode 100644 index 0000000000..9c391c38ad --- /dev/null +++ b/src/mbgl/util/clip_ids.cpp @@ -0,0 +1,96 @@ +#include <mbgl/util/clip_ids.hpp> +#include <mbgl/map/tile.hpp> + +#include <mbgl/util/math.hpp> + +#include <list> +#include <vector> +#include <bitset> +#include <cassert> +#include <iostream> +#include <algorithm> + +namespace mbgl { + +ClipIDGenerator::Leaf::Leaf(Tile &tile_) : tile(tile_) {} + +void ClipIDGenerator::Leaf::add(const Tile::ID &p) { + if (p.isChildOf(tile.id)) { + // Ensure that no already present child is a parent of the new p. + for (const Tile::ID &child : children) { + if (p.isChildOf(child)) + return; + } + children.push_front(p); + } +} + +bool ClipIDGenerator::Leaf::operator==(const Leaf &other) const { + return tile.id == other.tile.id && children == other.children; +} + +bool ClipIDGenerator::reuseExisting(Leaf &leaf) { + for (const std::vector<Leaf> &pool : pools) { + auto existing = std::find(pool.begin(), pool.end(), leaf); + if (existing != pool.end()) { + leaf.tile.clip = existing->tile.clip; + return true; + } + } + return false; +} + +void ClipIDGenerator::update(std::forward_list<Tile *> tiles) { + Pool pool; + + tiles.sort([](const Tile *a, const Tile *b) { + return a->id < b->id; + }); + + const auto end = tiles.end(); + for (auto it = tiles.begin(); it != end; it++) { + if (!*it) { + // Handle null pointers. + continue; + } + + Tile &tile = **it; + Leaf clip { tile }; + + // 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. + for (auto child_it = std::next(it); child_it != end; child_it++) { + clip.add((*child_it)->id); + } + clip.children.sort(); + + // Loop through all existing pools and try to find a matching ClipID. + if (!reuseExisting(clip)) { + // We haven't found an existing clip ID + pool.push_back(std::move(clip)); + } + } + + if (pool.size()) { + const uint32_t bit_count = util::ceil_log2(pool.size() + 1); + const std::bitset<8> mask = uint64_t(((1 << 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 (Leaf &leaf : pool) { + leaf.tile.clip.mask = mask; + leaf.tile.clip.reference = count++ << bit_offset; + } + + bit_offset += bit_count; + pools.push_front(std::move(pool)); + } + + if (bit_offset > 8) { + fprintf(stderr, "stencil mask overflow\n"); + } +} + +} |