Collision detection doesn't fully account for label zoom functions

[ChrisLoer]

When we do collision detection for a tile, we calculate the size of labels at zoom level tileZoom + 1, and then assume that the size of the labels will scale directly with the zoom level in the range between tileZoom and tileZoom + 1. This allows us to calculate a single "minimum zoom" for each label and pass that value to the shader, so that the shader can know whether or not to show a particular glyph/symbol.

With a text-size or icon-size zoom function, this can break down in a couple ways:

• If a zoom function makes the label smaller as the zoom increases, the label can be considered a "collision" prematurely. Within a single zoom level, this isn't so bad -- we're just being more conservative with label placement. However, it becomes a problem when you reach the next higher zoom level, because when the collision boxes get recalculated at the new zoom level, the label will start showing again. With a very reasonable zoom function that decreases text-size as the zoom level increases, this could cause lots of label flicker on crossing integer zoom levels.
• Zoom functions that make the label bigger as the zoom increases can lead to label collisions. Also, depending on how quickly the label increased size, we might need a "maximum zoom" for the label instead of a "minimum zoom". I don't see why you'd want to do this for a simple zoom function, but it might inadvertently result from the calculations for a composite zoom-and-property function.
• A zoom function that's not monotonically increasing or decreasing with zoom is fundamentally incompatible with the whole "minimum zoom" approach.

I think the first case could be fixed with some complicated but not necessarily prohibitively expensive logic in CollisionTile#getPlacementScale. Right now, to determine the "min zoom" for a new label, we compare it to each already placed label it may touch, and against each new label we solve to find the scale at which their sides touch. It's a very easy solution, because the sizes are all linear in scale. In the new logic, we'll have to do the algebra to solve for where two different zoom (and property) functions intersect.

The proposed changes to handling label size on pitched maps make this even a little more complicated, because labels will change size dynamically based on their position at render-time. The current proposal for handling that case is to treat distant pitched tiles as if they're at a much lower zoom level -- but that only works because the "minimum zoom" functionality doesn't account for label size zoom functions.

I came across this behavior while reviewing the DDS text-size changes. It's closely related to #1196 (text-offset isn't handled correctly by collision detection), but I think it makes sense to track separately.

/cc @ansis @anandthakker @mourner

[ChrisLoer]

One other wrinkle: although we're mainly concerned with label collision, we also have to make sure any solution has consistent behavior with the anchor min scale logic for line following. Otherwise, we could end up with individual glyphs be dropped out of a label (because they had no more line to follow) while the rest of the label kept showing.

[ChrisLoer]

/cc @mollymerp

[ChrisLoer]

This issue is mostly fixed by #5150, enough that I think it makes sense to close the issue. The "collision pyramids" don't exist anymore, and we also got rid of the "min scale" line following logic.

Collision boxes are still based on layout properties calculated at integer zoom levels, so it's still possible to create zoom functions that will make the size of a label significantly different from its collision box at fractional zooms. However, the "fade out just before crossing an integer zoom level and then pop back in" problem should be mostly gone. The infrastructure is in place for us to re-calculate the box sizes at collision detection time, but I'm in favor of waiting to see if it's actually a real-world problem before adding that extra work to the (performance-sensitive) collision detection code.

[ChrisLoer]

The infrastructure is in place for us to re-calculate the box sizes at collision detection time, but I'm in favor of waiting to see if it's actually a real-world problem before adding that extra work to the (performance-sensitive) collision detection code.

It took 8 months, but I just got a report of this causing a problem -- it was an icon-size with an exponential zoom function that would have spurious collisions at fractional zooms.

[ChrisLoer]

The currently broken case is using an exponential zoom function to fix the size of an icon relative to the map scale. The size of the collision boxes resets to "correct" on crossing integer zoom levels:

Ideally, when we fix this we should also add support for run-time size evaluation in the debug collision boxes as well.