[core] Skip fade animation for placed symbols that are currently offscreen.

Don't mark items that are outside the collision grid range as placed.
Requires new ignore because GL JS issue #5654 allows insertion of symbols outside the CollisionIndex range, and those symbols can cascade in to affect items within the viewport.

6 files changed, 84 insertions, 41 deletions

diff --git a/platform/node/test/ignores.json b/platform/node/test/ignores.json
index c4097fecd5..b841986e0f 100644
--- a/platform/node/test/ignores.json
+++ b/platform/node/test/ignores.json
@@ -55,6 +55,7 @@
   "render-tests/runtime-styling/image-add-sdf": "https://github.com/mapbox/mapbox-gl-native/issues/9847",
   "render-tests/runtime-styling/paint-property-fill-flat-to-extrude": "https://github.com/mapbox/mapbox-gl-native/issues/6745",
   "render-tests/runtime-styling/set-style-paint-property-fill-flat-to-extrude": "https://github.com/mapbox/mapbox-gl-native/issues/6745",
+  "render-tests/symbol-placement/line-overscaled": "https://github.com/mapbox/mapbox-gl-js/issues/5654",
   "render-tests/symbol-visibility/visible": "https://github.com/mapbox/mapbox-gl-native/pull/10103",
   "render-tests/text-pitch-alignment/auto-text-rotation-alignment-map": "https://github.com/mapbox/mapbox-gl-native/issues/9732",
   "render-tests/text-pitch-alignment/map-text-rotation-alignment-map": "https://github.com/mapbox/mapbox-gl-native/issues/9732",
diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp
index 129cc3f0e9..72a2d1af4e 100644
--- a/src/mbgl/text/collision_index.cpp
+++ b/src/mbgl/text/collision_index.cpp
@@ -27,9 +27,13 @@ static const float viewportPadding = 100;
 CollisionIndex::CollisionIndex(const TransformState& transformState_)
     : transformState(transformState_)
     , collisionGrid(transformState.getSize().width + 2 * viewportPadding, transformState.getSize().height + 2 * viewportPadding, 25)
-    , ignoredGrid(transformState.getSize().width + 2 * viewportPadding, transformState.getSize().height + 2 * viewportPadding, 25) {
-    pitchFactor = std::cos(transformState.getPitch()) * transformState.getCameraToCenterDistance();
-}
+    , ignoredGrid(transformState.getSize().width + 2 * viewportPadding, transformState.getSize().height + 2 * viewportPadding, 25)
+    , screenRightBoundary(transformState.getSize().width + viewportPadding)
+    , screenBottomBoundary(transformState.getSize().height + viewportPadding)
+    , gridRightBoundary(transformState.getSize().width + 2 * viewportPadding)
+    , gridBottomBoundary(transformState.getSize().height + 2 * viewportPadding)
+    , pitchFactor(std::cos(transformState.getPitch()) * transformState.getCameraToCenterDistance())
+{}
 
 float CollisionIndex::approximateTileDistance(const TileDistance& tileDistance, const float lastSegmentAngle, const float pixelsToTileUnits, const float cameraToAnchorDistance, const bool pitchWithMap) {
     // This is a quick and dirty solution for chosing which collision circles to use (since collision circles are
@@ -51,8 +55,16 @@ float CollisionIndex::approximateTileDistance(const TileDistance& tileDistance,
         (incidenceStretch - 1) * lastSegmentTile * std::abs(std::sin(lastSegmentAngle));
 }
 
+bool CollisionIndex::isOffscreen(const CollisionBox& box) const {
+    return box.px2 < viewportPadding || box.px1 >= screenRightBoundary || box.py2 < viewportPadding || box.py1 >= screenBottomBoundary;
+}
+
+bool CollisionIndex::isInsideGrid(const CollisionBox& box) const {
+    return box.px2 >= 0 && box.px1 < gridRightBoundary && box.py2 >= 0 && box.py1 < gridBottomBoundary;
+}
+
 
-bool CollisionIndex::placeFeature(CollisionFeature& feature,
+std::pair<bool,bool> CollisionIndex::placeFeature(CollisionFeature& feature,
                                       const mat4& posMatrix,
                                       const mat4& labelPlaneMatrix,
                                       const float textPixelRatio,
@@ -70,20 +82,19 @@ bool CollisionIndex::placeFeature(CollisionFeature& feature,
         box.py1 = box.y1 / tileToViewport + projectedPoint.first.y;
         box.px2 = box.x2 / tileToViewport + projectedPoint.first.x;
         box.py2 = box.y2 / tileToViewport + projectedPoint.first.y;
-        
-        if (!allowOverlap) {
-            if (collisionGrid.hitTest({{ box.px1, box.py1 }, { box.px2, box.py2 }})) {
-                return false;
-            }
+
+        if (!isInsideGrid(box) ||
+            (!allowOverlap && collisionGrid.hitTest({{ box.px1, box.py1 }, { box.px2, box.py2 }}))) {
+            return { false, false };
         }
 
-        return true;
+        return {true, isOffscreen(box)};
     } else {
         return placeLineFeature(feature, posMatrix, labelPlaneMatrix, textPixelRatio, symbol, scale, fontSize, allowOverlap, pitchWithMap, collisionDebug);
     }
 }
 
-bool CollisionIndex::placeLineFeature(CollisionFeature& feature,
+std::pair<bool,bool> CollisionIndex::placeLineFeature(CollisionFeature& feature,
                                       const mat4& posMatrix,
                                       const mat4& labelPlaneMatrix,
                                       const float textPixelRatio,
@@ -115,6 +126,8 @@ bool CollisionIndex::placeLineFeature(CollisionFeature& feature,
         /*return tile distance*/ true);
 
     bool collisionDetected = false;
+    bool inGrid = false;
+    bool entirelyOffscreen = true;
 
     const auto tileToViewport = projectedAnchor.first * textPixelRatio;
     // equivalent to pixel_to_tile_units
@@ -183,11 +196,14 @@ bool CollisionIndex::placeLineFeature(CollisionFeature& feature,
         circle.px = projectedPoint.x;
         circle.py = projectedPoint.y;
         circle.radius = radius;
+        
+        entirelyOffscreen &= isOffscreen(circle);
+        inGrid |= isInsideGrid(circle);
 
         if (!allowOverlap) {
             if (collisionGrid.hitTest({{circle.px, circle.py}, circle.radius})) {
                 if (!collisionDebug) {
-                    return false;
+                    return {false, false};
                 } else {
                     // Don't early exit if we're showing the debug circles because we still want to calculate
                     // which circles are in use
@@ -197,7 +213,7 @@ bool CollisionIndex::placeLineFeature(CollisionFeature& feature,
         }
     }
 
-    return !collisionDetected && firstAndLastGlyph;
+    return {!collisionDetected && firstAndLastGlyph && inGrid, entirelyOffscreen};
 }
 
 
diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp
index 6f78d8aeda..8653c1d76c 100644
--- a/src/mbgl/text/collision_index.hpp
+++ b/src/mbgl/text/collision_index.hpp
@@ -17,7 +17,7 @@ public:
 
     explicit CollisionIndex(const TransformState&);
 
-    bool placeFeature(CollisionFeature& feature,
+    std::pair<bool,bool> placeFeature(CollisionFeature& feature,
                                       const mat4& posMatrix,
                                       const mat4& labelPlaneMatrix,
                                       const float textPixelRatio,
@@ -34,7 +34,10 @@ public:
 
     
 private:
-    bool placeLineFeature(CollisionFeature& feature,
+    bool isOffscreen(const CollisionBox&) const;
+    bool isInsideGrid(const CollisionBox&) const;
+
+    std::pair<bool,bool> placeLineFeature(CollisionFeature& feature,
                                   const mat4& posMatrix,
                                   const mat4& labelPlaneMatrix,
                                   const float textPixelRatio,
@@ -51,11 +54,17 @@ private:
     std::pair<Point<float>,float> projectAndGetPerspectiveRatio(const mat4& posMatrix, const Point<float>& point) const;
     Point<float> projectPoint(const mat4& posMatrix, const Point<float>& point) const;
 
-    TransformState transformState;
-    float pitchFactor;
+    const TransformState transformState;
 
     CollisionGrid collisionGrid;
     CollisionGrid ignoredGrid;
+    
+    const float screenRightBoundary;
+    const float screenBottomBoundary;
+    const float gridRightBoundary;
+    const float gridBottomBoundary;
+    
+    const float pitchFactor;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
index 84753c6ea9..85f6385ce6 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -8,7 +8,11 @@
 
 namespace mbgl {
 
-OpacityState::OpacityState(bool placed_) : opacity(0), placed(placed_) {}
+OpacityState::OpacityState(bool placed_, bool offscreen)
+    : opacity((offscreen && placed_) ? 1 : 0)
+    , placed(placed_)
+{
+}
 
 OpacityState::OpacityState(const OpacityState& prevState, float increment, bool placed_) :
     opacity(std::fmax(0, std::fmin(1, prevState.opacity + (prevState.placed ? increment : -increment)))),
@@ -18,9 +22,9 @@ bool OpacityState::isHidden() const {
     return opacity == 0 && !placed;
 }
 
-JointOpacityState::JointOpacityState(bool placedIcon, bool placedText) :
-    icon(OpacityState(placedIcon)),
-    text(OpacityState(placedText)) {}
+JointOpacityState::JointOpacityState(bool placedIcon, bool placedText, bool offscreen) :
+    icon(OpacityState(placedIcon, offscreen)),
+    text(OpacityState(placedText, offscreen)) {}
 
 JointOpacityState::JointOpacityState(const JointOpacityState& prevOpacityState, float increment, bool placedIcon, bool placedText) :
     icon(OpacityState(prevOpacityState.icon, increment, placedIcon)),
@@ -99,29 +103,34 @@ void Placement::placeLayerBucket(
         if (seenCrossTileIDs.count(symbolInstance.crossTileID) == 0) {
             bool placeText = false;
             bool placeIcon = false;
+            bool offscreen = true;
 
             if (symbolInstance.placedTextIndex) {
                 PlacedSymbol& placedSymbol = bucket.text.placedSymbols.at(*symbolInstance.placedTextIndex);
                 const float fontSize = evaluateSizeForFeature(partiallyEvaluatedTextSize, placedSymbol);
 
-                placeText = collisionIndex.placeFeature(symbolInstance.textCollisionFeature,
+                auto placed = collisionIndex.placeFeature(symbolInstance.textCollisionFeature,
                         posMatrix, textLabelPlaneMatrix, textPixelRatio,
                         placedSymbol, scale, fontSize,
                         bucket.layout.get<TextAllowOverlap>(),
                         bucket.layout.get<TextPitchAlignment>() == style::AlignmentType::Map,
                         showCollisionBoxes);
+                placeText = placed.first;
+                offscreen &= placed.second;
             }
 
             if (symbolInstance.placedIconIndex) {
                 PlacedSymbol& placedSymbol = bucket.icon.placedSymbols.at(*symbolInstance.placedIconIndex);
                 const float fontSize = evaluateSizeForFeature(partiallyEvaluatedIconSize, placedSymbol);
 
-                placeIcon = collisionIndex.placeFeature(symbolInstance.iconCollisionFeature,
+                auto placed = collisionIndex.placeFeature(symbolInstance.iconCollisionFeature,
                         posMatrix, iconLabelPlaneMatrix, textPixelRatio,
                         placedSymbol, scale, fontSize,
                         bucket.layout.get<IconAllowOverlap>(),
                         bucket.layout.get<IconPitchAlignment>() == style::AlignmentType::Map,
                         showCollisionBoxes);
+                placeIcon = placed.first;
+                offscreen &= placed.second;
             }
 
             // combine placements for icon and text
@@ -143,7 +152,7 @@ void Placement::placeLayerBucket(
 
             assert(symbolInstance.crossTileID != 0);
 
-            placements.emplace(symbolInstance.crossTileID, PlacementPair(placeText, placeIcon));
+            placements.emplace(symbolInstance.crossTileID, JointPlacement(placeText, placeIcon, offscreen));
             seenCrossTileIDs.insert(symbolInstance.crossTileID);
         }
     } 
@@ -159,16 +168,16 @@ bool Placement::commit(const Placement& prevPlacement, TimePoint now) {
         1.0;
 
     // add the opacities from the current placement, and copy their current values from the previous placement
-    for (auto& placementPair : placements) {
-        auto prevOpacity = prevPlacement.opacities.find(placementPair.first);
+    for (auto& jointPlacement : placements) {
+        auto prevOpacity = prevPlacement.opacities.find(jointPlacement.first);
         if (prevOpacity != prevPlacement.opacities.end()) {
-            opacities.emplace(placementPair.first, JointOpacityState(prevOpacity->second, increment, placementPair.second.icon, placementPair.second.text));
+            opacities.emplace(jointPlacement.first, JointOpacityState(prevOpacity->second, increment, jointPlacement.second.icon, jointPlacement.second.text));
             placementChanged = placementChanged ||
-                placementPair.second.icon != prevOpacity->second.icon.placed ||
-                placementPair.second.text != prevOpacity->second.text.placed;
+                jointPlacement.second.icon != prevOpacity->second.icon.placed ||
+                jointPlacement.second.text != prevOpacity->second.text.placed;
         } else {
-            opacities.emplace(placementPair.first, JointOpacityState(placementPair.second.icon, placementPair.second.text));
-            placementChanged = placementChanged || placementPair.second.icon || placementPair.second.text;
+            opacities.emplace(jointPlacement.first, JointOpacityState(jointPlacement.second.icon, jointPlacement.second.text, jointPlacement.second.offscreen));
+            placementChanged = placementChanged || jointPlacement.second.icon || jointPlacement.second.text;
         }
     }
 
@@ -209,7 +218,7 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket, std::set<uint32_t>&
     for (SymbolInstance& symbolInstance : bucket.symbolInstances) {
         auto opacityState = seenCrossTileIDs.count(symbolInstance.crossTileID) == 0 ?
             getOpacity(symbolInstance.crossTileID) :
-            JointOpacityState(false, false);
+            JointOpacityState(false, false, false);
 
         seenCrossTileIDs.insert(symbolInstance.crossTileID);
 
@@ -271,7 +280,7 @@ JointOpacityState Placement::getOpacity(uint32_t crossTileSymbolID) const {
     if (it != opacities.end()) {
         return it->second;
     } else {
-        return JointOpacityState(false, false);
+        return JointOpacityState(false, false, false);
     }
 
 }
diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp
index 78bfc0a4d8..4d5fad06a1 100644
--- a/src/mbgl/text/placement.hpp
+++ b/src/mbgl/text/placement.hpp
@@ -14,7 +14,7 @@ namespace mbgl {
 
     class OpacityState {
         public:
-            OpacityState(bool placed);
+            OpacityState(bool placed, bool offscreen);
             OpacityState(const OpacityState& prevOpacityState, float increment, bool placed);
             bool isHidden() const;
             float opacity;
@@ -23,18 +23,26 @@ namespace mbgl {
 
     class JointOpacityState {
         public:
-            JointOpacityState(bool placedIcon, bool placedText);
+            JointOpacityState(bool placedIcon, bool placedText, bool offscreen);
             JointOpacityState(const JointOpacityState& prevOpacityState, float increment, bool placedIcon, bool placedText);
             bool isHidden() const;
             OpacityState icon;
             OpacityState text;
     };
 
-    class PlacementPair {
+    class JointPlacement {
         public:
-            PlacementPair(bool text_, bool icon_) : text(text_), icon(icon_) {}
-            bool text;
-            bool icon;
+            JointPlacement(bool text_, bool icon_, bool offscreen_)
+                : text(text_), icon(icon_), offscreen(offscreen_)
+            {}
+        
+            const bool text;
+            const bool icon;
+            // offscreen = outside viewport, but within CollisionIndex::viewportPadding px of the edge
+            // Because these symbols aren't onscreen yet, we can skip the "fade in" animation,
+            // and if a subsequent viewport change brings them into view, they'll be fully
+            // visible right away.
+            const bool offscreen;
     };
 
     class Placement {
@@ -72,7 +80,7 @@ namespace mbgl {
             MapMode mapMode;
             TimePoint commitTime;
 
-            std::unordered_map<uint32_t, PlacementPair> placements;
+            std::unordered_map<uint32_t, JointPlacement> placements;
             std::unordered_map<uint32_t, JointOpacityState> opacities;
         
             TimePoint recentUntil;
diff --git a/src/mbgl/util/grid_index.cpp b/src/mbgl/util/grid_index.cpp
index 1e1dcf0ed5..afd469501d 100644
--- a/src/mbgl/util/grid_index.cpp
+++ b/src/mbgl/util/grid_index.cpp
@@ -103,7 +103,7 @@ bool GridIndex<T>::hitTest(const BCircle& queryBCircle) const {
 
 template <class T>
 bool GridIndex<T>::noIntersection(const BBox& queryBBox) const {
-    return queryBBox.max.x < 0 || queryBBox.min.x > width || queryBBox.max.y < 0 || queryBBox.min.y > height;
+    return queryBBox.max.x < 0 || queryBBox.min.x >= width || queryBBox.max.y < 0 || queryBBox.min.y >= height;
 }
 
 template <class T>