仓库地址：gpu-font-rendering

GPU Font Rendering

This is a demonstration of rendering text directly on the GPU using the vector outlines defined by the font.

这个demo展示了，直接在GPU上，使用字体的矢量轮廓线来完成文字渲染。

This demo is based on the method described by Will Dobbie in GPU text rendering with vector textures

with some modifications/simplifications based on publications from Eric Lengyel (GPU Font Rendering: Current State of the Art, Poster for the Slug Font Rendering Library, Slug Algorithm Paper).

Other related work includes

Improved Alpha-Tested Magnification for Vector Textures and Special Effects (signed distance fields) by Chris Green and Easy Scalable Text Rendering on the GPU by Evan Wallace.

这个demo使用的方法，是Will Dobbie在《GPU text rendering with vector textures》中所描述的，它是一个修改/简化版本，其原文是来自Eric Lengyel的文章（《GPU Font Rendering: Current State of the Art》），发表在Slug Algorithm Paper, Slug Font Rendering Library。

相关引用还有

1. Chris Green的符号距离场：Improved Alpha-Tested Magnification for Vector Textures and Special Effects
2. Evan Wallace的Easy Scalable Text Rendering on the GPU

This technique is useful for rendering large text or rendering text with arbitrary transforms (e.g. in a 3D scene) and produces pixel-perfect and anti-aliased results.

该技术对于渲染大型文本或带有任意变换的文本非常有用（例如在3D场景当中），渲染出的像素非常完美，抗锯齿效果好。

It has a slightly higher GPU runtime cost, but does not require rasterizing glyphs on the CPU.

它有稍高的GPU运行时成本，但不需要在CPU上光栅化文字。

In contrast to signed distance fields, it preserves sharp corners at all scales.

与符号距离场相比，它在所有的比例尺下都保留了尖角。

Method

A glyph outline is described by one or more closed contours.

字形(Glyph)的形状由一个或多个封闭的轮廓所组成。

A contour consists of line segments and bezier curve segments defined by a list of points.

一个封闭的轮廓由一系列由顶点定义的线段和贝塞尔曲线所组成。

Following the TrueType convention, outside contours are oriented in clockwise direction and inside contours are oriented in counterclockwise direction.

遵循TrueType的约定，外部轮廓的顶点以顺时针方向环绕，内部的轮廓顶点以逆时针方向环绕。

In other words, when following the direction of the contour, the filled area is always to the right.

换句话说，当沿着轮廓线的方向时，填充区域总是向右。

The contours of a glyph are converted into a list of individual quadratic bezier curves (defined by their control points), which are uploaded to the GPU.

字形的轮廓被转换成N个单独的二次贝塞尔曲线（由它们的控制点定义），并直接传送到GPU上。

A quad is generated for each glyph and the pixel shader determines whether each pixel is inside or outside the glyph.

为每个字形生成一个四边形，像素着色器确定每个像素是在字形内部还是在外部。

To do this, the winding number of the pixel is calculated by intersecting a ray with the bezier curves.

为了做到这一点，我们要计算一个值，即像素的圈数(the winding number of the pixel)，它是通过射线与贝塞尔曲线相交的射线来计算的。

At every intersection the ray either enters or exits the filled area as determined by the direction of the bezier curve relative to the ray.

在每个交点上，射线要么进入填充区域、要么退出填充区域，这由贝塞尔曲线的绕向与射线方向所决定的。

At every exit the winding number is increased by one and at every entry the winding number is decreased by one.

在退出填充区域的地方像素圈数+1，在进入填充区域的地方像素圈数-1.

After considering all intersections, the winding number will be non-zero if the pixel is inside the outline.

考虑所有交点之后，如果像素在轮廓线内，则像素圈数非0。

The direction of the rays does not matter for this winding number computation, but the math can be greatly simplified by using rays parallel to the x-axis.

射线方向对圈数的计算无光紧要（可以朝上下左右、或任意一个方向），但是通过使用平行于X轴的射线可以大大简化计算量。

By subtracting the sample position from the control points of the bezier curves, the coordinate system is shifted so that the origin of the ray is at \((0, 0)\) and the ray coincides with the positive x-axis.

通过贝塞尔曲线的控制点来减少曲线的样本点，移动坐标系，使得射线的起点在原点，并且射线与X轴的正方向重合。

For an intersection between the ray and a bezier curve the conditions \(y = 0\) and \(x \ge 0\) must then be true.

如何计算射线与贝塞尔曲线的交点？使 \(y=0 \ and \ x \ge 0\)即可。

Anti-aliasing (see below) will happen along the direction of the rays, but other directions can be achieved by first rotating the control points of the bezier curves around the origin so that the rays align with the x-axis again.

[?] 抗锯齿将沿着射线的方向产生，其他方向可以通过 围绕原点旋转贝塞尔曲线的控制点 所实现，如此射线就可以再次与X轴对齐。

To find the intersections between a ray and a single bezier curve, recall that a quadratic bezier curve is described by the following formula (for background on bezier curves see Beauty and Primer):

接下来讨论，如何计算一条射线与一条贝塞尔曲线之间的交点。回想一下，二次贝塞尔曲线由以下公式描述（关于贝塞尔曲线的背景知识，可参阅Beauty and Primer）

\[ \textbf{C}(t) = (1-t)^2 \textbf{P}_0 + 2(1-t)t \textbf{P}_1 + t^2 \textbf{P}_2 \]

Taking only the y-component and applying the condition \(y = 0\) results in a simple quadratic equation:

只考虑y分量（x分量暂不考虑），并让\(y=0\)，可以简化方程

\[ (1-t)^2 \textrm{y}_0 + 2(1-t)t \textrm{y}_1 + t^2 \textrm{y}_2 = 0 \]

Which can be rearranged into:

整理式子可得：

\[ \textrm{y}_0 -2t \textrm{y}_0 + t^2 \textrm{y}_0 + 2t \textrm{y}_1 - 2t^2 \textrm{y}_1 + t^2 \textrm{y}_2 = 0 \]

\[ (\textrm{y}_0 - 2\textrm{y}_1 + \textrm{y}_2) t^2 - 2(\textrm{y}_0 - \textrm{y}_1) t + \textrm{y}_0 = 0 \]

So that it can be solved using the quadratic formula:

因此，可以用二次方程开根公式求解：

\[ t_{0/1} = {-B \pm \sqrt{B^2-4ac} \over 2a} \]

\[ a = \textrm{y}_0 - 2\textrm{y}_1 + \textrm{y}_2 \quad B = -2(\textrm{y}_0 - \textrm{y}_1) \quad c = \textrm{y}_0 \]

Substituting \(B = -2b\) yields:

将\(B = -2b\) 代入：

\[ t_{0/1} = {-(-2b) \pm \sqrt{(-2b)^2-4ac} \over 2a} = {2b \pm \sqrt{4b^2-4ac} \over 2a} = {b \pm \sqrt{b^2-ac} \over a} \]

\[ a = \textrm{y}_0 - 2\textrm{y}_1 + \textrm{y}_2 \quad b = \textrm{y}_0 - \textrm{y}_1 \quad c = \textrm{y}_0 \]

The quadratic equation may have zero, one or two solutions. Furthermore, a solution \(t\) has to satisfy \(0 \le t < 1\) to be on the segment described by the control points (the end point is excluded since it is part of the next segment of the outline).

二次方程可能有0、1、2个解。此外，\(t\)要满足\(0 \le t < 1\)才能在贝塞尔曲线上（端点被排除在外，因为我们把它归为下一个线段）

Finally, given a solution \(t\) the corresponding x-coordinate can be calculated as \(\mathbf{C}_x(t)\) to check the second condition \(x \ge 0\) for an intersection.

最后，将求解出来的\(t\)代入\(\mathbf{C}(t)\)的X分量，如果\(x \ge 0\)则代表射线与曲线相交。

At this point, the intersections between the ray and bezier curve have been identified, but they still need to be classified as entry or exit. The demo provided by Dobbie explicitly calculates the derivative of the bezier curve for each \(t\) value to do this. However, the derivative can also be computed in general for both potential solutions \(t_0/t_1\):

此时，射线和贝塞尔曲线的交点已经计算得出，但仍需要判断它是入口、还是出口。由Dobbie提供的demo中，显示地计算每个t的贝塞尔曲线导数来做到这一点。然而，对于两个解的情况（\(t_0/t_1\)）也可以计算导数。

\[ \mathbf{C}_y(t) = (\textrm{y}_0 - 2\textrm{y}_1 + \textrm{y}_2) t^2 - 2(\textrm{y}_0 - \textrm{y}_1) t + \textrm{y}_0 \]

\[ \mathbf{C}_y(t) = a t^2 - 2b t + c \]

\[ \frac{d\mathbf{C}_y(t)}{dt} = 2at - 2b \]

\[ \frac{d\mathbf{C}_y(t_0)}{dt} = 2a{b - \sqrt{b^2-ac} \over a} - 2b = 2b - 2\sqrt{b^2-ac} - 2b = -2\sqrt{b^2-ac} \le 0 \]

\[ \frac{d\mathbf{C}_y(t_1)}{dt} = 2a{b + \sqrt{b^2-ac} \over a} - 2b = 2b + 2\sqrt{b^2-ac} - 2b = 2\sqrt{b^2-ac} \ge 0 \]

Therefore, the bezier curve crosses the x-axis in a fixed direction at each solution, and, combined with the convention for the orientation of the contour, \(t_0\) is always an exit and \(t_1\) is always an entry.

因此，贝塞尔曲线在每个解处，都以固定方向穿过X轴，结合轮廓方向的定义，\(t_0\)始终是出口，\(t_1\)始终是入口。

A different approach to understanding this relationship is to notice that, because of the different signs used in the solutions and the square root being non-negative,
\(t_0\) has to come first along the curve \((t_0 <= t_1)\) if \(a > 0\). Conversely, if \(a < 0\), then the order is reversed and \(t_1\) has to come first \((t_1 <= t_0)\).

另一种理解是，由于解中使用的符号不同，且平方根非负

1. 如果\(a > 0\)，则\(t_0\)必在曲线上先出现，即\((t_0 <= t_1)\)
2. 相反，如果\(a < 0\)，则顺序颠倒，\(t_1\)在前面，即\((t_1 <= t_0)\)

The parameter \(a\) can be rewritten as \(2(\frac{\textrm{y}_0 + \textrm{y}_2}{2} - \textrm{y}_1)\),
so its sign depends on whether the second control point is above or below the midpoint of the first and third control point.

参数\(a\)可以被重写成\(2(\frac{\textrm{y}_0 + \textrm{y}_2}{2} - \textrm{y}_1)\)，因此它的符号取决于第二个控制点是在第一个控制点和第三个控制点的中点，中点前、中点后。

The following figure shows that the solutions are always correctly classified for all combinations of the direction of the curve and the sign of parameter \(a\).
Notice how the order of the solutions along the curve changes, but the ray always enters at a \(t_1\) solution and exits at a \(t_0\) solution.

下图显示，对于曲线方向和参数\(a\)符号的所有组合，可以看出，结论是正确的。 注意曲线上解的顺序是如何变化的，但是射线总是以\(t_1\)进入，以\(t_0\)退出。

If the parameter \(a\) is 0 (or sufficiently small in floating-point calculations), there is a linear relationship between \(t\) and \(y\) (this is true for linear segments, but also for some non-linear curves), and the quadratic formula can no longer be used because of the division by \(a\).

若参数 \(a = 0\)（或者在浮点计算中足够小），则 \(t\) 和 \(y\) 之间存在线性关系（这适用于线性线段，但也适用于一些非线性曲线），二次公式不能再用了，因为要除以 \(a\)。

However, because the relationship is now linear, there can be at most one solution, which is easily computed and classified.

然而，由于现在的关系是线性的，最多只有一个解，因此很容易计算和分类。

Anti-aliasing along the ray direction is implemented by considering a window the size of a pixel around the ray origin.

沿射线方向的抗锯齿是通过考虑射线原点周围像素大小的窗口来实现的

If an intersection falls into this window, then the winding number is changed only fractionally to compute the coverage of the pixel.

如果一个交点落在这个窗口内，那么圈数只改变一点点来计算像素的覆盖范围。

The fractional weight is determined by the distance from the left edge of the pixel (this is consistent with the rays pointing to the right).

分数权重由距离像素左边缘的距离所决定（这与指向右侧的射线一致）

By considering the individual sections, one can see that this calculates the one-dimensional coverage exactly.

通过考虑各个部分，可以看到这准确地计算了一维覆盖率。

Note, that we have to also consider intersections slightly behind the ray origin now,
but the implementation first calculates any intersection with the x-axis and then verifies the x-position, so it does not change much.

注意，我们现在还要考虑射线原点后面的交点，但是该实现首先计算与X轴的任何交点，然后验证x的位置，因为它不会发生太大变化。

A different way of thinking about this is that the condition \(x \ge 0\) implies a weighting function that is 0 for \(x < 0\) and 1 for \(x \ge 0\). We can remove the discontinuity by introducing a linear segment over the width of one pixel.

另一种思考方式是，条件\(x \ge 0\)暗示了一个加权函数

1. \(x<0\)时，为0
2. \(x \ge 0\)时，为1

我们可以通过在一个像素的宽度上引入一个线性线段来消除不连续。

For full anti-aliasing we can use multiple rays along different directions (e.g. one along the x-axis and one along the y-axis).

为了完全抗锯齿，我们可以沿不同方向使用多条射线(例如，一条沿x轴，一条沿y轴)。

Notes

This kind of technique is subject to artifacts from the limited numerical precision of floating point numbers.

这种技术收到浮点数有限精度的影响。

The image below shows an instance of such artifacts when fully zoomed in (and knowing where to look).
Nevertheless, I have found this implementation to be quite numerically stable already.
Any remaining artifacts could be eliminated using the Slug algorithm, which is not implemented here due to the associated patent.

下图显示了一个完全放大的工件实例。然而，我发现这个实现在数值上已经相当稳定。任何剩余的工件都可以使用Slug算法消除，由于相关专利，这里没有实现该算法。

This demo also does not implement any performance optimizations (like banding) and might have high GPU usage in some scenarios and when using very complex fonts.

此demo也没有实现任何性能优化（如banding），并且在某些场景和使用非常复杂的字体时，可能会有很高的GPU使用率。

Build Instructions

1. Init submodules

Clone the project recursively to initialize the submodules for the dependencies (or run git submodule update --init if you have already cloned the repo):

git clone --recursive https://github.com/GreenLightning/gpu-font-rendering.git
cd gpu-font-rendering

2. Use CMake

# Note: CMake will create the build directory.
cmake -S . -B build
make -j8 --directory build

On Windows you might want to use CMake GUI and/or Visual Studio instead.

On Linux you might have to install additional packages for OpenGL development (e.g. sudo apt-get install xorg-dev libgl1-mesa-dev for Ubuntu).

3. Run from the main project directory

./build/main

The program requires the fonts and shaders directories to be in the current directory to load its resources. If you only get a black window, this is most likely the issue. Check your working directory and check the console for errors.

Tested on Windows 10, MacOS Monterey and Ubuntu 22.04.