From 4735845a6ee4baad9306b8d5150b093fccdd11a2 Mon Sep 17 00:00:00 2001 From: Mikhail Pozdnyakov Date: Tue, 14 Jan 2020 20:59:22 +0200 Subject: [core] Consider symbol bucket leader id in cross-tile symbol indexing Only buckets with the same leader id participate in `TileLayerIndex::findMatches()` in order to improve its performace. `TileLayerIndex` constness is fixed. --- src/mbgl/text/cross_tile_symbol_index.cpp | 47 ++++++++++++++++++++----------- src/mbgl/text/cross_tile_symbol_index.hpp | 12 +++++--- 2 files changed, 38 insertions(+), 21 deletions(-) diff --git a/src/mbgl/text/cross_tile_symbol_index.cpp b/src/mbgl/text/cross_tile_symbol_index.cpp index 55ab2cc3c5..d8bd0292ec 100644 --- a/src/mbgl/text/cross_tile_symbol_index.cpp +++ b/src/mbgl/text/cross_tile_symbol_index.cpp @@ -6,15 +6,19 @@ namespace mbgl { - -TileLayerIndex::TileLayerIndex(OverscaledTileID coord_, std::vector& symbolInstances, uint32_t bucketInstanceId_) - : coord(coord_), bucketInstanceId(bucketInstanceId_) { - for (SymbolInstance& symbolInstance : symbolInstances) { - indexedSymbolInstances[symbolInstance.key].emplace_back(symbolInstance.crossTileID, getScaledCoordinates(symbolInstance, coord)); - } +TileLayerIndex::TileLayerIndex(OverscaledTileID coord_, + std::vector& symbolInstances, + uint32_t bucketInstanceId_, + std::string bucketLeaderId_) + : coord(coord_), bucketInstanceId(bucketInstanceId_), bucketLeaderId(std::move(bucketLeaderId_)) { + for (SymbolInstance& symbolInstance : symbolInstances) { + indexedSymbolInstances[symbolInstance.key].emplace_back(symbolInstance.crossTileID, + getScaledCoordinates(symbolInstance, coord)); } +} -Point TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstance, const OverscaledTileID& childTileCoord) { +Point TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstance, + const OverscaledTileID& childTileCoord) const { // Round anchor positions to roughly 4 pixel grid const double roundingFactor = 512.0 / util::EXTENT / 2.0; const double scale = roundingFactor / std::pow(2, childTileCoord.canonical.z - coord.canonical.z); @@ -24,9 +28,14 @@ Point TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstan }; } -void TileLayerIndex::findMatches(std::vector& symbolInstances, const OverscaledTileID& newCoord, std::set& zoomCrossTileIDs) { +void TileLayerIndex::findMatches(SymbolBucket& bucket, + const OverscaledTileID& newCoord, + std::set& zoomCrossTileIDs) const { + auto& symbolInstances = bucket.symbolInstances; float tolerance = coord.canonical.z < newCoord.canonical.z ? 1 : std::pow(2, coord.canonical.z - newCoord.canonical.z); + if (bucket.bucketLeaderID != bucketLeaderId) return; + for (auto& symbolInstance : symbolInstances) { if (symbolInstance.crossTileID) { // already has a match, skip @@ -41,7 +50,7 @@ void TileLayerIndex::findMatches(std::vector& symbolInstances, c auto scaledSymbolCoord = getScaledCoordinates(symbolInstance, newCoord); - for (IndexedSymbolInstance& thisTileSymbol: it->second) { + for (const IndexedSymbolInstance& thisTileSymbol : it->second) { // Return any symbol with the same keys whose coordinates are within 1 // grid unit. (with a 4px grid, this covers a 12px by 12px area) if (std::abs(thisTileSymbol.coord.x - scaledSymbolCoord.x) <= tolerance && @@ -87,7 +96,7 @@ void CrossTileSymbolLayerIndex::handleWrapJump(float newLng) { } bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, SymbolBucket& bucket, uint32_t& maxCrossTileID) { - const auto& thisZoomIndexes = indexes[tileID.overscaledZ]; + auto& thisZoomIndexes = indexes[tileID.overscaledZ]; auto previousIndex = thisZoomIndexes.find(tileID); if (previousIndex != thisZoomIndexes.end()) { if (previousIndex->second.bucketInstanceId == bucket.bucketInstanceId) { @@ -105,20 +114,22 @@ bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, Symbol symbolInstance.crossTileID = 0; } + auto& thisZoomUsedCrossTileIDs = usedCrossTileIDs[tileID.overscaledZ]; + for (auto& it : indexes) { auto zoom = it.first; - auto zoomIndexes = it.second; + const auto& zoomIndexes = it.second; if (zoom > tileID.overscaledZ) { for (auto& childIndex : zoomIndexes) { if (childIndex.second.coord.isChildOf(tileID)) { - childIndex.second.findMatches(bucket.symbolInstances, tileID, usedCrossTileIDs[tileID.overscaledZ]); + childIndex.second.findMatches(bucket, tileID, thisZoomUsedCrossTileIDs); } } } else { auto parentTileID = tileID.scaledTo(zoom); auto parentIndex = zoomIndexes.find(parentTileID); if (parentIndex != zoomIndexes.end()) { - parentIndex->second.findMatches(bucket.symbolInstances, tileID, usedCrossTileIDs[tileID.overscaledZ]); + parentIndex->second.findMatches(bucket, tileID, thisZoomUsedCrossTileIDs); } } } @@ -127,13 +138,15 @@ bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, Symbol if (!symbolInstance.crossTileID) { // symbol did not match any known symbol, assign a new id symbolInstance.crossTileID = ++maxCrossTileID; - usedCrossTileIDs[tileID.overscaledZ].insert(symbolInstance.crossTileID); + thisZoomUsedCrossTileIDs.insert(symbolInstance.crossTileID); } } - - indexes[tileID.overscaledZ].erase(tileID); - indexes[tileID.overscaledZ].emplace(tileID, TileLayerIndex(tileID, bucket.symbolInstances, bucket.bucketInstanceId)); + thisZoomIndexes.erase(tileID); + thisZoomIndexes.emplace( + std::piecewise_construct, + std::forward_as_tuple(tileID), + std::forward_as_tuple(tileID, bucket.symbolInstances, bucket.bucketInstanceId, bucket.bucketLeaderID)); return true; } diff --git a/src/mbgl/text/cross_tile_symbol_index.hpp b/src/mbgl/text/cross_tile_symbol_index.hpp index 4e32698b3e..ddcdb814c6 100644 --- a/src/mbgl/text/cross_tile_symbol_index.hpp +++ b/src/mbgl/text/cross_tile_symbol_index.hpp @@ -31,13 +31,17 @@ public: class TileLayerIndex { public: - TileLayerIndex(OverscaledTileID coord, std::vector&, uint32_t bucketInstanceId); + TileLayerIndex(OverscaledTileID coord, + std::vector&, + uint32_t bucketInstanceId, + std::string bucketLeaderId); + + Point getScaledCoordinates(SymbolInstance&, const OverscaledTileID&) const; + void findMatches(SymbolBucket&, const OverscaledTileID&, std::set&) const; - Point getScaledCoordinates(SymbolInstance&, const OverscaledTileID&); - void findMatches(std::vector&, const OverscaledTileID&, std::set&); - OverscaledTileID coord; uint32_t bucketInstanceId; + std::string bucketLeaderId; std::map> indexedSymbolInstances; }; -- cgit v1.2.1