面向高端復雜裝備模型的并行網格剖分算法綜述

趙寶臣 朱晨澍 郜超超

(1.河北工業大學理學院,天津 300400;2.河北工業大學計算機與軟件學院,天津 300400)

1 研究背景

隨著科技的發展,在機械工程領域中所應用的裝備更加復雜,傳統的對這些裝備的力學靜、動態分析的軟件CAE運行時間過長,精度無法滿足需求,這直接影響了工業生產的要求。有限元法是常用的方法,而網格剖分是應用有限元法的前提。因此,研究如何快速精準復雜連續體剖分成微小的網格單元,并且在單元上快速求解近似變分方程具有重要意義。

對于該問題的研究國內外已經有了初步的成果,網格生成更多的使用Delaunay網格,以及通過簡化模型來提高結構分析效率。復雜裝備設計的精度和速度問題的解決是多學科團隊積極協作的結果,現有研究已從網格剖分、并行算法優化等角度,證明多學科技術的融合有利于提升結構快速分析的可靠性,提升復雜裝備設計的效率。

2 研究內容

2.1 網格分類

結構化網格、非結構化網格、混合網格和特殊網格是目前網格的四個主要類別。結構化網格生成速度快、質量好、數據結構簡單,但適用范圍窄,有適體坐標法、塊結構化網格等生成方法;非結構化網格多用于復雜流體機械物理模型的網格生成,此網格有利于使用自適應技術,提高計算精度。但有兩個缺點:一是網格填充效率不高,二不能很好地處理粘性問題,生成該網格有Delaunay三角剖分、陣面推進法等方法;混合網格糅合了結構化和非結構化網格的優點,剖分靈活、易于實現網格自適應等;特殊的網格用于處理一些復雜的問題,能得到高質量高精度的網格,通過曲面網格、自適應網格等生成技術可以實現。

2.2 網格劃分算法

2.2.1 實際模型提取

網格劃分是實體模型做網格劃分的前提和基礎,進行曲面網格劃分的第一步就是對實體信息的提取。Open CASCADE (OCC)是常使用的平臺,該軟件提供的數據交換功能,可以直接從實體模型中讀取網格劃分所需要的數據,并使將不同數據存儲格式傳統一化,便于后期讀取與處理。

2.2.2 Delaunay三角剖分

由俄國數學家M.G. Voronoi提出的Voronoi圖,由平面區域中連接兩鄰點的線段的中垂線所形成的區域,實際上就是一種三角剖分。

在許多領域中,Delaunay三角剖分做出的網格相比較其他三角剖分具有很好的數學性質,因而被普遍的使用。在完成一般的三角剖分之后,二維上依照圓準則、最小內角最大準則、Thiessen區域準則等判據,三維上依據空球準則、最小立體角最大化優化準則等準則,通過翻轉等方法可以對其Delaunay化。但是在翻轉操作中有兩種特殊情況,一種是退化情況,一種是不可翻轉情況,此時需要進行修復。其中翻轉有:2-2翻轉、1-3翻轉、3-1翻轉、2-3翻轉、3-2翻轉、4-1翻轉、4-4翻轉等。生成網格的同時,難免會有畸形網格出現,常用的改進網格質量的方法主要有兩類:Laplace光順方法和Delaunay細化算法。

2.2.3 三角剖分算法

以三角形網格的構建過程的為依據將算法分為生長法,逐點插入法,和分治算法。

生長法在第三點的尋找上花費時間最大,因此,相應的實現算法差別主要表現在“第三點”的搜尋策略上。

逐點插入法中的各種算法的區別在于初始多邊形構建所采用的方法,如何搜索定位三角形和三角形重構的方法。

分治算法的各種實現算法的不同在于點集劃分的標準,子三角網生成采用的算法以及各子三角網合并的方法。

由于生長法需要在搜索第三點上消耗很長的時間,現在已經很少使用。逐點插入算法和分治算法是現在流行的兩類算法,前者實現難度較小,所需內存較小,但相比較分治算法,時間復雜度較高。由于大量的遞歸調用是分治算法的一個較為明顯的特點,因此會占用較大內存空間,對大數據集剖分時要求較高。有學者給出了合成算法,在分治算法中糅合了逐點插入算法,集中體現了兩種不同的算法的優勢。

2.2.4 并行化

目前的并行模式主要有三種:

適用于內存共享的多線程編程模型:如OpenMP并行模式、GPU并行模式;

適用于分布內存的消息傳遞編程模型:如常用的PVM和MPI;

混合編程模型:如許彥芹等人首次提出了一種基于SMP集群的MPI+CUDA并行模式,劉青昆等人提出來的基于OpenMP, MPI,CUDA混合并行編程模型。

并行算法設計是算法理論和計算機并行體系相結合的結果,并行網格生成的兩種主流方法為數據并行和任務并行。數據并行是將數據域劃分為有限個區域,并將每個區域映射到一個相應的處理器上,調用算法生成有限個網格;任務并行是在不同粒度層級上將算法運行所需要的時間和運行環境并行化,再利用并行開發工具設計新算法來完成并行網格的生成。前者反復使用已有的網格生成算法,實現較為容易,因此成為并行網格生成算法研究和開發的主流。對于并行網格生成算法的優劣性,Chrisochoides給出了三個評價標準:穩定性,復用性,可擴展性。基于任務并行的并行Delaunay方法主要是構建在并行Bowyer-Watson內核之上;基于數據并行模式的并行Delaunay方法有基于分割平面的并行,基于PDT理論的并行,基于稀疏網格的并行等方法,它們的主要區別是其所采用的數據分解方式不同。

2.2.5 修復

邊界邊、邊界面是否一致是網格生成后依然會存在的問題,網格生成過程中不可避免的會有Sliver單元出現,如何消除是另外一個重要的問題。保證剖分前后的模型邊界一致是一個準確的算法應該具有的結果。然而,因為僅僅考慮了點與點之間的連接狀況,Delaunay剖分算法無法解決邊界邊與邊界面的存在問題,只能確保該點在三角化中依然存在?；謴退惴ㄖ饕腥N:CDA、ADA和CDT。由于選取Delaunay算法生成的網格中一定會存在一些Sliver單元,影響網格質量,因此消除Sliver單元是網格生成中無法回避的問題。國內外專家提出了多種消除方法,主要分為兩種方法:優化消除Sliver單元以及運用Chew加密算法、Cheng加密算法、Li加密算法等三種算法進行加密來消除Sliver單元。

3 結語

本文對三角剖分的相應思想以及算法進行了簡單的歸納,對網格以及三角剖分,尤其是對三角剖分的理論、概念進行了簡述并且描述了并行化、修復網格的理論,為三角剖分拓寬思路,有助于提升剖分的效率,有助于提高網格的質量。

[1]董亮,劉厚林.非結構化網格生成技術及其應用[D].江蘇大學,2010,(6).

[2]ModelingAlgorithms User's Guide. Version 6.1[Z]. Open CASCADE S.A.S, 2006.

[3]David A. Field Laplacian smoothing and Delaunay Triangulations[J]. Communications in Applied Numerical Methods,1984(4):709-712.