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