///动态SDF字体实现要点//
使用SDF渲染字体最早比较出名的就是Valve在sigraph上的那篇论文了[1]，之后又有前辈大神实现了比较实用化的离线中文SDF静态字库[2]，到现在新版的Unity通过集成Text Mesh Pro已经可以很好且高效的实现动态SDF字体的渲染了。
对于Unity用户来说使用动态SDF字体来实现描边效果现在也就是勾选一个设置的事儿了。但是背后实现的原理还是非常想要研究一下，一是因为我目前在用UE4但美术却心心念Unity的描边效果，二就是因为当年自己大胆宣判过SDF Font的死刑，自己挖坑还是要自己填。
现在能写出这篇文章，自然是因为Text Mesh Pro已经把这块做好了，别人做好的东西拿出来说感觉是不太好，所以就只讲讲原理，分享一下收集到的相关论文（可能有墙），代码可以从链接的论文中去自己看。实现内容主要在1,2,3里，如果2没看太明白可以先看下4,5。
- 动态SDF Font实现概述
- 基于小尺寸的灰度图生成高质量的SDF图
- 高质量的SDF文字渲染
- SDF生成算法概览
- 光栅化扫描算法优化
- 静态SDF Font优化
1. 动态SDF Font实现概述
首先要做动态SDF字体的生成和渲染，Valve那篇论文可以直接扔掉了，静态字库的方案也可以Pass。原因有二：
- 首先是显而易见的，通过4096*4096的高精贴图来计算SDF贴图产生的开销是实时运行中承受不起的。
- 另外还有一个核心原因是，大部分时候驱动我们我们使用SDF字体的主要原因是我们希望能够基于SDF来高效高质量的实现如描边阴影等特殊文字效果，而不是用来做无损放大的，因此如果我们不能在光栅化时进行合理的抗锯齿处理，其文字渲染出来的效果将会非常显著的区别（差）于普通渲染出来的文字，差到无法进行实用。
（左）小号字的大部分点都是非整像素的。（右）TTF实际渲染出来的字符Bitmap是预先做了AA处理的，缩小为实际大小后看上去会很舒服。（中）如果简单的设置阈值进行SDF渲染，缩小后会表现为锯齿与抖动
要想实现可实用化的动态SDF字体渲染，我们就要解决上述的两个问题。解决方案就是对症下药：
- 基于TTF动态输出的字符点阵图实时生成其SDF图。
- 写一个适用于SDF字体渲染的Shader，这个Shader核心需要实现的功能是解决小分辨率SDF贴图采样后抗锯齿的问题。
2. 基于小尺寸的灰度图生成高质量SDF图
基于二值图生成SDF的算法在Valve的文章中并没有详细介绍，毕竟是离线计算的，即便是用本地空间暴力计算的方式来生成也不是不可接受，但若想实时生成的话就必须要有个在保证质量的情况下速度最快的算法。
后面的小节会对SDF生成算法进行更详细的分析，这里先说一下结论，就是目前时间复杂度是线性的生成算法中，8SSEDT(8-point Signed Sequential Euclidean Distance Transform)应该是综合速度与错误率性价比最高的。另外可选的方案还有Chamfer3x3 DT（错误率稍高，速度稍快）或者4SSEDT(速度很快，错误率偏高）。
单单有这些高效的算法是不够的，原因是这些算法都是基于二值图的，这也是为什么Valve的文章里在生成SDF图时使用的是4096尺寸的图片，本质上就是对于原图进行超采样以得到最精确的像素距离。但我们现在的需求是基于动态输出的字符点阵图来生成SDF，而字符点阵图中的像素经过AA处理后是灰度的，仅仅粗暴的通过设置阈值来区分点阵图中的前景与背景只能得到一个惨不忍睹的结果，跨像素（sub-pixel）的笔画线将不可避免的被处理成粗细不均，乃至更小的细节会直接丢失掉。
(a)一个圆点进行光栅化后的灰度图，虚线表示实际轮廓线。(b)放大局部区域可以看到轮廓线穿过的像素有不同的灰度值。(c)虚线为粗暴二值化后计算的距离，实线为正确距离，可以看出二者有明显的差距
因此我们需要还需要一个算法能够计算出像素点到真正轮廓线的最短距离，以修正常规的基于二值图的DT算法。这个算法可以说是SDF文字实现动态化的核心了，算法的名字叫做 Anti-aliased Euclidean Distance Transform。论文链接献上，直接看4、5节算法描述及优化就行，文末有源码链接。
这里我就简单概述一下他这个算法的思路：
- 定义：a=像素的灰度值，d=像素中心点到真实轮廓线的最近距离。
- 首先如果轮廓线水平或垂直的穿过一个像素，那么这个像素的灰度就能直接表示他的距离（比如轮廓线正好穿过像素中点时这个像素的颜色a应该是0.5对应距离的是0），写成公式就是：
- 如果轮廓线是斜穿过像素的，那么就需要基于这个轮廓线的梯度来计算，公式可以看论文自行推导，我就把图和结果给列一下：
（左）灰线表示轮廓线的方向，将一个像素分为了三个区域。（中）当轮廓线位于a1区域（0<a<a1）内时真实距离d的展示。（右）推导出来的公式
- 上面的公式是需要首先得到轮廓线在穿过该像素时的梯度的，而梯度的计算方式文章中没有细说，只是提到基于该像素周围一个3x3的梯度算子来进行模拟。梯度算子的选用那又是另一大领域了，不做展开自行百度搜索即可。因为我们在进行SDF计算的时候各项同性是一个跟重要的准确度保障点，所以为了保证效果可以用Isotropic Sobel算子来进行计算。
- 比较准确的能算出轮廓线上的像素到轮廓线的真实最短距离后，剩下的像素就可以按8SSEDT算法进行顺序推算了，对于不在轮廓线上但是离轮廓线也很近的像素，文中的优化小节中也给出了更精确的距离计算方式，这里就不过多赘述了。
3. 高质量的SDF文字渲染
游戏中动态字体的渲染流程简单来说是这样的：
- TTF将矢量字库中的字符，按照要求的尺寸输出为灰度点阵图，在这一过程中字库引擎处理了AA以及像素匹配
- 将字符灰度点阵图写入到字符图集纹理中，并记录其对应的uv位置和尺寸
- 计算字符面片的顶点位置，要保证其在像素中间，大小与字符图元一致，以得到最好的渲染效果
- 纹理、材质、模型传给GPU进行渲染
简单来说这一过程的核心目的，就是将光栅化好的文字点阵直接点对点的渲染到屏幕指定位置上，以到达最好的文字渲染质量。
好文字的光栅化看这张图就知道里面学问可深了，把大厨做好的菜能原封不动的端上桌就是游戏引擎在文字渲染过程中的角色
现在经过上一小节的处理，我们在第一步与第二步之间插入了灰度点阵图到SDF图的转换步骤。这相当于在将文字图集纹理传给GPU前重新把已经光栅化好的字符图像信息还原成了矢量信息，因此光栅化过程中抗锯齿的重担就需要在材质中进行额外处理了。这一步做的好坏也决定了这个SDF Font到底只是个技术玩具还是可以真正应用的字体渲染方案。
在Shader中对SDF纹理采样进行AA处理已经有不少文章写了，很好搜索，这里不做赘述了，直接给出最权威的文章链接，收录于OpenGL Insights：
有没有发现这个作者很眼熟，人家明显就是做事儿做全套的！
4. SDF生成算法概览
由二值图像生成SDF图的生成算法属于图形处理领域中的一个大类问题：DT（Distance Transform）。DT表示将图像中的点的值映射为到目标区域的最短距离的变换（用人话说就是把一张黑白图经过DT处理就变成了SDF图），这是很多图像识别处理的起手式，相关的论文和算法简直是多如牛毛。
根据对距离度量方式的不同，DT还可以分为两个子类：
- EDT[3]（Euclidean Distance Transform）: 特指使用欧几里得距离（两点直线距离）来计算的DT。对于SDF生成来说肯定用的是EDT了，这样才能保证线性采样的结果是正确的的。
- SWDT（Signed Weighted Distance Transform）: Chamfer DT, City Block DT, Chessboard DT，早期计算能力差的时候大部分的研究都在这一块，因为其距离的度量不是直线距离（City Block对应x+y，Chessboard对应max(x,y)，Chamfer的采样方式不是全角度因此无法做到各项向同性）
DT算法总体来说可以分为几大类，一类是光栅化扫描算法（Raster scan algorithms），前文介绍的8SSEDT就属于这个。另一类是传播算法（Propagation algorithms），还有独立扫描算法（Independent scanning algorithms）等等。
光栅化扫描算法简单直观好理解，速度相对也很快，时间复杂度都是O(N^2)。其他的咱也没细看，咱也不瞎说。感兴趣的可以看下面这篇论文 ，7.4节里介绍了所有的EDT算法。
5. 光栅化扫描算法优化
说回光栅化扫描算法，最早都是应用于SWDT的，直到Danielsson[4]提出了8SSEDT，后续Ye对这个算法进行了优化。扫描算法的思想非常简单，用朴素但不太准确的人话来说，就是每个像素到最近轮廓线的距离，可以通过遍历该像素点周围像素，求出周围像素已知的最近距离加上其到周围像素点的距离中最小的那个来得到。通过由左上到右下的遍历得到每个像素左上半边的最短距离，在通过由右下到左上的扫描遍历得到每个像素右下半边的最短距离，综合起来就得到了每个像素到轮廓线的全方向最近距离。
(a)早期的SWDT算法的扫描方式。(b)SEDT算法的扫描方式，多了mask 2和3，但是为了要求得正确的欧几里得距离，这两步必须的，没有这两步会导致斜线方向上的距离计算出现误差。
Ye对于8SSEDT优化的主要点在于原算法中每个点会记录 ，而其优化成了记录
，在计算基于相邻点的最短距离时以平方距离做最短距离比较
。减少了大量平方根的运算。
另外8SSEDT进行了四趟扫描，而最古老的3x3 SWDT只进行两趟扫描，看上去有两次扫描是多余的，实际上并不是，如果只进行两趟扫描的话对于左上和右上方向的距离计算会相较其他方向出现偏差，导致结果出现误差。但是另一方面，“这两种扫描方式产生误差相较于距离度量上的误差几乎可以忽略不计”（I. Ragnemalm. The Euclidean distance transform and its implementation on SIMD architectures）。
再给出一篇非常好的文章链接，里面详细的分析了这几种主要的扫描线DT算法，并给出了他们的性能开销对比和误差对比。
光栅化扫描算法综述pages.cs.wisc.edu/~dyer/cs766/readings/leymarie-cvgip92.pdf
pu是像素单位的意思，SSEDT产生的是绝对误差，0.09pu可以说是精度非常高了。相对的底下都是相对误差，与轮廓线的距离越远误差越大
6. 静态SDF Font优化
最后额外提一嘴静态SDF，如果需求就是大尺寸的字符LOGO渲染，那还是推荐使用静态的SDF的。 但是对于高质量的文字渲染来说，在我看来这个方案有两个点是不太能接受的，一个是圆角问题，第二个是缩小的问题。
缩小问题目前没有看到啥太好的解决方案，但是下面这个MSDF可以使用更低精度贴图来进行高质量的文字渲染，从某方面来说也算是解决了这个问题吧。
圆角问题的解决方案在写这篇文章时发现了一个叫做MSDF（Multi-channel Signed Distance Field）的技术，还没怎么细研究，但是效果看上去非常好，很好的解决了SDF放大渲染直角变圆角以及低精度SDF走样的问题。UE4商店里也看到插件了，先把链接放上回头慢慢研究吧。
https://github.com/Chlumsky/msdfgengithub.com/Chlumsky/msdfgen
参考
- ^Valve在游戏领域中的开山鼻祖文章 https://steamcdn-a.akamaihd.net/apps/valve/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf
- ^大神的静态SDF字库实现 KlayGE中的字体系统 - KlayGE游戏引擎
- ^Euclidean Distance Transform 论文集 http://www.lysator.liu.se/~ingemar/books/Ingemar%20Ragnemalm%20-%20The%20Euclidean%20Distance%20Transform%20(dissertation).pdf
- ^Sequential Euclidean Distance Transform (4/8 SEDT) - Danielsson http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.322.7605&rep=rep1&type=pdf
unity画个多边形如何用shader抗锯齿？
这个是七日之都的，可以看见多边形的锯齿恨严重。
崩坏三的好很多
别跟我说是弄好的一张UI图片或者开了抗锯齿…看过关于sdf 用 smoothstep搞，不知道能不能搞出来例如5边形的sdf？不过感觉效率绝对不如美术搞好一张图片贴上去的了
//
//