From 661b4e0558374dfd15fe46358accb3b340dfaec8 Mon Sep 17 00:00:00 2001 From: Chris Loer Date: Wed, 18 Apr 2018 16:33:37 -0700 Subject: [core] Port global symbol query from GL JS: - Symbol querying is now global instead of per-tile - Symbols that bleed over tile boundaries no longer missed in queries - Symbol results now sorted based on rendering order (ie overlapping symbols change their sort order when a bearing change causes their render order to change) - Placement::retainedQueryData now responsible for maintaining symbol querying data for buckets that may no longer be in the TilePyramid. --- platform/node/test/ignores.json | 2 - src/mbgl/annotation/render_annotation_source.cpp | 5 +- src/mbgl/annotation/render_annotation_source.hpp | 3 +- src/mbgl/geometry/feature_index.cpp | 58 ++++++++++++++------ src/mbgl/geometry/feature_index.hpp | 32 ++++++------ src/mbgl/layout/symbol_layout.cpp | 12 ++--- src/mbgl/layout/symbol_layout.hpp | 7 +-- src/mbgl/renderer/buckets/symbol_bucket.cpp | 4 ++ src/mbgl/renderer/buckets/symbol_bucket.hpp | 2 + src/mbgl/renderer/render_source.hpp | 3 +- src/mbgl/renderer/renderer_impl.cpp | 50 +++++++++++++----- src/mbgl/renderer/renderer_impl.hpp | 8 ++- .../sources/render_custom_geometry_source.cpp | 5 +- .../sources/render_custom_geometry_source.hpp | 3 +- .../renderer/sources/render_geojson_source.cpp | 5 +- .../renderer/sources/render_geojson_source.hpp | 3 +- src/mbgl/renderer/sources/render_image_source.cpp | 3 +- src/mbgl/renderer/sources/render_image_source.hpp | 3 +- .../renderer/sources/render_raster_dem_source.cpp | 3 +- .../renderer/sources/render_raster_dem_source.hpp | 3 +- src/mbgl/renderer/sources/render_raster_source.cpp | 3 +- src/mbgl/renderer/sources/render_raster_source.hpp | 3 +- src/mbgl/renderer/sources/render_vector_source.cpp | 5 +- src/mbgl/renderer/sources/render_vector_source.hpp | 3 +- src/mbgl/renderer/tile_pyramid.cpp | 6 +-- src/mbgl/renderer/tile_pyramid.hpp | 3 +- src/mbgl/text/collision_index.cpp | 61 +++++++--------------- src/mbgl/text/collision_index.hpp | 5 +- src/mbgl/text/placement.cpp | 36 ++++++++++--- src/mbgl/text/placement.hpp | 20 ++++++- src/mbgl/tile/geometry_tile.cpp | 34 ++++-------- src/mbgl/tile/geometry_tile.hpp | 10 ++-- src/mbgl/tile/geometry_tile_worker.cpp | 3 +- src/mbgl/tile/tile.cpp | 3 +- src/mbgl/tile/tile.hpp | 8 +-- 35 files changed, 220 insertions(+), 197 deletions(-) diff --git a/platform/node/test/ignores.json b/platform/node/test/ignores.json index e0c2475b75..b7ca72cee0 100644 --- a/platform/node/test/ignores.json +++ b/platform/node/test/ignores.json @@ -6,8 +6,6 @@ "query-tests/geometry/multilinestring": "needs investigation", "query-tests/geometry/multipolygon": "needs investigation", "query-tests/geometry/polygon": "needs investigation", - "query-tests/symbol/panned-after-insert": "https://github.com/mapbox/mapbox-gl-native/issues/10408", - "query-tests/symbol/rotated-after-insert": "https://github.com/mapbox/mapbox-gl-native/issues/10408", "query-tests/world-wrapping/box": "skip - needs issue", "query-tests/world-wrapping/point": "skip - needs issue", "render-tests/background-color/transition": "https://github.com/mapbox/mapbox-gl-native/issues/10619", diff --git a/src/mbgl/annotation/render_annotation_source.cpp b/src/mbgl/annotation/render_annotation_source.cpp index a237100d13..19d19d2901 100644 --- a/src/mbgl/annotation/render_annotation_source.cpp +++ b/src/mbgl/annotation/render_annotation_source.cpp @@ -64,9 +64,8 @@ std::unordered_map> RenderAnnotationSource::queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const { - return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options, collisionIndex); + const RenderedQueryOptions& options) const { + return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options); } std::vector RenderAnnotationSource::querySourceFeatures(const SourceQueryOptions&) const { diff --git a/src/mbgl/annotation/render_annotation_source.hpp b/src/mbgl/annotation/render_annotation_source.hpp index e812ec2883..da5376ab2d 100644 --- a/src/mbgl/annotation/render_annotation_source.hpp +++ b/src/mbgl/annotation/render_annotation_source.hpp @@ -27,8 +27,7 @@ public: queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const final; + const RenderedQueryOptions& options) const final; std::vector querySourceFeatures(const SourceQueryOptions&) const final; diff --git a/src/mbgl/geometry/feature_index.cpp b/src/mbgl/geometry/feature_index.cpp index 57719de038..145c16bf09 100644 --- a/src/mbgl/geometry/feature_index.cpp +++ b/src/mbgl/geometry/feature_index.cpp @@ -32,14 +32,6 @@ void FeatureIndex::insert(const GeometryCollection& geometries, } } -static bool topDown(const IndexedSubfeature& a, const IndexedSubfeature& b) { - return a.sortIndex > b.sortIndex; -} - -static bool topDownSymbols(const IndexedSubfeature& a, const IndexedSubfeature& b) { - return a.sortIndex < b.sortIndex; -} - void FeatureIndex::query( std::unordered_map>& result, const GeometryCoordinates& queryGeometry, @@ -48,9 +40,7 @@ void FeatureIndex::query( const double scale, const RenderedQueryOptions& queryOptions, const UnwrappedTileID& tileID, - const std::string& sourceID, const std::vector& layers, - const CollisionIndex& collisionIndex, const float additionalQueryRadius) const { if (!tileData) { @@ -67,7 +57,9 @@ void FeatureIndex::query( convertPoint(box.max + additionalRadius) }); - std::sort(features.begin(), features.end(), topDown); + std::sort(features.begin(), features.end(), [](const IndexedSubfeature& a, const IndexedSubfeature& b) { + return a.sortIndex > b.sortIndex; + }); size_t previousSortIndex = std::numeric_limits::max(); for (const auto& indexedFeature : features) { @@ -75,23 +67,55 @@ void FeatureIndex::query( if (indexedFeature.sortIndex == previousSortIndex) continue; previousSortIndex = indexedFeature.sortIndex; - addFeature(result, indexedFeature, queryGeometry, queryOptions, tileID.canonical, layers, bearing, pixelsToTileUnits); + addFeature(result, indexedFeature, queryOptions, tileID.canonical, layers, queryGeometry, bearing, pixelsToTileUnits); } +} + +std::unordered_map> FeatureIndex::lookupSymbolFeatures(const std::vector& symbolFeatures, + const RenderedQueryOptions& queryOptions, + const std::vector& layers, + const OverscaledTileID& tileID, + const std::shared_ptr>& featureSortOrder) const { + std::unordered_map> result; + if (!tileData) { + return result; + } + std::vector sortedFeatures(symbolFeatures.begin(), symbolFeatures.end()); + + std::sort(sortedFeatures.begin(), sortedFeatures.end(), [featureSortOrder](const IndexedSubfeature& a, const IndexedSubfeature& b) { + // Same idea as the non-symbol sort order, but symbol features may have changed their sort order + // since their corresponding IndexedSubfeature was added to the CollisionIndex + // The 'featureSortOrder' is relatively inefficient for querying but cheap to build on every bucket sort + if (featureSortOrder) { + // queryRenderedSymbols documentation says we'll return features in + // "top-to-bottom" rendering order (aka last-to-first). + // Actually there can be multiple symbol instances per feature, so + // we sort each feature based on the first matching symbol instance. + auto sortedA = std::find(featureSortOrder->begin(), featureSortOrder->end(), a.index); + auto sortedB = std::find(featureSortOrder->begin(), featureSortOrder->end(), b.index); + assert(sortedA != featureSortOrder->end()); + assert(sortedB != featureSortOrder->end()); + return sortedA > sortedB; + } else { + // Bucket hasn't been re-sorted based on angle, so use same "reverse of appearance in source data" + // logic as non-symboles + return a.sortIndex > b.sortIndex; + } + }); - std::vector symbolFeatures = collisionIndex.queryRenderedSymbols(queryGeometry, tileID, sourceID); - std::sort(symbolFeatures.begin(), symbolFeatures.end(), topDownSymbols); - for (const auto& symbolFeature : symbolFeatures) { - addFeature(result, symbolFeature, queryGeometry, queryOptions, tileID.canonical, layers, bearing, pixelsToTileUnits); + for (const auto& symbolFeature : sortedFeatures) { + addFeature(result, symbolFeature, queryOptions, tileID.canonical, layers, GeometryCoordinates(), 0, 0); } + return result; } void FeatureIndex::addFeature( std::unordered_map>& result, const IndexedSubfeature& indexedFeature, - const GeometryCoordinates& queryGeometry, const RenderedQueryOptions& options, const CanonicalTileID& tileID, const std::vector& layers, + const GeometryCoordinates& queryGeometry, const float bearing, const float pixelsToTileUnits) const { diff --git a/src/mbgl/geometry/feature_index.hpp b/src/mbgl/geometry/feature_index.hpp index 9e0c172342..5a15a379c4 100644 --- a/src/mbgl/geometry/feature_index.hpp +++ b/src/mbgl/geometry/feature_index.hpp @@ -25,27 +25,24 @@ public: , sourceLayerName(std::move(sourceLayerName_)) , bucketName(std::move(bucketName_)) , sortIndex(sortIndex_) - , tileID(0, 0, 0) + , bucketInstanceId(0) {} - IndexedSubfeature(std::size_t index_, std::string sourceLayerName_, std::string bucketName_, size_t sortIndex_, - std::string sourceID_, CanonicalTileID tileID_) - : index(index_) - , sourceLayerName(std::move(sourceLayerName_)) - , bucketName(std::move(bucketName_)) - , sortIndex(std::move(sortIndex_)) - , sourceID(std::move(sourceID_)) - , tileID(std::move(tileID_)) - {} + IndexedSubfeature(const IndexedSubfeature& other, uint32_t bucketInstanceId_) + : index(other.index) + , sourceLayerName(other.sourceLayerName) + , bucketName(other.bucketName) + , sortIndex(other.sortIndex) + , bucketInstanceId(bucketInstanceId_) + {} size_t index; std::string sourceLayerName; std::string bucketName; size_t sortIndex; // Only used for symbol features - std::string sourceID; - CanonicalTileID tileID; + uint32_t bucketInstanceId; }; class FeatureIndex { @@ -64,9 +61,7 @@ public: const double scale, const RenderedQueryOptions& options, const UnwrappedTileID&, - const std::string&, const std::vector&, - const CollisionIndex&, const float additionalQueryRadius) const; static optional translateQueryGeometry( @@ -77,15 +72,22 @@ public: const float pixelsToTileUnits); void setBucketLayerIDs(const std::string& bucketName, const std::vector& layerIDs); + + std::unordered_map> lookupSymbolFeatures( + const std::vector& symbolFeatures, + const RenderedQueryOptions& options, + const std::vector& layers, + const OverscaledTileID& tileID, + const std::shared_ptr>& featureSortOrder) const; private: void addFeature( std::unordered_map>& result, const IndexedSubfeature&, - const GeometryCoordinates& queryGeometry, const RenderedQueryOptions& options, const CanonicalTileID&, const std::vector&, + const GeometryCoordinates& queryGeometry, const float bearing, const float pixelsToTileUnits) const; diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp index cd9bcbd585..950b9ae382 100644 --- a/src/mbgl/layout/symbol_layout.cpp +++ b/src/mbgl/layout/symbol_layout.cpp @@ -180,8 +180,7 @@ bool SymbolLayout::hasSymbolInstances() const { } void SymbolLayout::prepare(const GlyphMap& glyphMap, const GlyphPositions& glyphPositions, - const ImageMap& imageMap, const ImagePositions& imagePositions, - const OverscaledTileID& tileID, const std::string& sourceID) { + const ImageMap& imageMap, const ImagePositions& imagePositions) { const bool textAlongLine = layout.get() == AlignmentType::Map && layout.get() == SymbolPlacementType::Line; @@ -252,7 +251,7 @@ void SymbolLayout::prepare(const GlyphMap& glyphMap, const GlyphPositions& glyph // if either shapedText or icon position is present, add the feature if (shapedTextOrientations.first || shapedIcon) { - addFeature(std::distance(features.begin(), it), feature, shapedTextOrientations, shapedIcon, glyphPositionMap, tileID, sourceID); + addFeature(std::distance(features.begin(), it), feature, shapedTextOrientations, shapedIcon, glyphPositionMap); } feature.geometry.clear(); @@ -265,9 +264,7 @@ void SymbolLayout::addFeature(const std::size_t index, const SymbolFeature& feature, const std::pair& shapedTextOrientations, optional shapedIcon, - const GlyphPositionMap& glyphPositionMap, - const OverscaledTileID& tileID, - const std::string& sourceID) { + const GlyphPositionMap& glyphPositionMap) { const float minScale = 0.5f; const float glyphSize = 24.0f; @@ -296,8 +293,7 @@ void SymbolLayout::addFeature(const std::size_t index, : layout.get(); const float textRepeatDistance = symbolSpacing / 2; - IndexedSubfeature indexedFeature(feature.index, sourceLayer->getName(), bucketName, symbolInstances.size(), - sourceID, tileID.canonical); + IndexedSubfeature indexedFeature(feature.index, sourceLayer->getName(), bucketName, symbolInstances.size()); auto addSymbolInstance = [&] (const GeometryCoordinates& line, Anchor& anchor) { // https://github.com/mapbox/vector-tile-spec/tree/master/2.1#41-layers diff --git a/src/mbgl/layout/symbol_layout.hpp b/src/mbgl/layout/symbol_layout.hpp index 6951c29ada..c93d8f4106 100644 --- a/src/mbgl/layout/symbol_layout.hpp +++ b/src/mbgl/layout/symbol_layout.hpp @@ -34,8 +34,7 @@ public: GlyphDependencies&); void prepare(const GlyphMap&, const GlyphPositions&, - const ImageMap&, const ImagePositions&, - const OverscaledTileID&, const std::string&); + const ImageMap&, const ImagePositions&); std::unique_ptr place(const bool showCollisionBoxes); @@ -52,9 +51,7 @@ private: const SymbolFeature&, const std::pair& shapedTextOrientations, optional shapedIcon, - const GlyphPositionMap&, - const OverscaledTileID&, - const std::string&); + const GlyphPositionMap&); bool anchorIsTooClose(const std::u16string& text, const float repeatDistance, const Anchor&); std::map> compareText; diff --git a/src/mbgl/renderer/buckets/symbol_bucket.cpp b/src/mbgl/renderer/buckets/symbol_bucket.cpp index 60e8a0b504..3d40a1714d 100644 --- a/src/mbgl/renderer/buckets/symbol_bucket.cpp +++ b/src/mbgl/renderer/buckets/symbol_bucket.cpp @@ -200,8 +200,12 @@ void SymbolBucket::sortFeatures(const float angle) { text.triangles.clear(); icon.triangles.clear(); + featureSortOrder = std::make_unique>(); + featureSortOrder->reserve(symbolInstanceIndexes.size()); + for (auto i : symbolInstanceIndexes) { const SymbolInstance& symbolInstance = symbolInstances[i]; + featureSortOrder->push_back(symbolInstance.featureIndex); if (symbolInstance.placedTextIndex) { addPlacedSymbol(text.triangles, text.placedSymbols[*symbolInstance.placedTextIndex]); diff --git a/src/mbgl/renderer/buckets/symbol_bucket.hpp b/src/mbgl/renderer/buckets/symbol_bucket.hpp index ed8afb052c..e52d18372d 100644 --- a/src/mbgl/renderer/buckets/symbol_bucket.hpp +++ b/src/mbgl/renderer/buckets/symbol_bucket.hpp @@ -131,6 +131,8 @@ public: uint32_t bucketInstanceId = 0; bool justReloaded = false; + + std::shared_ptr> featureSortOrder; }; } // namespace mbgl diff --git a/src/mbgl/renderer/render_source.hpp b/src/mbgl/renderer/render_source.hpp index 53519c763e..54a0b5db43 100644 --- a/src/mbgl/renderer/render_source.hpp +++ b/src/mbgl/renderer/render_source.hpp @@ -64,8 +64,7 @@ public: queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const = 0; + const RenderedQueryOptions& options) const = 0; virtual std::vector querySourceFeatures(const SourceQueryOptions&) const = 0; diff --git a/src/mbgl/renderer/renderer_impl.cpp b/src/mbgl/renderer/renderer_impl.cpp index 7b25b37cf2..4348dfca75 100644 --- a/src/mbgl/renderer/renderer_impl.cpp +++ b/src/mbgl/renderer/renderer_impl.cpp @@ -401,10 +401,6 @@ void Renderer::Impl::render(const UpdateParameters& updateParameters) { } placementChanged = newPlacement->commit(*placement, parameters.timePoint); - // commitFeatureIndexes depends on the assumption that no new FeatureIndex has been loaded since placement - // started. If we violate this assumption, then we need to either make CollisionIndex completely independendent of - // FeatureIndex, or find a way for its entries to point to multiple FeatureIndexes. - commitFeatureIndexes(); crossTileSymbolIndex.pruneUnusedLayers(usedSymbolLayers); if (placementChanged || symbolBucketsChanged) { placement = std::move(newPlacement); @@ -681,6 +677,39 @@ std::vector Renderer::Impl::queryRenderedFeatures(const ScreenLineStrin return queryRenderedFeatures(geometry, options, layers); } + +void Renderer::Impl::queryRenderedSymbols(std::unordered_map>& resultsByLayer, + const ScreenLineString& geometry, + const std::vector& layers, + const RenderedQueryOptions& options) const { + + auto renderedSymbols = placement->getCollisionIndex().queryRenderedSymbols(geometry); + std::vector> bucketQueryData; + for (auto entry : renderedSymbols) { + bucketQueryData.push_back(placement->getQueryData(entry.first)); + } + // Although symbol query is global, symbol results are only sortable within a bucket + // For a predictable global sort order, we sort the buckets based on their corresponding tile position + std::sort(bucketQueryData.begin(), bucketQueryData.end(), [](const RetainedQueryData& a, const RetainedQueryData& b) { + return + std::tie(a.tileID.canonical.z, a.tileID.canonical.y, a.tileID.wrap, a.tileID.canonical.x) < + std::tie(b.tileID.canonical.z, b.tileID.canonical.y, b.tileID.wrap, b.tileID.canonical.x); + }); + + for (auto wrappedQueryData : bucketQueryData) { + auto& queryData = wrappedQueryData.get(); + auto bucketSymbols = queryData.featureIndex->lookupSymbolFeatures(renderedSymbols[queryData.bucketInstanceId], + options, + layers, + queryData.tileID, + queryData.featureSortOrder); + + for (auto layer : bucketSymbols) { + auto& resultFeatures = resultsByLayer[layer.first]; + std::move(layer.second.begin(), layer.second.end(), std::inserter(resultFeatures, resultFeatures.end())); + } + } +} std::vector Renderer::Impl::queryRenderedFeatures(const ScreenLineString& geometry, const RenderedQueryOptions& options, const std::vector& layers) const { std::unordered_set sourceIDs; @@ -691,10 +720,12 @@ std::vector Renderer::Impl::queryRenderedFeatures(const ScreenLineStrin std::unordered_map> resultsByLayer; for (const auto& sourceID : sourceIDs) { if (RenderSource* renderSource = getRenderSource(sourceID)) { - auto sourceResults = renderSource->queryRenderedFeatures(geometry, transformState, layers, options, placement->getCollisionIndex()); + auto sourceResults = renderSource->queryRenderedFeatures(geometry, transformState, layers, options); std::move(sourceResults.begin(), sourceResults.end(), std::inserter(resultsByLayer, resultsByLayer.begin())); } } + + queryRenderedSymbols(resultsByLayer, geometry, layers, options); std::vector result; @@ -793,15 +824,6 @@ bool Renderer::Impl::hasTransitions(TimePoint timePoint) const { return false; } -void Renderer::Impl::commitFeatureIndexes() { - for (auto& source : renderSources) { - for (auto& renderTile : source.second->getRenderTiles()) { - Tile& tile = renderTile.get().tile; - tile.commitFeatureIndex(); - } - } -} - void Renderer::Impl::updateFadingTiles() { fadingTiles = false; for (auto& source : renderSources) { diff --git a/src/mbgl/renderer/renderer_impl.hpp b/src/mbgl/renderer/renderer_impl.hpp index 4675ac79ea..4124f6f416 100644 --- a/src/mbgl/renderer/renderer_impl.hpp +++ b/src/mbgl/renderer/renderer_impl.hpp @@ -64,7 +64,12 @@ private: RenderLayer* getRenderLayer(const std::string& id); const RenderLayer* getRenderLayer(const std::string& id) const; - + + void queryRenderedSymbols(std::unordered_map>& resultsByLayer, + const ScreenLineString& geometry, + const std::vector& layers, + const RenderedQueryOptions& options) const; + std::vector queryRenderedFeatures(const ScreenLineString&, const RenderedQueryOptions&, const std::vector&) const; // GlyphManagerObserver implementation. @@ -74,7 +79,6 @@ private: void onTileChanged(RenderSource&, const OverscaledTileID&) override; void onTileError(RenderSource&, const OverscaledTileID&, std::exception_ptr) override; - void commitFeatureIndexes(); void updateFadingTiles(); friend class Renderer; diff --git a/src/mbgl/renderer/sources/render_custom_geometry_source.cpp b/src/mbgl/renderer/sources/render_custom_geometry_source.cpp index 057ad5a4a7..88792db00b 100644 --- a/src/mbgl/renderer/sources/render_custom_geometry_source.cpp +++ b/src/mbgl/renderer/sources/render_custom_geometry_source.cpp @@ -67,9 +67,8 @@ std::unordered_map> RenderCustomGeometrySource::queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const { - return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options, collisionIndex); + const RenderedQueryOptions& options) const { + return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options); } std::vector RenderCustomGeometrySource::querySourceFeatures(const SourceQueryOptions& options) const { diff --git a/src/mbgl/renderer/sources/render_custom_geometry_source.hpp b/src/mbgl/renderer/sources/render_custom_geometry_source.hpp index 033d731029..9e47b9e392 100644 --- a/src/mbgl/renderer/sources/render_custom_geometry_source.hpp +++ b/src/mbgl/renderer/sources/render_custom_geometry_source.hpp @@ -27,8 +27,7 @@ public: queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const final; + const RenderedQueryOptions& options) const final; std::vector querySourceFeatures(const SourceQueryOptions&) const final; diff --git a/src/mbgl/renderer/sources/render_geojson_source.cpp b/src/mbgl/renderer/sources/render_geojson_source.cpp index cbf4db70b5..7492a4cf16 100644 --- a/src/mbgl/renderer/sources/render_geojson_source.cpp +++ b/src/mbgl/renderer/sources/render_geojson_source.cpp @@ -85,9 +85,8 @@ std::unordered_map> RenderGeoJSONSource::queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const { - return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options, collisionIndex); + const RenderedQueryOptions& options) const { + return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options); } std::vector RenderGeoJSONSource::querySourceFeatures(const SourceQueryOptions& options) const { diff --git a/src/mbgl/renderer/sources/render_geojson_source.hpp b/src/mbgl/renderer/sources/render_geojson_source.hpp index 72fccbd043..bcdc109953 100644 --- a/src/mbgl/renderer/sources/render_geojson_source.hpp +++ b/src/mbgl/renderer/sources/render_geojson_source.hpp @@ -31,8 +31,7 @@ public: queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex&) const final; + const RenderedQueryOptions& options) const final; std::vector querySourceFeatures(const SourceQueryOptions&) const final; diff --git a/src/mbgl/renderer/sources/render_image_source.cpp b/src/mbgl/renderer/sources/render_image_source.cpp index 4946b0bc30..8506dd1ab5 100644 --- a/src/mbgl/renderer/sources/render_image_source.cpp +++ b/src/mbgl/renderer/sources/render_image_source.cpp @@ -92,8 +92,7 @@ std::unordered_map> RenderImageSource::queryRenderedFeatures(const ScreenLineString&, const TransformState&, const std::vector&, - const RenderedQueryOptions&, - const CollisionIndex&) const { + const RenderedQueryOptions&) const { return std::unordered_map> {}; } diff --git a/src/mbgl/renderer/sources/render_image_source.hpp b/src/mbgl/renderer/sources/render_image_source.hpp index 85ee0ace11..7dc89d3591 100644 --- a/src/mbgl/renderer/sources/render_image_source.hpp +++ b/src/mbgl/renderer/sources/render_image_source.hpp @@ -32,8 +32,7 @@ public: queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const final; + const RenderedQueryOptions& options) const final; std::vector querySourceFeatures(const SourceQueryOptions&) const final; diff --git a/src/mbgl/renderer/sources/render_raster_dem_source.cpp b/src/mbgl/renderer/sources/render_raster_dem_source.cpp index b3153622c3..58bdba1840 100644 --- a/src/mbgl/renderer/sources/render_raster_dem_source.cpp +++ b/src/mbgl/renderer/sources/render_raster_dem_source.cpp @@ -146,8 +146,7 @@ std::unordered_map> RenderRasterDEMSource::queryRenderedFeatures(const ScreenLineString&, const TransformState&, const std::vector&, - const RenderedQueryOptions&, - const CollisionIndex& ) const { + const RenderedQueryOptions&) const { return std::unordered_map> {}; } diff --git a/src/mbgl/renderer/sources/render_raster_dem_source.hpp b/src/mbgl/renderer/sources/render_raster_dem_source.hpp index 741214a14d..512fe6367c 100644 --- a/src/mbgl/renderer/sources/render_raster_dem_source.hpp +++ b/src/mbgl/renderer/sources/render_raster_dem_source.hpp @@ -27,8 +27,7 @@ public: queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const final; + const RenderedQueryOptions& options) const final; std::vector querySourceFeatures(const SourceQueryOptions&) const final; diff --git a/src/mbgl/renderer/sources/render_raster_source.cpp b/src/mbgl/renderer/sources/render_raster_source.cpp index 60b3fa9a3b..3162acc7b4 100644 --- a/src/mbgl/renderer/sources/render_raster_source.cpp +++ b/src/mbgl/renderer/sources/render_raster_source.cpp @@ -76,8 +76,7 @@ std::unordered_map> RenderRasterSource::queryRenderedFeatures(const ScreenLineString&, const TransformState&, const std::vector&, - const RenderedQueryOptions&, - const CollisionIndex& ) const { + const RenderedQueryOptions&) const { return std::unordered_map> {}; } diff --git a/src/mbgl/renderer/sources/render_raster_source.hpp b/src/mbgl/renderer/sources/render_raster_source.hpp index 78eda199ac..c60a51c63b 100644 --- a/src/mbgl/renderer/sources/render_raster_source.hpp +++ b/src/mbgl/renderer/sources/render_raster_source.hpp @@ -27,8 +27,7 @@ public: queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const final; + const RenderedQueryOptions& options) const final; std::vector querySourceFeatures(const SourceQueryOptions&) const final; diff --git a/src/mbgl/renderer/sources/render_vector_source.cpp b/src/mbgl/renderer/sources/render_vector_source.cpp index e87bea5dcd..c9c47359f4 100644 --- a/src/mbgl/renderer/sources/render_vector_source.cpp +++ b/src/mbgl/renderer/sources/render_vector_source.cpp @@ -79,9 +79,8 @@ std::unordered_map> RenderVectorSource::queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const { - return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options, collisionIndex); + const RenderedQueryOptions& options) const { + return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options); } std::vector RenderVectorSource::querySourceFeatures(const SourceQueryOptions& options) const { diff --git a/src/mbgl/renderer/sources/render_vector_source.hpp b/src/mbgl/renderer/sources/render_vector_source.hpp index 592160dc16..a0351c226c 100644 --- a/src/mbgl/renderer/sources/render_vector_source.hpp +++ b/src/mbgl/renderer/sources/render_vector_source.hpp @@ -27,8 +27,7 @@ public: queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const final; + const RenderedQueryOptions& options) const final; std::vector querySourceFeatures(const SourceQueryOptions&) const final; diff --git a/src/mbgl/renderer/tile_pyramid.cpp b/src/mbgl/renderer/tile_pyramid.cpp index 8f83a0f982..e2d4d9829f 100644 --- a/src/mbgl/renderer/tile_pyramid.cpp +++ b/src/mbgl/renderer/tile_pyramid.cpp @@ -241,8 +241,7 @@ void TilePyramid::update(const std::vector>& layer std::unordered_map> TilePyramid::queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const { + const RenderedQueryOptions& options) const { std::unordered_map> result; if (renderTiles.empty() || geometry.empty()) { return result; @@ -285,8 +284,7 @@ std::unordered_map> TilePyramid::queryRendered tileSpaceQueryGeometry, transformState, layers, - options, - collisionIndex); + options); } return result; diff --git a/src/mbgl/renderer/tile_pyramid.hpp b/src/mbgl/renderer/tile_pyramid.hpp index 2638599c38..bf3ba0d7b8 100644 --- a/src/mbgl/renderer/tile_pyramid.hpp +++ b/src/mbgl/renderer/tile_pyramid.hpp @@ -53,8 +53,7 @@ public: queryRenderedFeatures(const ScreenLineString& geometry, const TransformState& transformState, const std::vector&, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) const; + const RenderedQueryOptions& options) const; std::vector querySourceFeatures(const SourceQueryOptions&) const; diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp index 833658c33e..091840a371 100644 --- a/src/mbgl/text/collision_index.cpp +++ b/src/mbgl/text/collision_index.cpp @@ -219,7 +219,7 @@ std::pair CollisionIndex::placeLineFeature(CollisionFeature& feature, } -void CollisionIndex::insertFeature(CollisionFeature& feature, bool ignorePlacement) { +void CollisionIndex::insertFeature(CollisionFeature& feature, bool ignorePlacement, uint32_t bucketInstanceId) { if (feature.alongLine) { for (auto& circle : feature.boxes) { if (!circle.used) { @@ -227,18 +227,18 @@ void CollisionIndex::insertFeature(CollisionFeature& feature, bool ignorePlaceme } if (ignorePlacement) { - ignoredGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ circle.px, circle.py }, circle.radius}); + ignoredGrid.insert(IndexedSubfeature(feature.indexedFeature, bucketInstanceId), {{ circle.px, circle.py }, circle.radius}); } else { - collisionGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ circle.px, circle.py }, circle.radius}); + collisionGrid.insert(IndexedSubfeature(feature.indexedFeature, bucketInstanceId), {{ circle.px, circle.py }, circle.radius}); } } } else { assert(feature.boxes.size() == 1); auto& box = feature.boxes[0]; if (ignorePlacement) { - ignoredGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ box.px1, box.py1 }, { box.px2, box.py2 }}); + ignoredGrid.insert(IndexedSubfeature(feature.indexedFeature, bucketInstanceId), {{ box.px1, box.py1 }, { box.px2, box.py2 }}); } else { - collisionGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ box.px1, box.py1 }, { box.px2, box.py2 }}); + collisionGrid.insert(IndexedSubfeature(feature.indexedFeature, bucketInstanceId), {{ box.px1, box.py1 }, { box.px2, box.py2 }}); } } } @@ -262,66 +262,41 @@ bool polygonIntersectsBox(const LineString& polygon, const GridIndex CollisionIndex::queryRenderedSymbols(const GeometryCoordinates& queryGeometry, const UnwrappedTileID& tileID, const std::string& sourceID) const { - std::vector result; +std::unordered_map> CollisionIndex::queryRenderedSymbols(const ScreenLineString& queryGeometry) const { + std::unordered_map> result; if (queryGeometry.empty() || (collisionGrid.empty() && ignoredGrid.empty())) { return result; } - - mat4 posMatrix; - mat4 projMatrix; - transformState.getProjMatrix(projMatrix); - transformState.matrixFor(posMatrix, tileID); - matrix::multiply(posMatrix, projMatrix, posMatrix); - - // queryGeometry is specified in integer tile units, but in projecting we switch to float pixels - LineString projectedQuery; + + LineString gridQuery; for (const auto& point : queryGeometry) { - auto projected = projectPoint(posMatrix, convertPoint(point)); - projectedQuery.push_back(projected); + gridQuery.emplace_back(point.x + viewportPadding, point.y + viewportPadding); } - auto envelope = mapbox::geometry::envelope(projectedQuery); + auto envelope = mapbox::geometry::envelope(gridQuery); using QueryResult = std::pair::BBox>; - std::vector thisTileFeatures; std::vector features = collisionGrid.queryWithBoxes(envelope); - - for (auto& queryResult : features) { - auto& feature = queryResult.first; - if (feature.sourceID == sourceID && feature.tileID == tileID.canonical) { - // We only have to filter on the canonical ID because even if the feature is showing multiple times - // we treat it as one feature. - thisTileFeatures.push_back(queryResult); - } - } - std::vector ignoredFeatures = ignoredGrid.queryWithBoxes(envelope); - for (auto& queryResult : ignoredFeatures) { - auto& feature = queryResult.first; - if (feature.sourceID == sourceID && feature.tileID == tileID.canonical) { - thisTileFeatures.push_back(queryResult); - } - } + features.insert(features.end(), ignoredFeatures.begin(), ignoredFeatures.end()); - std::unordered_map>> sourceLayerFeatures; - for (auto& queryResult : thisTileFeatures) { + std::unordered_map> seenBuckets; + for (auto& queryResult : features) { auto& feature = queryResult.first; auto& bbox = queryResult.second; // Skip already seen features. - auto& seenFeatures = sourceLayerFeatures[feature.sourceLayerName][feature.bucketName]; + auto& seenFeatures = seenBuckets[feature.bucketInstanceId]; if (seenFeatures.find(feature.index) != seenFeatures.end()) continue; - - seenFeatures.insert(feature.index); - if (!polygonIntersectsBox(projectedQuery, bbox)) { + if (!polygonIntersectsBox(gridQuery, bbox)) { continue; } - result.push_back(feature); + seenFeatures.insert(feature.index); + result[feature.bucketInstanceId].push_back(feature); } return result; diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp index 8653c1d76c..b2be4c6ade 100644 --- a/src/mbgl/text/collision_index.hpp +++ b/src/mbgl/text/collision_index.hpp @@ -28,11 +28,10 @@ public: const bool pitchWithMap, const bool collisionDebug); - void insertFeature(CollisionFeature& feature, bool ignorePlacement); + void insertFeature(CollisionFeature& feature, bool ignorePlacement, uint32_t bucketInstanceId); - std::vector queryRenderedSymbols(const GeometryCoordinates&, const UnwrappedTileID& tileID, const std::string& sourceID) const; + std::unordered_map> queryRenderedSymbols(const ScreenLineString&) const; - private: bool isOffscreen(const CollisionBox&) const; bool isInsideGrid(const CollisionBox&) const; diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp index 54b2b7539b..43e8ff4f93 100644 --- a/src/mbgl/text/placement.cpp +++ b/src/mbgl/text/placement.cpp @@ -49,8 +49,11 @@ void Placement::placeLayer(RenderSymbolLayer& symbolLayer, const mat4& projMatri if (!renderTile.tile.isRenderable()) { continue; } - - auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl); + assert(dynamic_cast(&renderTile.tile)); + GeometryTile& geometryTile = static_cast(renderTile.tile); + + + auto bucket = geometryTile.getBucket(*symbolLayer.baseImpl); assert(dynamic_cast(bucket)); SymbolBucket& symbolBucket = *reinterpret_cast(bucket); @@ -58,8 +61,8 @@ void Placement::placeLayer(RenderSymbolLayer& symbolLayer, const mat4& projMatri const float pixelsToTileUnits = renderTile.id.pixelsToTileUnits(1, state.getZoom()); - const float scale = std::pow(2, state.getZoom() - renderTile.tile.id.overscaledZ); - const float textPixelRatio = (util::tileSize * renderTile.tile.id.overscaleFactor()) / util::EXTENT; + const float scale = std::pow(2, state.getZoom() - geometryTile.id.overscaledZ); + const float textPixelRatio = (util::tileSize * geometryTile.id.overscaleFactor()) / util::EXTENT; mat4 posMatrix; state.matrixFor(posMatrix, renderTile.id); @@ -76,7 +79,14 @@ void Placement::placeLayer(RenderSymbolLayer& symbolLayer, const mat4& projMatri layout.get() == style::AlignmentType::Map, state, pixelsToTileUnits); - + + + // 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(symbolBucket.bucketInstanceId), + std::forward_as_tuple(symbolBucket.bucketInstanceId, geometryTile.getFeatureIndex(), geometryTile.id)); + placeLayerBucket(symbolBucket, posMatrix, textLabelPlaneMatrix, iconLabelPlaneMatrix, scale, textPixelRatio, showCollisionBoxes, seenCrossTileIDs, renderTile.tile.holdForFade()); } } @@ -150,11 +160,11 @@ void Placement::placeLayerBucket( } if (placeText) { - collisionIndex.insertFeature(symbolInstance.textCollisionFeature, bucket.layout.get()); + collisionIndex.insertFeature(symbolInstance.textCollisionFeature, bucket.layout.get(), bucket.bucketInstanceId); } if (placeIcon) { - collisionIndex.insertFeature(symbolInstance.iconCollisionFeature, bucket.layout.get()); + collisionIndex.insertFeature(symbolInstance.iconCollisionFeature, bucket.layout.get(), bucket.bucketInstanceId); } assert(symbolInstance.crossTileID != 0); @@ -305,6 +315,10 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket, std::set& bucket.updateOpacity(); bucket.sortFeatures(state.getAngle()); + auto retainedData = retainedQueryData.find(bucket.bucketInstanceId); + if (retainedData != retainedQueryData.end()) { + retainedData->second.featureSortOrder = bucket.featureSortOrder; + } } float Placement::symbolFadeChange(TimePoint now) const { @@ -337,5 +351,13 @@ void Placement::setStale() { const CollisionIndex& Placement::getCollisionIndex() const { return collisionIndex; } + +const RetainedQueryData& Placement::getQueryData(uint32_t bucketInstanceId) const { + auto it = retainedQueryData.find(bucketInstanceId); + if (it == retainedQueryData.end()) { + throw std::runtime_error("Placement::getQueryData with unrecognized bucketInstanceId"); + } + return it->second; +} } // namespace mbgl diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp index 653ae352ed..0e1751b127 100644 --- a/src/mbgl/text/placement.hpp +++ b/src/mbgl/text/placement.hpp @@ -44,7 +44,21 @@ public: // visible right away. const bool skipFade; }; - + +struct RetainedQueryData { + uint32_t bucketInstanceId; + std::shared_ptr featureIndex; + OverscaledTileID tileID; + std::shared_ptr> featureSortOrder; + + RetainedQueryData(uint32_t bucketInstanceId_, + std::shared_ptr featureIndex_, + OverscaledTileID tileID_) + : bucketInstanceId(bucketInstanceId_) + , featureIndex(std::move(featureIndex_)) + , tileID(std::move(tileID_)) {} +}; + class Placement { public: Placement(const TransformState&, MapMode mapMode); @@ -59,6 +73,8 @@ public: bool stillRecent(TimePoint now) const; void setRecent(TimePoint now); void setStale(); + + const RetainedQueryData& getQueryData(uint32_t bucketInstanceId) const; private: void placeLayerBucket( @@ -85,6 +101,8 @@ private: TimePoint recentUntil; bool stale = false; + + std::unordered_map retainedQueryData; }; } // namespace mbgl diff --git a/src/mbgl/tile/geometry_tile.cpp b/src/mbgl/tile/geometry_tile.cpp index 28f46f6f54..b0b898e61a 100644 --- a/src/mbgl/tile/geometry_tile.cpp +++ b/src/mbgl/tile/geometry_tile.cpp @@ -132,7 +132,7 @@ void GeometryTile::onLayout(LayoutResult result, const uint64_t resultCorrelatio buckets = std::move(result.buckets); - featureIndexPendingCommit = { std::move(result.featureIndex) }; + latestFeatureIndex = std::move(result.featureIndex); if (result.glyphAtlasImage) { glyphAtlasImage = std::move(*result.glyphAtlasImage); @@ -200,22 +200,12 @@ Bucket* GeometryTile::getBucket(const Layer::Impl& layer) const { return it->second.get(); } -void GeometryTile::commitFeatureIndex() { - // We commit our pending FeatureIndex when a global placement has run, - // synchronizing the global CollisionIndex with the latest buckets/FeatureIndex - if (featureIndexPendingCommit) { - featureIndex = std::move(*featureIndexPendingCommit); - featureIndexPendingCommit = nullopt; - } -} - void GeometryTile::queryRenderedFeatures( std::unordered_map>& result, const GeometryCoordinates& queryGeometry, const TransformState& transformState, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) { + const RenderedQueryOptions& options) { if (!getData()) return; @@ -228,17 +218,15 @@ void GeometryTile::queryRenderedFeatures( } } - featureIndex->query(result, - queryGeometry, - transformState.getAngle(), - util::tileSize * id.overscaleFactor(), - std::pow(2, transformState.getZoom() - id.overscaledZ), - options, - id.toUnwrapped(), - sourceID, - layers, - collisionIndex, - additionalRadius); + latestFeatureIndex->query(result, + queryGeometry, + transformState.getAngle(), + util::tileSize * id.overscaleFactor(), + std::pow(2, transformState.getZoom() - id.overscaledZ), + options, + id.toUnwrapped(), + layers, + additionalRadius); } void GeometryTile::querySourceFeatures( diff --git a/src/mbgl/tile/geometry_tile.hpp b/src/mbgl/tile/geometry_tile.hpp index 418db4a0b2..a3b2eb6492 100644 --- a/src/mbgl/tile/geometry_tile.hpp +++ b/src/mbgl/tile/geometry_tile.hpp @@ -54,8 +54,7 @@ public: const GeometryCoordinates& queryGeometry, const TransformState&, const std::vector& layers, - const RenderedQueryOptions& options, - const CollisionIndex& collisionIndex) override; + const RenderedQueryOptions& options) override; void querySourceFeatures( std::vector& result, @@ -88,11 +87,11 @@ public: void markRenderedPreviously() override; void performedFadePlacement() override; - void commitFeatureIndex() override; + const std::shared_ptr getFeatureIndex() const { return latestFeatureIndex; } protected: const GeometryTileData* getData() { - return featureIndex ? featureIndex->getData() : nullptr; + return latestFeatureIndex ? latestFeatureIndex->getData() : nullptr; } private: @@ -113,8 +112,7 @@ private: std::unordered_map> buckets; - optional> featureIndexPendingCommit; - std::unique_ptr featureIndex; + std::shared_ptr latestFeatureIndex; optional glyphAtlasImage; optional iconAtlasImage; diff --git a/src/mbgl/tile/geometry_tile_worker.cpp b/src/mbgl/tile/geometry_tile_worker.cpp index 61bc0cb597..ca20c4b8ab 100644 --- a/src/mbgl/tile/geometry_tile_worker.cpp +++ b/src/mbgl/tile/geometry_tile_worker.cpp @@ -440,8 +440,7 @@ void GeometryTileWorker::performSymbolLayout() { } symbolLayout->prepare(glyphMap, glyphAtlas.positions, - imageMap, imageAtlas.positions, - id, sourceID); + imageMap, imageAtlas.positions); } symbolLayoutsNeedPreparation = false; diff --git a/src/mbgl/tile/tile.cpp b/src/mbgl/tile/tile.cpp index 88db2ba07c..e65bc39540 100644 --- a/src/mbgl/tile/tile.cpp +++ b/src/mbgl/tile/tile.cpp @@ -37,8 +37,7 @@ void Tile::queryRenderedFeatures( const GeometryCoordinates&, const TransformState&, const std::vector&, - const RenderedQueryOptions&, - const CollisionIndex&) {} + const RenderedQueryOptions&) {} void Tile::querySourceFeatures( std::vector&, diff --git a/src/mbgl/tile/tile.hpp b/src/mbgl/tile/tile.hpp index 23365c6ae3..a0effa29a1 100644 --- a/src/mbgl/tile/tile.hpp +++ b/src/mbgl/tile/tile.hpp @@ -57,8 +57,7 @@ public: const GeometryCoordinates& queryGeometry, const TransformState&, const std::vector&, - const RenderedQueryOptions& options, - const CollisionIndex&); + const RenderedQueryOptions& options); virtual void querySourceFeatures( std::vector& result, @@ -109,11 +108,6 @@ public: // and will have time to finish by the second placement. virtual void performedFadePlacement() {} - // FeatureIndexes are loaded asynchronously, but must be used with a CollisionIndex - // generated from the same data. Calling commitFeatureIndex signals the current - // CollisionIndex is up-to-date and allows us to start using the last loaded FeatureIndex - virtual void commitFeatureIndex() {} - void dumpDebugLogs() const; const OverscaledTileID id; -- cgit v1.2.1