為甚麼要處理平手
四面體插值已經指定每個單元內各點的純量值。要顯示水平集,還須用算法產生多邊形,並令相鄰單元在邊界相接。上一節證明了非退化截面的形狀;本節提供有限的具體方法,並規定節點值剛好等於指定水平值時的決定。平手規則會改變所計算的數學物件,應與網格一同記錄,不能藏在浮點比較的細節裏。
設定與全域水平值規則
定義 13.1.1
(帶頂點數據的相容四面體複形)
設 是 中有限的相容幾何四面體複形:每個四面體非退化,任兩個單形的交集為空或其共同面。每個頂點 都有全域共用位置 和純量值 。每個四面體上, 是四個節點值的仿射插值;相鄰仿射函數在共同面的三個頂點相等,因此在整個面上相等。域為四面體的並集 。
暫不假設它是流形,也不假設邊界封閉。以下視輸入和計算為精確實數;浮點誤差及可靠比較須另行處理。
定義 13.1.2
(全域水平值位移)
指定水平值 後,對整個網格選擇同一個正數 。若有頂點滿足 ,定義
若全部頂點值等於 ,任取 。令 。例如可約定: 存在時取 ,否則取 ,單位與 相同。只要記錄所選數值並符合條件,其他選擇亦可。原本等於 的頂點都嚴格低於 ;原本嚴格高於或低於 的頂點保持原來的一側。沒有頂點值等於 。這是全域水平值位移,不是各單元獨立打破平手,也不是改動節點值。
輸出代表 ,不一定是 。若四面體的四個頂點值皆為 ,則整個四面體屬於 ,但其中沒有 。即使 ,這個單側曲面也未必找回孤立點、平坦單元或 的每一部分。另一位移幅度或向下位移可以得到不同曲面。若應用必須精確表示退化的原水平集,便要表示不同維數的部分,或另訂並說明規則;本算法不聲稱做到這件事。
構造
定義 13.1.3
(被截邊與邊鍵)
若 與 異號,邊 稱為被截邊。它的邊鍵是兩個唯一頂點編號的配對 ,並按排序後儲存,使兩種端點次序指向同一條邊。
把每個頂點依 分成正、負兩側。對每條端點異號的邊 ,用全域邊識別鍵 只計算一次
分母非零,且 。以邊鍵儲存該點;交換端點次序得到相同位置。每個四面體依下列步驟處理:
- 若四個頂點符號相同,不輸出圖元。
- 否則收集三個或四個被截邊上的點。四面體每個面有零條或兩條被截邊;若有兩條,就連接該面上的兩個交點。這些線段依循環次序構成截面多邊形的邊界。三個頂點時輸出三角形;四個頂點時沿任一對角線分成兩個三角形,例如取經排序後,其兩端全域邊鍵之配對字典序較小者。若需要指向場值增加方向的法線,令三角形方向與 一致。被截單元的梯度不可能為零。
- 共同邊重用相同交點索引。四邊形的對角線位於各自四面體內部,不改變共同面上的線段;相鄰單元毋須選同一對角線。
全域邊鍵是兩個唯一頂點編號排序後的配對;對角線兩端的邊鍵也先排序再按字典序比較。固定編號和 後,三角化便可重現。精確算術定義了上述數學輸出。浮點實作中,即使兩次使用相同公式也不能據此證明結果相等;共用儲存可避免分別捨入的副本,但側別判定和輸入表示仍須有可靠規則。
概念視角組合
把單元看成正負號型態
對一個單元來說,只有四個 的正負號向量有影響。十六種型態中,兩種全同號而不輸出;八種是一個頂點與其餘三個異側(一比三),給出三角形;六種是二比二,給出四邊形。由於 ,整個算法就是一張十六項的表,加上每條被截邊一條插值公式。
定理 13.1.4
(精確截面與共同面一致性)
在以上假設下,所有輸出的閉三角形之並集恰好是 。在每個共用三角面上,兩個相鄰四面體給出相同截面,包括端點和線段。
證明
(截面頂點在被截邊上,共同面一致)
在一個四面體內,仿射函數值是四個頂點值的凸組合。若所有值都嚴格在 同一側,單元內所有點亦然。否則兩側皆有頂點, 不可能在單元內為常數; 是一個平面與四面體的交,故截面是凸多邊形。其每個頂點都在四面體的邊上:若交點在四面體內部,截面在其附近包含一個小平面圓盤;若交點在面的內部,便可在該面內穿過它取一小段水平線段。因此兩者均非極點。反過來,被截邊上的交點是截面極點:若它是兩個四面體內點的真凸組合,由於重心座標非負,而該交點在另外兩個頂點的重心座標為零,兩點的這兩個座標都必須為零。故兩點都在該邊上;水平平面與該邊只有一個交點,兩點必須都等於該交點。沿邊作仿射插值時,端點異號恰有上式給出的唯一交點,同號則沒有。一對三的符號分組給三條被截邊,二對二給四條;每個被截面恰給一條邊界線段,因此循環連接便得到整個多邊形。凸四邊形的一條對角線把它分成兩個閉三角形而不改變並集。
在共同面上,兩個仿射限制在三個頂點一致,故在整個面一致。共同水平集不是空集,就是同一條線段,端點的全域被截邊鍵也相同。重用索引使端點完全一致,每個單元都把此線段輸出為截面邊界。對有限個單元取並,得到恰好 ,且單元之間沒有幾何裂縫。
證明透視
證明每一步用了哪項假設
把證明當作一張假設清單,看每項假設在哪裏用上。第一,沒有頂點值等於 。因此每個符號都是嚴格的,每條被截邊的分母非零且 ,單元的截面也不會包含該單元的頂點;若有頂點值恰為 ,截面可以是一點、一條邊或整個面,以被截邊描述截面便會失效。第二,唯一不顯然的一步是極點論證:它把單元內的幾何集合 化成一份有限的名單,即被截邊上的交點,於是整個構造化為一張符號表加每條邊一條公式。第三,複形的相容性與全域邊鍵只在第二段使用:兩個單元在共同面上一致,是因為兩個仿射限制在三個頂點相等,而共用的邊鍵使它們指向相同的端點。證明中任何地方都沒有用到梯度或流形性質。第四,論證以有限性收尾:有限個閉多邊形的並集,相鄰多邊形沿相同線段相接。它證明各片能夠接合,卻沒有證明結果是封閉曲面。
定理 13.1.5
(時間與記憶體)
在以上假設下,若全域邊查找的期望時間為常數,算法的期望時間是 ;記憶體用量相對於這些數目及輸出大小也是線性。以排序代替雜湊時,時間可保證為 ,其中 分別是四面體、邊和頂點數目。
證明
(逐個單元計算工作量)
每個單元只檢查固定數目的頂點、邊和面,並最多輸出兩個三角形;全域掃描找出 ,便得到上述雜湊或排序的成本。雜湊的期望時間依賴適當實作;排序則提供所述最壞情況比較界。
上述結果不要求複形本身是三維流形,也沒有聲稱擷取的曲面封閉。截面可以到達域的邊界,非流形複形也可以產生非流形截面。因此,共同面一致本身不能證明所得集合是封閉二維流形;要斷言流形性或封閉性,須另加假設並作局部分析。
算例
例題 13.1.6
(單個四面體和頂點平手的影響)
令 、、、 的值依次為 ,指定 。這裏 ,取 。相對 而言, 為正側, 為負側。沿各面循環排列的四個交點為
例如從 往 的插值參數為 。任取對角線所得的三角形並集都是平面 上同一四邊形。原水平值 的截面則包含 ,形狀與此不同;即使算術精確,位移仍是一項可見的建模選擇。
例題 13.1.7
(共用一個面的兩個四面體)
令 、、、、。四面體 、 共用面 。取 、、、、,指定 ;規則給出 。兩個單元都用 和 ,其多邊形都接在兩點之間同一條線段上。 的第三個交點是 ,截面為三角形。 的其餘交點是 和 ;四點構成四邊形。其內部對角線不會改變面 上的共同線段。相接源於共同面和共同場值,毋須假設兩單元梯度相同。
例題 13.1.8
(平坦面旁的被截單元(邊界情況))
取 、、、、,值為 、、,指定 。此時 , 規則給出 。在 中只有 高於 ,故被截邊為 、、,參數均為 ,輸出的三角形頂點是 、、。這是正確的,因為在 上 ,三角形位於 。在 中四個值都低於 ,不輸出任何圖元。共同面 上 ,所以它整個屬於原水平集 ,卻不含 的任何點:兩個單元平凡地一致,沒有裂縫,而輸出的三角形停在平坦面上方高度 處。
反例模式
平手可以隱藏非流形水平集
命題:若域是流形,且相鄰單元在共用面上完全一致,則每個精確水平集 都是分片線性二維流形。在原點附近的立方體上取 ,並用尊重平面 和 的相容四面體剖分。此函數在每個單元上仿射,而其零水平集是立方體內的兩個平面 和 。在共同的 軸上有四個半片相接。以軸上一點為中心的小球面與這些半片相交成四條連接南、北極的弧;此鏈環圖的每個極點度數均為四。分片線性二維流形內點的鏈環必須是一個圓,而此圖不是圓。因此原水平集沿該軸不是分片線性二維流形,儘管立方體本身是流形,且相鄰單元完全一致。正的非頂點水平位移會改變這個交叉,並非修復原集合的拓撲。共同面一致和數值相等不能證明頂點水平值處的流形性質。
另一種歧義出現在相鄰立方體以不同對角線分割共用正方面時:所得四面體不是相容複形。若角點高低交替,兩種分片仿射面重建可以把交點連成不同方式。相同角點樣本本身不會選定對角線或插值方法。應先決定全域相容剖分再擷取;改變剖分也可能改變重建的場。
常見錯誤
常見錯誤
(從錯誤的端點量度交點參數)
對第一個算例中的邊 , 是從 量起,得交點 。若在同一公式 中誤用從 量起的參數 ,便得 ,而該點的 。應始終檢查插值點是否滿足 。
常見錯誤
(把輸出當作水平值 的水平集)
若某個四面體的四個頂點值全等於 ,精確水平集 包含整個單元,而取 的算法在該處不輸出任何東西。輸出所描述的是所記錄的 對應的 ;當頂點與 平手時,它並不是水平值 的水平集。
常見錯誤
(預期得到封閉曲面)
單個四面體的值為 ,在 得到一個四邊形,其四條邊落在單元的四個面上。只要截面碰到 的邊界,擷取的曲面就有邊界;共同面一致與封閉性無關。
練習
快速檢查
(四面體頂點值為 ,指定水平值為零。用確定的 規則處理。共有多少條被截邊?由值為二的頂點出發,各邊插值參數是多少?)
先求 和 。
解答 · 答案
這裏 ,。只有值為二的頂點在 上方,與它相接的三條邊都被截。從該頂點出發,往兩個零值端點的參數都是 ,往負二端點的參數是 。截面是三角形。兩個平手頂點由全域位移放在同一側。
快速檢查
(在相鄰單元例子中驗算 ,並解釋兩單元在 上的梯度是否必須相同。)
對邊 套用交點公式。
解答 · 答案
從 往 ,,所以 ;對應的 交點為 。兩個函數在 上的限制相同,但跨面的法向導數可以不同,故完整梯度毋須相同。
快速檢查
(所有頂點值和指定水平值均為五。原水平集與位移後水平集各包含甚麼?算法為何終止?)
利用沒有頂點異於 時 的取法。
解答 · 答案
每個單元的插值恆為五,所以原水平集是整個域。規則取 、,不輸出任何圖元,位移後的水平集為空。單元數有限,每個只需有限次比較,因此即使原水平集是三維的,算法仍會終止。
快速檢查
(有限四面體複形有 個單元,所有頂點值均不等於 。給出輸出三角形數量上界;曲面必然封閉嗎?)
數一數一個單元最多貢獻多少個三角形。
解答 · 答案
至多 ,因為每個單元最多產生一個四邊形,再分成兩個三角形。水平集可以接觸域邊界,而域本身亦不一定是流形;數量上界既不保證封閉,也不保證流形性。