summaryrefslogtreecommitdiff
path: root/src/mbgl/text
diff options
context:
space:
mode:
Diffstat (limited to 'src/mbgl/text')
-rw-r--r--src/mbgl/text/collision_feature.cpp81
-rw-r--r--src/mbgl/text/collision_feature.hpp48
-rw-r--r--src/mbgl/text/collision_index.cpp359
-rw-r--r--src/mbgl/text/collision_index.hpp70
-rw-r--r--src/mbgl/text/collision_tile.cpp267
-rw-r--r--src/mbgl/text/collision_tile.hpp71
-rw-r--r--src/mbgl/text/cross_tile_symbol_index.cpp165
-rw-r--r--src/mbgl/text/cross_tile_symbol_index.hpp64
-rw-r--r--src/mbgl/text/glyph.hpp8
-rw-r--r--src/mbgl/text/placement.cpp332
-rw-r--r--src/mbgl/text/placement.hpp91
-rw-r--r--src/mbgl/text/placement_config.hpp33
-rw-r--r--src/mbgl/text/shaping.cpp2
13 files changed, 1140 insertions, 451 deletions
diff --git a/src/mbgl/text/collision_feature.cpp b/src/mbgl/text/collision_feature.cpp
index 3eb08da8d1..6d6f2aabc7 100644
--- a/src/mbgl/text/collision_feature.cpp
+++ b/src/mbgl/text/collision_feature.cpp
@@ -13,8 +13,9 @@ CollisionFeature::CollisionFeature(const GeometryCoordinates& line,
const float padding,
const style::SymbolPlacementType placement,
IndexedSubfeature indexedFeature_,
- const AlignmentType alignment)
- : indexedFeature(std::move(indexedFeature_)) {
+ const float overscaling)
+ : 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;
@@ -22,7 +23,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;
@@ -31,29 +32,26 @@ CollisionFeature::CollisionFeature(const GeometryCoordinates& line,
height = std::max(10.0f * boxScale, height);
GeometryCoordinate anchorPoint = convertPoint<int16_t>(anchor.point);
-
- if (alignment == AlignmentType::Straight) {
- // used for icon labels that are aligned with the line, but don't curve along it
- const GeometryCoordinate vector = convertPoint<int16_t>(util::unit(convertPoint<double>(line[anchor.segment + 1] - line[anchor.segment])) * length);
- const GeometryCoordinates newLine({ anchorPoint - vector, anchorPoint + vector });
- bboxifyLabel(newLine, anchorPoint, 0, length, height);
- } else {
- // used for text labels that curve along a line
- bboxifyLabel(line, anchorPoint, anchor.segment, length, height);
- }
+ bboxifyLabel(line, anchorPoint, anchor.segment, length, height, overscaling);
} else {
- boxes.emplace_back(anchor.point, Point<float>{ 0, 0 }, x1, y1, x2, y2, std::numeric_limits<float>::infinity());
+ boxes.emplace_back(anchor.point, Point<float>{ 0, 0 }, x1, y1, x2, y2);
}
}
void CollisionFeature::bboxifyLabel(const GeometryCoordinates& line, GeometryCoordinate& anchorPoint,
- const int segment, const float labelLength, const float boxSize) {
+ const int segment, const float labelLength, const float boxSize, const float overscaling) {
const float step = boxSize / 2;
const int nBoxes = std::floor(labelLength / step);
- // We calculate line collision boxes out to 300% of what would normally be our
+ // We calculate line collision circles 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 / 2);
+ // Vertically oriented labels in the distant field can extend past this padding
+ // This is a noticeable problem in overscaled tiles where the pitch 0-based
+ // symbol spacing will put labels very close together in a pitched map.
+ // To reduce the cost of adding extra collision circles, we slowly increase
+ // them for overscaled tiles.
+ const float overscalingPaddingFactor = 1 + .4 * std::log(overscaling) / std::log(2);
+ const int nPitchPaddingBoxes = std::floor(nBoxes * overscalingPaddingFactor / 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.
@@ -124,47 +122,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<float>::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<float>(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<float>(anchorPoint), -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, paddedAnchorDistance, boxSize / 2);
}
}
-float CollisionBox::adjustedMaxScale(const std::array<float, 4>& 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<float> 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 3b6e461a26..df1b12819c 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<float> _anchor, Point<float> _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<float, 4>& rotationMatrix, const float yStretch) const;
+ CollisionBox(Point<float> _anchor, Point<float> _offset, float _x1, float _y1, float _x2, float _y2, float _signedDistanceFromAnchor = 0, float _radius = 0) :
+ anchor(std::move(_anchor)), offset(_offset), x1(_x1), y1(_y1), x2(_x2), y2(_y2), used(true), signedDistanceFromAnchor(_signedDistanceFromAnchor), radius(_radius) {}
// the box is centered around the anchor point
Point<float> anchor;
@@ -28,20 +26,23 @@ public:
float x2;
float y2;
- // the box is only valid for scales < maxScale.
- // The box does not block other boxes at scales >= maxScale;
- float maxScale;
+ // Projected box geometry: generated/updated at placement time
+ float px1;
+ float py1;
+ float px2;
+ float py2;
+
+ // Projected circle geometry: generated/updated at placement time
+ float px;
+ float py;
+ bool used;
- // the scale at which the label can first be shown
- float placementScale = 0.0f;
+ float signedDistanceFromAnchor;
+ float radius;
};
class CollisionFeature {
public:
- enum class AlignmentType : bool {
- Straight = false,
- Curved
- };
// for text
CollisionFeature(const GeometryCoordinates& line,
@@ -50,23 +51,31 @@ public:
const float boxScale,
const float padding,
const style::SymbolPlacementType placement,
- const IndexedSubfeature& indexedFeature_)
- : CollisionFeature(line, anchor, shapedText.top, shapedText.bottom, shapedText.left, shapedText.right, boxScale, padding, placement, indexedFeature_, AlignmentType::Curved) {}
+ const IndexedSubfeature& indexedFeature_,
+ const float overscaling)
+ : CollisionFeature(line, anchor, shapedText.top, shapedText.bottom, shapedText.left, shapedText.right, boxScale, padding, placement, indexedFeature_, overscaling) {}
// for icons
+ // Icons collision features are always SymbolPlacementType::Point, which means the collision feature
+ // will be viewport-rotation-aligned even if the icon is map-rotation-aligned (e.g. `icon-rotation-alignment: map`
+ // _or_ `symbol-placement: line`). We're relying on most icons being "close enough" to square that having
+ // incorrect rotation alignment doesn't throw off collision detection too much.
+ // See: https://github.com/mapbox/mapbox-gl-js/issues/4861
CollisionFeature(const GeometryCoordinates& line,
const Anchor& anchor,
optional<PositionedIcon> shapedIcon,
const float boxScale,
const float padding,
- const style::SymbolPlacementType placement,
const IndexedSubfeature& indexedFeature_)
: CollisionFeature(line, anchor,
(shapedIcon ? shapedIcon->top() : 0),
(shapedIcon ? shapedIcon->bottom() : 0),
(shapedIcon ? shapedIcon->left() : 0),
(shapedIcon ? shapedIcon->right() : 0),
- boxScale, padding, placement, indexedFeature_, AlignmentType::Straight) {}
+ boxScale,
+ padding,
+ style::SymbolPlacementType::Point,
+ indexedFeature_, 1) {}
CollisionFeature(const GeometryCoordinates& line,
const Anchor&,
@@ -78,14 +87,15 @@ public:
const float padding,
const style::SymbolPlacementType,
IndexedSubfeature,
- const AlignmentType);
+ const float overscaling);
std::vector<CollisionBox> boxes;
IndexedSubfeature indexedFeature;
+ bool alongLine;
private:
void bboxifyLabel(const GeometryCoordinates& line, GeometryCoordinate& anchorPoint,
- const int segment, const float length, const float height);
+ const int segment, const float length, const float height, const float overscaling);
};
} // namespace mbgl
diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp
new file mode 100644
index 0000000000..fee28b5873
--- /dev/null
+++ b/src/mbgl/text/collision_index.cpp
@@ -0,0 +1,359 @@
+#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)
+ , screenRightBoundary(transformState.getSize().width + viewportPadding)
+ , screenBottomBoundary(transformState.getSize().height + viewportPadding)
+ , gridRightBoundary(transformState.getSize().width + 2 * viewportPadding)
+ , gridBottomBoundary(transformState.getSize().height + 2 * viewportPadding)
+ , 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::isOffscreen(const CollisionBox& box) const {
+ return box.px2 < viewportPadding || box.px1 >= screenRightBoundary || box.py2 < viewportPadding || box.py1 >= screenBottomBoundary;
+}
+
+bool CollisionIndex::isInsideGrid(const CollisionBox& box) const {
+ return box.px2 >= 0 && box.px1 < gridRightBoundary && box.py2 >= 0 && box.py1 < gridBottomBoundary;
+}
+
+
+std::pair<bool,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 (!isInsideGrid(box) ||
+ (!allowOverlap && collisionGrid.hitTest({{ box.px1, box.py1 }, { box.px2, box.py2 }}))) {
+ return { false, false };
+ }
+
+ return {true, isOffscreen(box)};
+ } else {
+ return placeLineFeature(feature, posMatrix, labelPlaneMatrix, textPixelRatio, symbol, scale, fontSize, allowOverlap, pitchWithMap, collisionDebug);
+ }
+}
+
+std::pair<bool,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;
+ bool inGrid = false;
+ bool entirelyOffscreen = true;
+
+ 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;
+
+ entirelyOffscreen &= isOffscreen(circle);
+ inGrid |= isInsideGrid(circle);
+
+ if (!allowOverlap) {
+ if (collisionGrid.hitTest({{circle.px, circle.py}, circle.radius})) {
+ if (!collisionDebug) {
+ return {false, 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 && inGrid, entirelyOffscreen};
+}
+
+
+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 }});
+ }
+ }
+}
+
+bool polygonIntersectsBox(const LineString<float>& polygon, const GridIndex<IndexedSubfeature>::BBox& bbox) {
+ // This is just a wrapper that allows us to use the integer-based util::polygonIntersectsPolygon
+ // Conversion limits our query accuracy to single-pixel resolution
+ GeometryCoordinates integerPolygon;
+ for (const auto& point : polygon) {
+ integerPolygon.push_back(convertPoint<int16_t>(point));
+ }
+ 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 }
+ };
+
+ return util::polygonIntersectsPolygon(integerPolygon, bboxPoints);
+}
+
+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);
+
+ // queryGeometry is specified in integer tile units, but in projecting we switch to float pixels
+ LineString<float> projectedQuery;
+ for (const auto& point : queryGeometry) {
+ auto projected = projectPoint(posMatrix, convertPoint<float>(point));
+ 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;
+ if (feature.sourceID == sourceID && feature.tileID == 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;
+ if (feature.sourceID == sourceID && feature.tileID == 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);
+
+ if (!polygonIntersectsBox(projectedQuery, bbox)) {
+ 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..8653c1d76c
--- /dev/null
+++ b/src/mbgl/text/collision_index.hpp
@@ -0,0 +1,70 @@
+#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&);
+
+ std::pair<bool,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 isOffscreen(const CollisionBox&) const;
+ bool isInsideGrid(const CollisionBox&) const;
+
+ std::pair<bool,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;
+
+ const TransformState transformState;
+
+ CollisionGrid collisionGrid;
+ CollisionGrid ignoredGrid;
+
+ const float screenRightBoundary;
+ const float screenBottomBoundary;
+ const float gridRightBoundary;
+ const float gridBottomBoundary;
+
+ const float pitchFactor;
+};
+
+} // namespace mbgl
diff --git a/src/mbgl/text/collision_tile.cpp b/src/mbgl/text/collision_tile.cpp
deleted file mode 100644
index cc9b602f08..0000000000
--- a/src/mbgl/text/collision_tile.cpp
+++ /dev/null
@@ -1,267 +0,0 @@
-#include <mbgl/text/collision_tile.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 <mapbox/geometry/envelope.hpp>
-#include <mapbox/geometry/multi_point.hpp>
-
-#include <cmath>
-
-namespace mbgl {
-
-CollisionTile::CollisionTile(PlacementConfig config_) : config(std::move(config_)) {
- // Compute the transformation matrix.
- const float angle_sin = std::sin(config.angle);
- const float angle_cos = std::cos(config.angle);
- rotationMatrix = { { angle_cos, -angle_sin, angle_sin, angle_cos } };
- reverseRotationMatrix = { { angle_cos, angle_sin, -angle_sin, angle_cos } };
-
- 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 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:
-
- 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));
-
- if (collisionFreeScale > blocking.maxScale) {
- // After a box's maxScale the label has shrunk enough that the box is no longer needed to cover it,
- // so unblock the new box at the scale that the old box disappears.
- collisionFreeScale = blocking.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 = boxMaxScale;
- }
-
- if (collisionFreeScale > minPlacementScale &&
- collisionFreeScale >= blocking.placementScale) {
- // If this collision occurs at a lower scale than previously found collisions
- // and the collision occurs while the other label is visible
-
- // this this is the lowest scale at which the label won't collide with anything
- minPlacementScale = collisionFreeScale;
- }
-
- return minPlacementScale;
-}
-
-float CollisionTile::placeFeature(const CollisionFeature& feature, bool allowOverlap, bool avoidEdges) {
- static const float infinity = std::numeric_limits<float>::infinity();
- static const std::array<CollisionBox, 4> edges {{
- // left
- CollisionBox(Point<float>(0, 0), { 0, 0 }, 0, -infinity, 0, infinity, infinity),
- // right
- CollisionBox(Point<float>(util::EXTENT, 0), { 0, 0 }, 0, -infinity, 0, infinity, infinity),
- // top
- CollisionBox(Point<float>(0, 0), { 0, 0 }, -infinity, 0, infinity, 0, infinity),
- // bottom
- CollisionBox(Point<float>(0, util::EXTENT), { 0, 0 }, -infinity, 0, infinity, 0, infinity)
- }};
-
- float minPlacementScale = minScale;
-
- 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, boxMaxScale, blockingAnchor, blocking));
- if (minPlacementScale >= maxScale) return minPlacementScale;
- }
- }
-
- if (avoidEdges) {
- const Point<float> rtl = util::matrixMultiply(reverseRotationMatrix, { box.x1, box.y1 });
- const Point<float> rtr = util::matrixMultiply(reverseRotationMatrix, { box.x2, box.y1 });
- 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),
- boxMaxScale);
-
- for (auto& blocking : edges) {
- minPlacementScale = util::max(minPlacementScale, findPlacementScale(box.anchor, rotatedBox, boxMaxScale, blocking.anchor, blocking));
- if (minPlacementScale >= maxScale) return minPlacementScale;
- }
- }
- }
-
- return minPlacementScale;
-}
-
-void CollisionTile::insertFeature(CollisionFeature& feature, float minPlacementScale, bool ignorePlacement) {
- for (auto& box : feature.boxes) {
- box.placementScale = minPlacementScale;
- }
-
- if (minPlacementScale < maxScale) {
- std::vector<CollisionTreeBox> treeBoxes;
- for (auto& box : feature.boxes) {
- 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());
- } else {
- tree.insert(treeBoxes.begin(), treeBoxes.end());
- }
- }
-
-}
-
-// +---------------------------+ As you zoom, the size of the symbol changes
-// |(x1,y1) | | relative to the tile e.g. when zooming in,
-// | | | the symbol gets smaller relative to the tile.
-// | (x1',y1') v |
-// | +-------+-------+ | The boxes inserted into the tree represents
-// | | | | | the bounds at the integer zoom level (where
-// | | | | | the symbol is biggest relative to the tile).
-// | | | | |
-// |---->+-------+-------+<----| This happens because placement is updated
-// | | |(xa,ya)| | once every new integer zoom level e.g.
-// | | | | | std::floor(oldZoom) != std::floor(newZoom).
-// | | | | |
-// | +-------+-------+ | Thus, they don't represent the exact bounds
-// | ^ (x2',y2') | of the symbol at the current zoom level. For
-// | | | calculating the bounds at current zoom level
-// | | (x2,y2)| we must unscale the box using its center as
-// +---------------------------+ transform origin.
-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 * perspectiveRatio,
- anchor.y + box.y1 / scale * yStretch * perspectiveRatio,
- },
- CollisionPoint{
- anchor.x + box.x2 / scale * perspectiveRatio,
- anchor.y + box.y2 / scale * yStretch * perspectiveRatio
- }
- };
-}
-
-std::vector<IndexedSubfeature> CollisionTile::queryRenderedSymbols(const GeometryCoordinates& queryGeometry, float scale) const {
- std::vector<IndexedSubfeature> result;
- if (queryGeometry.empty() || (tree.empty() && ignoredTree.empty())) {
- return result;
- }
-
- // Generate a rotated geometry out of the original query geometry.
- // Scale has already been handled by the prior conversions.
- GeometryCoordinates polygon;
- for (const auto& point : queryGeometry) {
- auto rotated = util::matrixMultiply(rotationMatrix, convertPoint<float>(point));
- polygon.push_back(convertPoint<int16_t>(rotated));
- }
-
- // Predicate for ruling out already seen features.
- std::unordered_map<std::string, std::unordered_set<std::size_t>> sourceLayerFeatures;
- auto seenFeature = [&] (const CollisionTreeBox& treeBox) -> bool {
- const IndexedSubfeature& feature = std::get<2>(treeBox);
- const auto& seenFeatures = sourceLayerFeatures[feature.sourceLayerName];
- 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(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.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 / 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 }
- };
- return util::polygonIntersectsPolygon(polygon, bbox);
- };
-
- auto predicates = bgi::satisfies(seenFeature)
- && bgi::satisfies(visibleAtScale)
- && bgi::satisfies(intersectsAtScale);
-
- auto queryTree = [&](const auto& tree_) {
- for (auto it = tree_.qbegin(predicates); it != tree_.qend(); ++it) {
- const IndexedSubfeature& feature = std::get<2>(*it);
- auto& seenFeatures = sourceLayerFeatures[feature.sourceLayerName];
- seenFeatures.insert(feature.index);
- result.push_back(feature);
- }
- };
-
- queryTree(tree);
- queryTree(ignoredTree);
-
- return result;
-}
-
-} // namespace mbgl
diff --git a/src/mbgl/text/collision_tile.hpp b/src/mbgl/text/collision_tile.hpp
deleted file mode 100644
index 9868266aa2..0000000000
--- a/src/mbgl/text/collision_tile.hpp
+++ /dev/null
@@ -1,71 +0,0 @@
-#pragma once
-
-#include <mbgl/text/collision_feature.hpp>
-#include <mbgl/text/placement_config.hpp>
-#include <mbgl/tile/geometry_tile_data.hpp>
-
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wunused-function"
-#pragma GCC diagnostic ignored "-Wunused-parameter"
-#pragma GCC diagnostic ignored "-Wunused-variable"
-#pragma GCC diagnostic ignored "-Wshadow"
-#ifdef __clang__
-#pragma GCC diagnostic ignored "-Wunknown-pragmas"
-#endif
-#pragma GCC diagnostic ignored "-Wpragmas"
-#pragma GCC diagnostic ignored "-Wdeprecated-register"
-#pragma GCC diagnostic ignored "-Wshorten-64-to-32"
-#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
-#ifndef __clang__
-#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
-#pragma GCC diagnostic ignored "-Wmisleading-indentation"
-#endif
-#include <boost/geometry.hpp>
-#include <boost/geometry/geometries/point.hpp>
-#include <boost/geometry/geometries/box.hpp>
-#include <boost/geometry/index/rtree.hpp>
-#pragma GCC diagnostic pop
-
-namespace mbgl {
-
-namespace bg = boost::geometry;
-namespace bgm = bg::model;
-namespace bgi = bg::index;
-using CollisionPoint = bgm::point<float, 2, bg::cs::cartesian>;
-using Box = bgm::box<CollisionPoint>;
-using CollisionTreeBox = std::tuple<Box, CollisionBox, IndexedSubfeature>;
-using Tree = bgi::rtree<CollisionTreeBox, bgi::linear<16, 4>>;
-
-class IndexedSubfeature;
-
-class CollisionTile {
-public:
- explicit CollisionTile(PlacementConfig);
-
- float placeFeature(const CollisionFeature&, bool allowOverlap, bool avoidEdges);
- void insertFeature(CollisionFeature&, float minPlacementScale, bool ignorePlacement);
-
- std::vector<IndexedSubfeature> queryRenderedSymbols(const GeometryCoordinates&, float scale) const;
-
- const PlacementConfig config;
-
- float minScale = 0.5f;
- float maxScale = 2.0f;
- float yStretch;
-
- std::array<float, 4> rotationMatrix;
- std::array<float, 4> reverseRotationMatrix;
-
-private:
- float findPlacementScale(
- const Point<float>& anchor, const CollisionBox& box, const float boxMaxScale,
- const Point<float>& blockingAnchor, const CollisionBox& blocking);
- Box getTreeBox(const Point<float>& anchor, const CollisionBox& box, const float scale = 1.0);
-
- Tree tree;
- Tree ignoredTree;
-
- float perspectiveRatio;
-};
-
-} // namespace mbgl
diff --git a/src/mbgl/text/cross_tile_symbol_index.cpp b/src/mbgl/text/cross_tile_symbol_index.cpp
new file mode 100644
index 0000000000..177615857f
--- /dev/null
+++ b/src/mbgl/text/cross_tile_symbol_index.cpp
@@ -0,0 +1,165 @@
+#include <mbgl/text/cross_tile_symbol_index.hpp>
+#include <mbgl/layout/symbol_instance.hpp>
+#include <mbgl/renderer/buckets/symbol_bucket.hpp>
+#include <mbgl/renderer/render_tile.hpp>
+#include <mbgl/tile/tile.hpp>
+
+namespace mbgl {
+
+
+TileLayerIndex::TileLayerIndex(OverscaledTileID coord_, std::vector<SymbolInstance>& symbolInstances, uint32_t bucketInstanceId_)
+ : coord(coord_), bucketInstanceId(bucketInstanceId_) {
+ for (SymbolInstance& symbolInstance : symbolInstances) {
+ indexedSymbolInstances[symbolInstance.key].emplace_back(symbolInstance.crossTileID, getScaledCoordinates(symbolInstance, coord));
+ }
+ }
+
+Point<int64_t> TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstance, const OverscaledTileID& childTileCoord) {
+ // Round anchor positions to roughly 4 pixel grid
+ const double roundingFactor = 512.0 / util::EXTENT / 2.0;
+ const double scale = roundingFactor / std::pow(2, childTileCoord.canonical.z - coord.canonical.z);
+ return {
+ static_cast<int64_t>(std::floor((childTileCoord.canonical.x * util::EXTENT + symbolInstance.anchor.point.x) * scale)),
+ static_cast<int64_t>(std::floor((childTileCoord.canonical.y * util::EXTENT + symbolInstance.anchor.point.y) * scale))
+ };
+}
+
+void TileLayerIndex::findMatches(std::vector<SymbolInstance>& symbolInstances, const OverscaledTileID& newCoord) {
+ float tolerance = coord.canonical.z < newCoord.canonical.z ? 1 : std::pow(2, coord.canonical.z - newCoord.canonical.z);
+
+ for (auto& symbolInstance : symbolInstances) {
+ if (symbolInstance.crossTileID) {
+ // already has a match, skip
+ continue;
+ }
+
+ auto it = indexedSymbolInstances.find(symbolInstance.key);
+ if (it == indexedSymbolInstances.end()) {
+ // No symbol with this key in this bucket
+ continue;
+ }
+
+ auto scaledSymbolCoord = getScaledCoordinates(symbolInstance, newCoord);
+
+ for (IndexedSymbolInstance& thisTileSymbol: it->second) {
+ // Return any symbol with the same keys whose coordinates are within 1
+ // grid unit. (with a 4px grid, this covers a 12px by 12px area)
+ if (std::abs(thisTileSymbol.coord.x - scaledSymbolCoord.x) <= tolerance &&
+ std::abs(thisTileSymbol.coord.y - scaledSymbolCoord.y) <= tolerance) {
+
+ symbolInstance.crossTileID = thisTileSymbol.crossTileID;
+ break;
+ }
+ }
+ }
+}
+
+CrossTileSymbolLayerIndex::CrossTileSymbolLayerIndex() {
+}
+
+void CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& coord, SymbolBucket& bucket, uint32_t& maxCrossTileID) {
+ if (bucket.bucketInstanceId) return;
+ bucket.bucketInstanceId = ++maxBucketInstanceId;
+
+ uint8_t minZoom = 25;
+ uint8_t maxZoom = 0;
+ for (auto& it : indexes) {
+ auto z = it.first;
+ minZoom = std::min(minZoom, z);
+ maxZoom = std::max(maxZoom, z);
+ }
+
+
+ // make all higher-res child tiles block duplicate labels in this tile
+ for (auto z = maxZoom; z > coord.overscaledZ; z--) {
+ auto zoomIndexes = indexes.find(z);
+ if (zoomIndexes != indexes.end()) {
+ for (auto& childIndex : zoomIndexes->second) {
+ if (!childIndex.second.coord.isChildOf(coord)) {
+ continue;
+ }
+ childIndex.second.findMatches(bucket.symbolInstances, coord);
+ }
+ }
+ if (z == 0) {
+ break;
+ }
+ }
+
+ // make this tile block duplicate labels in lower-res parent tiles
+ for (auto z = coord.overscaledZ; z >= minZoom; z--) {
+ auto parentCoord = coord.scaledTo(z);
+ auto zoomIndexes = indexes.find(z);
+ if (zoomIndexes != indexes.end()) {
+ auto parentIndex = zoomIndexes->second.find(parentCoord);
+ if (parentIndex != zoomIndexes->second.end()) {
+ parentIndex->second.findMatches(bucket.symbolInstances, coord);
+ }
+ }
+ if (z == 0) {
+ break;
+ }
+ }
+
+ for (auto& symbolInstance : bucket.symbolInstances) {
+ if (!symbolInstance.crossTileID) {
+ // symbol did not match any known symbol, assign a new id
+ symbolInstance.crossTileID = ++maxCrossTileID;
+ }
+ }
+
+ indexes[coord.overscaledZ].emplace(coord, TileLayerIndex(coord, bucket.symbolInstances, bucket.bucketInstanceId));
+}
+
+bool CrossTileSymbolLayerIndex::removeStaleBuckets(const std::unordered_set<uint32_t>& currentIDs) {
+ bool tilesChanged = false;
+ for (auto& zoomIndexes : indexes) {
+ for (auto it = zoomIndexes.second.begin(); it != zoomIndexes.second.end();) {
+ if (!currentIDs.count(it->second.bucketInstanceId)) {
+ it = zoomIndexes.second.erase(it);
+ tilesChanged = true;
+ } else {
+ ++it;
+ }
+ }
+ }
+ return tilesChanged;
+}
+
+CrossTileSymbolIndex::CrossTileSymbolIndex() {}
+
+bool CrossTileSymbolIndex::addLayer(RenderSymbolLayer& symbolLayer) {
+
+ auto& layerIndex = layerIndexes[symbolLayer.getID()];
+
+ bool symbolBucketsChanged = false;
+ std::unordered_set<uint32_t> currentBucketIDs;
+
+ for (RenderTile& renderTile : symbolLayer.renderTiles) {
+ if (!renderTile.tile.isRenderable()) {
+ continue;
+ }
+
+ auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl);
+ assert(dynamic_cast<SymbolBucket*>(bucket));
+ SymbolBucket& symbolBucket = *reinterpret_cast<SymbolBucket*>(bucket);
+
+ if (!symbolBucket.bucketInstanceId) {
+ symbolBucketsChanged = true;
+ }
+ layerIndex.addBucket(renderTile.tile.id, symbolBucket, maxCrossTileID);
+ currentBucketIDs.insert(symbolBucket.bucketInstanceId);
+ }
+
+ if (layerIndex.removeStaleBuckets(currentBucketIDs)) {
+ symbolBucketsChanged = true;
+ }
+ return symbolBucketsChanged;
+}
+
+void CrossTileSymbolIndex::reset() {
+ layerIndexes.clear();
+}
+
+} // namespace mbgl
+
diff --git a/src/mbgl/text/cross_tile_symbol_index.hpp b/src/mbgl/text/cross_tile_symbol_index.hpp
new file mode 100644
index 0000000000..c67cd37e00
--- /dev/null
+++ b/src/mbgl/text/cross_tile_symbol_index.hpp
@@ -0,0 +1,64 @@
+#pragma once
+
+#include <mbgl/tile/tile_id.hpp>
+#include <mbgl/util/geometry.hpp>
+#include <mbgl/util/constants.hpp>
+#include <mbgl/util/optional.hpp>
+
+#include <map>
+#include <vector>
+#include <string>
+#include <memory>
+#include <unordered_set>
+
+namespace mbgl {
+
+class SymbolInstance;
+class RenderSymbolLayer;
+class SymbolBucket;
+
+class IndexedSymbolInstance {
+public:
+ IndexedSymbolInstance(uint32_t crossTileID_, Point<int64_t> coord_)
+ : crossTileID(crossTileID_), coord(coord_)
+ {}
+
+ uint32_t crossTileID;
+ Point<int64_t> coord;
+};
+
+class TileLayerIndex {
+public:
+ TileLayerIndex(OverscaledTileID coord, std::vector<SymbolInstance>&, uint32_t bucketInstanceId);
+
+ Point<int64_t> getScaledCoordinates(SymbolInstance&, const OverscaledTileID&);
+ void findMatches(std::vector<SymbolInstance>&, const OverscaledTileID&);
+
+ OverscaledTileID coord;
+ uint32_t bucketInstanceId;
+ std::map<std::u16string,std::vector<IndexedSymbolInstance>> indexedSymbolInstances;
+};
+
+class CrossTileSymbolLayerIndex {
+public:
+ CrossTileSymbolLayerIndex();
+ void addBucket(const OverscaledTileID&, SymbolBucket&, uint32_t& maxCrossTileID);
+ bool removeStaleBuckets(const std::unordered_set<uint32_t>& currentIDs);
+private:
+ std::map<uint8_t,std::map<OverscaledTileID,TileLayerIndex>> indexes;
+ uint32_t maxBucketInstanceId = 0;
+};
+
+class CrossTileSymbolIndex {
+public:
+ CrossTileSymbolIndex();
+
+ bool addLayer(RenderSymbolLayer&);
+
+ void reset();
+private:
+ std::map<std::string, CrossTileSymbolLayerIndex> layerIndexes;
+ uint32_t maxCrossTileID = 0;
+};
+
+} // namespace mbgl
diff --git a/src/mbgl/text/glyph.hpp b/src/mbgl/text/glyph.hpp
index 6cccb72ebe..08ff82a20a 100644
--- a/src/mbgl/text/glyph.hpp
+++ b/src/mbgl/text/glyph.hpp
@@ -75,10 +75,10 @@ class Shaping {
explicit Shaping(float x, float y, WritingModeType writingMode_)
: top(y), bottom(y), left(x), right(x), writingMode(writingMode_) {}
std::vector<PositionedGlyph> positionedGlyphs;
- int32_t top = 0;
- int32_t bottom = 0;
- int32_t left = 0;
- int32_t right = 0;
+ float top = 0;
+ float bottom = 0;
+ float left = 0;
+ float right = 0;
WritingModeType writingMode;
explicit operator bool() const { return !positionedGlyphs.empty(); }
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
new file mode 100644
index 0000000000..9284e213c2
--- /dev/null
+++ b/src/mbgl/text/placement.cpp
@@ -0,0 +1,332 @@
+#include <mbgl/text/placement.hpp>
+#include <mbgl/renderer/render_layer.hpp>
+#include <mbgl/renderer/layers/render_symbol_layer.hpp>
+#include <mbgl/renderer/render_tile.hpp>
+#include <mbgl/tile/geometry_tile.cpp>
+#include <mbgl/renderer/buckets/symbol_bucket.hpp>
+#include <mbgl/renderer/bucket.hpp>
+
+namespace mbgl {
+
+OpacityState::OpacityState(bool placed_, bool offscreen)
+ : opacity((offscreen && placed_) ? 1 : 0)
+ , placed(placed_)
+{
+}
+
+OpacityState::OpacityState(const OpacityState& prevState, float increment, bool placed_) :
+ opacity(std::fmax(0, std::fmin(1, prevState.opacity + (prevState.placed ? increment : -increment)))),
+ placed(placed_) {}
+
+bool OpacityState::isHidden() const {
+ return opacity == 0 && !placed;
+}
+
+JointOpacityState::JointOpacityState(bool placedIcon, bool placedText, bool offscreen) :
+ icon(OpacityState(placedIcon, offscreen)),
+ text(OpacityState(placedText, offscreen)) {}
+
+JointOpacityState::JointOpacityState(const JointOpacityState& prevOpacityState, float increment, bool placedIcon, bool placedText) :
+ icon(OpacityState(prevOpacityState.icon, increment, placedIcon)),
+ text(OpacityState(prevOpacityState.text, increment, placedText)) {}
+
+bool JointOpacityState::isHidden() const {
+ return icon.isHidden() && text.isHidden();
+}
+
+Placement::Placement(const TransformState& state_, MapMode mapMode_)
+ : collisionIndex(state_)
+ , state(state_)
+ , mapMode(mapMode_)
+ , recentUntil(TimePoint::min())
+{}
+
+void Placement::placeLayer(RenderSymbolLayer& symbolLayer, const mat4& projMatrix, bool showCollisionBoxes) {
+
+ std::unordered_set<uint32_t> seenCrossTileIDs;
+
+ for (RenderTile& renderTile : symbolLayer.renderTiles) {
+ if (!renderTile.tile.isRenderable()) {
+ continue;
+ }
+
+ auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl);
+ assert(dynamic_cast<SymbolBucket*>(bucket));
+ SymbolBucket& symbolBucket = *reinterpret_cast<SymbolBucket*>(bucket);
+
+ auto& layout = symbolBucket.layout;
+
+ const float pixelsToTileUnits = renderTile.id.pixelsToTileUnits(1, state.getZoom());
+
+ const float scale = std::pow(2, state.getZoom() - renderTile.tile.id.overscaledZ);
+ const float textPixelRatio = util::EXTENT / (util::tileSize * renderTile.tile.id.overscaleFactor());
+
+ mat4 posMatrix;
+ state.matrixFor(posMatrix, renderTile.id);
+ matrix::multiply(posMatrix, projMatrix, posMatrix);
+
+ mat4 textLabelPlaneMatrix = getLabelPlaneMatrix(posMatrix,
+ layout.get<TextPitchAlignment>() == style::AlignmentType::Map,
+ layout.get<TextRotationAlignment>() == style::AlignmentType::Map,
+ state,
+ pixelsToTileUnits);
+
+ mat4 iconLabelPlaneMatrix = getLabelPlaneMatrix(posMatrix,
+ layout.get<IconPitchAlignment>() == style::AlignmentType::Map,
+ layout.get<IconRotationAlignment>() == style::AlignmentType::Map,
+ state,
+ pixelsToTileUnits);
+
+ placeLayerBucket(symbolBucket, posMatrix, textLabelPlaneMatrix, iconLabelPlaneMatrix, scale, textPixelRatio, showCollisionBoxes, seenCrossTileIDs, renderTile.tile.holdForFade());
+ }
+}
+
+void Placement::placeLayerBucket(
+ SymbolBucket& bucket,
+ const mat4& posMatrix,
+ const mat4& textLabelPlaneMatrix,
+ const mat4& iconLabelPlaneMatrix,
+ const float scale,
+ const float textPixelRatio,
+ const bool showCollisionBoxes,
+ std::unordered_set<uint32_t>& seenCrossTileIDs,
+ const bool holdingForFade) {
+
+ auto partiallyEvaluatedTextSize = bucket.textSizeBinder->evaluateForZoom(state.getZoom());
+ auto partiallyEvaluatedIconSize = bucket.iconSizeBinder->evaluateForZoom(state.getZoom());
+
+ const bool iconWithoutText = !bucket.hasTextData() || bucket.layout.get<TextOptional>();
+ const bool textWithoutIcon = !bucket.hasIconData() || bucket.layout.get<IconOptional>();
+
+ for (auto& symbolInstance : bucket.symbolInstances) {
+
+ if (seenCrossTileIDs.count(symbolInstance.crossTileID) == 0) {
+ if (holdingForFade) {
+ // Mark all symbols from this tile as "not placed", but don't add to seenCrossTileIDs, because we don't
+ // know yet if we have a duplicate in a parent tile that _should_ be placed.
+ placements.emplace(symbolInstance.crossTileID, JointPlacement(false, false, false));
+ continue;
+ }
+
+ bool placeText = false;
+ bool placeIcon = false;
+ bool offscreen = true;
+
+ if (symbolInstance.placedTextIndex) {
+ PlacedSymbol& placedSymbol = bucket.text.placedSymbols.at(*symbolInstance.placedTextIndex);
+ const float fontSize = evaluateSizeForFeature(partiallyEvaluatedTextSize, placedSymbol);
+
+ auto placed = collisionIndex.placeFeature(symbolInstance.textCollisionFeature,
+ posMatrix, textLabelPlaneMatrix, textPixelRatio,
+ placedSymbol, scale, fontSize,
+ bucket.layout.get<TextAllowOverlap>(),
+ bucket.layout.get<TextPitchAlignment>() == style::AlignmentType::Map,
+ showCollisionBoxes);
+ placeText = placed.first;
+ offscreen &= placed.second;
+ }
+
+ if (symbolInstance.placedIconIndex) {
+ PlacedSymbol& placedSymbol = bucket.icon.placedSymbols.at(*symbolInstance.placedIconIndex);
+ const float fontSize = evaluateSizeForFeature(partiallyEvaluatedIconSize, placedSymbol);
+
+ auto placed = collisionIndex.placeFeature(symbolInstance.iconCollisionFeature,
+ posMatrix, iconLabelPlaneMatrix, textPixelRatio,
+ placedSymbol, scale, fontSize,
+ bucket.layout.get<IconAllowOverlap>(),
+ bucket.layout.get<IconPitchAlignment>() == style::AlignmentType::Map,
+ showCollisionBoxes);
+ placeIcon = placed.first;
+ offscreen &= placed.second;
+ }
+
+ // combine placements for icon and text
+ if (!iconWithoutText && !textWithoutIcon) {
+ placeText = placeIcon = placeText && placeIcon;
+ } else if (!textWithoutIcon) {
+ placeText = placeText && placeIcon;
+ } else if (!iconWithoutText) {
+ placeIcon = placeText && placeIcon;
+ }
+
+ if (placeText) {
+ collisionIndex.insertFeature(symbolInstance.textCollisionFeature, bucket.layout.get<TextIgnorePlacement>());
+ }
+
+ if (placeIcon) {
+ collisionIndex.insertFeature(symbolInstance.iconCollisionFeature, bucket.layout.get<IconIgnorePlacement>());
+ }
+
+ assert(symbolInstance.crossTileID != 0);
+
+ if (placements.find(symbolInstance.crossTileID) != placements.end()) {
+ // If there's a previous placement with this ID, it comes from a tile that's fading out
+ // Erase it so that the placement result from the non-fading tile supersedes it
+ placements.erase(symbolInstance.crossTileID);
+ }
+
+ placements.emplace(symbolInstance.crossTileID, JointPlacement(placeText, placeIcon, offscreen));
+ seenCrossTileIDs.insert(symbolInstance.crossTileID);
+ }
+ }
+}
+
+bool Placement::commit(const Placement& prevPlacement, TimePoint now) {
+ commitTime = now;
+
+ bool placementChanged = false;
+
+ float increment = mapMode == MapMode::Continuous ?
+ std::chrono::duration<float>(commitTime - prevPlacement.commitTime) / Duration(std::chrono::milliseconds(300)) :
+ 1.0;
+
+ // add the opacities from the current placement, and copy their current values from the previous placement
+ for (auto& jointPlacement : placements) {
+ auto prevOpacity = prevPlacement.opacities.find(jointPlacement.first);
+ if (prevOpacity != prevPlacement.opacities.end()) {
+ opacities.emplace(jointPlacement.first, JointOpacityState(prevOpacity->second, increment, jointPlacement.second.icon, jointPlacement.second.text));
+ placementChanged = placementChanged ||
+ jointPlacement.second.icon != prevOpacity->second.icon.placed ||
+ jointPlacement.second.text != prevOpacity->second.text.placed;
+ } else {
+ opacities.emplace(jointPlacement.first, JointOpacityState(jointPlacement.second.icon, jointPlacement.second.text, jointPlacement.second.offscreen));
+ placementChanged = placementChanged || jointPlacement.second.icon || jointPlacement.second.text;
+ }
+ }
+
+ // copy and update values from the previous placement that aren't in the current placement but haven't finished fading
+ for (auto& prevOpacity : prevPlacement.opacities) {
+ if (opacities.find(prevOpacity.first) == opacities.end()) {
+ JointOpacityState jointOpacity(prevOpacity.second, increment, false, false);
+ if (!jointOpacity.isHidden()) {
+ opacities.emplace(prevOpacity.first, jointOpacity);
+ placementChanged = placementChanged || prevOpacity.second.icon.placed || prevOpacity.second.text.placed;
+ }
+ }
+ }
+
+ return placementChanged;
+}
+
+void Placement::updateLayerOpacities(RenderSymbolLayer& symbolLayer) {
+ std::set<uint32_t> seenCrossTileIDs;
+ for (RenderTile& renderTile : symbolLayer.renderTiles) {
+ if (!renderTile.tile.isRenderable()) {
+ continue;
+ }
+
+ auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl);
+ assert(dynamic_cast<SymbolBucket*>(bucket));
+ SymbolBucket& symbolBucket = *reinterpret_cast<SymbolBucket*>(bucket);
+ updateBucketOpacities(symbolBucket, seenCrossTileIDs);
+ }
+}
+
+void Placement::updateBucketOpacities(SymbolBucket& bucket, std::set<uint32_t>& seenCrossTileIDs) {
+ if (bucket.hasTextData()) bucket.text.opacityVertices.clear();
+ if (bucket.hasIconData()) bucket.icon.opacityVertices.clear();
+ if (bucket.hasCollisionBoxData()) bucket.collisionBox.dynamicVertices.clear();
+ if (bucket.hasCollisionCircleData()) bucket.collisionCircle.dynamicVertices.clear();
+
+ for (SymbolInstance& symbolInstance : bucket.symbolInstances) {
+ auto opacityState = seenCrossTileIDs.count(symbolInstance.crossTileID) == 0 ?
+ getOpacity(symbolInstance.crossTileID) :
+ JointOpacityState(false, false, false);
+
+ seenCrossTileIDs.insert(symbolInstance.crossTileID);
+
+ if (symbolInstance.hasText) {
+ auto opacityVertex = SymbolOpacityAttributes::vertex(opacityState.text.placed, opacityState.text.opacity);
+ for (size_t i = 0; i < symbolInstance.horizontalGlyphQuads.size() * 4; i++) {
+ bucket.text.opacityVertices.emplace_back(opacityVertex);
+ }
+ for (size_t i = 0; i < symbolInstance.verticalGlyphQuads.size() * 4; i++) {
+ bucket.text.opacityVertices.emplace_back(opacityVertex);
+ }
+ if (symbolInstance.placedTextIndex) {
+ bucket.text.placedSymbols[*symbolInstance.placedTextIndex].hidden = opacityState.isHidden();
+ }
+ if (symbolInstance.placedVerticalTextIndex) {
+ bucket.text.placedSymbols[*symbolInstance.placedVerticalTextIndex].hidden = opacityState.isHidden();
+ }
+ }
+ if (symbolInstance.hasIcon) {
+ auto opacityVertex = SymbolOpacityAttributes::vertex(opacityState.icon.placed, opacityState.icon.opacity);
+ if (symbolInstance.iconQuad) {
+ bucket.icon.opacityVertices.emplace_back(opacityVertex);
+ bucket.icon.opacityVertices.emplace_back(opacityVertex);
+ bucket.icon.opacityVertices.emplace_back(opacityVertex);
+ bucket.icon.opacityVertices.emplace_back(opacityVertex);
+ }
+ if (symbolInstance.placedIconIndex) {
+ bucket.icon.placedSymbols[*symbolInstance.placedIconIndex].hidden = opacityState.isHidden();
+ }
+ }
+
+ auto updateCollisionBox = [&](const auto& feature, const bool placed) {
+ for (const CollisionBox& box : feature.boxes) {
+ if (feature.alongLine) {
+ auto dynamicVertex = CollisionBoxDynamicAttributes::vertex(placed, !box.used);
+ bucket.collisionCircle.dynamicVertices.emplace_back(dynamicVertex);
+ bucket.collisionCircle.dynamicVertices.emplace_back(dynamicVertex);
+ bucket.collisionCircle.dynamicVertices.emplace_back(dynamicVertex);
+ bucket.collisionCircle.dynamicVertices.emplace_back(dynamicVertex);
+ } else {
+ auto dynamicVertex = CollisionBoxDynamicAttributes::vertex(placed, false);
+ bucket.collisionBox.dynamicVertices.emplace_back(dynamicVertex);
+ bucket.collisionBox.dynamicVertices.emplace_back(dynamicVertex);
+ bucket.collisionBox.dynamicVertices.emplace_back(dynamicVertex);
+ bucket.collisionBox.dynamicVertices.emplace_back(dynamicVertex);
+ }
+ }
+ };
+ updateCollisionBox(symbolInstance.textCollisionFeature, opacityState.text.placed);
+ updateCollisionBox(symbolInstance.iconCollisionFeature, opacityState.icon.placed);
+ }
+
+ bucket.updateOpacity();
+ bucket.sortFeatures(state.getAngle());
+}
+
+JointOpacityState Placement::getOpacity(uint32_t crossTileSymbolID) const {
+ auto it = opacities.find(crossTileSymbolID);
+ if (it != opacities.end()) {
+ return it->second;
+ } else {
+ return JointOpacityState(false, false, false);
+ }
+
+}
+
+float Placement::symbolFadeChange(TimePoint now) const {
+ if (mapMode == MapMode::Continuous) {
+ return std::chrono::duration<float>(now - commitTime) / Duration(std::chrono::milliseconds(300));
+ } else {
+ return 1.0;
+ }
+}
+
+bool Placement::hasTransitions(TimePoint now) const {
+ return symbolFadeChange(now) < 1.0 || stale;
+}
+
+bool Placement::stillRecent(TimePoint now) const {
+ return mapMode == MapMode::Continuous && recentUntil > now;
+}
+void Placement::setRecent(TimePoint now) {
+ stale = false;
+ if (mapMode == MapMode::Continuous) {
+ // Only set in continuous mode because "now" isn't defined in still mode
+ recentUntil = now + Duration(std::chrono::milliseconds(300));
+ }
+}
+
+void Placement::setStale() {
+ stale = true;
+}
+
+const CollisionIndex& Placement::getCollisionIndex() const {
+ return collisionIndex;
+}
+
+} // namespace mbgl
diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp
new file mode 100644
index 0000000000..bcc20f15a4
--- /dev/null
+++ b/src/mbgl/text/placement.hpp
@@ -0,0 +1,91 @@
+#pragma once
+
+#include <string>
+#include <unordered_map>
+#include <mbgl/util/chrono.hpp>
+#include <mbgl/text/collision_index.hpp>
+#include <mbgl/layout/symbol_projection.hpp>
+#include <unordered_set>
+
+namespace mbgl {
+
+class RenderSymbolLayer;
+class SymbolBucket;
+
+class OpacityState {
+public:
+ OpacityState(bool placed, bool offscreen);
+ OpacityState(const OpacityState& prevOpacityState, float increment, bool placed);
+ bool isHidden() const;
+ float opacity;
+ bool placed;
+};
+
+class JointOpacityState {
+public:
+ JointOpacityState(bool placedIcon, bool placedText, bool offscreen);
+ JointOpacityState(const JointOpacityState& prevOpacityState, float increment, bool placedIcon, bool placedText);
+ bool isHidden() const;
+ OpacityState icon;
+ OpacityState text;
+};
+
+class JointPlacement {
+public:
+ JointPlacement(bool text_, bool icon_, bool offscreen_)
+ : text(text_), icon(icon_), offscreen(offscreen_)
+ {}
+
+ const bool text;
+ const bool icon;
+ // offscreen = outside viewport, but within CollisionIndex::viewportPadding px of the edge
+ // Because these symbols aren't onscreen yet, we can skip the "fade in" animation,
+ // and if a subsequent viewport change brings them into view, they'll be fully
+ // visible right away.
+ const bool offscreen;
+};
+
+class Placement {
+public:
+ Placement(const TransformState&, MapMode mapMode);
+ void placeLayer(RenderSymbolLayer&, const mat4&, bool showCollisionBoxes);
+ bool commit(const Placement& prevPlacement, TimePoint);
+ void updateLayerOpacities(RenderSymbolLayer&);
+ JointOpacityState getOpacity(uint32_t crossTileSymbolID) const;
+ float symbolFadeChange(TimePoint now) const;
+ bool hasTransitions(TimePoint now) const;
+
+ const CollisionIndex& getCollisionIndex() const;
+
+ bool stillRecent(TimePoint now) const;
+ void setRecent(TimePoint now);
+ void setStale();
+private:
+
+ void placeLayerBucket(
+ SymbolBucket&,
+ const mat4& posMatrix,
+ const mat4& textLabelPlaneMatrix,
+ const mat4& iconLabelPlaneMatrix,
+ const float scale,
+ const float pixelRatio,
+ const bool showCollisionBoxes,
+ std::unordered_set<uint32_t>& seenCrossTileIDs,
+ const bool holdingForFade);
+
+ void updateBucketOpacities(SymbolBucket&, std::set<uint32_t>&);
+
+ CollisionIndex collisionIndex;
+
+ TransformState state;
+ MapMode mapMode;
+ TimePoint commitTime;
+
+ std::unordered_map<uint32_t, JointPlacement> placements;
+ std::unordered_map<uint32_t, JointOpacityState> opacities;
+
+ TimePoint recentUntil;
+ bool stale = false;
+};
+
+} // namespace mbgl
diff --git a/src/mbgl/text/placement_config.hpp b/src/mbgl/text/placement_config.hpp
deleted file mode 100644
index 48b24b5f41..0000000000
--- a/src/mbgl/text/placement_config.hpp
+++ /dev/null
@@ -1,33 +0,0 @@
-#pragma once
-
-#include <mbgl/util/constants.hpp>
-
-namespace mbgl {
-
-class PlacementConfig {
-public:
- PlacementConfig(float angle_ = 0, float pitch_ = 0, float cameraToCenterDistance_ = 0, float cameraToTileDistance_ = 0, bool debug_ = false)
- : angle(angle_), pitch(pitch_), cameraToCenterDistance(cameraToCenterDistance_), cameraToTileDistance(cameraToTileDistance_), debug(debug_) {
- }
-
- bool operator==(const PlacementConfig& rhs) const {
- return angle == rhs.angle &&
- pitch == rhs.pitch &&
- debug == rhs.debug &&
- ((pitch * util::RAD2DEG < 25) ||
- (cameraToCenterDistance == rhs.cameraToCenterDistance && cameraToTileDistance == rhs.cameraToTileDistance));
- }
-
- bool operator!=(const PlacementConfig& rhs) const {
- return !operator==(rhs);
- }
-
-public:
- float angle;
- float pitch;
- float cameraToCenterDistance;
- float cameraToTileDistance;
- bool debug;
-};
-
-} // namespace mbgl
diff --git a/src/mbgl/text/shaping.cpp b/src/mbgl/text/shaping.cpp
index 5d688ea539..a8232836b6 100644
--- a/src/mbgl/text/shaping.cpp
+++ b/src/mbgl/text/shaping.cpp
@@ -313,7 +313,7 @@ void shapeLines(Shaping& shaping,
align(shaping, justify, anchorAlign.horizontalAlign, anchorAlign.verticalAlign, maxLineLength,
lineHeight, lines.size());
- const uint32_t height = lines.size() * lineHeight;
+ const float height = lines.size() * lineHeight;
// Calculate the bounding box
shaping.top += -anchorAlign.verticalAlign * height;
View Lorry Controller Status