元記事：Dependency Graph

---

依存グラフ

Blender のアニメーションシステムが複雑に成長するにつれ、依存状態の評価を行うための、適切なシステムの必要性が非常に高まりました。2.37までは不適切な順番の評価により、見えないところでは、単なる計算の重複(Armatureデフォーム)、目に見えるところではアニメーションのラグなどと、多くの問題がありました。もしくは全く更新されてないことも…。

DAG(Directed Acyclic Graph: 非循環有向グラフ)

このような依存を取り扱うのに適切な方法が、非循環有向グラフ(directed acyclic graph: DAG)です。これは大変普及しており、タスクへ適用することのできるグラフ理論の中でもよく研究された構造です。枝がマージ可能なツリー構造体の拡張と考えることもできます。DAG はスケジューリングアプリケーションで非常によく使用されています。

DAG が一度構築されると、どの Object が他の物に依存しているかを表示したり、すべての循環しない依存関係について、評価の順序を見つけるためにクエリすることができます。副次的な動作として、新しい関係が循環を誘発していないかをチェックするのに使用することもできます。私たちはこれらのシンプルなタスクが、非常に多用途のサービスを提供するのを目にすることになるでしょう。

Jean-Luc Peurriere氏による完全な技術記事が、私たちの Wikiにあります。
(訳注：これを訳した時はまだ一般に開放されていなかったため、後日開放されるか、場所が移動することがあります)

DAG は Blender の多くの場所で使用可能ですが、現時点では、Blender のアニメーションシステムやツールによる Object 更新(表示)の信号を送る用途に議論を限定しています。

実装ノート

リレーションタイプ

4つの基本的なリレーションタイプが使用可能です。

1) Object が Object に影響 (OB_OB)
例えば Object の Parent、もしくはある種の Constraint 関係など。

2) Object が形状に影響 (OB_DATA)
これは Hook による Mesh の Vertex の移動、もしくはインバースキネマティクス(IK)Target の Object による Armature の変更がそうです。

3) 形状が Object に影響 (DATA_OB)
例えば Curve Path や、Vertex-Parent された Object など。

4) 形状が形状に影響 (DATA_DATA)
Curve や Lattice、Armature が他の Object をデフォームする場合。

下の画像は、４つすべてのリレーションタイプが使用されているケース、そして DAG のダイアグラムがどのようになるかを描いたものです。




Scene のソート

DAG の最初の使用は、Scene 内の、依存状態の順番でプリソーティングされた Object リストによる、ラグのない更新の計算の保証です。狙いはそれぞれの Object の計算を一度のみとすることで、これは、まだ循環依存に正しく取り組んでいないことを意味します。これは後の私たちの Todo です。
このコールはまた、新しい DAG もスクラッチから作成します。依存関係の変更(Parent など)や、Scene の切り替え時に常に呼ばれます。


Object のタグ付けとフラッシュ(Flush)

イベントや再描画毎に Object 更新の計算がされるのを阻止するため、Object をリフレッシュする必要があるかを示すタグ付けすることができます。現在、二つのタグのみが必要とされています。

Object->recalc:
OB_RECALC_OB: 自身の行列と Ipo で再評価すべき Object
OB_RECALC_DATA: 自身の形状(ジオメトリ)の表示を再構築すべき Object

DAG とリレーションタイプの使用時、シンプルな再帰の「フラッシュ(Flush)」でグラフ全体を処理させた後に、すべての関連する Object を更新することができます。
この時、リレーションタイプはフィルタとして働き、'recalc' タグがセットされる必要があるか、このようなタグを他のタイプに切り替えるべきかどうかを決定します。

例：上記の図では、IK-handle Object(OB_RECALC_OB)の移動で、Armature が OB_RECALC_DATA タグとしてフラッシュされ、これが順番に Cube へと OB_RECALC_OB として再びフラッシュされていきます。

コード内でこれらのタグを使用するには二つの方法があります。
'tag' には OB_RECALC_OB か、OB_RECALC_DATA のどちらかが入ります。このコールは現在の Object に、tag をセットするためのもので、もし、データが関係していれば、すべての Object は同じ形状を使用し、その後 tag で DAG を通じてフラッシュします。
このコールは EditMode もしくは UI のボタンの使用時のような、単一の Object の変更用です。

二つめの方法は、Object 自身にタグ付け(ob->recalc を設定)し、最後に下記をコールします。
これはその変更を DAG を通じてフラッシュします。

実際の Object 更新計算

この DAG のフラッシュは実際の Object の更新を全く行いません。単に Object に要再計算のタグをつけるだけです。実際の計算はその後、3DWindow の描画関数の始めで起こります。
このコール、object_handle_update() は recalc タグをチェックし、適切な動作をその Object に対して行い、タグをクリアします。すべての Object は、ここで評価される必要があります。これはプリソートでの評価の順序が関係しているからです。


Layer

不可視の Layer の Object の計算を阻止し、しかし不可視 Object に関連する可視の変更も確実に行うためには、DAG のフラッシュコードも、Layer の設定を使用してフラッシュする必要があります。
このフラッシュは実際には後方向(子から親)に行われ、すべての子の Layer 情報を含む、Parent 関係を確実に処理します。

Layer のフラッシュは、'recalc' タグのフラッシュより前に起こり、recalc タグ内の結果はフラッシュも、クリアさえもされません。


Transform サポート

上で説明したコールにより、Blender の transform() モジュールは簡単にタグを、変更した Object につけること、これらのタグのフラッシュ、このシステムにすべての更新をゆだねることが上手くできるようになりました。
最適化として、この Transform コードでは一度だけタグのフラッシュを行い、それらを一時的に格納し、それぞれの再描画時にセットしています。


アニメーションサポート

新しいフレームへの前進で、アニメーションシステムもまた、実行すべき変更の種類を、Object 群にタグ付けできます。例えば、Object Ipo、VertexKey、SoftBody、Action、アニメーションする Constraint などです。

そのためのコールがこれです。
これはタグの設定とフラッシュを行います。

また、すべてのアニメーションシステムを確実に更新するコールもあります。(Material、Sound、スクリプトを含む)。下記のコールは現在、レンダリングコードと、Blender の FrameChange で使用されています。
これはまた、DAG_scene_update_flags()コールを呼び出し、object_handle_update() により、直接その変更を適用します。




Armature サポート

Armature 内の Bone も同様で、特にインバースキネマティクス と Constraint の使用時には複雑な依存状態を持っています。Armature の Pose の変更時、Pose 'Channel'(Bone のラッパー)が DAG の構築により決定され、それが Channel のソートに使用されます。
この方法により、それぞれの Pose Channel で、変更時の評価が一度だけですむことが保障されます。


将来的な使用

DAG は Blender の他の関係状態の、効果的な評価の補助のために構築できます。二つの明らかになっている候補をあげます。
- Database 関係
- ライティング・シェーディング関係

---

元記事：Dependency Graph
Last update: Sep 11 2005.
This section is maintained by Ton Roosendaal.