Encoding features that can be “merged” from multiple tiles

[anandthakker]

This issue really encompasses a cluster of related problems:

Inter-tile feature identity: when a single logical feature exists in multiple tiles, there’s no guaranteed way to know that its instances in different tiles are all manifestations of the same feature. An identity relation would be useful for, e.g.:

• Feature interactivity in Mapbox GL: highlighting a feature in one tile should highlight parts of the same feature in other tiles (See https://github.com/mapbox/mapbox-gl-js/issues/6019)
• De-duplicating features for analysis (e.g., with tile-reduce or Turf)

Clipping detection: features that span multiple tiles are almost always clipped to each tile’s bounds (with some buffer). Clipping may introduce new points in linestring or polygon geometries (e.g., to close an otherwise open polygon ring). There is no way for a points that are clipping artifacts to be distinguished from those that come from the original geometry. As a result, Mapbox GL currently needs tiles with linestring or polygon to use a buffer so that it does not, for example, render polygon outlines or line caps at tile boundaries. (Related: https://github.com/mapbox/vector-tile-spec/issues/6)

Geometry reconstitution: Even when the inter-tile identity problem is not an issue (e.g., features have unique ids), recovering the original geometry—or reassembling the subset of it that exists in the tiles you have—is a challenge: at each place where a geometry has been ‘cut’ at a tile boundary, we need a way to associate the corresponding points or segments from each tile’s portion of the geometry. (See also https://github.com/mapbox/vector-tile-spec/issues/8) Support for this in the spec would be useful for, e.g.:

• Placing labels along a line
• Rendering things like gradients along a line (https://github.com/mapbox/mapbox-gl-js/pull/6303), or inner glow/tint bands (https://github.com/mapbox/mapbox-gl-js/pull/6303)

---

These problems also introduce new inter-tile consistency concerns that haven’t been an issue in previous versions of the spec.

• Will this necessitate some sort of id uniqueness across an entire tileset?
• If individual tiles in a tileset may change, how can clients determine when two tiles’ contents are consistent?

cc @ericfischer @flippmoke @jfirebaugh @kkaefer

[e-n-f]

The approach I have been working on in https://github.com/mapbox/tippecanoe/tree/reconstruct, is that each feature that is split across tiles is given a new 64-bit integer clipid message in the feature, which is unique within the tileset. (The clipid is assigned at the moment of first clipping, so it is not present in the low zooms, only in the first clipped zoom and beyond.)

Compositing of layers will need to be careful to make sure that the clipids are still unique.

Each clipped feature also has a geomids message, which is a list of ids for nodes within the geometry. It is a series of pairs: each is a skip and an id (so that space is not spent in the list on nodes that have no id). The geomids for nodes will be assigned to points on the tile boundary at the moment of clipping. A geomid that appears in zoom level N will also appear at the same location in zoom levels N+1 and higher, but I don't know if this is important. The geomid is unique within the feature, not globally.

MultiPoints:

• Points in the buffer are simply clipped away
• Points directly on the tile boundary have a geomid so they can be deduplicated (since they are duplicated in both tiles that share the edge).
• This will need to be more complicated if the order of Points within the MultiPoint matters.

LineStrings:

• Each new node that is introduced on the tile boundary during clipping is given a geomid so it can be matched to the corresponding node in the adjacent tile. Probably the "out" should be positive and the "in" should be negative so it can be sure to get the sequence right.
• If the LineString continues out into the buffer from this interpolated node, or has geometry in the buffer preceding the interpolated node, whatever happens out in the buffer is discarded.
• The nodes on each side of an edge that runs directly along a tile boundary will also have to be given geomids so they can be deduplicated. These should have a flag bit to indicate that they are legitimate nodes in the original feature, not nodes that have been interpolated just for clipping.
• This will need to be more complicated if the order of LineStrings within a MultiLineString matters.

Polygons:

• The easy way out is to do nothing with the geomids and to rely on client-side polygon unioning to fix up the geometry after merging. This is expensive though, and requires porting Wagyu to JavaScript.
• The right way is to do the same thing as with LineStrings and mark exits and entrances. The downside is that it will be hard to make sure that the geometries are clean in both the clipped and reconstructed polygons, especially when some but not all of the tiles have loaded. I think it will require keeping enough extra geometry out in the buffer to make sure that no rings are merged during clipping, so outer rings and holes in each tile are closed along stubs out of sight rather than being merged into a single concave outer ring.
• Wagyu already disregards the order of Polygons within the MultiPolygon, so there is even more work to do if we decide that that sequence should be preserved.

Other uncertainties:

• Should the clipid be assigned earlier in the process, so it appears even in the low zooms where it is not needed?
• Should features be given a bounding box and/or a per-zoom tile count so clients can know whether or not the entire feature has been loaded?

[anandthakker]

Capturing some notes from last week's conversation w/ @jfirebaugh @ericfischer @flippmoke :

• We probably will not expect clients to perform polygon unioning.
• If the order of parts within multi* geometry matters we could include in each clipped feature a total part count and the index of the first part in the original geometry. However, this might be problematic wrt partial updates, depending the requirements.
• Backwards compatibility
  • If other changes in VT3 do not require making backwards-incompatible changes, we can encode clipid and geomid information in separate messages that can be ignored by existing clients. On the other hand, if we are going to make a breaking change anyway, then we might as well encode this information wherever we feel is semantically ideal in the schema.
  • While the ability to drop (or substantially reduce) buffers is an eventual benefit of this change, doing so would break existing clients: in Mapbox GL, circle layers, symbol placement(?), server-side rendering of a single tile all rely on buffers for correct rendering.
• Partial updates to a tileset: scoping specific requirements for this is an important open issue that will affect the implementation of mergeable geometry encoding. Does a tileset author making a partial update need to be able to:
  • invalidate a single feature independently of others? invalidate all tiles containing a given feature?
  • express some kind of semantic versioning, distinguishing between 'patching' a feature fragment versus a more significant change?
  • insert parts within a multi* geometry, affecting the order of the parts?

[anandthakker]

I wanted to explore what it could look like to encode mergability data without using a clipid that's unique within the tileset.

For single-part geometries, this is pretty straightforward: geomids as described by @ericfischer above would suffice, with the caveat that if a client had only two non-adjacent tiles containing fragments of a single original feature, it wouldn't be able to relate them.

For multi* geometries, the problem is that if you have, e.g., two subgeometries where each is wholly in its own tile, there would be no geomid indicating their relationship.

@kkaefer previously proposed a slightly different scheme that could address this. Summarizing his idea as I understand it:

• When "clipping" a segment that crosses a tile boundary, instead of introducing an interpolated point at the clip boundary, store the point that lies beyond the boundary (in the 'buffer').
• Do this not only for LineTo, but also for MoveTo commands.
• Thus, any LineTo/MoveTo that crosses a tile boundary is duplicated (modulo translated coordinates) in both tiles sharing that boundary. Add a "continuity ID", unique within the feature, to any such LineTo/MoveTo command.

@kkaefer's example:

This consists of two features, one MultiLineString that has three LineStrings, only one of which is crossing a tile boundary, and one LineString that has points on the tile boundary.

The upper feature would be encoded as:

Left tile	Right tile
MoveTo 132/66 LineTo 239/107 LineTo 150/147 ContinuityID 0 MoveTo 299/134 (outside the tile extent) MoveTo 341/31 (outside the tile extent) ContinuityID 0 MoveTo 220/46 LineTo 151/17 ContinuityID 0 LineTo 288/9 (outside the tile extent)	MoveTo -106/147 (outside the tile extent) ContinuityID 0 MoveTo 43/124 LineTo 85/31 ContinuityID 0 MoveTo -36/45 (outside the tile extent) MoveTo -105/17 (outside the tile extent) ContinuityID 0 LineTo 32/9

The lower feature would be encoded as:

Left tile	Right tile
MoveTo 256/161 (outside the tile extent) ContinuityID 0 LineTo 159/199 LineTo 188/234 ContinuityID 0 LineTo 331/243 (outside the tile extent)	MoveTo 0/161 ContinuityID 0 LineTo -97/199 (outside the tile extent) MoveTo -68/234 (outside the tile extent) ContinuityID 0 LineTo 75/243 LineTo 0/206

_(Note: in this example, it appears that continuity ids are actually only unique with respect to a given MoveTo or LineTo segment, not within a feature. That might be all that's strictly necessary, but I could see it being simpler to have them be unique to the feature)_

[e-n-f]

OK, I can see the advantage of an ID that is only locally unique, especially in the case where just one tile from a larger area is being regenerated, since the necessary knowledge is then confined to just the adjacent tiles. Tagging the movetos also solves the MultiLineString sequence problem that I had been worrying about.

The disadvantage I see is that you have to look through the geometry of the features in the adjacent tile to find the feature that continues the one you are looking at instead of being able to look it up by ID.

I would still prefer that ID to be associated with a phantom point on the tile boundary than with the segment, because if the entire segment is preserved with its original coordinates, the buffer for that segment will be extremely large in some cases (imagine a LineString that jumps straight from one continent to another). I am OK with coordinates of that magnitude, but GL has overflow problems once you even get to 32768 tile units from the origin, so the tiles cease to render compatibly by existing clients. (And if you do clip closer in, for compatibility, you also need to add a point on the boundary to avoid visible discontinuity due to rounding error.)

I think phantom points will also generalize better to polygons, where the portion of the geometry in the buffer will have to be more schematic than the original if it is to preserve topology without preserving the entire original shape.

[anandthakker]

Yeah, @ericfischer I was just realizing the overflow issue and sketching out the same conclusion: we can still tag MoveTos and also clip them using interpolated points just as we do for LineTos.

I'm not actually sure whether I think local id's are preferable -- just wanted to put it on the table for consideration.

[e-n-f]

The only disadvantage I see to tagging the movetos is that in the case of the intercontinental MultiLineString (or the MultiPolygon of Alaska), we will end up with a long string of tiles that contain nothing but two movetos. But it's probably necessary as the way to know whether you have loaded the entire feature.

[anandthakker]

Last week, @jfirebaugh and I started thinking through the implications of "bufferless" rendering in GL. Summarizing our findings here.

Background: buffer-based rendering in GL

Currently, buffers are important for rendering in GL. We render each layer one tile at a time, with each tile responsible for the region within its boundaries. Preparing each tile for rendering must happen independently, without access to other tiles. Buffers are important because:

• Rendered geometry: A feature whose source geometry is located within tile A may be rendered partially in a neighboring tile B -- e.g., a line within A with a line-width that extends past the boundary into B. Thus, when we prepare tile B for rendering, we need access to this source geometry.
• Clipping detection: when a geometry crosses a tile boundary, it must be rendered differently than if it ended at the tile boundary. With geometries extending into the buffer, we can just process whatever geometry we have, and then mask away anything outside the tile's boundaries.

Bufferless rendering

In a "bufferless" rendering strategy, we'd alter how we divide responsibility between tiles: instead of each tile being responsible for the features that are rendered within its boundaries, each tile would be responsible for the features whose geometries are located within its boundaries. Clipping detection is straightforward, since we'll now have metadata distinguishing the "real" end of a geometry from a clipping artifact.

The difference between source & rendered geometry gives rise to more issues/constraints:

• Renderers will need to request more tiles, maintaining a 1-tile buffer around the viewport so that they can render geometries located outside the viewport but visible within it. This is probably(?) okay for GL JS and the native SDKs, but could be a significant problem for server-side rendering, where the "viewport" may be a single tile.
  • Unique ownership is important -- the VT3 spec should mandate that every point geometry and every vertex of a line/polygon geometry from the source data is uniquely owned by a single tile in the tileset.
  • Correct line rendering (or stroked polygon rendering) is quite complicated due to line joins near tile boundaries.
  • There are a lot of edge cases here. (See https://beta.observablehq.com/@jfirebaugh/line-clipping)
  • Our current best idea (h/t @ansis) is that the tile containing a given vertex is responsible for rendering the whole join for that vertex. If one of the vertex's segments is clipped at a tile boundary, doing this correctly will require at least some data about the rest of that segment.
  • Best case re: the amount of data we'll need in that case: when a segment S is clipped at a tile boundary, with e being the endpoint of S that falls on or outside the tile boundary, then the tile will need to include the following additional information:
  • If e is within B units of the boundary (B = ?): the location of e and, if it joins another segment T, the angle between S and T.
  • Otherwise: the location where s1 intersects the line B units outside of the tile boundary, and a flag indicating that this point was clipped at the buffer

Next steps:

• [ ] Develop a comprehensive set of test fixtures for line rendering edge cases (in progress)
• [ ] Prototype bufferless rendering approach based on the “best case” extra encoding info described above (in progress)
• [ ] Collect & prioritize research into possible approaches to mitigating server-side rendering risk

[mourner]

Renderers will need to request more tiles, maintaining a 1-tile buffer around the viewport so that they can render geometries located outside the viewport but visible within it.

@anandthakker do we really need a 1-tile buffer, or just a fixed pixel buffer around a viewport? The latter should cover the use case while loading only slightly more tiles — not nearly as many as a 1-tile buffer.

[anandthakker]

@mourner 1-tile buffer would be the worst case: if the viewport lines up with tile boundaries, for example, really would need the full 1-tile buffer. But it's true that in other cases, you might not need any/many additional tiles

[ansis]

@anandthakker thanks for the summary! I'm not sure if this ticket is the best place to ask, but what are the advantages of bufferless rendering? I can think of:

• not using the stencil buffer to clip to tile boundaries
• having slightly less data in line layers? (a 512 px tile with 25px buffers has 20% more data)

Another possible rendering issue to think about for bufferless rendering is the draw order of features within the same layer but in different tiles. Could a feature in tile A be rendered between two features in tile B? If yes, could this be specified by the data order somehow or would layers be considered unordered lists of features? How would the renderer actually render this with bufferless rendering?

These questions might be a bit off-topic for this issue. Is there a bufferless rendering issue open yet in any of the repos?

[anandthakker]

@ansis yeah, I think avoiding stencil clipping to tile boundaries and reducing tile size are the key benefits. I think in practice we see buffers quite a bit larger than 25px, so we could be avoiding quite a bit of duplicated data (and not just lines -- polygons too, and for that matter, dense point layers).

Good point about draw order -- we may need to require in the spec that the relative ordering of any pair of features is consistent in all the tiles in which they appear.

[ansis]

Good point about draw order -- we may need to require in the spec that the relative ordering of any pair of features is consistent in all the tiles in which they appear.

Without buffers it wouldn't be possible to determine the relative order of two features that are entirely in different tiles but have overlapping renderings. Actually rendering them in the right order would also be a challenge with bufferless. We'd probably need to merge the gl buffers across tiles instead of rendering each tile's batch separately.

Not supporting ordering might be a good choice

[jfirebaugh]

@ansis Can you post an example of the type of issue you're thinking of?

[anandthakker]

Ah. Yeah, this is tricky:

If the RH tile is drawn first, how would we avoid the blue line's join drawing above the portion of the red line that's in the LH tile?

[jfirebaugh]

The draw order is:

for (layer in layers)
  for (tile in tiles)
    draw(layer, tile)

So I don't think that particular scenario is an issue.

[anandthakker]

It is if those two features are in the same layer (colored w/ data-driven styling)

[ansis]

@anandthakker that's a worse one than I was thinking of!

@jfirebaugh it is an issue if the LH tile is drawn first in @anandthakker's example (assuming bottom up rendering. RH first for top-down opaque rendering)

---

My issue was one that already exists for our bufferless circle rendering and would exist for bufferless line rendering as well. We can't draw C above B above A currently.

We'd need to merge the data into one sorted buffer that can be drawn in one draw call. This could be a performance hit. It could be doable. With bufferless tiles we also lose the ability to specify the draw order using the data order but this could be ok.

[anandthakker]

Since geometry reconstruction is significantly more complicated than feature identity or marking clipping/buffer artifacts, here's a roundup of potential use cases for full geometry reconstruction.

🏗 = actually needs reconstruction ✂ = probably doable without doing reconstruction

• 🏗 queryRenderedFeatures: in Mapbox GL, users expect to be able to obtain a “whole” feature that’s been rendered from vector tiles (related: https://github.com/mapbox/mapbox-gl-js/issues/5639, though that ticket is technically about how GL handles GeoJSON, not VT)
• 🏗 Unity/3D - applying a texture to polygons that are clipped across tiles
  • Current approach relies on buffers + unique feature id for deduping
  • ^ relies on the assumption that the buffer contains the entirety of the geometry, which doesn’t hold up for e.g. large water layers
• ✂ Client-side analysis
  • All of the examples we’ve come up with for this seem to be possible—and, in fact, preferable—to do just with feature id & metadata for quickly identifying artifacts and redundant pieces of geometry (i.e. the portion in the buffer).
• ✂ Navigation: connecting routing data with features used for rendering
  • The key need here is to identify the VT feature(s) associated with a given “routing edge”. Actually reassembly isn’t needed.
• ❓Bufferless rendering
  • One approach to bufferless rendering would be to abandon tile-by-tile layout, but the loss of parallelization makes this seem pretty unlikely
• ❓Label placement
  • Reconstruction could be useful here, but like bufferless rendering, the loss of parallelization would probably make it unviable
• ✂ Rendering things like gradients along a line (mapbox/mapbox-gl-js#6303), or inner glow/tint bands (mapbox/mapbox-gl-js#6303)
  • We've got ideas for doing each of these that don't rely on reconstruction

I think the next questions here are:

1. Is anything missing? And then, once the answer to this is "no"...
2. ... do we feel that these use cases justify the complexity that geometry reassembly adds to the spec and its implementations?

[varna]

I'm using Google Maps JS with deck.gl MTSLayer to show MTS features on map. I don't have Mapbox GL (and queryRenderedFeatures installed). Trying to figure out a way to query an untiled Feature now.