基于八叉樹空間分割的NURBS曲面重構(gòu)方法

王育堅，譚紹維，荊文鵬，董偉偉

（北京聯(lián)合大學(xué) 信息學(xué)院，北京100101）

0 引 言

三維曲面重構(gòu)在逆向工程、圖像處理、計算機輔助設(shè)計和計算機視覺等領(lǐng)域得到應(yīng)用［1，2］。三維模型數(shù)據(jù)結(jié)構(gòu)復(fù)雜、數(shù)據(jù)規(guī)模龐大，使得點云的存儲和壓縮成為影響曲面重構(gòu)算法效率的關(guān)鍵因素［3］。由于通過不同方法獲取的點云數(shù)據(jù)量龐大、拓?fù)浣Y(jié)構(gòu)丟失，針對大規(guī)模點云的曲面重構(gòu)方法仍然需要深入研究。本文提出一種基于八叉樹空間分割的NURBS曲面重構(gòu)方法，利用八叉樹的快速收斂能力對點云進行分割、精簡處理，采用NURBS曲面重構(gòu)方法對局部網(wǎng)格曲面進行重構(gòu)，使用八叉樹和四叉樹相混合的數(shù)據(jù)結(jié)構(gòu)，漸進地進行曲面的重構(gòu)。

1 八叉樹空間分割方法

1.1 八叉樹結(jié)構(gòu)

在數(shù)據(jù)模型研究方面，研究者提出多種數(shù)據(jù)組織方法［4］，提高了重構(gòu)模型的精確度和運算效率。文獻 ［5］提出一種無指針八叉樹的二元結(jié)構(gòu)，并設(shè)計了八叉樹的快速創(chuàng)建算法，適用于不同結(jié)構(gòu)的八叉樹。該方法既減少了模型的存儲空間，又提高重構(gòu)速度。文獻 ［1］采用空間分布式方法，將海量點云分配到多個服務(wù)器，采用并行訪問技術(shù)，提高了數(shù)據(jù)管理的效率。從空間數(shù)據(jù)結(jié)構(gòu)的特點看，八叉樹的遞歸構(gòu)建原理和空間劃分規(guī)則非常適合散亂點云數(shù)據(jù)的處理。

八叉樹是將四叉樹推廣到三維空間而得到的一種遞歸結(jié)構(gòu)，可應(yīng)用于三維空間實體的分割表示。從邏輯結(jié)構(gòu)上看，八叉樹采用樹的結(jié)構(gòu)，按X、Y、Z 這3 個不同方向，將三維空間實體分割為8 個大小相等的子立方體。然后，根據(jù)每個子立方體所含的目標(biāo)來決定是否繼續(xù)對子立方體進行八劃分。重復(fù)下去，一直劃分到每個子立方體或被一個目標(biāo)充滿，或沒有目標(biāo)，或其大小已成為預(yù)先定義的規(guī)模為止。顯然，八叉樹每個結(jié)點有8個或0 個子結(jié)點，其度為8或0。

八叉樹物理結(jié)構(gòu)分為規(guī)則八叉樹和線性八叉樹。規(guī)則八叉樹要存儲8個子結(jié)點的指針和一個父結(jié)點的指針，非葉子結(jié)點還需要存儲下一個子結(jié)點的指針［6］，存貯效率較低。

線性八叉樹是一種算法效率較高的物理結(jié)構(gòu)，采用8進制的前綴編碼方法［5］。對于同一父結(jié)點的8 個子結(jié)點，具有最小x、y、z值的結(jié)點編號為0，相鄰兄弟結(jié)點的編號沿x方向增加1，沿y方向增加2，沿z方向增加4，并在8個子結(jié)點編碼中加入父結(jié)點編碼，作為其前綴。為了計算方便，可以在編碼后增加一串不同于0～7 八進制數(shù)的字符，保證八叉樹結(jié)點編碼q的長度一致，均為樹的最大的深度。這樣，八叉樹結(jié)點的編碼q代表分割空間后的立方體網(wǎng)格單元。

1.2 基于八叉樹的點云分割模型

一般的散亂點云數(shù)據(jù)不適合直接進行曲面重構(gòu)，需要對點云數(shù)據(jù)進行分割。點云數(shù)據(jù)的分割可以采用八叉樹空間結(jié)構(gòu)劃分的思想。首先，構(gòu)建一個包含所有點云在內(nèi)的長方體包圍盒，作為八叉樹的根結(jié)點進行初始化。然后，進行八叉樹遞歸分解。每一次分解后，點云數(shù)據(jù)散落在8個子立方體中。這樣，通過采用八叉樹體素分解方法，對包圍盒進行遞歸分割，將點云模型逐級分解，直到達到規(guī)定的細(xì)分程度為止。

八叉樹點云分割模型如圖1所示，每個子結(jié)點表示對應(yīng)的子立方體，圓圈表示該子立方體未被點云數(shù)據(jù)填滿，需要繼續(xù)分解；灰度小矩形表示該子立方體點云數(shù)據(jù)被填滿，空白矩形表示該子立方體中沒有點云數(shù)據(jù)，這兩種情況都不需要繼續(xù)分解。八叉樹的葉結(jié)點中存儲點集，每個葉結(jié)點中存儲了散落在該立方體內(nèi)的點云或抽樣點數(shù)據(jù)。

圖1 八叉樹結(jié)構(gòu)

利用點云構(gòu)建八叉樹模型，子立方體細(xì)分的程度是一個首先需要解決的問題。立方體劃分越細(xì)，落在每個子立方體內(nèi)的點越少，數(shù)據(jù)丟失率低。但如果立方體劃分太細(xì)，存在大量的冗余子立方體。反之，如果立方體劃分太粗，模型精度不高。因此，立方體的劃分規(guī)則必須高效、合理。

有兩種常用的立方體劃分方法，一種是根據(jù)點云密度設(shè)定細(xì)分的閥值［7］。八叉樹深度決定子空間 （葉結(jié)點）個數(shù)以及每個子空間包含的平均點數(shù)。設(shè)實體空間點云總數(shù)為n，子空間平均點數(shù)為k，則葉結(jié)點數(shù)為n/k，八叉樹深度h為

式中： “｜｜”表示取整數(shù)運算。顯然，當(dāng)八叉樹是滿八叉樹時，樹的深度h最小。k是每個子立方體中點數(shù)的平均值，從總體上反映了立方體內(nèi)點的密集程度。實際應(yīng)用時根據(jù)點云總數(shù)n和八叉樹深度h設(shè)定k值。將k作為分解結(jié)束的條件閥值，細(xì)分時檢查每個子立方體，如果子立方體內(nèi)的點數(shù)不大于k，則該子立方體停止分解；否則，需要對該子立方體繼續(xù)進行分解，直到所有子立方體內(nèi)的點云數(shù)滿足閥值。

另一種立方體劃分方法是根據(jù)子立方體的邊長進行八叉樹分割［8］。根據(jù)指定的點距，利用八叉樹編碼對點云進行空間鄰域劃分，把點云的空間包圍盒分解為8個指定邊長的子立方體；分解后在每個子立方體中都存在點云數(shù)據(jù)，在子立方體中迭代計算抽樣點，精簡數(shù)據(jù)量。這樣壓縮后，點云密度適中，并可以有效地得到每個點的局部幾何信息。

對于一些形狀復(fù)雜曲面的分割，上述方法都不好控制八叉樹的深度。如果點云中的數(shù)據(jù)點都落在少數(shù)包圍盒內(nèi)，則劃分得到的八叉樹不平衡度高，不利于搜索計算。本文采用一種基于曲率的形狀函數(shù)控制子體數(shù)，具體原理見2.2節(jié)。

2 NURBS曲面重構(gòu)

2.1 NURBS曲面表示

圍繞曲面重構(gòu)，近年來提出了多種基于Delaunay、參數(shù)曲面或隱式曲面的曲面重構(gòu)方法［9］，這些方法具有幾何量計算簡單、顯示不變形、便于控制等特點。但是，這些曲面重構(gòu)方法大多涉及網(wǎng)格拼接和法向一致化計算問題，增加了算法的時間復(fù)雜度。對于復(fù)雜結(jié)構(gòu)的模型，重構(gòu)效果不理想。NURBS曲面擬合具有空間幾何不變性、局部支撐性、光滑連續(xù)性等特點，是構(gòu)建三維空間實體曲面的有效方法［10］。

NURBS非均勻有理B樣條函數(shù)是在B樣條函數(shù)基礎(chǔ)上發(fā)展起來的，已被廣泛應(yīng)用于計算機輔助設(shè)計、制造和工程中。近年來，在三維建模領(lǐng)域也成為研究熱點。

k×l次NURBS曲面有理分式表示為

式中：Pij（0≤i＜n，0≤j＜m）是控制頂點，所有控制頂點構(gòu)成一個控制網(wǎng)絡(luò)；wij（0≤i＜n，0≤j＜m）為控制點Pij的權(quán)因子；Nki（u）（0≤i≤n）和Nlj（v）（0≤j≤m）分別是u、v方向的k 次、l次B樣條基函數(shù)，它們分別由u、v方向的非均勻結(jié)點矢量U、V 按德布爾遞歸公式?jīng)Q定

有關(guān)NURBS曲面重構(gòu)的主要研究內(nèi)容包括數(shù)據(jù)壓縮、數(shù)據(jù)點參數(shù)化、單片曲面重構(gòu)和曲面合并等，目標(biāo)旨在提高參數(shù)化、建模的精度和效率［7］。NURBS能用統(tǒng)一的數(shù)學(xué)表示描述曲面，且能夠通過權(quán)因子調(diào)整曲面形狀，使得曲面形狀易于控制。NURBS曲面擬合具有空間幾何不變性、光滑連續(xù)性等特點。但NURBS方法也有缺點，當(dāng)采用逐片構(gòu)造方法擬合復(fù)雜拓?fù)浣Y(jié)構(gòu)時，需要對曲面片進行裁剪。并要考慮片與片之間的光滑拼接，難以保持接縫處光滑。

2.2 混合數(shù)據(jù)結(jié)構(gòu)設(shè)計

模型在邏輯結(jié)構(gòu)上采用一種八叉樹與四叉樹相混合的數(shù)據(jù)結(jié)構(gòu)，如圖2所示。混合數(shù)據(jù)結(jié)構(gòu)由數(shù)據(jù)層和曲面層組成，數(shù)據(jù)層采用八叉樹結(jié)構(gòu)，曲面層采用四叉樹結(jié)構(gòu)。數(shù)據(jù)層利用八叉樹對點云數(shù)據(jù)進行分割，最終在葉結(jié)點中生成控制點，并與曲面層進行鏈接。曲面層根據(jù)數(shù)據(jù)層八叉樹葉結(jié)點提供的控制點數(shù)據(jù)，利用NURBS進行局部曲面擬合，然后采用四叉樹結(jié)構(gòu)對曲面進行合并。

利用八叉樹結(jié)構(gòu)分解點云時，在葉結(jié)點中除了存儲子體的X、Y、Z空間信息，還存儲了與點云數(shù)據(jù)相關(guān)的幾何信息，如結(jié)點的邊界、數(shù)據(jù)點的法向量坐標(biāo)、所屬曲面的編碼等。采用廣度優(yōu)先方法建立八叉樹，并確保八叉樹相鄰的4個葉結(jié)點屬于一個局部曲面。

在存儲結(jié)構(gòu)上，曲面層四叉樹并沒有存儲葉結(jié)點，而是共享了數(shù)據(jù)層八叉樹的葉結(jié)點。這樣數(shù)據(jù)層和曲面層構(gòu)成一種擴展的八叉樹－四叉樹結(jié)構(gòu)。

對形狀復(fù)雜的曲面進行分割，1.2 節(jié)介紹的兩種立方體劃分方法存在一些缺陷，不容易控制八叉樹的深度和平衡度。有些算法進行了些改進，在進行子結(jié)點分解時綜合考慮點云密度閥值和子立方體的邊長［11］。本文算法采用一種基于曲率的形狀函數(shù)控制點數(shù)的方法。

對曲面進行參數(shù)化的一個基本原則是保證曲面在每個區(qū)間內(nèi)都有數(shù)據(jù)點，即保證參數(shù)化的均勻，避免奇異情況的發(fā)生。抽樣的疏密度取決于曲面的曲率，曲率越大，抽樣點越密；反之，曲率越小，抽樣點越稀。

圖2 八叉樹－四叉樹混合結(jié)構(gòu)

設(shè)Q為一個曲面的采樣點集，q（x，y，z）為點集Q 中任意一個點，f（x，y）為插值于Q 的曲面。令r（x，y）為體現(xiàn)曲面f（x，y）曲率的形狀函數(shù)。顯然，在形狀函數(shù)r（x，y）較大的地方，所需的抽樣點較多。因此，可以將形狀函數(shù)r（x，y）作為是否繼續(xù)進行子立方體分解的條件。根據(jù)網(wǎng)格不變性，形狀函數(shù)r（x，y）只依賴于曲面固有的曲率測度［12］，為

其中，c＞0，為常數(shù)；k（x，y）是主曲率的幾何平均值

混合數(shù)據(jù)結(jié)構(gòu)的C語言描述如下：

對傳統(tǒng)的八叉樹生成算法進行改進，在進行結(jié)點分解時將形狀函數(shù)r（x，y）作為分支限界函數(shù)，以精簡八叉樹的結(jié)點數(shù)，保證八叉樹的平衡度，這樣提高算法的時間和空間效率。

八叉樹生成算法的基本步驟如下：

（1）計算空間點云總數(shù)n，設(shè)置葉結(jié)點中的平均點數(shù)k，根據(jù)式 （1）估算八叉樹深度h。

（2）計算包含所有點集的最小包圍盒，作為八叉樹根結(jié)點范圍。按廣度優(yōu)先方式建立八叉樹，存儲結(jié)點相應(yīng)的信息。

（3）計算子立方體內(nèi)點云的形狀函數(shù)r（x，y），如果滿足分支限界函數(shù)值，則停止分解；如果不滿足條件，則將子立方體分解為8個子結(jié)點。

（4）在八叉樹分解過程中，停止分解的結(jié)點作為葉結(jié)點，存儲所屬局部曲面的編碼。

（5）重復(fù) （3）和 （4），直至停止所有子立方體的細(xì)分；為了控制八叉樹的深度，當(dāng)深度超過估算深度h （最小值）的2倍時也停止分解。

數(shù)據(jù)層八叉樹葉結(jié)點的曲面編碼屬性表示該結(jié)點所關(guān)聯(lián)的曲面。曲面層四叉樹不存儲葉結(jié)點數(shù)據(jù)，所有與曲面相關(guān)的數(shù)據(jù)層葉結(jié)點的幾何數(shù)據(jù)也屬于曲面層。曲面層四叉樹最后一層的結(jié)點鏈接到數(shù)據(jù)層八叉樹的葉結(jié)點。即曲面四叉樹最后一層的結(jié)點需要存儲數(shù)據(jù)層內(nèi)對應(yīng)的4個葉結(jié)點的指針，建立曲面與數(shù)據(jù)點的聯(lián)系，以便進行曲面重構(gòu)。

2.3 NURBS曲面重構(gòu)方法

對于一個形狀復(fù)雜的實體模型，利用NURBS 進行整體曲面的擬合很困難，因為點云數(shù)據(jù)本身結(jié)構(gòu)散亂，不能直接根據(jù)數(shù)據(jù)形成矩形陣列［3］。可以按照實體形狀的特征將點云劃分為不同的區(qū)域，按區(qū)域?qū)⒉煌臄?shù)據(jù)點擬合成局部的曲面。前述已利用八叉樹數(shù)據(jù)結(jié)構(gòu)分割點云，把點集劃分為足夠小、互不相交的子集，這樣就可以利用八叉樹葉結(jié)點中的點云擬合一個矩形區(qū)域的曲面。

基于八叉樹的每4個葉結(jié)點構(gòu)成一個NURBS曲面的矩形區(qū)域，根據(jù)特征量建立數(shù)據(jù)點之間的拓?fù)潢P(guān)系［13］，然后逼近生成其余的控制點。這樣，將點數(shù)據(jù)劃分成一系列的網(wǎng)格，然后在網(wǎng)格上進行四邊形矩形區(qū)域的曲面重構(gòu)。

根據(jù)點云建立曲面，需要對點云進行空間鄰域劃分［8］。設(shè)數(shù)據(jù)點q（x，y，z）所在子立方體的空間索引值為 （a，b，c），q＝qn－1…qi…q1q0為與子立方體對應(yīng)的結(jié)點的八進制編碼。從q0、q1到qn－1表示葉結(jié)點到根結(jié)點的路徑。

已知子立方體對應(yīng)的八叉樹結(jié)點編碼q，可以求出數(shù)據(jù)點所在子立方體的空間索引值 （a，b，c）

根據(jù)式 （7）可以求出八叉樹葉結(jié)點的空間鄰域坐標(biāo)。葉結(jié)點作為曲面重構(gòu)的4個控制點，其它控制點利用樣條基函數(shù)進行插值得到。

曲面的次數(shù)取k＝l＝3，結(jié)點的重復(fù)度為4，u和v方向結(jié)點矢量兩端的0 和1 的個數(shù)為4，根據(jù)式 （3）和式（4），可設(shè)曲面u方向的結(jié)點矢量為U（0，0，0，0，u4，u5，…，u3＋n，1，1，1，1），v方向的結(jié)點矢量為V（0，0，0，0，v4，v5，…，v3＋m，1，1，1，1）。考慮數(shù)據(jù)點分布不均勻，中間內(nèi)結(jié)點的選取采用累積弦長法。

如果點云八叉樹分割精度較細(xì)，局部矩形區(qū)域曲面的形狀不復(fù)雜，為了簡化曲面擬合，可以采用三次均勻B 樣條逼近矩形區(qū)域曲面［14］。設(shè)Q 為矩形區(qū)域曲面的采樣點集，qk（xk，yk，zk）為Q 中任意一點，且a≤xk＜≤a＋1，b≤yk≤b＋1，pij是一個網(wǎng)格控制點，則受qk影響的4×4個控制點應(yīng)滿足

其中，Bi和Bj為樣條基函數(shù)。

為控制點坐標(biāo)添加約束條件

則可求得控制點坐標(biāo)

曲面采用四叉樹結(jié)構(gòu)表示，如圖3 所示。利用鏈?zhǔn)浇Y(jié)構(gòu)存儲曲面之間的關(guān)系，以避免曲面的拼接，方便曲面的合并。編碼采用前綴編碼［7］，構(gòu)造Hash表。混合模型通過數(shù)據(jù)層八叉樹結(jié)點的曲面編碼屬性建立曲面索引，提高了搜索效率。

生成NURBS曲面后，4個曲面構(gòu)成一個四叉樹的葉結(jié)點，通過指針形成一個曲面遞歸結(jié)構(gòu)。對應(yīng)于控制網(wǎng)格的每4個小四邊形網(wǎng)格都有一個共同點，即4個網(wǎng)格的交互點。對應(yīng)于每個共同的交互點，建立與四叉樹結(jié)點的鏈接，產(chǎn)生一個新的網(wǎng)格。每歸并一次，舊的網(wǎng)格都可以被新的網(wǎng)格表示，這樣不斷的遞歸細(xì)分下去，最終使網(wǎng)格擬合到一張復(fù)合曲面。

圖3 曲面四叉樹結(jié)構(gòu)

曲面層四叉樹按后序遍歷方式生成，即按后序遍歷方法逐步合并子曲面，得到一個四叉樹結(jié)構(gòu)的曲面表示方式，以根指針作為標(biāo)識。實體模型的多個子NURBS曲面相互關(guān)聯(lián)，可視化時通過后序遍歷四叉樹方式逐步重繪整個曲面。

3 實驗結(jié)果與分析

為了驗證方法的正確性和有效性，對不同的點云模型進行了實驗驗證。模型系統(tǒng)以Visual C＋＋6.0 為開發(fā)環(huán)境，使用了OpenGL 圖形開發(fā)包。圖4是根據(jù)點云數(shù)據(jù)dinosaurs重構(gòu)的結(jié)果。針對Bunny、Mannequin、Dragon 和Cow 等4個模型，表1給出了本文算法與傳統(tǒng)Delaunay算法在重構(gòu)速度方面的比較結(jié)果。

圖4 實驗結(jié)果

表1 重構(gòu)時間比較/s

實驗結(jié)果表明，對于一般的點云模型，本文算法比傳統(tǒng)的Delaunay算法在效率上可以提高10%～15%；對于較復(fù)雜的點云模型，重構(gòu)效率可以提高50%左右。算法效率較高，重構(gòu)效果較好，比較適合三維實體的實時繪制，適用于大數(shù)據(jù)量數(shù)據(jù)的表面重建。在處理不規(guī)則的實體時，在相同分辨率的前提下，混合模型的數(shù)據(jù)存儲空間比Delaunay模型少30%左右。

4 結(jié)束語

曲面重構(gòu)在多個領(lǐng)域得到了應(yīng)用，針對散亂點云的曲面重構(gòu)方法仍然需要進一步研究。在對三維建模理論和方法進行深入研究的基礎(chǔ)上，提出了一種基于八叉樹空間分割的NURBS曲面重構(gòu)方法。模型采用混合八叉樹和四叉樹的數(shù)據(jù)結(jié)構(gòu)，利用八叉樹劃分、精簡三維實體的點云數(shù)據(jù)，并建立八叉樹與四叉樹的鏈接，減少了數(shù)據(jù)模型的存儲空間。重構(gòu)算法避免了復(fù)雜曲面拼接的計算復(fù)雜度，可以過濾掉對重構(gòu)效果影響不大的數(shù)據(jù)點，并避免了法向一致化的復(fù)雜計算。相比傳統(tǒng)的Delaunay算法，本文算法在重構(gòu)效率方面有較大的改進，模型可以用于實體的三維可視化。但對復(fù)雜模型的可視化，仍存在邊緣效應(yīng)，算法還需要改進。今后的工作是將算法與極小曲面造型方法結(jié)合，進一步提高重建的精確性。

［1］MA H C，Wang Z Y.Distributed data organization and parallel data retrieval methods for huge laser scanner point clouds［J］.Computers ＆Geosciences，2011，37 （2）：193－201.

［2］FU Huan，LIANG Li，WANG Fei，et al.A point cloud segmentation algorithm using local convexity and octree［J］.Journal of Xi’an Jiaotong University，2012，46 （10）：60－65 （in Chinese）.［傅歡，梁力，王飛，等.采用局部凸性和八叉樹的點云分割算法 ［J］.西安交通大學(xué)學(xué)報，2012，46 （10）：60－65.］

［3］Bai Y，Han X，Prince J L.Digital topology on adaptive octree grids［J］.Journal of Mathematical Imaging and Vision，2009，34 （6）：165－184.

［4］GONG Jun，KE Shengnan，ZHU Qing，et al.An efficient management method for point cloud data based on Octree and 3D R－tree［J］.Acta Geodaetica ET Cartographica Sinica，2012，41 （4）：597－604 （in Chinese）. ［龔俊，柯勝男，朱慶，等.一種八叉樹和三維R 樹集成的激光點云數(shù)據(jù)管理方法 ［J］.測繪學(xué)報，2012，41 （4）：597－604.］

［5］Lewiner T，Mello V，Peixoto A.Fast generation of pointerless octree duals ［J］.Journal Compilation，2010，29 （5）：1661－1669.

［6］Wang M，Tseng Y H.Incremental segmentation of lidar point clouds with an octree－structured voxel space ［J］.The Photogrammetric Record，2011，26 （133）：32－57.

［7］WU Jun，YANG Jie.QIN Hongxing.Incremental surface reconstruction of unorganized points based on BFS ［J］.Journal of Shanghai Jiaotong University，2008，42 （10）：1740－1744（in Chinese）.［伍軍，楊杰，秦紅星.基于廣度搜索的增量式點云表面重建 ［J］.上海交通大學(xué)學(xué)報，2008，42 （10）：1740－1744.］

［8］SHAO Zhengwei，XI Ping.Data reduction for point cloud using octree coding ［J］.Journal of Engineering Graphics，2010，31 （4）：73－76 （in Chinese）.［邵正偉，席平.基于八叉樹編碼的點云數(shù)據(jù)精簡方法 ［J］.工程圖學(xué)學(xué)報，2010，31（4）：73－76.］

［9］GAO Xiangmin，PANG Mingyong.Incremental mesh reconstruction from unorganized points ［J］.Journal of Chinese Computer Systems，2011，32 （10）：2096－2011 （in Chinese）.［高向敏，龐明勇.散亂點云的快速增量網(wǎng)格重建算法 ［J］.小型微型計算機系統(tǒng)，2011，32 （10）：2096－2011.］

［10］Chen S Y，Guan Q.Parametric shape representation by a deformable NURBS model for cardiac functional measurements［J］.IEEE Transactions on Magnetics，2011，58 （3）：480－487.

［11］Jagannathan A，Miller E L.Three－dimensional surface mesh segmentation using curvedness－based region growing approach［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29 （12）：2195－2204.

［12］WANG Xiaoming，LIU Jixiao.A new approach of adaptive compression and mesh generation for large scale scattered data［J］.Journal of Engineering Graphics，2010，31 （2）：92－95（in Chinese）.［王曉明，劉吉曉.一種大規(guī)模散亂數(shù)據(jù)自適應(yīng)壓縮與曲面重建方法 ［J］.工程圖學(xué)學(xué)報，2010，31 （2）：92－95.］

［13］LIANG Qunxian，XU Hongli.A fast method of curved surface reconstruction based on point cloud data ［J］.Computer Engineering，2013，39 （2）：237－240 （in Chinese）. ［梁群仙，許宏麗.一種基于點云數(shù)據(jù)的快速曲面重構(gòu)方法 ［J］.計算機工程，2013，39 （2）：237－240.］

［14］NIE Jianhui，MA Zi，HU Ying，et al.Rapid surface reconstruction algorithm from dense point cloud ［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2012，24（5）：574－582 （in Chinese）.［聶建輝，馬孜，胡英，等.針對密集點云的快速曲面重建算法 ［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2012，24 （5）：574－582.］