Gongminmin at 16:03, 30 April 2012

2012-04-30T16:03:22Z

Gongminmin: 3个修订

2011-03-28T05:16:25Z

3个修订

Gongminmin: 1个修订

2011-03-28T05:14:52Z

1个修订

Gongminmin at 07:58, 11 December 2010

2010-12-11T07:58:20Z

New page

== 简介 ==

众所周知，字体显示是所有游戏引擎都会涉及到的一个功能组件。[[KlayGE]]实现此功能的方式是通过点阵的形式存储和显示信息，但其呈现的字体支持一定程度上的高质量放缩，兼具了矢量图的优点。

== 以往的工作 ==

目前的[[字体系统]]多种多样，从存储方式上看可分为点阵和矢量两大类。

点阵字体系统把每一个字存储成固定大小的点阵位图，常见的大小有16x16和32x32等。其中每个字形都用一组二维像素信息表示。这种文字显示方式于较早前的电脑系统（例如未有图形接口时的DOS操作系统）被普遍采用。常见的纯点阵字体有 bdf，pcf，fnt，hbf 等格式<ref name="wikipedia_font">Wikipedia, Computer font. http://en.wikipedia.org/wiki/Computer_font.</ref>。点阵字体的优点是具有简单快速的显示方式，且不受硬件限制；但是它的缺点也比较突出，即：实现高质量的放缩相对困难，特定的点阵字体只能清晰地显示在相应的字号下，否则显示的字型只能因被强行放大而失真，产生成马赛克式的锯齿边缘。因此为了满足各种显示需求，许多字体都需要要依照型号大小预先存储多套，使得字体所占的空间随着精度要求迅速上升。如果没有找到合适大小的字体，显示质量就会受到很大影响。

在矢量字体系统中，每一个字形都表示成一组数学曲线描述的轮廓，它包含了字形边界上的关键点，连线的导数信息等。在显示字体时，渲染引擎通过读取其数学矢量，并进行一定的数学运算来实现渲染，字的内部则通过光栅化来填充。矢量字体主要包括Type1和TrueType等几类<ref name="wikipedia_font" />。矢量字体的优点是存储空间小，可以无限放缩而不产生变形；缺点是显示系统复杂，需要很多操作才能显示出矢量资源，因而速度较慢，也不适用于一些硬件。

随着硬件的发展，Ray等人提出了一种新的矢量存储方式<ref>Ray, N., Neiger, T., Cavin, X., and Levy, B. 2005. Vector texture maps on the GPU. In Technical Report ALICE-TR-05-003.</ref>。它把矢量图分解成许多区域，每个区域用一个多项式表示。通过把多项式的系数存在纹理中，矢量纹理就可以在pixel shader中很好的计算出来。这种方法解决了矢量图型在GPU上的渲染，但涉及较复杂的shader，不能适用于配置较低的硬件。

== [[KlayGE]]中的方法 ==

[[KlayGE]]的字体系统设计目标是一个快速、易于实现、支持字体的高质量放缩，同时内存占用不应该太多，且适用于DX7以上硬件。为达到这个目的，我们选择了“可放缩的点阵字体”这条路线。

通过对点阵字体的分析，可以发现点阵字体不能放缩的根本原因是，点阵中每一个元素所代表的含义是sub-pixel的coverage信息<ref>Chris Green, Improved Alpha-Tested Magnification for Vector Textures and Special Effects, GDC 2008</ref>，表示该元素所覆盖的区域有多少在字的轮廓中。举例来说，如果某个元素是0.5，就表示这块区域有50%在字内。这样的一个coverage信息是非线性的，无法通过线性插值得到平滑的结果。所以强制对它进行放缩（线性插值）就会产生锯齿和间断等artifact。如果放弃使用coverage信息，而用线性的距离作为元素存储的内容，就可以在一定程度上克服放缩的麻烦。所以，我们在点阵上不存储传统的coverage，而存储signed distance field。

=== 核心算法 ===

经过分析，该字体系统的字形需要表示成signed distance field信息。做到这一点需要经过以下4个步骤。

==== 第一步：生成大位图 ====

在KFontGen中，这一步是通过freetype<ref>Freetype. A Free, High-Quality, and Portable Font Engine. http://freetype.sourceforge.net/.</ref>读取矢量字体，渲染一张4096x4096的灰度图。如下图所示（为了本文的显示方便，已经缩小到了512x512，下同）：

[[File:Font_R2_Char.png]]

图1. 用freetype读取truetype矢量字体生成的二值化位图

==== 第二步：轮廓搜索 ====

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

#该元素的值不为0
#该元素的8个相邻元素存在0

这两个条件的元素。把轮廓元素标识为1，其他标示为0，就可以提取到的下图所示的轮廓：

[[File:Font_R2_Edge.png]]

图2. 从灰度图提取轮廓

==== 第三步：得到distance field ====

一般来说，目标字体大小远远小于4096x4096。所以这里需要把对上一步得到的大位图进行离散采样，得到目标字体大小的点阵。在默认情况下，KFontGen生成的目标字体大小是32x32。也就是说，从(64, 64)开始，x和y方向分别每隔128采一个点。分别计算这些采样点到轮廓的最近距离，这样得到的就是一个32x32的distance field。同时，在采样的时候，根据步骤一得到的灰度图可以判断一个采样点是否在字内，如果在字内，这个距离就是正数，否则就是负数。由此可以得到所要的signed distance field。

==== 第四步：量化和压缩 ====

上一步得到的distance field每一个元素都是个float的数据，需要量化成每个元素8位，以减少空间占用，加速渲染。量化之后的数据经过LZMA压缩后存入文件中。上面例子的distance field经过量化可以得到一张小位图：

[[File:Font_R2_Dist.png]]

图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中。这样能把二值化的速度提高数倍。<ref name="intel_manuals">Intel, Intel® 64 and IA-32 Architectures Software Developer's Manuals. http://www.intel.com/products/processor/manuals/.</ref>

==== 通过and和xor可以加速轮廓搜索 ====

一旦用一个bit表示一个元素，就可以通过位运算来搜索轮廓。根据前面提出的轮廓条件可以推出，如果下面的表达式：

center & (center ^ (center & up & down & left & right))

不为0，那么该元素在轮廓上；否则就不属于轮廓。其中center表示要检测的元素，up、down、left和right分别表示该元素的上下左右四个相邻元素。在这里用SSE2可以进一步加速and和xor。<ref name="intel_manuals" />

==== 用Danielsson distance transform生成最近邻 ====

轮廓提取的结果可以看成是一个点集，集合中每个点都在轮廓上。计算distance field的本质就是计算采样点到这个点集的最短距离。这个操作可以用KD-tree来加速<ref>Bentley, J. L. Multidimensional binary search trees used for associative searching. In: Commun. ACM 18, 9 (Sep. 1975), 509-517.</ref>。把点集建立成一棵KD-tree，然后用每个采样点的坐标去查询KD-tree，得到最近的轮廓点。计算它们之间的距离就可以得到该采样点到轮廓的最短距离。但是，KD-tree的每次搜索都是独立的，distance filed上每个元素的搜索都没法利用到邻近元素的结果。而用Danielsson distance transform<ref>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</ref>对目标点集做固定次数的扫描，每个点可以根据周围点的最近邻搜索结果来更新自己的信息，一次操作就可以得到所有点的最近邻。平均速度比用KD-tree的方法快50%。

经过这些优化，在Pentium Core2 2.3GHz, 4GB DDR2-800的机器上可以做到174字/秒的速度。

== 结果与比较 ==

从恢复的结果来看，32x32的signed distance field恢复成16x16到512x512的点阵都可以得到不错的效果，边缘比较平滑，没有明显锯齿。相比之下，用linear方式直接放缩32x32的点阵，到了128x128的质量就严重下降了。
{|border="1" cellspacing="0" cellpadding="5"
|'''分辨率'''||'''基于signed distance field的方法'''||'''直接放缩点阵'''
|-
|16x16||[[File:Font_R2_Restore_16.png]]||[[File:Font_R2_Linear_16.png]]
|-
|32x32||[[File:Font_R2_Restore_32.png]]||[[File:Font_R2_Linear_32.png]]
|-
|64x64||[[File:Font_R2_Restore_64.png]]||[[File:Font_R2_Linear_64.png]]
|-
|128x128||[[File:Font_R2_Restore_128.png]]||[[File:Font_R2_Linear_128.png]]
|-
|256x256||[[File:Font_R2_Restore_256.png]]||[[File:Font_R2_Linear_256.png]]
|-
|512x512||[[File:Font_R2_Restore_512.png]]||[[File:Font_R2_Linear_512.png]]
|}

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

1. 可以通过调整scale在运行期无开销地改变笔划粗细：
{|border="1" cellspacing="0" cellpadding="5"
|'''scale'''||'''30'''||'''50'''||'''100'''
|-
|恢复结果||[[File:Font_R2_Restore_128_30.png]]||[[File:Font_R2_Restore_128_50.png]]||[[File:Font_R2_Restore_128.png]]
|}

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

[[File:Font_R2_Outline.png]]

3. 给文字加上soft shadow

[[File:Font_R2_Soft_Shadow.png]]

== 总结和发展 ==

基于distance field的字体能在和点阵字体存储结构相同的情况下获得更好的渲染效果，尤其是支持一定程度上的高质量放缩。由于把与矢量相关的计算挪到了预计算的部分，它的实时渲染的过程和一般点阵是一样的，远比直接渲染矢量字体来得简单。

本方法建立了矢量通往点阵的桥梁，可以很容易推广到一般矢量图的存储和渲染。任意的矢量图都可以用前述的算法转化成signed distance field并渲染。如果要支持彩色矢量图，可以把颜色保存在RGB通道，distance保存在A通道。另外，还可以使用每通道16 bit或32 bit的格式，或者较大的distance field，以达到更高精度的要求。

在渲染distance field的时候，也可以使用Marching cubes算法<ref>William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987</ref>（准确地说，是它的2D简化版本Marching squares<ref>Wikipedia, Marching squares. http://en.wikipedia.org/wiki/Marching_squares.</ref>）建立出矢量图形的三角形网格。这样，渲染的时候就不再是处理点阵，而是渲染生成的三角形网格，可以利用上其他的基于三角形渲染的特效。

== 参考资料 ==
<references />

Gongminmin at 06:59, 11 December 2010

2010-12-11T06:59:44Z

Show changes

Gongminmin at 06:56, 11 December 2010

2010-12-11T06:56:36Z

Gongminmin: Created page with "= 简介 = 众所周知，字体显示是所有游戏引擎都会涉及到的一个功能组件。KlayGE实现此功能的方式是通过点阵的形式存储和显示信息，..."

2010-12-11T06:56:08Z

Created page with "= 简介 = 众所周知，字体显示是所有游戏引擎都会涉及到的一个功能组件。KlayGE实现此功能的方式是通过点阵的形式存储和显示信息，..."