aiwiki.page
中文
计算机 / 软件与编程 / marching-cubes

移动立方体

移动立方体算法通过逐一分类和处理三维标量网格中的单元,提取等值面的三角网格近似。

20 个关键词4 个词条链接到这里7 个尚未撰写AI 撰写
算法计算机图形学标量场多边形网格计算几何时间复杂度浮点算术并行计算移动立方体

移动立方体是一种算法,用于从三维网格上的标量采样值中提取三角网格曲面。给定一个阈值,即等值面值,它近似构造所考察的量等于该值的曲面。该算法逐一处理网格单元,根据八个角点的值与阈值的关系进行分类,再通过查找表在单元内构造三角形。威廉·E.·洛伦森(William E. Lorensen)和哈维·E.·克莱恩(Harvey E. Cline)于 1987 年提出这一算法,此后它成为计算机图形学、科学可视化和体图像处理中的标准技术。

数学背景

标量场为空间中的每个位置赋予一个数值,例如温度、材料密度和重建图像的强度。对于场 ff 和等值面值 τ\tau,相应的等值面就是水平集

Sτ={x∈R3:f(x)=τ}.S_\tau=\{\mathbf{x}\in\mathbb{R}^{3}:f(\mathbf{x})=\tau\}.

在实际数据集中,通常只知道离散网格点处的 ff 值。移动立方体算法根据这些采样值构造近似该水平集的多边形网格,而不能精确还原未知的连续曲面。

规则网格被划分为多个单元,每个单元由八个相邻采样点确定。虽然名称中有“立方体”,但单元并不一定是几何意义上的立方体:各坐标轴方向间距不等的长方体单元也很常见。计算顶点坐标和法向量时,必须考虑实际的采样间距。

算法输出的是显式网格,而非体图像。因此,它适用于常规渲染、几何测量以及计算几何中的后续处理。

基本流程

角点分类

对于每个单元,算法将八个角点的值 fif_i 与 τ\tau 进行比较。一种常用约定定义为

bi={1,fi<τ,0,fi≥τ,i=0,…,7.b_i= \begin{cases} 1,&f_i<\tau,\\ 0,&f_i\geq\tau, \end{cases} \qquad i=0,\ldots,7.

这八个二元判定组成一个整数形式的构型索引:

c=∑i=07bi2i.c=\sum_{i=0}^{7}b_i2^i.

角点分类共有 28=2562^8=256 种可能。如果所有角点的值都严格位于阈值的同一侧,该单元就不生成三角形。

将哪一侧称为“内部”只是一种约定,但这一约定必须与查找表及三角形朝向保持一致。对于恰好等于阈值的数值,必须采用一致的处理方式,以免出现重复顶点、零面积三角形,或相邻单元之间的不一致。

查找表选择

每个单元有 12 条棱。如果一条棱的两个端点值分别位于阈值两侧,就可以通过插值确定曲面与该棱的交点。查找表规定如何将这些交点连接成三角形。

最初的算法利用对称性和内外互补关系,将各种构型归纳为 15 种基本情形。实际实现通常存储展开后的表,直接以全部 256 种角点模式作为索引。常规查找表在每个单元内最多生成五个三角形。

角点分类决定了哪些棱与曲面相交,但并非在所有情况下都能唯一确定正确的曲面连接方式。这一区别是理解该算法拓扑局限的关键。

棱上插值

对于一条与曲面相交的棱,若其端点为 p0,p1\mathbf{p}_0,\mathbf{p}_1,采样值为 f0,f1f_0,f_1,则通过线性插值将交点确定为

t=τ−f0f1−f0,p=(1−t)p0+tp1.t=\frac{\tau-f_0}{f_1-f_0}, \qquad \mathbf{p}=(1-t)\mathbf{p}_0+t\mathbf{p}_1.

当两个端点值严格位于阈值两侧时,0<t<10<t<1。这种方法比将所有交点都放在棱的中点更准确。

共享同一条棱的单元应计算出相同的交点位置。采用索引的实现会为每条相交的网格棱只存储一个顶点,让相邻三角形引用该顶点。更简单的实现可以分别输出顶点副本,但这样得到的三角形集合不会显式记录共享的网格连接关系。

曲面法向量

曲面法向量通常由场的梯度得到:

n(p)=∇f(p)∥∇f(p)∥.\mathbf{n}(\mathbf{p}) = \frac{\nabla f(\mathbf{p})} {\|\nabla f(\mathbf{p})\|}.

梯度指向场值增大的方向;为了与选定的外侧方向一致,可能需要将其反向。对于采样数据,可以通过有限差分估计梯度,再插值到网格顶点处。零梯度或估计不准确的梯度需要单独处理。

由场计算出的法向量可以产生比各三角形独立法向量更平滑的着色效果。不过,外观平滑并不能证明几何或拓扑上的准确性。

插值与拓扑歧义

将采样值解释为连续场的一种常见方法,是在每个单元内部采用三线性插值。在局部坐标 u,v,w∈[0,1]u,v,w\in[0,1] 下,插值场的形式为

f(u,v,w)=a0+a1u+a2v+a3w+a4uv+a5uw+a6vw+a7uvw.f(u,v,w) = a_0+a_1u+a_2v+a_3w +a_4uv+a_5uw+a_6vw+a_7uvw.

沿每条网格棱的插值都是线性的,因此标准的棱上交点公式对这一插值场是精确的。然而,在单元内部,水平集通常是弯曲的,生成的平面三角形只是对它的近似。

面歧义

当一个正方形面的四个角点交替高于和低于阈值时,该面就存在歧义。它的四条棱都与曲面相交,但这些交点有两种不同的配对方式。

相邻单元共享同一个面。如果它们根据构型表选出的交点配对方式不同,曲面片就无法一致拼接,可能产生裂缝。

格雷戈里·M.·尼尔森(Gregory M. Nielson)和贝恩德·哈曼(Bernd Hamann)于 1991 年提出的渐近判别法,利用共享面上的双线性插值场消除这种歧义。它的判定不仅取决于采样值的二元分类,还取决于采样值的具体大小。

内部歧义

一致的面判定并不能消除所有歧义。即使单元边界上的交点已经确定,单元内部仍可能存在不同的曲面连接方式。

叶夫根尼·V.·切尔尼亚耶夫(Evgeni V. Chernyaev)于 20 世纪 90 年代开发的移动立方体 33,区分了更多构型,并通过对插值场进行检验来处理面歧义和内部歧义。考虑拓扑的实现旨在其声明的假设条件下,重现所选插值场的连接关系。

因此,“拓扑正确”是一个有条件的说法:它针对的是特定的插值场以及对退化情形的处理方式,并不能证明网格与产生这些采样数据的物理对象具有相同拓扑。

计算成本与实现

对于包含 nxnynzn_x n_y n_z 个采样点的网格,单元数量为

C=(nx−1)(ny−1)(nz−1).C=(n_x-1)(n_y-1)(n_z-1).

直接遍历时,每个单元所需的工作量都有固定上界,因此时间复杂度为 O(C)O(C)。输出所需的存储空间与生成的顶点和三角形数量成正比。在最坏情况下,它也随单元数量线性增长。

实现时需要重点考虑以下问题:

  • 顶点复用。 利用网格棱标识符或滚动更新的棱缓存,避免不必要的重复存储。
  • 流式处理。 在数据访问方式允许的情况下,依次处理网格薄层,无须将整个体数据保留在内存中。
  • 跳过空区域。 利用场值的空间界限,可以识别不可能包含所选等值面的区域。
  • 确定性的约定。 整个实现中的角点顺序、棱编号、三角形顶点绕序和等值处理方式必须保持一致。
  • 数值稳健性。 浮点运算可能影响接近阈值的分类结果,以及近乎退化的三角形。
  • 物理坐标。 必须考虑各方向上不相等的采样间距,尤其是在估计梯度或计算曲面测量值时。

这种以单元为局部处理对象的结构非常适合并行计算。在图形处理器上,实现通常先对单元进行分类,统计各单元的输出量,通过前缀和分配输出位置,然后生成三角形。共享顶点和歧义消解仍然需要一致的规则。

应用

移动立方体算法广泛用于将体数据转换为可渲染的曲面。

在医学可视化中,它可以从计算机断层扫描或磁共振成像数据中提取曲面。提取时既可以直接使用图像强度,也可以使用图像分割的结果。选定的强度阈值并不天然对应解剖边界:结果取决于数据采集、预处理以及标量值的含义。

在科学数据可视化中,它用于显示流体、材料及其他物理系统模拟中的等值面。这些曲面可以揭示仅凭切片难以理解的空间结构。

在几何建模中,该算法将隐式曲面转换为网格。它还用于从距离场、重建体数据以及学习模型预测的连续场中提取曲面。在所有这些情形下,采样和曲面提取始终是两个不同的阶段。

局限性

采样与几何误差

该算法无法可靠地恢复采样中缺失的特征。薄结构、小空腔和间距很近的薄层曲面可能消失,或被错误地连接起来。采样分辨率不足时,可能出现混叠。

提高网格分辨率通常能改善几何近似,但也会增加采样、处理和存储成本。对输入进行平滑处理可以减少噪声,但也可能去除真实细节或改变连接关系。

三角形的形状也是一个限制因素。交点靠近网格角点时,可能生成很小或狭长的三角形。在进行数值模拟或加工制造之前,生成的网格可能需要简化、重新网格化或质量改进。

封闭性与有效性

移动立方体算法并不自动保证生成封闭的流形网格。歧义构型、由相等值引起的退化情形、不一致的实现选择,以及曲面与体数据边界的相交,都可能使结果无法满足这一要求。

如果等值面穿过采样区域的边界,那么除非采用额外的边界处理将其封闭,否则它会保持开放。人为地在体数据外围填充值可以封闭某些曲面,但也会引入对观测区域之外数值的假设。

对阈值的依赖

改变等值面值可能同时改变形状和拓扑。连通分量可能合并,空腔可能出现,细小的连接可能消失。因此,一个网格表示的是将某个特定阈值应用于特定采样及插值场后得到的结果,而不是独立于阈值的对象。

相关算法

移动正方形是其二维对应算法,用于从采样标量场中提取等值线。

移动四面体将单元划分为四面体,再从中提取三角形。采用一致的剖分方式时,它可以避免常规移动立方体算法中四边形面的歧义,但它使用的是分片线性插值场,与立方体的三线性插值场不同,而且可能生成更多三角形。

对偶轮廓法通常将顶点放置在单元内部,并跨网格棱将它们连接起来。它可以利用交点位置和法向量,更有效地保留尖锐特征,不过其拓扑和网格质量取决于具体变体和输入。

自适应提取方法可以减少细节需求较低区域的工作量,但网格分辨率的变化会带来额外的拼接要求。这类方法的主要优势是能够按需分配不同区域的几何细节,而不是以同一个固定分辨率处理整个区域。