[core] sort symbols using symbol-sort-key before placement (#16023)

fix #15964
partially port mapbox/mapbox-gl-js#9054

3 files changed, 44 insertions, 10 deletions

diff --git a/src/mbgl/layout/symbol_instance.hpp b/src/mbgl/layout/symbol_instance.hpp
index 3cd67125b4..3303e5f7e3 100644
--- a/src/mbgl/layout/symbol_instance.hpp
+++ b/src/mbgl/layout/symbol_instance.hpp
@@ -123,4 +123,11 @@ public:
     static constexpr uint32_t invalidCrossTileID() { return std::numeric_limits<uint32_t>::max(); }
 };
 
+class SortKeyRange {
+public:
+    float sortKey;
+    size_t symbolInstanceStart;
+    size_t symbolInstanceEnd;
+};
+
 } // namespace mbgl
diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp
index e0475f0acb..61c3b4ad66 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -106,7 +106,7 @@ SymbolLayout::SymbolLayout(const BucketParameters& parameters,
 
     const bool hasSymbolSortKey = !leader.layout.get<SymbolSortKey>().isUndefined();
     const auto symbolZOrder = layout->get<SymbolZOrder>();
-    const bool sortFeaturesByKey = symbolZOrder != SymbolZOrderType::ViewportY && hasSymbolSortKey;
+    sortFeaturesByKey = symbolZOrder != SymbolZOrderType::ViewportY && hasSymbolSortKey;
     const bool zOrderByViewportY = symbolZOrder == SymbolZOrderType::ViewportY || (symbolZOrder == SymbolZOrderType::Auto && !sortFeaturesByKey);
     sortFeaturesByY = zOrderByViewportY && (layout->get<TextAllowOverlap>() || layout->get<IconAllowOverlap>() ||
         layout->get<TextIgnorePlacement>() || layout->get<IconIgnorePlacement>());
@@ -572,9 +572,10 @@ void SymbolLayout::addFeature(const std::size_t layoutFeatureIndex,
         }
     }
 
-    auto addSymbolInstance = [&] (Anchor& anchor, std::shared_ptr<SymbolInstanceSharedData> sharedData) {
+    auto addSymbolInstance = [&](Anchor& anchor, std::shared_ptr<SymbolInstanceSharedData> sharedData) {
         assert(sharedData);
-        const bool anchorInsideTile = anchor.point.x >= 0 && anchor.point.x < util::EXTENT && anchor.point.y >= 0 && anchor.point.y < util::EXTENT;
+        const bool anchorInsideTile = anchor.point.x >= 0 && anchor.point.x < util::EXTENT && anchor.point.y >= 0 &&
+                                      anchor.point.y < util::EXTENT;
 
         if (mode == MapMode::Tile || anchorInsideTile) {
             // For static/continuous rendering, only add symbols anchored within this tile:
@@ -582,13 +583,36 @@ void SymbolLayout::addFeature(const std::size_t layoutFeatureIndex,
             // In tiled rendering mode, add all symbols in the buffers so that we can:
             //  (1) render symbols that overlap into this tile
             //  (2) approximate collision detection effects from neighboring symbols
-            symbolInstances.emplace_back(anchor, std::move(sharedData), shapedTextOrientations,
-                    shapedIcon, verticallyShapedIcon,
-                    textBoxScale, textPadding, textPlacement, textOffset,
-                    iconBoxScale, iconPadding, iconOffset, indexedFeature,
-                    layoutFeatureIndex, feature.index,
-                    feature.formattedText ? feature.formattedText->rawText() : std::u16string(),
-                    overscaling, iconRotation, textRotation, variableTextOffset, allowVerticalPlacement, iconType);
+            symbolInstances.emplace_back(anchor,
+                                         std::move(sharedData),
+                                         shapedTextOrientations,
+                                         shapedIcon,
+                                         verticallyShapedIcon,
+                                         textBoxScale,
+                                         textPadding,
+                                         textPlacement,
+                                         textOffset,
+                                         iconBoxScale,
+                                         iconPadding,
+                                         iconOffset,
+                                         indexedFeature,
+                                         layoutFeatureIndex,
+                                         feature.index,
+                                         feature.formattedText ? feature.formattedText->rawText() : std::u16string(),
+                                         overscaling,
+                                         iconRotation,
+                                         textRotation,
+                                         variableTextOffset,
+                                         allowVerticalPlacement,
+                                         iconType);
+
+            if (sortFeaturesByKey) {
+                if (sortKeyRanges.size() && sortKeyRanges.back().sortKey == feature.sortKey) {
+                    sortKeyRanges.back().symbolInstanceEnd = symbolInstances.size();
+                } else {
+                    sortKeyRanges.push_back({feature.sortKey, symbolInstances.size() - 1, symbolInstances.size()});
+                }
+            }
         }
     };
 
@@ -728,6 +752,7 @@ void SymbolLayout::createBucket(const ImagePositions&, std::unique_ptr<FeatureIn
                                                  sortFeaturesByY,
                                                  bucketLeaderID,
                                                  std::move(symbolInstances),
+                                                 std::move(sortKeyRanges),
                                                  tilePixelRatio,
                                                  allowVerticalPlacement,
                                                  std::move(placementModes),
diff --git a/src/mbgl/layout/symbol_layout.hpp b/src/mbgl/layout/symbol_layout.hpp
index b906b0b36c..52c912c8ae 100644
--- a/src/mbgl/layout/symbol_layout.hpp
+++ b/src/mbgl/layout/symbol_layout.hpp
@@ -45,6 +45,7 @@ public:
 
     const std::string bucketLeaderID;
     std::vector<SymbolInstance> symbolInstances;
+    std::vector<SortKeyRange> sortKeyRanges;
 
     static constexpr float INVALID_OFFSET_VALUE = std::numeric_limits<float>::max();
     /**
@@ -115,6 +116,7 @@ private:
 
     bool iconsNeedLinear = false;
     bool sortFeaturesByY = false;
+    bool sortFeaturesByKey = false;
     bool allowVerticalPlacement = false;
     bool iconsInText = false;
     std::vector<style::TextWritingModeType> placementModes;