Support user-specified feature z-indexing / sorting across layers

[nickidlugash]

In Mapnik, group rendering is used to render roads in the correct z-order. For background: @kkaefer's PR. This grouping is declared in Mapbox Studio projects in the yml:

_properties: 
  bridge: 
    "group-by": layer

We are currently ignoring the z-ordering, which is affecting mainly the bridges layers:

What would it take to implement something like this in GL? What would be the performance implications? I'm assuming this also requires a style-spec change. A group-by property would need to be defined by data layer, though, not by style layer.

/cc @kkaefer @ansis @1ec5 @jfirebaugh @mourner @ajashton

[ansis]

Currently: Style layers are the main thing that define draw order. Within a style layer, features are drawn in the order they appear in the data.

We could implement a group-by that sorts features within a style layer fairly easily. This would let you draw layer=3 roads above layer=2 roads that are in the same layer. But not within different layers.

To make it work across different classes of roads (main, motorway, etc) I think we'd need to draw all roads with one style layer. To make this possible, we would need to support functions that are both data-driven and dependent on zoom level. line-width needs to be different for each class and needs to change as you zoom.

---

Other approaches I think would not work well:

Another way to implement this would be to split layers into many sublayers. Imagine if you made a separate style layer for each layer value and then arranged them in the right order. We could add something that magically does this behind the scenes, but I'm worried that this approach would create too many internal layers that need to be drawn. This would be per-feature z-index and that scares me.

Or we could use the depth buffer. Each feature would have a z value partially based on the layer property. When drawing later features, pixels would be dropped if they are on top of something else that was drawn before with a higher z value. This would not work for semi-transparent features and near antialiased edges because with this approach you can only choose to not draw a pixel. You can't choose to blend it below a previously drawn value.

---

How important is this? In https://github.com/mapbox/mapbox-gl-custom-styles/issues/129 Emerald's ordering looks ok in this case. I'm sure it breaks in other cases, but if those cases are rare enough it should be ok

[1ec5]

It isn't terribly rare. Sometimes surface streets pass over highways, sometime under. Usually you can rely on one or the other being a bridge or tunnel, but that assumption breaks in urban areas. In my example, there happened to be a river beneath both roads. But cities often have things like double-decker bridges or complex highway interchanges that involve multiply stacked bridges.

The good news is that if one motorway bridge overlaps another, the two bridges receive a common casing. As long as no one wants to case the bridges individually, as in the openstreetmap-carto style, the main fallout is just the inconsistent over/underlapping in the screenshot above.

[jfirebaugh]

See #733 for a report of the issue in the wild.

[nickidlugash]

@ansis @1ec5 thanks for the feedback. I talked to @ajashton about this, and as a temporary solution to this, we can try adding a few strategic additional style layers to help alleviate some of the most common cases of incorrect overlapping. We can split up a few of the bridges classes into different layers by additionally filtering on the layer field. The two questions are:

1. Is it enough to have two style layers for a class, one with layer<=1 and one with layer>=2, or do we need to split it out even further (layer<=1, layer=2, layer>=3)?
2. Since style layers are filtered by class, which classes contain the most features with layer>=2?

We took a quick look at taginfo. Roughly 2.5% of highways have a layer tag. About 95% of layer values are -1, 0, and 1 (most roads on the ground are 0, most bridges are 1 and most tunnel are -1, so all these are ordered correctly since we split up the roads into tunnels, roads, and bridges. Roughly 0.055% of highways have layer=2, which translates to roughly 47,000 incidents of incorrect overlapping (assuming that any road with layer>2 is already overlapping a road with layer=2, which is usually but not always true). Of those 47,000 incidents, roughly 9,000 also include roads with layer>2, so filtering for layer>=2 only would fix about 38,000 overlaps and not fix about 9000.

These are super rough figures, since I'm generalizing from the breakdown of layer values overall, and not specifically for highways. Also, we cannot tell the breakdown of highway classes by layer value with this information. I did a quick visual scan in the editor, and although it looks like most of the highways with layer>=2 are motorways, motorway_links, and minor_rails, there are also quite a few main, street, street_limited, and major_rails.

@ajashton is going to a bit of postgis querying to get more accurate info. My sense is that we are not going to be able to cover the majority of cases without creating a bunch of additional style layers – but even adding a few layers will be better than nothing, and we can implement that in the styles right away without any rendering or style spec changes.

Regarding possible longer-term solutions:

We could implement a group-by that sorts features within a style layer fairly easily. This would let you draw layer=3 roads above layer=2 roads that are in the same layer. But not within different layers.

@ansis would it also be straightforward to sort features by multiple fields? E.g. sort first by layer, and then by class? I think we would need this in order to still let users control the ordering by class.

To make this possible, we would need to support functions that are both data-driven and dependent on zoom level.

In general we need to implement this in order to use data-driven styles for most basemap styling. Is this going to be something we consider doing?

[1ec5]

Roughly 2.5% of highways have a layer tag.

If I’m not mistaken, this is probably because JOSM issues a strict “Crossing ways” validator warning for bridges and tunnels without layer tags, so some mappers have been quite vigilant about applying layer everywhere.

47,000 incidents of incorrect overlapping

This looks like a big number, but it’s mitigated somewhat in the styles in mapbox/mapbox-gl-styles because individual bridges don’t receive casing that would cut across overlapping bridges. It could be more prominent in other styles, though.

[nickidlugash]

This is a stretch, but if we did implement group-by for style layers, and functions that are both data-dependent and zoom-dependent, we could maybe keep all roads in one data layer instead of splitting them out, since they would be z-ordered, and you could implement the differences in style between tunnels, bridges, and roads with data-driven styling. Although it initially seems crazy to have so much complexity in a single style layer, the more I think about it, the more this seems way simpler than having 30–60 style layers to style one system of related features. And this is clearer translation of how one might design a styling system for related features in the first place.

[nickidlugash]

This looks like a big number, but it’s mitigated somewhat in the styles in mapbox/mapbox-gl-styles because individual bridges don’t receive casing that would cut across overlapping bridges. It could be more prominent in other styles, though.

Yeah, I think in a lot of cases (like in the Boston example) the result is often just roads that look like they're intersecting when actually one is going above the other.

[kkaefer]

we could maybe keep all roads in one data layer instead of splitting them out, since they would be z-ordered

This is also the way we should use OpenGL rendering; adding 30-60 style layers will produce more draw calls which will ultimately make rendering slower.

[stirringhalo]

What are the current thoughts on adding "group-by"?

[lucaswoj]

@stirringhalo Nothing beyond what's posted here. We're hoping that data-driven styling will reduce the need for this feature.

[stirringhalo]

@lucaswoj Sounds good, I'm following your data-driven property functions for line attributes. Excited to start using that.

[lucaswoj]

There are no blockers left to implementing this! We have zoom-and-property functions now.

[ryanbaumann]

Here's an example of how to achieve z-order control in one layer with data-driven styles and geojson source types. The order of features in a geojson FeatureCollection Features array controls the draw-order.

http://bl.ocks.org/ryanbaumann/e5cd12a01ef72ab620a2a58b71b1aa6b/38d6cdb6fe1ca54b17ed30dc8db77fb550a99d3d

Without z-indexing this is method does not help with vector tile sources.

[anandthakker]

Closing as a duplicate of #4361 (since that issue has a more concrete proposal)

[nickidlugash]

I believe this is not a duplicate, as this feature is required across a data layer, not just a single style layer. Some of the needs for this feature could be partially alleviated by #4361 though.

[chloekraw]

@nickidlugash - I'm not sure I follow the distinction between sorting across a data layer vs. a style layer -- could you say more?

It sounds like if tunnels, roads, and bridges are already tagged with a layer number (#1349 (comment)), and you could render all of those features in a single layer styled with DDS (#1349 (comment)), then you could use the existing layer tags to populate the line-sort-key values for features in the "roads/tunnels/bridges" layer to sort all of the features correctly.

I do see your request for sorting by class as a separate feature request distinct from sort-key. I'm assuming this would require sorting across multiple layers, correct?

cc/ @ajashton

[1ec5]

Roughly 2.5% of highways have a layer tag.

If I’m not mistaken, this is probably because JOSM issues a strict “Crossing ways” validator warning for bridges and tunnels without layer tags, so some mappers have been quite vigilant about applying layer everywhere.

Since I wrote that, iD started adding layer=1 tags to bridges by default in openstreetmap/iD#3911, so now 85.58% of bridges have layer tags, whereas the percentage of highways with layer tags has decreased to 2.37%.

I do see your request for sorting by class as a separate feature request distinct from sort-key. I'm assuming this would require sorting across multiple layers, correct?

Consider that a style might generally render motorways above residential roads (based on importance) but would make exceptions for residential overpasses over motorways. Perhaps that would be feasible with #4361 as long as the line-sort-key property can simultaneously refer to two properties (for example, corresponding to the highway and layer tags in OSM).

[nickidlugash]

It sounds like if tunnels, roads, and bridges are already tagged with a layer number (#1349 (comment)), and you could render all of those features in a single layer styled with DDS (#1349 (comment)), then you could use the existing layer tags to populate the line-sort-key values for features in the "roads/tunnels/bridges" layer to sort all of the features correctly.

@chloekraw We commonly use a styling technique that uses road "casings" underneath the main road lines to visually indicate the grade separation (denoted by the structure and layer fields). I don't think we can create this styling with a sort feature that only sorts within a single style layer, because the casings would still need to be in a separate style layer.

Aside from this, there are other reasons why it is currently difficult to combine all roads into one style layer:

1. Not all style properties are DDS-supported. (Simplifying road styling is the main reason I've been pushing so hard to get line-dasharray and line-cap supported). This limitation can be solved by supported these style properties.

2. Not all road features are styled as lines – some are fills, some symbols, some circles – and so they cannot be combined into a single style layer. All these road features styled by different style layer types still need to be sorted together. This seems like a much harder limitation, which I'm not sure how we would get around without major refactoring. A relatively simple style that doesn't require fills or symbols could avoid this limitation.