[core] Add CrossTileSymbolIndex.

This class is responsible for tracking which symbols are "the same" between tiles at different zoom levels, so that symbol opacities (fade animations) can be copied smoothly between tiles.

3 files changed, 236 insertions, 0 deletions

diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake
index f70bbb943f..c6b951c237 100644
--- a/cmake/core-files.cmake
+++ b/cmake/core-files.cmake
@@ -531,6 +531,8 @@ set(MBGL_CORE_FILES
     src/mbgl/text/collision_feature.hpp
     src/mbgl/text/collision_tile.cpp
     src/mbgl/text/collision_tile.hpp
+    src/mbgl/text/cross_tile_symbol_index.cpp
+    src/mbgl/text/cross_tile_symbol_index.hpp
     src/mbgl/text/get_anchors.cpp
     src/mbgl/text/get_anchors.hpp
     src/mbgl/text/glyph.cpp
diff --git a/src/mbgl/text/cross_tile_symbol_index.cpp b/src/mbgl/text/cross_tile_symbol_index.cpp
new file mode 100644
index 0000000000..779bec283c
--- /dev/null
+++ b/src/mbgl/text/cross_tile_symbol_index.cpp
@@ -0,0 +1,167 @@
+#include <mbgl/text/cross_tile_symbol_index.hpp>
+#include <mbgl/layout/symbol_instance.hpp>
+#include <mbgl/renderer/buckets/symbol_bucket.hpp>
+#include <mbgl/renderer/render_tile.hpp>
+#include <mbgl/tile/tile.hpp>
+
+namespace mbgl {
+
+
+TileLayerIndex::TileLayerIndex(OverscaledTileID coord_, std::vector<SymbolInstance>& symbolInstances, uint32_t bucketInstanceId_)
+    : coord(coord_), bucketInstanceId(bucketInstanceId_) {
+        for (SymbolInstance& symbolInstance : symbolInstances) {
+            indexedSymbolInstances[symbolInstance.key].emplace_back(symbolInstance.crossTileID, getScaledCoordinates(symbolInstance, coord));
+        }
+    }
+
+Point<int64_t> TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstance, const OverscaledTileID& childTileCoord) {
+    // 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);
+    return {
+        static_cast<int64_t>(std::floor((childTileCoord.canonical.x * util::EXTENT + symbolInstance.anchor.point.x) * scale)),
+        static_cast<int64_t>(std::floor((childTileCoord.canonical.y * util::EXTENT + symbolInstance.anchor.point.y) * scale))
+    };
+}
+
+void TileLayerIndex::findMatches(std::vector<SymbolInstance>& symbolInstances, const OverscaledTileID& newCoord) {
+    float tolerance = coord.canonical.z < newCoord.canonical.z ? 1 : std::pow(2, coord.canonical.z - newCoord.canonical.z);
+
+    for (auto& symbolInstance : symbolInstances) {
+        if (symbolInstance.crossTileID) {
+            // already has a match, skip
+            continue;
+        }
+
+        auto it = indexedSymbolInstances.find(symbolInstance.key);
+        if (it == indexedSymbolInstances.end()) {
+            // No symbol with this key in this bucket
+            continue;
+        }
+
+        auto scaledSymbolCoord = getScaledCoordinates(symbolInstance, newCoord);
+
+        for (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 &&
+                std::abs(thisTileSymbol.coord.y - scaledSymbolCoord.y) <= tolerance) {
+
+                symbolInstance.crossTileID = thisTileSymbol.crossTileID;
+                break;
+            }
+        }
+    }
+}
+
+CrossTileSymbolLayerIndex::CrossTileSymbolLayerIndex() {
+}
+
+uint32_t CrossTileSymbolLayerIndex::maxCrossTileID = 0;
+
+void CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& coord, SymbolBucket& bucket) {
+    if (bucket.bucketInstanceId) return;
+    bucket.bucketInstanceId = ++maxBucketInstanceId;
+
+    uint8_t minZoom = 25;
+    uint8_t maxZoom = 0;
+    for (auto& it : indexes) {
+        auto z = it.first;
+        minZoom = std::min(minZoom, z);
+        maxZoom = std::max(maxZoom, z);
+    }
+
+
+    // make all higher-res child tiles block duplicate labels in this tile
+    for (auto z = maxZoom; z > coord.overscaledZ; z--) {
+        auto zoomIndexes = indexes.find(z);
+        if (zoomIndexes != indexes.end()) {
+            for (auto& childIndex : zoomIndexes->second) {
+                if (!childIndex.second.coord.isChildOf(coord)) {
+                    continue;
+                }
+                childIndex.second.findMatches(bucket.symbolInstances, coord);
+            }
+        }
+        if (z == 0) {
+            break;
+        }
+    }
+
+    // make this tile block duplicate labels in lower-res parent tiles
+    for (auto z = coord.overscaledZ; z >= minZoom; z--) {
+        auto parentCoord = coord.scaledTo(z);
+        auto zoomIndexes = indexes.find(z);
+        if (zoomIndexes != indexes.end()) {
+            auto parentIndex = zoomIndexes->second.find(parentCoord);
+            if (parentIndex != zoomIndexes->second.end()) {
+                parentIndex->second.findMatches(bucket.symbolInstances, coord);
+            }
+        }
+        if (z == 0) {
+            break;
+        }
+    }
+    
+    for (auto& symbolInstance : bucket.symbolInstances) {
+        if (!symbolInstance.crossTileID) {
+            // symbol did not match any known symbol, assign a new id
+            symbolInstance.crossTileID = ++maxCrossTileID;
+        }
+    }
+
+    indexes[coord.overscaledZ].emplace(coord, TileLayerIndex(coord, bucket.symbolInstances, bucket.bucketInstanceId));
+}
+
+bool CrossTileSymbolLayerIndex::removeStaleBuckets(const std::unordered_set<uint32_t>& currentIDs) {
+    bool tilesChanged = false;
+    for (auto& zoomIndexes : indexes) {
+        for (auto it = zoomIndexes.second.begin(); it != zoomIndexes.second.end();) {
+            if (!currentIDs.count(it->second.bucketInstanceId)) {
+                it = zoomIndexes.second.erase(it);
+                tilesChanged = true;
+            } else {
+                ++it;
+            }
+        }
+    }
+    return tilesChanged;
+}
+
+CrossTileSymbolIndex::CrossTileSymbolIndex() {}
+
+bool CrossTileSymbolIndex::addLayer(RenderSymbolLayer& symbolLayer) {
+
+    auto& layerIndex = layerIndexes[symbolLayer.getID()];
+
+    bool symbolBucketsChanged = false;
+    std::unordered_set<uint32_t> currentBucketIDs;
+
+    for (RenderTile& renderTile : symbolLayer.renderTiles) {
+        if (!renderTile.tile.isRenderable()) {
+            continue;
+        }
+
+        auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl);
+        assert(dynamic_cast<SymbolBucket*>(bucket));
+        SymbolBucket& symbolBucket = *reinterpret_cast<SymbolBucket*>(bucket);
+
+        if (!symbolBucket.bucketInstanceId) {
+            symbolBucketsChanged = true;
+        }
+        layerIndex.addBucket(renderTile.tile.id, symbolBucket);
+        currentBucketIDs.insert(symbolBucket.bucketInstanceId);
+    }
+
+    if (layerIndex.removeStaleBuckets(currentBucketIDs)) {
+        symbolBucketsChanged = true;
+    }
+    return symbolBucketsChanged;
+}
+
+void CrossTileSymbolIndex::reset() {
+    layerIndexes.clear();
+}
+
+} // namespace mbgl
+
diff --git a/src/mbgl/text/cross_tile_symbol_index.hpp b/src/mbgl/text/cross_tile_symbol_index.hpp
new file mode 100644
index 0000000000..0b8c5c4780
--- /dev/null
+++ b/src/mbgl/text/cross_tile_symbol_index.hpp
@@ -0,0 +1,67 @@
+#pragma once
+
+#include <mbgl/tile/tile_id.hpp>
+#include <mbgl/util/geometry.hpp>
+#include <mbgl/util/constants.hpp>
+#include <mbgl/util/optional.hpp>
+
+#include <map>
+#include <vector>
+#include <string>
+#include <memory>
+#include <unordered_set>
+
+namespace mbgl {
+
+class SymbolInstance;
+class RenderSymbolLayer;
+class SymbolBucket;
+
+class IndexEntry {
+    Point<float> anchorPoint;
+
+};
+
+class IndexedSymbolInstance {
+    public:
+        IndexedSymbolInstance(uint32_t crossTileID_, Point<int64_t> coord_)
+            : crossTileID(crossTileID_), coord(coord_) {};
+        uint32_t crossTileID;
+        Point<int64_t> coord;
+};
+
+class TileLayerIndex {
+    public:
+        TileLayerIndex(OverscaledTileID coord, std::vector<SymbolInstance>&, uint32_t bucketInstanceId);
+
+        Point<int64_t> getScaledCoordinates(SymbolInstance&, const OverscaledTileID&);
+        void findMatches(std::vector<SymbolInstance>&, const OverscaledTileID&);
+        
+        OverscaledTileID coord;
+        uint32_t bucketInstanceId;
+        std::map<std::u16string,std::vector<IndexedSymbolInstance>> indexedSymbolInstances;
+};
+
+class CrossTileSymbolLayerIndex {
+    public:
+        CrossTileSymbolLayerIndex();
+        void addBucket(const OverscaledTileID&, SymbolBucket&);
+        bool removeStaleBuckets(const std::unordered_set<uint32_t>& currentIDs);
+    private:
+        std::map<uint8_t,std::map<OverscaledTileID,TileLayerIndex>> indexes;
+        uint32_t maxBucketInstanceId = 0;
+        static uint32_t maxCrossTileID;
+};
+
+class CrossTileSymbolIndex {
+    public:
+        CrossTileSymbolIndex();
+
+        bool addLayer(RenderSymbolLayer&);
+    
+        void reset();
+    private:
+        std::map<std::string,CrossTileSymbolLayerIndex> layerIndexes;
+};
+
+} // namespace mbgl