《一周學習光線追蹤》（二）層次包圍盒BVH

來自專欄 從光柵到光線追蹤

上一章：一周學習光線追蹤》（一）序言及動態模糊

第二章：層次包圍盒 （Bounding Volume Hierarchies）

這部分是目前渲染器中最困難的部分，但是可以是渲染器更加高效，所以我們需要花上一點時間去重構之前的代碼。

尋找射線與物體的交點是渲染器主要耗時的地方之一，而且時間消耗隨著場景內物體的數量遞增。

我們要做的是使用二分法對場景內的物體進行搜索，而不是遍歷所有物體。

舉個例子：如果我們在世界地圖上隨機選一個點，查找距離最近的城市，我們會首先查找這個點在哪個大洲，然後是哪個國家，再然後是哪個省，最後選中距離點最近的城市。而不是遍歷世界上所有的城市來查找。

在渲染器中，我們會將數個物體放進一個盒子（Bounding Volume）內，如果射線沒有碰到這個盒子，那麼也就肯定碰不到盒子內的物體。但是值得注意的是盒子是可以重疊的。

當然，盒子內也可以放其他的盒子，這樣我們會得到一個樹形結構。

在上面的圖中，藍色盒子和紅色盒子都在紫色盒子裡面，並且他們發生了重疊。物體在盒子內並不是按照某種順序排列的，他們只是在裡面。所有這個樹狀結構也沒有左子樹右子樹的說法。

偽碼會是這樣

如果（射線碰到紫色盒子） hit0 = 碰撞 藍色盒子內的物體 hit1 = 碰撞 紅色盒子內的物體 如果 （hit0 或 hit1） 返回 真，和被撞擊的物體的信息 反之 返回 假

為了實現這個機制，我們需要一個高效的方法將空間分割為不同的盒子。

我們這裡採用軸對齊包圍盒（AABB盒)

AABB盒是一個簡單的3D的六面體，每一邊都平行於一個坐標平面，矩形邊界框不一定是正方體，它的長、寬、高可以彼此不同。

一般使用「平板(slab)」方法。 這是基於n維觀察的方法。

AABB只是n軸對齊的區間的交集，通常稱為「平板」。

間隔就是兩個端點之間的點，例如x，使得3 <x <5，或者更簡潔地:

x in（3,5）

在2D空間中中，兩個區間重疊產生2D AABB盒（矩形）：

如果想要判定射線是否與這個矩形相交，我們首先要確定射線對於矩形邊界的位置。

例如，這裡有個射線，參數是t0,t1

2D包圍盒的邊界是一條線，而3D包圍盒的邊界是一個面。

回顧之前的內容，射線可以看為是一個方程

t 的撞擊點是

我們可以得到一個類似的公式：

接下來我們要將這個公式實際應用。

例如，下面的2D空間中，綠色和藍色只有在第二條射線時發生重疊。

用偽碼來描述「在板中的t間隔是否重疊」是這樣的：

計算 (tx0, tx1)計算 (ty0, ty1)返回 重疊 ? ( (tx0, tx1), (ty0, ty1) )

這很簡單，而且套用在3D空間同樣簡單

計算 (tx0, tx1)計算 (ty0, ty1)計算 (tz0, tz1)返回 重疊 ? ( (tx0, tx1), (ty0, ty1), (tz0, tz1))

這個方法還是有一些問題的，

比如如果射線的是負方向，可能會造成結果翻轉。

而且這個方法在進行除法時可能會出現除數為0，這時就會出現NaN的結果。

我們這裡不會討論 SIMD （單指令多數據流），但是如果你想更深入的話，Ingo Wald 的論文是一個很好的開始。我們先不必討論這個。

tx0 = (x0 - Ax) / Bxtx1 = (x1 - Ax) / Bx

一件令人頭疼的事情是，存在具有Bx = 0的完全有效的射線，會導致除零出現NaN。

這樣的射線有的是在平板內的，有些不在，而且這個0會帶正負號。

在IEEE浮點標準下，在Bx=0時，t0和t1會都是 正無窮或者負無窮，反正不是x0和x1之間的數字，所以我們可以通過設置最大最小值來解決這個問題。

tx0 = min((x0 - Ax) / Bx, (x1 - Ax) / Bx);tx1 = max((x0 - Ax) / Bx, (x1 - Ax) / Bx

剩下的問題的是如果 Bx =0 而且 x0-Ax或x1-Ax也等於零，那麼我們依然會得到NaN。

在這種情況下，我們可以返回不命中作為結果

現在我們可以寫出檢測重疊的函數了，假定我們的射線不會顛倒，也就是說區間內第一個值小於第二個值。

bool overlap(d, D, e, E, f, F) f = max(d, e) F = min(D, E) return (f < F)

如果運算結果是NaN，我們的演算法會返回false

接下來我們開始編寫正式的代碼:

值得注意的是，接下來會出現Vecter3對象的索引器操作，這需要們重寫一下Vector3的代碼

對於索引器的操作：索引 值為0返回x,值為1返回y，值為2返回z。這麼寫的原因是方便後面的運算。

public class Vector3 { public float[] data=new float[3]; public float x {get => data[0];set => data[0] = value;} public float y {get => data[1];set => data[1] = value;} public float z {get => data[2];set => data[2] = value;} public float this[int index] { get => data[index]; set => data[index] = value; } public Vector3(float x, float y, float z) { this.x = x; this.y = y; this.z = z; } //...省略其他代碼...// }

首先創建AABB包圍盒的類

public class AABB { private Vector3 min, max; public AABB(Vector3 a, Vector3 b) { min = a; max=b; } public bool Hit(Ray r, float tmin, float tmax) { for (var a = 0; a < 3; a++) { var t0 = Mathf.Min((min[a] - r.original[a]) / r.direction[a], (max[a] - r.original[a]) / r.direction[a]); var t1 = Mathf.Max((min[a] - r.original[a]) / r.direction[a], (max[a] - r.original[a]) / r.direction[a]); tmin = Mathf.Max(t0, tmin); tmax = Mathf.Min(t1, tmax); if (tmax <= tmin) return false; } return true; } }

我們還需要一個函數生成物體的包圍盒，這個函數在不同物體上重載

首先修改基類

public abstract class Hitable { public abstract bool Hit(Ray ray, float t_min, float t_max, ref HitRecord rec); public abstract bool BoundingBox(float t0, float t1,ref AABB box); }

然後修改Sphere類重寫BoundingBox函數

//Class Sphere public override bool BoundingBox(float t0, float t1, ref AABB box) { box=new AABB(center-new Vector3(radius,radius,radius),center+new Vector3(radius,radius,radius)); return true; }

對於 MovingSphere類，我們可以將t0時的盒子和t1時的盒子放進一個大盒子里

//Class MovingSphere public override bool BoundingBox(float t0, float t1, ref AABB box) { box = GetBox( new AABB(Center(t0) - new Vector3(radius, radius, radius), Center(t0) + new Vector3(radius, radius, radius)), new AABB(Center(t1) - new Vector3(radius, radius, radius), Center(t1) + new Vector3(radius, radius, radius))); return true; } // Class Hitable public AABB GetBox(AABB box0,AABB box1) { var small=new Vector3( Mathf.Min(box0.min.x,box1.min.x), Mathf.Min(box0.min.y, box1.min.y), Mathf.Min(box0.min.z, box1.min.z)); var big = new Vector3( Mathf.Max(box0.max.x, box1.max.x), Mathf.Max(box0.max.y, box1.max.y), Mathf.Max(box0.max.z, box1.max.z)); return new AABB(small,big); }

對於HitableList類

你可以在構造函數直接儲存盒子，也可以在運行時計算，我們這裡使用運行時計算，因為這一般只在BVH構造函數的時候調用。

//Class HitableList public override bool BoundingBox(float t0, float t1, ref AABB box) { if (list.Count == 0) return false; var tempBox=new AABB(); if (!list[0].BoundingBox(t0, t1, ref tempBox)) return false; box = tempBox; foreach (var t in list) { if (t.BoundingBox(t0, t1, ref tempBox)) box = GetBox(box, tempBox); else return false; } return true; }

一個BVH節點也要寫成一個hitable的子類，因為它作為一個容器，其實也是一個在渲染空間中的物體。

public class BVHNode : Hitable { public Hitable left, right; public AABB box; public BVHNode() { } public BVHNode(Hitable[] p, int n, float time0, float time1) { //用來排序的嵌套函數。 int Compare(Hitable a, Hitable b, int i) { AABB l = new AABB(), r = new AABB(); if (!a.BoundingBox(0, 0, ref l) || !b.BoundingBox(0, 0, ref r)) throw new Exception("NULL"); return l.min[i] - r.min[i] < 0 ? -1 : 1; } //用來排序的分割數組的嵌套函數。 Hitable[] SplitArray(Hitable[] Source, int StartIndex, int EndIndex) { var result = new Hitable[EndIndex - StartIndex + 1]; for (var i = 0; i <= EndIndex - StartIndex; i++) result[i] = Source[i + StartIndex]; return result; } //隨機一個軸。 x軸:0 y軸:1 z軸:3 var method = (int) (3 * Mathematics.Random.Get()); //轉換為List然後使用排序,最後再轉換會Array //排序規則使用lambda表達式轉向比較函數，並加入軸向參數 var temp_list = p.ToList(); temp_list.Sort((a, b) => Compare(a, b, method)); p = temp_list.ToArray(); //檢測當前子節點數量，如果大於2則繼續分割。 switch (n) { case 1: left = right = p[0]; break; case 2: left = p[0]; right = p[1]; break; default: //拆分 left = new BVHNode(SplitArray(p,0,n/2-1), n / 2, time0, time1); right = new BVHNode(SplitArray(p, n / 2, n - 1), n - n / 2, time0, time1); break; } //根據子節點生成當前節點的包圍盒 AABB box_left = new AABB(), box_right = new AABB(); if (!left.BoundingBox(time0, time1, ref box_left) || !right.BoundingBox(time0, time1, ref box_right)) throw new Exception("no bounding box in bvh_node constructor"); box = GetBox(box_left, box_right); } public override bool BoundingBox(float t0, float t1, ref AABB b) { b = box; return true; } public override bool Hit(Ray ray, float t_min, float t_max, ref HitRecord rec) { //檢測包圍和碰撞，返回碰撞的子樹的信息 if (box.Hit(ray, t_min, t_max)) { HitRecord left_rec=new HitRecord(),right_rec=new HitRecord(); var hit_left = left.Hit(ray, t_min, t_max, ref left_rec); var hit_right = right.Hit(ray, t_min, t_max, ref right_rec); if (hit_left && hit_right) { rec = left_rec.t < right_rec.t ? left_rec : right_rec; return true; } if (hit_left) { rec = left_rec; return true; } if (hit_right) { rec = right_rec; return true; } return false; } return false; }}

這裡的左右節點都是基類Hitable類型，這樣BVH的子節點也有可能是另一個BVH節點或者是一個物體，如果是BVH的話就繼續檢測其子節點。

任何效率結構中最複雜的部分就是構建這個結構。關於BVH的一個很酷的事情是，只要BVH節點中的對象列表被分成兩個子列表，命中檢測就可以工作。如果合適分隔，這將最高效，為了生成一個盡量小的，包含所有對象的盒子，我們讓每個節點沿一個軸分割列表：

1. 隨機選擇一個軸
2. 將節點內的對象進行排序
3. 左右子樹各放一半

這樣我們的BVH就寫完了，我們可以先將數個物體添加到一個 Hitable[] 數組裡然後創建一個包圍盒子：

world.list.Add(new BVHNode(list,list.Length,0,1));

這樣可以有效地提高物體的查找效率。