半規(guī)則三角網(wǎng)格模型細(xì)分曲面重構(gòu)

陳甜甜 趙 罡

(北京航空航天大學(xué) 機械工程及自動化學(xué)院，北京 100191)

根據(jù)已有產(chǎn)品實物樣件的坐標(biāo)測量數(shù)據(jù)，重新建立樣件的數(shù)字化模型，再利用計算機輔助技術(shù)進(jìn)行分析、設(shè)計、數(shù)控加工編程，制造出所需的新產(chǎn)品就是逆向工程［1］.三維模型重構(gòu)技術(shù)是逆向工程的一個關(guān)鍵技術(shù).

隨著近十幾年來細(xì)分理論基礎(chǔ)的逐步加深與拓展［2－4］，細(xì)分造型技術(shù)已經(jīng)成為三維模型造型技術(shù)中非常重要的一類技術(shù).與工業(yè)造型的標(biāo)準(zhǔn)工具NURBS方法相比，細(xì)分造型技術(shù)具有以下優(yōu)勢:①能夠在任意復(fù)雜拓?fù)涞木W(wǎng)格上不斷運用細(xì)分規(guī)則生成光滑的細(xì)分曲面，克服了NURBS須經(jīng)曲面裁剪和曲面拼接來表達(dá)復(fù)雜曲面的不足;②細(xì)分曲面采用離散數(shù)據(jù)表示，從而在顯示和數(shù)控加工中不需將曲面離散化，減少了中間轉(zhuǎn)換過程;③細(xì)分是基于遞歸細(xì)化控制網(wǎng)格的技術(shù)，其本身具有天然的多分辨率性質(zhì)，易于構(gòu)造細(xì)分小波.細(xì)分小波是多分辨思想與細(xì)分曲面結(jié)合的最佳體現(xiàn).

鑒于上述細(xì)分造型技術(shù)的諸多優(yōu)點，細(xì)分曲面重構(gòu)就成為眾多學(xué)者研究的熱點.在1994年，文獻(xiàn)［5］就提出基于Loop細(xì)分的曲面重構(gòu)方法，該方法擬合精度高但是引入非線性優(yōu)化代價大.文獻(xiàn)［6］研究了雙循環(huán)過程來擬合控制網(wǎng)格，但未考慮初始網(wǎng)格模型的細(xì)節(jié)特征.文獻(xiàn)［7］提出了保持尖銳特征的Loop細(xì)分曲面擬合.在此基礎(chǔ)上，文獻(xiàn)［8］改進(jìn)了網(wǎng)格形狀優(yōu)化以及求重采樣網(wǎng)格的方法，但該方法需解龐大的線性方程組，還需討論解的奇異性.

最近，文獻(xiàn)［9］提出的漸進(jìn)插值逼近方法成為曲面重構(gòu)的新熱點.該方法通過不斷迭代修改初始網(wǎng)格控制頂點，得到插值于初始控制網(wǎng)格的非均勻B樣條曲面.文獻(xiàn)［10］將該方法推廣到細(xì)分曲面，提出了漸進(jìn)插值(PI，Progressive Interpolation)方法.文獻(xiàn)［11］提出與漸進(jìn)插值思想類似的幾何算法，但是未能證明收斂性.文獻(xiàn)［12］將該算法推廣到擬合算法.此外，文獻(xiàn)［13］對曲面局部擬合進(jìn)行了研究，文獻(xiàn)［14］對基于最小二乘優(yōu)化曲面擬合問題進(jìn)行了探討.

上述重構(gòu)方法不管是擬合還是插值，所生成的細(xì)分曲面都無法利用細(xì)分曲面的多分辨特性，無法直接進(jìn)行細(xì)分小波分析.這是因為，半規(guī)則網(wǎng)格，即具有細(xì)分連接性的網(wǎng)格是細(xì)分小波應(yīng)用的重要前提.所以，如何將測量后的非規(guī)則密集三角網(wǎng)格模型重構(gòu)為半規(guī)則細(xì)分曲面，以此作為最終建立的CAD模型可以直接進(jìn)行細(xì)分小波分析就是本文研究的主要內(nèi)容.

本算法首先用簡化方法將初始網(wǎng)格模型M簡化得到基網(wǎng)格M0，其次用插值Loop細(xì)分對基網(wǎng)格進(jìn)行1～2次細(xì)分得到網(wǎng)格M1，然后對M1重采樣得到網(wǎng)格M2，最后用PI方法得到插值于M2的控制網(wǎng)格M3，其極限曲面就是半規(guī)則三角網(wǎng)格的細(xì)分曲面.

1 基網(wǎng)格的生成

基網(wǎng)格是通過對初始網(wǎng)格進(jìn)行簡化得到的.文獻(xiàn)［15］提出了一種多分辨參數(shù)化方法MAPS(Multiresolution Adaptive Parameterization of Surface)，可以建立多分辨率網(wǎng)格，從而直接進(jìn)行細(xì)分小波分析.但是該方法由于對每個刪除點需要逐層投影，并且對每個新生成的頂點需要逐個定位，計算繁瑣費時.為了提高運算效率下面給出一種不需計算刪除點逐層投影的簡化算法來得到基網(wǎng)格.這里采用提取尖銳特征點和最大獨立點集刪除的方法來得到高保真度的基網(wǎng)格.

提取尖銳特征點首先判斷一條邊是否為特征邊.這可以通過它的2個共享三角形的外法向夾角確定［8］.判斷一個點是否為特征點，由該點所連接臨邊的的特征邊的個數(shù)所確定.若一個頂點的臨邊沒有特征邊，則該點為光滑點.

1.1 網(wǎng)格簡化

正文網(wǎng)格簡化過程中首先需要確定當(dāng)前所要刪除的所有頂點，每次簡化所刪除的頂點集合應(yīng)滿足最大獨立點集［15］的要求.對于給定網(wǎng)格，最大獨立點集不唯一.圖1中黑色的圓點構(gòu)成一組最大獨立點集.

圖1 最大獨立點集為黑色標(biāo)記的圓點

最大獨立點集的選取要保證刪除當(dāng)前最大獨立點集對網(wǎng)格曲面整體影響最小，即刪除一組最大獨立點集后，要最大化的保存初始網(wǎng)格特征.為了量化頂點的刪除優(yōu)先級，采用面積評價函數(shù)a(i)和曲率評價函數(shù)k(i)來確定每個頂點的刪除優(yōu)先權(quán)值 ω(i)［15］:

式中N(i)表示頂點 pi周圍1-鄰域點集合.在CAD/CAM中，離散曲率是至關(guān)重要的幾何不變量，其計算公式采用由Meyer等人提出的離散高斯曲率的離散形式［16］來計算:

式中，θj表示邊 pipi－1與 pipi+1的夾角;AM表示頂點pi周圍1-鄰域所有銳角三角形和鈍角三角形的混合面積.

計算出所有網(wǎng)格上的頂點的優(yōu)先權(quán)值ω(i)后，即可選擇當(dāng)前網(wǎng)格的最大獨立點集進(jìn)行刪除，每刪除一個頂點將留下一個空洞，需要對此空洞重新進(jìn)行三角剖分.按照上述刪除最大獨立點集的方法不斷刪除頂點，直到無法繼續(xù)刪除為止.至此，設(shè)初始網(wǎng)格為Mj，獲得簡化的基網(wǎng)格具體步驟如下:

1)保留網(wǎng)格Mj中所有度大于12的頂點，以及標(biāo)記為尖銳特征的頂點;

2)對網(wǎng)格Mj中剩余頂點按評價函數(shù)計算權(quán)值ω(i)，按照由小到大的順序進(jìn)行排序并建立頂點隊列Qj;

3)依次判斷Qj中頂點pi是否應(yīng)被刪除，得到刪除頂點的最大獨立點集Dj，將Dj中的頂點依次刪除;

4)將刪除頂點pi及其1-鄰域頂點進(jìn)行保角映射，記錄平面坐標(biāo)，刪除頂點pi，并將其構(gòu)成的多邊形進(jìn)行Delaunay三角剖分;

5)記錄剖分后頂點pi周圍1-鄰域點的拓?fù)湫畔ⅲ薷膒i周圍鄰域點的拓?fù)湫畔?

由于MAPS算法在每次簡化時，需遍歷初始網(wǎng)格的所有頂點，計算復(fù)雜度為O(N log N).本文的簡化算法在生成基網(wǎng)格時只需逐層刪除最大獨立點集，直接利用被刪除點周圍1-鄰域Delaunay三角剖分后的拓?fù)潢P(guān)系構(gòu)造簡化網(wǎng)格，計算復(fù)雜度為O(log N)，提高了計算效率.

2 復(fù)雜網(wǎng)格重構(gòu)

2.1 插值Loop細(xì)分模式

在將初始網(wǎng)格M簡化成基網(wǎng)格M0后，對基網(wǎng)格M0進(jìn)行1～2次Loop細(xì)分得到半規(guī)則網(wǎng)格M1.在刪除最大點集時僅改變了pi周圍1-鄰域點的拓?fù)湫畔ⅲ旤cpi的位置并未改變.這個過程希望盡可能多的保留初始網(wǎng)格上的頂點，進(jìn)而作為初始網(wǎng)格的采樣點以提高精度，故采用插值Loop 細(xì)分模式進(jìn)行細(xì)分［17］.

具體地，邊點的調(diào)整分為內(nèi)部邊點pe和邊界邊點p'e2種情況，其中內(nèi)部邊點pe周圍的4個頂點分別是臨點p0和p1及對頂點p2和p3;邊界邊點p'e周圍的2個頂點是p0和p1.插值Loop細(xì)分邊點細(xì)分模版分別見式(3)和式(4).

式中

Loop細(xì)分后的半規(guī)則網(wǎng)格M1與初始網(wǎng)格M的偏離程度還是很大的.按照MAPS方法接下來需要尋找每個頂點以及刪除點對應(yīng)的三角形，如何定位三角形是一個比較棘手的問題.所以下面利用最近點調(diào)整網(wǎng)格，得到重采樣網(wǎng)格M2.

2.2 最近點調(diào)整

最近點調(diào)整的主要思路是首先計算簡化網(wǎng)格M0上的頂點pi的極限位置p∞i，通過調(diào)整頂點pi的位置，使其成為初始網(wǎng)格M0上的采樣點.其中調(diào)整頂點pi位置的關(guān)鍵問題就是尋找頂點pi在初始網(wǎng)格M0上的最近點，即尋找頂點pi的極限點到初始網(wǎng)格M的投影點μi.

式中

計算最近點μi時首先計算與初始網(wǎng)格M中所有點的有向距離，一般認(rèn)為在頂點pi外側(cè)的有向距離為正向.最短的有向距離有可能不唯一，則根據(jù)求得的法失方向分別與該頂點周圍1-鄰域三角面片求交點，距離最近的點為μi;若沒有交點，令與1-鄰域三角面最近距離點為的法失方向由pi的1-鄰域三角形的法失方向按照三角形面積加權(quán)確定.由于在插值Loop細(xì)分時僅插入邊點，頂點位置未改變，故只需求邊點在初始網(wǎng)格上的最近點.調(diào)整網(wǎng)格頂點會使網(wǎng)格中的部分三角形質(zhì)量有所下降，可以通過Laplacian算子對網(wǎng)格進(jìn)行平滑處理［8］.

2.3 PI方法

至此，得到初始網(wǎng)格的采樣網(wǎng)格M2，將M2作為給定的網(wǎng)格，根據(jù)式(5)計算其極限曲面對于網(wǎng)格M2中的每一個頂點V0，計算其與對應(yīng)極限位置的距離，等距更新每一個網(wǎng)格頂點V1=V0+D0，此時得到迭代一次后的新網(wǎng)格.接下來同樣地，計算的極限曲面，等距更新中所有頂點 V2=V1+D1，其中.按照上面的迭代過程，得到一系列Loop細(xì)分曲面不斷逼近采樣網(wǎng)格M2，重構(gòu)的Loop細(xì)分曲面S就是逼近初始網(wǎng)格M0的半規(guī)則細(xì)分曲面.這里采用雙向 Hausdroff距離計算誤差［18］，見式(6).

3 實驗結(jié)果與討論

為驗證上述算法的有效性，結(jié)合OpenGL在Visual C++6.0下實現(xiàn)該算法.實驗環(huán)境是基于Windows XP操作系統(tǒng)，奔騰IV 3.0GHz處理器，1GB內(nèi)存.采用的數(shù)據(jù)結(jié)構(gòu)是半邊數(shù)據(jù)結(jié)構(gòu).

圖2 3孔環(huán)模型進(jìn)行細(xì)分曲面重構(gòu)

首先以文獻(xiàn)［15］中3孔環(huán)模型為例(圖2).對具有12000個三角片和5996個頂點的初始網(wǎng)格進(jìn)行簡化14次，快速得到了具有196個三角片和94個頂點的基網(wǎng)格.與初始網(wǎng)格相比，Loop細(xì)分2次后得到半規(guī)則網(wǎng)格(圖2c)有明顯的變形.調(diào)整后迭代插值初始網(wǎng)格得到圖2d，可以看出無尖銳特征的3孔模型重構(gòu)后的曲面質(zhì)量良好.

圖3為分別對cow模型和tiger模型進(jìn)行細(xì)分曲面重構(gòu).圖3a和圖3d是2個模型的渲染圖.首先將2個模型分別簡化5次，得到基網(wǎng)格(圖3b和圖3e).然后，按照第2節(jié)的方法進(jìn)行重采樣，通過調(diào)整半規(guī)則網(wǎng)格邊點的位置不斷迭代插值得到重構(gòu)的細(xì)分曲面，如圖3c和圖3f.在牛角、牛尾、虎耳和虎尾等處，重構(gòu)后的細(xì)分曲面很好的保持了初始網(wǎng)格的尖銳特征.

圖4a是casting模型的初始網(wǎng)格實體圖，共有5096個頂點.提取尖銳特征后，簡化14次得到具有1790個頂點的基網(wǎng)格實體圖(圖4b).經(jīng)插值Loop細(xì)分1次后按照第2節(jié)最近點調(diào)整采樣點，迭代插值得到半規(guī)則細(xì)分曲面的實體圖，如圖4c所示.

本文重構(gòu)的細(xì)分曲面實例具體數(shù)據(jù)見表1.可以看出，部分模型重構(gòu)后的網(wǎng)格頂點個數(shù)稍多于初始網(wǎng)格頂點數(shù)，主要原因在于本文以頂點增多為代價使得細(xì)分曲面保持尖銳特征的同時具有細(xì)分連接性.這對于下一步進(jìn)行細(xì)分小波分解而言是可以接受的.

圖3 cow模型和tiger模型細(xì)分曲面重構(gòu)

圖4 casting模型細(xì)分曲面重構(gòu)

文獻(xiàn)［12］中的方法擬合精度高，但是為了調(diào)整網(wǎng)格正則度，采用1-4分裂插入頂點法，只能從一定程度上緩解網(wǎng)格的不規(guī)則性，大部分網(wǎng)格的連接性還是不夠好，不能直接進(jìn)行細(xì)分小波分析.

表1 本文算法細(xì)分曲面重構(gòu)實例

4 結(jié)論

利用細(xì)分小波技術(shù)可以得到逼近于初始模型的不同分辨率下的幾何模型.本文以得到半規(guī)則三角網(wǎng)格模型作為出發(fā)點，研究了逆向工程中的三角網(wǎng)格重構(gòu)問題.在刪除最大獨立點集的同時，通過提取三角剖分后刪除點周圍1-鄰域點的拓?fù)潢P(guān)系快速得到基網(wǎng)格，對重采樣的基網(wǎng)格通過PI方法不斷迭代得到插值半規(guī)則網(wǎng)格的Loop細(xì)分曲面.與傳統(tǒng)網(wǎng)格重構(gòu)方法相比，本文提出的算法無需解線性方程組，所重構(gòu)出的細(xì)分曲面不僅能保持初始網(wǎng)格的尖銳特征，而且重構(gòu)后的三角網(wǎng)格細(xì)分曲面可以直接進(jìn)行細(xì)分小波變換，是進(jìn)一步利用細(xì)分造型技術(shù)進(jìn)行多分辨分析及編輯的基礎(chǔ).未來的工作包括優(yōu)化算法以提高大規(guī)模網(wǎng)格重構(gòu)曲面的質(zhì)量，同時提高算法效率以便更加利于工程應(yīng)用.

References)

［1］黃誠駒，李鄂琴，禹誠.逆向工程項目式實訓(xùn)教程［M］.北京:電子工業(yè)出版社，2004:1－17 Huang Chengju，Li Eqin，Yu Cheng.Reversing engineering project type training tutorial［M］.Beijing:Publishing House of Electronics Industry，2004:1 －17(in Chinese)

［2］ Jiang Qingtang，Li Baobin，Zhu Weiwei.Interpolatory quad/triangle subdivision schemes for surface design［J］.Computer Aided Geometric Design，2009，24(8):904 －922

［3］ Sadeghi J，Samavati F F.Smooth reverse Loop and Catmull-Calrk subdivision［J］.Graphical Models，2011，73(5):200 －117

［4］ Olsen L，Samamati F F，Bartels R H.Multiresolution for curves and surfaces based on constraining wavelets［J］.Computer Graphics，2007，31(3):449 － 462

［5］ Hoppe H，DeRose T，Duchamp T，et al.Piecewise smooth surface construction［C］//Proceedings of the21st Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press，1994:295 －302

［6］ Suzuki H，Takeuchi S，Kimura F，et al.Subdivision surface fitting to a range of points［C］//The Seventh Pacific Conference on Computer Graphics and Applications.Washington DC:IEEE Computer Society Press，1999:158 － 167

［7］ MaWeiyin，Ma Xiaohu，Tso Shiu-Kit，et al.A direct approach for subdivision surface fitting from a dense triangle mesh［J］.Computer-Aided Design，2004，36(6):525 －536

［8］李桂清，馬維銀，鮑虎軍.帶尖銳特征的Loop細(xì)分曲面擬合系統(tǒng)［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2005，17(6):1179－1185 Li Guiqing，Ma Weiyin，Bao Hujun.Fitting system using loop subdivision surfaces with sharp features［J］.Journal of Computer-Aided Design ＆ Computer Graphics，2005，17(6):1179 －1185(in Chinese)

［9］ Lin H，Wang G，Dong C.Constructing iterative non-uniform B-spline curve and surface to fit data points［J］.Science in China，2003，33:912 －923

［10］ Cheng Fuhua，F(xiàn)an Fengtao，Lai Shuhua，et al.Loop subdivision surface based progressive interpolation［J］.Journal of Computer Science and Technology，2009，24(1):39 －46

［11］ Maekawa T，Matsumoto Y，Namiki K.Interpolation by geometric algorithm［J］.Computer-Aided Design，2007，39(4):313 －323

［12］ Yu N，Masayuki M，Takashi M.Loop subdivision surface fitting by geometric algorithms［C］//Poster Proceedings of Pacific Graphics.Tokyo:Computer Graphics Forum，2008:67 －74

［13］ Wang Jun，Yu Zeyun.Quality mesh smoothing via local surface fitting and optimum projection［J］.Graphical Models，2011，73(4):127–139

［14］ Simon F，Michael H.Surface fitting and registration of point clouds using approximations of the unsigned distance function［J］.Computer Aided Geometric Design，2010，27(1):60 － 77

［15］ Lee AW F，Sweldens W，Schroder P，et al.MAPS:multiresolution adaptive parameterization of surfaces［C］//Proceedings of the 25th annual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press，1998:95 －104

［16］ Meyer M，Desbrun M，Schroder P，et al.Discrete differential-geometry operators for triangulated 2-manifolds［C］//International Workshop on Visualization and Mathematics.Berlin:Springer-Visualization and Mathematics，2002:52 －58

［17］白杰.基于小波的細(xì)分曲面數(shù)控加工技術(shù)研究［D］.北京:北京航空航天大學(xué)機械工程及自動化學(xué)院，2009 Bai Jie.Research on NC machining based on the subdivision technology and subdivision wavelets［D］.Beijing:School of Mechanical Engineering and Automation，Beijing University of Aeronautics and Astronautics，2009(in Chinese)

［18］ Cignoni P，Rocchini C，Scopigno CR.Metro:measuring error on simplified surfaces［J］.Computer Graphics Forum，1998，17(2):167－174