[tile mode] Place symbols in viewport-y orderupstream/mikhail_tile_mode_y_ordered_placement

In case multiple symbols are grouped close to the tile borders,
different tiles might place different symbols as each tile arbitrary
assigns feature ids, and these ids define the placement order being
applied. This causes artifacts at the tile boundaries.

With this change, in tile mode the placement order is defined by viewport-y
order. It means that the symbols are being placed the same order across all
the tiles.

3 files changed, 35 insertions, 22 deletions

diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp
index e75bdf8ba9..2f98ac6897 100644
--- a/src/mbgl/text/collision_index.cpp
+++ b/src/mbgl/text/collision_index.cpp
@@ -96,16 +96,18 @@ inline bool CollisionIndex::overlapsTile(const CollisionBoundaries& boundaries,
            boundaries[1] < tileBoundaries[3] && boundaries[3] > tileBoundaries[1];
 }
 
-bool CollisionIndex::featureIntersectsTileBorders(const CollisionFeature& feature,
-                                                  Point<float> shift,
-                                                  const mat4& posMatrix,
-                                                  const float textPixelRatio,
-                                                  const CollisionBoundaries& tileEdges) const {
+FeatureLocation CollisionIndex::getFeatureLocation(const CollisionFeature& feature,
+                                                   Point<float> shift,
+                                                   const mat4& posMatrix,
+                                                   const float textPixelRatio,
+                                                   const CollisionBoundaries& tileEdges) const {
     assert(!feature.alongLine);
     assert(!feature.boxes.empty());
     const CollisionBox& box = feature.boxes.front();
     auto collisionBoundaries = getProjectedCollisionBoundaries(posMatrix, shift, textPixelRatio, box);
-    return overlapsTile(collisionBoundaries, tileEdges) && !isInsideTile(collisionBoundaries, tileEdges);
+    if (isInsideTile(collisionBoundaries, tileEdges)) return FeatureLocation::InsideTile;
+    if (overlapsTile(collisionBoundaries, tileEdges)) return FeatureLocation::IntersectsTileBorder;
+    return FeatureLocation::OutsideTile;
 }
 
 std::pair<bool, bool> CollisionIndex::placeFeature(
diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp
index b9f3e9d88a..5b3da3a9be 100644
--- a/src/mbgl/text/collision_index.hpp
+++ b/src/mbgl/text/collision_index.hpp
@@ -16,17 +16,22 @@ struct TileDistance;
 
 using CollisionBoundaries = std::array<float, 4>; // [x1, y1, x2, y2]
 
+enum class FeatureLocation : uint8_t {
+    InsideTile = 0,
+    OutsideTile,
+    IntersectsTileBorder,
+};
+
 class CollisionIndex {
 public:
     using CollisionGrid = GridIndex<IndexedSubfeature>;
 
     explicit CollisionIndex(const TransformState&, MapMode);
-    bool featureIntersectsTileBorders(const CollisionFeature& feature,
-                                      Point<float> shift,
-                                      const mat4& posMatrix,
-                                      const float textPixelRatio,
-                                      const CollisionBoundaries& tileEdges) const;
-
+    FeatureLocation getFeatureLocation(const CollisionFeature& feature,
+                                       Point<float> shift,
+                                       const mat4& posMatrix,
+                                       const float textPixelRatio,
+                                       const CollisionBoundaries& tileEdges) const;
     std::pair<bool, bool> placeFeature(
         const CollisionFeature& feature,
         Point<float> shift,
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
index 8740e4b021..b87e921a91 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -356,8 +356,9 @@ void Placement::placeBucket(const SymbolBucket& bucket,
                         textBoxes.clear();
 
                         if (mapMode == MapMode::Tile && !isFirstAnchor &&
-                            collisionIndex.featureIntersectsTileBorders(
-                                textCollisionFeature, shift, posMatrix, pixelRatio, *tileBorders)) {
+                            (FeatureLocation::IntersectsTileBorder ==
+                             collisionIndex.getFeatureLocation(
+                                 textCollisionFeature, shift, posMatrix, pixelRatio, *tileBorders))) {
                             continue;
                         }
 
@@ -561,17 +562,16 @@ void Placement::placeBucket(const SymbolBucket& bucket,
     } else if (mapMode == MapMode::Tile && !avoidEdges) {
         // 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.
-        const auto& symbolInstances = bucket.symbolInstances;
+        const auto& symbolInstances = bucket.getSortedSymbols(state.getBearing());
         std::vector<std::reference_wrapper<const SymbolInstance>> sorted(symbolInstances.begin(),
                                                                          symbolInstances.end());
         optional<style::TextVariableAnchorType> variableAnchor;
         if (!variableTextAnchors.empty()) variableAnchor = variableTextAnchors.front();
-        std::unordered_map<uint32_t, bool> sortedCache;
-        sortedCache.reserve(sorted.size());
 
-        auto intersectsTileBorder = [&](const SymbolInstance& symbol) -> bool {
-            if (symbol.textCollisionFeature.alongLine || symbol.textCollisionFeature.boxes.empty()) return false;
+        std::unordered_map<uint32_t, FeatureLocation> sortedCache;
+        sortedCache.reserve(sorted.size());
 
+        auto getFeatureLocation = [&](const SymbolInstance& symbol) -> FeatureLocation {
             auto it = sortedCache.find(symbol.crossTileID);
             if (it != sortedCache.end()) return it->second;
 
@@ -589,15 +589,21 @@ void Placement::placeBucket(const SymbolBucket& bucket,
                                                        pitchTextWithMap,
                                                        state.getBearing());
             }
-            bool result = collisionIndex.featureIntersectsTileBorders(
+            FeatureLocation result = collisionIndex.getFeatureLocation(
                 symbol.textCollisionFeature, offset, posMatrix, pixelRatio, *tileBorders);
             sortedCache.insert(std::make_pair(symbol.crossTileID, result));
             return result;
         };
 
         std::stable_sort(
-            sorted.begin(), sorted.end(), [&intersectsTileBorder](const SymbolInstance& a, const SymbolInstance& b) {
-                return intersectsTileBorder(a) && !intersectsTileBorder(b);
+            sorted.begin(), sorted.end(), [&getFeatureLocation](const SymbolInstance& a, const SymbolInstance& b) {
+                if (a.textCollisionFeature.alongLine || a.textCollisionFeature.boxes.empty()) return false;
+                if (b.textCollisionFeature.alongLine || b.textCollisionFeature.boxes.empty()) return false;
+
+                auto locationA = getFeatureLocation(a);
+                auto locationB = getFeatureLocation(b);
+                return (locationA == FeatureLocation::IntersectsTileBorder) &&
+                       (locationB == FeatureLocation::InsideTile);
             });
 
         for (const SymbolInstance& symbol : sorted) {