using straight skeletons to render strokes, tint bands and antialiasing

Nobody has claimed this yet.

There are a bunch of long-standing feature requests and bugs that boil down to the same problem: knowing the correct distance to a line or polygon. These include shadows, inner-glow, tint bands (https://github.com/mapbox/mapbox-gl-js/issues/769), fill strokes (https://github.com/mapbox/mapbox-gl-js/issues/4087), polygon antialiasing (https://github.com/mapbox/mapbox-gl-js/issues/2080), translucent line rendering artifacts (https://github.com/mapbox/mapbox-gl-js/issues/4824 , https://github.com/mapbox/mapbox-gl-js/issues/794), and line-offset artifacts (https://github.com/mapbox/mapbox-gl-js/issues/3809).

So far, signed distance fields have been the proposed solution. The idea is to create a raster signed distance field and a buffered triangulation for each feature. The texture coordinates would be stored for each vertex and passed to the fragment shader which would read the signed distance from the texture.

I’ve been experimenting with a similar solution that avoids the need for a raster signed distance field for each feature. If we can construct a tessellation where a) no two triangles overlap, and b) all the fragments within a single triangle are closest to the same edge, then we can store the signed distance directly on each vertex and use built in interpolation to get the distance for each fragment.

Here’s what the tessellation looks like:

Rendering the signed distance:

Rendering an antialiased outline and a fill in a single draw call:

Using the same tessellation to render buffered polygons with no double drawing:

and shrunk polygons:

insets:

no examples yet for: shadows, inset patterns (for example, the [water here](http://mike.teczno.com/img/hachure/hachures-example.png))

### Signed distance tessellation vs signed distance fields
- signed distance tessellation has a smaller memory footprint than signed distance fields because they don’t need a ton of textures
- signed distance tessellation doesn’t need texture lookups
- signed distance tessellation could avoid overdraw from shading transparent fragments
- signed distance tessellation could have better sub pixel accuracy
- signed distance tessellations could be harder to generate correctly than signed distance fields. And maybe more expensive, but maybe not.
- handling degenerate polygons could be harder with signed distance tessellations
- geometries used for signed distance fields would still need to be buffered so that outlines can be rendered. This is part of the core implementation of signed distance tessellation.

### Straight skeletons

Creating this tessellation is mostly a matter of finding the [straight skeleton](https://en.wikipedia.org/wiki/Straight_skeleton) of the geometry (thanks @anandthakker for pointing me in the right direction). [This paper](http://www.dma.fi.upm.es/personal/mabellanas/tfcs/skeleton/html/documentacion/Straight%20Skeletons%20Implementation.pdf) provides an algorithm for generating straight skeletons.

The distances produced by a straight skeleton are a bit different than a regular signed distance field. In a straight skeleton, reflex corners produce miters. In a signed distance field, reflex corners produce a round join. Miters are great, but not always the right choice.

The algorithm would need to be extended to support round and bevelled corners. Both should be doable while sticking to the core straight skeleton algorithm. For bevels, the general idea would be to add zero-length line segments in the middle of sharp corners. Circles could be faked in a similar way by adding multiple “pie slice” triangles to fake roundness. We currently use this approach for round line joins. I think true round corners might be possible but that's harder.

The algorithm also needs to be tweaked to handle:
- extending the skeleton outward from the geometry
- lines instead of polygons
- self-intersecting lines

(scattered thoughts on a signed distance tessellation with true round corners)

I realize this probably isn't very coherent: Introducing round corners adds curves to the produced skeleton. Curves are probably a lot harder and more expensive to work with. We also can't triangulate them. But the curves in the skeleton can only happen when a round corner extends and hits a straight edge. When circles extend and hit circles the boundary between them is straight. And edges extending to hit edges are straight as well. We could produce a skeleton with straight segments where each pixel within a polygon could be nearer to a round corner or an edge. We could encode both into the vertex and have the fragment shader determine which is closer at render time. This would avoid dealing with calculating the curved boundaries. I'm not sure, but I think it might be possible to extend the skeleton algorithm to handle this.

### Algorithm performance

The biggest open question is whether we could generate these skeletons fast enough. I don’t know. We’d need to invest serious effort into implementing this before we could know. I’m optimistic.

The basic straight skeleton algorithm is `O(nm + n log n)` where `n` is the number of vertices and `m` is the number of reflex vertices. Handling convex polygons is cheap. It’s the concaveness that becomes expensive because you need to search for intersections with opposite edges.

But we have an advantage: we don’t really need a complete straight skeleton. All we need is a straight skeleton for a small area close to the edge of the geometry. We only need the skeleton for the area covered by the outline or shadow or inset. This makes finding the opposite edges much cheaper because we can use a grid index to get only the nearby edges. I think this would cut the algorithm down to something like `O(n * k^2)` where `k` is the width of the outline/inset/shadow.

The center part of the polygons not reached by the skeleton would be triangulated with earcut. This means we only need the slower skeleton tessellation for new features (outline, inset, shadow). Existing maps would not suffer a performance hit.

skeleton limited to nearest 40px:

signed distance rendering:

### Vertex format

If we want to avoid shading extra transparent fragments we can use a point + extrusion approach. This might look something like:

```
4 bytes x, y pos
2 bytes extrusion x, y
1 byte signed distance at x, y
1 byte max extrusion length
```

### Conclusion

Signed distance tessellations can be used to render outlines, antialiasing, insets, offset lines and shadows. The big question is whether we can calculate the tessellation fast enough. I think it might be possible.

My very messy and slow implementation used to generate the skeletons, tessellation and examples: https://github.com/mapbox/mapbox-gl-js/tree/signed-distance-tessellation

Possible next steps:
- experimentation with bevels and round joins to see if there are any pitfalls there
- start on a more optimized and careful implementation that we can benchmark

@mapbox/gl-core

Start with the signed-distance-tessellation branch and its straight-skeleton implementation, then review the proposed limitations for bevels, round joins, lines, and self-intersections. Benchmark an optimized implementation and verify the listed rendering cases before treating the work as done; the issue names no specific tests or files.

Written by the indexing model from the issue text.