半規則三角網格模型細分曲面重構

陳甜甜 趙 罡

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

根據已有產品實物樣件的坐標測量數據，重新建立樣件的數字化模型，再利用計算機輔助技術進行分析、設計、數控加工編程，制造出所需的新產品就是逆向工程［1］.三維模型重構技術是逆向工程的一個關鍵技術.

隨著近十幾年來細分理論基礎的逐步加深與拓展［2－4］，細分造型技術已經成為三維模型造型技術中非常重要的一類技術.與工業造型的標準工具NURBS方法相比，細分造型技術具有以下優勢:①能夠在任意復雜拓撲的網格上不斷運用細分規則生成光滑的細分曲面，克服了NURBS須經曲面裁剪和曲面拼接來表達復雜曲面的不足;②細分曲面采用離散數據表示，從而在顯示和數控加工中不需將曲面離散化，減少了中間轉換過程;③細分是基于遞歸細化控制網格的技術，其本身具有天然的多分辨率性質，易于構造細分小波.細分小波是多分辨思想與細分曲面結合的最佳體現.

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

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

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

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

1 基網格的生成

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

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

1.1 網格簡化

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

圖1 最大獨立點集為黑色標記的圓點

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

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

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

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

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

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

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

4)將刪除頂點pi及其1-鄰域頂點進行保角映射，記錄平面坐標，刪除頂點pi，并將其構成的多邊形進行Delaunay三角剖分;

5)記錄剖分后頂點pi周圍1-鄰域點的拓撲信息，修改pi周圍鄰域點的拓撲信息.

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

2 復雜網格重構

2.1 插值Loop細分模式

在將初始網格M簡化成基網格M0后，對基網格M0進行1～2次Loop細分得到半規則網格M1.在刪除最大點集時僅改變了pi周圍1-鄰域點的拓撲信息，頂點pi的位置并未改變.這個過程希望盡可能多的保留初始網格上的頂點，進而作為初始網格的采樣點以提高精度，故采用插值Loop 細分模式進行細分［17］.

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

式中

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

2.2 最近點調整

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

式中

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

2.3 PI方法

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

3 實驗結果與討論

為驗證上述算法的有效性，結合OpenGL在Visual C++6.0下實現該算法.實驗環境是基于Windows XP操作系統，奔騰IV 3.0GHz處理器，1GB內存.采用的數據結構是半邊數據結構.

圖2 3孔環模型進行細分曲面重構

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

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

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

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

圖3 cow模型和tiger模型細分曲面重構

圖4 casting模型細分曲面重構

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

表1 本文算法細分曲面重構實例

4 結論

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

References)

［1］黃誠駒，李鄂琴，禹誠.逆向工程項目式實訓教程［M］.北京:電子工業出版社，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細分曲面擬合系統［J］.計算機輔助設計與圖形學學報，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，Fan 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］白杰.基于小波的細分曲面數控加工技術研究［D］.北京:北京航空航天大學機械工程及自動化學院，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