From ce3370f38f519586cce16f97e9ad3dddf36d3666 Mon Sep 17 00:00:00 2001 From: Mikhail Pozdnyakov Date: Fri, 31 Jan 2020 14:42:12 +0200 Subject: [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. --- .../all-anchors-tile-map-mode/expected.png | Bin 158810 -> 160213 bytes src/mbgl/text/collision_index.cpp | 13 ++- src/mbgl/text/collision_index.hpp | 11 ++- src/mbgl/text/placement.cpp | 91 ++++++++++++++++----- 4 files changed, 80 insertions(+), 35 deletions(-) diff --git a/metrics/expectations/platform-all/render-tests/text-variable-anchor/all-anchors-tile-map-mode/expected.png b/metrics/expectations/platform-all/render-tests/text-variable-anchor/all-anchors-tile-map-mode/expected.png index 8b02991f2f..75af66e6a0 100644 Binary files a/metrics/expectations/platform-all/render-tests/text-variable-anchor/all-anchors-tile-map-mode/expected.png and b/metrics/expectations/platform-all/render-tests/text-variable-anchor/all-anchors-tile-map-mode/expected.png differ 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 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 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; explicit CollisionIndex(const TransformState&, MapMode); - bool featureIntersectsTileBorders(const CollisionFeature& feature, - Point shift, - const mat4& posMatrix, - const float textPixelRatio, - const CollisionBoundaries& tileEdges) const; - + bool intercectsTileEdges(const CollisionBox&, + Point shift, + const mat4& posMatrix, + const float textPixelRatio, + const CollisionBoundaries& tileEdges) const; std::pair placeFeature( const CollisionFeature& feature, Point shift, diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp index 8740e4b021..49c3831d63 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> sorted(symbolInstances.begin(), - symbolInstances.end()); + std::vector> symbolInstances(bucket.symbolInstances.begin(), + bucket.symbolInstances.end()); optional variableAnchor; if (!variableTextAnchors.empty()) variableAnchor = variableTextAnchors.front(); - std::unordered_map sortedCache; - sortedCache.reserve(sorted.size()); - auto intersectsTileBorder = [&](const SymbolInstance& symbol) -> bool { - if (symbol.textCollisionFeature.alongLine || symbol.textCollisionFeature.boxes.empty()) return false; + std::unordered_map 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 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 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 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 offset{}; if (variableAnchor) { @@ -589,18 +615,41 @@ 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) { + if (a.textCollisionFeature.alongLine || a.textCollisionFeature.boxes.empty()) return false; + if (b.textCollisionFeature.alongLine || 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); } -- cgit v1.2.1