# GPU-Centered Font Rendering Directly from Glyph Outlines

## Overview

### The problem
Games and other real-time applications often require text to be rendered on surfaces, with the possibility of different viewing angles. Because the perspective of said text (or glyph) needs to be distorted depending on the camera's position, dynamically rendering in high quality is needed.

### Previous solutions
Previous solutions include pre-rendered glyphs stored in a texture atlas, which is the most used. This method is extremely simple and fast, but does come with blurred outlines. Other solutions build on this, but come with their own issues, like rounded edges that should be pointy, different rounding errors, and other types of artifacts.

### Key idea


For a given point, we can know whether we are inside or outside the glyph (in order to draw it) just by looking at the sign (respect to our point) in one of the axis for each of the three points that define each of the Bézier curves forming the glyph.

TrueType fonts store their glyphs by using Bézier curves, which are **represented by three points** and whose formula can be expressed as a quadratic equation between them. **Given a point, we can determine if we are inside or outside the glyph by throwing a ray in any direction and calculating whether the "winding number" adds up to 0 or not**. Choosing arbitrarily a direction for all the edges, the winding number of an intersection of the ray with the edge is defined to be +1 when the direction goes to one side, left or right, and -1 when it goes to the other. Notice the choice of directions does not matter as long as it is consistent along the calculation. Throwing this ray in the direction of the main axis ($x$ and $y$) makes the formulae simple. Let's take a ray on $x$ as an example, but the same math would be applyable to y. Notice that, in the case of a ray on $x$, finding the intersections with the ray is equivalent to finding the roots of the quadratic equation for the $y$ axis.

$$C(t) = (1 - t)^2 p_1 + 2t(1 - t) p_2 + t^2p_3$$

In order to **render fonts from their glyph outline without introducing artifacts due to rounding errors**, the proposed techinque classifies Bézier curves into eight different equivalence classes based only on the sign of the value for the y-axis on each of the three points of the curve ($y_1$, $y_2$, $y_3$) and show that for each of this classes, the contribution from each of the root values of the equation to our winding number is always the same. In the previous table we can see the complete classification, in which $y_1$, $y_2$ and $y_3$ are marked 0 for negative values (respect to the ray) and 1 for positive values, and $t_1$ and $t_2$ (the roots of the equation) are marked 1 when they contribute to the winding and 0 when they don't. Notice that, given that $t_1$ always contributes adding 1 and $t_2$ always contributes -1, we have showed that, **by checking only the signs of the y-components of Bézier curve points**, we can calculate the winding number. Notice all of this can be done without precission errors.

They also make some basic optimizations to reduce the number of curves to test.

### What they achieve
Their results are great visually. The glyphs can be viewed from any angle and at any distance without visible artifacts.

One major drawback of their method is the rendering time. As can be seen in the table below, the time for one of the simplest fonts, arial, is 1.1ms. This can be compared to the simpler, more conventional method with pre-rendered glyph images, where the time to render is as low as 26 µs.


But compared to other dynamic methods, their results are still substantially faster. For example, the so called "Dobbie" method has a render time of 5.2ms for the Centaur font, which is 4 times slower than the results from this new method. <!-- do we need to have a source for this? -->

<!-- insert some numbers here? -->

## Questions

1. Could this method be used for more than just fonts? Vector graphics perhaps? <!-- probably yeah, but complexity = time -->

2. Is this method worth using, given the substantially longer rendering time? Is the original problem that noticible? <!-- Depends on the situation?. -->

3. The rendering time increases by a lot depending on the complexity of the font. Is there a workaround? How would you go about 'solving' this issue? <!-- Could be discussed, maybe using pre-rendered glyph images when fonts are more complex, combining old methods with new ones? -->

4. Why is an epsilon offset not a good solution to the rounding error problem?
<!-- Its value has to be manually adjusted and the resulting solution is not as robust -->

###### tags: `chalmers`