符号距离场生成

3D SDF的快速生成

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

SDF

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

$$u(p)=\underset{q\in M}{\min }|p-q|$$

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

$$s(p)=\{\begin{array}{l}\begin{array}{rlr}& +u(p),& p\text{ is inside }M\\ & -u(p),& \text{otherwise}\end{array}\end{array}$$

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

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

既有方法

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

for each voxel v:
    # compute udf
    udf = infinity
    for each triangle T on M:
        udf = min(udf, distance(v, T))
    # compute sdf
    if is_inside(v, M):
        sdf[v] = udf
    else
        sdf[v] = -udf

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

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

• 引入空间加速数据结构，减少对每个体素需要检测的三角形数量
• 反转暴力算法，对每个三角形，计算它到每个体素中心的距离，并更新到体素数组上
• 一类被统称为扫描转换的算法，用于计算物体表面附近小范围内的SDF（narrow-band SDF）

生成算法

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

• 对空间中的任意一个球体，判断是否有三角形与该球体相交
• 对空间中的任意一个球体，给出与该球体相交的三角形列表

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

r = find_proper_radius(A, p)
Ts = find_intersected_triangles(A, p, r)
udf[p] = compute udf(p) with Ts

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

• 存在三角形与该球体相交
• $r_p$尽可能小

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

$$u(q)\le u(p)+\Vert p-q\Vert$$

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

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

r0 = find_proper_radius(A, p0)
T0 = find_intersected_triangles(A, p0, r0)
udf[p0] = compute udf(p0) with T0
for each voxel pi other than p0:
    let pj be a neighboring voxel with known udf
    ri = udf[pj] + |pi - pj|
    Ti = find_intersected_triangles(A, pi, ri)
    udf[pi] = compute udf(pi) with Ti

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

符号判定

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

实现效率

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