一種基于八叉樹的動(dòng)態(tài)場(chǎng)景管理方式

張宇

摘要：在高度真實(shí)感的場(chǎng)景繪制中，相當(dāng)多的應(yīng)用需要一棵樹結(jié)構(gòu)來管理整個(gè)場(chǎng)景。對(duì)場(chǎng)景的搜索意味著對(duì)樹結(jié)構(gòu)的遍歷的過程，物體的變化意味著對(duì)樹結(jié)構(gòu)的重新建立過程。這些工作都是相當(dāng)耗費(fèi)資源卻又無法避免的過程。該文通過建立一棵八叉樹來管理整個(gè)場(chǎng)景，使用樹結(jié)點(diǎn)的編碼，經(jīng)過相對(duì)簡(jiǎn)單的計(jì)算來得到某結(jié)點(diǎn)的相鄰結(jié)點(diǎn)的編碼，并結(jié)合樹的有序結(jié)構(gòu)，來完成了高效的對(duì)于樹結(jié)點(diǎn)的查找和部分樹結(jié)構(gòu)的重建工作。

關(guān)鍵詞： 動(dòng)態(tài)場(chǎng)景；八叉樹；編碼

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）14-0054-04

1 引言

在高度真實(shí)感的場(chǎng)景繪制中，常常需要使用一棵樹結(jié)構(gòu)來管理整個(gè)場(chǎng)景的數(shù)據(jù)。常見的有BSP樹，kd樹，八叉樹等[1][2]。這樣通過對(duì)場(chǎng)景的劃分，將場(chǎng)景中的各種數(shù)據(jù)存儲(chǔ)到樹的各個(gè)葉結(jié)點(diǎn)中。但是如果我們?cè)谒阉髂硞€(gè)物體的具體位置的時(shí)候，難免需要對(duì)整棵樹進(jìn)行遍歷。對(duì)于動(dòng)態(tài)場(chǎng)景來說，在物體運(yùn)動(dòng)過程中，整個(gè)場(chǎng)景的樹結(jié)構(gòu)不會(huì)是一成不變的，因此還涉及到樹結(jié)構(gòu)的重建。與前兩種結(jié)構(gòu)想比，八叉樹具有更直觀的特性，并且容易控制，可以根據(jù)各種需要設(shè)置各種分割標(biāo)準(zhǔn)。作為一種在計(jì)算機(jī)圖形學(xué)中廣泛使用的樹結(jié)構(gòu)，八叉樹在很多方面都上都有應(yīng)用。對(duì)其的遍歷過程實(shí)際上就是找出一系列滿足給定要求的結(jié)點(diǎn)的過程。在對(duì)于這個(gè)問題已經(jīng)提出的方法中，大致分為兩類：第一，自底向上的方法。比如在光線追蹤中，從光線開始的葉結(jié)點(diǎn)出發(fā)，按照光線的方向搜索它的兄弟結(jié)點(diǎn)和父結(jié)點(diǎn)等，以得到一系列的葉結(jié)點(diǎn)[3] [4] [5]。第二，自頂向下的方法。它是從樹的根結(jié)點(diǎn)開始，遞歸的搜索整棵樹的結(jié)構(gòu)，如果當(dāng)前結(jié)點(diǎn)有光線通過，則將當(dāng)前結(jié)點(diǎn)加入到待求序列中，直到搜索完所有的葉結(jié)點(diǎn)為止[6] [7] [8] [9] [10]。但是上述方法中都很少對(duì)物體發(fā)生運(yùn)動(dòng)后如何改變樹結(jié)構(gòu)進(jìn)行討論。本文在八叉樹的基礎(chǔ)上，設(shè)計(jì)了動(dòng)態(tài)場(chǎng)景的管理模式，下文結(jié)構(gòu)如下：

第二部分： 編碼方法。簡(jiǎn)要介紹我們對(duì)八叉樹進(jìn)行編碼的基本方法 。

第三部分：介紹我們用于動(dòng)態(tài)場(chǎng)景管理的數(shù)據(jù)結(jié)構(gòu)和方法。

第四部分與第五部分得出結(jié)論并對(duì)將來工作進(jìn)行展望。

2 對(duì)于八叉樹的編碼及計(jì)算方法

我們對(duì)八叉樹的每個(gè)結(jié)點(diǎn)進(jìn)行編碼，通過編碼結(jié)合樹結(jié)構(gòu)來完成對(duì)八叉樹相鄰結(jié)點(diǎn)的查詢[11]。如圖1所示， 線性八叉樹的編碼基準(zhǔn)體系劃分為：

如果當(dāng)前編碼為0的結(jié)點(diǎn)需要進(jìn)行下一層剖分，則它的八個(gè)子結(jié)點(diǎn)的編碼按照類似順序依次為：00，01，02，03，04，05，06，07其它依次類推。對(duì)于任一結(jié)點(diǎn)編碼A = q1q2…qi…qn，

我們首先判斷其是否為邊界結(jié)點(diǎn)， 若從q1至qn全部屬于E 8 或S 8 或W 8 或N 8 或U 8 或D8，則在有公共面的相鄰結(jié)點(diǎn)中，其對(duì)應(yīng)的東部結(jié)點(diǎn)或南部結(jié)點(diǎn)或西部結(jié)點(diǎn)或北部結(jié)點(diǎn)或上部結(jié)點(diǎn)或下部結(jié)點(diǎn)將分別不存在。

我們就可以通過當(dāng)前結(jié)點(diǎn)的編碼來計(jì)算出它的相鄰結(jié)點(diǎn)的編碼，但是要注意這里的計(jì)算是采取八進(jìn)制的。對(duì)于相鄰的上下結(jié)點(diǎn)間的計(jì)算如下：若 qn 屬于上部集合，根據(jù)八叉樹編碼標(biāo)準(zhǔn)體系，可以直接得其下面結(jié)點(diǎn)的編碼為A + 4， 而其上面相鄰結(jié)點(diǎn)編碼的求解則要經(jīng)過如下判斷：從編碼的末位qn按從右到左的順序掃描， 直到找到第一個(gè)不屬于上部集合的編碼qi （1≤i≤n- 1， i 為從左到右的碼位序號(hào)）為止，顯然右邊的n- i個(gè)編碼位都屬于上部集合，將它們的值均加4，qi的值減4，而q1q2…qi-1的值不變，此時(shí)得到的新編碼即為所求相鄰的上部結(jié)點(diǎn)的編碼（若找不到不屬于上部集合的編碼，則表明該結(jié)點(diǎn)為上邊界結(jié)點(diǎn)，其上相鄰結(jié)點(diǎn)不存在，下面的類似）。若qn 屬于下部集合， 則其上面相鄰結(jié)點(diǎn)編碼為A - 4， 對(duì)其下部相鄰結(jié)點(diǎn)編碼的求解， 也可從編碼的末位qn 按從右到左的順序掃描， 直到找到第一個(gè)不屬于下部集合的編碼qi （1≤i≤n- 1）為止，顯然右邊的n- i個(gè)編碼位都屬于下部集合，將它們的值均減4，qi的值加4，其余的不變，得到的新編碼即為所求相鄰下部結(jié)點(diǎn)的編碼。

對(duì)于已知結(jié)點(diǎn)東、南、西、北四個(gè)方向相鄰結(jié)點(diǎn)的編碼，當(dāng)末尾qn 分別是0或者4，1或者5，2或者6，3或者7時(shí)，采取相同的計(jì)算方法。這樣，我們就可以通過當(dāng)前已知結(jié)點(diǎn)的編碼，得到和它有公共面的相鄰結(jié)點(diǎn)的所有編碼。這種結(jié)算方式將在我們的動(dòng)態(tài)場(chǎng)景管理模式中使用，另一方面，在計(jì)算過程中相鄰結(jié)點(diǎn)大小不一致的情況將在下文中進(jìn)行討論。

3 基于八叉樹的場(chǎng)景管理

我們選取八叉樹來對(duì)整個(gè)場(chǎng)景的結(jié)構(gòu)進(jìn)行組織，用它來劃分整個(gè)場(chǎng)景的空間，劃分的標(biāo)準(zhǔn)是八叉樹的單個(gè)結(jié)點(diǎn)內(nèi)最多含有的物體數(shù)量。在開始討論前，為了方便與直觀先進(jìn)行幾項(xiàng)假設(shè)：第一，假設(shè)與在場(chǎng)景中的物體所占有的空間相比，整個(gè)場(chǎng)景的空間占有絕對(duì)性優(yōu)勢(shì)，換句話說，整個(gè)場(chǎng)景的空間范圍遠(yuǎn)大于整個(gè)場(chǎng)景中所有物體所占有的空間范圍；第二，假設(shè)樹結(jié)構(gòu)建立后，場(chǎng)景中的最大物體占有的空間范圍不會(huì)超過最小的結(jié)點(diǎn)的空間范圍，也就是說，不會(huì)有物體在樹結(jié)構(gòu)剛建立好的時(shí)候占有一個(gè)結(jié)點(diǎn)以上的空間，并且在樹結(jié)構(gòu)發(fā)生改變后也不會(huì)有這樣的情況出現(xiàn)。由于我們主要考慮的問題就是當(dāng)場(chǎng)景中有物體發(fā)生運(yùn)動(dòng)或者其他改變的時(shí)候，整個(gè)場(chǎng)景的樹結(jié)構(gòu)跟著變化的過程。在這樣的過程中，整棵樹都重新建立一次是不太現(xiàn)實(shí)的，會(huì)造成過多的時(shí)間和計(jì)算開銷；整棵樹完全不變也是不太可能的，這樣很難反映出場(chǎng)景中發(fā)生的變化；只將發(fā)生變化的那部分樹結(jié)構(gòu)進(jìn)行重建是一種相對(duì)比較好的選擇。因此，我們將場(chǎng)景中的物體數(shù)據(jù)和樹結(jié)構(gòu)分離開來，在樹結(jié)構(gòu)中不涉及到具體的物體數(shù)據(jù)，只存儲(chǔ)指向每一個(gè)物體數(shù)據(jù)的指針，這樣在發(fā)生變化時(shí)只需要進(jìn)行指針的移動(dòng)而不用移動(dòng)大量的數(shù)據(jù)。例如有一個(gè)物體M當(dāng)前位于A結(jié)點(diǎn)內(nèi)（為劃分后的葉子結(jié)點(diǎn)，下同），將向A結(jié)點(diǎn)右邊相鄰的B結(jié)點(diǎn)運(yùn)動(dòng)，如圖2所示。則只需要將存儲(chǔ)在A結(jié)點(diǎn)內(nèi)的指向物體M的指針轉(zhuǎn)賦給B結(jié)點(diǎn)并清除A結(jié)點(diǎn)內(nèi)的指針即可。

3.1 八叉樹的建立

建立樹的過程如下所述：第一步，建立一個(gè)根結(jié)點(diǎn)，將場(chǎng)景中的所有物體都賦予該結(jié)點(diǎn)。第二步，判斷此結(jié)點(diǎn)是否滿足劃分要求（比如，單個(gè)結(jié)點(diǎn)中最多只能有一個(gè)物體存在），如果滿足要求，則分別判斷每個(gè)物體在根結(jié)點(diǎn)中的所在位置，在相應(yīng)位置分別生成相應(yīng)的子結(jié)點(diǎn)，將物體賦予生成的結(jié)點(diǎn)，并將其父結(jié)點(diǎn)中的該物體撤銷掉。第三步，對(duì)每一個(gè)子結(jié)點(diǎn)重復(fù)步驟二，直到?jīng)]有可以再次劃分的結(jié)點(diǎn)為止。最后物體只應(yīng)該存在于八叉樹的葉結(jié)點(diǎn)中。假設(shè)在場(chǎng)景初始化的時(shí)候，生成如下所示的樹型結(jié)構(gòu)（未含有物體的葉結(jié)點(diǎn)沒有表示出來）：

3.2 動(dòng)態(tài)場(chǎng)景的管理

3.2.1 編碼的應(yīng)用

這時(shí)我們就可以通過計(jì)算A的右邊相鄰結(jié)點(diǎn)B的編碼，然后搜索上述結(jié)構(gòu)，得到結(jié)點(diǎn)B的位置。由于我們計(jì)算編碼的方法是按照都是同一層次的結(jié)點(diǎn)計(jì)算的，所以這里存在搜索不到的情況，這表示結(jié)點(diǎn)B和結(jié)點(diǎn)A不是一個(gè)層次上的，我們需要采取不規(guī)則處理?；谖覀兊募僭O(shè)一，樹中含有物體的葉結(jié)點(diǎn)數(shù)量會(huì)遠(yuǎn)小于總結(jié)點(diǎn)數(shù)量，并不會(huì)使用太多的額外存儲(chǔ)開銷，所以這樣的搜索效率遠(yuǎn)遠(yuǎn)高于去遍歷樹來得到結(jié)點(diǎn)B的位置。事實(shí)上在一般空間場(chǎng)景中，這樣的假設(shè)總是成立的，故這樣的方法是可行的。

3.2.2 不規(guī)則相鄰結(jié)點(diǎn)的處理

在實(shí)際測(cè)試中，發(fā)生這種情況的概率很大，因此這部分才是影響我們方法的主要部分。在下面的討論中，為了繪圖直觀，我們用平面的四叉樹來代替立體的八叉樹，但是在方法上二者是一致的。分別由兩種情況存在：分別是物體從層次較底的結(jié)點(diǎn)（半徑較大的結(jié)點(diǎn)）向?qū)哟屋^高的結(jié)點(diǎn)（半徑較小的結(jié)點(diǎn)）運(yùn)動(dòng)或者相反。

如圖5.a和5.b 所示，當(dāng)物體從層次較低的結(jié)點(diǎn)向?qū)哟屋^高的結(jié)點(diǎn)運(yùn)動(dòng)時(shí)，我們按照上述方法計(jì)算出的結(jié)點(diǎn)編碼實(shí)際上是結(jié)點(diǎn)B的編碼q1q2…qi…qn，因此我們不會(huì)在當(dāng)前的MAP結(jié)構(gòu)中搜索到結(jié)點(diǎn)B。我們需要得到的是結(jié)點(diǎn)B2的編碼，顯然，在當(dāng)前MAP結(jié)構(gòu)中的編碼位數(shù)小于n的結(jié)點(diǎn)不符合要求，將剩下的結(jié)點(diǎn)編碼按照從左向右完全匹配的原則，重新搜索q1q2…qi…qn，我們將得到q1q2…qi…qn …q n + m 這樣的編碼值，若未能得到結(jié)果，則將如圖6.c或者圖6.d 所示。此時(shí)我們選取相對(duì)位數(shù)較少的編碼q1q2…qi…qn …q n + m，尋找該結(jié)點(diǎn)的父結(jié)點(diǎn)，直到得到編碼為q1q2…qi…qn的結(jié)點(diǎn)為止，即為當(dāng)前的結(jié)點(diǎn)B。判斷交界點(diǎn)P位于結(jié)點(diǎn)B的位置，如果當(dāng)前位置有已存在的結(jié)點(diǎn)，則將物體加入到該結(jié)點(diǎn)中，并判斷此結(jié)點(diǎn)現(xiàn)在是否需要進(jìn)行劃分，如圖5.a。如果當(dāng)前位置沒有已存在的葉結(jié)點(diǎn)，則建立一個(gè)結(jié)點(diǎn)，其父結(jié)點(diǎn)為B，將其添加到八叉樹中，如圖5.b。如果當(dāng)前位置有存在的非葉子結(jié)點(diǎn)，則重復(fù)上述方法，直到確定該目標(biāo)結(jié)點(diǎn)的準(zhǔn)確位置為止。

如圖5.c和5.d所示，當(dāng)物體從層級(jí)較高的結(jié)點(diǎn)向?qū)哟屋^低的結(jié)點(diǎn)運(yùn)動(dòng)時(shí)，我們按照上述編碼方法找到的結(jié)點(diǎn)實(shí)際上是結(jié)點(diǎn)B的一部分。因此我們將計(jì)算結(jié)果q1q2…qi…qn去掉最后一位，變成q1q2…qi…q n – 1，然后在MAP中按照從左到右的原則進(jìn)行匹配搜索，如果能得到完全一致的結(jié)果，即為在MAP中有q1q2…qi…q n – 1該編碼的存在。則如圖5.c所示，將物體加入到該結(jié)點(diǎn)中并判斷是否需要進(jìn)行下一層次的劃分。如果沒有完全一致的結(jié)果，不過搜索到q1q2…qi…q n – 1 …q n – 1 + m這樣的編碼，則從中選取位數(shù)較小的一個(gè)，尋找該結(jié)點(diǎn)的父結(jié)點(diǎn)，直到得到編碼為q1q2…qi…q n – 1的結(jié)點(diǎn)為止，即位當(dāng)前的結(jié)點(diǎn)B，如圖5.d所示。判斷交界點(diǎn)P位于結(jié)點(diǎn)B的位置，此時(shí)當(dāng)前位置不會(huì)有已存在的葉結(jié)點(diǎn)，如果當(dāng)前位置沒有已存在的結(jié)點(diǎn)，則建立一個(gè)結(jié)點(diǎn)，其父結(jié)點(diǎn)為B，將其添加到八叉樹中。如果當(dāng)前位置有存在的非葉子結(jié)點(diǎn)，則就變成如圖5.a或5.b所示的情況。如果上述搜索沒有得到合適的結(jié)果，再去掉編碼的最后一位，變成q1q2…qi…q n – 2重復(fù)上述過程，當(dāng)該值只剩下一位數(shù)時(shí)仍然沒有得到結(jié)果的話，則在根結(jié)點(diǎn)的相關(guān)位置建立此結(jié)點(diǎn)并添加到八叉樹中。

之前A作為包含物體的葉結(jié)點(diǎn)總是存在的，在物體M離開結(jié)點(diǎn)A后，如果結(jié)點(diǎn)A內(nèi)部仍然有物體存在，則這部分樹結(jié)構(gòu)保持不變。如果結(jié)點(diǎn)A內(nèi)沒有物體，則我們需要把結(jié)點(diǎn)A從樹結(jié)構(gòu)中刪除和在MAP中刪除。然后考慮A的父結(jié)點(diǎn)是否還滿足劃分條件，如果滿足的話則其余結(jié)構(gòu)不用更改，如果不滿足則需要將該父結(jié)點(diǎn)的其他子結(jié)點(diǎn)從上述兩個(gè)結(jié)構(gòu)中刪除，并將屬于其他子結(jié)點(diǎn)的物體賦予給該父結(jié)點(diǎn)，然后再加入到MAP中。對(duì)于有物體進(jìn)入的結(jié)點(diǎn)B，我們?cè)谏鲜鎏幚斫Y(jié)束后，從MAP中刪除掉已經(jīng)在樹結(jié)構(gòu)中不存在的葉結(jié)點(diǎn)，并加入新生成的有物體存在的葉結(jié)點(diǎn)。

當(dāng)我們?cè)贛AP中沒有搜索到求出的編碼值q1q2…qi…qn時(shí)，此時(shí)就面臨著選擇該運(yùn)動(dòng)情況是從層次較高的結(jié)點(diǎn)向?qū)哟屋^低的結(jié)點(diǎn)還是從層次較低的結(jié)點(diǎn)向?qū)哟屋^高的結(jié)點(diǎn)。實(shí)際上只有一種可能，因此我們要盡量避免多余的判斷和計(jì)算。我們假設(shè)在當(dāng)前整棵樹中，最深層次為a，在我們的定義中，結(jié)點(diǎn)的層次n在數(shù)值上越大，則它的層次越低。若結(jié)點(diǎn)A的層次n < a/2，則我們的判斷先向更高的層次進(jìn)行，也就是說對(duì)于從結(jié)點(diǎn)A運(yùn)動(dòng)到結(jié)點(diǎn)B的物體，我們先按照上述從低層次結(jié)點(diǎn)向高層次結(jié)點(diǎn)運(yùn)動(dòng)的方法處理，若這樣沒有得到我們想要的結(jié)果，則按照相反的方向進(jìn)行處理。若結(jié)點(diǎn)A的層次n >= a/2，則我們按照先按照高層次結(jié)點(diǎn)向低層次結(jié)點(diǎn)運(yùn)動(dòng)的方向處理，未能得到結(jié)果再反過來處理。

3.2.3 場(chǎng)景裁減

由于我們采用的八叉樹結(jié)構(gòu)每個(gè)結(jié)點(diǎn)都是立方體，因此對(duì)于場(chǎng)景裁減的操作比較簡(jiǎn)單。用當(dāng)前MAP中的葉結(jié)點(diǎn)的六個(gè)面和視角錐體進(jìn)行比較，很容易得出哪些結(jié)點(diǎn)完全位于場(chǎng)景裁減中，哪些部分位于以及哪些不在其中，完成對(duì)整個(gè)場(chǎng)景的裁剪。

4 實(shí)驗(yàn)結(jié)果與結(jié)論

測(cè)試場(chǎng)景由12個(gè)精細(xì)的并且都能夠在場(chǎng)景中自由運(yùn)動(dòng)的物體構(gòu)成，在它們開始運(yùn)動(dòng)之前，場(chǎng)景與樹結(jié)構(gòu)如圖6所示。經(jīng)過一段時(shí)間的運(yùn)動(dòng)后，場(chǎng)景與樹的結(jié)構(gòu)如圖7所示。在這個(gè)過程中，八叉樹的結(jié)構(gòu)一直隨著物體的運(yùn)動(dòng)發(fā)生改變，中間沒有停頓。在我們的例子中，黃色的線表示結(jié)點(diǎn)的范圍，藍(lán)色的線表示物體的AABB包圍盒[12]，它是用來進(jìn)行碰撞檢測(cè)的。整個(gè)方法的工作情況和我們之前討論的一致，因此這是一種有用的管理動(dòng)態(tài)場(chǎng)景的方法。

5 未來工作展望

由于暫時(shí)缺乏時(shí)間，沒有來得及進(jìn)行大規(guī)模的數(shù)據(jù)測(cè)試，故這是我們下一步需要進(jìn)行的工作。在這之后，可以更改八叉樹的劃分標(biāo)準(zhǔn)，比如單個(gè)結(jié)點(diǎn)內(nèi)表面的多邊型數(shù)量。在這種情況下，我們可以將對(duì)物體LOD模型的操作和整個(gè)場(chǎng)景結(jié)合起來，進(jìn)一步提高渲染效率。

參考文獻(xiàn)：

[1] GLASSNER A.An Introduction to Ray Tracing[M]. Morgan Kaufmann， 1989.

[2] HAVRAN V.Heuristic Ray Shooting Algorithms[D].Czech Technical University in Prague， 2001.

[3] Glassner A S. Space Subdivision for Fast Ray Tracing[J]. IEEE Computer Graphics & Applications， 1984，4（10）：15-22.

[4] Samet H. Implementing Ray Tracing with Octrees and Neighbor Finding[J]. Computer & Graphics，1989，13（4）：445-460.

[5] Samet H.Applications of Spatial Data Structures： Computer Graphics， Image Processing， and GIS. Addison-Wesley，1990.

[6] Agate M， Grimsdale R L， Lister P F. The HERO Algorithm for Ray Tracing Octrees. Advances in Computer Graphics Hardware IV R.L. Grimsdale， W. Strasser （eds） Springer-Verlag， New York， 1991.

[7] Cohen D， Shaked A. Photo-Realistic Imaging of Digital Terrains[J]. Computer Graphics Forum， 1993，12（3）：363-376.

[8] Endl R， Sommer M. Classification of Ray-Generators in Uniform Subdivisions an Octrees for Ray Tracing[J]. Computer Graphics Forum，1994，13（1）.

[9] Jansen F W. Data Structures for Ray-tracing. Data Structures for Raster Graphics L. Kessner， F.Peters， M. van Lierop （eds）. Springer-Verlag， 1985：57-73.

[10] Gargantini I， Atkinson H H. Ray Tracing an Octree： Numerical Evaluation of the First Intersection[J]. Computer Graphics Forum， 1993，12（4）.

[11] 肖樂斌，龔建華，謝傳節(jié).線性四叉樹和線性八叉樹鄰域?qū)ふ业囊环N新算法[J]. 測(cè)繪學(xué)報(bào)， 1998，27（3）.

[12] Gottschalk S.Collision Dctection Using Oriented Bounding Boxes[D]. Dept. Comput. Sci.， UNC Chapel Hill， 2000.