基于海量點(diǎn)云的曲面增量擴(kuò)展重建算法*

徐 昭，孫殿柱，薄志成

(山東理工大學(xué) 機(jī)械工程學(xué)院，山東 淄博 255049)

0 引言

曲面重建技術(shù)在CAD/CAM、機(jī)器視覺、工業(yè)制造等領(lǐng)域具有廣泛應(yīng)用。三維掃描設(shè)備的發(fā)展，使得點(diǎn)云數(shù)據(jù)的采樣規(guī)模日趨龐大，如何通過掃描得到的海量點(diǎn)云數(shù)據(jù)，高效地重建出能夠準(zhǔn)確反映原始物體細(xì)節(jié)特征的高精度曲面，一直以來都是國內(nèi)外研究的熱點(diǎn)問題[1]。國內(nèi)外學(xué)者針對(duì)曲面重建算法進(jìn)行了大量研究。Digne等[2]從一個(gè)初始三角形開始，通過某種準(zhǔn)則不斷選擇新點(diǎn)加入構(gòu)成新的三角網(wǎng)格，該算法的重建速度快但卻無法保證重建結(jié)果的拓?fù)湔_性。文獻(xiàn)[3-6] 采用隱函數(shù)逼近的方法構(gòu)造網(wǎng)格曲面，重建結(jié)果較為光滑但不適用于描述帶有明顯細(xì)節(jié)特征的實(shí)物表面。Amenta等[7]提出經(jīng)典Cocone算法的重建結(jié)果具有理論保證，但基于全局進(jìn)行Delaunay網(wǎng)格剖分時(shí)空復(fù)雜度太高，不適用于處理海量點(diǎn)云。Dey等[10]隨后基于局部Delaunay網(wǎng)格剖分提出的Localized-Cocone算法可適用于重建海量點(diǎn)云且重建結(jié)果具有理論保證，但該算法需對(duì)局部樣本進(jìn)行多次Delaunay網(wǎng)格剖分，嚴(yán)重降低了整體采樣點(diǎn)集的重建效率。

本文采用二維Delaunay網(wǎng)格剖分與三維Delaunay網(wǎng)格過濾相結(jié)合的方法重建曲面局部樣本，然后基于波前擴(kuò)展策略將局部重建過程傳播至整個(gè)采樣點(diǎn)集，最終獲得插值于整體采樣點(diǎn)集的二維定向流形網(wǎng)格曲面。在局部重建過程中，通過鑒別所生成面片相關(guān)樣點(diǎn)Cocone近鄰點(diǎn)的完整性，來保證局部重建結(jié)果的正確性。實(shí)驗(yàn)表明：本文算法能夠在保證重建結(jié)果拓?fù)湔_性的基礎(chǔ)上，顯著提高海量點(diǎn)云數(shù)據(jù)的重建效率，且適用于重建封閉和非封閉曲面。

1 局部重建結(jié)果正確性準(zhǔn)則

在局部重建過程中，由于局部樣本邊界樣點(diǎn)的拓?fù)浣徯畔⑷笔В沟蒙傻木植烤W(wǎng)格邊界區(qū)域面片重建不準(zhǔn)確。鑒于經(jīng)典Cocone算法的重建結(jié)果具有理論保證，若能保證局部網(wǎng)格Cocone重建正確，即可保證局部重建結(jié)果的正確性。

(1)

當(dāng)所生成三角面片的對(duì)偶Voronoi邊穿過該面片各頂點(diǎn)的Cocone區(qū)域時(shí)，將該面片稱為Cocone面片，對(duì)Cocone面片集合進(jìn)行修剪和流形提取[9]，即可獲得拓?fù)渫瑯?gòu)于原表面的網(wǎng)格曲面。由此可知，在面片生成過程中，若能正確構(gòu)造其相關(guān)樣點(diǎn)的Co-cone區(qū)域，則可保證該面片重建的正確性。

針對(duì)局部重建網(wǎng)格中具有完整的拓?fù)鋱A盤結(jié)構(gòu)的任意樣點(diǎn)，在能夠準(zhǔn)確獲取其Cocone近鄰點(diǎn)之后，將網(wǎng)格中Cocone近鄰點(diǎn)不完全位于該局部樣本中的樣點(diǎn)相關(guān)面片刪除，即可保證局部重建結(jié)果的正確性。

2 局部重建

采用經(jīng)典Cocone算法對(duì)海量點(diǎn)云局部樣本進(jìn)行重建，獲得局部二維定向流形網(wǎng)格；然后將局部網(wǎng)格中Cocone近鄰點(diǎn)不均位于該局部樣本中樣點(diǎn)的相關(guān)面片刪除，局部重建完成。

為避免局部平坦區(qū)域樣本因存在共面情況而無法進(jìn)行三維Delaunay 網(wǎng)格剖分的問題，可在局部樣本重建之前任取該樣本中不共線的三個(gè)點(diǎn)構(gòu)造參考平面F，計(jì)算局部樣本λ(p)中的樣點(diǎn)至參考平面F距離的均方根dRMS，其中，

(2)

式(2)中N為局部樣本中的樣點(diǎn)數(shù)量，然后根據(jù)均方根dRMS與尺度閾值ω之間關(guān)系，判定是否共面。針對(duì)共面點(diǎn)集，可通過投影剖分的方法確定各樣點(diǎn)之間的連接關(guān)系。

設(shè)整體點(diǎn)集為S，將S內(nèi)特定樣點(diǎn)p的鄰域點(diǎn)集作為局部樣本λ(p)。局部重建流程如圖1所示。

圖1 局部重建流程圖

對(duì)局部樣本λ(p)進(jìn)行重建的效果如圖2所示。在對(duì)λ(p)構(gòu)建參考平面F時(shí)，若λ(p)非初始局部樣本，則可依據(jù)獲取λ(p)的特定樣點(diǎn)及其法向量來構(gòu)建參考平面F。否則，F(xiàn)可由λ(p)中任意不共線的三個(gè)點(diǎn)來確定。

圖2 局部重建效果圖

3 局部重建網(wǎng)格波前擴(kuò)展

流形提取后的局部網(wǎng)格為二維流形結(jié)構(gòu)，可根據(jù)該結(jié)構(gòu)的面-邊映射關(guān)系提取波前環(huán)。提取流程為：遍歷局部網(wǎng)格邊鏈表，將關(guān)聯(lián)面片數(shù)為1的邊作為波前邊，對(duì)獲取的波前邊集合進(jìn)行排序，使其首尾順次連接構(gòu)成封閉波前環(huán)，并將波前環(huán)上的點(diǎn)標(biāo)記為波前點(diǎn)。

3.1 波前環(huán)的擴(kuò)張

通過初始局部重建網(wǎng)格獲得的波前環(huán)作為傳播主環(huán)Rpri，波前環(huán)的擴(kuò)張以Rpri為基礎(chǔ)。選擇Rpri的首結(jié)點(diǎn)pr，求取pr的k近鄰點(diǎn)集λ(pr)，并對(duì)λ(pr)進(jìn)行重建，并將提取的波前環(huán)作為局部子環(huán)Rloc。當(dāng)Rpri∩Rloc為Rloc上前后連續(xù)銜接的波前點(diǎn)時(shí)，如圖3所示，則滿足波前環(huán)的擴(kuò)張條件，該過程可表示為：

Rpri←Rpri⊕Rloc

(3)

Rpri的擴(kuò)張具體可分為波前環(huán)的向外擴(kuò)張(圖3a)和向內(nèi)擴(kuò)張(圖3b)，擴(kuò)張后的傳播主環(huán)應(yīng)保持環(huán)向不變。

(a) 傳播主環(huán)向外擴(kuò)張

(b) 傳播主環(huán)向內(nèi)擴(kuò)張 圖3 傳播主環(huán)的擴(kuò)張

3.2 波前環(huán)的分裂

當(dāng)Rpri∩Rloc為Rloc上非連續(xù)的波前點(diǎn)時(shí)，如圖4所示，則滿足傳播主環(huán)的分裂條件，Rpri將分裂為兩個(gè)分支，該過程可表示為：

{Rpri_1,Rpri_2}←Rpri⊕Rloc

(4)

對(duì)于局部子環(huán)Rloc上的點(diǎn)p，若p滿足：①p∈Rpri∩Rloc，②p在Rloc上的前向節(jié)點(diǎn)或后向節(jié)點(diǎn)不屬于Rpri，則稱p為分裂點(diǎn)。如果Rloc上p的后向節(jié)點(diǎn)不屬于Rpri，定義p為后向分裂點(diǎn)，如果Rloc上p的前向節(jié)點(diǎn)不屬于Rpri，定義p為前向分裂點(diǎn)，如果Rloc上p的前向節(jié)點(diǎn)與后向節(jié)點(diǎn)都不屬于Rpri，則定義p為雙向分裂點(diǎn)。通過上述分析可知，當(dāng)Rloc上分裂點(diǎn)個(gè)數(shù)為2時(shí)，需要對(duì)環(huán)進(jìn)行擴(kuò)張，當(dāng)分裂點(diǎn)個(gè)數(shù)大于2時(shí)，需要進(jìn)行環(huán)的分裂，而環(huán)的分裂又可根據(jù)分裂后新環(huán)之間是否為包含關(guān)系分為環(huán)的外部分裂和環(huán)的內(nèi)部分裂。

如圖4a所示為環(huán)的內(nèi)部分裂，圖4b所示為環(huán)的外部分裂。對(duì)于傳播主環(huán)Rpri，其分裂步驟如下：

Step1: 從pr開始，遍歷局部子環(huán)Rloc，查找首次出現(xiàn)的后向分裂點(diǎn)pb。

Step2: 檢測Rpri和Rloc在prpb間的波前點(diǎn)的傳遞方向是否相同，若相同，則此次分裂為環(huán)的外部分裂，并轉(zhuǎn)至Step4，否則此次分裂為內(nèi)部分裂，執(zhí)行Step3。

Step3: 反轉(zhuǎn)Rloc的環(huán)向，并重復(fù)Step1的操作，重新查找點(diǎn)pb。

Step4: 以pb為起點(diǎn)，分別遍歷Rloc和Rpri，以首次出現(xiàn)的且相同的pz或pf為終點(diǎn)， 兩分裂點(diǎn)間遍歷的有序點(diǎn)集組成新環(huán)Rpri-1。

(a) 傳播主環(huán)內(nèi)部分裂

(b) 傳播主環(huán)外部分裂 圖4 傳播主環(huán)的分裂

4 曲面增量擴(kuò)展重建

通過鑒別面片相關(guān)樣點(diǎn)Cocone近鄰點(diǎn)的完整性，可保證局部重建結(jié)果的正確性；基于波前環(huán)的擴(kuò)張、分裂可將局部重建過程逐步延伸，從而實(shí)現(xiàn)整體點(diǎn)云數(shù)據(jù)的增量擴(kuò)展重建。此外，為提升局部重建樣本的獲取效率，可采用R*樹[11]作為海量點(diǎn)云的空間索引。綜上所述，海量點(diǎn)云的曲面增量擴(kuò)展重建算法完整流程如圖5所示。

圖5 曲面增量擴(kuò)展重建流程圖

如圖6所示，在網(wǎng)格波前擴(kuò)展過程中，新生成的網(wǎng)格能夠與已重建完成的網(wǎng)格完整融合，最終可獲得一張完整的二維流形網(wǎng)格曲面。

圖6 曲面增量擴(kuò)展重建效果圖

5 實(shí)驗(yàn)分析

為驗(yàn)證本文算法的有效性，在硬件配置為HP xw8600 Workstation(2.5GHz，4.0GB內(nèi)存)，操作系統(tǒng)為GNU/Linux的實(shí)驗(yàn)環(huán)境下，分別利用Ball -Pivoting算法、 Localized-Cocone算法及本文算法對(duì)具有代表性的不同點(diǎn)云模型進(jìn)行測試。圖7a所示 Venus 模型為含有邊界的非封閉點(diǎn)云，圖7b所示 Happy Buddha 模型為封閉點(diǎn)云，但存在樣點(diǎn)分布不均勻以及曲率變化較大的區(qū)域。這兩種點(diǎn)云模型可充分代表曲面重建過程中常見的點(diǎn)云狀態(tài)。

(a) Venus 點(diǎn)云模型 (b) Happy Buddha點(diǎn)云模型 圖7 實(shí)驗(yàn)數(shù)據(jù)

Venus點(diǎn)云模型的重建效果如圖8所示。在該模型邊界區(qū)域，Localized-Cocone算法的重建結(jié)果存在狹長面片(圖8 b)，而基于波前環(huán)擴(kuò)張、分裂的Ball-Pivoting算法和本文算法在模型邊界區(qū)域有較好的重建效果，因此本文算法適用于重建非封閉曲面。Happy Buddha 點(diǎn)云模型的重建效果如圖9所示。Ball-Pivoting 算法的重建結(jié)果在該模型樣點(diǎn)分布不均勻及曲率變化較大區(qū)域存在孔洞(圖9 a)，而基于Delaunay剖分的Localized-Cocone算法和本文算法的重建結(jié)果不存在孔洞，且本文算法與Localized-Cocone算法的重建結(jié)果相同，因此本文算法重建的網(wǎng)格曲面能夠準(zhǔn)確反映原始曲面的拓?fù)溧徑雨P(guān)系。

(a) Ball-Pivoting算法

(b) Localized-Cocone算法

(c) 本文算法 圖8 不同算法對(duì)Venus 模型重建結(jié)果

(a) Ball-Pivoting算法

(b) Localized-Cocone算法

(c) 本文算法

圖10展示了本文算法與Ball-Pivoting 算法、Localized-Cocone算法對(duì)不同數(shù)量點(diǎn)云模型的重建時(shí)間對(duì)比。此實(shí)驗(yàn)中，Localized-Cocone算法所需參數(shù)為八叉樹停止細(xì)分時(shí)子節(jié)點(diǎn)中所能包含樣點(diǎn)數(shù)量的最大值，根據(jù)文獻(xiàn)[10]中的推薦設(shè)為500K。本文算法所需參數(shù)為局部樣本的獲取數(shù)量k，經(jīng)過大量實(shí)驗(yàn)驗(yàn)證，建議k取100。Ball-Pivoting算法的重建效率高于本文算法，但其重建結(jié)果不具備理論保證。Localized-Cocone算法重建結(jié)果具有理論保證，但該算法為實(shí)現(xiàn)各塊局部重建網(wǎng)格的準(zhǔn)確拼接，需要對(duì)八叉樹每個(gè)子節(jié)點(diǎn)中的局部樣本進(jìn)行多次Delaunay三角剖分，重建時(shí)間明顯高于本文算法。因此，在能夠保證重建結(jié)果拓?fù)湔_性的前提下，本文算法相比于Localized-Cocone算法，在重建效率方面至少提高了30%。

圖10 不同算法的重建時(shí)間對(duì)比

6 結(jié)束語

本文提出的曲面增量擴(kuò)展重建算法具有以下特點(diǎn)：①將基于Delaunay網(wǎng)格剖分的重建算法應(yīng)用于曲面局部區(qū)域，并通過波前擴(kuò)展策略實(shí)現(xiàn)整體點(diǎn)集的增量重建，避免了全局三維Delaunay剖分帶來的高復(fù)雜度問題，能夠?qū)⒑Ａ奎c(diǎn)云的重建效率提高30%以上。②通過鑒別局部重建網(wǎng)格邊界區(qū)域面片相關(guān)樣點(diǎn)Cocone近鄰點(diǎn)的完整性來保證局部重建結(jié)果的正確性，之后將此局部重建結(jié)果進(jìn)行波前擴(kuò)展，從而正確重建整體點(diǎn)集，得到與原表面拓?fù)渫瑯?gòu)的網(wǎng)格曲面。③由于最終得到的完整曲面是經(jīng)過波前環(huán)的擴(kuò)張、分裂等方式逐步擴(kuò)展而成，因此適應(yīng)于封閉和非封閉曲面的重建。