忘卻之湖

posts - 43, comments - 64, trackbacks - 0

??? kD 樹是二叉樹結構的一個變種，當前主要用于加速光纖跟蹤的遍歷過程。最簡單的排序二叉樹以各個元素的大小關系作為分割點，而 kD 樹簡而言之就是從數據中選擇一個“維度”構造一個超平面對數據集進行分割。比如要對學生數據進行分割，找出哪些學生的生日小于 2 月 18 日，那么就只要遍歷整個集合，把所有的數據分成。如果又要在符合第一次條件的學生中找出哪些學生是來自南京的，那么就只要再次進行比較規劃就可以辦到了。 kD 樹的帶來的性能提升很高，讓我們看一下常用加速結構的復雜度 [1] ，從 O(N) 到 O(logN) ：

Bounding Volumn Hierarchy
Grid
Octree （包括 Quadtree ）
kD Tree

　　一般來說，構造 kD 樹的方式有兩種：排序和掃描。我們參考了一些加速構造 kD 樹的方法，如采樣，再結合實際的 3D 模型來為大家說明具體的操作方法。

基本概念：

　　由于 kD 樹主要用于光線跟蹤等 3D 圖形學領域，所以很有必要把光線跟蹤的基本方法弄清楚。我們知道場景都是由三角形組成，整個空間的三角形組成了模型的拓撲結構。傳統的光柵化過程就是把所有變換過的三角形投射到屏幕上，也就是寫入幀緩沖。而光線跟蹤的最初概念來自于繪畫。 15 世紀意大利 Albrecht D?rer 發明了網格作畫的方法，也就是在待畫的物體前放一張同畫布一樣大小的紙質半透明網格，然后依次透過每個小格看物體，繪制那個小格子的圖畫，當把所有的小格子都畫滿了后，一幅畫也就畫好了。

　　我們由此可以想到暴力測試法，也就是從一個網格里發出光線后，檢測場景中每個三角形，然后確定點亮那個網格（像素）的是什么顏色。 kD 樹可以大幅度加速這個過程，類似于二叉樹的遍歷。

準備材料：

　　在真實的實現過程中，我們總是要面對許多模型的格式，比如 D3D 的 X 格式， QUAKE 系列所使用的 MD3/5 模型格式，以及諸多初學者所頭疼的 3DS ASE 格式。需要補充的是，如果牽涉到在場景中使用骨骼動畫，那么只有選擇 MD5 或者 X 格式， 3DS/ASE 文件中沒有記錄骨骼動畫所需要的權重節點等數據。

　　對于靜態模型來說，主要數據包括：頂點數據，三角形索引，紋理坐標，頂點向量（有可能沒有）。繪制模型的時候，用三角形索引來尋址，依次抽取頂點數組中的數據進行繪制。為了縮短開發周期，我們使用了來自 sourceforge.net 的 lib3ds[2] 開源庫來處理 3DS 模型。如圖：

　　這個 Hanana 模型由 10955 個頂點， 16221 個面（三角形）組成。我們用它來生成我們所需要的 kD 樹加速結構。

思路優先：

　　我們的 kD 樹的節點模型究竟應該是什么樣子的呢？讓我們看一下定義：

struct?kDInner{
unsigned?int?flagDimAndOffset;
//?bits?0..1?:?0?1?2代表x?y?z維
//?bits?2..30?:?offset?to?left?child
//?bit?31?:?是否是leaf
float?splitCoordinates;
};

struct?kDLeaf{
unsigned?int?flagAndOffset;
//?bits?0..30?:?在三角形數組組中的偏移量
//?bit?31?:?是否是leaf
unsigned?int?objectCount;//?三角形樹的數目
};

typedef?union{
kDLeaf?leaf;
kDInner?inner;
}kDNode;?//共用體，統inner和leaf統稱為為Node

??? 事實上，這樣一上來就如此的精簡并不方便構建kD樹，我們先用普通的容易理解的定義表現一個Node

union?offsetorsplitpos{
???? float ?SplitPos;
???? ulong ?AbsoluteOffset;
};

struct ?KDNode
{
????KDNode * ?Left;
????KDNode * ?Right;
????offsetorsplitpos?tag;
???? ulong ?Count;//當這個節電作為Inner使用的時候，Count儲存了Dimsion
};

　　每個三角形的 AABB(Axis Aligned Bounding Box 即軸對稱綁定盒 ) 也是必不可少的結構。 AABB 就很簡單了，可以定義成這樣：

struct AABB{
float min[3],max[3];
};

　　我們之所以要把每個三角形都打散，是為了計算合適的 Split Plane 位置，你可以想象為從什么地方把場景分成兩半，也就是把一堆三角形分成兩部分，代碼級的思路就是，計算合適的數組偏移量。那么什么叫做合適的呢？請看下面的這個公式 [3] ：

??? 看似好像很復雜，其實可以化簡為這樣的公式：

在這里， Ct 指遍歷整個節點包含的三角形遍歷時間，也就是渲染這一簇三角形的時間； Cl 指 Split Plane“ 左邊”的三角形遍歷時間，同理 Cr 是“右邊”的遍歷時間。引用的一些資料認為，

　　事實上， Cost(x) 是兩個單調函數 Cl(x) 、 Cr(x) 的線性疊加。我們要盡量找到 Cost(x) 最小的某個空間位置，或者是某一個三角形邊界，進而分割場景三角形。

　　顯然，這肯定由三步組成：

１、選擇合適的 Split Plane ，可以有三個維度，并且可以容易推斷總共有 2n 個

２、數數看左邊有多少個 AABBs

３、數數看右邊有多少個 AABBs

　　下面我們開始討論 2 種方法：排序與掃描。

Sort 排序

　　排序很容易理解。沿著軸將所有三角形的 AABB 排序（也就是對三角形索引數組進行排序）。排序后就可以直接把想要得位置和三角形數目帶入公式計算，如果繪制為函數圖像可以獲得最光滑連續的圖形。總花費為 O(nlogn) 。

Scan 掃描

　　掃描有些羅嗦，不過也很容易實現，最重要的是目前已經有成功的應用 [4] 。指定場景中的一個平面，遍歷三角形比較大小，記錄落在左邊和右邊的數目，再帶入公式。如果要獲得多個 Cost 數值，就必須要選擇多個位置進行計算。每次都要遍歷全部的三角形。經過處理后也可以達到 O(nlogn) 的復雜度，不過結合了采樣技術后可以獲得近似準確的結果，而且花費小的多。而且，這個過程是可以使用 SIMD 加速的。

　　還有一些技巧和疑問 [3] ：

１、是否總是計算三個軸中最小的那個位置，還是總是從一個軸計算？

２、樹需要細分到何種程度？每個 Leaf 需要有多少個三角形？

　　現在我們可以做進一步的推測，如果希望用光線跟蹤一個動態的場景，那么每當我們變換過矩陣后，都需要重新構造一次 kD 樹，所以為了達到實時交互式的速度，必須要對關鍵的步驟進行優化。而且生成樹的質量與遍歷的性能關系十分密切。

　　我們的思路有了，下面可以構思具體的實現過程

A. 準備三角形索引數組 Tris[] 。
B. 獲得整個場景的 AABB V ，其中 V.min[0] 就是場景的左邊界，以此類推。
C. 通過三角形索引數組讀取 3 個頂點，構造每個三角形的 AABB ，儲存到一個容器中 vector<AABB> AABBs ，同時記錄 AABB 究竟屬于哪個三角形。
D. 獲得三角形 AABBs 的數目 N ，如果大于一個數值比如 1024 就用步驟 FG 計算 3 次，否則只計算一次。獲得 AABBs 的開頭和末尾指針（迭代器）。
E. 如果選擇 Sort ，那么就要先對 AABBs 中的元素排序。這里我們采用 Scan 。
F. 在 (min[AXIS],max[AXIS]) 之間找幾個固定平面，比如 8 個。 AXIS 指選擇的坐標軸。
H. 帶入公式計算，選擇 Cost 最小的 Split Position ，生成 Node 。如果已經達到中止條件，那么就生成 Leaf Node ，否則生成 Inner Node 。把 v 從 Split Position 分成兩個 Voxel Vl 與 Vr 。把 AABBs 分割為兩個，從與 Split Position 最近的三角形開始。
G. 遍歷 AABBs 容器，比較平面和每個元素的位置，記錄 8 對數據。
I. 帶入 Vl 與 Vr 分別從 D 開始迭代。

??? 下面是分隔這個模型的輸出信息：

TriNum?:? 16220
Left?Voxel?has?:? 12377 ??Right?Voxel?has?:? 384
Left?Voxel?has?:? 2912 ???Right?Voxel?has?:? 946
Left?Voxel?has?:? 1025 ???Right?Voxel?has?:? 188
Left?Voxel?has?:? 415 ????Right?Voxel?has?:? 610
Left?Voxel?has?:? 128 ????Right?Voxel?has?:? 287
Left?Voxel?has?:? 68 ?????Right?Voxel?has?:? 60
Leaf?LEVEL?:? 5 ??Count?:? 128
Left?Voxel?has?:? 145 ????Right?Voxel?has?:? 142
Left?Voxel?has?:? 77 ?????Right?Voxel?has?:? 68
Leaf?LEVEL?:? 6 ??Count?:? 145
Left?Voxel?has?:? 61 ?????Right?Voxel?has?:? 81
Leaf?LEVEL?:? 6 ??Count?:? 142
Left?Voxel?has?:? 218 ????Right?Voxel?has?:? 392
Left?Voxel?has?:? 97 ?????Right?Voxel?has?:? 121
Leaf?LEVEL?:? 5 ??Count?:? 218
Left?Voxel?has?:? 211 ????Right?Voxel?has?:? 181
Left?Voxel?has?:? 114 ????Right?Voxel?has?:? 97
Leaf?LEVEL?:? 6 ??Count?:? 211
Left?Voxel?has?:? 82 ?????Right?Voxel?has?:? 99
Leaf?LEVEL?:? 6 ??Count?:? 181
Left?Voxel?has?:? 772 ????Right?Voxel?has?:? 111
Left?Voxel?has?:? 373 ????Right?Voxel?has?:? 399
Left?Voxel?has?:? 194 ????Right?Voxel?has?:? 179
Left?Voxel?has?:? 82 ?????Right?Voxel?has?:? 112
Leaf?LEVEL?:? 6 ??Count?:? 194
Left?Voxel?has?:? 111 ????Right?Voxel?has?:? 68
Leaf?LEVEL?:? 6 ??Count?:? 179
Left?Voxel?has?:? 190 ????Right?Voxel?has?:? 209
Left?Voxel?has?:? 99 ?????Right?Voxel?has?:? 91
Leaf?LEVEL?:? 6 ??Count?:? 190
Left?Voxel?has?:? 63 ?????Right?Voxel?has?:? 146
Left?Voxel?has?:? 516 ????Right?Voxel?has?:? 599
Left?Voxel?has?:? 246 ????Right?Voxel?has?:? 270
Left?Voxel?has?:? 124 ????Right?Voxel?has?:? 122
Leaf?LEVEL?:? 6 ??Count?:? 246
Left?Voxel?has?:? 126 ????Right?Voxel?has?:? 144
Left?Voxel?has?:? 285 ????Right?Voxel?has?:? 314
Left?Voxel?has?:? 150 ????Right?Voxel?has?:? 135
Left?Voxel?has?:? 152 ????Right?Voxel?has?:? 162
Left?Voxel?has?:? 4180 ???Right?Voxel?has?:? 528
Left?Voxel?has?:? 2220 ???Right?Voxel?has?:? 196
Left?Voxel?has?:? 1211 ???Right?Voxel?has?:? 100
Left?Voxel?has?:? 502 ????Right?Voxel?has?:? 709
Left?Voxel?has?:? 235 ????Right?Voxel?has?:? 267
Left?Voxel?has?:? 343 ????Right?Voxel?has?:? 366
Left?Voxel?has?:? 471 ????Right?Voxel?has?:? 538
Left?Voxel?has?:? 201 ????Right?Voxel?has?:? 270
Left?Voxel?has?:? 263 ????Right?Voxel?has?:? 275
Left?Voxel?has?:? 924 ????Right?Voxel?has?:? 103
Left?Voxel?has?:? 428 ????Right?Voxel?has?:? 496
Left?Voxel?has?:? 184 ????Right?Voxel?has?:? 244
Left?Voxel?has?:? 286 ????Right?Voxel?has?:? 210
Left?Voxel?has?:? 440 ????Right?Voxel?has?:? 596
Left?Voxel?has?:? 211 ????Right?Voxel?has?:? 229
Left?Voxel?has?:? 310 ????Right?Voxel?has?:? 286
Left?Voxel?has?:? 2437 ???Right?Voxel?has?:? 284
Left?Voxel?has?:? 1228 ???Right?Voxel?has?:? 120
Left?Voxel?has?:? 558 ????Right?Voxel?has?:? 670
Left?Voxel?has?:? 303 ????Right?Voxel?has?:? 255
Left?Voxel?has?:? 298 ????Right?Voxel?has?:? 372
Left?Voxel?has?:? 578 ????Right?Voxel?has?:? 631
Left?Voxel?has?:? 295 ????Right?Voxel?has?:? 283
Left?Voxel?has?:? 302 ????Right?Voxel?has?:? 329
Left?Voxel?has?:? 1466 ???Right?Voxel?has?:? 138
Left?Voxel?has?:? 805 ????Right?Voxel?has?:? 661
Left?Voxel?has?:? 430 ????Right?Voxel?has?:? 375
Left?Voxel?has?:? 346 ????Right?Voxel?has?:? 315
Left?Voxel?has?:? 653 ????Right?Voxel?has?:? 729
Left?Voxel?has?:? 347 ????Right?Voxel?has?:? 306
Left?Voxel?has?:? 367 ????Right?Voxel?has?:? 362
Left?Voxel?has?:? 2319 ???Right?Voxel?has?:? 152
Left?Voxel?has?:? 1413 ???Right?Voxel?has?:? 906
Left?Voxel?has?:? 825 ????Right?Voxel?has?:? 588
Left?Voxel?has?:? 437 ????Right?Voxel?has?:? 388
Left?Voxel?has?:? 180 ????Right?Voxel?has?:? 257
Left?Voxel?has?:? 98 ?????Right?Voxel?has?:? 82
Leaf?LEVEL?:? 6 ??Count?:? 180
Left?Voxel?has?:? 150 ????Right?Voxel?has?:? 107
Left?Voxel?has?:? 191 ????Right?Voxel?has?:? 197
Left?Voxel?has?:? 90 ?????Right?Voxel?has?:? 101
Leaf?LEVEL?:? 6 ??Count?:? 191
Left?Voxel?has?:? 68 ?????Right?Voxel?has?:? 129
Left?Voxel?has?:? 294 ????Right?Voxel?has?:? 294
Left?Voxel?has?:? 150 ????Right?Voxel?has?:? 144
Left?Voxel?has?:? 91 ?????Right?Voxel?has?:? 59
Leaf?LEVEL?:? 6 ??Count?:? 150
Left?Voxel?has?:? 51 ?????Right?Voxel?has?:? 93
Leaf?LEVEL?:? 6 ??Count?:? 144
Left?Voxel?has?:? 153 ????Right?Voxel?has?:? 141
Left?Voxel?has?:? 105 ????Right?Voxel?has?:? 48
Leaf?LEVEL?:? 6 ??Count?:? 153
Left?Voxel?has?:? 49 ?????Right?Voxel?has?:? 92
Leaf?LEVEL?:? 6 ??Count?:? 141
Left?Voxel?has?:? 457 ????Right?Voxel?has?:? 449
Left?Voxel?has?:? 214 ????Right?Voxel?has?:? 243
Left?Voxel?has?:? 124 ????Right?Voxel?has?:? 90
Leaf?LEVEL?:? 5 ??Count?:? 214
Left?Voxel?has?:? 102 ????Right?Voxel?has?:? 141
Left?Voxel?has?:? 79 ?????Right?Voxel?has?:? 62
Leaf?LEVEL?:? 6 ??Count?:? 141
Left?Voxel?has?:? 196 ????Right?Voxel?has?:? 253
Left?Voxel?has?:? 99 ?????Right?Voxel?has?:? 97
Leaf?LEVEL?:? 5 ??Count?:? 196
Left?Voxel?has?:? 133 ????Right?Voxel?has?:? 120
Left?Voxel?has?:? 56 ?????Right?Voxel?has?:? 77
Leaf?LEVEL?:? 6 ??Count?:? 133
Left?Voxel?has?:? 791 ????Right?Voxel?has?:? 733
Left?Voxel?has?:? 462 ????Right?Voxel?has?:? 329
Left?Voxel?has?:? 228 ????Right?Voxel?has?:? 234
Left?Voxel?has?:? 129 ????Right?Voxel?has?:? 99
Left?Voxel?has?:? 64 ?????Right?Voxel?has?:? 65
Leaf?LEVEL?:? 6 ??Count?:? 129
Left?Voxel?has?:? 117 ????Right?Voxel?has?:? 117
Leaf?LEVEL?:? 5 ??Count?:? 234
Left?Voxel?has?:? 171 ????Right?Voxel?has?:? 158
Left?Voxel?has?:? 90 ?????Right?Voxel?has?:? 81
Leaf?LEVEL?:? 5 ??Count?:? 171
Left?Voxel?has?:? 88 ?????Right?Voxel?has?:? 70
Leaf?LEVEL?:? 5 ??Count?:? 158
Left?Voxel?has?:? 423 ????Right?Voxel?has?:? 310
Left?Voxel?has?:? 205 ????Right?Voxel?has?:? 218
Left?Voxel?has?:? 114 ????Right?Voxel?has?:? 91
Leaf?LEVEL?:? 5 ??Count?:? 205
Left?Voxel?has?:? 112 ????Right?Voxel?has?:? 106
Leaf?LEVEL?:? 5 ??Count?:? 218
Left?Voxel?has?:? 177 ????Right?Voxel?has?:? 133
Left?Voxel?has?:? 86 ?????Right?Voxel?has?:? 91
Leaf?LEVEL?:? 5 ??Count?:? 177
Left?Voxel?has?:? 77 ?????Right?Voxel?has?:? 56
Leaf?LEVEL?:? 5 ??Count?:? 133

　　其中， C 可以用 foreach ， H 可以用 partition （ stable_partition ）等 STL 的算法。

核心的代碼如下：

void ?Count(AABB * ?BeginItr,AABB * ?EndItr,AXIS?Axis, float ?SplitPos, ulong * ?Cl, ulong * ?Cr)
{
???? for (?AABB * ?itr? = ?BeginItr?;?itr? != ?EndItr;?itr ++ ?){
????????( * Cl) += (?(itr -> max[Axis]? < ?SplitPos?)? ? ? 1 ?:? 0 ?);
????????( * Cr) += (?(itr -> min[Axis]? > ?SplitPos?)? ? ? 1 ?:? 0 ?);
????}
};

inline? bool ?Terminate( ulong ?TriCount, int ?Level)
{
???? if ?(?TriCount? < ? 128 ? || ?Level? > ?MAX_LEVEL){
???????? return ? true ;
????}
???? return ? false ;
};

inline? bool ?IsUpboundSmaller(AABB & ?AABB)
{
???? float ?half_width? = ?(?AABB.max[::gSplitAxis]? - ?AABB.min[::gSplitAxis]?) * 0.5f ;
???? return ?(AABB.max[::gSplitAxis]? - ?::gSplitPos)? < ?half_width? ? ? true ?:? false ;
};

float ?SAHCost(AXIS?Axis, ulong * ?Cl, ulong * ?Cr,AABB & ?V, float ?SplitPos)
{
???? ulong ?Nl? = ? * Cl;
???? ulong ?Nr? = ? * Cr;
???? float ?Length? = ?V.max[Axis]? - ?V.min[Axis];
???? float ?L? = ?SplitPos? - ?V.min[Axis],R? = ?SplitPos? - ?V.max[Axis];
???? float ?Pl? = ?L? / ?Length;
???? float ?Pr? = ? 1.0f ? - ?Pl;
???? float ?Tt? = ?TRAVERSAL_TIME;
???? float ?Til? = ?Nl? * ?INTERSECTION_TIME,Tir? = ?Nr? * ?INTERSECTION_TIME;
???? return ?Tt? + ?Pl * Nl * Til? + ?Pr * Nr * Tir;

};

void ?KDTreeBuild(KDNode * ?Root,AABB?V,AABB * ?BeginItr,AABB * ?EndItr,AXIS?Axis, int ?Level)
{
???? ulong ?TotalTriCount? = ?EndItr? - ?BeginItr;
???? if (?Terminate(TotalTriCount,Level)?)
???????? return ;

???? float ?SplitLoc[ 7 ];
???? float ?Cost[ 7 ];

???? ulong ?Cl? = ? 0 ,Cr? = ? 0 ;
???? float ?MinLoc? = ?V.min[Axis],MaxLoc? = ?V.max[Axis];
???? float ?step? = ?(MaxLoc? - ?MinLoc)? / ? 8.0f ;

???? for (? int ?i? = ? 0 ;i < 7 ?;i ++ ?){
????????SplitLoc[i]? = ?MinLoc? + ?step? * ? float (i + 1 );
????????Count(BeginItr,EndItr,Axis,SplitLoc[i], & Cl, & Cr);
????????Cost[i]? = ?SAHCost(Axis, & Cl, & Cr,V,SplitLoc[i]);
????????Cl? = ?Cr? = ? 0 ;
????}
???? float * ?pGoodCostPtr? = ?min_element(Cost,Cost + 7 );
????size_t?_Pos? = ?pGoodCostPtr? - ?Cost;

????::gSplitPos? = ?SplitLoc[_Pos];
????::gSplitAxis? = ?Axis;

????AABB * ?MidItr? = ?stable_partition(BeginItr,EndItr,IsUpboundSmaller);

????Cl? = ?MidItr? - ?BeginItr;
????Cr? = ?EndItr? - ?MidItr;

????cout << " Left?Voxel?has?:? " << Cl << " \tRight?Voxel?has?:? " << Cr << endl;

????AABB?Vl,Vr;

???? if ?(?Cr? > ? 128 ? || ?Cl? > ? 128 ?){
????????Root? = ? new ?KDNode;? // Root

????????Root -> Left? = ? new ?KDNode;
????????Root -> Right? = ? new ?KDNode;

????????Root -> tag.SplitPos? = ?::gSplitPos;
????????Root -> Count? = ?Axis; // Ulong.MaxSize?-?Axis?代表坐標?因為Left?Right肯定不是0
???????? switch (Axis){
???????????? case ?X?:
????????????????Vl.min[ 0 ]? = ?V.min[ 0 ];
????????????????Vl.min[ 1 ]? = ?V.min[ 1 ];
????????????????Vl.min[ 2 ]? = ?V.min[ 2 ];
????????????????Vl.max[ 0 ]? = ?::gSplitPos;
????????????????Vl.max[ 1 ]? = ?V.max[ 1 ];
????????????????Vl.max[ 2 ]? = ?V.max[ 2 ];

????????????????Vr.min[ 0 ]? = ?::gSplitPos;
????????????????Vr.min[ 1 ]? = ?V.min[ 1 ];
????????????????Vr.min[ 2 ]? = ?V.min[ 2 ];
????????????????Vr.max[ 0 ]? = ?V.max[ 0 ];
????????????????Vr.max[ 1 ]? = ?V.max[ 1 ];
????????????????Vr.max[ 2 ]? = ?V.max[ 2 ];
???????????????? break ;
???????????? case ?Y?:
????????????????Vl.min[ 0 ]? = ?V.min[ 0 ];
????????????????Vl.min[ 1 ]? = ?V.min[ 1 ];
????????????????Vl.min[ 2 ]? = ?V.min[ 2 ];
????????????????Vl.max[ 0 ]? = ?V.max[ 0 ];
????????????????Vl.max[ 1 ]? = ?::gSplitPos;
????????????????Vl.max[ 2 ]? = ?V.max[ 2 ];

????????????????Vr.min[ 0 ]? = ?V.min[ 0 ];
????????????????Vr.min[ 1 ]? = ?::gSplitPos;
????????????????Vr.min[ 2 ]? = ?V.min[ 2 ];
????????????????Vr.max[ 0 ]? = ?V.max[ 0 ];
????????????????Vr.max[ 1 ]? = ?V.max[ 1 ];
????????????????Vr.max[ 2 ]? = ?V.max[ 2 ];
???????????????? break ;
???????????? case ?Z?:
????????????????Vl.min[ 0 ]? = ?V.min[ 0 ];
????????????????Vl.min[ 1 ]? = ?V.min[ 1 ];
????????????????Vl.min[ 2 ]? = ?V.min[ 2 ];
????????????????Vl.max[ 0 ]? = ?V.max[ 0 ];
????????????????Vl.max[ 1 ]? = ?V.max[ 1 ];
????????????????Vl.max[ 2 ]? = ?::gSplitPos;

????????????????Vr.min[ 0 ]? = ?V.min[ 0 ];
????????????????Vr.min[ 1 ]? = ?V.min[ 1 ];
????????????????Vr.min[ 2 ]? = ?::gSplitPos;
????????????????Vr.max[ 0 ]? = ?V.max[ 0 ];
????????????????Vr.max[ 1 ]? = ?V.max[ 1 ];
????????????????Vr.max[ 2 ]? = ?V.max[ 2 ];
???????????????? break ;
????????}
????} else {
????????Root? = ? new ?KDNode;? // Leaf
????????Root -> Left? = ? 0 ;Root -> Right? = ? 0 ;
????????Root -> tag.AbsoluteOffset? = ?BeginItr? - ?::gScenePtr;
????????Root -> Count? = ?EndItr? - ?BeginItr;
??????? //cout << " Leaf?LEVEL?:? " << Level << " \tCount?:? " << Root -> Count << endl;
???????? return ;
????}
???? ++ Level;
????KDTreeBuild(Root -> Left,Vl,BeginItr,MidItr,Axis,Level);
????KDTreeBuild(Root -> Right,Vr,MidItr,EndItr,Axis,Level);
};

??? 這樣，我們就得到了一顆完整的基于SAH的KD樹。下面就是遍歷。

　　由于不同渲染要求的不同，遍歷代碼也大不相同。不過我們可以知道，kD樹及適用于光線跟蹤程序。目前在多款開源光線跟蹤器，比如blender就采用了kD樹作為加速結構。而且必須要提到的是，如果希望在Realtime Rendering的程序中使用光線跟蹤技術 —— 雖然說在目前的情況下還不是很現實，不過這畢竟是個趨勢，因為只有光線跟蹤才能夠精確的模擬物理全局光照，光柵化系統先天限制無法達到，雖然說Voxel渲染是一個折中的辦法。我引用下面的這張表格[3]作為性能參照。

　　可是這里又會出現一個問題，就是在實時渲染程序中如何處理多紋理貼圖？我們必須要模擬管線的處理過程。

A、如果場景中有運動的模型，標記出來

B、在世界坐標系統中對運動模型作矩陣變換，類似于OpenGL的MATRIX操作

C、把所有，各就各位的模型頂點、向量、紋理坐標、索引整合在一起。每當在這個鏈表中加入新的模型的時候，都要把現在模型的所有索引加上鏈表中已經加入的所有頂點的數目，構建一個好像是整體連續的單個模型。同時標記紋理，應該儲存一個頂點偏移量以及三角形數目，用來標示這個紋理屬于哪個模型。

D、根據視點，遍歷kD樹，把符合條件的三角形數目放入一個全局隊列

E、渲染隊列中的所有三角形，作為一個Frame。重復A。

　　目前由德國薩爾大學計算機科學系所開發的實時光線跟蹤硬件與軟件已經成功的問世，最令人振奮的莫過于表現了一個全部由光線跟蹤引擎實現的Quake3游戲。有興趣的朋友可以去[4]看看。

[1]Computer Graphics WS05/06 – kD-Tree and Optimization for Ray Tracing
[2]Lib3ds http://lib3ds.sf.net/
[3]Fast kd-tree Construction with an Adaptive Error-Bounded Heuristic

[4]OpenRT http://www.openrt.de/

posted on 2007-02-15 22:31 周波閱讀(3543) 評論(2) 編輯收藏引用所屬分類: Cg藝術、無庸技術

FeedBack:

# re: 利用SAH實現kD樹快速分割模型實踐

2007-02-16 14:59 | AIBPXTSHMF

bobo，這幾天研究kd樹的結果吧回復更多評論

# re: 利用SAH實現kD樹快速分割模型實踐

2007-09-03 09:14 | freesky

很精彩，不過資料再多點就好了回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: Pure GPU Computing Platform : NVIDIA CUDA Tutorial 利用SAH實現kD樹快速分割模型實踐 Progressive Mesh 矩陣圣經 FOR 3D Computer Graphic Final BattleField 2142引擎圖形程序員小訪談 GPU還可以做什么 —— Brook for GPUs,Stream Computing On GPUs

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理