From 2eb327ad3716974f5898c11bbc3894419daede74 Mon Sep 17 00:00:00 2001 From: Chris Loer Date: Thu, 5 Oct 2017 14:34:15 -0700 Subject: CollisionIndex initial implementation of line labels. 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] --- src/mbgl/layout/symbol_projection.cpp | 3 - src/mbgl/layout/symbol_projection.hpp | 3 + src/mbgl/text/collision_feature.cpp | 56 +++-------- src/mbgl/text/collision_feature.hpp | 27 ++++-- src/mbgl/text/collision_index.cpp | 175 ++++++++++++++++++++++++++++++---- src/mbgl/text/collision_index.hpp | 29 +++++- 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,float> PointAndCameraDistance; - PointAndCameraDistance project(const Point& 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,float> PointAndCameraDistance; + PointAndCameraDistance project(const Point& point, const mat4& matrix); void reprojectLineLabels(gl::VertexVector&, const std::vector&, 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(anchor.point); bboxifyLabel(line, anchorPoint, anchor.segment, length, height); } else { - boxes.emplace_back(anchor.point, Point{ 0, 0 }, x1, y1, x2, y2, std::numeric_limits::infinity()); + boxes.emplace_back(anchor.point, Point{ 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::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(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(anchorPoint), -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, paddedAnchorDistance); } } -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 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 _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; + CollisionBox(Point _anchor, Point _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 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& , 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 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 +#include #include #include #include #include #include #include - #include +#include // For PlacedSymbol: pull out to another location + #include #include @@ -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 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 CollisionIndex::queryRenderedSymbols(const Geomet return result; } +std::pair CollisionIndex::projectAnchor(const mat4& posMatrix, const Point& 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,float> CollisionIndex::projectAndGetPerspectiveRatio(const mat4& posMatrix, const Point& 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; using Tree = bgi::rtree>; 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 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 projectAnchor(const mat4& posMatrix, const Point& point) const; std::pair,float> projectAndGetPerspectiveRatio(const mat4& posMatrix, const Point& point) const; Point projectPoint(const mat4& posMatrix, const Point& point) const; -- cgit v1.2.1