劉晨燕，敬石開+，張 偉,2，趙芳?jí)?/p>

(1.北京理工大學(xué) 機(jī)械工程學(xué)院，北京 100081； 2.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190)

0 引言

近年來，基于體素的3D模型在虛擬醫(yī)學(xué)[1]、三維地質(zhì)屬性建模、機(jī)械加工仿真[2]、立體渲染、碰撞檢測(cè)、空間分析等領(lǐng)域得到了廣泛應(yīng)用。體素化算法是模型全信息建模表達(dá)與可視化的重要算法，體素化方法一般分為表面體素化和內(nèi)部體素化兩個(gè)步驟，最終獲得體素大小均一的體素模型[3]。為得到精確的體素化模型，在體素化的過程中一般采用較高的體素分辨率，而這會(huì)造成體素單元數(shù)量和體素化時(shí)間隨著分辨率的提高呈指數(shù)型增長(zhǎng)，存儲(chǔ)占用也隨著體素?cái)?shù)量變得很大，因此內(nèi)存和時(shí)間的限制極大地影響了體素化分辨率。

為了在時(shí)間和內(nèi)存都盡量小的情況下提升體素模型分辨率。理想方法是采用多分辨率體素化：在模型內(nèi)部使用較大體素單元，而模型表面體素則選用較小體素單元來滿足體素模型精度表達(dá)需要。針對(duì)這一問題，現(xiàn)有解決方法是對(duì)低精度體素模型表面進(jìn)行再切分的加密操作，在保持體素?cái)?shù)量相對(duì)較少的同時(shí)使體素模型滿足表面精度要求，避免過高精度模型的內(nèi)存占用和減少體素化時(shí)間。

在體素游戲顯示領(lǐng)域，Smith[4]提出一種體素加密策略，通過遞歸細(xì)分算子對(duì)顯示區(qū)域內(nèi)所有體素進(jìn)行切分細(xì)化。朱厚盛等[5]針對(duì)模型降維的需要，提出一種實(shí)體模型的多分辨率中軸生成方法，對(duì)模型中需要細(xì)化的部分進(jìn)行邊界體素化。但是該方法的實(shí)驗(yàn)數(shù)據(jù)加密層級(jí)只有2級(jí)，當(dāng)初始模型分辨率較低時(shí)，不能達(dá)到有效精度。Szucki[6]對(duì)體素模型的特征區(qū)域內(nèi)的體素劃分成N×N×N份，但該局部加密操作只有1次，即加密層級(jí)只有1級(jí)。Marko[1]先以粗糙分辨率進(jìn)行體素化，然后將體素尺寸增加到目標(biāo)分辨率，并計(jì)算每個(gè)粗糙體素內(nèi)的表面內(nèi)外的細(xì)化體素的比率，得到多分辨率體素模型。隨著圖形處理器(Graphics Processing Unit, GPU)硬件技術(shù)的發(fā)展，也有學(xué)者采用并行處理的方式進(jìn)行多分辨率體素化。Huang[7]最先使用GPU進(jìn)行體素化。Young[7]使用GPU創(chuàng)建和渲染多分辨率體素化模型，應(yīng)用三角面模型表面的法向量的函數(shù)將多邊形模型離散為體素模型，并且對(duì)細(xì)節(jié)部分的體素細(xì)分成N×N×N份進(jìn)行加密。其中，Szucki[6]和Young[8]所提的方法都通過增大N解決了精度和體素總數(shù)平衡的問題，但過大的N會(huì)導(dǎo)致加密處模型細(xì)節(jié)過渡不平滑，并且體素?cái)?shù)量同樣會(huì)迅速增加。

綜上所述，目前部分高分辨率的體素化算法只能實(shí)現(xiàn)加密層級(jí)數(shù)較小的情況，高分辨率的體素化結(jié)果是在較高的分辨率的均一體素化模型的基礎(chǔ)上一次加密獲得，導(dǎo)致體素單元數(shù)量依然巨大，無法同時(shí)兼顧體素?cái)?shù)量和分辨率。部分算法因采用GPU運(yùn)算而對(duì)硬件依賴，算法不具有通用性。

針對(duì)以上問題，本文提出一種采用CPU計(jì)算的基于邊界狀態(tài)約束的表面體素加密細(xì)分方法。該方法通過切分均一體素模型的邊界體素，刪除多余子體素，實(shí)現(xiàn)1級(jí)加密細(xì)化。再將表面體素與外部體素的鄰接關(guān)系(即邊界狀態(tài))層層向下層子體素傳遞。通過對(duì)子體素進(jìn)行編碼索引,實(shí)現(xiàn)多層級(jí)加密細(xì)分，獲得多分辨率的體素模型，加密層級(jí)理論上可以達(dá)到9級(jí)以及以上。

1 加密細(xì)分算法

1.1 基本概念定義

為描述算法，定義如下相關(guān)概念：

定義1依附三角面。以STL/AMF格式的三角面模型為輸入進(jìn)行表面體素化，每個(gè)與體素相交的三角面都是該體素的依附三角面，一個(gè)體素可能有0個(gè)、1個(gè)或多個(gè)依附三角面。當(dāng)一個(gè)體素的依附三角面數(shù)量不為0時(shí)，該體素被判定為表面體素。

在多分辨率體素化過程中，一個(gè)體素經(jīng)過一級(jí)或多級(jí)切分細(xì)化后，該體素切分為若干子體素，這些子體素之間的依附三角面信息會(huì)有所不同。

定義2外部面。一個(gè)體素共有6個(gè)表面，在一個(gè)邊界體素中，將該體素與外部體素共用的面記作外部面。如圖1中，若AB方向上6-鄰接體素是外部體素，則AB方向上的面α為外部面。根據(jù)吳曉軍[9]的定義，若兩個(gè)體素間存在一個(gè)公共面，則稱兩個(gè)體素是6-鄰接的。

定義集合Dir={z,y,x,-z,-y,-x}表示不同坐標(biāo)軸方向。對(duì)任意一個(gè)外部面α，以αt的下標(biāo)t表示外部面方向，其中t∈Dir，例如α-x表示該體素-x方向的外部面。αt=1表示體素的t方向的表面是外部面。

外部面是描述體素位置信息的一種方式，為了量化外部面隨著體素刪除而改變的過程，引入邊界狀態(tài)的概念。

定義3邊界狀態(tài)。表示一個(gè)體素中包含哪幾個(gè)方向的外部面。因?yàn)槲贿\(yùn)算的高效性，本文將6種外部面αz，αy，αx，α-z，α-y，α-x映射到一個(gè)字節(jié)的低6位[10]來表示，將該字節(jié)稱為邊界狀態(tài)，記為M，是一個(gè)二進(jìn)制數(shù)。標(biāo)記位按照z，y，x，-z，-y，-x的順序排列如下：

00zyx-z-y-x

定義M(αt)為外部面αt的二進(jìn)制形式，后面計(jì)算會(huì)用到。各個(gè)方向上外部面的二進(jìn)制形式如表1所示。

表1 外部面二進(jìn)制形式

與定義2對(duì)應(yīng)，在6個(gè)標(biāo)記位上，某位取1代表存在對(duì)應(yīng)方向的外部面，取0代表該方向的外部面不存在。所有的邊界體素都具有外部面，一個(gè)邊界體素可存在多個(gè)外部面。一個(gè)不具備任何邊界狀態(tài)的體素，不是邊界體素，它的邊界狀態(tài)M=0。

1.2 算法總流程

本文的算法流程如圖2所示。

具體步驟如下：

步驟1均一體素模型生成。輸入分辨率和模型，對(duì)模型進(jìn)行表面和內(nèi)部體素化，在表面體素化的過程中對(duì)每一個(gè)邊界體素記錄其依附三角面。初始化其邊界狀態(tài)。

步驟2邊界加密細(xì)分。使用八分法平均切分邊界體素，以八叉樹結(jié)構(gòu)存儲(chǔ)。每一個(gè)初始邊界體素都是一棵八叉樹的根節(jié)點(diǎn)。在第1級(jí)加密中，根節(jié)點(diǎn)是父體素；在N級(jí)加密中，父體素是上一輪加密后的子體素。將父體素的邊界狀態(tài)傳至子體素。遍歷八叉樹節(jié)點(diǎn)的體素，以分離軸定理計(jì)算每個(gè)子體素是否與自己的依附三角面相交。

步驟3檢查每個(gè)子體素的三角面相交情況和邊界狀態(tài)。若子體素與任一依附三角面相交，則保留該體素；不滿足相交條件的，檢查體素的邊界狀態(tài)。若邊界狀態(tài)不符合要求，則刪除體素，并傳遞邊界狀態(tài)至鄰接體素中；否則保留。

步驟4多級(jí)加密和模型輸出。若已達(dá)到模型加密層次要求，則輸出體素模型，結(jié)束流程；否則針對(duì)邊界體素重新執(zhí)行步驟2。

1.3 預(yù)處理階段

加密細(xì)分算法的對(duì)象是均一體素模型，因此需要先完成表面體素化和內(nèi)部體素化，對(duì)應(yīng)于流程圖2中的步驟1。本文表面體素化是Akeninem?llser[11]所提的，他將Gottschalk[12]的分離軸定理用于碰撞檢測(cè)進(jìn)行表面體素化。但這一步不是本文重點(diǎn)，只需要注意在表面體素化的同時(shí)記錄每個(gè)表面體素的三角面，構(gòu)建體素—三角面的映射關(guān)系，為后續(xù)進(jìn)行加密細(xì)分做基礎(chǔ)準(zhǔn)備。

若不從三角面模型開始，而是以均一體素模型為輸入，可以執(zhí)行一次表面體素化構(gòu)建該映射關(guān)系。

表面體素化方法有很多，采取何種方式并不影響本文加密算法的實(shí)現(xiàn)。本文使用基于分離軸定理的碰撞檢測(cè)[7]實(shí)現(xiàn)。分離軸定理實(shí)現(xiàn)表面體素化的原理是：對(duì)每個(gè)與三角面不相交的體素，總能找到一個(gè)方向，使得體素和三角面在這個(gè)方向的投影不重疊，滿足條件gap>0，如圖3所示。將與三角面相交的體素標(biāo)記為表面體素，即完成表面體素化。

當(dāng)分辨率較小、體素較大時(shí)，存在多個(gè)三角面位于同一體素內(nèi)部的情況，如圖4所示，該體素與多個(gè)三角面相交。

為了適應(yīng)后續(xù)體素加密細(xì)分的需求，需要記錄體素編號(hào)和三角面的映射關(guān)系，如式(1)所示：

f:voxel(i,j,k)→{triangle_ids}。

(1)

式(1)表示位于位置(i,j,k)的體素，有一個(gè)或多個(gè)三角面相交，記錄這些三角面的集合，它保證了在體素模型的分辨率很小時(shí)，最大限度地保留原三角面模型的信息。

使用外部6-鄰域Flooding算法進(jìn)行實(shí)體體素化。使用基于廣度優(yōu)先搜索(BFS)算法[13]對(duì)位于模型外的體素進(jìn)行標(biāo)記，故未被標(biāo)記的體素即為內(nèi)部體素。經(jīng)過以上步驟即獲得均一體素模型。

1.4 對(duì)表面體素進(jìn)行加密細(xì)分

本文的加密細(xì)分算法的總體思路是：在均一體素模型上，將每個(gè)表面體素細(xì)分為8個(gè)相同尺寸的子體素，將其與三角面進(jìn)行相交檢測(cè)，刪除多余的子體素，再對(duì)保留的子體素進(jìn)行下一級(jí)細(xì)分。

1.4.1 三角面和子體素的相交檢測(cè)

加密細(xì)分操作中對(duì)三角面和體素的相交檢測(cè)與表面體素化的方法一樣，將父體素的依附三角面依次與子體素進(jìn)行相交檢測(cè)，若有至少一個(gè)依附三角面與該子體素相交，就保留該子體素；否則刪除該子體素(即標(biāo)記其為外部體素)。例如對(duì)于圖5的子體素subv，分別從多個(gè)三角面投影，當(dāng)投影為圖中所示方向時(shí)，滿足gapk>0，其中k對(duì)應(yīng)映射關(guān)系(1)中三角面id，表明子體素subv不與任何三角面相交，故被判定為外部體素。

1.4.2 空洞問題—細(xì)分后子體素內(nèi)外位置判定

若僅依據(jù)子體素與依附三角面相交情況進(jìn)行刪除操作，會(huì)導(dǎo)致某些體素被誤刪，如圖6所示。在圖6b中，體素1,2不與三角面相交，但因?yàn)樵擉w素處于模型內(nèi)部，刪除后會(huì)產(chǎn)生內(nèi)部“空洞”。造成模型內(nèi)部出現(xiàn)孔隙，如圖6a所示。因此，還需要獲得子體素與三角面模型的內(nèi)外關(guān)系，才能準(zhǔn)確判斷是否應(yīng)該刪除此體素。

為了解決這個(gè)問題，本文提出邊界狀態(tài)約束算法。

2 邊界狀態(tài)約束算法

邊界狀態(tài)約束算法以二進(jìn)制運(yùn)算的形式，通過初始化、繼承、修改和傳遞邊界狀態(tài)信息，輔助判斷體素的模型內(nèi)外位置。

2.1 邊界狀態(tài)的使用和傳遞

2.1.1 邊界狀態(tài)初始化

使用八分法切分邊界體素之前，該體素的邊界狀態(tài)可由其外部面信息確定。將每個(gè)邊界體素的外部面信息整合至邊界狀態(tài)M。定義操作Add=M+M(αt)，表示在M的基礎(chǔ)上新增外部面αt，M(αt)是外部面的二進(jìn)制形式。

2.1.2 邊界狀態(tài)繼承

初始化后僅有Root體素保存邊界狀態(tài)，在八分法切分表面體素時(shí)，子體素將繼承父體素的邊界狀態(tài)。子體素所繼承得到的邊界狀態(tài)取決于其位置編號(hào)，位置編號(hào)與坐標(biāo)軸關(guān)系如圖7所示。固定位置編號(hào)體素繼承的外部面是固定的，如，對(duì)于位置編號(hào)為1的子體素，繼承的邊界狀態(tài)所包含的外部面有αx、α-y、α-z(如圖7)。

對(duì)于位置編號(hào)為p的體素，將會(huì)繼承的外部面的二進(jìn)制形式I(p)滿足：

(2)

其中：p=x+2y+4z；?是二進(jìn)制移位符號(hào)，表示左移一位。

將外部面加入子體素邊界狀態(tài)M。對(duì)子體素執(zhí)行多次Add=M+I(p)，即可完成子體素邊界狀態(tài)M的繼承操作。

2.1.3 邊界狀態(tài)解決“空洞”問題

在流程圖2的步驟3檢測(cè)出三角面與體素不相交的基礎(chǔ)上，進(jìn)一步判斷邊界狀態(tài)。若體素的邊界狀態(tài)M=0，則體素沒有任何外部面，表示該體素位于模型內(nèi)部，應(yīng)當(dāng)保留；若M≠0，表示該體素至少包含一個(gè)外部面，應(yīng)當(dāng)被刪除。借由邊界狀態(tài)的判斷，“空洞”問題得到解決，如圖8所示。

2.2 加密體素編號(hào)索引

為了在八叉樹中快速尋找體素的鄰居節(jié)點(diǎn)，為體素模型的多級(jí)加密細(xì)分做準(zhǔn)備，本文提出一種跨多棵八叉樹之間尋找鄰居節(jié)點(diǎn)的編號(hào)索引方法?，F(xiàn)有的家譜法[14-15]只能在同一棵樹內(nèi)尋找鄰居節(jié)點(diǎn)，一般用于基于八叉樹的體素化算法中，要求所有體素對(duì)應(yīng)節(jié)點(diǎn)都在同一棵八叉樹下。加密算法中，每一個(gè)表面體素都是一個(gè)Root節(jié)點(diǎn)，相應(yīng)地存在多棵八叉樹。家譜法不適用于此情況，故設(shè)計(jì)了一套編號(hào)索引方案。

第二，今天我們強(qiáng)調(diào)現(xiàn)實(shí)題材創(chuàng)作，在習(xí)總書記的批示下做這部戲，是特別應(yīng)該，特別及時(shí)。今年是改革開放40周年，改革開放40周年對(duì)中國(guó)的改變我不用重復(fù)了，而且剛才提到安徽小崗村，一個(gè)是農(nóng)業(yè)改革，一個(gè)是工業(yè)改革，我覺得這兩個(gè)是同一個(gè)級(jí)別的題材。

2.2.1 節(jié)點(diǎn)索引

節(jié)點(diǎn)的索引即體素在均一體素模型下的位置。Root節(jié)點(diǎn)對(duì)應(yīng)表面體素，其鄰居節(jié)點(diǎn)較易尋找。若體素索引為v(i,j,k)，則其+x方向鄰居節(jié)點(diǎn)為v(i+1,j,k)，如圖9a所示。

每一個(gè)非Root的體素都有一個(gè)體素索引和位置編號(hào)，體素索引表示體素在八叉樹中的位置；位置編號(hào)則包含子體素和父體素之間的聯(lián)系，如圖7所示。

對(duì)于體素v(i,j,k)的體素，其位置編號(hào)p(數(shù)值0～7)可以拆分為3個(gè)0-1二值數(shù)x,y,z，滿足p=x+2y+4z，其中x,y,z∈{0,1}。子體素索引與位置編號(hào)關(guān)系如圖9c所示，滿足：

v(ip,jp,kp)=v(2i+x,2i+y,2i+z)。

(3)

通過式(3)，可以從Root節(jié)點(diǎn)開始，逐層索引所有體素。同時(shí)，父體素索引滿足：

v(i,j,k)=v(ip/2,jp/2,kp/2)。

(4)

2.2.2 尋找鄰居節(jié)點(diǎn)

尋找索引為vs(is,js,ks)的子體素在+x的鄰居vsn，只需對(duì)子體素索引在該方向加減，即鄰居節(jié)點(diǎn)索引為vsn(is+1,js,ks)。但索引需要配合子體素所在的加密層級(jí)depth，才能唯一確定節(jié)點(diǎn)vsn。這樣即便不同八叉樹的多級(jí)體素之間索引重復(fù)也完全不影響。

用式(4)對(duì)索引vs(is,js,ks)執(zhí)行depth輪操作，即可得到Root節(jié)點(diǎn)的索引。根據(jù)索引獲得目標(biāo)Root體素后。將上述過程逆向，從目標(biāo)Root體素以式(3)尋找，執(zhí)行depth輪，可得到最終目標(biāo)體素。

多分辨率體素化中，存在葉子節(jié)點(diǎn)高度不一致的情況。本文加密任務(wù)中只存在高depth節(jié)點(diǎn)，即尺寸更小的體素節(jié)點(diǎn)，向低depth節(jié)點(diǎn)傳遞邊界狀態(tài)的情況。此時(shí)，上述算法執(zhí)行式(3)，直至找到葉子節(jié)點(diǎn)，無需執(zhí)行depth輪。

因此，通過上述加密體素編號(hào)索引，可以在多個(gè)八叉樹中準(zhǔn)確地找到任一體素的鄰接體素。

2.3 多級(jí)加密時(shí)邊界狀態(tài)傳遞

體素刪除將影響坐標(biāo)軸方向的其他體素。隨著子體素的刪除，其6-鄰接體素的邊界狀態(tài)會(huì)發(fā)生變化，原本不與外界相鄰的體素成為邊界體素。因此，體素刪除后，不同方向鄰接體素的邊界狀態(tài)需要各自調(diào)整。

圖10以二維xy平面為例解釋說明邊界狀態(tài)傳遞的方向，體素3的體素被刪除后，向內(nèi)傳遞外部面αx和αy，體素2獲得外部面αy，體素1獲得外部面αx，其邊界狀態(tài)相應(yīng)改變。對(duì)于被刪除的體素5，除了向體素6傳遞外部面αx之外，還需要在+y和-y方向調(diào)整體素的邊界狀態(tài)，體素7和8分別獲得外部面a-y和αy。

傳遞邊界狀態(tài)的時(shí)候需要快速尋找鄰接體素。如2.2.1所述建立八叉樹體素索引，如圖11所示，右下角大體素的索引是v(i+1,j,k)，體素vt將會(huì)傳遞邊界狀態(tài)αx到vq，傳遞邊界狀態(tài)αy到vp，二者均可由編號(hào)獲取相應(yīng)的八叉樹節(jié)點(diǎn)。使用2.2.2節(jié)方式結(jié)合depth尋找到目標(biāo)節(jié)點(diǎn)，故可完成跨八叉樹的體素加密。

通過傳遞外部面信息，更新相鄰體素的邊界狀態(tài)，可以使邊界狀態(tài)延續(xù)，使基于邊界狀態(tài)的多級(jí)加密成為可能。

3 實(shí)驗(yàn)驗(yàn)證

本文方法在Intellij IDEA環(huán)境下以Java語言編寫，處理器為Intel Core i7-4790 3.6 GHz，運(yùn)行內(nèi)存為8 GB。程序使用單線程運(yùn)行，以O(shè)penGL編寫的C++程序?yàn)轱@示軟件。使用Stanford模型數(shù)據(jù)庫中的Bunny、Ball、Dragon、Bike等模型作為主要實(shí)驗(yàn)對(duì)象。

3.1 加密細(xì)分效果

本文算法理論上可以實(shí)現(xiàn)從1～9級(jí)的加密細(xì)分，本節(jié)選擇比較有代表性的6級(jí)加密為例進(jìn)行效果展示。圖12展示了不同模型、83分辨率經(jīng)過6級(jí)加密后的體素模型顯示效果。以Ball，Bunny，Dragon模型為例，經(jīng)過加密細(xì)分的模型表面精細(xì)度和5123分辨率的均一體素模型完全一致，而模型內(nèi)部為更大尺寸體素，實(shí)現(xiàn)了多分辨率體素化。

圖12a為5123分辨率的均一體素模型，圖12b和圖12c是以83為初始分辨率，經(jīng)過6級(jí)加密獲得5123精細(xì)度的多分辨率體素模型。

本文算法還適用于一個(gè)體素中存在不封閉多重曲面的情況，可以處理具備復(fù)雜結(jié)構(gòu)的機(jī)械模型。如圖13所示，Bike模型在83分辨率下，整個(gè)體素模型效果粗糙。隨著加密層級(jí)升高，可以逐步將Bike的支架輪轂等結(jié)構(gòu)刻畫出來。由于邊界狀態(tài)能夠跨八叉樹傳遞，當(dāng)體素被刪除時(shí)，對(duì)其周圍體素邊界狀態(tài)的影響都會(huì)被記錄下來。模型細(xì)節(jié)信息在加密過程不會(huì)損失。

3.2 實(shí)驗(yàn)數(shù)據(jù)

本算法的各級(jí)加密詳細(xì)數(shù)據(jù)如表2所示。本文按三角面片數(shù)量級(jí)遞增的順序，列舉出Ball，Bunny，Dragon共3個(gè)模型的測(cè)試數(shù)據(jù)。在加密后最外層分辨率相同(即最小體素的尺寸相同)時(shí)，在不同初始分辨率和不同加密層級(jí)下，比較總體素?cái)?shù)量和算法運(yùn)行時(shí)間。

表2 多級(jí)加密體素化計(jì)算時(shí)間/s及體素?cái)?shù)量

續(xù)表2

表2中，層級(jí)0級(jí)加密對(duì)應(yīng)均一體素模型(見每個(gè)模型的第一行數(shù)據(jù))，從表中得出如下結(jié)論：

(1)對(duì)低分辨率體素模型加密，相比相同最外層分辨率的均一體素模型，用時(shí)更少，如圖14所示。

對(duì)不同數(shù)量級(jí)的三角面模型，加密用時(shí)表現(xiàn)優(yōu)于均一體素化算法，并存在一個(gè)用時(shí)最少的低分辨率和加密層次的組合。故可以通過合理選取初始分辨率和加密層次，實(shí)現(xiàn)最優(yōu)的時(shí)間效率。

(2)經(jīng)過加密后的低分辨率模型，總體素?cái)?shù)量相比相同最外層分辨率的均一模型更少。對(duì)比如圖15，例如，橫坐標(biāo)為0級(jí)對(duì)應(yīng)分辨率為5123的均一體素模型，橫坐標(biāo)4級(jí)對(duì)應(yīng)初始分辨率為323，加密4級(jí)之后的多分辨率體素模型。

Young[8]提出了一種體素模型細(xì)化方法：在均一體素模型的基礎(chǔ)上,將每一個(gè)邊界體素切分成N×N×N個(gè)同樣大小的子體素,從而實(shí)現(xiàn)多分辨率體素化。在相同硬件條件下，將本文算法與文獻(xiàn)[8]的體素細(xì)化方法進(jìn)行模型體素總數(shù)量的對(duì)比，結(jié)果如表3所示。

表3 本文算法與文獻(xiàn)[8]的體素?cái)?shù)量對(duì)比

從表中可以看出，本文算法的體素?cái)?shù)量遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[8]方法，而且細(xì)化層級(jí)越高，體素?cái)?shù)量差距越大。若將初始分辨率323的體素模型加密細(xì)化為最外層分辨率2563的模型,文獻(xiàn)[8]的算法需要將每一個(gè)邊界體素切分成8×8×8個(gè)。本文在體素細(xì)化過程中使用八叉樹結(jié)構(gòu)，如圖16所示，減少了不必要體素的切分,而且由于本文能實(shí)現(xiàn)層級(jí)很深的加密細(xì)化，而低初始分辨率又可以避免模型內(nèi)部較大尺寸體素的切分,故體素?cái)?shù)量隨加密層級(jí)增加而減少。

4 結(jié)束語

針對(duì)現(xiàn)有多分辨率體素化方法加密層級(jí)很低，體素模型體素?cái)?shù)量巨大的問題，本文提出一種體素模型加密細(xì)化方法，該算法將八叉樹結(jié)構(gòu)用于加密任務(wù)中。均一體素模型表面體素中包含體素與模型的內(nèi)外位置關(guān)系，通過設(shè)計(jì)邊界狀態(tài)約束算法，充分利用了這種位置信息。最后，本文采用多種模型對(duì)加密細(xì)化方法進(jìn)行了驗(yàn)證。算例結(jié)果表明，通過合理選取初始分辨率和加密層次，能夠在獲得同樣精細(xì)度的體素模型的同時(shí)，減少體素?cái)?shù)量，縮短算法運(yùn)行時(shí)間。在不同加密層級(jí)的結(jié)果對(duì)比上，本文算法相比文獻(xiàn)[8]方法，模型體素總數(shù)量平均減少71.53%，表明本文算法在加密體素?cái)?shù)量上優(yōu)于現(xiàn)有算法。

本文方法具有以下兩方面的意義：

(1)提出一種利用邊界狀態(tài)約束，輔助判斷體素位置的方案。體素與模型的位置關(guān)系可以通過邊界狀態(tài)來間接表示，通過在每個(gè)子體素內(nèi)維護(hù)邊界狀態(tài)信息，加密過程可快速確定體素內(nèi)外位置，無需復(fù)雜的幾何計(jì)算，具有較高的實(shí)用價(jià)值。

(2)提出一種跨八叉樹鄰居搜索方法。從加密Root節(jié)點(diǎn)開始，用編碼索引和八叉樹深度結(jié)合的方式，快速準(zhǔn)確地查找鄰居節(jié)點(diǎn)，使多級(jí)加密成為可能。在本文硬件條件下，加密算法最多實(shí)現(xiàn)了9級(jí)加密，且加密細(xì)分后的模型效果和29倍的高分辨率模型完全一致。

下一步的研究方向主要集中在如何根據(jù)不同模型的三維結(jié)構(gòu)特點(diǎn)，識(shí)別模型空間結(jié)構(gòu)相對(duì)復(fù)雜的區(qū)域，并對(duì)局部區(qū)域進(jìn)行加密細(xì)分。在保持體素模型細(xì)分效果的基礎(chǔ)上減少參與加密的體素，從而進(jìn)一步減少模型的體素?cái)?shù)量。