port the remained of CollisionTile

4 files changed, 99 insertions, 8 deletions

diff --git a/src/mbgl/geometry/anchor.hpp b/src/mbgl/geometry/anchor.hpp
index d30394f0b9..6ebb0e3be6 100644
--- a/src/mbgl/geometry/anchor.hpp
+++ b/src/mbgl/geometry/anchor.hpp
@@ -16,10 +16,15 @@ struct Anchor {
         : x(x_), y(y_), angle(angle_), scale(scale_) {}
     explicit Anchor(float x_, float y_, float angle_, float scale_, int segment_)
         : x(x_), y(y_), angle(angle_), scale(scale_), segment(segment_) {}
+
+    template <typename M>
+    inline Anchor matMul(const M &m) const {
+        return Anchor{m[0] * x + m[1] * y, m[2] * x + m[3] * y, angle, scale, segment};
+    }
 };
 
 typedef std::vector<Anchor> Anchors;
 
 }
 
-#endif
\ No newline at end of file
+#endif
diff --git a/src/mbgl/renderer/symbol_bucket.cpp b/src/mbgl/renderer/symbol_bucket.cpp
index 45e8819b09..2b65d1fefb 100644
--- a/src/mbgl/renderer/symbol_bucket.cpp
+++ b/src/mbgl/renderer/symbol_bucket.cpp
@@ -30,15 +30,22 @@ SymbolInstance::SymbolInstance(Anchor &anchor, const std::vector<Coordinate> &li
         const GlyphPositions &face) :
     hasText(shapedText),
     hasIcon(shapedIcon),
+
+    // Create the quads used for rendering the glyphs.
     glyphQuads(inside && shapedText ?
             getGlyphQuads(anchor, shapedText, textBoxScale, line, layout, textAlongLine, face) :
             PlacedGlyphs()),
+
+    // Create the quad used for rendering the icon.
     iconQuads(inside && shapedIcon ?
             getIconQuads(anchor, shapedIcon, line, layout, iconAlongLine) :
             PlacedGlyphs()),
+
+    // Create the collision features that will be used to check whether this symbol instance can be placed
     textCollisionFeature(line, anchor, shapedText, textBoxScale, textPadding, textAlongLine),
     iconCollisionFeature(line, anchor, shapedIcon, iconBoxScale, iconPadding, iconAlongLine) {};
 
+
 SymbolBucket::SymbolBucket(std::unique_ptr<const StyleLayoutSymbol> styleLayout_, Collision &collision_)
     : styleLayout(std::move(styleLayout_)), collision(collision_) {
     assert(styleLayout);
diff --git a/src/mbgl/text/collision_tile.cpp b/src/mbgl/text/collision_tile.cpp
index 688e9b7f35..a6ae4682ad 100644
--- a/src/mbgl/text/collision_tile.cpp
+++ b/src/mbgl/text/collision_tile.cpp
@@ -3,6 +3,9 @@
 
 namespace mbgl {
 
+const float minScale = 0.5f;
+const float maxScale = 2.0f;
+
 void CollisionTile::reset(const float _angle, const float pitch) {
     tree.clear();
     angle = _angle;
@@ -10,7 +13,7 @@ void CollisionTile::reset(const float _angle, const float pitch) {
      // Compute the transformation matrix.
     float angle_sin = std::sin(_angle);
     float angle_cos = std::cos(_angle);
-    matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}};
+    rotationMatrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}};
 
     // Stretch boxes in y direction to account for the map tilt.
     const float _yStretch = 1.0f / std::cos(pitch / 180 * M_PI);
@@ -20,12 +23,86 @@ void CollisionTile::reset(const float _angle, const float pitch) {
     yStretch = std::pow(_yStretch, 1.3);
 }
 
-void CollisionTile::placeFeature(CollisionFeature &) {
-//void CollisionTile::placeFeature(CollisionFeature &feature) {
+float CollisionTile::placeFeature(CollisionFeature &feature) {
+
+    float minPlacementScale = minScale;
+
+    for (auto& box : feature.boxes) {
+        const Anchor anchor = box.anchor.matMul(rotationMatrix);
+
+        std::vector<CollisionTreeBox> blockingBoxes;
+        tree.query(bgi::intersects(getTreeBox(anchor, box)), std::back_inserter(blockingBoxes));
+
+        for (auto& blockingTreeBox : blockingBoxes) {
+            const auto& blocking = std::get<1>(blockingTreeBox);
+            Anchor blockingAnchor = blocking.anchor.matMul(rotationMatrix);
+
+            // Find the lowest scale at which the two boxes can fit side by side without overlapping.
+            // Original algorithm:
+            float s1 = (blocking.x1 - box.x2) / (anchor.x - blockingAnchor.x); // scale at which new box is to the left of old box
+            float s2 = (blocking.x2 - box.x1) / (anchor.x - blockingAnchor.x); // scale at which new box is to the right of old box
+            float s3 = (blocking.y1 - box.y2) * yStretch / (anchor.y - blockingAnchor.y); // scale at which new box is to the top of old box
+            float s4 = (blocking.y2 - box.y1) * yStretch / (anchor.y - blockingAnchor.y); // scale at which new box is to the bottom of old box
+
+            if (std::isnan(s1) || std::isnan(s2)) s1 = s2 = 1;
+            if (std::isnan(s3) || std::isnan(s4)) s3 = s4 = 1;
+
+            float collisionFreeScale = std::fmin(std::fmax(s1, s3), std::fmax(s3, s4));
+
+            if (collisionFreeScale > blocking.maxScale) {
+                // After a box's maxScale the label has shrunk enough that the box is no longer needed to cover it,
+                // so unblock the new box at the scale that the old box disappears.
+                collisionFreeScale = blocking.maxScale;
+            }
+
+            if (collisionFreeScale > box.maxScale) {
+                // 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;
+            }
+
+            if (collisionFreeScale > minPlacementScale &&
+                    collisionFreeScale >= blocking.placementScale) {
+                // If this collision occurs at a lower scale than previously found collisions
+                // and the collision occurs while the other label is visible
+
+                // this this is the lowest scale at which the label won't collide with anything
+                minPlacementScale = collisionFreeScale;
+            }
+
+            if (minPlacementScale >= maxScale) return minPlacementScale;
+        }
+    }
+
+    return minPlacementScale;
+}
+
+void CollisionTile::insertFeature(CollisionFeature &feature, const float minPlacementScale) {
+    for (auto& box : feature.boxes) {
+        box.placementScale = minPlacementScale;
+    }
+
+    if (minPlacementScale < maxScale) {
+        std::vector<CollisionTreeBox> treeBoxes;
+        for (auto& box : feature.boxes) {
+            treeBoxes.emplace_back(getTreeBox(box.anchor.matMul(rotationMatrix), box), box);
+        }
+        tree.insert(treeBoxes.begin(), treeBoxes.end());
+    }
+
 }
 
-void CollisionTile::insertFeature(CollisionFeature &, const float ) {
-//void CollisionTile::insertFeature(CollisionFeature &feature, const float minPlacementScale) {
+Box CollisionTile::getTreeBox(const Anchor &anchor, const CollisionBox &box) {
+    return Box{
+        Point{
+            anchor.x + box.x1,
+            anchor.y + box.y1 * yStretch
+        },
+        Point{
+            anchor.x + box.x2,
+            anchor.y + box.y2 * yStretch
+        }
+    };
 }
 
 }
diff --git a/src/mbgl/text/collision_tile.hpp b/src/mbgl/text/collision_tile.hpp
index 9c209d9e23..b9f8446b15 100644
--- a/src/mbgl/text/collision_tile.hpp
+++ b/src/mbgl/text/collision_tile.hpp
@@ -38,7 +38,7 @@ class CollisionTile {
         zoom(_zoom), tilePixelRatio(tileExtent / tileSize) {}
 
     void reset(const float angle, const float pitch);
-    void placeFeature(CollisionFeature &feature);
+    float placeFeature(CollisionFeature &feature);
     void insertFeature(CollisionFeature &feature, const float minPlacementScale);
 
     const float zoom;
@@ -47,8 +47,10 @@ class CollisionTile {
 
     private:
 
+    Box getTreeBox(const Anchor &anchor, const CollisionBox &box);
+
     Tree tree;
-    std::array<float, 4> matrix;
+    std::array<float, 4> rotationMatrix;
     float yStretch;
 
 };