为什么需要并列规则
四面体插值已经指定每个单元内各点的标量值。要显示水平集,还须用算法产生多边形,并令相邻单元在边界相接。上一节证明了非退化截面的形状;本节提供有限的具体方法,并规定节点值刚好等于指定水平值时的决定。并列规则会改变所计算的数学对象,应与网格一同记录,不能藏在浮点比较的细节里。
设定与全局水平值规则
定义 13.1.1
(带顶点数据的相容四面体复形)
设 是 中有限的相容几何四面体复形:每个四面体非退化,任两个单形的交集为空或其共同面。每个顶点 都有全局共用位置 和标量值 。每个四面体上, 是四个节点值的仿射插值;相邻仿射函数在共同面的三个顶点相等,因此在整个面上相等。域为四面体的并集 。
暂不假设它是流形,也不假设边界封闭。以下视输入和计算为精确实数;浮点误差及可靠比较须另行处理。
定义 13.1.2
(全局水平值位移)
指定水平值 后,对整个网格选择同一个正数 。若有顶点满足 ,定义
若全部顶点值等于 ,任取 。令 。例如可约定: 存在时取 ,否则取 ,单位与 相同。只要记录所选数值并符合条件,其他选择亦可。原本等于 的顶点都严格低于 ;原本严格高于或低于 的顶点保持原来的一侧。没有顶点值等于 。这是全局水平值位移,不是各单元独立打破并列,也不是改动节点值。
输出代表 ,不一定是 。若四面体的四个顶点值皆为 ,则整个四面体属于 ,但其中没有 。即使 ,这个单侧曲面也未必找回孤立点、平坦单元或 的每一部分。另一位移幅度或向下位移可以得到不同曲面。若应用必须精确表示退化的原水平集,便要表示不同维数的部分,或另订并说明规则;本算法不声称做到这件事。
构造
定义 13.1.3
(被截边与边键)
若 与 异号,则称边 为被截边。它的边键是两个唯一顶点编号构成的二元组 ,按排序后存放,使两种端点顺序指向同一条边。
把每个顶点依 分成正、负两侧。对每条端点异号的边 ,用全局边识别键 只计算一次
分母非零,且 。以边键存储该点;交换端点次序得到相同位置。每个四面体依下列步骤处理:
- 若四个顶点符号相同,不输出图元。
- 否则收集三个或四个被截边上的点。四面体每个面有零条或两条被截边;若有两条,就连接该面上的两个交点。这些线段依循环次序构成截面多边形的边界。三个顶点时输出三角形;四个顶点时沿任一对角线分成两个三角形,例如取经排序后,其两端全局边键之配对字典序较小者。若需要指向场值增加方向的法线,令三角形方向与 一致。被截单元的梯度不可能为零。
- 共同边重用相同交点索引。四边形的对角线位于各自四面体内部,不改变共同面上的线段;相邻单元无须选同一对角线。
全局边键是两个唯一顶点编号排序后的配对;对角线两端的边键也先排序再按字典序比较。固定编号和 后,三角化便可重现。精确算术定义了上述数学输出。浮点实现中,即使两次使用相同公式也不能据此证明结果相等;共用存储可避免分别舍入的副本,但侧别判定和输入表示仍须有可靠规则。
概念视角组合
把单元看成正负号模式
对一个单元来说,只有四个 的正负号向量有影响。十六种模式中,两种全同号而不输出;八种是一个顶点与其余三个异侧(一比三),给出三角形;六种是二比二,给出四边形。由于 ,整个算法就是一张十六项的表,加上每条被截边一条插值公式。
定理 13.1.4
(精确截面与共同面一致性)
在以上假设下,所有输出的闭三角形之并集恰好是 。在每个共用三角面上,两个相邻四面体给出相同的截面,包括端点和线段。
证明
(截面顶点落在被截边上,共同面一致)
在一个四面体内,仿射函数值是四个顶点值的凸组合。若所有值都严格在 同一侧,单元内所有点亦然。否则两侧皆有顶点, 不可能在单元内为常数; 是一个平面与四面体的交,故截面是凸多边形。其每个顶点都在四面体的边上:若交点在四面体内部,截面在其附近包含一个小平面圆盘;若交点在面的内部,便可在该面内穿过它取一小段水平线段。因此两者均非极点。反过来,被截边上的交点是截面极点:若它是两个四面体内点的真凸组合,由于重心坐标非负,而该交点在另外两个顶点的重心坐标为零,两点的这两个坐标都必须为零。故两点都在该边上;水平平面与该边只有一个交点,两点必须都等于该交点。沿边作仿射插值时,端点异号恰有上式给出的唯一交点,同号则没有。一对三的符号分组给三条被截边,二对二给四条;每个被截面恰给一条边界线段,因此循环连接便得到整个多边形。凸四边形的一条对角线把它分成两个闭三角形而不改变并集。
在共同面上,两个仿射限制在三个顶点一致,故在整个面一致。共同水平集不是空集,就是同一条线段,端点的全局被截边键也相同。重用索引使端点完全一致,每个单元都把此线段输出为截面边界。对有限个单元取并,得到恰好 ,且单元之间没有几何裂缝。
证明透视
证明每一步用了哪项假设
不妨把证明看作一张假设清单,逐项看每个假设用在哪里。第一,没有顶点值等于 。因此每个符号都是严格的,每条被截边的分母不为零且 ,单元的截面也不会含有该单元的顶点;若有顶点的值恰为 ,截面可能是一个点、一条边或整个面,用被截边来描述截面就会失效。第二,唯一不显然的一步是极点论证:它把单元内的几何集合 化为一份有限的名单,即被截边上的交点,于是整个构造变成一张符号表加上每条边一个公式。第三,复形的相容性与全局边键只在第二段用到:两个单元在共同面上一致,是因为两个仿射限制在三个顶点处相等,而共用的边键让它们指向相同的端点。证明中任何地方都没有用到梯度或流形性质。第四,论证靠有限性收尾:有限个闭多边形的并集,相邻的多边形沿相同的线段相接。它证明各片能够拼合,但并没有证明结果是封闭曲面。
定理 13.1.5
(时间与内存)
在以上假设下,若全局边查找的期望时间为常数,算法的期望时间是 ;内存用量相对于这些数目及输出大小也是线性。以排序代替哈希时,时间可保证为 ,其中 分别是四面体、边和顶点数目。
证明
(逐个单元统计工作量)
每个单元只检查固定数目的顶点、边和面,并最多输出两个三角形;全局扫描找出 ,便得到上述哈希或排序的成本。哈希的期望时间依赖适当实现;排序则提供所述最坏情况比较界。
上述结果不要求复形本身是三维流形,也没有声称提取的曲面封闭。截面可以到达域的边界,非流形复形也可以产生非流形截面。因此,共同面一致本身不能证明所得集合是封闭二维流形;要断言流形性或封闭性,须另加假设并作局部分析。
算例
例题 13.1.6
(单个四面体和顶点并列的影响)
令 、、、 的值依次为 ,指定 。这里 ,取 。相对 而言, 为正侧, 为负侧。沿各面循环排列的四个交点为
例如从 往 的插值参数为 。任取对角线所得的三角形并集都是平面 上同一四边形。原水平值 的截面则包含 ,形状与此不同;即使算术精确,位移仍是一项可见的建模选择。
例题 13.1.7
(共用一个面的两个四面体)
令 、、、、。四面体 、 共用面 。取 、、、、,指定 ;规则给出 。两个单元都用 和 ,其多边形都接在两点之间同一条线段上。 的第三个交点是 ,截面为三角形。 的其余交点是 和 ;四点构成四边形。其内部对角线不会改变面 上的共同线段。相接源于共同面和共同场值,无须假设两单元梯度相同。
例题 13.1.8
(平坦面旁的被截单元(边界情形))
取 、、、、,取值 、、,指定 。这时 ,按 规则得 。在 中只有 高于 ,所以被截边是 、、,参数都是 ,输出的三角形顶点为 、、。这是正确的,因为在 上 ,该三角形位于平面 内。在 中四个值都低于 ,不输出任何图元。共同面 上 ,所以它整体属于原水平集 ,却不含 的任何点:两个单元平凡地一致,没有裂缝,而输出的三角形停在平坦面上方高度 处。
反例模式
并列可以隐藏非流形水平集
命题:若区域是流形,且相邻单元在共用面上完全一致,则每个精确水平集 都是分片线性二维流形。在原点附近的立方体上取 ,并用尊重平面 和 的相容四面体剖分。此函数在每个单元上仿射,而其零水平集是立方体内的两个平面 和 。在共同的 轴上有四个半片相接。以轴上一点为中心的小球面与这些半片相交成四条连接南、北极的弧;此链环图的每个极点度数均为四。分片线性二维流形内点的链环必须是一个圆,而此图不是圆。因此原水平集沿该轴不是分片线性二维流形,尽管立方体本身是流形,且相邻单元完全一致。正的非顶点水平位移会改变这个交叉,并非修复原集合的拓扑。共同面一致和数值相等不能证明顶点水平值处的流形性质。
另一种歧义出现在相邻立方体以不同对角线分割共用正方面时:所得四面体不是相容复形。若角点高低交替,两种分片仿射面重建可以把交点连成不同方式。相同角点样本本身不会选定对角线或插值方法。应先决定全局相容剖分再提取;改变剖分也可能改变重建的场。
常见错误
常见错误
(从错误的端点度量交点参数)
对第一个算例中的边 , 是从 量起的,得交点 。若在同一公式 中误用从 量起的参数 ,就会得到 ,而该点处 。应当随时检查插值点是否满足 。
常见错误
(把输出当成水平值 的水平集)
若某个四面体的四个顶点值都等于 ,精确水平集 含有整个单元,而取 的算法在那里什么也不输出。输出描述的是所记录的 对应的 ;当顶点值与 相等时,它并不是水平值 的水平集。
常见错误
(期望得到封闭曲面)
单个四面体的值为 ,在 处得到一个四边形,它的四条边落在单元的四个面上。只要截面碰到 的边界,提取出的曲面就有边界;共同面一致与曲面是否封闭无关。
练习
快速检查
(四面体的顶点值为 ,指定水平值为零。按确定的 规则处理。共有几条被截边?从值为二的顶点出发,各边的插值参数是多少?)
先求出 和 。
解答 · 答案
这里 ,。只有值为二的顶点在 之上,与它相连的三条边都被截。从该顶点出发,到两个零值端点的参数都是 ,到负二端点的参数是 。截面是三角形。两个与 相等的顶点由全局位移放到了同一侧。
快速检查
(在相邻单元的例子中验算 ,并说明两个单元在 上的梯度是否必须相同。)
对边 用交点公式。
解答 · 答案
从 到 ,,所以 ;对应的 交点为 。两个函数在 上的限制相同,但穿过该面的法向导数可以不同,所以完整的梯度不必相同。
快速检查
(所有顶点值和指定水平值都是五。原水平集与位移后的水平集各含有什么?算法为什么会终止?)
利用没有顶点值异于 时 的取法。
解答 · 答案
每个单元上的插值恒等于五,所以原水平集是整个区域。规则取 ,,不输出任何图元,位移后的水平集为空。单元个数有限,每个单元只需有限次比较,因此即使原水平集是三维的,算法仍会终止。
快速检查
(有限四面体复形有 个单元,所有顶点值都不等于 。给出输出三角形个数的上界;曲面一定封闭吗?)
数一数一个单元最多贡献几个三角形。
解答 · 答案
至多 ,因为每个单元最多产生一个四边形,再分成两个三角形。水平集可能碰到区域边界,而区域本身也不一定是流形;这个个数上界既不保证封闭,也不保证流形性。