diff options
Diffstat (limited to 'src/mbgl/text/collision_tile.cpp')
-rw-r--r-- | src/mbgl/text/collision_tile.cpp | 100 |
1 files changed, 66 insertions, 34 deletions
diff --git a/src/mbgl/text/collision_tile.cpp b/src/mbgl/text/collision_tile.cpp index 368750c89f..cc9b602f08 100644 --- a/src/mbgl/text/collision_tile.cpp +++ b/src/mbgl/text/collision_tile.cpp @@ -20,27 +20,39 @@ CollisionTile::CollisionTile(PlacementConfig config_) : config(std::move(config_ rotationMatrix = { { angle_cos, -angle_sin, angle_sin, angle_cos } }; reverseRotationMatrix = { { 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(config.pitch); - - // The amount the map is squished depends on the y position. - // Sort of account for this by making all boxes a bit bigger. - yStretch = std::pow(_yStretch, 1.3f); + perspectiveRatio = + 1.0f + + 0.5f * (util::division(config.cameraToTileDistance, config.cameraToCenterDistance, 1.0f) - + 1.0f); + + minScale /= perspectiveRatio; + maxScale /= perspectiveRatio; + + // We can only approximate here based on the y position of the tile + // The shaders calculate a more accurate "incidence_stretch" + // at render time to calculate an effective scale for collision + // purposes, but we still want to use the yStretch approximation + // here because we can't adjust the aspect ratio of the collision + // boxes at render time. + yStretch = util::max( + 1.0f, util::division(config.cameraToTileDistance, + config.cameraToCenterDistance * std::cos(config.pitch), 1.0f)); } - -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. // 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; + const float s1 = util::division(blocking.x1 - box.x2, anchor.x - blockingAnchor.x, + 1.0f); // scale at which new box is to the left of old box + const float s2 = util::division(blocking.x2 - box.x1, anchor.x - blockingAnchor.x, + 1.0f); // scale at which new box is to the right of old box + const float s3 = util::division((blocking.y1 - box.y2) * yStretch, anchor.y - blockingAnchor.y, + 1.0f); // scale at which new box is to the top of old box + const float s4 = util::division((blocking.y2 - box.y1) * yStretch, anchor.y - blockingAnchor.y, + 1.0f); // scale at which new box is to the bottom of old box float collisionFreeScale = util::min(util::max(s1, s2), util::max(s3, s4)); @@ -50,10 +62,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 && @@ -72,13 +84,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; @@ -86,12 +98,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; } } @@ -102,14 +116,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; } } @@ -126,7 +141,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()); @@ -157,13 +174,21 @@ void CollisionTile::insertFeature(CollisionFeature& feature, float minPlacementS Box CollisionTile::getTreeBox(const Point<float>& anchor, const CollisionBox& box, const float scale) { assert(box.x1 <= box.x2 && box.y1 <= box.y2); return Box{ + // When the 'perspectiveRatio' is high, we're effectively underzooming + // the tile because it's in the distance. + // In order to detect collisions that only happen while underzoomed, + // we have to query a larger portion of the grid. + // This extra work is offset by having a lower 'maxScale' bound + // Note that this adjustment ONLY affects the bounding boxes + // in the grid. It doesn't affect the boxes used for the + // minPlacementScale calculations. CollisionPoint{ - anchor.x + box.x1 / scale, - anchor.y + box.y1 / scale * yStretch + anchor.x + box.x1 / scale * perspectiveRatio, + anchor.y + box.y1 / scale * yStretch * perspectiveRatio, }, CollisionPoint{ - anchor.x + box.x2 / scale, - anchor.y + box.y2 / scale * yStretch + anchor.x + box.x2 / scale * perspectiveRatio, + anchor.y + box.y2 / scale * yStretch * perspectiveRatio } }; } @@ -190,23 +215,30 @@ std::vector<IndexedSubfeature> CollisionTile::queryRenderedSymbols(const Geometr return seenFeatures.find(feature.index) == seenFeatures.end(); }; + // "perspectiveRatio" is a tile-based approximation of how much larger symbols will + // be in the distance. It won't line up exactly with the actually rendered symbols + // Being exact would require running the collision detection logic in symbol_sdf.vertex + // in the CPU + const float perspectiveScale = scale / perspectiveRatio; + // Account for the rounding done when updating symbol shader variables. - const float roundedScale = std::pow(2.0f, std::ceil(util::log2(scale) * 10.0f) / 10.0f); + const float roundedScale = std::pow(2.0f, std::ceil(util::log2(perspectiveScale) * 10.0f) / 10.0f); // 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. auto intersectsAtScale = [&] (const CollisionTreeBox& treeBox) -> bool { const CollisionBox& collisionBox = std::get<1>(treeBox); const auto anchor = util::matrixMultiply(rotationMatrix, collisionBox.anchor); - const int16_t x1 = anchor.x + collisionBox.x1 / scale; - const int16_t y1 = anchor.y + collisionBox.y1 / scale * yStretch; - const int16_t x2 = anchor.x + collisionBox.x2 / scale; - const int16_t y2 = anchor.y + collisionBox.y2 / scale * yStretch; + + const int16_t x1 = anchor.x + (collisionBox.x1 / perspectiveScale); + const int16_t y1 = anchor.y + (collisionBox.y1 / perspectiveScale) * yStretch; + const int16_t x2 = anchor.x + (collisionBox.x2 / perspectiveScale); + const int16_t y2 = anchor.y + (collisionBox.y2 / perspectiveScale) * yStretch; auto bbox = GeometryCoordinates { { x1, y1 }, { x2, y1 }, { x2, y2 }, { x1, y2 } }; |