summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/mbgl/text/collision_index.cpp338
-rw-r--r--src/mbgl/text/collision_index.hpp61
2 files changed, 399 insertions, 0 deletions
diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp
new file mode 100644
index 0000000000..129cc3f0e9
--- /dev/null
+++ b/src/mbgl/text/collision_index.cpp
@@ -0,0 +1,338 @@
+#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 <mapbox/geometry/envelope.hpp>
+
+#include <mbgl/renderer/buckets/symbol_bucket.hpp> // For PlacedSymbol: pull out to another location
+
+#include <cmath>
+
+namespace mbgl {
+
+// When a symbol crosses the edge that causes it to be included in
+// collision detection, it will cause changes in the symbols around
+// it. This constant specifies how many pixels to pad the edge of
+// the viewport for collision detection so that the bulk of the changes
+// occur offscreen. Making this constant greater increases label
+// stability, but it's expensive.
+static const float viewportPadding = 100;
+
+CollisionIndex::CollisionIndex(const TransformState& transformState_)
+ : transformState(transformState_)
+ , collisionGrid(transformState.getSize().width + 2 * viewportPadding, transformState.getSize().height + 2 * viewportPadding, 25)
+ , ignoredGrid(transformState.getSize().width + 2 * viewportPadding, transformState.getSize().height + 2 * viewportPadding, 25) {
+ pitchFactor = std::cos(transformState.getPitch()) * transformState.getCameraToCenterDistance();
+}
+
+float CollisionIndex::approximateTileDistance(const TileDistance& tileDistance, const float lastSegmentAngle, const float pixelsToTileUnits, const float cameraToAnchorDistance, const bool pitchWithMap) {
+ // This is a quick and dirty solution for chosing which collision circles to use (since collision circles are
+ // laid out in tile units). Ideally, I think we should generate collision circles on the fly in viewport coordinates
+ // at the time we do collision detection.
+
+ // incidenceStretch is the ratio of how much y space a label takes up on a tile while drawn perpendicular to the viewport vs
+ // how much space it would take up if it were drawn flat on the tile
+ // Using law of sines, camera_to_anchor/sin(ground_angle) = camera_to_center/sin(incidence_angle)
+ // Incidence angle 90 -> head on, sin(incidence_angle) = 1, no stretch
+ // Incidence angle 1 -> very oblique, sin(incidence_angle) =~ 0, lots of stretch
+ // ground_angle = u_pitch + PI/2 -> sin(ground_angle) = cos(u_pitch)
+ // incidenceStretch = 1 / sin(incidenceAngle)
+
+ const float incidenceStretch = pitchWithMap ? 1 : cameraToAnchorDistance / pitchFactor;
+ const float lastSegmentTile = tileDistance.lastSegmentViewportDistance * pixelsToTileUnits;
+ return tileDistance.prevTileDistance +
+ lastSegmentTile +
+ (incidenceStretch - 1) * lastSegmentTile * std::abs(std::sin(lastSegmentAngle));
+}
+
+
+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) {
+ if (collisionGrid.hitTest({{ box.px1, box.py1 }, { box.px2, box.py2 }})) {
+ 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) {
+
+ 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 boxSignedDistanceFromAnchor = circle.signedDistanceFromAnchor;
+ if (!firstAndLastGlyph ||
+ (boxSignedDistanceFromAnchor < -firstTileDistance) ||
+ (boxSignedDistanceFromAnchor > 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 nextBoxDistanceFromAnchor = nextCircle.signedDistanceFromAnchor;
+ if ((nextBoxDistanceFromAnchor > -firstTileDistance) &&
+ (nextBoxDistanceFromAnchor < 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;
+
+ circle.px = projectedPoint.x;
+ circle.py = projectedPoint.y;
+ circle.radius = radius;
+
+ if (!allowOverlap) {
+ if (collisionGrid.hitTest({{circle.px, circle.py}, circle.radius})) {
+ 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 && firstAndLastGlyph;
+}
+
+
+void CollisionIndex::insertFeature(CollisionFeature& feature, bool ignorePlacement) {
+ if (feature.alongLine) {
+ for (auto& circle : feature.boxes) {
+ if (!circle.used) {
+ continue;
+ }
+
+ if (ignorePlacement) {
+ ignoredGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ circle.px, circle.py }, circle.radius});
+ } else {
+ collisionGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ circle.px, circle.py }, circle.radius});
+ }
+ }
+ } else {
+ assert(feature.boxes.size() == 1);
+ auto& box = feature.boxes[0];
+ if (ignorePlacement) {
+ ignoredGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ box.px1, box.py1 }, { box.px2, box.py2 }});
+ } else {
+ collisionGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ box.px1, box.py1 }, { box.px2, box.py2 }});
+ }
+ }
+}
+
+std::vector<IndexedSubfeature> CollisionIndex::queryRenderedSymbols(const GeometryCoordinates& queryGeometry, const UnwrappedTileID& tileID, const std::string& sourceID) const {
+ std::vector<IndexedSubfeature> result;
+ if (queryGeometry.empty() || (collisionGrid.empty() && ignoredGrid.empty())) {
+ return result;
+ }
+
+ mat4 posMatrix;
+ mat4 projMatrix;
+ transformState.getProjMatrix(projMatrix);
+ transformState.matrixFor(posMatrix, tileID);
+ matrix::multiply(posMatrix, projMatrix, posMatrix);
+
+ // Two versions of the query here just because util::polygonIntersectsPolygon requires
+ // GeometryCoordinates (based on int16_t). Otherwise, work with floats.
+ GeometryCoordinates projectedPolygon;
+ LineString<float> projectedQuery;
+
+ for (const auto& point : queryGeometry) {
+ auto projected = projectPoint(posMatrix, convertPoint<float>(point));
+ projectedPolygon.push_back(convertPoint<int16_t>(projected));
+ projectedQuery.push_back(projected);
+ }
+
+ auto envelope = mapbox::geometry::envelope(projectedQuery);
+
+ using QueryResult = std::pair<IndexedSubfeature, GridIndex<IndexedSubfeature>::BBox>;
+
+ std::vector<QueryResult> thisTileFeatures;
+ std::vector<QueryResult> features = collisionGrid.queryWithBoxes(envelope);
+
+ for (auto& queryResult : features) {
+ auto& feature = queryResult.first;
+ CanonicalTileID featureTileID(feature.z, feature.x, feature.y);
+ if (feature.sourceID == sourceID && featureTileID == tileID.canonical) {
+ // We only have to filter on the canonical ID because even if the feature is showing multiple times
+ // we treat it as one feature.
+ thisTileFeatures.push_back(queryResult);
+ }
+ }
+
+ std::vector<QueryResult> ignoredFeatures = ignoredGrid.queryWithBoxes(envelope);
+ for (auto& queryResult : ignoredFeatures) {
+ auto& feature = queryResult.first;
+ CanonicalTileID featureTileID(feature.z, feature.x, feature.y);
+ if (feature.sourceID == sourceID && featureTileID == tileID.canonical) {
+ thisTileFeatures.push_back(queryResult);
+ }
+ }
+
+ std::unordered_map<std::string, std::unordered_set<std::size_t>> sourceLayerFeatures;
+ for (auto& queryResult : thisTileFeatures) {
+ auto& feature = queryResult.first;
+ auto& bbox = queryResult.second;
+
+ // Skip already seen features.
+ auto& seenFeatures = sourceLayerFeatures[feature.sourceLayerName];
+ if (seenFeatures.find(feature.index) != seenFeatures.end())
+ continue;
+
+ seenFeatures.insert(feature.index);
+
+ int16_t minX1 = bbox.min.x;
+ int16_t maxY1 = bbox.max.y;
+ int16_t minY1 = bbox.min.y;
+ int16_t maxX1 = bbox.max.x;
+
+ auto bboxPoints = GeometryCoordinates {
+ { minX1, minY1 }, { maxX1, minY1 }, { maxX1, maxY1 }, { minX1, maxY1 }
+ };
+
+ if (!util::polygonIntersectsPolygon(projectedPolygon, bboxPoints))
+ continue;
+
+ result.push_back(feature);
+ }
+
+ 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);
+ return std::make_pair(
+ Point<float>(
+ (((p[0] / p[3] + 1) / 2) * transformState.getSize().width) + viewportPadding,
+ (((-p[1] / p[3] + 1) / 2) * transformState.getSize().height) + viewportPadding
+ ),
+ 0.5 + 0.5 * (p[3] / transformState.getCameraToCenterDistance())
+ );
+}
+
+Point<float> CollisionIndex::projectPoint(const mat4& posMatrix, const Point<float>& point) const {
+ vec4 p = {{ point.x, point.y, 0, 1 }};
+ matrix::transformMat4(p, p, posMatrix);
+ return Point<float>(
+ (((p[0] / p[3] + 1) / 2) * transformState.getSize().width) + viewportPadding,
+ (((-p[1] / p[3] + 1) / 2) * transformState.getSize().height) + viewportPadding
+ );
+}
+
+} // namespace mbgl
diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp
new file mode 100644
index 0000000000..6f78d8aeda
--- /dev/null
+++ b/src/mbgl/text/collision_index.hpp
@@ -0,0 +1,61 @@
+#pragma once
+
+#include <mbgl/geometry/feature_index.hpp>
+#include <mbgl/text/collision_feature.hpp>
+#include <mbgl/util/grid_index.hpp>
+#include <mbgl/map/transform_state.hpp>
+
+namespace mbgl {
+
+class PlacedSymbol;
+
+struct TileDistance;
+
+class CollisionIndex {
+public:
+ using CollisionGrid = GridIndex<IndexedSubfeature>;
+
+ explicit CollisionIndex(const TransformState&);
+
+ 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 std::string& sourceID) const;
+
+
+private:
+ 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);
+
+ 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;
+
+ TransformState transformState;
+ float pitchFactor;
+
+ CollisionGrid collisionGrid;
+ CollisionGrid ignoredGrid;
+};
+
+} // namespace mbgl
View Lorry Controller Status