球面追踪：隐式曲面抗锯齿射线追踪的几何方法

John C. Hart

电子电气计算机科学学院

华盛顿州立大学

普尔曼, WA 99164-2752

电话: (509) 335-2343

传真: (509) 335-3818

电子邮件: hart@eecs.wsu.edu

摘要

球面追踪是一种利用几何距离渲染隐式曲面的新技术。基于距离的模型在计算机辅助几何设计和关节图形建模中很常见。给定一个返回到物体距离的函数，球面追踪沿着射线前进，直到其首次与隐式曲面相交，确保不会穿透隐式曲面。

球面追踪特别擅长渲染病态曲面。折叠和粗糙的隐式曲面由导数不连续或未定义的函数定义。当前的求根技术，如L-G曲面和区间分析，需要定期评估导数，其行为依赖于导数的行为。球面追踪只需要对导数大小的界限，从而稳健地避免导数跳跃或消失的问题。这种稳健性和范围支持球面追踪作为设计和研究新隐式模型的高效直接可视化系统。

此外，球面追踪有效地近似锥体追踪，支持符号预滤波抗锯齿。针对各种原语和操作的符号距离函数被推导出来，并作为附录独立出现，特别是自然二次曲面和环面、超二次曲面、基于Bezier的广义圆柱体和偏移曲面、构造实体几何、伪范数和高斯混合、锥度、扭曲和超纹理。

关键词: 面积采样，混合，变形，距离，隐式曲面，Lipschitz条件，数值方法，射线追踪，实体建模。

1 引言

参数曲面由一个函数定义，给定一组参数，指示空间中的相应位置；而隐式曲面由一个函数定义，给定空间中的一个点，指示该点是在曲面内、曲面上还是曲面外。

最常研究的隐式曲面形式是代数曲面，隐式地由多项式函数定义。例如，单位球由二次代数隐式方程

\[x^2 + y^2 + z^2 - 1 = 0\]

定义为其斜边（平方）为单位的坐标轨迹。

或者，使用距离度量，可以通过隐式方程几何地表示单位球

\[\vert \vert \mathbf{x}\vert \vert - 1 = 0\]

作为与原点距离为单位的点的轨迹。这里 \(\mathbf{x} = (x, y, z)\)，\(\|\|(x, y, z)\|\|\) 表示欧几里得模 \(\sqrt{x^2 + y^2 + z^2}\)。方程 (2) 的隐式曲面与方程 (1) 的一致，尽管它们的值在 \(\mathbb{R}^3\) 中几乎每个其他点都不同。具体来说，(1) 返回代数距离 [Rockwood & Owen, 1987]，而 (2) 返回几何距离。

几何表示与代数表示的二次曲面比较中，更倾向于几何表示 [Goldman, 1983]。几何表示的参数是坐标无关的，比代数系数更稳健和直观。基于距离的函数如(2)是几何表示隐式曲面的一种方法。

基于距离的模型可以在多个领域中找到。偏移曲面在计算机辅助几何设计中因其使用距离来模拟机器切割工具的物理能力而变得有价值 [Barnhill et al, 1992]。骨架模型在计算机图形学中模拟如手和恐龙等关节图形，相当于偏移曲面。计算机视觉的中轴变换将给定形状转换为其骨架表示 [Ballard & Brown, 1982]。广义圆柱体最初是计算机视觉中的几何表示 [Agin & Binford, 1976]，但也已成熟为计算机图形学中的标准建模原语 [Bloomenthal, 1989]，为其渲染开发了特殊的射线追踪算法 [van Wijk, 1984; Bronsvoort & Klok, 1985]。

1.1 先前工作

存在几种渲染隐式曲面的方法。间接方法将隐式曲面多边形化到给定的公差，允许使用现有的多边形渲染技术和硬件进行交互式检查 [Wyvill et al, 1986; Bloomenthal, 1988]。尽管多边形化将隐式曲面转换为易于渲染和集成到图形系统中的表示，但多边形化通常不保证，并且可能无法准确检测隐式曲面的断开或详细部分。生产射线追踪系统倾向于多边形化曲面，导致在准确表示一个简单的隐式模型时需要大量的时间和内存开销。

为了结合速度和准确性，[Sederberg & Zundel, 1989] 开发了一种直接扫描线方法，以更准确地在交互速度下渲染代数隐式曲面。另一方面，射线追踪是一种直接、准确且优雅的方法，用于研究更大范围的隐式曲面。

设

\[\mathbf{r}(t) = \mathbf{r}_o + t\mathbf{r}_d \tag{3}\]

参数化地定义了一个锚定在$\mathbf{r}_o$方向上的射线，方向为单位向量$\mathbf{r}_d$。将射线方程$\mathbf{r} : \mathbb{R} \to \mathbb{R}^3$代入定义隐式曲面的函数$f : \mathbb{R}^3 \to \mathbb{R}$中，得到复合实函数$F : \mathbb{R} \to \mathbb{R}$，其中$F = f \circ \mathbf{r}$，使得

\[F(t) = 0 \tag{4}\]

的解对应于射线与隐式曲面的交点。隐式曲面射线追踪算法只需应用多种数值求根方法之一来求解(4)。

当$f(\mathbf{x}) = 0$隐式定义一个代数曲面时，(4)是一个多项式方程。对于四次或更低次的多项式，存在解析解，但在某些情况下可能不是最佳的数值方法。在这种情况下和更高次的情况下，通常需要迭代求根算法。一些代数曲面渲染器使用了笛卡尔符号法则 [Hanrahan, 1983]、Sturm序列 [van Wijk, 1984] 和 Laguerre方法 [Wyvill & Trotman, 1990]，这些方法利用了多项式的性质，并且比一般的求根方法更有效。

为了渲染任意函数的隐式曲面，必须使用通用的求根算法。理想情况下，这种求根算法应该只需要具备在任意点处计算函数值的能力。然而，人们总能构造出一个病态函数，通过在样本之间插入一个任意薄的区域（在该区域中函数值迅速变为零然后又变回原值），使得这种 “盲目” 的技术遗漏一个或多个根（这一观点在[Kalra & Barr, 1989; Von Herzen et al, 1990]中重申过）。因此，任何稳健的求根算法需要的信息都比简单的函数求值更多。

“超纹理（Hypertexture）”系统使用了一种暴力的盲目光线步进方案，仅使用函数求值[Perlin & Hoffert, 1989]。由于其缺乏稳健性，需要沿着光线进行精细采样，导致渲染速度极慢，因此需要并行实现。仅要求函数求值使得隐式曲面的设计无需考虑其定义函数的解析性质。摆脱了这些限制后，分形曲面和毛发状曲面可以通过包含过程元素的隐式曲面函数轻松建模。

稳健的光线相交计算需要额外的信息，在大多数情况下，这些信息由函数的导数提供。当前的技术反复细分$F(t)$的图像，直到将其划分为要么不与$t$轴相交的区间（对应无光线相交情况），要么导数$F^{\prime}(t)$的图像不与$t$轴相交的区间（对应只有一次光线相交情况）。在这样的区间内的根可以使用牛顿法和试位法进行细化。在出现重根的罕见情况下，例如当光线掠过曲面或与重合曲面相交时，根隔离过程会将根周围的区间细分到机器精度。

区间分析通过在区间上定义函数及其导数，而不是在单个值上定义，来找到光线相交点。它使用这种区间算术运算来界定$F$及其导数$F^{\prime}$的值。在一个区间上，如果$F$的边界不包含零，则没有根。否则，如果$F^{\prime}$的边界不包含零，则有一个单根。否则，该区间在其中点处进行细分[Mitchell, 1990b]。

李普希茨（Lipschitz）方法是区间分析的一种替代方法。（第2.3节对李普希茨方法和区间方法进行了比较）。如第2.1节所述，当且仅当函数导数的幅度保持有界时，该函数是李普希茨函数。LG - 曲面方法在一个区间上对导数$F^{\prime}$施加李普希茨条件，从而得到$F^{\prime\prime}$幅度的一个边界$G$。这个边界$G$是$F^{\prime}$的速度限制，这意味着$F^{\prime}$的取值范围变化速度最多是其定义域变化速度的$G$倍。如果在区间的一个端点处$F^{\prime}$的值距离零大于区间长度的$G$倍，那么李普希茨条件保证导数$F^{\prime}$永远不为零。如果原函数$F$在区间端点处的值具有相同的符号，则该区间上没有根；如果端点处的值符号不同，则有一个根[Kalra & Barr, 1989]。

1.2 概述

球体追踪是一种用于光线追踪隐式曲面的稳健技术。与LG - 曲面或区间分析不同，它不需要具备计算函数导数的能力。相反，它只需要函数导数幅度的一个边界——即函数是连续且满足李普希茨条件的。因此，函数的导数不需要连续，甚至不需要有定义。

球体追踪受益于这种宽松条件，它使用连续但不可微的最小和最大运算来进行构造实体几何（constructive solid geometry），而不是使用常用的罗斯图（Roth diagrams）[Roth, 1982]。与典型的光线追踪器不同，球体追踪可以专注于找到构造实体几何（CSG）模型的第一条光线交点，避免了寻找所有光线 - 组件交点的计算开销。使用最小和最大运算来定义构造实体几何（CSG），还使得球体追踪能够渲染对CSG模型进行混合和其他几何运算的结果，这使用罗斯图是无法实现的。

球体追踪还能够比以往更有效地可视化更广泛的隐式曲面，包括有折痕的、粗糙的和分形曲面。 与 “超纹理（Hypertexture）” 系统较慢的暴力渲染方法[Perlin & Hoffert, 1989]一样，球体追踪使隐式曲面设计者无需担心定义函数的解析行为，从而能够设计出更多样化的隐式公式。此外，数学中的结构通常被定义为满足特定条件的点的轨迹。球体追踪可以可视化这样的结构，无论其平滑度、范围和连通性如何，只需知道该条件在空间中连续变化的速率的一个边界即可。球体追踪为新的隐式模型的开发提供了一种直接且灵活的可视化工具。

球体追踪通过近似圆锥追踪[Amanatides, 1984]来消除走样伪影并模拟软阴影。走样伪影通常通过随机超采样来减少，即对每个像素投射许多随机方向的光线。超采样通过将伪影转移到更高频率来抑制走样，而随机采样则将伪影伪装成不相关的噪声[Mitchell, 1990a]。另一方面，圆锥追踪通过对场景进行预滤波来消除走样，因此单个点样本可以准确表示其邻域的平均值。除了圆锥追踪在抗走样方面的更好处理效果外，隐式曲面通常由计算成本很高的函数定义，通过每个像素追踪单个圆锥而不是多个光线来减少函数求值的次数，使得抗走样更加高效。

2 球体追踪

球体追踪利用那些返回其到隐式曲面距离的函数（2.1节）来定义一系列点（2.2节），这些点以线性方式收敛到光线与曲面的第一个交点（2.3节）。2.4节比较了李普希茨方法和区间分析。2.5节在模型层面将构造实体几何融入球体追踪。2.6节描述了对球体追踪的一些改进以加快收敛速度。

2.1 距离曲面

本节定义并讨论用于测量或界定到其隐式曲面几何距离的函数。如[Bloomenthal & Shoemake, 1991]中所述，这类函数隐式地定义了距离曲面。附录推导了用于测量或界定各种基本体和操作距离的函数。

设函数$f$是一个连续映射$f:\mathbb{R}^n\rightarrow\mathbb{R}$，它隐式地将集合$A\subset\mathbb{R}^n$描述为点的轨迹

\[A = \{ \boldsymbol{x}: f(\boldsymbol{x}) \leq 0 \}. \tag{5}\]

根据连续性，$f$在边界$\partial A$上为零，该边界构成了$f$的隐式曲面。此外，$f$在内部$\mathring{A}$上严格为负，这使得多值函数像$f^{-1}(0)$能够简洁地表示$f$的隐式曲面。

定义1 点到集合的距离定义为从点$\boldsymbol{x}\in\mathbb{R}^3$到集合$A\subset\mathbb{R}^3$的距离，即从$\boldsymbol{x}$到$A$中最近点的距离：

\[d(\boldsymbol{x}, A) = \min_{\boldsymbol{y} \in A} \|\boldsymbol{x} - \boldsymbol{y}\|. \tag{6}\]

给定一个集合$A$，点到集合的距离$d(\boldsymbol{x}, A)$从外部隐式地定义了$A$ [Kaplansky, 1977]。这里，我们感兴趣的是相反的情况：给定一个隐式函数，到其曲面的点到集合距离是多少？

定义2 函数$f:\mathbb{R}^3\rightarrow\mathbb{R}$是其隐式曲面$f^{-1}(0)$的有向距离边界，当且仅当

\[\vert f(\boldsymbol{x})\vert \leq d(\boldsymbol{x}, f^{-1}(0)). \tag{7}\]

如果式(7) 中等式成立，那么$f$是一个有向距离函数。

一些基本体，比如球体，很容易用有向距离函数来定义。而计算到其他形状的距离可能相当困难。表1列出了附录中包含有向距离函数和边界的基本体和操作。

李普希茨常数是一个用于推导复杂形状有向距离边界的有用量。

李普希茨常数已在计算机图形学的碰撞检测[Von Herzen & Barr, 1987]和隐式函数渲染[Kalra & Barr, 1989]中得到应用。李普希茨常数是函数导数幅度的尽可能最紧的边界。

在实际应用中，李普希茨常数通常会被李普希茨界高估，特别是对于其分量具有已知李普希茨常数的函数。例如，两个函数之和的李普希茨常数最多是它们的李普希茨界之和。根据链式法则，函数复合的李普希茨常数最多是各分量函数的李普希茨常数之积。

可以通过代数方法将连续函数的李普希茨常数确定为该函数的最大斜率。这个最大斜率出现在函数二阶导数的零点之一处。在确定李普希茨常数时，几何观察往往比代数运算更有用。例如，可查看附录D中对软物体的简化代数李普希茨推导，或附录E中对扭曲物体的完全几何推导。

下面的定理展示了如何将李普希茨函数转化为有向距离边界，从而使球体追踪能够渲染由李普希茨函数定义的任何隐式曲面。

定理1 设$f$是李普希茨函数，其李普希茨界为$\lambda\geq \text{Lip } f$。那么函数$f/\lambda$是其隐式曲面的有向距离边界。

证明：给定一个点$\boldsymbol{x}$，设$\boldsymbol{y}\in f^{-1}(0)$是满足

\[\|\boldsymbol{x} - \boldsymbol{y}\| = d(\boldsymbol{x}, f^{-1}(0)). \tag{9}\]

的点之一。

然后根据(8)以及$f(\boldsymbol{y}) = 0$，可以得出

\[\vert f(\boldsymbol{x})\vert \leq \lambda d(\boldsymbol{x}, f^{-1}(0)). \tag{10}\]

因此，对于任何李普希茨函数$f$，$\lambda^{-1}f(\boldsymbol{x})$是一个有向距离边界（对比[Kalra & Barr, 1989]中的公式(8)）。$\square$

在(10)中使用李普希茨常数可得到最优的有向距离边界。较宽松的李普希茨界会导致对距离的低估变差，这会对使用该边界的算法效率产生不利影响。

2.2 光线相交

通过寻找函数$F(t)$的最小正根（第一个根），可以确定光线$r(t)$与由有向距离边界$f(\boldsymbol{x})$定义的隐式曲面的交点。这个根是由递推公式

\[t_{i + 1} = t_i + F(t_i) \tag{11}\]

以及初始点$t_0 = 0$所定义序列的极限点。当且仅当光线与隐式曲面相交时，该序列收敛。这个序列构成了图1中几何隐式曲面渲染算法的核心。

收敛测试的精度$\epsilon$被设置为所需的精度值。最大距离$D$对应于以观察者为中心的远裁剪球的半径，用于检测不收敛的序列。

有向距离函数的绝对值可以看作是一个球体的半径，该球体保证不会穿透任何隐式曲面。在[Hart et al, 1989]中，这个球体被称为“非包围球（unbounding sphere）”（该文献使用距离边界来隐式定义和可视化三维确定性分形），因为隐式曲面包含在这个球体的闭补集中。与包围物体的包围体不同，非包围体围绕的是不包含物体的空间区域。“球体追踪（sphere tracing）” 这个名字源于光线交点由非包围球序列确定这一特性。

如同[Ricci, 1974]所述，球体追踪在构造实体几何中使用最小和最大函数。这些操作在局部创建隐式曲面，使得定义函数的值保持连续，但导数不连续。导数的不连续性可能会给求根算法带来问题，求根算法必须找到函数的所有根，并使用罗斯图（Roth diagram）[Roth, 1982]来解析构造实体几何（CSG）操作。给定有向距离边界，球体追踪的操作不依赖于导数，并且即使对于CSG模型，也只需要收敛到第一个根。

2.3 分析

像牛顿法这样的根细化方法，对于单根（光线穿透曲面的情况）呈二次收敛，对于重根（光线掠过曲面的情况）呈线性收敛[Gerald & Wheatley, 1989]。诸如LG - 曲面[Kalra & Barr, 1989]和区间分析[Mitchell, 1990b]这类采用分治法的根隔离方法呈线性收敛，因为每次迭代区间宽度都会减半。根隔离方法仅在出现重根时才会收敛，否则一旦找到跨越$t$轴的单调区域，它们就会将控制权交给更快的根细化方法。

定理2 给定函数$F:\mathbb{R}\to\mathbb{R}$，其李普希茨界为$\lambda\geq \text{Lip }F$，以及初始点$t_0$，球体追踪线性收敛到大于$t_0$的最小根。

球体追踪序列可以写成

\[t_{i + 1} = g(t_i) = t_i + \frac{\vert F(t_i)\vert }{\lambda}. \tag{12}\]

从这个形式来看，式(12)与牛顿法的相似之处更为明显。设$r$是大于初始点$t_0$的最小根。由于$F(r) = 0$，那么$g(r) = r$，并且在任何非根点处$\vert F\vert /\lambda$为正。因此，式(12)收敛到第一个根。

不失一般性，假设$F$在感兴趣的区域内非负，这样就无需使用绝对值。$F(t_i)$在根$r$处的泰勒展开式为

\[g(t_i)=g(r)+(t_i - r)g^{\prime}(r)+\frac{(t_i - r)^2}{2}g^{\prime\prime}(\tau)\tag{13}\]

其中$\tau\in[t_i, r]$且$g^{\prime}(r)=1 + F^{\prime}(y)/\lambda$。误差项为

\[\epsilon_{i + 1}=t_{i + 1}-r = g(t_i)-g(r)=g^{\prime}(r)\epsilon_i + \text{高阶项}\tag{14}\]

由于$g^{\prime}(r)$在迭代过程中为常数，所以式(12)线性收敛到$y$。$\square$

推论2.1 当且仅当函数在其第一个根处斜率最大时，球体追踪呈二次收敛。

如果$F^{\prime}(r)=-\lambda$，误差式(13)中的线性项消失，只剩下二次项和更高阶项。$\square$

2.4 李普希茨方法与区间分析

基于细分的李普希茨方法[Von Herzen & Barr, 1987; Von Herzen et al, 1990; Kalra & Barr, 1989]已被类似但更灵活的区间方法所取代[Mitchell, 1990b; Snyder, 1992]。在函数定义中使用区间算术和自动微分[Mitchell & Hanrahan, 1992]，将求根信息与用户隔离开来，而使用李普希茨界通常要求用户对函数有足够的了解，以便知道它对数值的收缩程度。然而，这两种方法都涉及类似的操作。

设$f:\mathbb{R}\to\mathbb{R}$是区间$X\subset\mathbb{R}$上的一个函数。用区间算术操作定义$f$，会得到一个区间值$[a, b]=f(X)$，它界定了$f$在$X$上的取值范围（我们假设对于所有区间，第一个值$a$不大于第二个值$b$）。此外，区间$[a’, b’] = f’(X)$界定了$f’$在$X$上的取值范围。$f$在定义域$X$上的李普希茨界由下式给出

\[\underset{X}{\text{Lip }f} \leq \max(-a', b')\tag{15}\]

而区间$[-\text{Lip}_X f, \text{Lip}_X f]$则界定了$f’$在$X$上所有可能的取值。

区间算术的规则与李普希茨界的加法和复合规则类似。它们是为最坏情况设计的，而这种最坏情况在给定的定义域上可能实际上并不会发生。区间算术对函数值的界定进行了抽象，因此用户无需检查其结果。区间算术通过先界定函数的各个组成部分，然后再界定它们的复合，自下而上地对函数进行界定。

例如，图3展示了由函数$f(x)=x(1 - x)$定义的抛物线，该函数是$x$和$1 - x$的乘积。两个单调的组成函数的区间界最优定义为$[0, 1]$。它们的区间乘积$[0, 1]\times[0, 1]=[0, 1]$，比乘积$x(1 - x)$的最优界$[0, \frac{1}{4}]$大了四倍。此外，将$x(1 - x)$视为$x+-(x\times x)$，会得出更差的区间界$[-1, 1]$。

虽然可以使用类似于区间算术的规则来确定李普希茨界，但它们通常是自上而下设计的，需要对函数及其度量效果有一个整体的理解。与仅对函数的组成部分进行简单的区间算术运算相比，这种过程能够得出更紧的、通常是最优的李普希茨界。

球体追踪与计算机图形学中以往基于李普希茨的方法不同，它不基于二分法细分。球体追踪的区间版本可以使用式(15)来定义一个（局部）李普希茨界，不过，如[Mitchell, 1990b]中所述，定义域中的任何折痕都会产生一个（对球体追踪而言）无用的导数区间$[-\infty, \infty]$ 。

2.5 构造实体几何

根据[Ricci, 1974]，对函数进行最小和最大运算，会在它们的隐式曲面上分别产生并集和交集操作。在下面的等式中，设$f_A$、$f_B$分别为集合$A$和$B$的有向距离函数。如果$f_A$或$f_B$是有向距离边界，那么得到的构造实体几何（CSG）隐式函数也将是一个边界。

到集合$A$和$B$的并集的距离，是到这两者中较近者的距离

\[d(\boldsymbol{x}, A\cup B)=\min\{f_A(\boldsymbol{x}), f_B(\boldsymbol{x})\}. \tag{16}\]

类似地，到一组对象的距离，是到每个组成对象距离中的最小值。

到集合$A$的补集的距离，利用了距离函数的有向性质

\[d(\boldsymbol{x}, \mathbb{R}^3\setminus A)= - f_A(\boldsymbol{x}). \tag{17}\]

尽管德摩根定理将交集定义为补集的并集的补集，但并集中使用的最小运算符不能正确地进行补集运算。相反，到交集的距离由到最远组成部分的距离界定。

定理3 设由有向距离边界$f_A$、$f_B$定义的两个隐式曲面分别为$A = f_A^{-1}(0)$和$B = f_B^{-1}(0)$，那么点$\boldsymbol{x}$到这两个隐式曲面交集的距离满足

\[d(\boldsymbol{x}, A\cap B)\geq \max\{f_A(\boldsymbol{x}), f_B(\boldsymbol{x})\}. \tag{18}\]

证明：分情况讨论，如图4中一个示例交集所示。

情况I：$\boldsymbol{x}\in A\cap B$。$f_A$和$f_B$均为负，两者中较大的值表示到交集最近边界的（负）距离。

情况II：$\boldsymbol{x}\in A$，$\boldsymbol{x}\notin B$。函数$f_A$为负，而$f_B$为正，取两者中的较大值。$B$上距离$\boldsymbol{x}$最近的点可能不在交集中，但交集中不可能存在更近的点。

情况III：$\boldsymbol{x}\notin A$，$\boldsymbol{x}\in B$。与情况II对称。

情况IV：$\boldsymbol{x}\notin A\cup B$。和之前一样，交集中$A\cap B$的最近点不会比$A$中的最近点和$B$中的最近点中较远的那个更近。$\square$

根据定义，集合差运算$A - B$可以模拟为$A\cap(\mathbb{R}^3\setminus B)$，不过由于交集运算符的存在，只能得到一个有向距离边界。

并集和交集运算符在4.2节的图10中展示。

2.6 改进措施

以下改进措施通过减少不必要的距离计算来提高球体追踪的效率，因为这些距离计算可能成本很高，在某些情况下甚至需要迭代计算。4.3节对这些改进措施进行了实证评估和分析。

2.6.1 图像连贯性

一种类似于球体追踪的算法已被开发出来，用于使用三维距离变换渲染离散体数据[Zuiderveld等人，1992]。距离变换将二进制的“填充/未填充”体素数组转换为数值体素数组，使得每个体素包含在给定度量下到最近“填充”体素的距离。我们还将李普希茨常数的概念扩展到了体绘制中[Stander & Hart，1994]，像[Kalra & Barr，1989]中那样，用局部李普希茨常数的八叉树代替距离变换，从而能够对任意等值面进行基于距离的加速体绘制，同时消除了每次阈值变化时重新计算预处理数据结构的需要。

[Zuiderveld等人，1992]中的一项改进是跟踪未命中物体的光线所遇到的最小距离。在正交投影下，这个最小距离定义了围绕采样点的、保证为空像素的圆盘半径。在透视投影下，必须计算最小投影距离（这需要光线与球体求交），并且这种改进的效率会降低。初步测试表明，对于典型的隐式曲面，在透视投影情况下这种改进会降低性能。

2.6.2 包围体

包围体是一种有用的机制，用于剔除与当前任务无关的复杂几何图形的处理。除了能避免投射未命中物体的光线（这是其典型优势）之外，它们还能帮助球体追踪避免对距离更远物体进行距离计算。在大多数情况下，快速进行包围体距离检查所带来的开销，相较于避免大量耗时却无用的距离计算而言，代价微不足道。

首先，计算到物体并集或集合中每个包围体的距离。然后，按照包围体距离递增的顺序，计算到每个包围体内部物体的距离，直到某个内部物体的距离小于最小的包围体距离。该距离即为到物体集合的点到集合距离。此过程如图5所示。

[Kay & Kajiya, 1986]中介绍了一种使用拉格朗日乘数法来寻找隐式曲面的包围平行六面体的方法。有向距离边界的一些特性或许能产生一种替代的隐式曲面包围体算法，但这个主题留待进一步研究。

2.6.3 三角不等式

三角不等式

\[\|\boldsymbol{a} - \boldsymbol{c}\| \leq \|\boldsymbol{a} - \boldsymbol{b}\| + \|\boldsymbol{b} - \boldsymbol{c}\| \ \forall\boldsymbol{a}, \boldsymbol{b}, \boldsymbol{c} \in \mathbb{R}^3, \tag{19}\]

是任何度量定义的一部分。它也有助于消除对物体集合进行不必要的距离计算。在计算一个点与一个物体集合之间的最短距离时，对于那些上次距离评估值减去自上次评估后沿光线所经过的距离 ，仍然大于到当前最近物体距离的物体，无需计算到它们的距离。三角不等式改进算法如图6所示。

2.6.4 八叉树划分

消除空白空间无疑有助于提高渲染效率，但划分的主要好处在于，它能够对李普希茨常数施加局部边界，从而得出更精确的有向距离边界。八叉树划分已应用于隐式曲面的多边形化[Bloomenthal, 1989]和光线追踪[Kalra & Barr, 1989]中。球体追踪从空间划分中获得的好处，与[Kalra & Barr, 1989]中的求根方法相同，后者利用李普希茨常数来剔除肯定不会与隐式曲面相交的八叉树节点。

对于由有向距离边界定义的隐式曲面，光线相交计算在梯度幅度最大的定义域部分代价较高。将一个物体分割成多个较小部分的并集，能对每个部分单独处理，仅受其边界内最大梯度的影响。由于[Kalra & Barr, 1989]中的划分算法只需要函数的李普希茨常数的一个边界，因此使用这种八叉树绝不会限制可用于球体追踪的函数范围。

八叉树划分通过选择性地存储距离单元最近的物体的索引，进一步增强了对物体并集和集合的球体追踪效果。当且仅当一个物体是八叉树单元中每个点的最近物体时，该物体才是距离该单元最近的物体。根据此定义，某些单元可能没有最近的物体。根据三角不等式(19)，如果从单元质心到某物体的距离，加上从质心到单元角点的距离，仍然小于从质心到其他任何物体的距离，那么该物体就是距离该单元最近的物体。

2.6.5 凸性

凸性有多种定义方式。例如，度量拓扑学[Kaplansky, 1977]将完备度量空间中的一个集合定义为凸集，当且仅当对于该集合中的任意两个不同点，存在第三个不同点，使得该点到前两个点的距离之和等于前两个点之间的距离。在坐标空间$\mathbb{R}^3$中，有我们更为熟悉的凸性定义。

定义4 [Farin, 1990] 集合$A\subset\mathbb{R}^3$是凸集，当且仅当连接两个端点$\boldsymbol{x}, \boldsymbol{y}\in A$的线段

\[\text{lerp}(\boldsymbol{x}, \boldsymbol{y}) = s\boldsymbol{x}+(1 - s)\boldsymbol{y}, \ \forall s\in[0, 1] \tag{20}\]

是$A$的子集。

知道一个物体是凸的，可以通过增加沿光线的步长来提高球体追踪的效率。

定理4 设$A\subset\mathbb{R}^3$是由有向距离函数$f$隐式定义的凸集。那么，给定单位向量$\boldsymbol{v}\in\mathbb{R}^3$，线段

\[\text{lerp}(\boldsymbol{x}, \frac{f(\boldsymbol{x})}{-\boldsymbol{v}\cdot\nabla f(\boldsymbol{x})}\boldsymbol{v}) \tag{21}\]

除了可能在其第二个端点处，不会与$A$相交。

证明：有向距离函数的梯度$\nabla f$在凸集$\mathbb{R}^3\setminus A$的补集上具有以下性质：(1) 它是连续的；(2) 其模为1（函数的变化量等于距离的变化量）；(3) 其方向直接远离隐式曲面上的最近点。因此，对于任意$\boldsymbol{x}\in\mathbb{R}^3\setminus A$，我们知道$A$中的最近点，并且其表面法向量指向$\boldsymbol{x}$。由于$A$是凸的，它不会穿过$\boldsymbol{x}$处的切平面。

以$\boldsymbol{x}$为起点、方向为$\boldsymbol{v}$的光线，与在距离$\boldsymbol{x}$为$f(\boldsymbol{x})$处且法向量为$\nabla f(\boldsymbol{x})$的切平面的交点，由式(21)的第二个端点给出。$\square$

推论4.1 如果$\nabla f(\boldsymbol{x})\cdot\boldsymbol{v}\geq 0$，那么以$\boldsymbol{x}$为起点、方向为$\boldsymbol{v}$的光线不会与$f$的隐式曲面相交。

定理4使得球体追踪在朝向凸物体时可以采取更大的步长，推论4.1则使得球体追踪能够避免计算已经越过的凸物体的距离。由于凸性改进与牛顿法相似（牛顿法也是二次收敛），所以它可能会使球体追踪呈二次收敛。

包围体通常是凸的，将这两种技术结合可以进一步减少不必要的距离计算。

在渲染有地平线的场景时，了解凸性是必要的。考虑一个地平面和一条与之平行的光线，球体追踪会沿着这条光线以固定间隔寻找永远不会出现的交点。推论4.1可以避免这种情况，而定理4则加速了几乎与地平面平行的光线的收敛。

3 抗锯齿

在[Amanatides, 1984]中，追踪圆锥而非光线产生了一种区域采样抗锯齿方法。圆锥追踪通过计算圆锥与球体、平面和多边形的交点，对图像进行预滤波，从而消除由点采样导致的锯齿伪影。球体追踪可以很容易地用于检测和近似圆锥与由有向距离函数定义的任何隐式曲面的交点。虽然仍需实现圆锥追踪算法的细节，以确定圆锥在场景中反射时的形状，但可以借助非包围球来提高确定圆锥交点的效率。此外，球体追踪仅增强了对轮廓边缘处圆锥交点的检测，对于圆锥追踪能修复的其他类型的锯齿，如纹理锯齿，则没有帮助。

在一条掠过光线的某个位置，非包围球序列会先缩小到圆锥范围内，然后再扩大并超出圆锥范围。这就带来了“选择一个代表性点”的问题[Amanatides, 1984]，即选择一个位置进行采样，以近似圆锥与曲面交点处的着色。

覆盖区域是一个以像素半径为偏移量，在隐式曲面内外界定的区域，这样光线与覆盖区域的交点就表示圆锥与物体的交点[Thomas等人, 1989]。给定由有向距离函数$f(\boldsymbol{x})$定义的隐式曲面，其外部覆盖区域是由$f(\boldsymbol{x}) - r_p$隐式定义的全局偏移曲面，内部覆盖区域是由$f(\boldsymbol{x}) + r_p$隐式定义的全局偏移曲面，其中$r_p$是像素半径（像素直径的一半）[Hart & DeFanti, 1991]。换句话说，外部覆盖区域是曲面$f^{-1}(r_p)$，内部覆盖区域是曲面$f^{-1}(-r_p)$。抗锯齿算法不是对$f(\boldsymbol{x})$的隐式曲面进行球体追踪，而是对内部覆盖区域，即$f(\boldsymbol{x}) + r_p$的隐式曲面进行球体追踪。

覆盖区域的提出表明，对于轮廓抗锯齿，最具代表性的选择是光线中最接近曲面部分的点。因此，在圆锥内部的非包围球中，最小球（按像素大小）的中心成为代表性样本。尽管这个样本不在隐式曲面上，但我们假设距离函数梯度具有一定程度的连续性，以便定义可用的曲面法向量。如图7所示，沿光线的非包围球序列与圆锥相关。

对于平滑的隐式曲面，可以假设局部平面性。因此，假定隐式曲面覆盖圆锥的横截面，且该横截面的直边与圆锥中心的距离为给定值。这个着色点对于光线进一步相交的点的影响程度，取决于在代表性点处（即最近非包围球的半径）对有向距离函数$f(\boldsymbol{x})$到隐式曲面的求值结果。半径为$r_p$的圆盘被距其中心有向距离为$f(\boldsymbol{x})$的相交半平面覆盖的比例$\alpha$由下式给出

\[\alpha=\frac{1}{2}-\frac{f(\boldsymbol{x})\sqrt{r_p^2 - f(\boldsymbol{x})^2}}{\pi r_p^2}-\frac{1}{\pi}\arcsin\frac{f(\boldsymbol{x})}{r_p} \tag{22}\]

该公式在[Thompson, 1990]中推导得出。光线遍历以$f(\boldsymbol{x}) + r_p$为步长进行（这可能会使光线穿过曲面）。覆盖比例$\alpha$表示掠过光线与圆锥的相交情况。它被视为不透明度，进行累积后，根据图像合成的标准规则[Porter & Duff, 1984]，用于将当前代表性点$\boldsymbol{x}$的着色与光线进一步接近未命中点和交点处的着色进行混合。

对于相交边缘，必须跟踪所有非包围球在圆锥范围内的有向距离函数。在近似光线相交时，每个相交曲面的有向距离函数为其着色属性的恰当组合提供比例。相交的代表性点是光线遍历序列的最后一个点，即满足收敛测试的点。

通常，有向距离函数的计算成本过高，因此会使用有向距离边界。边界可能会返回半径过早缩小到像素半径以下的非包围球，从而导致错误的圆锥相交结果。在这种情况下，单独的距离近似可能会有所帮助。例如，[Pratt, 1987; Taubin, 1994]使用一阶近似$f/|\nabla f|$来估计到$f$的隐式曲面的距离。一般来说，这种近似不一定是距离边界。[Taubin, 1994]中的引理1表明，当接近曲面时，这种近似与几何距离渐近相等。因此，通过这种近似比通过有向距离边界能更准确地确定圆锥相交情况。

对于纹理锯齿，圆锥追踪会根据相交处圆锥的半径对纹理进行滤波。由于圆锥追踪是在非包围球光线相交方案内进行的，所以在这个渲染系统中，纹理同样可以进行抗锯齿处理。

4 结果

球体追踪简化了隐式曲面光线追踪器的实现，并且运行速度与其他隐式曲面渲染算法相当。

4.1 实现

球体追踪已在一个名为zeno的渲染系统中实现。在zeno中加入一个隐式曲面，需要定义两个函数：用于光线相交的有向距离函数，以及用于着色的曲面法向量函数。

一个新的基本体或操作最多只需一个距离边界，就可以整合到zeno中。有向距离边界的负值部分仅在某些构造实体几何和混合操作中是必要的，对于在隐式曲面内部取值为零的函数可视化则不需要。通过使用距离边界梯度的一般六点采样数值梯度近似，可以避免使用曲面法向量函数。由于大部分时间都花在光线相交计算上，效率不高的数值梯度近似对渲染性能的影响可以忽略不计。

在zeno中整合隐式曲面的简单性，使其在数学任务的可视化以及新隐式曲面的研究方面很有用。例如，一种在不移动丝带两端的情况下消除丝带720°扭转的同伦，是动画短片《狄拉克弦上的空气》[Sandin等人, 1993]的基础，zeno为该短片渲染了一个片段。这种同伦在很大程度上基于插值四元数旋转，在对同伦中最极端的变形进行快速搜索和分析后，它很容易作为一种域变换整合到zeno中[Hart等人, 1993]。

4.2 展示

图8中的三个环面是使用附录D.2中描述的超椭圆混合方法组合而成的。这些环面的大半径均为1，小半径为0.1。蓝绿色混合区域是二次型的，从环面的相交处沿环面延伸出0.5的半径。红绿色混合区域半径同样是0.5，但次数为8。红蓝色混合区域次数也为8，但半径仅为0.2。

球体追踪在12分47秒内渲染出了图8（左图），分辨率仅为256×256，渲染时使用了预滤波，以避免通常在如此低采样率下会出现的严重锯齿问题。关于点采样和区域采样在执行上差异的实验表明，区域采样所增加的执行时间可以忽略不计。

尽管超椭圆混合在zeno中作为有向距离边界实现，但它返回的距离被低估，不过该距离至少为实际距离的70%，这足以指示圆锥相交情况，如图8（右上角）的放大图所示。

图8（右下角）的工作图像显示，球体追踪聚焦于轮廓边缘。蓝色区域在10次迭代内收敛，绿色区域约50次，红色区域超过100次。

图9展示了附录C中的广义圆柱体，其骨架由一条用14个贝塞尔控制多边形建模的空间曲线组成。球体追踪使用包围球来消除不必要的距离计算，最快可在5分30秒内渲染出此场景。弯曲的地平线是用于终止光线步进的半径为1000的远裁剪球产生的假象。

图10展示了球体追踪在有折痕表面上的稳健性。这两张图像均在预滤波处理后以512×512的分辨率渲染，圆柱体的渲染时间为16分48秒，立方体为12分36秒。

折痕是通过构造实体几何（CSG）的并集和交集操作创建的，由2.5节中连续但不可微的最小和最大操作隐式定义。然后使用附录D.2中的伪范数混合将得到的边缘合并到第三个物体中。这种有折痕的表面会周期性地出现在各种形状中，尤其是在生物形态的建模中。

图11展示了附录F中描述的“噪声”范围变形。左图使用了单倍频程的噪声，而接下来的两张图使用了六倍频程的噪声，其幅度分别按$1/f^2$和$1/f$缩放，分别生成了肌肉纹理和岩石表面。这三张图像的分辨率均为256×256，（从左到右）渲染时间分别约为5分钟、半小时和2小时。由于距离估计的高度变化，无法对噪声函数的结果进行预滤波处理。

4.3 分析

球体追踪的收敛完全是线性的，而其他通用的求根方法，如区间分析，有一个线性收敛的根隔离阶段，随后是一个二次收敛的根细化阶段。如图8（右下角）这样的工作图像表明，光线相交在轮廓边缘的计算成本最高。当球体追踪这些边缘时，到表面的距离只是到光线交点距离的一部分，这会减缓收敛速度。对于像区间分析这样的其他方法，轮廓处是重根（会阻碍根的细化），并且其邻域由间距很近的根对组成。对于中点细分根细化方法来说，分离这样的根对成本很高，因为两个根之间的距离可能比初始区间小几个数量级。

如表2所示，凸性改进使收敛速度加快了31%。该表还显示，对于更多的基本体，三角不等式改进使收敛速度提高了一倍多，当与凸性改进结合时，可使普通的球体追踪提高60%。

表2还比较了zeno标志在各种改进后的渲染时间。由于所有14条贝塞尔曲线到眼睛的距离几乎相等，这使得在球体追踪遍历每条光线的大部分路程之前，三角不等式无法显著减少不必要的距离计算。

图12展示了球体追踪一个球体时所使用的步长分布情况。此直方图仅统计了用于与主光线（视线光线）相交的距离计算。

未改进的球体追踪步长分布较为均匀，中间有一个小峰值。八叉树用八叉树解析开销取代了这个峰值区域中增加的距离计算（此直方图未统计该开销）。八叉树边界的影响导致其频谱高端出现振荡，而低端则与未改进时的性能相符。

对简单场景的实验未能证明八叉树改进能提升性能，不过更复杂的场景可能会从中受益。

凸性直方图展示了这种改进的效果。其左侧的斜率证实了2.6.5节中的预期，即它能让球体追踪的收敛速度更快。由于在越过球体后停止步进，该直方图的右侧显著缩短。

未改进和凸性改进的图表中的峰值表示从眼睛到球体的距离，这是从视点发出的每条光线的第一步。可以通过仅测量一次该距离，并将其视为从视点发出光线的第一步，来消除图表中的这些峰值，对于光源也是如此。在实验中，这种“起始优势”几乎没有提升性能。

[Zuiderveld等人, 1992]中类似的直方图，在步数上采用对数方式衡量性能，但在步长上采用线性方式。因此，他们的图表比图12更呈对数形状。

距离估计的准确性与收敛速度成正比。对球体的实验表明，距离减半会使步数翻倍。图13中的步长直方图揭示了距离低估的影响。

距离准确性和球体追踪性能之间的关系表明，在某些情况下，计算速度较慢的有向距离函数可能比快速但低估距离的函数表现更好。例如，考虑到一个半轴半径分别为100、100和1的椭球体的距离，该椭球体被建模为单位球体的非均匀缩放变换。附录E得出一个有向距离边界，其结果最好是到椭球体的距离，最差是实际距离的1% （以封闭形式表示），而[Hart, 1994]得出一个有向距离函数，它通过几次牛顿迭代得出精确距离。在这种情况下，有向距离函数可能会带来更好的性能。

最后，噪声函数的李普希茨常数分别为：单噪声为3，$1/f^2$噪声为6，$1/f$噪声（六倍频程）为18。表2中与图11图像对应的时间显示，$1/f^2$噪声的渲染时间实际上是单噪声时间的7.3倍（而不是预期的2倍）。很可能的原因是，$1/f^2$噪声调用噪声函数的次数比单噪声函数多6倍（预期值为12倍）。$1/f$噪声的渲染时间比单噪声长27.5倍（小于预期的36倍），比$1/f^2$噪声长3.75倍（略大于预期的3倍） 。

5 结论

球体追踪提供了一种工具，能够比以往研究更多种类的隐式曲面。

通过改进和预滤波，球体追踪成为一种具有竞争力、可呈现高质量效果的隐式曲面渲染器。特别是，凸性改进极大地提高了渲染速度，三角不等式对于大量物体的处理非常有效。包围体也如预期的那样提高了渲染性能。然而，基于图像连贯性和空间连贯性（八叉树）的技术表现不佳。

虽然在由二次曲面和多边形组成的简单物体上，球体追踪的速度明显慢于标准光线追踪，但在渲染复杂几何建模操作的结果时表现出色。

球体追踪的几何特性使其适用于符号预滤波，能以较小的开销支持抗锯齿。

无需直接进行实验对比，一些理论论据表明，球体追踪是区间分析和LG曲面的可行替代方案。

5.1 进一步研究

球体追踪展示了有向距离函数在渲染几何隐式曲面任务中的实用性。我们预计这些函数也会同样提升其他应用，特别是在几何处理领域。随着几何距离在计算机辅助几何设计和其他建模领域变得越来越重要，对更高效的几何距离算法的需求将会增加。

回顾来看，在球体追踪中使用欧几里得距离度量似乎是一种随意的选择。棋盘距离度量和曼哈顿距离度量的线性特性，可能会使距离计算和光线相交的计算更加高效。“立方体追踪”和“八面体追踪”算法留作进一步研究的内容。

5.2 致谢

感谢Tom DeFanti和Larry Smarr在本研究第一年给予的支持，也感谢Pat Flynn、Robert Bamberger和Tom Fischer欢迎我和我的研究加入华盛顿州立大学的成像研究实验室。

本研究得到了美国国家科学基金会CCR - 9309210号资助。本文中表达的任何观点、研究结果、结论或建议均为作者个人观点，不一定反映美国国家科学基金会的观点。

特别感谢Alan Norton，他在1989年鼓励我将球体追踪应用于非分形模型。在附录中推导距离相关内容时，与Al Barr、Chandrajit Bajaj、Charlie Gunn、Pat Hanrahan、Jim Kajiya、Don Mitchell和Alyn Rockwood的交流对我帮助很大。

Brian Wyvill和Jules Bloomenthal值得特别提及，他们在1990年的SIGGRAPH会议上开设了关于隐式曲面的精彩课程，为本研究提供了灵感。

A 到常见二次曲面和环面的距离

这些附录推导了多种基本体和操作的有向距离函数、边界以及李普希茨常数和边界，希望它们有助于球体追踪的实现，同时也可作为为其他基本体和操作开发有向距离函数、边界以及李普希茨常数和边界的教程。

下面列出了到标准实体建模基本体的距离。与标准的封闭形式解相比，几何渲染算法的效率不高。不过，当这些基本体用于如混合和变形等高阶构造时，这些距离是有用的。

平面 到单位法向量为$\boldsymbol{n}$且过点$r\boldsymbol{n}$的平面$P$的有向距离为

\[d(\boldsymbol{x}, P)=\boldsymbol{x}\cdot\boldsymbol{n}-r. \tag{23}\]

球体 球体定义为到给定点距离固定的点的集合。因此，到以原点为球心的单位球体$S$的距离为

\[d(\boldsymbol{x}, S)=\|\boldsymbol{x}\|-1. \tag{24}\]

通过域变换（附录E），球体的半径和位置可以改变。球体甚至可以变成椭球体，不过这会将有向距离函数重新表述为需要求解一个六次多项式的函数[Hart, 1994]。通过替代距离度量（附录B），球体可以变成超椭球体。这些技术同样也可推广到其他基本体。

圆柱体 到以$z$轴为中心的单位半径圆柱体的距离，可通过向$xy$平面投影，然后测量到单位圆的距离得到

\[d(\boldsymbol{x}, Cyl)=\|(x,y)\|-1. \tag{25}\]

注意，在公式(25)以及本附录的其余部分中，$\boldsymbol{x} = (x, y, z)$。

圆锥体 到以原点为中心、沿$z$轴方向的圆锥体的距离为

\[d(\boldsymbol{x}, Cone)=\|(x,y)\|\cos\theta - \vert z\vert \sin\theta, \tag{26}\]

其中$\theta$是与$z$轴的发散角。其推导背后的三角函数关系如图14所示。

环面 环面是两个圆的乘积，其距离计算如下

\[d(\boldsymbol{x}, T)=\|(\|(x,y)\|-R,z)\|-r \tag{27}\]

对于一个以原点为中心、绕$z$轴旋转，大半径为$R$、小半径为$r$的环面，使用此公式计算距离。

B 到超二次曲面的距离

超二次曲面[Barr, 1981]源于距离度量的一般化。到基本图元的距离都使用 $|\cdot|$ 运算符。在二维空间中，该运算符一般化为$p$-范数：

\[\|(x, y)\|^p = (\vert x\vert ^p + \vert y\vert ^p)^{\frac{1}{p}} \tag{28}\]

当 $p = 2$ 时，它就变成了我们熟悉的欧几里得度量，其“圆” 是正圆形。曼哈顿度量（$p = 1$）的“圆” 是菱形。当 $p \to \infty$ 时取极限，得到棋盘度量：

\[\|(x, y)\|^{\infty} = \max\{x, y\} \tag{29}\]

此时“圆” 的形状是正方形。$p$ 的其他中间值会产生这些基本形状的圆角变体，而设置 $0 < p < 1$ 则会产生收缩的变体。广义球体，即所谓的超椭球体，由 $pq$-范数生成，如下：

\[\|(x, y, z)\|^{pq} = \|(\|(x, y)\|^p, z)\|^q \tag{30}\]

自然二次曲面现在一般化为超二次曲面，环面同样变为超环面，它们的距离使用合适的度量来测量。为了使距离具有可比性，必须使用一个统一的度量空间。因此，$pq$-范数距离必须转换为欧几里得距离。

设$f(\boldsymbol{x})$返回其隐式曲面对应的$pq$-范数距离。该距离定义了一个无界超椭球体的半径。在半径为$r_s$（以$pq$-范数度量）的$pq$-范数超椭球体内，能内接的最大欧几里得球体半径$r_e$由下式给出：

\[r_e = \begin{cases} r_s / \|(\frac{\sqrt{3}}{3}, \frac{\sqrt{3}}{3}, \frac{\sqrt{3}}{3})\|^{pq} & \text{如果 } p < 2 \\ r_s & \text{否则} \end{cases} \tag{31}\]

C 到偏移曲面的距离

给定一些封闭的骨架几何图形$S \subset \mathbb{R}^3$，那么全局偏移曲面由以下隐式方程从几何上定义：

\[d(\boldsymbol{x}, S) - r = 0 \tag{32}\]

当$r$为常数时，得到的隐式曲面是骨架$S$的扩展。

点到集合的距离定义为在整个集合中搜索最近点。如果$\partial S$（$S$的边界）处处都定义了曲面法向量，那么$S$中距离$\boldsymbol{x}$最近的点$\boldsymbol{y}$是$\partial S$上法向量直接指向$\boldsymbol{x}$的点之一。这极大地缩小了在一些基本图形（如参数曲面）上确定点到集合距离的搜索空间。

然而，用这种点到集合距离的公式来定义偏移可能会产生问题。如果骨架是由参数函数$\boldsymbol{g}(u, v)$表示的生成曲面，那么局部偏移曲面由参数函数定义为：

\[\boldsymbol{p}(u, v)=\boldsymbol{g}(u, v)+r\boldsymbol{n}(u, v) \tag{33}\]

其中

\[\boldsymbol{n}(u, v)=\frac{\boldsymbol{g}_u(u, v)}{\|\boldsymbol{g}_u(u, v)\|} \times \frac{\boldsymbol{g}_v(u, v)}{\|\boldsymbol{g}_v(u, v)\|} \tag{34}\]

是$\boldsymbol{g}(u, v)$处的单位长度曲面法向量，$\boldsymbol{g}_u$，$\boldsymbol{g}_v$是关于$u$，$v$的偏导数。

全局偏移通常定义为几何隐式曲面，而局部偏移通常用参数形式定义。全局偏移是更理想的表示形式[Hoffman, 1989]，特别是它能避免内部曲面，因为内部曲面会在光线追踪和构造实体几何（CSG）中引发问题[van Wijk, 1984]。

代数隐式曲面的偏移仍是代数形式的，不过一般来说次数更高。同样，偏移曲面的参数形式通常比生成曲面的次数更高。次数的增加部分是由于在偏移曲面的定义中使用了距离（公式(34) 中需要叉积和平方根运算）。已经开发出了几种技术来用低次表示近似偏移曲面。从几何角度处理偏移曲面，能克服处理不必要的高次代数表示以及因不精确的低次近似而导致精度损失的问题。

一种有用的骨架模型是简化广义圆柱体，它是一个全局偏移曲面，定义为与由三维贝塞尔曲线分段定义的空间曲线保持固定距离的点的轨迹。

将空间曲线用参数形式定义为函数 $\boldsymbol{p}: \mathbb{R} \to \mathbb{R}^3$ 的像。不失一般性，假设我们想求到该空间曲线距离的点为原点。

那么，空间曲线上的最近点要么是端点之一，要么是空间曲线上切线与指向原点的向量垂直的点。后者可通过求解以下方程得到：

\[\boldsymbol{p}(u) \cdot \boldsymbol{p}_u(u)=0 \tag{35}\]

设 $\boldsymbol{p}$ 为三次贝塞尔曲线。[Schneider, 1990] 展示了如何将公式(35) 转换为一个五次一维贝塞尔曲线，这是一种伯恩斯坦多项式，其图像由控制点的凸包界定。使用[Rockwood & Owen, 1987] 中描述的技术，可以高效地求解伯恩斯坦多项式。

广义圆柱体在4.2节的图9中进行了展示。

D 到混合对象的距离

混合是对对象各部分相交处的接合点进行平滑处理。以下两种混合是局部的，这意味着它们仅影响对象的一部分。这在计算机辅助几何设计中很有用，这样对象不同部分的混合不会相互干扰；并且在计算机图形学中，在可能的情况下对混合进行界定和剔除渲染时也很有用。

D.1 软元球

[Blinn, 1982] 使用高斯分布函数生成了一个混合函数，该函数后来被称为 “软团” 模型。“软” 对象用六次多项式逼近高斯分布，以避免指数运算并实现局部混合 [Wyvill 等人, 1986]。“元球” 用分段二次函数逼近高斯分布，以避免指数运算和迭代求根 [Nishimura 等人, 1985]。

根据 [Wyvill 等人, 1986]，以下是距离$r$的分段三次函数：

\[C_R(r)= \begin{cases} 2\frac{r^3}{R^3}-3\frac{r^2}{R^2}+1 & \text{如果 } r < R, \\ 0 & \text{否则} \end{cases} \tag{36}\]

逼近高斯分布。也存在一个类似的六次代数版本，并且通常使用该版本，以更高的次数为代价避免距离计算[Wyvill & Trotman, 1990]。

重新表述此函数以适应本文中的隐式曲面定义，公式(36)构成了一个软隐式曲面的基础，该曲面由$n$个关键点$\boldsymbol{p}_i$（半径为$R_i$）和阈值$T$组成，由函数定义为：

\[f(\boldsymbol{x}) = T - \sum_{i = 1}^{n} C_{R_i}(\|\boldsymbol{x} - \boldsymbol{p}_i\|) \tag{37}\]

通过将$C_{R_i}()$返回的值取负，将负关键点纳入模型。

定理5 由公式(37)定义的隐式混合$B$的距离下限为：

\[d(\boldsymbol{x}, B) \geq \frac{2}{3} f(\boldsymbol{x}) \sum_{i = 1}^{n} R_i \tag{38}\]

证明：对公式(36)进行多次求导可得：

\[C'(r)=6\frac{r^2}{R^3}-6\frac{r}{R^2} \tag{39}\] \[C''(r)=12\frac{r}{R^3}-\frac{6}{R^2} \tag{40}\]

求解$C’‘(r)=0$可得到最大斜率，其出现在中点$r = R/2$处。其利普希茨常数为：

\[\text{Lip }C(r)=\vert C'(R/2)\vert =\frac{3}{2R} \tag{41}\]

和的利普希茨常数由各部分利普希茨常数之和界定，由此得到上述结果。$\square$

在实际应用中，通过对公式(38)中具有非零贡献的关键点$i$进行第一项求和，可以使用局部利普希茨边界来获得更精确的距离边界。如[Wyvill & Trotman, 1990]中详细所述，围绕关键点$\boldsymbol{p}_i$使用半径为$R_i$的包围体，可进一步提高效率。

D.2 超椭圆混合

[Rockwood & Owen, 1987]中的伪范数混合是一种局部混合。它返回有符号距离函数的隐式曲面混合并集的$p$-范数距离。这种混合基于[Ricci, 1974]的开创性工作，在该工作中，隐式曲面是通过将严格非负函数设为1来定义的。因此，我们需要通过定义以下式子将函数重新表述成这种形式：

\[g_A(\boldsymbol{x}) = \max\left\{1 - \frac{f_A(\boldsymbol{x})}{r_A}, 0\right\} \tag{42}\]

$g_B$的定义类似。参数$r_A$，$r_B$将界定局部混合的范围，如果各分量是有符号距离函数，则以欧几里得单位表示。$f_A$的隐式曲面与$f_B$的隐式曲面并集的伪范数混合由以下隐式曲面定义：

\[f_{AB}(f_A(\boldsymbol{x}), f_B(\boldsymbol{x})) = \left(\frac{g_A(\boldsymbol{x})r_A + g_B(\boldsymbol{x})r_B}{g_A(\boldsymbol{x}) + g_B(\boldsymbol{x})}(1 - g_A(\boldsymbol{x})^p - g_B(\boldsymbol{x})^p)\right)^{\frac{1}{p}} \tag{43}\]

参数$p$是一个权重参数，用于描述混合与原始曲面的贴合程度。相反，混合交集由$-f_{AB}(-f_A(\boldsymbol{x}), -f_B(\boldsymbol{x}))$定义。

$f_{AB}$的定义域是$f_A(\boldsymbol{x}) \leq r_A$且$f_B(\boldsymbol{x}) \leq r_B$的区域。在这个定义域之外，无法平滑地组合$f_A$和$f_B$的结果，从而在混合周围的空间中产生褶皱[Rockwood & Owen, 1987]。这种梯度不连续性对某些求根算法可能是灾难性的，但不会影响前面描述的几何光线相交方法。

伪范数混合在4.2节的图8和图10中进行了展示。

E 到变换后对象的距离

在应用函数之前，通过对空间应用逆变换来对隐式曲面进行变换。设$\boldsymbol{T}(\boldsymbol{x})$为一个变换，$f(\boldsymbol{x})$定义隐式曲面。那么变换后的隐式曲面被定义为：

\[f(\boldsymbol{T}^{-1}(\boldsymbol{x})) = 0 \tag{44}\]

复合函数的利普希茨常数不大于各分量利普希茨常数的乘积。我们关注变换逆的利普希茨常数，它不一定是变换的利普希茨常数的倒数。

等距变换

等距变换是保持距离不变的变换。如果$\boldsymbol{I}$是一个等距变换，由$f$返回的距离无需调整：

\[d(\boldsymbol{x}, \boldsymbol{I} \circ f^{-1}(0)) = d(\boldsymbol{I}^{-1}(\boldsymbol{x}), f^{-1}(0)) \tag{45}\]

等距变换包括旋转、平移和反射。

均匀缩放

均匀缩放是一种形式为$\boldsymbol{S}(\boldsymbol{x})$的变换：

\[\boldsymbol{S}(\boldsymbol{x}) = s\boldsymbol{x} \tag{46}\]

其中$s$是缩放因子。其逆变换$\boldsymbol{S}^{-1}$是按$1/s$进行缩放。因此，到缩放后的隐式曲面的距离为：

\[d(\boldsymbol{x}, \boldsymbol{S}(f^{-1}(0))) = s d(\boldsymbol{S}^{-1}(\boldsymbol{x}), f^{-1}(0)) \tag{47}\]

并且逆缩放的利普希茨常数为$1/s$。

线性变形

到隐式曲面线性变换像的距离，可通过确定线性变换的逆变换（其本身也是一个线性变换）的利普希茨常数来求得。

任意线性变换的利普希茨常数可通过幂法求得，该方法通过迭代找出矩阵的最大特征值[Gerald & Wheatley, 1989]。

锥化

锥化变形是根据第三轴的函数$r(\cdot)$对两个轴进行缩放[Barr, 1984]。锥化的定义为：

\[\text{taper }(\boldsymbol{x}) = (r(z)x, r(z)y, z) \tag{48}\]

而其逆变换仅将$r(\cdot)$换为$r^{-1}(\cdot)$。逆变形的利普希茨常数为：

\[\text{Lip taper} = \min_{z \in \mathbb{R}} r^{-1}(z) \tag{49}\]

换句话说，逆锥化的利普希茨常数是其 “最紧” 锥化的程度。

扭转

扭转变形是根据第三轴的线性函数$a(\cdot)$对两个轴进行旋转。扭转的定义为：

\[\text{twist }(\boldsymbol{x}) = \begin{pmatrix} x \cos a(z) - y \sin a(z), \\ x \sin a(z) + y \cos a(z), \\ z \end{pmatrix} \tag{50}\]

而其逆变换仅将$a(\cdot)$换为$a^{-1}(\cdot)$。扭转在$\mathbb{R}^n$上不是利普希茨连续的，因为对于任意的利普希茨界$\lambda$，都能在远离扭转轴的$\mathbb{R}^n$中找到两个点，它们经过变换后的距离之比大于$\lambda$。 因此，扭转必须限制在满足利普希茨条件的定义域内。 这样的一个定义域是沿着扭转轴方向的单位圆柱体。扭转的利普希茨常数是根据单位圆柱体内的最坏情况场景计算得出的，如图15所示：

\[\text{Lip twist} = \sqrt{4 + \left(\frac{\pi}{a'}\right)^2} \tag{51}\]

F 到超纹理的距离

复杂噪声函数的使用极大地增强了过程模型的能力，使现有的几何表示更加逼真。最近的研究工作直接将随机纹理应用于几何图形，而不是改变着色效果[Perlin & Hoffert, 1989; Lewis, 1989]。

最初的 “超纹理” 系统为包括毛发和火焰在内的各种表面现象建立了隐式模型。本附录重点介绍将超纹理的噪声模型整合到球体追踪中，不过同样的技术也可用于适配其他超纹理模型。

“超纹理” 将实体过程噪声视为一种变形，并且是为与隐式曲面配合使用而设计的。其最初的光线追踪算法沿着光线以固定间隔步进。确定 “超纹理化” 形状的距离边界，能够让球体追踪更高效地渲染结果。

与[Perlin & Hoffert, 1989]稍有不同，噪声函数 $\text{noise}:\mathbb{R}^3 \to \mathbb{R}$ 通过影响有符号距离函数 $f$ 的值域（而不是像之前的附录那样影响其定义域）来对其隐式曲面进行变形。变形后的曲面由函数 $f(\boldsymbol{x}) + \text{noise}(\boldsymbol{x})$ 隐式定义。

带限实体噪声源于对随机单位向量晶格的平滑插值。概括[Perlin & Hoffert, 1989]的内容，噪声函数表示为：

\[\text{noise}(x, y, z)=\sum_{k = \lfloor z \rfloor}^{\lfloor z \rfloor + 1} \sum_{j = \lfloor y \rfloor}^{\lfloor y \rfloor + 1} \sum_{i = \lfloor x \rfloor}^{\lfloor x \rfloor + 1} C_1(\vert x - i\vert ) C_1(\vert y - j\vert ) C_1(\vert z - k\vert ) \Gamma(i, j, k) \cdot (x - i, y - j, z - k) \tag{52}\]

其中 $C_R$ 是用于软物体的三次高斯近似公式(36)，$\Gamma$ 是一个随机单位向量数组。根据定理5，我们知道 $\text{Lip }C_1 = 3/2$。在 $\Gamma$ 中，两个相反的向量可能是相邻的，所以 $\text{Lip }\Gamma = 2$。因此，它们的复合结果是 $\text{Lip noise} = 3$。

基于 $1/f^{\beta}$ 频谱分布的分形噪声是通过对噪声函数的缩放版本求和得到的：

\[1/f^{\beta} \text{ noise}(\boldsymbol{x})=\sum_{i = 0}^{n - 1} \frac{\text{noise}(2^i \boldsymbol{x})}{2^{\beta i}} \tag{53}\]

这里涉及 $n$ 个倍频程[Perlin & Hoffert, 1989]。

当参数 $\beta = 0$ 时得到白噪声，$\beta = 1$ 时得到自然界常见的 $1/f$ 噪声，$\beta = 2$ 时对应布朗运动。当 $1 \leq \beta \leq 3$ 时，它与变形后所得曲面的分形维数 $D$ 的关系为 $D = 2+\frac{3 - \beta}{2}$ [Voss, 1988]。$2^i$ 因子增加了频率（从水平方向压缩图像），而 $1/2^{\beta i}$ 因子降低了幅度（从垂直方向压缩图像）。

对于 $1/f$ 噪声，幅度随着频率的增加成比例降低，所以其利普希茨常数等于各个噪声函数之和：

\[\text{Lip }1/f \text{ noise} = 3n \tag{54}\]

因此，$1/f$ 噪声不是利普希茨连续的，但对于有限的 $n$ ，其带限形式是利普希茨连续的。

对于布朗运动（$\beta = 2$），随着频率增加，幅度呈几何级数降低，结果为：

\[\text{Lip }1/f^{2} \text{ noise} = 3(2 - 1/2^{n - 1}) \leq 6 \tag{55}\]

因此，布朗运动是利普希茨连续的（这也可以从将布朗运动定义为白噪声的积分推导得出）。

噪声函数在4.2节的图11中进行了展示。