Add line-trim paint property to LineLayer

[Tagakov]

Design Proposal: Add trim-line paint property to LineLayer

Motivation

I have a route-line which is being erased by the car moving along it, the thing you can see in a navigator app.

Right now I'm updating the polyline geometry on every frame which seems to be a pretty CPU intensive and also require complex and hacky logic to not to thrash GC by mapping app's LatLon models to Maplibre's Point creating GC pressure and increasing memory footprint by storing two instances of the same polyline in memory.

I also tried to use line-gradient to set consumed part of the route to be transparent, but it changes discretely and doesn't let me to have a sharp cut or even a small fade-out cut which I'd be able to mask by rendering a car marker on top of it. It also has an issue where the length of the fading segment going from the polyline color to fully transparent seems to be depending on the polyline length and its distance from the poles.

In addition to that we also render congestions along the route and we either need to render them as a MultiLineString and update the whole geometry or have tens of LineLayer one per a congestion segment.

Proposed Change

Introduce line-trim paint property for the LineLayer which will can take values from 0 to 1 and from 0 to -1. Where:

• 0 - the whole polyline is visible (default)
• 1, -1 - the whole polyline is invisible
• 0.5 - second half of the polyline is visible
• -0.5 - first half of the polyline is visible (erased from the end)

The property should support expressions and data-driven styling, that will allow me to render all our congestion segments in a single LineLayer using MultiLineString and remap line-trim value passed to the actual lineTrim value for every element in MultiLineString. E.g. by setting 0.5 as line-trim to the LineLayer with all the congestions, using data-driven styling I'll be able to erase all MultiLineString elements that are before 0.5 point on my route and partially erase the segment that overlaps 0.5 point if any.

Mapbox already have something similar: https://docs.mapbox.com/android/maps/api/10.7.0/mapbox-maps-android/com.mapbox.maps.extension.style.layers.generated/-line-layer/line-trim-offset.html

The new property is expected to work only when lineMetrics set to true.

Implementation

To implement this behavior I suggest to introduce a new float32 vertex attribute (affecting all polylines) that will represent the progress along the polyline based on geodesic calculations. To do that we'd need:

• modify polyline_generator to reproject vertice positions of the polyline back to LatLon, calculate the length of given segments using harvestine for every line bucket.
• modify geojsonvt to change how mapbox_clip_start and mapbox_clip_end are being calculated, replacing euclidian distance by harvestine.
• introduce new paint property to linelayer

I am not sure how easy it is to add another GeoJsonOption similar to lineMetrics to be able to enable/disable this behavior, I'd suggest to only calculate harvestine distances when lineMetrics == true so the change will only affect lines where it is enabled.

API Modifications

Add new LineLayer paint-property. On android: PropertyFactory.lineTrim(0.5) or PropertyFactory.lineTrim(Expression.get("myProperty"))

Migration Plan and Compatibility

The change is backwards compatible.

Rejected Alternatives

• Use gradient to erase the polyline
  • Not accurate enough
  • The minimal change to the position of a gradient segment is to coarse
• Cut the polyline into smaller chunks and modify smaller geometries on every frame
  • Hard to implement even for a base case
  • Creates a lot of LineLayers
  • Can't be scaled with data-driven-styling

[louwers]

@Tagakov All the paint properties use kebab-case so we should stick with that?

The property should support expressions and data-driven styling, that will allow me to render all our congestion segments in a single LineLayer using MultiLineString and remap lineTrim value passed to the actual lineTrim value for every element in MultiLineString. E.g. by setting 0.5 as lineTrim to the LineLayer with all the congestions, using data-driven styling I'll be able to erase all MultiLineString elements that are before 0.5 point on my route and partially erase the segment that overlaps 0.5 point if any.

Could you clarify this a bit more? I am not sure I get it.

[Fabi755]

Rejected Alternatives
Cut the polyline into smaller chunks and modify smaller geometries on every frame

That's something I also tried in a draft PR for our navigation project already: RouteDrawer
And this feels more like a workaround.

So a lineTrim property would be very nice!! 👍

[HarelM]

You'd still need to update this property every frame, wouldn't you?
You would also need to calculate the "trim" number, which I think would also be GC intensive, wouldn't it?
I'm not sure what options there are for native, but for maplibre-gl-js you can use a custom layer to interact with the GL context for stuff that require more control over rendering, so you get a call for every render frame to do exactly this type of operations.

I also tried to use line-gradient to set consumed part of the route to be transparent, but it changes discretely and doesn't let me to have a sharp cut or even a small fade-out cut which I'd be able to mask by rendering a car marker on top of it

I'm curious as what exactly was the issue with this, and maybe focus on improving this feature instead of introducing something very similar in terms of behavior (i.e. I think line-gradient is a more powerful version of this proposal if I understand everything correct here).

For reference, here's an example of line-gradient used with line-progress:
https://maplibre.org/maplibre-gl-js/docs/examples/create-a-gradient-line-using-an-expression/

[Tagakov]

@louwers Of course, it's going to be line-trim, I was just too used to java api, sorry.

Sorry, I confused MultiLineString with FeatureCollection for this case, my bad, I think the confusion comes from there.

Using a single line-trim property to erase LineStrings in FeatureCollection

Goal

The data structure I'm displaying:

class Congestion(val fromIndex: Int, val toIndex: Int, level: LevelEnum)

class Route(
  val polyline: List<Point>,
  val congestions: List<Congestion>, 
  val progress: Float, //0..1
)

Every Congestion instance contains two indices pointing to the original polyline so if we have a route made out of four points: polyline = listOf(Point.fromLngLat(...), Point.fromLngLat(...), ...) and we want to display two congestions that span from route's 0 point to 1 and 2..3 we will have congestions = listOf(Congestion(0, 1, LevelEnum.HEAVY), Congestion(2, 3, LevelEnum.HEAVY)).

Although it is possible to display the route and its congestions using a single LineLayer and FeatureCollection we're going to assume that route and congestions are displayed in two distinct LineLayers and focus on the congestion's one.

First, we need to map our congestions to Features:

val congestionFeatures = congestions.map { congestion ->
    val properties = JsonObject()
    properties.add(
        "start",
        calculateFractionAlongLine(polyline, congestion.fromIndex)
    )

    properties.add(
        "end",
        calculateFractionAlongLine(polyline, congestion.toIndex)
    )

    Feature.fromGeometry(
        LineString.fromLngLats(
            polyline.subList(congestion.fromIndex, congestion.toIndex)
        ),
        properties
    )
}

source.setGeoJson(
    FeatureCollection.fromFeatures(congestionFeatures)    
)

calculateFractionAlongLine() function returns the fraction of the route represented by a passed index. So calculateFractionAlongLine(line, 0) == 0f and calculateFractionAlongLine(line, line.size) == 1f.

Now we need to create an expression that will remap our global route progress to the actual progress along the polyline in each feature in the feature collection.

//[
//  "let", "globalProgress", 0.5,
//  [
//    "/",
//    ["-", ["var", "globalProgress"], ["get", "start"]],
//    ["-", ["get", "end"], ["get", "start"]]
//  ]
//]
layer.setProperties(
    PropertyFactory.lineTrim(
        let(
            literal("globalProgress"), literal(0.5),
            division(
                subtract(
                    `var`("globalProgress"),
                    get("start")
                ),
                subtract(
                    get("end"),
                    get("start")
                ),
            )
        )
    )
)

That way for every feature in the collection the global progress will be mapped to its own local progress. I omitted the clamping of the local progress for clarity.

With this approach when erasing the polyline we only need to update line-trim property.

[Tagakov]

@HarelM

You'd still need to update this property every frame, wouldn't you?

Yes I'll need to update the property every frame but it is a relatively cheap compared to copying the whole (albeit evershrinking) route geometry on every frame.

You would also need to calculate the "trim" number, which I think would also be GC intensive, wouldn't it?

No it is a cheap operation. I calculate the real trim based on real geo-position every 5 sec when backend sends me a new location and then animate it for the 5 sec to have smooth position update. Both animation and real trim calculation are cheap.

I'm not sure what options there are for native, but for maplibre-gl-js you can use a custom layer to interact with the GL context for stuff that require more control over rendering, so you get a call for every render frame to do exactly this type of operations.

Not sure what you've meant here, can you clarify? AFAIK it is not possible to change polyline shader or get the access to maplibre's internal polyline representation so I can't mutate it throwing away erased parts and mutating the start point of the polyline.

I'm curious as what exactly was the issue with this, and maybe focus on improving this feature instead of introducing something very similar in terms of behavior (i.e. I think line-gradient is a more powerful version of this proposal if I understand everything correct here).

There are two issues, here, the first one can be fixed, the second AFAIU can't:

The gradient points are not accurate

You can check that by setting your gradient to be:

const EPS = 1e-4;

const lineGradient = [
  'interpolate', ['linear'], ['line-progress'],
  0.0, '#000000',
  0.5 - EPS, '#000000',
  0.5, '#FFFFFF', // we expect the middle of the polyline to have a narrow white band
  0.5 + EPS, '#000000',
  1.0, '#000000'
];

You can later construct a polyline out of a midpoint and display both the polyline and a marker at the midpoint to check how far the gradient's white part is from the actual middle of the line:

//I suggest to use a midpoint closer to a pole, e.g. [-87.70945, 41.87023]
function buildPolyline(midPointLngLat /* [lng, lat] */) {
  const pMid = point(midPointLngLat);

  const pA = destination(pMid, 100, 135, { units: 'kilometers' });  // 90 + 45
  const pB = destination(pMid, 100, -45, { units: 'kilometers' });

  return {
    type: 'Feature',
    properties: {},
    geometry: {
      type: 'LineString',
      coordinates: [
        pA.geometry.coordinates,
        midPointLngLat,
        pB.geometry.coordinates
      ]
    }
  };
}

After doing that you will see that:

• The gradient's middle point is significantly off the actual midpoint, I believe it can be fixed by using the geodesic progress I propose in this issue.
• The white band of the gradient will span hundreds of meters on larger zooms. Meaning that your "cut" of the polyline will always be feathered and the length of the falloff from the actual polyline color to the transparent color will depend on polyline length and its position on the globe. I believe it can't be fixed due to how the gradient is rendered, but I am not 100% sure.

The gradient property can't use data-driven styling

I believe it is a fundamental limitation of how gradient is being rendered and can't be changed. Look at the comment above where I explain how line-trim can be used to trim multiple features in a FeatureCollection at once.

I'd prefer to improve gradient's accuracy so it will be closer to real geo-positions and leave other issues as is. The accuracy fix AFAIK we should get for free out of more accurate line progress calculations.

[HarelM]

I'm not sure I got a good answer to my question:
Assuming we can improve line-gradient to be data-driven by supporting this (accepted?) proposal and probably some missing implementation:

• Design Proposal: Allow creating arrays with expressions #950

And solve some of the bugs described here, do we still need additional spec property to facilitate this feature request?

Or in short, can line-trim be described by line-gradient without the need to introduce a new style-spec property?
If not, I'll be happy to understand why.

[CommanderStorm]

How about this usecase:

Can this be described by the gradient? Yes
Is this harder for style authors? Also yes
Is the [-1, 1] solution very ergonmomic? 🤷🏻‍♂️ not sure, a bit akward for this usecase

Style authors commonly don't have a lot of control of how such tiny parts of the data works.

[Tagakov]

@HarelM

First of all: I do agree that the gradient API is perfect for the task, and I'd prefer to rely on it instead of line-trim since it provides a very flexible api that, for example, supports the @CommanderStorm's case (if I got it correctly). I am not concerned with the complexity of using gradient compared to the line-trim approach for authors, I think it is reasonably simple given the mentioned flexibility gains.

But I don't believe the issues I mentioned can be solved and need some input from experienced graphics-oriented folks here :)

To reiterate on what I said about line-gradient before:

• Gradient points are not accurate
  • The proposed change to v_lineprogress calculation should fix this
• Gradient can't produce narrow transition between colors on big zoom levels, the transition spans hundreds of pixels at zoom 15-ish
  • I am not sure if it can be fixed, but maybe there is some GPU trick I don't know about. (I don't know a single one)
• Gradient do not support data-driven styling
  • As far as I understand the proposal you mentioned won't help with this and trying to make it work will have a significant perf-hit (needs verification by an expert)

In addition to the above it is theoretically possible to make line-trim property to work with dashed lines, although the dashed line is not rendered correctly if lineMetrics: true. So it will need additional investigation.

Now let me explain why I don't think the issues can't be solved:

Gradient do not support data-driven styling

As far as I understand a single gradient texture with a fixed length is being generated when the gradient is set and then being sampled by GPU to set the correct color to a pixel of the polyline. If LineLayer has multiple features the same single texture is used to paint all of them.

So that means that to support data-driven styling we will need to create a texture not per layer, but per feature. Also any time when data-driven expression change we will need to regenerate and reupload the texture to the GPU. Naively it seems like a very costly change to make.

If someone can help us to verify my hypothesis that would be great!

Gradient transitions can't be narrow on big zooms

I think it is a fundamental limitation of how zoom and gradient texture sampling work together. The GPU uses interpolated v_lineprogress and on big zoom levels the difference between v_lineprogress for adjacent pixels in fragment shader is tiny which leads to this wide transition between gradient colors even if user specifies the transition to be practically instant.

---

Anyway even if we can try to fix the latter, the data-driven support is my main concern, can someone verify can we support that for gradient property?

[Tagakov]

@CommanderStorm

If I get your use-case correctly you want to "punch" gaps in your polyline so it will look nice on intersections with other lines. Unfortunately the proposed api, or the one from the mapbox won't help here in general case, because it doesn't support multiple cuts per line, so the gradient or splitting the geometry of the polyline to introduce gaps would be the only options AFAICT.

[HarelM]

@mwilsnd can you comment on the above in regards to the possibility and performance from a graphic oriented perspective?

[mwilsnd]

I'm not able to think of any readily apparent issues from the line-trim approach. Such a property would most easily be implemented at the shader level by a simple discard operation. I'd expect most of the performance complexity to come from updating all the line segments in the layer on the CPU side, but you're only paying that price when you use the feature presumably. Not everyone may want a sharp cutoff though so I might also consider adding some kind of falloff parameter to slightly smooth out the cut for certain use cases.

Line gradients do all share the same texture per layer. In theory it could be possible to support multiple textures for a single line gradient layer. You'd need more bookkeeping logic and it would probably be better to place a limit on the maximum number of unique textures per layer for performance and memory reasons. That said, an unbounded texture approach might be possible with the specific texture used being data driven. Lines would need to be further segmented by the texture being sampled, so a layer which switches textures frequently could certainly take a big performance hit, but used with those limitations in mind you could do some interesting things for sure.

[Tagakov]

@mwilsnd @HarelM

So what we would need to do:

• add more precise (f32) vertex shader attribute, since it is a prerequisite for accurate gradient fractions
• change the existing logic from having a texture per layer to multiple textures per layer
• introduce some limit so it will work for some simple-ish geometries and will not for more complex ones, without that limitation being reflected in the API and only in documentation
• accept the fact that a user can invalidate all their gradient textures on every zoom change (as the worst case scenario)

In comparison to:

• add more precise (f32) vertex shader attribute

I think it is a wrong direction to go, because it introduces a new, hidden API contract where the one can have fully valid code that silently hits some internal limitations and crashes/not-rendering. I think this kind of limitations need to be clearly defined in the API, for example right now similar behavior can be achieved by creating multiple LineLayer's each with its own gradient texture, yes that won't support data-driven, but at least the cost would be clear, since it forces user to create multiple relatively expensive entities (LineLayers).

This approach also eliminates all the perf wins I described in FeatureCollection approach making it effectively the same as having a LineLayer per congestion segment.

In addition to that it significantly increases the proposal scope. Is there a way I can convince you to support the original approach?

---

@mwilsnd Can you please comment on the long transitions of gradient color? So if I set gradient like

[
  [0, Transparent],
  [0.5, Transparent],
  [0.5000001, Red],
  [1, Red],
]

The transition between transparent and red is long and depends on zoom and polyline length. Why does it happen, can it be fixed given that we use 1d texture of limited length?

[HarelM]

In theory, as I said, I believe you can use a custom layer of some sort.
The main problem I have with this proposal is that you are saying the following:
We have something that is not working as expected and have issues and limitations, so let's avoid fixing the issues there and have another one that is not buggy and simpler.
From a spec perspective, that's a real problem, because both will need to be maintained and it will create confusion for users, which I would like to avoid as much as possible.
I tend to say that if line-gradient was solving the problem for most cases and supported all what you needed, but you still get to a situation where the implementation can't solve your problem (not a theoretical one that a user might get into in the future but is likely not to happen) then I think we should evaluate what our options are at this point.
But I don't think we are at this point right now...
I'm sorry this is not the answer you wanted to hear... :-/

[louwers]

Judging by the amount of upvotes this proposal has received in a short amount of time, that this problem comes up again and again for our navigation users, and the fact that Mapbox has implemented something similar, I think there is a real need for this functionality and it is not just a theoretical problem.

Custom layers are not cross platform, brittle, hard to distribute and do not hook into existing source loading and rendering machinery. It is not a desirable or even feasible solution in my opinion.

I agree that we should prefer fixing or improving the performance of existing style spec properties over introducing new ones. The questions is, is that possible in this case? I think @Tagakov makes a good case that it's not.