[core] Support a range of zooms in TileRange. Accounts for TilePyramid requesting parent tiles of ideal zoom tiles.

3 files changed, 57 insertions, 23 deletions

diff --git a/src/mbgl/renderer/tile_pyramid.cpp b/src/mbgl/renderer/tile_pyramid.cpp
index c4372e7112..8f83a0f982 100644
--- a/src/mbgl/renderer/tile_pyramid.cpp
+++ b/src/mbgl/renderer/tile_pyramid.cpp
@@ -143,10 +143,13 @@ void TilePyramid::update(const std::vector<Immutable<style::Layer::Impl>>& layer
         auto it = tiles.find(tileID);
         return it == tiles.end() ? nullptr : it->second.get();
     };
-    
+
+    // The min and max zoom for TileRange are based on the updateRenderables algorithm.
+    // Tiles are created at the ideal tile zoom or at lower zoom levels. Child
+    // tiles are used from the cache, but not created.
     optional<util::TileRange> tileRange = {};
     if (bounds) {
-        tileRange = util::TileRange::fromLatLngBounds(*bounds, std::min(tileZoom, (int32_t)zoomRange.max));
+        tileRange = util::TileRange::fromLatLngBounds(*bounds, zoomRange.min, std::min(tileZoom, (int32_t)zoomRange.max));
     }
     auto createTileFn = [&](const OverscaledTileID& tileID) -> Tile* {
         if (tileRange && !tileRange->contains(tileID.canonical)) {
diff --git a/src/mbgl/util/tile_range.hpp b/src/mbgl/util/tile_range.hpp
index f630a49078..8554cfb65e 100644
--- a/src/mbgl/util/tile_range.hpp
+++ b/src/mbgl/util/tile_range.hpp
@@ -6,41 +6,61 @@
 #include <mbgl/util/projection.hpp>
 
 namespace mbgl {
-
 namespace util {
 
 class TileRange {
 public:
-    Range<Point<double>> range;
-    uint8_t z;
+    Range<Point<uint32_t>> range;
+    Range<uint8_t> zoomRange;
+
+    // Compute the range of tiles covered by the bounds at maxZoom.
+    static TileRange fromLatLngBounds(const LatLngBounds& bounds, uint8_t minZoom, uint8_t maxZoom) {
+        if (minZoom > maxZoom) {
+            std::swap(minZoom, maxZoom);
+        }
+
+        auto swProj = Projection::project(bounds.southwest().wrapped(), maxZoom);
+        auto ne = bounds.northeast();
+        auto neProj = Projection::project(ne.longitude() > util::LONGITUDE_MAX ? ne.wrapped() : ne , maxZoom);
+
+        const auto maxTile = std::pow(2.0, maxZoom);
+        const auto minX = static_cast<uint32_t>(std::floor(swProj.x));
+        const auto maxX = static_cast<uint32_t>(std::floor(neProj.x));
+        const auto minY = static_cast<uint32_t>(util::clamp(std::floor(neProj.y), 0.0 , maxTile));
+        const auto maxY = static_cast<uint32_t>(util::clamp(std::floor(swProj.y), 0.0, maxTile));
+
+        return TileRange({ {minX, minY}, {maxX, maxY} }, {minZoom, maxZoom});
+    }
 
     // Compute the range of tiles covered by the bounds.
     static TileRange fromLatLngBounds(const LatLngBounds& bounds, uint8_t z) {
-        auto swProj = Projection::project(bounds.southwest().wrapped(), z);
-        auto ne = bounds.northeast();
-        auto neProj = Projection::project(ne.longitude() > util::LONGITUDE_MAX ? ne.wrapped() : ne , z);
-        const auto minX = std::floor(swProj.x);
-        const auto maxX = std::ceil(neProj.x);
-        const auto minY = std::floor(neProj.y);
-        const auto maxY = std::ceil(swProj.y);
-        return TileRange({ {minX, minY}, {maxX, maxY} }, z);
+        return fromLatLngBounds(bounds, z, z);
     }
 
     bool contains(const CanonicalTileID& tileID) {
-        return z == tileID.z &&
-        (range.min.x >= range.max.x ? //For wrapped bounds
-            tileID.x >= range.min.x || tileID.x < range.max.x :
-            tileID.x < range.max.x && tileID.x >= range.min.x) &&
-        tileID.y < range.max.y &&
-        tileID.y >= range.min.y;
+        if (tileID.z <= zoomRange.max && tileID.z >= zoomRange.min) {
+            if (tileID.z == 0) {
+                return true;
+            }
+            uint8_t dz = (zoomRange.max - tileID.z);
+            auto x0 = range.min.x >> dz;
+            auto x1 = range.max.x >> dz;
+            auto y0 = range.min.y >> dz;
+            auto y1 = range.max.y >> dz;
+            return (range.min.x > range.max.x ? //For wrapped bounds
+                    tileID.x >= x0 || tileID.x <= x1 :
+                    tileID.x <= x1 && tileID.x >= x0) &&
+                tileID.y <= y1 &&
+                tileID.y >= y0;
+        }
+        return false;
     }
 
 private:
-    TileRange(Range<Point<double>> range_, uint8_t z_)
+    TileRange(Range<Point<uint32_t>> range_, Range<uint8_t> z_)
      : range(range_),
-     z(z_) {
+     zoomRange(z_) {
     }
-    
 };
 
 } // namespace util
diff --git a/test/util/tile_range.test.cpp b/test/util/tile_range.test.cpp
index dc8ae28705..c4c37c74d7 100644
--- a/test/util/tile_range.test.cpp
+++ b/test/util/tile_range.test.cpp
@@ -1,4 +1,3 @@
-
 #include <mbgl/util/tile_range.hpp>
 #include <mbgl/util/geo.hpp>
 #include <mbgl/map/transform.hpp>
@@ -25,6 +24,18 @@ TEST(TileRange, ContainsBoundsFromTile) {
         EXPECT_TRUE(range.contains(CanonicalTileID(10, 162, 395)));
     }
 }
+
+TEST(TileRange, ContainsMultiZoom) {
+    auto wrappedBounds = LatLngBounds::hull({ 37.6609, -122.5744 }, { 37.8271, -122.3204 });
+    auto range = util::TileRange::fromLatLngBounds(wrappedBounds, 5, 13);
+    EXPECT_FALSE(range.contains(CanonicalTileID(0, 0, 0)));
+    EXPECT_FALSE(range.contains(CanonicalTileID(5, 3, 11)));
+    EXPECT_FALSE(range.contains(CanonicalTileID(6, 9, 22)));
+    EXPECT_TRUE(range.contains(CanonicalTileID(5, 5, 12)));
+    EXPECT_TRUE(range.contains(CanonicalTileID(6, 10, 24)));
+    EXPECT_TRUE(range.contains(CanonicalTileID(13, 1310, 3166)));
+}
+
 TEST(TileRange, ContainsIntersectingTiles) {
     auto bounds = LatLngBounds::hull({ 37.6609, -122.5744 }, { 37.8271, -122.3204 });
     auto range = util::TileRange::fromLatLngBounds(bounds, 13);