Mapbox-gl-js: the future of labelling

[ansis]

@ChrisLoer, @kkaefer and I talked about making large changes to text rendering and label placement.

Problems

current problems:

• labels aren't legible in pitched views (https://github.com/mapbox/mapbox-gl-js/pull/4682)
• labels have collisions across sources (#2703)
• labels have collisions across tiles in pitched view
• labels aren't faded across tiles or on rotation
• collision prevention code is hard to expand to account for new features like text-pitch-scaling

future problems:

• collision prevention for labels offset in the z direction (a label on top of a building)
• rendering and collision prevention for labels following a 3D path (a label for a road on 3D terrain)

---

Labelling has two subproblems:

• placement: figuring out where you want to put labels and avoiding collisions
• rendering: actually drawing glyphs where you want them

Rendering

Up until now

We're still using the sliding-glyph-for-each-segment-that-gets-toggled-on-and-off approach (original devlog). This approach really only works if labels are always rendered on the map plane. text-pitch-alignment was added to make labels more legible in pitched views. @ChrisLoer's recent work improves on this. Both of these text-pitch-alignment implementations are workarounds that work fairly well but have some problems because of the limitations of the original implementation.

Using a different approach

I think we all agreed that this approach is getting hard to adapt to our needs and is getting harder to understand. We should try something completely different. If we have access to the full line geometry when doing the vertex transform it gets a lot easier and more accurate. The rough algorithm:

1. Project the line into the plane you want to put the text on (map plane, viewport plane)
2. Iterate along the line to find a point the correct distance along the line.
3. Offset the corner of the glyph from this point on the line.
4. Project the resulting position into GL coords.

We need to figure out a way to do this fast enough that we can do it on every frame.

CPU version

On every every, perform the above algorithm in javascript to transform each symbol vertex into gl coords. Create a new vertex buffer, upload the changes.

Potential concerns:

• we can't make vertex transformations fast enough (~2ms total?)
• uploading new buffers every frame has some cost
  If performance is good enough this approach is probably ideal.

GPU version

If we can't make the CPU version fast enough here's something we can try:

Encode a fixed size representation of the line in a vertex attribute. Perform the entire algorithm in the vertex shader.

Potential concerns:

• limited amount of attributes a shader can have in native. We might need one or two for passing a delta encoded line geometry
• the fixed size line limitation could result in jagged curved lines
• unclear if this would be faster than doing it on the cpu

Placement and collision prevention

Up until now

We've been doing label placement with a tiled approach where the placement is calculated completely separately for each tile. This approach lets us do cross-tile labels in api gl (where each tile is rendered separately) while having exactly the same labelling as client-side gl maps.

The current approach calculates placement for an entire zoom level at once to reduce flickering. We do this by creating a bunch of boxes that cover the label and collision checking them in 3 dimensions. It was adapted to mostly work in pitched views but this gets harder to do with text-pitch-alignment. It will get worse if we support tilting the map further or support z offsets for labels.

A different approach

I think we're going to have to do global placement instead of tiled placement in order to:

• do cross source label placement
• support more pitched views
• support text-pitch-alignment properly
• support z offset labels

The general idea would be to collect all label data from all tiles/workers and move it to a single thread where we can operate on them all at once.

open questions:

• how does this interact with the tiled needs of api-gl?
• does api-gl need to have exactly the same label placement as dynamic gl maps?
• how important is it to reduce the number of labels flickering in and out as you move the map?
• how important is it for the placement of a view to be deterministic? (in the sense that it doesn't depend on how the map got to where it is)

---

Next steps

I'm going start working on rendering using the CPU vertex transformation approach. @ChrisLoer is looking at his current PRs and seeing what can be merged without waiting for this future work.

[mb12]

@ansis Thank you very much for publicly sharing such a detailed logical and high level description. Can you please kindly answer the following?

1. Can you please explain why in the current scheme labels appear illegible in
   pitched mode? Distortion is only visible on labels placed along a line. There
   is no distortion for Labels for which rotation alignment is viewport (labels that stay upright on
   rotation).

2. Can you please clarify the following? Does this mean applying the perspective
   transform on the vertices? The vertices are already projected in the sense
   that they are relative coordinates.

"Project the line into the plane you want to put the text on (map plane,
viewport plane)"

3.) In pitched mode lines also show sawtoothed edges/aliasing artifacts.
Is it something that can be improved/fixed?
Currently highways looks like really thin strands of hair in pitched mode to this
artifact (Even highways at center of the viewport get this artifact. Highway shield is legible but the underlying road is not).

1. Is there any specific reason to do this on JS first?
   Native development tools are much superior when it comes to debugging (
   breakpoints etc in non UI thread). It would be easier to catch any performance
   issues with weaker CPUs during development itself (Desktop CPUs have much better performance).

[ansis]

1. Can you please explain why in the current scheme labels appear illegible in
   pitched mode? Distortion is only visible on labels placed along a line. There
   is no distortion for Labels for which rotation alignment is viewport (labels that stay upright on
   rotation).

Yep, I was referring to the distortion on labels placed along lines.

1. Can you please clarify the following? Does this mean applying the perspective
   transform on the vertices? The vertices are already projected in the sense
   that they are relative coordinates.

Yep, projecting them from tile coordinates to screen pixels if you want labels rendered on the viewport plane.

1. In pitched mode lines also show sawtoothed edges/aliasing artifacts.
   Is it something that can be improved/fixed?
   Currently highways looks like really thin strands of hair in pitched mode to this
   artifact (Even highways at center of the viewport get this artifact. Highway shield is legible but the underlying road is not).

I'm not sure. I think last time I looked at this lines were pretty ok, except when they are drawn on top of a casing. The way two really thin lines drawn on top of each look isn't great.

1. Is there any specific reason to do this on JS first?
   Native development tools are much superior when it comes to debugging (
   breakpoints etc in non UI thread). It would be easier to catch any performance
   issues with weaker CPUs during development itself (Desktop CPUs have much better performance).

I think it might be faster for me to start with JS. and I think we're also more concerned about performance in Javascript and large viewports than on mobile devices. Also, we're now using this repository for general high level issues that span -js and -native.

[nickidlugash]

I think we're going to have to do global placement instead of tiled placement

😄

how does this interact with the tiled needs of api-gl?

Would api-gl continue to use a placement system similar to what we have currently?

does api-gl need to have exactly the same label placement as dynamic gl maps?

Probably would be helpful to talk to support/customer success about customers that use both to see exactly how they use them. I think that most use cases of api-gl don't require the static map to look exactly like the dynamic map. One of the possible concerns might be that users design maps in Studio with a dynamic map preview, so if they are creating that style for use with api-gl they might see unexpected results. Similarly, we're developing a map design tool for showing lots of views of your map style at one time, which currently uses static maps as it's not performant to load so many gl maps on the same page. This workflow might create similar discrepancies.

how important is it to reduce the number of labels flickering in and out as you move the map?

I think this depends on how they behave. Labels flickering in and out seems like a necessary evil if we want to optimize display for our increasingly versatile camera and styling abilities. Personally I don't think it is in itself a bad thing, but I do find two things very jarring:

1. The lack of fading for rotated (and now, pitched) labels and labels across tiles.
2. Instances when the appearance/disappearance of a label is difficult to reason about – e.g, a label disappears when there appears to be plenty of room for it (sometimes because of inaccuracies in size/shape of collision box), or label jumps in and out of visibility multiple times over the course of one or two zoom levels (I think mainly due to cascading effects of other labels coming in).

It sounds like this new approach would improve at last parts of both of these points. @ansis can you speak more to either of these?

how important is it for the placement of a view to be deterministic? (in the sense that it doesn't depend on how the map got to where it is)

My gut reaction is that this doesn't matter much for dynamic maps, but that's an interesting question 🤔

[andrewharvey]

Probably would be helpful to talk to support/customer success about customers that use both to see exactly how they use them. I think that most use cases of api-gl don't require the static map to look exactly like the dynamic map. One of the possible concerns might be that users design maps in Studio with a dynamic map preview, so if they are creating that style for use with api-gl they might see unexpected results.

Most of the customers I've seen either use api-gl because:

1. they built their app on Leaflet/Mapbox.js and haven't yet been able to upgrade to GL JS but use Mapbox Studio for Styles, or
2. they use api-gl as a fallback where the browser/device doesn't work with GL JS

In some of these cases labelling is quite important (a label not showing up is a big deal so will spend a bit of time tweaking the label position manually and symbol properties to get it right in Studio) and discrepancies between Studio and api-gl would be an issue in some cases. Mostly it's only important for default pitch and bearing. Although there are already discrepancies between GL JS and api-gl labelling with labels being cut off tile borders which is an issue.

[nickidlugash]

@andrewharvey ohh, thanks for these insights 👍

---

Just throwing out another issue with our current system:

text-pitch-scaling (whether hardcoded or implemented as a style spec property) can't scale symbol-spacing accordingly, since the placement is only done once per zoom level.

[nickidlugash]

@ansis @ChrisLoer will we be able to improve labels along a line that have a text offset? E.g. if we have access to the full line geometry when calculating placement, can we offset the line first (and analyze text-max-angle against the offset line) and then place the glyphs along the offset line?

[ansis]

@nickidlugash yes! We should be able to improve:

• offset text at corners
• regular text at corners
• sharp angles / simplification

The main challenge is doing this fast enough and finding a tradeoff between speed and quality if we need to.

[nickidlugash]

Based on the work already happening in the viewport label placement branch, here's some potential further areas for label placement improvement that are high priority for the cartography team. Can we discuss/evaluate for feasibility? Some items have already been separated ticketed, and others I can ticket out later if they seem like things we want to pursue:

Variable text placement for point labels

https://github.com/mapbox/mapbox-gl-js/issues/5038

This is the ability for the renderer to assign different placements for a label in order to improve the likelihood that the label will be visible.

Add placement logic for a single centered line label

https://github.com/mapbox/mapbox-gl-js/issues/5061

While not directly affected by switching to viewport placement, I think this would be useful to consider now while we're refactoring label placement in general.

Labeling offset lines

Improving the appearance of offset lines has come up many times. We don't currently use any offset line label in our own Mapbox styles due to the rendering issues for curved/angled lines, but we would like to. As we discussed earlier in this ticket, more accurate rendering should be possible with the viewport placement refactor. @ansis @ChrisLoer any further thoughts on this now that the refactor is underway?

Cross fading for symbol layout property changes

I think cross fading symbols at zoom levels where there are symbol layout changes would greatly improve the appearance of symbols that have either large value differences, or multiple changes simultaneously. City labels in Mapbox Streets at zoom level 8 is a great example, where text-font, text-offset, text-anchor all change at once. In the next update of our Mapbox styles, we'll be adding additional placement directions (whether via variable text placement as mentioned above, or using data-defined placements) which will cause even more substantial placement jumps at z8, so the ability to cross fade will be even more helpful.

This was discussed briefly during the viewport placement refactor sprint. My understanding from that conversation was that since we are already implementing fading for symbols in general for all situations when they get shown/hidden, adding this capability should be fairly straight-forward.

Symbol spacing along lines that accounts for pitch

Right now, symbol spacing does not account for pitch (since anchor placement along a line only gets calculated once when a tile loads), so symbols along a line in the background are closer together (i.e. seem denser) than in the foreground. Ideally the spacing should appear about equal (you could argue that it should actually be less dense in the background, but I think we can separate that issue out from this, since the need to reduce density in the background in general also affects point placement labels). For our Mapbox styles, symbol spacing for pitched labels is most noticeably an issue for highway shields.

Based on previous conversations, it seems like the simplest way to reduce the density of symbols in the background is selectively hiding certain anchors based on pitch. This probably will also create more stable label placement than other options. I have concerns that this won't look seamless (the labels will look too dense, and at a certain pitch will switch to looking to sparse), but I think this is hard to evaluate without seeing it.

The only other options I can think of right now require either anchor placement or other functions in addFeature to be recalculated every pitch change. @ansis @ChrisLoer can you explain in more detail about the feasibility of doing this? Would you suggest just trying the simpler approach first and seeing if the results are acceptable?

Collision boxes for geometries

Not high priority right now. Sometimes it's not desirable to have symbols overlap specific geometries (e.g. admin boundaries). This was briefly discussed during the viewport placement refactor sprint, and seems technically feasible, but we should first see if we can gather enough compelling use cases for this.

/cc @ansis @ChrisLoer @mollymerp @mapbox/cartography-cats

[ChrisLoer]

@nickidlugash For handling symbol-spacing and pitch, maybe it would make sense to cut density based on "distance from the camera" instead of the overall pitch of the viewport? So for instance, highway shields in the near field would remain densely placed, but after reaching a certain distance the density would be cut in half (and maybe cut in half again in the far distance).

It would be nice to keep the underlying anchor placement calculation in the background if we can get away with it, both to keep the overall placement more stable and to save expensive calculation in the foreground.

[nickidlugash]

For handling symbol-spacing and pitch, maybe it would make sense to cut density based on "distance from the camera" instead of the overall pitch of the viewport?

@ChrisLoer Yep, sorry – this is what I had in mind based on our previous conversations, but didn't describe it well above. I'm not sure if the transitions at those certain distances will be jarring, but if this is straightforward to implement then I think it makes sense to try this approach first. Do you think it makes sense to incorporate this into the main viewport placement refactor branch, or to separate it out?

[ChrisLoer]

@nickidlugash I think that should be relatively straightforward, and I suspect it won't be that jarring in most real-world cases. I'll give it a try and if it's easy I'll roll it into the bigger changes.

[ChrisLoer]

Here's the status quo in a pitched view:

And here's after removing every other anchor if the anchors have a "perspective ratio" > 1.1 (i.e. they're at least somewhat in the distance).

This doesn't help at all for point-placed labels, which we use in Mapbox Streets below zoom level 11. We'd have to come up with some other solution to handle those in pitched views.

[nickidlugash]

Moving the discussion about symbol spacing/density reduction for pitched labels to it's own ticket: https://github.com/mapbox/mapbox-gl-js/issues/5086

/cc @ChrisLoer

[mb12]

@ansis and @ChrisLoer Is it possible to also add support for following kind of symbols as part of the re-write? It will be useful for feature parity with Google Maps and Apple Mapkit. @friedbunny also mentioned this the first time pitched support was added to native.

In the current implementation, in pitched mode, the size of the icons depends on its position in the viewport. It would be nice to have an icon-{property} that keeps the size of the icon same at all positions in the viewport irrespective of the map state.

[ChrisLoer]

Hi @mb12, that sounds like adding the properties text/icon-pitch-scaling. We decided not to implement them in the interest of simplicity, but we could re-visit the decision if we knew of some compelling use cases.

Although we don't plan to include an icon-pitch-scaling feature directly in the viewport/foreground collision detection changes, the changes will make it much easier to add customizable pitch-scaling in the future if we decide to.

[mb12]

@ChrisLoer The most conspicuous use cases I have noticed so far are the following:

1. ShieldSymbolizer is always the fixed size on Apple Maps as well as Nokia Maps.
2. All icons and text-size are the same size on Apple Maps (and Nokia Maps) irrespective of their position in pitched mode.
3. On Apple Maps, the font stroke seems to be a function of viewport. Text at the bottom is bold and turns regular as you move it towards the top of viewport.

Is it possible to expose text/pitch scaling value of 1 (perhaps at the style level) if not at the layer level?

Another common usecase is the pin dropped on long touch.

• Long touch drops a pin whose size remains the same even when the map is panned around.

[jfirebaugh]

Viewport collision detection landed! 🎉 Please open separate issues for any followup work that's not already tracked.