JP2010530581A - 相互作用するオブジェクト集合をシミュレートするコンピュータ装置とその対応方法 - Google Patents

Abstract

【解決手段】相互作用するオブジェクト集合をシミュレートするコンピュータ装置および対応する方法である。相互作用するオブジェクト集合をシミュレートするコンピュータ装置は、オブジェクトの木表現を含むメモリ（８）および、各ノードが、その子ノードのデータおよび一定のノードに関する局所的な相互作用データに左右される動的データ、幾何的データおよび相互作用データに関連付けられ、＋木表現をスキャンして、その子ノードの局所的な相互作用データの関数としてノードの相互作用データの項目を更新する相互作用の更新用の機構を有する相互作用データのディストリビュータ（１０）と、＋木表現をスキャンして、関連する幾何的相互作用データの関数として動作する動的データを更新するための機構（１２）と、＋相互作用の対象となるノードに関する木表現をスキャンして、更新された動的データの関数として動作する、幾何的データを更新するための機構（１４）とを反復的に起動するシミュレーションコントローラ（４）を有する。更に、相互作用するオブジェクト集合をシミュレートする方法およびコンピュータプログラム製品に関する。
【選択図】図１

Description

本発明は、相互作用するオブジェクト集合のシミュレーションに関する。

相互作用するオブジェクトのシミュレーションは、多数の多かれ少なかれ複雑な機械的体のシミュレーションから、例えばたんぱく質などの分子の挙動のシミュレーションに至る、巨大な分野である。

開発された第１のアプローチは、オブジェクトを組み立てる目的、すなわち、大域的な挙動を定義するためにそれらを共にグループ化する目的を有する。この種のアプローチは、比較的低い計算コストの上で有用である。

しかし、計算コストの削減は、グループ化されるオブジェクト間の相関に関係する種々の態様が、意図的に無視されるか、または最も簡単な表現まで縮小されることとなるため、シミュレーションの現実味を損なう。

他のアプローチは、相互作用するオブジェクトを多関節構造体として見ることを含む。多関節構造体は一般に、結合部によって共に接合される２つの構造体から構成される。２つの構造体は、それ自体多関節構造体などであってもよい。このアプローチは、高い性能レベルを保持しつつ、この種のオブジェクト集合の機械的挙動に忠実なモデルを製作することを可能にする。

「機械的」挙動なる用語を用いるのは、本来オブジェクトはそれらを接続する関節または結合部によって相互作用するためである。従って、オブジェクト集合をモデル化するためには、結合部をモデル化すればよい。

オブジェクト間の相互作用が更に複雑になるに従い、それらに関係する計算要件／コストが法外となるため、これらのアプローチは、かなり急速に効果がなくなってしまう。

本発明は、上記の状況を改善することを目指す。

この目的のために、本発明において、相互作用するオブジェクト集合をシミュレートするコンピュータ装置であって、オブジェクト集合の木表現を含んだメモリを有するコンピュータ装置を提案する。この木表現において、中間表現のそれぞれは、動的データ、幾何的データおよび相互作用データに関連付けられる。

本装置は、反復サイクルによって
−オブジェクトおよびオブジェクトの部分集合に関する相互作用データディストリビュータと、
−対象となる相互作用データおよび幾何的データの関数として、相互作用を受けるノードに関する木表現のスキャンによって、動的データを更新するための機構と、
−更新された動的データの関数として、相互作用の対象となるノードに関する木表現のスキャンによって、幾何的データを更新するための機構とを起動するシミュレーションコントローラを更に有する。

関節に独立であるノード間の相互作用を考慮するために、メモリは更に、ノードの少なくともいくつかに関連付けられる局所的な相互作用データを含み、相互作用データディストリビュータは、対象となる子ノードの局所的な相互作用データの関数として、相互作用する対象物の木表現のスキャンによって、ノードの相互作用データ項目を更新する相互作用更新機構を有する。

この種の装置は、計算時間を著しく増大することなく、関節以外の力を考慮しつつ、多関節構造体に関するモデル化を用いたアプローチを拡大する可能性を提供するため、特に有利であり、それにより、シミュレーションの有用性を増大する。

本発明はまた、オブジェクト集合の木表現を保持する相互作用するオブジェクト集合の挙動をシミュレートする方法に関する。その表現において、各中間ノードは、その子ノードからのデータに依存する動的データ、幾何的データおよび相互作用データに関連付けられる。

本発明は反復的に、以下のステップを含むサイクル、すなわち
ａ．オブジェクトの一部およびオブジェクトの部分集合にわたって相互作用データを分配するステップと、
ｂ．相互作用の対象となるノードに関する木表現をスキャンし、関係する相互作用データおよび幾何的データの関数として、これらのノードの動的データを更新するステップと、
ｃ．相互作用の対象となるノードの場合には、再び木表現をスキャンし、ステップｂ．において更新された動的データの関数として幾何データを更新するステップとを実行する。

更に詳細には、ステップａ．は、
ａ１．相互作用の対象となるノードの相互作用データの更新によって、対象となる子ノードの局所的な相互作用データの関数として相互作用の対象となるノードに関する木表現をスキャンする予備スキャンを含む。

本発明のさらなる特徴および利点は、非限定的かつ例示的である実施例から導き出されるものであり、図面に基づき、以下の記載を読み進めることにより明らかとなる。

本発明におけるコンピュータ装置の概略図を示す。 図１における装置によって実行されるシミュレーションループの関数によるアプリケーションのブロック図を示す。 図２におけるシミュレーションループの第１の関数のブロック図を示す。 図３における関数のブロック図を示す。 図４の２つの関数を概略的に示す。 図４の２つの関数を概略的に示す。 図３の別の関数のブロック図を示す。 図２におけるシミュレーションループの第２の関数のブロック図を示す。 図２におけるシミュレーションループの第３の関数のブロック図を示す。 図２におけるシミュレーションループの第４の関数のブロック図を示す。 図２におけるシミュレーションループの第５の関数のブロック図を示す。

以下の図面および説明は、原則として限られた要素を記載する。従って、これらは本発明の理解を助けるために機能するだけでなく、いくつかの場合において、その定義にも寄与するであろう。

本記載は、著作者および／または著作権による保護に適格な要素を用いるものである。権利所有者は、正式書類に見られるように、本特許文書またはその説明のいかなる人物による同一の再現に対する異議はない。その他の点では、権利を全面的に保持する。

本発明はまた、製品として任意のコンピュータで読み込み可能な「媒体」（支持物）に提供される記載されたソフトウェア要素を包含する。「コンピュータで読み込み可能な媒体」なる表現は、磁気的、光学的および/または電子的データ記憶支持物のほか、アナログ信号またはデジタル信号などの伝送支持物またはキャリアも対象とする。

更に、詳細な説明は、本発明の範囲内で用いられる特定の数学的公式を提供する付録Ａによって補足される。この付録は、明確化の目的で提供され、参照を容易にするものである。本付録は、説明の構成部分を形成するものであり、従って、本発明の理解を助けるための役割だけではなく、いくつかの場合において、その定義にも寄与するであろう。

多関節構造体の機械的シミュレーションに対する第１のアプローチは、Ｆｅａｔｈｅｒｓｔｏｎｅによる論文“Ａ ｄｉｖｉｄｅ−ａｎｄ−ｃｏｎｑｕｅｒ ａｒｔｉｃｕｌａｔｅｄ ｂｏｄｙ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｐａｒａｌｌｅｌ ｏ（ｌｏｇ（ｎ））ｃａｌｃｕｌａｔｉｏｎ ｏｆ ｒｉｇｉｄ ｂｏｄｙ ｄｙｎａｍｉｃｓ．Ｐａｒｔ１：Ｂａｓｉｃ Ａｌｇｏｒｉｔｈｍ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｒｏｂｏｔｉｃｓ Ｒｅｓｅａｒｃｈ１８（９）：８６７−８７５（以下、Ｆｅａｔｈｅｒｓｔｏｎｅ’９９と呼ぶ）において提案されている。

Ｆｅａｔｈｅｒｓｔｏｎｅ’９９は、再帰的に力の成分および位置のすべてを計算するために、二分木に多関節構造体を切り離すためのアルゴリズムについて記載する。多関節構造体とは、それ自体多関節構造体であってもよい２つの構造体を接続する関節または結合部を含む全体的なユニットを指す。

従って、多関節体の概念は、単に機械的な意味に制限されてはならない。関節の概念もまた、より広義の意味で理解されなければならない。たとえば、関節は、ゼロ（２つの部分集合の固定結合）と６（２つの部分集合の無制限の相対的移動）との間の自由度の変数を含んでもよい。

二分木は、関節型オブジェクトの最も基本的な要素を表し、それぞれが結合部またはノードに接続される葉ノードを含む。従って、二分木の各ノードはそれ自体、オブジェクトの部分集合を表示する多関節体である。

ＲｅｄｏｎおよびＬｉｎによる論文“Ａｎ Ｅｆｆｉｃｉｅｎｔ，Ｅｒｒｏｒ−Ｂｏｕｎｄｅｄ Ａｐｐｒｏｘｉｍａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｓｉｍｕｌａｔｉｎｇ Ｑｕａｓｉ−Ｓｔａｔｉｃｓ ｏｆ Ｃｏｍｐｌｅｘ Ｌｉｎｋａｇｅｓ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｓｏｌｉｄ ａｎｄ Ｐｈｙｓｉｃａｌ Ｍｏｄｅｌｉｎｇ，２００５（以下、ＳＰＭ’０５と呼ぶ）は、結合部の加速度数的指標を定義することによって、このアプローチを達成する。

これらの数的指標は、葉のデータを認識することなく、純粋にこの結合部のデータから所与の結合部と関連付けられる多関節体の加速度を評価することを可能にする。従って、加速度数的指標が選択された閾値未満である多関節体の加速度を無効にすることによって、木を「固定」にすることを可能にする。従って、木を固定することは、確実に信頼性のあるシミュレーションを達成すると同時に、木のスキャンを削減されたノード数に制限することを可能にする。

Ｒｅｄｏｎ、ＧａｌｌｏｐｏおよびＬｉｎによる論文「Ａｄａｐｔａｔｉｖｅ Ｄｙｎａｍｉｃｓ ｏｆ Ａｒｔｉｃｕｌａｔｅｄ Ｂｏｄｉｅｓ」，ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｇｒａｐｈｉｃｓ（ＳＩＧＧＲＡＰＨ ２００５），２４（３）（以下、ＳＩＧＧＲＡＰＨ’０５と呼ぶ）において、シミュレーションの品質は、動的事例を処理することによっても、擬似静的事例のみを処理することによっても、また固定化を考慮する方法を追加することによっても改善され、具体的な現実性がない力の作成を回避する。

本明細書に記載される実施の形態は、これらの方法のすべてを活かし、いくつかの場合において、その拡張として実施されてもよいが、本発明のあらゆる他の実施の形態が予測され得る。

シミュレーションに関して、木の各ノードは、種々のデータと関連付けられる。データの３つの主要なタイプ、すなわち、相互作用データ、動的データおよび幾何的データは、区別され、以下に更に詳細に記載される。

相互作用データは、以下のように定義されてもよい。相互作用データは、所与のノードまたはこのノードによって表されるオブジェクトの部分集合において所与のオブジェクトに適用される力を表す。これらの力は、以下の２種類の力に分類されてもよい。

−関節を介したオブジェクトの相互作用にリンクされる応力、および
−所与のノードに加えられる可能性がある他の力のすべてを包含する局所的な力である。

ここに記載される実施例において、オブジェクトは、分子および原子であり、局所的な力は、一方では結合部に個別に加えられる外力を含み、他方では、静電力、ファンデルワールス力などの原子間力および分子間力のすべてを含む。

動的データは、多関節体の動力学的合成データ特性を表す。これらのデータは、オブジェクトの集合の位置および力のデータのすべてを必ずしも知る必要なく、結合部の加速度および速度の数的指標を計算することを可能にする。その用途は、以下に更に詳細に記載される。

幾何的データは、専ら互いにオブジェクトの相対位置に依存する多関節体の一連のデータ特性を表す。これらのデータは、特に、計算の大部分を局所的な参照点において実行することを可能にし、シミュレーションを更に容易にする。ここで再び、これらのデータについて以下に説明する。

ここに記載される実施の形態は、オブジェクトの擬似静的シミュレーションに適用する。これは、それらの速度がどの時点においてもゼロであると考えられることを意味する。

図１は、本発明による装置の概略図を示す。

装置２は、シミュレーションコントローラ４、シミュレーションブロック６およびメモリ８を有する。シミュレーションブロック６は、相互作用データディストリビュータ１０、動的データ更新機構１２および幾何的データ更新機構１４を含む。

シミュレーション中、コントローラ４は、メモリ８に含まれるデータに基づいて、以下に記載されるシミュレーションループにより、シミュレーションブロック６を反復的に起動する。

装置２は、種々の形態をとってよい。本好ましい実施の形態は、市販のコンピュータ、たとえば、１ＧＢのＲＡＭメモリを有する１．７ＧＨｚのマイクロプロセッサと、オペレーティングシステムおよびプログラムコードを含むのに十分な大きさのハードディスクとを有するコンピュータで実行されることができる形態で、コントローラ４およびブロック６を作動するコンピュータプログラムである。

しかし、特殊なプリント回路（ドーターボード、ＡＳＩＣなど）または専用のプロセッサ（ＦＰＧＡ、マイクロチップなど）の形態の構成など、他の実施形態が可能である。

図２は、ブロック６によって作成されるシミュレーションループの動作の概略図を示す。このループにおいて、関数Ｕｐｄ＿Ｉｎｔ（）２０、Ｓｐｒｄ＿Ｉｎｔ（）２２、Ｇｅｔ＿Ｄｙｎ＿Ｃｏｅｆｆ（）２４、Ｕｐｄ＿Ｄｙｎ（）２６およびＵｐｄ＿Ｇｅｏ（）２８が、連続的に呼び出される。

図２に示すループは、所与の動作ループにおけるシミュレーションの主要ステップを表す。これらのステップはそれぞれ、非関節性のオブジェクト間相互作用の更新、これらの相互作用のブロードキャスティング、動的シミュレーションパラメータの取得および更新、続いて、幾何的シミュレーションパラメータの更新である。

図２に示す異なるステップは、本発明を実装するプログラムにおける関数（ｆｕｎｃｔｉｏｎｓ）に対応するが、以下では、これらの関数自体が、多数のサブ関数を含み、当業者が選択し自由に実装する関数要素と見なされるべきであることが明らかとなろう。

関数の観点から、以下のように見なしてもよい。

＊関数Ｕｐｄ＿Ｉｎｔ（）２０およびＳｐｒｄ＿Ｉｎｔ（）２２は、データディストリビュータ１０の核を構成する、
＊関数Ｇｅｔ＿Ｄｙｎ＿Ｃｏｅｆｆ（）２４およびＵｐｄ＿Ｄｙｎ（）２６は、動的データ更新機構１２の核を構成する、および
＊関数Ｕｐｄ＿Ｇｅｏ（）２８は、幾何的データ更新機構１４の核を構成する。

図３は、図２における関数Ｕｐｄ＿Ｉｎｔ（）２０の考えられる実装を表す。この図から分かるように、関数Ｕｐｄ＿Ｉｎｔ（）２０は、３つのサブ関数Ｕｐｄ＿ＢＢ（）３０、Ｕｐｄ＿Ｉｎｔ＿Ｌ（）３２およびＵｐｄ＿Ｉｎｔ＿Ｖａｌ（）３４を有する。

従来のアプローチにおいては、オブジェクトの部分集合が固定になるとすぐに、これがシミュレーションにおいて処理されるのを一時的に停止する。この種のシミュレーションにおいて考慮される力は、機械的性質を帯びているため、この部分集合は、これから生じる結果がなかったとしても、オブジェクトの別の部分集合に空間的にきわめて近くてもよい。

蛋白質または分子鎖の挙動をシミュレートしたい場合には、静電気またはファンデルワールス型の局所的な原子間力が、応力および外力に加えられる。

固定化された部分集合に関して別の部分集合と相互作用することが可能になるにあたり、「機械的な」シミュレーションはもはや十分ではない。従って、オブジェクト同士の相対的な位置にのみ左右されるこれらの新たな局所的な力を考慮するために、「脱固定化」が必要である。既存のアプローチでは、すべての利点を失うことなく、これを実現することは可能ではない。

関数Ｕｐｄ＿Ｉｎｔ（）２０は、これらの局所的な力を考慮することが可能である。これを行うために、この関数は、所与の分子状態から始まり、第１の期間において、どのオブジェクトが互いに相互作用しやすいかを判定することを可能にする。第２の期間において、この関数は、対応する局所的な力を計算し、順序付けされた方式でこれらのデータを統合する。

関数Ｕｐｄ＿ＢＢ（）３０は、相互作用の検出を分子シミュレーションに対し適用したものである。原子間力は主に短距離であるため、この関数は、各オブジェクトの周囲の潜在的な相互作用のための空間を定義する。

更に正確に言えば、これらの空間は、オブジェクトまたはオブジェクトのグループの周囲の「有向空間」として定義される。ボックス自体は、シミュレーションの開始で二分木の各ノードに関して定義され、関数Ｕｐｄ＿ＢＢ（）３０は、各ボックスに関する参照点の位置および向きの方向を更新することによって作動する。

文献において「有向バウンディングボックス（Ｏｒｉｅｎｔｅｄ Ｂｏｕｎｄｉｎｇ Ｂｏｘ）」またはＯＢＢとして知られている有向ボックスの原理は、Ｇｏｔｔｓｈａｌｋらによる論文“Ｏｂｂｔｒｅｅ：ａ ｈｉｅｒａｒｃｈｉｃａｌ ｓｔｒｕｃｔｕｒｅ ｆｏｒ ｒａｐｉｄ ｉｎｔｅｒｆｅｒｅｎｃｅ ｄｅｔｅｃｔｉｏｎ”，ＡＣＭ Ｔｒａｎｓｌａｔｉｏｎ ｏｆ Ｇｒａｐｈｉｃｓ（ＳＩＧＧＲＡＰＨ １９９６）に記載されている。

ＯＢＢは、包囲するオブジェクトの位置に専ら左右され、取り付けられるノードへの関係接続において表現されるため、ノードが固定化されるときには変化しない。従って、関数Ｕｐｄ＿ＢＢ（）３０は、その位置が、先行するシミュレーションステップ中に変化したノードで専ら作動する。この関数は、選択的な方式で下から上に二分木を通過し、以下で説明するように、いわゆるアクティブノードのみを通過する。

更新されたＯＢＢは、関数Ｕｐｄ＿Ｉｎｔ＿Ｌ（）３２によって用いられる作業ベースを形成する。この関数、図４に示される実装は、上から下に、根ＲＮから再帰的に二分木をスキャンする。

関数Ｕｐｄ＿Ｉｎｔ＿Ｌ（）は、各ノードに関して、２つの主要なリストＩｎｔ＿ＬおよびＩｎｔ＿Ｌ＿Ｏｌｄを維持する。各ノードで、リストＩｎｔ＿Ｌ（またはそれぞれ、Ｉｎｔ＿Ｌ＿Ｏｌｄ）は、現行ループ（またはそれぞれ、先行ループ）で局所的な力によって相互作用する所与のノードによって指定されるオブジェクトの部分集合に属するノードのペアを含む。

これらのリストは、先行ループの後のオブジェクトの位置によって変更された局所的な相互作用、すなわち、修正された局所的な相互作用を検出することを可能にする。

関数Ｕｐｄ＿Ｉｎｔ（）は、現在のノードにおける活性試験３２００から始まる。この試験は、現在のノードの加速度数的指標（または適切であれば、他の適切な数的指標）に関連し、これらの数的指標の値の関数として決定されるノードが実際にアクティブであるかどうかを指定するこれらの数的指標の計算の形態またはデータ項目の読み出しの形態（一般に「フラグ」と呼ばれる）において実行されてもよい。

ここに記載される実施例において、ノードは、その加速度数的指標の値がユーザによって選択された閾値より大きい場合には、すなわち、非固定化されると見なされる場合には、アクティブであると考えられる。ノードが固定されている場合には、このことは、ノードと関連付けられる多関節体の中の大域的な加速度が、シミュレーションの範囲内でゼロであると考えられることを意味する。

前述から分かるように、このことは、この構造体の加速度がゼロであると考えられるため、この構造体の中のオブジェクトの位置が変化しないことを意味する。従って、先行ループの相互作用のリストＩｎｔ＿ＬおよびＩｎｔ＿Ｏｌｄ＿Ｌは、このノードおよびすべてのこれらの子ノードに関して有効なままであり、関数が停止する（３２０２）。

ノードＣがアクティブである場合には、先行ループのリストＩｎｔ＿Ｌ（Ｃ）は、上書き（３２０４）することによって現在のループではリストＩｎｔ＿Ｏｌｄ＿Ｌ（Ｃ）になり、リストＩｎｔ＿Ｌ（Ｃ）はゼロにリセットされる（３２０６）。

次に、ノードＣの子ノードたちの間の考えられる相互作用のすべてを待ち行列に入れるために、ループが始動される。従って、２つの中間子ノードＡおよびＢは、３２０８で関数ＣＨ（）によって復元され、それらのＯＢＢ、ＯＢＢＡおよびＯＢＢＢが３２１０で復元される。

その結合（ｃｏｕｐｌｅ）（ＯＢＢＡ，ＯＢＢＢ）が次に、リストＱにスタックされ（３２１２）、ＯＢＢ間の潜在的相互作用用の記憶スタックとして機能する。記載したループは、その停止条件としてスタックＱを空にすることを有し（３２１４）、関数Ｕｐｄ＿Ｉｎｔ＿Ｌ（Ｃ）は、この条件が満たされるときに停止する（３２１６）。

ループは、リストＱのスタックから取り出されることによって始まり、Ｑに導入される潜在的相互作用（ＯＢＢＥ、ＯＢＢＦ）の最後の結合を復元することを可能にする（３２１８）。このループの第１の相互作用が、ステップ３２１２の結合（ＯＢＢＡ、ＯＢＢＢ）によるものであるのは明らかである。

３２２０で、衝突したかどうかの立証を可能にするために、関数Ｕｐｄ＿Ｐｏｓ（）は、ＯＢＢ、ＯＢＢＥおよびＯＢＢＦの実世界における位置を更新する。この「実」位置の更新は、そのノードの関係において各ＯＢＢの相対的な位置を更新する関数Ｕｐｄ＿ＯＢＢ（）３０において達成される更新とは異なる。

実位置と相対位置との間の差は、更に効果的かつ統合した方式でアルゴリズムを実装することを可能にする。にもかかわらず、関数Ｕｐｄ＿ＢＢ（）３０において直接的にＯＢＢの実位置を更新することが可能である。

３２２２で、関数Ｃｏｌｌ（）は、ＯＢＢＥとＯＢＢＦが衝突状態にある、すなわち、有向ボックスが交差したかどうかを判定する。これが当てはまらない場合には、局所的な相互作用はなく、ループは３２１４で次の潜在的な相互作用をテストするためにリセットされる。

ノードＥおよびＦそれぞれと関連付けられるＯＢＢＥおよびＯＢＢＦが衝突状態にある場合には、４つの可能性がある。

ａ）ＥおよびＦがいずれも木の葉であり、このことは、これらのオブジェクトが互いと相互作用することを意味し、関数が停止する、
ｂ）Ｆが関節型オブジェクトであり、Ｅが葉であり、このことは、Ｆの子ノードとＥに関連付けられるオブジェクトとの相互作用を判定し、次にＦの子ノード同士の相互作用を判定するするためには、Ｆを探索せねばならないことを意味する、
ｃ）Ｅが関節型オブジェクトであり、Ｆが葉であり、このことは、Ｅの子ノードとＦに関連付けられるオブジェクトとの相互作用を判定し、次にＥの子ノード同士の相互作用を判定するためにはＥを探索しなければならないことを意味する、および
ｄ）ＥおよびＦがいずれも関節型オブジェクトであり、このことは、ＥとＦそれぞれの
子ノードの間の相互作用を判定し、次にＥおよびＦの子ノード同士の相互作用を判定するためにＥおよびＦを探索しなければならないことを意味する。

そのためには、テスト３２２４は、ＯＢＢＥに関して関数ＣＨ＿ＯＢＢ（）を呼び出すことによって、Ｅが葉ノードであるかどうかを判定する。ＯＢＢを取り込み、その入力時ではノードではない点を除き、関数ＣＨ＿ＯＢＢ（）は関数ＣＨ（）と同様である。

Ｅが葉ノードである場合には、関数ＤＰ１（）が３２３０で呼び出され、事例ａ）およびｂ）を管理する。関数ＤＰ１（）の実装の実施例を図５に示す。この関数において、テスト３２３２は、ＯＢＢＦに関して関数ＣＨ＿ＯＢＢ（）を呼び出すことによって、Ｆが葉ノードであるかどうかを判定する。

Ｆが葉ノードである場合には、事例ａ）が適用され、リストＩｎｔ＿Ｌ（Ｃ）が、３２３４でペア（Ｅ，Ｆ）を受け取り、関数ＤＰ１（）が３２３６で停止し、Ｕｐｄ＿Ｉｎｔ＿Ｌ（Ｃ）のループが、３２１４でスタックＱのテストから再開する。

Ｆが関節型オブジェクトである場合には、ＦＡおよびＦＢは、Ｆの子であり、事例ｂ）が適用される。ＥとＦの子らの相互作用を判定するために、ＦＡおよびＦＢのＯＢＢが、３２３８で復元され、次に２つの潜在的相互作用（ＯＢＢＥ，ＯＢＢＦＡ）が、３２４０でスタックされ、（ＯＢＢＥ，ＯＢＢＦＢ）が３２４２でスタックＱにスタックされる。

次に、３２４４でＦに関してＵｐｄ＿Ｉｎｔ＿Ｌ（）を呼び出すことによって、Ｆの子同士の相互作用が判定される。この関数呼び出しは、リストＵｐｄ＿Ｏｌｄ＿Ｌ（Ｆ）およびＵｐｄ＿Ｌ（Ｆ）の更新を可能にする。最後に、関数ＤＰ１（）は、３２３６で停止し、Ｕｐｄ＿Ｉｎｔ＿Ｌ（Ｃ）のループが、３２１４でスタックＱのテストから再開する。

Ｅが関節型オブジェクトである場合には、ＥＡおよびＥＢは、その子である。次に、関数ＤＰ２（）が３２５０で呼び出され、事例ｃ）およびｄ）を管理する。関数ＤＰ２（）の実装の例を図６に示す。

この関数において、テスト３２５２は、ＯＢＢＦに関して関数ＣＨ＿ＯＢＢ（）を呼び出すことによって、Ｆが葉ノードであるかどうかを判定する。

Ｆが葉ノードである場合には、事例ｃ）が適用される。Ｅの子たちとＦの相互作用を決定するために、ＥＡおよびＥＢのＯＢＢが、３２５４で復元され、次に２つの潜在的相互作用（ＯＢＢＥＡ，ＯＢＢＦ）が、３２５６でスタックされ、（ＯＢＢＥＢ，ＯＢＢＦ）が３２５８でスタックＱにスタックされる。

次に、３２６０でＥに関してＵｐｄ＿Ｉｎｔ＿Ｌ（）を呼び出すことによって、Ｅの子同士の相互作用が判定される。この関数呼び出しは、リストＵｐｄ＿Ｏｌｄ＿Ｌ（Ｅ）およびＵｐｄ＿Ｌ（Ｅ）の更新を可能にする。最後に、関数ＤＰ２（）は、３２６２で停止し、Ｕｐｄ＿Ｉｎｔ＿Ｌ（Ｃ）のループが、３２１４でスタックＱのテストから再開する。

Ｆが関節型オブジェクトである場合には、ＦＡおよびＦＢは、Ｆの子たちであり、事例ｄ）が適用される。Ｅの子たちとＦの子たちとの相互作用を判定するために、ＯＢＢＥおよびＯＢＢＦに関して関数Ｍａｘ＿Ｖｏｌ（）が、３２６４で呼び出される。

関数Ｍａｘ＿Ｖｏｌ（）は、他のノードと関連付けられるノードの子たちの相互作用を探索するために、ＯＢＢＥおよびＯＢＢＦのいずれがより大きな量を有するかを決定する。これは、Ｕｐｄ＿Ｉｎｔ＿Ｌ（）の性能を最適化することを可能にする。

結果として、３つのＯＢＢ、すなわち、ＯＢＢＭＡ、ＯＢＢＭＢおよびＯＢＢＭｉｎが得られる。従って、ＯＢＢＥがＯＢＢＦより大きい場合には、ＯＢＢＭＡはＯＢＢＥＡを含み、ＯＢＢＭＢはＯＢＢＥＢを含み、ＯＢＢＭｉｎはＯＢＢＦを含む。逆の事例においては、ＯＢＢＭＡはＯＢＢＦＡを含み、ＯＢＢＭＢはＯＢＢＦＢを含み、ＯＢＢＭｉｎはＯＢＢＥを含む。

２つの潜在的相互作用（ＯＢＢＭＡ，ＯＢＢＭｉｎ）が、３２６６でスタックされ、（ＯＢＢＭＢ，ＯＢＢＭｉｎ）が３２６８でスタックＱにスタックされる。次に、３２７０でＥに関してＵｐｄ＿Ｉｎｔ＿Ｌ（）を呼び出すことによって、Ｅの子同士の相互作用が判定され、３２７２でＦに関してＵｐｄ＿Ｉｎｔ＿Ｌ（）を呼び出すことによって、Ｆの子同士の相互作用が判定される。

これらの関数呼び出しは、リストＵｐｄ＿Ｉｎｔ＿Ｌ（Ｅ）、Ｕｐｄ＿Ｌ（Ｅ）、Ｕｐｄ＿Ｏｌｄ＿Ｌ（Ｆ）およびＵｐｄ＿Ｌ（Ｆ）を更新することを可能にする。最後に、関数ＤＰ２（）は、３２６２で停止し、Ｕｐｄ＿Ｉｎｔ＿Ｌ（Ｃ）のループが、３２１４でスタックＱのテストから再開する。

暗に示されているように、関数Ｕｐｄ＿Ｉｎｔ（）が、ノードＣに適用され、その結果、２つの重なる再帰を有する。

第１の再帰は、ノードに関する深さレベルに関係なく、ノードＣの子たちの間の潜在的相互作用結合のすべてを分析するために、スタックＱのスタッキングおよびアンスタッキングに関する。

第２の再帰は、Ｃの子ノードに関する関数Ｕｐｄ＿Ｉｎｔ（）の選択的呼び出しに関し、すべてのアクティブノードのリストＵｐｄ＿Ｏｌｄ＿Ｌ（）およびＵｐｄ＿Ｌ（）の更新を可能にする。

上記で分かるように、二分木における局所的な相互作用を決定することは主に、ＯＢＢの特性に基づいている。しかし、ＯＢＢは有益なツールを構成するが、相互作用予測表などの他のツールまたは特定の用途を踏まえて当業者が予想することができる他の適切なツールを用いてもよい。

リストＵｐｄ＿Ｏｌｄ＿Ｌ（）およびＵｐｄ＿Ｌ（）が、すべてのアクティブノードに関して更新されたとき、相互作用データは、関数Ｕｐｄ＿Ｉｎｔ＿Ｖａｌ（）３４によって更新される準備ができる。

関数Ｕｐｄ＿Ｉｎｔ＿Ｖａｌ（）の１つの実装を図７に示す。この図から分かるように、この関数は、再帰ブロック７００で始まる。ノードＲＮに関して関数Ｕｐｄ＿Ｉｎｔ＿Ｖａｌ（）を呼び出すことによって、ブロック７００は、二分木において下降（ｄｅｓｃｅｎｔ）を実行する。

ブロック７００は、上述したように、７０２で現在ノードＣにおける活性テストから始まる。現在ノードが非アクティブである場合には、関数は７０４で終了する。現在ノードがアクティブである場合には、木における下降は、７０６で関数ＣＨ（）によってこのノードの子たちＡおよびＢを得ることによって開始される。

次に、活性テストは、前述したように、７０８でＣの左側の子Ａで実行される。ノードＡがアクティブである場合には、左側の降下が、Ａに関してＵｐｄ＿Ｉｎｔ＿Ｖａｌ（）を呼び出すことによって、７１０で実行される。

次に、活性テストが、前述したように、７１２でＣの右側の子Ｂで実行される。Ａが非アクティブである場合には、テスト７１２が直接実行され、ノードＣに関する左側の下降はない。

ノードＢがアクティブである場合には、Ｂに関してＵｐｄ＿Ｉｎｔ＿Ｖａｌ（）を呼び出すことによって、右側の下降が７１４で実行される。これは次に、再帰下降ブロック７００の終了であり、関数はその実際の処理部分によって続行される。Ｂが非アクティブである場合には、ノードＣに関する右側の下降はなく、ブロック７００が終了し、関数はその実際の処理部によって続行される。

一旦、ブロック７００が反復され、再帰が実行されると、データの処理は、７２０でリストＵｐｄ（Ｃ）およびスタックＱをリスタートすることによってノードＣで開始する。

リストＵｐｄ（Ｃ）は、ブロック７００によって実行された再帰呼び出し中に、Ｃの子たちにおいて更新されたデータから更新された相互作用データを徐々に上昇させるように機能する。

リストＱは、現在ノードで更新されなければならない相互作用データのオブジェクトに関する記憶スタックとして機能する。従って、リストＱは、７２２でＵｐｄ（Ａ）、Ｕｐｄ（Ｂ）、Ｉｎｔ＿Ｏｌｄ＿Ｌ（Ｃ）およびＩｎｔ＿Ｌ（Ｃ）を受ける。なお、当業者においては、Ｉｎｔ＿Ｏｌｄ＿Ｌ（Ｃ）およびＩｎｔ＿Ｌ（Ｃ）は、ノードのペアを含むものでありノードではないが、動作７２２は互いに区別されたノードのみをＱにスタッキングすることからなるということがわかるであろう。

従って、相互作用データを増大するためのループは、作業ノードＲにおけるリストＱのアンスタッキングと共に７２４で始まる。作業ノードＲは、ブロック７００の再帰のアンスタッキング中にそれに関連付けられるデータを上昇するために、７２６でリストＵｐｄ（Ｃ）に追加される。次に、ＲがＡで指定されたオブジェクトの部分集合またはＢで指定された部分集合のいずれに属しているかを判定するために、テスト７２８が実行される。

ＲがＡで指定されたオブジェクトの部分集合に属している場合には、７３０で、相互作用データＦ（Ｃ，Ｒ）がＦ（Ａ，Ｒ）の値によってリセットされる。そうでない場合には、７３２で、Ｆ（Ｃ，Ｒ）がＦ（Ｂ，Ｒ）の値によってリセットされる。最後に、７３４におけるＱのテストは、Ｑのオブジェクトの相互作用データのすべてがリセットされたかどうかを表す。

Ｑが空である場合には、相互作用データのための更新ループは、７３６でリストＩｎｔ＿Ｌ＿ｔ（Ｃ）のアンスタッキングから始まる。リストＩｎｔ＿Ｌ＿ｔ（Ｃ）は、リストＩｎｔ＿Ｌ（Ｃ）の作業コピーであり、ループの更新のためだけに用いられる。リストＩｎｔ＿Ｌ＿ｔ（Ｃ）のアンスタッキングの結果は、作業ノードのペア（Ｐ，Ｔ）に格納される。

７３８で、相互作用データＦ（Ｃ，Ｐ）が、上述したループにおいてリセットされた値Ｆ（Ｃ，Ｐ）にＰとＴの相互作用の値Ｆ（Ｐ，Ｔ）を追加することによって更新される。Ｆ（Ｐ，Ｔ）の値は、関数Ｆ＿Ｉｎｔ（）によって計算され、Ｐの参照点において、Ｔに関するＰの原子間の相互作用の強度を与える。これと同様の動作が、Ｔの参照点の中で、上記のループでリセットされたＦ（Ｃ，Ｔ）の値にＴとＰの相互作用の値Ｆ（Ｔ，Ｐ）を追加することによって、Ｔに関して７４０で実行される。

関数Ｆ＿Ｉｎｔ（）は、２つの原子／分子の間の静電気相互作用およびファンデルワース相互作用の公知の公式に基づいている。当然のことながら、他の公式を用いてもよい。Ｆ＿Ｉｎｔ（）が呼び出された第１のノードと関連付けられる参照点における相互作用を計算するものであることを留意することが重要である。

次に、７４２で、テストは、Ｉｎｔ＿Ｌ＿ｔ（Ｃ）が完全にアンスタッキングされたかどうかを調べる。アンスタッキングされた場合には、７４４でＵｐｄ＿Ｉｎｔ＿Ｖａｌ（）の関連インスタンスが終了する。そうでない場合には、更新ループが７３６で再開する。一旦リストＩｎｔ＿Ｌ＿ｔ（Ｃ）が完全にアンスタッキングされると、相互作用データＦ（Ｃ，Ｘ）（但し、ＸはＣから下降した葉ノードである）は、Ｃの子孫である他の葉ノードのすべてによって、ノードＸによって行われたすべての相互作用を表す。

上記を踏まえると、関数Ｕｐｄ＿Ｉｎｔ＿Ｖａｌ（）は、根ノードによって呼び出されるが、下から上へのアプローチを有することは明白である。また、この関数は、Ｃの他の葉ノードによって、ノードＣの各葉ノードによって行われるすべての相互作用を徐々に上昇させるように見える。

最後に、この関数はまた、その相互作用データがリストＵｐｄ（）によって更新されるノードの追跡（ｔｒａｃｅ）を保持する。従って、関数Ｕｐｄ＿Ｉｎｔ＿Ｖａｌ（）が終了するとき、根ノードＲＮは、一方ではその葉ノードの相互作用データのすべてを含むだけではなく、現在ループで更新された相互作用データのリストも含み、実際に展開された（ｅｖｏｌｖｅｄ）ノードのみがアクセスされることを保証する。

一旦、関数Ｕｐｄ＿Ｉｎｔ＿Ｖａｌ（）が終了されると、関数Ｕｐｄ＿Ｉｎｔ（）が終わる。図２に示されるように、関数Ｕｐｄ＿Ｉｎｔ（）の後には、シミュレーションループにおいて、関数Ｓｐｒｄ＿Ｉｎｔ（）が続く。関数Ｓｐｒｄ＿Ｉｎｔ（）は、そのリストＵｐｄ（ＲＮ）が関数Ｕｐｄ＿Ｉｎｔ（）によって修正された相互作用データのすべてを含むため、根ノードＲＮによって呼び出される。

この関数の実装の例を図８に示す。関数Ｓｐｒｄ＿Ｉｎｔは、入力ノードのリストＵｐｄ（Ｃ）におけるテスト８０２から始まるループである。このリストが空である場合には、関数は８０４で終了する。

リストＵｐｄ（Ｃ）が空でない場合には、要素Ｒが８０６でアンスタッキングされ、対応するノードの相互作用データＦ（Ｒ，Ｒ）が８０８で値Ｆ（Ｃ，Ｒ）に更新される。

次に、関数Ｓｅｔ＿Ｆｌｇ（）が、８１０でＲに関連付けられるデータＦｌｇ＿ｂｐｈを記録する。データＦｌｇ＿ｂｐｈの値は、動的係数ｂ，ｐおよびηを更新する必要度を表す。関数Ｓｅｔ＿Ｆｌｇ（）はまた、根ノードＲＮまでのノードＲの祖先のすべてに関するデータＦｌｇ＿ｂｐｈも記録する。ループは次に、リストＵｐｄ（Ｃ）が空になるまで８０２で再開する。

関数Ｓｐｒｄ＿Ｉｎｔ（）が、種々の方法で実装されることができることに留意されたい。注目すべきことに、ここでは更新された相互作用データが、問題のノードに格納される。しかし、別の位置、たとえば、個別の表にこれらの相互作用を格納することが可能である。関数Ｓｅｔ＿Ｆｌｇ（）に記録されるデータについても同様である。

またこの関数を実行せず、必要に応じて適切な方式でリストＵｐｄ（ＲＮ）の呼び出しで済ませることも可能であるが、これは、明確さの一定の欠如を生じ、相対的に管理の複雑さをもたらすことになる。

相互作用データが更新されると、シミュレーションループは、関数Ｇｅｔ＿Ｄｙｎ＿Ｃｏｅｆｆ（）によって拡張され、木のオブジェクトおよびノードの動的パラメータを決定することを可能にする。

関数Ｇｅｔ＿Ｄｙｎ＿Ｃｏｅｆｆ（）の実装の一例を図９に示す。関数Ｇｅｔ＿Ｄｙｎ＿Ｃｏｅｆｆ（）は、関数Ｕｐｄ＿Ｉｎｔ＿Ｖａｌ（）のように、下から上への伝搬関数である。この伝搬を得るために、テスト９０２は、ノードＣに子ノードＡおよびＢがあるかどうかを調べる。

ノードＣに子ノードがない場合には、テスト９０４は、データＦｌｇ＿ｂｐｈ（Ｃ）が作動されるかどうかを調べる。これが当てはまる場合には、ノードＣは、９０６で関数Ｃｏｅｆｆ＿ｂｐｈ（）が呼び出される葉ノードであり、この関数はｐ（Ｃ）およびη（Ｃ）を０に設定し、更新された相互作用データＦ（Ｃ，Ｃ）からｂ（Ｃ）を計算する。ステップ９０６の後でまたはデータＦｌｇ＿ｂｐｈ（Ｃ）が動作されない場合には、関数は９０８で終了する。

ノードＣが子ノードを有する場合には、９１０および９１２でＡおよびＢに関して、関数Ｇｅｔ＿Ｃｏｅｆｆ＿Ｄｙｎ（）が再帰的に呼び出される。これは、下から上への二分木の必要なノードのスキャンを保証する。一旦すべての再帰呼び出しが起動され、必要な葉ノードのすべてが処理されると、木のリセットが実行され、ブロック９２０において再帰ループによるループを再帰する。

ブロック９２０において、第１のテスト９２２が、現在のノードＣがアクティブであるかどうかを調べる。アクティブである場合には、Ｃの子たち、すなわちＡおよびＢの係数の値に関して、関数Ｃｏｅｆｆ＿ｐｈｉｐｓｉ（）を呼び出すことによって、係数ΦＣおよびΨＣが、９２４で計算される。次に、Ｃの子たち、すなわちＡおよびＢの係数の値に関して、関数Ｃｏｅｆｆ＿ｂｐｈ（）を呼び出すことによって、係数ｂ（Ｃ）、ｐ（Ｃ）およびη（Ｃ）が、９２６で計算される。最後に、関数は、９２８で終了する。

現在のノードＣが非アクティブである場合には、９３０で、データＦｌｇ＿ｂｐｈ（Ｃ）に関するテストが、実行される。テストが否定である場合には、関数は、９２８で直接的に終了する。このテストが肯定である場合、すなわち、データが係数ｂ（Ｃ）、ｐ（Ｃ）およびη（Ｃ）の更新が必要であると示す場合には、これらは、９３２で、Ｃの子たち、すなわちＡおよびＢの係数の値に関して、関数Ｃｏｅｆｆ＿ｂｐｈ（）を呼び出すことによって計算される。最後に、関数は、９２８で終了する。

付録Ａにおける公式（１）〜（１３）は、これらの係数が、関数Ｃｏｅｆｆ＿ｐｈｉｐｓｉ（）およびＣｏｅｆｆ＿ｂｐｈ（）において確立されていることに基づいた計算の公式を与える。本記載の目的において、再帰的に決定されたこれらの係数が、多関節体の挙動を局所的に記述し、またシミュレーションの数的指標、加速度および位置の計算に関する基準として機能することを可能にすることを認識していればよい。さらなる情報に関しては、文献ＳＰＭ’０５およびＳＩＧＧＲＡＰＨ’０５が、正確な定義およびこれらの式の取得法を説明する。本出願人は、これらの文献をこの目的のために閲覧することを推奨する。

特に、係数ｂ（Ｃ）、ｐ（Ｃ）およびη（Ｃ）の計算は、ノードＣの関節におけるアクティブな力のデータ項目を表す大きさＱを直接的および間接的に伴ってもよいことに留意されたい。この大きさＱは、たとえば、二面角に左右される結合を表すために用いられてもよい。ノードＣと関連付けられる大きさＱの計算が、Ｃの子たちＡおよびＢの相対位置にのみ左右される場合には、この大きさは、アクティブノードに関してのみ更新される。従って、この更新は、たとえば、関数Ｃｏｅｆｆ＿ｂｐｈ（）によるｂ（Ｃ）、ｐ（Ｃ）およびη（Ｃ）の計算の直前に実行されてもよい。

動的係数が更新されると、関数Ｕｐｄ＿Ｄｙｎ（）は、これらの係数に基づいて動的データを更新する。関数Ｕｐｄ＿Ｄｙｎ（）の実装の例を図１０に示す。

図１０に示される関数Ｕｐｄ＿Ｄｙｎ（）は、上から下に二分木を通過する再帰関数である。

この関数は、以下に示されるように、アクティブノードの判定を最適化するために設定する優先度待ち行列を用いる。このため、現在のノードが根ノードＲＮである場合には、現在のノードのテスト１００２が、加速度数的指標１００３の計算を呼び出す。結果は、１００６における停止条件として作用する終点εのための基礎として１００４で機能する。

加速度数的指標の計算は、付録Ａの公式２１に記載される計算を行い、現在ノードの子ノードの加速度の平方和に対応する関数Ｔｏｔ＿Ａｃｃ（）によって実行される。これは、アクティブノードおよび非アクティブノードを定義することを可能にする。

実際には、εｍａｘが、加速度数的指標に関して所望のシミュレーション精度を定義する。従って、ε＜εｍａｘである場合には、これは、所望の正確さが達成されることを意味する。従って、ノードＣの加速度ｑｄｄ（Ｃ）は、計算されず、関数は１０１０で終了する。

他方、ε＞εｍａｘである場合には、シミュレーションは、十分に正確であるものとは見なされない。１０１２で、テストは、ノードＣが子を有するかどうかを決定する。子を有しない場合には、関数は１０１０で終了する。

関数Ａｃｔｉｖｅ＿Ｆｌｇ（ｃ）が次に、１０１４で呼び出される。関数Ａｃｔｉｖｅ＿Ｆｌｇ（）は、現在のシミュレーションループと関連付けられる時間マーカを含むデータ項目を記録する。ノードにおける活性テストにおいて用いられるのがこの時間マーカである。このために、所与のノードに関して、それと関連付けられる最適な時間マーカが、現在ループの時間マーカと比較される。一致する場合には、ノードはアクティブであると考えられる。同様の方法を、データＦｌｇ＿ｂｐｈ（Ｃ）を起動するために用いることができる。

ノードＣが子たちＡおよびＢを有する場合には、ノードＣの加速度ｑｄｄ（Ｃ）は、関数Ｑ＿Ｄｏｔによって１０１６で計算される。関数Ｑ＿Ｄｏｔ（）は、動的係数Φ（Ｃ）およびｂ（Ｃ）および力Ｆ（Ｃ）を用いる。関数Ｑ＿Ｄｏｔ（）によって実行される計算は、付録Ａの式２２によって説明される。

力Ｆ（Ｃ）は、ノードＣに適用される関節力のすべてを表す合成ベクトルである。根ノードＲＮに関し、特定の条件が、ＳＰＭ’０５の３．１．２節に記載されるように、ベクトルＦ（Ｃ）を決定することを可能にする。

論文ＳＰＭ’０５の３．１．１節に記載されるように、ベクトルＦ（Ｃ）は、２つの成分Ｆ（１，Ｃ）およびＦ（２，Ｃ）を有する。本発明の範囲内で、ノードのベクトルＦ（Ｃ）は、その子ノードＦ（Ａ）およびＦ（Ｂ）のベクトルを計算するように機能する。

実際には、Ｃの２つの子たちＡおよびＢを考えると、力Ｆ（１，Ｃ）はＦ（１，Ａ）に等しく、Ｆ（２，Ｃ）はＦ（２，Ｂ）に等しい。更に、以下に記載されるように、Ｆ（Ｃ）から始まって、成分Ｆ（２，Ａ）およびＦ（１，Ｂ）もまた、得られてもよい。それゆえ、Ｆ（Ａ）およびＦ（Ｂ）の成分は、Ｆ（Ｃ）から全体的に得られてもよい。

一旦ノードＣの加速度が計算されると、関数Ｕｐｄ＿Ｄｙｎ（）は、１０１８および１０２０で、付録Ａの公式２３に基づく関数Ｃｈ＿Ｆ（）によって、ベクトルＦ（２，Ａ）およびＦ（１，Ｂ）の計算を続行する。

次に、ノードＡおよびＢの加速度数的指標が、１０２２および１０２４で計算され、ノードＡおよびＢは、１０２６で、Ａｃｃ（Ａ）およびＡｃｃ（Ｂ）の値の関数として、優先度待ち行列Ｑ＿ｐｒｉｏに戻される。シミュレーションの精度を更新するために、１０２８で、加速度ｑｄｄ（Ｃ）の平方の値がεから減算される。最後に、ノードＲが、１０３０で待ち行列Ｑ＿ｐｒｉｏからアンスタッキングされ、関数の再帰および木における下降を確実にするために、関数Ｕｐｄ＿Ｄｙｎ（）が、１０３２でＲに関して呼び出される。

待ち行列Ｑ＿ｐｒｉｏは、最も重要であるノードを迅速に判定するために、加速度数的指標の値に基づいて、ノードを分類する。従って、ノードの加速度数的指標が、その子ノードたちの加速度の平方の和を表す場合には、関数は、εを最も迅速に減少させるノードにおいて段階的に下降し、従って、シミュレーションを加速させる。

この関数は同時に２つのタスクを実行することに留意されたい。実際には、ノードのアクティビティは、加速度数的指標の値に基づいている。一定のノードの加速度の計算をしないことおよびデータＡｃｔｉｖｅ＿Ｆｌｇ（）を使用することは従って、追加計算コストを生じることなく、アクティビティを考慮する以降のループからそれらを除去することを可能にする。

これは、下から上に木をスキャンする関数がアクティブノードにおいてのみ再帰的に下降することによって始まるという事実によって特に可能となる。

それゆえ、上記の関数の集合は、アクティブノードを選択することによって、木の最小スキャンを確保し、ノードのいくつかのデータの選択的な更新を構成する。

また、シミュレーションの精度は、ここでは最大化速度エラーを表すパラメータεｍａｘによって保証されることに留意されたい。シミュレートされるノードの数の仕様（指定；ｓｐｅｃｉｆｉｃａｔｉｏｎ）または他の数的指標などの他の手段を用いてもよい。

動的データの更新が完了すると、関数Ｕｐｄ＿Ｇｅｏ（）が、シミュレーションループを終了する。実際には、前述したように、ノードにおける相互作用データが、各ノードに特有の局所的な参照点に関して計算される。

実際には、導出することができるノードの加速度および位置もまた、相対的または固有である。シミュレーションの結果を表示することができるようにするため、および木の種々のスキャンにおいてデータを上に（または下に）送り返すことができるようにするために、ここまでで述べなかった通過マトリックスがここで必要とされる。

図４における関数Ｕｐｄ＿Ｐｏｓ（）におけるＯＢＢの実際の位置を計算するため、または図７におけるステップ７３２および７３４において力Ｆ（Ｃ，Ｒ）を更新するために用いられるのが、これらの通過マトリックス（ｐａｓｓａｇｅ ｍａｔｒｉｃｅｓ）である。

これらのマトリックスを更新するために、関数Ｕｐｄ＿Ｇｅｏ（）は、１１０２でサブ関数Ｕｐｄ＿Ｈｙｂ＿ｑｄｄ（）から始まる。関数Ｕｐｄ＿Ｈｙｂ＿ｑｄｄ（）は、関数Ｕｐｄ＿Ｄｙｎ（）で得られた固定化を考慮するために補正される動的係数を計算する。次に、ノードの加速度ｑｄｄ（Ｃ）は、補正された動的係数によって再計算される。この関数によって実行される動作およびｑｄｄ（Ｃ）の計算におけるそれらの統合は、論文ＳＩＧＧＲＡＰＨ’０５の４節および５節に記載されている。

本発明の好ましい実施形態に記載されているが、関数Ｕｐｄ＿Ｈｙｂ＿ｑｄｄ（）は、すべての場合において絶対的に必要というわけではない。任意に、関数Ｕｐｄ＿Ｇｅｏ（）はこの関数を含まなくてもよく、１１０４で直接的に処理されてもよい。

関数Ｕｐｄ＿Ｇｅｏ（）は、１１０４で、関数Ｕｐｄ＿ｑｐｏｓ（）で続行され、それらの加速度に基づいて、ノードの固有の位置を更新する。これは、付録Ａの式１４に対応する基本的な時間積分を表す簡単な計算である。たとえば、補助加速度の計算を用いて、ノードの固有の位置を更新するための他の方法が、用いられてもよい。

最後に、関数Ｕｐｄ＿Ｇｅｏ（）は、１１０６で、関数Ｕｐｄ＿ＣＴ＿Ｍａｔ（）で終了し、ノードの更新された固有の位置に基づいて、上述した内部マトリックスを更新する。これらのマトリックスおよびそれらの更新は、ＳＰＭ’０５の５節に更に詳細に記載されている。

上記において、相互作用データおよび幾何的データは主に、本質的に、すなわち、すべての事例において、問題のノードと関連付けられる局所的な参照点に関して計算される。

このことは、係数Φ（Ｃ）およびΨ（Ｃ）および局所的な相互作用力などオブジェクトの相対的位置にのみ左右されるデータを再計算する必要性がないことを意味する。従って、実世界の座標への移行は、ノードの実際の位置を計算するために必要とされるだけである。

他の実施形態において、実世界における座標のデータを毎回動作させることが可能であり、アクティブでないノードに関してのみ固有のデータを保持する。

本発明は二分木による表現に関して記載してきたが、他のタイプの木、たとえば、三分木またはｎ分木などを用いることができる。また、匹敵するスキャンコストでアクティブノードおよび非アクティブノードを弁別することを可能にするのであれば、他のタイプの表現を用いることも可能である。

上述した関数は、本発明を実行するための主要なステップを含む。これらは、本発明を実装するコンピュータプログラムを製作するための基礎として、当業者によって用いられてもよい。そのようなプログラムは、Ｃ＋＋言語または当業者に周知である適切な任意の他のコンピュータ言語で設計されてもよい。

添付書類

Claims (10)

1. 相互作用するオブジェクト集合をシミュレートするコンピュータ装置であって、
   −前記オブジェクト集合の木表現を含むように適合され、各中間ノードが、その子ノードのデータに左右される動的データ、幾何的データおよび相互作用データに関連付けられるメモリ（８）と、
   −シミュレーションコントローラ（４）であって、反復サイクルにおいて
   ＋オブジェクトおよびオブジェクトの部分集合に関する相互作用データのディストリビュータ（１０）と、
   ＋問題の相互作用データおよび幾何的データの関数として、相互作用を受けるノードに関する前記木表現のスキャンによって、前記動的データを更新するための機構（１２）と、
   ＋前記更新された動的データの関数として、前記相互作用の対象となるノードに関する木表現のスキャンによって、前記幾何的データを更新するための機構（１４）とを起動するシミュレーションコントローラ（４）を有し、
   −前記メモリ（８）はまた、前記ノードの少なくともいくつかと関連付けられる局所的な相互作用データを有し、
   −前記相互作用データディストリビュータ（１０）は、問題の子ノードの局所的な相互作用データの関数として、ノードの相互作用データ項目を更新するために、前記相互作用の対象となるノードに関する木表現のスキャンによる相互作用更新機構（２０）を有することを特徴とする、コンピュータ装置。
2. 請求項１に記載の装置であって、
   −前記局所的な相互作用データは、局所的に相互作用するノードを表す結合を含む相互作用リストを有し、
   −前記相互作用データ更新機構は、
   ＋前記相互作用リストのデータを更新する関数（３２）と、
   ＋前記更新された相互作用リストのデータの少なくとも一部に基づいて、前記相互作用データを更新する関数（３４）を含むことを特徴とする装置。
3. 請求項２に記載の装置であって、
   −前記メモリは、前記ノードの少なくともいくつかに関して、関連ノードの周囲の相互作用空間を表す有向ボックスデータを含み、
   −前記相互作用データを更新するための機構は、有向ボックスデータを更新するための関数（３０）を有し、前記相互作用リストを更新するための関数は、前記更新された有向ボックスデータの少なくとも一部に基づいて動作することを特徴とする装置。
4. 請求項１〜３のいずれか一項に記載の装置であって、
   −前記メモリは、前記ノードの少なくともいくつかに関して、動的係数データを含むことと、
   −前記動的データを更新するための機構は、
   ＋前記動的係数データを更新する関数（２６）と、
   ＋前記更新された動的係数データに基づいて、前記動的係数を更新する関数（２８）とを含むことを特徴とする装置。
5. 請求項１〜４のいずれか一項に記載の装置であって、
   −前記記憶メモリは、前記ノードの少なくともいくつかに関して、活性マーカ（Ａｃｔｉｖｉｔｙ＿Ｆｌｇ（））を表すデータを有し、
   −前記動的データを更新するための機構（１２）は、前記処理するノードの活性マーカ（Ａｃｔｉｖｉｔｙ＿Ｆｌｇ（））を更新することもでき、
   −前記相互作用データを更新するための機構、動的データ機構および、幾何的データを更新するための機構の中から選択される少なくとも１つの前記機構が、前記木表現をスキャンするように設計され、アクティブだと印されない前記ノードを無視することを特徴とする装置。
6. オブジェクト集合の木表現が保持される、相互作用する前記オブジェクト集合の挙動をシミュレートする方法であって、
   各中間ノードが、その子ノードからのデータに左右される動的データ、幾何的データおよび相互作用データと関連付けられ、
   ａ．前記オブジェクトの一部およびオブジェクトの部分集合にわたって前記相互作用データを分配するステップと、
   ｂ．相互作用の対象となるノードに関する木表現をスキャンし、問題の前記相互作用データおよび幾何的データの関数として、これらのノードの動的データを更新するステップと、
   ｃ．相互作用の対象となるノードの場合には、再び前記木表現をスキャンし、前記ステップｂ．において更新された前記動的データの関数として前記幾何データを更新するステップとを有するサイクルが反復され、
   前記ステップａ．は、
   ａ１．問題の子ノードの局所的な相互作用データの関数として、これらのノードの前記相互作用データの更新によって、前記相互作用の対象となるノードに関する木表現の予備スキャンを有することを特徴とする方法。
7. 請求項６に記載のシミュレートの方法
   前記ステップａ１は、
   ａ１ａ．前記ノードの少なくとも一部と関連付けられる局所的な相互作用データを形成する、局所的に相互作用するノードの結合を含む相互作用リストの更新と、
   ａ１ｂ．前記更新された相互作用リストの関数とした、相互作用データの更新を有することを特徴とするシミュレートの方法。
8. 請求項７に記載のシミュレートの方法であって、
   前記ステップａ１は、
   ａ１ａ１．前記ノードの少なくとも一部と関連付けられ、関連ノードの周囲の相互作用空間を表す有向ボックスデータの更新と、
   ａ１ａ２．前記更新された有向ボックスデータの関数とした、相互作用リストの更新を含むことを特徴とするシミュレートの方法。
9. 請求項６〜８のいずれか一項に記載の方法であって、
   前記ステップａ、ｂおよびｃの少なくとも１つは、前記木表現をスキャンし、前記ノードの少なくとも一部と関連付けられる活性マーカの関数として、前記ノードの少なくとも一部を無視すること含むことを特徴とする方法。
10. プログラムコード部分／手段／命令を含むコンピュータプログラム製品であって、前記プログラムをコンピュータ上で実行するときに、請求項６〜９のいずれか一項に基づく処理のステップを実行するプログラム製品。

Images