[core] Set sortKey for symbol segments during layout phase

3 files changed, 29 insertions, 10 deletions

diff --git a/src/mbgl/layout/symbol_feature.hpp b/src/mbgl/layout/symbol_feature.hpp
index e16dd0b2f3..445a370630 100644
--- a/src/mbgl/layout/symbol_feature.hpp
+++ b/src/mbgl/layout/symbol_feature.hpp
@@ -26,6 +26,7 @@ public:
     GeometryCollection geometry;
     optional<TaggedString> formattedText;
     optional<std::string> icon;
+    unsigned int sortKey = 0u;
     std::size_t index;
 };
 
diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp
index badc352f76..1f1dff0488 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -96,6 +96,13 @@ SymbolLayout::SymbolLayout(const BucketParameters& parameters,
         return;
     }
 
+    const bool hasSymbolSortKey = !leader.layout.get<SymbolSortKey>().isUndefined();
+    const auto symbolZOrder = layout.get<SymbolZOrder>();
+    const bool 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>());
+
     for (const auto& layer : layers) {
         layerPaintProperties.emplace(layer->getID(), toRenderSymbolLayer(layer)->evaluated);
     }
@@ -155,6 +162,10 @@ SymbolLayout::SymbolLayout(const BucketParameters& parameters,
             imageDependencies.emplace(*ft.icon, ImageType::Icon);
         }
 
+        if (sortFeaturesByKey) {
+            ft.sortKey = static_cast<unsigned int>(layout.evaluate<SymbolSortKey>(zoom, ft));
+        }
+
         if (ft.formattedText || ft.icon) {
             features.push_back(std::move(ft));
         }
@@ -163,6 +174,12 @@ SymbolLayout::SymbolLayout(const BucketParameters& parameters,
     if (layout.get<SymbolPlacement>() == SymbolPlacementType::Line) {
         util::mergeLines(features);
     }
+
+    if (sortFeaturesByKey) {
+        std::sort(features.begin(), features.end(), [](const auto& a, const auto& b) {
+            return a.sortKey < b.sortKey;
+        });
+    }
 }
 
 bool SymbolLayout::hasDependencies() const {
@@ -541,10 +558,6 @@ std::vector<float> CalculateTileDistances(const GeometryCoordinates& line, const
 }
 
 void SymbolLayout::createBucket(const ImagePositions&, std::unique_ptr<FeatureIndex>&, std::unordered_map<std::string, std::shared_ptr<Bucket>>& buckets, const bool firstLoad, const bool showCollisionBoxes) {
-    const bool zOrderByViewport = layout.get<SymbolZOrder>() == SymbolZOrderType::ViewportY;
-    const bool sortFeaturesByY = zOrderByViewport && (layout.get<TextAllowOverlap>() || layout.get<IconAllowOverlap>() ||
-        layout.get<TextIgnorePlacement>() || layout.get<IconIgnorePlacement>());
-
     auto bucket = std::make_shared<SymbolBucket>(layout, layerPaintProperties, textSize, iconSize, zoom, sdfIcons, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(symbolInstances), tilePixelRatio);
 
     for (SymbolInstance &symbolInstance : bucket->symbolInstances) {
@@ -590,7 +603,7 @@ void SymbolLayout::createBucket(const ImagePositions&, std::unique_ptr<FeatureIn
                 symbolInstance.placedIconIndex = bucket->icon.placedSymbols.size() - 1;
                 PlacedSymbol& iconSymbol = bucket->icon.placedSymbols.back();
                 iconSymbol.vertexStartIndex = addSymbol(bucket->icon, sizeData, *symbolInstance.iconQuad,
-                                                        symbolInstance.anchor, iconSymbol);
+                                                        symbolInstance.anchor, iconSymbol, feature.sortKey);
 
                 for (auto& pair : bucket->paintProperties) {
                     pair.second.iconBinders.populateVertexVectors(feature, bucket->icon.vertices.elements(), {}, {});
@@ -645,7 +658,7 @@ std::size_t SymbolLayout::addSymbolGlyphQuads(SymbolBucket& bucket,
             }
             lastAddedSection = symbolQuad.sectionIndex;
         }
-        size_t index = addSymbol(bucket.text, sizeData, symbolQuad, symbolInstance.anchor, placedSymbol);
+        size_t index = addSymbol(bucket.text, sizeData, symbolQuad, symbolInstance.anchor, placedSymbol, feature.sortKey);
         if (firstSymbol) {
             placedSymbol.vertexStartIndex = index;
             firstSymbol = false;
@@ -659,7 +672,8 @@ size_t SymbolLayout::addSymbol(SymbolBucket::Buffer& buffer,
                                const Range<float> sizeData,
                                const SymbolQuad& symbol,
                                const Anchor& labelAnchor,
-                               PlacedSymbol& placedSymbol) {
+                               PlacedSymbol& placedSymbol,
+                               unsigned int sortKey) {
     constexpr const uint16_t vertexLength = 4;
 
     const auto &tl = symbol.tl;
@@ -668,8 +682,10 @@ size_t SymbolLayout::addSymbol(SymbolBucket::Buffer& buffer,
     const auto &br = symbol.br;
     const auto &tex = symbol.tex;
 
-    if (buffer.segments.empty() || buffer.segments.back().vertexLength + vertexLength > std::numeric_limits<uint16_t>::max()) {
-        buffer.segments.emplace_back(buffer.vertices.elements(), buffer.triangles.elements());
+    if (buffer.segments.empty() ||
+        buffer.segments.back().sortKey != sortKey ||
+        buffer.segments.back().vertexLength + vertexLength > std::numeric_limits<uint16_t>::max()) {
+        buffer.segments.emplace_back(buffer.vertices.elements(), buffer.triangles.elements(), 0ul, 0ul, sortKey);
     }
 
     // We're generating triangle fans, so we always start with the first
diff --git a/src/mbgl/layout/symbol_layout.hpp b/src/mbgl/layout/symbol_layout.hpp
index d88c79c552..fa53bdec6a 100644
--- a/src/mbgl/layout/symbol_layout.hpp
+++ b/src/mbgl/layout/symbol_layout.hpp
@@ -66,7 +66,8 @@ private:
                      const Range<float> sizeData,
                      const SymbolQuad&,
                      const Anchor& labelAnchor,
-                     PlacedSymbol& placedSymbol);
+                     PlacedSymbol& placedSymbol,
+                     unsigned int sortKey);
 
     // Adds symbol quads to bucket and returns formatted section index of last
     // added quad.
@@ -97,6 +98,7 @@ private:
 
     bool sdfIcons = false;
     bool iconsNeedLinear = false;
+    bool sortFeaturesByY = false;
 
     style::TextSize::UnevaluatedType textSize;
     style::IconSize::UnevaluatedType iconSize;