From a8b86fedfe0e6ed466ee7e8c5611d6662474c979 Mon Sep 17 00:00:00 2001 From: Chris Loer Date: Tue, 16 Jan 2018 12:38:27 -0800 Subject: [core] Prevent symbols at the same zoom from sharing a crossTileID. Port of GL JS PR #5994. Fixes issue #10844, which would allow multiple symbols in a tile to share the same crossTileID as one of their duplicate parent-tile symbols. Once the symbols shared a crossTileID, they would permanently remain "duplicates" of each other, even after increasing zoom level allowed the CrossTileSymbolIndex to distinguish between them. --- src/mbgl/text/cross_tile_symbol_index.cpp | 35 +++++++++++--- src/mbgl/text/cross_tile_symbol_index.hpp | 8 +++- test/text/cross_tile_symbol_index.test.cpp | 74 ++++++++++++++++++++++++++++++ 3 files changed, 108 insertions(+), 9 deletions(-) diff --git a/src/mbgl/text/cross_tile_symbol_index.cpp b/src/mbgl/text/cross_tile_symbol_index.cpp index 30d265d885..a9210601f9 100644 --- a/src/mbgl/text/cross_tile_symbol_index.cpp +++ b/src/mbgl/text/cross_tile_symbol_index.cpp @@ -24,7 +24,7 @@ Point TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstan }; } -void TileLayerIndex::findMatches(std::vector& symbolInstances, const OverscaledTileID& newCoord) { +void TileLayerIndex::findMatches(std::vector& symbolInstances, const OverscaledTileID& newCoord, std::set& zoomCrossTileIDs) { float tolerance = coord.canonical.z < newCoord.canonical.z ? 1 : std::pow(2, coord.canonical.z - newCoord.canonical.z); for (auto& symbolInstance : symbolInstances) { @@ -45,8 +45,12 @@ void TileLayerIndex::findMatches(std::vector& symbolInstances, c // 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 && - std::abs(thisTileSymbol.coord.y - scaledSymbolCoord.y) <= tolerance) { - + std::abs(thisTileSymbol.coord.y - scaledSymbolCoord.y) <= tolerance && + zoomCrossTileIDs.find(thisTileSymbol.crossTileID) == zoomCrossTileIDs.end()) { + // Once we've marked ourselves duplicate against this parent symbol, + // don't let any other symbols at the same zoom level duplicate against + // the same parent (see issue #10844) + zoomCrossTileIDs.insert(thisTileSymbol.crossTileID); symbolInstance.crossTileID = thisTileSymbol.crossTileID; break; } @@ -60,8 +64,15 @@ CrossTileSymbolLayerIndex::CrossTileSymbolLayerIndex() { bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, SymbolBucket& bucket, uint32_t& maxCrossTileID) { auto thisZoomIndexes = indexes[tileID.overscaledZ]; auto previousIndex = thisZoomIndexes.find(tileID); - if (previousIndex != thisZoomIndexes.end() && previousIndex->second.bucketInstanceId == bucket.bucketInstanceId) { - return false; + if (previousIndex != thisZoomIndexes.end()) { + if (previousIndex->second.bucketInstanceId == bucket.bucketInstanceId) { + return false; + } else { + // We're replacing this bucket with an updated version + // Remove the old bucket's "used crossTileIDs" now so that the new bucket can claim them. + // The old index entries themselves stick around until 'removeStaleBuckets' is called. + removeBucketCrossTileIDs(tileID.overscaledZ, previousIndex->second); + } } for (auto& symbolInstance: bucket.symbolInstances) { @@ -74,14 +85,14 @@ bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, Symbol if (zoom > tileID.overscaledZ) { for (auto& childIndex : zoomIndexes) { if (childIndex.second.coord.isChildOf(tileID)) { - childIndex.second.findMatches(bucket.symbolInstances, tileID); + childIndex.second.findMatches(bucket.symbolInstances, tileID, usedCrossTileIDs[tileID.overscaledZ]); } } } else { auto parentTileID = tileID.scaledTo(zoom); auto parentIndex = zoomIndexes.find(parentTileID); if (parentIndex != zoomIndexes.end()) { - parentIndex->second.findMatches(bucket.symbolInstances, tileID); + parentIndex->second.findMatches(bucket.symbolInstances, tileID, usedCrossTileIDs[tileID.overscaledZ]); } } } @@ -90,6 +101,7 @@ 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); } } @@ -99,11 +111,20 @@ bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, Symbol return true; } +void CrossTileSymbolLayerIndex::removeBucketCrossTileIDs(uint8_t zoom, const TileLayerIndex& removedBucket) { + for (auto key : removedBucket.indexedSymbolInstances) { + for (auto indexedSymbolInstance : key.second) { + usedCrossTileIDs[zoom].erase(indexedSymbolInstance.crossTileID); + } + } +} + bool CrossTileSymbolLayerIndex::removeStaleBuckets(const std::unordered_set& currentIDs) { bool tilesChanged = false; for (auto& zoomIndexes : indexes) { for (auto it = zoomIndexes.second.begin(); it != zoomIndexes.second.end();) { if (!currentIDs.count(it->second.bucketInstanceId)) { + removeBucketCrossTileIDs(zoomIndexes.first, it->second); it = zoomIndexes.second.erase(it); tilesChanged = true; } else { diff --git a/src/mbgl/text/cross_tile_symbol_index.hpp b/src/mbgl/text/cross_tile_symbol_index.hpp index 995e0061b9..5abcde241c 100644 --- a/src/mbgl/text/cross_tile_symbol_index.hpp +++ b/src/mbgl/text/cross_tile_symbol_index.hpp @@ -6,6 +6,7 @@ #include #include +#include #include #include #include @@ -32,7 +33,7 @@ public: TileLayerIndex(OverscaledTileID coord, std::vector&, uint32_t bucketInstanceId); Point getScaledCoordinates(SymbolInstance&, const OverscaledTileID&); - void findMatches(std::vector&, const OverscaledTileID&); + void findMatches(std::vector&, const OverscaledTileID&, std::set&); OverscaledTileID coord; uint32_t bucketInstanceId; @@ -45,7 +46,10 @@ public: bool addBucket(const OverscaledTileID&, SymbolBucket&, uint32_t& maxCrossTileID); bool removeStaleBuckets(const std::unordered_set& currentIDs); private: - std::map> indexes; + void removeBucketCrossTileIDs(uint8_t zoom, const TileLayerIndex& removedBucket); + + std::map> indexes; + std::map> usedCrossTileIDs; }; class CrossTileSymbolIndex { diff --git a/test/text/cross_tile_symbol_index.test.cpp b/test/text/cross_tile_symbol_index.test.cpp index ef5bd4a101..794c2b59a1 100644 --- a/test/text/cross_tile_symbol_index.test.cpp +++ b/test/text/cross_tile_symbol_index.test.cpp @@ -127,3 +127,77 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) { index.addBucket(mainID, mainBucket, maxCrossTileID); ASSERT_EQ(mainBucket.symbolInstances.at(0).crossTileID, 2u); } + +TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) { + uint32_t maxCrossTileID = 0; + uint32_t maxBucketInstanceId = 0; + CrossTileSymbolLayerIndex index; + + style::SymbolLayoutProperties::PossiblyEvaluated layout; + bool sdfIcons = false; + bool iconsNeedLinear = false; + bool sortFeaturesByY = false; + + OverscaledTileID mainID(6, 0, 6, 8, 8); + std::vector mainInstances; + mainInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A + mainInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B + SymbolBucket mainBucket { layout, {}, 16.0f, 1.0f, 0, sdfIcons, iconsNeedLinear, sortFeaturesByY, std::move(mainInstances) }; + mainBucket.bucketInstanceId = ++maxBucketInstanceId; + + OverscaledTileID childID(7, 0, 7, 16, 16); + std::vector childInstances; + childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // A' + childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // B' + childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // C' + SymbolBucket childBucket { layout, {}, 16.0f, 1.0f, 0, sdfIcons, iconsNeedLinear, sortFeaturesByY, std::move(childInstances) }; + childBucket.bucketInstanceId = ++maxBucketInstanceId; + + // assigns new ids + index.addBucket(mainID, mainBucket, maxCrossTileID); + ASSERT_EQ(mainBucket.symbolInstances.at(0).crossTileID, 1u); + ASSERT_EQ(mainBucket.symbolInstances.at(1).crossTileID, 2u); + + // copies parent ids without duplicate ids in this tile + index.addBucket(childID, childBucket, maxCrossTileID); + ASSERT_EQ(childBucket.symbolInstances.at(0).crossTileID, 1u); // A' copies from A + ASSERT_EQ(childBucket.symbolInstances.at(1).crossTileID, 2u); // B' copies from B + ASSERT_EQ(childBucket.symbolInstances.at(2).crossTileID, 3u); // C' gets new ID +} + +TEST(CrossTileSymbolLayerIndex, bucketReplacement) { + uint32_t maxCrossTileID = 0; + uint32_t maxBucketInstanceId = 0; + CrossTileSymbolLayerIndex index; + + style::SymbolLayoutProperties::PossiblyEvaluated layout; + bool sdfIcons = false; + bool iconsNeedLinear = false; + bool sortFeaturesByY = false; + + OverscaledTileID tileID(6, 0, 6, 8, 8); + std::vector firstInstances; + firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A + firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B + SymbolBucket firstBucket { layout, {}, 16.0f, 1.0f, 0, sdfIcons, iconsNeedLinear, sortFeaturesByY, std::move(firstInstances) }; + firstBucket.bucketInstanceId = ++maxBucketInstanceId; + + std::vector secondInstances; + secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A' + secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B' + secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // C' + SymbolBucket secondBucket { layout, {}, 16.0f, 1.0f, 0, sdfIcons, iconsNeedLinear, sortFeaturesByY, std::move(secondInstances) }; + secondBucket.bucketInstanceId = ++maxBucketInstanceId; + + // assigns new ids + index.addBucket(tileID, firstBucket, maxCrossTileID); + ASSERT_EQ(firstBucket.symbolInstances.at(0).crossTileID, 1u); + ASSERT_EQ(firstBucket.symbolInstances.at(1).crossTileID, 2u); + + // copies parent ids without duplicate ids in this tile + index.addBucket(tileID, secondBucket, maxCrossTileID); + ASSERT_EQ(secondBucket.symbolInstances.at(0).crossTileID, 1u); // A' copies from A + ASSERT_EQ(secondBucket.symbolInstances.at(1).crossTileID, 2u); // B' copies from B + ASSERT_EQ(secondBucket.symbolInstances.at(2).crossTileID, 3u); // C' gets new ID +} + -- cgit v1.2.1