一種基于八叉樹的快速體素化方法*

段偉偉，羅健欣，倪桂強，唐 斌

(解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，江蘇 南京 210007)

?

一種基于八叉樹的快速體素化方法*

段偉偉，羅健欣，倪桂強，唐 斌

(解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，江蘇 南京 210007)

當(dāng)前的體素化方法大都具有較高的復(fù)雜性，計算開銷大，對硬件要求高。為了簡單快速地實現(xiàn)3D模型的體素化，提出一種基于八叉樹的快速體素化方法。首先在使用八叉樹進(jìn)行模型細(xì)分的基礎(chǔ)上，得到模型表面數(shù)據(jù)。然后根據(jù)表面數(shù)據(jù)選擇多個方向?qū)δＰ瓦M(jìn)行逐行掃描。該方法能快速地區(qū)分出模型的外部數(shù)據(jù)和內(nèi)部數(shù)據(jù)，最終實現(xiàn)模型的體素化。對不同分辨率下的多種模型的實驗結(jié)果表明，文中提出的方法能有效地實現(xiàn)快速體素化，具有一定的應(yīng)用價值。

體素化；八叉樹；快速；多方向逐行掃描；模型細(xì)分

0 引言

近年來，基于體素(Voxel)的3D模型在眾多領(lǐng)域(如立體渲染、虛擬現(xiàn)實、醫(yī)學(xué)影像、機械零件制造、流體力學(xué)等)得到了廣泛的應(yīng)用。傳統(tǒng)的3D模型表示方法(如掃描表示法、邊界表示法等)只能表示物體的表面信息，難以描述其內(nèi)部屬性。體素化(Voxelization)能根據(jù)3D模型的表面幾何信息，計算并獲取模型的內(nèi)部數(shù)據(jù)，產(chǎn)生描述完整3D模型的體數(shù)據(jù)集。目前，作為一個研究熱點，關(guān)于體素化方法的研究成果越來越多，可以較好地將3D模型表面數(shù)據(jù)轉(zhuǎn)換為能描述模型內(nèi)部信息的體數(shù)據(jù)。然而，這些已有的方法一般具有較高的復(fù)雜性，計算開銷大，對硬件要求高。為此，本文提出了一種簡單的基于八叉樹的快速體素化方法，在利用八叉樹對3D模型進(jìn)行細(xì)分的基礎(chǔ)上，對模型的表面數(shù)據(jù)進(jìn)行多方向逐行掃描，快速地區(qū)分出模型的外部數(shù)據(jù)與內(nèi)部數(shù)據(jù)，有效地實現(xiàn)模型的體素化。

1 相關(guān)工作

1.1 八叉樹

八叉樹是一種空間分割的層次數(shù)據(jù)結(jié)構(gòu)，它將其節(jié)點遞歸地分解為8個子節(jié)點，直至達(dá)到一定精度[1]。樹的第一個節(jié)點是根節(jié)點，對應(yīng)一個立方體，表示整個物體模型。每個節(jié)點有8個子節(jié)點或者沒有子節(jié)點，這8個子節(jié)點是對父節(jié)點的一次2×2×2規(guī)則細(xì)分，其中沒有子節(jié)點的節(jié)點叫做葉節(jié)點。在一個3D模型的八叉樹結(jié)構(gòu)中，那些包含了模型表面的節(jié)點被更細(xì)致地劃分，而余下的空節(jié)點則成為葉節(jié)點。八叉樹結(jié)構(gòu)的每個維度上每細(xì)分一次，其分辨率都增大到原來的兩倍。因此，要達(dá)到一個1283的分辨率，每個維度上均需要7層細(xì)分操作(log2128=7)。八叉樹結(jié)構(gòu)是表達(dá)三維模型的一種重要方法，能方便有效地進(jìn)行三維模型的表示。

1.2 體素化

體素化也被稱作三維掃描轉(zhuǎn)換(3D Scan Conversion)，最早是由Kaufman在1987年提出[2]，其根據(jù)3D模型的表面數(shù)據(jù)，轉(zhuǎn)換成指定精度的體素表示形式，以獲得包含模型內(nèi)部信息的體數(shù)據(jù)集。

體素化自出現(xiàn)以來，眾多研究者提出了許多不同的體素化方法。Huang等[3]以基于模型表面的法向量函數(shù)為距離標(biāo)準(zhǔn)，將多邊形模型離散為體素模型，可以選擇實現(xiàn)6-鄰域封閉或26-鄰域封閉。Jones等[4]應(yīng)用距離變換和距離場的方法生成體素模型，主要針對CT和MRI等產(chǎn)生的灰度體數(shù)據(jù)集體素模型，便于后續(xù)的可視化處理。Dachille等[5]提出一種增量式三角形的體素化方法。Haumont等[6]提出一種基于種子填充方式的實體體素化方法。Beckhaus等[7]提出了一種切面法，根據(jù)Z軸方向的分辨率設(shè)定一組裁剪面，依次繪制每個切片并保存在幀緩存中，所有的像素數(shù)據(jù)構(gòu)成了最終的體素化數(shù)據(jù)。Thon等[8]運用四叉樹結(jié)構(gòu)對基于光線投射的體素化算法進(jìn)行了改進(jìn)。吳曉軍等[9-10]利用八叉樹編碼的特性，提出一種產(chǎn)生整個三維模型的體素表示算法。Laine[11]研究了拓?fù)浣Y(jié)構(gòu)在體素化過程中的應(yīng)用，提出一種基于拓?fù)浣Y(jié)構(gòu)的體素化方法。近些年隨著圖形處理器GPU的快速發(fā)展，一些研究者嘗試將GPU技術(shù)應(yīng)用到體素化方法研究中[12-13]。Martin等[14]提出一種基于GPU的核外(out-of-core)體素化方法，能有效處理高分辨率下的模型。這些方法雖然利用GPU的并行特性提高了算法性能，但是其算法的判斷過程較為復(fù)雜，計算開銷較大，對硬件要求較高。

2 基于八叉樹的快速體素化方法

本文針對一般3D模型的體素化需求，提出了一種基于八叉樹的快速體素化方法。該方法分為兩個階段：第一階段，使用八叉樹結(jié)構(gòu)對初始的3D模型進(jìn)行空間細(xì)分，直至達(dá)到指定的分辨率精度，得到在該精度下模型表面對應(yīng)的體素數(shù)據(jù)；第二階段，提出一種簡單的多方向逐行掃描算法，能夠根據(jù)3D模型的表面數(shù)據(jù)，快速地區(qū)分模型外部數(shù)據(jù)和內(nèi)部數(shù)據(jù)，進(jìn)而獲得體數(shù)據(jù)集，實現(xiàn)模型的體素化。

2.1 基于八叉樹的模型細(xì)分

對于3D模型，首先使用八叉樹對其進(jìn)行空間細(xì)分，直至得到指定的分辨率。圖1表示對模型節(jié)點從第l層到第l+1層的細(xì)分過程，相應(yīng)的分辨率從2l提高到2l+1。在最高分辨率層，那些與模型表面相交的節(jié)點將被標(biāo)記為模型表面點，而其余的節(jié)點被標(biāo)記為非表面點。以此可以將所有空間數(shù)據(jù)劃分為兩類：第1類，模型表面點對應(yīng)的體素數(shù)據(jù)，標(biāo)示為1，即表示3D模型的表面數(shù)據(jù)；第2類，除第1類以外的所有體素數(shù)據(jù)，標(biāo)示為0，包括3D模型內(nèi)部的元素和模型外部的元素。在本階段暫時不對模型的內(nèi)部數(shù)據(jù)和外部數(shù)據(jù)進(jìn)行區(qū)分。不同類型的元素劃分如下：

(1)

圖1 模型細(xì)分過程

2.2 多方向逐行掃描算法

在上一小節(jié)已經(jīng)獲得了3D模型的表面數(shù)據(jù)。在本節(jié)中，提出了一種簡單的多方向逐行掃描算法。使用該算法，能根據(jù)3D模型的表面數(shù)據(jù)，快速地區(qū)分出模型的內(nèi)部元素和外部元素，實現(xiàn)模型體素化。

為簡單起見，首先給出多方向逐行掃描算法在2D空間中的描述。對于二維平面中的一個物體，在已知物體邊界數(shù)據(jù)的情況下，如何區(qū)分其外部數(shù)據(jù)與內(nèi)部數(shù)據(jù)。此處考慮依次選擇不同方向，從空間邊界開始逐行對物體進(jìn)行掃描。一般地，由于模型空間邊界的元素不在模型內(nèi)部，因此在每一行的掃描過程中，將遇到的非物體邊界元素標(biāo)記為物體的外部元素，直至遇到物體邊界元素時停止該行掃描。圖2是分別從坐標(biāo)平面的X、Y軸的正、負(fù)方向?qū)ξ矬w進(jìn)行逐行掃描判斷的示意圖。

圖2 多方向逐行掃描的二維示意

在經(jīng)過4個不同方向的逐行掃描遍歷之后，所有的外部元素被區(qū)分出來。對于整個數(shù)據(jù)域而言，除去物體的邊界元素和外部元素，其余的元素即為物體的內(nèi)部數(shù)據(jù)。對內(nèi)部數(shù)據(jù)進(jìn)行賦值填充，即實現(xiàn)了物體內(nèi)部數(shù)據(jù)的識別與判定，如圖3所示。

圖3 根據(jù)掃描結(jié)果，填充物體內(nèi)部數(shù)據(jù)

將上述2D空間中的多方向逐行掃描算法推廣到3D空間，將平面坐標(biāo)軸的4個掃描方向擴展到空間坐標(biāo)軸的6個掃描方向，即可快速實現(xiàn)對3D模型內(nèi)部數(shù)據(jù)的識別與填充，完成3D模型的體素化。分別選擇模型所在的空間坐標(biāo)系的X、Y、Z軸的正、負(fù)方向，從邊界開始對模型進(jìn)行逐行掃描。首先選擇一個掃描方向，比如Z軸正方向((0,0,0)→(0,0,z))，在選定的方向上，對每個元素進(jìn)行如下判斷：如果該元素值為0，即判定其為模型外部元素，將其值重新標(biāo)示為-1；如果該元素值為1，說明遇到了模型表面，則停止該行的掃描，并開始下一行的掃描；如果元素為-1，說明遇到的是模型外部元素，不做任何處理，繼續(xù)下一個元素的掃描判定。3D模型的多方向逐行掃描算法的偽代碼如下所示：

select a scanning direction, such as (0,0,0) to (0,0,z);

for (x=0;x

for (y=0; y

for (z=0; z

//(x,y,z) is outside of the model, set it as a outer voxel

if (voxel(x,y,z)==0)

voxel(x,y,z)=-1;

//(x,y,z) is on the model surface, stop scaning on this row

else (voxel (x,y,z)==1)

break;

}

在6個方向的掃描遍歷完成以后，所有的體數(shù)據(jù)被分為三類：標(biāo)示值為1的模型表面元素、標(biāo)示值為0的模型內(nèi)部元素，以及標(biāo)示值為-1的模型外部元素。至此，得到了那些標(biāo)示值為1和0的數(shù)據(jù)，即能完整描述3D模型表面及其內(nèi)部的體數(shù)據(jù)。

(2)

圖4 算法流程圖

圖4為整個方法的流程圖。首先，載入3D模型，使用八叉樹進(jìn)行節(jié)點細(xì)分，得到指定分辨率的模型表面數(shù)據(jù)。然后，依次選擇不同的掃描方向，對模型進(jìn)行逐行遍歷掃描，如果元素值為0，則將其標(biāo)示為-1；如果值為1，則停止該行掃描，開始下一行掃描；如果值為-1，則不處理，繼續(xù)下一個元素的掃描。最后，掃描結(jié)束得到模型內(nèi)部數(shù)據(jù)，體素化完成。

3 實驗結(jié)果

為了驗證本文算法的有效性，對不同分辨率的多個3D模型進(jìn)行了體素化測試。本文算法在Visual Studio 2010環(huán)境下調(diào)用OpenGL函數(shù)庫實現(xiàn)，所有的實驗結(jié)果均是在一臺2.3 GHz Intel Core2 i7-4712處理器、4 GB內(nèi)存、NVIDIA GeForce 840M顯卡的筆記本電腦上測試獲得。

表1給出了本文算法所使用的實驗?zāi)Ｐ蛥?shù)及其測試結(jié)果。圖5是分辨率為1283的tank模型和lady模型的體素化效果圖。

表1 模型參數(shù)及體素化測試結(jié)果

實驗結(jié)果顯示，本文算法在多個模型的不同分辨率需求下，均能在較快的時間內(nèi)產(chǎn)生較好的體素化效果。

圖5 3D模型體素化效果圖

4 結(jié)論

本文提出了一種基于八叉樹細(xì)分模型的多方向逐行掃描的體素化方法，首先在使用八叉樹對3D模型進(jìn)行細(xì)分的基礎(chǔ)上，得到模型表面數(shù)據(jù)，然后根據(jù)表面數(shù)據(jù)進(jìn)行多個方向的逐行掃描，快速地區(qū)分出模型的外部數(shù)據(jù)和內(nèi)部數(shù)據(jù)，實現(xiàn)模型體素化。本文算法思路簡單，易于實現(xiàn)，對硬件需求不高。在處理一般的3D模型體素化任務(wù)時，該算法具有較大的優(yōu)勢。實驗結(jié)果表明，本文方法可以以較快的速度對不同分辨率下的多種模型實現(xiàn)體素化。但是，本文算法并不能很好地處理內(nèi)部包含有空洞的3D模型，會將內(nèi)部的封閉空洞誤識別為模型的內(nèi)部體數(shù)據(jù)。

下一步的工作將針對無法識別3D模型內(nèi)部封閉空洞的問題，對多方向逐行掃描算法進(jìn)行改進(jìn)，期望可以正確地識別出模型的內(nèi)部空洞，進(jìn)一步提高算法的適用性，擴大應(yīng)用范圍。

[1] MEAGHER D. Geometric modeling using octree encoding[J]. Computer Graphics and Image Processing, 1982, 19(2):129-147.

[2] KAUFMAN A. Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes[J]. ACM Siggraph Computer Graphics, 1987, 21(4):171-179.

[3] HUANG J, YAGEL R, KURZION Y. An accurate method to voxelize polygonal meshes[C]. IEEE Symposium on Volume Visualization, 1998:119-126.

[4] JONES M W,SATHERLEY R. Voxelisation: modeling for volume graphics[C]. Conference on Vision Modeling and Visualization, 2000:319-326.

[5] DACHILLE F, KAUFMAN A. Incremental triangle voxelization[C].Proceeding of Graphics Interface, 2000:205-212.

[6] HAUMONT D, WARZEE N. Complete polygonal scene voxelization[J]. Journal of Graphics Tools, 2002, 7(3):27-41.

[7] BECKHAUS S, WIND J, Strothotte H. Hardware-based voxelization for 3D spatial analysis[C].Proceeding of the 5th International Conference on Computer Graphics and Imaging, 2002:15-20.

[8] THON S,GESQUIERE G, RAFFIN R. A low cost anti-aliased space filled voxelization of polygonal object[C].Proceeding of International Conference Graphics, 2004: 71-78.

[9] 吳曉軍，劉偉軍，王天然,等. 改進(jìn)的基于歐式距離測度網(wǎng)格模型體素化算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2004, 16(4): 592-597.

[10] 吳曉軍，劉偉軍，王天然,等. 基于八叉樹的三維網(wǎng)格模型體素化方法[J]. 工程圖學(xué)學(xué)報, 2005, 26(4):1-7.

[11] LAINE S. A topological approach to voxelization[J]. Computer Graphics Forum, 2013, 32(4):77-86.

[12] SCHWARZ M, SEIDEL H P. Fast parallel surface and solid voxelization on GPUs[J].ACM Transation on Graphics, 2010, 29(6): 179.

[13] CRASSIN C, GREEN S. Octree-based sparse voxelization using the GPU hardware rasterizer[M]. OpenGL Insights, 2012.

[14] MARTIN P, ANDREAS K. Grid-free out-of-core voxelization to sparse voxel octrees on GPU[C]. Conference on High-Performance Graphics, ACM, 2015:95-103.

A fast voxelization method based on octree

Duan Weiwei, Luo Jianxin, Ni Guiqiang, Tang Bin

(School of Command Information System, PLA University of Science and Technology, Nanjing 210007, China)

Current methods of voxelization almost have extraordinary complexity which need a high cost of calculation and hardware requirements. In order to achieve a simple and fast voxelization of 3D models, this paper presents a fast voxelization method based on octree. Firstly, subdividing the 3D models using octree structure to get the voxel data on the model surface. After selecting multi-directions to scan the model per row according to the surface data, it’s easy to judge that the voxels are inside of the model or outside of the model. Then the voxelization of 3D model is done. The experimental results of several models on different resolutions show that this method achieves a fast voxelization efficiently and is valuable in application.

voxelization; octree; fast; scanning per row of multi-directions; model subdividing

江蘇省自然科學(xué)青年基金(BK20150722)

TP391.4

A

10.19358/j.issn.1674- 7720.2017.11.027

段偉偉，羅健欣，倪桂強，等.一種基于八叉樹的快速體素化方法[J].微型機與應(yīng)用，2017,36(11)：91-93，101.

2016-12-13)

段偉偉(1988-)，男，博士研究生，主要研究方向：計算機圖形學(xué)，算法設(shè)計。

羅健欣(1984-)，男，博士，講師，主要研究方向：計算機圖形學(xué)，可視化，計算機網(wǎng)絡(luò)。

倪桂強(1966-)，通信作者，男，博士，教授，主要研究方向：計算機網(wǎng)絡(luò)，可視化，計算機圖形學(xué)。E-mail:nigq1966@163.com。