三維點云模型區域選擇算法設計與實現

鮑彬　武云濤

摘要：本文提出一種基于射線的拾取算法和一種點云模型區域填充算法，實現了在點云模型上交互地選擇區域。本文將算法應用于點云模型實例，實驗結果表明提出的算法有效，快速且容易實現。

關鍵詞：點云模型;拾取;區域填充

中圖分類號：TP391.41 文獻標識碼：A 文章編號：1007-9416（2019）02-0126-02

0 引言

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

1 點云模型拾取方法

1.1 點云模型拾取的特點及拾取方法的選擇

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

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

1.2 點云模型上的射線拾取算法

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

2 點云模型區域的交互定義和預處理

點云模型上的點是散亂的，點之間沒有聯接關系，對于這個問題，首先采用前面提到的單元網格剖分點云數據，從而問題轉化為對包含點云數據盒子的填充。經過預處理，對點云模型的區域填充就轉化為對包含這塊區域中點的盒子的填充。區域的邊界是Dijkstra最短路徑算法計算得到的盒子序列。在點云模型上交互的拾取幾個點，用Dijkstra最短路徑算法計算兩點間連線，從而用線連結這幾個點，這樣就選中一塊區域。連接這幾個點的封閉曲線就構成區域的邊界。

3 點云模型區域填充

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

3.1 溢出分析

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

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

3.2 填充算法設計與實現

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

結合前文提出的射線拾取算法，使用OpenGL實現程序并在dragon點云模型上測試，實驗結果如圖3所示。

4 結語

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

參考文獻

[1] Tomas Akenine-Moller，Eric Haines.實時計算機圖形學（第2版）[M].北京：北京大學出版社，2004.

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

[3] 杜培林，屠長河，王文平.點云模型上測地線的計算[C].第二屆全國幾何設計與計算學術會議，2005.

[4] 唐榮錫，汪嘉業，彭群生.計算機圖形學教程[M].科學出版社，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