From 761ef9cc8f375aff9a0d756e78da0de994aa1d3f Mon Sep 17 00:00:00 2001 From: Ansis Brammanis Date: Tue, 11 Feb 2020 11:24:14 -0500 Subject: [core] sort symbols using symbol-sort-key before placement (#16023) fix #15964 partially port mapbox/mapbox-gl-js#9054 --- src/mbgl/layout/symbol_instance.hpp | 7 ++ src/mbgl/layout/symbol_layout.cpp | 23 +++- src/mbgl/layout/symbol_layout.hpp | 2 + src/mbgl/renderer/buckets/symbol_bucket.cpp | 2 + src/mbgl/renderer/buckets/symbol_bucket.hpp | 2 + src/mbgl/renderer/layers/render_symbol_layer.cpp | 25 +++- src/mbgl/renderer/render_layer.hpp | 16 ++- src/mbgl/text/placement.cpp | 29 +++-- src/mbgl/text/placement.hpp | 3 + test/gl/bucket.test.cpp | 15 ++- test/text/cross_tile_symbol_index.test.cpp | 149 +++++++++++++++++++++-- 11 files changed, 242 insertions(+), 31 deletions(-) diff --git a/src/mbgl/layout/symbol_instance.hpp b/src/mbgl/layout/symbol_instance.hpp index 4a57b527f7..35426ba9cf 100644 --- a/src/mbgl/layout/symbol_instance.hpp +++ b/src/mbgl/layout/symbol_instance.hpp @@ -122,4 +122,11 @@ public: uint32_t crossTileID = 0; }; +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 d0227c36c5..f25147f6de 100644 --- a/src/mbgl/layout/symbol_layout.cpp +++ b/src/mbgl/layout/symbol_layout.cpp @@ -107,7 +107,7 @@ SymbolLayout::SymbolLayout(const BucketParameters& parameters, const bool hasSymbolSortKey = !leader.layout.get().isUndefined(); const auto symbolZOrder = layout->get(); - 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() || layout->get() || layout->get() || layout->get()); @@ -560,6 +560,14 @@ void SymbolLayout::addFeature(const std::size_t layoutFeatureIndex, 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()}); + } + } } }; @@ -679,8 +687,17 @@ std::vector CalculateTileDistances(const GeometryCoordinates& line, const } void SymbolLayout::createBucket(const ImagePositions&, std::unique_ptr&, std::unordered_map& renderData, const bool firstLoad, const bool showCollisionBoxes) { - auto bucket = std::make_shared(layout, layerPaintProperties, textSize, iconSize, zoom, iconsNeedLinear, - sortFeaturesByY, bucketLeaderID, std::move(symbolInstances), tilePixelRatio, + auto bucket = std::make_shared(layout, + layerPaintProperties, + textSize, + iconSize, + zoom, + iconsNeedLinear, + 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 1abcaaa5d6..e8472a7406 100644 --- a/src/mbgl/layout/symbol_layout.hpp +++ b/src/mbgl/layout/symbol_layout.hpp @@ -44,6 +44,7 @@ public: const std::string bucketLeaderID; std::vector symbolInstances; + std::vector sortKeyRanges; static constexpr float INVALID_OFFSET_VALUE = std::numeric_limits::max(); /** @@ -105,6 +106,7 @@ private: bool iconsNeedLinear = false; bool sortFeaturesByY = false; + bool sortFeaturesByKey = false; bool allowVerticalPlacement = false; std::vector placementModes; diff --git a/src/mbgl/renderer/buckets/symbol_bucket.cpp b/src/mbgl/renderer/buckets/symbol_bucket.cpp index 03ab1c87d1..846161cacc 100644 --- a/src/mbgl/renderer/buckets/symbol_bucket.cpp +++ b/src/mbgl/renderer/buckets/symbol_bucket.cpp @@ -22,6 +22,7 @@ SymbolBucket::SymbolBucket(Immutable&& symbolInstances_, + const std::vector&& sortKeyRanges_, float tilePixelRatio_, bool allowVerticalPlacement_, std::vector placementModes_) @@ -36,6 +37,7 @@ SymbolBucket::SymbolBucket(Immutable&&, + const std::vector&&, const float tilePixelRatio, bool allowVerticalPlacement, std::vector placementModes); @@ -100,6 +101,7 @@ public: bool hasVariablePlacement : 1; std::vector symbolInstances; + std::vector sortKeyRanges; struct PaintProperties { SymbolIconProgram::Binders iconBinders; diff --git a/src/mbgl/renderer/layers/render_symbol_layer.cpp b/src/mbgl/renderer/layers/render_symbol_layer.cpp index a4a73d3fe5..23ee215705 100644 --- a/src/mbgl/renderer/layers/render_symbol_layer.cpp +++ b/src/mbgl/renderer/layers/render_symbol_layer.cpp @@ -362,6 +362,8 @@ void RenderSymbolLayer::render(PaintParameters& parameters) { assert(bucket.paintProperties.find(getID()) != bucket.paintProperties.end()); const auto& bucketPaintProperties = bucket.paintProperties.at(getID()); + bucket.justReloaded = false; + auto addRenderables = [&renderableSegments, &tile, renderData, &bucketPaintProperties, it = renderableSegments.begin()] (auto& segments, const SymbolType type) mutable { for (auto& segment : segments) { it = renderableSegments.emplace_hint(it, SegmentWrapper{std::ref(segment)}, tile, *renderData, bucketPaintProperties, segment.sortKey, type); @@ -518,7 +520,28 @@ void RenderSymbolLayer::prepare(const LayerPrepareParameters& params) { const Tile* tile = params.source->getRenderedTile(renderTile.id); assert(tile); assert(tile->kind == Tile::Kind::Geometry); - placementData.push_back({*bucket, renderTile, static_cast(tile)->getFeatureIndex()}); + + bool firstInBucket = true; + auto featureIndex = static_cast(tile)->getFeatureIndex(); + + if (bucket->sortKeyRanges.empty()) { + placementData.push_back( + {*bucket, renderTile, featureIndex, firstInBucket, 0.0f, 0, bucket->symbolInstances.size()}); + } else { + for (const SortKeyRange& sortKeyRange : bucket->sortKeyRanges) { + LayerPlacementData layerData{*bucket, + renderTile, + featureIndex, + firstInBucket, + sortKeyRange.sortKey, + sortKeyRange.symbolInstanceStart, + sortKeyRange.symbolInstanceEnd}; + auto sortPosition = std::upper_bound(placementData.cbegin(), placementData.cend(), layerData); + placementData.insert(sortPosition, std::move(layerData)); + + firstInBucket = false; + } + } } } } diff --git a/src/mbgl/renderer/render_layer.hpp b/src/mbgl/renderer/render_layer.hpp index ba3c638f88..4931893271 100644 --- a/src/mbgl/renderer/render_layer.hpp +++ b/src/mbgl/renderer/render_layer.hpp @@ -1,11 +1,11 @@ #pragma once +#include #include #include #include #include #include #include - #include #include @@ -20,6 +20,7 @@ class RenderTile; class TransformState; class PatternAtlas; class LineAtlas; +class SymbolBucket; class LayerRenderData { public: @@ -29,9 +30,16 @@ public: class LayerPlacementData { public: + friend bool operator<(const LayerPlacementData& lhs, const LayerPlacementData& rhs) { + return lhs.sortKey < rhs.sortKey; + } std::reference_wrapper bucket; std::reference_wrapper tile; std::shared_ptr featureIndex; + bool firstInBucket; + float sortKey; + size_t symbolInstanceStart; + size_t symbolInstanceEnd; }; class LayerPrepareParameters { @@ -95,9 +103,7 @@ public: virtual void prepare(const LayerPrepareParameters&); - const std::vector& getPlacementData() const { - return placementData; - } + const std::list& getPlacementData() const { return placementData; } // Latest evaluated properties. Immutable evaluatedProperties; @@ -126,7 +132,7 @@ protected: // evaluated StyleProperties object and is updated accordingly. RenderPass passes = RenderPass::None; - std::vector placementData; + std::list placementData; private: // Some layers may not render correctly on some hardware when the vertex attribute limit of diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp index ecc8f93032..fc6db89cd6 100644 --- a/src/mbgl/text/placement.cpp +++ b/src/mbgl/text/placement.cpp @@ -1,3 +1,4 @@ +#include #include #include @@ -110,12 +111,14 @@ void Placement::placeLayer(const RenderLayer& layer, const mat4& projMatrix, boo std::set seenCrossTileIDs; for (const auto& item : layer.getPlacementData()) { Bucket& bucket = item.bucket; - BucketPlacementParameters params{ - item.tile, - projMatrix, - layer.baseImpl->source, - item.featureIndex, - showCollisionBoxes}; + BucketPlacementParameters params{item.tile, + projMatrix, + layer.baseImpl->source, + item.featureIndex, + item.sortKey, + item.symbolInstanceStart, + item.symbolInstanceEnd, + showCollisionBoxes}; bucket.place(*this, params, seenCrossTileIDs); } } @@ -518,13 +521,15 @@ void Placement::placeBucket( placeSymbol(*it); } } else { - for (const SymbolInstance& symbol : bucket.symbolInstances) { - placeSymbol(symbol); + auto beginIt = bucket.symbolInstances.begin() + params.symbolInstanceStart; + auto endIt = bucket.symbolInstances.begin() + params.symbolInstanceEnd; + assert(params.symbolInstanceStart < params.symbolInstanceEnd); + assert(params.symbolInstanceEnd <= bucket.symbolInstances.size()); + for (auto it = beginIt; it != endIt; ++it) { + placeSymbol(*it); } } - bucket.justReloaded = false; - // As long as this placement lives, we have to hold onto this bucket's // matching FeatureIndex/data for querying purposes retainedQueryData.emplace(std::piecewise_construct, @@ -590,7 +595,9 @@ void Placement::commit(TimePoint now, const double zoom) { void Placement::updateLayerBuckets(const RenderLayer& layer, const TransformState& state, bool updateOpacities) const { std::set seenCrossTileIDs; for (const auto& item : layer.getPlacementData()) { - item.bucket.get().updateVertices(*this, updateOpacities, state, item.tile, seenCrossTileIDs); + if (item.firstInBucket) { + item.bucket.get().updateVertices(*this, updateOpacities, state, item.tile, seenCrossTileIDs); + } } } diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp index e2d634c54b..595515d9e9 100644 --- a/src/mbgl/text/placement.hpp +++ b/src/mbgl/text/placement.hpp @@ -91,6 +91,9 @@ public: const mat4& projMatrix; std::string sourceId; std::shared_ptr featureIndex; + float sortKey; + size_t symbolInstanceStart; + size_t symbolInstanceEnd; bool showCollisionBoxes; }; diff --git a/test/gl/bucket.test.cpp b/test/gl/bucket.test.cpp index 13b30eb75d..b9fae18f31 100644 --- a/test/gl/bucket.test.cpp +++ b/test/gl/bucket.test.cpp @@ -123,9 +123,22 @@ TEST(Buckets, SymbolBucket) { bool sortFeaturesByY = false; std::string bucketLeaderID = "test"; std::vector symbolInstances; + std::vector symbolRanges; gl::Context context{ backend }; - SymbolBucket bucket { std::move(layout), {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(symbolInstances), 1.0f, false, {}}; + SymbolBucket bucket{std::move(layout), + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(symbolInstances), + std::move(symbolRanges), + 1.0f, + false, + {}}; ASSERT_FALSE(bucket.hasIconData()); ASSERT_FALSE(bucket.hasSdfIconData()); ASSERT_FALSE(bucket.hasTextData()); diff --git a/test/text/cross_tile_symbol_index.test.cpp b/test/text/cross_tile_symbol_index.test.cpp index 4ff84063f9..625d95a9e5 100644 --- a/test/text/cross_tile_symbol_index.test.cpp +++ b/test/text/cross_tile_symbol_index.test.cpp @@ -37,9 +37,22 @@ TEST(CrossTileSymbolLayerIndex, addBucket) { OverscaledTileID mainID(6, 0, 6, 8, 8); std::vector mainInstances; + std::vector mainRanges; mainInstances.push_back(makeSymbolInstance(1000, 1000, u"Detroit")); mainInstances.push_back(makeSymbolInstance(2000, 2000, u"Toronto")); - SymbolBucket mainBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(mainInstances), 1.0f, false, {} }; + SymbolBucket mainBucket{layout, + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(mainInstances), + std::move(mainRanges), + 1.0f, + false, + {}}; mainBucket.bucketInstanceId = ++maxBucketInstanceId; index.addBucket(mainID, mainBucket, maxCrossTileID); @@ -50,11 +63,24 @@ TEST(CrossTileSymbolLayerIndex, addBucket) { OverscaledTileID childID(7, 0, 7, 16, 16); std::vector childInstances; + std::vector childRanges; childInstances.push_back(makeSymbolInstance(2000, 2000, u"Detroit")); childInstances.push_back(makeSymbolInstance(2000, 2000, u"Windsor")); childInstances.push_back(makeSymbolInstance(3000, 3000, u"Toronto")); childInstances.push_back(makeSymbolInstance(4001, 4001, u"Toronto")); - SymbolBucket childBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(childInstances), 1.0f, false, {} }; + SymbolBucket childBucket{layout, + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(childInstances), + std::move(childRanges), + 1.0f, + false, + {}}; childBucket.bucketInstanceId = ++maxBucketInstanceId; index.addBucket(childID, childBucket, maxCrossTileID); @@ -69,8 +95,21 @@ TEST(CrossTileSymbolLayerIndex, addBucket) { OverscaledTileID parentID(5, 0, 5, 4, 4); std::vector parentInstances; + std::vector parentRanges; parentInstances.push_back(makeSymbolInstance(500, 500, u"Detroit")); - SymbolBucket parentBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(parentInstances), 1.0f, false, {} }; + SymbolBucket parentBucket{layout, + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(parentInstances), + std::move(parentRanges), + 1.0f, + false, + {}}; parentBucket.bucketInstanceId = ++maxBucketInstanceId; index.addBucket(parentID, parentBucket, maxCrossTileID); @@ -84,9 +123,22 @@ TEST(CrossTileSymbolLayerIndex, addBucket) { // grandchild OverscaledTileID grandchildID(8, 0, 8, 32, 32); std::vector grandchildInstances; + std::vector grandchildRanges; grandchildInstances.push_back(makeSymbolInstance(4000, 4000, u"Detroit")); grandchildInstances.push_back(makeSymbolInstance(4000, 4000, u"Windsor")); - SymbolBucket grandchildBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(grandchildInstances), 1.0f, false, {} }; + SymbolBucket grandchildBucket{layout, + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(grandchildInstances), + std::move(grandchildRanges), + 1.0f, + false, + {}}; grandchildBucket.bucketInstanceId = ++maxBucketInstanceId; index.addBucket(grandchildID, grandchildBucket, maxCrossTileID); @@ -111,14 +163,40 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) { OverscaledTileID mainID(6, 0, 6, 8, 8); std::vector mainInstances; + std::vector mainRanges; mainInstances.push_back(makeSymbolInstance(1000, 1000, u"Detroit")); - SymbolBucket mainBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(mainInstances), 1.0f, false, {} }; + SymbolBucket mainBucket{layout, + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(mainInstances), + std::move(mainRanges), + 1.0f, + false, + {}}; mainBucket.bucketInstanceId = ++maxBucketInstanceId; OverscaledTileID childID(7, 0, 7, 16, 16); std::vector childInstances; + std::vector childRanges; childInstances.push_back(makeSymbolInstance(2000, 2000, u"Detroit")); - SymbolBucket childBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(childInstances), 1.0f, false, {} }; + SymbolBucket childBucket{layout, + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(childInstances), + std::move(childRanges), + 1.0f, + false, + {}}; childBucket.bucketInstanceId = ++maxBucketInstanceId; // assigns a new id @@ -151,17 +229,43 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) { OverscaledTileID mainID(6, 0, 6, 8, 8); std::vector mainInstances; + std::vector mainRanges; mainInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A mainInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B - SymbolBucket mainBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(mainInstances), 1.0f, false, {} }; + SymbolBucket mainBucket{layout, + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(mainInstances), + std::move(mainRanges), + 1.0f, + false, + {}}; mainBucket.bucketInstanceId = ++maxBucketInstanceId; OverscaledTileID childID(7, 0, 7, 16, 16); std::vector childInstances; + std::vector childRanges; childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // A' childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // B' childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // C' - SymbolBucket childBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(childInstances), 1.0f, false, {} }; + SymbolBucket childBucket{layout, + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(childInstances), + std::move(childRanges), + 1.0f, + false, + {}}; childBucket.bucketInstanceId = ++maxBucketInstanceId; // assigns new ids @@ -191,14 +295,39 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) { std::vector firstInstances; firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B - SymbolBucket firstBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(firstInstances), 1.0f, false, {} }; + SymbolBucket firstBucket{layout, + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(firstInstances), + {}, + 1.0f, + false, + {}}; firstBucket.bucketInstanceId = ++maxBucketInstanceId; std::vector secondInstances; + std::vector secondRanges; secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A' secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B' secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // C' - SymbolBucket secondBucket { layout, {}, 16.0f, 1.0f, 0, iconsNeedLinear, sortFeaturesByY, bucketLeaderID, std::move(secondInstances), 1.0f, false, {} }; + SymbolBucket secondBucket{layout, + {}, + 16.0f, + 1.0f, + 0, + iconsNeedLinear, + sortFeaturesByY, + bucketLeaderID, + std::move(secondInstances), + std::move(secondRanges), + 1.0f, + false, + {}}; secondBucket.bucketInstanceId = ++maxBucketInstanceId; // assigns new ids -- cgit v1.2.1