Refactor tileCover to support lod tiles

10 files changed, 511 insertions, 44 deletions

diff --git a/src/mbgl/algorithm/update_renderables.hpp b/src/mbgl/algorithm/update_renderables.hpp
index 316ada8269..91eb058638 100644
--- a/src/mbgl/algorithm/update_renderables.hpp
+++ b/src/mbgl/algorithm/update_renderables.hpp
@@ -21,19 +21,18 @@ void updateRenderables(GetTileFn getTile,
                        RenderTileFn renderTile,
                        const IdealTileIDs& idealTileIDs,
                        const Range<uint8_t>& zoomRange,
-                       const uint8_t dataTileZoom,
                        const optional<uint8_t>& maxParentOverscaleFactor = nullopt) {
     std::unordered_set<OverscaledTileID> checked;
     bool covered;
     int32_t overscaledZ;
 
     // for (all in the set of ideal tiles of the source) {
-    for (const auto& idealRenderTileID : idealTileIDs) {
-        assert(idealRenderTileID.canonical.z >= zoomRange.min);
-        assert(idealRenderTileID.canonical.z <= zoomRange.max);
-        assert(dataTileZoom >= idealRenderTileID.canonical.z);
+    for (const auto& idealDataTileID : idealTileIDs) {
+        assert(idealDataTileID.canonical.z >= zoomRange.min);
+        assert(idealDataTileID.canonical.z <= zoomRange.max);
+        assert(idealDataTileID.overscaledZ >= idealDataTileID.canonical.z);
 
-        const OverscaledTileID idealDataTileID(dataTileZoom, idealRenderTileID.wrap, idealRenderTileID.canonical);
+        const UnwrappedTileID idealRenderTileID = idealDataTileID.toUnwrapped();
         auto tile = getTile(idealDataTileID);
         if (!tile) {
             tile = createTile(idealDataTileID);
@@ -56,7 +55,7 @@ void updateRenderables(GetTileFn getTile,
             // The tile isn't loaded yet, but retain it anyway because it's an ideal tile.
             retainTile(*tile, TileNecessity::Required);
             covered = true;
-            overscaledZ = dataTileZoom + 1;
+            overscaledZ = idealDataTileID.overscaledZ + 1;
             if (overscaledZ > zoomRange.max) {
                 // We're looking for an overzoomed child tile.
                 const auto childDataTileID = idealDataTileID.scaledTo(overscaledZ);
@@ -85,11 +84,12 @@ void updateRenderables(GetTileFn getTile,
 
             if (!covered) {
                 // We couldn't find child tiles that entirely cover the ideal tile.
-                for (overscaledZ = dataTileZoom - 1; overscaledZ >= zoomRange.min; --overscaledZ) {
+                for (overscaledZ = idealDataTileID.overscaledZ - 1; overscaledZ >= zoomRange.min; --overscaledZ) {
                     const auto parentDataTileID = idealDataTileID.scaledTo(overscaledZ);
 
                     // Request / render parent tile only if it's overscale factor is less than defined maximum.
-                    if (maxParentOverscaleFactor && (dataTileZoom - overscaledZ) > *maxParentOverscaleFactor) {
+                    if (maxParentOverscaleFactor &&
+                        (idealDataTileID.overscaledZ - overscaledZ) > *maxParentOverscaleFactor) {
                         break;
                     }
 
diff --git a/src/mbgl/map/transform_state.cpp b/src/mbgl/map/transform_state.cpp
index b5513f3d83..1894c59e2b 100644
--- a/src/mbgl/map/transform_state.cpp
+++ b/src/mbgl/map/transform_state.cpp
@@ -171,9 +171,12 @@ void TransformState::updateMatricesIfNeeded() const {
     getProjMatrix(projectionMatrix);
     coordMatrix = coordinatePointMatrix(projectionMatrix);
 
-    bool err = matrix::invert(invertedMatrix, coordMatrix);
+    bool err = matrix::invert(invProjectionMatrix, projectionMatrix);
+    if (err) throw std::runtime_error("failed to invert projectionMatrix");
 
+    err = matrix::invert(invertedMatrix, coordMatrix);
     if (err) throw std::runtime_error("failed to invert coordinatePointMatrix");
+
     requestMatricesUpdate = false;
 }
 
@@ -182,6 +185,11 @@ const mat4& TransformState::getProjectionMatrix() const {
     return projectionMatrix;
 }
 
+const mat4& TransformState::getInvProjectionMatrix() const {
+    updateMatricesIfNeeded();
+    return invProjectionMatrix;
+}
+
 const mat4& TransformState::getCoordMatrix() const {
     updateMatricesIfNeeded();
     return coordMatrix;
diff --git a/src/mbgl/map/transform_state.hpp b/src/mbgl/map/transform_state.hpp
index b7fa97eea6..69f0eebd40 100644
--- a/src/mbgl/map/transform_state.hpp
+++ b/src/mbgl/map/transform_state.hpp
@@ -216,6 +216,7 @@ public:
 
     void constrain(double& scale, double& x, double& y) const;
     const mat4& getProjectionMatrix() const;
+    const mat4& getInvProjectionMatrix() const;
 
 private:
     bool rotatedNorth() const;
@@ -282,6 +283,7 @@ private:
 
     mutable bool requestMatricesUpdate{true};
     mutable mat4 projectionMatrix;
+    mutable mat4 invProjectionMatrix;
     mutable mat4 coordMatrix;
     mutable mat4 invertedMatrix;
 };
diff --git a/src/mbgl/renderer/layers/render_background_layer.cpp b/src/mbgl/renderer/layers/render_background_layer.cpp
index 3e12b74db9..c791a394a1 100644
--- a/src/mbgl/renderer/layers/render_background_layer.cpp
+++ b/src/mbgl/renderer/layers/render_background_layer.cpp
@@ -116,14 +116,15 @@ void RenderBackgroundLayer::render(PaintParameters& parameters) {
 
         uint32_t i = 0;
         for (const auto& tileID : util::tileCover(parameters.state, parameters.state.getIntegerZoom())) {
+            const UnwrappedTileID unwrappedTileID = tileID.toUnwrapped();
             draw(parameters.programs.getBackgroundLayerPrograms().backgroundPattern,
-                 BackgroundPatternProgram::layoutUniformValues(parameters.matrixForTile(tileID),
+                 BackgroundPatternProgram::layoutUniformValues(parameters.matrixForTile(unwrappedTileID),
                                                                evaluated.get<BackgroundOpacity>(),
                                                                parameters.patternAtlas.getPixelSize(),
                                                                *imagePosA,
                                                                *imagePosB,
                                                                crossfade,
-                                                               tileID,
+                                                               unwrappedTileID,
                                                                parameters.state),
                  BackgroundPatternProgram::TextureBindings{
                      textures::image::Value{parameters.patternAtlas.textureBinding()},
@@ -141,7 +142,7 @@ void RenderBackgroundLayer::render(PaintParameters& parameters) {
         for (const auto& tileID : util::tileCover(parameters.state, parameters.state.getIntegerZoom())) {
             draw(parameters.programs.getBackgroundLayerPrograms().background,
                  BackgroundProgram::LayoutUniformValues{
-                     uniforms::matrix::Value(parameters.matrixForTile(tileID)),
+                     uniforms::matrix::Value(parameters.matrixForTile(tileID.toUnwrapped())),
                      uniforms::color::Value(evaluated.get<BackgroundColor>()),
                      uniforms::opacity::Value(evaluated.get<BackgroundOpacity>()),
                  },
diff --git a/src/mbgl/renderer/tile_pyramid.cpp b/src/mbgl/renderer/tile_pyramid.cpp
index c456bf6e24..57086cb915 100644
--- a/src/mbgl/renderer/tile_pyramid.cpp
+++ b/src/mbgl/renderer/tile_pyramid.cpp
@@ -91,8 +91,8 @@ void TilePyramid::update(const std::vector<Immutable<style::LayerProperties>>& l
     int32_t tileZoom = overscaledZoom;
     int32_t panZoom = zoomRange.max;
 
-    std::vector<UnwrappedTileID> idealTiles;
-    std::vector<UnwrappedTileID> panTiles;
+    std::vector<OverscaledTileID> idealTiles;
+    std::vector<OverscaledTileID> panTiles;
 
     if (overscaledZoom >= zoomRange.min) {
         int32_t idealZoom = std::min<int32_t>(zoomRange.max, overscaledZoom);
@@ -118,7 +118,7 @@ void TilePyramid::update(const std::vector<Immutable<style::LayerProperties>>& l
             }
         }
 
-        idealTiles = util::tileCover(parameters.transformState, idealZoom);
+        idealTiles = util::tileCover(parameters.transformState, idealZoom, tileZoom);
     }
 
     // Stores a list of all the tiles that we're definitely going to retain. There are two
@@ -185,18 +185,11 @@ void TilePyramid::update(const std::vector<Immutable<style::LayerProperties>>& l
             [](const UnwrappedTileID&, Tile&) {},
             panTiles,
             zoomRange,
-            panZoom,
             maxParentTileOverscaleFactor);
     }
 
-    algorithm::updateRenderables(getTileFn,
-                                 createTileFn,
-                                 retainTileFn,
-                                 renderTileFn,
-                                 idealTiles,
-                                 zoomRange,
-                                 tileZoom,
-                                 maxParentTileOverscaleFactor);
+    algorithm::updateRenderables(
+        getTileFn, createTileFn, retainTileFn, renderTileFn, idealTiles, zoomRange, maxParentTileOverscaleFactor);
 
     for (auto previouslyRenderedTile : previouslyRenderedTiles) {
         Tile& tile = previouslyRenderedTile.second;
diff --git a/src/mbgl/util/bounding_volumes.cpp b/src/mbgl/util/bounding_volumes.cpp
new file mode 100644
index 0000000000..8d34f9bd62
--- /dev/null
+++ b/src/mbgl/util/bounding_volumes.cpp
@@ -0,0 +1,283 @@
+#include <mbgl/util/bounding_volumes.hpp>
+
+#include <algorithm>
+#include <cassert>
+#include <cmath>
+
+namespace mbgl {
+namespace {
+
+vec3 toVec3(const vec4& v) {
+    return vec3{v[0], v[1], v[2]};
+}
+
+vec3 vec3Sub(const vec3& a, const vec3& b) {
+    return vec3{a[0] - b[0], a[1] - b[1], a[2] - b[2]};
+}
+
+vec3 vec3Scale(const vec3& a, double s) {
+    return vec3{a[0] * s, a[1] * s, a[2] * s};
+}
+
+vec3 vec3Cross(const vec3& a, const vec3& b) {
+    return vec3{a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0]};
+}
+
+double vec3Dot(const vec3& a, const vec3& b) {
+    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
+}
+
+double vec3LengthSq(const vec3& a) {
+    return vec3Dot(a, a);
+}
+
+double vec3Length(const vec3& a) {
+    return std::sqrt(vec3LengthSq(a));
+}
+
+vec3 vec3Normalize(const vec3& a) {
+    return vec3Scale(a, 1.0 / vec3Length(a));
+}
+
+double vec4Dot(const vec4& a, const vec4& b) {
+    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2] + a[3] * b[3];
+}
+
+template <size_t N>
+static Point<double> ProjectPointsToAxis(const std::array<vec3, N>& points, const vec3& origin, const vec3& axis) {
+    double min = std::numeric_limits<double>::max();
+    double max = -std::numeric_limits<double>::max();
+
+    for (const vec3& point : points) {
+        double projectedPoint = vec3Dot(vec3Sub(point, origin), axis);
+        min = std::min(projectedPoint, min);
+        max = std::max(projectedPoint, max);
+    }
+
+    return {min, max};
+}
+
+} // namespace
+
+namespace util {
+
+AABB::AABB() : min({0, 0, 0}), max({0, 0, 0}) {}
+
+AABB::AABB(const vec3& min_, const vec3& max_) : min(min_), max(max_) {}
+
+vec3 AABB::closestPoint(const vec3& point) const {
+    return {std::max(std::min(max[0], point[0]), min[0]),
+            std::max(std::min(max[1], point[1]), min[1]),
+            std::max(std::min(max[2], point[2]), min[2])};
+}
+
+vec3 AABB::distanceXYZ(const vec3& point) const {
+    vec3 vec = vec3Sub(closestPoint(point), point);
+
+    vec[0] = std::abs(vec[0]);
+    vec[1] = std::abs(vec[1]);
+    vec[2] = std::abs(vec[2]);
+
+    return vec;
+}
+
+AABB AABB::quadrant(int idx) const {
+    assert(idx >= 0 && idx < 4);
+    vec3 quadrantMin = min;
+    vec3 quadrantMax = max;
+    const double xCenter = 0.5 * (max[0] + min[0]);
+    const double yCenter = 0.5 * (max[1] + min[1]);
+
+    // This aabb is split into 4 quadrants. For each axis define in which side of the split "idx" is
+    // The result for indices 0, 1, 2, 3 is: { 0, 0 }, { 1, 0 }, { 0, 1 }, { 1, 1 }
+    const std::array<int, 4> xSplit = {0, 1, 0, 1};
+    const std::array<int, 4> ySplit = {0, 0, 1, 1};
+
+    quadrantMin[0] = xSplit[idx] ? xCenter : quadrantMin[0];
+    quadrantMax[0] = xSplit[idx] ? quadrantMax[0] : xCenter;
+
+    quadrantMin[1] = ySplit[idx] ? yCenter : quadrantMin[1];
+    quadrantMax[1] = ySplit[idx] ? quadrantMax[1] : yCenter;
+
+    return {quadrantMin, quadrantMax};
+}
+
+bool AABB::intersects(const AABB& aabb) const {
+    if (min[0] > aabb.max[0] || aabb.min[0] > max[0]) return false;
+    if (min[1] > aabb.max[1] || aabb.min[1] > max[1]) return false;
+    if (min[2] > aabb.max[2] || aabb.min[2] > max[2]) return false;
+    return true;
+}
+
+bool AABB::operator==(const AABB& aabb) const {
+    return min == aabb.min && max == aabb.max;
+}
+
+bool AABB::operator!=(const AABB& aabb) const {
+    return !(*this == aabb);
+}
+
+// Named index values for frustum::points array
+enum {
+    near_tl = 0,
+    near_tr = 1,
+    near_br = 2,
+    near_bl = 3,
+    far_tl = 4,
+    far_tr = 5,
+    far_br = 6,
+    far_bl = 7,
+};
+
+Frustum::Frustum(const std::array<vec3, 8>& points_, const std::array<vec4, 6>& planes_)
+    : points(points_), planes(planes_) {
+    const Point<double> xBounds = ProjectPointsToAxis(points, {0, 0, 0}, {1, 0, 0});
+    const Point<double> yBounds = ProjectPointsToAxis(points, {0, 0, 0}, {0, 1, 0});
+    const Point<double> zBounds = ProjectPointsToAxis(points, {0, 0, 0}, {0, 0, 1});
+
+    bounds = AABB({xBounds.x, yBounds.x, zBounds.x}, {xBounds.y, yBounds.y, zBounds.y});
+
+    // Precompute a set of separating axis candidates for precise intersection tests.
+    // Remaining axes not covered in basic intersection tests are: axis[] = (edges of aabb) x (edges of frustum)
+    std::array<vec3, 6> frustumEdges = {vec3Sub(points[near_br], points[near_bl]),
+                                        vec3Sub(points[near_tl], points[near_bl]),
+                                        vec3Sub(points[far_tl], points[near_tl]),
+                                        vec3Sub(points[far_tr], points[near_tr]),
+                                        vec3Sub(points[far_br], points[near_br]),
+                                        vec3Sub(points[far_bl], points[near_bl])};
+
+    for (size_t i = 0; i < frustumEdges.size(); i++) {
+        // Cross product [1, 0, 0] x [a, b, c] == [0, -c, b]
+        // Cross product [0, 1, 0] x [a, b, c] == [c, 0, -a]
+        const vec3 axis0 = {0.0, -frustumEdges[i][2], frustumEdges[i][1]};
+        const vec3 axis1 = {frustumEdges[i][2], 0.0, -frustumEdges[i][0]};
+
+        projections[i * 2] = {axis0, ProjectPointsToAxis(points, points[0], axis0)};
+        projections[i * 2 + 1] = {axis1, ProjectPointsToAxis(points, points[0], axis1)};
+    }
+}
+
+Frustum Frustum::fromInvProjMatrix(const mat4& invProj, double worldSize, double zoom, bool flippedY) {
+    // Define frustum corner points in normalized clip space
+    std::array<vec4, 8> cornerCoords = {vec4{-1.0, 1.0, -1.0, 1.0},
+                                        vec4{1.0, 1.0, -1.0, 1.0},
+                                        vec4{1.0, -1.0, -1.0, 1.0},
+                                        vec4{-1.0, -1.0, -1.0, 1.0},
+                                        vec4{-1.0, 1.0, 1.0, 1.0},
+                                        vec4{1.0, 1.0, 1.0, 1.0},
+                                        vec4{1.0, -1.0, 1.0, 1.0},
+                                        vec4{-1.0, -1.0, 1.0, 1.0}};
+
+    const double scale = std::pow(2.0, zoom);
+
+    // Transform points to tile space
+    for (auto& coord : cornerCoords) {
+        matrix::transformMat4(coord, coord, invProj);
+        for (auto& component : coord) component *= 1.0 / coord[3] / worldSize * scale;
+    }
+
+    std::array<vec3i, 6> frustumPlanePointIndices = {
+        vec3i{near_bl, near_br, far_br},  // bottom
+        vec3i{near_tl, near_bl, far_bl},  // left
+        vec3i{near_br, near_tr, far_tr},  // right
+        vec3i{near_tl, far_tl, far_tr},   // top
+        vec3i{near_tl, near_tr, near_br}, // near
+        vec3i{far_br, far_tr, far_tl}     // far
+    };
+
+    if (flippedY) {
+        std::for_each(frustumPlanePointIndices.begin(), frustumPlanePointIndices.end(), [](vec3i& tri) {
+            std::swap(tri[1], tri[2]);
+        });
+    }
+
+    std::array<vec4, 6> frustumPlanes;
+
+    for (std::size_t i = 0; i < frustumPlanePointIndices.size(); i++) {
+        const vec3i indices = frustumPlanePointIndices[i];
+
+        // Compute plane equation using 3 points on the plane
+        const vec3 p0 = toVec3(cornerCoords[indices[0]]);
+        const vec3 p1 = toVec3(cornerCoords[indices[1]]);
+        const vec3 p2 = toVec3(cornerCoords[indices[2]]);
+
+        const vec3 a = vec3Sub(p0, p1);
+        const vec3 b = vec3Sub(p2, p1);
+        const vec3 n = vec3Normalize(vec3Cross(a, b));
+
+        frustumPlanes[i] = {n[0], n[1], n[2], -vec3Dot(n, p1)};
+    }
+
+    std::array<vec3, 8> frustumPoints;
+
+    for (size_t i = 0; i < cornerCoords.size(); i++) frustumPoints[i] = toVec3(cornerCoords[i]);
+
+    return {frustumPoints, frustumPlanes};
+}
+
+IntersectionResult Frustum::intersects(const AABB& aabb) const {
+    // Execute separating axis test between two convex objects to find intersections
+    // Each frustum plane together with 3 major axes define the separating axes
+    // This implementation is conservative as it's not checking all possible axes.
+    // False positive rate is ~0.5% of all cases (see intersectsPrecise).
+    // Note: test only 4 points as both min and max points have zero elevation
+    assert(aabb.min[2] == 0.0 && aabb.max[2] == 0.0);
+
+    if (!bounds.intersects(aabb)) return IntersectionResult::Separate;
+
+    const std::array<vec4, 4> aabbPoints = {
+        vec4{aabb.min[0], aabb.min[1], 0.0, 1.0},
+        vec4{aabb.max[0], aabb.min[1], 0.0, 1.0},
+        vec4{aabb.max[0], aabb.max[1], 0.0, 1.0},
+        vec4{aabb.min[0], aabb.max[1], 0.0, 1.0},
+    };
+
+    bool fullyInside = true;
+
+    for (const vec4& plane : planes) {
+        size_t pointsInside = 0;
+
+        pointsInside += vec4Dot(plane, aabbPoints[0]) >= 0.0;
+        pointsInside += vec4Dot(plane, aabbPoints[1]) >= 0.0;
+        pointsInside += vec4Dot(plane, aabbPoints[2]) >= 0.0;
+        pointsInside += vec4Dot(plane, aabbPoints[3]) >= 0.0;
+
+        if (!pointsInside) {
+            // Separating axis found, no intersection
+            return IntersectionResult::Separate;
+        }
+
+        if (pointsInside != aabbPoints.size()) fullyInside = false;
+    }
+
+    return fullyInside ? IntersectionResult::Contains : IntersectionResult::Intersects;
+}
+
+IntersectionResult Frustum::intersectsPrecise(const AABB& aabb, bool edgeCasesOnly) const {
+    if (!edgeCasesOnly) {
+        IntersectionResult result = intersects(aabb);
+
+        if (result == IntersectionResult::Separate) return result;
+    }
+
+    const std::array<vec3, 4> aabbPoints = {vec3{aabb.min[0], aabb.min[1], 0.0},
+                                            vec3{aabb.max[0], aabb.min[1], 0.0},
+                                            vec3{aabb.max[0], aabb.max[1], 0.0},
+                                            vec3{aabb.min[0], aabb.max[1], 0.0}};
+
+    // For a precise SAT-test all edge cases needs to be covered
+    // Projections of the frustum on separating axis candidates have been precomputed already
+    for (const Projection& proj : projections) {
+        Point<double> projectedAabb = ProjectPointsToAxis(aabbPoints, points[0], proj.axis);
+        const Point<double>& projectedFrustum = proj.projection;
+
+        if (projectedFrustum.y < projectedAabb.x || projectedFrustum.x > projectedAabb.y) {
+            return IntersectionResult::Separate;
+        }
+    }
+
+    return IntersectionResult::Intersects;
+}
+
+} // namespace util
+} // namespace mbgl
\ No newline at end of file
diff --git a/src/mbgl/util/bounding_volumes.hpp b/src/mbgl/util/bounding_volumes.hpp
new file mode 100644
index 0000000000..bca183d842
--- /dev/null
+++ b/src/mbgl/util/bounding_volumes.hpp
@@ -0,0 +1,68 @@
+#pragma once
+
+#include <mbgl/util/geometry.hpp>
+#include <mbgl/util/mat3.hpp>
+#include <mbgl/util/mat4.hpp>
+
+namespace mbgl {
+namespace util {
+
+enum class IntersectionResult : int {
+    Separate,
+    Intersects,
+    Contains,
+};
+
+class AABB {
+public:
+    AABB();
+    AABB(const vec3& min_, const vec3& max_);
+
+    vec3 closestPoint(const vec3& point) const;
+
+    // Computes the shortest manhattan distance to the provided point
+    vec3 distanceXYZ(const vec3& point) const;
+
+    // Creates an aabb covering one quadrant of the aabb on XZ-plane.
+    AABB quadrant(int idx) const;
+
+    bool intersects(const AABB& aabb) const;
+
+    bool operator==(const AABB& aabb) const;
+    bool operator!=(const AABB& aabb) const;
+
+    vec3 min;
+    vec3 max;
+};
+
+class Frustum {
+public:
+    Frustum(const std::array<vec3, 8>& points_, const std::array<vec4, 6>& planes_);
+
+    static Frustum fromInvProjMatrix(const mat4& invProj, double worldSize, double zoom, bool flippedY = false);
+
+    // Performs conservative intersection test using separating axis theorem.
+    // Some accuracy is traded for better performance. False positive rate is < 1%
+    IntersectionResult intersects(const AABB& aabb) const;
+
+    // Performs precise intersection test using separating axis theorem.
+    // It is possible run only edge cases that were not covered in intersects()
+    IntersectionResult intersectsPrecise(const AABB& aabb, bool edgeCasesOnly = false) const;
+
+    const std::array<vec3, 8>& getPoints() const { return points; }
+    const std::array<vec4, 6>& getPlanes() const { return planes; }
+
+private:
+    struct Projection {
+        vec3 axis;
+        Point<double> projection;
+    };
+
+    AABB bounds;
+    std::array<vec3, 8> points;
+    std::array<vec4, 6> planes;
+    std::array<Projection, 12> projections;
+};
+
+} // namespace util
+} // namespace mbgl
\ No newline at end of file
diff --git a/src/mbgl/util/mat3.hpp b/src/mbgl/util/mat3.hpp
index c4203c940b..5069e02056 100644
--- a/src/mbgl/util/mat3.hpp
+++ b/src/mbgl/util/mat3.hpp
@@ -28,6 +28,7 @@ namespace mbgl {
 
 using vec3 = std::array<double, 3>;
 using vec3f = std::array<float, 3>;
+using vec3i = std::array<int, 3>;
 using mat3 = std::array<double, 9>;
 
 namespace matrix {
diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp
index cf774abf00..dffee9e841 100644
--- a/src/mbgl/util/tile_cover.cpp
+++ b/src/mbgl/util/tile_cover.cpp
@@ -1,10 +1,11 @@
-#include <mbgl/util/tile_cover.hpp>
+#include <mbgl/map/transform_state.hpp>
+#include <mbgl/math/log2.hpp>
+#include <mbgl/util/bounding_volumes.hpp>
 #include <mbgl/util/constants.hpp>
 #include <mbgl/util/interpolate.hpp>
-#include <mbgl/map/transform_state.hpp>
-#include <mbgl/util/tile_cover_impl.hpp>
 #include <mbgl/util/tile_coordinate.hpp>
-#include <mbgl/math/log2.hpp>
+#include <mbgl/util/tile_cover.hpp>
+#include <mbgl/util/tile_cover_impl.hpp>
 
 #include <functional>
 #include <list>
@@ -146,6 +147,128 @@ int32_t coveringZoomLevel(double zoom, style::SourceType type, uint16_t size) {
     }
 }
 
+std::vector<OverscaledTileID> tileCover(const TransformState& state, uint8_t z, const optional<uint8_t>& overscaledZ) {
+    struct Node {
+        AABB aabb;
+        uint8_t zoom;
+        uint32_t x, y;
+        int16_t wrap;
+        bool fullyVisible;
+    };
+
+    struct ResultTile {
+        OverscaledTileID id;
+        double sqrDist;
+    };
+
+    const double numTiles = std::pow(2.0, z);
+    const double worldSize = Projection::worldSize(state.getScale());
+    const uint8_t minZoom = state.getPitch() <= (60.0 / 180.0) * M_PI ? z : 0;
+    const uint8_t maxZoom = z;
+    const uint8_t overscaledZoom = overscaledZ.value_or(z);
+    const bool flippedY = state.getViewportMode() == ViewportMode::FlippedY;
+
+    auto centerPoint =
+        TileCoordinate::fromScreenCoordinate(state, z, {state.getSize().width / 2.0, state.getSize().height / 2.0}).p;
+
+    vec3 centerCoord = {centerPoint.x, centerPoint.y, 0.0};
+
+    const Frustum frustum = Frustum::fromInvProjMatrix(state.getInvProjectionMatrix(), worldSize, z, flippedY);
+
+    // There should always be a certain number of maximum zoom level tiles surrounding the center location
+    const double radiusOfMaxLvlLodInTiles = 3;
+
+    const auto newRootTile = [&](int16_t wrap) -> Node {
+        return {AABB({wrap * numTiles, 0.0, 0.0}, {(wrap + 1) * numTiles, numTiles, 0.0}),
+                uint8_t(0),
+                uint16_t(0),
+                uint16_t(0),
+                wrap,
+                false};
+    };
+
+    // Perform depth-first traversal on tile tree to find visible tiles
+    std::vector<Node> stack;
+    std::vector<ResultTile> result;
+    stack.reserve(128);
+
+    // World copies shall be rendered three times on both sides from closest to farthest
+    for (int i = 1; i <= 3; i++) {
+        stack.push_back(newRootTile(-i));
+        stack.push_back(newRootTile(i));
+    }
+
+    stack.push_back(newRootTile(0));
+
+    while (!stack.empty()) {
+        Node node = stack.back();
+        stack.pop_back();
+
+        // Use cached visibility information of ancestor nodes
+        if (!node.fullyVisible) {
+            const IntersectionResult intersection = frustum.intersects(node.aabb);
+
+            if (intersection == IntersectionResult::Separate) continue;
+
+            node.fullyVisible = intersection == IntersectionResult::Contains;
+        }
+
+        const vec3 distanceXyz = node.aabb.distanceXYZ(centerCoord);
+        const double* longestDim = std::max_element(distanceXyz.data(), distanceXyz.data() + distanceXyz.size());
+        assert(longestDim);
+
+        // We're using distance based heuristics to determine if a tile should be split into quadrants or not.
+        // radiusOfMaxLvlLodInTiles defines that there's always a certain number of maxLevel tiles next to the map
+        // center. Using the fact that a parent node in quadtree is twice the size of its children (per dimension) we
+        // can define distance thresholds for each relative level: f(k) = offset + 2 + 4 + 8 + 16 + ... + 2^k. This is
+        // the same as "offset+2^(k+1)-2"
+        const double distToSplit = radiusOfMaxLvlLodInTiles + (1 << (maxZoom - node.zoom)) - 2;
+
+        // Have we reached the target depth or is the tile too far away to be any split further?
+        if (node.zoom == maxZoom || (*longestDim > distToSplit && node.zoom >= minZoom)) {
+            // Perform precise intersection test between the frustum and aabb. This will cull < 1% false positives
+            // missed by the original test
+            if (node.fullyVisible || frustum.intersectsPrecise(node.aabb, true) != IntersectionResult::Separate) {
+                const OverscaledTileID id = {
+                    node.zoom == maxZoom ? overscaledZoom : node.zoom, node.wrap, node.zoom, node.x, node.y};
+                const double dx = node.wrap * numTiles + node.x + 0.5 - centerCoord[0];
+                const double dy = node.y + 0.5 - centerCoord[1];
+
+                result.push_back({id, dx * dx + dy * dy});
+            }
+            continue;
+        }
+
+        for (int i = 0; i < 4; i++) {
+            const uint32_t childX = (node.x << 1) + (i % 2);
+            const uint32_t childY = (node.y << 1) + (i >> 1);
+
+            // Create child node and push to the stack for traversal
+            Node child = node;
+
+            child.aabb = node.aabb.quadrant(i);
+            child.zoom = node.zoom + 1;
+            child.x = childX;
+            child.y = childY;
+
+            stack.push_back(child);
+        }
+    }
+
+    // Sort results by distance
+    std::sort(
+        result.begin(), result.end(), [](const ResultTile& a, const ResultTile& b) { return a.sqrDist < b.sqrDist; });
+
+    std::vector<OverscaledTileID> ids;
+    ids.reserve(result.size());
+
+    for (const auto& tile : result) {
+        ids.push_back(tile.id);
+    }
+
+    return ids;
+}
+
 std::vector<UnwrappedTileID> tileCover(const LatLngBounds& bounds_, uint8_t z) {
     if (bounds_.isEmpty() ||
         bounds_.south() >  util::LATITUDE_MAX ||
@@ -166,20 +289,6 @@ std::vector<UnwrappedTileID> tileCover(const LatLngBounds& bounds_, uint8_t z) {
         z);
 }
 
-std::vector<UnwrappedTileID> tileCover(const TransformState& state, uint8_t z) {
-    assert(state.valid());
-
-    const double w = state.getSize().width;
-    const double h = state.getSize().height;
-    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);
-}
-
 std::vector<UnwrappedTileID> tileCover(const Geometry<double>& geometry, uint8_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 5ac3537bf6..5e09d8a671 100644
--- a/src/mbgl/util/tile_cover.hpp
+++ b/src/mbgl/util/tile_cover.hpp
@@ -33,7 +33,9 @@ private:
 
 int32_t coveringZoomLevel(double z, style::SourceType type, uint16_t tileSize);
 
-std::vector<UnwrappedTileID> tileCover(const TransformState&, uint8_t z);
+std::vector<OverscaledTileID> tileCover(const TransformState&,
+                                        uint8_t z,
+                                        const optional<uint8_t>& overscaledZ = nullopt);
 std::vector<UnwrappedTileID> tileCover(const LatLngBounds&, uint8_t z);
 std::vector<UnwrappedTileID> tileCover(const Geometry<double>&, uint8_t z);