Efficient WebGL stroking

While working on WebGL rendering you soon realize that a canvas like API, despite its opinionated implementation, is extremely useful and easy to work with. Concretely, I am referring to its stroking capabilities. While making a stroke WebGL implementation I came up with the following solution, which requires very simple maths, is fast, and can be implemented just from 2d vectors.

The Canvas API offers support for plenty of cool stuff like line width, line cap and line join value, etc. and so will we. Here’s an example of the implementation:

Efficient WebGL stroking live demo:

https://hypertolosana.github.io/efficient-webgl-stroking/index.html

• Check ‘show lines’ to see the internally calculated anchors and vectors to setup the tessellation.
• The red points, and the green arrows can be dragged to see live results.
• ‘Draw with canvas’ is enabled so that the calculated triangles will be over-imposed for visual comparison between the algorithm and the canvas API.
• Select different line caps and join values.
• The pink line (substracted intersection point from center point) will disappear when the angle is too narrow to base the tessellation in the intersection point. Note that not always exists an intersection point.

For the implementation to work, a vector of Points and some line attributes are necessary. These points should define a poly-line which is a contour we want to have tessellated. In Cocos2d-html5 v4 we have a general purpose Path class, which classifies its segments in contours, and could be a good starting point if nothing else is around.

First steps, just stroke the poly-line

If we went to create quads for each line segment of our contour, we would end up with wrong results, where too much overdraw, and no fancy corners are gotten as a result. To avoid this, the supplied data must be a bit preprocessed if smooth line join and closed contours showing correctly a requirement. Specifically, we want to split our contour segments (but the first and last one) into two different segments by creating a new middle point.
This is the result of an straighforward algorithm that will create a straight line every two points, thus, for each 3 points, we’ll get two straight line segments.

Data setup will be as follows:

  var i;

  for ( i = 0; i < points.length - 1; i++) {
    if ( i===0 ) {
      midp.push( points[0] );
    } else if ( i===points.length-2 ) {
      midp.push( points[points.length-1] )
    } else {
      midp.push( Point.Middle(points[i], points[i + 1]) );
    }
  }

  // for every middle point, create all necessary triangles for the two segments is represents.
  for ( i = 1; i < mids.length; i++) {
    createTriangles( 
      midp[i - 1], 
      points[i], 
      midp[i], 
      resulting_array_of_points, 
      lineWidth,
      join, 
      cap, 
      miterLimit );
  }

Second, we must calculate the correct line width based on the current transformation matrix. To do so, we create two vectors: Vector( 0, 0 ) and Vector( lineWidth, 0 ) both of which will be transformed by the current transformation matrix. the module of the resulting vector between both transformed points will be our actual line width:

  var v0= new Vector();
  var v1= new Vector(lineWidth, 0);
  currentMatrix.transformPoint( v0 );
  currentMatrix.transformPoint( v1 );

  lineWidth= Vector.sub( v0, v1 ).getModule();

The result from stroking 3 points at (100,100), (300,100), and (300,300) with a line width of 80, and assuming an identity transformation matrix would be the following:

And for 4 points at (100,100), (300,100), (300,300), and (100,300) we’d get the following:

In this example the resuting triangles include a filler triangle for the union of both segments, corresponding to a “bevel” type line join.
Importatnt to note that in the examples, with 3 points there’s no mid point created, but there’s one with 4 points, leading to two 3-point (or two line segment) tessellation blocks. More points will create more mid points.

But how’s all this calculated ?

From each line segment, a vector is calculated (blue), and normal vectors with the size of half the line width are created too (green). From the segment points (red circles), these normal vectors are added, creating 6 new points, which will be the pointers of the green arrows.
Between each 2 of the external newly created points, a line will be traced (red). The intersection point of the two red lines and the subtraction of the middle point and the middle point are very important (blue dots). If the lines do not cross, the segments are parallel, and the tessellation is straightforward, just create the two triangles that compose it.

With the segment points, the ‘bottom’ blue point, and the calculated normal points for the line segments, we can already simply tessellate the segment. The result will be the one we have in the previous images.

For example, the first tessellated triangle would be: (p0+t0), (p0-t0), (p1+anchor), being:

• p0, p1: the first two line segment points. (red dots)
• t0: the external perpendicular vector to each p0 and p1 (light red arrow)
• anchor: the vector resulting from subtracting the intersection point from the last (p1) line segment point.

And another one would be: (p0+t0), (p1+t0), (p1+anchor)

It is just a matter of continuing dividing the space for the rest of the points.

My two lines do not intersect

Sometimes there’s no intersection point (red lines). In this case, or when the angle between the two segments is very narrow (the vector from center point to the intersection, which is magenta in the playground, is bigger than any of the segments) the algorithm switches to a different way of tessellation, since otherwise, that would be a failed case. Since there’s no intersection point, some elements like the miter must be calculated differently.

Line Joins

Line joins are the tessellation between every two line segments. The most basic one would be a bevel line join, which is trivial a single triangle whose tessellation information is already available:

A round needs to draw with center at p1 (middle point) and radius the difference between p1 and p1+t0 for example. The result would be:

Another line join type is miter. The following image describes it:

This type of line join is controlled by a parameter, a miter limit. The miter is a ratio between the length of the anchor vector (magenta) and half the line width. (Remember the line width is used to grow the tessellation segment in both line segment point directions). It is also important to note that the miter limit calculation must be clamped to an integer (something not told even in the Canvas Spec).

For segments that have a narrow angle between them, the miter should be very lengthy to cover the join area, leading to odd visuals like in the example:
This can be controlled by the miter limit parameter, which will prevent the mitter join (switching to bevel) if the value is too high.

Line cap

Line caps control how the start and the end of a poly-line looks like. With a butt value, the line looks as it results tessellated, no extra triangles like in the image:

Other types of cap are available: square

And round

Triangle signed area

In all the cases, signs and directions of the perpendicular or line cap vectors must be taken into account. For example, it is mandatory to get the direction of the triangle created by each 3 points before tessellation since otherwise odd visual results will arise. For example, if this is not addressed, the following result will be seen:

What we have here is that the intersection lines (red lines in the previous examples) are being calculated from the inner instead the outer. It is important to appropriately calculate the ‘signed area of the line segments triangle’, which not only gives the area of the triangle defined by 3 points, but also the sign, describing whether it is defined clockwise or counterclockwise.
In our case, if the signed area is greater than 0, describing a counterclockwise triangle, we invert the vectors to define the intersection lines. We always see these vectors pointing outwards in green light.

Analogously, vectors to line caps must be appropriately calculated, where they point to in order to have the caps pointing in the right direction.

Also, when rounds cap or joins are used, the arc angle must be calculated as the minimum angle.

Closed contours

In order to have closed contours properly tessellated, some extra work must done. A closed contour will be that which has the first and last point to be the same one, either same reference, or same coordinates. The process is simple:

• calculate a new point which is going to be the middle between the first and second contour points.
• remove the first point.
• add twice, at the beginning and at the end of the contour points the calculated point.

The results would be: w/o processing:

And processing the collection of points:

Important to note that closed contours don’t have any line cap applied.

Trivial optimizations

As far as i can tell, the most trivial optimization will be switching to bevel joins and butt caps when the size of the calculated line width is too small (<1.5).
Also it is important to calculate rounded arcs tessellated triangles based on the length of the arc for the current transformation matrix. You don't want to have super perfectly tessellated arcs with 200 triangles each.

Limitations

The algorithm is totally unoptimized.
It is also not suited for situations where there are a lot of segments taking over the same area, for example with very twisted segments. In this case, the tessellation won’t be correct.
Sometimes there’s overdraw on the generated triangles. If transparency is used, some overdraw will appear. You could first draw the triangles to the stencil though (weak solution, I know).

Playground

Efficient WebGL stroking playground live demo:

https://hypertolosana.github.io/efficient-webgl-stroking/playground.html