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.

2 files changed, 58 insertions, 32 deletions

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<std::string, std::vector<Feature>>& 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<const RenderLayer*>& layers,
-        const CollisionIndex& collisionIndex,
         const float additionalQueryRadius) const {
     
     if (!tileData) {
@@ -68,7 +58,9 @@ void FeatureIndex::query(
                                                            convertPoint<float>(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<size_t>::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<std::string, std::vector<Feature>> FeatureIndex::lookupSymbolFeatures(const std::vector<IndexedSubfeature>& symbolFeatures,
+                                                                                         const RenderedQueryOptions& queryOptions,
+                                                                                         const std::vector<const RenderLayer*>& layers,
+                                                                                         const OverscaledTileID& tileID,
+                                                                                        const std::shared_ptr<std::vector<size_t>>& featureSortOrder) const {
+    std::unordered_map<std::string, std::vector<Feature>> result;
+    if (!tileData) {
+        return result;
+    }
+    std::vector<IndexedSubfeature> 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<IndexedSubfeature> 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<std::string, std::vector<Feature>>& result,
     const IndexedSubfeature& indexedFeature,
-    const GeometryCoordinates& queryGeometry,
     const RenderedQueryOptions& options,
     const CanonicalTileID& tileID,
     const std::vector<const RenderLayer*>& 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 RenderLayer*>&,
-            const CollisionIndex&,
             const float additionalQueryRadius) const;
 
     static optional<GeometryCoordinates> translateQueryGeometry(
@@ -77,15 +72,22 @@ public:
             const float pixelsToTileUnits);
 
     void setBucketLayerIDs(const std::string& bucketName, const std::vector<std::string>& layerIDs);
+    
+    std::unordered_map<std::string, std::vector<Feature>> lookupSymbolFeatures(
+           const std::vector<IndexedSubfeature>& symbolFeatures,
+           const RenderedQueryOptions& options,
+           const std::vector<const RenderLayer*>& layers,
+           const OverscaledTileID& tileID,
+           const std::shared_ptr<std::vector<size_t>>& featureSortOrder) const;
 
 private:
     void addFeature(
             std::unordered_map<std::string, std::vector<Feature>>& result,
             const IndexedSubfeature&,
-            const GeometryCoordinates& queryGeometry,
             const RenderedQueryOptions& options,
             const CanonicalTileID&,
             const std::vector<const RenderLayer*>&,
+            const GeometryCoordinates& queryGeometry,
             const float bearing,
             const float pixelsToTileUnits) const;