Recently I wrote a small 2D vector graphics renderer for Essence. It's currently only used for drawing binary SVG icons (previously I used the renderer in nanosvgrast.h), but I plan to use it for a custom animatable icon format, and also expose its functionality through the API directly. For the actual rasterization process, it uses a method closely adapted from stb_truetype.h, which you can read more about in Sean Barrett's article. In this blog post I'm going to discuss how my renderer generates outlines of polygons to draw lines.
The two functions that handle generating outlines are RastShapeCreateContour and RastShapeCreateDashed, which create solid and dashed lines respectively. They both take a RastPath as an argument, which is simply a list of vertices representing the polygon. Curved edges are flattened to straight lines of a given tolerance before outline generation begins. The polygon outline is returned as a RastShape, which consists of a sorted array of edges, and the bounding rectangle of the shape. The shape can then be drawn onto a surface. Outlines should be drawn with a non-zero fill rule, for reasons we'll discuss later.
First attempt
Let's think about the steps needed to generating an outline. First, we have our polygon (convex for now).
For each pair of adjacent vertices, we're going to extrude the edge in both directions. Draw some perpendicular lines:
Then draw the extruded edges.
Now we do this for all pairs of adjacent vertices.
The code looks something like this.
1 2 3 4 5 6 7 8 9 10 11 12 | RastVertex *from = vertices + (i + 0) % vertexCount;
RastVertex *to = vertices + (i + 1) % vertexCount;
float dx = to->x - from->x;
float dy = to->y - from->y;
float scale = width / sqrtf(dx * dx + dy * dy);
if (internal) scale = -scale; // Extrude in the opposite direction.
float ox = -dy * scale;
flaot oy = dx * scale;
RastVertex cf = { from->x + ox, from->y + oy };
RastVertex ct = { to->x + ox, to->y + oy };
AddVertexToPath(path, cf);
AddVertexToPath(path, ct);
|
Since the extruded edges don't meet up, we need to connect them somehow. For now, we'll just draw a straight line connecting them.
Finally, we can fill the created shape.
Well... it was only a first try, wasn't it...
Line joins
By directly connecting internal edges of the outline, we find that regions of the desired outline get cut-out. What we actually want to do is find the intersection of the edges (this is done by solving the two linear equations, one in each axis), and then join them at that point. This process is called mitering.
This results in a decent looking outline!
Here's the code.
1 2 3 4 5 6 | // from1 and to1 are the ends of the first edge, and from2 and to2 are the ends of the second edge.
float a = to1->x - from1->x, b = from2->x - to2->x, e = from2->x - from1->x;
float c = to1->y - from1->y, d = from2->y - to2->y, f = from2->y - from1->y;
float j = (d * e - b * f) / (d * a - b * c);
RastVertex v = { from1->x + j * a, from1->y + j * c };
AddVertexToPath(path, v);
|
However, the external edges' bevelled joins still look wrong. We can also apply mitering to them, by extending them out until they meet, in a similar fashion as before.
Pointy.
Unfortunately, mitering the external joins isn't always a good idea. As the angle formed by the three adjacent vertices gets smaller and smaller, the mitered join begins to look hilariously oversized. It's common to place a limit on the distance the lines can be extended and fallback to the bevelled edge when this happens.
An alternative to mitered joins is to round them, which creates a softer, more Microsoft Office-like appearance.
In code, this looks like:
1 2 3 4 5 | for (int j = 0; j < divisions; j++) {
float angle = fromAngle + j * (toAngle - fromAngle) / (divisions - 1 /* don't miss out the final point! */);
RastVertex v = { point->x + cosf(angle) * width, point->y + sinf(angle) * width };
AddVertexToPath(path, v);
}
|
Line caps
As fun as creating outlines for polygons is, in the real world we also need to draw plain lines. This is a nearly identical process, except we now have two ends of the line to deal with, denoted by question marks in the following diagram.
The easiest thing to do is to simply connect the two vertices at either edge with a straight line. This is called a flat line cap.
However, we see that "half" of the vertex at either end of the line is outside the shape we have formed. By imagining an imaginary square with the vertex at its center, and tracing its edges, we form a more pleasing line cap, known as square cap.
Here's the code.
1 2 3 4 5 6 7 | float dx = to->x - from->x;
float dy = to->y - from->y;
float scale = width / sqrtf(dx * dx + dy * dy);
RastVertex c0 = { .x = c.x + scale * dx, .y = c.y + scale * dy };
RastVertex d0 = { .x = d.x + scale * dx, .y = d.y + scale * dy };
AddVertexToPath(path, c0);
AddVertexToPath(path, d0);
|
By re-imagining our imaginary square as an imaginary circle, we can also create rounded line caps.
The code to do this is identical to the rounded line join code given above.
Dashed and dotted lines
To create dashed and dotted lines, we break the path forming the polygon up before sending it to RastShapeCreateContour. In fact, a dashed line is just several evenly spaced lines, going around the polygon's perimeter.
We start by adding the first vertex to the "dash".
1 2 3 4 5 6 | RastPath dash = {};
RastVertex from = vertices[0];
RastVertex *to = &vertices[1];
loopStart:
AddVertexToPath(&dash, from);
|
We then accumulate length going around the polygon until we reach the dash's length. If we stop in the middle of a edge, we linearly interpolate from the start to end vertex to find the stopping position.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | float accumulatedLength = 0;
while (true) {
float dx = to->x - from.x;
float dy = to->y - from.y;
float distance = sqrtf(dx * dx + dy * dy);
if (accumulatedLength + distance >= dashLength) {
float fraction = (dashLength - accumulatedLength) / distance;
RastVertex stop = { from.x + fraction * dx, from.y + fraction * dy };
AddVertexToPath(&dash, stop);
from = stop; // We'll pick up from this point.
break;
}
// Go to the next edge of the perimeter.
accumulatedLength += distance;
from = *to;
AddVertexToPath(&dash, from);
to++;
}
|
We use the path formed to create an outline. Next, we skip over some length of perimeter given by the gap between the dashes, and then we repeat the process, until we've worked our way around the entire polygon, optionally alternating between different dash lengths to create a variety of patterns. Dots also be constructed by specifying a dash length of 0 and using rounded line caps.
Concave polygons
Let's investigate what happens if we try to use the algorithm we created in the earlier sections to construct the outline of a concave polygon, mitering internal joins and rounding external joins.
Create the lines...
Apply the joins...
Oh no! By rounding the join at the concave section, we get a large arc inside the polygon! For concave sections, we need to force the external edges to the mitered. We can also rounds the interior edge at concave joins, if we want.
Much better. The code the detect the concavity of three adjacent vertices uses the sign of the cross product.
1 | float cross = (p2->x - p1->x) * (p3->y - p2->y) - (p2->y - p1->y) * (p3->x - p2->x); |
Assuming vertices given anticlockwise: for external edges, if the cross product is greater than zero, we have to use a miter join, and for internal edges, if the cross product is less than zero, we have to use a miter join. Otherwise, we can use a bevelled or rounded join.
Why we use a non-zero fill rule
Let's apply our algorithm to this shape.
When we extrude edges, something bad happens. Edges extruded from non-adjacent vertices are crossing!
Focusing on the interior edges, and after applying mitering, we get:
Unfortunately, I couldn't think of a way these extra bits without searching the resulting outline for self-intersections. So instead, I just draw the outlines with a non-zero fill rule, and these unwanted regions don't shown up.
The end
When writing the code for this renderer, I was surprised how easy most of it was. I always expected outline generation to be complicated, but once I began to break the problem down it wasn't that bad after all. Furthermore, writing the renderer was very rewarding, because of the immediate visual feedback you get. Unfortunately, there are a few edge cases and bugs that need to be ironed out, but currently there's no rush for me to fix them.
You can find the full code for the renderer on the Essence Bitbucket page.
If you'd like to contribute to Essence, or otherwise discuss it, join the Handmade Network Discord guild, where Essence has its own text channel.