CollisionIndex initial implementation of line labels.upstream/collision-index

Boxes are still used instead of circles, but it would be pretty easy (if not necessarily most performant) to add a circle geometry refinement to the tree-querying logic.
Compiles but not tested.
[skip ci]

6 files changed, 216 insertions, 77 deletions

diff --git a/src/mbgl/layout/symbol_projection.cpp b/src/mbgl/layout/symbol_projection.cpp
index 67af0753b0..377c8ea5b2 100644
--- a/src/mbgl/layout/symbol_projection.cpp
+++ b/src/mbgl/layout/symbol_projection.cpp
@@ -92,9 +92,6 @@ namespace mbgl {
         return m;
     }
 
-
-    typedef std::pair<Point<float>,float> PointAndCameraDistance;
-
     PointAndCameraDistance project(const Point<float>& point, const mat4& matrix) {
         vec4 pos = {{ point.x, point.y, 0, 1 }};
         matrix::transformMat4(pos, pos, matrix);
diff --git a/src/mbgl/layout/symbol_projection.hpp b/src/mbgl/layout/symbol_projection.hpp
index 72d6172d6b..51b3896edf 100644
--- a/src/mbgl/layout/symbol_projection.hpp
+++ b/src/mbgl/layout/symbol_projection.hpp
@@ -33,6 +33,9 @@ namespace mbgl {
 
     mat4 getLabelPlaneMatrix(const mat4& posMatrix, const bool pitchWithMap, const bool rotateWithMap, const TransformState& state, const float pixelsToTileUnits);
     mat4 getGlCoordMatrix(const mat4& posMatrix, const bool pitchWithMap, const bool rotateWithMap, const TransformState& state, const float pixelsToTileUnits);
+    
+    typedef std::pair<Point<float>,float> PointAndCameraDistance;
+    PointAndCameraDistance project(const Point<float>& point, const mat4& matrix);
 
     void reprojectLineLabels(gl::VertexVector<SymbolDynamicLayoutAttributes::Vertex>&, const std::vector<PlacedSymbol>&,
             const mat4& posMatrix, const style::SymbolPropertyValues&,
diff --git a/src/mbgl/text/collision_feature.cpp b/src/mbgl/text/collision_feature.cpp
index c6224d72af..4c08d17422 100644
--- a/src/mbgl/text/collision_feature.cpp
+++ b/src/mbgl/text/collision_feature.cpp
@@ -13,7 +13,8 @@ CollisionFeature::CollisionFeature(const GeometryCoordinates& line,
                                    const float padding,
                                    const style::SymbolPlacementType placement,
                                    IndexedSubfeature indexedFeature_)
-        : indexedFeature(std::move(indexedFeature_)) {
+        : indexedFeature(std::move(indexedFeature_))
+        , alongLine(placement == style::SymbolPlacementType::Line) {
     if (top == 0 && bottom == 0 && left == 0 && right == 0) return;
 
     const float y1 = top * boxScale - padding;
@@ -21,7 +22,7 @@ CollisionFeature::CollisionFeature(const GeometryCoordinates& line,
     const float x1 = left * boxScale - padding;
     const float x2 = right * boxScale + padding;
 
-    if (placement == style::SymbolPlacementType::Line) {
+    if (alongLine) {
         float height = y2 - y1;
         const double length = x2 - x1;
 
@@ -32,7 +33,7 @@ CollisionFeature::CollisionFeature(const GeometryCoordinates& line,
         GeometryCoordinate anchorPoint = convertPoint<int16_t>(anchor.point);
         bboxifyLabel(line, anchorPoint, anchor.segment, length, height);
     } else {
-        boxes.emplace_back(anchor.point, Point<float>{ 0, 0 }, x1, y1, x2, y2, std::numeric_limits<float>::infinity());
+        boxes.emplace_back(anchor.point, Point<float>{ 0, 0 }, x1, y1, x2, y2);
     }
 }
 
@@ -114,47 +115,18 @@ void CollisionFeature::bboxifyLabel(const GeometryCoordinates& line, GeometryCoo
             p0.x + segmentBoxDistance / segmentLength * (p1.x - p0.x),
             p0.y + segmentBoxDistance / segmentLength * (p1.y - p0.y)
         };
-
-        // Distance from label anchor point to inner (towards center) edge of this box
-        // The tricky thing here is that box positioning doesn't change with scale,
-        // but box size does change with scale.
-        // Technically, distanceToInnerEdge should be:
-        // Math.max(Math.abs(boxDistanceToAnchor - firstBoxOffset) - (step / scale), 0);
-        // But using that formula would make solving for maxScale more difficult, so we
-        // approximate with scale=2.
-        // This makes our calculation spot-on at scale=2, and on the conservative side for
-        // lower scales
-        const float distanceToInnerEdge = std::max(std::fabs(boxDistanceToAnchor - firstBoxOffset) - step / 2, 0.0f);
-        float maxScale = util::division(labelLength / 2, distanceToInnerEdge, std::numeric_limits<float>::infinity());
-
-        // The box maxScale calculations are designed to be conservative on collisions in the scale range
-        // [1,2]. At scale=1, each box has 50% overlap, and at scale=2, the boxes are lined up edge
-        // to edge (beyond scale 2, gaps start to appear, which could potentially allow missed collisions).
-        // We add "pitch padding" boxes to the left and right to handle effective underzooming
-        // (scale < 1) when labels are in the distance. The overlap approximation could cause us to use
-        // these boxes when the scale is greater than 1, but we prevent that because we know
-        // they're only necessary for scales less than one.
-        // This preserves the pre-pitch-padding behavior for unpitched maps.
-        if (i < 0 || i >= nBoxes) {
-            maxScale = std::min(maxScale, 0.99f);
-        }
-
-        boxes.emplace_back(boxAnchor, boxAnchor - convertPoint<float>(anchorPoint), -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, maxScale);
+        
+        // If the box is within boxSize of the anchor, force the box to be used
+        // (so even 0-width labels use at least one box)
+        // Otherwise, the .8 multiplication gives us a little bit of conservative
+        // padding in choosing which boxes to use (see CollisionIndex#placedCollisionCircles)
+        const float paddedAnchorDistance = std::abs(boxDistanceToAnchor - firstBoxOffset) < step ?
+            0 :
+            (boxDistanceToAnchor - firstBoxOffset) * 0.8;
+
+        boxes.emplace_back(boxAnchor, boxAnchor - convertPoint<float>(anchorPoint), -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, paddedAnchorDistance);
     }
 }
 
-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 91cd98ec6f..011f5b45f3 100644
--- a/src/mbgl/text/collision_feature.hpp
+++ b/src/mbgl/text/collision_feature.hpp
@@ -11,10 +11,8 @@ namespace mbgl {
 
 class CollisionBox {
 public:
-    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;
+    CollisionBox(Point<float> _anchor, Point<float> _offset, float _x1, float _y1, float _x2, float _y2, float _tileUnitDistanceToAnchor = 0) :
+        anchor(std::move(_anchor)), offset(_offset), x1(_x1), y1(_y1), x2(_x2), y2(_y2), used(true), tileUnitDistanceToAnchor(_tileUnitDistanceToAnchor) {}
 
     // the box is centered around the anchor point
     Point<float> anchor;
@@ -28,12 +26,24 @@ public:
     float x2;
     float y2;
 
-    // the box is only valid for scales < maxScale.
-    // The box does not block other boxes at scales >= maxScale;
+    // TODO Where's the right place to store the projected bounding box?
+    float px1;
+    float py1;
+    float px2;
+    float py2;
+    // Placeholder for center of circles (can be derived from bounding box)
+    float px;
+    float py;
+    bool used;
+
+    float tileUnitDistanceToAnchor;
+
+    
+    // TODO Placeholders for old collision tiles
     float maxScale;
+    float placementScale;
+    float adjustedMaxScale(const std::array<float, 4>& , const float) const { return 1; }
 
-    // the scale at which the label can first be shown
-    float placementScale = 0.0f;
 };
 
 class CollisionFeature {
@@ -77,6 +87,7 @@ public:
 
     std::vector<CollisionBox> boxes;
     IndexedSubfeature indexedFeature;
+    bool alongLine;
 
 private:
     void bboxifyLabel(const GeometryCoordinates& line, GeometryCoordinate& anchorPoint,
diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp
index 4504459f05..232aa23a8d 100644
--- a/src/mbgl/text/collision_index.cpp
+++ b/src/mbgl/text/collision_index.cpp
@@ -1,13 +1,15 @@
 #include <mbgl/text/collision_index.hpp>
+#include <mbgl/layout/symbol_instance.hpp>
 #include <mbgl/geometry/feature_index.hpp>
 #include <mbgl/math/log2.hpp>
 #include <mbgl/util/constants.hpp>
 #include <mbgl/util/math.hpp>
 #include <mbgl/math/minmax.hpp>
 #include <mbgl/util/intersection_tests.hpp>
-
 #include <mbgl/layout/symbol_projection.hpp>
 
+#include <mbgl/renderer/buckets/symbol_bucket.hpp> // For PlacedSymbol: pull out to another location
+
 #include <mapbox/geometry/envelope.hpp>
 #include <mapbox/geometry/multi_point.hpp>
 
@@ -47,40 +49,162 @@ float CollisionIndex::approximateTileDistance(const TileDistance& tileDistance,
         (incidenceStretch - 1) * lastSegmentTile * std::abs(std::sin(lastSegmentAngle));
 }
 
-Box CollisionIndex::getTreeBox(const CollisionBox& box, const mat4& posMatrix, const float textPixelRatio) const {
-    const auto projectedPoint = projectAndGetPerspectiveRatio(posMatrix, box.anchor);
-    const float tileToViewport = textPixelRatio * projectedPoint.second;
-    const float tlX = box.x1 / tileToViewport + projectedPoint.first.x;
-    const float tlY = box.y1 / tileToViewport + projectedPoint.first.y;
-    const float brX = box.x2 / tileToViewport + projectedPoint.first.x;
-    const float brY = box.y2 / tileToViewport + projectedPoint.first.y;
-
+Box CollisionIndex::getTreeBox(const CollisionBox& box) const {
     return Box{
-        CollisionPoint{ tlX, tlY },
-        CollisionPoint{ brX, brY }
+        CollisionPoint{ box.px1, box.py1 },
+        CollisionPoint{ box.px2, box.py2 }
     };
 }
 
-// TODO: add circle support
-bool CollisionIndex::placeFeature(const CollisionFeature& feature, bool allowOverlap, const mat4& posMatrix, const float textPixelRatio) {
-    for (auto& box : feature.boxes) {
-        const auto projectedBox = getTreeBox(box, posMatrix, textPixelRatio);
-
+bool CollisionIndex::placeFeature(CollisionFeature& feature,
+                                      const mat4& posMatrix,
+                                      const mat4& labelPlaneMatrix,
+                                      const float textPixelRatio,
+                                      PlacedSymbol& symbol,
+                                      const float scale,
+                                      const float fontSize,
+                                      const bool allowOverlap,
+                                      const bool pitchWithMap,
+                                      const bool collisionDebug) {
+    if (!feature.alongLine) {
+        CollisionBox& box = feature.boxes.front();
+        const auto projectedPoint = projectAndGetPerspectiveRatio(posMatrix, box.anchor);
+        const float tileToViewport = textPixelRatio * projectedPoint.second;
+        box.px1 = box.x1 / tileToViewport + projectedPoint.first.x;
+        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) {
-            for (auto it = tree.qbegin(bgi::intersects(projectedBox)); it != tree.qend(); ++it) {
+            if (tree.qbegin(bgi::intersects(getTreeBox(box))) != tree.qend()) {
                 return false;
             }
         }
+
+        return true;
+    } else {
+        return placeLineFeature(feature, posMatrix, labelPlaneMatrix, textPixelRatio, symbol, scale, fontSize, allowOverlap, pitchWithMap, collisionDebug);
     }
+}
+
+bool CollisionIndex::placeLineFeature(CollisionFeature& feature,
+                                      const mat4& posMatrix,
+                                      const mat4& labelPlaneMatrix,
+                                      const float textPixelRatio,
+                                      PlacedSymbol& symbol,
+                                      const float scale,
+                                      const float fontSize,
+                                      const bool allowOverlap,
+                                      const bool pitchWithMap,
+                                      const bool collisionDebug) {
 
-    return true;
+    const auto tileUnitAnchorPoint = symbol.anchorPoint;
+    const auto projectedAnchor = projectAnchor(posMatrix, tileUnitAnchorPoint);
+
+    const float fontScale = fontSize / 24;
+    const float lineOffsetX = symbol.lineOffset[0] * fontSize;
+    const float lineOffsetY = symbol.lineOffset[1] * fontSize;
+
+    const auto labelPlaneAnchorPoint = project(tileUnitAnchorPoint, labelPlaneMatrix).first;
+
+    const auto firstAndLastGlyph = placeFirstAndLastGlyph(
+        fontScale,
+        lineOffsetX,
+        lineOffsetY,
+        /*flip*/ false,
+        labelPlaneAnchorPoint,
+        tileUnitAnchorPoint,
+        symbol,
+        labelPlaneMatrix,
+        /*return tile distance*/ true);
+
+    bool collisionDetected = false;
+
+    const auto tileToViewport = projectedAnchor.first * textPixelRatio;
+    // equivalent to pixel_to_tile_units
+    const auto pixelsToTileUnits = tileToViewport / scale;
+
+    float firstTileDistance = 0, lastTileDistance = 0;
+    if (firstAndLastGlyph) {
+        firstTileDistance = approximateTileDistance(*(firstAndLastGlyph->first.tileDistance), firstAndLastGlyph->first.angle, pixelsToTileUnits, projectedAnchor.second, pitchWithMap);
+        lastTileDistance = approximateTileDistance(*(firstAndLastGlyph->second.tileDistance), firstAndLastGlyph->second.angle, pixelsToTileUnits, projectedAnchor.second, pitchWithMap);
+    }
+
+    bool atLeastOneCirclePlaced = false;
+    for (size_t i = 0; i < feature.boxes.size(); i++) {
+        CollisionBox& circle = feature.boxes[i];
+        const float boxDistanceToAnchor = circle.tileUnitDistanceToAnchor;
+        if (!firstAndLastGlyph ||
+            (boxDistanceToAnchor < -firstTileDistance) ||
+            (boxDistanceToAnchor > lastTileDistance)) {
+            // The label either doesn't fit on its line or we
+            // don't need to use this circle because the label
+            // doesn't extend this far. Either way, mark the circle unused.
+            circle.used = false;
+            continue;
+        }
+
+        const auto projectedPoint = projectPoint(posMatrix, circle.anchor);
+        const float tileUnitRadius = (circle.x2 - circle.x1) / 2;
+        const float radius = tileUnitRadius / tileToViewport;
+
+        if (atLeastOneCirclePlaced) {
+            const CollisionBox& previousCircle = feature.boxes[i - 1];
+            const float dx = projectedPoint.x - previousCircle.px;
+            const float dy = projectedPoint.y - previousCircle.py;
+            // The circle edges touch when the distance between their centers is 2x the radius
+            // When the distance is 1x the radius, they're doubled up, and we could remove
+            // every other circle while keeping them all in touch.
+            // We actually start removing circles when the distance is √2x the radius:
+            //  thinning the number of circles as much as possible is a major performance win,
+            //  and the small gaps introduced don't make a very noticeable difference.
+            const bool placedTooDensely = radius * radius * 2 > dx * dx + dy * dy;
+            if (placedTooDensely) {
+                const bool atLeastOneMoreCircle = (i + 1) < feature.boxes.size();
+                if (atLeastOneMoreCircle) {
+                    const CollisionBox& nextCircle = feature.boxes[i + 1];
+                    const float nextBoxDistanceToAnchor = nextCircle.tileUnitDistanceToAnchor;
+                    if ((nextBoxDistanceToAnchor > -firstTileDistance) &&
+                    (nextBoxDistanceToAnchor < lastTileDistance)) {
+                        // Hide significantly overlapping circles, unless this is the last one we can
+                        // use, in which case we want to keep it in place even if it's tightly packed
+                        // with the one before it.
+                        circle.used = false;
+                        continue;
+                    }
+                }
+            }
+        }
+
+        atLeastOneCirclePlaced = true;
+        circle.px1 = projectedPoint.x - radius;
+        circle.px2 = projectedPoint.x + radius;
+        circle.py1 = projectedPoint.y - radius;
+        circle.py2 = projectedPoint.y + radius;
+        
+        circle.used = true;
+
+        if (!allowOverlap) {
+            if (tree.qbegin(bgi::intersects(getTreeBox(circle))) != tree.qend()) {
+                if (!collisionDebug) {
+                    return false;
+                } else {
+                    // Don't early exit if we're showing the debug circles because we still want to calculate
+                    // which circles are in use
+                    collisionDetected = true;
+                }
+            }
+        }
+    }
+
+    return collisionDetected;
 }
 
-// TODO: don't duplicate projection that just happened in placeFeature
-void CollisionIndex::insertFeature(CollisionFeature& feature, bool ignorePlacement, const mat4& posMatrix, const float textPixelRatio) {
+
+void CollisionIndex::insertFeature(CollisionFeature& feature, bool ignorePlacement) {
     std::vector<CollisionTreeBox> treeBoxes;
     for (auto& box : feature.boxes) {
-        treeBoxes.emplace_back(getTreeBox(box, posMatrix, textPixelRatio), box, feature.indexedFeature);
+        treeBoxes.emplace_back(getTreeBox(box), box, feature.indexedFeature);
     }
     
     if (ignorePlacement) {
@@ -147,6 +271,15 @@ std::vector<IndexedSubfeature> CollisionIndex::queryRenderedSymbols(const Geomet
     return result;
 }
 
+std::pair<float,float> CollisionIndex::projectAnchor(const mat4& posMatrix, const Point<float>& point) const {
+    vec4 p = {{ point.x, point.y, 0, 1 }};
+    matrix::transformMat4(p, p, posMatrix);
+    return std::make_pair(
+        0.5 + 0.5 * (p[3] / transformState.getCameraToCenterDistance()),
+        p[3]
+    );
+}
+
 std::pair<Point<float>,float> CollisionIndex::projectAndGetPerspectiveRatio(const mat4& posMatrix, const Point<float>& point) const {
     vec4 p = {{ point.x, point.y, 0, 1 }};
     matrix::transformMat4(p, p, posMatrix);
diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp
index 554662e72f..e75661a3a5 100644
--- a/src/mbgl/text/collision_index.hpp
+++ b/src/mbgl/text/collision_index.hpp
@@ -39,6 +39,7 @@ using CollisionTreeBox = std::tuple<Box, CollisionBox, IndexedSubfeature>;
 using Tree = bgi::rtree<CollisionTreeBox, bgi::linear<16, 4>>;
 
 class IndexedSubfeature;
+class PlacedSymbol;
 
 struct TileDistance;
 
@@ -46,17 +47,39 @@ class CollisionIndex {
 public:
     explicit CollisionIndex(const TransformState&);
 
-    bool placeFeature(const CollisionFeature&, bool allowOverlap, const mat4& posMatrix, const float textPixelRatio);
-    void insertFeature(CollisionFeature& feature, bool ignorePlacement, const mat4& posMatrix, const float textPixelRatio);
+    bool placeFeature(CollisionFeature& feature,
+                                      const mat4& posMatrix,
+                                      const mat4& labelPlaneMatrix,
+                                      const float textPixelRatio,
+                                      PlacedSymbol& symbol,
+                                      const float scale,
+                                      const float fontSize,
+                                      const bool allowOverlap,
+                                      const bool pitchWithMap,
+                                      const bool collisionDebug);
+
+    void insertFeature(CollisionFeature& feature, bool ignorePlacement);
 
     std::vector<IndexedSubfeature> queryRenderedSymbols(const GeometryCoordinates&, const UnwrappedTileID& tileID, const float textPixelRatio) const;
 
     
 private:
-    Box getTreeBox(const CollisionBox& box, const mat4& posMatrix, const float textPixelRatio) const;
+    bool placeLineFeature(CollisionFeature& feature,
+                                  const mat4& posMatrix,
+                                  const mat4& labelPlaneMatrix,
+                                  const float textPixelRatio,
+                                  PlacedSymbol& symbol,
+                                  const float scale,
+                                  const float fontSize,
+                                  const bool allowOverlap,
+                                  const bool pitchWithMap,
+                                  const bool collisionDebug);
+
+    Box getTreeBox(const CollisionBox& box) const;
     
     float approximateTileDistance(const TileDistance& tileDistance, const float lastSegmentAngle, const float pixelsToTileUnits, const float cameraToAnchorDistance, const bool pitchWithMap);
     
+    std::pair<float,float> projectAnchor(const mat4& posMatrix, const Point<float>& point) const;
     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;