From f5430ca33c713a6b709074440961447146a16302 Mon Sep 17 00:00:00 2001 From: Mikhail Pozdnyakov Date: Mon, 23 Mar 2020 19:20:41 +0200 Subject: [core] Introduce map mode specific Placement implementations --- src/mbgl/renderer/render_orchestrator.cpp | 5 +- src/mbgl/text/placement.cpp | 413 +++++++++++++++++------------- src/mbgl/text/placement.hpp | 41 ++- 3 files changed, 275 insertions(+), 184 deletions(-) diff --git a/src/mbgl/renderer/render_orchestrator.cpp b/src/mbgl/renderer/render_orchestrator.cpp index e38990293f..8c8cd4a0ea 100644 --- a/src/mbgl/renderer/render_orchestrator.cpp +++ b/src/mbgl/renderer/render_orchestrator.cpp @@ -407,9 +407,8 @@ std::unique_ptr RenderOrchestrator::createRenderTree( renderTreeParameters->placementChanged = !placementController.placementIsRecent( updateParameters->timePoint, updateParameters->transformState.getZoom(), placementUpdatePeriodOverride); symbolBucketsChanged |= renderTreeParameters->placementChanged; - if (renderTreeParameters->placementChanged) { - Mutable placement = makeMutable(updateParameters, placementController.getPlacement()); + Mutable placement = Placement::create(updateParameters, placementController.getPlacement()); placement->placeLayers(layersNeedPlacement); placementController.setPlacement(std::move(placement)); crossTileSymbolIndex.pruneUnusedLayers(usedSymbolLayers); @@ -425,7 +424,7 @@ std::unique_ptr RenderOrchestrator::createRenderTree( } else { renderTreeParameters->placementChanged = symbolBucketsChanged = !layersNeedPlacement.empty(); if (renderTreeParameters->placementChanged) { - Mutable placement = makeMutable(updateParameters); + Mutable placement = Placement::create(updateParameters); placement->placeLayers(layersNeedPlacement); placementController.setPlacement(std::move(placement)); } diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp index a6de0baba7..7ea89fd80d 100644 --- a/src/mbgl/text/placement.cpp +++ b/src/mbgl/text/placement.cpp @@ -90,14 +90,12 @@ Placement::Placement(std::shared_ptr updateParameters_, optional> prevPlacement_) : updateParameters(std::move(updateParameters_)), collisionIndex(updateParameters->transformState, updateParameters->mode), - mapMode(updateParameters->mode), transitionOptions(updateParameters->transitionOptions), commitTime(updateParameters->timePoint), placementZoom(updateParameters->transformState.getZoom()), collisionGroups(updateParameters->crossSourceCollisions), prevPlacement(std::move(prevPlacement_)), showCollisionBoxes(updateParameters->debugOptions & MapDebugOptions::Collision) { - assert(prevPlacement || mapMode != MapMode::Continuous); if (prevPlacement) { prevPlacement->get()->prevPlacement = nullopt; // Only hold on to one placement back } @@ -105,6 +103,8 @@ Placement::Placement(std::shared_ptr updateParameters_, Placement::Placement() : collisionIndex({}, MapMode::Static), collisionGroups(true) {} +Placement::~Placement() = default; + void Placement::placeLayers(const RenderLayerReferences& layers) { for (auto it = layers.crbegin(); it != layers.crend(); ++it) { placeLayer(*it); @@ -175,16 +175,7 @@ void Placement::placeSymbolBucket(const BucketPlacementData& params, std::setevaluateForZoom(placementZoom); auto partiallyEvaluatedIconSize = bucket.iconSizeBinder->evaluateForZoom(placementZoom); - optional tileBorders; - optional avoidEdges; - if (mapMode == MapMode::Tile) { - tileBorders = collisionIndex.projectTileBoundaries(posMatrix); - if (layout.get() || - layout.get() == style::SymbolPlacementType::Line) { - avoidEdges = tileBorders; - } - } - + optional avoidEdges = getAvoidEdges(bucket, posMatrix); const bool textAllowOverlap = layout.get(); const bool iconAllowOverlap = layout.get(); // This logic is similar to the "defaultOpacityState" logic below in updateBucketOpacities @@ -207,7 +198,6 @@ void Placement::placeSymbolBucket(const BucketPlacementData& params, std::set() != style::IconTextFitType::None; - const bool zOrderByViewportY = layout.get() == style::SymbolZOrderType::ViewportY; std::vector textBoxes; std::vector iconBoxes; @@ -356,13 +346,9 @@ void Placement::placeSymbolBucket(const BucketPlacementData& params, std::set() == style::SymbolPlacementType::Point) { - // In this case we first try to place symbols, which intersects the tile borders, so that - // those symbols will remain even if each tile is handled independently. - SymbolInstanceReferences symbolInstances = bucket.getSymbols(params.sortKeyRange); - optional variableAnchor; - if (!variableTextAnchors.empty()) variableAnchor = variableTextAnchors.front(); - - std::unordered_map locationCache; - locationCache.reserve(symbolInstances.size()); - - // Keeps the data necessary to find a feature location according to a tile. - struct NeighborTileData { - NeighborTileData(const CollisionIndex& collisionIndex, UnwrappedTileID id_, Point shift_) - : id(id_), shift(shift_), matrix() { - collisionIndex.getTransformState().matrixFor(matrix, id); - matrix::multiply(matrix, collisionIndex.getTransformState().getProjectionMatrix(), matrix); - borders = collisionIndex.projectTileBoundaries(matrix); - } - - UnwrappedTileID id; - Point shift; - mat4 matrix; - CollisionBoundaries borders; - }; + for (const SymbolInstance& symbol : getSortedSymbols(params, pixelRatio)) { + placeSymbol(symbol); + } - uint8_t z = renderTile.id.canonical.z; - uint32_t x = renderTile.id.canonical.x; - uint32_t y = renderTile.id.canonical.y; - const std::array neightbors{{ - {collisionIndex, UnwrappedTileID(z, x, y - 1), {0.0f, util::EXTENT}}, // top - {collisionIndex, UnwrappedTileID(z, x, y + 1), {0.0f, -util::EXTENT}}, // bottom - {collisionIndex, UnwrappedTileID(z, x - 1, y), {util::EXTENT, 0.0f}}, // left - {collisionIndex, UnwrappedTileID(z, x + 1, y), {-util::EXTENT, 0.0f}} // right - }}; - - auto collisionBoxIntersectsTileEdges = [&](const CollisionBox& collisionBox, - Point shift) noexcept->bool { - bool intersects = - collisionIndex.intersectsTileEdges(collisionBox, shift, renderTile.matrix, pixelRatio, *tileBorders); - // Check if this symbol intersects the neighbor tile borders. If so, it also shall be placed with priority. - for (const auto& neighbor : neightbors) { - if (intersects) break; - intersects = collisionIndex.intersectsTileEdges( - collisionBox, shift + neighbor.shift, neighbor.matrix, pixelRatio, neighbor.borders); - } - return intersects; - }; + // As long as this placement lives, we have to hold onto this bucket's + // matching FeatureIndex/data for querying purposes + retainedQueryData.emplace(std::piecewise_construct, + std::forward_as_tuple(bucket.bucketInstanceId), + std::forward_as_tuple(bucket.bucketInstanceId, params.featureIndex, overscaledID)); +} - auto symbolIntersectsTileEdges = [ - &locationCache, - &collisionBoxIntersectsTileEdges, - variableAnchor, - pitchTextWithMap, - rotateTextWithMap, - bearing = state.getBearing() - ](const SymbolInstance& symbol) noexcept->bool { - auto it = locationCache.find(symbol.crossTileID); - if (it != locationCache.end()) return it->second; - - bool intersects = false; - if (!symbol.textCollisionFeature.boxes.empty()) { - const auto& textCollisionBox = symbol.textCollisionFeature.boxes.front(); - - Point offset{}; - if (variableAnchor) { - float width = textCollisionBox.x2 - textCollisionBox.x1; - float height = textCollisionBox.y2 - textCollisionBox.y1; - offset = calculateVariableLayoutOffset(*variableAnchor, - width, - height, - symbol.variableTextOffset, - symbol.textBoxScale, - rotateTextWithMap, - pitchTextWithMap, - bearing); - } - intersects = collisionBoxIntersectsTileEdges(textCollisionBox, offset); - } +namespace { - if (!symbol.iconCollisionFeature.boxes.empty() && !intersects) { - const auto& iconCollisionBox = symbol.iconCollisionFeature.boxes.front(); - intersects = collisionBoxIntersectsTileEdges(iconCollisionBox, {}); - } +SymbolInstanceReferences getBucketSymbols(const SymbolBucket& bucket, + optional sortKeyRange, + float bearing) { + if (bucket.layout->get() == style::SymbolZOrderType::ViewportY) { + auto sortedSymbols = bucket.getSortedSymbols(bearing); + // Place in the reverse order than draw i.e., starting from the foreground elements. + std::reverse(std::begin(sortedSymbols), std::end(sortedSymbols)); + return sortedSymbols; + } + return bucket.getSymbols(sortKeyRange); +} - locationCache.insert(std::make_pair(symbol.crossTileID, intersects)); - return intersects; - }; +} // namespace +SymbolInstanceReferences Placement::getSortedSymbols(const BucketPlacementData& params, float) { + const auto& bucket = static_cast(params.bucket.get()); + SymbolInstanceReferences sortedSymbols = + getBucketSymbols(bucket, params.sortKeyRange, collisionIndex.getTransformState().getBearing()); + auto* previousPlacement = getPrevPlacement(); + if (previousPlacement && isTiltedView()) { std::stable_sort( - symbolInstances.begin(), - symbolInstances.end(), - [&symbolIntersectsTileEdges](const SymbolInstance& a, const SymbolInstance& b) noexcept { - assert(!a.textCollisionFeature.alongLine); - assert(!b.textCollisionFeature.alongLine); - auto intersectsA = symbolIntersectsTileEdges(a); - auto intersectsB = symbolIntersectsTileEdges(b); - if (intersectsA) { - if (!intersectsB) return true; - // Both symbols are inrecepting the tile borders, we need a universal cross-tile rule - // to define which of them shall be placed first - use anchor `y` point. - return a.anchor.point.y < b.anchor.point.y; + sortedSymbols.begin(), + sortedSymbols.end(), + [previousPlacement](const SymbolInstance& a, const SymbolInstance& b) noexcept { + auto* aPlacement = previousPlacement->getSymbolPlacement(a); + auto* bPlacement = previousPlacement->getSymbolPlacement(b); + if (!aPlacement) { + // a < b, if 'a' is new and if 'b' was previously hidden. + return bPlacement && !bPlacement->placed(); } - return false; + if (!bPlacement) { + // a < b, if 'b' is new and 'a' was previously shown. + return aPlacement && aPlacement->placed(); + } + // a < b, if 'a' was shown and 'b' was hidden. + return aPlacement->placed() && !bPlacement->placed(); }); - - for (const SymbolInstance& symbol : symbolInstances) { - placeSymbol(symbol); - } - } else { - SymbolInstanceReferences sortedSymbols = bucket.getSymbols(params.sortKeyRange); - auto* previousPlacement = getPrevPlacement(); - if (previousPlacement && isTiltedView()) { - std::stable_sort( - sortedSymbols.begin(), - sortedSymbols.end(), - [previousPlacement](const SymbolInstance& a, const SymbolInstance& b) noexcept { - auto* aPlacement = previousPlacement->getSymbolPlacement(a); - auto* bPlacement = previousPlacement->getSymbolPlacement(b); - if (!aPlacement) { - // a < b, if 'a' is new and if 'b' was previously hidden. - return bPlacement && !bPlacement->placed(); - } - if (!bPlacement) { - // a < b, if 'b' is new and 'a' was previously shown. - return aPlacement && aPlacement->placed(); - } - // a < b, if 'a' was shown and 'b' was hidden. - return aPlacement->placed() && !bPlacement->placed(); - }); - } - for (const SymbolInstance& symbol : sortedSymbols) { - placeSymbol(symbol); - } } - - // As long as this placement lives, we have to hold onto this bucket's - // matching FeatureIndex/data for querying purposes - retainedQueryData.emplace(std::piecewise_construct, - std::forward_as_tuple(bucket.bucketInstanceId), - std::forward_as_tuple(bucket.bucketInstanceId, params.featureIndex, overscaledID)); + return sortedSymbols; } void Placement::commit() { - if (!getPrevPlacement()) { - assert(mapMode != MapMode::Continuous); - fadeStartTime = commitTime; - for (auto& jointPlacement : placements) { - opacities.emplace( - jointPlacement.first, - JointOpacityState( - jointPlacement.second.text, jointPlacement.second.icon, jointPlacement.second.skipFade)); - } - return; - } - bool placementChanged = false; - + assert(getPrevPlacement()); prevZoomAdjustment = getPrevPlacement()->zoomAdjustment(placementZoom); float increment = getPrevPlacement()->symbolFadeChange(commitTime); @@ -1254,7 +1133,7 @@ Duration Placement::getUpdatePeriod(const float zoom) const { } bool Placement::transitionsEnabled() const { - return mapMode == MapMode::Continuous && transitionOptions.enablePlacementTransitions; + return transitionOptions.enablePlacementTransitions; } bool Placement::hasTransitions(TimePoint now) const { @@ -1275,4 +1154,194 @@ const RetainedQueryData& Placement::getQueryData(uint32_t bucketInstanceId) cons return it->second; } +class StaticPlacement : public Placement { +public: + StaticPlacement(std::shared_ptr updateParameters_) + : Placement(std::move(updateParameters_), nullopt) {} + +private: + void commit() override; + float symbolFadeChange(TimePoint) const override { return 1.0f; } + bool hasTransitions(TimePoint) const override { return false; } + bool transitionsEnabled() const override { return false; } +}; + +void StaticPlacement::commit() { + fadeStartTime = commitTime; + for (auto& jointPlacement : placements) { + opacities.emplace( + jointPlacement.first, + JointOpacityState(jointPlacement.second.text, jointPlacement.second.icon, jointPlacement.second.skipFade)); + } +} + +class TilePlacement : public StaticPlacement { +public: + TilePlacement(std::shared_ptr updateParameters_) + : StaticPlacement(std::move(updateParameters_)) {} + +private: + optional getAvoidEdges(const SymbolBucket&, const mat4&) override; + SymbolInstanceReferences getSortedSymbols(const BucketPlacementData&, float pixelRatio) override; + bool stickToFirstVariableAnchor(const CollisionBox& box, + Point shift, + const mat4& posMatrix, + float textPixelRatio) override; + + std::unordered_map locationCache; + optional tileBorders; +}; + +optional TilePlacement::getAvoidEdges(const SymbolBucket& bucket, const mat4& posMatrix) { + tileBorders = collisionIndex.projectTileBoundaries(posMatrix); + const auto& layout = *bucket.layout; + if (layout.get() || + layout.get() == style::SymbolPlacementType::Line) { + return tileBorders; + } + return nullopt; +} + +SymbolInstanceReferences TilePlacement::getSortedSymbols(const BucketPlacementData& params, float pixelRatio) { + const auto& bucket = static_cast(params.bucket.get()); + const auto& layout = *bucket.layout; + const RenderTile& renderTile = params.tile; + const auto& state = collisionIndex.getTransformState(); + if (layout.get() != style::SymbolPlacementType::Point || + layout.get()) { + return StaticPlacement::getSortedSymbols(params, pixelRatio); + } + const bool rotateTextWithMap = layout.get() == style::AlignmentType::Map; + const bool pitchTextWithMap = layout.get() == style::AlignmentType::Map; + + std::vector variableTextAnchors = layout.get(); + // In this case we first try to place symbols, which intersects the tile borders, so that + // those symbols will remain even if each tile is handled independently. + SymbolInstanceReferences symbolInstances = + getBucketSymbols(bucket, params.sortKeyRange, collisionIndex.getTransformState().getBearing()); + optional variableAnchor; + if (!variableTextAnchors.empty()) variableAnchor = variableTextAnchors.front(); + locationCache.clear(); + + // Keeps the data necessary to find a feature location according to a tile. + struct NeighborTileData { + NeighborTileData(const CollisionIndex& collisionIndex, UnwrappedTileID id_, Point shift_) + : id(id_), shift(shift_), matrix() { + collisionIndex.getTransformState().matrixFor(matrix, id); + matrix::multiply(matrix, collisionIndex.getTransformState().getProjectionMatrix(), matrix); + borders = collisionIndex.projectTileBoundaries(matrix); + } + + UnwrappedTileID id; + Point shift; + mat4 matrix; + CollisionBoundaries borders; + }; + + uint8_t z = renderTile.id.canonical.z; + uint32_t x = renderTile.id.canonical.x; + uint32_t y = renderTile.id.canonical.y; + const std::array neightbors{{ + {collisionIndex, UnwrappedTileID(z, x, y - 1), {0.0f, util::EXTENT}}, // top + {collisionIndex, UnwrappedTileID(z, x, y + 1), {0.0f, -util::EXTENT}}, // bottom + {collisionIndex, UnwrappedTileID(z, x - 1, y), {util::EXTENT, 0.0f}}, // left + {collisionIndex, UnwrappedTileID(z, x + 1, y), {-util::EXTENT, 0.0f}} // right + }}; + + auto collisionBoxIntersectsTileEdges = [&](const CollisionBox& collisionBox, Point shift) noexcept->bool { + bool intersects = + collisionIndex.intersectsTileEdges(collisionBox, shift, renderTile.matrix, pixelRatio, *tileBorders); + // Check if this symbol intersects the neighbor tile borders. If so, it also shall be placed with priority. + for (const auto& neighbor : neightbors) { + if (intersects) break; + intersects = collisionIndex.intersectsTileEdges( + collisionBox, shift + neighbor.shift, neighbor.matrix, pixelRatio, neighbor.borders); + } + return intersects; + }; + + auto symbolIntersectsTileEdges = [ + this, + &collisionBoxIntersectsTileEdges, + variableAnchor, + pitchTextWithMap, + rotateTextWithMap, + bearing = state.getBearing() + ](const SymbolInstance& symbol) noexcept->bool { + auto it = locationCache.find(symbol.crossTileID); + if (it != locationCache.end()) return it->second; + + bool intersects = false; + if (!symbol.textCollisionFeature.boxes.empty()) { + const auto& textCollisionBox = symbol.textCollisionFeature.boxes.front(); + + Point offset{}; + if (variableAnchor) { + float width = textCollisionBox.x2 - textCollisionBox.x1; + float height = textCollisionBox.y2 - textCollisionBox.y1; + offset = calculateVariableLayoutOffset(*variableAnchor, + width, + height, + symbol.variableTextOffset, + symbol.textBoxScale, + rotateTextWithMap, + pitchTextWithMap, + bearing); + } + intersects = collisionBoxIntersectsTileEdges(textCollisionBox, offset); + } + + if (!symbol.iconCollisionFeature.boxes.empty() && !intersects) { + const auto& iconCollisionBox = symbol.iconCollisionFeature.boxes.front(); + intersects = collisionBoxIntersectsTileEdges(iconCollisionBox, {}); + } + + locationCache.insert(std::make_pair(symbol.crossTileID, intersects)); + return intersects; + }; + + std::stable_sort( + symbolInstances.begin(), + symbolInstances.end(), + [&symbolIntersectsTileEdges](const SymbolInstance& a, const SymbolInstance& b) noexcept { + assert(!a.textCollisionFeature.alongLine); + assert(!b.textCollisionFeature.alongLine); + auto intersectsA = symbolIntersectsTileEdges(a); + auto intersectsB = symbolIntersectsTileEdges(b); + if (intersectsA) { + if (!intersectsB) return true; + // Both symbols are inrecepting the tile borders, we need a universal cross-tile rule + // to define which of them shall be placed first - use anchor `y` point. + return a.anchor.point.y < b.anchor.point.y; + } + return false; + }); + return symbolInstances; +} + +bool TilePlacement::stickToFirstVariableAnchor(const CollisionBox& box, + Point shift, + const mat4& posMatrix, + float textPixelRatio) { + assert(tileBorders); + return collisionIndex.intersectsTileEdges(box, shift, posMatrix, textPixelRatio, *tileBorders); +} + +// static +Mutable Placement::create(std::shared_ptr updateParameters_, + optional> prevPlacement) { + assert(updateParameters_); + switch (updateParameters_->mode) { + case MapMode::Continuous: + assert(prevPlacement); + return makeMutable(std::move(updateParameters_), std::move(prevPlacement)); + case MapMode::Static: + return staticMutableCast(makeMutable(std::move(updateParameters_))); + case MapMode::Tile: + return staticMutableCast(makeMutable(std::move(updateParameters_))); + } + assert(false); + return makeMutable(); +} + } // namespace mbgl diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp index dcb67fa8c8..b6354670b1 100644 --- a/src/mbgl/text/placement.hpp +++ b/src/mbgl/text/placement.hpp @@ -12,6 +12,7 @@ namespace mbgl { class SymbolBucket; class SymbolInstance; +using SymbolInstanceReferences = std::vector>; class UpdateParameters; enum class PlacedSymbolOrientation : bool; @@ -106,13 +107,21 @@ private: class Placement { public: - Placement(std::shared_ptr, optional> prevPlacement = nullopt); - Placement(); + /** + * @brief creates a new placement instance, from the given update parameters and the previous placement instance. + * + * Different placement implementations are created based on `updateParameters->mapMode`. + * In Continuous map mode, `prevPlacement` must be provided. + */ + static Mutable create(std::shared_ptr updateParameters, + optional> prevPlacement = nullopt); + + virtual ~Placement(); void placeLayers(const RenderLayerReferences&); void updateLayerBuckets(const RenderLayer&, const TransformState&, bool updateOpacities) const; - float symbolFadeChange(TimePoint now) const; - bool hasTransitions(TimePoint now) const; - bool transitionsEnabled() const; + virtual float symbolFadeChange(TimePoint now) const; + virtual bool hasTransitions(TimePoint now) const; + virtual bool transitionsEnabled() const; const CollisionIndex& getCollisionIndex() const; TimePoint getCommitTime() const { return commitTime; } @@ -123,11 +132,27 @@ public: const RetainedQueryData& getQueryData(uint32_t bucketInstanceId) const; -private: + // Public constructors are required for makeMutable(), shall not be called directly. + Placement(); + Placement(std::shared_ptr, optional> prevPlacement); + +protected: friend SymbolBucket; void placeSymbolBucket(const BucketPlacementData&, std::set& seenCrossTileIDs); void placeLayer(const RenderLayer&); - void commit(); + virtual void commit(); + // Implentation specific hooks, which get called during a symbol bucket placement. + virtual optional getAvoidEdges(const SymbolBucket&, const mat4& /*posMatrix*/) { + return nullopt; + } + virtual SymbolInstanceReferences getSortedSymbols(const BucketPlacementData&, float pixelRatio); + virtual bool stickToFirstVariableAnchor(const CollisionBox&, + Point /*shift*/, + const mat4& /*posMatrix*/, + float /*textPixelRatio*/) { + return false; + } + // Returns `true` if bucket vertices were updated; returns `false` otherwise. bool updateBucketDynamicVertices(SymbolBucket&, const TransformState&, const RenderTile& tile) const; void updateBucketOpacities(SymbolBucket&, const TransformState&, std::set&) const; @@ -142,7 +167,6 @@ private: std::shared_ptr updateParameters; CollisionIndex collisionIndex; - MapMode mapMode = MapMode::Static; style::TransitionOptions transitionOptions; TimePoint fadeStartTime; @@ -159,7 +183,6 @@ private: CollisionGroups collisionGroups; mutable optional> prevPlacement; bool showCollisionBoxes = false; - // Used for debug purposes. std::unordered_map> collisionCircles; }; -- cgit v1.2.1