面向科學(xué)工程計(jì)算的通用網(wǎng)格生成軟件系統(tǒng)研究

高 翔，張 翔，徐傳福，劉 杰，龔春葉

(1.國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073；2.國(guó)防科技大學(xué)高性能計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410073)

1 引言

科學(xué)工程計(jì)算是20世紀(jì)后半葉出現(xiàn)的新型交叉學(xué)科，旨在利用計(jì)算機(jī)探索科學(xué)原理，是除了理論和實(shí)驗(yàn)之外的第3種科學(xué)手段，極大地延伸了人的計(jì)算能力[1]。近幾十年來(lái)，它一直是自然科學(xué)和工程科學(xué)領(lǐng)域的熱點(diǎn)，特別是以計(jì)算數(shù)學(xué)為基礎(chǔ)形成的計(jì)算力學(xué)、工程設(shè)計(jì)等諸多交叉學(xué)科。相比以往理論和實(shí)驗(yàn)學(xué)科，這些新型學(xué)科注重工程應(yīng)用中的實(shí)際問(wèn)題。典型地，計(jì)算機(jī)輔助工程CAE(Computer Aided Engineering)是利用計(jì)算手段有機(jī)組織包括航空、航天、造船、機(jī)械等重大工程項(xiàng)目中的各個(gè)制造環(huán)節(jié)。因而，研究科學(xué)工程計(jì)算對(duì)于解決實(shí)際問(wèn)題具有不可估量的實(shí)用價(jià)值。

當(dāng)前計(jì)算流體動(dòng)力學(xué)、電磁學(xué)、通信仿真、計(jì)算機(jī)圖形學(xué)等皆已成為科學(xué)工程計(jì)算領(lǐng)域的主流學(xué)科。這些學(xué)科領(lǐng)域的許多重要系統(tǒng)最終歸結(jié)為偏微分方程PDE(Partial Differential Equation)的數(shù)值求解。典型的PDE數(shù)值求解方法包括有限元FEM(Finite Element Method)、有限體積法FVE(Finite Volume Method)、有限差分法FDM(Finite Difference Method)等[2]。在運(yùn)用這些數(shù)值求解方法前，一步關(guān)鍵的前處理操作就是如何將連續(xù)的幾何模型網(wǎng)格化，即網(wǎng)格生成(Mesh Generation)，又稱(chēng)為網(wǎng)格劃分。網(wǎng)格生成是按照求解條件、材料特性等限制因素將給定幾何區(qū)域劃分成有限個(gè)基本幾何形體，一般將二維幾何體劃分為三角形或四邊形網(wǎng)格，將三維幾何體劃分為四面體或六面體網(wǎng)格等。德克薩斯大學(xué)奧斯汀分校的Hughes教授指出，在科學(xué)工程計(jì)算應(yīng)用中，數(shù)值求解時(shí)間僅占4%，而前處理中的網(wǎng)格生成卻占總用時(shí)的20%以上[2]。由此可見(jiàn)，如何實(shí)現(xiàn)高效的網(wǎng)格生成算法，是解決科學(xué)工程計(jì)算中重大應(yīng)用問(wèn)題的關(guān)鍵步驟。

研制網(wǎng)格生成軟件，不僅要考慮理論模型的理想情況，還要考慮模型問(wèn)題中的先驗(yàn)知識(shí)，避免在求解過(guò)程中出現(xiàn)網(wǎng)格質(zhì)量影響計(jì)算準(zhǔn)確性等問(wèn)題。故而網(wǎng)格生成軟件需借助多個(gè)交叉學(xué)科領(lǐng)域技術(shù)人員的通力合作，才能達(dá)到高可用水平?，F(xiàn)階段比較成熟、實(shí)用的網(wǎng)格生成軟件大多為西方大學(xué)、研究機(jī)構(gòu)、商業(yè)公司等單位所研制，這得益于他們多年來(lái)的理論知識(shí)和工程實(shí)戰(zhàn)經(jīng)驗(yàn)的積累，以及持續(xù)不斷地在網(wǎng)格生成、圖形交互、數(shù)據(jù)可視化等方面的技術(shù)攻關(guān)和研發(fā)投入。相比之下，國(guó)內(nèi)網(wǎng)格生成軟件仍然不夠成熟，缺乏一定的通用性和靈活性。

2 國(guó)內(nèi)外相關(guān)研究

迄今，傳統(tǒng)的網(wǎng)格生成技術(shù)已逐漸趨于完善階段，目前并未出現(xiàn)顛覆性的重要網(wǎng)格生成算法。加之多年來(lái)軟件研制技術(shù)的快速發(fā)展，國(guó)內(nèi)外已涌現(xiàn)出許多知名網(wǎng)格生成軟件，并廣泛應(yīng)用于學(xué)術(shù)界和工業(yè)界。

2.1 國(guó)外研究現(xiàn)狀

國(guó)外網(wǎng)格生成軟件研發(fā)開(kāi)始得最早，其最大推動(dòng)力主要來(lái)自于航空航天等領(lǐng)域的工業(yè)需求[2]。根據(jù)幾何拓?fù)浞绞?，網(wǎng)格生成方法通常分為結(jié)構(gòu)網(wǎng)格和非結(jié)構(gòu)網(wǎng)格。結(jié)構(gòu)網(wǎng)格生成最早可追溯到20世紀(jì)70年代美國(guó)勞倫斯利弗莫爾國(guó)家實(shí)驗(yàn)室的Winslow和Crowley以及同時(shí)期俄國(guó)Godunov和Prokopow的研究工作[3]。此后，具備結(jié)構(gòu)網(wǎng)格生成軟件的有EAGLE系統(tǒng)，它誕生于1987年，并無(wú)圖形交互功能，1992年集成圖形化功能并重新命名為EAGLEView。緊接著，許多其他結(jié)構(gòu)網(wǎng)格生成軟件亦不斷涌現(xiàn)，如AGPS面幾何系統(tǒng)、GridPro/az3000系統(tǒng)、ENGRID塊結(jié)構(gòu)系統(tǒng)等[3]。它們都將人機(jī)交互作為必備功能，并提供編程語(yǔ)言實(shí)現(xiàn)可定制功能。其中，源于NASA的Gridgen[4]是一套多塊分區(qū)結(jié)構(gòu)網(wǎng)格生成系統(tǒng)，后來(lái)發(fā)展為商業(yè)軟件系統(tǒng)PointWise，還有現(xiàn)在著名的ICEM CFD軟件除了包含非結(jié)構(gòu)網(wǎng)格功能，也包含了強(qiáng)大結(jié)構(gòu)網(wǎng)格生成能力，已成為著名商業(yè)軟件ANSYS的重要工具之一。

相比結(jié)構(gòu)網(wǎng)格，非結(jié)構(gòu)網(wǎng)格對(duì)網(wǎng)格的規(guī)則性沒(méi)有嚴(yán)格要求，但在20世紀(jì)70年代早期想獲得自動(dòng)生成的非結(jié)構(gòu)網(wǎng)格極其困難[2]。從70年代末開(kāi)始，隨著計(jì)算機(jī)領(lǐng)域基礎(chǔ)研究發(fā)展，四面體網(wǎng)格生成算法開(kāi)始發(fā)展并持續(xù)至今[5]。此外，六面體等基本幾何形體及其混合網(wǎng)格生成算法也得到空前發(fā)展。相應(yīng)地，一批優(yōu)秀的非結(jié)構(gòu)網(wǎng)格生成軟件應(yīng)運(yùn)而生，例如ICEM CFD、Hypermesh、TurboGrid、STAR CCM+等。現(xiàn)有的這些網(wǎng)格生成軟件大多提供友好的交互界面，強(qiáng)大的各類(lèi)網(wǎng)格生成和處理技術(shù)，保證網(wǎng)格質(zhì)量滿足工程應(yīng)用中的數(shù)值求解需求。這些軟件更具通用性、靈活性，成為許多工業(yè)領(lǐng)域的主流工具。根據(jù)統(tǒng)計(jì)，國(guó)外商業(yè)或開(kāi)源的結(jié)構(gòu)/非結(jié)構(gòu)網(wǎng)格生成軟件數(shù)目多達(dá)60余款[6]，功能齊全、技術(shù)成熟，為不同領(lǐng)域應(yīng)用問(wèn)題提供高質(zhì)量網(wǎng)格生成。除了網(wǎng)格生成軟件本身，許多商業(yè)CAE軟件將其作為整個(gè)數(shù)值仿真的有機(jī)整體之一，不僅具有適用于其他軟件的輸出格式，還能兼容主流開(kāi)源和商業(yè)軟件的二次開(kāi)發(fā)，因此這些國(guó)外網(wǎng)格生成軟件幾乎壟斷了CAE領(lǐng)域。

2.2 國(guó)內(nèi)研究現(xiàn)狀

國(guó)內(nèi)對(duì)于網(wǎng)格生成軟件的研制起步較晚，據(jù)不完全統(tǒng)計(jì)，目前由國(guó)內(nèi)機(jī)構(gòu)研發(fā)的網(wǎng)格生成軟件系統(tǒng)主要包括：浙江大學(xué)研發(fā)的HEDP/Pre[2]、中國(guó)空氣動(dòng)力研究與發(fā)展中心研發(fā)的NNW-GridStar[7]、山東大學(xué)研發(fā)的AUTOMESH-2D[8]、大連理工大學(xué)研發(fā)的JIFEX軟件前處理子系統(tǒng)AutoFEM[9]以及中國(guó)工程物理研究院高性能數(shù)值模擬軟件中心研發(fā)的SuperMesh[10]等。其中HEDP/Pre是CAE軟件HEDP的前處理模塊，支持非結(jié)構(gòu)網(wǎng)格生成，主要包括三角形、四邊形、四面體、六面體和混合網(wǎng)格。NNW-GridStar軟件基于網(wǎng)格拓?fù)淇蚣軜?gòu)造技術(shù)實(shí)現(xiàn)了復(fù)雜外形結(jié)構(gòu)網(wǎng)格附面層的自動(dòng)生成，具備良好的人機(jī)交互功能和模塊設(shè)計(jì)，是專(zhuān)業(yè)的結(jié)構(gòu)網(wǎng)格生成軟件。AUTOMESH-2D集成了多種網(wǎng)格生成算法，并支持各類(lèi)網(wǎng)格單元的混合，但其目前僅支持二維網(wǎng)格生成。JIFEX的前處理子系統(tǒng)AutoFEM是基于AutoCAD/MDT的有限元建模軟件，可直接利用幾何模型建立有限元計(jì)算模型，并包含多種有限元網(wǎng)格生成方法。SuperMesh兼具結(jié)構(gòu)網(wǎng)格、非結(jié)構(gòu)網(wǎng)格生成能力，特別是并行網(wǎng)格生成技術(shù)，能支持百萬(wàn)億次規(guī)模的并行計(jì)算。此外，國(guó)內(nèi)一些自主CAE軟件內(nèi)部也集成了部分網(wǎng)格生成功能，這一系列CAE軟件一般以其面向特定應(yīng)用而聞名，采用了較為先進(jìn)的設(shè)計(jì)理念和高效計(jì)算方法，解決了國(guó)內(nèi)業(yè)界不少實(shí)際應(yīng)用問(wèn)題，帶來(lái)了直接和間接的經(jīng)濟(jì)效益，也培養(yǎng)出一批從事科學(xué)工程計(jì)算的人才。但是，從整個(gè)技術(shù)和軟件市場(chǎng)份額而言，無(wú)論CAE領(lǐng)域還是網(wǎng)格生成領(lǐng)域，由于國(guó)內(nèi)自主軟件競(jìng)爭(zhēng)力不足，大多相關(guān)從業(yè)人員還是使用國(guó)外開(kāi)源或商業(yè)軟件。

3 通用網(wǎng)格生成軟件YHGRID研制方案及其關(guān)鍵技術(shù)

網(wǎng)格生成作為數(shù)值模擬的第一步，也是影響數(shù)值模擬精度和效率的一個(gè)關(guān)鍵環(huán)節(jié)。為打破國(guó)外商業(yè)軟件的壟斷，提升我國(guó)工業(yè)軟件自主可控水平，基于國(guó)產(chǎn)高性能計(jì)算平臺(tái)，擬采用Python和C/C++高級(jí)編程語(yǔ)言，研制通用的網(wǎng)格生成軟件YHGRID，服務(wù)于結(jié)構(gòu)、流體、電磁等科學(xué)工程計(jì)算領(lǐng)域。由于網(wǎng)格質(zhì)量依賴(lài)操作人員的工程經(jīng)驗(yàn)，自動(dòng)化程度還處于較低水平。為滿足未來(lái)工程應(yīng)用對(duì)效率和精度的需求，通用網(wǎng)格生成軟件要解決的關(guān)鍵技術(shù)包括可擴(kuò)展性的軟件架構(gòu)設(shè)計(jì)、高效可靠的核心并行網(wǎng)格生成算法和數(shù)據(jù)結(jié)構(gòu)、高質(zhì)量的網(wǎng)格優(yōu)化技術(shù)等。

3.1 軟件架構(gòu)

為實(shí)現(xiàn)方便高效的人機(jī)交互，通用網(wǎng)格生成軟件YHGRID采用可視化的圖形界面，實(shí)時(shí)顯示幾何模型和所生成的計(jì)算網(wǎng)格，具有幾何模型處理、并行網(wǎng)格生成、網(wǎng)格格式轉(zhuǎn)換等功能，且具有較強(qiáng)的功能可擴(kuò)展性。為實(shí)現(xiàn)上述功能和目標(biāo)，軟件架構(gòu)可由如圖1所示4個(gè)層級(jí)的功能組成：(1)人機(jī)交互。采用GUI圖形界面實(shí)現(xiàn)人機(jī)交互，在圖形界面下實(shí)現(xiàn)項(xiàng)目的全周期管理、各種功能的調(diào)度和業(yè)務(wù)流程控制。(2)前端引擎。主要滿足幾何外形和計(jì)算網(wǎng)格實(shí)時(shí)顯示的需求，在并行環(huán)境下能夠?qū)Ψ植际酱鎯?chǔ)的數(shù)據(jù)進(jìn)行整合，顯示統(tǒng)一、完整的幾何外形和網(wǎng)格。(3)核心算法。該部分是網(wǎng)格生成軟件的核心，包括幾何模型處理、各種網(wǎng)格生成算法和優(yōu)化技術(shù)。(4)并行環(huán)境。指生成大規(guī)模網(wǎng)格的并行環(huán)境系統(tǒng)，是通用網(wǎng)格生成軟件并行計(jì)算的基礎(chǔ)層功能。

Figure 1 Architecture of the mesh generation software YHGRID圖1 YHGRID網(wǎng)格生成軟件架構(gòu)

YHGRID網(wǎng)格生成軟件的研制目標(biāo)是既可以部署在單機(jī)平臺(tái)，也可以將界面客戶(hù)端部署在微機(jī)，服務(wù)端部署在遠(yuǎn)程高性能計(jì)算平臺(tái)，兩者之間通過(guò)SSH應(yīng)用采用易于網(wǎng)絡(luò)傳輸?shù)臉?biāo)準(zhǔn)格式實(shí)現(xiàn)高效數(shù)據(jù)通信。在超大規(guī)模網(wǎng)格生成的交互實(shí)時(shí)性方面，由于三維網(wǎng)格可視化過(guò)程中需要顯示的一般是所選擇的部分區(qū)域外表面的信息，因此可轉(zhuǎn)化為快速判斷三維網(wǎng)格中哪些是外表面以及哪些外表面可見(jiàn)，并應(yīng)用數(shù)據(jù)壓縮、硬件加速等技術(shù)提高可視化交互的實(shí)時(shí)性。

3.2 核心并行網(wǎng)格生成算法和數(shù)據(jù)結(jié)構(gòu)

通用網(wǎng)格生成軟件最重要、最核心的技術(shù)是高效可靠的網(wǎng)格生成算法和數(shù)據(jù)結(jié)構(gòu)。針對(duì)結(jié)構(gòu)網(wǎng)格、非結(jié)構(gòu)網(wǎng)格和混合網(wǎng)格等不同類(lèi)型的網(wǎng)格，雖然目前已有不少成熟公開(kāi)的生成算法甚至開(kāi)源程序可供借鑒，但是為了提高自主可控軟件的核心競(jìng)爭(zhēng)力，還需要在基礎(chǔ)的表面網(wǎng)格、體網(wǎng)格生成上下功夫，研究高效率、高可靠的單元網(wǎng)格生成算法，從而提供給用戶(hù)更多可定制化的參數(shù)，以滿足不同領(lǐng)域的計(jì)算需求。另一方面，隨著數(shù)值模擬的精細(xì)化程度不斷增加，所需計(jì)算網(wǎng)格的規(guī)模也越來(lái)越大，例如考慮湍流模型的真實(shí)飛行器模擬就需要數(shù)以?xún)|計(jì)的網(wǎng)格單元。由于內(nèi)存和單核性能的限制，傳統(tǒng)串行網(wǎng)格生成算法很難在當(dāng)前計(jì)算系統(tǒng)上快速生成滿足需求的網(wǎng)格。為充分利用現(xiàn)代HPC (High Performance Computing)平臺(tái)快速生成大規(guī)模的精細(xì)化網(wǎng)格，需要發(fā)展并行的網(wǎng)格生成算法。

以非結(jié)構(gòu)網(wǎng)格生成為例，一般并行網(wǎng)格生成算法從設(shè)計(jì)思路出發(fā)可以分成數(shù)據(jù)并行和算法并行：其中數(shù)據(jù)并行通常利用區(qū)域分解將原區(qū)域劃分成多個(gè)子區(qū)域，然后將子區(qū)域映射到不同處理器進(jìn)行處理；算法并行則是通過(guò)挖掘串行算法流程中潛在的并行度，將其重新組織為多個(gè)可以并發(fā)執(zhí)行的子任務(wù)集合。基于區(qū)域分解的數(shù)據(jù)并行是當(dāng)前網(wǎng)格并行算法研究的主流。根據(jù)子區(qū)域交接面網(wǎng)格和子區(qū)域內(nèi)部網(wǎng)格生成的先后順序，大致可以分為同步生成、先生成子區(qū)域網(wǎng)格和先生成交界面網(wǎng)格3大類(lèi)。并行網(wǎng)格生成算法的關(guān)鍵是區(qū)域分解的負(fù)載均衡以及交界面的處理。以交界面處理為例，一方面需要維持交界面附近生成高質(zhì)量的網(wǎng)格單元，另一方面需要在保證交界面網(wǎng)格一致性的同時(shí)，高效處理跨處理器的通信和同步。

同步生成的一類(lèi)典型算法是基于Delaunay原理的Bowyer-Watson增量插入算法。其核心過(guò)程是不斷對(duì)新加入的網(wǎng)格點(diǎn)形成空腔，然后對(duì)空腔區(qū)域重新Delaunay三角化[11]。因此，Bowyer- Watson算法進(jìn)行并行化處理時(shí)，若2個(gè)進(jìn)程處理的空腔互相不重疊，則可以同時(shí)進(jìn)行網(wǎng)格生成；當(dāng)處理的新網(wǎng)格點(diǎn)所在的空腔在其他進(jìn)程的處理范圍內(nèi)時(shí)，則需要進(jìn)行通信，即此時(shí)生成的是子區(qū)域之間的交界面網(wǎng)格單元。其并行化算法在二維情形下插入新的網(wǎng)格點(diǎn)，示意圖如圖2所示。Bowyer-Watson算法的空腔形成是通過(guò)判斷已有網(wǎng)格單元的外接圓或者外接球是否包含新的網(wǎng)格點(diǎn)，若包含則刪除該單元作為空腔的一部分。故當(dāng)同時(shí)插入多個(gè)點(diǎn)時(shí)，只要多個(gè)點(diǎn)周邊形成的空腔相互獨(dú)立、互不影響，則多個(gè)點(diǎn)可以并行插入；但當(dāng)空腔發(fā)生交叉的情況時(shí)，并行性則被破壞。因此，使用Bowyer-Watson算法構(gòu)建并行算法時(shí)，需要將原區(qū)域劃分成多個(gè)子網(wǎng)格區(qū)域發(fā)送給各個(gè)進(jìn)程或者處理器。每個(gè)進(jìn)程處理各自的網(wǎng)格區(qū)域，當(dāng)插入新的點(diǎn)時(shí)則要判斷新形成的空腔是否跨越了子網(wǎng)格之間的交界面，若沒(méi)跨越則可插入，若已經(jīng)跨越則需要進(jìn)行相應(yīng)的進(jìn)程通信。如圖2所示，該區(qū)域由3個(gè)子網(wǎng)格構(gòu)成，其中當(dāng)子網(wǎng)格2中插入新網(wǎng)格點(diǎn)P時(shí)，經(jīng)判斷可以發(fā)現(xiàn)除了本區(qū)域中的三角形BCD的外接圓包含點(diǎn)P，子網(wǎng)格1中的三角形ABC外接圓也包含點(diǎn)P，子網(wǎng)格3中的三角形DEF的三角形也包含點(diǎn)P。故進(jìn)程2需要向進(jìn)程1和進(jìn)程3發(fā)送訪問(wèn)相關(guān)區(qū)域的請(qǐng)求，若進(jìn)程1和進(jìn)程3同意該請(qǐng)求，且返回相應(yīng)的數(shù)據(jù)并對(duì)特定區(qū)域加鎖，則進(jìn)程2可進(jìn)行相關(guān)操作。通過(guò)上面的分析可以看出，并行的Bowyer-Watson算法對(duì)子網(wǎng)格區(qū)域交界面處的網(wǎng)格生成時(shí)間是不確定的，決定于插入的新網(wǎng)格點(diǎn)是否在交界面附近。

Figure 2 Point insertion of the parallel Bowyer-Watson algorithm圖2 并行Bowyer-Watson算法的插點(diǎn)示意圖

并行的前沿推進(jìn)算法是先生成子區(qū)域網(wǎng)格再生成交界面網(wǎng)格，其核心思想為：將原區(qū)域劃分成多個(gè)子區(qū)域，先對(duì)非共享邊界區(qū)域進(jìn)行網(wǎng)格生成，之后重新劃分區(qū)域形成新的共享邊界并對(duì)之前的未生成網(wǎng)格區(qū)域完成網(wǎng)格生成。L?hner等[12]是第1個(gè)提出前沿推進(jìn)并行算法的研究者，其算法主要過(guò)程是首先利用四叉樹(shù)覆蓋整個(gè)幾何區(qū)域(生成三維網(wǎng)格時(shí)使用八叉樹(shù))，形成相應(yīng)的單元尺寸場(chǎng)指導(dǎo)非結(jié)構(gòu)網(wǎng)格生成，同時(shí)將幾何區(qū)域劃分成多個(gè)四分區(qū)域；之后將劃分的多個(gè)四分區(qū)域在遵循負(fù)載平衡的原則前提下分配給各個(gè)子進(jìn)程，進(jìn)程間共享著子區(qū)域的邊界邊和邊界點(diǎn)；各個(gè)進(jìn)程對(duì)未靠近邊界線的地方使用前沿推進(jìn)法生成非結(jié)構(gòu)網(wǎng)格，遺留下邊界區(qū)域的未生成區(qū)域；之后將四分區(qū)中的劃分朝著x軸和y軸方向移動(dòng)一定距離，形成新的邊界區(qū)域和邊界線；最后各個(gè)進(jìn)程對(duì)未生成區(qū)域進(jìn)行非結(jié)構(gòu)網(wǎng)格生成；一直如此操作直到前沿集合為空時(shí)停止。

如圖3所示為并行前沿推進(jìn)算法過(guò)程的簡(jiǎn)略示意圖，展示的過(guò)程分為3個(gè)階段。第1個(gè)階段為劃分區(qū)域構(gòu)成4個(gè)子區(qū)域；第2個(gè)階段為各個(gè)子區(qū)域中的進(jìn)程生成非靠近公共邊界的網(wǎng)格；第3個(gè)階段為移動(dòng)整體劃分的區(qū)域，形成新的公共邊界，如AB邊和CD邊，原先屬于邊界附近的空白區(qū)域，如今可以利用前沿推進(jìn)法生成網(wǎng)格。

Figure 3 Procedure of the parallel advance front algorithm圖3 并行前沿推進(jìn)算法過(guò)程示意圖

不同于并行的Bowyer-Watson算法和前沿推進(jìn)算法，交界面優(yōu)先并行算法則是一種先生成交界面網(wǎng)格的算法，其一般步驟為：首先利用區(qū)域分解方法將目標(biāo)幾何體劃分成多個(gè)子區(qū)域，或者先生成粗體網(wǎng)格再進(jìn)行區(qū)域劃分；然后對(duì)各個(gè)子區(qū)域交界面進(jìn)行最終網(wǎng)格的生成，如此不同子區(qū)域的邊界網(wǎng)格保證了一致性；最后將各個(gè)子區(qū)域分配給不同處理器進(jìn)行最終的網(wǎng)格生成。不同的交界面優(yōu)先并行算法的區(qū)別主要在于在交界面生成網(wǎng)格的方式或區(qū)域分解的方式存在差異。如圖4所示為交界面優(yōu)先并行算法的示意圖，首先對(duì)幾何體ABCDIJKL生成粗體網(wǎng)格，然后區(qū)域分解成2個(gè)部分并對(duì)邊界面EFHG生成最終的邊界面網(wǎng)格。

Figure 4 Schematic diagram of the interface first parallel algorithm圖4 交界面優(yōu)先并行算法示意圖

3.3 幾何模型處理和網(wǎng)格格式轉(zhuǎn)換

幾何模型處理能力是網(wǎng)格生成軟件系統(tǒng)能用和好用的基礎(chǔ)，它為網(wǎng)格生成算法提供前置處理的CAD (Computer Aided Design)幾何模型。一般網(wǎng)格生成軟件應(yīng)包括基礎(chǔ)的CAD功能庫(kù)、通用幾何數(shù)據(jù)格式的讀寫(xiě)、基本幾何的創(chuàng)建以及幾何模型的清理和修復(fù)等功能。目前國(guó)際主流的幾何處理引擎主要有美國(guó)Spatial Technology公司推出的ACIS、德國(guó)西門(mén)子公司擁有的Parasolid和開(kāi)源的Open Cascade等平臺(tái)，一些成熟的商業(yè)網(wǎng)格生成軟件大都通過(guò)購(gòu)買(mǎi)集成相關(guān)軟件的模塊獲得幾何處理能力。

ACIS平臺(tái)提供從簡(jiǎn)單實(shí)體到復(fù)雜實(shí)體的造型功能，包括實(shí)體的布爾運(yùn)算、曲面裁剪和過(guò)渡等多種編輯功能，其特點(diǎn)是采用C++面向?qū)ο蟮臄?shù)據(jù)結(jié)構(gòu)，使得線架造型、曲面造型、實(shí)體造型可以靈活組合使用。ACIS使用軟件組件技術(shù)，用戶(hù)可使用所需的組件，也可以開(kāi)發(fā)相應(yīng)部件來(lái)代替，它提供高級(jí)的專(zhuān)業(yè)函數(shù)，可以單獨(dú)出售接口源碼給需要特定功能的用戶(hù)。Parasolid平臺(tái)支持包括通用的單元建模、集成的自由曲面建模和實(shí)體建模，提供漸變、偏移和幾何替換等功能，可通過(guò)自動(dòng)再生周?chē)鷶?shù)據(jù)來(lái)移除特征細(xì)節(jié)。Parasolid還提供廣泛的圖形和渲染支持，包括隱藏線、線框和繪圖，曲面細(xì)分和模型數(shù)據(jù)查詢(xún)等功能，并支持多種編程語(yǔ)言的接口調(diào)用。Open Cascade是一款開(kāi)源的幾何造型引擎，基于該建模引擎已發(fā)展了若干CAD/CAE軟件，如國(guó)外的FreeCAD、HeeksCAD以及國(guó)內(nèi)的AnyCAD等。Open Cascade基于邊界表示方法，能夠滿足二維、三維實(shí)體造型和曲面造型，大致分為建模、可視化和數(shù)據(jù)管理3大模塊。其中建模為核心模塊，可視化模塊基于OpenGL庫(kù)實(shí)現(xiàn)，數(shù)據(jù)管理采用樹(shù)形結(jié)構(gòu)，使用較為復(fù)雜。由于國(guó)內(nèi)CAD幾何模型處理技術(shù)的缺失較為嚴(yán)重，研制YHGRID網(wǎng)格生成軟件擬采用開(kāi)源的Open Cascade作為幾何處理引擎，并利用OpenGL圖形庫(kù)實(shí)現(xiàn)幾何和網(wǎng)格的可視化交互顯示。

另一方面，豐富的網(wǎng)格格式轉(zhuǎn)換和導(dǎo)出功能是網(wǎng)格生成軟件好用和易用的顯著標(biāo)志。當(dāng)前，科學(xué)工程計(jì)算軟件百花齊放，每個(gè)計(jì)算軟件都有自己特定支持的網(wǎng)格格式，為使得生成的網(wǎng)格能夠便捷地用于更多的計(jì)算軟件，YHGRID網(wǎng)格生成軟件應(yīng)該支持導(dǎo)出豐富多樣的網(wǎng)格格式，例如CGNS格式、Fluent格式和Plot3D格式、開(kāi)源計(jì)算軟件如OpenFOAM格式和SU2格式等。據(jù)統(tǒng)計(jì)，應(yīng)用廣泛的ICEM CFD網(wǎng)格生成軟件支持的網(wǎng)格格式多達(dá)一百多種，一些沒(méi)有公開(kāi)的網(wǎng)格格式還需要與相應(yīng)工程計(jì)算軟件的開(kāi)發(fā)機(jī)構(gòu)合作開(kāi)發(fā)。

3.4 網(wǎng)格優(yōu)化技術(shù)

網(wǎng)格生成在某種程度上可以說(shuō)是一個(gè)工程性問(wèn)題，結(jié)構(gòu)/非結(jié)構(gòu)網(wǎng)格生成算法生成的初始網(wǎng)格可能會(huì)存在大量的低質(zhì)量網(wǎng)格單元，因此研制YHGRID軟件還需要網(wǎng)格優(yōu)化技術(shù)來(lái)進(jìn)一步提升網(wǎng)格單元的質(zhì)量。一般來(lái)說(shuō)，網(wǎng)格優(yōu)化算法可分為2類(lèi)：幾何優(yōu)化算法和拓?fù)鋬?yōu)化算法。幾何優(yōu)化算法指的是平移網(wǎng)格頂點(diǎn)，改變幾何位置來(lái)提高網(wǎng)格質(zhì)量，而不會(huì)改變網(wǎng)格頂點(diǎn)的相對(duì)位置。經(jīng)典的算法如拉普拉斯光順[13]，其將內(nèi)部點(diǎn)移到多邊形或多面體的形心或重心。還有一些算法會(huì)定義一些平滑目標(biāo)函數(shù)，通過(guò)數(shù)值優(yōu)化算法來(lái)優(yōu)化頂點(diǎn)的位置，如牛頓法[14]或最速下降法[15]等，這一類(lèi)算法稱(chēng)為基于數(shù)值優(yōu)化的平滑算法[16]。拓?fù)鋬?yōu)化算法指的是改變網(wǎng)格點(diǎn)的相對(duì)位置，通常會(huì)使用一組新的網(wǎng)格單元來(lái)代替原有質(zhì)量較差的網(wǎng)格單元組。拓?fù)鋬?yōu)化有很多種，其中邊交換是用新的網(wǎng)格邊替代刪除的網(wǎng)格邊來(lái)優(yōu)化拓?fù)?，比如圖5所示的3-2變換。面交換算法可以看做是邊交換的逆過(guò)程[17]，如圖5所示的2-3變換。邊收縮算法則是將一條邊的2個(gè)頂點(diǎn)收縮成1個(gè)點(diǎn)來(lái)簡(jiǎn)單化網(wǎng)格拓?fù)鋄18]。邊分裂算法將一條網(wǎng)格邊插入一個(gè)新的網(wǎng)格點(diǎn)，用于產(chǎn)生新的網(wǎng)格單元來(lái)優(yōu)化網(wǎng)格拓?fù)鋄19]。單一的網(wǎng)格優(yōu)化算法可以?xún)?yōu)化一類(lèi)特定的低質(zhì)量網(wǎng)格單元，還有一些研究人員采用幾組不同的網(wǎng)格優(yōu)化組合算法，取得了不錯(cuò)的效果。

Figure 5 Schematic diagram of edge swap and surface swap圖5 邊交換、面交換的示意圖

4 自主研發(fā)YHGRID網(wǎng)格生成軟件所面臨的挑戰(zhàn)及其未來(lái)發(fā)展方向

網(wǎng)格生成作為科學(xué)工程計(jì)算的基礎(chǔ)，是一門(mén)融合計(jì)算機(jī)圖形學(xué)、拓?fù)鋵W(xué)、計(jì)算機(jī)科學(xué)等為一體的技術(shù)，其產(chǎn)品一直以來(lái)被國(guó)外商業(yè)軟件所壟斷，嚴(yán)重影響我國(guó)在該領(lǐng)域的話語(yǔ)權(quán)。為了打破國(guó)外商業(yè)軟件的壟斷，保障具有自主知識(shí)產(chǎn)權(quán)的工業(yè)軟件體系完整性，迫切需要基于國(guó)產(chǎn)高性能計(jì)算平臺(tái)研發(fā)滿足科學(xué)工程計(jì)算需求的網(wǎng)格生成軟件。本節(jié)主要從面臨的技術(shù)挑戰(zhàn)和未來(lái)的發(fā)展方向2個(gè)方面，分析自主開(kāi)展YHGRID網(wǎng)格生成軟件研發(fā)可能遇到的問(wèn)題。

4.1 面臨的技術(shù)挑戰(zhàn)

由于國(guó)外商業(yè)軟件已經(jīng)過(guò)長(zhǎng)期的技術(shù)積累和發(fā)展，相關(guān)的功能和接口已十分成熟，并且占據(jù)了絕大部分的市場(chǎng)份額和用戶(hù)?；趪?guó)產(chǎn)HPC平臺(tái)研制網(wǎng)格生成軟件YHGRID，一方面需要充分調(diào)研當(dāng)前商業(yè)軟件的功能和接口，盡量滿足現(xiàn)有用戶(hù)的功能需求，才有可能吸引更多的潛在用戶(hù)群體，健全工業(yè)軟件的生態(tài)體系；另一方面需要結(jié)合高性能計(jì)算的發(fā)展，超前布局新的網(wǎng)格生成技術(shù)和功能模塊，才有可能在未來(lái)實(shí)現(xiàn)“彎道超車(chē)”。

在幾何模型處理方面，光滑、清晰的幾何模型將極大地減少網(wǎng)格生成的工作量，并為表面網(wǎng)格、附面層網(wǎng)格自動(dòng)化生成提供良好的條件?？梢砸蚤_(kāi)源的或國(guó)內(nèi)發(fā)展較好的幾何處理引擎為基礎(chǔ)，進(jìn)一步提高模型修補(bǔ)效率，發(fā)展模型自動(dòng)化檢測(cè)方法，首先通過(guò)自動(dòng)化檢測(cè)，標(biāo)識(shí)出幾何模型中的空洞、縫隙等待修復(fù)的位置。對(duì)于單個(gè)曲面上的空洞，可以直接刪除空洞的幾何特征，保留完整的曲面信息。對(duì)于由多個(gè)曲面組成的空洞，可以通過(guò)新的平面或曲面進(jìn)行填充。對(duì)于縫隙，如果其由2條鄰近的線組成，則直接合并2條線。如果縫隙較大，則可在縫隙中填充新的平面或者曲面。通過(guò)采用上述技術(shù)手段，可實(shí)現(xiàn)若干種實(shí)用的模型修補(bǔ)和清理方法。

在網(wǎng)格生成算法方面，需要高度重視核心生成算法的研究，高效可靠的面網(wǎng)格和體網(wǎng)格生成算法和數(shù)據(jù)結(jié)構(gòu)是整個(gè)網(wǎng)格生成軟件功能的基礎(chǔ)。這方面固然有許多比較成熟的方法，但是至少在六面體網(wǎng)格生成、邊界限定的網(wǎng)格生成、高效的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)、網(wǎng)格生成算法的可靠性、任意多邊形/多面體網(wǎng)格生成等技術(shù)方面仍需要探索和突破。在生成算法的大規(guī)模并行方面，可能會(huì)面臨諸多問(wèn)題，如邊界網(wǎng)格一致性問(wèn)題、并行網(wǎng)格數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)問(wèn)題、大規(guī)模并行的負(fù)載均衡和通信效率等問(wèn)題。需要結(jié)合國(guó)產(chǎn)高性能計(jì)算平臺(tái)，研究高效的多級(jí)并行網(wǎng)格生成算法，充分挖掘算法潛在的并行性。通過(guò)動(dòng)態(tài)負(fù)載均衡等方法提升并行計(jì)算的性能，并采用HDF5等并行文件讀寫(xiě)庫(kù)實(shí)現(xiàn)大規(guī)模網(wǎng)格的并發(fā)I/O。

在附面層網(wǎng)格自動(dòng)生成方面，由于在空氣動(dòng)力學(xué)等工程計(jì)算中，靠近物面的附面層流場(chǎng)變化劇烈，需要更加精細(xì)的網(wǎng)格捕捉流場(chǎng)特征，這部分網(wǎng)格生成的魯棒性問(wèn)題一直是一個(gè)難點(diǎn)。在幾何外形變化劇烈的凹凸區(qū)域，存在網(wǎng)格相交、質(zhì)量變差的可能，需要結(jié)合通用的附面層網(wǎng)格構(gòu)造技術(shù)，研究新的附面層網(wǎng)格自動(dòng)生成算法和網(wǎng)格過(guò)渡技術(shù)。

在網(wǎng)格質(zhì)量?jī)?yōu)化方面，傳統(tǒng)的幾何優(yōu)化和拓?fù)鋬?yōu)化方法一般是基于單個(gè)網(wǎng)格單元質(zhì)量的評(píng)價(jià)而進(jìn)行的改進(jìn)，對(duì)網(wǎng)格質(zhì)量的優(yōu)化缺少整體把握，往往只是對(duì)網(wǎng)格局部進(jìn)行了一些優(yōu)化，又或是需要人工的反復(fù)操作迭代才能達(dá)到預(yù)期的網(wǎng)格質(zhì)量要求。針對(duì)這一問(wèn)題，自主研發(fā)YHGRID軟件時(shí)可以嘗試新型的網(wǎng)格全局自動(dòng)優(yōu)化技術(shù)，減少人工干預(yù)并提高網(wǎng)格質(zhì)量。

4.2 未來(lái)的發(fā)展方向

分析基于國(guó)產(chǎn)HPC平臺(tái)研發(fā)自主可控的網(wǎng)格生成軟件YHGRID面臨的技術(shù)挑戰(zhàn)，雖然困難重重，且與國(guó)外成熟商業(yè)軟件在技術(shù)積累上還存在不小差距，但是隨著高性能計(jì)算的不斷發(fā)展，商業(yè)網(wǎng)格生成軟件現(xiàn)有的架構(gòu)和功能已不能很好地滿足超大規(guī)模、高自動(dòng)化網(wǎng)格生成的需求。因此，現(xiàn)階段研制國(guó)產(chǎn)的網(wǎng)格生成軟件也具有一定的后發(fā)優(yōu)勢(shì)，可以從以下幾個(gè)方面把握網(wǎng)格生成未來(lái)的發(fā)展方向：

(1)高階曲面網(wǎng)格的生成。由于高精度計(jì)算方法的發(fā)展和應(yīng)用，科學(xué)工程計(jì)算的計(jì)算量越來(lái)越大，故而一般希望使用較少的計(jì)算單元即可獲得滿足精度要求的解。但是，用較少的單元來(lái)離散復(fù)雜曲面幾何外形的計(jì)算域時(shí)，常常會(huì)遇到困難，主要是因?yàn)樵趲缀瓮庑巫兓瘎×覅^(qū)域，需要線性單元的尺度足夠小才能獲得滿意的計(jì)算精度。研究表明，如果采用高精度算法時(shí)仍然用線性直網(wǎng)格，將無(wú)法達(dá)到設(shè)計(jì)精度，需要將形狀規(guī)則的參考單元轉(zhuǎn)化為邊界為曲線或曲面的高階物理單元。因此，高階曲面網(wǎng)格生成近年來(lái)得到了持續(xù)關(guān)注。一般的方法是將傳統(tǒng)軟件生成的直網(wǎng)格轉(zhuǎn)化為曲網(wǎng)格，但由于缺少原始幾何模型的信息，轉(zhuǎn)化的曲網(wǎng)格并不能完全貼合真實(shí)幾何，故而在自主研制網(wǎng)格生成軟件時(shí)，可以研究高階曲面網(wǎng)格生成算法直接在CAD幾何上生成曲網(wǎng)格的方法，從而滿足高精度數(shù)值模擬的需求。

(2)超大規(guī)模的并行網(wǎng)格并行生成算法?；谀壳皯?yīng)用廣泛的Delaunay、前沿推進(jìn)等非結(jié)構(gòu)網(wǎng)格生成算法，研究高可擴(kuò)展的并行網(wǎng)格生成算法，以適應(yīng)當(dāng)前大規(guī)模、高精度的數(shù)值模擬需求。其中區(qū)域分解負(fù)責(zé)將問(wèn)題域分解成多個(gè)離散子區(qū)域，然后子區(qū)域相對(duì)獨(dú)立地生成網(wǎng)格，因此區(qū)域分解是并行網(wǎng)格生成算法的關(guān)鍵步驟。由于各子區(qū)域最終生成的網(wǎng)格單元數(shù)量參差不齊，可結(jié)合單元尺寸分布算法預(yù)估網(wǎng)格量，研究并行可擴(kuò)展的區(qū)域分解算法。并行網(wǎng)格生成的另一個(gè)難點(diǎn)是交界面處理，為保證網(wǎng)格質(zhì)量和并行可擴(kuò)展性，可研究先生成高質(zhì)量交界面網(wǎng)格的解耦式生成算法，實(shí)現(xiàn)交界面的一致性，并大大減少子區(qū)域網(wǎng)格生成的通信和同步開(kāi)銷(xiāo)。此外，當(dāng)前主流的高性能計(jì)算結(jié)點(diǎn)都是處理器加協(xié)處理器的組合，研究集成異構(gòu)并行計(jì)算的超大規(guī)模網(wǎng)格負(fù)載均衡剖分算法，可充分發(fā)揮國(guó)產(chǎn)HPC平臺(tái)的計(jì)算優(yōu)勢(shì)。

(3)基于深度學(xué)習(xí)的高自動(dòng)化網(wǎng)格生成和優(yōu)化算法。給定幾何模型，傳統(tǒng)的非結(jié)構(gòu)網(wǎng)格生成方法一般先離散幾何曲線和曲面，生成表面網(wǎng)格后，再以此為基礎(chǔ)生成空間體網(wǎng)格。這種自底向上的方式在保證網(wǎng)格貼體性質(zhì)的同時(shí)，也很大程度限制了網(wǎng)格生成的自由度和自動(dòng)化。自主研制YHGRID網(wǎng)格生成軟件，可研究采用自頂向下方式的新型生成算法，例如首先給定一個(gè)初始的三角網(wǎng)格，結(jié)合網(wǎng)格變形和加密技術(shù)，探索基于圖卷積神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)方法，全自動(dòng)化地將初始網(wǎng)格的邊界逐步移動(dòng)映射到給定的幾何模型，從而實(shí)現(xiàn)貼體網(wǎng)格的生成。另一方面，可基于支持向量機(jī)和多層感知機(jī)等機(jī)器學(xué)習(xí)技術(shù)，以傳統(tǒng)的全局尺寸參數(shù)、點(diǎn)源/線源和幾何曲率特征等信息作為輸入，研究新型的自適應(yīng)連續(xù)單元尺寸分布模型，高效指導(dǎo)計(jì)算區(qū)域內(nèi)各處的網(wǎng)格疏密程度，從而取代傳統(tǒng)交互頻繁的背景網(wǎng)格等方法。

總而言之，自主研制YHGRID網(wǎng)格生成軟件，可以某些特色功能為牽引，以點(diǎn)帶面吸引用戶(hù)深度使用，從而逐步減輕對(duì)國(guó)外商業(yè)軟件的依賴(lài)。

5 結(jié)束語(yǔ)

在科學(xué)工程計(jì)算實(shí)踐中，首先需要對(duì)計(jì)算域進(jìn)行網(wǎng)格生成，且網(wǎng)格生成的便捷程度和網(wǎng)格質(zhì)量直接影響著計(jì)算周期和計(jì)算結(jié)果。因此，通用的網(wǎng)格生成軟件系統(tǒng)是開(kāi)展現(xiàn)代科學(xué)工程計(jì)算的基礎(chǔ)。本文首先介紹了國(guó)內(nèi)外網(wǎng)格生成軟件的發(fā)展現(xiàn)狀，國(guó)內(nèi)相關(guān)領(lǐng)域的市場(chǎng)長(zhǎng)期被國(guó)外的商業(yè)軟件壟斷，嚴(yán)重阻礙了自主工業(yè)軟件體系的發(fā)展。然后分析了研制YHGRID網(wǎng)格生成軟件系統(tǒng)中的若干關(guān)鍵技術(shù)，總結(jié)了可供參考的技術(shù)方案。最后基于國(guó)產(chǎn)高性能計(jì)算平臺(tái)，對(duì)研制自主可控的YHGRID網(wǎng)格生成軟件面臨的技術(shù)挑戰(zhàn)和未來(lái)的發(fā)展方向進(jìn)行了探討。