董天琪　張志毅

(西北農(nóng)林科技大學(xué)信息工程學(xué)院　陜西 楊凌 712100)

?

直接精簡密集點(diǎn)云的三角網(wǎng)格重建

董天琪張志毅*

(西北農(nóng)林科技大學(xué)信息工程學(xué)院陜西 楊凌 712100)

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

關(guān)鍵詞精簡密集點(diǎn)云網(wǎng)格重建外擴(kuò)

0引言

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

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

1概念

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

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

2算法描述

2.1獲得長方體包圍盒

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

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

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

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

檢索鄰域和環(huán)域受影響的立方體時(shí)，實(shí)際上使用的是數(shù)字L。

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

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

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

(PxPy+PxPz+PyPz)×2

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

即：

(1)

劃分的立方體，以編號命名文件保存立方體中的點(diǎn)，并非所有連續(xù)編號的立方體都有其對應(yīng)的文件，沒有點(diǎn)的立方體不會生成文件，所以效率上并沒有多余的浪費(fèi)。

2.3重建過程

2.3.1初次外擴(kuò)方法

重建的第一步是獲取種子點(diǎn)。由于是擴(kuò)展重建，所以適宜從點(diǎn)云的中心開始，本文所有實(shí)驗(yàn)均選取距離長方體包圍盒中心最近的點(diǎn)。根據(jù)2.1節(jié)中得到的Pmax，Pmin計(jì)算長方體包圍盒的中心，遍歷所有點(diǎn)得到距離中心最近的點(diǎn)設(shè)為初始種子點(diǎn)。

得到種子點(diǎn)后，要根據(jù)種子點(diǎn)進(jìn)行外擴(kuò)。對于一次外擴(kuò)，它的準(zhǔn)備工作有以下幾項(xiàng)。

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

? 第三，對環(huán)域點(diǎn)集進(jìn)行排序。排序需要一個(gè)值作為排序的標(biāo)記點(diǎn)。已知種子點(diǎn)O，如果當(dāng)前生成的三角形是第一個(gè)三角形，則當(dāng)前三角形的第二個(gè)頂點(diǎn)可在環(huán)域中隨機(jī)選取，如果當(dāng)前生成的三角形不是第一個(gè)三角形，則由于隊(duì)列的搜索順序并不可隨機(jī)選取。具體的排序方法為：標(biāo)記點(diǎn)記為A，OA作為微切平面上的x軸正向，z軸正向?yàn)槲⑶衅矫娴姆ㄏ蛄颗cO點(diǎn)之差，由此既確定搜索的時(shí)針時(shí)序，本文采用逆時(shí)針?biāo)阉鳌Ｓ?jì)算環(huán)域點(diǎn)與O點(diǎn)連線與OA夾角的cos值，并計(jì)算叉乘結(jié)果與z軸正向比較，即知該點(diǎn)與OA的逆時(shí)序夾角是否超過180°，如果超過則取負(fù)值并減去2，使得cos函數(shù)在0～2π上是變成一個(gè)連續(xù)的遞減函數(shù)，由此可以根據(jù)它對環(huán)域點(diǎn)進(jìn)行排序。

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

圖1　找到合適點(diǎn)組成三角形狀況圖

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

找到合適點(diǎn)的情形如圖1所示，點(diǎn)J為找到的合適點(diǎn)。

圖1中，B為當(dāng)前種子點(diǎn)，隊(duì)列順序?yàn)镃DEFGHI。判斷J與隊(duì)頭C的關(guān)系并做相應(yīng)處理。本文將其分為以下三種情況：

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

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

c.如果JC中等大小，本文設(shè)置為0.5L至2L，即至少可容納兩個(gè)底角最大即70°～75°的等腰三角形，至多容納兩個(gè)底角最小即45°的等腰三角形，滿足上文的條件，此時(shí)直接生成兩個(gè)三角形，△BIJ和△BJC。種子點(diǎn)變?yōu)镃。

2.3.2外擴(kuò)整體過程及方法

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

圖2　左側(cè)為第一次擴(kuò)展圖，右側(cè)為第二次擴(kuò)展圖

圖3　第三次擴(kuò)展圖

圖2左側(cè)為第一次擴(kuò)展圖，種子點(diǎn)為O，此時(shí)隊(duì)列中點(diǎn)的順序?yàn)锳BCDEF，右側(cè)為進(jìn)一步進(jìn)行擴(kuò)展圖，種子點(diǎn)為A，隊(duì)列中點(diǎn)的順序?yàn)锽CDEFGHI，此時(shí)以A為種子點(diǎn)時(shí)的搜索區(qū)域正是左側(cè)圖對應(yīng)種子序列從隊(duì)頭到隊(duì)尾的扇形區(qū)域。

但是這樣并不能保證所有的點(diǎn)都被遍歷，需要在外側(cè)再設(shè)置循環(huán)，判斷是否所有的點(diǎn)標(biāo)記為已讀。最終得到三角網(wǎng)格。

3實(shí)驗(yàn)與分析

本文算法采用C語言實(shí)現(xiàn)，并在主頻為2.60GHz，內(nèi)存2GB的PC機(jī)上進(jìn)行測試。本文分別對標(biāo)準(zhǔn)試驗(yàn)數(shù)據(jù)斯坦福兔子和實(shí)驗(yàn)室掃描的實(shí)測數(shù)據(jù)進(jìn)行了測試。

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

圖4　左上為立方體邊長為10的結(jié)果，右上為立方體邊長為14的結(jié)果，左下為立方體邊長為20的結(jié)果，右下為原始高密度點(diǎn)云的效果

立方體邊長立方體個(gè)數(shù)三角形個(gè)數(shù)用時(shí)(s)102918412122.690141499241014.50120741184312.188

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

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

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

圖5　瓶子模型網(wǎng)格重建效果。左上為本文實(shí)驗(yàn)效果，右上為掃描得到的密集數(shù)據(jù)。下側(cè)為古玩瓶實(shí)物圖

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

圖6　兵馬俑模型網(wǎng)格重建效果

由于實(shí)測掃描數(shù)據(jù)噪聲較大，所以實(shí)驗(yàn)結(jié)果邊緣略顯瑣碎，但仍能保持基本形狀，取得了較為良好的效果。

4結(jié)語

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

參考文獻(xiàn)

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

[2] 崔漢國,胡懷宇,張濤,等.空間自由管道點(diǎn)云重建方法[J].海軍工程大學(xué)學(xué)報(bào),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].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(10):14-18.

[8] 紀(jì)志浩,于明旭.基于點(diǎn)云數(shù)據(jù)三維重建方法的研究[J].黑龍江工程學(xué)院學(xué)報(bào):自然科學(xué)版,2014,28(3):7-9.

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

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

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

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

[13] 聶建輝,馬孜,胡英,等.針對密集點(diǎn)云的快速曲面重建算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與計(jì)算機(jī)圖形學(xué)學(xué)報(bào),2012,24(5):574-582.

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

[15] 董艷,張志毅,楊客.基于頂點(diǎn)重要度的保形網(wǎng)格簡化方法研究[J].計(jì)算機(jī)工程與設(shè)計(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。國家高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目(2013AA 10230402)；中央高?；究蒲袠I(yè)務(wù)費(fèi)西北農(nóng)林科技大學(xué)科技創(chuàng)新項(xiàng)目(QN2013054)。董天琪，碩士生，主研領(lǐng)域：計(jì)算機(jī)圖形學(xué)。張志毅，副教授。

中圖分類號TP391.41

文獻(xiàn)標(biāo)識碼A

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