特征驅(qū)動的曲面重建

摘要：提出了基于散亂空間點集進(jìn)行曲面重建的新方法，從點集的空間位置信息中提取待建曲面的內(nèi)蘊(yùn)特征量——法向和曲率，利用點集的這些特征信息來確定拓?fù)渲亟ǖ乃阉骺臻g，采用面片生長的方式重建曲面。該方法在快速獲得正確拓?fù)溥B接的同時，直接生成了用較少的面片就能保持曲面特征的優(yōu)化網(wǎng)格。

關(guān)鍵詞：曲面重建； 散亂點集； 逆向工程； 曲面特征

中圖分類號：TP391.72文獻(xiàn)標(biāo)志碼：A

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

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

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

基于散亂點集的曲面重建技術(shù)從實體模型出發(fā)，利用數(shù)據(jù)采集設(shè)備（如三維激光掃描儀），對實體的表面采樣，得到離散無序的點集；然后利用離散幾何信息處理技術(shù)，對這個點集進(jìn)行拓?fù)浜蛶缀翁幚恚玫接嬎銠C(jī)能夠理解的實體曲面模型。散亂點集所包含的只是模型表面離散的空間位置信息，基于散亂點集的曲面重建的前提是散亂點集的采樣密度足夠大。

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

 對于海量的散亂點集（點云），先前的方法主要基于點云的空間位置信息進(jìn)行曲面拓?fù)涞闹亟ǎ粌H計算代價大，而且獲得的網(wǎng)格往往冗余信息多，存儲量大；重建后還需進(jìn)一步對網(wǎng)格進(jìn)行優(yōu)化，以得到簡潔、精確的網(wǎng)格。

2特征驅(qū)動的曲面重建

曲率和法向是曲面的重要特征，反映曲面變化的趨勢和程度。在曲面重建時，以曲率和法向為驅(qū)動可以克服點云中點與點之間互相獨(dú)立、毫無關(guān)聯(lián)的缺點。其優(yōu)點體現(xiàn)在兩個方面：

a）網(wǎng)格拓?fù)渲亟āτ邳c云中的任意一點，直接搜索與之拓?fù)湎噙B的點，不僅計算代價大，而且難以保證連接的正確性。事實上，曲面上每點的法向量和曲率決定了與之拓?fù)湎噙B點的搜索空間：點在法向的搜索高度與曲率成正比，在切向的搜索長度與曲率成反比，通過這一特性來限定搜索空間。在重建網(wǎng)格的拓?fù)浣Y(jié)構(gòu)時，可以減少計算代價，獲得正確的拓?fù)溥B接。

b）網(wǎng)格優(yōu)化。優(yōu)秀的網(wǎng)格應(yīng)該是使用較少的面片來滿足重建曲面精度的要求。例如在局部平坦處應(yīng)生成較大的面片，以減少網(wǎng)格的存儲量以及加速其他建立在網(wǎng)格基礎(chǔ)上的處理；在形狀變化劇烈處應(yīng)生成較小面片，以保證曲面的精度。常規(guī)的基于點云的曲面重建方法在重建曲面的拓?fù)浣Y(jié)構(gòu)后，往往需要對所建網(wǎng)格進(jìn)行優(yōu)化。曲率驅(qū)動的三角形面片大小可自適應(yīng)優(yōu)化，能減小網(wǎng)格的存儲量，獲得優(yōu)化的網(wǎng)格。

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

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

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

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

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

2．2構(gòu)造種子三角形

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

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

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

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

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

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

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

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

2．4確定新頂點

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

3實驗結(jié)果與分析

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

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

4結(jié)束語

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

參考文獻(xiàn)：

［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:一個點模型的數(shù)字幾何處理平臺[R]．杭州：浙江大學(xué)，2004．

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