From 65d2f7ed6afe17c6fbc8155cb116aae7de16db9a Mon Sep 17 00:00:00 2001 From: Mikhail Pozdnyakov Date: Thu, 1 Aug 2019 19:16:01 +0300 Subject: [core] Introduce ProjectedCollisionBox type ProjectedCollisionBox encapsulates geometry of the projected collision box, it is using union and thus provides memory save - 12 bytes per collision box instance. --- src/mbgl/text/collision_feature.cpp | 2 +- src/mbgl/text/collision_feature.hpp | 55 +++++++++++++++++++------- src/mbgl/text/collision_index.cpp | 78 ++++++++++++++++++------------------- src/mbgl/text/collision_index.hpp | 6 +-- src/mbgl/text/placement.cpp | 2 +- 5 files changed, 83 insertions(+), 60 deletions(-) diff --git a/src/mbgl/text/collision_feature.cpp b/src/mbgl/text/collision_feature.cpp index fbf259d1db..f9f6b3a4a5 100644 --- a/src/mbgl/text/collision_feature.cpp +++ b/src/mbgl/text/collision_feature.cpp @@ -155,7 +155,7 @@ void CollisionFeature::bboxifyLabel(const GeometryCoordinates& line, GeometryCoo 0 : (boxDistanceToAnchor - firstBoxOffset) * 0.8; - boxes.emplace_back(boxAnchor, -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, paddedAnchorDistance, boxSize / 2); + boxes.emplace_back(boxAnchor, -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, paddedAnchorDistance); } } diff --git a/src/mbgl/text/collision_feature.hpp b/src/mbgl/text/collision_feature.hpp index 82a9113caa..106fe8402a 100644 --- a/src/mbgl/text/collision_feature.hpp +++ b/src/mbgl/text/collision_feature.hpp @@ -9,10 +9,46 @@ namespace mbgl { +class ProjectedCollisionBox { +public: + enum class Type : char { + Unknown, + Box, + Circle + }; + + ProjectedCollisionBox() = default; + ProjectedCollisionBox(float x1, float y1, float x2, float y2) : geometry(x1, y1, x2, y2), type(Type::Box) {} + ProjectedCollisionBox(float x, float y, float r) : geometry(x, y, r), type(Type::Circle) {} + + const mapbox::geometry::box& box() const { + assert(isBox()); + return geometry.box; + } + + const geometry::circle& circle() const { + assert(isCircle()); + return geometry.circle; + } + + bool isCircle() const { return type == Type::Circle; } + bool isBox() const { return type == Type::Box; } + +private: + union Geometry { + Geometry(float x1, float y1, float x2, float y2) : box({x1, y1}, {x2, y2}) {} + Geometry(float x, float y, float r) : circle({x, y}, r) {} + Geometry() {} + mapbox::geometry::box box; + geometry::circle circle; + } geometry; + Type type = Type::Unknown; +}; + class CollisionBox { public: - CollisionBox(Point _anchor, float _x1, float _y1, float _x2, float _y2, float _signedDistanceFromAnchor = 0, float _radius = 0) : - anchor(std::move(_anchor)), x1(_x1), y1(_y1), x2(_x2), y2(_y2), used(true), signedDistanceFromAnchor(_signedDistanceFromAnchor), radius(_radius) {} + CollisionBox(Point _anchor, float _x1, float _y1, float _x2, float _y2, float _signedDistanceFromAnchor = 0) : + anchor(std::move(_anchor)), x1(_x1), y1(_y1), x2(_x2), y2(_y2), signedDistanceFromAnchor(_signedDistanceFromAnchor) {} // the box is centered around the anchor point Point anchor; @@ -27,19 +63,10 @@ public: float x2; float y2; - // 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; - float signedDistanceFromAnchor; - float radius; + + // generated/updated at placement time + ProjectedCollisionBox projected; }; class CollisionFeature { diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp index ae8b29c3fb..4329b314ea 100644 --- a/src/mbgl/text/collision_index.cpp +++ b/src/mbgl/text/collision_index.cpp @@ -55,12 +55,12 @@ float CollisionIndex::approximateTileDistance(const TileDistance& tileDistance, (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::isOffscreen(float x1, float y1, float x2, float y2) const { + return x2 < viewportPadding || x1 >= screenRightBoundary || y2 < viewportPadding || y1 >= screenBottomBoundary; } -bool CollisionIndex::isInsideGrid(const CollisionBox& box) const { - return box.px2 >= 0 && box.px1 < gridRightBoundary && box.py2 >= 0 && box.py1 < gridBottomBoundary; +bool CollisionIndex::isInsideGrid(float x1, float y1, float x2, float y2) const { + return x2 >= 0 && x1 < gridRightBoundary && y2 >= 0 && y1 < gridBottomBoundary; } CollisionTileBoundaries CollisionIndex::projectTileBoundaries(const mat4& posMatrix) const { @@ -71,11 +71,11 @@ CollisionTileBoundaries CollisionIndex::projectTileBoundaries(const mat4& posMat } -bool CollisionIndex::isInsideTile(const CollisionBox& box, const CollisionTileBoundaries& tileBoundaries) const { +bool CollisionIndex::isInsideTile(float x1, float y1, float x2, float y2, const CollisionTileBoundaries& tileBoundaries) const { // This check is only well defined when the tile boundaries are axis-aligned // We are relying on it only being used in MapMode::Tile, where that is always the case - return box.px1 >= tileBoundaries[0] && box.py1 >= tileBoundaries[1] && box.px2 < tileBoundaries[2] && box.py2 < tileBoundaries[3]; + return x1 >= tileBoundaries[0] && y1 >= tileBoundaries[1] && x2 < tileBoundaries[2] && y2 < tileBoundaries[3]; } @@ -96,19 +96,19 @@ std::pair CollisionIndex::placeFeature(CollisionFeature& feature, CollisionBox& box = feature.boxes.front(); const auto projectedPoint = projectAndGetPerspectiveRatio(posMatrix, box.anchor); const float tileToViewport = textPixelRatio * projectedPoint.second; - box.px1 = (box.x1 + shift.x) * tileToViewport + projectedPoint.first.x; - box.py1 = (box.y1 + shift.y) * tileToViewport + projectedPoint.first.y; - box.px2 = (box.x2 + shift.x) * tileToViewport + projectedPoint.first.x; - box.py2 = (box.y2 + shift.y) * tileToViewport + projectedPoint.first.y; - - - if ((avoidEdges && !isInsideTile(box, *avoidEdges)) || - !isInsideGrid(box) || - (!allowOverlap && collisionGrid.hitTest({{ box.px1, box.py1 }, { box.px2, box.py2 }}, collisionGroupPredicate))) { + float px1 = (box.x1 + shift.x) * tileToViewport + projectedPoint.first.x; + float py1 = (box.y1 + shift.y) * tileToViewport + projectedPoint.first.y; + float px2 = (box.x2 + shift.x) * tileToViewport + projectedPoint.first.x; + float py2 = (box.y2 + shift.y) * tileToViewport + projectedPoint.first.y; + box.projected = ProjectedCollisionBox{ px1, py1, px2, py2 }; + + if ((avoidEdges && !isInsideTile(px1, py1, px2, py2, *avoidEdges)) || + !isInsideGrid(px1, py1, px2, py2) || + (!allowOverlap && collisionGrid.hitTest(box.projected.box(), collisionGroupPredicate))) { return { false, false }; } - return {true, isOffscreen(box)}; + return {true, isOffscreen(px1, py1, px2, py2)}; } else { return placeLineFeature(feature, posMatrix, labelPlaneMatrix, textPixelRatio, symbol, scale, fontSize, allowOverlap, pitchWithMap, collisionDebug, avoidEdges, collisionGroupPredicate); } @@ -126,7 +126,7 @@ std::pair CollisionIndex::placeLineFeature(CollisionFeature& feature, const bool collisionDebug, const optional& avoidEdges, const optional> collisionGroupPredicate) { - + assert(feature.alongLine); const auto tileUnitAnchorPoint = symbol.anchorPoint; const auto projectedAnchor = projectAnchor(posMatrix, tileUnitAnchorPoint); @@ -173,7 +173,6 @@ std::pair CollisionIndex::placeLineFeature(CollisionFeature& feature, // 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; previousCirclePlaced = false; continue; } @@ -184,9 +183,10 @@ std::pair CollisionIndex::placeLineFeature(CollisionFeature& feature, if (previousCirclePlaced) { const CollisionBox& previousCircle = feature.boxes[i - 1]; - assert(previousCircle.used); - const float dx = projectedPoint.x - previousCircle.px; - const float dy = projectedPoint.y - previousCircle.py; + assert(previousCircle.projected.isCircle()); + const auto& previousCenter = previousCircle.projected.circle().center; + const float dx = projectedPoint.x - previousCenter.x; + const float dy = projectedPoint.y - previousCenter.y; // 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. @@ -204,7 +204,6 @@ std::pair CollisionIndex::placeLineFeature(CollisionFeature& feature, // 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; previousCirclePlaced = false; continue; } @@ -213,22 +212,18 @@ std::pair CollisionIndex::placeLineFeature(CollisionFeature& feature, } previousCirclePlaced = 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; + float px1 = projectedPoint.x - radius; + float px2 = projectedPoint.x + radius; + float py1 = projectedPoint.y - radius; + float py2 = projectedPoint.y + radius; + + circle.projected = ProjectedCollisionBox{projectedPoint.x, projectedPoint.y, radius}; - entirelyOffscreen &= isOffscreen(circle); - inGrid |= isInsideGrid(circle); + entirelyOffscreen &= isOffscreen(px1, py1, px2, py2); + inGrid |= isInsideGrid(px1, py1, px2, py2); - if ((avoidEdges && !isInsideTile(circle, *avoidEdges)) || - (!allowOverlap && collisionGrid.hitTest({{circle.px, circle.py}, circle.radius}, collisionGroupPredicate))) { + if ((avoidEdges && !isInsideTile(px1, py1, px2, py2, *avoidEdges)) || + (!allowOverlap && collisionGrid.hitTest(circle.projected.circle(), collisionGroupPredicate))) { if (!collisionDebug) { return {false, false}; } else { @@ -246,34 +241,35 @@ std::pair CollisionIndex::placeLineFeature(CollisionFeature& feature, void CollisionIndex::insertFeature(CollisionFeature& feature, bool ignorePlacement, uint32_t bucketInstanceId, uint16_t collisionGroupId) { if (feature.alongLine) { for (auto& circle : feature.boxes) { - if (!circle.used) { + if (!circle.projected.isCircle()) { continue; } if (ignorePlacement) { ignoredGrid.insert( IndexedSubfeature(feature.indexedFeature, bucketInstanceId, collisionGroupId), - {{ circle.px, circle.py }, circle.radius} + circle.projected.circle() ); } else { collisionGrid.insert( IndexedSubfeature(feature.indexedFeature, bucketInstanceId, collisionGroupId), - {{ circle.px, circle.py }, circle.radius} + circle.projected.circle() ); } } } else { assert(feature.boxes.size() == 1); auto& box = feature.boxes[0]; + assert(box.projected.isBox()); if (ignorePlacement) { ignoredGrid.insert( IndexedSubfeature(feature.indexedFeature, bucketInstanceId, collisionGroupId), - {{ box.px1, box.py1 }, { box.px2, box.py2 }} + box.projected.box() ); } else { collisionGrid.insert( IndexedSubfeature(feature.indexedFeature, bucketInstanceId, collisionGroupId), - {{ box.px1, box.py1 }, { box.px2, box.py2 }} + box.projected.box() ); } } diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp index ea65a426fd..a1b277d06d 100644 --- a/src/mbgl/text/collision_index.hpp +++ b/src/mbgl/text/collision_index.hpp @@ -45,9 +45,9 @@ public: const TransformState& getTransformState() const { return transformState; } private: - bool isOffscreen(const CollisionBox&) const; - bool isInsideGrid(const CollisionBox&) const; - bool isInsideTile(const CollisionBox&, const CollisionTileBoundaries& tileBoundaries) const; + bool isOffscreen(float x1, float y1, float x2, float y2) const; + bool isInsideGrid(float x1, float y1, float x2, float y2) const; + bool isInsideTile(float x1, float y1, float x2, float y2, const CollisionTileBoundaries& tileBoundaries) const; std::pair placeLineFeature(CollisionFeature& feature, const mat4& posMatrix, diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp index 79bb984aa2..4ad911212d 100644 --- a/src/mbgl/text/placement.cpp +++ b/src/mbgl/text/placement.cpp @@ -628,7 +628,7 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket, const TransformState return; } for (const CollisionBox& box : feature.boxes) { - const auto& dynamicVertex = CollisionBoxProgram::dynamicVertex(placed, !box.used, {}); + const auto& dynamicVertex = CollisionBoxProgram::dynamicVertex(placed, !box.projected.isCircle(), {}); bucket.collisionCircle->dynamicVertices.extend(4, dynamicVertex); } }; -- cgit v1.2.1