Add support for `cameraForBounds` on globe projection

[karimnaaji]

Fixes https://github.com/mapbox/gl-js-team/issues/479

This PR adds support for cameraForBounds on globe and updates the method used by cameraForBounds to account fully for 3d perspective. A demo of the prototype to help visualize the new method is available here.

Currently, cameraForBounds only takes into account the map bearing in 2d dimension. In order to use it on globe as well as extend the method to account for pitch appropriately, the camera frustum adjustment has to be done in using the 3d bounding box of the coordinates we are fitting.

The new method reconstructs a 3d bounding box from the perspective of the camera, as can be seen in the following video:

https://user-images.githubusercontent.com/7061573/182975631-35471466-c537-434f-975a-2ec90d9cab67.mov

It's important to note that left and right planes aren't perfectly tight with the initial bounding box; this is an overall preferable behavior as we ensure that that the final camera placement is looking at the centroid of both the reconstructed aabb in camera space and the original bounds.

TODO

• [ ] Reject placement that can't fit or view the original bounds with a given orientation due to the earth curvature, refer:

https://user-images.githubusercontent.com/7061573/182977491-7858fbff-70cf-446b-a5c9-a7e1c576023c.mov

• [ ] Correctly account for fixed pixel space correction introduced for globe to prevent implicit zooming on the poles
• [ ] Account for padding options

Launch Checklist

• [x] briefly describe the changes in this PR
• [x] include before/after visuals or gifs if this PR includes visual changes
• [ ] write tests for all new functionality
• [ ] document any changes to public APIs
• [x] manually test the debug page
• [x] tagged @mapbox/gl-native if this PR includes shader changes or needs a native port
• [x] apply changelog label ('bug', 'feature', 'docs', etc) or use the label 'skip changelog'
• [ ] add an entry inside this element for inclusion in the mapbox-gl-js changelog: <changelog>Add support for cameraForBounds with globe view</changelog>

[mpulkki-mapbox]

These animations are awesome and really help to understand the idea behind the code! I have few questions as this is a really fascinating topic!

I see that you're finding the best fit for the camera frustum using an AABB in camera's coordinate space that's been built by encapsulating the AABB transformed from the ecef space. Why do you think it's necessary step to construct an intermediate AABB in ecef space first? Right now result of the algorithm seems to vary as a function of longitude and latitude as the bounding box is aligned in ecef space and not in camera space (your interactive demo is really useful for spotting things like these!)

Taking this route you could first try to transform corners of the lat&lng bounds into world space (aka pixel space) using the globe matrix and then building the AABB. This could help with the aforementioned issue as the up vector in world space is always pointing to same direction because camera actually moves on a flat plane in mercator coordinates. In other words intermediate AABBs built this way should always be aligned with the tangent plane at the centroid location (I think).

A slightly modified approach I've been thinking about is to simplify the problem into fitting points inside a frustum. It should be a fairly simple problem as camera centroid, bearing & pitch are fixed and only distance to the ground is changing. Given a set of points (corners of the lat&lng region in this case) and camera frustum planes you could find the closest intersection point between any pair of frustum planes and points and use that distance to move the camera forward.

[karimnaaji]

These animations are awesome and really help to understand the idea behind the code! I have few questions as this is a really fascinating topic!

Thanks for giving a look!

I see that you're finding the best fit for the camera frustum using an AABB in camera's coordinate space that's been built by encapsulating the AABB transformed from the ecef space. Why do you think it's necessary step to construct an intermediate AABB in ecef space first? Right now result of the algorithm seems to vary as a function of longitude and latitude as the bounding box is aligned in ecef space and not in camera space (your interactive demo is really useful for spotting things like these!)

Taking this route you could first try to transform corners of the lat&lng bounds into world space (aka pixel space) using the globe matrix and then building the AABB. This could help with the aforementioned issue as the up vector in world space is always pointing to same direction because camera actually moves on a flat plane in mercator coordinates. In other words intermediate AABBs built this way should always be aligned with the tangent plane at the centroid location (I think).

Yes that's a good point, it's worth investigating whether we could skip an extra space transformation in order to reduce the longitude/latitude dependency by doing it directly in world space as you suggest, I'll investigate that as it might might also result in a better fit overall.

A slightly modified approach I've been thinking about is to simplify the problem into fitting points inside a frustum. It should be a fairly simple problem as camera centroid, bearing & pitch are fixed and only distance to the ground is changing. Given a set of points (corners of the lat&lng region in this case) and camera frustum planes you could find the closest intersection point between any pair of frustum planes and points and use that distance to move the camera forward.

I investigated this, but unless I missed something, finding the closest intersection of the frustum planes aligned with a set of points may not always result in the camera being aligned or looking at the centroid, which I think is an important property of cameraForBounds placement API. Although it would result in tighter placement, keeping the centroid of the bounds being fit aligned with the center (as implemented in this PR) is a tradeoff.

[karimnaaji]

Thanks for the review and helpful simplification suggestions, I've addressed most of them and will add more tests for the corner case of requesting entries such as [-180, 0], [180, 0]. Regarding the concern of size:

and adds quite a bit of bundle size (+1.3KB gzipped!)

it will level-out with https://github.com/mapbox/mapbox-gl-js/pull/12211 (once fitScreenCoordinates and fitBounds all go through the method introduced here, allowing to delete some code and benefit from globe support), I've split the work in two separate PRs to make it easier to review.

[karimnaaji]

I'm seeing some strange behavior with bounds surrounding a pole. The map usually zooms much further out than I would expect. Sometimes, when starting at high zoom and pitch, zoom doesn't change at all.

That's a side from the method we adopted in https://github.com/mapbox/mapbox-gl-js/pull/11951. Minimizing scaling towards the pole has the effect of not resolving the real zoom for a given altitude. Since we re-adjust the scaling to be constant instead of implicitly zooming in but aren't adjusting zoom at the same time, we may resolve a much higher zoom than if we were to zoom towards the pole, compared to before https://github.com/mapbox/mapbox-gl-js/issues/11353.

The current approach towards resolving altitude -> true z in this PR is an approximation: https://github.com/mapbox/mapbox-gl-js/pull/12138/files#diff-a2b3330768267b8c7996b8bf292fcd864e8b768f538436813b0d7e19f7202176R1988, which may introduce a fairly localized issue around the poles/extreme latitudes as you noticed. I think we can improve and put more effort into deriving true zoom if that becomes more of an issue in practice.

A suggested fix towards the original issue of #11353 would be to adjust the zoom dynamically, so that such calculation are always correct, but this had other side effects since styling can depend on zoom. It's not a trivial problem and these are some of the trade-offs that we have to account for.

I'm also noticing that the globe will spin around rather than crossing the antimeridian, this seems to be an existing issue with map.easeTo().

This isn't an issue directly related to this PR, and part of easeTo.