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

趙寶臣 朱晨澍 郜超超

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

1 研究背景

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

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

2 研究?jī)?nèi)容

2.1 網(wǎng)格分類

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

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

2.2.1 實(shí)際模型提取

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

2.2.2 Delaunay三角剖分

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

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

2.2.3 三角剖分算法

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

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

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

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

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

2.2.4 并行化

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

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

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

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

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

2.2.5 修復(fù)

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

3 結(jié)語(yǔ)

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

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