鮑彬　武云濤

摘要：本文提出一種基于射線的拾取算法和一種點(diǎn)云模型區(qū)域填充算法，實(shí)現(xiàn)了在點(diǎn)云模型上交互地選擇區(qū)域。本文將算法應(yīng)用于點(diǎn)云模型實(shí)例，實(shí)驗(yàn)結(jié)果表明提出的算法有效，快速且容易實(shí)現(xiàn)。

關(guān)鍵詞：點(diǎn)云模型;拾取;區(qū)域填充

中圖分類號：TP391.41 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2019）02-0126-02

0 引言

隨著各種三維掃描技術(shù)的迅速發(fā)展，三維掃描產(chǎn)生了大量的高精度、大數(shù)據(jù)量的模型，點(diǎn)云模型就是用物體表面大量采樣點(diǎn)來表示三維物體的高精度模型，對點(diǎn)云模型的處理已成為近年來研究的熱點(diǎn)。實(shí)現(xiàn)點(diǎn)云模型上的交互，能夠在點(diǎn)云模型上選擇感興趣的區(qū)域并得到其中的點(diǎn)云數(shù)據(jù)，這對于進(jìn)一步研究點(diǎn)云模型是很有意義的。點(diǎn)云模型上拾取的難點(diǎn)在于，點(diǎn)云模型要拾取的是大量點(diǎn)云數(shù)據(jù)中的一點(diǎn)，而通常圖形學(xué)中的交互是在場景中拾取某個物體，顯然點(diǎn)云模型上的拾取對拾取精確度有更高要求;另外由于點(diǎn)云數(shù)據(jù)量很大，對于效率也必須有更多的考慮。本文針對這些問題，設(shè)計(jì)了一種基于射線的拾取算法。點(diǎn)云模型上區(qū)域填充的難點(diǎn)在于，點(diǎn)云模型是由大量的離散點(diǎn)表示，點(diǎn)與點(diǎn)之間沒有任何拓?fù)渎?lián)系。首先采用單元網(wǎng)格剖分點(diǎn)云數(shù)據(jù)，將問題轉(zhuǎn)化為對包含點(diǎn)云數(shù)據(jù)盒子的填充，然后借鑒種子填充算法的思想設(shè)計(jì)填充算法。轉(zhuǎn)化之后，不能直接把種子填充算法擴(kuò)展到三維，這樣會出現(xiàn)填充溢出問題，本文重點(diǎn)分析了溢出的原因和路徑，得到點(diǎn)云模型上的一種有效區(qū)域填充算法。

1 點(diǎn)云模型拾取方法

1.1 點(diǎn)云模型拾取的特點(diǎn)及拾取方法的選擇

點(diǎn)云模型是用大量點(diǎn)來表示物體表面的模型，點(diǎn)云模型上的拾取問題是如何由屏幕上一點(diǎn)得到點(diǎn)云模型上的一點(diǎn)。點(diǎn)云模型上拾取的特點(diǎn)如：（1）點(diǎn)云模型要拾取的是大量點(diǎn)云數(shù)據(jù)中的一點(diǎn)，而通常圖形學(xué)中的交互是在場景中拾取某個物體，顯然點(diǎn)云模型上的拾取對拾取精確度有更高要求。另外由于點(diǎn)云數(shù)據(jù)量很大，對于效率也必須有更多的考慮。（2）點(diǎn)云模型上的點(diǎn)是離散的，即點(diǎn)與點(diǎn)之間是有空隙的，在點(diǎn)繪制時采用相應(yīng)的技術(shù)填充孔洞，從而得到連續(xù)的圖像。所以，屏幕上一點(diǎn)并不直接也不一一對應(yīng)點(diǎn)云上一點(diǎn)，它們之間的對應(yīng)關(guān)系還與繪制時填充孔洞的方式有關(guān)。這就使得點(diǎn)云模型上的拾取不容易得到完全精確的結(jié)果[1]。

基于上述特點(diǎn)，首先，選擇射線拾取的方式，是由于在常見的幾種射線拾取方法中，射線拾取是一種精確度和效率都比較高的方法。其次，算法設(shè)計(jì)中不能用射線直接與點(diǎn)比較，需要先預(yù)處理用單元網(wǎng)格剖分點(diǎn)云數(shù)據(jù)，轉(zhuǎn)化為射線與盒子求交。射線拾取的原理是：由于屏幕上繪制的實(shí)際上是人眼觀察的結(jié)果，所以屏幕上一點(diǎn)對應(yīng)于三維世界坐標(biāo)系中的一條射線。通過判斷這條射線與三維物體的相交情況，就可以得到拾取的結(jié)果。

1.2 點(diǎn)云模型上的射線拾取算法

點(diǎn)云模型上的點(diǎn)數(shù)量巨大且是散亂的，點(diǎn)與點(diǎn)之間存在空洞，所以不適合用射線直接與點(diǎn)比較。首先進(jìn)行預(yù)處理：用包圍盒劃分點(diǎn)云散亂點(diǎn)，從而轉(zhuǎn)化為射線與包圍盒求交。所以首先用單元網(wǎng)格剖分點(diǎn)云數(shù)據(jù)：用分別垂直于X，Y，Z三個坐標(biāo)軸的三組平行平面對點(diǎn)云數(shù)據(jù)進(jìn)行均勻剖分，X，Y，Z方向剖分的步長不同，得到若干長方體盒子，從而把點(diǎn)云數(shù)據(jù)劃分到若干盒子中[2]。其次通過射線逆運(yùn)算方法計(jì)算射線上兩點(diǎn)，從而確定屏幕上一點(diǎn)對應(yīng)的射線。將射線與垂直于Z軸的那組平行平面（預(yù)處理中用分別垂直于X，Y，Z軸的3組平行平面劃分點(diǎn)云數(shù)據(jù)）按Z值遞增的順序順次求交。對每一個平面，計(jì)算平面與射線的交點(diǎn)，然后計(jì)算交點(diǎn)所在的盒子號，判斷該盒子是否有效，直到找到第一個有效盒子，這就是射線拾取的盒子。上一步拾取的盒子中一般有幾個到十幾個點(diǎn)，計(jì)算這些點(diǎn)與射線的距離，取距離最小的一點(diǎn)為拾取得結(jié)果。

2 點(diǎn)云模型區(qū)域的交互定義和預(yù)處理

點(diǎn)云模型上的點(diǎn)是散亂的，點(diǎn)之間沒有聯(lián)接關(guān)系，對于這個問題，首先采用前面提到的單元網(wǎng)格剖分點(diǎn)云數(shù)據(jù)，從而問題轉(zhuǎn)化為對包含點(diǎn)云數(shù)據(jù)盒子的填充。經(jīng)過預(yù)處理，對點(diǎn)云模型的區(qū)域填充就轉(zhuǎn)化為對包含這塊區(qū)域中點(diǎn)的盒子的填充。區(qū)域的邊界是Dijkstra最短路徑算法計(jì)算得到的盒子序列。在點(diǎn)云模型上交互的拾取幾個點(diǎn)，用Dijkstra最短路徑算法計(jì)算兩點(diǎn)間連線，從而用線連結(jié)這幾個點(diǎn)，這樣就選中一塊區(qū)域。連接這幾個點(diǎn)的封閉曲線就構(gòu)成區(qū)域的邊界。

3 點(diǎn)云模型區(qū)域填充

區(qū)域填充是指將區(qū)域內(nèi)的一點(diǎn)（常稱種子點(diǎn)）賦予給定顏色，然后將這種顏色擴(kuò)展到整個區(qū)域內(nèi)的過程。在光柵圖形學(xué)中，區(qū)域是二維的并具備一定連通性：四連通或八連通。常用的算法是種子填充算法。用盒子表示的點(diǎn)云模型是三維模型，對于每一個盒子，邊鄰接的盒子是12個，點(diǎn)鄰接的是8個，面鄰接的是6個，所以共有26個鄰接的盒子，即點(diǎn)云模型上的區(qū)域是26連通的。將種子填充算法直接改為26連通就可以得到一個遞歸的填充算法，但是這個算法用于點(diǎn)云模型會出現(xiàn)填充溢出。下面通過分析溢出的原因和路徑，得到點(diǎn)云模型上的一種有效區(qū)域填充算法[3-4]。

3.1 溢出分析

點(diǎn)云模型是用大量的點(diǎn)來表示三維物體的表面，所以原問題是一個曲面填充問題，用一條封閉曲線作邊界，填充時不會溢出。經(jīng)過預(yù)處理，對點(diǎn)云模型的區(qū)域填充就轉(zhuǎn)化為對包含這塊區(qū)域中點(diǎn)的盒子的填充。問題轉(zhuǎn)化后的模型是26連通的3維體，形狀近似于曲面。要保證26連通的3維體一定不溢出，其邊界應(yīng)該是一個封閉的曲面。模型雖然形狀近似于曲面，但其實(shí)還是26連通的3維體，所以一條封閉的曲線作邊界不能保證不溢出。

以上是從理論上分析溢出原因，下面通過一個溢出實(shí)例分析溢出原因。從圖1所示中可以看到，盒子m是內(nèi)點(diǎn)，盒子n是外點(diǎn)。邊界無法阻擋從m到n的擴(kuò)散，即填充時會通過盒子m溢出。正如前面提到的盒子模型是26連通3維體，但其形狀是近似于曲面的，這就把溢出路徑限制在邊界附近。進(jìn)一步分析溢出路徑，圖2所示顯示了兩條邊界附近的溢出路徑，路徑1通過盒子b溢出，路徑2通過盒子c溢出。考慮點(diǎn)云模型的曲面是薄薄的一層點(diǎn)云，在把點(diǎn)劃分到盒子中時，盒子b中有點(diǎn)是很有可能的，但盒子c中有點(diǎn)的可能性就很小，即溢出路徑2發(fā)生的可能性很小。由以上分析猜測：算法1中的溢出都是通過邊界盒子的相鄰盒子溢出的。填充算法的設(shè)計(jì)就是基于這個猜測。

3.2 填充算法設(shè)計(jì)與實(shí)現(xiàn)

種子填充是遇到邊界點(diǎn)則停止擴(kuò)散，即對邊界點(diǎn)不再擴(kuò)散其鄰點(diǎn)。針對點(diǎn)云模型上的填充會通過邊界盒子的相鄰盒子溢出的情況，填充算法的思路就是若遇到一個盒子其相鄰盒子中有邊界盒子，則停止對該盒子擴(kuò)散。算法如下：對包含點(diǎn)云數(shù)據(jù)的盒子設(shè)置顏色，邊界盒子為border-color，邊界盒子的鄰接盒子為badj-color，種子盒子為new-color，其它有效盒子是old-color。建立堆棧S，初始時S中僅包含種子盒子。對于每個出棧的盒子，將其26個鄰接的盒子作如下處理：顏色為old-color的壓棧并置為new-color，顏色為border-color的置為new-color。反復(fù)這個過程直至S為空。最后，顏色為new-color的盒子就是填充結(jié)果，填充這些盒子中的點(diǎn)，就得到點(diǎn)云模型上的填充結(jié)果。

結(jié)合前文提出的射線拾取算法，使用OpenGL實(shí)現(xiàn)程序并在dragon點(diǎn)云模型上測試，實(shí)驗(yàn)結(jié)果如圖3所示。

4 結(jié)語

本文主要討論了點(diǎn)云模型上的拾取和區(qū)域填充問題，提出有效算法。并實(shí)現(xiàn)了在點(diǎn)云模型上交互地選擇區(qū)域得到區(qū)域中的點(diǎn)云數(shù)據(jù)，為進(jìn)一步研究點(diǎn)云模型提供了有用結(jié)果。對于拾取算法，還可以考慮將點(diǎn)云數(shù)據(jù)組織成一定的層次結(jié)構(gòu)，從而獲得更高的效率;另外，為了獲得更高的精確度，還可以進(jìn)一步考慮具體的點(diǎn)繪制方式。對于區(qū)域填充，本文提出的算法是基于一定的猜測的，雖然實(shí)驗(yàn)中證明這種猜測對于大多數(shù)情況是正確的，但是也不排除例外情況，還有進(jìn)一步研究的必要;另外，預(yù)處理有可能把相靠近的兩個面連接在一起，這時也會填充溢出，但這與算法無關(guān)，是模型轉(zhuǎn)化的問題，可以將盒子劃分的更密或者采用其它方式轉(zhuǎn)化模型。

參考文獻(xiàn)

[1] Tomas Akenine-Moller，Eric Haines.實(shí)時計(jì)算機(jī)圖形學(xué)（第2版）[M].北京：北京大學(xué)出版社，2004.

[2] OpenGL體系結(jié)構(gòu)審核委員會，Dave Shreiner，Mason Woo等. OpenGL編程指南（第四版）[M].人民郵電出版社，2005.

[3] 杜培林，屠長河，王文平.點(diǎn)云模型上測地線的計(jì)算[C].第二屆全國幾何設(shè)計(jì)與計(jì)算學(xué)術(shù)會議，2005.

[4] 唐榮錫，汪嘉業(yè)，彭群生.計(jì)算機(jī)圖形學(xué)教程[M].科學(xué)出版社，1994.

Design and Implementation of Region Selection

Algorithms for 3D Point Cloud Model

BAO Bin1， WU Yun-tao2

（1.Shangdong Woman University School of Data Science and Computer Science， Jinan Shandong? 250300;

2.Shandong Kaiwen College of Science & Technology， Jinan Shandong? 250200）

Abstract：In this paper a ray-based pick-up algorithm and a point cloud model area filling algorithm are proposed to realize the interactive selection of regions on the point cloud model. In this paper the algorithm is applied to the point cloud model. The experimental results show that the proposed algorithm is effective， fast and easy to implement.

Key words：point cloud model; pickup; region filling