Difference between revisions of "字体系统"

From KlayGE
Jump to: navigation, search
m
m
Line 1: Line 1:
−
= 简介 =
+
== 简介 ==
  
−
众所周知，字体显示是所有游戏引擎都会涉及到的一个功能组件。KlayGE实现此功能的方式是通过点阵的形式存储和显示信息，但其呈现的字体支持一定程度上的高质量放缩，兼具了矢量图的优点。
+
众所周知，字体显示是所有游戏引擎都会涉及到的一个功能组件。[[KlayGE]]实现此功能的方式是通过点阵的形式存储和显示信息，但其呈现的字体支持一定程度上的高质量放缩，兼具了矢量图的优点。
  
−
= 以往的工作 =
+
== 以往的工作 ==
  
−
目前的字体系统多种多样，从存储方式上看可分为点阵和矢量两大类。
+
目前的[[字体系统]]多种多样，从存储方式上看可分为点阵和矢量两大类。
  
 
点阵字体系统把每一个字存储成固定大小的点阵位图，常见的大小有16x16和32x32等。其中每个字形都用一组二维像素信息表示。这种文字显示方 式于较早前的电脑系统（例如未有图形接口时的DOS操作系统）被普遍采用。常见的纯点阵字体有 bdf，pcf，fnt，hbf 等格式<ref name="wikipedia_font">Wikipedia, Computer font. http://en.wikipedia.org/wiki/Computer_font.</ref>。 点阵字体的优点是具有简单快速的显示方式，且不受硬件限制；但是它的缺点也比较突出，即：实现高质量的放缩相对困难，特定的点阵字体只能清晰地显示在相应 的字号下，否则显示的字型只能因被强行放大而失真，产生成马赛克式的锯齿边缘。因此为了满足各种显示需求，许多字体都需要要依照型号大小预先存储多套，使 得字体所占的空间随着精度要求迅速上升。如果没有找到合适大小的字体，显示质量就会受到很大影响。
 
点阵字体系统把每一个字存储成固定大小的点阵位图，常见的大小有16x16和32x32等。其中每个字形都用一组二维像素信息表示。这种文字显示方 式于较早前的电脑系统（例如未有图形接口时的DOS操作系统）被普遍采用。常见的纯点阵字体有 bdf，pcf，fnt，hbf 等格式<ref name="wikipedia_font">Wikipedia, Computer font. http://en.wikipedia.org/wiki/Computer_font.</ref>。 点阵字体的优点是具有简单快速的显示方式，且不受硬件限制；但是它的缺点也比较突出，即：实现高质量的放缩相对困难，特定的点阵字体只能清晰地显示在相应 的字号下，否则显示的字型只能因被强行放大而失真，产生成马赛克式的锯齿边缘。因此为了满足各种显示需求，许多字体都需要要依照型号大小预先存储多套，使 得字体所占的空间随着精度要求迅速上升。如果没有找到合适大小的字体，显示质量就会受到很大影响。
Line 13: Line 13:
 
随着硬件的发展，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，不能适用于配置较低的硬件。
 
随着硬件的发展，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]]中的方法 ==
  
−
KlayGE的字体系统设计目标是一个快速、易于实现、支持字体的高质量放缩，同时内存占用不应该太多，且适用于DX7以上硬件。为达到这个目的，我们选择了“可放缩的点阵字体”这条路线。
+
[[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。
 
通过对点阵字体的分析，可以发现点阵字体不能放缩的根本原因是，点阵中每一个元素所代表的含义是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个步骤。
 
经过分析，该字体系统的字形需要表示成signed distance field信息。做到这一点需要经过以下4个步骤。
  
−
=== 第一步：生成大位图 ===
+
==== 第一步：生成大位图 ====
  
 
在KFontGen中，这一步是通过freetype<ref>Freetype. A Free, High-Quality, and Portable Font Engine. http://freetype.sourceforge.net/.</ref>读取矢量字体，渲染一张4096x4096的灰度图。如下图所示（为了本文的显示方便，已经缩小到了512x512，下同）：
 
在KFontGen中，这一步是通过freetype<ref>Freetype. A Free, High-Quality, and Portable Font Engine. http://freetype.sourceforge.net/.</ref>读取矢量字体，渲染一张4096x4096的灰度图。如下图所示（为了本文的显示方便，已经缩小到了512x512，下同）：
Line 31: Line 31:
 
图1. 用freetype读取truetype矢量字体生成的二值化位图
 
图1. 用freetype读取truetype矢量字体生成的二值化位图
  
−
=== 第二步：轮廓搜索 ===
+
==== 第二步：轮廓搜索 ====
  
 
freetype生成的灰度图是经过光栅化的，也就是说字的轮廓和内部都进行了填充。我们只关心轮廓本身，所以在这一步，我们需要提取出它的轮廓，也就是同时满足
 
freetype生成的灰度图是经过光栅化的，也就是说字的轮廓和内部都进行了填充。我们只关心轮廓本身，所以在这一步，我们需要提取出它的轮廓，也就是同时满足
Line 44: Line 44:
 
图2. 从灰度图提取轮廓
 
图2. 从灰度图提取轮廓
  
−
=== 第三步：得到distance field ===
+
==== 第三步：得到distance field ====
  
 
一般来说，目标字体大小远远小于4096x4096。所以这里需要把对上一步得到的大位图进行离散采样，得到目标字体大小的点阵。在默认情况 下，KFontGen生成的目标字体大小是32x32。也就是说，从(64, 64)开始，x和y方向分别每隔128采一个点。分别计算这些采样点到轮廓的最近距离，这样得到的就是一个32x32的distance field。同时，在采样的时候，根据步骤一得到的灰度图可以判断一个采样点是否在字内，如果在字内，这个距离就是正数，否则就是负数。由此可以得到所要 的signed distance field。
 
一般来说，目标字体大小远远小于4096x4096。所以这里需要把对上一步得到的大位图进行离散采样，得到目标字体大小的点阵。在默认情况 下，KFontGen生成的目标字体大小是32x32。也就是说，从(64, 64)开始，x和y方向分别每隔128采一个点。分别计算这些采样点到轮廓的最近距离，这样得到的就是一个32x32的distance field。同时，在采样的时候，根据步骤一得到的灰度图可以判断一个采样点是否在字内，如果在字内，这个距离就是正数，否则就是负数。由此可以得到所要 的signed distance field。
  
−
=== 第四步：量化和压缩 ===
+
==== 第四步：量化和压缩 ====
  
 
上一步得到的distance field每一个元素都是个float的数据，需要量化成每个元素8位，以减少空间占用，加速渲染。量化之后的数据经过LZMA压缩后存入文件中。上面例子的distance field经过量化可以得到一张小位图：
 
上一步得到的distance field每一个元素都是个float的数据，需要量化成每个元素8位，以减少空间占用，加速渲染。量化之后的数据经过LZMA压缩后存入文件中。上面例子的distance field经过量化可以得到一张小位图：
Line 56: Line 56:
 
图3. 量化后的signed 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上，处理速度可以线性地随着核的数量增长而增长。
 
步骤一得到的灰度图是存成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指令加速二值化 ====
  
 
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>
 
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可以加速轮廓搜索 ===
+
==== 通过and和xor可以加速轮廓搜索 ====
  
 
一旦用一个bit表示一个元素，就可以通过位运算来搜索轮廓。根据前面提出的轮廓条件可以推出，如果下面的表达式：
 
一旦用一个bit表示一个元素，就可以通过位运算来搜索轮廓。根据前面提出的轮廓条件可以推出，如果下面的表达式：
Line 76: Line 76:
 
不为0，那么该元素在轮廓上；否则就不属于轮廓。其中center表示要检测的元素，up、down、left和right分别表示该元素的上下左右四个相邻元素。在这里用SSE2可以进一步加速and和xor。<ref name="intel_manuals" />
 
不为0，那么该元素在轮廓上；否则就不属于轮廓。其中center表示要检测的元素，up、down、left和right分别表示该元素的上下左右四个相邻元素。在这里用SSE2可以进一步加速and和xor。<ref name="intel_manuals" />
  
−
=== 用Danielsson distance transform生成最近邻 ===
+
==== 用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%。
 
轮廓提取的结果可以看成是一个点集，集合中每个点都在轮廓上。计算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%。
Line 82: Line 82:
 
经过这些优化，在Pentium Core2 2.3GHz, 4GB DDR2-800的机器上可以做到174字/秒的速度。
 
经过这些优化，在Pentium Core2 2.3GHz, 4GB DDR2-800的机器上可以做到174字/秒的速度。
  
−
= 结果与比较 =
+
== 结果与比较 ==
  
 
从恢复的结果来看，32x32的signed distance field恢复成16x16到512x512的点阵都可以得到不错的效果，边缘比较平滑，没有明显锯齿。相比之下，用linear方式直接放缩32x32的点阵，到了128x128的质量就严重下降了。
 
从恢复的结果来看，32x32的signed distance field恢复成16x16到512x512的点阵都可以得到不错的效果，边缘比较平滑，没有明显锯齿。相比之下，用linear方式直接放缩32x32的点阵，到了128x128的质量就严重下降了。
Line 100: Line 100:
 
|512x512||[[File:Font_R2_Restore_512.png]]||[[File:Font_R2_Linear_512.png]]
 
|512x512||[[File:Font_R2_Restore_512.png]]||[[File:Font_R2_Linear_512.png]]
 
|}
 
|}
−
= 基于distance field的字体一些其它优势 =
+
 
 +
== 基于distance field的字体一些其它优势 ==
  
 
1. 可以通过调整scale在运行期无开销地改变笔划粗细：
 
1. 可以通过调整scale在运行期无开销地改变笔划粗细：
Line 117: Line 118:
 
[[File:Font_R2_Soft_Shadow.png]]
 
[[File:Font_R2_Soft_Shadow.png]]
  
−
= 总结和发展 =
+
== 总结和发展 ==
  
 
基于distance field的字体能在和点阵字体存储结构相同的情况下获得更好的渲染效果，尤其是支持一定程度上的高质量放缩。由于把与矢量相关的计算挪到了预计算的部分，它的实时渲染的过程和一般点阵是一样的，远比直接渲染矢量字体来得简单。
 
基于distance field的字体能在和点阵字体存储结构相同的情况下获得更好的渲染效果，尤其是支持一定程度上的高质量放缩。由于把与矢量相关的计算挪到了预计算的部分，它的实时渲染的过程和一般点阵是一样的，远比直接渲染矢量字体来得简单。
Line 125: Line 126:
 
在渲染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>）建立出矢量图形的三角形网格。这样，渲染的时候就不再是处理点阵，而是渲染生成的三角形网格，可以利用上其他的基于三角形渲染的特效。
 
在渲染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 />
 
<references />

Revision as of 01:59, 11 December 2010

简介

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

以往的工作

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

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

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

随着硬件的发展，Ray等人提出了一种新的矢量存储方式[2]。它把矢量图分解成许多区域，每个区域用一个多项式表示。通过把多项式的系数存在纹理中，矢量纹理就可以在pixel shader中很好的计算出来。这种方法解决了矢量图型在GPU上的渲染，但涉及较复杂的shader，不能适用于配置较低的硬件。

KlayGE中的方法

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

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

核心算法

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

第一步：生成大位图

在KFontGen中，这一步是通过freetype[4]读取矢量字体，渲染一张4096x4096的灰度图。如下图所示（为了本文的显示方便，已经缩小到了512x512，下同）：

Font R2 Char.png

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

第二步：轮廓搜索

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

  1. 该元素的值不为0
  2. 该元素的8个相邻元素存在0

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

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经过量化可以得到一张小位图：

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中。这样能把二值化的速度提高数倍。[5]

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

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

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

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

用Danielsson distance transform生成最近邻

轮廓提取的结果可以看成是一个点集，集合中每个点都在轮廓上。计算distance field的本质就是计算采样点到这个点集的最短距离。这个操作可以用KD-tree来加速[6]。 把点集建立成一棵KD-tree，然后用每个采样点的坐标去查询KD-tree，得到最近的轮廓点。计算它们之间的距离就可以得到该采样点到轮廓的最短距 离。但是，KD-tree的每次搜索都是独立的，distance filed上每个元素的搜索都没法利用到邻近元素的结果。而用Danielsson distance transform[7]对目标点集做固定次数的扫描，每个点可以根据周围点的最近邻搜索结果来更新自己的信息，一次操作就可以得到所有点的最近邻。平均速度比用KD-tree的方法快50%。

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

结果与比较

从恢复的结果来看，32x32的signed distance field恢复成16x16到512x512的点阵都可以得到不错的效果，边缘比较平滑，没有明显锯齿。相比之下，用linear方式直接放缩32x32的点阵，到了128x128的质量就严重下降了。

分辨率 基于signed distance field的方法 直接放缩点阵
16x16 Font R2 Restore 16.png Font R2 Linear 16.png
32x32 Font R2 Restore 32.png Font R2 Linear 32.png
64x64 Font R2 Restore 64.png Font R2 Linear 64.png
128x128 Font R2 Restore 128.png Font R2 Linear 128.png
256x256 Font R2 Restore 256.png Font R2 Linear 256.png
512x512 Font R2 Restore 512.png Font R2 Linear 512.png

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

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

scale 30 50 100
恢复结果 Font R2 Restore 128 30.png Font R2 Restore 128 50.png Font R2 Restore 128.png

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

Font R2 Outline.png

3. 给文字加上soft shadow

Font R2 Soft Shadow.png

总结和发展

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

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

在渲染distance field的时候，也可以使用Marching cubes算法[8]（准确地说，是它的2D简化版本Marching squares[9]）建立出矢量图形的三角形网格。这样，渲染的时候就不再是处理点阵，而是渲染生成的三角形网格，可以利用上其他的基于三角形渲染的特效。

参考资料

  1. ↑ 1.0 1.1 Wikipedia, Computer font. http://en.wikipedia.org/wiki/Computer_font.
  2. ↑ Ray, N., Neiger, T., Cavin, X., and Levy, B. 2005. Vector texture maps on the GPU. In Technical Report ALICE-TR-05-003.
  3. ↑ Chris Green, Improved Alpha-Tested Magnification for Vector Textures and Special Effects, GDC 2008
  4. ↑ Freetype. A Free, High-Quality, and Portable Font Engine. http://freetype.sourceforge.net/.
  5. ↑ 5.0 5.1 Intel, Intel® 64 and IA-32 Architectures Software Developer's Manuals. http://www.intel.com/products/processor/manuals/.
  6. ↑ Bentley, J. L. Multidimensional binary search trees used for associative searching. In: Commun. ACM 18, 9 (Sep. 1975), 509-517.
  7. ↑ 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
  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. ↑ Wikipedia, Marching squares. http://en.wikipedia.org/wiki/Marching_squares.
Retrieved from "http://klayge.org/wiki/index.php?title=字体系统&oldid=105"