summaryrefslogtreecommitdiff
path: root/src/mbgl
diff options
context:
space:
mode:
Diffstat (limited to 'src/mbgl')
-rw-r--r--src/mbgl/map/tile_id.hpp4
-rw-r--r--src/mbgl/util/clip_id.cpp111
-rw-r--r--src/mbgl/util/clip_id.hpp20
3 files changed, 99 insertions, 36 deletions
diff --git a/src/mbgl/map/tile_id.hpp b/src/mbgl/map/tile_id.hpp
index dddbce3bb7..3ecc5c6cef 100644
--- a/src/mbgl/map/tile_id.hpp
+++ b/src/mbgl/map/tile_id.hpp
@@ -6,6 +6,7 @@
#include <string>
#include <functional>
#include <forward_list>
+#include <limits>
namespace mbgl {
@@ -48,7 +49,8 @@ public:
TileID parent(int8_t z, int8_t sourceMaxZoom) const;
TileID normalized() const;
- std::forward_list<TileID> children(int8_t sourceMaxZoom) const;
+ std::forward_list<TileID>
+ children(int8_t sourceMaxZoom = std::numeric_limits<int8_t>::max()) const;
bool isChildOf(const TileID&) const;
operator std::string() const;
diff --git a/src/mbgl/util/clip_id.cpp b/src/mbgl/util/clip_id.cpp
index b89315d97b..8274be338d 100644
--- a/src/mbgl/util/clip_id.cpp
+++ b/src/mbgl/util/clip_id.cpp
@@ -2,6 +2,7 @@
#include <mbgl/platform/log.hpp>
#include <mbgl/util/math.hpp>
+#include <mbgl/util/std.hpp>
#include <mbgl/map/tile.hpp>
#include <list>
@@ -10,13 +11,14 @@
#include <cassert>
#include <iostream>
#include <algorithm>
+#include <iterator>
namespace mbgl {
-ClipIDGenerator::Leaf::Leaf(Tile &tile_) : tile(tile_) {}
+ClipIDGenerator::Leaf::Leaf(TileID id_, ClipID& clip_) : id(id_), clip(clip_) {}
void ClipIDGenerator::Leaf::add(const TileID &p) {
- if (p.isChildOf(tile.id)) {
+ if (p.isChildOf(id)) {
// Ensure that no already present child is a parent of the new p.
for (const auto& child : children) {
if (p.isChildOf(child))
@@ -27,27 +29,16 @@ void ClipIDGenerator::Leaf::add(const TileID &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 auto& 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;
+ return id == other.id && children == other.children;
}
void ClipIDGenerator::update(std::forward_list<Tile *> tiles) {
- Pool pool;
-
tiles.sort([](const Tile *a, const Tile *b) {
return a->id < b->id;
});
+ std::size_t size = 0;
+
const auto end = tiles.end();
for (auto it = tiles.begin(); it != end; it++) {
if (!*it) {
@@ -56,37 +47,49 @@ void ClipIDGenerator::update(std::forward_list<Tile *> tiles) {
}
Tile &tile = **it;
- Leaf clip { tile };
+ // Use the actual zoom level for computing the clipping mask.
+ Leaf leaf{ TileID{ tile.id.sourceZ, tile.id.x, tile.id.y, tile.id.sourceZ }, tile.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.
for (auto child_it = std::next(it); child_it != end; child_it++) {
- clip.add((*child_it)->id);
+ // Use the actual zoom level for computing the clipping mask.
+ const auto& childID = (*child_it)->id;
+ leaf.add(TileID { childID.sourceZ, childID.x, childID.y, childID.sourceZ });
}
- clip.children.sort();
+ leaf.children.sort();
// Loop through all existing pools and try to find a matching ClipID.
- if (!reuseExisting(clip)) {
+ auto existing = std::find(pool.begin(), pool.end(), leaf);
+ if (existing != pool.end()) {
+ leaf.clip = existing->clip;
+ } else {
// We haven't found an existing clip ID
- pool.push_back(std::move(clip));
+ leaf.clip = {};
+ size++;
}
+
+ pool.emplace_back(std::move(leaf));
}
- if (!pool.empty()) {
- const uint32_t bit_count = util::ceil_log2(pool.size() + 1);
+ 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& leaf : pool) {
- leaf.tile.clip.mask = mask;
- leaf.tile.clip.reference = uint32_t(count++) << bit_offset;
+ for (auto& tile : tiles) {
+ tile->clip.mask |= mask;
+
+ // Assign only to clip IDs that have no value yet.
+ if (tile->clip.reference.none()) {
+ tile->clip.reference = uint32_t(count++) << bit_offset;
+ }
}
bit_offset += bit_count;
- pools.push_front(std::move(pool));
}
if (bit_offset > 8) {
@@ -94,4 +97,58 @@ void ClipIDGenerator::update(std::forward_list<Tile *> tiles) {
}
}
+template <typename Container>
+bool coveredByChildren(const TileID& id, const Container& container) {
+ for (const auto& child : id.children()) {
+ const auto lower = container.lower_bound(child);
+ if (lower == container.end() ||
+ (lower->first != child && !coveredByChildren(child, container))) {
+ return false;
+ }
+ }
+
+ // We looked at all four immediate children and verified that they're covered.
+ return true;
+}
+
+std::map<TileID, ClipID> ClipIDGenerator::getStencils() const {
+ std::map<TileID, ClipID> stencils;
+
+ // Merge everything.
+ for (auto& leaf : pool) {
+ auto res = stencils.emplace(leaf.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<std::map<TileID, ClipID>::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 coveredByChildren(stencil.first, stencils);
+ });
+
+ return stencils;
+}
+
} // namespace mbgl
diff --git a/src/mbgl/util/clip_id.hpp b/src/mbgl/util/clip_id.hpp
index 71a07708c9..2c128d2643 100644
--- a/src/mbgl/util/clip_id.hpp
+++ b/src/mbgl/util/clip_id.hpp
@@ -14,7 +14,6 @@
namespace mbgl {
class Tile;
-class TileID;
struct ClipID {
inline ClipID() {}
@@ -26,28 +25,33 @@ struct ClipID {
inline bool operator==(const ClipID &other) const {
return mask == other.mask && reference == other.reference;
}
+
+ inline ClipID& operator|=(const ClipID &other) {
+ mask |= other.mask;
+ reference |= other.reference;
+ return *this;
+ }
};
class ClipIDGenerator {
private:
struct Leaf {
- Leaf(Tile &tile);
+ Leaf(TileID, ClipID&);
void add(const TileID &p);
bool operator==(const Leaf &other) const;
- Tile &tile;
+ const TileID id;
std::forward_list<TileID> children;
+ ClipID& clip;
};
- typedef std::vector<Leaf> Pool;
- std::forward_list<Pool> pools;
uint8_t bit_offset = 0;
-
-private:
- bool reuseExisting(Leaf &leaf);
+ std::vector<Leaf> pool;
public:
void update(std::forward_list<Tile *> tiles);
+
+ std::map<TileID, ClipID> getStencils() const;
};
View Lorry Controller Status