1.5 表示转换方法

来源：Mario Botsch 等人的 Polygon Mesh Processing，第 1 章 Surface Representations，1.5 小节 Conversion Methods。

这一节讨论参数化表面和隐式表面之间的转换。前面两节已经看到，这两类表示几乎是互补的：参数化表示适合采样和渲染，隐式表示适合 inside / outside 查询、距离查询和拓扑变化。因此，实际几何处理中经常需要在它们之间来回转换。

本节核心

两类表示各有优势：

表示	典型形式	优势
参数化表示	triangle mesh	采样、渲染、局部邻域、纹理
隐式表示	signed distance field / voxel grid	距离查询、inside/outside、拓扑变化、修补

因此需要两种转换：

parametric -> implicit
implicit -> parametric

对于本书而言，最重要的具体形式是：

triangle mesh -> signed distance field
signed distance field -> triangle mesh

注意

每次转换本质上都是一次 resampling。只要重新采样，就可能丢失细节、引入误差或改变拓扑。因此转换算法的核心目标是尽量减少信息损失。

图源说明：根据 Botsch et al., Polygon Mesh Processing, Chapter 1 的曲面表示与转换关系重绘，非原书截图。

为什么转换会损失信息

参数化表示和隐式表示通常都是有限采样。

例如：

• 参数化侧常见的是 triangle mesh。
• 隐式侧常见的是 uniform grid 或 adaptive grid。

从 mesh 转成 grid 时，需要在网格节点上采样距离值。

从 grid 转回 mesh 时，需要从离散标量场中提取等值面。

这两个过程都会受到采样分辨率影响：

$$h \downarrow \quad \Rightarrow \quad \text{误差降低，但存储和计算增加}$$

如果分辨率不足，尖锐边、薄结构、小孔洞和高曲率区域都容易被抹掉。

1.5.1 Parametric to Implicit

从参数化表示转成隐式表示，本质上是计算或近似 signed distance field。

对于三角网格 $M$，目标是构造：

$$d:\mathbb{R}^3\rightarrow \mathbb{R}$$

使得：

$$|d(\mathbf{x})| = \operatorname{dist}(\mathbf{x},M)$$

并且符号表示 $\mathbf{x}$ 在物体内部还是外部。

通常会在一个 3D grid 上采样：

$$d_{ijk}=d(\mathbf{g}_{ijk})$$

其中 $\mathbf{g}_{ijk}$ 是网格节点。

voxelization / scan conversion

一种直接方式是 voxelization 或 3D scan-conversion。

它们可以很快把几何体转成体素表示。

但直接 voxelization 通常得到的是 piecewise constant approximation，也就是每个 voxel 只有一个粗糙分类或常量值。

距离场通常不是处处光滑，因此实际中 piecewise linear 或 piecewise trilinear approximation 往往是精度和效率之间更好的折中。

网格节点到三角网格的距离

给定一个 grid node：

$$\mathbf{g}$$

要计算它到三角网格的 signed distance，需要两步：

1. 找到最近三角形或最近点。
2. 判断 $\mathbf{g}$ 在物体内部还是外部。

距离的绝对值是：

$$\operatorname{dist}(\mathbf{g},M) = \min_{\mathbf{x}\in M}\|\mathbf{g}-\mathbf{x}\|$$

如果最近点为：

$$\mathbf{c}$$

那么距离为：

$$\|\mathbf{g}-\mathbf{c}\|$$

寻找最近三角形如果暴力遍历所有面会很慢，因此通常使用空间加速结构，例如 kd-tree。

signed distance 的符号判断

仅有距离大小还不够，还需要判断符号。

设：

• $\mathbf{g}$ 是 grid node。
• $\mathbf{c}$ 是表面上的最近点。
• $\mathbf{n}(\mathbf{c})$ 是 $\mathbf{c}$ 处的外法向。

可以用向量：

$$\mathbf{g}-\mathbf{c}$$

和外法向的夹角判断内外。

如果：

$$(\mathbf{g}-\mathbf{c})^T\mathbf{n}(\mathbf{c}) < 0$$

则 $\mathbf{g}$ 在物体内部。

如果：

$$(\mathbf{g}-\mathbf{c})^T\mathbf{n}(\mathbf{c}) > 0$$

则 $\mathbf{g}$ 在物体外部。

注意

这个符号判断是否可靠，很依赖法向 $\mathbf{n}(\mathbf{c})$ 的计算方式。顶点、边、面附近的法向如果处理不好，signed distance field 会出现符号错误。

书中提到 angle-weighted pseudo-normals 可以提高这种符号测试的可靠性。

fast marching 加速距离传播

如果对整个 grid 的每个节点都精确求最近三角形，计算量会很大。

可以用 fast marching methods 加速。

基本思路是：

1. 先在三角网格附近的 grid nodes 上计算精确 signed distance。
2. 再从这些已知节点出发，向外传播距离值。
3. 以类似 breadth-first 的方式填充剩余未知节点。

这种方法利用了距离场的传播结构，避免每个远处节点都重新查找最近三角形。

1.5.2 Implicit to Parametric

从隐式表示转回参数化表示，通常叫 isosurface extraction。

目标是从标量场：

$$F:\mathbb{R}^3\rightarrow \mathbb{R}$$

中提取零水平集：

$$S=\{\mathbf{x}\mid F(\mathbf{x})=0\}$$

并生成一个 triangle mesh。

这种转换常见于：

• CSG 建模结果转网格。
• 医学 CT 中提取骨骼表面。
• mesh repair 后从 SDF 中恢复网格。
• implicit modeling 结果可视化。

Marching Cubes

isosurface extraction 的经典标准算法是 marching cubes。

它的输入是规则网格上的标量值，输出是三角网格。

基本流程：

遍历每个 grid cell
-> 判断该 cell 是否被 F=0 穿过
-> 在被穿过的边上计算交点
-> 根据查表结果生成局部三角片
-> 合并所有 cell 的局部三角片

由于每个 cell 可以独立处理，所以 marching cubes 很容易并行。

Marching Cubes 需要采样小立方体顶点的 SDF 吗？如何知道顶点在内还是在外？

是的。Marching Cubes 的核心输入就是规则网格节点上的标量值。

对一个小立方体，也就是一个 grid cell，它有 8 个角点：

$$\mathbf{p}_0,\mathbf{p}_1,\ldots,\mathbf{p}_7$$

算法会先在这 8 个角点上查询隐式函数或 SDF：

$$d_k = F(\mathbf{p}_k)$$

如果这个隐式函数就是 signed distance field，那么：

$$d_k = \operatorname{SDF}(\mathbf{p}_k)$$

判断 inside / outside 只看符号：

• $d_k<0$：点在物体内部。
• $d_k>0$：点在物体外部。
• $d_k=0$：点刚好在表面上。

因此，我们不是直接“看见”一个顶点在内还是在外，而是通过 SDF 的正负号判断。

例如一个 cube 的 8 个角点 SDF 符号为：

[-, -, +, +, -, +, +, -]

这说明这个小立方体的一部分角点在物体内部，一部分角点在外部。既然 inside 和 outside 同时存在，那么零水平集：

$$F(\mathbf{x})=0$$

大概率穿过这个 cube。

Marching Cubes 会把 8 个角点的 inside/outside 状态编码成一个 8-bit case index：

$$\text{case} = \sum_{k=0}^{7} b_k 2^k$$

其中：

$$b_k = \begin{cases} 1,& F(\mathbf{p}_k)<0\\ 0,& F(\mathbf{p}_k)\ge 0 \end{cases}$$

这个 case index 用来查表，决定哪些边被表面穿过，以及应该生成哪些三角形。

关键点是：Marching Cubes 并不需要知道 cube 内部完整的连续曲面长什么样。它只用 8 个角点的符号模式，近似推断表面如何穿过这个小立方体。

那么 SDF 值从哪里来？

常见来源有三种：

1. 已经有一个解析隐式函数，例如球：

$$F(\mathbf{x})=\|\mathbf{x}-\mathbf{c}\|-r$$

2. 从已有 triangle mesh 预先计算 signed distance field。

3. 像 DeepSDF 这类神经隐式表示，直接用网络查询：

$$F(\mathbf{x})=f_\theta(\mathbf{z},\mathbf{x})$$

所以完整流程可以理解为：

先在规则网格点上采样 SDF
-> 每个 cube 读取自己的 8 个角点 SDF
-> 用符号判断 inside/outside
-> 找到符号相反的边
-> 在这些边上插值出 F=0 的交点
-> 查表连接成交三角片

边上的交点插值

如果一条 grid edge 的两个端点：

$$\mathbf{p}_1,\quad \mathbf{p}_2$$

对应的标量值为：

$$d_1=F(\mathbf{p}_1), \qquad d_2=F(\mathbf{p}_2)$$

如果 $d_1$ 和 $d_2$ 符号不同，说明零水平集穿过这条边。

因为在 grid edge 上可以把 $F$ 近似为线性函数，交点 $\mathbf{s}$ 可以用线性插值计算：

$$\mathbf{s} = \frac{|d_2|}{|d_1|+|d_2|}\mathbf{p}_1 + \frac{|d_1|}{|d_1|+|d_2|}\mathbf{p}_2$$

这给出了一个近似的表面采样点。

查表生成三角片

每个 cube 有 8 个角点。

每个角点只看符号：

inside / outside

因此理论上有：

$$2^8=256$$

种符号配置。

Marching cubes 使用 lookup table，根据角点符号配置决定：

• 哪些边被表面穿过。
• 交点如何连接。
• 生成哪些三角形。

由于很多配置可以通过旋转、反射或符号反转得到，实际基础模式少很多。

ambiguous cases 和 watertightness

某些 cube 配置存在二义性。

如果处理不一致，相邻 cell 生成的三角片可能无法正确拼接，产生裂缝。

改进后的 lookup table 可以解决这些裂缝问题，生成 watertight 2-manifold isosurfaces。

这对 mesh repair 特别重要，因为修补算法往往希望输出一个封闭、无裂缝、流形的网格。

Marching Cubes 的 sharp feature 问题

标准 marching cubes 只在 grid edges 上放置交点。

这会导致尖锐边和角被截断或磨平。

直观上，它只能“沿体素边”采样表面，无法在 cell 内部放置额外点来表达 sharp feature。

因此，对于有尖锐特征的模型，标准 marching cubes 可能产生明显 alias artifacts。

Extended Marching Cubes

Extended Marching Cubes 的目标是更好地保留 sharp features。

它会利用距离函数的梯度：

$$\nabla F$$

来检测包含尖锐特征的 cell。

基本思想是：

1. 在边交点处估计法向或切平面。
2. 对 sharp feature 两侧的 tangent planes 求交。
3. 在 cell 内部加入额外采样点。
4. 生成更能贴合尖锐边角的局部网格。

这比标准 marching cubes 更能忠实重建尖锐特征。

高三角形复杂度问题

Marching cubes 还有一个常见问题：输出网格可能非常密。

如果使用高分辨率 regular grid，生成的三角形数量会非常大。

一种处理方式是：

先 marching cubes
-> 再 mesh decimation

但更好的方式可能是在提取阶段就使用 adaptive octree，避免一开始就生成过多三角形。

Dual Contouring

Dual contouring 是另一类从 adaptive octree 直接提取网格的方法。

与 marching cubes 不同：

• marching cubes 通常在 grid edges 上产生顶点。
• dual contouring 在 voxel 内部生成顶点。
• dual contouring 为每条与等值面相交的 voxel edge 构造多边形。

它能更好地支持自适应结构和特征保持。

缺点是：在某些包含多个 surface sheets 的 cell 配置中，dual 方法可能产生 non-manifold meshes。

后续方法可以修复这个问题。

Delaunay refinement 方法

除了 marching cubes 系列算法，还有基于 3D Delaunay triangulation 的方法。

这类方法通过细化和过滤三维 Delaunay 剖分来得到表面网格。

优点是可以生成形状较好的三角形，并在拓扑和几何上较好逼近输入表面。

这类方法更偏计算几何路线，CGAL 中有相关实现。

两个方向的转换对比

转换方向	核心任务	常见方法	主要风险
parametric -> implicit	计算 signed distance field	voxelization、closest triangle、fast marching	符号错误、分辨率不足、细节损失
implicit -> parametric	提取 isosurface	marching cubes、dual contouring、Delaunay refinement	裂缝、过密网格、sharp feature 被磨平

和前几节的关系

1.3 说明 triangle mesh 灵活、直接、适合渲染和编辑。

1.4 说明 implicit / SDF 适合距离查询、CSG、拓扑变化和修补。

1.5 说明实际系统中常常需要混合使用：

mesh -> SDF -> repaired / processed field -> mesh

这也是很多 mesh repair 和 geometry processing pipeline 的核心套路。

本节记忆点

• 参数表示和隐式表示互补，因此需要转换方法。
• 每次转换都是 resampling，可能造成信息损失。
• parametric -> implicit 的核心是计算 signed distance field。
• 对三角网格求 SDF，需要计算 grid node 到最近三角形的距离，并判断内外符号。
• fast marching 可以从表面附近的精确距离向外传播，减少全网格精确计算成本。
• implicit -> parametric 的核心是 isosurface extraction。
• marching cubes 是经典等值面提取算法。
• marching cubes 在 cube 边上插值产生表面点，并用 lookup table 生成局部三角片。
• 标准 marching cubes 对 sharp features 不友好，Extended Marching Cubes 会利用梯度和切平面改善。
• adaptive octree、dual contouring 和 Delaunay refinement 可以减少复杂度或改善网格质量。

后续问题

进入 1.6 时可以重点关注：

1. 参数表示和隐式表示的优缺点如何总结？
2. hybrid representations 为什么能结合两者优势？
3. 本书为什么最终以 polygon meshes 为主线？
4. 后续章节中哪些算法会依赖这些表示转换？