シーングラフは、ベクター ベースのグラフィック編集アプリケーションや最新のコンピュータ ゲームでよく使用される階層型データ構造で、一連のオブジェクトの継承または空間表現をカスケードします。これは、グラフまたはツリー構造内のノードのコレクションです。ツリー ノードには多くの子がありますが、親は 1 つだけであり、親の効果はそのすべての子ノードに適用されます。グループに対して実行された操作は、その効果をすべてのメンバーに自動的に伝播します。多くのプログラムでは、各グループ レベルで幾何学的変換マトリックス(変換とマトリックスも参照) を関連付け、そのようなマトリックスを連結することが、そのような操作を処理する効率的で自然な方法です。たとえば、関連する形状やオブジェクトを 1 つの複合オブジェクトにグループ化し、単一のオブジェクトと同じくらい簡単に操作できるようにする機能が一般的な機能です。
グラフィック編集ツール
ベクターベースのグラフィック編集において、シーングラフ内の各リーフノードはドキュメントの最小単位、通常は楕円やベジェパスなどの図形を表します。図形自体（特にパス）はスプラインノードなどのノードにさらに分解できますが、より低レベルの表現ではなく、シーングラフを図形で構成されていると考える方が実用的です。
もう一つの便利でユーザー主導のノード概念は、レイヤーです。レイヤーは透明なシートのように機能し、その上に任意の数の図形や図形グループを配置できます。ドキュメントはレイヤーの集合となり、各レイヤーは必要に応じて非表示、淡色表示、またはロック（読み取り専用）にすることができます。アプリケーションによっては、すべてのレイヤーを線形リストに配置するものもあれば、任意の深さまでレイヤー内にレイヤーを配置できるものもあります。
内部的には、レイヤーとグループの間に実質的な構造的な違いはないかもしれません。どちらもシーングラフのノードに過ぎないからです。違いが必要な場合は、C++で一般的な型宣言として、汎用ノードクラスを作成し、そこからレイヤーとグループをサブクラスとして派生させるのが一般的です。例えば、可視性メンバーはレイヤーの機能ですが、必ずしもグループの機能であるとは限りません。
ゲームや3Dアプリケーション
シーングラフは、 3Dグラフィックスや、ますます大規模なワールドやレベルを扱う現代のゲームに役立ちます。このようなアプリケーションでは、シーングラフ内のノードは（一般的に）シーン内のエンティティまたはオブジェクトを表します。
例えば、あるゲームでは騎士と馬の間に論理的な関係を定義し、騎士を馬の延長として扱うとします。この場合、シーングラフには「馬」ノードとそれに付随する「騎士」ノードが存在します。
シーン グラフは、さまざまなエンティティの空間的関係と論理的関係も記述します。たとえば、騎士は馬が動くと 3D 空間を動きます。
このような大規模アプリケーションでは、シーングラフを設計する際にメモリ要件が重要な考慮事項となります。そのため、多くの大規模シーングラフシステムでは、メモリコストを削減し、速度を向上させるためにジオメトリインスタンス化が使用されています。上記の例では、各ナイトは個別のシーンノードですが、ナイトのグラフィカル表現（3Dメッシュ、テクスチャ、マテリアル、シェーダーで構成）はインスタンス化されています。つまり、データのコピーは1つだけ保持され、シーングラフ内の任意の「ナイト」ノードから参照されます。これにより、新しいナイトノードを作成する際に外観データを複製する必要がないため、メモリ使用量を削減し、速度を向上させることができます。
実装
シーングラフの最も単純な形式は、配列またはリンクリストのデータ構造を使用し、その形状の表示は、ノードを1つずつ線形反復処理するだけです。マウスポインタと交差する形状を確認するなどの一般的な操作も、線形探索によって行われます。小規模なシーングラフであれば、これで十分な場合が多いです。
運用と派遣
シーングラフに操作を適用するには、ノードの種類に基づいて操作をディスパッチする何らかの方法が必要です。例えば、レンダリング操作では、変換グループノードは、行列乗算、ベクトル変位、クォータニオン、またはオイラー角によって変換を蓄積します。その後、リーフノードはオブジェクトをレンダラーにレンダリングのために送信します。実装によっては、オブジェクトを直接レンダリングし、DirectXやOpenGLなどの基盤となるレンダリングAPIを呼び出すものもあります。しかし、レンダリングAPIの基盤となる実装は通常、移植性に欠けるため、シーングラフとレンダリングシステムを分離する場合もあります。このようなディスパッチを実現するには、いくつかの異なるアプローチがあります。
C++などのオブジェクト指向言語では、仮想関数を使うことで簡単にこれを実現できます。仮想関数は、ノードに対して実行可能な操作をそれぞれ表現します。仮想関数は簡単に記述できますが、ソースコードにアクセスできない状態では、ノードに新しい操作を追加することは通常不可能です。代わりに、ビジターパターンを使用することもできます。ただし、ビジターパターンにも同様の欠点があり、新しいノードタイプを追加するのも同様に困難です。
他の手法としては、RTTI（実行時型情報）の利用があります。操作は、現在のノードに渡されるクラスとして実現できます。そして、RTTIを用いてノードの型を照会し、コールバックまたはファンクタの配列から適切な操作を検索します。この場合、型とコールバックまたはファンクタのマップを実行時に初期化する必要がありますが、柔軟性、速度、拡張性が向上します。
これらの手法には様々なバリエーションがあり、新たな手法によって更なるメリットがもたらされる場合があります。代替手法の一つとして、シーングラフの再構築があります。これは、実行される操作ごとにシーングラフを再構築する手法です。ただし、この手法は非常に時間がかかる場合がありますが、高度に最適化されたシーングラフが生成されます。これは、シーングラフの適切な実装は、それが使用されるアプリケーションに大きく依存することを示しています。
トラバーサル
トラバーサルは、シーン グラフに操作を適用する際の威力の鍵です。トラバーサルは通常、任意のノード (多くの場合、シーン グラフのルート) から開始し、操作を適用し (多くの場合、更新操作とレンダリング操作は順番に適用されます)、シーン グラフ (ツリー) を再帰的に下に移動して子ノードに移動し、リーフ ノードに到達するまで続きます。この時点で、多くのシーン グラフ エンジンはツリーを上に向かってトラバースし、同様の操作を適用します。たとえば、変換を考慮したレンダリング操作を考えてみましょう。シーン グラフ階層を再帰的にトラバースしているときに、レンダリング前操作が呼び出されます。ノードが変換ノードの場合、そのノード自身の変換が現在の変換マトリックスに追加されます。操作がノードのすべての子のトラバースを終了すると、ノードのレンダリング後操作が呼び出され、変換ノードが変換を元に戻すことができるようになります。このアプローチにより、必要なマトリックス乗算の量が大幅に削減されます。
一部のシーン グラフ操作は、実際にはノードが異なる順序で走査されるときの方が効率的です。そのため、一部のシステムでは、シーン グラフの再構築を実装して、シーン グラフをより解析しやすい形式またはツリーに並べ替えます。
例えば2Dの場合、シーングラフは通常、ツリーのルートノードから開始し、子ノードを再帰的に描画することでレンダリングされます。ツリーの葉は、最も前面にあるオブジェクトを表します。描画は奥から手前へと進み、近いオブジェクトが遠いオブジェクトを単純に上書きするため、このプロセスは「ペインターアルゴリズム」を採用していると言われています。深度バッファを採用することが多い3Dシステムでは、近いオブジェクトを先に描画する方が効率的です。遠いオブジェクトは、近くのオブジェクトに隠されているため、実際にレンダリングする必要はなく、深度テストのみで済むことが多いためです。
シーングラフとバウンディングボリューム階層（BVH）
バウンディングボリューム階層（BVH）は、効率的なカリングやオブジェクト間の衝突判定の高速化など、様々なタスクに役立ちます。BVHは空間構造ですが、ジオメトリを分割する必要はありません（下記の空間分割を参照）。
BVHは、バウンディングボリューム（通常は球、軸に沿ったバウンディングボックス、または方向付きバウンディングボックス）のツリーです。階層の最下部では、ボリュームのサイズは単一のオブジェクト（高解像度のBVHでは、オブジェクトの一部）をしっかりと囲むのに十分な大きさです。階層を上っていくと、各ノードは独自のボリュームを持ち、その下にあるすべてのボリュームをしっかりと囲みます。ツリーのルートには、ツリー内のすべてのボリューム（シーン全体）を囲むボリュームがあります。
BVHは、オブジェクト間の衝突判定を高速化するのに役立ちます。オブジェクトの境界ボリュームがツリー内の上位のボリュームと交差しない場合、そのノードの下位のオブジェクトとは交差しません（そのため、すべてのオブジェクトはすぐに拒否されます）。
BVHとシーングラフにはいくつかの類似点があります。シーングラフは、各ノードにボリュームが関連付けられている場合、または階層内の便利な場所に専用の「バウンドノード」が追加されている場合、簡単にBVHを含むように、あるいはBVHになるように調整できます。これはシーングラフの典型的な表示方法ではないかもしれませんが、シーングラフにBVHを含めることにはメリットがあります。
シーングラフと空間分割
空間分割とシーングラフを組み合わせる効果的な方法は、空間分割データを含むシーンリーフノードを作成することです。これにより、レンダリングの計算効率が向上します。
空間データは通常静的であり、通常は何らかの分割された形式で固定されたシーンデータを含んでいます。システムによっては、システムとそのレンダリングが別々に扱われる場合があります。これは問題なく、どちらの方法にも実質的な利点はありません。特に、シーングラフを空間分割システム内に含めるのは好ましくありません。シーングラフは空間分割よりも大きなシステムと考える方が適切だからです。
非常に大規模な描画、またはレイトレーシング・レンダリング・プログラムのように実行時にのみ生成されるシーングラフでは、グループノードをより自動化された方法で定義する必要があります。例えば、レイトレーサーは3Dモデルのシーン記述を受け取り、個々のパーツをバウンディングボックス（バウンディングスラブとも呼ばれる）に分割する内部表現を構築します。これらのボックスは階層的にグループ化されるため、レイの交差テスト（可視性判定の一部）を効率的に計算できます。例えば、視線レイと交差しないグループボックスは、そのメンバーのテストを完全に省略できます。
同様の効率性は2Dアプリケーションにも当てはまります。ユーザーがドキュメントを拡大し、コンピューター画面に一部しか表示されていない状態でスクロールする場合、境界ボックス（この場合は境界矩形スキーム）を使用すると、どのシーングラフ要素が表示され、実際に描画する必要があるかを素早く判断できます。
アプリケーションの描画パフォーマンスの特性によっては、シーングラフの設計の大部分がレンダリング効率の考慮によって影響を受ける可能性があります。Quake などの3Dビデオゲームでは、可視性テストを最小限に抑えるために、バイナリ空間分割（BSP）ツリーが強く推奨されています。しかし、BSPツリーはデザインシーングラフからの計算に非常に長い時間がかかり、デザインシーングラフが変更されるたびに再計算する必要があるため、レベルは静的なままになる傾向があり、動的なキャラクターは空間分割スキームでは通常考慮されません。
ハイトフィールドやポリゴンメッシュといった高密度な規則的オブジェクトのシーングラフでは、3Dバウンディングボックス階層の特殊なバリエーションである四分木や八分木が用いられる傾向があります。ハイトフィールドはボックスの体積を占有するため、このボックスを個々のハイトフィールド要素に到達するまで8つのサブボックスに再帰的に分割する（これが八分木（octree）の「oct」の由来です）方法は効率的かつ自然です。四分木は単純に2Dの八分木です。
標準
フィグス
PHIGSは最初の商用シーングラフ仕様であり、 1988年にANSI規格となりました。Unixハードウェアベンダーによって異なる実装が提供されていました。HOOPS 3Dグラフィックスシステムは、単一のソフトウェアベンダーによって提供された最初の商用シーングラフライブラリであったようです。HOOPSは、異なる低レベルの2Dおよび3Dインターフェース上で動作するように設計されており、最初のメジャー製品バージョン（v3.0）は1991年に完成しました。
SGI
Silicon Graphics (SGI) は1991年にOpenGL Performer（通称Performer）をリリースしました。これはその後のほとんどのSGI製品の主要シーングラフシステムとなりました。SGIは1992年にIRIS Inventor 1.0をリリースしました。これはPerformerを基盤とした高レベルシーングラフでした。その後1994年にはOpen Inventorがリリースされ、これはPerformerの新しいリリースを基盤とした高レベルシーングラフの新たなバージョンです。その他の3Dシーングラフライブラリについては、カテゴリ:3DシーングラフAPIをご覧ください。
X3D
X3Dは、 XMLを使用して3Dシーンとオブジェクトを表現および通信するための、ロイヤリティフリーのオープンスタンダードファイル形式およびランタイムアーキテクチャです。ISO承認済みの標準規格であり、アプリケーションに埋め込まれたリアルタイムグラフィックコンテンツの保存、取得、再生のためのシステムを提供します。これらはすべてオープンアーキテクチャ内で実現され、幅広いドメインとユーザーシナリオをサポートします。
参照
参考文献
 |
本
- Leler, WmとMerry, Jim (1996) 3D with HOOPS、Addison-Wesley
- Wernecke, Josie (1994) The Inventor Mentor: Programming Object-Oriented 3D Graphics with Open Inventor、Addison-Wesley、ISBN 0-201-62495-8（リリース2）
記事
- バージーヴ、アヴィ。『シーングラフ：過去、現在、そして未来』
- ケアリー、リック、ベル、ギャビン (1997)。「注釈付きVRML 97リファレンスマニュアル」
- ジェームズ・H・クラーク (1976). 「可視曲面アルゴリズムのための階層的幾何学モデル」 Communications of the ACM . 19 (10): 547– 554. doi : 10.1145/360349.360354 .
- ヘルマン、ジム、ロルフ、ジョン (1994). 「IRIS Performer: リアルタイム3Dグラフィックスのための高性能マルチプロセッシングツールキット」
- PEXTimes – 「非公式には、X の PHIGS 拡張です。公式には、PEX は頭字語ではありませんでした。」
- シュトラウス、ポール (1993). 「IRIS Inventor, 3Dグラフィックスツールキット」
外部リンク
