網(wǎng)格質(zhì)量分析-計算機應(yīng)用研究

1、第 32 卷第 1 期2012 年 1 期計算機應(yīng)用研究Application Research of ComputersVol.32 No.1Jan. 2015基本體素表面網(wǎng)格生成新方法吳 婷，張禮兵（嘉興學(xué)院 機電工程學(xué)院，浙江 嘉興 314001）摘 要 :為提高三角網(wǎng)格生成的質(zhì)量和速度，針對圓柱體和圓錐體，提出了一種新的曲面網(wǎng)格生成方法。根據(jù)曲面的表面形態(tài)特征，以正三角形單元為基礎(chǔ)，利用波前法（Advancing Front Method, AFM） 層層推進原理直接在三維空間中進行三角剖分。實驗分析結(jié)果表明該方法能夠避免映射法的邊界調(diào)整問題以及傳統(tǒng)波前法由于遞歸剖分引入的累積變形，

2、無需坐標(biāo)變換 和耗時的合法性檢查就能夠高效、快速的生成較高質(zhì)量的曲面網(wǎng)格。關(guān)鍵詞 :網(wǎng)格；三角剖分；波前法 （AFM） ；基本體素；曲面中圖分類號 : TP391New method for triangular mesh generation of basic voxel surfaceWu Ting, Zhang Libing( College of Mechanical & Electrical Engineering, Jiaxing University, Jiaxing Zhejiang, 314001, China )Abstract: To raise the quality

3、and generation velocity of triangular meshes, this paper proposed a novel surface triangular mesh generation method for cylinder and cone. Based on the surface shape characteristics and the regular triangle unit, it finished the triangulation directly in 3D according to the advancing layers principl

4、e of AFM (advancing front method). Experimental results demonstrate that this method can avoid the boundary adjustment problem of mapping method and the accumulated deformation resulted by recursion decomposition of AFM, and need no coordinate transformation and the time-consuming legal examination,

5、 therefore can efficiently and rapidly generate a higher quality surface meshes.Key words: mesh; triangulation; advancing front method (AFM); basic voxel; surface0 引言隨著計算機技術(shù)和逆向工程技術(shù)的快速發(fā)展， 由大量小 三角面片組成的三角網(wǎng)格模型因其拓?fù)淠芰姡?操作簡便等 優(yōu)點 , 已經(jīng)成為數(shù)字幾何模型的重要表現(xiàn)形式， 并廣泛應(yīng)用 于制造業(yè)、醫(yī)學(xué)、娛樂等領(lǐng)域。 在幾何模型的三角化處理中， 最重要的環(huán)節(jié)就是將圍成形體或形面的各個曲面

6、（如平面、柱面、 圓錐面、球面、 NURBS 曲面等 ）進行網(wǎng)格剖分。網(wǎng) 格剖分的好壞直接影響到后續(xù)的有限元分析、 逆向建模、 快 速成型等結(jié)果的質(zhì)量和精度 1-2 。目 前 ， 關(guān) 于曲 面 的 三角 網(wǎng) 格生 成 方 法 主要 集 中 在 Delaunay 三角剖分方法和波前法 （Advancing Front Method, AFM） 。Delaunay 三角剖分方法 3-4 根據(jù)外接圓為空準(zhǔn)則將指 定區(qū)域內(nèi)的節(jié)點進行連接以生成網(wǎng)格。 該方法在二維平面域 中較為成熟， 但如果直接應(yīng)用到三維曲面則穩(wěn)定性差。 因此， 對于三維曲面， 主要采用映射法， 即首先將曲面邊界映射到 平面參數(shù)域上后，

7、利用 Delaunay 三角剖分方法構(gòu)建平面網(wǎng) 格，最后再映射回三維物理空間 5 ；該方法簡單快速，但由 于映射過程失真形， 曲面適應(yīng)能力較差， 生成的網(wǎng)格質(zhì)量不 高。李鴻亮等 6 以正三角形單元為基礎(chǔ)，基于映射法建立圓 柱和圓臺的三角剖分， 但該策略在曲面邊界處會出現(xiàn)不規(guī)則 狹小三角片。關(guān)振群等 7通過引入虛邊界 , 解決了閉合曲面 由于映射參數(shù)平面域邊界不完整的問題?；?AFM 波前法 8-10的曲面網(wǎng)格方法從區(qū)域邊界開始， 采用遞歸的方式不斷地向內(nèi)部收縮產(chǎn)生新的三角形， 直到填 滿整個區(qū)域。 該方法具有良好的曲面適應(yīng)能力， 因此越來越 多的被應(yīng)用于曲面的三角形網(wǎng)格自動生成過程中。 但是

8、由于 該方法缺乏成熟的理論支撐， 涉及到數(shù)據(jù)的存儲方式、 波前 的查找方法、 波前之間的相交判斷等， 算法實現(xiàn)依賴于實踐 經(jīng)驗的積累。 吳海寶等 11提出一種從曲面兩條邊界向曲面中 心推進的改進波前法， 避免了常規(guī)波前法由于曲面角點不良 導(dǎo)致的網(wǎng)格規(guī)劃失敗問題。王偉等 12結(jié)合直接法和映射法 各自的優(yōu)點來消除傳統(tǒng)波前法的映射畸變問題。 劉湘梅等 13 基于 AFM 法層層推進原理，提出一種非層次遞歸剖分的球面三角剖分算法， 避免了耗時的單元合法性檢查。 覃先云等14利用多維搜索二叉樹數(shù)據(jù)結(jié)構(gòu)實現(xiàn)臨近前沿和節(jié)點的快速查找，并引進點修正算子來改善周期曲面的網(wǎng)格質(zhì)量。 本文針對常用的基本體素：圓柱、

9、圓錐（圓臺） ，提出 一種新的曲面網(wǎng)格生成算法。 該方法根據(jù)曲面的表面形態(tài)特 征，以正三角形單元為基礎(chǔ)， 基于波前法自動生成網(wǎng)格模型。 該方法能夠避免 AFM 法的遞歸剖分引入的累積變形，也無 需進行耗時的合法性檢查， 能夠快速的生成較高質(zhì)量的曲面 網(wǎng)格。1 算法描述傳統(tǒng)波前法的基本流程是：首先離散待剖分區(qū)域的邊 界（稱為波前） ，然后從波前開始 , 探索式插入節(jié)點以生成 新單元 ; 由此循環(huán)向內(nèi)部收縮直到填滿整個區(qū)域。 為避免傳 統(tǒng)方法費時的合法性檢測， 本文根據(jù)圓柱和圓錐每個表面的 形態(tài)特點， 基于波前法層層推進原理， 利用節(jié)點排列規(guī)律直 接在三維空間生成節(jié)點和新單元。1.1 圓面的三角網(wǎng)

10、格生成算法圓柱和圓臺的上下底面都為圓面， 故首先研究圓面的網(wǎng) 格生成算法。 為使每個三角形單元近似為正三角形， 采用如 下的非遞歸剖分策略： 首先將圓面均勻分割為 M 個扇形 （為 使圓心處的三角片為等邊三角形， 取 M = 6） ，然后再將圓面 等間距劃分 N 個同心圓弧 （波前） ；最后按照波前法的思想由 內(nèi)向外層層推進以生成三角網(wǎng)格，如圖 1 所示?；痦椖浚?國家自然科學(xué)基金資助項目 （51405197） ；浙江省自然科學(xué)基金資助項目 （LQ14E050006）作者簡介 : 吳婷（1979）,女, 河南洛陽人 , 講師，博士, 主要研究方向為數(shù)字化設(shè)計與制造 , 生物醫(yī)學(xué)工程 （wut

11、ing628） ；張禮兵 （1974）, 男, 講師 , 博士, 主要研究方向為數(shù)字化設(shè)計與制造 .頁碼計算機應(yīng)用研究(a)分割 M 個扇形(b)劃分 N 個圓弧 (波前 )圖 1 本文基于波前法的圓面網(wǎng)格生成原理第 28 卷(a)邊長參數(shù) a=3(b)邊長參數(shù) a=2 (c) 邊長參數(shù) a=1圖 3 圓環(huán)面 (R=4，r=2) 三角網(wǎng)格生成結(jié)果設(shè)圓半徑為 R，圓心坐標(biāo)為 (0， 0)。將圓心設(shè)為初始波 前 i = 0 ，相鄰波前之間的徑向間距為r 。從圖 1b 可以看出如下排列規(guī)律： 在每一個等分扇形中， 第一個波前上三角形 的邊數(shù)為 1，第二個波前上三角形的邊數(shù)為 2 ，即波前上三 角形邊

12、的個數(shù)由里向外依次遞增。假定外圓周上三角形邊長為 a，可將波前之間的徑向間 距近似為：1.2 圓柱面的三角網(wǎng)格生成算法由于圓柱面為三維曲面，因此直接進行剖分容易產(chǎn) 生不穩(wěn)定問題。傳統(tǒng)方法是基于映射法首先將圓柱側(cè)面 展開成矩形，對矩形進行三角剖分，然后再映射到三維 空間；然而該方法對這種封閉回轉(zhuǎn)曲面需要進行分片處 理，或者對閉曲面邊界進行調(diào)整才能達(dá)到無縫連接 14-15。本文采用如下剖分策略：將下底面圓周等分若干個 頂點，并作為初始波前，然后基于波前法依次向上層層 推進生成三角網(wǎng)格。其剖分原理如圖 4 所示。r 23 a(1)設(shè)相鄰波前間距都相等，則波前總數(shù)為：N R / r(2)其中 為向上取

13、整，則實際波前徑向間距為r R/N (3) 根據(jù)上述剖分規(guī)則可知，第 i 個波前上的圓弧半徑和其上面 的三角形邊的個數(shù)分別為：ri i rni iMi 1,2, ,N(4)根據(jù)幾何關(guān)系，可得第 i 個波前上，第 j 個網(wǎng)格頂點坐標(biāo) 為：xij ri cos(j 1) ( /i) i 1,2, ,N ,( yij ri sin (j 1) ( /i) j 1,2, ,ni其中， 2 /M 為扇形分角。 利用上式計算出圓面的網(wǎng)格頂點后， 按順序由里向外依 次連接前后波前上的網(wǎng)格頂點即可生成三角網(wǎng)格。圖 4 本文基于波前法的圓柱面網(wǎng)格生成原理圖 2 顯示了在不同網(wǎng)格邊長參數(shù) a 下，對半徑 R=5

14、的 圓面生成三角網(wǎng)格的結(jié)果， 可以看出， 無論網(wǎng)格間距是較大設(shè)圓柱半徑為 R，高為 H ，每個三角形邊長為 a，則 圓周上的離散頂點總數(shù)為：Nc 2 R / a(6)圓周上每條邊所對應(yīng)的圓心角：2 / Nc(7)為使圓柱面網(wǎng)格三角形都近似為正三角形， 將相鄰層的波前 間距設(shè)為：還是較小，都能較好地保證網(wǎng)格的質(zhì)量(a)邊長參數(shù) a=3(b)邊長參數(shù) a=2(c)邊長參數(shù) a=1圖2 圓面(半徑R=5)三角網(wǎng)格生成結(jié)果由此可得，波前總數(shù)為：Nz H / z 其中. 為向上取整，則實際波前間距為 z H / Nz(8)(9)(10)對于圓環(huán)面的三角剖分， 其方法與實心圓面的網(wǎng)格生成 策略相同，這里不

15、再贅述。圖 3 顯示了對外圓半徑 R=5 、內(nèi) 圓半徑 r =2的圓環(huán)面進行三角網(wǎng)格生成結(jié)果。 可以看出， 本 文方法無需傳統(tǒng)波前法耗時的相交性檢查以及龐大的數(shù)據(jù) 結(jié)構(gòu)存儲， 只需根據(jù)圓面的內(nèi)外半徑和初始邊長， 即可快速 的生成較高質(zhì)量的網(wǎng)格。同時，下一層波前上的頂點相對于上層波前頂點的圓心角旋 轉(zhuǎn) / 2。由此可得，圓柱表面上第 i 個波前上，第 j 個網(wǎng)格頂點 的三維坐標(biāo)為：1 1 (4 1)1 1 (4 1)zij i z,i 0,1, ,Nz , j 1,2, ,Nc(11)圖 5 顯示了在不同邊長參數(shù) a 下，本文方法對圓柱面 ( 外 圓半徑 R=5、高 H =2)進行三角剖分的結(jié)果

16、。頁碼計算機應(yīng)用研究第 28 卷(a)邊長參數(shù) a=2(b)邊長參數(shù) a=1(c)邊長參數(shù) a=0.5圖5 圓柱面(R=5, H =10)三角網(wǎng)格生成結(jié)果圖 7 顯示了在不同邊長參數(shù) a0 下，對圓錐面 (下底面 半徑 R=5, 高 H =5)進行三角剖分的結(jié)果。圖7 圓錐面(R=5, r=2，H=5)三角網(wǎng)格生成結(jié)果1.3 圓錐面的三角網(wǎng)格生成算法圓錐面的網(wǎng)格生成原理與圓柱面類似， 但由于圓錐面向 錐頂點方向逐漸收縮， 如果完全按照圓柱面那樣劃分等間距 波前，會造成三角片的形狀向錐頂方向逐漸變窄。因此， 圓錐面的波前位置采用如下的方法計算，其原理如圖 6 所示。圖6 本文基于波前法的圓錐面網(wǎng)

17、格生成原理2 網(wǎng)格質(zhì)量分析 由于對同剖分精度的網(wǎng)格模型來說，剖分邊的變化 越小，則所構(gòu)成的剖分單元與等邊三角形的相似性越高， 網(wǎng)格的質(zhì)量越好。因此采用文獻(xiàn) 7 的方法進行網(wǎng)格質(zhì)量 評價。對于網(wǎng)格中的任意三角單元ABC，定義其形狀質(zhì)量系數(shù)為：=2 3 2 CA C2B 2CA2 AB2 BC 2 則整個網(wǎng)格的形狀質(zhì)量系數(shù)為：12 =NT N T1ii1(17)(18)設(shè)圓錐上底面半徑為 r ，下底面半徑為 R，高為 H 。 當(dāng)這三個基本特征參數(shù)確定后，可得出圓錐母線長：L (R r)2 H 2(12)圓錐母線與底面的夾角：arcsin(H / L)(13)將下底面圓周按間距 a0 進行離散，并將

18、其離散頂點作為 初始波前 i = 0。為使網(wǎng)格三角形近似為正三角形，將第 i 層波前和第 i-1層波前沿母線方向的間距Li 設(shè)為：Li 3ai 1(14)2其中， ai-1 為第 i-1 層波前的三角形邊長。 為避免層層向上推進時圓錐頂部的三角形過小，按 照如前所述的圓面網(wǎng)格生成原理，將圓錐面每層波前上n。三角形邊的個數(shù)由下向上依次遞減，遞減數(shù)為 根據(jù)上述剖分規(guī)則， 第 i 層波前上的三角形邊的個數(shù)Ni、波前三角形邊長 ai，波前圓弧半徑 ri，以及波前上頂點的 Z 坐標(biāo) zi ，可按如下遞歸公式進行求解：N 0 2aR0 a0Ni Ni 1 n,a 2 riiiNi3ri ri 1 aii

19、i 1 2 izi zi 1 3ai 1 sin , z0 0i i1 2 i 1 0當(dāng) ziH 或 Ni(為波前上三角形邊個數(shù)的最小閾值) 時，迭代停止。這樣由幾何關(guān)系可得，圓錐表面上第 個波前上，第 j 個網(wǎng)格頂點的坐標(biāo)為：cos , r0 R(15)i jrci oyi j rsi i zi j z ii, 0,1, 2, j, 1, 2,Ni ,(16)其中， NT 為網(wǎng)格總數(shù)。如果網(wǎng)格中每個三角片越接近正三 角形，則網(wǎng)格形狀質(zhì)量系數(shù)越接近于 1。為驗證本文算法的 有效性和優(yōu)越性，將文獻(xiàn) 4 ，文獻(xiàn) 5和本文方法的剖分網(wǎng) 格質(zhì)量進行比較，結(jié)果如下。圖 8 為圓面的網(wǎng)格分析對比結(jié)果。圖

20、8a 是基于文獻(xiàn) 5 的參數(shù)方程法生成的網(wǎng)格， 該方法簡單快速， 只需根據(jù)圓的 極坐標(biāo)參數(shù)方程生成網(wǎng)格頂點，然后利用 Delaunay 三角剖 分即可生成網(wǎng)格； 然而這種方法會導(dǎo)致網(wǎng)格中每個三角片都 近似為直角三角形， 而且在圓心附近的三角片將變得十分細(xì) 小，因此質(zhì)量系數(shù)較低。圖 8b 是采用文獻(xiàn) 6的映射法，該 方法首先將圓形區(qū)域映射在已生成好的正三角形矩形區(qū)域 網(wǎng)格內(nèi)， 然后裁剪掉圓形外的多余三角形； 雖然該方法的網(wǎng) 格質(zhì)量系數(shù)較高， 但該方法會在圓邊界處出現(xiàn)很多不規(guī)則狹 小三角片。本文方法無須進行邊緣的相交判斷和合法性檢 查，生成的網(wǎng)格系數(shù)表明每個單元的形狀都較好。圖 9 為圓柱面的網(wǎng)格

21、分析對比結(jié)果。圖 9a 的文獻(xiàn) 5 方 法首先將柱面映射到平面域， 利用參數(shù)方程對矩形進行三角 剖分， 然后再映射回三維空間； 該方法同樣導(dǎo)致網(wǎng)格每個三 角片都近似為直角三角形，網(wǎng)格質(zhì)量系數(shù)不高。圖9b 的文獻(xiàn)6方法在映射矩形參數(shù)域上進行正三角剖分，但由于封 閉曲面的參數(shù)域是周期無界的， 因此該方法導(dǎo)致曲面閉合接 縫處產(chǎn)生為直角三角形。 本文的波前法從曲面的另一非周期 方向開始剖分， 避免了文獻(xiàn) 714 對封閉曲面邊界的調(diào)整問 題，無需坐標(biāo)變換和合法性檢查就能保證每個三角單元近似 等邊三角形。圖 10 為圓錐面的網(wǎng)格分析對比結(jié)果。 可以看出， 圖 10a 文獻(xiàn)5方法生成的網(wǎng)格質(zhì)量系數(shù)最低。 圖

22、 10b為文獻(xiàn) 6 結(jié) 合映射法和遞推法生成的網(wǎng)格， 其網(wǎng)格質(zhì)量系數(shù)最高， 但網(wǎng) 格數(shù)量向錐頂點方向無限增多， 其網(wǎng)格總數(shù)大致是本文方法 的 4 倍。本文方法通過控制相鄰波前上網(wǎng)格頂點數(shù)量， 有效 避免了圓錐頂點附近網(wǎng)格過密問題， 而且無需坐標(biāo)變換就能 生成較高質(zhì)量的網(wǎng)格。綜上所述，本文方法在剖分基本曲面時所生成網(wǎng)格在 整體布局上層次分明， 單元排列整齊， 網(wǎng)格整體質(zhì)量系數(shù)較 高，凸顯了波前法和映射法的優(yōu)點， 同時又避免了各自的不 足。頁碼計算機應(yīng)用研究第 28 卷快速成型加工出來的導(dǎo)板表明， 該設(shè)計方法高效穩(wěn)定、 自動 化程度高，生成模型網(wǎng)格均勻，質(zhì)量較好。(a)文獻(xiàn)5法(b)文獻(xiàn)6法(c)

23、本文方法圖 8 圓面網(wǎng)格生成結(jié)果對比(a)文獻(xiàn)5法(b)文獻(xiàn)6法(c)本文方法圖 9 圓面網(wǎng)格生成結(jié)果對比圖 12 本文方法應(yīng)用于口腔種植導(dǎo)板4 結(jié)束語(a)文獻(xiàn)5法(b)文獻(xiàn)6法(c)本文方法本文采用正三角形的剖分策略， 以波前法為基礎(chǔ)， 研究 了圓面、 圓柱面和圓錐面的三角形網(wǎng)格生成算法 , 并對算 法進行了具體實現(xiàn)和實際應(yīng)用。 在實際使用中， 只需根據(jù)圓 柱和圓錐的尺寸， 以及用戶指定的三角形邊長， 即可快速獲 得所需結(jié)構(gòu)的三角網(wǎng)格模型。 該設(shè)計方法高效穩(wěn)定、 自動化 程度高，生成模型網(wǎng)格均勻，質(zhì)量較好，這對于逆向工程、 三維重構(gòu)、快速成型等領(lǐng)域具有重要的意義。參考文獻(xiàn) :圖 10 圓面

24、網(wǎng)格生成結(jié)果對比圖 11 圓柱和圓錐網(wǎng)格生成實例3 實例應(yīng)用將本文的曲面剖分方法合并在一起， 可以快速生成各種 形狀的實心或空心圓柱 (圓錐) 的表面網(wǎng)格， 其三角化結(jié)果 如圖 11 所示。在網(wǎng)格生成過程中，先從圓柱(圓錐)的底 面開始剖分，基于波前法層層推進，依次剖分側(cè)面、頂面， 直到剖分完整個曲面。 可以看出， 本文方法能用于各種圓柱 圓錐組合曲面的網(wǎng)格生成， 無需耗時的相交性檢查就能使各 個表面的網(wǎng)格點無縫連接， 使用時只需根據(jù)圓柱圓錐的基本 尺寸參數(shù)和初始網(wǎng)格邊長，即可生成整個曲面網(wǎng)格。將本文方法應(yīng)用于自主開發(fā)的口腔種植CAD/CAM 系統(tǒng)中，可以快速實現(xiàn)數(shù)字化修復(fù)設(shè)計，如圖12 所示

25、。在數(shù)字化口腔種植修復(fù)系統(tǒng)中， 為了保證種植牙植入位置的準(zhǔn)確 性，可以根據(jù)修復(fù)方案設(shè)計種植導(dǎo)板， 佩戴在病人口腔中使 用，以確保手術(shù)的成功。 將種植導(dǎo)板的定位結(jié)構(gòu)設(shè)計為空心 圓柱或空心圓錐， 能夠方便引導(dǎo)手術(shù)鉆頭的植入方向。 利用 本文的方法可以快速生成該定位結(jié)構(gòu)的網(wǎng)格模型， 然后和患 者口腔模型進行布爾運算即可形成相應(yīng)的種植導(dǎo)板。 從最后1 關(guān)振群, 宋超, 顧元憲,等. 有限元網(wǎng)格生成方法研究的新進展 J. 計算機輔助設(shè)計與圖形學(xué)學(xué)報 , 2003, 15(1): 1-14.2 黃曉東 ,丁問司 , 杜群貴 . 基于波前法的參數(shù)曲面有限元網(wǎng)格生成 算法J. 計算機輔助設(shè)計與圖形學(xué)學(xué)報 ,

26、2010, 22(1):51-59.3 Green P J, Sibson R. Computing Dirichlet tessellations in the plane J. The Computer Journal , 1977, 21(2): 168-173.4 Lawson C L. Generation of a triangular grid with applications to contour plotting , Technical Memo 299 R.1972.5 王偉, 劉春, 王艷秋 . 快速實現(xiàn)二次曲面片三角網(wǎng)格剖分的新方法J. 沈陽航空工業(yè)學(xué)院學(xué)報 , 2009, 26(2): 16-19.6 李鴻亮 , 陸金桂 , 宣兆新 , 等 . 基本體素的三角形面單元剖分方法 J.計算機集成制造系統(tǒng) , 2011, 17(2)：261-