搜索有限元網(wǎng)格劃分的“圣杯”（Holy Grail）問題
2017-03-23 by:CAE仿真在線 來(lái)源:互聯(lián)網(wǎng)
“對(duì)于給定的三維空間中的區(qū)域,具有復(fù)雜拓?fù)浜蛶缀?如何自動(dòng)生成高質(zhì)量的結(jié)構(gòu)化的六面體網(wǎng)格?”
在早期的文章中我們說過,六面體網(wǎng)格是有限元分析中最理想的網(wǎng)格,科學(xué)家和工程師一直在為此找尋最理想的方案,但至今沒有完美解決,對(duì)于復(fù)雜的幾何,我們?nèi)匀恍枰柚拿骟w單元,但對(duì)于數(shù)學(xué)家來(lái)說,尋找完美的解決方案是情懷和動(dòng)力所在。這個(gè)問題被成為神圣網(wǎng)格問題(HOLY GRAIL GRID ),可見其重要性。為了給大家科普這些領(lǐng)域的知識(shí),下面的內(nèi)容轉(zhuǎn)載自拓?fù)鋷缀晤I(lǐng)域的專家顧險(xiǎn)峰老師(后續(xù)還會(huì)陸續(xù)更新)。大家如果想了解顧教授更多的文章,請(qǐng)關(guān)注公眾號(hào)“老顧談幾何”
顧險(xiǎn)峰,1989年考入清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,基礎(chǔ)理論方向,班主任黃連生教授。1992年獲得清華大學(xué)特等獎(jiǎng)學(xué)金。后于美國(guó)哈佛大學(xué)獲得計(jì)算機(jī)博士學(xué)位,師從國(guó)際著名微分幾何大師丘成桐先生。目前為美國(guó)紐約州立大學(xué)石溪分校計(jì)算機(jī)系終身教授。曾獲美國(guó)國(guó)家自然科學(xué)基金CAREER獎(jiǎng),中國(guó)國(guó)家自然科學(xué)基金海外杰出青年獎(jiǎng)(與胡事民教授合作),“華人菲爾茨獎(jiǎng)”:晨興應(yīng)用數(shù)學(xué)金獎(jiǎng)。丘成桐先生和顧險(xiǎn)峰博士團(tuán)隊(duì),將微分幾何,代數(shù)拓?fù)?黎曼面理論,偏微分方程與計(jì)算機(jī)科學(xué)相結(jié)合,創(chuàng)立跨領(lǐng)域?qū)W科“計(jì)算共形幾何”,并廣泛應(yīng)用于計(jì)算機(jī)圖形學(xué),計(jì)算機(jī)視覺,幾何建模,無(wú)線傳感器網(wǎng)絡(luò),醫(yī)學(xué)圖像等領(lǐng)域。目前已經(jīng)發(fā)表二百篇余篇國(guó)際論文,學(xué)術(shù)專著包括“Computational Conformal Geometry”(計(jì)算共形幾何), “Ricci Flow for Surface Registration and Shape Analysis”等。
作者:顧險(xiǎn)峰
(2016年九月27-30日,第二十五屆國(guó)際網(wǎng)格生成圓桌會(huì)議在美國(guó)華盛頓召開(25th International Meshing Roundtable),受會(huì)議主席斯杭博士的邀請(qǐng),老顧在會(huì)上介紹了如何用計(jì)算共形幾何計(jì)算曲面和體的網(wǎng)格化。
斯杭博士是網(wǎng)格生成領(lǐng)域的絕對(duì)國(guó)際權(quán)威,久負(fù)盛名的傳奇人物,目前在德國(guó)維爾斯特拉斯應(yīng)用分析和隨機(jī)研究所任資深研究員。老顧和斯博士神交已久,一見如故,通過熱烈的討論,深入交流了許多學(xué)術(shù)思想。經(jīng)過數(shù)十年的積累沉淀,斯博士對(duì)于這一領(lǐng)域許多根本性問題具有非常深刻的見解,提出了大量的幾何猜想。同時(shí)老顧結(jié)識(shí)了許多年輕才俊,思想的交流碰撞產(chǎn)生了許多火花,必將引發(fā)一系列的新穎算法。)
中國(guó)龍的三角剖分,斯杭作
波音747飛機(jī)的空氣動(dòng)力學(xué)模擬網(wǎng)格化,斯杭作
小白鼠的肺部氣管混合網(wǎng)格,焦向民用TetGen作
在漫長(zhǎng)的教學(xué)和科研的生涯中,老顧經(jīng)常和一線的純粹數(shù)學(xué)家和一線的工程師合作,也正在指導(dǎo)數(shù)學(xué)方向和計(jì)算機(jī)方向的博士生。一些純粹數(shù)學(xué)背景的學(xué)生和學(xué)者對(duì)于抽象深邃的理論如何在實(shí)際中應(yīng)用產(chǎn)生深深的困惑,許多學(xué)生因?yàn)闊o(wú)法看到抽象數(shù)學(xué)(例如代數(shù)拓?fù)?的用途而缺乏深入鉆研的內(nèi)在動(dòng)力。同時(shí)另一方面,工程師往往從實(shí)用角度出發(fā),利用直覺經(jīng)驗(yàn)設(shè)計(jì)各種技術(shù)方案,往往忽視構(gòu)建嚴(yán)密的理論體系。對(duì)于簡(jiǎn)單的技術(shù)問題,這種發(fā)展方式行之有效,但是對(duì)于更為深刻的問題,因?yàn)槿狈碚摰闹笇?dǎo),很容易陷入瓶頸。在以商業(yè)利益為主導(dǎo)的工業(yè)界,理論研究一直是難得的奢侈;在以科研教育為主導(dǎo)的學(xué)術(shù)界,許多問題的規(guī)模和復(fù)雜程度超越了學(xué)者個(gè)人的想象能力,研究者往往缺乏第一手的實(shí)踐經(jīng)驗(yàn),以及深刻的直覺和洞察,從而無(wú)法提煉思想精髓。如何將理論和實(shí)踐有機(jī)結(jié)合,令人深思。這種現(xiàn)象在網(wǎng)格生成領(lǐng)域(Mesh Generation)體現(xiàn)得淋漓盡致。
圖1. CAD 模型
在現(xiàn)代社會(huì),幾乎所有的工業(yè)產(chǎn)品都是在計(jì)算機(jī)上設(shè)計(jì)出來(lái),一般都是用樣條曲面來(lái)表示,因此計(jì)算機(jī)輔助設(shè)計(jì)(Computer Aided Design CAD)具有根本的重要性。
圖2. CAE 模型,計(jì)算受力分析
CAD模型在真正生產(chǎn)之前,需要在計(jì)算機(jī)上進(jìn)行模擬仿真,計(jì)算其力學(xué)特性,從而改進(jìn)設(shè)計(jì)。這類計(jì)算問題屬于計(jì)算機(jī)輔助工程領(lǐng)域(Computer Aided Engineering CAE)。模擬仿真需要建立物理模型,往往是偏微分方程,然后利用有限元方法求解方程。例如波音公司大量使用CAE方法進(jìn)行模擬仿真,從而減少風(fēng)洞實(shí)驗(yàn)時(shí)間。
圖3. 有限元方法需要將空間網(wǎng)格化
有限元方法需要將曲面和空間網(wǎng)格化,從而將偏微分方程轉(zhuǎn)化成代數(shù)方程,然后用計(jì)算機(jī)求解。如圖3所示,為了模擬飛機(jī)的飛行情況,我們需要求解流體力學(xué)方程,這需要將飛機(jī)外圍的空間網(wǎng)格化。網(wǎng)格的質(zhì)量和數(shù)量會(huì)根本地影響計(jì)算結(jié)果的精度和速度。因此,毫不夸張地說網(wǎng)格生成(Mesh Generation)是整個(gè)現(xiàn)代工業(yè)的基礎(chǔ)。
據(jù)紐約州立大學(xué)的陳世魁教授估計(jì),每年全世界的CAD市場(chǎng)大概為5千億美元,CAE市場(chǎng)大概為50億美元。因?yàn)槠渚薮蟮膶?shí)用價(jià)值,工業(yè)界和學(xué)術(shù)界都在竭盡全力地研究開發(fā)網(wǎng)格生成算法工具。斯杭博士獨(dú)自開發(fā)和維護(hù)的TetGen系統(tǒng),在業(yè)界極其著名,幾乎所有這個(gè)領(lǐng)域的學(xué)者和工程師都曾經(jīng)用過TetGen。同時(shí),幾乎世界上所有網(wǎng)格生成系統(tǒng)都曾參考借鑒過TetGen的算法。斯杭博士只手擎天地開發(fā)了TetGen,卻從未從中謀求過任何經(jīng)濟(jì)利益,高風(fēng)亮節(jié),令人欽佩,堪稱網(wǎng)格生成領(lǐng)域的Linus (Linux的發(fā)明人)。
圖4. 四面體網(wǎng)格化(France Inria)
如圖4所示,給定三維歐式空間中的一個(gè)區(qū)域,我們將其三角剖分,每個(gè)胞腔都是四面體,這種網(wǎng)格化被稱為是四面體網(wǎng)格化(Tetrahedral Meshing)。四面體網(wǎng)格化算法基本上是基于所謂的Delaunay三角剖分。
圖5. Delaunay三角剖分
圖5解釋了Delaunay三角剖分的概念:給定平面一組離散點(diǎn),構(gòu)造一個(gè)三角剖分,使得每個(gè)三角形的外接圓內(nèi)不包含第四個(gè)點(diǎn)。在三維情形,我們構(gòu)造四面體剖分,使得每個(gè)四面體的外接球不包含第五個(gè)點(diǎn)。Delaunay三角剖分使得最小內(nèi)角最大化,從而提高數(shù)值模擬的穩(wěn)定性,因此成為網(wǎng)格生成算法的根基。
Delaunay三角剖分算法于1970年代被發(fā)明出來(lái),由此誕生了“計(jì)算幾何”這一學(xué)科。從此,計(jì)算幾何領(lǐng)域的主旋律一直是Delaunay三角剖分。經(jīng)過數(shù)十年的發(fā)展,Delaunay三角剖分算法日趨成熟,目前自動(dòng)四面體網(wǎng)格生成問題已經(jīng)被解決,并且在工業(yè)界得到廣泛應(yīng)用。
計(jì)算幾何領(lǐng)域的翹楚- Herbert Edelsbrunner 基于Delaunay三角剖分技巧開創(chuàng)了知名的Geomagic公司,主要應(yīng)用于點(diǎn)云重建。Geomagic于2013年被3D Systems收購(gòu),成為3D打印工業(yè)不可或缺的軟件工具。
與之成為鮮明對(duì)比的是斯杭博士的理想主義歷程。斯杭博士開發(fā)的TetGen在工業(yè)界影響廣泛,其核心算法被許多商業(yè)軟件無(wú)償借鑒和使用,極大地推動(dòng)了網(wǎng)格生成算法的普及和推廣,對(duì)于CAD和CAE領(lǐng)域的發(fā)展,起到了不可取代的推動(dòng)作用。
斯杭博士告訴老顧這段歷史:在他開發(fā)TetGen系統(tǒng)之前,世界上只有法國(guó)Inria(法國(guó)國(guó)家計(jì)算機(jī)與應(yīng)用數(shù)學(xué)研究所)開發(fā)的一個(gè)商業(yè)軟件,Tetmesh-GHS3d, 這是由一個(gè)團(tuán)隊(duì)開發(fā)三十年的成果,基本上所有大型的有限元商業(yè)軟件,例如Ansys,都用GHS3d來(lái)做四面體網(wǎng)格生成。斯杭博士獨(dú)力開發(fā)了TetGen,在許多關(guān)鍵技術(shù)上都超過了GHS3d,這一點(diǎn)在國(guó)際網(wǎng)格生成領(lǐng)域得到廣泛承認(rèn)。
圖6. EdgeSwap操作
經(jīng)驗(yàn)表明,平面Delaunay三角剖分可以如下生成。給定平面離散點(diǎn)集,我們從任意一個(gè)三角剖分開始,任給一條邊,與其相鄰的兩個(gè)三角形構(gòu)成一個(gè)四邊形。如果與此邊相鄰的兩個(gè)三角形不是Delaunay,如圖6左幀所示,則將此邊替換成四邊形的另外一條對(duì)角線,如右?guī)尽＿@種操作被稱為是換邊操作(Edge Swap)。那么經(jīng)過一系列換邊操作,我們一定能夠得到一個(gè)Delaunay三角剖分。斯杭告訴老顧,雖然算法非常成熟,并且理論上有嚴(yán)格證明,但是反過來(lái),從Delaunay三角剖分經(jīng)過一系列的換邊操作到任意給定的三角剖分,如果要求換邊操作具有某種單調(diào)性,則不存在理論上的完整證明。斯博士認(rèn)為存在本質(zhì)的拓?fù)湔系K。同時(shí),類似的算法是否可以求三維Delaunay三角剖分,這一問題長(zhǎng)期以來(lái)懸而未決。經(jīng)過大量的實(shí)驗(yàn),斯杭博士認(rèn)為這一算法也存在全局的拓?fù)湔系K,并進(jìn)一步提出了許多深刻的猜想。
圖7. 黎曼映照將無(wú)窮小圓映到無(wú)窮小圓,從而保持Delaunay三角剖分。(馬明作)
Delaunay三角剖分和共形幾何之間存在深刻的內(nèi)在聯(lián)系。如圖7所示,我們用黎曼映照(保角變換)將一張人臉曲面映到平面圓盤,人臉上的無(wú)窮小圓映到平面上的無(wú)窮小圓。Delaunay三角剖分的最主要特性就是“空?qǐng)A性”,由此我們看到保角變換保持Delaunay三角剖分。因此曲面的測(cè)地Delaunay三角剖分可以被轉(zhuǎn)化成平面Delaunay三角剖分。歷史上,Delaunay三角剖分的算法提出于1970年代,共形幾何算法提出于2000年左右,因此這種基于共形幾何的曲面Delaunay網(wǎng)格化算法在工業(yè)界并不普遍。我們相信,在不久的未來(lái),這一方法在實(shí)踐中會(huì)日益普及。
但是,這一方法無(wú)法直接向三維推廣。其主要的困難在于三流形間的保角變換基本上都是等距變換,因此我們無(wú)法用保角變換化彎為直。這一現(xiàn)象實(shí)質(zhì)是由三維流形的Mostow剛性所決定。
圖8. 六面體網(wǎng)格化。(賀英作)
如圖8所示,六面體網(wǎng)格化是將空間中的區(qū)域剖分,每個(gè)胞腔都是六面體。六面體網(wǎng)格具有四面體網(wǎng)格無(wú)法比擬的優(yōu)越性。對(duì)于模擬大形變的物理現(xiàn)象,六面體網(wǎng)格更加靈活,四面體網(wǎng)格過于僵硬;對(duì)于同樣的精度要求,六面體網(wǎng)格的體元數(shù)目遠(yuǎn)遠(yuǎn)小于四面體體元個(gè)數(shù);據(jù)紐約州立大學(xué)的焦向民教授介紹,存在特殊的一類問題,其精度要求很難用四面體網(wǎng)格達(dá)到,只能用六面體網(wǎng)格才能達(dá)到。因此,在廣大工業(yè)界和國(guó)家實(shí)驗(yàn)室,六面體網(wǎng)格被廣泛使用。
相比于四面體網(wǎng)格化,六面體網(wǎng)格化非常不成熟,算法設(shè)計(jì)和理論理解都存在許多問題。目前,四面體網(wǎng)格可以自動(dòng)生成,六面體網(wǎng)格的生成經(jīng)常需要人工干預(yù)。同時(shí)需要用戶積累的大量經(jīng)驗(yàn)來(lái)事先將物體切割成簡(jiǎn)單形狀。在許多工業(yè)研發(fā)部門,都有專門的小組專注于網(wǎng)格生成。就目前發(fā)展水平而言,六面體網(wǎng)格生成依然處于“藝術(shù)”階段,而非“技術(shù)”階段。由于工業(yè)界的強(qiáng)烈要求和算法理論幼稚原始之間的巨大落差,下列的問題被稱為是網(wǎng)格生成領(lǐng)域的“圣杯”(Holy Grail)
對(duì)于給定的三維空間中的區(qū)域,具有復(fù)雜拓?fù)浜蛶缀?如何自動(dòng)生成高質(zhì)量的結(jié)構(gòu)化的六面體網(wǎng)格?
這一問題又被稱為是“神圣網(wǎng)格”(Holy Grid)問題。
數(shù)十年來(lái),無(wú)數(shù)的工程師為此殫精竭慮,奮斗終生。他們發(fā)展了大量的復(fù)雜算法,開發(fā)了昂貴的商用軟件,但是依然無(wú)法建立普適的幾何拓?fù)淅碚摵妥詣?dòng)的算法來(lái)統(tǒng)一處理這一問題。
圖9. 虧格為三的曲面上的葉狀結(jié)構(gòu)。(雷娜,鄭曉朋作)
在過去的學(xué)術(shù)訪問中,老顧接觸了許多學(xué)者和工程師,他們都不約而同的提到了神圣網(wǎng)格問題。焦向民教授告訴老顧:“這一領(lǐng)域的理論非常匱乏,任何理論的建立都是一個(gè)突破!”
關(guān)于非結(jié)構(gòu)性的六面體網(wǎng)格的存在性理論,早在1980年代由菲爾茲獎(jiǎng)得主瑟斯頓(Thurston)洞察到,其主要工具是微分拓?fù)?特別是光滑同倫理論,其主要的光滑同倫定理由另一位菲爾茲獎(jiǎng)得主斯梅爾(Smale)證明。歷經(jīng)幾十年的發(fā)展,理論上沒有實(shí)質(zhì)性改變,近期又由計(jì)算拓?fù)鋵W(xué)家 Jeff Erickson用代數(shù)拓?fù)涞恼Z(yǔ)言加以厘清。
結(jié)構(gòu)性的六面體網(wǎng)格的存在性理論,最近被大連理工大學(xué)的羅鐘鉉,雷娜團(tuán)隊(duì)和老顧合作共同創(chuàng)立,其理論根基是流形的葉狀結(jié)構(gòu)理論和黎曼面的亞純微分理論。這一理論給出了復(fù)雜拓?fù)淙S流形六面體網(wǎng)格的存在性證明,并給出了神圣網(wǎng)格的自動(dòng)生成算法。美國(guó)三院院士(國(guó)家科學(xué)院,國(guó)家工程院,國(guó)家科學(xué)和藝術(shù)院),Thomas Hughes教授對(duì)于這項(xiàng)工作給與高度評(píng)價(jià),他認(rèn)為這項(xiàng)工作極其重要(Extremely Important)。相對(duì)于微分拓?fù)?葉狀結(jié)構(gòu)理論對(duì)于問題的刻畫更為精致而深刻。在未來(lái)的系列文章中,老顧將會(huì)給出這一系列理論發(fā)展的歷史脈絡(luò),和拓?fù)鋵?shí)質(zhì)。
相關(guān)標(biāo)簽搜索：有限元網(wǎng)格劃分的“圣杯”（Holy Grail）問題 Ansys有限元培訓(xùn) Ansys workbench培訓(xùn) ansys視頻教程 ansys workbench教程 ansys APDL經(jīng)典教程 ansys資料下載 ansys技術(shù)咨詢 ansys基礎(chǔ)知識(shí) ansys代做 Fluent、CFX流體分析 HFSS電磁分析 Abaqus培訓(xùn)
