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

趙寶臣 朱晨澍 郜超超

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

1 研究背景

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

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

2 研究內(nèi)容

2.1 網(wǎng)格分類

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

2.2 網(wǎng)格劃分算法

2.2.1 實際模型提取

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

2.2.2 Delaunay三角剖分

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

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

2.2.3 三角剖分算法

以三角形網(wǎng)格的構(gòu)建過程的為依據(jù)將算法分為生長法,逐點插入法,和分治算法。

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

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

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

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

2.2.4 并行化

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

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

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

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

并行算法設(shè)計是算法理論和計算機并行體系相結(jié)合的結(jié)果,并行網(wǎng)格生成的兩種主流方法為數(shù)據(jù)并行和任務(wù)并行。數(shù)據(jù)并行是將數(shù)據(jù)域劃分為有限個區(qū)域,并將每個區(qū)域映射到一個相應(yīng)的處理器上,調(diào)用算法生成有限個網(wǎng)格;任務(wù)并行是在不同粒度層級上將算法運行所需要的時間和運行環(huán)境并行化,再利用并行開發(fā)工具設(shè)計新算法來完成并行網(wǎng)格的生成。前者反復使用已有的網(wǎng)格生成算法,實現(xiàn)較為容易,因此成為并行網(wǎng)格生成算法研究和開發(fā)的主流。對于并行網(wǎng)格生成算法的優(yōu)劣性,Chrisochoides給出了三個評價標準:穩(wěn)定性,復用性,可擴展性?；谌蝿?wù)并行的并行Delaunay方法主要是構(gòu)建在并行Bowyer-Watson內(nèi)核之上;基于數(shù)據(jù)并行模式的并行Delaunay方法有基于分割平面的并行,基于PDT理論的并行,基于稀疏網(wǎng)格的并行等方法,它們的主要區(qū)別是其所采用的數(shù)據(jù)分解方式不同。

2.2.5 修復

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

3 結(jié)語

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

[1]董亮,劉厚林.非結(jié)構(gòu)化網(wǎng)格生成技術(shù)及其應(yīng)用[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.