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

陳甜甜 趙 罡

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

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

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

鑒于上述細(xì)分造型技術(shù)的諸多優(yōu)點(diǎn)，細(xì)分曲面重構(gòu)就成為眾多學(xué)者研究的熱點(diǎn).在1994年，文獻(xiàn)［5］就提出基于Loop細(xì)分的曲面重構(gòu)方法，該方法擬合精度高但是引入非線性優(yōu)化代價(jià)大.文獻(xiàn)［6］研究了雙循環(huán)過(guò)程來(lái)擬合控制網(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)的新熱點(diǎn).該方法通過(guò)不斷迭代修改初始網(wǎng)格控制頂點(diǎn)，得到插值于初始控制網(wǎng)格的非均勻B樣條曲面.文獻(xiàn)［10］將該方法推廣到細(xì)分曲面，提出了漸進(jìn)插值(PI，Progressive Interpolation)方法.文獻(xiàn)［11］提出與漸進(jìn)插值思想類(lèi)似的幾何算法，但是未能證明收斂性.文獻(xiàn)［12］將該算法推廣到擬合算法.此外，文獻(xiàn)［13］對(duì)曲面局部擬合進(jìn)行了研究，文獻(xiàn)［14］對(duì)基于最小二乘優(yōu)化曲面擬合問(wèn)題進(jìn)行了探討.

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

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

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

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

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

1.1 網(wǎng)格簡(jiǎn)化

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

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

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

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

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

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

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

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

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

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

5)記錄剖分后頂點(diǎn)pi周?chē)?-鄰域點(diǎn)的拓?fù)湫畔?，修改pi周?chē)徲螯c(diǎn)的拓?fù)湫畔?

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

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

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

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

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

式中

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

2.2 最近點(diǎn)調(diào)整

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

式中

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

2.3 PI方法

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

3 實(shí)驗(yàn)結(jié)果與討論

為驗(yàn)證上述算法的有效性，結(jié)合OpenGL在Visual C++6.0下實(shí)現(xiàn)該算法.實(shí)驗(yà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).對(duì)具有12000個(gè)三角片和5996個(gè)頂點(diǎn)的初始網(wǎng)格進(jìn)行簡(jiǎn)化14次，快速得到了具有196個(gè)三角片和94個(gè)頂點(diǎn)的基網(wǎng)格.與初始網(wǎng)格相比，Loop細(xì)分2次后得到半規(guī)則網(wǎng)格(圖2c)有明顯的變形.調(diào)整后迭代插值初始網(wǎng)格得到圖2d，可以看出無(wú)尖銳特征的3孔模型重構(gòu)后的曲面質(zhì)量良好.

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

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

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

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

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

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

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

4 結(jié)論

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

References)

［1］黃誠(chéng)駒，李鄂琴，禹誠(chéng).逆向工程項(xiàng)目式實(shí)訓(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］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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é)機(jī)械工程及自動(dòng)化學(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