運用邊界狀態(tài)約束的表面體素加密細分算法

劉晨燕，敬石開+，張 偉,2，趙芳壘

(1.北京理工大學 機械工程學院，北京 100081； 2.中國科學院 計算技術研究所，北京 100190)

0 引言

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

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

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

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

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

1 加密細分算法

1.1 基本概念定義

為描述算法，定義如下相關概念：

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

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

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

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

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

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

00zyx-z-y-x

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

表1 外部面二進制形式

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

1.2 算法總流程

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

具體步驟如下：

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

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

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

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

1.3 預處理階段

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

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

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

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

為了適應后續(xù)體素加密細分的需求，需要記錄體素編號和三角面的映射關系，如式(1)所示：

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

(1)

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

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

1.4 對表面體素進行加密細分

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

1.4.1 三角面和子體素的相交檢測

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

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

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

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

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

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

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

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

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

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

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

對于位置編號為p的體素，將會繼承的外部面的二進制形式I(p)滿足：

(2)

其中：p=x+2y+4z；?是二進制移位符號，表示左移一位。

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

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

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

2.2 加密體素編號索引

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

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

2.2.1 節(jié)點索引

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

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

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

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

(3)

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

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

(4)

2.2.2 尋找鄰居節(jié)點

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

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

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

因此，通過上述加密體素編號索引，可以在多個八叉樹中準確地找到任一體素的鄰接體素。

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

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

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

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

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

3 實驗驗證

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

3.1 加密細分效果

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

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

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

3.2 實驗數(shù)據(jù)

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

表2 多級加密體素化計算時間/s及體素數(shù)量

續(xù)表2

表2中，層級0級加密對應均一體素模型(見每個模型的第一行數(shù)據(jù))，從表中得出如下結論：

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

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

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

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

表3 本文算法與文獻[8]的體素數(shù)量對比

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

4 結束語

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

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

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

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

下一步的研究方向主要集中在如何根據(jù)不同模型的三維結構特點，識別模型空間結構相對復雜的區(qū)域，并對局部區(qū)域進行加密細分。在保持體素模型細分效果的基礎上減少參與加密的體素，從而進一步減少模型的體素數(shù)量。