Label placement

[dmitrig01]

• [ ] currently, labels are only placed to the right hand side; code up a way to try out alternative label positions
• [ ] figure out what to do when the user zooms the tile so that it's smaller than the initially labels places
• [ ] handle tile bounding boxes correctly; use other tile's tree to do collission detection
• [ ] for label placement on short broken segments of streets (e.g. in a street grid), we'd have to recombine all segments of a street before placing labels so that we get a large enough straight line (this is something we could use for mapnik too!) recombination could be done on a vector tile level by joining all lines that shared the same name and have at least one vertex in common
• [ ] label placement for rotated rects, e.g. for street names:
  • find an algorithm that extracts all parts of streets that are straight enough to have labels at the top zoom level, or at lower zoom levels
  • do collision detect with rotated rects
  • could be easier if we do collision detection with every (non-rotated) glyph bbox rather than one bbox, even for glyphs that are rotated (like mapnik)

[kkaefer]

Biggest question on this is how we're going to do placement when rotating the map. The issue is that our current approach of precomputing label placements for all zoom levels of a tile (using the 3D cones) doesn't work because the rectangles will overlap differently.

What we could do is:

• Leave the labels as is and allow them to overlap while rotating. When the user stopped rotating we'll recompute the label placement for that rotation
• For every frame, place labels again according to the current zoom level, but don't try to place deep labels while rotation. This should be pretty fast, but we might not be able to reuse the font textures and have to render labels again (which makes it very slow to impossible)

We might have to do different label placement approaches for different labelling: Text that always stays horizontal needs to be placed differently from text that stays with the road. This is because if you rotate the map, the labels that stay with the road will stay with the road and there are no collisions from the rotation there. The labels that are always placed horizontally are different, they will overlap differently if you change the rotation.

What to do for animations that change both the zoom and rotation at the same time?

[kkaefer]

wrote up the current state of label placement: https://gist.github.com/kkaefer/67c01981447c2c1e816d

[ansis]

Consistent Labeling of Rotating Maps http://arxiv.org/pdf/1104.5634v1.pdf

[ansis]

Here's a summary of my notes, which is basically what you wrote earlier + some problems + some ideas. Sorry about it being long and not that articulate -- I started writing too late at night. I can rewrite anything tomorrow if its too confusing.

edges between zoom levels

To make zoom level changes seamless, you need enough data in both tiles to place labels in the same spot. If you have one possible label position, and child tiles contain all labels found in parent tiles, this can be done. This requirement makes is problematic for having multiple possible positions (more on that later).

rotation

The ideas in Consistent Labeling of Rotating Maps are interesting, but it doesn't talk much about zooming. Some weighted approach that optimizes for both zoom and rotation could be used, but this will break zoom boundaries.

I think the approach to take is to place all labels similar to your demo, and then use a second pass to greedily add continuous rotation ranges. Greedy is good, because its simpler to implement and more predictable, which we need for seamlessness. Instead of two passes, this could all be done in one, but I think the two-pass approach is better because it favors the default orientation.

Its not possible to represent the continous rotation range as a single value, or even a continous function. Since having a single range per label per tile will probably cause too many labels to be hidden, ranges should be calculated for multiple zoom levels with the tile. A couple ranges should cause a significant improvement. These could all be added in the same buffer to avoid re-uploading data.

The implementation would work similar to your demo, except with bigger bounding boxes more complicated conflict calculation. More on this in the pseudo-pseudo-code later on.

The bounding boxes in the rtree can be placed either from the perspective of the map rotating or the screen rotating. One might be faster if there are more horizontal than path labels.

multiple possible placements

Having multiple possible positions for a label is problematic with seams. For edges we could just avoid crossing tile boundaries. I can't think of a solution for zoom boundaries.

This means we can only support multiple possible placements in the highest zoom level vector tile (eg 14). With the last zoom level we don't have to worry about being seamless with children because there are no children. Luckily, this is probably the zoom level where multiple positions are most useful. Multiple positions could be just tried greedily. If multiple placements are allowed, tile edges should be avoided for these labels.

For better placement at higher zooms, we could use some server-side processing to add hints about which side to place a label on. The client would still only check one spot, but would have a slightly lower possibility of conflict.

serverside placement

Could be useful, but I think client side is doable. Labels can always be faded in slightly later (which we might want to do anyways with chunked parsing -- but thats for another issue and another time).

tile edges

The only way to avoid this is disallow any placement over edges. Even this is problematic, because we need to consider edges in child tiles.

We should allow writing over edges, try to reduce the likelihood of edge conflicts, and ultimately prevent edge conflicts from being drawn.

The probability of conflicts can obviously be reduced by increasing the tile padding for labels. I think it could also be reduced by giving similar priority labels a higher priority of they are near an edge, but this seems weird.

Ultimately, we check for conflicts for each pair of neighboring tiles. We adjust the min zoom level of one of conflicting labels to avoid the conflict.

hiding labels at lower zoom levels

This seems doable. Simplest approach would be to still place it and have it conflict with other labels, just not show it. In order to maintain zoom seamlessness we only need to consider it as a conflict when placing labels found in the previous tile. When placing new we could place them where the hidden label would go. This means each label in vector tiles would need to specify if it appears in the parent (this would also be useful for fading in buildings, etc).

labels along curves

The placement part could be solved with generous bounding boxes, and maybe several bounding boxes for several zoom ranges. Drawing probably needs to have data uploaded at each draw call, but we can probably limit this to 4 bytes (offsets, rotation).

(a bit crazy) I'm intrigued by the idea of representing labels along paths as paths we can represent with a small constant number of values, for example an ellipse. Beziers don't work great, since you can't find the point x distance along a line without looping, although that might be ok here. This would let us render path labels without updating the vertex buffer.

changing font sizes

This is doable, but complicates finding the first zoom level at which a label can fit. It could always be solved iteratively.

pseudo-pseudo-code

Its just a brain dump, so its hard to follow, and it glosses over some details, but:

// insert based on zoom, similar to Been and your demo
- iterate over labels by priority
    - place labels greedily similar to your demo, but with several differences:
        - the bounding box for the rtree is the extent of the label at all rotations
          (a square with a side length that is 2x the length of the label from the anchor point)

        - if this tile is the highest zoom level tile available (eg, 14)
          and the label appears only in this tile:
            - don't place the label across a tile boundary
            - try placing the label in one of the other points if it fails          
            (a square with a side length that is 2x the length of the label from the anchor point)

// greedily add rotation ranges
- for each label in rtree
    - for all possible conflicting labels found in rtree
        - for various zoom levels
            - skip if label not visible at zoom level
            - check the two labels for actual conflicts:
                - if both are horizontal labels
                    - find the 8 potential conflict points (see rotational labelling paper)
                    - check if they are conflicts
                    - calculate range
                - else if both are path labels
                    - no conflict (full range)
                - else if one is horizontal, the other path
                    - todo details
            - intersect these ranges to find the result range
            - write this range

// check for tile boundary conflicts, eliminate them without affecting other placements
for every pair of neighbouring tiles:
    find all labels that conflict with something in the other tile
    for the less important label, add a second, higher z-value for when its safe to render

write buffer with all labels who's anchor is in the main tile area
either include the z values and degenerate in the shader
or sort by z values and control visiblility by controlling length of features drawn by draw call

Summary

I'm seeing an approach that:

• supports both horizontal and path labels
• optimizes for zoom
• supports rotation, but prioritizes optimizes for no rotation
• is seamless and conflict-less across edges and zoom levels
• supports multiple possible positions for highest zoom level, only one for others
• is probably fast enough for client side use
• can be made to work with changing font sizes

[kkaefer]

Thanks for your summary; a braindump is totally sufficient at this point. You're talking about not crossing tile boundaries. However, I think that we should do exactly that: Tile boundary issues have been a major pain point in the past and now we finally have a way to adopt a more "global" view at the map labelling problem. I think it's totally fine if labels bleed into other tiles, as long as they are fully visible and not cut off. If the user pans, and a new tile is loaded, label placement for that tile should respect the labels that already bleed into that tile. If the user pans further and the original tile gets removed, we have two options: We retain the label until the tile it bleeds into is removed as well, or we remove it right away. The latter approach would leave some minor gaps at the tile seams where we ordinarily would have placed other labels, but I think it's fine to just leave them empty. In this case, we'd violate the often-declared desiderate of history-independent labelling. Most other maps have interaction-history-dependent labelling too, and I don't think this is a big issue for now.

An alternative approach would be to recalculate the label placement for all tiles if the set of tiles changed: We'd merge all buckets across all loaded tiles and then do a global label placement for the tile set. This means labels might disappear/reappear if you're panning. Since we're not going to do a packing optimization and are going to use a greedy approach (like mapnik), this popping should be limited to the outermost tile seams (which often aren't visible anyway). This has the advantage that we could combine long-running streets that span several tiles and compute a unified labelling for the entire visible length of the street. Unfortunately, it's going to be hard to recombine features across tiles since our current vector tiles have a generous bounding box (ironically, we do this to avoid cut-off labels...) so we'd need a way to find these duplicate stretches which seems very compute-intensive and error-prone.

Finally, for curved labels, Google has these interesting "gradient" textures that contain 1px high gradients that all have a different width:

I'm not exactly sure what they're using these for, but we could create textures that for every placed glyph contains the glyph metrics (for the sdf texture), as well as the position/rotation for various zoom levels, and use interpolation between these fixed values to correctly place the glyph. This might be very expensive since we'd have to do a texture lookup in every vertex shader, but then again, we could use the texture to store constant per-glyph settings to reduce the glyph buffer size, and we're doing a texture lookup for every fragment anyway and there are a lot fewer vertices than fragments per glyph.

[kkaefer]

Note that for curved path text, we'd have to store both the x/y position of the glyph as well as the rotation for every zoom level. Additionally, that'd make it hard to simply flip the label if they are upside down. Alternatively we could somehow encode an approximated version of the path segment (y distance from anchor point) for every label (not glyph!) and reference that label ID in the glyph buffer, then look it up in the texture and compute the correct position based on the distance/zoom from the anchor point.

[kkaefer]

We should also support label alternatives: First place the big label (e.g. "Deutschland"). If it's not placed at the "root" zoom level (i.e. it only appears when zooming in due to collision), then try placing an abbreviated/alternate label (e.g. "DE") at the same position and show that label until there's enough space to show the long version of the label.

[kkaefer]

Also note that label placement depends on the text size. Currently, we determine the text size at render time (it is a layer style property, not a bucket property), but we can't really do that anymore when we calculate the placement in a preprocessing step.

[ansis]

I'm not exactly sure what they're using these for, but we could create textures that for every placed glyph contains the glyph metrics (for the sdf texture), as well as the position/rotation for various zoom levels, and use interpolation between these fixed values to correctly place the glyph.

Using a texture is a great idea. You only need to do this for one zoom level, not multiple. Just have the line contain data for a point that distance along the line. A per-glyph distance-along-the-line attribute could be scaled based on zoom level to adjust the distance along the line. Basically, the glyph figures out how far along the path it needs to be placed, and then lookup the offset/rotation for a point that far along the path.

[ansis]

And flipping should be doable in the vertex shader if glyph vertices know the total distance along the line, and the angle at which the line flips (either vertex data, or from a separate texture lookup).

[ansis]

You're talking about not crossing tile boundaries. However, I think that we should do exactly that: Tile boundary issues have been a major pain point in the past and now we finally have a way to adopt a more "global" view at the map labeling problem.

I agree, on crossing tile boundaries:

We should allow writing over edges, try to reduce the likelihood of edge conflicts, and ultimately prevent edge conflicts from being drawn.

The first approach to tile boundaries you describe is mostly what I had in mind. I hadn't thought of the issue of which tile was loaded first when suggesting inter-tile conflicts are resolved by label priority. Resolving them based based on which tile was shown first seems like a good approach. The goal of not hiding conflicting labels that have already been drawn is good, but probably isn't 100% necessary. It might not be that visually jarring to hide them to make way for higher priority labels, since it doesn't affect other label placements.

[kkaefer]

This first attempt at label placement places all labels on a 4096x4096 square. It does not place any labels across tile boundaries, and it makes no attempt to find "deeper" initial label placement if it doesn't fit on the main plane. It doesn't place horizontal labels (instead, this patch converts all horizontal labels to curved labels so they are rotated if you rotate the map). It also makes no attempt at cured labels and no attempt to only choose placements so that the label fits onto the line (i.e. discard short segments)

[mikemorris]

Noticed this while playing around with the Maps app on OS X 10.9 last night, thought it might be relevant. Apple is clearly rendering the base layer tiles separately from the roads layers and labels, not sure if you may be able to infer anything useful from this.

[kkaefer]

Thanks. You're looking at satellite tiles, so the actual vector data and the pixel data are separated to begin with.

[kkaefer]

Labels are being placed for now. We have more detailed tickets for further work to improve label placement.