[core] port pitch-label collision hack

https://github.com/mapbox/mapbox-gl-js/pull/4781/commits/81363951ed56c54f331ffc8d88e4e5079226a224

4 files changed, 50 insertions, 20 deletions

diff --git a/src/mbgl/text/collision_feature.cpp b/src/mbgl/text/collision_feature.cpp
index 58a7949a8e..022ee50644 100644
--- a/src/mbgl/text/collision_feature.cpp
+++ b/src/mbgl/text/collision_feature.cpp
@@ -42,7 +42,7 @@ CollisionFeature::CollisionFeature(const GeometryCoordinates& line,
             bboxifyLabel(line, anchorPoint, anchor.segment, length, height);
         }
     } else {
-        boxes.emplace_back(anchor.point, x1, y1, x2, y2, std::numeric_limits<float>::infinity());
+        boxes.emplace_back(anchor.point, Point<float>{ 0, 0 }, x1, y1, x2, y2, std::numeric_limits<float>::infinity());
     }
 }
 
@@ -50,10 +50,10 @@ void CollisionFeature::bboxifyLabel(const GeometryCoordinates& line, GeometryCoo
                                     const int segment, const float labelLength, const float boxSize) {
     const float step = boxSize / 2;
     const int nBoxes = std::floor(labelLength / step);
-    // We calculate line collision boxes out to 150% of what would normally be our
+    // We calculate line collision boxes out to 300% of what would normally be our
     // max size, to allow collision detection to work on labels that expand as
     // they move into the distance
-    const int nPitchPaddingBoxes = std::floor(nBoxes / 4);
+    const int nPitchPaddingBoxes = std::floor(nBoxes / 2);
 
     // offset the center of the first box by half a box so that the edge of the
     // box is at the edge of the label.
@@ -90,7 +90,13 @@ void CollisionFeature::bboxifyLabel(const GeometryCoordinates& line, GeometryCoo
 
     for (int i = -nPitchPaddingBoxes; i < nBoxes + nPitchPaddingBoxes; i++) {
         // the distance the box will be from the anchor
-        const float boxDistanceToAnchor = labelStartDistance + i * step;
+        const float boxOffset = i * step;
+        float boxDistanceToAnchor = labelStartDistance + boxOffset;
+
+         // make the distance between pitch padding boxes bigger
+         if (boxOffset < 0) boxDistanceToAnchor += boxOffset;
+         if (boxOffset > labelLength) boxDistanceToAnchor += boxOffset - labelLength;
+
         if (boxDistanceToAnchor < anchorDistance) {
             // The line doesn't extend far enough back for this box, skip it
             // (This could allow for line collisions on distant tiles)
@@ -143,8 +149,22 @@ void CollisionFeature::bboxifyLabel(const GeometryCoordinates& line, GeometryCoo
             maxScale = std::min(maxScale, 0.99f);
         }
 
-        boxes.emplace_back(boxAnchor, -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, maxScale);
+        boxes.emplace_back(boxAnchor, boxAnchor - convertPoint<float>(anchorPoint), -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, maxScale);
     }
 }
 
+float CollisionBox::adjustedMaxScale(const std::array<float, 4>& rotationMatrix, const float yStretch) const {
+    // When the map is pitched the distance covered by a line changes.
+    // Adjust the max scale by (approximatePitchedLength / approximateRegularLength)
+    // to compensate for this.
+    const Point<float> rotatedOffset = util::matrixMultiply(rotationMatrix, offset);
+    const float xSqr = rotatedOffset.x * rotatedOffset.x;
+    const float ySqr = rotatedOffset.y * rotatedOffset.y;
+    const float yStretchSqr = ySqr * yStretch * yStretch;
+    const float adjustmentFactor = xSqr + ySqr != 0 ?
+        std::sqrt((xSqr + yStretchSqr) / (xSqr + ySqr)) :
+        1.0f;
+    return maxScale * adjustmentFactor;
+}
+
 } // namespace mbgl
diff --git a/src/mbgl/text/collision_feature.hpp b/src/mbgl/text/collision_feature.hpp
index c94ec23513..3b6e461a26 100644
--- a/src/mbgl/text/collision_feature.hpp
+++ b/src/mbgl/text/collision_feature.hpp
@@ -11,11 +11,16 @@ namespace mbgl {
 
 class CollisionBox {
 public:
-    CollisionBox(Point<float> _anchor, float _x1, float _y1, float _x2, float _y2, float _maxScale) :
-        anchor(std::move(_anchor)), x1(_x1), y1(_y1), x2(_x2), y2(_y2), maxScale(_maxScale) {}
+    CollisionBox(Point<float> _anchor, Point<float> _offset, float _x1, float _y1, float _x2, float _y2, float _maxScale) :
+        anchor(std::move(_anchor)), offset(_offset), x1(_x1), y1(_y1), x2(_x2), y2(_y2), maxScale(_maxScale) {}
+
+    float adjustedMaxScale(const std::array<float, 4>& rotationMatrix, const float yStretch) const;
 
     // the box is centered around the anchor point
     Point<float> anchor;
+    
+    // the offset of the box from the label's anchor point
+    Point<float> offset;
 
     // distances to the edges from the anchor
     float x1;
diff --git a/src/mbgl/text/collision_tile.cpp b/src/mbgl/text/collision_tile.cpp
index 520f66ead8..b3fbe6f8a3 100644
--- a/src/mbgl/text/collision_tile.cpp
+++ b/src/mbgl/text/collision_tile.cpp
@@ -34,7 +34,7 @@ CollisionTile::CollisionTile(PlacementConfig config_) : config(std::move(config_
 }
 
 
-float CollisionTile::findPlacementScale(const Point<float>& anchor, const CollisionBox& box, const Point<float>& blockingAnchor, const CollisionBox& blocking) {
+float CollisionTile::findPlacementScale(const Point<float>& anchor, const CollisionBox& box, const float boxMaxScale, const Point<float>& blockingAnchor, const CollisionBox& blocking) {
     float minPlacementScale = minScale;
 
     // Find the lowest scale at which the two boxes can fit side by side without overlapping.
@@ -55,10 +55,10 @@ float CollisionTile::findPlacementScale(const Point<float>& anchor, const Collis
         collisionFreeScale = blocking.maxScale;
     }
 
-    if (collisionFreeScale > box.maxScale) {
+    if (collisionFreeScale > boxMaxScale) {
         // If the box can only be shown after it is visible, then the box can never be shown.
         // But the label can be shown after this box is not visible.
-        collisionFreeScale = box.maxScale;
+        collisionFreeScale = boxMaxScale;
     }
 
     if (collisionFreeScale > minPlacementScale &&
@@ -77,13 +77,13 @@ float CollisionTile::placeFeature(const CollisionFeature& feature, bool allowOve
     static const float infinity = std::numeric_limits<float>::infinity();
     static const std::array<CollisionBox, 4> edges {{
         // left
-        CollisionBox(Point<float>(0, 0), 0, -infinity, 0, infinity, infinity),
+        CollisionBox(Point<float>(0, 0), { 0, 0 }, 0, -infinity, 0, infinity, infinity),
         // right
-        CollisionBox(Point<float>(util::EXTENT, 0), 0, -infinity, 0, infinity, infinity),
+        CollisionBox(Point<float>(util::EXTENT, 0), { 0, 0 }, 0, -infinity, 0, infinity, infinity),
         // top
-        CollisionBox(Point<float>(0, 0), -infinity, 0, infinity, 0, infinity),
+        CollisionBox(Point<float>(0, 0), { 0, 0 }, -infinity, 0, infinity, 0, infinity),
         // bottom
-        CollisionBox(Point<float>(0, util::EXTENT), -infinity, 0, infinity, 0, infinity)
+        CollisionBox(Point<float>(0, util::EXTENT), { 0, 0 }, -infinity, 0, infinity, 0, infinity)
     }};
 
     float minPlacementScale = minScale;
@@ -91,12 +91,14 @@ float CollisionTile::placeFeature(const CollisionFeature& feature, bool allowOve
     for (auto& box : feature.boxes) {
         const auto anchor = util::matrixMultiply(rotationMatrix, box.anchor);
 
+        const float boxMaxScale = box.adjustedMaxScale(rotationMatrix, yStretch);
+
         if (!allowOverlap) {
             for (auto it = tree.qbegin(bgi::intersects(getTreeBox(anchor, box))); it != tree.qend(); ++it) {
                 const CollisionBox& blocking = std::get<1>(*it);
                 Point<float> blockingAnchor = util::matrixMultiply(rotationMatrix, blocking.anchor);
 
-                minPlacementScale = util::max(minPlacementScale, findPlacementScale(anchor, box, blockingAnchor, blocking));
+                minPlacementScale = util::max(minPlacementScale, findPlacementScale(anchor, box, boxMaxScale, blockingAnchor, blocking));
                 if (minPlacementScale >= maxScale) return minPlacementScale;
             }
         }
@@ -107,14 +109,15 @@ float CollisionTile::placeFeature(const CollisionFeature& feature, bool allowOve
             const Point<float> rbl = util::matrixMultiply(reverseRotationMatrix, { box.x1, box.y2 });
             const Point<float> rbr = util::matrixMultiply(reverseRotationMatrix, { box.x2, box.y2 });
             CollisionBox rotatedBox(box.anchor,
+                    box.offset,
                     util::min(rtl.x, rtr.x, rbl.x, rbr.x),
                     util::min(rtl.y, rtr.y, rbl.y, rbr.y),
                     util::max(rtl.x, rtr.x, rbl.x, rbr.x),
                     util::max(rtl.y, rtr.y, rbl.y, rbr.y),
-                    box.maxScale);
+                    boxMaxScale);
 
             for (auto& blocking : edges) {
-                minPlacementScale = util::max(minPlacementScale, findPlacementScale(box.anchor, rotatedBox, blocking.anchor, blocking));
+                minPlacementScale = util::max(minPlacementScale, findPlacementScale(box.anchor, rotatedBox, boxMaxScale, blocking.anchor, blocking));
                 if (minPlacementScale >= maxScale) return minPlacementScale;
             }
         }
@@ -131,7 +134,9 @@ void CollisionTile::insertFeature(CollisionFeature& feature, float minPlacementS
     if (minPlacementScale < maxScale) {
         std::vector<CollisionTreeBox> treeBoxes;
         for (auto& box : feature.boxes) {
-            treeBoxes.emplace_back(getTreeBox(util::matrixMultiply(rotationMatrix, box.anchor), box), box, feature.indexedFeature);
+            CollisionBox adjustedBox = box;
+            box.maxScale = box.adjustedMaxScale(rotationMatrix, yStretch);
+            treeBoxes.emplace_back(getTreeBox(util::matrixMultiply(rotationMatrix, box.anchor), box), std::move(adjustedBox), feature.indexedFeature);
         }
         if (ignorePlacement) {
             ignoredTree.insert(treeBoxes.begin(), treeBoxes.end());
@@ -215,7 +220,7 @@ std::vector<IndexedSubfeature> CollisionTile::queryRenderedSymbols(const Geometr
     // Check if feature is rendered (collision free) at current scale.
     auto visibleAtScale = [&] (const CollisionTreeBox& treeBox) -> bool {
         const CollisionBox& box = std::get<1>(treeBox);
-        return roundedScale >= box.placementScale && roundedScale <= box.maxScale;
+        return roundedScale >= box.placementScale && roundedScale <= box.adjustedMaxScale(rotationMatrix, yStretch);
     };
 
     // Check if query polygon intersects with the feature box at current scale.
diff --git a/src/mbgl/text/collision_tile.hpp b/src/mbgl/text/collision_tile.hpp
index dbff6a007b..9868266aa2 100644
--- a/src/mbgl/text/collision_tile.hpp
+++ b/src/mbgl/text/collision_tile.hpp
@@ -58,7 +58,7 @@ public:
 
 private:
     float findPlacementScale(
-            const Point<float>& anchor, const CollisionBox& box,
+            const Point<float>& anchor, const CollisionBox& box, const float boxMaxScale,
             const Point<float>& blockingAnchor, const CollisionBox& blocking);
     Box getTreeBox(const Point<float>& anchor, const CollisionBox& box, const float scale = 1.0);