search

mapbox / mapbox-gl-native

Interactive, thoroughly customizable maps in native Android, iOS, macOS, Node.js, and Qt applications, powered by vector tiles and OpenGL
https://mapbox.com/mobile
Other
4.37k stars 1.33k forks source link

Refactor tile coverage to support level of detail #16335

Closed mpulkki-mapbox closed 4 years ago

mpulkki-mapbox commented 4 years ago

This pull request implements a more versatile logic for finding visible tiles on the screen. Intersection tests have been extended to 3D space by using bounding volumes for tiles and camera instead of projecting everything to zero elevation plane. Tile pyramid is traversed depth-first while preserving distances to tiles allowing an easy support for a level-of-detail. Even though the distance based lod is supported by this implementation, this PR has no visible effect for the user. Level of detail logic is deactive when pitch is <= 60 degrees.

The native implementation follows the javascript one (https://github.com/mapbox/mapbox-gl-js/pull/8975) with few exceptions:

  1. Certain edge cases (false positives) were found in the tests. These cases (<1%) are culled by more precise intersection tests before reporting a tile to be visible.
  2. Few hotspots were found using a profiler so the order of intersection tests were slightly modified for a better performance.

Performance-wise the new implementation is few orders of magnitude slower than the original one. In a bigger picture the difference is not noticeable. I could see an increase of 5-15% time spent in TilePyramid::Update. Perhaps it's worth of discussion if the new tileCover should be a separate function and optional unless explicitly activated?

TODO

pozdnyakov commented 4 years ago

Looks great, but let @astojilj to take a look before merge

astojilj commented 4 years ago

Performance-wise the new implementation is few orders of magnitude slower than the original one. In a bigger picture the difference is not noticeable. I could see an increase of 5-15% time spent in TilePyramid::Update. Perhaps it's worth of discussion if the new tileCover should be a separate function and optional unless explicitly activated?

In case that this was measured using some benchmark, how much is "tile cover update" budget per frame affected by this on example mobile platform?

astojilj commented 4 years ago

LGTM after documenting performance impact on one frame.

mpulkki-mapbox commented 4 years ago

Performance-wise the new implementation is few orders of magnitude slower than the original one. In a bigger picture the difference is not noticeable. I could see an increase of 5-15% time spent in TilePyramid::Update. Perhaps it's worth of discussion if the new tileCover should be a separate function and optional unless explicitly activated?

In case that this was measured using some benchmark, how much is "tile cover update" budget per frame affected by this on example mobile platform?

I profiled the code on my quite fast laptop in the following location: [INFO] {mbgl-glfw}[General]: Exit location: --lat="60.169900" --lon="24.943500" --zoom="16.064100" --bearing "43.857600". I chose few test runs describing the average performance of both new and original tileCover implementation. These numbers are not exact but they give a rough idea of the performance impact.

original: vtune_orig

new: vtune_new

Tests were done by rendering a map 60fps for 10 seconds using "streets-v11" style. Time spent in TilePyramid::update increased ~10%. tileCover is also called from render_background_layer.cpp, but the profiler could not catch that. Frame budget used by TilePyramid::update during a 10s test run increases from ~2.7% to ~3.0% based on these observations. Impact on the overall tile budget is quite small.