張宇

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2015）14-0054-04

1 引言

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

第二部分： 編碼方法。簡要介紹我們對八叉樹進行編碼的基本方法 。

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

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

2 對于八叉樹的編碼及計算方法

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

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

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

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

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

3 基于八叉樹的場景管理

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

3.1 八叉樹的建立

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

3.2 動態(tài)場景的管理

3.2.1 編碼的應(yīng)用

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

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

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

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

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

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

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

3.2.3 場景裁減

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

4 實驗結(jié)果與結(jié)論

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

5 未來工作展望

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

參考文獻：

[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]. 測繪學報， 1998，27（3）.

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