From 1c94e0e5e7ed83dc6517e5550233362ed09561ff Mon Sep 17 00:00:00 2001 From: Mikko Pulkki Date: Mon, 23 Mar 2020 18:21:13 +0200 Subject: Refactor tileCover to support lod tiles --- src/mbgl/util/tile_cover.cpp | 145 +++++++++++++++++++++++++++++++++++++------ 1 file changed, 127 insertions(+), 18 deletions(-) (limited to 'src/mbgl/util/tile_cover.cpp') 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 +#include +#include +#include #include #include -#include -#include #include -#include +#include +#include #include #include @@ -146,6 +147,128 @@ int32_t coveringZoomLevel(double zoom, style::SourceType type, uint16_t size) { } } +std::vector tileCover(const TransformState& state, uint8_t z, const optional& 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 stack; + std::vector 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 ids; + ids.reserve(result.size()); + + for (const auto& tile : result) { + ids.push_back(tile.id); + } + + return ids; +} + std::vector tileCover(const LatLngBounds& bounds_, uint8_t z) { if (bounds_.isEmpty() || bounds_.south() > util::LATITUDE_MAX || @@ -166,20 +289,6 @@ std::vector tileCover(const LatLngBounds& bounds_, uint8_t z) { z); } -std::vector 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 tileCover(const Geometry& geometry, uint8_t z) { std::vector result; TileCover tc(geometry, z, true); -- cgit v1.2.1