在 Unity 中使用 JFA (Jump Flood Algorithm) 快速生成 SDF (Signed Distance Field)

摘要：本文介绍在Unity中使用Jump Flood Algorithm(JFA)高效生成Signed Distance Field(SDF)的方法，通过GPU并行处理种子图的迭代传播，最终通过像素坐标差计算SDF图，显著提升距离场生成效率。

What is JFA

这是一个用于构建 Voronoi 图和 SDF 图的算法.

其在GPU上效率很高

Algorithm

首先我们有一张 $N*N$ 的种子图

比如下图:

其中有颜色的地方为种子, 没有的则是’未定义’

随着算法迭代, 最终整张图的想读都会被’定义’

‍

伪代码如下:

对于每个步长 $k \in \{ \frac{N}{2}, \frac{N}{4}, \dots, 1 \}$, 执行一次 JFA

遍历$(x,y)$处的每一个像素$p$

	对于每一个在$(x+i,y+j)$处的像素$q$ ( $i, j \in \{-k, 0, k\}$)

		如果$p$未定义且$q$着色

			将$p$的颜色更改为$q$的颜色

		如果$p$着色且$q$着色

			$p$的颜色使用 `min(dist(p,s),dist(q,s'))`, 其中, $s$ 和 $s'$ 分别是 $p$ 和 $q$ 的种子颜色

JFA to SDF

我们让JFA种子图中的每个像素存储当前位置的UV坐标，那么最终我们就得到了一张存储了离该像素最近的“物体像素”的 UV 坐标的纹理

那么, 轻易可以得到:
$SDF = distance(当前像素坐标, 最近物体像素坐标)$

当然, 这里没有考虑屏幕比例

Unity Implementation

可以看这个仓库