Jump Flooding Algorithm

什么是有向距离场以及它能用来干什么有向距离场记录的是从一个点到集合边界的的距离值，其值的正负对应该点在集合外部或内部。有向距离场有很广的应用范围可以用来简单的生成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....