Loading article…
シーングラフは、ベクターベースのグラフィック編集アプリケーションや最新のコンピュータゲームで一般的に使用される階層型データ構造であり、オブジェクトのセットの継承または空間表現を階層化します。これは、グラフまたはツリー構造のノードの集合です。ツリーノードは多くの子を持つことができますが、親は1つだけであり、親の効果はすべての子ノードに適用されます。グループに対して実行された操作は、その効果を自動的にすべてのメンバーに伝播します。多くのプログラムでは、各グループレベルで幾何学的変換行列（変換と行列も参照）を関連付け、そのような行列を連結することが、このような操作を処理する効率的で自然な方法です。たとえば、関連する形状やオブジェクトを複合オブジェクトにグループ化し、単一のオブジェクトと同じように簡単に操作できる機能は、一般的な機能です。
ベクターベースのグラフィック編集では、シーングラフの各リーフノードは、ドキュメントの最小単位、通常は楕円やベジェパスなどの形状を表します。形状自体（特にパス）は、スプラインノードなどのノードにさらに分解できますが、シーングラフは形状で構成されていると考える方が、より低いレベルの表現に移行するよりも実用的です。
もう一つ、ユーザー主導で利用できる便利なノード概念として「レイヤー」があります。レイヤーは透明なシートのように機能し、その上に任意の数の図形や図形グループを配置できます。ドキュメントはレイヤーの集合となり、各レイヤーは簡単に非表示、暗くしたり、ロック（読み取り専用）したりできます。アプリケーションによっては、すべてのレイヤーを線形リストに配置するものもあれば、任意の深さまでレイヤーの中にレイヤーを配置できるものもあります。
内部的には、レイヤーとグループはどちらもシーングラフのノードに過ぎないため、構造的に大きな違いはないかもしれません。違いが必要な場合は、C++では一般的な型宣言として、汎用ノードクラスを作成し、そのサブクラスとしてレイヤーとグループを派生させる方法が考えられます。例えば、可視性メンバーはレイヤーの機能ではありますが、グループの機能であるとは限りません。
シーングラフは、 3Dグラフィックスを使用し、ますます大規模化するワールドやレベルを持つ現代のゲームにおいて有用です。このようなアプリケーションでは、シーングラフのノードは（一般的に）シーン内のエンティティまたはオブジェクトを表します。
例えば、ゲームでは騎士と馬の間に論理的な関係を定義し、騎士を馬の延長線上の存在とみなすことがある。シーングラフには「馬」ノードがあり、それに「騎士」ノードが接続される。
シーングラフは、さまざまなエンティティ間の空間的な関係と論理的な関係の両方を記述することもできます。例えば、騎士は馬の動きに合わせて3D空間を移動します。
こうした大規模アプリケーションでは、シーングラフの設計においてメモリ要件が重要な考慮事項となります。そのため、多くの大規模シーングラフシステムでは、メモリコストを削減し処理速度を向上させるためにジオメトリインスタンス化が用いられています。上記の例では、各騎士は個別のシーンノードですが、騎士のグラフィック表現（3Dメッシュ、テクスチャ、マテリアル、シェーダーで構成）はインスタンス化されています。つまり、データのコピーは1つだけ保持され、シーングラフ内のどの「騎士」ノードからも参照されます。これにより、新しい騎士ノードが作成される際に外観データを複製する必要がなくなるため、メモリ使用量を削減し、処理速度を向上させることができます。
シーングラフの最もシンプルな形式は、配列またはリンクリストのデータ構造を使用し、その形状を表示するには、ノードを1つずつ線形に反復するだけで済みます。マウスカーソルと交差する形状をチェックするなど、その他の一般的な操作も線形探索によって行われます。小規模なシーングラフであれば、これで十分でしょう。
シーングラフに操作を適用するには、ノードのタイプに基づいて操作をディスパッチする方法が必要です。たとえば、レンダリング操作では、変換グループノードは、行列乗算、ベクトル変位、クォータニオン、またはオイラー角によって変換を蓄積します。その後、リーフノードがレンダリングのためにオブジェクトをレンダラーに送信します。一部の実装では、 DirectXやOpenGLなどの基盤となるレンダリングAPIを呼び出すことで、オブジェクトを直接レンダリングする場合があります。しかし、レンダリングAPIの基盤となる実装は通常移植性に欠けるため、シーングラフとレンダリングシステムを分離する方が望ましいでしょう。このようなディスパッチを実現するには、いくつかの異なるアプローチが考えられます。
C++のようなオブジェクト指向言語では、仮想関数を用いることでこれを容易に実現できます。仮想関数は、ノードに対して実行可能な操作を表します。仮想関数は簡単に記述できますが、ソースコードにアクセスできないと、ノードに新しい操作を追加することは通常不可能です。あるいは、ビジターパターンを使用することもできます。ただし、このパターンにも同様の欠点があり、新しいノードタイプを追加するのが同様に困難です。
その他の手法としては、RTTI（ランタイム型情報）を利用する方法があります。この操作は、現在のノードに渡されるクラスとして実現できます。クラスはRTTIを使用してノードの型を照会し、コールバックまたはファンクタの配列から適切な操作を検索します。この方法では、型とコールバックまたはファンクタのマッピングをランタイム時に初期化する必要がありますが、柔軟性、速度、拡張性に優れています。
これらの手法には様々なバリエーションが存在し、新しい手法によってさらなる利点が得られる場合もあります。その一つがシーングラフの再構築です。これは、実行される各操作ごとにシーングラフを再構築する手法です。ただし、この方法は非常に時間がかかる場合がありますが、高度に最適化されたシーングラフが生成されます。これは、優れたシーングラフの実装が、それが使用されるアプリケーションに大きく依存することを示しています。
シーングラフに操作を適用する際の鍵となるのが、トラバーサルです。トラバーサルは一般的に、任意のノード（多くの場合、シーングラフのルート）から開始し、操作（多くの場合、更新操作とレンダリング操作が連続して適用されます）を適用し、シーングラフ（ツリー）を再帰的に下へ移動して子ノードに到達し、リーフノードに到達するまで続きます。この時点で、多くのシーングラフエンジンはツリーを上へ戻り、同様の操作を適用します。たとえば、変換を考慮したレンダリング操作を考えてみましょう。シーングラフ階層を再帰的に下へ移動する際に、プリレンダリング操作が呼び出されます。ノードが変換ノードの場合、現在の変換行列に自身の変換を追加します。操作がノードのすべての子ノードのトラバーサルを完了すると、変換ノードが変換を元に戻せるように、ノードのポストレンダリング操作が呼び出されます。このアプローチにより、必要な行列乗算の量が大幅に削減されます。
シーングラフの操作の中には、ノードを異なる順序で走査した方が効率的なものがあります。そのため、一部のシステムでは、シーングラフを再構築して、解析しやすい形式やツリー構造に並べ替える処理を実装しています。
例えば、2D の場合、シーン グラフは通常、ツリーのルート ノードから開始し、子ノードを再帰的に描画することでレンダリングされます。ツリーの葉は、最も前景にあるオブジェクトを表します。描画は奥から手前に進み、近いオブジェクトが遠いオブジェクトを上書きするため、このプロセスはペインター アルゴリズムを採用していると言われています。深度バッファを使用することが多い 3D システムでは、近いオブジェクトによって遮蔽されるため、遠いオブジェクトは実際にレンダリングするのではなく、深度テストのみで済むことが多いため、最も近いオブジェクトを最初に描画する方が効率的です。
バウンディングボリューム階層（BVH）は、効率的なカリングやオブジェクト間の衝突検出の高速化など、さまざまなタスクに役立ちます。BVHは空間構造ですが、ジオメトリを分割する必要はありません（空間分割については後述）。
BVHは、バウンディングボリューム（多くの場合、球体、軸に沿ったバウンディングボックス、または方向付けされたバウンディングボックス）のツリー構造です。階層の最下層では、ボリュームのサイズは単一のオブジェクトをぴったりと囲むのに十分な大きさです（高解像度BVHでは、オブジェクトのごく一部を囲む場合もあります）。階層を上に進むにつれて、各ノードは自身のボリュームを持ち、その下のすべてのボリュームをぴったりと囲みます。ツリーのルートには、ツリー内のすべてのボリューム（シーン全体）を囲むボリュームがあります。
BVHは、オブジェクト間の衝突検出を高速化するのに役立ちます。オブジェクトのバウンディングボリュームがツリーの上位にあるボリュームと交差しない場合、そのノードより下位のオブジェクトとも交差しないため、それらはすべて非常に迅速に拒否されます。
BVHとシーングラフにはいくつかの類似点があります。シーングラフは、各ノードにボリュームが関連付けられているか、階層構造内の適切な場所に専用の「バインドノード」が追加されている場合、簡単にBVHを組み込んだり、BVHにしたりできます。これは一般的なシーングラフの見方ではないかもしれませんが、シーングラフにBVHを含めることには利点があります。
空間分割とシーングラフを効果的に組み合わせる方法の一つは、空間分割データを含むシーンリーフノードを作成することです。これにより、レンダリングの計算効率を高めることができます。
空間データは通常静的であり、一般的には分割された形式で静止したシーンデータを含んでいます。システムによっては、システムとレンダリングが別々になっている場合もあります。これは問題なく、どちらの方法にも特に利点はありません。特に、シーングラフを空間分割システム内に含めるのは好ましくありません。シーングラフは、空間分割よりも上位のシステムとして捉える方が適切だからです。
非常に大きな図面、あるいは実行時にのみ生成されるシーングラフ（レイトレーシングレンダリングプログラムなどで発生する）では、グループノードをより自動化された方法で定義する必要があります。たとえば、レイトレーサーは3Dモデルのシーン記述を受け取り、その個々の部分を境界ボックス（境界スラブとも呼ばれる）に分割する内部表現を構築します。これらのボックスは階層的にグループ化されるため、（可視性判定の一部として）レイ交差テストを効率的に計算できます。たとえば、視線と交差しないグループボックスは、そのメンバーのテストを完全にスキップできます。
2Dアプリケーションでも同様の効率性が当てはまります。ユーザーがドキュメントを拡大してコンピュータ画面に一部だけが表示されるようにし、その上でスクロールする場合、バウンディングボックス（この場合はバウンディング矩形）を使用して、どのシーングラフ要素が表示され、実際に描画する必要があるかを素早く判断すると便利です。
アプリケーションの描画パフォーマンスの詳細によっては、シーングラフの設計の大部分がレンダリング効率の考慮事項によって影響を受ける可能性があります。Quake などの 3D ビデオゲームでは、可視性テストを最小限に抑えるためにバイナリ空間分割(BSP) ツリーが好まれています。しかし、BSP ツリーは設計シーングラフから計算するのに非常に時間がかかり、設計シーングラフが変更されると再計算する必要があるため、レベルは静的なままになりがちで、動的なキャラクターは一般的に空間分割スキームでは考慮されません。
ハイトフィールドやポリゴンメッシュなどの密な規則的なオブジェクトのシーングラフでは、3Dバウンディングボックス階層の特殊なバリアントであるクワッドツリーやオクツリーがよく使用されます。ハイトフィールド自体がボックスボリュームを占めるため、個々のハイトフィールド要素に到達するまでこのボックスを8つのサブボックス（オクツリーの「oct」の由来）に再帰的に分割していくのは効率的で自然な方法です。クワッドツリーは、2Dオクツリーに相当します。
PHIGSは最初の商用シーングラフ仕様であり、 1988年にANSI規格となった。Unixハードウェアベンダーによって様々な実装が提供された。HOOPS 3Dグラフィックスシステムは、単一のソフトウェアベンダーによって提供された最初の商用シーングラフライブラリであったようだ。これは、様々な低レベルの2Dおよび3Dインターフェース上で動作するように設計されており、最初の主要な製品版（v3.0）は1991年に完成した。
Silicon Graphics (SGI) は1991 年にOpenGL Performer (一般的には Performer と呼ばれる) をリリースしました。これは、その後のほとんどの SGI 製品の主要なシーングラフ システムとなりました。IRIS Inventor 1.0 (1992 年) は SGI によってリリースされ、Performer の上に構築された高レベルのシーングラフでした。1994 年にOpen Inventorがそれに続き、Performer の新しいリリースの上に構築された高レベルのシーングラフの別のバージョンとなりました。その他の 3D シーングラフ ライブラリについては、カテゴリ:3D シーングラフ API を参照してください。
X3Dは、 XMLを使用して3Dシーンやオブジェクトを表現・通信するための、ロイヤリティフリーのオープンスタンダードファイルフォーマットおよびランタイムアーキテクチャです。ISOが承認した標準規格であり、アプリケーションに組み込まれたリアルタイムグラフィックスコンテンツの保存、取得、再生のためのシステムを提供します。オープンアーキテクチャを採用することで、幅広いドメインやユーザーシナリオに対応します。