Publication: 2025-01-03

To render any geometric figure to a GPU (with OpenGL / Direct3D / Vulkan / …),
they must first be triangulated, i.e. decomposed as a series of triangles.
Some figures are trivial to transform into triangles: for instance, a segment with thickness
is represented by a rectangle, which can be rendered with two triangles.
But a segment strip with thickness (aka. polyline) is not trivial.

Ultimately, this exploration has been a rabbit hole, also partly due to some digressions along the path
— let’s prototype with a bare implementation of GeoGebra in vanilla JavaScript
— let’s do a WebGL + WASM demo to verify the algorithm works correctly … 😅
At least, it gives some fancy interactive visuals for this blog post. 😁

As usual, my implementation is available in the public domain. Without further ado, let’s dive in. 🫡

---

A bit of geometry

Geometrically-speaking, a polyline is defined by an ordered list of 2D points.
A segment is drawn between each consecutive pair of points: a polyline of \(n\) points
contain \(n-1\) segments.

A trivial way to add thickness to a polyline is to add thickness to the individual segments,
i.e. every segment is replaced by a rectangle with desired thickness.

Two problems arise with this method:

1. The first, major problem is with regard to the corners between each rectangle:
   there are gaps between them. We need to add triangles in these corners to fill them.

2. The second, more minor problem is that the rectangles overlap at every angle.
   This matters if the rectangles are filled with translucent fill color (i.e. \(0~),
   as some regions will be darker than expected.
   Alas, trying to solve that creates some edge cases, and I’ve found
   no satisfying solution when two points are near, as it causes all kinds
   of contours not easy to triangulate. A pixel-based approach (e.g. GPU pixel shader)
   would probably be the best place to render translucent polylines without overlap.
   For the time being, I’ve given up on supporting those via triangulation… 😢

Polyline rendering is present in every browser, as they can be drawn with SVG images and
JavaScript’s Canvas2D API, thus I’ve taken inspiration from
the HTML5 standard,
which defines three types of line joins.

1. Bevel join is obtained by filling the triangle between the corner point and
   the two exterior endpoints.

2. Miter join is obtained by adding to the Bevel join a triangle between
   the two endpoints on the exterior of the corner, and the intersection between the two exterior sides.
   Note that acute angles will result in very long triangles, thus HTML5 and SVG
   both define a Miter limit to fallback on Bevel join instead of creating distorted shapes.

3. Round join is obtained by drawing a partial circle centered on the corner point
   and of diameter equal to the thickness.

I’ve chosen to implement the Miter joins, and expose the Miter limit parameter.
If this limit is zero, it fallbacks nicely as Bevel joins. With that choice made,
let’s consider the different points and segments defining these joins:

• \(A\), \(B\) and \(C\) are three distinct and consecutive points from the polyline.
• \(A_1 A_2 A_1′ A_2’\) is the rectangle representing the segment \([AB]\).
• \(B_1 B_2 B_1′ B_2’\) is the rectangle representing the segment \([BC]\).
• \(I_1\) is the intersection of the lines \((A_1, A_1′)\) and \((B_1, B_1′)\)
• \(I_2\) is the intersection of the lines \((A_2, A_2′)\) and \((B_2, B_2′)\)

Thus:

• To render the segment \([AB]\), we need the 2 triangles \(A_1 A_2 A_1’\) and \(A_2 A_1′ A_2’\).
• To render the Bevel join, we need one triangle: either \(B A_1′ B_1\) or \(B A_2′ B_2\),
  depending on whether the angle \(\widehat{ABC}\) is clockwise or anticlockwise.
• To render the Miter join, we need one extra triangle: either \(I_1 A_1′ B_1\) or \(I_2 A_2′ B_2\),
  depending on whether the angle \(\widehat{ABC}\) is clockwise or anticlockwise.

---

From geometry to algebra

The first step is to define the input coordinates \(A=(x_A,y_A)\), \(B=(x_B,y_B)\) and \(C=(x_C,y_C)\),
from which we derive the vectors \(\overrightarrow{AB}=(x_{AB},y_{AB})\) and \(\overrightarrow{BC}=(x_{BC},y_{BC})\) .

To build the rectangle representing segment \([AB]\), we first need the vector \(\overrightarrow{A A_1}\),
which is perpendicular to \(\overrightarrow{AB}\) and of length \(\|\overrightarrow{A A_1}\| = \text{Thickness} / 2\):

\[\overrightarrow{A A_1} = \frac{\text{Thickness}}{2 \cdot \|\overrightarrow{AB}\|} \times
\begin{pmatrix}x_{AB} \cos\theta – y_{AB} \sin\theta \\ x_{AB} \sin\theta + y_{AB} \cos\theta \end{pmatrix}^{\theta=90°}
= \frac{\text{Thickness}}{2 \cdot \|\overrightarrow{AB}\|} \times \begin{pmatrix}-y_{AB} \\ x_{AB} \end{pmatrix}\]

Alternatively, instead of using trigonometry functions, the perpendicular vector can be obtained with the 3D cross-product \(\overrightarrow{z} \times \overrightarrow{AB}\). This formula can be adapted
in a 3D environment as \(\overrightarrow{v} \times \overrightarrow{AB}\) with \(\overrightarrow{v}\) the camera’s direction.

The rectangle \(A_1 A_2 A_1′ A_2’\) is then defined by the four points:

\[
\begin{cases}
A_1 = A + \overrightarrow{A A_1} \\
A_2 = A – \overrightarrow{A A_1} \\
A_1′ = B + \overrightarrow{A A_1} \\
A_2′ = B – \overrightarrow{A A_1}
\end{cases}
\]

For the joins, we need the endpoints \(B_1\) and \(B_2\) of the next segment,
obtained with the same formulas.

\[\overrightarrow{B B_1} = \frac{\text{Thickness}}{2 \cdot \|\overrightarrow{BC}\|} \times \begin{pmatrix}-y_{BC} \\ x_{BC} \end{pmatrix}\]

\[\begin{cases}
B_1 = B + \overrightarrow{B B_1} \\
B_2 = B – \overrightarrow{B B_1}
\end{cases}\]

We also need to know whether the \(\widehat{ABC}\) angle is clockwise or anticlockwise.
The cross product \(\overrightarrow{AB} \times \overrightarrow{BC}\) has a coordinate Z
whose sign can distinguish the angle’s orientation.

\[\overrightarrow{AB} \times \overrightarrow{BC} =
\begin{pmatrix}x_{AB} \\ y_{AB} \\ 0 \end{pmatrix} \times \begin{pmatrix}x_{BC} \\ y_{BC} \\ 0 \end{pmatrix}
= \begin{pmatrix}0 \\ 0 \\ x_{AB} y_{BC} – y_{AB} x_{BC} \end{pmatrix}
= \begin{pmatrix}0 \\ 0 \\ z_{AB\_BC} \end{pmatrix}
\]

I’ve tried my best to reason about how the sign of \(z_{AB\_BC}\) relates to the angle’s orientation,
but it depends on whether the coordinate system is left- or right-handed when considering the Z axis,
and whether the Y axis points up or down. I’ve given up, and I used trial and error to determine which sign means what.

\[\text{Bevel triangle} = \begin{cases}
B A_1′ B_1 & \text{if} & z_{AB\_BC} 0
\end{cases}\]

Finally, the Miter join \(M\) is obtained by finding the intersection point of the two exterior edges,
which also depends on the sign of \(z_{AB\_BC}\).

\[M = \begin{cases}
I_1 = (A_1, \overrightarrow{AB}) \cap (B_1, \overrightarrow{BC}) & \text{if} & z_{AB\_BC} 0
\end{cases}\]

Let’s only consider the case when \(z_{AB\_BC} , as the other case is symettrical.
We want to solve a system of two equations:

\[\begin{cases}
x_{I1} & = & x_{A1} + \alpha \cdot x_{AB} & = & x_{B1} + \beta \cdot x_{BC} & \textcircled{1} \\
y_{I1} & = & y_{A1} + \alpha \cdot y_{AB} & = & y_{B1} + \beta \cdot y_{BC} & \textcircled{2}
\end{cases}\]

There are multiple ways of solving the system, but there is a way to limit the number of divisions
(and thus, checks for zero) by solving \(y_{BC} \textcircled{1} – x_{BC} \textcircled{2}\):

\[\begin{matrix}
&y_{BC}x_{A1} &+& y_{BC}x_{AB} \cdot \alpha_1 &=& & y_{BC}x_{B1} &+& y_{BC}x_{BC} \cdot \beta_2 & \\
-&x_{BC}y_{A1} &-& x_{BC}y_{AB} \cdot \alpha_1 & & -& x_{BC}y_{B1} &-& x_{BC}y_{BC} \cdot \beta_2 &
\end{matrix}
\\\ \\
\begin{matrix}
\Leftrightarrow&(y_{BC}x_{AB} – x_{BC}y_{AB}) \cdot \alpha_1 &=& y_{BC}x_{B1} – x_{BC}y_{B1} – y_{BC}x_{A1} + x_{BC}y_{A1} \\
\Leftrightarrow&z_{AB\_BC} \cdot \alpha_1 &=& y_{BC} \cdot (x_{B1} – x_{A1}) – x_{BC} \cdot (y_{B1} – y_{A1}) \\
\Leftrightarrow&\alpha_1 &=& \frac{y_{BC} \cdot (x_{B1} – x_{A1}) – x_{BC} \cdot (y_{B1} – y_{A1})}{z_{AB\_BC}}
\end{matrix}
\\\ \\
\begin{matrix}
I_1 &=& A_1 + \alpha_1 \cdot \overrightarrow{AB} \\
I_2 &=& A_2 + \alpha_2 \cdot \overrightarrow{AB}
\end{matrix}
\]

\[\text{Miter triangle} = \begin{cases}
I_1 A_1′ B_1 & \text{if} & z_{AB\_BC} 0
\end{cases}\]

To prevent acute angles to be extended disproportionately far,
let’s define a limit \(\text{miterLimit}\). The Miter triangle is displayed
if the ratio between the distance of the external corner \(M\) and the polyline corner \(B\)
and half the thickness is less than \(\text{miterLimit}\):

\[
\text{Miter triangle displayed if…} \\[1em]
\begin{matrix}
&\frac{2 \cdot \| \overrightarrow{BM} \|}{\text{Thickness}} &\le& \text{miterLimit} \\[0.5em]
\Leftrightarrow&\| \overrightarrow{BM} \| &\le& \text{miterLimit} &\times& \text{Thickness} &/& 2\\[0.5em]
\Leftrightarrow&\sqrt{(x_M – x_B)^2 + (y_M – y_B)^2} &\le& \text{miterLimit} &\times& \text{Thickness} &/& 2\\[0.5em]
\Leftrightarrow&(x_M – x_B)^2 + (y_M – y_B)^2 &\le& \text{miterLimit}^2 &\times& \text{Thickness}^2 &/& 4
\end{matrix}
\]

HTML5 provides a default value of \(\text{miterLimit} = 10\).
If \(\text{miterLimit} = 0\), the Miter triangle will never be displayed, always resulting in a Bevel join.

---

Implementation in C

The API to implement is composed of a single function:

/// @param polyline[in] Input array of coordinates (X,Y) composing the polyline.
/// @param polylineCount Number of points in @a polyline .
/// @param thickness Distance between the two parallel lines.
/// @param miterLimit Threshold to make angles sharp. Use `10.f` as default, `0.0f` to disable.
/// @param triangles[out] Output array of coordinates (X,Y), to be assembled three-by-three into
/// triangles.
/// @param triangleCapacity Number of triangles writable in @a triangles .
/// @return Number of triangles corresponding to the given @a polyline,
/// which can be bigger than @a triangleCapacity .
///
/// @attention
/// - @a pPolyline must have `2 * polylineCount` readable coordinates.
/// - The generated triangles count is at most `4 * (polylineCount - 2) + 2`.
///   Thus, there are at most `24 * (polylineCount - 2) + 6` coordinates written into @a triangles .
int32_t jvPolylineTriangulate(float const polyline[], int32_t polylineCount, float thickness,
                              float miterLimit, float triangles[], int32_t triangleCapacity);

The computation regarding point coordinates are straightforward from the equations,
the difficult part in the implementation is the iteration logic. polyline contain
the 2D coordinates of polylineCount points. We must find consecutive \((A, B, C)\)
triplets such that \([AB]\) and \([BC]\) have a non-zero length, and correctly handle
the last segment which has no corresponding point \(C\). Moreover, the output
triangles count is variable (due to edge cases and the miterLimit).

• idxIn and idxInEnd represent the iteration state for the polyline points.
• idxOut and idxOutEnd represent the iteration state for the output buffer.
  idxOut can grow greater than idxOutEnd, at which case the triangle coordinates
  are not written anymore, but the triangle count is still kept for the return value.

// Iteration logic in the input and output arrays.
// Indices represent coordinates (2 per point, 6 per triangle).
int32_t idxIn = 0;
int32_t idxInEnd = 2 * polylineCount;
int32_t idxOut = 0;
int32_t idxOutEnd = triangleCapacity * 6;

During initialization, \(A\) is set to the first polyline point,
and we iterate on polyline to find \(B\) the next polyline point
which is distinct from \(A\).

// First point.
float xA = polyline[idxIn];
float yA = polyline[idxIn + 1];
idxIn += 2;

float xB, yB, lenAB = 0;
while (idxIn 

During main loop, \(C\) is set to the next polyline which is distinct from \(B\).
As a special case for the last segment, \(C\) is set to \(A\), which ensures
that \(A B C\) are aligned, thus the join logic will be skipped.

for (; idxIn 

I skip the ~100 lines of coordinates computations, which are direct translations of the algebra above.
Outputting triangles is done with the following code pattern:

if (idxOut 

At the end of the main loop, the points \(B\) and \(C\)
become the points \(A\) and \(B\) for the next iteration:

    // Prepare for next segment.
    xA = xB;
    yA = yB;
    xB = xC;
    yB = yC;
    lenAB = lenBC;
} // for (; idxIn 

Finally, the number of triangles composing the polyline is idxOut / 6.

---

Results

The C code is available freely, in the public domain. I’ve compiled it into WASM, and I programmed a small demo showcasing it is working below. 😎

• Click on the canvas to add more points.
• See the Miter limit in action by creating acute angles.
• Add multiple points at the exact same pixel and see that there’s no issue.

In addition to the C code, this article results in two by-products.
First, I’ve isolated the interactive geometry drawings logic into a reusable script,
in case someone happens to have the same needs than me. It is available under the MIT License,
available on GitHub. Here is a usage example:

The second by-product is the WASM demo. I’ll not detail the whole process,
as this could be the topic for an entire article, but here are some notes
if you want to follow the same path as me:

The C source file is compiled into WASM with this command:

clang --target=wasm32 -O3 -ffast-math -nostdlib -Wl,--no-entry -Wl,--export-all -Wl,--allow-undefined -Wl,--import-memory -o jv_polyline.wasm jv_polyline.c

• --target=wasm32: Output a .wasm file.
• -O3 -ffast-math: Enable optimizations.
• -nostdlib: We don’t have a standard library to link… which is troublesome because the code uses hypotf().
• -Wl,--no-entry: We don’t have a main function.
• -Wl,--export-all: Export all defined functions (there is only one: jvPolylineTriangulate).
• -Wl,--allow-undefined: Unknown functions (eg. hypotf) are marked as “imported” in WASM:
  the JavaScript caller is responsible to expose these functions.
• -Wl,--import-memory: Memory is initialized by JavaScript caller.

The JavaScript must then provide both hypotf (from Math.hypot) and the memory.
The communication with WASM represents the first 50 lines of the
demo’s source code
(the ~200 other lines are WebGL and UI).

If you find this article or the code useful, feel free to send me an email or share this article. 😊

Thanks for reading, have a nice day!

Attributions

“Math time” image : Math Time Vectors by Vecteezy