add SymbolOpacityIndex [skip ci]upstream/viewport-collision-symbol-opacity-index

8 files changed, 284 insertions, 4 deletions

diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake
index 85b30026b6..591f56e449 100644
--- a/cmake/core-files.cmake
+++ b/cmake/core-files.cmake
@@ -467,6 +467,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/include/mbgl/tile/tile_id.hpp b/include/mbgl/tile/tile_id.hpp
index 0457dd3a07..e5f46584ef 100644
--- a/include/mbgl/tile/tile_id.hpp
+++ b/include/mbgl/tile/tile_id.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include <mbgl/util/constants.hpp>
+#include <mbgl/util/optional.hpp>
 
 #include <cstdint>
 #include <array>
@@ -58,6 +59,7 @@ public:
     uint32_t overscaleFactor() const;
     OverscaledTileID scaledTo(uint8_t z) const;
     UnwrappedTileID toUnwrapped() const;
+    optional<OverscaledTileID> parent() const;
 
     const uint8_t overscaledZ;
     const int16_t wrap;
@@ -191,6 +193,17 @@ inline UnwrappedTileID OverscaledTileID::toUnwrapped() const {
     return { wrap, canonical };
 }
 
+inline optional<OverscaledTileID> OverscaledTileID::parent() const {
+    if (overscaledZ == 0) {
+        return {};
+    } else if (overscaledZ > canonical.z) {
+        return { OverscaledTileID{ static_cast<uint8_t>(overscaledZ - 1), wrap, canonical } };
+    } else {
+        return { OverscaledTileID{ static_cast<uint8_t>(overscaledZ - 1), wrap,
+            static_cast<uint8_t>(canonical.z - 1), static_cast<uint8_t>(canonical.x / 2), static_cast<uint8_t>(canonical.y / 2) }};
+    }
+}
+
 inline UnwrappedTileID::UnwrappedTileID(uint8_t z_, int64_t x_, int64_t y_)
     : wrap((x_ < 0 ? x_ - (1ll << z_) + 1 : x_) / (1ll << z_)),
       canonical(
diff --git a/src/mbgl/layout/symbol_instance.cpp b/src/mbgl/layout/symbol_instance.cpp
index 02fb800df6..8a83cc4b90 100644
--- a/src/mbgl/layout/symbol_instance.cpp
+++ b/src/mbgl/layout/symbol_instance.cpp
@@ -23,7 +23,8 @@ SymbolInstance::SymbolInstance(Anchor& anchor_,
                                const std::array<float, 2> iconOffset_,
                                const GlyphPositionMap& positions,
                                const IndexedSubfeature& indexedFeature,
-                               const std::size_t featureIndex_) :
+                               const std::size_t featureIndex_,
+                               const std::u16string& key_) :
     anchor(anchor_),
     line(line_),
     index(index_),
@@ -35,7 +36,8 @@ SymbolInstance::SymbolInstance(Anchor& anchor_,
     iconCollisionFeature(line_, anchor, shapedIcon, iconBoxScale, iconPadding, iconPlacement, indexedFeature),
     featureIndex(featureIndex_),
     textOffset(textOffset_),
-    iconOffset(iconOffset_) {
+    iconOffset(iconOffset_),
+    key(key_) {
 
     // Create the quads used for rendering the icon and glyphs.
     if (addToBuffers) {
diff --git a/src/mbgl/layout/symbol_instance.hpp b/src/mbgl/layout/symbol_instance.hpp
index f1df416cd1..0ad97edf87 100644
--- a/src/mbgl/layout/symbol_instance.hpp
+++ b/src/mbgl/layout/symbol_instance.hpp
@@ -10,6 +10,14 @@ namespace mbgl {
 class Anchor;
 class IndexedSubfeature;
 
+class OpacityState {
+    public:
+        OpacityState() : opacity(0), targetOpacity(0) {}
+        float opacity;
+        float targetOpacity;
+        TimePoint time;
+};
+
 class SymbolInstance {
 public:
     SymbolInstance(Anchor& anchor,
@@ -30,7 +38,8 @@ public:
                    const std::array<float, 2> iconOffset,
                    const GlyphPositionMap&,
                    const IndexedSubfeature&,
-                   const std::size_t featureIndex);
+                   const std::size_t featureIndex,
+                   const std::u16string& key);
 
     Anchor anchor;
     GeometryCoordinates line;
@@ -45,6 +54,10 @@ public:
     std::size_t featureIndex;
     std::array<float, 2> textOffset;
     std::array<float, 2> iconOffset;
+    std::u16string key;
+    bool isDuplicate;
+    OpacityState iconOpacityState;
+    OpacityState textOpacityState;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp
index 2c90b69b08..97806d05c2 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -321,7 +321,7 @@ void SymbolLayout::addFeature(const std::size_t index,
                 addToBuffers, symbolInstances.size(),
                 textBoxScale, textPadding, textPlacement, textOffset,
                 iconBoxScale, iconPadding, iconPlacement, iconOffset,
-                glyphPositionMap, indexedFeature, index);
+                glyphPositionMap, indexedFeature, index, feature.text ? *feature.text : std::u16string{});
     };
     
     const auto& type = feature.getType();
diff --git a/src/mbgl/style/style_impl.hpp b/src/mbgl/style/style_impl.hpp
index 3dc222bfad..b392c34f0a 100644
--- a/src/mbgl/style/style_impl.hpp
+++ b/src/mbgl/style/style_impl.hpp
@@ -18,6 +18,8 @@
 #include <mbgl/util/optional.hpp>
 #include <mbgl/util/geo.hpp>
 
+#include <mbgl/text/cross_tile_symbol_index.hpp>
+
 #include <memory>
 #include <string>
 #include <vector>
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..fadc33acc8
--- /dev/null
+++ b/src/mbgl/text/cross_tile_symbol_index.cpp
@@ -0,0 +1,190 @@
+#include <mbgl/text/cross_tile_symbol_index.hpp>
+#include <mbgl/layout/symbol_instance.hpp>
+
+namespace mbgl {
+
+
+TileLayerIndex::TileLayerIndex(OverscaledTileID coord, std::shared_ptr<std::vector<SymbolInstance>> symbolInstances)
+    : coord(coord), symbolInstances(symbolInstances) {
+        for (SymbolInstance& symbolInstance : *symbolInstances) {
+            if (indexedSymbolInstances.find(symbolInstance.key) == indexedSymbolInstances.end()) {
+                indexedSymbolInstances.emplace(symbolInstance.key, std::vector<IndexedSymbolInstance>{});
+            }
+
+            indexedSymbolInstances.at(symbolInstance.key).emplace_back(symbolInstance, getScaledCoordinates(symbolInstance, coord));
+
+            symbolInstance.isDuplicate = false;
+            // symbolInstance.isDuplicate = false;
+            // If we don't pick up an opacity from our parent or child tiles
+            // Reset so that symbols in cached tiles fade in the same
+            // way as freshly loaded tiles
+            symbolInstance.textOpacityState = OpacityState{};
+            symbolInstance.iconOpacityState = OpacityState{};
+        }
+    }
+
+Point<double> TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstance, 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 {
+        std::floor((childTileCoord.canonical.x * util::EXTENT + symbolInstance.anchor.point.x) * scale),
+        std::floor((childTileCoord.canonical.y * util::EXTENT + symbolInstance.anchor.point.y) * scale)
+    };
+}
+
+optional<SymbolInstance> TileLayerIndex::getMatchingSymbol(SymbolInstance& childTileSymbol, OverscaledTileID& childTileCoord) {
+    auto it = indexedSymbolInstances.find(childTileSymbol.key);
+    if (it == indexedSymbolInstances.end()) return {};
+
+    Point<double> childTileSymbolCoord = getScaledCoordinates(childTileSymbol, childTileCoord);
+
+    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::fabs(thisTileSymbol.coord.x - childTileSymbolCoord.x) <= 1 &&
+            std::fabs(thisTileSymbol.coord.y - childTileSymbolCoord.y) <= 1) {
+            return { thisTileSymbol.instance };
+        }
+    }
+
+    return {};
+}
+
+CrossTileSymbolLayerIndex::CrossTileSymbolLayerIndex() {
+}
+
+void CrossTileSymbolLayerIndex::addTile(const OverscaledTileID& coord, std::shared_ptr<std::vector<SymbolInstance>> symbolInstances) {
+    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);
+    }
+
+    TileLayerIndex tileIndex(coord, symbolInstances);
+
+    // make all higher-res child tiles block duplicate labels in this tile
+    for (auto z = maxZoom; z > coord.overscaledZ; z--) {
+        auto zoomIndexes = indexes.find(coord.overscaledZ);
+        if (zoomIndexes != indexes.end()) {
+            for (auto& childIndex : zoomIndexes->second) {
+                if (!childIndex.second.coord.isChildOf(coord)) continue;
+                // Mark labels in this tile blocked, and don't copy opacity state
+                // into this tile
+                blockLabels(childIndex.second, tileIndex, false);
+            }
+        }
+    }
+
+    // make this tile block duplicate labels in lower-res parent tiles
+    auto parentCoord = std::make_unique<OverscaledTileID>(coord);
+    for (auto z = coord.overscaledZ - 1; z >= minZoom; z--) {
+        parentCoord = std::make_unique<OverscaledTileID>(*(parentCoord->parent()));
+        auto zoomIndexes = indexes.find(z);
+        if (zoomIndexes != indexes.end()) {
+            auto parentIndex = zoomIndexes->second.find(*parentCoord);
+            if (parentIndex != zoomIndexes->second.end()) {
+                // Mark labels in the parent tile blocked, and copy opacity state
+                // into this tile
+                blockLabels(tileIndex, parentIndex->second, true);
+            }
+        }
+    }
+    
+    if (indexes.find(coord.overscaledZ) == indexes.end()) {
+        indexes.emplace(coord.overscaledZ, std::map<OverscaledTileID,TileLayerIndex>{});
+    }
+
+    indexes.at(coord.overscaledZ).emplace(coord, std::move(tileIndex));
+}
+
+void CrossTileSymbolLayerIndex::removeTile(const OverscaledTileID& coord) {
+	
+	auto removedIndex = indexes.at(coord.overscaledZ).at(coord);
+
+    uint8_t minZoom = 25;
+    for (auto& it : indexes) {
+        auto z = it.first;
+        minZoom = std::min(minZoom, z);
+    }
+
+    auto parentCoord = std::make_unique<OverscaledTileID>(coord);
+    for (auto z = coord.overscaledZ - 1; z >= minZoom; z--) {
+        parentCoord = std::make_unique<OverscaledTileID>(*(parentCoord->parent()));
+        auto zoomIndexes = indexes.find(z);
+        if (zoomIndexes != indexes.end()) {
+            auto parentIndex = zoomIndexes->second.find(*parentCoord);
+            if (parentIndex != zoomIndexes->second.end()) {
+                unblockLabels(removedIndex, parentIndex->second);
+            }
+        }
+    }
+
+    indexes.at(coord.overscaledZ).erase(coord);
+    if (indexes.at(coord.overscaledZ).size() == 0) {
+        indexes.erase(coord.overscaledZ);
+    }
+}
+
+void CrossTileSymbolLayerIndex::blockLabels(TileLayerIndex& childIndex, TileLayerIndex& parentIndex, bool copyParentOpacity) {
+    for (auto& symbolInstance : *childIndex.symbolInstances) {
+        // only non-duplicate labels can block other labels
+        if (!symbolInstance.isDuplicate) {
+            auto parentSymbolInstance = parentIndex.getMatchingSymbol(symbolInstance, childIndex.coord);
+            if (parentSymbolInstance) {
+                // if the parent label was previously non-duplicate, make it duplicate because it's now blocked
+                if (!parentSymbolInstance->isDuplicate) {
+                    parentSymbolInstance->isDuplicate = true;
+
+                    // If the child label is the one being added to the index,
+                    // copy the parent's opacity to the child
+                    if (copyParentOpacity) {
+                        symbolInstance.textOpacityState = parentSymbolInstance->textOpacityState;
+                        symbolInstance.iconOpacityState = parentSymbolInstance->iconOpacityState;
+                    }
+                }
+            }
+        }
+    }
+}
+
+void CrossTileSymbolLayerIndex::unblockLabels(TileLayerIndex& childIndex, TileLayerIndex& parentIndex) {
+    assert(childIndex.coord.overscaledZ > parentIndex.coord.overscaledZ);
+    for (auto& symbolInstance : *childIndex.symbolInstances) {
+        // only non-duplicate labels were blocking other labels
+        if (!symbolInstance.isDuplicate) {
+            auto parentSymbolInstance = parentIndex.getMatchingSymbol(symbolInstance, childIndex.coord);
+            if (parentSymbolInstance) {
+                // this label is now unblocked, copy its opacity state
+                parentSymbolInstance->isDuplicate = false;
+                parentSymbolInstance->textOpacityState = symbolInstance.textOpacityState;
+                parentSymbolInstance->iconOpacityState = symbolInstance.iconOpacityState;
+
+                // mark child as duplicate so that it doesn't unblock further tiles at lower res
+                // in the remaining calls to unblockLabels before it's fully removed
+                symbolInstance.isDuplicate = true;
+            }
+        }
+    }
+}
+
+CrossTileSymbolIndex::CrossTileSymbolIndex() {}
+
+void CrossTileSymbolIndex::addTileLayer(std::string& layerId, const OverscaledTileID& coord, std::shared_ptr<std::vector<SymbolInstance>> symbolInstances) {
+    if (layerIndexes.find(layerId) == layerIndexes.end()) {
+        layerIndexes.emplace(layerId, CrossTileSymbolLayerIndex{});
+    }
+
+    CrossTileSymbolLayerIndex& layerIndex = layerIndexes.at(layerId);
+    layerIndex.addTile(coord, symbolInstances);
+}
+
+void CrossTileSymbolIndex::removeTileLayer(std::string& layerId, const OverscaledTileID& coord) {
+    auto it = layerIndexes.find(layerId);
+    if (it != layerIndexes.end()) {
+        it->second.removeTile(coord);
+    }
+}
+} // 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..3358c59366
--- /dev/null
+++ b/src/mbgl/text/cross_tile_symbol_index.hpp
@@ -0,0 +1,58 @@
+#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>
+
+namespace mbgl {
+
+class SymbolInstance;
+
+class IndexedSymbolInstance {
+    public:
+        IndexedSymbolInstance(SymbolInstance& symbolInstance, Point<double> coord)
+            : instance(symbolInstance), coord(coord) {};
+        SymbolInstance& instance;
+        Point<double> coord;
+};
+
+class TileLayerIndex {
+    public:
+        TileLayerIndex(OverscaledTileID coord, std::shared_ptr<std::vector<SymbolInstance>>);
+
+        Point<double> getScaledCoordinates(SymbolInstance&, OverscaledTileID&);
+        optional<SymbolInstance> getMatchingSymbol(SymbolInstance& childTileSymbol, OverscaledTileID& childTileCoord);
+        
+        OverscaledTileID coord;
+        std::map<std::u16string,std::vector<IndexedSymbolInstance>> indexedSymbolInstances;
+        std::shared_ptr<std::vector<SymbolInstance>> symbolInstances;
+};
+
+class CrossTileSymbolLayerIndex {
+    public:
+        CrossTileSymbolLayerIndex();
+
+        void addTile(const OverscaledTileID&, std::shared_ptr<std::vector<SymbolInstance>>);
+        void removeTile(const OverscaledTileID&);
+        void blockLabels(TileLayerIndex& childIndex, TileLayerIndex& parentIndex, bool copyParentOpacity);
+        void unblockLabels(TileLayerIndex& childIndex, TileLayerIndex& parentIndex);
+    private:
+        std::map<uint8_t,std::map<OverscaledTileID,TileLayerIndex>> indexes;
+};
+
+class CrossTileSymbolIndex {
+    public:
+        CrossTileSymbolIndex();
+
+        void addTileLayer(std::string& layerId, const OverscaledTileID&, std::shared_ptr<std::vector<SymbolInstance>>);
+        void removeTileLayer(std::string& layerId, const OverscaledTileID&);
+    private:
+        std::map<std::string,CrossTileSymbolLayerIndex> layerIndexes;
+};
+
+} // namespace mbgl