特征驅動的曲面重建

摘要：提出了基于散亂空間點集進行曲面重建的新方法，從點集的空間位置信息中提取待建曲面的內蘊特征量——法向和曲率，利用點集的這些特征信息來確定拓撲重建的搜索空間，采用面片生長的方式重建曲面。該方法在快速獲得正確拓撲連接的同時，直接生成了用較少的面片就能保持曲面特征的優化網格。

關鍵詞：曲面重建； 散亂點集； 逆向工程； 曲面特征

中圖分類號：TP391.72文獻標志碼：A

文章編號：1001－3695(2008)06－1756－03

近年來，隨著數據采集技術與計算機技術的迅速發展，基于散亂點集的曲面重建技術[1]，成為了計算機圖形學、CAD/CAM、虛擬現實等領域的研究熱點。該技術基于逆向工程原理，克服了傳統造型技術過程繁瑣且對于復雜實體在精度上難以滿足要求的缺點，從而受到了廣泛重視。本文從散亂點集的空間位置信息中提取反映曲面特征的法向量和曲率，并以法向量和曲率為驅動，以面片生長的方式，重建實體的表面網格，重建的網格以較少的三角形面片保持了模型表面的幾何特征，既精確又簡潔。

1基于散亂點集的曲面重建

基于散亂點集的曲面重建技術從實體模型出發，利用數據采集設備（如三維激光掃描儀），對實體的表面采樣，得到離散無序的點集；然后利用離散幾何信息處理技術，對這個點集進行拓撲和幾何處理，得到計算機能夠理解的實體曲面模型。散亂點集所包含的只是模型表面離散的空間位置信息，基于散亂點集的曲面重建的前提是散亂點集的采樣密度足夠大。

 為了獲得正確的拓撲連接和精確的網格形狀，基于散亂點集的曲面重建一般需要三個步驟：a）曲面拓撲的重建；b）網格形狀的優化;c）網格空間位置的優化。目前常用的算法有零集法[2]、α－shape法[3]、漸進網格法、Voronoi法[4]和基于點云內在性質驅動的網格重建算法(IPD)[5]等。其中，零集法生成的網格不經過原采樣點，只是一種近似的網格；α－shape法、Voronoi法生成的是插值網格曲面，但網格密度大，存儲量較大。同時這些算法受到采樣密度和均勻度的制約，而且在生成曲面的拓撲結構后仍需對網格進行形狀和空間的優化。IPD算法引進了采樣均勻度的概念；將重建網格中點所鄰接的最長邊與最短邊的長度比定義為點云在該點處的采樣均勻度，利用點云的內在性質，構造三角形面片。IPD算法重建的網格曲面體現了點云的內在性質，僅依賴于點云本身，它實際上是對點云限制在二維流形上的局部最小權三角剖分，就拓撲結構而言，它與被采樣物體的表面非常接近。但為了獲得精確的網格，仍需進行適當的優化，且對于均勻采樣密度的點云，網格存儲量較大。

 對于海量的散亂點集（點云），先前的方法主要基于點云的空間位置信息進行曲面拓撲的重建，不僅計算代價大，而且獲得的網格往往冗余信息多，存儲量大；重建后還需進一步對網格進行優化，以得到簡潔、精確的網格。

2特征驅動的曲面重建

曲率和法向是曲面的重要特征，反映曲面變化的趨勢和程度。在曲面重建時，以曲率和法向為驅動可以克服點云中點與點之間互相獨立、毫無關聯的缺點。其優點體現在兩個方面：

a）網格拓撲重建。對于點云中的任意一點，直接搜索與之拓撲相連的點，不僅計算代價大，而且難以保證連接的正確性。事實上，曲面上每點的法向量和曲率決定了與之拓撲相連點的搜索空間：點在法向的搜索高度與曲率成正比，在切向的搜索長度與曲率成反比，通過這一特性來限定搜索空間。在重建網格的拓撲結構時，可以減少計算代價，獲得正確的拓撲連接。

b）網格優化。優秀的網格應該是使用較少的面片來滿足重建曲面精度的要求。例如在局部平坦處應生成較大的面片，以減少網格的存儲量以及加速其他建立在網格基礎上的處理；在形狀變化劇烈處應生成較小面片，以保證曲面的精度。常規的基于點云的曲面重建方法在重建曲面的拓撲結構后，往往需要對所建網格進行優化。曲率驅動的三角形面片大小可自適應優化，能減小網格的存儲量，獲得優化的網格。

 基于這一思想，本文提出了曲面的特征曲率和法向重建曲面的方法。首先依據點云的空間信息，提取曲面在每一頂點處的曲率和法向；選擇一頂點建立第一個三角形面片（成為種子三角形）；以種子三角形的邊為基礎，選擇新的頂點生成新的三角形面片，直至生成完整的網格。在網格的生長過程中，以曲率和法向定義新頂點的搜索空間和面片的大小，同時完成網格的拓撲重建和優化，獲得精確、簡潔的網格。

2．1獲取點集的法向、曲率

表面采樣只能獲得模型表面離散的空間位置信息，不能直接得到曲面的法向和曲率信息。但作為內蘊幾何量的曲率和法向信息可以從點云數據的空間位置信息中獲取。策略是對每個頂點進行局部幾何重建，采用合適的曲面來擬合局部點集， 然后估計頂點法向量和曲面在該點的曲率值。文獻[6]提出了基于多層鄰域分解的局部重建和雙邊法向估計算法。首先對每個頂點的鄰域按歐式距離進行分層，根據頂點的法向確定一個初始切平面，將各層的鄰域點投影到這個切平面上；然后根據它們在平面上的旋轉角度大小依次連接各個投影點，最后連接空間鄰域點，使得它具有與平面投影點一致的拓撲關系。頂點的鄰域被分劃成若干層，因此每個頂點都附有若干個鄰域環，如圖1所示。

以鄰域的層次作為尺度空間參數σ， 取每個鄰域環中各三角形重心到該頂點的距離以及三角形面積作為權值參數， 對頂點進行雙邊法向估計：

曲率是法向的變化率，反映了曲面的彎曲程度和特征。常規地使用相鄰點法向量的差來度量曲面在該點的彎曲程度，但需要判斷法向量的正反方向，對于表面變化劇烈時不僅計算代價大，而且難以判斷法向量的方向。本文提出一種快速準確的曲率度量方法：對于給定點P，其k個近鄰點的集合記為P(k)，將P及 和P點的法向N(P)構造平面T(P)近似作為待建曲面S在P點的切平面。P(k)中每一點Pi到T(P)的投影為P′i，定義Pi相對P的彎曲程度為

2．2構造種子三角形

用生長法進行曲面重建時，首先要建立第一個三角形面片；然后以此面片的邊為基礎，按照一定的條件“生長”出其他面片；再以新面片的邊為基礎，繼續“生長”，直至所有的邊都處理完畢。曲面重建時，面片在曲面上的分布應該是曲率大的位置，面片小；曲率小的位置，面片大。筆者可在曲率最大處建立起第一個較小三角形面片，該三角形稱之為種子三角形（圖2）。步驟如下：

a)在點云中找到Cip值最大的點P;

b)找到與點P 距離最近的點Q， 它與點P 組成邊L;

c)構造以線段PQ 為軸、以PQ中點為中心、以PQ 的長度為直徑且以PQ為高的一個圓柱，使其半徑均勻增大，同時其高也沿著軸的兩個方向均勻增大，直到這個圓柱內包含點云中的點;

d)在上述圓柱所包含的點中，選取一個點R，使它與邊L 的兩個端點所構成的兩條邊的長度之和為最短，取這個點與邊L 構成的三角形△PQR 即為種子三角形。

2．3確定生長邊的搜索空間

網格的生長過程如圖3所示。其中，為兩個面片所共有的邊稱為成熟邊，不再參與網格的生長；只為一個面片所有的邊稱為生長邊。對于每一條生長邊，在其搜索空間內搜索新頂點，以構成新的三角形面片。若搜索不到滿足條件的頂點，則該生長邊被認為是邊界邊；若搜索到滿足條件的頂點，則該生長邊成為成熟邊。已生成的面片的頂點成為成熟點。

生長邊的搜索空間形狀為一四棱柱（圖4），由與生長邊所在的面片共面的四邊形sPjPkt拉伸而成。

2．4確定新頂點

新頂點Pn應該滿足以下條件：a）與已生成的面片有正確的拓撲關系（完整性）；b）在滿足一定精度的同時減小網格密度；c）盡量減少生成狹長三角形面片的生成。因此新頂點的確定采用如下方法：對于條件b），由于搜索空間的大小和方向都已作了嚴格的限定，搜索空間內的任意一點作為新頂點都能精確反映曲面的形狀。為了減少網格的密度，筆者選擇使△PcPjPk面積最大的點Pn作為新頂點的候選點。對于條件c），為了減少狹長三角形面片的產生，對候選點作合并測試：以候選點為中心，以r=α×max(PjPc，PkPc)為半徑（α=0．1~ 0．2）在搜索空間內搜索是否存在成熟點，若存在，則將該成熟點作為新候選點。對于條件a），對候選點進行完整性測試，如果△PcPjPk與生長邊PjPk搜索空間內的點所鄰接的已生成的三角面片之間的交集為空， 或者為已存在的生長邊或邊界邊，則此候選點即為新頂點；否則，將該點從搜索空間點云中除區，在搜索空間內重新選擇新的候選點并進行合并性和完整性測試。如果在搜索空間中找不到滿足條件的點， 則該邊為邊界邊。

3實驗結果與分析

在曲面重建中，記σ=C×D。當σ一定時，C與D成反比，即曲率較大處的重建面片較小，曲率較小處的重建面片較大。σ能夠反映曲面的整體特征。對于同一待建曲面，σ越大，相同頂點處重建的面片相對較大；反之，σ越小，重建的面片相對較小。σ可以控制曲面重建的精度。

對于一均勻采樣為1 500點散亂點集的空間曲面，取σ=0．3，曲面重建結果 如圖5所示，共使用81個頂點，128個面片；取σ=0．1，曲面重建結果如圖6所示，共使用225個頂點，420個面片；取σ=0．05，曲面重建結果如圖7所示，共使用300個頂點，532個面片。比對不同σ的重建結果，可以看出由于σ包含了曲面的曲率信息，重建時只使用參量σ即可整體保持曲面原有特征，同時σ的大小可以直觀反映重建曲面的精度，因而用戶可以方便地交互式重建和對重建結果的控制。

4結束語

特征驅動的曲面重建方法從散亂的空間位置信息中提取曲面的曲率和法向信息，進而充分利用這些特征信息來控制曲面的重建。所生成的網格總能保持待建曲面的特征，因而天然具備了優化、簡潔的特點，省去了其他重建方法所必需的網格優化過程，大大加快了曲面重建的速度。曲面的重建精度僅由單個參量確定，使得用戶可以方便地控制重建結果。

參考文獻：

［1］ZWICKER M，PFISTER H，VANBAAR J，et al.Surface splatting[C]//Procof ACM SIGGRAPH’01.2001:371－378.

[2] HOPPE H，DEROSE T，DUCHAMP T，et al.Surface reconstruction from unorganized points[C]//Proc of ACM SIGGRAPH. 1992:71－78．

[3] EDELSBRUNNER H，MCKE E. 3D alpha shapes[J]．ACM Trans on Graphics，1994，13(1):43－72．

[4] AMENTA N，BERN M，KAMVYSSELIS M．A new voronoi－based surface reconstruction algorithm[C]//Proc of ACM SIGGRAPH. 1998:415－421．

[5]LIN Hong－wei，TAI C L，WANG Guo－jin. A mesh reconstruction algorithm driven by intrinsic property of apoint cloud[J]．Computer－Aided Design，2004，36(1):1－9．

[6]胡國飛，彭群生．PBDGP:一個點模型的數字幾何處理平臺[R]．杭州：浙江大學，2004．

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文