From 18d735ccc20e1e7d4616b3d3b5b1a527a01d1b91 Mon Sep 17 00:00:00 2001 From: Chris Loer Date: Thu, 9 Nov 2017 13:24:43 -0800 Subject: [core] Add Placement class. Responsible for running global collision detection/symbol placement algorithm and updating symbol opacity buffers accordingly. --- cmake/core-files.cmake | 2 + src/mbgl/text/placement.cpp | 307 ++++++++++++++++++++++++++++++++++++++++++++ src/mbgl/text/placement.hpp | 82 ++++++++++++ 3 files changed, 391 insertions(+) create mode 100644 src/mbgl/text/placement.cpp create mode 100644 src/mbgl/text/placement.hpp diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake index c6b951c237..fc918b34c8 100644 --- a/cmake/core-files.cmake +++ b/cmake/core-files.cmake @@ -546,6 +546,8 @@ set(MBGL_CORE_FILES src/mbgl/text/glyph_pbf.hpp src/mbgl/text/glyph_range.hpp src/mbgl/text/placement_config.hpp + src/mbgl/text/placement.cpp + src/mbgl/text/placement.hpp src/mbgl/text/quads.cpp src/mbgl/text/quads.hpp src/mbgl/text/shaping.cpp diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp new file mode 100644 index 0000000000..ac8c15aae9 --- /dev/null +++ b/src/mbgl/text/placement.cpp @@ -0,0 +1,307 @@ +#include +#include +#include +#include +#include +#include +#include + +namespace mbgl { + +OpacityState::OpacityState(bool placed_) : opacity(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) : + icon(OpacityState(placedIcon)), + text(OpacityState(placedText)) {} + +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 seenCrossTileIDs; + + for (RenderTile& renderTile : symbolLayer.renderTiles) { + + if (!renderTile.tile.isRenderable()) { + continue; + } + + auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl); + assert(dynamic_cast(bucket)); + SymbolBucket& symbolBucket = *reinterpret_cast(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(renderTile.matrix, + layout.get() == style::AlignmentType::Map, + layout.get() == style::AlignmentType::Map, + state, + pixelsToTileUnits); + + mat4 iconLabelPlaneMatrix = getLabelPlaneMatrix(renderTile.matrix, + layout.get() == style::AlignmentType::Map, + layout.get() == style::AlignmentType::Map, + state, + pixelsToTileUnits); + + placeLayerBucket(symbolBucket, posMatrix, textLabelPlaneMatrix, iconLabelPlaneMatrix, scale, textPixelRatio, showCollisionBoxes, seenCrossTileIDs); + } +} + +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& seenCrossTileIDs) { + + auto partiallyEvaluatedTextSize = bucket.textSizeBinder->evaluateForZoom(state.getZoom()); + auto partiallyEvaluatedIconSize = bucket.iconSizeBinder->evaluateForZoom(state.getZoom()); + + const bool iconWithoutText = !bucket.hasTextData() || bucket.layout.get(); + const bool textWithoutIcon = !bucket.hasIconData() || bucket.layout.get(); + + for (auto& symbolInstance : bucket.symbolInstances) { + + if (seenCrossTileIDs.count(symbolInstance.crossTileID) == 0) { + bool placeText = false; + bool placeIcon = false; + + if (symbolInstance.placedTextIndex) { + PlacedSymbol& placedSymbol = bucket.text.placedSymbols.at(*symbolInstance.placedTextIndex); + const float fontSize = evaluateSizeForFeature(partiallyEvaluatedTextSize, placedSymbol); + + placeText = collisionIndex.placeFeature(symbolInstance.textCollisionFeature, + posMatrix, textLabelPlaneMatrix, textPixelRatio, + placedSymbol, scale, fontSize, + bucket.layout.get(), + bucket.layout.get() == style::AlignmentType::Map, + showCollisionBoxes); + } + + if (symbolInstance.placedIconIndex) { + PlacedSymbol& placedSymbol = bucket.icon.placedSymbols.at(*symbolInstance.placedIconIndex); + const float fontSize = evaluateSizeForFeature(partiallyEvaluatedIconSize, placedSymbol); + + placeIcon = collisionIndex.placeFeature(symbolInstance.iconCollisionFeature, + posMatrix, iconLabelPlaneMatrix, textPixelRatio, + placedSymbol, scale, fontSize, + bucket.layout.get(), + bucket.layout.get() == style::AlignmentType::Map, + showCollisionBoxes); + } + + // 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()); + } + + if (placeIcon) { + collisionIndex.insertFeature(symbolInstance.iconCollisionFeature, bucket.layout.get()); + } + + assert(symbolInstance.crossTileID != 0); + + placements.emplace(symbolInstance.crossTileID, PlacementPair(placeText, placeIcon)); + seenCrossTileIDs.insert(symbolInstance.crossTileID); + } + } +} + +bool Placement::commit(const Placement& prevPlacement, TimePoint now) { + commitTime = now; + + bool placementChanged = false; + + float increment = mapMode == MapMode::Still ? 1.0 : std::chrono::duration(commitTime - prevPlacement.commitTime) / Duration(std::chrono::milliseconds(300)); + + // add the opacities from the current placement, and copy their current values from the previous placement + for (auto& placementPair : placements) { + auto prevOpacity = prevPlacement.opacities.find(placementPair.first); + if (prevOpacity != prevPlacement.opacities.end()) { + opacities.emplace(placementPair.first, JointOpacityState(prevOpacity->second, increment, placementPair.second.icon, placementPair.second.text)); + placementChanged = placementChanged || + placementPair.second.icon != prevOpacity->second.icon.placed || + placementPair.second.text != prevOpacity->second.text.placed; + } else { + opacities.emplace(placementPair.first, JointOpacityState(placementPair.second.icon, placementPair.second.text)); + placementChanged = placementChanged || placementPair.second.icon || placementPair.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::unordered_set seenCrossTileIDs; + for (RenderTile& renderTile : symbolLayer.renderTiles) { + if (!renderTile.tile.isRenderable()) { + continue; + } + + auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl); + assert(dynamic_cast(bucket)); + SymbolBucket& symbolBucket = *reinterpret_cast(bucket); + updateBucketOpacities(symbolBucket, seenCrossTileIDs); + } +} + +void Placement::updateBucketOpacities(SymbolBucket& bucket, std::unordered_set& 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); + + 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); + } + +} + +float Placement::symbolFadeChange(TimePoint now) const { + if (mapMode == MapMode::Still) { + return 1.0; + } + return std::chrono::duration(now - commitTime) / Duration(std::chrono::milliseconds(300)); +} + +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..a50fc47125 --- /dev/null +++ b/src/mbgl/text/placement.hpp @@ -0,0 +1,82 @@ +#pragma once + +#include +#include +#include +#include +#include +#include + +namespace mbgl { + + class RenderSymbolLayer; + class SymbolBucket; + + class OpacityState { + public: + OpacityState(bool placed); + OpacityState(const OpacityState& prevOpacityState, float increment, bool placed); + bool isHidden() const; + float opacity; + bool placed; + }; + + class JointOpacityState { + public: + JointOpacityState(bool placedIcon, bool placedText); + JointOpacityState(const JointOpacityState& prevOpacityState, float increment, bool placedIcon, bool placedText); + bool isHidden() const; + OpacityState icon; + OpacityState text; + }; + + class PlacementPair { + public: + PlacementPair(bool text_, bool icon_) : text(text_), icon(icon_) {} + bool text; + bool icon; + }; + + 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& seenCrossTileIDs); + + void updateBucketOpacities(SymbolBucket&, std::unordered_set&); + + CollisionIndex collisionIndex; + + TransformState state; + MapMode mapMode; + TimePoint commitTime; + + std::unordered_map placements; + std::unordered_map opacities; + + TimePoint recentUntil; + bool stale = false; + }; + +} // namespace mbgl -- cgit v1.2.1