Mapbox-gl-native: Map::queryPointAnnotations() -> Map::queryRenderedFeatures() returns unexpected result as map is moved

[boundsj]

In https://github.com/mapbox/mapbox-gl-native/pull/5165 we added a new method queryPointAnnotations that calls queryRenderedFeatures with a ScreenBox representing the view port for which you want to query for all point annotations. In the iOS SDK, this is used by:

• -[MGLMapView annotationTagAtPoint:persistingResults:] // used for annotation selection
• -[MGLMapView accessibilityAnnotationCount]
• -[MGLMapView accessibilityElementAtIndex:]
• -[MGLMapView indexOfAccessibilityElement:]

I was planing to use queryPointAnnotations in https://github.com/mapbox/mapbox-gl-native/pull/5987 to help clean up and optimize the implementation in the iOS SDK's updateAnnotationViews. However, based on the visual behavior I'm seeing after doing that, I don't know that it'll be possible to rely on the underlying queryRenderedFeatures for this purpose.

For example, if I give queryPointAnnotations\queryRenderedFeatures a view port of:

viewPort == mapView.bounds //(origin = (x = 0, y = 0), size = (width = 375, height = 667))

I see that the annotation view update method stops updating views ~almost~ when I would expect it to, at first (the views get stuck near the edge of the view port when their annotations move offscreen). However, when I change the zoom level, the view port / ScreenBox seems to reflect only the upper left section of the view. This is illustrated by native views getting stuck on the map even when the underlying annotation is still technically visible -- at this point, queryPointAnnotations is returning less annotations than I would expect (and sometimes 0 annotations).

Another issue is that the result of queryPointAnnotations\queryRenderedFeatures seems to lag behind the map movement. This is particularly noticeable when changing zoom level. Annotation views will maintain their center for the last zoom level and then snap back suddenly.

Finally, I see that queryPointAnnotations\queryRenderedFeatures returns no annotations where I expect it should as the map is panned. However, once panning is stopped you can still select annotations via [MGLMapView annotationTagAtPoint:persistingResults:] (which uses queryPointAnnotations\queryRenderedFeatures under the hood) by clicking where they ~should~ be (not where the annotation view is floating) and you get the "expected" result (a callout over the actual location of the annotation that really is in the view port):

For now, I don't think we should use queryPointAnnotations\queryRenderedFeatures as currently implemented for queries when the map is panned, zoom levels are changed, rotation or pitch is changed, etc. I'm not able to reproduce this issue under test in test/api/annotations.cpp but the test does not simulate queries while the map is moved so it may be fine to keep #5165 for the use cases it was written for (noted above) and just not use it for the updateAnnotationViews case.

Next steps:

• [ ] Simplify #5165 to not use queryPointAnnotations
• [ ] Test that accessibilityAnnotationCount, accessibilityElementAtIndex:, indexOfAccessibilityElement: work as expected when implemented using queryPointAnnotations
• [ ] Review the implementation of queryPointAnnotations with @jfirebaugh to learn more about how it should / can be used
• [ ] Revert #5165 if necessary (this may not be required if it works for all cases other than annotation view updates)

cc @1ec5 @tobrun @incanus @jfirebaugh @pveugen

[1ec5]

We should determine whether these issues arise from calling mbgl::Map::queryRenderedFeatures() in response to mbgl::MapChangeDidFinishRenderingFrame. Perhaps the feature index hasn’t been updated by that point? Otherwise, maybe we have on our hands a real bug in queryRenderedFeatures() that would affect ordinary querying. We should investigate both possibilities before abandoning queryPointAnnotations(), which would put #5502 in jeopardy.

[boundsj]

I went ahead and opened a WIP PR for a visible annotations API in https://github.com/mapbox/mapbox-gl-native/pull/6061 since that API can help us visualize the problematic behavior. In https://github.com/mapbox/mapbox-gl-native/pull/6061/commits/c2a7ec8468abde9db4bf218b71d6eacf7fb29c2c I query for annotations with the map view's bounds as the viewport.

I think I can consistently repro now on that PR's branch as follows:

1) Add an annotation (a sprite annotation will do)
2) Move the map so that the annotation is in the upper left
3) Query for annotations and see the expected value of 1
4) Move the map so that the annotation is in the lower right
5) Query for annotations and see an unexpected value of 0

Upper left works fine

Lower right fails

Additional context

• Tilting the map helps in the sense that I'm more likely to find the annotation if I search for it. Although if the map is panned such that the annotation is in the upper right portion of the map the query returns no results
• Rotating the map > 90º appears to mostly break queryRenderedFeatures. I almost never get a result after doing that. Removing the rotation allows it to work (as much as it can) again.

So, despite what I said before, this does not seem like an issue that'll happen only when using queryRenderedFeatures in response to mbgl::MapChangeDidFinishRenderingFrame. I'll keep digging but it seems like there might be a problem with the math or the way we are calling queryRenderedFeatures. I'd appreciate 👀 to spot check my work to see if I've made some sort of obvious mistake.

cc @1ec5 @tobrun @incanus

[tobrun]

After reading up on this, I'm all for reverting this for now but at the same time don't see an issue keeping the new api around (internally). In the end we want to migrate to that proposed solution.. thank you for looking into this! These were some interesting finds!

[ivovandongen]

Been looking into this today. Couple of observations:

• Using queryRenderedFeatures for features works properly (on android) with the use cases as described by @boundsj above:
  
  
  
  • When panning / right after
  
  
  • After rotating
  
  
  • When tilted
  
  
• Using queryRenderedFeatures for point annotations though, only works correctly when you don't zoom or change the bearing. Panning does work correctly
• To use the queryRenderedFeatures, the coordinates passed should be corrected for pixelRatio. When testing some more in the branch from @boundsj I noticed that the top-right corner also doesn't give the expected results. Indicating that the area may be too small to begin with.

That said, I haven't found the root cause yet.

[boundsj]

Thanks @ivovandongen. I noticed that when I updated the ScreenBox points to reflect the device pixelRatio it certainly helped. However, the retina values (2x and 3x on iPhone 6 and 6 Plus) were actually too big -- annotations were coming back in the query result even though they were far offscreen to the right ("far" as a function of zoom level).

Digging more, I noticed that we calculate a dynamic scale factor based on the current zoom level and the tile's notion of what zoom level it is intended to represent. I thought that this scale value is key but, since it is a per tile value, there was no way apply it to the ScreenBox at the SDK level.

In https://github.com/mapbox/mapbox-gl-native/pull/6061/commits/16da44f3584321d1acea53556137ad2e6727fcf3, I propose pushing the ScreenBox down several levels so that the coordinates can be adjusted once we have all the data we need (i.e. the tile). This is less efficient than before but I'm not sure how else we can get the per tile value. Maybe we could take one tile as a representation of all for the current query and move the geometry vector formation up higher again in Impl::queryRenderedFeatures()?

In any case, with this change querying for point annotations now works for all devices at all zoom levels and all values of pitch.

I'm still seeing that querying completely fails after the map is rotated past 45 degrees. I thinkwe should investigate FeatureIndex::addFeature() and its use of queryIntersectsGeometry since I think the issue with interpreting the bearing is somewhere in that method.

[1ec5]

I'm still seeing that querying completely fails after the map is rotated past 45 degrees.

This is usually indicative of a problem where we try to compute a coordinate bounding box by converting four screen coordinates, each at the corner of the screen, and we assume that each screen corner corresponds to a particular corner of the bounding box regardless of the rotation. We saw this issue as we implemented fitBounds and camera roundtripping originally.

[ivovandongen]

@boundsj I'm afraid that this change (https://github.com/mapbox/mapbox-gl-native/pull/6061/commits/16da44f3584321d1acea53556137ad2e6727fcf3) breaks "normal" feature querying. When I rotate / zoom now the area queried doesn't match the expected area anymore (see the screenshot).

[ivovandongen]

What still puzzles me is the way we need to use queryRenderedFeatures on android. When using a Nexus 5 with a screen of 1920x1080px, if I want an accurate query box for the entire mapview (1584.0x1080px after subtracting space for bar and top navigation) I need to divide the size in pixels by the pixelRatio (2.65 on a nexus 5) to get the right ScreenBox to pass to map::queryRenderedFeatures, so 411.42x603.42 in this case. This implies that the coordinates are multiplied with the pixelratio somewhere in core again.

This seems to be different on ios though, as your example shows that the ScreenBox needs to be closer to the actual pixel size of the map. Maybe this indicates a difference in how we instantiate the platform specific mbgl::View implementation.

[boundsj]

@ivovandongen when I run with https://github.com/mapbox/mapbox-gl-native/pull/6061/commits/16da44f3584321d1acea53556137ad2e6727fcf3 in the Android emulator, I don't think I see the same issue you are describing. The highlight features in box query appears to work, I think.

Never mind. I'm not certain that I'm running with the correct core dependency in the Android emulator.

[boundsj]

In https://github.com/mapbox/mapbox-gl-native/pull/6061/commits/4aa6e6e8bbed5c36ddee376f32b6f6c98a86cee1 I added a new test harness for adding two specific annotations (a point and a line) and a query for those annotations. In https://github.com/mapbox/mapbox-gl-native/pull/6061/commits/bae271708d43075945d7b195a18e2311e29b99c1 I kept hacking around the core issue by using scaled and non-scaled boxes for the shape vs point queries in FeatureIndex::query(). I think that this should fix the issues noted above with "normal" feature querying. I see that the features are returned as expected as they pass in and out of the query box -- although rotating the map still completely breaks the query's ability to find points:

At this point, I'm suspicious of CollisionTile::queryRenderedSymbols() and/or the way we call it in FeatureIndex::query().

[ivovandongen]

@boundsj I think you are right in your suspicions of CollisionTile::queryRenderedSymbols(). I've added some debug logging, and it seems that when you rotate the anchor is correct, but the query box is not always projected in the right direction.

More concretely. I see the following when querying without rotation:

• Query TreeBox: 7392.000000,4992.000000 8991.000000,6592.000000
• Location of annotation in rtree: (8151, 5665)x(8231, 5745)

With rotation (around 180 degrees):

• Query TreeBox: -7230.944336,-5159.246582 -5609.944336,-3538.246582
• Location of annotation in rtree: (-8077.09, -5959.86)x(-7997.09, -5879.86)

[ivovandongen]

@boundsj I made an attempt to transform the querybox with the given rotation (see last commit). This gives surprisingly good results, but it isn't quite there yet. When rotated, the box is not quite in the right place / of the right form.

[1ec5]

The vertical offset in https://github.com/mapbox/mapbox-gl-native/issues/6055#issuecomment-243377516 may be due to the top edge inset that the SDK automatically applies to accommodate the top bar. visibleCoordinateBounds should be excluding the top bar, but the origin is still at the top-left of the screen in this case.

[ansis]

I started looking into this today but I didn't get to the bottom of it. I'm out for the next two weeks but hopefully this gives you enough background to dig in a bit more without me.

While writing this up I realized that the query box used by CollisionTile#queryRenderedSymbols is wrong. See the bold section further down. I'd try fixing this first.

Narrowing down what is affected

• Are regular map layers affected? Or only annotation layers?
  
  
  
  • If only annotation layers are affected then the bug is most likely not in the core part of queryRenderedFeatures
  
  
  • If all layers are affected, create a query test and add it to mapbox-gl-test-suite
  
  
  • Running the test against mapbox-gl-js tells you whether it is a porting error
  
  
  • Running the test lets you debug quickly without restarting the simulator: make node && node platform/node/test/query.test.js
  
  
• Are lines, fills and circles affected by the bug? Or only symbols?
  
  
  
  • Symbols are indexed differently, so
  
  

Coordinate systems

Unfortunately the coordinate systems, conversions between them can be hard to follow. Here's a bit of background:

• the query gets converted from screen coordinates to global tile coordinates. Rotation get's handled in this step.
• the query gets converted from global tile coordinates to each individual tile's coordinate system
• The query that FeatureIndex#query receives in in that individual tile's coordinate system
• Since FeatureIndex indexes all geometries in the tile's coordinate system, FeatureIndex#query can use this query without transforming it to find all the fills, lines and circles
• FeatureIndex#query calls CollisionTile#queryRenderedFeatures to find all the symbols.
• Symbols are indexed separately from fills, lines and circles for several reasons:
  
  
  
  • fills, lines and circles are always visible. Individual symbols may be hidden to prevent collisions
  
  
  • fills, lines and circles always rotate with the tile surface. Symbols can stay aligned with the map
  
  

Symbol indexing

The index used for symbol querying is the same one used to do symbol placement (collision prevention). During symbol placement we need to check how much two collision boxes can be scaled before they collide. This calculation is much simpler when all the boxes are axis-aligned (all the edges are either perfectly horizontal or perfectly vertical, never slanted). If you enable the collision debug rendering you'll see all these axis aligned boxes.

All the collision boxes are aligned with the screen, not the tile edges. Because of this, the CollisionTile index can't just use regular tile coordinates. It needs to rotate them.

CollisionTile#queryRenderedSymbols needs to convert the query to the CollisionTile's rotated coordinate system. It tries to do that here by rotating the bbox of the already-rotated-query. This is a bug! The entire query geometry should be passed to CollisionTile#queryRenderedSymbols. It should rotate each point of the query using rotationMatrix and then take the bbox of that. The fix for this should be tested in mapbox-gl-test-suite and should be ported to -gl-js.

Symbol index updates

When the map is rotated, the CollisionTile index is recalculated to update placement and prevent symbol collisions. An updated CollisionTile index should also be created for layers that allow collisions. These updated indexes do not get created instantly! Map rotation triggers a recalculation but it does not wait for the results before rendering. The map is rendered with stale data until the recalculation is finished. Not waiting before rendering reduces the amount of work that needs to be done each frame and let's rendering happen at a higher framerate.

Since queryRenderedFeatures uses this index, queries could be slightly incorrect in the split second after the map is rotated. Or it is possible that the recalculation is failing entirely for annotation tiles.

[brunoabinader]

Fixing the bug reported above (forwarding the query geometry to CollisionTile::queryRenderedSymbols so each individual geometry can be rotated using CollisionTile rotation matrix and then generating a box out of that) seems to fix the issue - my unit tests are now passing. I'm writing up a few more tests and then finish generating the query test for mapbox-gl-test-suite to confirm - thanks @ansis for the detailed explanation!

[jfirebaugh]

Per GL Core scrum today, we believe that #6627 resolved the main issue reported here with queryPointAnnotations, but only for a _non-tilted_ map. The following issues remain:

• For tilted maps, we believe that queryPointAnnotations may still return incorrect results.
• For symbol layers in general, which don't necessarily use the same layout properties as the point annotation layer, queryRenderedFeatures may return incorrect results.

@brunoabinader Did I summarize that correctly?

@boundsj Can you confirm that queryPointAnnotations is now behaving as expected, so long as the map isn't tilted?

[brunoabinader]

For tilted maps, we believe that queryPointAnnotations may still return incorrect results.

Related ticket: https://github.com/mapbox/mapbox-gl-native/issues/6630

For symbol layers in general, which don't necessarily use the same layout properties as the point annotation layer, queryRenderedFeatures may return incorrect results.

Precise @jfirebaugh 🎯 thank you for summarizing this. For colliding symbol layers, I'm still perceiving the same issues reported by @boundsj here.

I had a talk with @ansis last week about some ideas on how to solve the remaining tasks:

• Perspective: we could try using TransformState's projection matrix to transform the query geometry instead of applying rotation and perspective transformations manually;
• Query on symbol buckets instead of CollisionTile - idea behind this is that placement calculation done when rendering might differ from querying and thus produce different results.
• Store the minimum placement scale value for each feature that gets into the symbol buckets so we don't need to recalculate them when querying.

[boundsj]

Can you confirm that queryPointAnnotations is now behaving as expected, so long as the map isn't tilted?

@jfirebaugh @brunoabinader Yes! It appears to be behaving as expected when the map is not tilted. I see the expected query result when the map is and is not rotated. In fact, even when the map is tilted (with and without rotation), the query result returns results that are just outside of the viewport (i.e. it over counts) which is a lot better than under counting for the PRs I'm working on. Although https://github.com/mapbox/mapbox-gl-native/pull/6061 probably needs an accurate count, if possible.

[1ec5]

Possibly related to mapbox/mapbox-gl-js#2647.

[brunoabinader]

Fixed in #6773.

[PhaelIshall]

I am having the same issue now with map.queryRenderedFeatures{layers:['somelayer']}). It is returning an empty map when I zoom in or out but when I move the cursor it returns the correct value. Have there been no fixes for this yet? I looked at the above posts and the issues linked as well but nothing mentions fixing this particular function?

[1ec5]

@PhaelIshall, please open a separate issue about the problem you’re seeing. If possible, please provide some sample code that demonstrates the problem. Lots has changed in this library since this issue was closed, so it’s possible that the root cause is unrelated to #6773.