3D遊戲引擎入門課程2——場景管理

寫在前面#

本專欄內容均為學堂在線慕課《3D 遊戲引擎架構設計基礎》中的內容。個人將其轉化成文字和圖片的版本（個人更加喜歡文字版本的教程，閱讀速度更快很多），方便查閱。
原課程鏈接：3D 遊戲引擎架構設計基礎。

場景管理#

場景管理概述與 BVH#

為了提高場景管理的效率，場景對象的邏輯組織架構通常是樹型的結構。舉例：

在這裡插入圖片描述

遊戲場景組織的架構包括：

場景圖，多用於管理動態場景。
八叉樹，多用於管理大型室外場景。
二叉空間分割，即 BSP 樹，多用於管理室內場景。

BVH（Bouding Volume Hierarchies）包圍體層次結構，用於快速判斷場景對象之間的幾何位置關係，其通過 BVH 方法為每個對象計算包圍體。BVH 就是節點有包圍體信息的樹狀結構。舉例：
在這裡插入圖片描述

其中包圍體類型又包括：包圍球，軸平行包圍體，有向包圍體，k - 離散有向多面體。其計算複雜度是逐漸上升的。其中計算方法如下圖所示：

在這裡插入圖片描述

場景組織結構：場景樹，八叉樹和 BSP 樹#

場景樹#

用層次結構表示場景中的對象
上層對象的操作影響其所有子樹的對象
有向無環圖

場景圖的抽象描述如下：

在這裡插入圖片描述

八叉樹#

將空間分成八等份，如果被分的部分填滿了場景內容，或被分的部分沒有場景內容，則不再分割；否則，繼續分割，直到滿足終止條件。

八叉樹的組織：

在這裡插入圖片描述

其缺點是葉子節點的指針空間都為空，浪費很多空間。其中一種改進的做法是：

在這裡插入圖片描述
線性八叉樹節省了儲存空間，場景運算也非常簡便。

八叉樹分割算法：
在這裡插入圖片描述

其中可以通過計算分割的立方體與幾何包圍體的包含關係來確定幾何體與場景的幾何關係是 F（Full）還是 E（Empty）。遞歸的分割算法實現非常簡潔快速。

八叉樹的構建思想決定了場景的有序性，當鏡頭位置和方向確定後，場景的遍歷順序就可以確定。八叉樹的遍歷方式可以從後向前遍歷，或是從前向後遍歷。其中前者被也稱為畫家算法，這種方式不需要計算遮擋關係，但是需要渲染每一個面，效率很低。後者是最近的面先渲染，再通過遮擋關係或深度緩存信息，決定像素的最終渲染結果。這種方法深度緩存需要在像空間執行，但是減少了很多渲染計算，效率較高。

八叉樹的優點如下：
在這裡插入圖片描述

BSP 樹#

是用空間超平面，遞歸地將空間分割為凸多面體集，用二叉樹表示被分割的空間。

其中凸多面體的定義為：由若干平面多邊形所圈成的封閉的立體叫做多面體，這些平面多邊形稱為多面體的面，這些多邊形的邊和頂點分別稱為多面體的棱和頂點。如果多面體在它們每一面所決定的平面的同一側，則稱此多面體為凸多面體，或歐拉多面體。凸多面體的任何截面都是凸多邊形，與凹多面體相反。

其分割思想為：
在這裡插入圖片描述
其構建算法為：

其中幾個幾何問題算法包括：

如何判斷凸多面體：
如何判斷兩個面片的幾何位置關係：
判斷面片與頂點的幾何位置關係：

解決了上述幾個幾何問題，繼續討論 BSP 樹的構建。另外一個問題是，如何確定分割的超平面，選擇步驟為：

在這裡插入圖片描述

剔除凸包面
計算 NF、NB、NS
選擇分割空間的超平面

最後是 BSP 樹完整的構建算法：

BSP 樹的遍歷算法（畫家算法）：

可以通過從前往後遍歷，通過深度緩存進行計算進行優化。
BSP 樹的應用：

最後對幾種算法進行對比：

場景管理實例#

OGRE 場景管理#

OGRE 中場景類型分為：靜態、動態、擴展的：

靜態型：非常龐大、向四周不規則蔓延的、不可移動的、由三角形網格組成的物，包括地形、天空盒等，有以下的表示：SkyPlane, Skybox, SkyDome (SceneNode *)；World geometry, 通常是一個確定的 SceneManager；Static geometry，通常 SceneManager 的樹結構是確定的，如室內場景。
動態性：可在場景中移動的、離散的、相對較小的物體，主要包括實體（Entity）、粒子、攝像機等，用 SceneNode 類和 MovableObject 類表示。
擴展型：主要包括 BSPSceneNode, OctreeNode, PCZSceneNode 等。

OGRE 場景管理部分類圖：
在這裡插入圖片描述
其中的主要類描述：

SceneManger（場景管理單例）主要功能圖：
OGRE 創建場景對象示例：