转载请注明出处为KlayGE游戏引擎,本文的永久链接为http://www.klayge.org/?p=202

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生成的灰度图是经过光栅化的,也就是说字的轮廓和内部都进行了填充。我们只关心轮廓本身,所以在这一步,我们需要提取出它的轮廓,也就是同时满足

  1. 该元素的值不为0
  2. 该元素的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 restore_16 linear_16
32×32 restore_32 linear_32
64×64 restore_64 linear_64
128×128 restore_128 linear_128
256×256 restore_256 linear_256
512×512 restore_512 linear_512

基于distance field的字体一些其它优势

1. 可以通过调整scale在运行期无开销地改变笔划粗细:

scale 30 50 100
恢复结果 restore_128_30 restore_128_50 restore_128_100

2. 勾边很容易,只要把某一距离的像素填上特定颜色即可:

outline

3. 给文字加上soft shadow

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

  • 初次发布