From 15019425bef4d486d1de068be53649056375bc5e Mon Sep 17 00:00:00 2001 From: Asheem Mamoowala Date: Wed, 16 May 2018 17:18:17 -0700 Subject: Better describe the streaming tilecover algorithm in comments --- src/mbgl/util/tile_cover_impl.cpp | 63 +++++++++++++++++++++++++-------------- src/mbgl/util/tile_cover_impl.hpp | 16 ++++++++++ 2 files changed, 57 insertions(+), 22 deletions(-) diff --git a/src/mbgl/util/tile_cover_impl.cpp b/src/mbgl/util/tile_cover_impl.cpp index 2fac8b239d..f796cc7bd3 100644 --- a/src/mbgl/util/tile_cover_impl.cpp +++ b/src/mbgl/util/tile_cover_impl.cpp @@ -17,8 +17,7 @@ struct TileSpan { bool winding; }; - -// Find the first local minimum going forward in the list. +// Reorder a ring of points such that it starts at a point with a local minimum y-coordinate void start_list_on_local_minimum(PointList& points) { auto prev_pt = std::prev(points.end(), 2); auto pt = points.begin(); @@ -42,6 +41,8 @@ void start_list_on_local_minimum(PointList& points) { } //Create a bound towards a local maximum point, starting from pt. +// Traverse from current pt until the next pt changes y-direction, and copy +// all points from start to end (inclusive) into a Bound. Bound create_bound_towards_maximum(PointList& points, PointList::iterator& pt) { if (std::distance(pt, points.end()) < 2) { return {}; } @@ -50,7 +51,7 @@ Bound create_bound_towards_maximum(PointList& points, PointList::iterator& pt) { while (pt->y <= next_pt->y) { pt++; next_pt++; - if(next_pt == points.end()) { pt++; break; } + if (next_pt == points.end()) { pt++; break; } } const auto pt_distance = std::distance(begin, next_pt); @@ -66,6 +67,8 @@ Bound create_bound_towards_maximum(PointList& points, PointList::iterator& pt) { } //Create a bound towards a local minimum point, starting from pt. +// Traverse from current pt until the next pt changes y-direction, and copy +// all points from start to end (inclusive) into a Bound. Bound create_bound_towards_minimum(PointList& points, PointList::iterator& pt) { if (std::distance(pt, points.end()) < 2) { return {}; } @@ -74,7 +77,7 @@ Bound create_bound_towards_minimum(PointList& points, PointList::iterator& pt) { while (pt->y > next_pt->y) { pt++; next_pt++; - if(next_pt == points.end()) { pt++; break; } + if (next_pt == points.end()) { pt++; break; } } const auto pt_distance = std::distance(begin, next_pt); @@ -89,10 +92,14 @@ Bound create_bound_towards_minimum(PointList& points, PointList::iterator& pt) { return bnd; } -//Build a map of bounds and their starting Y tile coordinate. +// Given a set of points (ring or list) representing a shape, compute a set of +// Bounds, where each Bound represents edges going from a local minima to a local +// maxima point. The BoundsMap is an edge table indexed on the starting Y-tile +// of each Bound. void build_bounds_map(PointList& points, uint32_t maxTile, BoundsMap& et, bool closed = false) { if (points.size() < 2) return; - //While traversing closed rings, start the bounds at a local minimum + //While traversing closed rings, start the bounds at a local minimum. + // (For linestrings the starting point is always a local maxima/minima) if (closed) { start_list_on_local_minimum(points); } @@ -120,12 +127,16 @@ void update_span(TileSpan& xp, double x) { xp.xmax = std::max(xp.xmax, static_cast(std::ceil(x))); } -//Build a vector of X tile-coordinates spanned by each bound. -std::vector scan_row(uint32_t y, Bounds& aet) { +// Use the active bounds, an accumulation of all bounds that enter the y tile row, +// or start in that row. +// Iterate all points of a bound until it exits the row (or ends) and compute the +// set of X tiles it spans across. The winding direction of the bound is also +// captured for each span to later fill tiles between bounds for polygons +std::vector scan_row(uint32_t y, Bounds& activeBounds) { std::vector tile_range; - tile_range.reserve(aet.size()); + tile_range.reserve(activeBounds.size()); - for(Bound& b: aet) { + for(Bound& b: activeBounds) { TileSpan xp = { INT_MAX, 0, b.winding }; double x; const auto numEdges = b.points.size() - 1; @@ -140,7 +151,7 @@ std::vector scan_row(uint32_t y, Bounds& aet) { x = b.interpolate(y+1); update_span(xp, x); break; - } else if(b.currentPoint == numEdges - 1) { + } else if (b.currentPoint == numEdges - 1) { // For last edge, consider x-intercept at the end of the edge. x = p1.x; update_span(xp, x); @@ -151,11 +162,11 @@ std::vector scan_row(uint32_t y, Bounds& aet) { } // Erase bounds in the active table whose current edge ends inside this row, // or there are no more edges - auto bound = aet.begin(); - while (bound != aet.end()) { + auto bound = activeBounds.begin(); + while (bound != activeBounds.end()) { if ( bound->currentPoint == bound->points.size() - 1 && bound->points[bound->currentPoint].y <= y+1) { - bound = aet.erase(bound); + bound = activeBounds.erase(bound); } else { bound++; } @@ -195,7 +206,7 @@ struct BuildBoundsMap { BoundsMap operator()(const Point&p) const { Bound bnd; auto point = p; - if(project) { + if (project) { point = Projection::project(LatLng{p.y, p.x}, zoom); } bnd.points.insert(bnd.points.end(), 2, point); @@ -211,7 +222,7 @@ struct BuildBoundsMap { for (const Point& p: points) { Bound bnd; auto point = p; - if(project) { + if (project) { point = Projection::project(LatLng{p.y, p.x}, zoom); } bnd.points.insert(bnd.points.end(), 2, point); @@ -272,20 +283,26 @@ TileCover::Impl::Impl(int32_t z, const Geometry& geom, bool project) tileX = tileXSpans.front().first; } +// Aggregate all Bounds that start in or enter into the next tileY row. Multi-geoms +// may have discontinuity in the BoundMap, so skip forward to the next tileY row +// when the current/next row has no more bounds in it. +// Use scan_row to generate the tileX spans. Merge spans to avoid duplicate tiles +// in TileCoverImpl::next(). For closed geometry, use the non-zero rule to expand +// (fill) tiles between pairs of spans. void TileCover::Impl::nextRow() { - // Update AET for next row + // Update activeBounds for next row if (currentBounds != boundsMap.end()) { if (activeBounds.size() == 0 && currentBounds->first > tileY) { //For multi-geoms: use the next row with an edge table starting point tileY = currentBounds->first; } if (tileY == currentBounds->first) { - - std::move(currentBounds->second.begin(), currentBounds->second.end(), std::back_inserter(activeBounds)); + std::move(currentBounds->second.begin(), currentBounds->second.end(), + std::back_inserter(activeBounds)); currentBounds++; } } - //Scan aet and update currenRange with x_min, x_max pairs + //Scan the active bounds and update currentRange with x_min, x_max pairs auto xps = util::scan_row(tileY, activeBounds); if (xps.size() == 0) { return; @@ -309,7 +326,9 @@ void TileCover::Impl::nextRow() { } bool TileCover::Impl::hasNext() const { - return (!tileXSpans.empty() && tileX < tileXSpans.front().second && tileY < (1u << zoom)); + return (!tileXSpans.empty() + && tileX < tileXSpans.front().second + && tileY < (1u << zoom)); } optional TileCover::Impl::next() { @@ -320,7 +339,7 @@ optional TileCover::Impl::next() { tileX++; if (tileX >= tileXSpans.front().second) { tileXSpans.pop(); - if(tileXSpans.empty()) { + if (tileXSpans.empty()) { tileY++; nextRow(); } diff --git a/src/mbgl/util/tile_cover_impl.hpp b/src/mbgl/util/tile_cover_impl.hpp index 7c16718984..e9c06e44aa 100644 --- a/src/mbgl/util/tile_cover_impl.hpp +++ b/src/mbgl/util/tile_cover_impl.hpp @@ -60,6 +60,22 @@ struct Bound { } }; +// Implements a modified scan-line algorithm to provide a streaming interface for +// tile cover on arbitrary shapes. +// A `BoundsMap` is genereted from the input geometry where each tuple indicates +// the set of Bounds that start at a y tile coordinate. Each bound represents +// a chain of edges from a local y-minima to a local y-maxima. +// For each row, the activeBounds list aggregates all bounds that enter into or +// begin in that row. This running list of bounds is scanned, capturing the +// x-coordinates spanned by edges in a bound until the bound exits the row (or +// ends). The result is a set of (possibly overlapping) min,max pairs of x coordinates +// (spans). In the simplest case a span represents the x-coordinates at which a +// single edge intersects the top and bottom of a tile row. Interior tiles of a +// polygon are captured by merging spans using the non-zero rule. +// The result of a scan using `nextRow()` is a list of spans (tileXSpans) of x-coordinates +// that includes edges and interiors of polygons. +// next() returns a tileID for each x-coordinate from (first, second] in each +// span in tileXSpans. class TileCover::Impl { public: Impl(int32_t z, const Geometry& geom, bool project = true); -- cgit v1.2.1