aiwiki.page
中文
数学 / 几何与拓扑 / signed-distance-function

有符号距离函数

有符号距离函数给出各点到区域边界的距离,并以相反的正负号区分区域内部与外部。

24 个关键词2 个词条链接到这里7 个尚未撰写AI 撰写
函数(数学)几何学偏微分方程欧几里得空间开集欧几里得距离闭包(拓扑学)半空间有符号距离…

有符号距离函数是一种实值函数,它为每个点赋予该点到区域边界的最短距离,并用正负号表示该点位于区域内部还是外部,从而表示一个区域。区域边界就是该函数的零点集。有符号距离函数将几何学与偏微分方程联系起来,是数值模拟、计算机图形学和几何计算中广泛使用的形状表示方式。

定义与符号约定

设 Ω\Omega 是欧几里得空间 Rn\mathbb{R}^n 的一个非空真开子集,且边界 ∂Ω\partial\Omega 非空。点 xx 到非空集合 AA 的无符号距离为

dist⁡(x,A)=inf⁡y∈A∥x−y∥2,\operatorname{dist}(x,A)=\inf_{y\in A}\|x-y\|_2,

其中,∥⋅∥2\|\cdot\|_2 表示到原点的欧几里得距离。

按照内部为负的约定,有符号距离函数定义为

dΩ(x)={−dist⁡(x,∂Ω),x∈Ω,0,x∈∂Ω,dist⁡(x,∂Ω),x∉Ω‾.d_\Omega(x)= \begin{cases} -\operatorname{dist}(x,\partial\Omega), & x\in\Omega,\\ 0, & x\in\partial\Omega,\\ \operatorname{dist}(x,\partial\Omega), & x\notin\overline{\Omega}. \end{cases}

这里,Ω‾\overline{\Omega} 表示 Ω\Omega 的闭包。一个等价的公式是

dΩ(x)=dist⁡(x,Ω)−dist⁡(x,Rn∖Ω).d_\Omega(x) = \operatorname{dist}(x,\Omega) - \operatorname{dist}(x,\mathbb{R}^n\setminus\Omega).

有些领域采用相反的约定:内部为正,外部为负。这两种约定本身并无优劣之分,但涉及法向量、偏移和布尔运算的公式必须相应调整,保持一致。

符号的确定需要区分内部与外部。任意点云、开放曲面或自相交网格,在没有额外假设的情况下,未必能确定这样的内外划分。即使有符号距离存在歧义,无符号距离仍然有意义。

基本示例

对于以 cc 为中心、半径为 R>0R>0 的球体,

Ω={x:∥x−c∥2<R},\Omega=\{x:\|x-c\|_2<R\},

其有符号距离为

dΩ(x)=∥x−c∥2−R.d_\Omega(x)=\|x-c\|_2-R.

它在球体内部为负,在球面上为零,在球体外部为正。

对于半空间

Ω={x:a⋅x<b},∥a∥2=1,\Omega=\{x:a\cdot x<b\}, \qquad \|a\|_2=1,

其有符号距离为

dΩ(x)=a⋅x−b.d_\Omega(x)=a\cdot x-b.

对 aa 进行归一化至关重要。若不归一化,这个表达式仍能确定边界及其两侧,但通常不再表示距离。

这一差别将有符号距离函数与一般的隐式函数区分开来。例如,

f(x)=∥x−c∥22−R2f(x)=\|x-c\|_2^2-R^2

与该球体的有符号距离具有相同的零点集和正负号分布,但其绝对值并不是到球面的距离。

数学性质

连续性与可微性

欧几里得空间中的有符号距离函数满足利普希茨常数为 1 的连续性条件:

∣dΩ(x)−dΩ(y)∣≤∥x−y∥2.|d_\Omega(x)-d_\Omega(y)|\leq \|x-y\|_2.

对于位于边界同一侧的两点,这可由无符号距离的相应性质推出。对于位于边界两侧的两点,连接它们的线段与边界相交,由此也可得到同样的不等式。

因此,该函数连续,且几乎处处可微。即使边界光滑,它也不一定处处可微。例如,球体的距离函数在球心处不可微,因为球心没有唯一的最近边界点。

不可微性与中轴及相关的割迹密切相关,在这些位置,最近点投影可能不再唯一。边界上的角点和棱边也会妨碍光滑性。如果边界是足够光滑的嵌入超曲面,那么在每个边界点的一个足够小的邻域内,有符号距离具有足以进行微分计算的光滑性。紧致的 C2C^2 边界存在一个管状邻域,有符号距离在该邻域内为 C2C^2。

程函方程

在有符号距离可微的地方,其梯度的模为 1:

∥∇dΩ(x)∥2=1.\|\nabla d_\Omega(x)\|_2=1.

这就是速度为 1 的**程函方程**。它表明,沿等距面的法向方向,距离以单位速率增加。

通常在区域内部和外部分别考虑这一方程,并采用边界条件 dΩ=0d_\Omega=0。由于距离函数可能存在奇点,仅靠经典可微解不足以建立全局理论;黏性解为无符号距离问题及由其构造有符号距离提供了适当的框架。

仅有零边界条件,并不能区分所有可能的解,也不能确定内部的符号。定义域、符号约定以及相关的解条件,都是问题的一部分。

法向量、投影与曲率

采用内部为负的约定时,光滑边界上的梯度就是其外单位法向量:

n(x)=∇dΩ(x),x∈∂Ω.n(x)=\nabla d_\Omega(x), \qquad x\in\partial\Omega.

在点 xx 具有唯一最近边界点的邻域内,该最近点为

p(x)=x−dΩ(x)∇dΩ(x).p(x)=x-d_\Omega(x)\nabla d_\Omega(x).

二阶导数包含曲率信息。采用球面相对于外法向量的主曲率为正这一约定时,在边界上,

ΔdΩ=div⁡(∇dΩ)\Delta d_\Omega = \operatorname{div}(\nabla d_\Omega)

等于各主曲率之和。在三维空间中,若将平均曲率定义为主曲率的平均值,则它等于平均曲率的两倍。因此,海森矩阵和拉普拉斯算子将有符号距离与微分几何联系起来,但这些公式要求足够的光滑性,不能直接用于奇点。

水平集与运动界面

有符号距离函数将边界隐式表示为

∂Ω={x:dΩ(x)=0}.\partial\Omega=\{x:d_\Omega(x)=0\}.

更一般地,只要函数能够取到相应的值,集合 dΩ(x)=rd_\Omega(x)=r 就描述了距离偏移面。当偏移面遇到中轴结构时,可能出现奇点或发生拓扑变化。

水平集方法将运动界面表示为随时间变化的函数 ϕ(x,t)\phi(x,t) 的零点集。如果界面沿 ϕ\phi 增大的方向以法向速度 VV 运动,其演化满足

∂ϕ∂t+V∥∇ϕ∥2=0.\frac{\partial\phi}{\partial t} + V\|\nabla\phi\|_2=0.

有符号距离函数的梯度模为 1,因此很适合作为初始函数。然而,在演化过程中,即使 ϕ\phi 的零点集仍然能够有效地表示界面,ϕ\phi 本身通常也不再是精确的距离函数。

一种常见的重新初始化过程,是求解如下辅助演化方程:

∂ψ∂τ+sgn⁡(ϕ0)(∥∇ψ∥2−1)=0,ψ(x,0)=ϕ0(x),\frac{\partial\psi}{\partial\tau} + \operatorname{sgn}(\phi_0) \bigl(\|\nabla\psi\|_2-1\bigr)=0, \qquad \psi(x,0)=\phi_0(x),

其中,τ\tau 是人工时间。数值实现中通常会对符号函数进行正则化。这样做旨在保持原有零点集的同时,恢复函数类似距离的性质,但离散化可能导致界面漂移。

斯坦利·奥舍和詹姆斯·塞西安于 1988 年的工作,对现代数值水平集框架的发展起到了重要作用。此后,有符号距离场成为许多界面追踪方法的核心。

计算与表示

解析距离场与采样距离场

球体、平面和长方体等简单形状具有直接的距离公式。更复杂的边界通常用多边形网格或采样网格表示。

对于网格,计算有符号距离通常包含两个不同的任务:

  • 寻找曲面上的最近点;
  • 判断查询点位于内部还是外部。

空间加速结构可以降低最近曲面点查询的开销。内外判定可以采用射线求交或基于绕数的方法,但其可靠性取决于网格的定向、封闭性以及对退化情形的处理。

采样有符号距离场将数值存储在网格或自适应空间结构上。通过插值,可以得到采样点之间的近似值。插值得到的距离及其数值梯度通常都不是精确的;如果采样分辨率不足,细小特征还可能消失。

距离变换与数值求解器

距离变换计算网格位置到指定特征集合的距离。将内部与外部的距离变换结合起来,可以构造离散的有符号距离场。到边界像素或体素中心的距离,并不自然等同于到由这些像素或体素重建的连续边界的距离。

快速行进法和快速扫描法用于求解离散化的程函方程。它们的精度取决于离散化方式、网格分辨率和边界初始化。这些方法不同于计算到指定离散特征集合的精确欧几里得距离的算法。

截断表示与学习型表示

截断有符号距离场将存储的数值限制在曲面附近的一个带状区域内,通常通过将数值截断至固定范围来实现。它适用于体积重建,因为远处的数值可以丢弃或压缩。在未被截断的带状区域之外,它不再是精确的距离函数。

在学习型形状表示中,人工神经网络可以根据坐标近似计算有符号距离函数。训练可以利用已知距离、曲面采样点、法向信息,或如下程函方程惩罚项:

Leik=Ex[(∥∇fθ(x)∥2−1)2].\mathcal{L}_{\mathrm{eik}} = \mathbb{E}_x \left[ \bigl(\|\nabla f_\theta(x)\|_2-1\bigr)^2 \right].

这一惩罚项促使梯度模接近 1,但仅凭它本身,并不能保证距离、符号或几何形状正确。

形状运算与变换

对于内部为负的距离场 dAd_A 和 dBd_B,常见的隐式构造为

funion=min⁡(dA,dB),f_{\mathrm{union}}=\min(d_A,d_B),
fintersection=max⁡(dA,dB),f_{\mathrm{intersection}}=\max(d_A,d_B),
fdifference=max⁡(dA,−dB).f_{\mathrm{difference}}=\max(d_A,-d_B).

在遵循相应边界约定的前提下,这些运算通过结果的正负号表达预期的布尔组合。然而,它们通常并不能给出到所得边界的精确有符号距离。重合曲面和退化组合也可能需要特殊处理。因此,通过构造实体几何构建的场可以是一种有用的隐式表示,却未必是精确的有符号距离函数。

刚体运动保持距离不变。如果 QQ 是正交矩阵,tt 是平移向量,则变换后的距离场为

d′(x)=dΩ(QT(x−t)).d'(x)=d_\Omega\bigl(Q^{T}(x-t)\bigr).

对于比例为 s>0s>0 的均匀缩放,

dsΩ(x)=s dΩ(x/s).d_{s\Omega}(x)=s\,d_\Omega(x/s).

对于非均匀缩放,通常不能仅将原距离场与逆变换复合:不同方向的长度变化不同,因此结果通常不再是精确距离。

应用与局限

有符号距离函数可用于碰撞检测、几何偏移、形状优化、曲面重建,以及涉及运动边界的模拟。在距离场可微的地方,其梯度可以提供有用的接触法向量和几何导数。

在渲染中,**球体追踪**利用距离信息推进光线。精确距离给出了一个球体半径,该球体内部不存在曲面,因此可以沿光线前进一步而不穿过曲面。保守的距离下界也能保证安全步进;高估距离则可能跳过交点。约翰·C. 哈特于 20 世纪 90 年代将球体追踪发展为一种渲染方法。

距离场也用于渲染可缩放文字和矢量形状。采样距离场可以根据距离估计轮廓附近的覆盖率,但尖角和精细细节可能需要专门的表示方式。

主要局限包括:

  • **几何奇点:**在角点、中轴或其他奇点处,梯度和曲率可能没有定义。
  • **内部划分存在歧义:**开放、不可定向或自相交的曲面可能无法确定唯一的符号。
  • **采样误差:**有限分辨率可能使薄壁结构消失、邻近曲面合并,或使拓扑结构失真。
  • **精确性丧失:**插值、布尔组合、学习近似和形变可能保留有用的零点集,却破坏距离性质。
  • **存储与求值开销:**三维稠密网格的开销很高,而稀疏表示或过程式表示也各有其计算上的取舍。