From 4f18d5fa92df175ac30f856a9273a00349b56cc3 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 | 45 ++++++++++++++++++------ 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 | 2 ++ test/text/cross_tile_symbol_index.test.cpp | 24 ++++++++++++- 11 files changed, 130 insertions(+), 27 deletions(-) diff --git a/src/mbgl/layout/symbol_instance.hpp b/src/mbgl/layout/symbol_instance.hpp index 3cd67125b4..3303e5f7e3 100644 --- a/src/mbgl/layout/symbol_instance.hpp +++ b/src/mbgl/layout/symbol_instance.hpp @@ -123,4 +123,11 @@ public: static constexpr uint32_t invalidCrossTileID() { return std::numeric_limits::max(); } }; +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 e0475f0acb..61c3b4ad66 100644 --- a/src/mbgl/layout/symbol_layout.cpp +++ b/src/mbgl/layout/symbol_layout.cpp @@ -106,7 +106,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()); @@ -572,9 +572,10 @@ void SymbolLayout::addFeature(const std::size_t layoutFeatureIndex, } } - auto addSymbolInstance = [&] (Anchor& anchor, std::shared_ptr sharedData) { + auto addSymbolInstance = [&](Anchor& anchor, std::shared_ptr sharedData) { assert(sharedData); - const bool anchorInsideTile = anchor.point.x >= 0 && anchor.point.x < util::EXTENT && anchor.point.y >= 0 && anchor.point.y < util::EXTENT; + const bool anchorInsideTile = anchor.point.x >= 0 && anchor.point.x < util::EXTENT && anchor.point.y >= 0 && + anchor.point.y < util::EXTENT; if (mode == MapMode::Tile || anchorInsideTile) { // For static/continuous rendering, only add symbols anchored within this tile: @@ -582,13 +583,36 @@ void SymbolLayout::addFeature(const std::size_t layoutFeatureIndex, // In tiled rendering mode, add all symbols in the buffers so that we can: // (1) render symbols that overlap into this tile // (2) approximate collision detection effects from neighboring symbols - symbolInstances.emplace_back(anchor, std::move(sharedData), shapedTextOrientations, - shapedIcon, verticallyShapedIcon, - textBoxScale, textPadding, textPlacement, textOffset, - iconBoxScale, iconPadding, iconOffset, indexedFeature, - layoutFeatureIndex, feature.index, - feature.formattedText ? feature.formattedText->rawText() : std::u16string(), - overscaling, iconRotation, textRotation, variableTextOffset, allowVerticalPlacement, iconType); + symbolInstances.emplace_back(anchor, + std::move(sharedData), + shapedTextOrientations, + shapedIcon, + verticallyShapedIcon, + textBoxScale, + textPadding, + textPlacement, + textOffset, + iconBoxScale, + iconPadding, + iconOffset, + indexedFeature, + 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()}); + } + } } }; @@ -728,6 +752,7 @@ void SymbolLayout::createBucket(const ImagePositions&, std::unique_ptr symbolInstances; + std::vector sortKeyRanges; static constexpr float INVALID_OFFSET_VALUE = std::numeric_limits::max(); /** @@ -115,6 +116,7 @@ private: bool iconsNeedLinear = false; bool sortFeaturesByY = false; + bool sortFeaturesByKey = false; bool allowVerticalPlacement = false; bool iconsInText = false; std::vector placementModes; diff --git a/src/mbgl/renderer/buckets/symbol_bucket.cpp b/src/mbgl/renderer/buckets/symbol_bucket.cpp index 55002e7851..7b8eec4471 100644 --- a/src/mbgl/renderer/buckets/symbol_bucket.cpp +++ b/src/mbgl/renderer/buckets/symbol_bucket.cpp @@ -23,6 +23,7 @@ SymbolBucket::SymbolBucket(Immutable&& symbolInstances_, + const std::vector&& sortKeyRanges_, float tilePixelRatio_, bool allowVerticalPlacement_, std::vector placementModes_, @@ -40,6 +41,7 @@ SymbolBucket::SymbolBucket(Immutable&&, + const std::vector&&, const float tilePixelRatio, bool allowVerticalPlacement, std::vector placementModes, @@ -117,6 +118,7 @@ public: bool hasUninitializedSymbols : 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 17376fd864..955ad2ce51 100644 --- a/src/mbgl/renderer/layers/render_symbol_layer.cpp +++ b/src/mbgl/renderer/layers/render_symbol_layer.cpp @@ -424,6 +424,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); @@ -580,7 +582,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 c927fdd782..57cf1f0f1f 100644 --- a/src/mbgl/text/placement.cpp +++ b/src/mbgl/text/placement.cpp @@ -1,11 +1,11 @@ -#include - +#include #include #include #include #include #include #include +#include #include #include #include @@ -113,7 +113,12 @@ void Placement::placeLayer(const RenderLayer& layer) { std::set seenCrossTileIDs; for (const auto& item : layer.getPlacementData()) { Bucket& bucket = item.bucket; - BucketPlacementParameters params{item.tile, layer.baseImpl->source, item.featureIndex}; + BucketPlacementParameters params{item.tile, + layer.baseImpl->source, + item.featureIndex, + item.sortKey, + item.symbolInstanceStart, + item.symbolInstanceEnd}; bucket.place(*this, params, seenCrossTileIDs); } } @@ -656,18 +661,20 @@ void Placement::placeBucket(const SymbolBucket& bucket, } } 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, - std::forward_as_tuple(bucket.bucketInstanceId), - std::forward_as_tuple(bucket.bucketInstanceId, params.featureIndex, overscaledID)); + std::forward_as_tuple(bucket.bucketInstanceId), + std::forward_as_tuple(bucket.bucketInstanceId, params.featureIndex, overscaledID)); } void Placement::commit() { @@ -737,7 +744,9 @@ void Placement::commit() { 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 46d560b673..9fbd6b9743 100644 --- a/src/mbgl/text/placement.hpp +++ b/src/mbgl/text/placement.hpp @@ -91,6 +91,9 @@ public: const RenderTile& tile; std::string sourceId; std::shared_ptr featureIndex; + float sortKey; + size_t symbolInstanceStart; + size_t symbolInstanceEnd; }; class Placement; diff --git a/test/gl/bucket.test.cpp b/test/gl/bucket.test.cpp index 2a7455e17c..c7636dabcf 100644 --- a/test/gl/bucket.test.cpp +++ b/test/gl/bucket.test.cpp @@ -123,6 +123,7 @@ 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), @@ -134,6 +135,7 @@ TEST(Buckets, SymbolBucket) { sortFeaturesByY, bucketLeaderID, std::move(symbolInstances), + std::move(symbolRanges), 1.0f, false, {}, diff --git a/test/text/cross_tile_symbol_index.test.cpp b/test/text/cross_tile_symbol_index.test.cpp index 6119392fd2..bedf96b430 100644 --- a/test/text/cross_tile_symbol_index.test.cpp +++ b/test/text/cross_tile_symbol_index.test.cpp @@ -47,6 +47,7 @@ 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, @@ -58,6 +59,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) { sortFeaturesByY, bucketLeaderID, std::move(mainInstances), + std::move(mainRanges), 1.0f, false, {}, @@ -72,6 +74,7 @@ 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")); @@ -85,6 +88,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) { sortFeaturesByY, bucketLeaderID, std::move(childInstances), + std::move(childRanges), 1.0f, false, {}, @@ -103,6 +107,7 @@ 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, {}, @@ -113,6 +118,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) { sortFeaturesByY, bucketLeaderID, std::move(parentInstances), + std::move(parentRanges), 1.0f, false, {}, @@ -130,6 +136,7 @@ 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, @@ -141,6 +148,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) { sortFeaturesByY, bucketLeaderID, std::move(grandchildInstances), + std::move(grandchildRanges), 1.0f, false, {}, @@ -169,6 +177,7 @@ 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, {}, @@ -179,6 +188,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) { sortFeaturesByY, bucketLeaderID, std::move(mainInstances), + std::move(mainRanges), 1.0f, false, {}, @@ -187,6 +197,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) { OverscaledTileID childID(7, 0, 7, 16, 16); std::vector childInstances; + std::vector childRanges; childInstances.push_back(makeSymbolInstance(2000, 2000, u"Detroit")); SymbolBucket childBucket{layout, {}, @@ -197,6 +208,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) { sortFeaturesByY, bucketLeaderID, std::move(childInstances), + std::move(childRanges), 1.0f, false, {}, @@ -233,6 +245,7 @@ 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, @@ -244,6 +257,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) { sortFeaturesByY, bucketLeaderID, std::move(mainInstances), + std::move(mainRanges), 1.0f, false, {}, @@ -252,6 +266,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) { 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' @@ -264,6 +279,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) { sortFeaturesByY, bucketLeaderID, std::move(childInstances), + std::move(childRanges), 1.0f, false, {}, @@ -295,6 +311,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) { OverscaledTileID tileID(6, 0, 6, 8, 8); std::vector firstInstances; + std::vector firstRanges; firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B SymbolBucket firstBucket{layout, @@ -306,6 +323,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) { sortFeaturesByY, bucketLeaderID, std::move(firstInstances), + std::move(firstRanges), 1.0f, false, {}, @@ -313,6 +331,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) { 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' @@ -325,6 +344,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) { sortFeaturesByY, bucketLeaderID, std::move(secondInstances), + std::move(secondRanges), 1.0f, false, {}, @@ -369,6 +389,7 @@ TEST(CrossTileSymbolLayerIndex, offscreenSymbols) { std::vector mainInstances; mainInstances.push_back(makeSymbolInstance(1000, 1000, u"Washington")); mainInstances.push_back(makeSymbolInstance(2000, 2000, u"Richmond")); + std::vector mainRanges; SymbolBucket symbolBucket{layout, {}, 16.0f, @@ -378,6 +399,7 @@ TEST(CrossTileSymbolLayerIndex, offscreenSymbols) { sortFeaturesByY, bucketLeaderID, std::move(mainInstances), + std::move(mainRanges), 1.0f, false, {}, @@ -394,4 +416,4 @@ TEST(CrossTileSymbolLayerIndex, offscreenSymbols) { EXPECT_EQ(symbolBucket.symbolInstances.at(0).crossTileID, 1u); EXPECT_EQ(symbolBucket.symbolInstances.at(1).crossTileID, 2u); -} \ No newline at end of file +} -- cgit v1.2.1