[core] Add Placement class.

Responsible for running global collision detection/symbol placement algorithm and updating symbol opacity buffers accordingly.

3 files changed, 391 insertions, 0 deletions

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 <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_) : 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<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(renderTile.matrix,
+                layout.get<TextPitchAlignment>() == style::AlignmentType::Map,
+                layout.get<TextRotationAlignment>() == style::AlignmentType::Map,
+                state,
+                pixelsToTileUnits);
+
+        mat4 iconLabelPlaneMatrix = getLabelPlaneMatrix(renderTile.matrix,
+                layout.get<IconPitchAlignment>() == style::AlignmentType::Map,
+                layout.get<IconRotationAlignment>() == 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<uint32_t>& seenCrossTileIDs) {
+
+    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) {
+            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<TextAllowOverlap>(),
+                        bucket.layout.get<TextPitchAlignment>() == 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<IconAllowOverlap>(),
+                        bucket.layout.get<IconPitchAlignment>() == 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<TextIgnorePlacement>());
+            }
+
+            if (placeIcon) {
+                collisionIndex.insertFeature(symbolInstance.iconCollisionFeature, bucket.layout.get<IconIgnorePlacement>());
+            }
+
+            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<float>(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<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::unordered_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);
+
+        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<float>(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 <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);
+            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<uint32_t>& seenCrossTileIDs);
+
+            void updateBucketOpacities(SymbolBucket&, std::unordered_set<uint32_t>&);
+        
+            CollisionIndex collisionIndex;
+
+            TransformState state;
+            MapMode mapMode;
+            TimePoint commitTime;
+
+            std::unordered_map<uint32_t,PlacementPair> placements;
+            std::unordered_map<uint32_t,JointOpacityState> opacities;
+        
+            TimePoint recentUntil;
+            bool stale = false;
+    };
+
+} // namespace mbgl