李 航， 黨 崗， 程志全， 金士堯

（國防科技大學(xué)并行與分布處理國防科技重點實驗室，湖南 長沙 410073）

紋理映射是一種增加多邊形模型細(xì)節(jié)外觀的非常有效和高效的技術(shù)。但目前廣泛使用的2D紋理映射有著很大的局限性，它需要將網(wǎng)格參數(shù)化、即分配給每個網(wǎng)格頂點一個2D紋理坐標(biāo)來完成。通常這一參數(shù)化過程是非常困難的，而且會帶來扭曲和裂縫，特別是在含有隱含表面、細(xì)分表面等的復(fù)雜網(wǎng)格上。

與2D紋理相比，3D紋理通過將紋理定義在包圍物體的體上來避免2D參數(shù)化。3D體紋理的優(yōu)勢在于其紋理坐標(biāo)能程序化自動產(chǎn)生，而且在任意精度下的采樣都是均勻的。其缺點也很明顯，占用的內(nèi)存隨著立方體分辨率的提高而急劇增加，在高分辨率的需求下幾乎是難以實現(xiàn)的。

八叉樹紋理是體紋理的一種變形，它只對體的子集與模型表面相交的那一部分進(jìn)行存儲，形成了一種稀疏紋理，大大節(jié)省了存儲空間。在GPU上實現(xiàn)八叉樹紋理后，通過硬件協(xié)助，使紋理的查找速度進(jìn)一步加快，實時性得到提高。在原有的低分辨率、小內(nèi)存占用情況下，如果用戶想進(jìn)行高分辨率的繪畫，雖然可以將分辨率提高到相應(yīng)水平來達(dá)到目的，但是由于體紋理的特性，內(nèi)存的需求將上升的非?？?！

本文提出了一種基于 GPU加速的、可變局部分辨率的、實現(xiàn)實時繪畫的自適應(yīng)八叉樹紋理繪畫算法。本文的實現(xiàn)將需要高分辨率的細(xì)節(jié)繪畫部分與其他部分區(qū)別對待，只在需要的部位創(chuàng)建高分辨率紋理，進(jìn)一步節(jié)省了存儲空間。

在下面的章節(jié)中，本文將首先概述相關(guān)工作，而后闡述一種新型的自適應(yīng)八叉樹紋理映射機制（第二部分），進(jìn)而說明其基于GPU實現(xiàn)的方法（第三部分）。在給出實驗結(jié)果并加以分析（第四部分）后，本文最后對工作進(jìn)行總結(jié)。

1 相關(guān)工作

紋理映射一詞最早由Catmull[1]提出，其實質(zhì)是從二維紋理平面到三維模型表面的一個映射。在立體紋理的概念出現(xiàn)后，因為體紋理坐標(biāo)能自動生成，人們從手工賦予模型坐標(biāo)的繁瑣工作中解脫出來。但用體紋理進(jìn)行高品質(zhì)紋理建模將占用大量存儲空間，因此3D紋理的發(fā)展速度比較緩慢。

八叉樹是一種規(guī)則的層次數(shù)據(jù)結(jié)構(gòu)。樹的第一個節(jié)點即根節(jié)點，是一個立方體。每個節(jié)點有8個子節(jié)點或者沒有子節(jié)點，且這8個子節(jié)點是對父節(jié)點的一個2×2×2的規(guī)則細(xì)分。其中，不含有子節(jié)點的叫做葉節(jié)點。在一個包含了3D模型的八叉樹中，那些包含了模型表面的節(jié)點被更細(xì)致地劃分，而余下的空節(jié)點則成為了葉節(jié)點。八叉樹每個維度每細(xì)分一次，其分辨率都將增大到原來的兩倍。因此，要達(dá)到一個256×256×256的分辨率，總共需要 8層（28=256）。自適應(yīng)八叉樹則是在模型的不同區(qū)域有著不同的分辨率或者說樹深度，其樹深度大的地方能表現(xiàn)更詳細(xì)、更真實的圖像效果。

SIGGRAPH2002會議上David Benson和Joel Davis[2]撰文提出了一種用八叉樹實現(xiàn)紋理映射的方法，David DeBry[3]等人的文章也獨立發(fā)展了一種近似于用八叉樹實現(xiàn)紋理映射的方法。到了現(xiàn)在，在GPU上實現(xiàn)八叉樹紋理[4]后，八叉樹紋理的性能得到了進(jìn)一步提高。相比體紋理，用八叉樹結(jié)構(gòu)來存儲紋理時，顏色只存儲在物體表面與體相交的地方，因此可以減少內(nèi)存需求，而且在物體表面的采樣也是均勻的。雖然對于大數(shù)據(jù)量的模型來說，八叉樹紋理仍然會因占用了太多存儲空間而被限制使用，甚至不可實現(xiàn)，但作為圖形硬件上所用的通用數(shù)據(jù)結(jié)構(gòu)[5]之一，八叉樹還是有著很重要的作用和廣闊的應(yīng)用空間。近年針對八叉樹的不足，已出現(xiàn)了如分塊的混合八叉樹[6]、GPU加速的八叉樹體繪制[7]等從不同角度對八叉樹進(jìn)行改善的方法。

2 自適應(yīng)八叉樹紋理

指定深度的規(guī)則八叉樹，其分辨率在用戶使用前已經(jīng)固定下來?，F(xiàn)在考慮這樣一個問題：低分辨率情況下，在一個全白色的模型上畫一個很小的紅色點，其尺寸遠(yuǎn)小于葉節(jié)點的尺寸時，會出現(xiàn)什么樣的情況。一種可能是在葉節(jié)點中進(jìn)行簡單的判斷，將這很少量的紅色拋棄；還有一種可能是通過線性插值將紅色和白色混合在一起，形成粉色；或者干脆將整個葉節(jié)點變成了紅色。但無論出現(xiàn)哪種情況，都是嚴(yán)重的失真。要保持紅色點的細(xì)節(jié)，只有將該處的八叉樹紋理分辨率提高，也即將該處葉節(jié)點進(jìn)行細(xì)分，直到新葉節(jié)點的大小適合于紅色點。

根據(jù)不同的細(xì)節(jié)表現(xiàn)要求，將不同區(qū)域的分辨率自動設(shè)置成所需的程度，規(guī)則八叉樹便變?yōu)樽赃m應(yīng)八叉樹。

2.1 構(gòu)建自適應(yīng)八叉樹

先以低分辨率建立一個原始八叉樹，即細(xì)分所有與物體表面相交的節(jié)點，直到葉節(jié)點為空或者達(dá)到了選擇的深度（包含顏色的節(jié)點）。最初分辨率在程序中指定，可設(shè)為一個較小的值，比如43或83，這樣包含顏色信息的葉節(jié)點深度只有2或 3。然后根據(jù)光標(biāo)的繪畫位置開始構(gòu)建自適應(yīng)八叉樹并最終上色，偽代碼如下所示：

首先獲得畫筆繪畫位置的屏幕坐標(biāo)，然后參照模型獲得物體表面要上色的點的空間坐標(biāo)，再找出空間坐標(biāo)位于哪個葉節(jié)點，然后遞歸細(xì)分節(jié)點；這里利用程序的重復(fù)性，在每次細(xì)分后再找到要進(jìn)行下次細(xì)分的葉節(jié)點，依次循環(huán)下去；達(dá)到用戶指定的分辨率水平后，將葉節(jié)點上色。

這樣做在達(dá)到合適分辨率的同時，還最大限度的節(jié)省了存儲空間。自適應(yīng)八叉樹的建立過程如圖1所示。

圖1 框架結(jié)構(gòu)圖

2.2 占用存儲空間的對比

占用過多的內(nèi)存是限制3D紋理廣泛應(yīng)用的主要原因。雖然八叉樹是一種稀疏的數(shù)據(jù)結(jié)構(gòu)，八叉樹中那些不包含物體表面的節(jié)點不需再進(jìn)行細(xì)分，只有與物體表面相交的葉節(jié)點中存儲了數(shù)據(jù)，但是要達(dá)到和通用的2D紋理同樣的效果，仍需要將八叉樹紋理的分辨率提到比較高的層次，其存儲空間的迅速膨脹依然是個很嚴(yán)重的問題。與此相比，自適應(yīng)八叉樹紋理能較好的緩解內(nèi)存開銷問題。

比較一下體紋理、八叉樹紋理和自適應(yīng)八叉樹紋理的存儲開銷。對于傳統(tǒng)的體紋理，當(dāng)分辨率為256×256×256時，每個體元素中存儲一組RGBA 值，占用的空間就是 256×256×256×4B=64M。達(dá)到同樣的分辨率需要一個深度為 8的八叉樹，不妨假設(shè)八叉樹的每個節(jié)點都只有4個子節(jié)點和物體的表面相交，另4個子節(jié)點為空，那么八叉樹中包含的節(jié)點數(shù)為

每個節(jié)點存儲8組RGBA值，則占用的存儲空間約為 683K?？梢钥闯霰绕饌鹘y(tǒng)的體紋理，八叉樹紋理已經(jīng)節(jié)省了大部分存儲空間。而對于自適應(yīng)八叉樹紋理，假設(shè)最初樹深度只有2，考慮兩個極端情況：一是在物體表面只畫一個分辨率為 256×256的點，另一種是用這樣的點畫滿整個物體表面。容易看出后一種情況就變回到常規(guī)的八叉樹紋理，無需再算。下面計算第一種情況：初始時，樹節(jié)點個數(shù)為5。每次細(xì)分時，一個葉節(jié)點下產(chǎn)生8個子葉節(jié)點，最后得到的總節(jié)點數(shù)為5+8×6=53個，占用空間1.7K。那么最大深度為 8的自適應(yīng)八叉樹占用的存儲空間就在1.7K到683K之間。對于繪畫青花瓷這類只在少數(shù)部位有高細(xì)節(jié)表現(xiàn)的物體來說，使用自適應(yīng)八叉樹來存儲紋理將最大限度的節(jié)省存儲開銷。

3 GPU實現(xiàn)

GPU（Graphic Processing Units，圖形處理單元）驅(qū)動3D圖形進(jìn)入了新的復(fù)興時代?，F(xiàn)代的高級編程語言聯(lián)合難以置信的并行計算能力，可以輕易地完成實時的模糊陰影、精確的照明模型和真實的材質(zhì)影響。傳統(tǒng)上在程序中用語句遍歷八叉樹進(jìn)行查找是個比較慢的過程，而在 GPU上實現(xiàn)八叉樹后，紋理的查找速度大幅提高，實時繪畫才能較好的實現(xiàn)。

在 CPU上實現(xiàn)八叉樹的一個很簡單的辦法是用指針將節(jié)點連接在一起，每個節(jié)點包含一個指向其子節(jié)點的指針數(shù)組，葉節(jié)點中則只包含數(shù)據(jù)而沒有指針。每個節(jié)點包含8個指針，指向其子節(jié)點。

在 GPU上實現(xiàn)八叉樹與此相似，只是將指針變?yōu)榱思y理中的索引，索引被編碼成RGB值。葉節(jié)點的RGB值則干脆直接存儲在其父節(jié)點的索引中，并用Alpha通道來區(qū)分某個子節(jié)點中存儲的到底是索引還是葉節(jié)點的 RGB值。換句話說，節(jié)點中存儲的要么是用于指向其子節(jié)點的RGB值（即索引）、要么就是其葉節(jié)點的 RGB值（即數(shù)據(jù)）。本文的實現(xiàn)同樣需要依賴紋理查詢(dependent texture lookup)。自適應(yīng)八叉樹和規(guī)則八叉樹在存儲方式和 GPU實現(xiàn)等方面都是類似的，下文中提到的八叉樹紋理則泛指包含自適應(yīng)八叉樹紋理在內(nèi)的一般意義上的八叉樹紋理。

3.1 紋理存儲

本文采取的方法是把八叉樹存儲在一個8位的RGBA 3D紋理中，這種紋理叫做間接池。間接池中的最小存儲元素叫做單元，每個單元存儲一組RGBA值（索引或者數(shù)據(jù)值）。間接池又被細(xì)分為間接?xùn)鸥?，間接?xùn)鸥袷怯?×2×2個單元組成的立方體，那么每個間接?xùn)鸥窬捅硎疽粋€樹節(jié)點，它對應(yīng)于CPU實現(xiàn)中每個樹節(jié)點包含的8個指針。每個間接?xùn)鸥竦膯卧梢允强盏模蛘邽橐韵虑闆r之一：

（1）如果相應(yīng)的子節(jié)點為葉節(jié)點，則單元中存儲的是數(shù)據(jù)值；

（2）如果相應(yīng)的子節(jié)點為另一個非葉的子節(jié)點，則單元中存儲的是一個間接?xùn)鸥竦乃饕?/p>

圖2展示了間接池中八叉樹的存儲結(jié)構(gòu)，第一個間接?xùn)鸥裰械?個有色子塊表示存儲的是索引，后3個間接?xùn)鸥竦母鲉卧鶎?yīng)的子節(jié)點是葉節(jié)點，存儲的是數(shù)據(jù)值。

圖2 間接池存儲結(jié)構(gòu)示意圖

為了清晰起見，在圖中將間接?xùn)鸥穹蛛x開來，而在實際的存儲結(jié)構(gòu)中間接?xùn)鸥袷沁B續(xù)的。

如果用戶想得到256×256×256的分辨率，就要設(shè)置間接池中的間接?xùn)鸥駛€數(shù)為128×128× 128，這樣間接池中的單元的分辨率就是(2×128)×(2×128)×(2×128)。

前面已提到，在單元中，數(shù)據(jù)和子節(jié)點索引都是存儲為RGB元組的形式。Alpha通道則作為區(qū)分單元內(nèi)容的標(biāo)志。Alpha=1表明是數(shù)據(jù)，Alpha=0.5表明是索引，Alpha=0表明是空節(jié)點。八叉樹的根節(jié)點就存儲在間接池的（0，0，0）處。

3.2 紋理查找

把八叉樹存儲在紋理存儲器中之后，需要在片段程序中對它進(jìn)行訪問。和標(biāo)準(zhǔn)的3D紋理一樣，樹把紋理定義在單位立方體中。如果希望獲得在樹中某點M處存儲的紋理值，那么要從樹的根節(jié)點開始，順序訪問包含M點的節(jié)點，直到葉節(jié)點為止。

對于某個深度D，完全樹會在單位立方體內(nèi)產(chǎn)生分辨率為 2D×2D×2D的規(guī)則柵格。把該柵格叫做深度D柵格，樹在深度D的每個節(jié)點都對應(yīng)于該柵格的一個單元，顯然M也位于深度為D的被訪問節(jié)點所對應(yīng)的單元中。設(shè)M在該單元中的相對坐標(biāo)為(XD，YD，ZD)，該單元在樹中的坐標(biāo)即為被訪問節(jié)點間接?xùn)鸥竦乃饕齀D，再設(shè)間接池中間接?xùn)鸥竦膫€數(shù)為S，用這些參數(shù)可得到間接池中的查找坐標(biāo)

然后得到了間接池中 P點所存儲的 RGBA值。根據(jù)Alpha通道的值判斷，如果子節(jié)點是葉節(jié)點，將會返回RGB值，否則就表明存儲的值是索引，把 RGB值作為該子節(jié)點的間接?xùn)鸥竦乃饕齀D+1，并繼續(xù)查找下一個樹深度。圖3為樹層數(shù)為3時的間接池查找過程示意。

樹的深度是有一定限制的，對于1024×1024分辨率的顯示器來說，深度 10已經(jīng)是硬件能支持的最大值，因為此時已經(jīng)達(dá)到了像素級水平，再增加深度已經(jīng)沒有意義。

所以每次查找的紋理訪問次數(shù)也是有限的，對于最大深度為8的自適應(yīng)八叉樹，顯然最多只需要8次訪問就可以找到間接池中的目標(biāo)點了。

圖3 紋理查找過程

4 實驗結(jié)果

隨著幾何體表面積的增加，八叉樹的節(jié)點數(shù)會大幅度增加，占用的存儲空間也會越來越多，對于有海量數(shù)據(jù)的模型來說，八叉樹紋理也是不可實現(xiàn)的。所以目前3D紋理主要應(yīng)用于較小型的物體上。而由于對不同區(qū)域采用了不同的分辨率，只占幾何體一小部分的高細(xì)節(jié)部位才需要較多的節(jié)點，自適應(yīng)八叉樹紋理能較好的用于部分大型模型。

針對表面積較大的 Mouse模型和表面積較小的Laddy模型，本文的實現(xiàn)對比了使用固定深度的規(guī)則八叉樹和使用自適應(yīng)八叉樹進(jìn)行繪畫時兩者的占用存儲空間、建樹時間、指定的最大深度等數(shù)據(jù)，如表1和圖4所示。

當(dāng)樹深度指定為9或10時，由于節(jié)點數(shù)量過于龐大，即使對于表面積較小的Laddy模型，Matt Pharr[4]的實現(xiàn)程序在構(gòu)建規(guī)則八叉樹時經(jīng)過 30多分鐘仍未得到結(jié)果，而本文的實現(xiàn)在構(gòu)建自適應(yīng)八叉樹時則不存在這個問題。

此外在樹深度較小時，規(guī)則八叉樹不能進(jìn)行很理想的細(xì)節(jié)繪畫，因為此時的樹節(jié)點不能很好的近似匹配物體表面，繪畫時的鋸齒現(xiàn)象比較嚴(yán)重。

表1 規(guī)則八叉樹和自適應(yīng)八叉樹的相關(guān)數(shù)據(jù)

5 結(jié) 論

本文提出了一種 GPU上的自適應(yīng)八叉樹紋理算法：利用自適應(yīng)八叉樹來存儲紋理信息，達(dá)到在局部進(jìn)行細(xì)節(jié)表現(xiàn)的目的，更進(jìn)一步節(jié)省了存儲空間；同時經(jīng)過 GPU加速，實現(xiàn)了細(xì)節(jié)實時繪畫。實驗結(jié)果表明，使用自適應(yīng)八叉樹紋理，在相同的最大分辨率情況下比規(guī)則八叉樹紋理占用了更小的存儲空間，也可在更高的分辨率水平上進(jìn)行比較理想的細(xì)節(jié)繪畫，甚至是像素級的逐點繪畫。從而，本文改進(jìn)了八叉樹紋理的構(gòu)建和存儲，同時利用了 GPU加速，很大程度上解決了八叉樹紋理自適應(yīng)分辨率的局限，實現(xiàn)了自適應(yīng)分辨率的實時繪畫。

本文提出的這種自適應(yīng)八叉樹紋理繪畫算法還有以下幾個需要優(yōu)化的方向：一是剛開始繪畫時的延時比較嚴(yán)重，因為在最初開始繪畫時要進(jìn)行適應(yīng)分辨率的節(jié)點細(xì)分和新建存儲，相當(dāng)于將最初的構(gòu)建八叉樹紋理的時間分散到繪畫步驟中去，雖然極大的節(jié)省了最初構(gòu)建八叉樹紋理的時間，但是部分影響到了繪畫時的實時性。二是本文的實現(xiàn)依然沒有解決模型中非常接近或相交的表面的處理問題，例如皮膚和衣服。

圖4 實驗結(jié)果

[1]Catmull E E. A subdivision algorithm for computer display of curved surfaces [D]. University of Utah,1974.

[2]David Benson, Joel Davis. Octree textures [C]//Proceedings of SIGGRAPH 02, 2002: 785-790.

[3]DeBry D, Gibbs J, Petty D, et al. Painting and rendering textures on unparameterized models [C]//Proceedings of SIGGRAPH 02, 2002: 763-768.

[4]Matt Pharr. GPU精粹2[M]. 北京: 清華大學(xué)出版社,2007. 425-438.

[5]Lefohn A E. Glift: generic data structures for graphics hardware [D]. University of California, 2006.

[6]張傳明, 潘 懋, 徐繪宏. 基于分塊混合八叉樹編碼的海量體視化研究[J]. 計算機工程, 2007, 33(14):33-35.

[7]蘇超軾, 趙明昌, 張向文. GPU加速的八叉樹體繪制算法[J]. 計算機應(yīng)用, 2008, 28(5): 1232-1235, 1239.