大規(guī)模點(diǎn)云選擇及精簡(jiǎn)

范 然， 金小剛

（浙江大學(xué)CAD&CG國(guó)家重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310058）

逆向工程中最普遍的應(yīng)用模式是利用基于光學(xué)原理的掃描設(shè)備測(cè)量零件或模具外表面形成點(diǎn)云數(shù)據(jù)，從中提取幾何特征進(jìn)而重建多邊形或 NURBS曲面[1]。隨著掃描硬件精度的提升，原始掃描數(shù)據(jù)能夠較好逼近物理模型的曲面形態(tài)，但是，刪減處理始終是不可或缺的關(guān)鍵步驟。根據(jù)被測(cè)物體的擺放方式，掃描點(diǎn)云中不可避免地包含如墻面、支撐物等非目標(biāo)背景數(shù)據(jù)，解決這一問(wèn)題需設(shè)計(jì)能夠高效并靈活指定大規(guī)模點(diǎn)云中待刪除區(qū)域的選擇算法。此外，原始掃描點(diǎn)云通常由多次測(cè)量的單片數(shù)據(jù)拼合而成，接合處存在重疊冗余采樣，而且數(shù)據(jù)規(guī)模大、分布不均勻，普通計(jì)算機(jī)的計(jì)算及內(nèi)存資源不易直接對(duì)其進(jìn)行曲面重建。針對(duì)這一問(wèn)題，點(diǎn)云精簡(jiǎn)算法的目標(biāo)是減少數(shù)據(jù)量并使采樣點(diǎn)依幾何特征自適應(yīng)均衡分布。

由于常用計(jì)算機(jī)輸入方式是二維指針設(shè)備，二維套索UI是點(diǎn)云選擇最直觀的交互方式。研究領(lǐng)域通常使用簡(jiǎn)單空間形體實(shí)現(xiàn)點(diǎn)云選擇[2]，并未給出支持套索UI的點(diǎn)云選擇算法。目前，在逆向工程應(yīng)用領(lǐng)域中多使用Geomagic[3]、Rapidform[4]等商業(yè)軟件進(jìn)行處理，相關(guān)算法并未公開(kāi)，無(wú)法滿足研究領(lǐng)域構(gòu)建低成本三維掃描系統(tǒng)的需求。因此本文提出了一種支持套索UI的大規(guī)模點(diǎn)云選擇算法，利用套索形狀的矩形覆蓋與輸入點(diǎn)云八叉樹(shù)編碼剔除大部分點(diǎn)在多邊形內(nèi)判斷。不同于傳統(tǒng)的平面射線奇偶法及其改進(jìn)算法，本文方法利用了掃描點(diǎn)云密集分布的特點(diǎn)，能夠整體判斷點(diǎn)云的局部區(qū)域。

點(diǎn)云精簡(jiǎn)通常有兩種定義[5]：給定容許誤差閾值計(jì)算最小采樣數(shù)分布；給定目標(biāo)采樣點(diǎn)數(shù)目搜索最小誤差分布。在逆向工程中后者相對(duì)合理，用戶通常希望點(diǎn)云精簡(jiǎn)算法同時(shí)具備如下特性：1）任意指定目標(biāo)采樣點(diǎn)數(shù)目；2）不改變?cè)胁蓸狱c(diǎn)位置以維持掃描精度；3）盡可能保留尖銳幾何特征，依曲面曲率自適應(yīng)均衡分布。然而，傳統(tǒng)基于曲率自適應(yīng)[6]以及基于QEM誤差[7]的點(diǎn)云精簡(jiǎn)方法具有采樣點(diǎn)局部聚集以及不能保持尖銳邊特征與邊界的缺點(diǎn)。本文利用Poisson-disk采樣原理獲得簡(jiǎn)化后點(diǎn)云均衡分布的效果，并以采樣點(diǎn)鄰域球布爾交運(yùn)算來(lái)定義曲面上的圓盤半徑度量、擴(kuò)展采樣邊界，獲得了尖銳邊特征及邊界保持的性質(zhì)。

1 相關(guān)工作

點(diǎn)云選擇算法涉及如何判斷采樣點(diǎn)在視平面上的投影與套索多邊形之間的包含關(guān)系。Eric[8]總結(jié)了若干經(jīng)典的點(diǎn)在多邊形內(nèi)測(cè)試方法，包括射線奇偶、角度和、三角形扇等算法。在地理信息與圖形學(xué)領(lǐng)域，目標(biāo)應(yīng)用通常需實(shí)時(shí)測(cè)試大規(guī)模數(shù)據(jù)，經(jīng)典方法無(wú)法滿足速度指標(biāo)，后續(xù)研究采用基于區(qū)域分解的分治策略進(jìn)行優(yōu)化。Li[9]等分解多邊形為凸子域，將點(diǎn)在任意多邊形內(nèi)測(cè)試轉(zhuǎn)換為更為簡(jiǎn)單的點(diǎn)在凸多邊形內(nèi)測(cè)試。Zalik[10]等將多邊形所在區(qū)域分解為均勻單元格并賦予內(nèi)、外、邊界屬性，首先進(jìn)行簡(jiǎn)單的點(diǎn)在單元格內(nèi)測(cè)試，最后僅對(duì)包含于邊界單元格的點(diǎn)執(zhí)行完整測(cè)試。Yang[11]等利用近似最近點(diǎn)概念提高了均勻單元格方法的準(zhǔn)確度。本文注意到現(xiàn)存方法僅注重分解或降低多邊形復(fù)雜性然后進(jìn)行逐個(gè)單點(diǎn)測(cè)試，針對(duì)大規(guī)模掃描點(diǎn)云數(shù)據(jù)密集分布的特點(diǎn)，將輸入點(diǎn)云組織為八叉樹(shù)層次結(jié)構(gòu)，以局部區(qū)域?yàn)閱卧袛喟P(guān)系，剔除大部分點(diǎn)在多邊形內(nèi)測(cè)試。

隨著基于點(diǎn)的繪制與造型技術(shù)的發(fā)展，已經(jīng)存在許多算法簡(jiǎn)化點(diǎn)云數(shù)據(jù)。根據(jù)精簡(jiǎn)點(diǎn)云采樣分布形成的方式可將現(xiàn)有方法分為3類：迭代最優(yōu)剔除、層次聚類、曲面重采樣。不同的方法分別側(cè)重減少原始點(diǎn)云與精簡(jiǎn)后點(diǎn)云之間的距離、曲率自適應(yīng)、分布質(zhì)量等方面。迭代最優(yōu)剔除方法的優(yōu)點(diǎn)在于采樣前后的點(diǎn)云距離誤差小，缺點(diǎn)在于隨著點(diǎn)云規(guī)模的增加由于全局排序、屬性更新需要大量的內(nèi)存與計(jì)算消耗，不適合逆向工程中海量點(diǎn)云高效精簡(jiǎn)，且不容易保留尖銳邊特征與邊界。Pauly[7]等將三角網(wǎng)格的QEM簡(jiǎn)化算法推廣到點(diǎn)云上。Linden[12]提出一種綜合的采樣點(diǎn)影響度，每次移除最小影響度的采樣點(diǎn)。Song[13]等首先識(shí)別出尖銳特征采樣點(diǎn)并予以保留，其余采樣點(diǎn)依次按照影響度排序迭代去除。層次聚類方法具有計(jì)算效率高的優(yōu)點(diǎn)，其缺點(diǎn)是不容易控制采樣點(diǎn)的分布與誤差。Lee[6]等采用非均勻八叉樹(shù)對(duì)點(diǎn)云進(jìn)行聚類并以法向變動(dòng)控制八叉樹(shù)細(xì)分，效率較高，但精簡(jiǎn)點(diǎn)云分布不均勻。Yu[14]等利用k-means算法對(duì)點(diǎn)云進(jìn)行層次分割，采用局部協(xié)方差分析控制聚類過(guò)程，雖然分布質(zhì)量提高但無(wú)法精確指定采樣點(diǎn)數(shù)目。Shi[15]等同樣利用k-means算法獲得了類似的效果。Song[16]等采用全局聚類方法具有更加優(yōu)良的分布效果，但由于其全局優(yōu)化特性計(jì)算效率較低?，F(xiàn)有的曲面重采樣方法直接從分布特性角度出發(fā)，能夠獲得理論上最優(yōu)采樣點(diǎn)分布，但由于通常需計(jì)算流形上的距離或維持采樣點(diǎn)之間的動(dòng)態(tài)平衡，其所消耗的計(jì)算資源也是最大的。Moenning[17]等利用Fast Marching方法漸進(jìn)計(jì)算內(nèi)蘊(yùn)Voronoi圖以實(shí)現(xiàn)最遠(yuǎn)點(diǎn)采樣策略。Pauly[7]等人將粒子平衡模擬方法推廣到點(diǎn)云上。

上述3類方法分別體現(xiàn)了優(yōu)化、數(shù)據(jù)分析、幾何結(jié)構(gòu)分析的思想，本文的點(diǎn)云精簡(jiǎn)方法屬于曲面重采樣，基于Poisson-disk采樣均勻分布采樣點(diǎn)、防止過(guò)度集中，利用鄰域球布爾交運(yùn)算擴(kuò)展可用采樣邊界，如圖9和圖10所示由于尖銳邊特征以及邊界數(shù)據(jù)不容易被周圍鄰域球覆蓋從而被密集采樣。與本文目標(biāo)最接近的方法是Kang[18]等提出的均衡點(diǎn)云采樣方法，不同之處在于基于Poisson-disk采樣的方法能夠通過(guò)采樣半徑調(diào)整點(diǎn)云分布。

2 支持套索UI的大規(guī)模點(diǎn)云選擇算法

點(diǎn)云選擇的套索UI接口與圖像區(qū)域選擇類似，用戶旋轉(zhuǎn)點(diǎn)云模型至合適方位后草繪套索多邊形、圈選目標(biāo)區(qū)域，如圖1(a)和圖1(b)所示，遴選出投影在套索多邊形之內(nèi)的點(diǎn)云區(qū)域。最基本的實(shí)現(xiàn)方式是將每個(gè)采樣點(diǎn)投影在視平面上逐個(gè)進(jìn)行點(diǎn)在多邊形內(nèi)測(cè)試，然而對(duì)于百萬(wàn)級(jí)甚至千萬(wàn)級(jí)的掃描點(diǎn)云數(shù)據(jù)，該方法無(wú)法獲得理想的交互性能。

圖1 套索UI點(diǎn)云選擇

本文算法受到Zalik[10]等方法的啟發(fā)，該方法主要針對(duì)地理信息應(yīng)用，不適合直接用于選擇掃描點(diǎn)云數(shù)據(jù)。首先，該方法只能處理簡(jiǎn)單曲線，在點(diǎn)云區(qū)域選擇中，限制用戶輸入的套索形狀為簡(jiǎn)單曲線并不合理。本文提出的算法構(gòu)造了輸入多邊形的矩形區(qū)域覆蓋并利用改進(jìn)的射線奇偶法賦予內(nèi)、外、邊界屬性，圖2比較了Zalik[10]等方法與本文方法處理非簡(jiǎn)單曲線的差異。

圖2 輸入非簡(jiǎn)單曲線，從紙張點(diǎn)云模型中選擇數(shù)據(jù)

此外，本文注意到掃描點(diǎn)云數(shù)據(jù)通常是密集分布的，因此，將原始點(diǎn)云嵌入八叉樹(shù)層次結(jié)構(gòu)，利用節(jié)點(diǎn)單元在視平面上投影與矩形覆蓋之間的幾何包含關(guān)系剔除大部分點(diǎn)在多邊形內(nèi)測(cè)試。

2.1 套索多邊形矩形覆蓋

給定多邊形P，由邊列表{E1,E2,… ,En}構(gòu)成，其中Ei連接頂點(diǎn)(xi,yi)和 (xi+1,yi+1)。設(shè)C為任意矩形，定義P的矩形覆蓋為{Ci}，要求矩形之間無(wú)交集且所有矩形的并集覆蓋了P所在區(qū)域，即：DC(P) = {Ci|∪iCi?Pand ?i≠jCi∩Cj=?}。本文利用四叉樹(shù)計(jì)算DC(P)，主要有兩個(gè)優(yōu)點(diǎn)：能夠根據(jù)多邊形P的距離場(chǎng)自適應(yīng)確定矩形數(shù)量；索引矩形計(jì)算量較小。設(shè)c為四叉樹(shù)節(jié)點(diǎn)單元，其位置由坐標(biāo)函數(shù)x0(c),x1(c),y0(c),y1(c)確定，點(diǎn)(x,y)∈c：x0(c) ≤x＜x1(c)與y0(c) ≤y＜y1(c)。DC(P)由四叉樹(shù)的所有末端子節(jié)點(diǎn)構(gòu)成。根據(jù)與P的相對(duì)幾何位置分別賦予矩形單元內(nèi)部、外部、邊界屬性，其中邊界屬性是指P穿越該矩形，此外矩形單元的大小取決于相對(duì)于P的距離，即遠(yuǎn)離P的矩形較大，邊界矩形較小。DC(P)由遞歸分裂四叉樹(shù)節(jié)點(diǎn)構(gòu)建而成，根節(jié)點(diǎn)是覆蓋P的正方形。節(jié)點(diǎn)分裂由以下形狀誤差決定：

其中ci是四叉樹(shù)節(jié)點(diǎn)，vij是其四個(gè)頂點(diǎn)之一，dist(vij)表示到P的距離函數(shù)。由于距離函數(shù)在P內(nèi)部中軸附近存在一階不連續(xù)使得線性逼近誤差較大、節(jié)點(diǎn)分裂過(guò)多，為減少包含測(cè)試計(jì)算量通常需以盡可能少的矩形分別覆蓋P的內(nèi)、外、邊界區(qū)域。因此(1)中顯式地判斷了ci是否具有邊界屬性。DC(P)的復(fù)雜性取決于P以及分裂閾值Te，該閾值由用戶指定或者根據(jù)P的最小線段長(zhǎng)度即P的分辨率確定，當(dāng)err(ci)＞Te時(shí)分裂ci為4個(gè)子節(jié)點(diǎn)。

計(jì)算上述矩形覆蓋需判斷ic是否具有邊界屬性，如果P是凸多邊形則可以通過(guò)對(duì)ic四個(gè)頂點(diǎn)執(zhí)行點(diǎn)在多邊形內(nèi)測(cè)試得知其是否具有邊界屬性。對(duì)于一般的多邊形，如果ic的4條邊與P沒(méi)有交點(diǎn)，根據(jù)連續(xù)性推斷P沒(méi)有穿越ic即不具有邊界屬性。本文采用結(jié)合單元邊交點(diǎn)偵測(cè)的射線奇偶算法判斷單元的內(nèi)、外、邊界屬性，如圖3所示該方法能夠正確地賦予邊界屬性。

對(duì)于ci的每個(gè)頂點(diǎn)分別發(fā)射水平與豎直方向且與ci的邊部分重合的射線，統(tǒng)計(jì)射線與P的交點(diǎn)數(shù)目并偵測(cè)交點(diǎn)是否落在ci的邊上。以從ci的左上角頂點(diǎn) (x0(ci),y1(ci))發(fā)射水平射線rright為例，對(duì)于所有Ej∈P，判斷與rright的穿射關(guān)系。

圖3 基于四叉樹(shù)的矩形覆蓋，藍(lán)色、綠色、紅色分別表示外部、內(nèi)部、邊界屬性

在DC(P)計(jì)算完成后，為了在后續(xù)測(cè)試中減少可能的求交運(yùn)算，將組成P的所有線段嵌入矩形單元中。本文采用Lastra[19]等的射線穿透四叉樹(shù)訪問(wèn)算法。設(shè)iE∈P，以t為參數(shù)可表示為：

其中(dx,dy)是單位方向向量。首先確定包含起始頂點(diǎn)(xi,yi)的末端節(jié)點(diǎn)cs，移除包含在cs中的Ei部分、更新ts，同時(shí)將Ei記錄在cs中；對(duì)于cs的父節(jié)點(diǎn)cp計(jì)算其4條邊所在直線與Ei方向射線r的交點(diǎn)參數(shù)：

并按照下式斷定Ei是否穿透cp：

對(duì)于滿足式(5)的cp，考察其所有子節(jié)點(diǎn)并移除Ej中被包含的部分，交替進(jìn)行以上兩步直至到達(dá)終止頂點(diǎn) (xi+1,yi+1)。

2.2 點(diǎn)在多邊形內(nèi)測(cè)試

掃描點(diǎn)云具有密集分布的特點(diǎn)，可利用其空間一致性剔除大部分點(diǎn)在多邊形內(nèi)測(cè)試。本文將點(diǎn)云嵌入在八叉樹(shù)G內(nèi)，每個(gè)末端子節(jié)點(diǎn)不超過(guò)64個(gè)采樣點(diǎn)。從根節(jié)點(diǎn)開(kāi)始，將節(jié)點(diǎn)立方體gi∈G沿視線方向投影為側(cè)影輪廓多邊形gi′，其邊界由同時(shí)鄰接可見(jiàn)面與不可見(jiàn)面的立方體邊投影而成，可見(jiàn)性由面法向與視線向量?jī)?nèi)積確定。判斷gi′與DC(P)矩形之間的幾何包含關(guān)系，分3種情況處理：

1）gi′包含在單個(gè)非邊界矩形內(nèi)的，將gi內(nèi)所有采樣點(diǎn)標(biāo)識(shí)為與該矩形同樣的屬性；

2）gi′的所有頂點(diǎn)皆落在內(nèi)部或者外部區(qū)域，偵測(cè)gi′的邊與P的交點(diǎn)，采用Feito[20]等方法，無(wú)需計(jì)算出交點(diǎn)，并且已將P的邊嵌入在DC(P)中因此只需做局部判斷，如果沒(méi)有交點(diǎn)將gi內(nèi)所有采樣點(diǎn)標(biāo)識(shí)為gi′所在區(qū)域的屬性；

3）gi′與具有邊界屬性的矩形有交集，遞歸處理gi′的子節(jié)點(diǎn)；

如果仍有末端節(jié)點(diǎn)gi′具有邊界屬性，將gi內(nèi)的采樣點(diǎn)投影在視平面上，如果落于具有內(nèi)、外屬性的矩形內(nèi)，則賦予同樣的屬性。最后對(duì)落于邊界矩形內(nèi)的采樣點(diǎn)執(zhí)行基于射線奇偶的點(diǎn)在多邊形內(nèi)測(cè)試。經(jīng)過(guò)上述層次測(cè)試步驟只有很少的一部分采樣點(diǎn)需執(zhí)行完整的點(diǎn)在多邊形內(nèi)測(cè)試，因而能夠提升大規(guī)模點(diǎn)云區(qū)域選擇的效率。

帶預(yù)處理階段的包含測(cè)試策略其核心在于將針對(duì)復(fù)雜多邊形的測(cè)試轉(zhuǎn)化為針對(duì)一組簡(jiǎn)單多邊形的測(cè)試，這一策略有利于快速判斷大量采樣點(diǎn)針對(duì)同一多邊形的位置。不同于之前的工作，本文基于點(diǎn)云密集分布、具有空間一致性的特性，將點(diǎn)云組織為八叉樹(shù)結(jié)構(gòu)，利用投影八叉樹(shù)節(jié)點(diǎn)單元與多邊形矩形覆蓋之間的包含關(guān)系剔除了大部分點(diǎn)在多邊形內(nèi)測(cè)試。

3 基于Possion-disk采樣的點(diǎn)云精簡(jiǎn)

在點(diǎn)云精簡(jiǎn)過(guò)程中顯式地控制采樣點(diǎn)分布對(duì)于尖銳邊特征保持、邊界保持、平坦與彎曲區(qū)域之間的均衡分布至關(guān)重要。其他基于減少簡(jiǎn)化前后點(diǎn)云間距離、曲率自適應(yīng)的精簡(jiǎn)方法通常會(huì)造成采樣點(diǎn)局部聚集、且不能密集采樣尖銳邊特征以及邊界數(shù)據(jù)。后續(xù)應(yīng)用如三角化、基于點(diǎn)的繪制、形狀約束動(dòng)畫等的效果非常依賴于點(diǎn)云數(shù)據(jù)的分布質(zhì)量。本文首先估計(jì)采樣點(diǎn)法向，進(jìn)而利用Poisson-disk采樣控制采用點(diǎn)的分布，但由于Poisson-disk采樣的控制參數(shù)是采樣半徑因而不容易控制采樣點(diǎn)數(shù)目，本文對(duì)初步采樣結(jié)果依采樣點(diǎn)Voronoi鄰域面積進(jìn)行排序，向稀疏區(qū)域添加以及從擁擠區(qū)域移除采樣點(diǎn)以達(dá)到目標(biāo)精簡(jiǎn)數(shù)目。

3.1 法向估計(jì)

原始點(diǎn)云來(lái)源于不同的掃描技術(shù)，可分為帶有法向與缺失法向兩種情況。對(duì)于不具備法向信息的數(shù)據(jù)本文采用Pauly[7]等的方法，對(duì)每一個(gè)采樣點(diǎn)pi利用局部協(xié)方差分析計(jì)算其法向ni，pi鄰域的協(xié)方差矩陣為：

其中Ni是采樣點(diǎn)pi的鄰域，包括k個(gè)最近采樣點(diǎn)，是位置均值。然后進(jìn)行特征值分解并以其最小特征值向量作為該點(diǎn)的法向：

圖4 法向雙邊濾波

需要指出的是本文算法并不需要統(tǒng)一法向定向，法向僅用于確定采樣點(diǎn)的切平面。采用式(7)計(jì)算的法向?qū)τ诠饣c(diǎn)云數(shù)據(jù)能夠較好地逼近被測(cè)曲面法向，但不能良好表示逆向工程中常見(jiàn)的具有尖銳邊特征的機(jī)械模型，而且增加采樣分辨率并不能解決這一問(wèn)題[21]。因此，本文采用法向雙邊濾波[22]，使得尖銳邊特征兩側(cè)法向數(shù)據(jù)分區(qū)域平滑：

3.2 點(diǎn)云Possion-disk采樣

Poisson-disk采樣具有兩種性質(zhì)，即采樣點(diǎn)符合隨機(jī)分布、采樣點(diǎn)之間的距離不小于2r，其中r是每個(gè)采樣點(diǎn)所屬圓盤的半徑。飛鏢投擲算法是最直接的生成方法，即隨機(jī)生成新的采樣點(diǎn)并判斷該點(diǎn)所屬圓盤是否被已經(jīng)存在的采樣點(diǎn)圓盤覆蓋。投擲成功率隨著采樣點(diǎn)的增加而降低因而算法效率較低。Dunbar[23]等提出了基于邊界區(qū)域增長(zhǎng)的平面Poisson-disk采樣算法，如圖5所示，采樣點(diǎn)及其所屬圓盤用紅色表示，可用采樣邊界用藍(lán)色表示，初始3個(gè)采樣點(diǎn)增長(zhǎng)為6個(gè)采樣點(diǎn)。采樣過(guò)程主要包括兩步：在可用邊界上隨機(jī)采樣、更新可用采樣邊界。

圖5 平面Poisson-disk采樣，藍(lán)色表示可用采樣邊界

在曲面上進(jìn)行Poisson-disk采樣需定義適合的距離度量以確定每個(gè)采樣點(diǎn)的影響域，F(xiàn)u[24]等將Dunbar[23]的方法推廣到三角網(wǎng)格曲面上，利用測(cè)地距離計(jì)算網(wǎng)格曲面上的等距線從而擴(kuò)展采樣邊界。但是對(duì)于掃描點(diǎn)云數(shù)據(jù)，拓?fù)湫畔⑷笔А⒎植疾痪鶆蚴沟煤茈y直接在點(diǎn)云上計(jì)算測(cè)地距離。本文的關(guān)鍵想法是基于Klein[25]等提出定義點(diǎn)云曲面的球影響圖方法，對(duì)采樣點(diǎn)ip定義半徑為2r的鄰域球Bi，所有采樣點(diǎn)鄰域球的集合構(gòu)成對(duì)點(diǎn)云曲面的覆蓋，將可用采樣邊界定義在采樣點(diǎn)切平面與鄰域球的交集上，可用采樣邊界的擴(kuò)展通過(guò)鄰域球布爾交運(yùn)算實(shí)現(xiàn)。如圖6所示，在加入新的采樣點(diǎn)后，Bi內(nèi)可用采樣邊界消去了鄰域球Bj沿法向投影覆蓋的部分。

采樣邊界更新后，從當(dāng)前所有采樣點(diǎn)鄰域球內(nèi)可用采樣邊界的集合中隨機(jī)選取點(diǎn)p′，然后查找p′在點(diǎn)云中的最近點(diǎn)作為下一個(gè)采樣點(diǎn)。其中，對(duì)每個(gè)已有采樣點(diǎn)的采樣邊界賦予一概率值iq，隨長(zhǎng)度減少以及采樣次數(shù)增加而減少。

圖6 鄰域球布爾交運(yùn)算，可用采樣邊界用藍(lán)色表示，被消去的采樣邊界用紅色表示

本文算法同樣可用于點(diǎn)云重采樣，只需將最近點(diǎn)查找替換為移動(dòng)最小二乘點(diǎn)云曲面投影計(jì)算即可。算法主要計(jì)算量在于鄰域球布爾交運(yùn)算以及搜索最近點(diǎn)。采樣半徑r根據(jù)原始點(diǎn)云的的近似面積S按照下式計(jì)算[24]：

其中n是目標(biāo)精簡(jiǎn)數(shù)目，ρ是疏密控制參數(shù)一般取為0.7，S根據(jù)原始點(diǎn)云的球影響圖計(jì)算[25]。點(diǎn)云Poisson-disk采樣算法步驟如下：

Step 1根據(jù)原始點(diǎn)云近似面積估計(jì)采樣半徑，隨機(jī)選擇一個(gè)初始采樣點(diǎn)，生成初始可用采樣邊界。

Step 2根據(jù)每段可用采樣邊界的概率值，隨機(jī)選取新的備選點(diǎn)，查找該點(diǎn)在點(diǎn)云中的最近點(diǎn)作為新的采樣點(diǎn)。

Step 3利用鄰域球布爾交運(yùn)算更新可用采樣邊界，降低當(dāng)前更新的可用采樣邊界段的概率值。

Step 4迭代2，3步直到所有鄰域球內(nèi)采樣邊界段最大概率值低于預(yù)先指定值Qτ。

初步采樣結(jié)果接近預(yù)先指定的采樣點(diǎn)數(shù)目，但由于Poisson-disk采樣的控制參數(shù)是采樣半徑因而不容易精確達(dá)到該數(shù)目，本文對(duì)初步采樣結(jié)果依采樣點(diǎn)Voronoi鄰域面積進(jìn)行排序，迭代向稀疏區(qū)域添加或者從擁擠區(qū)域移除采樣點(diǎn)以達(dá)到目標(biāo)精簡(jiǎn)數(shù)目。

Poisson-disk采樣保證了相鄰采樣點(diǎn)之間的距離不小于2r從而防止了在高曲率區(qū)域產(chǎn)生局部聚集以及在平坦區(qū)域均衡分布。同時(shí)，如圖6所示，可用采樣邊界的更新依賴于鄰域球的交集在曲面切平面內(nèi)的投影，因此，在尖銳特征附近，由于法向差異較大導(dǎo)致相對(duì)密集的采樣。

4 討論與比較

本文的實(shí)驗(yàn)平臺(tái)是Intel?Core?2雙核處理器，1.86GHz，2G內(nèi)存，NVIDIA GTS450顯卡，Windows XP?操作系統(tǒng)。

圖7顯示了點(diǎn)云選擇算法性能測(cè)試的真實(shí)掃描樣例數(shù)據(jù)，如圖8所示本文算法的速度快于射線奇偶法，對(duì)于規(guī)模較大的數(shù)據(jù)效果更加明顯。同時(shí)本文與商業(yè)軟件Geomagic[3]的點(diǎn)云選擇功能進(jìn)行了比較，獲得了接近的用戶體驗(yàn)。表1顯示了本文點(diǎn)云選擇算法的具體統(tǒng)計(jì)數(shù)據(jù)，主要包括矩形覆蓋計(jì)算時(shí)間、內(nèi)外判斷時(shí)間以及單點(diǎn)包含測(cè)試剔除率。通過(guò)實(shí)驗(yàn)可以看出，主要計(jì)算時(shí)間消耗在構(gòu)建矩形覆蓋階段；采樣點(diǎn)數(shù)目與多邊形復(fù)雜性共同決定了計(jì)算時(shí)間，例如圖7(d)的時(shí)間消耗大于圖7(e)；大部分點(diǎn)在多邊形內(nèi)測(cè)試被剔除，因而大大提升了交互速度。

圖7 點(diǎn)云選擇算法測(cè)試?yán)?/p>

圖8 點(diǎn)云選擇算法速度比較

如圖8所示，速度曲線圖中數(shù)據(jù)依頂點(diǎn)增長(zhǎng)順序分別對(duì)應(yīng)圖7中的(a)、(b)、(c)、(d)、(e)。紅色曲線表示射奇偶法，綠色曲線表示本文方法

表1 點(diǎn)云選擇算法統(tǒng)計(jì)數(shù)據(jù)表

本文與經(jīng)典的曲率柵格以及均勻柵格[6]點(diǎn)云精簡(jiǎn)方法進(jìn)行了比較。首先為了測(cè)試對(duì)尖銳邊特征與邊界的保持，針對(duì)立方體模型以及紙張模型進(jìn)行了實(shí)驗(yàn)，其中立方體點(diǎn)云是由計(jì)算機(jī)生成的，紙張點(diǎn)云是真實(shí)的單幅掃描數(shù)據(jù)。如圖9與圖10所示，相較于曲率柵格與均勻柵格方法，本文算法加強(qiáng)了對(duì)尖銳邊特征以及邊界數(shù)據(jù)的采樣，并在平坦區(qū)域均衡分布采樣點(diǎn)。

圖11顯示了對(duì)真實(shí)掃描數(shù)據(jù)進(jìn)行精簡(jiǎn)的例子，結(jié)果表明本文的方法在保持尖銳邊特征與邊界數(shù)據(jù)的同時(shí)防止了采樣點(diǎn)局部聚集，獲得了更加均衡的分布，因而更加有利于高質(zhì)量三角化，基于點(diǎn)的繪制以及形狀約束動(dòng)畫[26]。

圖9 立方體模型點(diǎn)云精簡(jiǎn)

圖10 紙張模型點(diǎn)云精簡(jiǎn)

圖11 龍頭模型點(diǎn)云精簡(jiǎn)

本文采用Cignoni[27]等方法定量計(jì)算了精簡(jiǎn)點(diǎn)云重構(gòu)曲面與原始點(diǎn)云之間的距離，本文算法與曲率柵格方法結(jié)果的平均距離誤差分別為0.0329 與0.1556。這是由于該數(shù)據(jù)背面是光滑曲面，曲率柵格方法未能均衡曲率采樣與均勻分布。如圖12所示，本文算法在平坦區(qū)域形成了良好的分布因而誤差比曲率柵格方法低，在曲率較大區(qū)域由于采樣點(diǎn)數(shù)量相對(duì)稀疏因而誤差比曲率柵格方法高。

圖13 龍頭模型點(diǎn)云精簡(jiǎn)誤差分析

5 結(jié) 論

本文提出了面向逆向工程、用于消除原始掃描點(diǎn)云中存在無(wú)效背景數(shù)據(jù)、冗余采樣、分布不均勻等問(wèn)題的點(diǎn)云選擇與精簡(jiǎn)算法。點(diǎn)云選擇算法支持套索UI接口，通過(guò)套索多邊形的矩形覆蓋與點(diǎn)云八叉樹(shù)節(jié)點(diǎn)投影之間的包含關(guān)系剔除大部分點(diǎn)在多邊形內(nèi)測(cè)試，達(dá)到了商業(yè)軟件的交互性能。點(diǎn)云精簡(jiǎn)算法利用Poisson-disk采樣控制簡(jiǎn)化后點(diǎn)云的分布，與經(jīng)典曲率柵格方法的比較結(jié)果表明本文算法具有保持尖銳邊特征、保持邊界、分布均衡的優(yōu)勢(shì)。

[1]Wang W. Reverse engineering technology of reinvention [M]. New York: CRC Press, 2011: 6-11.

[2]Weyrich T, Pauly M, Heinzle S, et al. Post-processing of scanned 3D surface data [C]//Proceedings of Eurographics Symposium on Point-Based Graphics.New York: ACM Press, 2004: 85-94.

[3]Geomagic studio. Geomagic studio user’s guide [M].Carolina: Geomagic Studio, 2008: 8-12.

[4]Inus Technology. RapidForm2004 user guide and tutorial [M]. Korea: Inus Technology Inc, 2004:59-62.

[5]張麗艷, 周儒容, 蔡煒斌, 等. 海量測(cè)量數(shù)據(jù)簡(jiǎn)化技術(shù)研究[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2001,13(11): 1023-1119.

[6]Lee K H, Woo H, Suk T. Point data reduction using 3D grids [J]. The International Journal of Advanced Manufacturing Technology, 2001, 18(3): 201-210.

[7]Pauly M, Gross M, Kobbelt L P. Efficient simplification of point-sampled surfaces [C]//Proceedings of the Conference on Visualization,Washington D C: IEEE Press, 2002: 163-170.

[8]Haines Eric. Point in polygon strategies, graphics gems IV [M]. San Diego: Academic Press, 1994:24-26.

[9]Li Jing, Wang Wencheng, Wu Enhua. Point-in-polygon tests by convex decomposition [J]. Computers &Graphics, 2007, 31(4): 636-648.

[10]Zalik B, Kolingerova I. A cell-based point-in-polygon algorithm suitable for large sets of points [J].Computers & Geosciences, 2001, 27(10): 1135-1145.

[11]Yang S, Yong J H, Sun J, et al. A point-in-polygon method based on a quasi-closest point [J]. Computers& Geosciences, 2010, 36(2): 205-213.

[12]Linsen L. Point cloud representation. Universitat Karlsruhe [M]. CS technical report, 2001: 6-8.

[13]Song H, Feng H Y. A progressive point cloud simplification algorithm with preserved sharp edge data [J]. The International Journal of Advanced Manufacturing Technology, 2009, 45(5-6): 583-592.

[14]Yu Zhiwen, Wong Hansan, Peng Hong, et al. ASM:an adaptive simplification method for 3D point-based models [J]. Computer-Aided Design, 2010, 42(7):598-612.

[15]Shi Baoquan, Liang Jin, Liu Qing. Adaptive simplification of point cloud using k-means clustering [J].Computer-Aided Design, 2011, 43(8): 910-922.

[16]Song Hao, Feng Hsiyung. A global clustering approach to point cloud simplification with a specified data reduction ratio [J]. Computer-Aided Design, 2007,40(3): 281-292.

[17]Moenning C, Dodgson N A. Intrinsic point cloud simplification [C]//Proceedings of the 14th International Conference on Computer Graphics and Vision. Moscow, 2004: 1147-1154.

[18]Kang E C, Kim D B, Lee K H. Balanced feature-sensitive point sampling for 3D model generation [J]. The International Journal of Advanced Manufacturing Technology, 2007, 38(1-2): 130-142.

[19]Lastra M. An efficient parametric algorithm for octree traversal [J]. Journal of WSCG, 2000, 8(2): 212-219.

[20]Feito F R, Torres J C, Urena A. Orientation, simplicity,and inclusion test for planar polygons [J]. Computers& Graphics, 1995, 19(4): 595-600.

[21]Kobbelt L P, Botsch M, Schwanecke U, et al. Feature sensitive surface extraction from volume data [C]//Proceedings of the ACM SIGGRAPH. New York:ACM Press, 2001: 57-66.

[22]Zheng Y, Fu H, Au O K C, et al. Bilateral normal filtering for mesh denoising [J]. IEEE Transactions on Visualization and Computer Graphics, 2010, 17(10):1521-1530.

[23]Dunbar D, Humphreys G. A spatial data structure for fast poisson-disk sample generation [J]. ACM Transactions on Graphics, 2006, 25(3): 503-508.

[24]Fu Yan, Zhou Bingfeng. Direct sampling on surfaces for high quality remeshing [J]. Computer Aided Geometric Design, 2009, 26(6): 711-723.

[25]Klein J, Zachmann G. Point cloud surfaces using geometric proximity graphs [J]. Computers &Graphics, 2004, 28(6): 839-850.

[26]Zhao Hanli, Fan Ran, Wang Charlie C L, et al.Fireworks controller [J]. Journal of Visualization and Computer Animation, 2009, 20(2-3): 185-194.

[27]Cignoni P, Rocchini C, Scopigno R. Metro: measuring error on simplified surfaces [J]. Computer Graphics Forum, 1998, 17(2): 167-174.