From a62745edf9ee2da1f6ebda07acfd8260f3696e50 Mon Sep 17 00:00:00 2001 From: Chris Loer Date: Wed, 18 Apr 2018 16:33:37 -0700 Subject: 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, 219 insertions(+), 198 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 c67786274a..8ea6259129 100644 --- a/src/mbgl/geometry/feature_index.cpp +++ b/src/mbgl/geometry/feature_index.cpp @@ -33,14 +33,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, @@ -49,9 +41,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) { @@ -68,7 +58,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) { @@ -76,23 +68,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 82a9255824..d3126bba45 100644 --- a/src/mbgl/layout/symbol_layout.cpp +++ b/src/mbgl/layout/symbol_layout.cpp @@ -181,8 +181,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; @@ -253,7 +252,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(); @@ -266,9 +265,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; @@ -297,8 +294,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 962a6571db..5b739678fb 100644 --- a/src/mbgl/renderer/renderer_impl.cpp +++ b/src/mbgl/renderer/renderer_impl.cpp @@ -396,10 +396,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); @@ -668,6 +664,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; @@ -678,10 +707,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; @@ -780,15 +811,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 31a5916a34..b35e151f82 100644 --- a/src/mbgl/renderer/sources/render_image_source.cpp +++ b/src/mbgl/renderer/sources/render_image_source.cpp @@ -84,8 +84,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..daf996356e 100644 --- a/src/mbgl/text/placement.cpp +++ b/src/mbgl/text/placement.cpp @@ -46,11 +46,13 @@ void Placement::placeLayer(RenderSymbolLayer& symbolLayer, const mat4& projMatri std::unordered_set seenCrossTileIDs; for (RenderTile& renderTile : symbolLayer.renderTiles) { - if (!renderTile.tile.isRenderable()) { + if (!renderTile.tile.isRenderable() || !dynamic_cast(&renderTile.tile)) { continue; } - - auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl); + GeometryTile& geometryTile = static_cast(renderTile.tile); + + + auto bucket = geometryTile.getBucket(*symbolLayer.baseImpl); assert(dynamic_cast(bucket)); SymbolBucket& symbolBucket = *reinterpret_cast(bucket); @@ -58,8 +60,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 +78,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 +159,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 +314,9 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket, std::set& bucket.updateOpacity(); bucket.sortFeatures(state.getAngle()); + if (retainedQueryData.find(bucket.bucketInstanceId) != retainedQueryData.end()) { + retainedQueryData.find(bucket.bucketInstanceId)->second.featureSortOrder = bucket.featureSortOrder; + } } float Placement::symbolFadeChange(TimePoint now) const { @@ -337,5 +349,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 a99cb91d26..317c5454f6 100644 --- a/src/mbgl/tile/geometry_tile.cpp +++ b/src/mbgl/tile/geometry_tile.cpp @@ -133,7 +133,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); @@ -201,22 +201,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; @@ -229,17 +219,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 1378ad5d3a..2e7d588d9b 100644 --- a/src/mbgl/tile/geometry_tile_worker.cpp +++ b/src/mbgl/tile/geometry_tile_worker.cpp @@ -441,8 +441,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