3Dゲームエンジン入門コース2——シーン管理

前書き#

本コラムの内容は、学堂オンライン MOOC「3D ゲームエンジンアーキテクチャ設計基礎」の内容です。個人的に文字と画像のバージョンに変換しました（個人的には文字バージョンのチュートリアルが好きで、読む速度がかなり速いです）、参照しやすくするためです。
元のコースリンク：3D ゲームエンジンアーキテクチャ設計基礎。

シーン管理#

シーン管理の概要と BVH#

シーン管理の効率を向上させるために、シーンオブジェクトの論理的な組織構造は通常ツリー構造です。例：

ここに画像の説明を挿入

ゲームシーンの組織構造には以下が含まれます：

シーングラフ、主に動的シーンの管理に使用されます。
オクツリー、主に大規模な屋外シーンの管理に使用されます。
バイナリ空間分割、すなわち BSP ツリー、主に屋内シーンの管理に使用されます。

BVH（バウンディングボリュームヒエラルキー）は、シーンオブジェクト間の幾何的位置関係を迅速に判断するために使用され、BVH メソッドを通じて各オブジェクトのバウンディングボリュームを計算します。BVH は、ノードにバウンディングボリューム情報を持つツリー構造です。例：
ここに画像の説明を挿入

バウンディングボリュームのタイプには、バウンディングスフィア、軸平行バウンディングボリューム、有向バウンディングボリューム、k - 離散有向多面体が含まれます。その計算の複雑さは徐々に上昇します。計算方法は以下の図に示されています：

ここに画像の説明を挿入

シーンの組織構造：シーンツリー、オクツリー、BSP ツリー#

シーンツリー#

階層構造でシーン内のオブジェクトを表現します
上位オブジェクトの操作は、そのすべての子ツリーのオブジェクトに影響を与えます
有向非巡回グラフ

シーングラフの抽象的な説明は以下の通りです：

ここに画像の説明を挿入

オクツリー#

空間を 8 等分し、分割された部分がシーン内容で満たされている場合、または分割された部分にシーン内容がない場合は、分割を行わない；それ以外の場合は、終了条件を満たすまで分割を続けます。

オクツリーの組織：

ここに画像の説明を挿入

その欠点は、葉ノードのポインタ空間がすべて空で、多くの空間を無駄にすることです。改善策の一つは：

ここに画像の説明を挿入
線形オクツリーはストレージスペースを節約し、シーン計算も非常に簡単です。

オクツリー分割アルゴリズム：
ここに画像の説明を挿入

ここでは、分割された立方体と幾何バウンディングボリュームの包含関係を計算することで、幾何体とシーンの幾何関係が F（Full）か E（Empty）かを判断できます。再帰的な分割アルゴリズムの実装は非常にシンプルで迅速です。

オクツリーの構築思想は、シーンの順序性を決定します。カメラの位置と方向が決まると、シーンの走査順序も決まります。オクツリーの走査方法は、後ろから前に走査するか、前から後ろに走査することができます。前者は画家アルゴリズムとも呼ばれ、この方法では遮蔽関係を計算する必要はありませんが、各面をレンダリングする必要があり、効率は非常に低いです。後者は最近の面を先にレンダリングし、遮蔽関係や深度キャッシュ情報を通じてピクセルの最終レンダリング結果を決定します。この方法では深度キャッシュが空間で実行される必要がありますが、多くのレンダリング計算を減少させ、効率が高くなります。

オクツリーの利点は以下の通りです：
ここに画像の説明を挿入

BSP ツリー#

空間の超平面を使用して、空間を凸多面体の集合に再帰的に分割し、分割された空間をバイナリツリーで表現します。

凸多面体の定義は：いくつかの平面多角形によって囲まれた閉じた立体を多面体と呼び、これらの平面多角形は多面体の面と呼ばれ、これらの多角形の辺と頂点はそれぞれ多面体のエッジと頂点と呼ばれます。多面体がそれぞれの面によって決定された平面の同じ側にある場合、この多面体は凸多面体またはオイラー多面体と呼ばれます。凸多面体の任意の断面は凸多角形であり、凹多面体とは対照的です。

その分割思想は：
ここに画像の説明を挿入
その構築アルゴリズムは：

ここでいくつかの幾何問題アルゴリズムには以下が含まれます：

凸多面体を判断する方法：
2 つの面片の幾何的位置関係を判断する方法：
面片と頂点の幾何的位置関係を判断する方法：

上記の幾何問題を解決した後、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 でのシーンオブジェクト作成の例：

OSG シーン管理#

OSG のシーン管理の主なモジュール：ここに画像の説明を挿入
OSG シーン関係クラス図：

以下は OSG シーン管理のいくつかのコアクラス：

OSG シーン管理の設計分析：

Panda3D シーン管理#

Panda3D シーン管理の概念：

シーングラフには共通の基底クラス（PandaNode 抽象クラス）があり、すべてのシーンノードクラスを派生させます；
シーングラフの任意のノードは 1 つ以上の親ノードを持つことができ、シーングラフは有向非巡回構造です；
派生した幾何ノードクラスはシーングラフの葉ノードであり、レンダリング可能なノードです；
NodePath クラスはシーングラフを管理するインターフェースクラスであり、シーンノードを操作し、ルートからアクセスノードへのパスを取得するなどの機能を持ちます。