3D SDF的快速生成

本文所述内容的GPU实现：SDFGenerator

给定封闭表面$M$，可以根据$M$定义一个空间中的标量函数：

$u(p)$表示网格表面到$p$的最近距离，称为无符号距离场（unsigned distance field，UDF）。基于$u$，我们可以定义出另一个函数：

$s$就是本文的主角，被称为有符号距离场（signed distance field，SDF）。

对一般的$M$，SDF不具备解析形式，且计算非常耗时。因此，我们通常会预计算物体的SDF，供运行时快速查询使用。SDF的压缩/近似是一个非常困难的问题，不在本文覆盖的范围内。本文仅讨论三维空间下针对三角网格的SDF生成，生成结果以三维数组的形式存储。

根据定义，可以很容易想到下述暴力方法：

当三角形数目和三维数组分辨率都较大时，这一算法耗时会长到令人无法忍受。

人们提出了各种各样的加速SDF生成的方法，譬如：

我们使用上一节提到的第一种优化措施——引入空间加速数据结构来减少需要遍历的三角形数量。以下将这一数据结构记作$A$，$A$需要以下操作：

满足这一需求的空间加速数据结构很多，诸如BVH树，KD树等都可以，可以根据实际性能选取，这里不再赘述。然后就可以用$A$来加速计算UDF了：

其中，find_proper_radius会以$p$点为中心找到一个合适的球体半径$r_p$，它需要满足：

我们可以采用二分搜索等算法来搜索一个比较合适的$r_p$。在得到$r_p$之后，只需要遍历$r_p$范围内的所有三角形，用它们计算UDF。当然，对每个体素都运行一遍二分搜索仍然是非常耗时的，我们可以利用UDF的局部性来改善这一问题。对空间中任意两点$p, q$，有：

也就是说，假如我们已经计算出了$p$点的UDF值，那么以$q$点为中心，以$u(p) + |p - q|$为半径的球体内一定存在三角形。倘若$p$和$q$点非常接近，我们就可以直接把$u(p) + |p - q|$当作$r_q$，用于计算$u(q)$。这样一来，我们只需要在最开始用二分搜索估计某个体素的$r$，而对其他体素，可以直接用与之相邻的体素处的SDF值结合这两个体素的距离快速得到半径。

综上，计算UDF的算法如下：

对每个体素，我们都只需要遍历很少的一部分三角形，就可以精确地计算出其UDF值。

在计算了UDF之后，我们还需要判断体素在物体的内部还是外部。由于在实践中，并不是所有的物体都严格满足watertight的要求，我们不会简单地根据最近三角形的法线来判定内外，而是发射多条射线，并在击中物体表面的射线中有一半以上命中物体外侧时，判定SDF为UDF，否则为-UDF。这一判断方法付出了一定的时间代价，但极大地提高了符号判定的鲁棒性。此外，射线和三角形的求交可以重用之前的空间加速数据结构$A$。

我用DirectX 11 Compute Shader在GPU上实现了本文所述的SDF生成算法。在GTX 1060上，对结构比较复杂、三角形数量在十万左右的物体，生成512^3分辨率的高精度SDF，并且在每个体素处用多达12条射线来判定符号，整个生成流程也可以在十几秒内完成。这样的计算效率离实时非常遥远，但对预计算来说是可以接受的。