[發(fā)明專利]基于最大化泊松圓盤采樣的四面體網(wǎng)格化方法和系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201610031891.6
• 申請日: 2016-01-19
• 公開（公告）號: CN105719349B
• 公開（公告）日: 2018-07-31
• 發(fā)明（設計）人: 嚴冬明;郭建偉;全衛(wèi)澤;張曉鵬
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06T17/30
• 分類號: G06T17/30
• 代理公司: 北京瀚仁知識產(chǎn)權代理事務所(普通合伙) 11482
• 代理人: 宋寶庫

本發(fā)明公開了一種基于最大化泊松圓盤采樣的四面體網(wǎng)格化方法和系統(tǒng)；其中，該方法包括獲取三維區(qū)域；對三維區(qū)域進行均勻地體素化，得到三維均勻網(wǎng)格；在三維區(qū)域的邊界表面，進行最大化泊松圓盤采樣，獲得表面采樣點集；然后根據(jù)表面采樣點集，提取表面網(wǎng)格；使用松弛方法對表面網(wǎng)格進行邊界保護，并在三維均勻網(wǎng)格上進行體采樣，得到體采樣點集；根據(jù)體采樣點集，使用三維狄洛尼三角化方法或者三維正則三角化方法，提取四面體網(wǎng)格。通過本發(fā)明實施例，解決了如何快速生成四面體網(wǎng)格，且消除四面體網(wǎng)格中薄片的技術問題。

技術領域

本發(fā)明實施例涉及計算機圖形處理技術領域，尤其是涉及一種基于最大化泊松圓盤采樣的四面體網(wǎng)格化方法和系統(tǒng)。

背景技術

網(wǎng)格生成是使用簡單的離散元素(例如，二維情況下的三角形和四邊形；三維情況下的四面體、角錐體、棱柱、六面體)來近似表示一個給定的封閉區(qū)域。網(wǎng)格生成在工程領域和科學研究領域，都有眾多的應用，例如機械部件或者建筑結構的仿真、醫(yī)學和生物數(shù)據(jù)分析、地理科學、計算流體動力學、以及計算機圖形學領域的動畫等等。

對于四面體網(wǎng)格生成，現(xiàn)在已經(jīng)存在很多魯棒的商業(yè)軟件(例如，Ansys)和用于網(wǎng)格生成的開源軟件包(例如，TetGen、CGALmesh、GelPSC和Gmsh等)。但是由于不同的應用對于網(wǎng)格質量的要求不同，這些工具往往不能同時滿足各種應用的需求，因此四面體網(wǎng)格化方法依然有很大的研究價值。

另一方面，對于四面體網(wǎng)格有很多評價其質量的指標，例如與原始區(qū)域的近似程度、四面體二面角以及半徑比等，這些指標彼此沖突，很難被同時滿足。對于仿真應用來說，二面角幾乎是最重要的評價指標，因為它與剛度矩陣的條件數(shù)直接相關。一個具有壞形狀的四面體(體積接近零，被叫做薄片)將會導致整個仿真實驗的失敗。然而，現(xiàn)有的四面體網(wǎng)格化方法仍然沒有很好的解決這個問題。目前常用的開源庫Tetgen(H.Si.Tetgen,aDelaunay-based quality tetrahedral mesh generator.ACM Trans.Math.Softw.,41(2):11:1-11:36,Feb.2015.)使用基于狄洛尼插入的方法，但是該方法得到的四面體網(wǎng)格質量不高。Yan等人(D.-M.Yan,W.Wang,B.Lévy,and Y.Liu.Efficient computation ofclipped Voronoi diagram for mesh generation.Computer-Aided Design,45(4):843-852,2013.)將重心Voronoi圖(CVT)的方法應用到四面體網(wǎng)格生成，但是會在邊界處產(chǎn)生大量薄片。

Tournois等人(J.Tournois,C.Wormser,P.Alliez,and M.Desbrun.Interleavingdelaunayrefinement and optimization for practical isotropictetrahedron meshgeneration.ACM Trans.on Graphics(Proc.SIGGRAPH),28(3):75:1-75:9,July2009.)將最優(yōu)狄洛尼三角化(Optimal Delaunay Triangulation--ODT)能量擴展到區(qū)域邊界，叫做natural ODT(NODT)，這個擴展確保了區(qū)域邊界和區(qū)域內(nèi)部的能量函數(shù)的一致性，從而減少了區(qū)域邊界的薄片數(shù)目。Chen等人(Z.Chen,W.Wang,B.Lévy,L.Liu,and F.Sun.Revisitingoptimal Delaunay triangulation for 3D graded mesh generation.SIAM Journal onScientific Computing,36(3):A930-A954,2014.)的revisited optimal Delaunaytriangulation(RODT)方法使用擬牛頓算子來快速生成變密度的四面體網(wǎng)格。但是這些算法自身不能消除薄片，必須要依賴后期處理。

有鑒于此，特提出本發(fā)明。

發(fā)明內(nèi)容