三角形網格演算法

① 三角曲面求交的網格法

6.1.3.1 網格法的基本原理

由於三角曲面求交運算最終是三角形之間的求交運算，因此，我們在不能漏掉任何可能相交的三角形對的同時，要盡量排除不可能相交的三角形對。網格法的目的就是尋找可能相交的三角形對。該方法先將曲麵包圍盒的相交區域劃分成規則六面體格網，先找到與每個網格單元相交的三角形，再將每個單元內分別來自兩張曲面的三角形組成可能相交三角形對，再對可能相交三角形對進行求交運算。網格法的基本過程為:

(1)先在合適的坐標系下分別構造出兩張三角曲面的矩形包圍盒，求出兩個包圍盒的交作為新的包圍盒;

(2)然後將新包圍盒劃分成由若干規則六面體組成的格網;

(3)針對每個網格，分別從兩張曲面中找到與其相交的所有三角形，並組成可能相交的三角形對;

(4)對所有網格中的三角形對進行整理，刪除重復三角形對;

(5)對所有三角形對進行求交運算，計算出交線段;

(6)進行交線追蹤，獲得曲面交線。

6.1.3.2 格網的構建

為了方便，常常將兩張曲面的包圍盒的相交區域劃分成等尺寸的規則六面體格網。這樣，僅僅根據坐標就可以很方便地確定每個結點位於哪個網格內。

顯然，不與任何一個相同網格相交的兩個三角形是不可能相交的。網格法可以排除很多不相交的三角形對，也不會漏掉任何相交的三角形對。網格的大小是影響計算效率的關鍵。如果網格單元尺度太大，則會得到更多的可能相交三角形對，降低了不相交三角形對的排除效率;如果網格單元尺度太小，內存就會開銷增大，而且三角形與格網相交計算量也會增大。一般情況下，可以使網格邊長與三角網格的平均邊長相當。

6.1.3.3 三角形與格網的相交判斷

由於曲面上有數量眾多的三角形，如果直接判斷每個三角形與每個網格單元是否相交，則計算效率非常低。下面介紹一種判斷一個三角形與格網相交的方法，演算法思路如下:

(1)在格網所在坐標系下，將三角形與格網分別投影到xoy面上(圖6.3(a))。格網的投影為一個平面格網，而三角形的投影為三角形或一條線段。如果三角形的投影為線段，則選擇xoz或yoz為投影面。為了敘述簡便，這里只介紹在xoy面上的投影為三角形的情況。

(2)計算投影三角形的邊與平面網格線的交點，並計算過每個交點的xoy面的垂線與三角形的交點，將這些交點與三角形的頂點合並組成點集Ω。

(3)利用Ω中的點在xoy面上的投影坐標直接判斷每個點所在的格網單元(包括位於格網單元內部或邊界上)，找到同屬一個格網單元內的點組成子集(一個點可以位於多個格網單元內)。

(4)針對每個Ω的子集Ф及投影所在的格網單元g(圖6.4(b))，將原三維格網中平面投影為g的所有格網單元組成列G。找到子集Φ中點的最小與最大z坐標，從最小到最大z坐標所跨越的G中的網格單元即為與該三角形有相交的格網單元。

(5)刪除由上述方法所得的重復記錄的格網單元，就可得到與該三角形相交的所有格網單元。

圖6.4 三角形與格網求交示意

6.1.3.4 網格法曲面求交演算法

網格法三角曲面求交演算法如下:

三維地質建模方法及程序實現

② 推進波前法

經過近年來的發展，推進波前法(Advancing Front Technique，AFT)已經成為通用的全自動非結構化有限元網格生成方法之一。該方法最初由Lo提出並用於平面區域三角形網格自動生成(Lo，1985)。AFT方法具有生成的邊界網格質量高、易於自適應加密等優點，但不同於Delaunay三角剖分演算法，它沒有後者那樣成熟的理論依據，在很多情形下靠經驗解決問題，但是這並不妨礙它的成功應用。

推進波前法的基本思路是:按照剖分規模將邊界離散成有序線段，然後從邊界出發，依次以邊界線段為三角形的一條邊，在邊界點與內部點中尋找合適點，組成三角形，選取組成三角形頂角最大的點為最終三角形頂點;將已形成三角形的邊界線段從邊界鏈表中刪除，形成新邊界;重復上述過程直到除邊界外的三角形的邊兩側均有三角形為止。為了更好地說明該演算法，下面先介紹幾個術語。

3.3.1.1 二維AFT方法術語定義

(1)剖分域:即需要剖分的區域。正確地定義剖分域(區域的幾何描述)是網格能夠正常生成的必要條件。剖分域是由一系列有向邊界曲線圍成的連通域，並且每條邊界曲線必須是簡單封閉曲線。通常情況下，剖分域的外邊界按照逆時針排列，而內邊界則按照順時針排列。

(2)前沿Ω:所有未剖分區域的邊界線段以及端點的集合構成Ω，前沿包括活躍前沿(記為Ω₁)和非活躍前沿(記為Ω₂)，其中活躍前沿為當前正在推進的前沿，非活躍前沿為暫時不推進的前沿。

(3)選定前沿S:選定前沿S是Ω中的一個元素。S的選取取決於網格的生成策略，如果為了保證生成網格的尺寸過渡以及保證小尺寸單元優先生成，一般選取Ω中的最小前沿作為S。如果為了程序實現上的便利，則從Ω中從前往後依次選定一個元素作為選定前沿S。

3.3.1.2 演算法要點

(1)選取合適的數據結構建立點、邊、三角形之間的關系，並建立儲存點、邊與三角形的鏈表。

(2)選取合適的驅動方式。如以三角形的邊為基礎進行波陣式擴展，必須考慮邊的使用次數與方向:任何位於區域邊界上的邊應且只應使用1次，任何位於區域內部的邊應且只應使用2次(正、反方向各1次)。因此，在初始狀態，應將邊界邊的使用次數賦1，內部邊使用次數賦0。

(3)以邊為基礎進行波陣式擴展，是以某邊為三角形的一條邊，再從點集中尋找合適的頂點組成三角形的過程。所尋找到的點必須滿足以下要求:新形成邊與已生成的邊不能相交;所有邊必須滿足使用次數要求(邊界邊使用一次，其餘邊使用兩次);新頂點與該邊(有方向)組成的三角形面積必須大於零;保證頂角最大。

3.3.1.3 演算法與程序代碼

平面區域的AFT方法主要有三大步:向剖分域中布點、離散剖分域的邊界和推進前沿生成三角形。

3.3.1.3.1 布點

布點即是根據需要得到的三角形單元的各邊的大概長度，在剖分域內生成一系列的散亂點。最常用的方法是先根據剖分域邊界上端點的x和y坐標的最大值和最小值，生成一個包含剖分域的矩形，該矩形也叫做剖分域的包圍盒;再在矩形中生成點，最簡單的是生成「棋盤狀」的一系列點，另外是生成「正三角形狀」的一系列點;生成一系列點之後，判斷這些點是否落在區域內，若是，則為需要布設的數據點，否則，刪除;同時需要注意的是若某些點落在了區域內，但是又距離邊界太近，依舊刪除這些點。圖3.9中(a)為剖分域，(b)則是布設「正三角形狀」點的結果。

圖3.9 在平面區域中布點

3.3.1.3.2 離散邊界

離散邊界即是按照剖分規模或需要得到的三角形單元的各邊的大概長度將邊界離散成有序線段，如圖3.10所示，為布點之後進行離散邊界的結果。

圖3.10 離散邊界

3.3.1.3.3 生成三角形

以三角形的邊為基礎進行波陣式擴展生成三角形，即以三角形的邊為推進前沿，主要過程有如下4小步。

第一步:建立點集PS和邊集ES。初始點集PS包括所有布設的數據點和邊界離散後小線段的端點。初始邊集ES只包括邊界離散後的有向線段。此時，邊集ES就是前沿Ω。

第二步:以邊集ES中的邊E_i為基礎搜索頂點P_i，即選定E_i作為選定前沿S，以該點為頂點、該邊為一邊形成三角形。設E_i的端點為A與B，所有待選點P_i與E_i組成的頂角為∠AP_iB，將頂角從大到小排序，從最大頂角開始，依次選擇對應的頂點P_i與E_i組成三角形。如果形成的三角形滿足以下要求，則為新三角形，P_i為合適的頂點:①新形成三角形的邊與已生成的邊不能相交;②所有邊必須滿足使用次數要求;③新頂點與該邊(有方向)組成的三角形面積必須大於零。如果不滿足則選下一個頂點。

第三步:找到合適頂點後，將新頂點與選定前沿S(即邊E_i)的端點連成的邊加入到邊集中，生成新的前沿Ω的元素，並將新形成的三角形加入到三角形集中，刪除原選定前沿S，選定邊集ES中的下一條邊作為選定前沿S。

第四步:重復第二、三步，當所有邊滿足使用次數要求時循環結束。圖3.11中，(a)、(b)和(c)依次為循環一步、二步和多步之後形成的三角形，當循環結束時得到的三角剖分如圖3.12所示。

圖3.11 推進前沿過程

三維地質建模方法及程序實現

函數CreateTrgls()中調用的函數SearchID()搜索某一點在頂點集合surf-＞pNodes的ID;函數CountCos()用於計算當一條線段/邊搜索到一頂點並組成三角形時該頂點處角度的餘弦值;函數SameLine()用於判斷兩條線段/邊是否相同。

3.3.1.4 約束的處理

區域三角剖分中的約束是指待剖分區域中存在特定的點或線，稱為點約束或線約束，其中約束點必須是剖分後網格的頂點，而約束線必須是剖分後網格三角形的邊的集合，不存在某個三角形跨越約束線的狀況。

3.3.1.4.1 點約束的處理方法

點約束的處理非常簡單，直接將約束點加入到生成的點集中，再刪除與約束點距離非常近的點，然後就可以按無約束的方法進行三角剖分了。

3.3.1.4.2 線約束的處理方法

當待剖分區域存在線約束時，可以將所有線約束作為一種邊界。在剖分前，與外邊界及內邊界的處理方法一樣，先按照一定的規模將約束線離散成順序連接的線段，每條線段均作為三角網格的邊，然後設置約束線上的邊的使用次數為0，並加入到原始邊集中，再按照按無約束的方法進行三角剖分即可完成約束三角剖分。圖3.13(a)為含線約束的待剖分區域，圖3.13(b)為約束剖分網格。

圖3.13 約束三角剖分實例