KlayGE游戏引擎

在2010年字体生成工具经历了一次提速，通过只填充边缘、SSE2、Danielsson distance transform后，速度已经较快，而且很难再提升了。前不久一个朋友周赫发现了一篇paper Anti-aliased Euclidean distance transform[1]。该文提供了一个新的生成距离场的算法，只需要较小的灰度图，就能估算出叫高精度的距离场，该算法已经用于freetype-gl。这给KlayGE的字体生成工具提供了一个再次大幅度提速的机会，所以在KlayGE 4.5中，我尝试实现了这个算法。

原算法回顾

原算法的完整描述可以在这里找到。总的来说，可以把距离场的生成概括成这几个步骤。

1. 通过freetype生成光栅化的4096×4096的灰度图，转成二值位图。
2. 轮廓提取，得到4096×4096的轮廓二值位图。
3. 通过Danielsson distance transform计算32×32的signed distance field。

这里的一个很大的瓶颈就是需要光栅化出一个4096×4096的位图。虽然可以通过给freetype一个callback的方式减少IO，但那么大的位图仍会产生不小的内存和计算压力。轮廓提取的时候，那么大的位图产生的轮廓点也非常的多。这一切都降低了这个算法的速度。

新算法

如果能减小原位图大小，就能提升算法速度。理论上提速的比例应该和位图大小成正比。[1]中的算法输入为一个anti-aliased的位图，输出是一个同大小的signed distance field，并保证质量和原先接近。也就是说，对于32×32的距离场，只需要32×32的灰度图！

实际测试的效果来看，同大小的AA灰度图并不能产生足够好的质量，并会丢失一些很细的线。但4倍大小的时候，就已经和原算法产生的距离场没区别了。所以新算法概括如下。

1. 通过freetype生成128×128的灰度图，带AA标志。
2. 降采样得到64×64的灰度图。
3. 生成64×64的梯度场，再降采样一次得到32×32的梯度场。
4. 用[1]的算法得到signed distance field。

这个新算法的计算量大于原算法，但IO减少了近千倍。目前最终速度提高了4倍。

未来

现在我只是采用freetype-gl的实现，还没做任何优化，速度远没达到理论值。在未来的版本里，速度会继续提高。如果速度足够快，甚至可以在loading time做字体转换，而不用在offline做。这样就能用系统的字体，而不用在程序包里提供一个字库。