Max Did It
Coding
,Wed
Post the First Comment
Tagged

Polygon Outlines With Uniform Inset

I want users of my hardware text rendering library firetype to be able to render characters with outlines.

Sounds simple enough, right? Adding an outline to text is a matter of setting a simple value in all major graphic softwares. Since firetype is able to retrieve the shapes of characters from font files, it should not be a problem to add an offset to these and render the result.

Turns out that adding an outline to a simple polygon is not as straightforward as you might think. In fact, to have a robust method of creating polygon outlines means to implement a relatively complex algorithm that encompasses several steps.

Even seemingly minor details like how far each vertex has to be moved to create the outline can create problems. The solution, however, is pleasently elegant, as you will see below. I will cover the other aspects of the outline algorithm in the next posts.

The Objective

Let’s say we have a set of vertices which represent the input. The vertices have a certain order. Two consecutive vertices form an edge.

Vertices

We want to create an outline to that set of line segments where all new edges have the same, arbitrary distance to the original segments. The distance is measured between the two closest points of two edges.

Extruded Edges

The Problem

We want our edges to have a certain distance to each other. The edges in our line are not actual objects, though. They are defined implicitly by two vertices.

This is especially true in 3D graphics, where you pass vertex data to the GPU and an order in which the vertices form edges and triangles. There is no edge data, though.

So, the direct approach would be to move the vertices to new positions. To do this, we first need the normal for each vertex. The vertex normal is defined as the normalized average of the two adjacent edge normals of the vertex.

However, we can’t move each vertex by the same distance along it’s normal. If we do that, we will get a very irregular outline:

So, for the edges to have the same distance to their respective origins, we have to move the vertices by different distances. How do we do that?

The Solution

Finding the Actual Position of the Outline Vertex

This is only an intermediate step to see what the actual position of the new outline vertex should be. We actually make these considerations mostly for ourselves, so that the solution in the next section doesn’t come too much out the blue.

  1. Let’s say we have only three vertices, forming two edges.

  2. We consider the two edges not just as line segments, but as actual lines extending infinitely.

  3. Now, we “push” both lines along the respective edge normals by the thickness the outline should have.

  4. Finally, the intersection of the two new lines marks the actual position of the new outline vertex.

We could perform all these operations for every vertex in our polygon when creating our outline. However, if we keep exploring this model, we can actually find a solution that’s easier to implement and doesn’t need as many computations.

Simplifying The Calculations

Let’s forget the lines for a moment. What if we “push” one of the edge’s offset vectors over to the offset vector we calculated for the vertex? This is simply done to mentally visualize this step. It doesn’t have any meaning geometrically since a vector is only a value with a direction anyways.

As we can see, we can form a triangle with these two vectors and a segment of the edge. Not only that, the triangle has a right angle in it.

This gives us a whole new angle to attack this problem since we can now use trigonometric functions!

So, we know the length of the triangle’s side h since we set this value ourselves and we want to know the length of the offset vector s . We can also calculate the angle \beta between h and s by calculating the angle between the vertex normal and the edge normal.

s is the side oppsite to the right angle, which makes it the hypotenuse. h is next to our known angle, which makes it the adjacent.

The trigonometric function that applies here is the cosine function.

\cos(\theta)=\frac{\displaystyle adjacent}{\displaystyle hypotenuse}

\cos(\beta)=\frac{\displaystyle h}{\displaystyle s}

If we solve this equation for s , it becomes:

s=\frac{\displaystyle h}{\displaystyle \cos(\beta)}

Fair enough. Now we need the value for cos(\beta) . So, what was the formula for calculating the angle of a vector again? Right, we use the dot product!

A \cdot B=\|A\|\|B\|cos(\theta)

In our case, we put the vertex normal and the edge normal into the equation.

v_n \cdot e_n=\|v_n\|\|e_n\|cos(\beta)

Both vectors have unit length which means that we can drop the lengths of each vector from the equation.

v_n \cdot e_n=cos(\beta)

Aaand… that’s it. We just solved that part of the equation. To get the actual angle, we would have to apply the arccosine on the left hand side of the equation above, but in fact we only need the cosine value for our orignal equation. This conveniently saves us an expensive calculation.

I Love It When A Plan Comes Together

We just put the dot product calculation in our original equation.

s=\frac{\displaystyle h}{\displaystyle v_n \cdot e_n}

If we expand the dot product operation the actual calculations would look like this:

s=\frac{\displaystyle h}{\displaystyle v_{nx} e_{nx}+v_{ny} e_{ny}}

This is the equation for the distance by which we have to move each vertex to get the respective vertex in the outline.

Fun Fact: It doesn’t matter which of the adjacent edge’s normals you use for this calculation. Since the vertex normal is the average of both adjacent edge normals anyways, the angle to both of them should be the same.

The Result

If we apply the equation above to our original set of line segments, then we get a nice, regular outline.

Next Steps

Is that it? Shouldn’t this be enough for us to create outlines for text characters, for example? Unfortunately not.

You will run into edge cases very fast with this naive approach. Issues like overlapping shapes will only fail to appear for very simply glyphs. Even if the original shape is a simple polygon, insetting the edges will create intersections and overlapping areas very easily.

In the best case, this will create unnecessary triangles and occasional overdraw. In the worst case, it will diminish the optical quality of the results.

firetype Outlines First Try

To fix this, we will need to implement more complex algorithms which I will describe in my next posts.

Leave A Comment

Your email address will not be published. Required fields are marked *

Connect with Facebook

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>