[core] Limit TileCoordinate-based coverage

4 files changed, 77 insertions, 17 deletions

diff --git a/src/mbgl/renderer/tile_pyramid.cpp b/src/mbgl/renderer/tile_pyramid.cpp
index fc70f7c8b3..2bf56b18a8 100644
--- a/src/mbgl/renderer/tile_pyramid.cpp
+++ b/src/mbgl/renderer/tile_pyramid.cpp
@@ -121,11 +121,12 @@ void TilePyramid::update(const std::vector<Immutable<style::Layer::Impl>>& layer
             }
 
             if (panZoom < idealZoom) {
-                panTiles = util::tileCover(parameters.transformState, panZoom);
+                panTiles = util::tileCover(parameters.transformState, panZoom, util::TileCoverMode::Full);
             }
         }
 
-        idealTiles = util::tileCover(parameters.transformState, idealZoom);
+        idealTiles = util::tileCover(parameters.transformState, idealZoom,
+                panTiles.empty() ? util::TileCoverMode::Full : util::TileCoverMode::Limited5x5);
     }
 
     // Stores a list of all the tiles that we're definitely going to retain. There are two
@@ -187,8 +188,8 @@ void TilePyramid::update(const std::vector<Immutable<style::Layer::Impl>>& layer
     renderTiles.clear();
 
     if (!panTiles.empty()) {
-        algorithm::updateRenderables(getTileFn, createTileFn, retainTileFn,
-                [](const UnwrappedTileID&, Tile&) {}, panTiles, zoomRange, panZoom);
+        algorithm::updateRenderables(getTileFn, createTileFn, retainTileFn, renderTileFn,
+                                     panTiles, zoomRange, panZoom);
     }
 
     algorithm::updateRenderables(getTileFn, createTileFn, retainTileFn, renderTileFn,
diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp
index 64d1fb374e..1392ecb2db 100644
--- a/src/mbgl/util/tile_cover.cpp
+++ b/src/mbgl/util/tile_cover.cpp
@@ -1,6 +1,8 @@
 #include <mbgl/util/tile_cover.hpp>
 #include <mbgl/util/constants.hpp>
 #include <mbgl/util/interpolate.hpp>
+#include <mbgl/util/math.hpp>
+#include <mbgl/map/mode.hpp>
 #include <mbgl/map/transform_state.hpp>
 #include <mbgl/util/tile_cover_impl.hpp>
 #include <mbgl/util/tile_coordinate.hpp>
@@ -78,13 +80,15 @@ namespace util {
 
 namespace {
 
-std::vector<UnwrappedTileID> tileCover(const Point<double>& tl,
-                                       const Point<double>& tr,
-                                       const Point<double>& br,
-                                       const Point<double>& bl,
+std::vector<UnwrappedTileID> tileCover(Point<double> tl,
+                                       Point<double> tr,
+                                       Point<double> br,
+                                       Point<double> bl,
                                        const Point<double>& c,
-                                       uint8_t z) {
-    const int32_t tiles = 1 << z;
+                                       uint8_t z,
+                                       TileCoverMode mode,
+                                       double bearing = 0) {
+    const int32_t maxTilesPerAxis = 1 << z;
 
     struct ID {
         int32_t x, y;
@@ -93,9 +97,38 @@ std::vector<UnwrappedTileID> tileCover(const Point<double>& tl,
 
     std::vector<ID> t;
 
+    // Rotate the center according to bearing.
+    const Point<double> rotatedCenter = util::rotate(c, bearing);
+
+    // Limits the tile coverage to an axis-aligned rectangle according to the
+    // given bearing.
+    auto limitTileCoordinate = [&](Point<double>& point) {
+        auto clampAxis = [](double a, double b) -> double {
+            const double min = a >= b ? b : b - 2.0;
+            const double max = a >= b ? b + 2.0 : b;
+            return util::clamp(a, min, max);
+        };
+
+        // Rotate the tile coordinate according to bearing.
+        Point<double> rotated = util::rotate(point, bearing);
+        rotated.x = clampAxis(rotated.x, rotatedCenter.x);
+        rotated.y = clampAxis(rotated.y, rotatedCenter.y);
+
+        // After clamping, rotate back to original value.
+        point = util::rotate(rotated, -bearing);
+    };
+
+    // Limit tile coverage in continuous mode.
+    if (mode == TileCoverMode::Limited5x5) {
+        limitTileCoordinate(tl);
+        limitTileCoordinate(tr);
+        limitTileCoordinate(br);
+        limitTileCoordinate(bl);
+    }
+
     auto scanLine = [&](int32_t x0, int32_t x1, int32_t y) {
         int32_t x;
-        if (y >= 0 && y <= tiles) {
+        if (y >= 0 && y <= maxTilesPerAxis) {
             for (x = x0; x < x1; ++x) {
                 const auto dx = x + 0.5 - c.x, dy = y + 0.5 - c.y;
                 t.emplace_back(ID{ x, y, dx * dx + dy * dy });
@@ -107,8 +140,8 @@ std::vector<UnwrappedTileID> tileCover(const Point<double>& tl,
     // \---+
     // | \ |
     // +---\.
-    scanTriangle(tl, tr, br, 0, tiles, scanLine);
-    scanTriangle(br, bl, tl, 0, tiles, scanLine);
+    scanTriangle(tl, tr, br, 0, maxTilesPerAxis, scanLine);
+    scanTriangle(br, bl, tl, 0, maxTilesPerAxis, scanLine);
 
     // Sort first by distance, then by x/y.
     std::sort(t.begin(), t.end(), [](const ID& a, const ID& b) {
@@ -155,21 +188,23 @@ std::vector<UnwrappedTileID> tileCover(const LatLngBounds& bounds_, uint8_t z) {
         Projection::project(bounds.southeast(), z),
         Projection::project(bounds.southwest(), z),
         Projection::project(bounds.center(), z),
-        z);
+        z, TileCoverMode::Full);
 }
 
-std::vector<UnwrappedTileID> tileCover(const TransformState& state, uint8_t z) {
+std::vector<UnwrappedTileID> tileCover(const TransformState& state, uint8_t z, TileCoverMode mode) {
     assert(state.valid());
 
     const double w = state.getSize().width;
     const double h = state.getSize().height;
+
+    // top-left, top-right, bottom-right, bottom-left, center
     return tileCover(
         TileCoordinate::fromScreenCoordinate(state, z, { 0,   0   }).p,
         TileCoordinate::fromScreenCoordinate(state, z, { w,   0   }).p,
         TileCoordinate::fromScreenCoordinate(state, z, { w,   h   }).p,
         TileCoordinate::fromScreenCoordinate(state, z, { 0,   h   }).p,
         TileCoordinate::fromScreenCoordinate(state, z, { w/2, h/2 }).p,
-        z);
+        z, mode, state.getAngle());
 }
 
 std::vector<UnwrappedTileID> tileCover(const Geometry<double>& geometry, uint8_t z) {
diff --git a/src/mbgl/util/tile_cover.hpp b/src/mbgl/util/tile_cover.hpp
index 552f252960..30254b6c92 100644
--- a/src/mbgl/util/tile_cover.hpp
+++ b/src/mbgl/util/tile_cover.hpp
@@ -31,9 +31,15 @@ private:
     std::unique_ptr<Impl> impl;
 };
 
+enum class TileCoverMode : uint32_t {
+    Full,       // Full tile coverage
+    Limited5x5, // Limited tile coverage to a viewport axis-aligned 5x5 matrix
+    // Pyramid  // TODO: Tile pyramid containing multiple tile zoom levels
+};
+
 uint8_t coveringZoomLevel(double z, style::SourceType type, uint16_t tileSize);
 
-std::vector<UnwrappedTileID> tileCover(const TransformState&, uint8_t z);
+std::vector<UnwrappedTileID> tileCover(const TransformState&, uint8_t z, TileCoverMode = TileCoverMode::Full);
 std::vector<UnwrappedTileID> tileCover(const LatLngBounds&, uint8_t z);
 std::vector<UnwrappedTileID> tileCover(const Geometry<double>&, uint8_t z);
 
diff --git a/test/util/tile_cover.test.cpp b/test/util/tile_cover.test.cpp
index 72d77450a4..2e27da9090 100644
--- a/test/util/tile_cover.test.cpp
+++ b/test/util/tile_cover.test.cpp
@@ -1,6 +1,8 @@
 #include <mbgl/util/tile_cover.hpp>
 #include <mbgl/util/geo.hpp>
 #include <mbgl/map/transform.hpp>
+#include <mbgl/util/tile_coordinate.hpp>
+#include <mbgl/util/math.hpp>
 
 #include <algorithm>
 #include <stdlib.h>     /* srand, rand */
@@ -43,6 +45,22 @@ TEST(TileCover, Pitch) {
         { 2, 1, 2 }, { 2, 1, 1 }, { 2, 2, 2 }, { 2, 2, 1 }, { 2, 3, 2 }
     }),
               util::tileCover(transform.getState(), 2));
+
+    // 2 tiles on the left, 1 center tiler, then 2 tiles on the right.
+    constexpr uint32_t maximumLimitedTiles = 5 * 5;
+
+    transform.resize({ 2048, 2048 });
+    transform.setAngle(-45.0 * M_PI / 180.0);
+
+    transform.setPitch(67.5 * M_PI / 180.0);
+    for (double zoom = 0.0; zoom < 16.0; zoom += 0.5) {
+        uint8_t integerZoom = std::floor(zoom);
+        transform.setZoom(zoom);
+        auto fullTiles = util::tileCover(transform.getState(), integerZoom, util::TileCoverMode::Full);
+        auto limitedTiles = util::tileCover(transform.getState(), integerZoom, util::TileCoverMode::Limited5x5);
+        EXPECT_GT(fullTiles.size(), limitedTiles.size());
+        EXPECT_GE(maximumLimitedTiles, limitedTiles.size());
+    }
 }
 
 TEST(TileCover, WorldZ1) {