[core] Do not index and place the off-screen symbols for overscaled tiles

For overscaled tiles the viewport might be showing only a small part of the
tile, so we filter out the off-screen symbols to improve the performance.

9 files changed, 69 insertions, 30 deletions

diff --git a/src/mbgl/layout/symbol_instance.hpp b/src/mbgl/layout/symbol_instance.hpp
index 2a25c655aa..3cd67125b4 100644
--- a/src/mbgl/layout/symbol_instance.hpp
+++ b/src/mbgl/layout/symbol_instance.hpp
@@ -119,6 +119,8 @@ public:
     std::array<float, 2> variableTextOffset;
     bool singleLine;
     uint32_t crossTileID = 0;
+
+    static constexpr uint32_t invalidCrossTileID() { return std::numeric_limits<uint32_t>::max(); }
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/renderer/bucket.hpp b/src/mbgl/renderer/bucket.hpp
index 3e756a06a4..fc34f55e75 100644
--- a/src/mbgl/renderer/bucket.hpp
+++ b/src/mbgl/renderer/bucket.hpp
@@ -56,7 +56,7 @@ public:
     // Returns a pair, the first element of which is a bucket cross-tile id
     // on success call; `0` otherwise. The second element is `true` if
     // the bucket was originally registered; `false` otherwise.
-    virtual std::pair<uint32_t, bool> registerAtCrossTileIndex(CrossTileSymbolLayerIndex&, const OverscaledTileID&) {
+    virtual std::pair<uint32_t, bool> registerAtCrossTileIndex(CrossTileSymbolLayerIndex&, const RenderTile&) {
         return std::make_pair(0u, false);
     }
     // Places this bucket to the given placement.
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.cpp b/src/mbgl/renderer/buckets/symbol_bucket.cpp
index 382aac6563..55002e7851 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.cpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.cpp
@@ -1,6 +1,7 @@
+#include <mbgl/renderer/bucket_parameters.hpp>
 #include <mbgl/renderer/buckets/symbol_bucket.hpp>
 #include <mbgl/renderer/layers/render_symbol_layer.hpp>
-#include <mbgl/renderer/bucket_parameters.hpp>
+#include <mbgl/renderer/render_tile.hpp>
 #include <mbgl/style/layers/symbol_layer_impl.hpp>
 #include <mbgl/text/cross_tile_symbol_index.hpp>
 #include <mbgl/text/glyph_atlas.hpp>
@@ -37,6 +38,7 @@ SymbolBucket::SymbolBucket(Immutable<style::SymbolLayoutProperties::PossiblyEval
       iconsInText(iconsInText_),
       justReloaded(false),
       hasVariablePlacement(false),
+      hasUninitializedSymbols(false),
       symbolInstances(symbolInstances_),
       textSizeBinder(SymbolSizeBinder::create(zoom, textSize, TextSize::defaultValue())),
       iconSizeBinder(SymbolSizeBinder::create(zoom, iconSize, IconSize::defaultValue())),
@@ -296,8 +298,8 @@ bool SymbolBucket::hasFormatSectionOverrides() const {
 }
 
 std::pair<uint32_t, bool> SymbolBucket::registerAtCrossTileIndex(CrossTileSymbolLayerIndex& index,
-                                                                 const OverscaledTileID& tileID) {
-    bool firstTimeAdded = index.addBucket(tileID, *this);
+                                                                 const RenderTile& renderTile) {
+    bool firstTimeAdded = index.addBucket(renderTile.getOverscaledTileID(), renderTile.matrix, *this);
     return std::make_pair(bucketInstanceId, firstTimeAdded);
 }
 
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.hpp b/src/mbgl/renderer/buckets/symbol_bucket.hpp
index 432589a52b..82d8c682aa 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.hpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.hpp
@@ -81,7 +81,7 @@ public:
 
     void upload(gfx::UploadPass&) override;
     bool hasData() const override;
-    std::pair<uint32_t, bool> registerAtCrossTileIndex(CrossTileSymbolLayerIndex&, const OverscaledTileID&) override;
+    std::pair<uint32_t, bool> registerAtCrossTileIndex(CrossTileSymbolLayerIndex&, const RenderTile&) override;
     void place(Placement&, const BucketPlacementParameters&, std::set<uint32_t>&) override;
     void updateVertices(
         const Placement&, bool updateOpacities, const TransformState&, const RenderTile&, std::set<uint32_t>&) override;
@@ -114,6 +114,7 @@ public:
     // Set and used by placement.
     mutable bool justReloaded : 1;
     bool hasVariablePlacement : 1;
+    bool hasUninitializedSymbols : 1;
 
     std::vector<SymbolInstance> symbolInstances;
 
diff --git a/src/mbgl/renderer/render_orchestrator.cpp b/src/mbgl/renderer/render_orchestrator.cpp
index 79059164ae..c771bd100b 100644
--- a/src/mbgl/renderer/render_orchestrator.cpp
+++ b/src/mbgl/renderer/render_orchestrator.cpp
@@ -422,7 +422,7 @@ std::unique_ptr<RenderTree> RenderOrchestrator::createRenderTree(
             Mutable<Placement> placement = makeMutable<Placement>(updateParameters);
             for (auto it = layersNeedPlacement.crbegin(); it != layersNeedPlacement.crend(); ++it) {
                 const RenderLayer& layer = *it;
-                crossTileSymbolIndex.addLayer(layer, updateParameters->transformState);
+                crossTileSymbolIndex.addLayer(layer, longitude);
                 placement->placeLayer(layer);
             }
             placement->commit();
diff --git a/src/mbgl/text/cross_tile_symbol_index.cpp b/src/mbgl/text/cross_tile_symbol_index.cpp
index 5b9d6ae69c..f806c652e1 100644
--- a/src/mbgl/text/cross_tile_symbol_index.cpp
+++ b/src/mbgl/text/cross_tile_symbol_index.cpp
@@ -12,6 +12,7 @@ TileLayerIndex::TileLayerIndex(OverscaledTileID coord_,
                                std::string bucketLeaderId_)
     : coord(coord_), bucketInstanceId(bucketInstanceId_), bucketLeaderId(std::move(bucketLeaderId_)) {
     for (SymbolInstance& symbolInstance : symbolInstances) {
+        if (symbolInstance.crossTileID == SymbolInstance::invalidCrossTileID()) continue;
         indexedSymbolInstances[symbolInstance.key].emplace_back(symbolInstance.crossTileID,
                                                                 getScaledCoordinates(symbolInstance, coord));
     }
@@ -95,11 +96,29 @@ void CrossTileSymbolLayerIndex::handleWrapJump(float newLng) {
     lng = newLng;
 }
 
-bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, SymbolBucket& bucket) {
+namespace {
+
+bool isInVewport(const mat4& posMatrix, const Point<float>& point) {
+    vec4 p = {{point.x, point.y, 0, 1}};
+    matrix::transformMat4(p, p, posMatrix);
+
+    // buffer covers area of the next zoom level (current zoom - 1 covered area).
+    constexpr float buffer = 1.0f;
+    constexpr float edge = 1.0f + buffer;
+    float x = p[0] / p[3];
+    float y = p[1] / p[3];
+    return (x > -edge && y > -edge && x < edge && y < edge);
+}
+
+} // namespace
+
+bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID,
+                                          const mat4& tileMatrix,
+                                          SymbolBucket& bucket) {
     auto& thisZoomIndexes = indexes[tileID.overscaledZ];
     auto previousIndex = thisZoomIndexes.find(tileID);
     if (previousIndex != thisZoomIndexes.end()) {
-        if (previousIndex->second.bucketInstanceId == bucket.bucketInstanceId) {
+        if (previousIndex->second.bucketInstanceId == bucket.bucketInstanceId && !bucket.hasUninitializedSymbols) {
             return false;
         } else {
             // We're replacing this bucket with an updated version
@@ -110,8 +129,23 @@ bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, Symbol
         }
     }
 
-    for (auto& symbolInstance: bucket.symbolInstances) {
-        symbolInstance.crossTileID = 0;
+    bucket.hasUninitializedSymbols = false;
+
+    if (tileID.overscaleFactor() > 1u) {
+        // For overscaled tiles the viewport might be showing only a small part of the tile,
+        // so we filter out the off-screen symbols to improve the performance.
+        for (auto& symbolInstance : bucket.symbolInstances) {
+            if (isInVewport(tileMatrix, symbolInstance.anchor.point)) {
+                symbolInstance.crossTileID = 0u;
+            } else {
+                symbolInstance.crossTileID = SymbolInstance::invalidCrossTileID();
+                bucket.hasUninitializedSymbols = true;
+            }
+        }
+    } else {
+        for (auto& symbolInstance : bucket.symbolInstances) {
+            symbolInstance.crossTileID = 0u;
+        }
     }
 
     auto& thisZoomUsedCrossTileIDs = usedCrossTileIDs[tileID.overscaledZ];
@@ -195,7 +229,7 @@ auto CrossTileSymbolIndex::addLayer(const RenderLayer& layer, float lng) -> AddL
     for (const auto& item : layer.getPlacementData()) {
         const RenderTile& renderTile = item.tile;
         Bucket& bucket = item.bucket;
-        auto pair = bucket.registerAtCrossTileIndex(layerIndex, renderTile.getOverscaledTileID());
+        auto pair = bucket.registerAtCrossTileIndex(layerIndex, renderTile);
         assert(pair.first != 0u);
         if (pair.second) result |= AddLayerResult::BucketsAdded;
         currentBucketIDs.insert(pair.first);
diff --git a/src/mbgl/text/cross_tile_symbol_index.hpp b/src/mbgl/text/cross_tile_symbol_index.hpp
index 3b7c367726..8dfdb8466f 100644
--- a/src/mbgl/text/cross_tile_symbol_index.hpp
+++ b/src/mbgl/text/cross_tile_symbol_index.hpp
@@ -2,8 +2,9 @@
 
 #include <mbgl/tile/tile_id.hpp>
 #include <mbgl/util/bitmask_operations.hpp>
-#include <mbgl/util/geometry.hpp>
 #include <mbgl/util/constants.hpp>
+#include <mbgl/util/geometry.hpp>
+#include <mbgl/util/mat4.hpp>
 #include <mbgl/util/optional.hpp>
 
 #include <map>
@@ -48,7 +49,7 @@ public:
 class CrossTileSymbolLayerIndex {
 public:
     CrossTileSymbolLayerIndex(uint32_t& maxCrossTileID);
-    bool addBucket(const OverscaledTileID&, SymbolBucket&);
+    bool addBucket(const OverscaledTileID&, const mat4& tileMatrix, SymbolBucket&);
     bool removeStaleBuckets(const std::unordered_set<uint32_t>& currentIDs);
     void handleWrapJump(float newLng);
 private:
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
index 43d9713717..32edf679e8 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -157,10 +157,7 @@ void Placement::placeBucket(const SymbolBucket& bucket,
     const bool rotateIconWithMap = layout.get<style::IconRotationAlignment>() == style::AlignmentType::Map;
     const bool pitchIconWithMap = layout.get<style::IconPitchAlignment>() == style::AlignmentType::Map;
 
-    mat4 posMatrix;
-    const auto& projMatrix = state.getProjectionMatrix();
-    state.matrixFor(posMatrix, renderTile.id);
-    matrix::multiply(posMatrix, projMatrix, posMatrix);
+    const mat4& posMatrix = renderTile.matrix;
 
     mat4 textLabelPlaneMatrix =
         getLabelPlaneMatrix(posMatrix, pitchTextWithMap, rotateTextWithMap, state, pixelsToTileUnits);
@@ -212,8 +209,10 @@ void Placement::placeBucket(const SymbolBucket& bucket,
     std::vector<ProjectedCollisionBox> textBoxes;
     std::vector<ProjectedCollisionBox> iconBoxes;
 
-    auto placeSymbol = [&] (const SymbolInstance& symbolInstance) {
-        if (seenCrossTileIDs.count(symbolInstance.crossTileID) != 0u) return;
+    auto placeSymbol = [&](const SymbolInstance& symbolInstance) {
+        if (symbolInstance.crossTileID == SymbolInstance::invalidCrossTileID() ||
+            seenCrossTileIDs.count(symbolInstance.crossTileID) != 0u)
+            return;
 
         if (renderTile.holdForFade()) {
             // Mark all symbols from this tile as "not placed", but don't add to seenCrossTileIDs, because we don't
diff --git a/test/text/cross_tile_symbol_index.test.cpp b/test/text/cross_tile_symbol_index.test.cpp
index f0c78ce632..61597e021f 100644
--- a/test/text/cross_tile_symbol_index.test.cpp
+++ b/test/text/cross_tile_symbol_index.test.cpp
@@ -62,7 +62,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                             {},
                             false /*iconsInText*/};
     mainBucket.bucketInstanceId = ++maxBucketInstanceId;
-    index.addBucket(mainID, mainBucket);
+    index.addBucket(mainID, mat4{}, mainBucket);
 
     // Assigned new IDs
     ASSERT_EQ(mainBucket.symbolInstances.at(0).crossTileID, 1u);
@@ -89,7 +89,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                              {},
                              false /*iconsInText*/};
     childBucket.bucketInstanceId = ++maxBucketInstanceId;
-    index.addBucket(childID, childBucket);
+    index.addBucket(childID, mat4{}, childBucket);
 
     // matched parent tile
     ASSERT_EQ(childBucket.symbolInstances.at(0).crossTileID, 1u);
@@ -117,7 +117,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                               {},
                               false /*iconsInText*/};
     parentBucket.bucketInstanceId = ++maxBucketInstanceId;
-    index.addBucket(parentID, parentBucket);
+    index.addBucket(parentID, mat4{}, parentBucket);
 
     // matched child tile
     ASSERT_EQ(parentBucket.symbolInstances.at(0).crossTileID, 1u);
@@ -145,7 +145,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                                   {},
                                   false /*iconsInText*/};
     grandchildBucket.bucketInstanceId = ++maxBucketInstanceId;
-    index.addBucket(grandchildID, grandchildBucket);
+    index.addBucket(grandchildID, mat4{}, grandchildBucket);
 
     // Matches the symbol in `mainBucket`
     ASSERT_EQ(grandchildBucket.symbolInstances.at(0).crossTileID, 1u);
@@ -203,7 +203,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
     childBucket.bucketInstanceId = ++maxBucketInstanceId;
 
     // assigns a new id
-    index.addBucket(mainID, mainBucket);
+    index.addBucket(mainID, mat4{}, mainBucket);
     ASSERT_EQ(mainBucket.symbolInstances.at(0).crossTileID, 1u);
 
     // removes the tile
@@ -211,11 +211,11 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
     index.removeStaleBuckets(currentIDs);
 
     // assigns a new id
-    index.addBucket(childID, childBucket);
+    index.addBucket(childID, mat4{}, childBucket);
     ASSERT_EQ(childBucket.symbolInstances.at(0).crossTileID, 2u);
 
     // overwrites the old id to match the already-added tile
-    index.addBucket(mainID, mainBucket);
+    index.addBucket(mainID, mat4{}, mainBucket);
     ASSERT_EQ(mainBucket.symbolInstances.at(0).crossTileID, 2u);
 }
 
@@ -270,12 +270,12 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) {
     childBucket.bucketInstanceId = ++maxBucketInstanceId;
 
     // assigns new ids
-    index.addBucket(mainID, mainBucket);
+    index.addBucket(mainID, mat4{}, mainBucket);
     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);
+    index.addBucket(childID, mat4{}, childBucket);
     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
@@ -331,12 +331,12 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
     secondBucket.bucketInstanceId = ++maxBucketInstanceId;
 
     // assigns new ids
-    index.addBucket(tileID, firstBucket);
+    index.addBucket(tileID, mat4{}, firstBucket);
     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);
+    index.addBucket(tileID, mat4{}, secondBucket);
     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