From d661b4ba61a7bd7770c96464c190bfadf9a42414 Mon Sep 17 00:00:00 2001 From: Ansis Brammanis Date: Fri, 30 Jun 2017 15:38:43 -0400 Subject: [core] port pitch-label collision hack https://github.com/mapbox/mapbox-gl-js/pull/4781/commits/81363951ed56c54f331ffc8d88e4e5079226a224 --- src/mbgl/text/collision_feature.cpp | 30 +++++++++++++++++++++++++----- src/mbgl/text/collision_feature.hpp | 9 +++++++-- src/mbgl/text/collision_tile.cpp | 29 +++++++++++++++++------------ src/mbgl/text/collision_tile.hpp | 2 +- 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::infinity()); + boxes.emplace_back(anchor.point, Point{ 0, 0 }, x1, y1, x2, y2, std::numeric_limits::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(anchorPoint), -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, maxScale); } } +float CollisionBox::adjustedMaxScale(const std::array& 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 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 _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 _anchor, Point _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& rotationMatrix, const float yStretch) const; // the box is centered around the anchor point Point anchor; + + // the offset of the box from the label's anchor point + Point 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& anchor, const CollisionBox& box, const Point& blockingAnchor, const CollisionBox& blocking) { +float CollisionTile::findPlacementScale(const Point& anchor, const CollisionBox& box, const float boxMaxScale, const Point& 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& 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::infinity(); static const std::array edges {{ // left - CollisionBox(Point(0, 0), 0, -infinity, 0, infinity, infinity), + CollisionBox(Point(0, 0), { 0, 0 }, 0, -infinity, 0, infinity, infinity), // right - CollisionBox(Point(util::EXTENT, 0), 0, -infinity, 0, infinity, infinity), + CollisionBox(Point(util::EXTENT, 0), { 0, 0 }, 0, -infinity, 0, infinity, infinity), // top - CollisionBox(Point(0, 0), -infinity, 0, infinity, 0, infinity), + CollisionBox(Point(0, 0), { 0, 0 }, -infinity, 0, infinity, 0, infinity), // bottom - CollisionBox(Point(0, util::EXTENT), -infinity, 0, infinity, 0, infinity) + CollisionBox(Point(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 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 rbl = util::matrixMultiply(reverseRotationMatrix, { box.x1, box.y2 }); const Point 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 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 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& anchor, const CollisionBox& box, + const Point& anchor, const CollisionBox& box, const float boxMaxScale, const Point& blockingAnchor, const CollisionBox& blocking); Box getTreeBox(const Point& anchor, const CollisionBox& box, const float scale = 1.0); -- cgit v1.2.1