diff options
| -rw-r--r-- | CMakeLists.txt | 2 | ||||
| -rw-r--r-- | src/mbgl/algorithm/update_renderables.hpp | 18 | ||||
| -rw-r--r-- | src/mbgl/map/transform_state.cpp | 10 | ||||
| -rw-r--r-- | src/mbgl/map/transform_state.hpp | 2 | ||||
| -rw-r--r-- | src/mbgl/renderer/layers/render_background_layer.cpp | 7 | ||||
| -rw-r--r-- | src/mbgl/renderer/tile_pyramid.cpp | 17 | ||||
| -rw-r--r-- | src/mbgl/util/bounding_volumes.cpp | 283 | ||||
| -rw-r--r-- | src/mbgl/util/bounding_volumes.hpp | 68 | ||||
| -rw-r--r-- | src/mbgl/util/mat3.hpp | 1 | ||||
| -rw-r--r-- | src/mbgl/util/tile_cover.cpp | 145 | ||||
| -rw-r--r-- | src/mbgl/util/tile_cover.hpp | 4 | ||||
| -rw-r--r-- | test/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | test/algorithm/update_renderables.test.cpp | 258 | ||||
| -rw-r--r-- | test/src/mbgl/test/mock.hpp | 2 | ||||
| -rw-r--r-- | test/util/bounding_volumes.test.cpp | 152 | ||||
| -rw-r--r-- | test/util/tile_cover.test.cpp | 169 |
16 files changed, 947 insertions, 192 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 4357493cef..bd9bc75798 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -732,6 +732,8 @@ add_library( ${PROJECT_SOURCE_DIR}/src/mbgl/tile/vector_tile.hpp ${PROJECT_SOURCE_DIR}/src/mbgl/tile/vector_tile_data.cpp ${PROJECT_SOURCE_DIR}/src/mbgl/tile/vector_tile_data.hpp + ${PROJECT_SOURCE_DIR}/src/mbgl/util/bounding_volumes.hpp + ${PROJECT_SOURCE_DIR}/src/mbgl/util/bounding_volumes.cpp ${PROJECT_SOURCE_DIR}/src/mbgl/util/chrono.cpp ${PROJECT_SOURCE_DIR}/src/mbgl/util/color.cpp ${PROJECT_SOURCE_DIR}/src/mbgl/util/constants.cpp 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); diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt index 2ed92eb987..35d8f2300f 100644 --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -81,6 +81,7 @@ add_library( ${PROJECT_SOURCE_DIR}/test/tile/tile_id.test.cpp ${PROJECT_SOURCE_DIR}/test/tile/vector_tile.test.cpp ${PROJECT_SOURCE_DIR}/test/util/async_task.test.cpp + ${PROJECT_SOURCE_DIR}/test/util/bounding_volumes.test.cpp ${PROJECT_SOURCE_DIR}/test/util/dtoa.test.cpp ${PROJECT_SOURCE_DIR}/test/util/geo.test.cpp ${PROJECT_SOURCE_DIR}/test/util/grid_index.test.cpp diff --git a/test/algorithm/update_renderables.test.cpp b/test/algorithm/update_renderables.test.cpp index 6958f21ea2..bca04ab661 100644 --- a/test/algorithm/update_renderables.test.cpp +++ b/test/algorithm/update_renderables.test.cpp @@ -122,14 +122,14 @@ TEST(UpdateRenderables, SingleTile) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 1, 1, 1 }); + source.idealTiles.emplace(OverscaledTileID{1, 1, 1}); // Make sure that we're getting the tile back. auto tile_1_1_1_1 = source.createTileData(OverscaledTileID{ 1, 1, 1 }); tile_1_1_1_1->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 1, 1 } }, Found }, // found ideal tile RetainTileDataAction{ { 1, 0, { 1, 1, 1 } }, TileNecessity::Required }, // @@ -139,8 +139,8 @@ TEST(UpdateRenderables, SingleTile) { // Check a repeated render with the same data. log.clear(); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 1, 1 } }, Found }, // found ideal tile RetainTileDataAction{ { 1, 0, { 1, 1, 1 } }, TileNecessity::Required }, // @@ -150,9 +150,9 @@ TEST(UpdateRenderables, SingleTile) { // Insert a tile we don't have data for. log.clear(); - source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 1 }); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + source.idealTiles.emplace(OverscaledTileID{1, 0, 1}); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 1 } }, NotFound }, // missing ideal tile CreateTileDataAction{ { 1, 0, { 1, 0, 1 } } }, // create ideal tile @@ -172,8 +172,8 @@ TEST(UpdateRenderables, SingleTile) { // Mark the created tile as having the optional request tried. log.clear(); source.dataTiles[{ 1, 0, { 1, 0, 1 } }]->triedOptional = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 1 } }, Found }, // missing ideal tile RetainTileDataAction{ { 1, 0, { 1, 0, 1 } }, TileNecessity::Required }, // @@ -195,8 +195,8 @@ TEST(UpdateRenderables, SingleTile) { log.clear(); auto tile_1_1_0_1 = source.createTileData(OverscaledTileID{ 1, 0, 1 }); tile_1_1_0_1->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 1 } }, Found }, // newly added tile RetainTileDataAction{ { 1, 0, { 1, 0, 1 } }, TileNecessity::Required }, // @@ -211,11 +211,11 @@ TEST(UpdateRenderables, SingleTile) { // Insert another tile, and another bucket that has a different name and check that we're not // using it. log.clear(); - source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{1, 0, 0}); auto tile_1_1_0_0 = source.createTileData(OverscaledTileID{ 1, 0, 0 }); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 0 } }, Found }, // found tile, not ready RetainTileDataAction{ { 1, 0, { 1, 0, 0 } }, TileNecessity::Required }, // @@ -240,8 +240,8 @@ TEST(UpdateRenderables, SingleTile) { // Then, add the bucket and check that it's getting used. log.clear(); tile_1_1_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 0 } }, Found }, // found tile, now ready RetainTileDataAction{ { 1, 0, { 1, 0, 0 } }, TileNecessity::Required }, // @@ -266,15 +266,15 @@ TEST(UpdateRenderables, UseParentTile) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 1 }); - source.idealTiles.emplace(UnwrappedTileID{ 1, 1, 0 }); - source.idealTiles.emplace(UnwrappedTileID{ 1, 1, 1 }); + source.idealTiles.emplace(OverscaledTileID{1, 0, 1}); + source.idealTiles.emplace(OverscaledTileID{1, 1, 0}); + source.idealTiles.emplace(OverscaledTileID{1, 1, 1}); // Make sure that we're getting the tile back. auto tile_0_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, 0 }); tile_0_0_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 1 } }, NotFound }, // missing ideal tile CreateTileDataAction{ { 1, 0, { 1, 0, 1 } } }, // @@ -312,12 +312,12 @@ TEST(UpdateRenderables, DontUseWrongParentTile) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 2, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{2, 0, 0}); auto tile_1_1_1_0 = source.createTileData(OverscaledTileID{ 1, 1, 0 }); tile_1_1_1_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 2); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 2, 0, { 2, 0, 0 } }, NotFound }, // missing ideal tile CreateTileDataAction{ { 2, 0, { 2, 0, 0 } } }, // @@ -334,8 +334,8 @@ TEST(UpdateRenderables, DontUseWrongParentTile) { // Now mark the created tile as having the optional request tried. log.clear(); source.dataTiles[{ 2, 0, { 2, 0, 0 } }]->triedOptional = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 2); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 2, 0, { 2, 0, 0 } }, Found }, // non-ready ideal tile RetainTileDataAction{ { 2, 0, { 2, 0, 0 } }, TileNecessity::Required }, // @@ -352,9 +352,9 @@ TEST(UpdateRenderables, DontUseWrongParentTile) { // Add a new child tile and check that it is now used. log.clear(); - source.idealTiles.emplace(UnwrappedTileID{ 2, 2, 0 }); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 2); + source.idealTiles.emplace(OverscaledTileID{2, 2, 0}); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 2, 0, { 2, 0, 0 } }, Found }, // non-ready ideal tile RetainTileDataAction{ { 2, 0, { 2, 0, 0 } }, TileNecessity::Required }, // @@ -389,7 +389,7 @@ TEST(UpdateRenderables, UseParentTileWhenChildNotReady) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 1 }); + source.idealTiles.emplace(OverscaledTileID{1, 0, 1}); auto tile_0_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, 0 }); tile_0_0_0_0->renderable = true; @@ -398,8 +398,8 @@ TEST(UpdateRenderables, UseParentTileWhenChildNotReady) { // Don't create bucket. // Make sure that it renders the parent tile. - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 1 } }, Found }, // found, but not ready RetainTileDataAction{ { 1, 0, { 1, 0, 1 } }, TileNecessity::Required }, // @@ -416,8 +416,8 @@ TEST(UpdateRenderables, UseParentTileWhenChildNotReady) { // Now insert the bucket and make sure we're now using the matching tile log.clear(); tile_1_1_0_1->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 1 } }, Found }, // found and ready RetainTileDataAction{ { 1, 0, { 1, 0, 1 } }, TileNecessity::Required }, // @@ -434,8 +434,8 @@ TEST(UpdateRenderables, UseOverlappingParentTile) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 0 }); - source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 1 }); + source.idealTiles.emplace(OverscaledTileID{1, 0, 0}); + source.idealTiles.emplace(OverscaledTileID{1, 0, 1}); auto tile_0_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, 0 }); tile_0_0_0_0->renderable = true; @@ -443,8 +443,8 @@ TEST(UpdateRenderables, UseOverlappingParentTile) { auto tile_1_1_0_1 = source.createTileData(OverscaledTileID{ 1, 0, 1 }); tile_1_1_0_1->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 0 } }, NotFound }, // ideal tile not found CreateTileDataAction{ { 1, 0, { 1, 0, 0 } } }, // @@ -472,15 +472,15 @@ TEST(UpdateRenderables, UseChildTiles) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 0, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{0, 0, 0}); auto tile_1_1_0_0 = source.createTileData(OverscaledTileID{ 1, 0, 0 }); tile_1_1_0_0->renderable = true; auto tile_1_1_1_0 = source.createTileData(OverscaledTileID{ 1, 1, 0 }); tile_1_1_1_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 0); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 0, 0, { 0, 0, 0 } }, NotFound }, // ideal tile, missing CreateTileDataAction{ { 0, 0, { 0, 0, 0 } } }, // @@ -506,15 +506,15 @@ TEST(UpdateRenderables, PreferChildTiles) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{1, 0, 0}); auto tile_0_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, 0 }); tile_0_0_0_0->renderable = true; auto tile_2_2_0_0 = source.createTileData(OverscaledTileID{ 2, 0, 0 }); tile_2_2_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 0 } }, NotFound }, // ideal tile, not found CreateTileDataAction{ { 1, 0, { 1, 0, 0 } } }, // @@ -536,8 +536,8 @@ TEST(UpdateRenderables, PreferChildTiles) { log.clear(); auto tile_2_2_0_1 = source.createTileData(OverscaledTileID{ 2, 0, 1 }); tile_2_2_0_1->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 0 } }, Found }, // ideal tile, not ready // ideal tile was added in previous invocation, but is not yet ready @@ -559,8 +559,8 @@ TEST(UpdateRenderables, PreferChildTiles) { log.clear(); auto tile_2_2_1_0 = source.createTileData(OverscaledTileID{ 2, 1, 0 }); tile_2_2_1_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 0 } }, Found }, // ideal tile, not ready // ideal tile was added in first invocation, but is not yet ready @@ -585,8 +585,8 @@ TEST(UpdateRenderables, PreferChildTiles) { log.clear(); auto tile_2_2_1_1 = source.createTileData(OverscaledTileID{ 2, 1, 1 }); tile_2_2_1_1->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 0 } }, Found }, // ideal tile, not ready // ideal tile was added in first invocation, but is not yet ready @@ -615,7 +615,7 @@ TEST(UpdateRenderables, UseParentAndChildTiles) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{1, 0, 0}); auto tile_0_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, 0 }); tile_0_0_0_0->renderable = true; @@ -623,8 +623,8 @@ TEST(UpdateRenderables, UseParentAndChildTiles) { tile_2_2_0_0->renderable = true; // Check that it uses the child tile and the parent tile to cover the rest. - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 0 } }, NotFound }, // ideal tile, missing CreateTileDataAction{ { 1, 0, { 1, 0, 0 } } }, // @@ -644,8 +644,8 @@ TEST(UpdateRenderables, UseParentAndChildTiles) { // Then, remove the child tile and check that it now only the parent tile. log.clear(); source.dataTiles.erase(OverscaledTileID{ 2, 0, 0 }); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, 0, { 1, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 1, 0, { 1, 0, 0 } }, TileNecessity::Required }, // @@ -669,13 +669,13 @@ TEST(UpdateRenderables, DontUseTilesLowerThanMinzoom) { auto renderTile = renderTileFn(log); source.zoomRange.min = 2; - source.idealTiles.emplace(UnwrappedTileID{ 2, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{2, 0, 0}); auto tile_1_1_0_0 = source.createTileData(OverscaledTileID{ 1, 0, 0 }); tile_1_1_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 2); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 2, 0, { 2, 0, 0 } }, NotFound }, // ideal tile, missing CreateTileDataAction{ { 2, 0, { 2, 0, 0 } } }, // @@ -698,13 +698,13 @@ TEST(UpdateRenderables, UseOverzoomedTileAfterMaxzoom) { auto renderTile = renderTileFn(log); source.zoomRange.max = 2; - source.idealTiles.emplace(UnwrappedTileID{ 2, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{2, 0, 0}); // Add a child tile (that should never occur in practice) and make sure it's not selected. auto tile_3_3_0_0 = source.createTileData(OverscaledTileID{ 3, 0, 0 }); tile_3_3_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 2); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ( ActionLog({ GetTileDataAction{ { 2, 0, { 2, 0, 0 } }, NotFound }, // ideal tile, missing @@ -719,8 +719,8 @@ TEST(UpdateRenderables, UseOverzoomedTileAfterMaxzoom) { // Mark the created tile as having tried the optional request. log.clear(); source.dataTiles[{ 2, 0, { 2, 0, 0 } }]->triedOptional = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 2); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ( ActionLog({ GetTileDataAction{ { 2, 0, { 2, 0, 0 } }, Found }, // ideal tile, missing @@ -733,12 +733,14 @@ TEST(UpdateRenderables, UseOverzoomedTileAfterMaxzoom) { }), log); - // Only add a non-overzoomed ("parent") tile at first. + // Switch to overzoomed tile and only add a non-overzoomed ("parent") tile at first. log.clear(); + source.idealTiles.clear(); + source.idealTiles.emplace(OverscaledTileID{3, 0, {2, 0, 0}}); auto tile_2_2_0_0 = source.createTileData(OverscaledTileID{ 2, 0, { 2, 0, 0 } }); tile_2_2_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 3); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 3, 0, { 2, 0, 0 } }, NotFound }, // ideal tile, missing CreateTileDataAction{ { 3, 0, { 2, 0, 0 } } }, // @@ -754,8 +756,8 @@ TEST(UpdateRenderables, UseOverzoomedTileAfterMaxzoom) { log.clear(); auto tile_3_2_0_0 = source.createTileData(OverscaledTileID{ 3, 0, { 2, 0, 0 } }); tile_3_2_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 3); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 3, 0, { 2, 0, 0 } }, Found }, // RetainTileDataAction{ { 3, 0, { 2, 0, 0 } }, TileNecessity::Required }, // @@ -765,8 +767,10 @@ TEST(UpdateRenderables, UseOverzoomedTileAfterMaxzoom) { // Check that it's switching back to the tile that has the matching overzoom value. log.clear(); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 2); + source.idealTiles.clear(); + source.idealTiles.emplace(OverscaledTileID{2, 0, 0}); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 2, 0, { 2, 0, 0 } }, Found }, // RetainTileDataAction{ { 2, 0, { 2, 0, 0 } }, TileNecessity::Required }, // @@ -780,8 +784,8 @@ TEST(UpdateRenderables, UseOverzoomedTileAfterMaxzoom) { tile_2_2_0_0 = nullptr; // Use the overzoomed tile even though it doesn't match the zoom level. - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 2); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 2, 0, { 2, 0, 0 } }, NotFound }, // CreateTileDataAction{ { 2, 0, { 2, 0, 0 } } }, // @@ -802,13 +806,13 @@ TEST(UpdateRenderables, AscendToNonOverzoomedTiles) { auto renderTile = renderTileFn(log); source.zoomRange.max = 2; - source.idealTiles.emplace(UnwrappedTileID{ 2, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{3, 0, {2, 0, 0}}); // Add a matching overzoomed tile and make sure it gets selected. auto tile_3_2_0_0 = source.createTileData(OverscaledTileID{ 3, 0, { 2, 0, 0 } }); tile_3_2_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 3); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 3, 0, { 2, 0, 0 } }, Found }, // RetainTileDataAction{ { 3, 0, { 2, 0, 0 } }, TileNecessity::Required }, // @@ -822,8 +826,8 @@ TEST(UpdateRenderables, AscendToNonOverzoomedTiles) { tile_3_2_0_0 = nullptr; auto tile_2_2_0_0 = source.createTileData(OverscaledTileID{ 2, 0, { 2, 0, 0 } }); tile_2_2_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 3); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 3, 0, { 2, 0, 0 } }, NotFound }, // CreateTileDataAction{ { 3, 0, { 2, 0, 0 } } }, // @@ -841,8 +845,8 @@ TEST(UpdateRenderables, AscendToNonOverzoomedTiles) { tile_2_2_0_0 = nullptr; auto tile_1_1_0_0 = source.createTileData(OverscaledTileID{ 1, 0, { 1, 0, 0 } }); tile_1_1_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 3); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 3, 0, { 2, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 3, 0, { 2, 0, 0 } }, TileNecessity::Required }, // @@ -857,8 +861,8 @@ TEST(UpdateRenderables, AscendToNonOverzoomedTiles) { // Now, mark the created tile as found. log.clear(); source.dataTiles[{ 3, 0, { 2, 0, 0 } }]->triedOptional = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 3); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 3, 0, { 2, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 3, 0, { 2, 0, 0 } }, TileNecessity::Required }, // @@ -881,11 +885,11 @@ TEST(UpdateRenderables, DoNotAscendMultipleTimesIfNotFound) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 8, 0, 0 }); - source.idealTiles.emplace(UnwrappedTileID{ 8, 1, 0 }); + source.idealTiles.emplace(OverscaledTileID{8, 0, 0}); + source.idealTiles.emplace(OverscaledTileID{8, 1, 0}); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 8); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 8, 0, { 8, 0, 0 } }, NotFound }, // ideal tile CreateTileDataAction{ { 8, 0, { 8, 0, 0 } } }, // @@ -919,8 +923,8 @@ TEST(UpdateRenderables, DoNotAscendMultipleTimesIfNotFound) { auto tile_4_0_0_0 = source.createTileData(OverscaledTileID{ 4, 0, { 4, 0, 0 } }); tile_4_0_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 8); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 8, 0, { 8, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 8, 0, { 8, 0, 0 } }, TileNecessity::Required }, // @@ -954,13 +958,13 @@ TEST(UpdateRenderables, DontRetainUnusedNonIdealTiles) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 2, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{2, 0, 0}); source.createTileData(OverscaledTileID{ 1, 0, 0 }); source.createTileData(OverscaledTileID{ 2, 0, 0 }); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 2); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 2, 0, { 2, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 2, 0, { 2, 0, 0 } }, TileNecessity::Required }, // @@ -983,16 +987,22 @@ TEST(UpdateRenderables, WrappedTiles) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 1, -1, 0 }); // 'wrap' -> -1 - source.idealTiles.emplace(UnwrappedTileID{ 1, 0, 0 }); // 'wrap' -> 0 - source.idealTiles.emplace(UnwrappedTileID{ 1, 1, 0 }); // 'wrap' -> 0 - source.idealTiles.emplace(UnwrappedTileID{ 1, 2, 0 }); // 'wrap' -> 1 + UnwrappedTileID tileIds[] = { + {1, -1, 0}, // 'wrap' -> -1 + {1, 0, 0}, // 'wrap' -> 0 + {1, 1, 0}, // 'wrap' -> 0 + {1, 2, 0} // 'wrap' -> 1 + }; + + for (const auto& id : tileIds) { + source.idealTiles.emplace(OverscaledTileID{1, id.wrap, id.canonical}); + } auto tile_0_0_0_0 = source.createTileData(OverscaledTileID{ 0, 0, { 0, 0, 0 } }); tile_0_0_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 1); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 1, -1, { 1, 1, 0 } }, NotFound }, // ideal tile 1/-1/0 (wrapped to -1) CreateTileDataAction{ { 1, -1, { 1, 1, 0 } } }, // @@ -1043,10 +1053,10 @@ TEST(UpdateRenderables, RepeatedRenderWithMissingOptionals) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{ 6, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{6, 0, 0}); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 6); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 6, 0, { 6, 0, 0 } }, NotFound }, // ideal tile, not found CreateTileDataAction{ { 6, 0, { 6, 0, 0 } } }, // @@ -1066,8 +1076,8 @@ TEST(UpdateRenderables, RepeatedRenderWithMissingOptionals) { // Repeat. log.clear(); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 6); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 6, 0, { 6, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 6, 0, { 6, 0, 0 } }, TileNecessity::Required }, // @@ -1087,8 +1097,8 @@ TEST(UpdateRenderables, RepeatedRenderWithMissingOptionals) { // Mark next level has having tried optional. log.clear(); source.dataTiles[{ 6, 0, { 6, 0, 0 } }]->triedOptional = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 6); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 6, 0, { 6, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 6, 0, { 6, 0, 0 } }, TileNecessity::Required }, // @@ -1109,8 +1119,8 @@ TEST(UpdateRenderables, RepeatedRenderWithMissingOptionals) { // Repeat. log.clear(); - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 6); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 6, 0, { 6, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 6, 0, { 6, 0, 0 } }, TileNecessity::Required }, // @@ -1131,8 +1141,8 @@ TEST(UpdateRenderables, RepeatedRenderWithMissingOptionals) { // Mark next level has having tried optional. log.clear(); source.dataTiles[{ 5, 0, { 5, 0, 0 } }]->triedOptional = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 6); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 6, 0, { 6, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 6, 0, { 6, 0, 0 } }, TileNecessity::Required }, // @@ -1155,8 +1165,8 @@ TEST(UpdateRenderables, RepeatedRenderWithMissingOptionals) { // Mark next level has having tried optional. log.clear(); source.dataTiles[{ 4, 0, { 4, 0, 0 } }]->triedOptional = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 6); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 6, 0, { 6, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 6, 0, { 6, 0, 0 } }, TileNecessity::Required }, // @@ -1180,8 +1190,8 @@ TEST(UpdateRenderables, RepeatedRenderWithMissingOptionals) { // Mark next level has having tried optional. log.clear(); source.dataTiles[{ 3, 0, { 3, 0, 0 } }]->triedOptional = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 6); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 6, 0, { 6, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 6, 0, { 6, 0, 0 } }, TileNecessity::Required }, // @@ -1207,8 +1217,8 @@ TEST(UpdateRenderables, RepeatedRenderWithMissingOptionals) { log.clear(); auto tile_3_3_0_0 = source.dataTiles[{ 3, 0, { 3, 0, 0 } }].get(); tile_3_3_0_0->renderable = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 6); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 6, 0, { 6, 0, 0 } }, Found }, // ideal tile, not ready RetainTileDataAction{ { 6, 0, { 6, 0, 0 } }, TileNecessity::Required }, // @@ -1236,14 +1246,14 @@ TEST(UpdateRenderables, LoadRequiredIfIdealTileCantBeFound) { auto renderTile = renderTileFn(log); source.zoomRange.max = 6; - source.idealTiles.emplace(UnwrappedTileID{ 6, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{6, 0, 0}); auto tile_6_6_0_0 = source.createTileData(OverscaledTileID{ 6, 0, { 6, 0, 0 } }); tile_6_6_0_0->triedOptional = true; tile_6_6_0_0->loaded = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 6); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 6, 0, { 6, 0, 0 } }, Found }, // ideal tile, not found RetainTileDataAction{ { 6, 0, { 6, 0, 0 } }, TileNecessity::Required }, // @@ -1270,7 +1280,7 @@ TEST(UpdateRenderables, LoadOverscaledMaxZoomTile) { auto renderTile = renderTileFn(log); source.zoomRange.max = 2; - source.idealTiles.emplace(UnwrappedTileID{ 2, 0, 0 }); + source.idealTiles.emplace(OverscaledTileID{4, 0, {2, 0, 0}}); auto tile_4_2_0_0 = source.createTileData(OverscaledTileID{ 4, 0, { 2, 0, 0 } }); tile_4_2_0_0->renderable = false; @@ -1293,8 +1303,8 @@ TEST(UpdateRenderables, LoadOverscaledMaxZoomTile) { tile_1_1_0_0->triedOptional = true; tile_1_1_0_0->loaded = true; - algorithm::updateRenderables(getTileData, createTileData, retainTileData, renderTile, - source.idealTiles, source.zoomRange, 4); + algorithm::updateRenderables( + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange); EXPECT_EQ(ActionLog({ GetTileDataAction{ { 4, 0, { 2, 0, 0 } }, Found }, RetainTileDataAction{ { 4, 0, { 2, 0, 0 } }, TileNecessity::Required }, @@ -1318,15 +1328,15 @@ TEST(UpdateRenderables, MaxParentOverscaleFactor) { auto retainTileData = retainTileDataFn(log); auto renderTile = renderTileFn(log); - source.idealTiles.emplace(UnwrappedTileID{4, 0, 0}); - source.idealTiles.emplace(UnwrappedTileID{4, 1, 0}); + source.idealTiles.emplace(OverscaledTileID{4, 0, 0}); + source.idealTiles.emplace(OverscaledTileID{4, 1, 0}); auto tile_0_0_0_0 = source.createTileData(OverscaledTileID{0, 0, 0}); tile_0_0_0_0->renderable = true; // Set max parent overscale factor to 4, so that tile 0,0,0 would be rendered algorithm::updateRenderables( - getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange, 4, 4); + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange, 4); EXPECT_EQ(ActionLog({GetTileDataAction{{4, 0, {4, 0, 0}}, NotFound}, // ideal tile CreateTileDataAction{{4, 0, {4, 0, 0}}}, RetainTileDataAction{{4, 0, {4, 0, 0}}, TileNecessity::Required}, @@ -1354,7 +1364,7 @@ TEST(UpdateRenderables, MaxParentOverscaleFactor) { // Set max parent overscale factor to 3. // Parent tile 0,0,0 should not be requested / rendered. algorithm::updateRenderables( - getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange, 4, 3); + getTileData, createTileData, retainTileData, renderTile, source.idealTiles, source.zoomRange, 3); EXPECT_EQ(ActionLog({GetTileDataAction{{4, 0, {4, 0, 0}}, Found}, // ideal tile RetainTileDataAction{{4, 0, {4, 0, 0}}, TileNecessity::Required}, GetTileDataAction{{5, 0, {5, 0, 0}}, NotFound}, // child tiles diff --git a/test/src/mbgl/test/mock.hpp b/test/src/mbgl/test/mock.hpp index b8eb020105..c61cdf56f4 100644 --- a/test/src/mbgl/test/mock.hpp +++ b/test/src/mbgl/test/mock.hpp @@ -14,7 +14,7 @@ struct MockTileData; struct MockSource { mbgl::Range<uint8_t> zoomRange { 0, 16 }; std::map<mbgl::OverscaledTileID, std::unique_ptr<MockTileData>> dataTiles; - std::set<mbgl::UnwrappedTileID> idealTiles; + std::set<mbgl::OverscaledTileID> idealTiles; // Test API inline MockTileData* createTileData(const mbgl::OverscaledTileID& tileID); diff --git a/test/util/bounding_volumes.test.cpp b/test/util/bounding_volumes.test.cpp new file mode 100644 index 0000000000..c788c9919a --- /dev/null +++ b/test/util/bounding_volumes.test.cpp @@ -0,0 +1,152 @@ +#include <mbgl/util/bounding_volumes.hpp> + +#include <gtest/gtest.h> +#include <math.h> + +using namespace mbgl; + +TEST(BoundingVolumes, CreateAabb) { + util::AABB aabb({0, 0, 0}, {2, 4, 6}); + + EXPECT_EQ(aabb.min, (vec3{0, 0, 0})); + EXPECT_EQ(aabb.max, (vec3{2, 4, 6})); +} + +TEST(BoundingVolumes, AabbEquality) { + util::AABB aabb0({-4.23, 1.01, 2.0}, {-1.0, 1.02, 100.0}); + util::AABB aabb1({-4.23, 1.01, 2.0}, {-1.0, 1.02, 100.0}); + util::AABB aabb2({-4.23, 1.01, 2.0}, {-1.0, 1.03, 55.0}); + + EXPECT_EQ(aabb0, aabb1); + EXPECT_NE(aabb0, aabb2); +} + +TEST(BoundingVolumes, CreateAabbQuadrants) { + util::AABB aabb({0, 0, 0}, {2, 4, 16}); + + util::AABB quadrant0({0, 0, 0}, {1, 2, 16}); + util::AABB quadrant1({1, 0, 0}, {2, 2, 16}); + util::AABB quadrant2({0, 2, 0}, {1, 4, 16}); + util::AABB quadrant3({1, 2, 0}, {2, 4, 16}); + + EXPECT_EQ(aabb.quadrant(0), quadrant0); + EXPECT_EQ(aabb.quadrant(1), quadrant1); + EXPECT_EQ(aabb.quadrant(2), quadrant2); + EXPECT_EQ(aabb.quadrant(3), quadrant3); +} + +TEST(BoundingVolumes, AabbDistanceToPoint) { + util::AABB aabb({-1.0, -1.0, -1.0}, {1.0, 1.0, 1.0}); + + EXPECT_EQ(aabb.distanceXYZ({0.5, -0.5, 0.5}), (vec3{0, 0, 0})); + EXPECT_EQ(aabb.distanceXYZ({1, 1, 1}), (vec3{0, 0, 0})); + EXPECT_EQ(aabb.distanceXYZ({0, 10, 0}), (vec3{0, 9, 0})); + EXPECT_EQ(aabb.distanceXYZ({-2, -2, -4}), (vec3{1, 1, 3})); +} + +TEST(BoundingVolumes, AabbAabbIntersection) { + util::AABB aabb0({1, 0, 0}, {3, 2, 1}); + util::AABB aabb1({2.5, 1.5, -1}, {6.0, 2.5, 1}); + util::AABB aabb2({3.5, -2, -2}, {5.0, 1, -1.5}); + util::AABB aabb3({0.5, -1, -1}, {6.5, 3, 4}); + + EXPECT_EQ(aabb0.intersects(aabb1), true); + EXPECT_EQ(aabb0.intersects(aabb2), false); + EXPECT_EQ(aabb1.intersects(aabb2), false); + EXPECT_EQ(aabb3.intersects(aabb0), true); + EXPECT_EQ(aabb3.intersects(aabb1), true); + EXPECT_EQ(aabb3.intersects(aabb2), false); +} + +TEST(BoundingVolumes, CreateFrustumFromProjectionMatrix) { + mat4 projMatrix; + mat4 invProjMatrix; + matrix::perspective(projMatrix, M_PI_2, 1.0, 0.1, 100.0); + matrix::invert(invProjMatrix, projMatrix); + + const util::Frustum frustum = util::Frustum::fromInvProjMatrix(invProjMatrix, 1.0, 0.0, false); + + const std::array<vec3, 8> expectedPoints = {vec3{-0.1, 0.1, -0.1}, + vec3{0.1, 0.1, -0.1}, + vec3{0.1, -0.1, -0.1}, + vec3{-0.1, -0.1, -0.1}, + vec3{-100.0, 100.0, -100.0}, + vec3{100.0, 100.0, -100.0}, + vec3{100.0, -100.0, -100.0}, + vec3{-100.0, -100.0, -100.0}}; + + const std::array<vec4, 6> expectedPlanes = { + + vec4{0, -0.707, 0.707, 0}, + vec4{-0.707, 0, 0.707, 0}, + vec4{0.707, 0, 0.707, 0}, + vec4{0, 0.707, 0.707, 0}, + vec4{0, 0, 1.0, 0.1}, + vec4{0, 0, -1.0, -100.0}}; + + const auto roundPoint = [](vec3& v) { + for (auto& p : v) { + p = round(p * 10.0) / 10.0; + } + }; + + const auto roundPlane = [](vec4& v) { + for (auto& p : v) { + p = round(p * 1000.0) / 1000.0; + } + }; + + std::array<vec3, 8> actualPoints = frustum.getPoints(); + std::array<vec4, 6> actualPlanes = frustum.getPlanes(); + + std::for_each(actualPoints.begin(), actualPoints.end(), roundPoint); + std::for_each(actualPlanes.begin(), actualPlanes.end(), roundPlane); + + EXPECT_EQ(actualPoints, expectedPoints); + EXPECT_EQ(actualPlanes, expectedPlanes); +} + +static util::Frustum createTestFrustum( + double fovy, double aspectRatio, double zNear, double zFar, double elevation, double bearing) { + mat4 proj; + mat4 invProj; + + // Create a complete projection matrix for transforming from world space to clip space + matrix::perspective(proj, fovy, aspectRatio, zNear, zFar); + matrix::scale(proj, proj, 1, -1, 1); + matrix::translate(proj, proj, 0, 0, elevation); + matrix::rotate_z(proj, proj, bearing); + matrix::invert(invProj, proj); + + return util::Frustum::fromInvProjMatrix(invProj, 1.0, 0.0); +} + +TEST(BoundingVolumes, AabbFullyInsideFrustum) { + const util::Frustum frustum = createTestFrustum(M_PI_2, 1.0, 0.1, 100.0, -5.0, 0.0); + + const std::array<util::AABB, 3> aabbArray = { + util::AABB({-1, -1, 0}, {1, 1, 0}), util::AABB({-5, -5, 0}, {5, 5, 0}), util::AABB({-5, -5, 0}, {-4, -2, 0})}; + + EXPECT_EQ(frustum.intersects(aabbArray[0]), util::IntersectionResult::Contains); + EXPECT_EQ(frustum.intersects(aabbArray[1]), util::IntersectionResult::Contains); + EXPECT_EQ(frustum.intersects(aabbArray[2]), util::IntersectionResult::Contains); +} + +TEST(BoundingVolumes, AabbIntersectsFrustum) { + const util::Frustum frustum = createTestFrustum(M_PI_2, 1.0, 0.1, 100.0, -5.0, 0.0); + + const std::array<util::AABB, 2> aabbArray = {util::AABB({-6, -6, 0}, {6, 6, 0}), + util::AABB({-6, -6, 0}, {-5, -5, 0})}; + + EXPECT_EQ(frustum.intersects(aabbArray[0]), util::IntersectionResult::Intersects); + EXPECT_EQ(frustum.intersects(aabbArray[1]), util::IntersectionResult::Intersects); +} + +TEST(BoundingVolumes, AabbIntersectsFrustumEdgeCase) { + const util::Frustum frustum = createTestFrustum(M_PI_2, 1.0, 0.1, 100.0, -5.0, M_PI_4); + const util::AABB aabb({-10, 10, 0}, {10, 12, 0}); + + // Intersection test should report intersection even though shapes are separate + EXPECT_EQ(frustum.intersects(aabb), util::IntersectionResult::Intersects); + EXPECT_EQ(frustum.intersectsPrecise(aabb), util::IntersectionResult::Separate); +}
\ No newline at end of file diff --git a/test/util/tile_cover.test.cpp b/test/util/tile_cover.test.cpp index ba39bfa61b..2401608d45 100644 --- a/test/util/tile_cover.test.cpp +++ b/test/util/tile_cover.test.cpp @@ -37,9 +37,7 @@ TEST(TileCover, Pitch) { transform.jumpTo(CameraOptions().withCenter(LatLng { 0.1, -0.1, }).withZoom(2.0).withBearing(5.0).withPitch(40.0)); - EXPECT_EQ((std::vector<UnwrappedTileID>{ - { 2, 1, 1 }, { 2, 2, 1 }, { 2, 1, 2 }, { 2, 2, 2 } - }), + EXPECT_EQ((std::vector<OverscaledTileID>{{2, 1, 1}, {2, 2, 1}, {2, 1, 2}, {2, 2, 2}}), util::tileCover(transform.getState(), 2)); } @@ -51,25 +49,23 @@ TEST(TileCover, PitchIssue15442) { .withZoom(2.0551126748417214).withBearing(0.74963938256567264 * util::RAD2DEG) .withPitch(1.0471975511965976 * util::RAD2DEG)); - EXPECT_EQ((std::vector<UnwrappedTileID>{ - { 2, 3, 1 }, { 2, 2, 1 }, { 2, 3, 0 }, { 2, 2, 0 }, { 1, { 2, 0, 0 } }, { 1, { 2, 1, 0 } } - }), + EXPECT_EQ((std::vector<OverscaledTileID>{ + {2, 3, 1}, {2, 2, 1}, {2, 3, 0}, {2, 2, 0}, {2, 1, {2, 0, 0}}, {2, 1, {2, 1, 0}}}), util::tileCover(transform.getState(), 2)); } TEST(TileCover, PitchOverAllowedByContentInsets) { Transform transform; - transform.resize({ 512, 512 }); + transform.resize({512, 512}); transform.jumpTo(CameraOptions().withCenter(LatLng { 0.1, -0.1 }).withPadding(EdgeInsets { 376, 0, 0, 0 }) .withZoom(8.0).withBearing(45.0).withPitch(60.0)); // Top padding of 376 leads to capped pitch. See Transform::getMaxPitchForEdgeInsets. EXPECT_LE(transform.getPitch() + 0.001, util::DEG2RAD * 60); - EXPECT_EQ((std::vector<UnwrappedTileID>{ - { 3, 4, 3 }, { 3, 3, 3 }, { 3, 4, 4 }, { 3, 3, 4 }, { 3, 4, 2 }, { 3, 5, 3 }, { 3, 5, 2 } - }), - util::tileCover(transform.getState(), 3)); + EXPECT_EQ( + (std::vector<OverscaledTileID>{{3, 4, 3}, {3, 3, 3}, {3, 4, 4}, {3, 3, 4}, {3, 4, 2}, {3, 5, 3}, {3, 5, 2}}), + util::tileCover(transform.getState(), 3)); } TEST(TileCover, PitchWithLargerResultSet) { @@ -84,29 +80,156 @@ TEST(TileCover, PitchWithLargerResultSet) { auto cover = util::tileCover(transform.getState(), 5); // Returned vector has above 100 elements, we check first 16 as there is a // plan to return lower LOD for distant tiles. - EXPECT_EQ((std::vector<UnwrappedTileID> { - { 5, 15, 16 }, { 5, 15, 17 }, { 5, 14, 16 }, { 5, 14, 17 }, - { 5, 16, 16 }, { 5, 16, 17 }, { 5, 15, 15 }, { 5, 14, 15 }, - { 5, 15, 18 }, { 5, 14, 18 }, { 5, 16, 15 }, { 5, 13, 16 }, - { 5, 13, 17 }, { 5, 16, 18 }, { 5, 13, 18 }, { 5, 15, 19 } - }), (std::vector<UnwrappedTileID> { cover.begin(), cover.begin() + 16}) ); + EXPECT_EQ((std::vector<OverscaledTileID>{{5, 15, 16}, + {5, 15, 17}, + {5, 14, 16}, + {5, 14, 17}, + {5, 16, 16}, + {5, 16, 17}, + {5, 15, 15}, + {5, 14, 15}, + {5, 15, 18}, + {5, 14, 18}, + {5, 16, 15}, + {5, 13, 16}, + {5, 13, 17}, + {5, 16, 18}, + {5, 13, 18}, + {5, 15, 19}}), + (std::vector<OverscaledTileID>{cover.begin(), cover.begin() + 16})); } TEST(TileCover, WorldZ1) { EXPECT_EQ((std::vector<UnwrappedTileID>{ - { 1, 0, 0 }, { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 1 }, - }), + {1, 0, 0}, + {1, 0, 1}, + {1, 1, 0}, + {1, 1, 1}, + }), util::tileCover(LatLngBounds::world(), 1)); } TEST(TileCover, SingletonZ0) { - EXPECT_EQ((std::vector<UnwrappedTileID>{}), - util::tileCover(LatLngBounds::singleton({ 0, 0 }), 0)); + EXPECT_EQ((std::vector<UnwrappedTileID>{}), util::tileCover(LatLngBounds::singleton({0, 0}), 0)); } TEST(TileCover, SingletonZ1) { - EXPECT_EQ((std::vector<UnwrappedTileID>{}), - util::tileCover(LatLngBounds::singleton({ 0, 0 }), 1)); + EXPECT_EQ((std::vector<UnwrappedTileID>{}), util::tileCover(LatLngBounds::singleton({0, 0}), 1)); +} + +TEST(TileCover, CoordinatesAreUnwrapped) { + Transform transform; + transform.resize({512, 512}); + transform.jumpTo(CameraOptions() + .withCenter(LatLng{ + 0.1, + -180.1, + }) + .withZoom(1.0)); + + EXPECT_EQ( + (std::vector<OverscaledTileID>{{1, 0, {1, 1, 0}}, {1, 1, {1, 0, 0}}, {1, 0, {1, 1, 1}}, {1, 1, {1, 0, 1}}}), + util::tileCover(transform.getState(), 1)); +} + +TEST(TileCover, DifferentOverscaledZ) { + Transform transform; + transform.resize({512, 512}); + // slightly offset center so that tile order is better defined + + transform.jumpTo(CameraOptions() + .withCenter(LatLng{ + 0.1, + -0.1, + }) + .withZoom(2.0)); + + EXPECT_EQ( + (std::vector<OverscaledTileID>{{3, 0, {2, 1, 1}}, {3, 0, {2, 2, 1}}, {3, 0, {2, 1, 2}}, {3, 0, {2, 2, 2}}}), + util::tileCover(transform.getState(), 2, 3)); +} + +TEST(TileCover, DifferentOverscaledZWithPitch) { + Transform transform; + transform.resize({512, 512}); + transform.jumpTo(CameraOptions() + .withCenter(LatLng{ + 30.0, + -10.0, + }) + .withZoom(3.5) + .withPitch(60)); + + EXPECT_EQ((std::vector<OverscaledTileID>{{5, 0, {3, 3, 3}}, + {5, 0, {3, 4, 3}}, + {5, 0, {3, 3, 2}}, + {5, 0, {3, 4, 2}}, + {5, 0, {3, 3, 1}}, + {5, 0, {3, 4, 1}}, + {5, 0, {3, 2, 1}}}), + util::tileCover(transform.getState(), 3, 5)); +} + +TEST(TileCover, DifferentOverscaledZWrapped) { + Transform transform; + transform.resize({512, 512}); + transform.jumpTo(CameraOptions() + .withCenter(LatLng{ + 0.1, + -180.1, + }) + .withZoom(1.0)); + + EXPECT_EQ( + (std::vector<OverscaledTileID>{{2, 0, {1, 1, 0}}, {2, 1, {1, 0, 0}}, {2, 0, {1, 1, 1}}, {2, 1, {1, 0, 1}}}), + util::tileCover(transform.getState(), 1, 2)); +} + +TEST(TileCover, FlippedY) { + Transform transform; + transform.resize({512, 512}); + transform.setViewportMode(ViewportMode::FlippedY); + transform.jumpTo(CameraOptions() + .withCenter(LatLng{ + 0.2, + -0.1, + }) + .withZoom(1.0)); + + EXPECT_EQ((std::vector<OverscaledTileID>{{1, 0, 0}, {1, 1, 0}, {1, 0, 1}, {1, 1, 1}}), + util::tileCover(transform.getState(), 1)); +} + +TEST(TileCover, FlippedYPitch) { + Transform transform; + transform.resize({512, 512}); + transform.setViewportMode(ViewportMode::FlippedY); + transform.jumpTo(CameraOptions() + .withCenter(LatLng{ + 0.1, + -0.1, + }) + .withZoom(2.0) + .withBearing(5.0) + .withPitch(40.0)); + + EXPECT_EQ((std::vector<OverscaledTileID>{{2, 1, 1}, {2, 2, 1}, {2, 1, 2}, {2, 2, 2}}), + util::tileCover(transform.getState(), 2)); +} + +TEST(TileCover, FlippedYHelsinki) { + Transform transform; + transform.resize({512, 512}); + transform.setViewportMode(ViewportMode::FlippedY); + transform.jumpTo(CameraOptions() + .withCenter(LatLng{ + 60.167231, + 24.942063, + }) + .withZoom(11.447425)); + + EXPECT_EQ((std::vector<OverscaledTileID>{{11, 1165, 592}, {11, 1166, 592}, {11, 1165, 593}, {11, 1166, 593}}), + util::tileCover(transform.getState(), 11)); } TEST(TileCoverStream, Arctic) { |