高藝，羅健欣，裘杭萍，唐斌，吳波

1.中國人民解放軍陸軍工程大學(xué)，南京210007

2.中國人民解放軍61175部隊(duì)

高度場八叉樹的體特征表達(dá)算法

高藝1，2，羅健欣1，裘杭萍1，唐斌1，吳波1

1.中國人民解放軍陸軍工程大學(xué)，南京210007

2.中國人民解放軍61175部隊(duì)

1 引言

場景表達(dá)是可視化技術(shù)的一個(gè)重要分支，也是計(jì)算機(jī)圖形學(xué)研究的熱點(diǎn)。體特征表達(dá)是其中必不可少的一項(xiàng)內(nèi)容，它直接體現(xiàn)了場景的細(xì)節(jié)及真實(shí)感，對用戶理解環(huán)境、認(rèn)知環(huán)境有著至關(guān)重要的作用。

當(dāng)前，體特征表達(dá)主要采用網(wǎng)格模型或體素模型。

網(wǎng)格模型是采用隱式表面近似來表達(dá)三維物體的幾何信息。網(wǎng)格數(shù)量越多，越接近于原始曲面，但繪制耗費(fèi)的時(shí)間也隨之增加。這使得網(wǎng)格模型僅適用于小規(guī)模對象的建模。當(dāng)前，研究的主要問題集中在網(wǎng)格簡化[1-2]，對模型中遠(yuǎn)離觀察者或相對較小的區(qū)域進(jìn)行簡化，減少多邊形的數(shù)量，降低渲染開銷。常見的簡化機(jī)制包括頂點(diǎn)聚類[3]、增量式簡化、采樣[4]和自適應(yīng)細(xì)分[5]等四種機(jī)制。對拓?fù)浜唵?、平滑的表面具有較好的效果，但對復(fù)雜的表面，要將多個(gè)表面用一個(gè)表面來表示常常涉及復(fù)雜的計(jì)算。

體素模型[6]在計(jì)算機(jī)處理能力有限的早期，在醫(yī)學(xué)成像如斷層掃描CT，核磁共振成像MRI等方面提供了極大的幫助。隨著圖形硬件的快速發(fā)展，體素模型再一次煥發(fā)活力。目前，研究的主要內(nèi)容是如何組織體素?cái)?shù)據(jù)，盡可能地跳過空體素，節(jié)省存儲空間，提高空間檢索的效率。

Laine與Karras[7]提出了有效的稀疏體素八叉樹（Efficient Sparse Voxel Octree，ESVO），該方法為每一個(gè)柵格單元都提供一個(gè)過濾的輪廓近似，如果該輪廓可以很好地近似原始幾何，則八叉樹不需要進(jìn)一步細(xì)分到更深的層次。這種表達(dá)方法對具有大量平坦表面的場景有很好的壓縮性能，用近似輪廓在高分辨率下取代體素，能實(shí)現(xiàn)有效的存儲壓縮。Crassin等[8]注意到八叉樹中具有自相似特性的特性可以合并，K?mpe[9]利用這一思想通過將稀疏八叉樹轉(zhuǎn)化為有向圖（Directed Acyclic Graph，DAG）的方式實(shí)現(xiàn)了使用約1 GB內(nèi)存對128K3解析率場景的建模。Villanueva[10]在此基礎(chǔ)上提出了一種通過相似變換將八叉樹的子節(jié)點(diǎn)合并，通過合并子樹來實(shí)現(xiàn)無損壓縮。

盡管如此，與高度場表達(dá)相比，網(wǎng)格表達(dá)和體素表達(dá)的存儲量仍遠(yuǎn)高于高度場表達(dá)，且這兩種模型的渲染都不易于移植到GPU中。

網(wǎng)格模型的渲染效率會受到三角形面片數(shù)量的影響，很容易達(dá)到GPU渲染管線的性能極限，還可能因面片太小而導(dǎo)致重采樣的問題；體素模型因其三維的數(shù)據(jù)結(jié)構(gòu)并不適合直接在GPU中進(jìn)行快速地并行光線投射。

相反，高度場模型具有存儲量較小，易于調(diào)度更新的優(yōu)點(diǎn)，而且高度場數(shù)據(jù)可通過二維紋理的方式載入顯存，在GPU中能獲得極高的光線投射效率，性能優(yōu)勢明顯[11-13]。但是，高度場不具備體特征表達(dá)的能力，在表達(dá)場景時(shí)通常采用法線貼圖、視差貼圖等技術(shù)對對象表面實(shí)施偏移操作，得到具有凹凸感的表面。這僅僅是一種增強(qiáng)視覺效果的2.5維表達(dá)，不是真三維體特征表達(dá)。目前的相關(guān)研究，高度場模型若要實(shí)現(xiàn)對真三維體特征表達(dá)，需輔以網(wǎng)格模型或體素模型才能實(shí)現(xiàn)[14-16]。在同一場景中使用不同類型的數(shù)據(jù)模型會增加系統(tǒng)的復(fù)雜度，降低渲染效率，在層次細(xì)節(jié)（LoD）更新、視點(diǎn)運(yùn)動處理等方面都難以同步，對系統(tǒng)的圖像質(zhì)量有很大影響，影響用戶體驗(yàn)。

基于上述討論，本文提出了一種高度場八叉樹的體特征表達(dá)算法。該算法既保留了傳統(tǒng)高度場的優(yōu)勢，又解決了其體特征表達(dá)能力不足的問題。該算法的提出使得在同一個(gè)場景中可以使用統(tǒng)一的表達(dá)方式建模，為場景的體特征表達(dá)提供了一種新的可行途徑。

2 基本原理

給出高度場八叉樹的形式化描述如下：

i表示當(dāng)前八叉樹子節(jié)點(diǎn)深度，L表示八叉樹最大深度。

對圖1（a）中的任意模型，傳統(tǒng)的高度場z=h(x,y)是無法建模z方向上關(guān)于(x,y)的多值函數(shù)（圖1（b））問題；圖1（c）是體素八叉樹模型示例，基于體素的場景則是由許多三維體素表示的空間。

高度場八叉樹采用八叉樹對三維模型進(jìn)行樹狀細(xì)分，在八叉樹的子節(jié)點(diǎn)內(nèi)從三個(gè)坐標(biāo)軸方向上判斷是否存在高度場的單值函數(shù)，若在其中一個(gè)方向上存在單值函數(shù)即存在單一高度場，則在子節(jié)點(diǎn)中進(jìn)行均勻離散采樣，得到分布規(guī)則的高度場八叉樹模型。圖1（d）是一個(gè)高度場八叉樹模型示例，八叉樹不同層的高度場以不同的顏色進(jìn)行標(biāo)記區(qū)分，每層高度場的覆蓋范圍包含了從基平面到該層次表面所有的空間，各層疊加在一起構(gòu)成了高度場八叉樹結(jié)構(gòu)。

圖1 （d）高度場八叉樹建模示意圖

與所有的節(jié)點(diǎn)都是基于八叉樹細(xì)分的體素模型相比，八叉樹高度場模型只需要少量的子節(jié)點(diǎn)就可以表達(dá)一個(gè)網(wǎng)格內(nèi)的連續(xù)空間。

2.1 高度場八叉樹約束體系

八叉樹是組織三維模型的一種重要數(shù)據(jù)結(jié)構(gòu)。樹的根節(jié)點(diǎn)包含整個(gè)模型的數(shù)據(jù)及八個(gè)指針，每個(gè)指針指向一個(gè)子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)關(guān)聯(lián)一個(gè)與軸對齊的包圍盒。傳統(tǒng)八叉樹子節(jié)點(diǎn)遞歸等分原則是八叉樹結(jié)構(gòu)達(dá)到最大深度或子節(jié)點(diǎn)中三角面片數(shù)小于設(shè)定的閾值，但本文的高度場八叉樹約束體系是：

（1）八叉樹節(jié)點(diǎn)的最大深度。

（2）子節(jié)點(diǎn)中所有三角面片可用高度場表示。

2.2 節(jié)點(diǎn)編碼及類型

通常八叉樹采用八進(jìn)制Morton編碼對節(jié)點(diǎn)進(jìn)行編號，用0～7表示8個(gè)子節(jié)點(diǎn)的編號，在逐層構(gòu)樹中，節(jié)點(diǎn)編碼的位數(shù)不斷增加。

八叉樹節(jié)點(diǎn)分為4個(gè)類型：內(nèi)部節(jié)點(diǎn)、高度場節(jié)點(diǎn)、邊界節(jié)點(diǎn)和空節(jié)點(diǎn)。內(nèi)部節(jié)點(diǎn)為可剖分節(jié)點(diǎn)，有8個(gè)子節(jié)點(diǎn)；高度場節(jié)點(diǎn)為可剖分節(jié)點(diǎn)即葉節(jié)點(diǎn)，其所代表的空間滿足約束體系（1）和（2），僅存儲高度場數(shù)據(jù)及相應(yīng)的參考平面信息；邊界節(jié)點(diǎn)，其所代表的空間滿足約束體系（1）但不滿足約束體系（2）；空節(jié)點(diǎn)，其所代表的空間不包含三角面片。

2.3 算法流程

算法包含三個(gè)主要的階段：一是三角面片預(yù)處理，二是判斷是否存在單一高度場，三是高度場柵格化。算法流程如圖2所示。

圖2 算法流程圖

3 空間高度場化

將三角面片表示的網(wǎng)格模型轉(zhuǎn)換為二維的規(guī)則高度場并存儲在3D紋理中的方法，即網(wǎng)格模型空間高度場化。提出了一個(gè)簡單的高度場化方法，如圖3所示。首先，對每一個(gè)三角面片進(jìn)行空間幾何求交，判斷在三個(gè)坐標(biāo)方向的相交性，然后，根據(jù)相交性確定不相交的坐標(biāo)方向即為坐標(biāo)軸主導(dǎo)軸，主導(dǎo)軸所對應(yīng)的平面即為主導(dǎo)軸平面，最后柵格化后生成高度場數(shù)據(jù)及其他屬性數(shù)據(jù)。

圖3 高度場化管線流程

3.1 三角面片預(yù)處理

三角面片作為模型的基本圖形單元，隨著八叉樹不斷切分，與八叉樹節(jié)點(diǎn)的一個(gè)或多個(gè)邊界盒相交并衍生出新的三角面片。將其抽象化，即三角形邊與邊界盒平面的相交及交點(diǎn)計(jì)算。

如圖4所示，三角面片（a）、（b）、（c）、（d）在父節(jié)點(diǎn)被剖分后，（b）、（c）、（d）與相應(yīng)的子節(jié)點(diǎn)包圍盒的不同平面相交并產(chǎn)生交點(diǎn)。

圖4 八叉樹父節(jié)點(diǎn)包含多個(gè)三角面片

將邊界盒看作剖分區(qū)域，令待剖分的三角形網(wǎng)格模型為D，其頂點(diǎn)集和三角面片集為SV和ST，剖分后形成的三角形在剖分區(qū)域內(nèi)為D+，在剖分區(qū)域外為D-，相應(yīng)的頂點(diǎn)集和三角面片集分別記為VD+、TD+和VD-、TD-。令三角面片三個(gè)頂點(diǎn)(v1,v2,v3)所在剖分區(qū)域的Morton編碼為m(vi)，Ti為該三角面片的面片集。

按如下方式對三角面片進(jìn)行處理：

（1）三個(gè)m(vi)值相等，三角面片的三個(gè)頂點(diǎn)都在剖分區(qū)域內(nèi)。如圖5（a）（b）（c）所示，此種情況三角形沒有被分割，因此在網(wǎng)格模型數(shù)據(jù)中保留，則；VD+=VD+?Vi，TD-=TD-?Ti。

（2）三個(gè)m(vi)值兩兩相等，三角面片兩個(gè)頂點(diǎn)位于剖分區(qū)域內(nèi)，一個(gè)節(jié)點(diǎn)在剖分區(qū)域外，此時(shí)參與求交運(yùn)算的平面只有一個(gè)，需要分兩種情況分別討論。

如圖5（d）所示，三角形一個(gè)頂點(diǎn)在相交平面上，其對邊被剖切，此時(shí)原三角形被分割成兩個(gè)三角形；如圖5（e）所示，原三角形被剖分成一個(gè)四邊形和一個(gè)三角形，四邊形將根據(jù)對角線的長度，取較大的對角線為新三角形的邊，剖分為兩個(gè)新的三角形。原三角形在網(wǎng)格模型數(shù)據(jù)中刪除，新增的三角形面片及其頂點(diǎn)信息添加到VD+、TD+和VD-、TD-中繼續(xù)參與到下一層八叉樹剖分。

（3）三個(gè)m(vi)值均不等，三角面片一個(gè)頂點(diǎn)位于剖分區(qū)域內(nèi)，另兩個(gè)頂點(diǎn)分別位于剖分區(qū)域外兩個(gè)不同的節(jié)點(diǎn)。如圖5（f）所示，相對于剖分區(qū)域而言，參與求交運(yùn)算的平面有兩個(gè)，此時(shí)原三角形被分割為多個(gè)三角形，與上相同，新增的三角形面片及其頂點(diǎn)信息添加到VD+、TD+和VD-、TD-中繼續(xù)參與到下一層八叉樹剖分。

圖5 三角面片的三個(gè)頂點(diǎn)與邊界盒平面的相交關(guān)系

算法直接在三角網(wǎng)格模型的三角面片上實(shí)現(xiàn)剖分，經(jīng)過預(yù)處理后，模型依然保持網(wǎng)格拓?fù)湫畔⒌挠行?，同時(shí)也保證了網(wǎng)格數(shù)據(jù)的完整性。

3.2 空間幾何求交

空間幾何求交的目的是判斷能否轉(zhuǎn)換成空間高度場的依據(jù)。若存在單一高度場，則該子節(jié)點(diǎn)內(nèi)包含的所有三角面片將被高度場化；若不存在單一高度場，則當(dāng)前子節(jié)點(diǎn)內(nèi)所有三角面片仍將繼續(xù)參與剖分，直到能被高度場化為止。對空間幾何求交這一問題的求解通常采用降維計(jì)算，將幾何圖元轉(zhuǎn)換到相應(yīng)的局部坐標(biāo)系下，建立空間幾何與平面圖形間的映射關(guān)系，從而將三維的空間問題降為二維的平面問題，這是將復(fù)雜問題簡單化的一種有效方式?？臻g幾何的求交算法可簡單表述如下：

步驟1根據(jù)參與運(yùn)算幾何圖元的性質(zhì)，構(gòu)造局部坐標(biāo)系。以XZ平面為例，平面方程為ax+by+cz+d=0。O是平面中心點(diǎn)，E是體邊界盒的角點(diǎn)，EO單位向量為n1(a1,b1,c1),平面法向量n2,第三個(gè)向量n3=n1×n2。三個(gè)互相垂直的單位向量n1，n2，n3構(gòu)成局部坐標(biāo)投影系。如圖6所示。

圖6 空間幾何相交問題的降維過程

步驟2應(yīng)用2D/3D對應(yīng)理論建立空間幾何圖元降維前后的計(jì)算關(guān)系，形成投影面上的計(jì)算方案。

設(shè)頂點(diǎn)坐標(biāo)為(x,y,z)的空間三角形，變換到局部坐標(biāo)下的坐標(biāo)為(x′,y′,z′)，其滿足(x'y'z'1)=(xyz1)PTT，其中P是投影矩陣，T是變換矩陣，如下式所示：

3.3 主導(dǎo)軸選取

定義三個(gè)坐標(biāo)方向索引值，0為XY坐標(biāo)方向，1為ZY坐標(biāo)方向，2為XZ坐標(biāo)方向，依次遍歷節(jié)點(diǎn)中的所有幾何圖元，向三個(gè)方向的任一平面做投影降維。經(jīng)過投影降維后的幾何圖元（三角面片）在二維平面上分別進(jìn)行相交關(guān)系的判斷，如果投影三角面片互不相交，則該投影方向即為主導(dǎo)軸，該軸對應(yīng)的平面即為參考平面。對于二維平面的判交已有成熟的研究[17]，本文不再贅述。

3.4 柵格化及數(shù)據(jù)生成

每一個(gè)三角片和其所在的參考平面將一起輸入到柵格化管線中。在柵格化的過程中，每一個(gè)三角面片都會生成一系列的2D片元，每一個(gè)片元都與主導(dǎo)軸相關(guān)聯(lián)，計(jì)算插值后的三角形頂點(diǎn)到主導(dǎo)軸平面的距離，這樣的2D片元即為高度場數(shù)據(jù)片元。

高度場數(shù)據(jù)通常包含高度值數(shù)據(jù)，還包含一些屬性數(shù)據(jù)如：顏色、法線以及在實(shí)際應(yīng)用中所需的其他有用信息如材質(zhì)等。這些值或許是從頂點(diǎn)屬性像素中插值得到，或許是從模型的2D表面紋理得到，最后會被寫入到3D紋理中。

整個(gè)空間高度場化的過程只有空間幾何求交部分在CPU中實(shí)現(xiàn)，其余過程均在GPU中實(shí)現(xiàn)，盡管CPU和GPU之間的通信會造成一定的時(shí)間耗費(fèi)，但比起在CPU中已經(jīng)極大地提升了執(zhí)行效率。

4 高度場八叉樹光線投射

目前，高度場渲染從技術(shù)的角度來分，可以分為兩種：一種是將高度場轉(zhuǎn)換為三角形網(wǎng)格，用硬件渲染三角網(wǎng)格即基于高度場的光柵化方法。用GPU進(jìn)行渲染時(shí)，需要將三角形面片發(fā)送至GPU的顯存中，而CPU與GPU之間進(jìn)行數(shù)據(jù)交換的代價(jià)比較高，大量的數(shù)據(jù)發(fā)送必將導(dǎo)致很高的渲染耗時(shí)，降低系統(tǒng)性能。一種是使用光線投射直接渲染高度場，其優(yōu)點(diǎn)一是表達(dá)方式更簡潔，有較低的內(nèi)存要求；二是對于大規(guī)模高度場數(shù)據(jù)集來說，光線追蹤是一個(gè)圖像的順序算法，本質(zhì)上忽略了高度場的遮擋區(qū)域；三是高度場包含多個(gè)對象的表示，包括幾何、體積、全局光照效果如反射、折射、軟陰影等。

早期的高度場光線投射算法都在CPU中執(zhí)行，由于CPU的串行工作方式，算法只能逐光線渲染，渲染效率很低。隨著圖形硬件突飛猛進(jìn)的發(fā)展，顯卡的處理能力不再是性能提升的瓶頸，基于GPU光線高度場光線投射算法再一次受到了重視?，F(xiàn)有的基于GPU高度場光線投射算法都是傳統(tǒng)的單層高度場，因此是在z-xoy坐標(biāo)系中，以地面（xoy）作為參考平面，模型被看做各空間位置相對于z平面的距離值集合，在光線迭代時(shí)，使用如下公式進(jìn)行相交測試：

式中，Hen為光線進(jìn)入單元邊界處坐標(biāo)，Hex為光線離開單元邊界處坐標(biāo)，Height為光線進(jìn)入的單元高度。如圖7所示[18]。

圖7 傳統(tǒng)的高度場光線投射光線與模型相交關(guān)系

圖8 高度場八叉樹光線投射光線與模型相交關(guān)系

在本文的高度場八叉樹中，高度場在空間中不再只是z=f(x,y)函數(shù)，還可能是y=f(x,z)或x=f(y,z)的函數(shù)，坐標(biāo)系不同，相交規(guī)則也不同，因此重新定義相交規(guī)則如下式：

式中，Den=dist(Hen,plane)為光線進(jìn)入單元邊界處到參考平面的距離，Dex=dist(Hex,plane)為光線離開單元邊界處參考平面的距離。如圖8所示。

光線在不同的參考平面上迭代，逐像素步進(jìn)，在每個(gè)迭代位置，使用公式進(jìn)行相交測試，若相交則輸出當(dāng)前交點(diǎn)的顏色紋理，渲染在屏幕上。

5 實(shí)驗(yàn)與分析

實(shí)驗(yàn)使用C++與GLSL語言，在Microsoft Windows 7操作系統(tǒng)，OpenGL4.4.0上實(shí)現(xiàn)。實(shí)驗(yàn)環(huán)境為Inter?CoreTMi5-3337U處理器，4 GB內(nèi)存。顯卡為NVIDIA GeForce GT 620M。

為了驗(yàn)證本文所述的稀疏空間高度場的表達(dá)能力及對所述模型算法進(jìn)行重現(xiàn)驗(yàn)證，實(shí)驗(yàn)所用的數(shù)據(jù)來自NVIDIA SDK的Venusm模型、Lady和Rabbit三維模型。

圖9是不同分辨率下的Venusm模型渲染效果對比。從對比圖可知，Venusm模型場景分辨率為1 024×1 024時(shí)即可以得到質(zhì)量較高的圖像。

圖9 基于稀疏空間高度場的Venusm模型在不同分辨率下的效果對比

表1給出了本文所用的模型參數(shù)和測試結(jié)果，在不同的分辨率下，對比了使用SVO和使用本文高度場八叉樹進(jìn)行建模時(shí)兩者的占用存儲空間對比。從表1可知，使用高度場八叉樹在相同的分辨率情況下比SVO占用了更小的存儲空間。因?yàn)殡S著分辨率的不斷提高，SVO除空節(jié)點(diǎn)外的每一個(gè)節(jié)點(diǎn)都有8個(gè)子節(jié)點(diǎn)，而高度場八叉樹中，只要存在單一高度場的節(jié)點(diǎn)將不再產(chǎn)生子節(jié)點(diǎn)。

表1 不同分辨率下規(guī)則八叉樹與本文算法占用存儲空間對比MB

圖10是使用SVO和高度場八叉樹的模型結(jié)構(gòu)圖及參考平面（綠色）。從圖10可知，在樹深度相同的情況下，SVO生成的模型幾乎被八叉樹的子節(jié)點(diǎn)塊完全覆蓋，而本文算法在相對平坦（如兔子的腹部）或相對對稱（如人的腰部和腿部）的部分能快速地找到單一高度場，具有更少的節(jié)點(diǎn)數(shù)。

圖10 （a）最大深度為8的SVO結(jié)構(gòu)圖

圖10 （b）最大深度為8的高度場八叉樹結(jié)構(gòu)圖

圖10 （c）深度5時(shí)的單一高度場參考平面

圖10 （d）最大深度為8的SVO結(jié)構(gòu)圖

圖10 （e）最大深度為8的高度場八叉樹結(jié)構(gòu)圖

圖10 （f）深度3時(shí)的單一高度場參考平面

圖11是平面分辨率為4 096×4 096的Lady模型，在本文算法與文獻(xiàn)[7]算法下的光線投射幀速率對比。圖中橫坐標(biāo)為渲染過程中的時(shí)間記錄，縱坐標(biāo)為記錄的幀速率。根據(jù)幀速率公式[19]：

dt為幀時(shí)間，w×h為屏幕分辨率，文獻(xiàn)[7]的平均幀速率大約為55幀/s，而高度場八叉樹的平均幀速率大約為83幀/s，本文算法具有更高的光線投射效率。

圖11 兩種算法的光線投射效率對比

6 結(jié)束語

本文提出了一種基于高度場八叉樹的體特征表達(dá)算法。算法將傳統(tǒng)的z向高度場擴(kuò)展到了x、y、z三個(gè)方向的高度場，借助八叉樹的空間分割，使得高度場具備了體特征表達(dá)的能力。與體素八叉樹表達(dá)相比，高度場八叉樹和體素八叉樹一樣，都是基于三維的空間網(wǎng)格結(jié)構(gòu)，但高度場八叉樹的子節(jié)點(diǎn)是一個(gè)二維空間的高度場數(shù)據(jù)，而體素八叉樹的子節(jié)點(diǎn)是一個(gè)三維空間的體素?cái)?shù)據(jù)，這使得高度場八叉樹在存儲空間和光線投射效率上都比體素八叉樹更有優(yōu)勢，實(shí)驗(yàn)結(jié)果也進(jìn)一步證明了算法的有效性。因此，本文算法在保持傳統(tǒng)高度場表達(dá)優(yōu)勢的同時(shí)，又解決了傳統(tǒng)高度場體特征表達(dá)能力不足的問題。

本文提出的算法還有需要優(yōu)化的方向：一是算法沒有考慮極端復(fù)雜的模型，對于已經(jīng)達(dá)到樹最大深度，仍然未找到高度場的節(jié)點(diǎn)采用網(wǎng)格模型渲染，下一步可以在此類節(jié)點(diǎn)中對高度場分層，形成層次高度場；二是八叉樹的構(gòu)建過程需要不斷地進(jìn)行三角面片剖分及相交判斷，影響了建樹的時(shí)間，下一步在GPU中實(shí)現(xiàn)這一過程，可以很好地解決這一問題。

[1] Kumar S，Manocha D.Interactive display of large scale trimmed NURBS models[R].University of North Carolina at Chapel Hill，1994.

[2] 韓敏，陳鴻博，鄭丹晨.基于分塊Morton壓縮和混合生成準(zhǔn)則的地形簡化方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2014，26（2）：293-301.

[3] 郭力真，吳恩華.多邊形模型簡化算法綜述[J].計(jì)算機(jī)應(yīng)用研究，2005，22（8）：20-23.

[4] Akeley K.Reality engine graphics[C]//Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques，1993：109-116.

[5] Whitted T.An improved illumination model for shaded display[J].Communications of the ACM，1980，23：343-349.

[6] Kaufman A，Shimony E.3D scan-conversion algorithms for voxel-based graphics[C]//Proceedings of the 1986 Workshop on Interactive 3D Graphics，1987：45-75.

[7] Laine S，Karras T.Efficient sparse voxel octrees[J].IEEE Transactions on Visualization and Computer Graphics，2011，17（8）：1048-1059.

[8] Crassin C，Neyret F，Sainz M，et al.Interactive indirect illumination using voxel cone tracing[J].Computer Graphics Forum，2011，30（7）：1921-1930.

[9] K?mpe V，Sintorn E，Assarsson U.High resolution sparse voxel DAGs[J].ACM Transactions on Graphics，2013，32（4）：101.

[10] Villanueva A J，Marton F，Gobbetti E.SSVDAGs：Symmetryaware sparse voxel DAGs[C]//Proceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games，2016：7-14.

[11] Zhai R，Lu K，Pan W，et al.GPU-based real-time terrain rendering：Design and implementation[J].Neurocomputing，2016，171（C）：1-8.

[12] 羅健欣，胡谷雨，倪桂強(qiáng).平行流形空間光線投射高度場可視化算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2013，25（3）：356-362.

[13] Luo J，Hu G，Ni G.Dual-space ray casting for height fieldrendering[J].ComputerAnimationandVirtual Worlds，2014，25（1）：45-56.

[14] Paredes E G，Amor M，Bóo M，et al.Hybrid terrain rendering based on the external edge primitive[J].International Journal of Geographical Information Science，2016，30（6）：1095-1116.

[15] Ammann L，Dischler J M.Hybrid rendering of dynamic heightfields using ray-casting and mesh rasterization[C]//Graphics Interface.[S.l.]：Canadian Information Processing Society，2010：161-168.

[16] Koca ?，Güdükbay U.A hybrid representation for modeling，interactive editing，and real-time visualization of terrains with volumetric features[J].International Journal of Geographical Information Science，2014，28（9）：1821-1847.

[17] 于海燕，何援軍.空間兩三角形的相交問題[J].圖學(xué)學(xué)報(bào)，2013，34（4）：54-62.

[18] Luo J，Ni G，Cui P，et al.Quad-tree atlas ray casting：A GPU based framework for terrain visualization and its applications[M]//TransactionsonEdutainmentVII.Berlin Heidelberg：Springer，2012：74-85.

[19] van Wingerden T L.Real-time ray tracing and editing of large voxel scenes[D].Utrecht University，2015.

GAO Yi,LUO Jianxin,QIU Hangping,et al.Volumetric features representation algorithm using heightfields-octree.Computer Engineering andApplications,2018,54（6）：1-6.

GAO Yi1，2,LUO Jianxin1,QIU Hangping1,TANG Bin1,WU Bo1

1.PLAArmy Engineering University,Nanjing 210007,China
2.PLATroops of 61175,China

Volumetric features representation plays a vital role for user understanding and recognizing the virtual environment.The current algorithm is inefficient due to its large storage and inconvenient acceleration in GPU,and it is difficult to satisfy the real-time requirements of visualization.Aiming at this problem,an efficient volumetric features representation algorithm using heightfields-octree is proposed.The algorithm can not only solve the problem that the heightfields can only represent 2.5 dimensional scene,and cannot express the true 3 dimensional scene,but also provide a new feasible way for volumetric features representation.The heightfields representation of 3D scene is generated by octree structure,which extends the traditional heightfields of z to x,y and z three directions.Firstly,a preprocessing method of triangular is put forward,ensuring model accuracy and data integrity.Secondly,an algorithm of heightfields judgment and rasterization on projection transformation is proposed,converting geometric primitives into heightfields of two-dimensional space.Finally,the ray casting algorithm based on heightfields octree is realized.The experimental results show that the algorithm can dramatically reduce data storage capacity,and higher ray casting efficiency,and better expression of 3 dimensional scene.

volumetric features representation;heightfields-octree;projection transformation;ray casting

體特征表達(dá)對用戶理解和認(rèn)知虛擬環(huán)境有著至關(guān)重要的作用。當(dāng)前的體特征表達(dá)算法由于存儲量大且不易于在GPU中加速等問題，渲染效率低下，難以滿足場景可視化的實(shí)時(shí)性需求。針對這一問題，提出了一種高效的高度場八叉樹體特征表達(dá)算法，不僅解決了傳統(tǒng)高度場僅能表達(dá)2.5維模型，無法表達(dá)真三維模型的問題，而且為體特征表達(dá)提供了一種新的可行途徑。算法使用八叉樹結(jié)構(gòu)生成三維模型的高度場表示，將傳統(tǒng)的z向高度場擴(kuò)展到x，y，z三個(gè)方向的高度場。首先，提出了三角面片預(yù)處理方法，保證模型精度和數(shù)據(jù)的完整性;其次，提出了基于投影變換的高度場表示判斷及柵格化方法，將幾何圖元轉(zhuǎn)換成二維空間的高度場數(shù)據(jù);最后，提出了基于高度場八叉樹的光線投射算法。實(shí)驗(yàn)結(jié)果表明，算法能極大地減少存儲量，具有較高的光線投射效率，表達(dá)三維模型時(shí)取得較好效果。

體特征表達(dá)；高度場八叉樹；投影變換；光線投射

2017-11-17

2018-01-26

1002-8331（2018）06-0001-06

A

TP393

10.3778/j.issn.1002-8331.1711-0245

國家部委科技基金；江蘇省青年科學(xué)基金（No.BK20150722）。

高藝（1982—），女，博士研究生，工程師，主要研究方向?yàn)樘摂M現(xiàn)實(shí)與仿真，E-mail：iamninigao@163.com；羅健欣（1984—），男，博士，講師，主要研究方向?yàn)橛?jì)算機(jī)圖形與圖像處理；裘杭萍（1965—），女，博士，教授，主要研究方向?yàn)橄到y(tǒng)工程；唐斌（1986—），男，博士，主要研究方向?yàn)橛?jì)算機(jī)圖形與圖像處理；吳波（1977—），男，講師，主要研究方向?yàn)橄到y(tǒng)工程。