[tile mode] Improvements in symbol placement on tile borders

This change fixes the following problems:
1) Before this change, when multiple symbols were grouped close to the
tile borders, different tiles could place different symbols, because each
tile arbitrary assigned feature ids, and these ids defined the placement
order being applied. This caused artifacts at the tile boundaries.

With this change, in tile mode the placement order of two symbols crossing
a tile border is defined by their anchor `y` values. It means that the
symbols are being placed the same order across all the tiles.

2) Before this change, the engine did not place with priority the symbols
crossing the borders between two neighboring tiles. Now it does, and it
improves a lot symbol placement stability in the tile map mode.

3 files changed, 82 insertions, 35 deletions

diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp
index e75bdf8ba9..a9386d0f9a 100644
--- a/src/mbgl/text/collision_index.cpp
+++ b/src/mbgl/text/collision_index.cpp
@@ -96,14 +96,11 @@ 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 {
-    assert(!feature.alongLine);
-    assert(!feature.boxes.empty());
-    const CollisionBox& box = feature.boxes.front();
+bool CollisionIndex::intercectsTileEdges(const CollisionBox& box,
+                                         Point<float> shift,
+                                         const mat4& posMatrix,
+                                         const float textPixelRatio,
+                                         const CollisionBoundaries& tileEdges) const {
     auto collisionBoundaries = getProjectedCollisionBoundaries(posMatrix, shift, textPixelRatio, box);
     return overlapsTile(collisionBoundaries, tileEdges) && !isInsideTile(collisionBoundaries, tileEdges);
 }
diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp
index b9f3e9d88a..2ed3ab81bc 100644
--- a/src/mbgl/text/collision_index.hpp
+++ b/src/mbgl/text/collision_index.hpp
@@ -21,12 +21,11 @@ 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;
-
+    bool intercectsTileEdges(const CollisionBox&,
+                             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..c927fdd782 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -356,8 +356,11 @@ void Placement::placeBucket(const SymbolBucket& bucket,
                         textBoxes.clear();
 
                         if (mapMode == MapMode::Tile && !isFirstAnchor &&
-                            collisionIndex.featureIntersectsTileBorders(
-                                textCollisionFeature, shift, posMatrix, pixelRatio, *tileBorders)) {
+                            collisionIndex.intercectsTileEdges(symbolInstance.textCollisionFeature.boxes.front(),
+                                                               shift,
+                                                               posMatrix,
+                                                               pixelRatio,
+                                                               *tileBorders)) {
                             continue;
                         }
 
@@ -561,19 +564,42 @@ 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;
-        std::vector<std::reference_wrapper<const SymbolInstance>> sorted(symbolInstances.begin(),
-                                                                         symbolInstances.end());
+        std::vector<std::reference_wrapper<const SymbolInstance>> symbolInstances(bucket.symbolInstances.begin(),
+                                                                                  bucket.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, bool> locationCache;
+        locationCache.reserve(symbolInstances.size());
 
-            auto it = sortedCache.find(symbol.crossTileID);
-            if (it != sortedCache.end()) return it->second;
+        // Keeps the data necessary to find a feature location according to a tile.
+        struct NeighborTileData {
+            NeighborTileData(const CollisionIndex& collisionIndex, UnwrappedTileID id_, Point<float> shift_)
+                : id(id_), shift(shift_), matrix() {
+                collisionIndex.getTransformState().matrixFor(matrix, id);
+                matrix::multiply(matrix, collisionIndex.getTransformState().getProjectionMatrix(), matrix);
+                borders = collisionIndex.projectTileBoundaries(matrix);
+            }
+
+            UnwrappedTileID id;
+            Point<float> shift;
+            mat4 matrix;
+            CollisionBoundaries borders;
+        };
+
+        uint8_t z = renderTile.id.canonical.z;
+        uint32_t x = renderTile.id.canonical.x;
+        uint32_t y = renderTile.id.canonical.y;
+        const std::array<NeighborTileData, 4> neightbors{{
+            {collisionIndex, UnwrappedTileID(z, x, y - 1), {0.0f, util::EXTENT}},  // top
+            {collisionIndex, UnwrappedTileID(z, x, y + 1), {0.0f, -util::EXTENT}}, // bottom
+            {collisionIndex, UnwrappedTileID(z, x - 1, y), {util::EXTENT, 0.0f}},  // left
+            {collisionIndex, UnwrappedTileID(z, x + 1, y), {-util::EXTENT, 0.0f}}  // right
+        }};
+
+        auto intercectsTileEdges = [&](const CollisionBox& collisionBox, const SymbolInstance& symbol) -> bool {
+            auto it = locationCache.find(symbol.crossTileID);
+            if (it != locationCache.end()) return it->second;
 
             Point<float> offset{};
             if (variableAnchor) {
@@ -589,18 +615,43 @@ void Placement::placeBucket(const SymbolBucket& bucket,
                                                        pitchTextWithMap,
                                                        state.getBearing());
             }
-            bool result = collisionIndex.featureIntersectsTileBorders(
-                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);
-            });
+            bool intercects =
+                collisionIndex.intercectsTileEdges(collisionBox, offset, renderTile.matrix, pixelRatio, *tileBorders);
+            if (!intercects) {
+                // Check if this symbol intersects the neighbor tile borders.
+                // If so, it also shall be placed with priority (location = FeatureLocation::IntersectsTileBorder).
+                for (const auto& neighbor : neightbors) {
+                    intercects = collisionIndex.intercectsTileEdges(
+                        collisionBox, offset + neighbor.shift, neighbor.matrix, pixelRatio, neighbor.borders);
+                    if (intercects) break;
+                }
+            }
+
+            locationCache.insert(std::make_pair(symbol.crossTileID, intercects));
+            return intercects;
+        };
 
-        for (const SymbolInstance& symbol : sorted) {
+        std::stable_sort(symbolInstances.begin(),
+                         symbolInstances.end(),
+                         [&intercectsTileEdges](const SymbolInstance& a, const SymbolInstance& b) {
+                             assert(!a.textCollisionFeature.alongLine);
+                             assert(!b.textCollisionFeature.alongLine);
+                             if (a.textCollisionFeature.boxes.empty() || b.textCollisionFeature.boxes.empty())
+                                 return false;
+
+                             auto intercectsA = intercectsTileEdges(a.textCollisionFeature.boxes.front(), a);
+                             auto intercectsB = intercectsTileEdges(b.textCollisionFeature.boxes.front(), b);
+                             if (intercectsA) {
+                                 if (!intercectsB) return true;
+                                 // Both symbols are inrecepting the tile borders, we need a universal cross-tile rule
+                                 // to define which of them shall be placed first - use anchor `y` point.
+                                 return a.anchor.point.y < b.anchor.point.y;
+                             }
+                             return false;
+                         });
+
+        for (const SymbolInstance& symbol : symbolInstances) {
             placeSymbol(symbol);
         }