Revision 2
简介
众所周知，字体显示是所有游戏引擎都会涉及到的一个功能组件。KlayGE实现此功能的方式是通过点阵的形式存储和显示信息，但其呈现的字体支持一定程度上的高质量放缩，兼具了矢量图的优点。
以往的工作
目前的字体系统多种多样，从存储方式上看可分为点阵和矢量两大类。
点阵字体系统把每一个字存储成固定大小的点阵位图，常见的大小有16×16和32×32等。其中每个字形都用一组二维像素信息表示。这种文字显示方 式于较早前的电脑系统（例如未有图形接口时的DOS操作系统）被普遍采用。常见的纯点阵字体有 bdf，pcf，fnt，hbf 等格式[6]。 点阵字体的优点是具有简单快速的显示方式，且不受硬件限制；但是它的缺点也比较突出，即：实现高质量的放缩相对困难，特定的点阵字体只能清晰地显示在相应 的字号下，否则显示的字型只能因被强行放大而失真，产生成马赛克式的锯齿边缘。因此为了满足各种显示需求，许多字体都需要要依照型号大小预先存储多套，使 得字体所占的空间随着精度要求迅速上升。如果没有找到合适大小的字体，显示质量就会受到很大影响。
在矢量字体系统中，每一个字形都表示成一组数学曲线描述的轮廓，它包含了字形边界上的关键点，连线的导数信息等。在显示字体时，渲染引擎通过读取其 数学矢量，并进行一定的数学运算来实现渲染，字的内部则通过光栅化来填充。矢量字体主要包括Type1和TrueType等几类[6]。矢量字体的优点是存储空间小，可以无限放缩而不产生变形；缺点是显示系统复杂，需要很多操作才能显示出矢量资源，因而速度较慢，也不适用于一些硬件。
随着硬件的发展，Ray等人提出了一种新的矢量存储方式[5]。它把矢量图分解成许多区域，每个区域用一个多项式表示。通过把多项式的系数存在纹理中，矢量纹理就可以在pixel shader中很好的计算出来。这种方法解决了矢量图型在GPU上的渲染，但涉及较复杂的shader，不能适用于配置较低的硬件。
KlayGE中的方法
KlayGE的字体系统设计目标是一个快速、易于实现、支持字体的高质量放缩，同时内存占用不应该太多，且适用于DX7以上硬件。为达到这个目的，我们选择了“可放缩的点阵字体”这条路线。
通过对点阵字体的分析，可以发现点阵字体不能放缩的根本原因是，点阵中每一个元素所代表的含义是sub-pixel的coverage信息[2]， 表示该元素所覆盖的区域有多少在字的轮廓中。举例来说，如果某个元素是0.5，就表示这块区域有50%在字内。这样的一个coverage信息是非线性 的，无法通过线性插值得到平滑的结果。所以强制对它进行放缩（线性插值）就会产生锯齿和间断等artifact。如果放弃使用coverage信息，而用 线性的距离作为元素存储的内容，就可以在一定程度上克服放缩的麻烦。所以，我们在点阵上不存储传统的coverage，而存储signed distance field。
核心算法
经过分析，该字体系统的字形需要表示成signed distance field信息。做到这一点需要经过以下4个步骤。
第一步：生成大位图
在KFontGen中，这一步是通过freetype[3]读取矢量字体，渲染一张4096×4096的灰度图。如下图所示（为了本文的显示方便，已经缩小到了512×512，下同）：
图1. 用freetype读取truetype矢量字体生成的二值化位图
第二步：轮廓搜索
freetype生成的灰度图是经过光栅化的，也就是说字的轮廓和内部都进行了填充。我们只关心轮廓本身，所以在这一步，我们需要提取出它的轮廓，也就是同时满足
- 该元素的值不为0
- 该元素的8个相邻元素存在0
这两个条件的元素。把轮廓元素标识为1，其他标示为0，就可以提取到的下图所示的轮廓：
图2. 从灰度图提取轮廓
第三步：得到distance field
一般来说，目标字体大小远远小于4096×4096。所以这里需要把对上一步得到的大位图进行离散采样，得到目标字体大小的点阵。在默认情况 下，KFontGen生成的目标字体大小是32×32。也就是说，从(64, 64)开始，x和y方向分别每隔128采一个点。分别计算这些采样点到轮廓的最近距离，这样得到的就是一个32×32的distance field。同时，在采样的时候，根据步骤一得到的灰度图可以判断一个采样点是否在字内，如果在字内，这个距离就是正数，否则就是负数。由此可以得到所要 的signed distance field。
第四步：量化和压缩
上一步得到的distance field每一个元素都是个float的数据，需要量化成每个元素8位，以减少空间占用，加速渲染。量化之后的数据经过LZMA压缩后存入文件中。上面例子的distance field经过量化可以得到一张小位图：
图3. 量化后的signed distance field位图
实现细节
这四个步骤原理虽然简单，但在实际实现中，需要经过比较深入的优化才能得到实用级别的速度。
二值化灰度图
步骤一得到的灰度图是存成BYTE的形式，每个元素一个字节。实际上我们需要的只是一个0，1的二值信息，表示一个元素是否在字内。所以我们需要对 它进行二值化操作，不但节省空间，而且加速了后面的步骤。对于灰度图中的每一个元素，取它的最高位，就可以生成前述的二值化位图。注意：freetype 虽然可以直接生成单色图，但是这样生成的结果锯齿很多，无法达到高质量的要求。虽然FT_Load_Char可以生成字符的灰度图，但在profile的 过程中发现30%的时间竟然在它的memset上。为了提高这个步骤的效率，应该调用的函数是FT_Outline_Render，通过设置call back来那到freetype的渲染结果。freetype的rasterizer会在光栅化出每一条水平线的时候调用那个call back，传入的是line的起点x, y，length和coverage。coverage < 128的line可以直接忽略，剩下的按照每个像素一个bit直接填入二值化位图中。这样，每个像素的开销从memset写入8-bit、 rasterizer写入8-bit coverage、读取8-bit coverage、写入1-bit，简化成了memset写入1-bit、call back写入1-bit，IO减少了很多。而由于瓶颈因此从IO转向计算，并行性大大提高，在多核CPU上，处理速度可以线性地随着核的数量增长而增长。
SSE2的PMOVMSKB指令加速二值化
SSE2提供了PMOVMSKB指令，可以在一次提取存放在一个XMM中的16个BYTE的最高位，放入一个unsigned short中。这样能把二值化的速度提高数倍。[4]
通过and和xor可以加速轮廓搜索
一旦用一个bit表示一个元素，就可以通过位运算来搜索轮廓。根据前面提出的轮廓条件可以推出，如果下面的表达式：
center & (center ^ (center & up & down & left & right))
不为0，那么该元素在轮廓上；否则就不属于轮廓。其中center表示要检测的元素，up、down、left和right分别表示该元素的上下左右四个相邻元素。在这里用SSE2可以进一步加速and和xor。[4]
用Danielsson distance transform生成最近邻
轮廓提取的结果可以看成是一个点集，集合中每个点都在轮廓上。计算distance field的本质就是计算采样点到这个点集的最短距离。这个操作可以用KD-tree来加速[1]。 把点集建立成一棵KD-tree，然后用每个采样点的坐标去查询KD-tree，得到最近的轮廓点。计算它们之间的距离就可以得到该采样点到轮廓的最短距 离。但是，KD-tree的每次搜索都是独立的，distance filed上每个元素的搜索都没法利用到邻近元素的结果。而用Danielsson distance transform[9]对目标点集做固定次数的扫描，每个点可以根据周围点的最近邻搜索结果来更新自己的信息，一次操作就可以得到所有点的最近邻。平均速度比用KD-tree的方法快50%。
经过这些优化，在Pentium Core2 2.3GHz, 4GB DDR2-800的机器上可以做到174字/秒的速度。
结果与比较
从恢复的结果来看，32×32的signed distance field恢复成16×16到512×512的点阵都可以得到不错的效果，边缘比较平滑，没有明显锯齿。相比之下，用linear方式直接放缩32×32的点阵，到了128×128的质量就严重下降了。
| 分辨率 | 基于signed distance field的方法 | 直接放缩点阵 |
|---|---|---|
| 16×16 |  |
 |
| 32×32 |  |
 |
| 64×64 |  |
 |
| 128×128 |  |
 |
| 256×256 |  |
 |
| 512×512 |  |
 |
基于distance field的字体一些其它优势
1. 可以通过调整scale在运行期无开销地改变笔划粗细：
| scale | 30 | 50 | 100 |
|---|---|---|---|
| 恢复结果 |  |
 |
 |
2. 勾边很容易，只要把某一距离的像素填上特定颜色即可：
3. 给文字加上soft shadow
总结和发展
基于distance field的字体能在和点阵字体存储结构相同的情况下获得更好的渲染效果，尤其是支持一定程度上的高质量放缩。由于把与矢量相关的计算挪到了预计算的部分，它的实时渲染的过程和一般点阵是一样的，远比直接渲染矢量字体来得简单。
本方法建立了矢量通往点阵的桥梁，可以很容易推广到一般矢量图的存储和渲染。任意的矢量图都可以用前述的算法转化成signed distance field并渲染。如果要支持彩色矢量图，可以把颜色保存在RGB通道，distance保存在A通道。另外，还可以使用每通道16 bit或32 bit的格式，或者较大的distance field，以达到更高精度的要求。
在渲染distance field的时候，也可以使用Marching cubes算法[8]（准确地说，是它的2D简化版本Marching squares[7]）建立出矢量图形的三角形网格。这样，渲染的时候就不再是处理点阵，而是渲染生成的三角形网格，可以利用上其他的基于三角形渲染的特效。
参考资料
[1] Bentley, J. L. Multidimensional binary search trees used for associative searching. In: Commun. ACM 18, 9 (Sep. 1975), 509-517.
[2] Chris Green, Improved Alpha-Tested Magnification for Vector Textures and Special Effects, GDC 2008
[3] Freetype. A Free, High-Quality, and Portable Font Engine. http://freetype.sourceforge.net/.
[4] Intel, Intel® 64 and IA-32 Architectures Software Developer’s Manuals. http://www.intel.com/products/processor/manuals/.
[5] Ray, N., Neiger, T., Cavin, X., and Levy, B. 2005. Vector texture maps on the GPU. In Technical Report ALICE-TR-05-003.
[6] Wikipedia, Computer font. http://en.wikipedia.org/wiki/Computer_font.
[7] Wikipedia, Marching squares. http://en.wikipedia.org/wiki/Marching_squares.
[8] William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987
[9] H Breu, J Gil, D Kirkpatrick, M Werman. Linear time Euclidean distance transform algorithms. In: IEEE Trans. Pattern Analysis and Machine Intell. 17(5), 529-533, 1995
版本更新
Revision 2
- 二值化的步骤改用call back实现
- 用Danielsson distance transform生成最近邻
- 在2-core的情况下总体速度提升3倍以上
Revision 1
- 初次发布
Comments