@ChrisLoer, @kkaefer and I talked about making large changes to text rendering and label placement.
Problems
current problems:
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:
- Project the line into the plane you want to put the text on (map plane, viewport plane)
- Iterate along the line to find a point the correct distance along the line.
- Offset the corner of the glyph from this point on the line.
- 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.
@ChrisLoer, @kkaefer and I talked about making large changes to text rendering and label placement.
Problems
current problems:
text-pitch-scalingfuture problems:
Labelling has two subproblems:
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-alignmentwas added to make labels more legible in pitched views. @ChrisLoer's recent work improves on this. Both of thesetext-pitch-alignmentimplementations 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:
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:
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:
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:
text-pitch-alignmentproperlyThe 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:
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.