Tiles LOD: load and render based on zoom when displayed

Fixes #9037

6 files changed, 71 insertions, 11 deletions

diff --git a/include/mbgl/util/constants.hpp b/include/mbgl/util/constants.hpp
index ffdc4b2b30..6633e25323 100644
--- a/include/mbgl/util/constants.hpp
+++ b/include/mbgl/util/constants.hpp
@@ -34,7 +34,13 @@ constexpr double LATITUDE_MAX = 85.051128779806604;
 constexpr double LONGITUDE_MAX = 180;
 constexpr double DEGREES_MAX = 360;
 constexpr double PITCH_MIN = 0.0;
-constexpr double PITCH_MAX = M_PI / 3;
+/*
+ * Max pitch is limited to 90 deg - TransformState::fov / 2, which evaluates to 71.5 deg, when
+ * perspective center's offset is 0.  When padding is used, and the perspective center moved from
+ * center of the screen, max pitch is further capped by Transform::getMaxPitchForEdgeInsets.
+ * We set the max to 70 to keep the limit constant with small padding.
+ */
+constexpr double PITCH_MAX = 70 * DEG2RAD;
 constexpr double MIN_ZOOM = 0.0;
 constexpr double MAX_ZOOM = 25.5;
 constexpr float  MIN_ZOOM_F = MIN_ZOOM;
diff --git a/src/mbgl/map/transform_state.cpp b/src/mbgl/map/transform_state.cpp
index 77309a2a55..31d95821f1 100644
--- a/src/mbgl/map/transform_state.cpp
+++ b/src/mbgl/map/transform_state.cpp
@@ -174,6 +174,10 @@ double TransformState::pixel_y() const {
     return center + y;
 }
 
+ScreenCoordinate TransformState::getCenterOffset() const {
+    return { 0.5 * (edgeInsets.left() - edgeInsets.right()), 0.5 * (edgeInsets.top() - edgeInsets.bottom()) };
+}
+
 #pragma mark - Zoom
 
 double TransformState::getZoom() const {
@@ -373,10 +377,6 @@ void TransformState::constrain(double& scale_, double& x_, double& y_) const {
     }
 }
 
-ScreenCoordinate TransformState::getCenterOffset() const {
-    return { 0.5 * (edgeInsets.left() - edgeInsets.right()), 0.5 * (edgeInsets.top() - edgeInsets.bottom()) };
-}
-
 void TransformState::moveLatLng(const LatLng& latLng, const ScreenCoordinate& anchor) {
     auto centerCoord = Projection::project(getLatLng(LatLng::Unwrapped), scale);
     auto latLngCoord = Projection::project(latLng, scale);
diff --git a/src/mbgl/map/transform_state.hpp b/src/mbgl/map/transform_state.hpp
index cca42db20f..3ec1d52d20 100644
--- a/src/mbgl/map/transform_state.hpp
+++ b/src/mbgl/map/transform_state.hpp
@@ -49,6 +49,10 @@ public:
     double pixel_x() const;
     double pixel_y() const;
 
+    // Viewport center offset, from [size.width / 2, size.height / 2], defined
+    // by |edgeInsets| in screen coordinates, with top left origin.
+    ScreenCoordinate getCenterOffset() const;
+
     // Zoom
     double getZoom() const;
     uint8_t getIntegerZoom() const;
@@ -96,10 +100,6 @@ private:
     bool rotatedNorth() const;
     void constrain(double& scale, double& x, double& y) const;
 
-    // Viewport center offset, from [size.width / 2, size.height / 2], defined
-    // by |edgeInsets| in screen coordinates, with top left origin.
-    ScreenCoordinate getCenterOffset() const;
-
     LatLngBounds bounds;
 
     // Limit the amount of zooming possible on the map.
diff --git a/src/mbgl/renderer/tile_pyramid.cpp b/src/mbgl/renderer/tile_pyramid.cpp
index 54e0b1eb26..64eb5f2a7b 100644
--- a/src/mbgl/renderer/tile_pyramid.cpp
+++ b/src/mbgl/renderer/tile_pyramid.cpp
@@ -106,11 +106,11 @@ void TilePyramid::update(const std::vector<Immutable<style::LayerProperties>>& l
             }
 
             if (panZoom < idealZoom) {
-                panTiles = util::tileCover(parameters.transformState, panZoom);
+                panTiles = util::tileCoverWithLOD(parameters.transformState, panZoom, zoomRange.min);
             }
         }
 
-        idealTiles = util::tileCover(parameters.transformState, idealZoom);
+        idealTiles = util::tileCoverWithLOD(parameters.transformState, idealZoom, zoomRange.min);
     }
 
     // Stores a list of all the tiles that we're definitely going to retain. There are two
diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp
index 5189b79f26..11e1a97f4c 100644
--- a/src/mbgl/util/tile_cover.cpp
+++ b/src/mbgl/util/tile_cover.cpp
@@ -173,6 +173,59 @@ std::vector<UnwrappedTileID> tileCover(const TransformState& state, int32_t z) {
         z);
 }
 
+std::vector<UnwrappedTileID> tileCoverWithLOD(const TransformState& state, int32_t z, int32_t minZ) {
+    assert(state.valid());
+
+    const double w = state.getSize().width;
+    const double h = state.getSize().height;
+
+    const auto offset = state.getCenterOffset();
+    constexpr double zoomDiff = 1.0;
+    constexpr double coefLOD[] = {
+       0.55 * zoomDiff / (zoomDiff + 1),
+       0.55 * (zoomDiff + 1) / (zoomDiff + 2),
+       0.55 * (zoomDiff + 2) / (zoomDiff + 3)
+    };
+    // Tangens of field of view above center.
+    const double tanFov = (h * 0.5 + offset.y) / (1.5 * h);
+
+    std::vector<UnwrappedTileID> result;
+    double top = 0.0;
+    double bottom = 0.0;
+
+    for (size_t i = 0; top < h && i <= std::extent<decltype(coefLOD)>::value; i++, z--) {
+        if (z == minZ || i == std::extent<decltype(coefLOD)>::value) {
+            top = h; // final pass, get all to the top.
+        } else {
+            const double treshold = state.getPitch() ?  : (h * 0.5 + offset.y);
+            top = std::min(h, treshold );
+            top = state.getPitch()
+                ? std::min(h, h * 0.5 - offset.y + h * coefLOD[i] / (tanFov * std::tan(state.getPitch())))
+                : h;
+        }
+        std::vector<UnwrappedTileID> cover = tileCover(
+            TileCoordinate::fromScreenCoordinate(state, z, { 0,   top }).p,
+            TileCoordinate::fromScreenCoordinate(state, z, { w,   top }).p,
+            TileCoordinate::fromScreenCoordinate(state, z, { w,   bottom }).p,
+            TileCoordinate::fromScreenCoordinate(state, z, { 0,   bottom }).p,
+            TileCoordinate::fromScreenCoordinate(state, z, { w/2, h/2 }).p,
+            z);
+        bottom = top;
+        if (i == 0) {
+            if (top == h) {
+                return cover;
+            }
+            std::swap(result, cover);
+            continue;
+        }
+        result.insert(
+            result.end(),
+            std::make_move_iterator(cover.begin()),
+            std::make_move_iterator(cover.end()));
+    }
+    return result;
+}
+
 std::vector<UnwrappedTileID> tileCover(const Geometry<double>& geometry, int32_t z) {
     std::vector<UnwrappedTileID> result;
     TileCover tc(geometry, z, true);
diff --git a/src/mbgl/util/tile_cover.hpp b/src/mbgl/util/tile_cover.hpp
index c953d764d2..eb9e0bc325 100644
--- a/src/mbgl/util/tile_cover.hpp
+++ b/src/mbgl/util/tile_cover.hpp
@@ -34,6 +34,7 @@ private:
 int32_t coveringZoomLevel(double z, style::SourceType type, uint16_t tileSize);
 
 std::vector<UnwrappedTileID> tileCover(const TransformState&, int32_t z);
+std::vector<UnwrappedTileID> tileCoverWithLOD(const TransformState&, int32_t z, int32_t minZLOD);
 std::vector<UnwrappedTileID> tileCover(const LatLngBounds&, int32_t z);
 std::vector<UnwrappedTileID> tileCover(const Geometry<double>&, int32_t z);