基于三維ＴＩＮ的精細表面建模方法
2006-12-31 00:00:00李逢春龔俊王青
計算機應用研究 2006年8期
(1. 武漢大學 測繪遙感信息工程國家重點實驗室， 湖北 武漢 430079; 2. 浙江大學 CADCG國家重點實驗室， 浙江 杭州 310027)
摘 要： 對現有三維不規則三角網（3DTIN）生成算法作了簡要分類，回顧和評價了各類典型方法的優缺點和適用性，然后在此基礎上提出了一種融合雕刻算法和生長算法優勢的合成算法，給出了相應的數據結構。算法基于表面三角形任意一邊的鄰域結構，采用加權最小長度準則實現表面的快速生長。應用實例表明，算法可以重構具有任意拓撲的復雜表面，并且重構的三角網格表面與被采樣的物體表面拓撲差別最小。
關鍵詞： 三維TIN; 表面重構; 3D Delaunay; 三維可視化
中圖法分類號： TP391文獻標識碼： A
文章編號： 1001 3695(2006)08 0159 03
Highly Refined Surface Reconstruction Method Based on 3D TIN
LI Feng chun1， GONG Jun1， WANG Qing2
(1. State Key Laboratory of Information Engineering in Surveying Mapping Remote Sensing，Wuhan University， Wuhan Hubei 430079， China; 2. State Key Laboratory of CADCG， Zhejiang University， Hangzhou Zhejiang 310027， China)
Abstract: This paper firstly by analysing and classifying the wide variety of 3D TIN generation methods， provides a clear overall outline of all those typical methods. Secondly， a combinatorial algorithm for surface reconstruction from three dimensional points is presented， which is a combination of the sculpture algorithm and growing algorithm. A region growing starting from arbitrary side of the seed triangle is preformed. During the growing procedure， a weighted minimal length criterion is employed to ensured geometric integrity and automatic boundary detection. Experimental results show that the algorithm can efficiently obtain the reconstructed mesh surface with arbitrary topology and with only small topological difference from the surface of the original object.
Key words: 3D TIN; Surface Reconstruction; 3D Delaunay Triangulation; Three Dimensional Visualization
根據影像匹配和激光掃描獲得的大量三維離散點集數據快速準確地重建物體的幾何表面模型，在虛擬環境、計算機視覺、逆向工程等諸多領域具有重要的意義。隨著數字攝影測量、高分辨率遙感技術，特別是激光掃描系統的發展，包含被測目標更多細節的三維點云數據獲取成為可能，并且成為高精細測量建模的發展方向。由于將真實世界從三維空間投影到二維平面，二維TIN模型及其相關算法的弊端已經表現得越來越明顯，如何實現快速準確的真三維表面構模已經成為目前亟待解決的問題。
1 三維TIN算法回顧
三維TIN構網算法種類繁多，Mencl[1]的分類方法曾經是一種廣為接受的分類方法，但是它并不能很好地概括現有方法的特點。根據每類方法的原理和主要特點，本文將現有典型的三維TIN構網方法從宏觀上分為直接法和間接法兩大類。直接法包括雕刻算法、距離函數法、表面生長法；間接法主要有映射法。
1.1 雕刻算法
雕刻算法(Sculpture Algorithm)是三維表面構網應用最為廣泛的方法。這類算法的基本思想首先是計算離散點集的拓撲鄰接關系，然后根據特定的規則或知識提取表面三角形面片。根據提取策略的不同，其代表算法又有α shape算法[2， 3]、Crust算法[4]、Cocone算法[5]、傘形過濾算法等[6， 7]。
法國INRIA的Boissonnat[8]最早提出了雕刻算法，首先對點集進行Delaunay三角化，然后通過對外接球半徑的判斷剝離冗余四面體和三角形使物體表面的所有散亂點可見。冗余四面體的剔除規則和剔除的先后順序對最終構網結果的影響很大，因此不同的作者提出了各自的剔除策略。α shape算法和γ indicator算法[9]實際上是一種參數構造的方法，根據參數值以遞增次序刪除冗余四面體，這種方法處理密度不均勻的數據需要更多的人工干預。Attene[10]的方法采用歐幾里德最小空間樹(Euclidean Minimum Spanning Tree， EMST)和擴展的Gabriel超圖(Extended Gabriel Hypergraph， EGH)作為約束剔除準則。Crust算法和Cocone算法在提取表面時利用了表面的近似法向和角度參數，但是往往產生表面空洞、重疊的面片和不正確的連接等現象。Amenta等人[11]提出Power Crust算法雖然輸出無隙表面，但是增加了輔助點。
表面的流形特征必然反映在離散點集的鄰域結構中，一些研究者提出了利用局部的拓撲關系準則和知識提取表面模型的方法，如瑞士蘇黎世大學Adamy[6]提出基于傘形條件過濾的表面構網方法。Adamy以三維空間中基于一點的鄰域結構及其可能的傘形作為過濾條件，算法根據過濾條件在Delaunay復形中為每個頂點找出局部的表面結構，再經過逐點的強制拓撲糾正重構得到正確的三維表面格網。傘形過濾條件仍然離不開參數λ的計算。浙江大學李立新博士提出了基于一點的鄰域結構和一邊的鄰域結構及其可能的傘形，并發現基于一邊的鄰域結構更加簡便。Mencl[12]提出基于EMST圖和規則（知識）來進行表面構網的方法，算法的基本思想是在計算點集EMST圖的基礎上，根據識別規則提取表面特征，擴展得到形如線框的表面描述圖（Surface Description Graph，SDG），然后用三角形面片充填線框圖。這種方法需要在復雜的表面形狀特征描述規則的支持下才能完成表面重構，適用性不強。
1.2 距離函數法
距離函數法的典型代表是Hoppe[13]提出的算法，通過ρ密度計算樣點近似切平面，定義到最近切平面的有符號距離函數，然后用等值面抽取算法得到表面三角形格網。Hoppe的方法自動化程度高，能夠識別表面邊界，復雜度較低。但對于表面邊界以及尖銳棱邊部分的重建效果不夠理想，而且生成的格網不經過原始采樣點，適用性較差。其他的類似算法還有自然鄰居算法[14]、改進的距離函數法[15]。
1.3 表面生長法
表面生長的重構方法開始于種子三角形，以局部增量擴張的方式生成新的三角形，直至覆蓋整個表面。這種方法的關鍵在于如何為當前擴展邊選取第三點形成新三角形。BPA算法[16]對第三點的選取依賴于用戶定義的外接球半徑；Lin[17]的方法需要依靠樣點的最長和最短關聯邊的比率（采樣均勻度）來確定第三點的搜索范圍；譚建榮[18]的方法則利用了三維Delaunay 三角剖分后的局部鄰域關系，通過對當前邊所有鄰域三角形逐一求取使得最大張角最小的第三點；Huang[19]的算法把與當前擴展邊端點相關聯的K 個鄰接點投影到局部平面上，然后根據最小長度準則為當前擴展邊選取第三點。
1.4 映射法
映射法是一種從二維到三維的間接表面構網方法，算法將局部的鄰近點投影到切平面上進行二維三角化，然后在考慮局部三角網邊緣一致性的基礎上拼接成整體的三維表面模型，如文獻[20～22]中的算法。映射算法把復雜的三維問題簡化為二維問題，具有較高的構網效率。但是這種方法依賴于 K 鄰域大小的選取，并且點與點間的空間距離經投影后發生變形，直接影響表面格網的質量。
2 合成算法
可以看出，以上各類方法都有各自的優缺點。當前的發展趨勢是綜合各種方法的優勢，互相取長補短，達到效率和可靠性間的平衡。傳統的生長算法由于舍棄了點集中一些有用的規律，如法向、數據點隱含的拓撲關系等，導致算法設計復雜，效率和可靠性不高。與其他類似的三維表面重構方法相比，Amenta的方法雖然利用點的近似法向，但不能很好地消除表面空洞、重疊面片。本文提出并實現了一種合成的算法，把雕刻算法和生長算法的優勢很好結合起來。其基本思想是，首先構造離散點集 P 的Delaunay三角剖分DP ，利用文獻[5]的表面法向過濾條件從DP中快速抽取初始的候選表面三角形集合TP；然后由一個初始表面種子三角形開始，基于三角形任意邊的共邊鄰域拓撲關系，通過區域增長實現整個表面T′P的重建。
2.1 數據結構及基本操作
根據算法的需要，設計了顯式描述三維Delaunay剖分單元、表面三角形以及剖分單元和表面 三角形兩者間拓撲關系的數據結構。利用這種數據結構能夠從中快速提取三角形任意一邊的鄰域三角形集合，從而避免大量存儲拓撲關系所導致的昂貴內存開銷。主要的數據結構Tetrahedron表示DP的一個剖分單元TEN，Shellface表示表面的一個三角形。在數據結構Shellface中，除了用face數據項表示三角形的鄰接三角形指針外，還為三角形的內外表面增設了tet數據項指向兩個鄰接四面體，把表面三角形真正嵌入到三維空間。如圖1所示，{V1V2V3V4}和{V1V2V3V5} 表示兩個相鄰的TEN剖分單元，用數據結構Tetrahedron實現。三角面片△ V1V2V3 處于兩個相鄰TEN的公共面位置，用數據結構Shellface實現。
算法所設計的主要數據結構如下：
struct Tetrahedron
{
Tetrahedron tet[4]; //四個鄰接四面體指針
Point vertice[4]; //四個頂點指針
Shellface face[4]; //四個表面三角形指針
Bool filtermark[4]; //四個候選三角面標記
…
};
struct Shellface
{
Shellface face[3]; //三個鄰接三角形指針
Point vertice[3]; //三個頂點指針
Tetrahedron tet[2]; //兩個鄰接四面體指針
Bool normalmark; //法向反置標記
…
};
組成TEN單元的點、面和鄰接TEN的存儲順序規定如下：設 V0，V1，V2，V3 為TEN的四個有序頂點，第四個頂點 V 3相對于 V0，V1，V2 的位置根據右手定則判斷。TEN單元四個面 f0，f1，f2，f3 的頂點分別為 f0(V0，V1，V2)，f1(V0，V3，V1)，f2(V1，V3，V2)，f3(V2，V3，V0)，四個鄰接TEN的存儲順序和f1，f2，f3 的順序一致。基本操作函數Getnextface(tetface*tface1， tetface*tface2) 以TEN的一個面對象指針tetface1作為輸入，輸出tetface2是以共享邊為軸順時針（逆時針）方向的下一個面對象指針。因此，具有共享邊的所有鄰接TEN面都能夠從Tetrahedron所包含的拓撲信息中提取出來。
2.2 算法步驟
隊列結構ActiveEdgeQueue用于臨時存放待生長擴展的表面三角形的邊。ePQ為當前三角形的擴展邊，所有與△PQR具有公共邊ePQ的三角形形成ePQ的鄰域三角形集合TPQ={△n0，△n1，…， △nm}， 其中灰色的三角形表示預先提取出的的表面候選三角形，如圖2所示。
整個合成算法流程如下：
(1)點集的三維Delaunay剖分。
(2)候選三角形集合快速提取。
(3)以種子三角形的三邊將隊列ActiveEdgeQueue初始化。種子三角形的任意一邊有且只有一個鄰接三角形，且與種子三角形所夾的二面角為鈍角。
(4)若隊列ActiveEdgeQueue非空，擴展邊PQ出隊，轉向(5)；否則轉向(9)。
(5)擴展邊 PQ狀態檢查。如果PQ不是邊界邊或者內部邊，轉向(6)；如果PQ 是邊界邊或已經變成內部邊，轉向(4)。
(6)鄰接三角形定位。在TPQ中為PQ 邊搜索第三點ni 生成新三角形。如果TPQ中存在唯一的被標記過的表面候選三角形，則該三角形入選；否則運用加權的最小長度準則為 PQ 邊搜索最優鄰接三角形。
(7)拓撲一致性檢驗。分別檢查 PQ的左右鄰邊QE1和PE2 所在的三角形，如果△PQni與這兩個三角形在空間上重疊，轉向(6)；否則，轉向(8)。
(8)綁定△PQR和△QPni 的拓撲鄰接關系。如果Pni和Qni邊有鄰接三角形，將Pni和Qni邊的狀態改為內部邊；如果Pni和Qni邊無鄰接三角形，則作為待擴展邊加入隊列ActiveEdgeQueue。轉向(4)。
(9)法向一致化并輸出表面模型。
3 應用實例
本文算法已用C++語言實現，為了驗證合成算法的實際運行效果，選取有73068個點的佛像數據在Pentium1.8GHz/256MB RAM微機上進行了測試。佛像的頭頂、手部和腳部區域的點云數據采樣不均勻，對生成的模型進行瀏覽和檢查，沒有發現不合理的連接，實驗結果如圖3所示。其中Delaunay剖分時間為88s，產生TEN的個數為478 753，初始候選表面三角形集合提取時間為4s，表面生長的時間為3s，模型的表面三角形個數為145 723。利用其他數據進行測試，也可以得到正確的結果。
4 結束語
三維TIN建模方法已經廣泛應用于計算機視覺、圖形圖像和地球信息科學等領域，本文對代表性的方法作了歸納和分類，分析了它們各自的優缺點和適用性。結合雕刻算法和生長算法提出了簡單高效的合成算法，采用由粗到精的表面提取策略，在表面候選三角形標記階段僅需要運用角度條件對所有的TEN單元遍歷過濾一次；對表面格網的生長過程而言，每條邊只需要執行一次鄰接三角形搜索。很明顯，這兩個過程的時間復雜度是線性的，有效降低了鄰接三角形的定位時間。三維Delaunay剖分過程是本文算法耗時的主要影響因素，因此動態隨機增量插入算法的復雜度O(nlogn)是本文算法復雜度一個很好的估計。本文的工作一方面對根據實際應用的需要來選取適當的表面構網生成算法具有重要的指導作用，另一方面為實現高精度的表面快速建模、為更好地利用各種三維空間數據奠定理論和技術基礎。
參考文獻：
[1] Mencl R， Muller H.Interpolation and Approximation of Surfaces from Three Dimensional Scattered Data Points[C]. Lisbon : State of the Art Report (STAR) for EUROGRAPHICS，1998.51-67.
[2] Edelsbrunner H，E P Muche. Three Dimensional Alpha Shapes[J].ACM Transactions on Graphics，1994，13(1):43-72.
[3] Guo B，Menon J，Willette B. Surface Reconstruction Using AlphaShaps[J]. Computer Graphics Forum，1997，16(4):177-190.
[4] Amenta N，Bern M，Kamvysselis M. A New Voronoi based Surface Reconstruction Algorithm[C].Orlando:Proceedings of SIGGRAPH，ACM Press，1998.415-420.
[5] Amenta N，Choi S，Dey T K， et al .A Simple Algorithm for Homeomorphic Surface Reconstruction[C].Hong Kong：Proceedings of the 16th Annual ACM Symposium on Computational Geometry，2000.213-222.
[6] Adamy U，Giesen J，John M. New Techniques for Topologically CorrectSurface Reconstruction[C].Proceedings of IEEE Visualization，Los Alamitos：IEEE ComputerSociety Press， 2000.373-380.
[7] 李立新. 散亂點集曲面重建的理論、方法及應用研究[D]. 杭州: 浙江大學， 2001.
[8] Boissonnat J D. Geometric Structures for Three Dimensional Shape Representation[J]. ACM Transactions on Graphics，1984，3(4):266-286.
[9] Veltkamp R C.Boundaries through Scattered Points of Unknown Density[J].Graphical Model and Image Processing，1995，57(6):441-452.
[10] Attene M，Spagnuolo M. Automatic Surface Reconshuction from Point Sets in Space[J].Computer Graphics Forum，2000，19(3):457-465.
[11] Amenta N， Choi S，Kolluri R K. The Power Crust， Unions of Balls， and the Medial Axis Transform[J].Comput.Geom.Theory Appl.，2001，19:127-153.
[12] Mencl R. A Graph based Approach to Surface Reconstruction[J].Computer Graphics Forum，1995，14(3):445-456.
[13] Hoppe H，De Rose T， et al . Surface Reconstruction from Unorganized Points[J].Computer Graphics，1992，26(2):71-78.
[14] Boissonnat J D，Cazals F. Smooth Surface Reconstruction via Natural Neighbor Interpolation of Distance Functions[J].Computational Geo metryTheory and Applications，2002，22(1 3):185-203.
[15] 周儒榮， 張麗艷， 蘇旭，等.海量散亂點的曲面重建算法研究[J]. 軟件學報， 2001， 12(2):249-255.
[16] Bernardini F，Mittleman J，Rushmeier H， et al. The Ball pivoting Algorithm for Surface Reconstruction[J]. IEEE Transactions on Visua lization and Computer Graphics， 1999， 5(4):349-359.
[17] Lin Hong wei， Tai Chiew Lan， Wang Guo jin. A Mesh Reconstruction Algor
ithm Driven by Intrinsic Property of Point Cloud[J]. Computer Aided Design， 2004， 36(1):1 9.
[18] 譚建榮， 李立新. 基于曲面局平特性的散亂點數據拓撲重建算法[J]. 軟件學報，2002，13(11):2121-2126.
[19] Huang J， Menq C H.Combinatorial Manifold Mesh Reconstruction and Optimization from Unorganized Points with Arbitrary Topology[J]. Computer Aided Design，2002，34(2):65-149.
[20] Gopi M，Krishnan S，Silva C T.Surface Reconstruction Based on Lower Dimensional Localized Delaunay Triangulation[J].Eurogra phics， 2000，19(3):467-478.
[21] 王青， 王融清， 鮑虎軍， 等. 散亂數據點的增量快速曲面重建算法[J].軟件學報， 2000， 11(9):1221-1227.
[22] 鄭順義，蘇國中，張祖勛.三維點集的自動表面重構算法[J].武漢大學學報(信息科學版)，2005，30(2):154-157.
作者簡介：李逢春(1976 )，男，重慶人，博士研究生，主要研究方向為三維地理信息系統、三維表面重建;龔俊(1978 )，男，博士研究生，主要研究方向為三維城市模型與海量空間數據管理;王青(1976 )，男，講師，博士，主要研究方向為計算機圖形學、幾何造型。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
