用C++畫光（三）：四叉樹

相關文章目錄

用C++畫光（一）：基礎和反射

用C++畫光（二）：折射和色散

用C++畫光（三）：四叉樹

用C++畫光（四）：更好的色散

這次主要引入了更多的Entity並使用四叉樹管理場景。

好像隔了很久。最近加班比較忙。

在實際的光線追蹤計算中，以及在遊戲3D場景管理和碰撞檢測中，用八叉樹來管理場景模型是一種常用的方法。而在2D情況下，則可以使用四叉樹類似的進行Entity的管理。

在前面的例子中，計算從某個點p方向為d的光線是否與場景中的Entity相交，是遍歷了所有Entity判斷是否相交並取最近的交點，因此，當畫布上的Entity越來越多，遍歷的成本也線性增加。引入四叉樹，正是為了減少這種消耗。

以一個簡單的三個圓形Entity的場景為例

對其進行四叉樹劃分。首先將整個畫布作為根節點，並將其劃分為四個子節點LU（左上），LD（左下），RU（右上），RD（右下），以此類推，遞歸劃分子節點。而對場景中的每個物體，可掛在包含該物體的最小子節點上。如下圖所示。灰色的節點表示其中沒有場景物體。可在建樹的過程中就預先剔除，減少遍歷樹的消耗。

這樣，就將場景中的Entity全都掛在了樹上。

四叉樹節點的結構為：

template<typename T> class QuadNode{ float m_left, m_right, m_up, m_down; list<T*> m_dataList; QuadNode* m_child[4] = { NULL, NULL, NULL, NULL }; //0:LeftUp, 1:LeftDown, 2:RightUp, 3:RightDown ... //遞歸生成四叉樹節點 void GenerateNode() //判斷射線與四叉樹節點包圍盒本身是否相交，用於剪枝 bool IntersectBound(Point p, Vector d) //返回該射線相交的最近entity和距離 bool Intersect(Point p, Vector d, T* &ent_near, Point& inter, float& dist)};

此時，對所有Entity的遍歷就變為了對四叉樹的遍歷（訪問每個四叉樹節點時遍歷掛在節點上的所有Entity）

但此時消耗並沒有減少，因為依舊要遍歷所有的Entity。甚至增加了建樹和遍歷四叉樹本身的消耗。

為此，需要對這棵樹進行剪枝。

剪枝

所謂剪枝，就是將不可能與射線相交的節點提前剔除。以此減少相應的遍歷消耗。

很容易想到，如果從p點出發的光線沒有與節點本身的包圍盒相交，那麼必然不會與節點內包含的Entity相交，這樣就可以將該節點提前剪掉（包括該節點上的子節點）

首先，進行一次預判斷，根據p與四叉樹節點包圍盒的相對位置和d的方向，可以預過濾一大批不相交的情況。下圖即是在各個位置的採樣點p與節點包圍盒相交的方向向量d必須滿足的條件。

當然，這僅僅是必要條件而不是充分條件。（剪枝1）

然後判斷從p點出發方向為d的直線與包圍盒是否相交，可根據直線的方程計算。直線方程形如：

若直線與包圍盒相交，則必滿足

或者 （剪枝2）

還可以引入別的更多的剪枝思路。需要指出的是，剪枝操作越複雜，帶來的計算消耗就越多，因此剪枝計算並不是越多越好，而是希望以儘可能簡單的計算，剪掉儘可能多的節點。

對分布較均勻的場景Entity來說，進行了這樣的剪枝之後，每次光線求交可以減少一大部分的Entity遍歷和相交判斷。在下圖這個"特別均勻"的示例中，經過這樣剪枝後，與最初始的遍歷方法相比，總時間消耗減少了約59%（包括建樹和樹的遍歷增加的消耗（約31%））。

其它補充

關於在平面上如何生成多個不相交的圓，也是一個很有趣的問題。具體可以看 @葉飛影 老闆的這個回答

葉飛影：如何生成多個互不重疊的不同半徑圓？

本文採取的方法比較簡單，包括

1. 暴力生成：每次隨機生成一個圓，如果跟前面隨機到的圓相交了，就重新隨機一個
2. 先分割後隨機：在一個包圍盒內部隨機一個圓，保證不會超出包圍盒的邊界

引入四叉樹能提高場景Entity遍歷的效率，但這也有一個條件：Entity在場景中分布的比較均勻。如果都集中在畫布的某一個角落，那麼使用四叉樹來處理這個問題，並不會有效率上的提升，反而徒增消耗。這時，可以考慮引入k-d tree對場景Entity進行比較均勻的劃分。此處不再額外介紹。

結果示例

代碼見 lilypuye/cppLight2d

破乎又壓我圖。傷心。越是畫的時間長的，越是顏值下降的厲害。

歡迎探討各種問題和想法

但不是很擅長回答如何在vs中創建一個工程等問題

推薦閱讀：