常用的有限元網格生成方法（下）
上期的《常用的有限元網格生成方法（上）》為大家介紹了映射法（Mapping）和四（八）叉樹法（Quadtree/Octree）。本期我們繼續(xù)發(fā)放“干貨”，為大家?guī)鞤elaunay三角化法（Delaunay Triangulation）和前沿推進法(Advancing Front Technique)這兩種有限元網格生成方法。
03 Delaunay三角化法(Delaunay Triangulation)
談到Delaunay三角化的來歷，就不得不先提它的對偶圖——Voronoi圖。1908年，俄國數學家Voronoi提出：給定平面內點集Q，對于其中每個點p，存在一個區(qū)域，該區(qū)域內的任意一點與p的距離是與Q中所有點距離的最小值，這些區(qū)域的合集構成Q的Voronoi圖。1934年Delaunay提出，通過連接Voronoi圖相鄰區(qū)域的點，可以得到一個平面點集的三角化，這樣的三角化就稱作該點集的Delaunay Triangulation，簡稱DT。
給定一個平面點集Q，其DT有以下特性：
唯一性：在不考慮四點共圓的情況下，DT是唯一的；
最大化最小角：在Q的所有三角化中，DT使最小角達到最大；
空圓特性：DT中每個三角形單元的外接圓都不包含其它節(jié)點，此特性也稱為DT條件，可用于判斷三角化是否為DT，如下圖所示。此外，通過簡單的邊翻轉（BD->AC）可將局部非DT轉化為DT。
也就是說，DT避免了生成小內角的長薄單元，盡可能地將所有三角形趨向均勻。鑒于其良好的特性，到了上世紀80年代，DT開始大量應用于有限元的網格生成，出現了許多DT的生成算法，最常見的當屬Bowyer-Watson算法。Bowyer-Watson算法采用逐點插入法，每次插入新點后，都要保證當前的三角化符合DT條件。此外，點集的插入順序是影響生成算法效率的重要因素，一般采用隨機次序插入。Bowyer-Watson算法的主要步驟如下：
插入一個新點，在已生成的三角形中找出所有外接圓包含插入點的三角形，得到影響區(qū)域多邊形；
刪除多邊形的內部邊，連接插入點與多邊形的全部頂點，連接前需要進行可見性檢查。
DT生成算法對凸區(qū)域十分有效，然而待剖分區(qū)域很有可能在局部是凹的，凹區(qū)域采用DT方法生成的網格不能保證邊界的完整性，需要進行邊界恢復。對二維而言，可以通過簡單的邊翻轉操作恢復邊界。若AB是丟失的邊界，循環(huán)多邊形的每對相鄰三角形構成的四邊形進行邊翻轉判斷，確保四邊形的對角線不會穿過AB，直至多邊形內的所有三角形都不穿過AB即可。
綜上，二維的Delaunay三角化法的基本步驟如下：
得到待剖分區(qū)域的點集，包括邊界節(jié)點和內部節(jié)點；
將點集中的點生成一個隨機插入次序；
創(chuàng)建一個能包含點集凸包的三角形或正方形；
Bowyer-Watson算法，確保每一步都滿足DT條件；
通過拓撲操作恢復邊界。
Delaunay三角化在由二維推廣至三維的時候卻遇到了一些問題。首先，三維Delaunay三角化會產生四個節(jié)點幾乎共面的薄元，薄元的單元質量很差卻能符合三維的DT條件。此外，三維的邊界恢復不能直接由二維推廣，需要分別針對邊界邊和邊界面進行處理。不過隨著研究的深入，這些問題目前都已經有了較好的解決辦法。
04 前沿推進法 (Advancing Front Technique)
前沿推進法也叫波前法，由Lo和Lohner提出，是一種基于邊界的全自動非結構化網格生成方法。顧名思義，該方法將區(qū)域邊界作為初始波前，根據一定規(guī)則向區(qū)域內部推進，推進的過程中進行網格生成，當所有波前在區(qū)域內部聚合消失，網格生成完畢。與Delaunay三角化法具有成熟的理論依據不同，前沿推進法的推進規(guī)則在很多情形下是依靠經驗制定的，但這并不妨礙它的成功應用。前沿推進法的算法時間復雜度與四（八）叉樹法和Delaunay三角化法相當，并且生成的網格在邊界處有更好的質量。
以二維為例，前沿推進法的基本步驟如下：
將待剖分區(qū)域邊界離散化，得到一組線段集合，即初始前沿；
根據前沿各線段的位置關系和推進規(guī)則生成新節(jié)點，并與前沿線段連接得到新的單元，并更新前沿中的線段；
重復步驟2，直至前沿為空，剖分完成。
前沿推進法的優(yōu)勢在于新節(jié)點和新單元同時生成，便于利用已存在的單元控制后續(xù)生成的節(jié)點位置，以達到質量控制、局部加密或網格過渡的要求。此外，從邊界向內推進，能夠優(yōu)先保證邊界附近的單元質量。
不過，前沿數據結構的設計一直是此方法的難點。一方面要考慮推進規(guī)則的完整性；另一方面，在生成新單元時要進行大量的相交判斷、距離判斷，需要盡可能減少執(zhí)行判斷的次數以提升剖分效率。
就算法的時間復雜度而言，四（八）叉樹、Delaunay三角化法和前沿推進法這三種全自動的非結構化網格生成方法計算效率都為O(nlogn)，難分伯仲。但實際上各種網格生成方法都有各自的優(yōu)勢和局限性，在實際的網格生成算法中，往往需要將多種方法組合運用，揚長避短，以達到更好的剖分效果。
圖片出處
[1] S.H. Lo, Finite Element Mesh Generation, CRC PressTaylor & Francis USA, 2015
[2] PJ Frey, L Marechal, Fast Adaptive Quadtree MeshGeneration, 7th International Meshing Roundtable, 1998
自主通用多物理場耦合仿真平臺Simdroid試用：
Simdroid 是云道智造自主研發(fā)的通用多物理場仿真平臺，具備自主可控的隱式結構、顯式動力學、流體、熱、低頻電磁、高頻電磁、多體動力學等通用求解器，支持多物理場耦合仿真。在統一友好的環(huán)境中為仿真工作者提供前處理、求解分析和后處理工具。同時，作為仿真PaaS平臺，其內置的APP開發(fā)器支持用戶以無代碼化的方式便捷封裝參數化仿真模型及仿真流程，將仿真知識、專家經驗轉化為可復用的仿真APP。歡迎使用Simdroid通用仿真平臺定制開發(fā)行業(yè)專用軟件。下載試用：https://www.simapps.com/v2/tool/simdroid
