Annotation symbols are overdrawn if located on tile edges

[brunoabinader]

Spin-off from the discussions around stencil clip usage from #3563.

Fixing the position of repeated features near tile edges caused a new issue to rise: opaque symbols are now overdrawn:

[brunoabinader]

As previously mentioned in #3563, fixing this issue requires either removing stencil clip usage for symbols (option 1), or enforcing stencil clip for all symbol buckets (option 2).

Option 1 is tricky because it contains some corner cases in which I have no proper fix in mind:

• Style property symbol-avoid-edges depends on stencil clip functionality
• Requires enforcing non-duplicated entries when updating tile layers, layout and querying features:

  • 1.1) When updating annotation tile layers, we check if each symbol intersects with them. We can enforce them to be unique by e.g. letting only the left-topmost tile to get the feature. That's not something trivally possible with regular symbol layers because we already receive them duplicated from the server:

    For example, if a tile has an extent of 4096, coordinate units within the tile refer to 1/4096th of its square dimensions. A coordinate of 0 is on the top or left edge of the tile, and a coordinate of 4096 is on the bottom or right edge. Coordinates from 1 through 4095 inclusive are fully within the extent of the tile,

  • 1.2) When inserting symbol geometries in layout step, we could filter symbol instances based on their ID. That involves forwarding the feature ID when populating the symbol instances container.

  • 1.3) When querying, we can filter out duplicated features based on their ID.

Option 2 involves enforcing stencil clip for all symbol buckets. I've already tried this and it produces erroneous rendering results such as the ones seen below (clipped symbols close to tile edges):

[brunoabinader]

/cc @jfirebaugh @kkaefer @ansis

[ansis]

As previously mentioned in #3563, fixing this issue requires either removing stencil clip usage for symbols (option 1), or enforcing stencil clip for all symbol buckets (option 2).

Why is this the case? I read through #3563 and I still don't understand why only these options exist

[brunoabinader]

Why is this the case? I read through #3563 and I still don't understand why only these options exist

@ansis though not specific to annotation symbols, this issue happens when both assertions below are true for symbol layers:

1. Stencil clip is disabled (draw across tile edges); and
2. Symbol feature is located on tile edge i.e.:
   • anchorPoint.x == 0 || anchorPoint.x == util::EXTENT or
   • anchorPoint.y == 0 || anchorPoint.y == util::EXTENT

My understanding is that the overdraw happens because we consider a feature to be inside when its anchor point is located within the 0...extent inclusive range when populating symbol instances - used for calculating collision and generating symbol buckets in SymbolLayout::place.
Because features are repeated among neighbor tiles when they are located on tile edges, this makes each symbol bucket render its own repeated version of the same feature, and because we are not clipping, overdraw happens.

I've added a render test example here: symbol-opacity-edge/default

In the render test above, I've added a source containing two GeoJSON points: one at [ 0, 0 ] and the other at [ 1.1, 0.1 ]. That source is used on a symbol layer in which stencil clip is disabled (we don't set any of the layout properties that enables stencil clip for symbols). In this layer, icon-opacity is set to 0.25.

Expected	Actual

The actual result above is from GL JS. In GL native, we obtain the same results when we fix/remove the hacks that disables symbol stencil clip here, here and here. I have a proof-of-concept patch for GL native that re-enables symbol stencil clip for GL native: 782a477.

[jfirebaugh]

Here's my understanding of the situation, and points where I have gaps in my understanding.

• Currently, in Continuous mode, we endeavor to draw symbol layers with the stencil test disabled, i.e. the symbol bucket is not clipped to its tile.
• It has been asserted that this is a necessary measure for layout and rendering performance. However, I don't believe it's something we've formally benchmarked.
• We're inconsistent about how we refer to this mode. Sometimes it's referred to as "clipping" and sometimes in the inverted sense as "drawAcrossEdges". To avoid confusion and ambiguity, let's settle on "clipped" vs "unclipped". This is preferable to "drawAcrossEdges" because even clipped drawing can "draw across" a tile edge -- it just requires both tiles to cooperate in the drawing to do so.
• In order to obtain the correct result for unclipped drawing, we require that the text and/or icon for a given feature be drawn by exactly one tile, even when that text and/or icon crosses a tile boundary.
• For Continuous mode, we attempt to satisfy this constraint by throwing out features that lie within the buffer area of a tile. However, our implementation fails to consider that features can lie exactly on the line delineating "tile proper" and "tile buffer". That's this issue.
  • A quick fix -- call it "Option 3" -- for this issue would seem to be to keep features that with x or y coordinate equal to 0, but throw out features with x or y coordinate equal to EXTENT.
• The "throw out features in the tile buffer area" approach does not work for Still mode, because a critical use case for Still mode is to render a single tile without requiring data for any adjacent tiles. I.e. each tile must be responsible for drawing the portion of any text and/or icons that lie within that tile.
• Therefore we must have different code paths for both layout and drawing in Still versus Continuous mode. In the past I have argued that this is dangerous, not only because of the additional code complexity, but also because it can lead to situations where someone designs a style with large fonts or generous text spacing that looks fine in Continuous mode but then gets clipped in Still mode.
• This strategy produces edge-case misrenderings even in Continuous mode: when the edge of the map coincides with the edge of a tile, text and icons that cross that edge can "pop" in and out depending on whether the adjacent tile is just off screen and not rendered, or just on screen and rendered.
• Certain other symbol layout properties also require modifications to the above approach. In particular symbol-avoid-edges.

Gaps in my understanding:

• Why does symbol-avoid-edges require clipping? What does it actually do?
• What does this comment mean? It implies that {text,icon}-allow-overlap and {text,icon}-ignore-placement are relevant to whether we want clipping or not. Why?
• add padding to annotation tiles #1673: why would we care whether the point annotation layer has a buffer, if we're going to throw out features within the buffer anyway? Note that, other than for rendering tests, we don't require annotations to support Still mode -- we're going to use GeoJSON layers for static overlays, which are already buffered.

[mikemorris]

@jfirebaugh symbol-avoid-edges was discussed in #3582 and implemented in #3623. We've considered removing it in mapbox/mapbox-gl-style-spec#287 and hard-coding smarter decisions around clipping.

[jfirebaugh]

I'm not sure I really understand those issues. #3582 seems to indicate that the purpose of symbol-avoid-edges is to avoid icons placed on lines from being clipped at tile edges in Still rendering mode. That's not at all what the documentation suggests. And the default value for symbol-avoid-edges is false, which would seem to indicate that the rendering shown in #3582 is still the norm for Still mode.

[mikemorris]

The purpose of symbol-avoid-edges is to prevent placing features near edges at all, which is nearly always the right decision for icons on lines in MapMode::Still because of

The point positions for line labels are calculated by finding the points every __px along the line. Since the same line could be clipped differently in both tiles, it is pretty likely that these calculated points won't be the same in both tiles.
#3582 (comment)

symbol-avoid-edges defaults to false because when applied to features that render fine across tiles, like roads, it make them disappear. I believe we always set this to true for line labels in mapbox styles though.

[brunoabinader]

It has been asserted that this is a necessary measure for layout and rendering performance.

Ansis comments about the extra quads are right. On #6832, I add a virtual padding that accounts for 1/8 of the tile size, for each direction. This can result in a performance impact during placement for a big amount of features (~100k). However, I don't see a large number of features like this to be the common use case.

In order to obtain the correct result for unclipped drawing, we require that the text and/or icon for a given feature be drawn by exactly one tile, even when that text and/or icon crosses a tile boundary.

Yes - e.g. issue #6670 is about the rendering artifact caused by unclipped features being overdrawn on tile edges.

A quick fix -- call it "Option 3" -- for this issue would seem to be to keep features that with x or y coordinate equal to 0, but throw out features with x or y coordinate equal to EXTENT.

Yes - IIRC this was my first proposed solution for #3563. However, that implies in features on tile edges in which tile is rightmost or bottommost being skipped, plus other issues mentioned below.

Therefore we must have different code paths for both layout and drawing in Still versus Continuous mode. In the past I have argued that this is dangerous, not only because of the additional code complexity, but also because it can lead to situations where someone designs a style with large fonts or generous text spacing that looks fine in Continuous mode but then gets clipped in Still mode.

I believe both code paths and behavior should be the same for both modes - this is what I propose in #6832.

Why does symbol-avoid-edges require clipping? What does it actually do?

Besides the comments from @mikemorris - I believe we enable clipping there because we don't want symbols from other tiles polluting the requested tile in still mode.

What does this comment mean? It implies that {text,icon}-allow-overlap and {text,icon}-ignore-placement are relevant to whether we want clipping or not. Why?

Yes - rationale is that collision detection algorithm runs on a per-tile basis, relying on additional padding added to each tile for detecting collision with features on neighbor tiles. This gives us some guarantees that a colliding feature near one tile edge won't collide with another from a neighbor tile - thus no need for clipping.

In theory, this is not an issue for non-colliding features (we disable collision when enabling one of the style properties mentioned above) - because we shouldn't need to worry about overdraw. However:

• because we duplicate features on tile edges; and
• because we want non-colliding features to be sorted by their y position, even on tile edges;

We then add buffers around each tile and then enable clipping to avoid overdraws.

#1673: why would we care whether the point annotation layer has a buffer, if we're going to throw out features within the buffer anyway? Note that, other than for rendering tests, we don't require annotations to support Still mode -- we're going to use GeoJSON layers for static overlays, which are already buffered.

We use the buffer for rendering the "other side" of the clipped feature - and we only throw out features outside of the tile boundaries if symbol-avoid-edges is true.

OK, this is a lengthy reply so here's a summary of my thoughts on this:

• We always need buffers around each tile:
  • Colliding symbols uses them to calculate collision with near symbols from neighbor tiles.
    • We don't need to enable clipping here because we have guarantees that the feature won't collide with others.
  • Non-colliding symbols uses them to properly sort features by their y position near tile edges - which is why IMO option 3 won't work as expected.
    • We need to enable clipping to avoid overdraws.
• When we enable each one of the {text,icon}-allow-overlap and {text,icon}-ignore-placement, we disable collision, thus requiring clipping.
• Annotation symbols are non-colliding, thus requires clipping and extra buffers - this is what I propose in [core] Avoid clipping symbols in continuous mode #6832.

[ansis]

Fixing the original duplicate feature problem.

A quick fix -- call it "Option 3" -- for this issue would seem to be to keep features that with x or y coordinate equal to 0, but throw out features with x or y coordinate equal to EXTENT.

Sounds right to me. A point should only exist inside one tile.

However, that implies in features on tile edges in which tile is rightmost or bottommost being skipped

I think this is the correct behavior. The rightmost edge of the world is the same space as the leftmost. The bottommost edge is a trickier question, but depending on the interpretation of the tile space and projection this edge maybe shouldn't exist. In practice I think excluding it won't cause any problems.

Answers / comments about clipping

The first part would fix the original issue so this question is completely separate from that.

It has been asserted that this is a necessary measure for layout and rendering performance. However, I don't believe it's something we've formally benchmarked.

It would be good to benchmark. I think the 50% - 66% number came from counting the number of skipped labels but it would be good to get a difference a tile's total buffer size and processing time.

A 1/8 buffer for annotations sounds good. We need a much bigger buffer for text labels though depending on their size and max width. Some of the text layers in the vector tiles have pretty large buffers.

Why does symbol-avoid-edges require clipping? What does it actually do?

I can't think of why this needs clipping. If it does, it's buggy.

What does this comment mean? It implies that {text,icon}-allow-overlap and {text,icon}-ignore-placement are relevant to whether we want clipping or not. Why?

In order to get y sorting to work correctly at tile boundaries we need to have the features in both tiles and then clip them when rendering. This is what -js does. We can't do this in -native yet because the annotation tiles only contain features strictly within them.

#1673: why would we care whether the point annotation layer has a buffer, if we're going to throw out features within the buffer anyway? Note that, other than for rendering tests, we don't require annotations to support Still mode -- we're going to use GeoJSON layers for static overlays, which are already buffered.

We're not going to throw them away. Annotations in continuous mode need to be clipped to tile boundaries to get y sorting to be correct. The annotations along borders need to be in both tiles.

What I think about clipping

I don't like the two paths. If we can get rid of the non-clipped one and the cost in size/time is reasonable I think this would be a worthwhile tradeoff. It might result in some visible clipping when rapidly zooming out but it would fix popping when panning.

But I'm not sure how clipping everywhere would play with 3D. Labels in 3D will extend too far beyond tile edges for the clipping approach to work. I'm not sure if we can make the current tiled collision algorithm work in 3D either. Collision detection in 3D will need some global knowledge. I haven't thought much about what this would look like but I think we might need two separate paths here.

[jfirebaugh]

I don't like the two paths. If we can get rid of the non-clipped one and the cost in size/time is reasonable I think this would be a worthwhile tradeoff.

The only way I could see getting rid of the unclipped mode is if we distinguished between two still rendering modes:

• Still rendering of a single tile. In this mode, we can never throw away features within the tile buffer. However, since we're only rendering a single tile, it doesn't matter whether we clip or not.
• Still rendering of an arbitrary bounding box. We could change this mode to load extra tiles around the border of the bounding box, and then follow the pathway for the Continuous rendering mode, with buffered feature discarding and clipping.

I gotta admit, even with all the above discussion, I'm not clear on the role of symbol-avoid-edges and {text,icon}-allow-overlap and {text,icon}-ignore-placement. Does anyone feel they understand these properties at a deep level?

[Edit: basically, this means we can't "get rid of the non-clipped one", in the sense of being able to throw away features within the tile buffer no matter what. We can't ever do that unless we want to increase the cost of rendering a single still tile by ~9x.]

[ansis]

Still rendering of a single tile. In this mode, we can never throw away features within the tile buffer. However, since we're only rendering a single tile, it doesn't matter whether we clip or not.

If we get rid of unclipped mode we will never want to throw away features, so we wouldn't need to distinguish here.

Still rendering of an arbitrary bounding box. We could change this mode to load extra tiles around the border of the bounding box, and then follow the pathway for the Continuous rendering mode, with buffered feature discarding and clipping.

We discard buffered features in unclipped mode. We can't discard them in clipped mode.

I gotta admit, even with all the above discussion, I'm not clear on the role of symbol-avoid-edges and {text,icon}-allow-overlap and {text,icon}-ignore-placement. Does anyone feel they understand these properties at a deep level?

• -allow-overlap determines if previous symbols affect the placement of the current symbol
• -ignore-placement determines if the current symbol will affect the placement of layer symbols

In most cases you want both to have the same value. I can't think of an example you would want them to be different. I think we should merge them into one property.

There is an open spec issue about this: mapbox/mapbox-gl-style-spec#429

symbol-avoid-edges

symbol-avoid-edges prevents the symbols from crossing any tile boundary. The reasons behind it are complicated. It exists because of some limitations of our tiled collision detection.

These same limitations existed in Mapnik before it. CartoCSS had -avoid-edges properties which worked the same way. We calculate placement separately for each tile. In order to support cross-tile labels we need both tiles to be able to make the same choice without any communication between them. A tile needs to know where the neighbouring tile would place labels close to the tile edge. We include features in a tile that are outside it's strict boundaries so that it can make a good guess what it's neighbours are doing. There are some cases where these guesses aren't good enough.

We can't predict line labels because they could be anywhere along the line. Any point labels placed after line labels are contaminated by the chaos in the line labels so we can't predict their position either. symbol-avoid-edges should be used to prevent these point labels from crossing tile edges.

OK, why don't we just automatically set this for any point labels below a line label layer? My understanding (I might be wrong) is that there are cases where we want to risk the chaos in exchange for having cross-tile point labels that are placed after line labels. We might have a rare line label layer somewhere early on and we don't want that to affect all subsequent point layers.

Another case where it might be used is if the style makes the text bigger than the buffer safely supports.

I don't like this but my understanding is that this is a necessary part of mapnik-style tiled label placement. I've wondered if we could figure out a way to eliminate the chaos caused by lines.

[brunoabinader]

In practice, on -native symbol-avoid-edges is used only to check whether a feature outside of the tile border should be accounted as a symbol instance (symbol instances are used for y-sorting, placement and to draw collision debug rects).

Why does symbol-avoid-edges require clipping? What does it actually do?

I can't think of why this needs clipping. If it does, it's buggy.

Check out https://github.com/mapbox/mapbox-gl-test-suite/blob/master/render-tests/symbol-avoid-edges/rotated-false/expected.png:

I remember this specific render test being failing on my initial tests with clipping disabled (option 1). I also agree this clipping behavior looks wrong.

If option 1 is still viable as long as we also add padding to annotation tiles to account for y-sorting, then a side effect is that the sorting is right up to the padding we add e.g. 1/8:

IMO this is the only side-effect for choosing option 1 + annotation padding. if you're curious, the screenshot above was taken using a modified patch on top of fix-symbol-clipping branch.

[brunoabinader]

Heads up I found a way of rendering sorted, non-colliding symbol annotations across tiles - we just need to order symbol render tiles in opposite Y order prior to rendering. Since this was the only reason for adding padding to symbol annotation tiles (#1673) - it seems we no longer need it. Sorting symbol render tiles is a cheap operation (certainly much cheaper than add padding to every render tiles) and also portable into -js code.

IMO this makes getting rid of symbol clipping a valid option again. I'm going to update #6832 to reflect these findings. We still clip when in Still mode, but just because we need to update our render test results e.g. some render tests results have (expected!) clipped symbols that don't need to be.

[ansis]

Heads up I found a way of rendering sorted, non-colliding symbol annotations across tiles - we just need to order symbol render tiles in opposite Y order prior to rendering.

I don't think this works in all cases. Take a look at the image in the original issue (#1673). Some icons from the left tile need to be rendered on top of some icons from the right tile and some icons from the right tile need to be rendered on top of icons from the left tile.

[brunoabinader]

I don't think this works in all cases.

Yes - it does not cover all cases, but the exceptions are almost imperceptible (tolerable):

IMO that sounds good enough as an argument against over-populating the symbol instances for each symbol annotation tile. What do you think?

[ansis]

If we are fine with closer-to-the-top annotations sometimes being drawn over closer-to-the-bottom annotations then this is ok. I think the mobile team could better answer whether this is acceptable

Also, I'm not sure if the closely packed grids are the worst case. I think the incorrect overlap could be more visible with just two annotations

[brunoabinader]

Fair enough @ansis 🙇‍♂️

Just worth noticing I'm not against adding padding - that is the best solution render-wise. I'm just curious whether we could use a faster (needs benchmark?) implementation that doesn't use padding and produces almost the same results.

I think the incorrect overlap could be more visible with just two annotations

Not sure if I follow, but the results I obtained with just two annotations looks OK with the sorted render tile approach:

[brunoabinader]

Can we settle a decision? I'm afraid #6832 is going to get bit-rotten soon.

I'm a supporter for avoiding the extra padding given the results above, plus the fact we can avoid using clipping for symbols. If we proceed with this implementation decision, we'd need to backport these changes into GL JS before removing clip for Still mode, so we can update render test expectations that currently expects clipped symbols (which looks wrong IMO).

ITOH, I won't argue if we decide to keep with the extra padding in favor of rendering results and parity with GL JS implementation.

[jfirebaugh]

Once again: we will likely never be able to remove clipping in Still mode. We have to be able to render a single tile without loading the 8 surrounding tiles. That requires rendering all features within the tile buffers, but clipping the rendering.

I don't see a way around this that won't kill our COGS for static tile rendering. @brunoabinader you seem very very keen on removing clipping in Still mode. How do you propose to get around this?

[jfirebaugh]

Check out https://github.com/mapbox/mapbox-gl-test-suite/blob/master/render-tests/symbol-avoid-edges/rotated-false/expected.png:

I remember this specific render test being failing on my initial tests with clipping disabled (option 1). I also agree this clipping behavior looks wrong.

The clipping in this test-case is a side effect of:

• Needing to use clipping for Still mode
• Using line placement for icons but not symbol-avoid-edges (Annotation symbols are overdrawn if located on tile edges #6670 (comment))

I don't think we can avoid it. In the real world, you'd be using symbol-avoid-edges: true if you wanted line-placed symbols.

[brunoabinader]

We have to be able to render a single tile without loading the 8 surrounding tiles. That requires rendering all features within the tile buffers, but clipping the rendering.

Thank you @jfirebaugh - this helped me understand/record why we need to clip symbols in still mode. I'll update the comments in #6832 accordingly.

Please reconsider what I've said here except removing symbol clipping in Still mode. FWIW this is exactly what is proposed in #6832 atm.

[zugaldia]

Capturing chat with @brunoabinader + some Android folks, the solution proposed in #6670 (comment) (option 1 preserving current behavior for still mode), while not perfect, is an improvement over the current state of things and seems unlikely that we'll see it in real world situations. On the other hand, the alternative solution (option 2) is more expensive and will bring a performance hit.

From a practical point of view, if I were to choose between a performance hit, or a better performing solution with rendering errors in unlikely scenarios, I'd say we go with the more performant approach (option 1).

[brunoabinader]

Fixed in #6832.