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.

4 files changed, 67 insertions, 55 deletions

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<bool,bool> 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<float>& polygon, const GridIndex<Inde
     return util::polygonIntersectsPolygon(integerPolygon, bboxPoints);
 }
 
-std::vector<IndexedSubfeature> CollisionIndex::queryRenderedSymbols(const GeometryCoordinates& queryGeometry, const UnwrappedTileID& tileID, const std::string& sourceID) const {
-    std::vector<IndexedSubfeature> result;
+std::unordered_map<uint32_t, std::vector<IndexedSubfeature>> CollisionIndex::queryRenderedSymbols(const ScreenLineString& queryGeometry) const {
+    std::unordered_map<uint32_t, std::vector<IndexedSubfeature>> 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<float> projectedQuery;
+
+    LineString<float> gridQuery;
     for (const auto& point : queryGeometry) {
-        auto projected = projectPoint(posMatrix, convertPoint<float>(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<IndexedSubfeature, GridIndex<IndexedSubfeature>::BBox>;
     
-    std::vector<QueryResult> thisTileFeatures;
     std::vector<QueryResult> 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<QueryResult> 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<std::string, std::unordered_map<std::string, std::unordered_set<std::size_t>>> sourceLayerFeatures;
-    for (auto& queryResult : thisTileFeatures) {
+    std::unordered_map<uint32_t, std::unordered_set<size_t>> 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<IndexedSubfeature> queryRenderedSymbols(const GeometryCoordinates&, const UnwrappedTileID& tileID, const std::string& sourceID) const;
+    std::unordered_map<uint32_t, std::vector<IndexedSubfeature>> 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<uint32_t> seenCrossTileIDs;
 
     for (RenderTile& renderTile : symbolLayer.renderTiles) {
-        if (!renderTile.tile.isRenderable()) {
+        if (!renderTile.tile.isRenderable() || !dynamic_cast<GeometryTile*>(&renderTile.tile)) {
             continue;
         }
-
-        auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl);
+        GeometryTile& geometryTile = static_cast<GeometryTile&>(renderTile.tile);
+        
+        
+        auto bucket = geometryTile.getBucket(*symbolLayer.baseImpl);
         assert(dynamic_cast<SymbolBucket*>(bucket));
         SymbolBucket& symbolBucket = *reinterpret_cast<SymbolBucket*>(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::IconRotationAlignment>() == 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<style::TextIgnorePlacement>());
+                collisionIndex.insertFeature(symbolInstance.textCollisionFeature, bucket.layout.get<style::TextIgnorePlacement>(), bucket.bucketInstanceId);
             }
 
             if (placeIcon) {
-                collisionIndex.insertFeature(symbolInstance.iconCollisionFeature, bucket.layout.get<style::IconIgnorePlacement>());
+                collisionIndex.insertFeature(symbolInstance.iconCollisionFeature, bucket.layout.get<style::IconIgnorePlacement>(), bucket.bucketInstanceId);
             }
 
             assert(symbolInstance.crossTileID != 0);
@@ -305,6 +314,9 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket, std::set<uint32_t>&
 
     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> featureIndex;
+    OverscaledTileID tileID;
+    std::shared_ptr<std::vector<size_t>> featureSortOrder;
+    
+    RetainedQueryData(uint32_t bucketInstanceId_,
+                      std::shared_ptr<FeatureIndex> 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<uint32_t, RetainedQueryData> retainedQueryData;
 };
 
 } // namespace mbgl