Signed Distance Field

动机和贝塞尔曲线相关的背景知识 动机当然是要在UI上绘制一个贝塞尔曲线的形状了，想做的效果大概就和虚幻引擎蓝图连接节点的线差不多了。这里要绘制的是一种较为特殊的贝塞尔曲线，它的两个端点的切线是水平的，且拥有旋转对称的特性。 我们想要绘制的S形曲线是三阶的贝塞尔曲线。三阶贝塞尔曲线有四个控制点\(P_0, P_1, P_2, P_3\)，对于一个从0到1的变量\(t\)，贝塞尔曲线的做法是对这四个点按照顺序以\(t\)做插值生成三个新的点，然后对这三个点按照顺序以\(t\)做插值生成新的两个点，再对这两个点以t做插值生成最后的点，当t在0到1中变化时，这个点的轨迹就构成了贝塞尔曲线。贝塞尔曲线上的点可以用四个控制点和\(t\)来表示： $$ P_{bezier} = P_0 \cdot (1 - t)^3 + 3 P_1 \cdot (1 - t)^2 \cdot t + 3 P_2 \cdot (1 - t) \cdot t^2 + P_3 \cdot t^3 $$ 如果初始四个点分别是(0.0, 1.0), (d, 1.0), (1.0 - d, 0.0)，和(1.0, 0.0)的话，也就是我们所要绘制的特殊的贝塞尔曲线，可以算出贝塞尔曲线的坐标为 $$ P_{bezier} = ((3 t - 9t ^ 2 + 6t^3) \cdot d + 3t^2 - 2t^3, 1 - 3t^2 + 2t^3) $$ 但是即使得到了贝塞尔曲线的参数方程，想要将其表达成\(f(x)\)的形式仍然是相当困难的。Alan Wolfe在他的博客中提到了一种一维贝塞尔曲线，也是一种贝塞尔曲线的特殊情况，四个控制点在水平方向上等距排开，这样子贝塞尔曲线的参数方程的水平分量就刚好是\(t\)，它的竖直分量也就是我们需要的\(f(x)\)。唯一美中不足的是，能轻易得到\(f(x)\)的一维贝赛尔曲线，往往是一个“躺倒”的贝赛尔曲线，感官上看上去是横着的，Shadertoy上有相关的演示。但这种一维贝塞尔曲线又有一种特殊情况，也就是前两个控制点的竖直高度相等，后两个控制点的竖直高度也相等，这时这种特殊的一维贝塞尔曲线就是我们耳熟能详的smoothstep曲线了（数学真奇妙啊）。可惜smoothstep不能满足我们随意控制曲线形状的需求，只能另求他法。...

什么是有向距离场以及它能用来干什么 有向距离场记录的是从一个点到集合边界的的距离值，其值的正负对应该点在集合外部或内部。有向距离场有很广的应用范围可以用来简单的生成Voronoi图形，可以用来做全局光照的计算，可以用来做两个形状的平滑的变形，可以用来做高清晰度的字体，也可以用来做Ray March（虽然我认为不如直接光线追踪求交来的效率高）。像原神就使用了SDF的方法，生成了角色脸部的阴影图，从而让角色脸部的阴影能自然的变化。 那么什么又是Jump Flooding Algorithm呢 Jump Flooding Algorithm是荣国栋在他的博士论文Jump Flooding Algorithm On Graphics Hardware And Its Applications提出的一种在GPU上运行的能够快速传播某个像素的信息到其他像素的算法。 普通的Flooding算法在一次运行中，固定向相邻的一个像素的像素传播信息，而Jump Flooding则是按照2的幂次递增或是递减来传播信息。这和之前提到的并行计算——Reduction的想法差不多。下图演示了普通的Flooding和Jump Flooding的过程： 使用JFA计算一张2D图片对应的SDF贴图 首先在Unity中创建JumpFlooding.cs, JFAComputeShader.compute, 和JFAVisualize.shader，分别用来执行Compute Shader，使用JFA算法计算SDF和可视化JFA算法的结果。 这里使用一张RGB通道为灰色，Alpha通道写着“JFA”的贴图作为我们2D图片的输入。 整体思路和需要注意的事项 先从简单实现功能上来考虑，暂时忽略掉抗锯齿的需求，直接对Alpha通道的值按照0.5来划分出图形的内部和外部，大于等于0.5为外部，小于0.5为内部。 SDF需要要计算距离，这里使用像素点中心到另一个像素点中心的距离（也可以使用像素点左下角到另一个像素点左下角的距离，不过为了明确起见，还是加上这半个像素的偏移比较好）。距离可以用uv的大小来表示，也可以用像素数量来表示，针对图像长宽不同的情况，这里以一个像素宽度为1来表示两个像素点的距离。在最后采样JFA的Render Texture的时候，也要注意使用sampler_PointClamp来进行采样，计算距离时也不能仅仅使用uv来计算，而是要使用像素中间的点的位置来进行计算。 普通的JFA算法会使用到Render Texture的两个通道，来标记像素对应的最近边界像素的UV，由于记录的是UV的数值而不是颜色信息，Render Texture要储存在线性空间中。由于要同时计算内部和外部的点到边界的有向距离，JFA算法会使用到Render Texture全部的四个通道，这里使用前两位记录位于内部的像素对应的边界像素的坐标，用后两位记录位于外部的像素对应的边界像素的坐标，即对于内部的像素(nearestUV.x, nearestUV.y, Z, W)，对于外部的像素(X, Y, nearestUV.x, nearestUV.y)，XYZW则可以用来表示该点为最初始的内外部的点、包含JFA传递的信息的点。不包含JFA传递的信息的点。 在JFA计算之前，需要先让贴图对应的点包含JFA信息，也就是说，对于内部的点初始化为(UV.x, UV.y, -1, -1)，对于外部的点初始化为(-1, -1, UV.x, UV.y)。这要求我们使用的Render Texture格式为至少R16G16B16A16 SFloat。 在JFA的计算中，以外部的像素点为例，所进行的操作是：采样上次经过JFA操作的Render Texture；根据XY通道判断该点在边界的内部还是外部，内部就跳过；对外部的像素点，通过XY通道判断是否已包含JFA的信息，如果包含，根据ZW通道计算出当前点到其包含的最近像素的距离，如果不包含，将这个距离设置为一个极大的常数；分别采样距离像素点2的幂次的距离的八个像素，判断这些像素是否已包含JFA的信息，如果不包含，采样下一个点，如果包含，根据这些像素的ZW通道计算出当前点到这些像素包含的最近像素的距离，并和上一步算出的距离进行比较，如果小于上一步算出的距离，则证明该像素对应的最近像素为周围点包含的像素，更新该像素的ZW通道，并且将XY通道标记成已包含JFA的信息。 采样周边像素的步长从2D贴图的长宽的一半向上取整开始，每次JFA都取上一步步长的一半向上取整作为新的步长，一直进行到步长为(1, 1)，进行最后一次JFA计算。 经过JFA计算之后，还需要将分别表示内部的点对应的最近像素的UV和外部的点对应的最近像素的UV结合起来，储存为一张贴图，可以是(nearestUV.x, nearestUV.y, 0, inside?1:0)，也可以是(distance * inside?-1:1, 1)。 应该是跟当前平台有关，有时候会出现贴图上下颠倒的情况，可以用UNITY_UV_STARTS_AT_TOP来协助解决，不过compute shader可能需要自己启用这个宏，这里就直接硬写在shader里，不做平台判断了。 JFAComputeShader.compute 根据上面的整体思路，我们需要三个kernel，一个用来初始化，一个做JFA计算，最后一个用来合成最后的贴图。Compute Shader的关键字需要Unity 2020以上（我也不知道具体哪个版本）才能有，这里就暂时用UNITY_2020_2_OR_NEWER这个宏来屏蔽了。 #pragma kernel CopyUVMain #define PIXEL_OFFSET 0....