顯隱式幾何模型混合運動邊界追蹤方法

段忠祥 楊欽

（北京航空航天大學計算機學院 北京市 100191）

1 引言

在計算機動畫，流體運動模擬，醫學圖像分割等領域，經常涉及幾何實體邊界面的運動變形與追蹤問題。目前，常用的幾何模型運動邊界面追蹤方法分為歐拉型方法（Eulerian Methods）和拉格朗日型方法（Lagrangian Methods）[1]。拉格朗日方法一般針對顯式網格方式描述的實體，通過推動網格頂點移動從而帶動整個網格變化的策略描述物體的運動變形過程。顯式網格可直接用于運動實體可視化，然而隨著時間累積，網格單元的質量和尺寸會慢慢惡化，并且出現難以處理的拓撲沖突問題[2]。通常情況下，歐拉型方法在實體變形過程中網格保持不變，通過更新網格頂點存儲的隱函數值描述新時刻物體的幾何外形。相較于推動顯式網格運動，歐拉型方法能夠自然適應實體運動變形過程中出現的分裂，合并，侵入等拓撲變化現象[3]。

本文根據歐拉型方法和拉格朗日方法的特性，提出一種顯式幾何模型和隱式幾何模型相結合的實體變形和運動邊界面追蹤方法。在實體變形的每一步，根據顯式四面體網格頂點處的位移或速度移動網格，隨后在規則背景網格上重建變形后幾何邊界的局部符號距離場。對隱式幾何模型等值面調用Delaunay 三角化算法重新生成顯式四面體網格支撐后續運動變形過程。實體顯式表達和隱式表達相結合的運動邊界面追蹤方法結合了顯式幾何模型和隱式幾何模型各自優點，可在實體變形過程中維持質量和尺度優良的不規則網格以方便可視化，同時適應幾何外形拓撲變化，在運動實體仿真模擬相關領域具有重要研究價值。

2 隱式幾何模型與符號距離場

通常隱式幾何模型隱函數選取符號距離函數[4]，此時

其中Ω 和Ω*表示實體的內部和外部，為實體邊界。為點到的最短距離，也即

離散水平集隱式幾何模型是目前工程計算中典型的隱式幾何模型。由于其能夠表達更任意的形狀并方便運動界面追蹤，被廣泛應用于醫學圖像分割，流體運動模擬，結構優化設計等領域[5-7]。如圖1 所示，假設笛卡爾網格D 在X，Y，Z 三個方向的頂點數目為m，n 和l，可以為網格的各個頂點和單元編號

3 顯式與隱式表達相結合的運動邊界面追蹤過程

如圖2 所示，本文提出的運動界面追蹤方法參考實體外形隱式和顯式表達各自特點。在每個時間步長內，其主要包括網格運動變形，實體邊界局部符號距離場構建，隱式幾何模型Delaunay 三角化三個過程。其中實體邊界符號距離場構建生成表達實體變形后區域的隱式幾何模型，針對隱式幾何模型的Delaunay 三角化生成新的四面體網格顯式表達物體內部區域并作為下一時間步長實體繼續運動的輸入條件。

3.1 網格運動變形

在本文中，只有有向面積為正的四面體稱為合法四面體。在實體變形第i 時刻起始以四面體網格Ti表達當前物體區域Ωi，其表面三角網格Fi描述實體邊界。最初網格Ti中所有單元都為合法四面體。根據Ti各個頂點處位移或速度可推動頂點運動變形產生新的四面體網格T*i，記表面網格Fi頂點移動產生的三角網格為。變形后幾何實體的內部區域以中所有合法四面體并集表示，也即

3.2 邊界局部符號距離場構建算法

由于實體運動過程中可能發生分裂，合并，侵入等拓撲沖突，三角網格經常無法有效表達實體表面。本小節根據T*i 中所有合法四面體以及三角網格保留的幾何信息，借助隱式幾何建模思想，在背景笛卡爾網格上重建實體邊界附近的局部符號距離場重新捕捉實體邊界及其內部區域。實體邊界局部符號距離場構建過程如算法LocalSignedDistanceGen 所示。

M=LocalSignedDistanceGen(T*i,F*i,m,n,l)

1.計算網格區域T*i 包圍盒B。根據包圍盒B 創建大小為m×n×l 的笛卡爾網格D。對于D 中任意頂點pi,j,k，設置標量標記其隱函數值為+∞以創建水平集隱式幾何模型M。

4.返回隱式幾何模型M。

算法LocalSignedDistanceGen 首先根據參數m,n,l 創建模型空間覆蓋網格區域T*i的水平集隱式幾何模型M，隨后判斷各個笛卡爾網格頂點是否位于實體內或實體外。在最初，假設所有笛卡爾網格頂點都在實體外無窮遠處，也即，對任意頂點標記其隱函數值遍歷所有合法四面體，對于合法四面體內部的頂點，重新設置其隱函數值為-∞以聲明其位于實體內部。

如圖3 所示，對于任意單元，若其同時包含隱函數值為-∞和+∞的頂點，則一定有隱式邊界穿過單元c 的內部，此時稱單元c 為邊界單元（圖3 中以黃色單元標示）。為了能夠通過邊界單元集合準確表達實體邊界，在算法LocalSignedDistanceGen 后續步驟中，需要遍歷三角網格F*i中的所有三角形，不斷更新三角網格附近頂點的隱函數值使其接近頂點到實體邊界的符號距離值。假設頂點pi,j,k到任意三角形單元的距離為Lp，若其原隱函數值滿足則重新設置頂點p 隱函數值為

其中為δ 符號函數，滿足

隱式幾何模型M 中所有邊界單元頂點及其附屬隱函數值構成的局部符號距離場即可隱式描述實體變形后邊界。

3.3 隱式幾何模型Delaunay三角化

如果四面體網格T 所有單元外接球內不包含其它的頂點，則稱T 滿足Delaunay 特性或空圓（球）特性[8]。采用一定策略，生成滿足Delaunay 特性的網格，也稱為區域的Delaunay 三角化。目前，針對光滑曲面限定條件的Delaunay 三角化技術發展較為成熟。Boissonnat 和 Oudo[9,10]根據拓撲閉球屬性原理[11]，提出針對光滑曲面的Delaunay 細化算法，其生成的Delaunay 三角網格能夠在理論上保證與光滑外形幾何實體同胚。Dey 與Levine[12]提出針對光滑等值面的Delaunay 三角化算法，能夠針對隱式幾何模型的等值面生成拓撲一致，質量和尺寸過渡性良好的三角網格。本文提出的顯隱式幾何模型混合運動邊界追蹤方法在第三步調用現有成熟限定Delaunay 三角化算法庫[13]，以隱式幾何模型M 中的零等值面為限定條件對隱式表達實體區域進行四面體網格劃分生成新的顯式網格表達模型實體。

4 變形實例

在Intel core i7-4790K,NVIDIA GeForce GTX970，16G 內存，win 7 X64 位系統平臺上實現了實體幾何大變形示例。實體運動變形效果如圖4(a)～(f)所示。在實體變形過程中每一時間步長內，初始四面體表面網格頂點向目標實體表面最近點移動，采用分辨率為133×193×103 的笛卡爾網格構建邊界符號距離場，最終迭代16 步后變形實體基本接近目標實體幾何形狀。實體大變形實例證明了顯隱式幾何模型相結合的實體邊界面追蹤方法對拓撲變化和大尺度幾何變形過程具有良好適應性。

5 總結

在表達實體的顯式網格運動變形時，實體的幾何外形可能發生分裂，合并，侵入等現象。原實體邊界可能運動到實體內部，實體內部區域也可能變化為邊界導致顯式網格不合法。本文采取將不合法顯式網格向隱式幾何模型轉化然后再重新對隱式表達區域限定Delaunay 三角化的方式對變形后的網格進行重構。恢復合法性的顯式網格可以繼續推動頂點移動以支撐后續實體運動變形過程。針對變形后顯式網格建立隱式幾何模型并構建邊界附近局部符號距離場是每一個時間步長內運動邊界面追蹤實現的關鍵。顯隱式幾何模型混合運動邊界面追蹤方法綜合了歐拉型方法和拉格朗日方法的優勢，通過實體隱式顯式表達相互轉換解決網格變形拓撲沖突問題，在科學和工程計算相關領域具有一定應用潛力。