基于區(qū)域生長的三角網(wǎng)格模型孔洞修補(bǔ)方法

劉云華,呂 劍,朱 林,羅年猛

(華中科技大學(xué)國家CAD支撐軟件工程技術(shù)研究中心,武漢430074)

基于區(qū)域生長的三角網(wǎng)格模型孔洞修補(bǔ)方法

劉云華,呂 劍,朱 林,羅年猛

(華中科技大學(xué)國家CAD支撐軟件工程技術(shù)研究中心,武漢430074)

為復(fù)原殘缺三角網(wǎng)格模型的原始形狀,針對丟失尖銳特征的模型,提出一種基于區(qū)域生長的孔洞修補(bǔ)方法。在根據(jù)模型的拓?fù)溥B接關(guān)系提取孔洞邊界信息后,利用廣度優(yōu)先算法以孔洞邊界為起點(diǎn)對孔洞周邊網(wǎng)格進(jìn)行區(qū)域劃分,由對應(yīng)孔洞特征區(qū)域的幾何性質(zhì)計(jì)算新補(bǔ)丁面片的法矢,并據(jù)此逐層迭代地向孔洞內(nèi)部進(jìn)行異步生長,同時(shí)為每個(gè)孔洞邊界網(wǎng)格設(shè)置一個(gè)控制信號控制區(qū)域生長的異步性,對不同區(qū)域的新面片求交恢復(fù)以確定尖銳特征線和特征角。實(shí)驗(yàn)結(jié)果表明,對于尖銳特征丟失的殘缺模型,該方法在修補(bǔ)孔洞的同時(shí)能夠完整地恢復(fù)模型的原始形狀。

孔洞修補(bǔ);區(qū)域劃分;區(qū)域生長;異步性;特征恢復(fù);三角網(wǎng)格

1 概述

隨著逆向工程的發(fā)展,三角網(wǎng)格表達(dá)形式已經(jīng)越來越多地應(yīng)用到工業(yè)領(lǐng)域,如輕量化顯示、三維工藝系統(tǒng)等,并且貫穿于模型的整個(gè)生命周期。當(dāng)前已經(jīng)有很多描述三角網(wǎng)格的文件格式,包括STL, HSF,DWF,VRML,3DS,3DXML,U3D,JT,CGR等。三角網(wǎng)格的主要來源是三維測量設(shè)備,但是由于測量技術(shù)與精度的限制以及采樣點(diǎn)信息不充足,點(diǎn)云連接后生成的網(wǎng)格模型可能會(huì)產(chǎn)生孔洞。這些孔洞會(huì)影響模型的后續(xù)使用,如模型重建、有限元分析、快速成型等。因此,孔洞修補(bǔ)是一項(xiàng)重要的研究課題,國內(nèi)外對此進(jìn)行了大量的研究。

文獻(xiàn)[1]提出了一種先將孔洞多邊形三角化,再通過調(diào)整和光順三角網(wǎng)格來達(dá)到美學(xué)效果的修補(bǔ)方法。文獻(xiàn)[2]提出了一種首先用波前法進(jìn)行修補(bǔ),再通過泊松方程進(jìn)行法矢調(diào)整的修補(bǔ)方法。文獻(xiàn)[3]采用改進(jìn)的波前法進(jìn)行孔洞修補(bǔ),利用隨機(jī)-最小角原則提高修補(bǔ)網(wǎng)格的質(zhì)量。文獻(xiàn)[4-7]利用分治的思想修補(bǔ)復(fù)雜孔洞,將復(fù)雜孔洞分解成簡單的子孔洞再對各個(gè)子孔洞分別進(jìn)行修補(bǔ),最后將子孔洞的補(bǔ)丁面片縫合起來。文獻(xiàn)[8]提出一種用線性力學(xué)模型來模擬三角網(wǎng)格模型的算法,將幾何問題轉(zhuǎn)化成物理問題進(jìn)行求解。文獻(xiàn)[9]提出了一種體擴(kuò)展的方法來修補(bǔ)孔洞,該方法將孔洞邊界向內(nèi)部擴(kuò)展,直到孔洞完全封閉為止。文獻(xiàn)[10]提出了一種將網(wǎng)格模型轉(zhuǎn)成八叉樹結(jié)構(gòu)的孔洞修補(bǔ)算法。

近年來,研究者們開始關(guān)注在修補(bǔ)孔洞的同時(shí)恢復(fù)模型原始尖銳特征的問題,并進(jìn)行了一些研究。文獻(xiàn)[11]提出一種首先采用徑向基函數(shù)進(jìn)行孔洞修補(bǔ),再根據(jù)尖銳特征過濾器恢復(fù)出模型的原始特征。文獻(xiàn)[12]也提出了一種通過雙邊濾波器恢復(fù)尖銳特征的方法。這類方法僅利用了孔洞邊界第一層三角面片的信息,在此基礎(chǔ)上構(gòu)造出的濾波器調(diào)整特征邊附近面片的法矢時(shí)不可避免地會(huì)產(chǎn)生誤差。文獻(xiàn)[13-14]提出了一種利用分治思想修補(bǔ)并恢復(fù)孔洞原始尖銳特征的方法。該方法首先根據(jù)特征點(diǎn)擬合出特征曲線的混合多項(xiàng)式,并將復(fù)雜孔洞分成簡單小孔洞,然后再用最小二乘法擬合出三次bezier曲面來修補(bǔ)每個(gè)簡單子孔洞。文獻(xiàn)[15]提出了一種用特征點(diǎn)的匹配方式將復(fù)雜孔洞分解成簡單子孔洞,再通過波前法修補(bǔ)每個(gè)簡單孔洞的方法。這類方法對應(yīng)信息丟失不多的情況效果較好,但是如果信息丟失過多導(dǎo)致特征點(diǎn)無法匹配就難以獲得理想的結(jié)果。本文提出一種基于區(qū)域生長的修補(bǔ)方法,在識(shí)別孔洞后對孔洞周邊區(qū)域進(jìn)行分割,然后利用影響孔洞幾何形狀的全局信息計(jì)算孔洞新面片的法矢,并據(jù)此逐層迭代地向孔洞內(nèi)部進(jìn)行異步生長,最后求交恢復(fù)孔洞補(bǔ)丁區(qū)域尖銳特征。

2 算法描述

對于連通的流形三角網(wǎng)格模型,在曲率變化不劇烈時(shí)能取得較好的效果。算法流程如圖1所示。修補(bǔ)過程示意圖如圖2所示。在圖2(b)中,實(shí)線環(huán)為識(shí)別的邊界環(huán);在圖2(c)中,Ⅰ,Ⅱ,Ⅲ3個(gè)面分別代表孔洞周邊的3個(gè)特征區(qū)域,其他為未被劃分的區(qū)域;在圖2(d)中,與3個(gè)特征區(qū)域相連的新面片為區(qū)域生長的補(bǔ)丁面片;在圖2(e)中,不同補(bǔ)丁區(qū)域求交確定出特征線和特征點(diǎn)。

圖1 流形三角網(wǎng)格模型算法流程

圖2 修補(bǔ)過程示意圖

定義1 給定的一條邊ei如果屬于2個(gè)三角面片,則ei稱為內(nèi)部邊;如果只屬于一個(gè)三角面片,則ei稱為邊界邊,對應(yīng)的三角面片稱為邊界面;由邊界邊首尾相連構(gòu)造的封閉多邊形稱為邊界環(huán)(如圖2(b)粗實(shí)線環(huán));邊界環(huán)內(nèi)部的區(qū)域(即待修補(bǔ)的區(qū)域)稱為補(bǔ)丁區(qū)域;填充補(bǔ)丁區(qū)域的三角面片稱為補(bǔ)丁面片(如圖2(e)新面片)。

定義2 如果相鄰兩面片的二面角小于用戶指定的臨界值θ,則這2個(gè)面片屬于同一區(qū)域,否則屬于不同區(qū)域。如果某區(qū)域包含邊界面,則稱為孔洞特征區(qū)域(簡稱特征區(qū)域);如果特征區(qū)域的參數(shù)方程小于3次,則稱為簡單特征區(qū)域,否則稱為復(fù)雜特征區(qū)域;2個(gè)相鄰特征區(qū)域的公共邊稱為特征邊;依次連接相鄰的特征邊構(gòu)成的多段線稱為特征線;3個(gè)或3個(gè)以上相鄰特征區(qū)域的公共點(diǎn)稱為特征角。

識(shí)別原始模型的孔洞。根據(jù)三角網(wǎng)格的拓?fù)溥B接關(guān)系,搜索一條邊界邊,再以該邊界邊為起點(diǎn)搜索其相鄰的邊界邊,直至構(gòu)成一個(gè)邊界環(huán)為止[2],即識(shí)別出一個(gè)孔洞。

對孔洞周邊區(qū)域進(jìn)行分割。依次從未被劃分的邊界面出發(fā)以廣度優(yōu)先方式搜索與其相鄰且未被劃分的三角面片,如果兩相鄰面片的二面角小于θ,則其應(yīng)屬于同一特征區(qū)域,否則,應(yīng)屬于不同特征區(qū)域(如圖2(c)所示)。

2.1 新補(bǔ)丁面片的法矢計(jì)算

通過分析特征區(qū)域計(jì)算生長步驟中新補(bǔ)丁面片的法矢。工程中常見的孔洞模型的特征區(qū)域多為簡單特征區(qū)域,為了保證修補(bǔ)的準(zhǔn)確性,首先以曲面擬合的方法對特征區(qū)域進(jìn)行簡單特征區(qū)域分析,如果不滿足要求再進(jìn)行復(fù)雜特征區(qū)域分析。

2.1.1 簡單特征區(qū)域分析

同一特征區(qū)域內(nèi)的所有點(diǎn){p1,p2,…,pi,…,ps},通過最小二乘擬合的一次和二次參數(shù)曲面方程分別為:

擬合誤差為:

首先用式(1)擬合特征區(qū)域,如果ε小于用戶指定最大允許誤差εmax1,則一次擬合成功;否則一次擬合失敗,用式(2)進(jìn)行二次擬合,如果ε小于用戶指定最大允許誤差εmax2,則二次擬合成功。對于一次或者二次擬合成功的特征區(qū)域,其新補(bǔ)丁面片法矢根據(jù)特征區(qū)域的參數(shù)方程計(jì)算得出。否則,進(jìn)入復(fù)雜特征區(qū)域分析。

2.1.2 復(fù)雜特征區(qū)域分析

根據(jù)用戶指定的數(shù)量計(jì)算一組過A點(diǎn)和N的平面集{Γi},稱為割平面集,記錄本特征區(qū)域中與每個(gè)割平面相交的面片集{fk},如圖3所示。從{Γi}中選擇最優(yōu)割平面Γ,選擇原則為:(1)相交面片數(shù)量最多;(2)面片集法矢的波動(dòng)性最小;當(dāng){Γi}所有割平面的相交面片集數(shù)量較少時(shí),原則(1)為主要因素,較多時(shí)原則(2)為主要因素。

圖3 孔洞區(qū)域示意圖

分析最優(yōu)割平面Γ相交面片集{fk}各面片的法矢n和距A點(diǎn)距離d,在二維空間依次分析法矢各分量的對稱性、周期性和單調(diào)性等性質(zhì),以x方向?yàn)槔?如圖4所示,實(shí)線表示已知值,虛線表示計(jì)算值,并計(jì)算新補(bǔ)丁面片的法矢。

圖4 法矢分析

2.2 孔洞修補(bǔ)

本文首先通過特征區(qū)域計(jì)算孔洞補(bǔ)丁面片的法矢,然后據(jù)此采用迭代方式逐層向孔洞內(nèi)部進(jìn)行異步生長,最后不同區(qū)域面片求交恢復(fù)原始模型的尖銳特征。

2.2.1 孔洞邊界預(yù)處理

為了使區(qū)域生長過程能夠順利進(jìn)行,需要對孔洞邊界做預(yù)處理,依次包含3個(gè)方面的處理:合并極近點(diǎn),分裂長邊界,連接小夾角。

(1)合并極近點(diǎn):計(jì)算任意2個(gè)孔洞邊界點(diǎn)之間的歐氏距離,如果小于給定的臨界值d1,則將這2個(gè)點(diǎn)合并到其算術(shù)平均值所確定的點(diǎn),如圖5中的圓環(huán)區(qū)域。

(2)分裂長邊界:計(jì)算每個(gè)孔洞邊界邊的長度,如果其大于給定的長度臨界值d2,將其分裂成多條符合長度的短邊界,使最終的邊界邊長度基本一致,如圖5中的虛線。

(3)連接小夾角:計(jì)算依次相鄰的2條邊界邊PiPi+1,Pi+1Pi+2的夾角,如果小于120°,連接Pi和Pi+2,構(gòu)造新的三角形,直至所有夾角都大于120°,如圖5中的點(diǎn)劃線。

圖5 孔洞邊界預(yù)處理

預(yù)處理孔洞邊界同時(shí)更新相應(yīng)的邊界面片,以免產(chǎn)生非流形結(jié)構(gòu)。

2.2.2 基于區(qū)域生長的孔洞修補(bǔ)

孔洞特征區(qū)域同步生長會(huì)造成孔洞修補(bǔ)失敗,因此,本文采用異步方式生長,引入控制信號控制生長異步性,每個(gè)邊界面片記錄其所對應(yīng)的控制信號并根據(jù)信號指示生長?？刂菩盘柗譃榧t色信號(Rsignal),綠色信號(Gsignal)和黃色信號(Ysignal)3種。

(1)控制信號判定面的計(jì)算設(shè)置

為每個(gè)特征區(qū)域邊界面擬合一張直紋面,其方程如下:

其中,a(u,v)為直紋面的準(zhǔn)線;l(u)為直紋面母線方向的單位向量。

特征區(qū)域邊界邊的直紋面示意圖如圖6所示。

圖6 特征區(qū)域邊界邊的直紋面

取特征區(qū)域邊界邊為準(zhǔn)線(圖6的粗實(shí)線),取垂直于邊界邊起終點(diǎn)連線(圖6的細(xì)實(shí)線)且屬于每個(gè)邊界面所在平面的直線集為母線(圖6的虛線);本文用三角面片集擬合該直紋面(圖6中由2種虛線組成)。邊界邊PiPi+1所對應(yīng)的邊界面片法矢為n=(xn,yn,zn),則該邊界邊對應(yīng)的直紋面三角面片ΔPiPi+1P′i(其中,Pi,Pi+1,P′i點(diǎn)的坐標(biāo)分別為Pi(xi,yi,zi),Pi+1(xi+1,yi+1,zi+1)和Pi′(x′i,y′i,z′i))的方程為:

三角面片ΔPiPi+1P′i記為Ti,ΔPi′P′i+1Pi+1的方程與ΔPiPi+1P′i類似,記為T′i。則第k個(gè)特征區(qū)域所對應(yīng)的直紋面為{T1,T2,…,Ti,…,Tm,T1′,T2′,…,Ti′,…,T′m}記為Sk,其中,m為本特征區(qū)域邊界點(diǎn)的數(shù)量。該直紋面的首個(gè)及末個(gè)三角面片T′1和Tm為開區(qū)間,向兩側(cè)無限延展。

(2)孔洞修補(bǔ)算法步驟

孔洞修補(bǔ)算法步驟如下:

1)單一特征區(qū)域逐層迭代異步生長

Step 1 預(yù)處理孔洞邊界。

Step 2 初始化孔洞邊界面片的控制信號,將邊界面片的控制信號都設(shè)為Gsignal。

Step 3 孔洞的每個(gè)特征區(qū)域進(jìn)行區(qū)域生長(本步驟以第i個(gè)特征區(qū)域?yàn)槔M(jìn)行說明),根據(jù)邊界面片控制信號不同,分3種情況進(jìn)行區(qū)域生長,以實(shí)現(xiàn)區(qū)域生長的異步性:

①當(dāng)邊界面片的控制信號為Gsignal時(shí),根據(jù)2.1節(jié)的徑向法矢預(yù)測以等邊三角形向內(nèi)生長,并判斷補(bǔ)丁面片是否與Ω/i相交。如果不相交,將補(bǔ)丁面片控制信號設(shè)置為Gsignal;否則,設(shè)置為Ysignal。

②當(dāng)邊界面片的控制信號為Ysignal時(shí),判斷該面片與對應(yīng)的原始邊界面片是否分居Ω/i兩側(cè),如果分居兩側(cè),則刪除該邊界面片,并將其母面片的控制信號設(shè)置成Ysignal;否則設(shè)置成Rsignal。

③當(dāng)邊界面片的控制信號為Rsignal時(shí),該面片停止生長。

所有孔洞特征區(qū)域的邊界面片每向內(nèi)生長一層更新邊界面片和對應(yīng)的直紋面。

Step 4 重復(fù)Step3,并在每次生長之前對孔洞邊界進(jìn)行預(yù)處理,直至所有邊界面片的控制信號都為Rsignal為止,單一特征區(qū)域生長結(jié)束(如圖2(d)所示)。

2)不同特征區(qū)域的補(bǔ)丁面片求交,恢復(fù)模型的原始特征。

當(dāng)孔洞特征區(qū)域所有邊界面片的所有控制信號都為Rsignal時(shí),采用求交的方式恢復(fù)特征,首先恢復(fù)特征線,然后恢復(fù)特征角(如圖2(e)所示)。

Step 1 每個(gè)最新的孔洞邊界面產(chǎn)生的新面片與其他區(qū)域新面片進(jìn)行求交得出相鄰特征區(qū)域的交線。依次連接所有的交線即得孔洞區(qū)域的特征線。當(dāng)特征區(qū)域的2個(gè)相鄰面片與不同區(qū)域的面片相交時(shí),說明這2個(gè)面片處在特征角附近,記錄特征角信息。

Step 2 根據(jù)恢復(fù)特征線時(shí)記錄的特征角信息,確定特征角的位置和其相關(guān)的特征區(qū)域面片信息。將這些特征區(qū)域面片進(jìn)行求交確定出特征角,如果特征角的相關(guān)特征區(qū)域數(shù)量大于3,則每3個(gè)面片進(jìn)行求交之后,取交點(diǎn)的算術(shù)平均值為特征角位置。

3 實(shí)驗(yàn)結(jié)果與分析

本文主要目是在修補(bǔ)孔洞的同時(shí)有效地恢復(fù)模型的原始尖銳特征,該部分展示了復(fù)原模型尖銳特征的效果,并與其他恢復(fù)尖銳特征的孔洞修補(bǔ)算法結(jié)果進(jìn)行比較。

圖7為丟失尖銳特征角的B樣條曲面的修補(bǔ)效果,通過復(fù)雜區(qū)域分析步驟計(jì)算補(bǔ)丁面片的法矢,當(dāng)特征區(qū)域的曲率變化較為平緩時(shí),修補(bǔ)結(jié)果幾乎能夠完全復(fù)原模型的原始形狀。圖8為發(fā)動(dòng)機(jī)曲軸模型丟失少量尖銳特征信息時(shí)的修補(bǔ)效果,補(bǔ)丁面片的法矢通過特征區(qū)域的參數(shù)方程計(jì)算得出,修補(bǔ)結(jié)果比較精確。

圖7 B樣條曲面的修補(bǔ)效果

圖8 曲軸模型修補(bǔ)效果

圖9 (a)、圖9(b)為文獻(xiàn)[11]方法修補(bǔ)立方體尖銳角特征的效果,可以看出修補(bǔ)后的尖角明顯不符合模型的原始形狀;圖9(c)、圖9(d)為本文算法在類似模型上的修補(bǔ)效果,由于可以精確計(jì)算出孔洞特征區(qū)域的參數(shù)方程,修補(bǔ)的結(jié)果能夠完全復(fù)原出模型的原始尖銳角特征。圖10(a)、圖10(b)為文獻(xiàn)[15]方法修復(fù) fandisk模型特征角的效果,圖10(c)、圖10(d)為本文算法在類似模型上的修補(bǔ)效果,可以看出本文算法的修補(bǔ)效果優(yōu)于文獻(xiàn)[15]方法的修補(bǔ)效果。

圖9 立方體尖銳角的修補(bǔ)效果

圖10 fandisk模型特征角的修補(bǔ)效果

圖11 (a)、圖11(b)為文獻(xiàn)[12]方法丟失尖銳特征邊信息的fandisk模型的修補(bǔ)效果,圖11(c)、圖11(d)為本文方法在類似模型上的修補(bǔ)效果,本文方法根據(jù)孔洞的特征區(qū)域進(jìn)行異步生長修補(bǔ)孔洞,對尖銳特征的恢復(fù)效果比較好。

圖11 丟失尖銳特征邊信息的fandisk模型修補(bǔ)效果

圖12 (a)、圖12(b)為長方體模型丟失相鄰2個(gè)特征角時(shí)的修補(bǔ)效果,孔洞區(qū)域可以看作是由各個(gè)特征區(qū)域的丟失部分組合而成,各特征區(qū)域異步生長并進(jìn)行區(qū)域間求交,即可恢復(fù)模型的原始尖銳特征。圖12(c)、圖12(d)為模型丟失6個(gè)特征角時(shí)本文方法的修補(bǔ)情況,可以看出修補(bǔ)效果比較理想,十分接近模型的原始尖銳特征。對于丟失特征信息較多的情況,本文方法優(yōu)于文獻(xiàn)[15]的方法。針對圖12(a)丟失2個(gè)相鄰特征角的長方體和圖12(c)丟失較多信息的Fandisk模型,由于特征點(diǎn)無法匹配,無法構(gòu)造出對應(yīng)的特征線,導(dǎo)致文獻(xiàn)[15]方法失效,而本文方法能夠得到比較理想的修補(bǔ)效果。

圖12 丟失特征角的Fandisk模型修補(bǔ)效果

但是當(dāng)模型丟失信息過多以至于孔洞的某個(gè)特征區(qū)域完全丟失時(shí),如圖13所示,本文無法完成修補(bǔ);當(dāng)特征區(qū)域各方向上曲率變化比較劇烈時(shí)會(huì)導(dǎo)致補(bǔ)丁面片法矢計(jì)算的精確性下降,本文的修補(bǔ)效果也不是十分理想。

圖13 長方體丟失某個(gè)特征的全部信息

4 結(jié)束語

為了有效地復(fù)原殘缺三角網(wǎng)格模型的原始形狀,針對丟失尖銳特征的模型,本文提出一種基于區(qū)域生長的孔洞修補(bǔ)方法,利用特征區(qū)域的幾何性質(zhì)計(jì)算補(bǔ)丁面片的法矢,并據(jù)此采用異步生長方式修補(bǔ)孔洞。實(shí)驗(yàn)結(jié)果表明,本文方法在曲率變化較平緩時(shí)能夠取得比較精確的修補(bǔ)效果。但是當(dāng)孔洞特征區(qū)域曲率變化劇烈時(shí)修補(bǔ)效果不是十分理想,補(bǔ)丁面片法矢計(jì)算的精確性有待加強(qiáng)。如何更加精確地計(jì)算補(bǔ)丁面片的法矢是今后研究的重點(diǎn)。

[1] Liepa P.Filling Holes in Meshes[C]//Proc.of EurographicsSymposium on Geometry Processing. Airela-Ville,Switzerland:[s.n.],2003:200-205.

[2] Zhao Wei,Gao Shuming,Lin Hongwei.A Robust Hole-Filling Algorithm for Triangular Mesh[J].The Visual Computer,2007,23(12):987-997.

[3] 王小超,曹俊杰,劉秀平,等.波前法在三角網(wǎng)格孔洞修補(bǔ)中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào), 2011,23(6):1048-1054.

[4] Chui C K,Lai Minjun.Filling Polygonal Holes Using C1 Cubic Triangular Spline Patches[J].Computer Aided Geometric Design,2000,17(4):297-307.

[5] Jun Y.A Piecewise Hole Filling Algorithm in Reverse Engineering[J].Computer-aided Design,2005,37(2): 262-270.

[6] Li Gen,Ye Xiuzi,Zhang Sanyuan.An Algorithm for Filling Complex Holes in Reverse Engineering[J]. Engineering with Computers,2008,24(2):119-125.

[7] Piegl L A,TillerW.Fillingn-sided Regionswith NURBS Patches[J].The Visual Computer,1999,15 (2):77-89.

[8] Pernot J P,Moraru G,Véron P.Filling Holes in Meshes Using a Mechanical Model to Simulate the Curvature Variation Minimization[J].Computers&Graphics, 2006,30(6):892-902.

[9] Davis J,Marschner S R,Garr M,et al.Filling Holes in Complex Surfaces Using Volumetric Diffusion[C]// Proc.of the 1st International Symposium on 3D Data Processing,Visualization,and Transmission.Padua, Italy:[s.n.],2002:428-441.

[10] Ju Tao.Robust Repair of Polygonal Models[J].ACM Transactions on Graphics,2004,23(3):888-895.

[11] Chen C Y,Cheng K Y.A Sharpness-dependent Filter for Recovering Sharp Features in Repaired 3D Mesh Models [J].IEEE Transactions on Visualization and Computer Graphics,2008,14(1):200-212.

[12] Hu Ping,Wang Changsheng,Li Baojun.Filling Holes in Triangular Meshesin Engineering[J].Journalof Software,2012,7(1):141-148.

[13] Li Zhong,Mee D S,Walton D J.Polynomial Blending in a Mesh Hole-filling Application[J].Computer-aided Design,2010,42(4):340-349.

[14] Li Zhong.An Effective Third-order Local Fitting Patch and Its Application[C]//Proc.of IEEE International Conferenceon Shape Modeling and Applications. [S.l.]:IEEE Press,2009:7-14.

[15] Wang Xiaochao,LiuXiuping,LiuLinfa.Automatic Hole-filling of CAD Models with Feature-preserving [J].Computers&Graphics,2012,36(2):101-110.

編輯 顧逸斐

Hole-repairing Method for Triangular Mesh Model Based on Region Growing

LIU Yun-hua,LV Jian,ZHU Lin,LUO Nian-meng
(National CAD Support Software Engineering Research Center, Huazhong University of Science and Technology,Wuhan 430074,China)

To recover the original shape of the imperfect triangular mesh model with missing sharp feature effectively, this paper proposes a hole-repairing method based on region growing.The basic procedures of the method are as follows: Hole boundaries are detected according to the topological relationship of the model.Taking hole boundaries as the starting point,mesh around holes are segmented into regions according to breath first research.The normal new facet is obtained by analyzing the geometric property of relevant feature region.Afterward,according to the obtained normal,an asynchronous growth of new mesh is realized through an iteratively way inward and meanwhile,a controlling signal is set for every hole boundary facet to control the asynchronism of region growing.New facets in different region are intersected to rest sharp feature line and feature corner.Experimental results show that the approach works well for recovering the original shape of imperfect model with missing sharp feature.

hole-filling;region segmentation;region growing;asynchronism;feature recovery;triangular mesh

1000-3428(2014)10-0239-06

A

TP391

10.3969/j.issn.1000-3428.2014.10.045

國家自然科學(xué)基金資助項(xiàng)目(51075162)。

劉云華(1974-),男,講師、博士,主研方向:CAD/CAM技術(shù),三維模型輕量化技術(shù),三維可視化顯示;呂 劍,碩士研究生;朱 林,副教授;羅年猛,副教授、博士。

2013-11-07

2013-12-11E-mail:liuyh@hustcad.com

中文引用格式:劉云華,呂 劍,朱 林,等.基于區(qū)域生長的三角網(wǎng)格模型孔洞修補(bǔ)方法[J].計(jì)算機(jī)工程,2014, 40(10):239-244.

英文引用格式:Liu Yunhua,Lv Jian,Zhu Lin,et al.Hole-repairing Method for Triangular Mesh Model Based on Region Growing[J].Computer Engineering,2014,40(10):239-244.