直接精簡密集點云的三角網格重建

董天琪　張志毅

(西北農林科技大學信息工程學院　陜西 楊凌 712100)

?

直接精簡密集點云的三角網格重建

董天琪張志毅*

(西北農林科技大學信息工程學院陜西 楊凌 712100)

摘要為解決快速傳輸需求，從稠密點云直接生成精簡的三角網格模型，提出一種自適應立體柵格劃分方法，并給出以立體柵格為基本單元的三角網格重建過程。首先以各點無差異的宏觀估測方法獲得立體柵格的邊長，將點云數據分割為柵格單元。然后選取基本單元中數據點為種子點，設定三角形邊長以近似正6鄰域為約束，構建初始三角網格，再逐層外擴完成三角網格重建。該方法的優點在于可將簡化和重建過程融為一體。實驗結果表明所提方法速度較快，魯棒性較好。

關鍵詞精簡密集點云網格重建外擴

0引言

點云數據是對現實世界物體形狀最自然的表示方法之一，但是它不能表示物體的拓撲信息。近些年來已經有多種成熟的測量設備能夠高速獲取現實場景的三維點云數據。表面重建是從點云重構出忠實于原始曲面的三角形網格過程。其在逆向工程、數據可視化、機器視覺、虛擬現實、醫療技術等領域中都具有廣泛的應用。文獻[1]回顧了國內外的研究現狀及商業軟件開發情況，對目前逆向工程研究與應用存在的問題及解決的對策提出了討論。目前也出現了文獻[2]這種針對性較強的研究成果。散亂點云曲面重建的關鍵在于拓撲結構的正確建立，而由于數據信息的不完整性，這也成為曲面重建的難點所在。根據現有算法的特點，可以將它們分為以下幾類：隱式曲面算法、參數曲面算法、基于學習的方法、Delaunay三角剖分算法等。隱曲面方法[3]重建效果良好，但模型較難選定。Delaunay方法研究成果眾多，文獻[4,5]中的Crust方法最為廣泛。Cocone方法[6]也是備受關注的方法之一。Crust方法較為復雜，而Cocone方法則需要針對不同點云數據進行相應的方法的變化。對于大規模的數據來講，Delaunay方法重建速度慢。文獻[7]提出一種基于Delaunay三角化區域增長式的曲面重建方法。較以往方法具有人為參與更少、適用范圍更廣的優點，但算法效率有待提高。外擴方法容易理解和實現，但將三角形添加進已三角化的區域是其難點。其他方法[8-10]有的通過Voronoi圖，有的利用平面投影線加快建模速度，有的基于多視圖的三維模型進行重建。

隨著激光掃描設備的發展，包含被測物體更多細節的大量數據的獲取成為可能。針對高密度點云數據，文獻[11]中提出首先采用基于密度聚類的方法篩選三維點云，然后進行網格重建。浙江大學的藺宏偉等人[12]提出了根據點云內在屬性進行重建的方法。文獻[13]提出了對數據進行柵格化的方法，但沒有給出一個合適的柵格規則。文獻[14]采用自適應八叉樹分割點云的方法進行表面模型重建，提高了模型重建的效率，也能夠體現點云模型的細節特征，但與傳統的三角網生長法相比，有一定的冗余網格。本文提出一種自適應立體柵格劃分方法，并給出以立體柵格為基本單元實現三角網格重建的實現過程，解決了快速傳輸需求。對于高密度的點云精簡重建速度快，并且具有可將簡化和重建過程融為一體的優點。

1概念

已知集合P，對于其中的任一點p，定義該點的r鄰域點為點集P中到p點距離不大于r的點集合，即：

定義該點的環域點為點集P中到p點距離介于r+σ與r-σ之間的點的集合，即：

2算法描述

2.1獲得長方體包圍盒

要實現對點云的分割，首先要獲得散亂點云的長方體包圍盒。遍歷全部點云，找到x，y，z三個坐標軸方向上最小和最大的共六個點，分別只取它們在對應坐標軸上的分量，組成兩個點，記為兩個點Pmax，Pmin，這兩個點即長方體包圍盒最長對角線的兩個端點。

2.2劃分立方體柵格及立方體邊長選擇策略

長方體包圍盒的長、寬、高，分別除以立方體的邊長，向上取整，即得點云分別在x，y，z坐標方向上立方體的個數，記為CubeNum(x,y,z)。立方體的編號通過它在x、y、z坐標方向上的編號組成的一個向量Id(x,y,z)來表示，獲取鄰域環域時需要檢索立方體的編號，為檢索方便，需將此立方體編號轉化為整數，方法如下：

L=Idx×CubeNumy×CubeNumz+Idy×CubeNumz+Idz

檢索鄰域和環域受影響的立方體時，實際上使用的是數字L。

在劃分立方體柵格的過程中，立方體的邊長的選擇尤為重要，它的大小直接影響到模型的重建效果。其具體的選擇策略描述如下。

由于掃描得到的是表面點，而立方體是根據長方體包圍盒來劃分的，所以在物體的內部會有很多空的立方體。因此不能用體積來計算，本文選擇使用表面積進行計算。實際上是利用了長方體包圍盒的表面積近似等于所要重建的模型的表面積。

通過計算可以得出長方體包圍盒的長、寬、高即Pmax-Pmin所得的x、y、z分量，分別記為Px、Py、Pz，長方體包圍盒的表面積近似表示為物體的表面積，即：

(PxPy+PxPz+PyPz)×2

記為S。另外，點云中點的個數即總點數記為N。為便于后期對生成的網格進行曲面擬合，每個非空立方體內至少要有多個數據點存在，一般為滿足三次曲面擬合，至少應有16個點，具體所取數值記為n，N除以n即可以得出需要立方體的個數。立方體邊長記為a，綜上所述，得出：

即：

(1)

劃分的立方體，以編號命名文件保存立方體中的點，并非所有連續編號的立方體都有其對應的文件，沒有點的立方體不會生成文件，所以效率上并沒有多余的浪費。

2.3重建過程

2.3.1初次外擴方法

重建的第一步是獲取種子點。由于是擴展重建，所以適宜從點云的中心開始，本文所有實驗均選取距離長方體包圍盒中心最近的點。根據2.1節中得到的Pmax，Pmin計算長方體包圍盒的中心，遍歷所有點得到距離中心最近的點設為初始種子點。

得到種子點后，要根據種子點進行外擴。對于一次外擴，它的準備工作有以下幾項。

? 第二，根據鄰域點集計算該鄰域的微切平面，得到微切平面的法向量。目的是為后續排序工作確定z軸正向。

? 第三，對環域點集進行排序。排序需要一個值作為排序的標記點。已知種子點O，如果當前生成的三角形是第一個三角形，則當前三角形的第二個頂點可在環域中隨機選取，如果當前生成的三角形不是第一個三角形，則由于隊列的搜索順序并不可隨機選取。具體的排序方法為：標記點記為A，OA作為微切平面上的x軸正向，z軸正向為微切平面的法向量與O點之差，由此既確定搜索的時針時序，本文采用逆時針搜索。計算環域點與O點連線與OA夾角的cos值，并計算叉乘結果與z軸正向比較，即知該點與OA的逆時序夾角是否超過180°，如果超過則取負值并減去2，使得cos函數在0～2π上是變成一個連續的遞減函數，由此可以根據它對環域點進行排序。

準備工作做好后，接下來就是三角形生成的過程。具體策略如下。

圖1　找到合適點組成三角形狀況圖

依次檢查排序后環域中的點與A點的距離，找到距A點最接近L的點。對于大部分數據來說，不需要搜索整個環域，只需所求點滿足一定條件即認為已找到。本文設置找到點距A大于0.6L即標記為已找到，0.6L為下限，保證等腰三角形的底角以70°至75°為上限而非過于苛刻得要求正三角形。由于搜索的環域已經排序，當搜索到距1.4L(1.4L為上限，即保證等腰三角形的底角以45°為下限。)的位置，會判斷是否已經找到合適的點。如果沒有找到，則進行分類討論：若當前點已滿足與隊頭的位置關系，則直接處理；若不合適則將當前點而非點A作為新三角形的第一個點，繼續向下搜索。如果找到則跳出循環判斷該點與隊頭的位置關系。判斷點與隊頭位置關系的策略如下。

找到合適點的情形如圖1所示，點J為找到的合適點。

圖1中，B為當前種子點，隊列順序為CDEFGHI。判斷J與隊頭C的關系并做相應處理。本文將其分為以下三種情況：

a.如果JC較大，本文設為大于2L。說明扇形BJC可以容納不止一個三角形，則先生成△BIJ，返回搜索。

b.如果JC非常小，本文設置為小于0.4L，此時本文認為IC接近于1.4L，滿足上文中以45°為等腰三角形底角下限的要求。繼而認為IC≈IJ≈L(由于模型是立體的，圖1顯示為平面效果，所以實際上IC不一定通過B，尤其在JC非常小的前提下)，則生成三角形△BIC。種子點變為C。

c.如果JC中等大小，本文設置為0.5L至2L，即至少可容納兩個底角最大即70°～75°的等腰三角形，至多容納兩個底角最小即45°的等腰三角形，滿足上文的條件，此時直接生成兩個三角形，△BIJ和△BJC。種子點變為C。

2.3.2外擴整體過程及方法

外擴是一個隊列遍歷種子點不斷生成三角形，不斷有新種子點入隊、舊種子點出隊的過程。本文中搜索順序是從隊尾搜索到隊頭，直到隊列中沒有點。由于始終采取逆時針遍歷，每當數據點出隊即作為當前種子時，除第一次擴展需特殊處理外(只需設置標記位即可解決此問題)，當前種子的搜索區域始終是隊尾—當前種子點—隊伍這樣一個扇形區域，如圖2-圖3所示。

圖2　左側為第一次擴展圖，右側為第二次擴展圖

圖3　第三次擴展圖

圖2左側為第一次擴展圖，種子點為O，此時隊列中點的順序為ABCDEF，右側為進一步進行擴展圖，種子點為A，隊列中點的順序為BCDEFGHI，此時以A為種子點時的搜索區域正是左側圖對應種子序列從隊頭到隊尾的扇形區域。

但是這樣并不能保證所有的點都被遍歷，需要在外側再設置循環，判斷是否所有的點標記為已讀。最終得到三角網格。

3實驗與分析

本文算法采用C語言實現，并在主頻為2.60GHz，內存2GB的PC機上進行測試。本文分別對標準試驗數據斯坦福兔子和實驗室掃描的實測數據進行了測試。

斯坦福兔子數據包含數據點20 002個，根據本文介紹的劃分立方體方法計算得到(以下數值均為取整后數值)，Pmax=(511,441,508)，Pmin=(200,200,200)，Px、Py、Pz分別為311、241、308，繼而表面積S=489 934，根據前文所述，n取16，則由式(1)計算得a約為19.7，取整為20。式(1)中S和N都為確定值，所以，有且僅有n的取值影響a。n的取值為滿足三次曲面擬合所取數值。為測試實驗結果，本文將n取4、8又可得到a=10、a=14兩個值。即最終本文分別取小立方體邊長a為10、14、20進行實驗，得到結果比對如圖4和表1所示。圖4展示了立方體邊長分別取不同數值的效果及原始數據效果。表1列出了重建的詳細信息。

圖4　左上為立方體邊長為10的結果，右上為立方體邊長為14的結果，左下為立方體邊長為20的結果，右下為原始高密度點云的效果

立方體邊長立方體個數三角形個數用時(s)102918412122.690141499241014.50120741184312.188

由表1可知，本文對于密集散亂點云的網格數據精簡重建速度快，且根據歐拉公式可算出對應于立方體邊長選10、14、20時的簡化率分別為89.686%，93.966%，95.380%的前提下，本文所提出的方法均能保持基本形狀，有良好的魯棒性。

文獻[15]是一種基于頂點重要度的保形網格簡化方法，其數據顯示，當頂點數為4850時，簡化率達到91.81%時所用時間為8.24s，且簡化率越高，耗時越長。推算該方法當頂點數大于20 000時，達到同樣簡化率所用時間約為33.979s，而本文方法處理大于20 000點以上數據時(如上文斯坦福兔子數據)，達到精簡率93.966%僅需14.501s，達到精簡率95.380%僅需12.188s，可見本文精簡速度較快。并且本文方法在立方體邊長取值較大時，精簡率越高，重建時間越短，將簡化和重建過程融為一體。

本文還對實驗室掃描的實測數據進行了測試。雖然自掃描數據存在噪聲大，存在大量重復點等缺點，但本文方法仍取得了良好的實驗結果。第一個實驗數據是一個古玩瓶子模型，單面掃描有18 553個點，根據本文介紹的劃分立方體方法計算得到(以下數值均為取整后數值)，Pmax=(214,136,234)，Pmin= (51,38,11)，Px、Py、Pz分別為163、98、223，繼而表面積S=148 354，由于該掃描數據為單側面，所以表面積本文取一半即S=74 177，n取16，則由式(1)計算得a約為7。立方體邊長7.0，運行時間9.879s。效果如圖5所示。

圖5　瓶子模型網格重建效果。左上為本文實驗效果，右上為掃描得到的密集數據。下側為古玩瓶實物圖

第二個數據是本實驗室自掃描兵馬俑模型，側面數據點96 780個，根據本文介紹的劃分立方體方法計算得到(以下數值均為取整后數值)，Pmax=(424,76,711)，Pmin= (-129,-135,394)，Px、Py、Pz分別為553、211、317，繼而表面積S=717 742，由于該掃描數據為單側面，所以表面積本文取一半即S=358 871，n取16，則由式(1)計算得a約為8。邊長取8，運行時間30.595s。效果如圖6所示。

圖6　兵馬俑模型網格重建效果

由于實測掃描數據噪聲較大，所以實驗結果邊緣略顯瑣碎，但仍能保持基本形狀，取得了較為良好的效果。

4結語

本文提出一種自適應立體柵格劃分方法，并給出以立體柵格為基本單元實現三角網格重建的實現過程。首先將點云數據分割為柵格單元，然后通過選取基本單元中數據點為種子點和設定三角形邊長以近似正6鄰域為約束來構建初始三角網格，再逐層外擴完成三角網格重建。本文方法解決了快速傳輸需求，從高密度點云直接生成精簡的三角網格模型，從實驗結果來看，對于高密度的點云精簡重建速度快，魯棒性較好，并且具有可將簡化和重建過程融為一體的優點。

參考文獻

[1] 陳建良,童水光.逆向工程技術研究進展[J].中國機械工程,2002,13(16):1430-1436.

[2] 崔漢國,胡懷宇,張濤,等.空間自由管道點云重建方法[J].海軍工程大學學報,2011,23(2):76-79.

[3]HoppeH,DeRoseT,DuchampT,etal.SurfaceReconstructionfromUnorganizedPoints[J].ACMSIGGRAPHComputGraphics,1992,26(2):71-78.

[4]AmentaN,BernM,KamvysselisM.ANewVoronoi-basedSurfaceReconstructionAlgorithm[C]//Proceedingsofthe25thAnnualConferenceonComputerGraphicsandInteractiveTechniques,1998:415-421.

[5]AmentaN,ChoiS,KolluriRK.ThePowercrust[C]//Proceedingsofthe6thACMSymposiumonSolidModelingandApplications,2001:249-260.

[6]DeyTK,GiesenJ,HudsonJ.DelaunayBasedShapeReconstructionfromLargeData[C]//ProceedingoftheIEEESymposiumonParallelandLarge-DataVisualizationandGraphic,2001:19-27.

[7] 袁方,唐杰,武港山.一種基于三維Delaunay三角化的曲面重建算法[J].計算機技術與發展,2011,21(10):14-18.

[8] 紀志浩,于明旭.基于點云數據三維重建方法的研究[J].黑龍江工程學院學報:自然科學版,2014,28(3):7-9.

[9] 陳治睿,官云蘭,楊鵬,等.基于點云數據的建筑物快速三維重建方法[J].江西科學,2011,29(5):603-606.

[10] 段春梅.基于多視圖的三維模型重建方法研究[D].山東:山東大學,2009.

[11] 陳曉霞,陳孝威.三維重建中散亂點云的聚類篩選與網格重建[J].計算機系統應用,2011,20(4):141-144.

[12]HongweiLin,ChiewlanTai,GuojinWang.AMeshReconstructionAlgorithmDrivenbyanIntrinsicPropertyofaPointCloud[J].Computer-AidedDesign,2004,36(1):1-9.

[13] 聶建輝,馬孜,胡英,等.針對密集點云的快速曲面重建算法[J].計算機輔助設計與計算機圖形學學報,2012,24(5):574-582.

[14] 楊客,張志毅,董艷.基于自適應八叉樹分割點云的表面模型重建[J].計算機應用與軟件,2013,30(6):83-87.

[15] 董艷,張志毅,楊客.基于頂點重要度的保形網格簡化方法研究[J].計算機工程與設計,2013,34(5):1889-1895.

TRIANGULAR MESH RECONSTRUCTION BY DIRECTLY SIMPLIFYINGDENSEPOINTCLOUD

Dong TianqiZhang Zhiyi*

(College of Information Engineering,Northwest A&F University,Yangling 712100,Shaanxi,China)

AbstractTo address the needs of rapid transmission and to generate the streamlined triangular mesh model directly from dense point cloud, this paper presents an adaptive method for three-dimensional grid division, and gives the reconstruction process of triangular mesh which uses the three-dimensional grid as basic unit. First, by using the macro-estimation method of no difference between points the method obtains the side length of three-dimensional grid, and segments the point cloud data into grid units. Then it selects the data points in basic unit as the seed points, and sets the triangle side lengths to be constrained with approximate positive 6 neighbourhoods to build the initial triangle mesh, and then expands outwardly layer by layer to complete the triangular mesh reconstruction. The advantage of this method is that the reconstruction and simplification processes can be integrated as a whole. Experimental results show that the proposed method is faster with better robustness.

KeywordsSimplifyDense point cloudMesh reconstructionOutward expansion

收稿日期：2015-01-14。國家高技術研究發展計劃項目(2013AA 10230402)；中央高校基本科研業務費西北農林科技大學科技創新項目(QN2013054)。董天琪，碩士生，主研領域：計算機圖形學。張志毅，副教授。

中圖分類號TP391.41

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.063