From 4c6f0e8138338f0d4a8d2298a053513ad30be5ea Mon Sep 17 00:00:00 2001 From: Chris Loer Date: Thu, 9 Nov 2017 13:24:43 -0800 Subject: [core] Add global CollisionIndex to replace CollisionTile. - Switches from tile to viewport coordinates - Represents line labels with circle geometries - Projects line labels at collision detection time to improve accuracy - Adapts tile-based symbol queries to viewport coordinates --- cmake/core-files.cmake | 2 + src/mbgl/text/collision_index.cpp | 338 ++++++++++++++++++++++++++++++++++++++ src/mbgl/text/collision_index.hpp | 61 +++++++ 3 files changed, 401 insertions(+) create mode 100644 src/mbgl/text/collision_index.cpp create mode 100644 src/mbgl/text/collision_index.hpp diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake index fc918b34c8..457b786a4d 100644 --- a/cmake/core-files.cmake +++ b/cmake/core-files.cmake @@ -531,6 +531,8 @@ set(MBGL_CORE_FILES src/mbgl/text/collision_feature.hpp src/mbgl/text/collision_tile.cpp src/mbgl/text/collision_tile.hpp + src/mbgl/text/collision_index.cpp + src/mbgl/text/collision_index.hpp src/mbgl/text/cross_tile_symbol_index.cpp src/mbgl/text/cross_tile_symbol_index.hpp src/mbgl/text/get_anchors.cpp 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 +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +#include // For PlacedSymbol: pull out to another location + +#include + +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 CollisionIndex::queryRenderedSymbols(const GeometryCoordinates& queryGeometry, const UnwrappedTileID& tileID, const std::string& sourceID) const { + std::vector 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 projectedQuery; + + for (const auto& point : queryGeometry) { + auto projected = projectPoint(posMatrix, convertPoint(point)); + projectedPolygon.push_back(convertPoint(projected)); + projectedQuery.push_back(projected); + } + + auto envelope = mapbox::geometry::envelope(projectedQuery); + + using QueryResult = std::pair::BBox>; + + std::vector thisTileFeatures; + std::vector 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 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> 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 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); + return std::make_pair( + Point( + (((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 CollisionIndex::projectPoint(const mat4& posMatrix, const Point& point) const { + vec4 p = {{ point.x, point.y, 0, 1 }}; + matrix::transformMat4(p, p, posMatrix); + return Point( + (((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 +#include +#include +#include + +namespace mbgl { + +class PlacedSymbol; + +struct TileDistance; + +class CollisionIndex { +public: + using CollisionGrid = GridIndex; + + 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 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 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; + + TransformState transformState; + float pitchFactor; + + CollisionGrid collisionGrid; + CollisionGrid ignoredGrid; +}; + +} // namespace mbgl -- cgit v1.2.1