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

王育堅(jiān)，譚紹維，荊文鵬，董偉偉

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

0 引 言

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

1 八叉樹(shù)空間分割方法

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

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

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

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

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

1.2 基于八叉樹(shù)的點(diǎn)云分割模型

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

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

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

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

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

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

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

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

2 NURBS曲面重構(gòu)

2.1 NURBS曲面表示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

八叉樹(shù)生成算法的基本步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

圖4 實(shí)驗(yàn)結(jié)果

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

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

4 結(jié)束語(yǔ)

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

［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）.［傅歡，梁力，王飛，等.采用局部凸性和八叉樹(shù)的點(diǎn)云分割算法 ［J］.西安交通大學(xué)學(xué)報(bào)，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）. ［龔俊，柯勝男，朱慶，等.一種八叉樹(shù)和三維R 樹(shù)集成的激光點(diǎn)云數(shù)據(jù)管理方法 ［J］.測(cè)繪學(xué)報(bào)，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）.［伍軍，楊杰，秦紅星.基于廣度搜索的增量式點(diǎn)云表面重建 ［J］.上海交通大學(xué)學(xué)報(bào)，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ù)編碼的點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法 ［J］.工程圖學(xué)學(xué)報(bào)，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）.［高向敏，龐明勇.散亂點(diǎn)云的快速增量網(wǎng)格重建算法 ［J］.小型微型計(jì)算機(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é)報(bào)，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）. ［梁群仙，許宏麗.一種基于點(diǎn)云數(shù)據(jù)的快速曲面重構(gòu)方法 ［J］.計(jì)算機(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）.［聶建輝，馬孜，胡英，等.針對(duì)密集點(diǎn)云的快速曲面重建算法 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，24 （5）：574－582.］