Reinventing line joins
I’ve been working on Gleo for months now. When I started with it, I was pretty sure I had to reinvent big chunks of a vector rendering pipeline, come with terms with the idiosincrasies of WebGL, and challenge preconceptions from the GIS world.
However, I did not foresee I had to rethink freakin’ line joins.
Drawing lines (or rather, linestrings) in WebGL is a surprisingly hard subject: Whereas 2D drawing APIs implement line joins and line ends, WebGL does nothing of the sort, and the labour of doing so is passed on to the developer.
There are three classic (i.e. “implemented by 2D drawing APIs”) kinds of line joins: miter (inglete), bevel (chaflán), and round. These are only noticeable when looking at them very very closely, or when using very thick lines:
A miter join looks the worst for acute angles, but is the simplest to achieve: just two triangles per segment, and just two vertices per point of the linestring. Those two (WebGL) vertices are extruded from the (linestring) point, in the direction of the normal of the join (which is the same as the sum of the unit normals of each of the segments involved in the join), and by a magnitude equal to (half) the width of the line divided by the cosine of the angle between the join normal and any of the segment normals (whidh equals half the angle of the join). Easy, huh?
Implementation is fairly straightforward. I’m writing Gleo with my fresh set of constraints, so my implementation assumes a constant number of vertices and triangles needed for a given stroke symbol no matter the cartographic projection of the linestring. This leads to some…. “interesting” edge cases.
Since I’m looking at all these problems with fresh eyes, I decided that it’d be a good idea to build miter joins with an extra triangle, having three (WebGL) vertices per (linestring) point. The well-established way of doing bevel joins in 2D APIs is extruding the exterior vertices of the joins along the normal of each segment, by a magnitude of (half) the width of the line.
An implementation is kinda straightforward. As with classic bevels, the area covered by the join is less than any of the other options.
I’ve added some circles to each linestring point to illustrate something that bothers me: the vertices are on a circumference of diameter equal to the line width, and the outer edge of the bevel triangle is fully inside such a circle.
Why does this bother me? Because besides lies, I’m using the extrusion code for heatmap-style scalar fields, and the fall-off of the field along the bevel is way off:
What could be done to alleviate this? Well, implementing “round” line joins would be ideal, but that may involve either a complex WebGL fragment shader (which would need to compute distances, and quickly risks becoming a GPU hog), or a constant number of additional vertices and triangles (because Gleo assumes that any cartographic symbol will use the same amount of vertices and triangles no matter the cartographic projection of the geometry.
One of the assumptions that was helping me keep control of WebGL vertices and triangles, that assumption that symbols always need the same amount of vertices, was getting some revenge on me. Damn.
So one option was to add more vertices. I dubbed this the “tent” and “dome” joins:
The whole idea being more vertices on the circumference, equally spaced. Which seemed simple until I realized the trigonometric calculations could be done based on unit vectors intead of using trigonometric functions, potentially being faster.
I’ve been pondering on this problem for a while. Also, it’d be possible to tweak the behaviour of line joins via the fragment shader via the miter implementation, but it’s hard to minimize the amount of fragments (AKA “WebGL pixels”) to be ignored in the case of very acute angles.
And then it struck on me: I can do bevels on the outer side of the circle.
The problem is offsetting the vertex extrusion by the right amount. It’s no longer the unit segment normal times (half) the width, but rather one has to take the segment unit normal (“A”), draw a normal line that intersects it; do the same for the join normal (“B”), find the intersection between those two.
I spent way too much time thinking about the problem before realising that the extrusion is the segment unit normal plus the join unit normal multiplied by the tangent of the angle between segment and join normal; all of that multiplied by (half) the stroke width.
And, at last, my bevels were encompassing the area of the round joins:
The area should be better now, and with this newly gained knowledge it should be easier to design a triangulation and fragment shader to do round joins. In any case the area of the join feels better, and the GPU doesn’t do any extra work (since the extrusion is performed only once on the CPU when the stroke symbol is instantiated).
Plus, I can do an animated comparison of both the inner and outer bevels which looks nice:
I don’t know if the “tent” and “dome” joins are needed anymore. But having this extra line join will surely get me in some nitpicky fights with the people who know more semiology than me.