(57)【要約】  本発明は、粒子位置ソルバーであり、このソルバーによって、粒子は、無効状態で固定時間の時間ステップの終わりに達し、次に、有効状態の方へ押し進められる。これによって、ソルバーは、シミュレーション結果が有効な挙動に近づいている間、シミュレーションを継続することが可能になる。粒子衝突計算は、いくつかの衝突を無視するかまたはそれらを組み合わせる非シーケンシャルモデルの採用によって、単純化される。シミュレーションの速度がまた、ソルバー計算ループの外部でいくつかの動作を実行することによって、および専用のデータ構造を用いることによって改善される。
2008541203.tif 000002
【特許請求の範囲】
【請求項１】
粒子の動的運動をシミュレートし、粒子状態を無効にさせるステップと、
前記粒子状態を有効状態へ向かって調節するステップと、
を含む粒子シミュレーション方法。
【請求項２】
前記粒子が、共にリンクされたときに、球、エッジ、三角形および表面を含む基本要素を含む、請求項１に記載の方法。
【請求項３】
前記粒子が、エッジ、三角形もしくは四面体またはそれらの組み合わせを用いて接続される、請求項１に記載の方法。
【請求項４】
前記粒子が、エッジ、三角形もしくは四面体またはそれらの組み合わせを用いて共にリンクされる、請求項１に記載の方法。
【請求項５】
前記粒子が、布を表現するようにリンクされる、請求項１に記載の方法。
【請求項６】
前記シミュレーティングが、単一の固定時間ステップをシミュレートする、請求項１に記載の方法。
【請求項７】
前記シミュレーティングが、
粒子衝突を決定するステップと、
前記粒子に制約を適用するステップと、
を含む、請求項１に記載の方法。
【請求項８】
前記適用が、静止長さを有する同じ粒子にリンクされた非接続粒子間にリンクを加える、請求項７に記載の方法。
【請求項９】
前記適用が、エッジに隣接する三角形間の角度を計算して曲げ制約を実現する、請求項７に記載の方法。
【請求項１０】
角度が面法線間で維持される、請求項７に記載の方法。
【請求項１１】
前記決定が、
時間ステップの始めおよび終わりに符号付き体積を計算するステップと、
前記符号が変化した場合に衝突が生じたことを決定するステップと、
を含む、請求項７に記載の方法。
【請求項１２】
前記決定が、前記粒子に対して厚さを仮定する、請求項７に記載の方法。
【請求項１３】
前記決定が、時間ステップ内の最小衝突時間での衝突の衝突速度として、粒子の最終速度を決定する、請求項７に記載の方法。
【請求項１４】
前記決定が、粒子の衝突速度の時間加重平均として、粒子の最終速度を決定する、請求項７に記載の方法。
【請求項１５】
前記決定が、非シーケンシャルモデルを用いて粒子の最終速度を決定する、請求項７に記載の方法。
【請求項１６】
前記調節が、粒子を有効状態へ移動させるための方向および速度を決定することを含む、請求項１に記載の方法。
【請求項１７】
前記方向が、最短有効点方向を含み、前記速度が、前記粒子を分離する分離速度を含む、請求項１６に記載の方法。
【請求項１８】
前記調節が、粒子が重なり合うか否かを決定する、請求項１に記載の方法。
【請求項１９】
前記無効状態が、別の粒子と重なり合う粒子を含む、請求項１に記載の方法。
【請求項２０】
各粒子のための境界球を決定することおよび重なり合う境界球と粒子を対にすることによって、衝突ペアを決定することをさらに含む、請求項１に記載の方法。
【請求項２１】
前記衝突ペアが、ハッシュテーブルを用いて計算される、請求項２０に記載の方法。
【請求項２２】
前記衝突ペアが、スフィアツリーを用いて計算される、請求項２０に記載の方法。
【請求項２３】
衝突候補が、粒子半径の合計の最小値に等しい衝突長さと静止状態の粒子間の距離を用いて決定される、請求項２０に記載の方法。
【請求項２４】
三角形によってリンクされた粒子を含む布の動的運動をシミュレートし、かつ粒子状態を無効にさせるステップであって、時間ステップの始めおよび終わりに符号付き体積を計算するステップと、前記符号が変化した場合に衝突が生じたことを決定するステップと、時間ステップ内の最小衝突時間での衝突の衝突速度として、粒子の最終速度を決定するステップとを含む粒子衝突を決定するステップと、曲げを制御する静止長さを有する同じ粒子にリンクされた非接続粒子間にリンクを加えることによって、曲げ制約を前記布に適用するステップと、を含むステップと、
前記粒子状態を有効状態へ向けて調節するステップであって、粒子を有効状態へ移動させるための方向および速度を決定することを含み、前記方向が、最短有効点方向を含み、前記速度が、前記粒子を分離する分離速度を含むステップと、
を含む粒子シミュレーション方法。
【請求項２５】
粒子の動的運動をシミュレートし、有効状態における前記粒子の第１の画像を表示するステップと、
前記粒子の動的運動をシミュレートし、粒子状態を無効にさせ、前記無効状態における前記粒子の第２の画像を表示するステップと、
前記粒子の動的運動をシミュレートし、前記粒子状態を有効状態へ向けて調節し、前記有効状態における前記粒子の第３の画像を表示するステップと、
を含む粒子シミュレーション方法。
【請求項２６】
有効状態における粒子の第１の画像と、
無効状態における前記粒子の第２の画像と、
前記有効状態における前記粒子の第３の画像と、
を含むディスプレイ。
【請求項２７】
粒子の動的運動をシミュレートし、粒子状態を無効にさせ、前記粒子状態を有効状態へ向けて調節するコンピュータと、
前記シミュレーションを表示するディスプレイと、
を含む装置。
【請求項２８】
前記ディスプレイが、有効状態における粒子の第１の画像、無効状態における前記粒子の第２の画像、および前記有効状態における前記粒子の第３の画像を表示する、請求項２７に記載の装置。
【請求項２９】
粒子シミュレーションプロセスを介してコンピュータを制御するためのコンピュータ可読記憶装置であって、
粒子の動的運動をシミュレートし、粒子状態を無効にさせるステップと、
前記粒子状態を有効状態へ向けて調節するステップと、
を含むコンピュータ可読記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、粒子系の状態が無効状態にある間に、それを絶えず改善する粒子ベースのソルバーに関する。
【背景技術】
【０００２】
アニメーション動作のためなど、シミュレーションで用いられる従来の粒子系は、ステップの開始時に粒子の全てが有効状態にあると仮定して、各粒子運動計算ステップを始める。各ステップにおいて、系は、粒子、エッジおよび表面が重なり合わない有効状態に粒子の全てが達するまで、粒子の位置および速度に対して作用しあう。従来の系は、制約または他の要因ゆえに、全ての粒子に対して有効状態に到達できない状況に至った場合には、それは失敗する。失敗は、たとえば系が無限ループに入るか、または一枚の布にある程度しわがよるなど、シミュレーションが予想外に振る舞う、シミュレーションの「クラッシュ」に帰着する。その結果、従来の粒子系は、しばしば、粒子の最終位置を計算するために長い時間を要する場合がある。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
粒子が無効状態に帰着した場合に失敗せず、かつ系の状態を絶えず改善しながら、よりコスト的に効率よく計算を実行する系が必要とされている。
【課題を解決するための手段】
【０００４】
本発明の一側面は、シミュレーションの失敗なしに粒子を無効状態に入らせる系を提供することである。
【０００５】
本発明の別の側面は、シミュレーションをよりコスト的に効率よくするために、計算を単純化する系を提供することである。
【０００６】
本発明の別の側面は、粒子系に対する全ての制約が、同じ反復ループで処理されることである。
【０００７】
本発明の別の側面は、任意の時間ステップが可能なことである。
【０００８】
そのシミュレーションの別の側面は、異なる現象が、制約された粒子を用いて、統一された枠組みで処理されることである。たとえば、布、剛体および流体の相互作用が、同じ枠組み内で全て同時に処理される。
【０００９】
上記の側面は、固定時間ステップ粒子位置ソルバーによって得ることができるが、このソルバーによって、粒子は、無効状態で時間ステップの終わりに達し、次に、有効状態の方へ押し進められる。これによって、ソルバーは、シミュレーション結果が有効な挙動に近づいている間、シミュレーションを継続することが可能になる。粒子衝突計算は、非シーケンシャルモデルの採用によって単純化される。シミュレーションの速度は、ソルバー計算ループの外部でいくつかの動作を実行することによって改善される。
【００１０】
これらは、続いて明白になる他の態様および利点と共に、以下でより完全に説明され権利請求される構成および動作の詳細に存在し、また本明細書の一部を形成する添付の図面が参照されるが、これらの図では、全体にわたって同様の数字が同様の部分を指す。
【発明を実施するための最良の形態】
【００１１】
序文
ここの解説では、相互作用粒子のためのダイナミックスソルバーを説明する。ソルバーの目的は、種々様々な相互作用様態の動力学を統一的枠組みで計算することである。ソルバーは、長編特作映画の特殊効果からゲームのリアルタイムシミュレーションに及ぶコンピュータグラフィックスの用途を主なターゲットにするが、シミュレーションを通した物理系の初期のプロトタイプおよび試験などの他の目的のために用いることができ、たとえシミュレーションが、最終的な検証には十分に正確でなくても、それは、初期の設計決定を下す際に役立ち得る。これらのターゲット用途は、液体、剛体および布などの広範囲な自然現象の、物理的に妥当と思われるシミュレーションを必要とする。これら全ての現象が、潜在的に同時に相互作用し得るので、それらを単一の枠組みで取り扱うことが重要である。
【００１２】
ダイナミックスソルバーが直面する難問のいくつかを、布シミュレーションの例を用いて、以下で解説する。最初に、リボンまたは一点の衣服のような一枚の布の動きは、それが熟知されているので、かなり簡単に見えるかも知れない。しかしながら、布は、高自己変化系の例である。布ソルバーが直面する群を抜いて最大の難問は、布が自身および環境の両方と衝突するということである。結果として、シミュレーションの全てのステップで、多くの相互作用を処理しなければならない。理想的には、布が、自身と自己交差したり、または環境におけるどんな物体にも貫通しないのが望ましい。また、布の外観は、折り目およびしわの外観のために、非常に複雑である。したがって、布ソルバーは、非常に大きなデータセットを取り扱うことができなければならない。特に、ソルバーのコスト（計算時間）は、複雑さの増加に伴い、うまくスケーリングすべきである。これは、高価で複雑なソルバーを除外する。単純で効率的なソルバーが好ましい。布をシミュレートするのを困難にする別の要因は、布が非常に伸びにくいということである。このために、たとえば接続されたばねの系として布をモデル化することが難しくなる。なぜなら、硬いばねは、不安定性を回避するために高価なソルバーを必要とするからである。最後に、ソルバーが布の長期的な挙動を再現することが、重要である。たとえば、重力だけの影響下で落下した一枚の布は、完全な静止状態になるはずである。これらの難問の全てを完璧に取り扱うことができる布ソルバーは、存在するようには少しも思えない。したがって、今日、布シミュレーションは、まだコンピュータグラフィックス分野内における研究の活動的領域である。本明細書で説明する本発明の背後にある最初の動機は、新規の布ソルバーを構築することだった。続いて、布ソルバーを、粒子などのより大きな種類の現象に拡張可能なことが理解された。
【００１３】
本明細書で説明するアプローチの主な特徴の１つは、系により、ダイナミックスソルバーが、各時間ステップにおいて、自身と自己交差するかまたは別の物体と交差する布などの無効状態を、復帰させることが可能になるということである。シミュレーションの各時間ステップの後に有効状態を保証しようとするのではなく、系は、力学状態を有効状態の方へ推し進めようとする。ソルバーは、シミュレーションの単一時間ステップにわたって布の状態を徐々に改善する。系の有効状態が計算されるとすぐに、または状態を改善するために系がどれだけの時間を費やすことができるかについて、ユーザ設定した時間制限に系が到達した場合には、ソルバーは停止する。このアプローチには、いくつかの利点がある。第１に、それによって、より速い計算時間が可能になる。いくつかの用途では、シミュレーションは、無効状態にあってもよい。たとえば、アニメーション作成の初期段階では、アニメータは、形状の一般的な動きの感触を得ることにより関心がある。その段階では、形状の外観における小さな欠点より、速いフィードバックがより重要である。このアプローチの別の利点は、制約の全ては満たすことができない状況において、ソルバーがロックされないということである。これらの状況は、アニメーション環境において、環境および作業集団が、必ずしも物理的に一貫していないために生じる。最後に、最初から有効状態を仮定するソルバーは、無効状態を与えられた場合には、（少なくとも一般的な体験では）通常、惨めに失敗する。要約すれば、シミュレーションを「失敗」させることによって、より速く、より堅固で、実行がより容易なソルバーが得られる。なぜなら、それは、常に有効状態を解決しようと試みる系では許容できそうにない近似を可能にするからである。
【００１４】
表記法
本明細書で解説するアルゴリズムをより読みやすくするために、次の表記法を採用する。配列の特定の要素を選択するために、インデックスセットを含む変数が用いられる。たとえば、Ｉ＝（０，１００，３）の場合には、ステートメントａｒｒａｙ［Ｉ］＝０は、配列のエントリ０、１００および３をゼロに設定するだけである。インデックスセットが、ａおよびｂ間の連続するインデックスのセットである場合には、表記法ａ．ｂが用いられる。たとえば、次のステートメントａｒｒａｙ［１．．Ｎ］＋＝１は、１とＮとの間のインデックスを備えた配列の各要素に１を加える。これらの表記法によって、アルゴリズムの多くはよりコンパクトになり、したがって、より読みやすくなる。当業者にとって、アルゴリズムをＣ＋＋などの任意のコンピュータ言語に翻訳することは、簡単なはずである。
【００１５】
ソルバーの基本構造
本明細書で解説するモデルにおける形状は、エッジ、三角形および四面体を用いて接続される粒子の集まりである。図１は、ダイナミックスソルバーによって取り扱われる、エッジ、三角形および四面体から構成された形状のいくつかの例２０および２２を示す。ソルバーは、これらの要素がどのように共に接続されて物体を形成するか、および従来的に取り扱われると予想される限り、物体がどのように取り扱われるかについての仮定をしない。布は、たとえば、三角形メッシュとしてモデル化され、また三角形メッシュは、従来の再分割方法を用いて、より精細な解像度の画像のために再分割することができる。
【００１６】
系の動力学は、粒子インデックスｉによりインデックスを付けられて配列に格納された粒子に、異なる特性を割り当てることによってモデル化される。ソルバーは、Ｎを粒子の合計数とする。各粒子の動力学は、その位置ｐｏｓ［ｉ］および速度ｖｅｌ［ｉ］によってモデル化される。他の特性には、逆質量ｉｎｖ＿ｍａｓｓ［ｉ］および厚さｒａｄｉｕｓ［ｉ］が含まれる。さらに、以下でより詳細に説明するが、ソルバーは、各粒子に関連するいくらかの追加データを必要とする。
【００１７】
形状はまた、環境をモデル化する表面と相互作用する。必要とされる特性は、空間における任意の所定の点に最近接の（または最短距離の）表面上の点の計算が、その表面によって可能になるということである。必要とされる別の特性は、表面のどちら側に点が位置するかを決定する、各点における法線である。したがって、形状と相互作用する全ての表面は、次の関数を有するべきである。
【００１８】
ｃｌｏｓｅｓｔ＿ｐｏｉｎｔ（ｓｕｒｆ，ｐｏｓ，ｃｐ，ｎｏｒｍ），
この関数は、当業者によって提供され得るが、位置ｐｏｓからの表面ｓｕｒｆにおける最近接点ｃｐおよび法線ｎｏｒｍを返す。
【００１９】
かかる表面の単純な例には、平面および球が含まれる。三角形メッシュは、別の重要な例である。この場合には、エッジおよび頂点における法線は、それらの隣接するフェースの法線の平均として定義される。図２は、表面およびそれらの最近接点の２つの例４０および４２を示すが、これらの最近接点は、空間における法線と共に、空間における任意の点に対して表面上の最近接点を返す関数によって定義される。場合によっては、法線が、最近接点への正規化された点方向と必ずしも等しくないことに留意されたい。
【００２０】
シミュレーションは、一度に一フレーム（または時間ステップ）計算される。ソルバーは、シミュレーションの各フレームに対して呼び出され、粒子に適用された外力を入力として取る。これらは、ｆｏｒｃｅと呼ばれる配列に格納される。本明細書で解説するアプローチによるアニメーションループの一般的な構造は、次のとおりである。
【００２１】
do_initializations ()
while (simulating)
get_forces (force)
do_solve (force)
do_damping ()
end
第１のルーチンｇｅｔ＿ｆｏｒｃｅｓ（ｆｏｒｃｅ）（図３の６０も参照されたい）は、全シミュレーションのために一度計算する必要があるだけの、ソルバーで必要とされる量を処理する。このソルバーを用いるアプリケーションは、重力および空気抵抗などの外力を計算する役割を果たす。従来のソルバーは、（以下でより詳細に解説するように）衝突に関連する時間サブステップにおいて動作するので、この力の入力が、従来のソルバーでは時間ステップ内に複数回生じなければならないことに留意されたい。結果として、本明細書で説明するソルバーが、より効率的になる。
【００２２】
最後のルーチンｄｏ＿ｄａｍｐｉｎｇ（）は、粒子の速度を抑える。このステップは、粒子間の激しい衝突による大きなオーバーシュートを除去するのに役立つ。したがって、いくつかの状況において、シミュレーションステップの終わりにこのルーチンを呼び出すことは、重要である。
【００２３】
シミュレーションは、通常、可変時間ステップを用いて進められる。以下の手法を簡単にしておくために、本発明者らは、この時間ステップが常に１に等しいと仮定する。ソルバーは、量のいくつかを、それらの単位が時間に依存する場合には、それ相応にスケーリングすることによって、他の時間ステップを取り扱うことができる。この仮定によってまた、ソルバーは、安定性を達成するように小さな時間ステップに依存することを強いられない。
【００２４】
ソルバーには、おおよそ３つの基本ステップがある。図３に示すように、第１のステップ６２において、外力が速度に加えられる。第２のステップ６４において、衝突および制約が、速度を修正することによって取り扱われる。最後に、第３のステップ６６において、粒子の位置が、修正された速度を用いて更新される。より正確には、
do_solve (force)
vel[1..N] += inv_mass[1..N]*force[1..N]
prev_vel[1..N] = vel[1..N]
compute_pairs()
for it=1 to it_max do
do_collisions_space_time()
do_constraints ()
if nothing happened then break
end
pos[1..N] += prev_vel[1..N]
end
である。
【００２５】
ｆｏｒｃｅ配列に供給される力は、たとえば重力および空気抵抗などの外力をモデル化する。これらの力には、たとえば剛性および曲げによる内力は含まれない。これらの力をこのように処理することは、制御されない結果を生じる不安定なシミュレーションに帰着する可能性がある。
【００２６】
アルゴリズムの非常に重要なステップは、衝突および内力を解決する、アルゴリズムのループである。このループの各反復は、シミュレーションの状態を改善しようと試みる。ループ内部の動作には、２つの基本ステップが含まれる。第１のステップにおいて、ソルバーは、現在のシミュレーションステップにわたって形状間に生じる全ての衝突を解決しようと試みる。これには、時空間を通して、形状における要素の経路を追跡することが含まれる。第２のステップは、穏やかな制約を介して、伸びおよび曲げなどの内力を解決し、衝突ステップによって解決されない形状間の貫通を解決する。反復ループは、粒子の修正が生じなかった場合（「何も起こらなかった」）か、または最大数ｉｔ＿ｍａｘに達した場合に終了する。この最後のパラメータは、アプリケーションに、ソルバーで費やされる最大時間を制御させる。典型的には、これは５〜２０反復間で設定されるであろう。
【００２７】
この時点で、本明細書で解説するアプローチを、他の従来のシミュレーション戦略と対比することができる。本明細書で説明するソルバーの主な特徴の１つは、ソルバーが、同じ時間ステップ（本発明者らの場合には、１に等しい）を用いて、シミュレーションを進めるということである。このアプローチは、時間ステップをサブサンプリングすることによって衝突をより正確に解決しようと試みる他の従来のソルバーとは非常に異なる。特に、サブステップが、第１の衝突までの時間に基づいている場合である。この従来のケースでは、全ての粒子は、常に、第１の衝突時間へ向かって進められる。次に、衝突は解決され、粒子は、再び更新される。このプロセスは、これ以上の衝突がないかまたは時間ステップの終わりに達するまで、反復される。この従来のアプローチに関して起こり得る問題は、多くの衝突がある場合に、このアプローチが潜在的にコストがかかる可能性があるということである。場合によっては、それは、系が多くの同時的衝突を伴う状況を解決することができない場合に、行き詰まってしまう可能性さえある。対照的に、本明細書で解説するソルバーは、サブステップを全く用いる必要がない。図４および５は、３つの相互作用粒子ａ、ｂおよびｃのケースに対する、本明細書で解説するアプローチ（図４）と従来の衝突イベント駆動シミュレーション（図５）との間の相違を示す。粒子は、水平方向に位置するように制約される。時間は、垂直方向に示される。したがって、時間ステップにわたって、粒子は底部から上端へ連続的な経路に沿って移動する。本発明の実施形態のアプローチでは、本発明者らは、時間にわたって各粒子の全ての衝突を解決し、次に、結果を組み合わせる。たとえば、粒子ｃに対して、２つの「可能な」経路が示される。他方で、衝突イベント駆動アプローチでは、衝突は、図５の２つのサブ時間ステップまたは衝突点によって示されるように、順次的に取り扱われ（順次衝突モデル）、それによって、各粒子に対して単一の「可能な」経路だけが可能になる。ソルバーの別の特徴は、反復の終わりに有効状態を保証する必要がないということである。この可能であることは、粒子が、順次衝突モデルに関連する位置で終了しない図４の粒子の最終位置によって、示される。序文で言及したように、これには、いくつかの利点がある。
【００２８】
次の項で、ソルバーの様々なコンポーネントをより詳細に説明する。
【００２９】
衝突ペアの計算
前述のように、形状は、点、エッジ、三角形および四面体から組み立てられる。形状が動いた場合には、ソルバーは、これらの基本要素間の相互作用を計算する必要がある。さらに、これらの基本要素には、それらに割り当てられた所定の厚さがある。したがって、点ではなく、本発明者らは、実際には球を処理している。厚さは、各粒子にとって変化する可能性があり、またｒａｄｉｕｓ配列に格納される。エッジ、三角形または四面体の任意の点における厚さは、それらの頂点で定義された厚さを補間することによって計算される。
【００３０】
基本要素間の起こり得る相互作用は、次のペアに制限される。球／球（ｓｓ）、球／エッジ（ｓｅ）、球／三角形（ｓｔ）およびエッジ／エッジ（ｅｅ）である。図６は、ソルバーで考慮される、異なるタイプのペアを表わす。三角形／三角形などの他の相互作用は、４つの基本タイプの組み合わせに属する相互作用のシーケンスに変えることができる。たとえば、２つの三角形間の完全な相互作用を取り扱うために、本発明者らは、第１の三角形の各球を第２の三角形に対して衝突させ、逆の場合も同様に行なう。さらに、本発明者らはまた、それらのエッジを衝突させる。これは、タイプ「ｓｔ」の６つの相互作用およびタイプ「ｅｅ」の９つの相互作用に帰着する。
【００３１】
各時間ステップにおいて、ソルバーは、４つのペア配列ｐａｉｒ＿ｓｓ、ｐａｉｒ＿ｓｅ、ｐａｉｒ＿ｓｔおよびｐａｉｒ＿ｅｅを計算する。ペア配列の各エントリは、インデックスセットである。各テーブルのためのインデックス番号およびそれらの意味は、次の通りである。
ｐａｉｒ＿ｓｓ：（ｉ０，ｊ０）            ：球ｉ０と球ｊ０の相互作用
ｐａｉｒ＿ｓｅ：（ｉ０，ｊ０，ｊ１）      ：球ｉ０とエッジ（ｊ０，ｊ１）の相互作用
ｐａｉｒ＿ｓｔ：（ｉ０，ｊ０，ｊ１，ｊ２）：球ｉ０と三角形（ｊ０，ｊ１，ｊ２）の相互作用
ｐａｉｒ＿ｅｅ：（ｉ０，ｉ１，ｊ０，ｊ１）：エッジ（ｉ０，ｉ１）とエッジ（ｊ０，ｊ１）の相互作用
これらの４つのペア配列は、単一のｐａｉｒ配列に組み合わされる。
【００３２】
ペア配列の計算は、一般に非常に費用がかかる。したがって、それらを反復ループの外部で計算するように処理しなければならない。これには、衝突による速度変化によって引き起こされる衝突ペアを含む全ての潜在的な衝突ペアを含むことが必要となる。幸運にも、粒子の質量がおおむね同一である場合には、粒子は、図７に示すように、その初期位置および初期速度（ならびに時間ステップの長さ）によって定義される（境界）球から逃れることができない。図７は、初期速度によって定義された球が、衝突の後でさえ、粒子がアクセスできる領域の境界を定めることを示す。特に、図７は、時間ステップにおいて衝突せず、かくして、その初期位置から最も遠くへ移動する粒子１２０と、時間ステップの中程で衝突する粒子１２２と、時間ステップの初期に衝突する粒子１２４とを示す。三角形およびエッジを伴うペアについては、ソルバーは、それらの粒子の境界球の境界を定める球を計算する。
【００３３】
潜在的な衝突ペアが、重なり合う境界球の各ペアに対して作成される。これらのペアを計算するための簡単だが高くつく方法は、全ての境界球を単に比較することである。明らかに、このアプローチは、多くの境界球がある場合には、高くつきすぎる。幸運にも、この動作は、空間データ構造を用いることによって、加速することができる。本明細書の後の方で（以下で解説する空間データ構造を参照されたい）、２つの可能なデータ構造を解説する。すなわち、ハッシュテーブルおよびスフィアツリーであり、これらは、この動作を加速することができる。しかしながら、ソルバーは、これらのデータ構造に制限されない。
【００３４】
自己衝突を解決する場合に、次の問題に遭遇した。外力を印加されずに静止状態にある形状を想像されたい。この場合に、形状は、静止状態に留まるはずである。しかしながら、２つの粒子の半径の合計が、静止状態におけるそれらの距離より大きい場合には、それらは、自己衝突して離れるように移動する。これは、形状の望ましくない膨張に帰着する。この問題を改善するために、ソルバーは、各球／球衝突ペアに「衝突長さ」を関連付ける。この長さは、衝突ペアの半径と、静止状態にあるそれらの間の距離との合計の最小値に等しい。これによって、外力が印加されない場合には、自己衝突が静止状態を変化させないことが保証される。衝突長さは、ｃｏｌｌ＿ｌｅｎｇｔｈと呼ばれる配列に格納される。これらの衝突長さの計算を加速するために、本明細書で説明するソルバーのアプローチは、シミュレーションの開始時に衝突ネイバーのリストを予め計算し、初期状態におけるそれらの隔離距離もまた計算する。ペアは追加されるたびに、ペアの粒子がネイバーかどうかを確認し、それに応じて、このペアのためにｃｏｌｌ＿ｌｅｎｇｔｈ［ｋ］を設定するために、チェックが実行される。
【００３５】
この動作において説明される全てのステップは、反復ループの直前に呼び出される関数ｃｏｍｐｕｔｅ＿ｐａｉｒｓ（）で計算される。
【００３６】
時空間衝突
反復ループにおける第１のステップは、時間ステップ内に生じる球、エッジ、三角形および表面間の衝突を解決することである。これらの衝突を解決するために、ソルバーは、各潜在的衝突ペアをよく調べ、衝突までの時間を計算する。この衝突が時間ステップ内に生じる場合には、対応する衝突反応が計算される。図４の例では、粒子ｃにとって２つの衝突が生じる可能性があり、ｃはｂと衝突し、またｃはａと衝突する。ソルバーは、反応を組み合わせた、２つの異なる非シーケンシャルモデル方式または実施形態を有する。第１の方式または実施形態は、好ましくは、最終速度を、最小衝突時間での衝突の衝突速度に設定する。図４において、これは、粒子ｂおよびｃのための最終衝突速度を、これらの粒子間の粒子の衝突に起因する最終衝突速度として設定し、粒子ａと粒子ｂの衝突速度が無視されることになる。これは、図４に示す方式である。第２の方式は、好ましくは、衝突速度の時間加重平均を計算する。第１の方法は、第２の方法より反応が良く、人工的制動を受けない。しかしながら、第２の方法は、単一の時間ステップにおける全ての相互作用を考慮するので、より確固としている。実際にどちらを用いるべきかは、用途に依存し、アニメータは、必要に応じて、これらの方式の間で選択することができる。このステップのインプリメンテーションは、次の通りである。
【００３７】
do_collisions_space_time ()
pre_collisions ()
do_pair_collisions ()
do_surface_collisions ()
post_collisions ()
end
ペアおよび表面間の衝突を取り扱う関数は、両方とも、ｕｐｄａｔｅ＿ｖｅｌｏｃｉｔｙと呼ばれる共通関数を通して速度を更新する。この関数ならびにｐｒｅ＿ｃｏｌｌｉｓｉｏｎｓおよびｐｏｓｔ＿ｃｏｌｌｉｓｉｏｎｓルーチンは、用いられる更新方式に依存する。ソルバーが第１の衝突を考慮するだけの第１の方式に対して、インプリメンテーションは、次の通りである。
【００３８】
pre_collisions ()
t_coll[1..N] = 1
end
update_velocity (l, new_vel, t )
if (t > t_coll) return
vel[l] = new_vel[l]
t_coll[l]=t
end
post_ collisions ()
prev_vel[1..N] = t_coll[1..N] *prev_vel[1..N] +
(1-t_coll[[1..N])*vel[1..N]
end
衝突速度の加重平均が用いられる第２の方法では、インプリメンテーションは、次の通りである。
【００３９】
pre_collisions ()
w_tot[1..N] = 0
coll_vel[1..N] = (0,0,0)
vel[1..N] = (0,0,0)
end
update_velocity (l, new_vel, t )
w = weight(t)
coll_vel[l]+=w* (t*prev_vel[l]+(1-t) *new_vel[l])
vel[l] += w*tmp_vel[l]
w_tot[l] += w
end
post_collisions ()
prev_vel[1..N] = coll_vel[l..N]/w_tot[1..N]
vel[1..N] /= w_tot[1..N]
end
通常、関数ｗｅｉｇｈｔ（ｔ）＝１−ｔであるが、それは、衝突までの時間または他のいくつかのパラメータに依存する任意の関数とすることができる。
【００４０】
ｓｓ：エッジ
ｓｅ：三角形
ｓｔ：四面体
ｅｅ：四面体
より高次元の要素にグループ化されたペアの表示については、図８を参照されたい。これによって、ソルバーは、各ペアに「符号付き体積」を割り当てることが可能になる。一次元空間におけるエッジは、その端点の差によって定義された符号付き体積を有する。同様に、三角形が、外積を用いて、二次元空間における符号付き面積を定義する。最後に、四面体が、三次元空間における符号付き体積を定義する。一般に、要素の体積は、列が同次座標における要素の点であるマトリックスの行列式として定義される。より正確には、要素がｎ点Ｐ０、Ｐ１、．．．Ｐｎ、を有する場合には、体積は、次のマトリックスの行列式である。
Ｐ０，１  Ｐ１，１．．．Ｐｎ，１
Ｐ０，２  Ｐ１，２．．．Ｐｎ，２
：        ：            ：
Ｐ０，ｎ  Ｐ１，ｎ．．．Ｐｎ，ｎ
１      １          １
ｖｏｌ（ｐａｉｒ）を、この体積を計算する関数とする。体積の有用性は、それが、ペアの要素が衝突した場合には、消失することに由来する。２つのエッジが衝突したときに符号を逆にして衝突の瞬間にゼロになる四面体の体積を示す、２つの衝突エッジのための、この事実に関して図９を参照されたい。この結果によって、各ペアの交点を計算する方法が提供される。第１に、時間ステップの始めおよび終わりに体積を計算する。次に、符号に変化がある場合には、ソルバーは、単純な直線補間を用いて、衝突の時間を見つけることができる。このアプローチは、要素が非常に薄い場合にはうまくいく。任意の厚さを取り扱うために、ソルバーは、同様に、ペアの２つの要素間の距離の２乗を考慮する。球については、これは、単に、それらの中心間の距離の２乗である。しかしながら、他の相互作用については、計算は、少しばかり複雑であり、本明細書の後の方で解説する（以下の基本要素間の距離を参照されたい）。この解説のために、本発明者らは、距離計算が関数ｄｉｓｔ２（ｐａｉｒ）において実行されると仮定する。衝突の時間を見い出すために、体積だけではなく、次の関数を考慮する。
【００４１】
ｃｏｌｌ＿ｆｕｎｃ（ｐａｉｒ）＝ｓｉｇｎ（ｖｏｌ（ｐａｉｒ））＊ｄｉｓｔ２（ｐａｉｒ）．
要素の組み合わされた厚さが、ｔｈｉｃｋに等しいと仮定すると、衝突時間を計算する手順は、次の通りである。
【００４２】
collision_time ( pair )
eO = pos[pair]
e1 = pos[pair]+prev_vel[pair]
vO = coll_func(eO)
v1 = coll_func(e1)
if v0*v1 > 0 return -1.0
t = (thick-v0)/(v1-v0)
end
この手順の長所は、それが非常に単純で、４つの全てのタイプのペアに対して働くということである。このアプローチは、ペアに関連する点が、時間ステップ中に直線軌道で移動すると仮定しないことに留意されたい。この仮定を用いると、「ｓｅ」のケースにおける衝突時間の計算は、二次方程式の解を必要とし、「ｓｔ」および「ｅｅ」のケースでは三次方程式の解を必要とするであろう。本方法は、最初はそれほど正確ではないように見えるかもしれない。しかし、線形経路を仮定することが、それ自体既に近似である。なぜなら、任意の時間期間に関して、時間期間中に印加される力は、粒子に曲線経路を移動させるからである。従来の線形近似などの近似を正確に解決するために高価な技術を用いることは、過剰である。
【００４３】
「ｓｓ」相互作用のために、ソルバーは、体積の公式を用いる前に、ラインに球を投影する必要がある。ランダムな方向を選択するのではなく、ソルバーは、時間０において球位置間の差が絶対値で最大である座標軸を用いるかまたは選択する。同様に、「ｓｅ」相互作用のために、ソルバーは、３つの点を平面上に投影するが、この平面の法線は、時間０において３つの点によって定義される法線の最大座標である。これらの選択によって、ソルバーは、たとえ点が接していないにもかかわらず体積がゼロである平面を選択しないことが保証される。
【００４４】
これらの断片を組み立てると、次のようなペア衝突のインプリメンテーションが得られる。
【００４５】
do_pair_collisions ()
for k=1 to n_pairs do
t = collision time ( pair[k] )
if t>=0 and t<=1 then
collide_pair ( pair[k], new_vel, t )
update_velocity ( pair[k], new_vel, t )
end
end
end
関数ｃｏｌｌｉｄｅ＿ｐａｉｒ（）は、ペアタイプに依存し、また本明細書の後の方でより詳細に説明される（以下の衝突反応の解説を参照されたい）。
【００４６】
表面との衝突を取り扱うために、ソルバーは、各粒子に対して、時間の始めおよびの終わりに、貫通深さを計算する。両方の点が表面の外にある場合には、する必要があることは何もない。交差がある場合には、衝突の時間を見い出して、ペア衝突と同様に進む。貫通深さは、表面上の最近接点および表面における法線方向から計算される。
【００４７】
penetration_depth ( pos, radius, p )
closest_point(surface[p],pos,cpos,norm)
diff = pos-cpos
len = length(diff)
if dot(diff,norm) < 0 then
return len+radius
else
return radius-len
end
end
貫通がない場合には、貫通深さは負である。次に、接触する時間のインプリメンテーションは、次によって与えられる。
【００４８】
collision_surface (i, p )
r = radius[i]
dO = penetration_depth(pos[i],r,p)
d1 = penetration_depth (pos[i]+prev_vel[i],r,p)
if dO < 0 and d1 < 0 return -1
if ( dO < 0) return (-r-d0)/(d1-d0)
return (r-dO)/(d1-dO)
end
これらの２つの関数を用いて、全ての球／ｓｐ−表面衝突を解決する。ここにインプリメンテーションがある。
【００４９】
do_surface_collisions()
for i=1 to N do
for p=0 to n_surfaces do
t = collision_surface(i,p)
if t>=0 and t<=1 then
collide surface(i,p,new_vel,t)
update_velocity(i,new_vel,t)
end
end
end
end
ｃｏｌｌｉｄｅ＿ｓｕｒｆａｃｅルーチンのより詳細な説明に関しては、本明細書の後の方の衝突反応の解説を参照されたい。
制約の取り扱い
時空間衝突を実行した後、ソルバーは、伸びおよび曲げなど、内部応力による任意の変形力を解決する必要がある。同時に、ソルバーは、衝突ステップで完全には解決されなかったいかなる貫通も解決する必要がある。
【００５０】
ソルバーは、最初に、全ての伸びおよび曲げ制約を解決する。両方とも、長さ制約だけを用いて取り扱うことができる。伸びを取り扱うために、粒子のペア間にリンクが作成されるが、ペアの静止長さは、静止位置のリンクの長さに等しい。これは、「ｓｓ」タイプの相互作用に類似している。同様に、ソルバーは、メッシュにおける各内部エッジのために、エッジによって共有されないフェースにおける２つの頂点間のリンクを加える。各内部のエッジ１８２の動きを制約する追加リンク１８０を加えることによって取り扱われる曲げ効果を示す実例について、図１０を参照されたい。
【００５１】
次に、ソルバーは、一度に１つのリンクの伸びおよび曲げ力を解決する。
【００５２】
do_internal_energy()
delta_vel[1..n] = (0,0,0)
w_tot[1..n] = 0
for k=1 to n_links do
i1 = pair[k][1]
i2 = pair[k][2]
p1 = pos[i1] + prev_vel[i1]
p2 = pos[i2] + prev_vel[i2]
diff=p2-p1
len = length(diff)
dlen = len - rest_length[k]
tmp_vel = 0.5*dlen*diff /len
delta_vel[i0] += tmp_vel
delta_vel[i1]-=tmp_vel
w_tot[i0] += 1
w_tot[il] += 1
end
delta_vel[1..n]/=w_tot[1..n]
prev_vei[1..n] += delta_vel[1..n]
vel[1..n] += delta_vel[1..n]
end
このルーチンは、変化が一つのリンクから他のリンクへ伝搬するように、何度も反復される。上記で示したインプリメンテーションの変形は可能である。たとえば、粒子速度は、ｄｅｌｔａ＿ｖｅｌに変化を蓄積せずに、「適所で（ｉｎ  ｐｌａｃｅ）」直接更新できる。これは、時空間衝突に対して上記で出会った異なるインプリメンテーションに類似している。
【００５３】
隣接するフェース間のクロスエッジを用いた曲げ制約のモデル化には、それが、図１１の（ａ）および（ｂ）に示すような２つの有効状態を有するという問題がある。隣接する三角形は、両者の間で反転する可能性がある。これらの理由で、ある値を有するようにフェース間の角度を制約するより正確なモデルが開発された。図に１１の（ｃ）に示すように、Ｐ０、Ｐ１、Ｐ２およびＰ３を、２つの隣接する三角形の点とする。最初に、次の３つのベクトルＤ１＝Ｐ１−Ｐ０、Ｄ２＝Ｐ２−Ｐ０、Ｄ３＝Ｐ３−Ｐ０を定義する。これらのベクトルから、三角形の法線を定義することができる。すなわち、Ｎ０＝Ｄ１×Ｄ２およびＮ１＝Ｄ３×Ｄ１である。これらのベクトルが全て正規化されると仮定する。これらのベクトルの表示については、図１１の（ｃ）を参照されたい。三角形間の角度は、角度＝（ｄｏｔ（（Ｎ０×Ｎ１），Ｄ１））に等しい。アングル０を安息角とする。次に、角度が安息角アングル０と等しくなるようなやり方で、４つの点を移動させたい。一般に、これは、おそらく多くの解を備えた複雑な問題である。本発明者らは、各点が、固定変位ｚで、ある方向に沿ってだけ移動するように制限されると仮定することによって、この問題の複雑さを低減する。１つの可能な選択肢は、次のＱ０＝Ｐ０−ｚＮ、Ｑ１＝Ｐ１−ｚＮ、Ｑ２＝Ｐ２＋ｚＮ０およびＱ３＝Ｐ３＋ｚＮ１を用いることであり、ここで、Ｎ＝（Ｎ０＋Ｎ１）／２は、法線間の中間のベクトルである（図１１の（ｃ）を参照されたい）。方向は、総和が０になることに留意されたい。変位ｚを変えることによって、角度の異なる値が得られる。本発明者らの目標は、角度が安息角アングル０に等しくなるようなｚの値を見つけて、法線間の角度が維持されるようにすることである。所望の角度に収束する従来の一次近似が用いられる。各角度を正確に解決しようと試みることは、時間を浪費する。なぜなら、１つの三角形ペアに対してなされた変更が、隣接するペアの結果に影響するからである。
【００５４】
形状間の貫通を取り扱うために、ソルバーは、全ての相互作用ペアにわたってループし、また基本要素が分離されるように、結果として生じる衝突速度に加えられる速度（分離速度）を生成する。これは、シミュレーションを改善する有効状態への移行に効果をもつ。要素の各ペアのために、ソルバーは、要素間の最近接または最短距離を計算し、重なり合いがあるかどうかを確認するためにチェックする。重なり合いがある場合には、ソルバーは、基本要素を分離する最近接もしくは距離（または有効点）方向に沿って分離速度を生成する。図１２は、これが、４つの全てのタイプの相互作用に対して、どのように行なわれるかを示すが、この場合には、要素間の重なり合いが、要素間の最短距離に基づいて分離速度を計算することによって取り扱われる。図１２における例のうち上部の横列は、重なり合い状況を表わし、下部の横列は、必要とされる分離に帰着する「プッシュ」を示す。平面のケースで、粒子の中心が、物体の外部にある場合には、速度は、Ｖ＝（ｒ−ｄ）Ｄ／ｄであり、ここで、Ｄは粒子の中心と最近接点との間のベクトル、ｒは粒子のサイズ、ｄは粒子と最近接点との間の距離であり、また粒子の中心が物体の外部にある場合には、速度は、Ｖ＝（ｒ＋ｄ）Ｄ／ｄである。
【００５５】
表面との重なり合いを取り扱うために、ソルバーは、上述のように、各粒子の貫通深さを計算し、また重なり合いの場合には、粒子を形状から押し出す速度を生成する。この手順はまた、表面のように、閉じた三角形メッシュとの重なり合いを解決するのに有用である。図１３は、このステップがどのように働くかを示すが、この場合には、表面のための貫通処理において、各粒子が、表面における最近接点への経路に沿って表面から押し出される。
【００５６】
空間データ構造
重なり合う境界球を効率的に見い出すために、少なくとも２つの空間データ構造を用いることができる。すなわち、ハッシュテーブルおよびスフィアツリーである。
【００５７】
ハッシュテーブルは、空間を均一なセルに分割するという考えに依存する。セルのサイズは、最大の境界球のサイズの２倍に設定される。各セルは、セル内に中心がある境界球のリストを格納する。ペアを見い出すためには、隣接セルにある境界球を比較するだけをすればよい。これにより、結果として計算時間の大きな節約がもたらされる。このアプローチの問題は、セルを含むグリッドがあることである。この場合に、ハッシュテーブルが役立つ。ハッシュテーブルは、セルの三次元グリッドの一次元表現である。ハッシュ関数は、グリッドの各エントリ（ｉ、ｊ、ｋ）を、一次元ハッシュテーブルのためのインデックスにマッピングする。ｎ−ｈａｓｈがハッシュテーブルのサイズである場合には、利用するのが好ましい１つの可能なハッシュ関数は、
ｈａｓｈ（ｉ，ｊ，ｋ）＝（（ｉｍｏｄ  ｐ）ｘｏｒ（ｊｍｏｄ  ｑ）ｘｏｒ（ｋｍｏｄ  ｒ））ｍｏｄ  ｎ＿ｈａｓｈ
であり、ここで、ｐ、ｑおよびｒは、いくつかの大きな素数である。当然ながら、多くのグリッドインデックスセットが、ハッシュテーブルの同じインデックスにマッピングされる。これは、ハッシュテーブルのエントリが、多くの異なるグリッドセルから境界球を有し得ることを意味する。しかしながら、それでも、境界球の比較数は、記憶装置にオーバヘッドのないアプローチより速くなる程度の多さである。
【００５８】
ハッシュテーブルアプローチの１つの欠点は、境界球が広く異なるサイズである場合に、遅くなるということである。これは、たとえばいくつかの粒子だけが非常に速く移動する場合またはエッジおよび三角形のサイズがとても変化する場合に起こる。したがって、ある実施形態において、ソルバーは、このケースによりよく適合された別のデータ構造、すなわちスフィアツリーを用いることができる。この考え方は、非常に単純である。ソルバーは、境界球のペアをより大きな球と再帰的に結び付ける。これは、ただ１つの球、すなわちスフィアツリーのルートが残されるまで行なわれる。ツリーのトポロジの計算は、ペア化のためのハッシュテーブルを用いて行なわれる。このステップは、多少高くつくが、しかしそれは、シミュレーションのために一度行なうだけでよい。ペアを計算するために、ソルバーは、球がツリーにおける球と境界を接するかどうかを確認するために再帰的にチェックする。そうでなければ、ソルバーは、球の子を全て無視することができる。そうである場合には、ソルバーは、子の境界球に対して継続する。ツリーにおける境界球の位置およびサイズは、どの時間ステップの開始時にも、再計算しなければならない。しかしながら、これは、ソルバーが葉の境界球を再設定し、次に、ツリーの残りのノードにおける境界球を再帰的に再計算する、かなり簡単な計算である。
【００５９】
基本要素間の距離
衝突の時間を計算するため、および基本要素間の貫通を解決するために、ソルバーは、それらのペア間の最短距離を計算することが必要である。２つの球面の場合はたいしたことではなく、最短距離は、それらの中心間の距離に等しい。球とエッジとの間の最短距離は、最初に、エッジを含む無限直線に球の中心を投影することによって計算される。点がエッジ内にある場合には、ソルバーは用がなく、エッジ内になければ、最近接点が、端点の１つである。同様に、球に対する三角形の最近接点は、最初に点を三角形の平面に投影することによって得られる。点が三角形の内部にある場合には、ソルバーは用がない。三角形の内部になければ、ソルバーは、三角形の３つのエッジの１つに最近接点を見い出す。２つのエッジ間の最近接点は、無限直線上の点を、それらの差が両方のラインに垂直になるように、見い出すことによって計算される。次に、これらの点は、ラインの外部にある場合には、エッジ上の最近接点に投影される。
【００６０】
衝突反応
最初に、ｎｏｒｍに等しい法線を有する平面に当たる、速度ｖｅｌの粒子の衝突反応を考える。衝突の挙動は、ｂｏｕｎｃｅパラメータおよびｆｒｉｃｔｉｏｎパラメータによってモデル化することができる。そのインプリメンテーションは、次の通りである。
【００６１】
collid_plane (vel, norm, new_vel )
vel_n = dot(vel,norm) *norm
vel_t = vel - vel_n
new_vel = friction*vel_t - bounce*vel_n
end
ここでは、非常に単純な摩擦モデルが用いられているが、実際には、より洗練されたモデルを用いることができる。はね返りが１度で、摩擦がゼロである場合には、粒子の速度の法線成分は、単に逆にされる。
【００６２】
ｃｏｌｌｉｄｅ＿ｓｕｒｆａｃｅルーチンは、ｃｏｌｌｉｄｅ  ｐｌａｎｅルーチンとほとんど同一である。なぜなら、粒子は、衝突点で接平面（ｔａｎｇｅｎｔ  ｐｌａｎｅ）と衝突するからである。そのインプリメンテーションは、次の通りである。
【００６３】
collide_surface( i, p, new_vel,t )
pos_coll = pos[i] + t*prev_vel[i]
closest_point (surf[p], pos_coll, cp, norm )
collide_plane ( prev_vel[i], norm, new_vel )
end
ペア衝突は、同様に処理される。最初に、ソルバーは、交点に点を移動させる。次に、ソルバーは、上記のように決定された点間の最近接距離に対応する「法線」ｎｏｒｍを計算する。基本要素が、ある厚さを有するので、この距離は、決してゼロに等しくはない。エッジおよび三角形については、最近接点の位置は、それらの頂点の一次結合である。これらの座標は、配列ｃｏｏｒｄに格納される。以下のいくつかの手法をより簡単にするために、本発明者らは、ペアにおける第２の基本要素の座標を無効にする。たとえば、２つの球の場合には、本発明者らは、このｃｏｏｒｄ［ｉ０］＝１およびｃｏｏｒｄ［ｉ１］＝−１を常に有し、他の全てのエントリはゼロに等しい。この配列を用いれば、相対速度の計算は、単に次の通りである。
【００６４】
ｒｅｌ＿ｖｅｌ＝ｄｏｔ（ｃｏｏｒｄ，ｐｒｅｖ＿ｖｅｌ）．
ｎｏｒｍおよびｃｏｏｒｄが、ｃｏｍｐ＿ｐａｉｒ＿ｄａｔａ（）と呼ばれるルーチンによって計算されると仮定する。ペアのための衝突は、次の通りである。
【００６５】
collide_pair (l, new_vel, t )
pos_coll[l] = pos[ｌ] + t*prev_vel[l]
comp_pair_ data (l, norm, coord )
rel_vel = dot(coord,prev_vel)
collide_plane ( rel_vel, norm, new_vel0)
w_tot = dot(coord,coord)
new_vel[l] = prev_vel[l] + coord[l] *new_velO/wtot
end
全体的プロセス
上記のように、好ましい実施形態において、本発明の全体的プロセス２４０（図１４を参照されたい）には、スフィアツリートポロジの計算２４２と、最近接ネイバーおよび衝突長さの決定２４４とが含まれる。系はまた、再分割トポロジを従来的に計算する（２４６）。次に、曲げリンクが決定される（２４８）。粒子および要素のための初期位置および速度が取得され（２５０）、ソルバー動作が実行される（２５２）。次に、再分割平滑化動作を実行するのが好ましい（２５４）。
表示
図１５ａ−１５ｈは、無効状態を通過し、また逆に有効状態へ展開するロッドおよび布をシミュレートする粒子系を示す表示を表わす。図１５ａは、ロッドが布に接近することを示す。図１５ｂは、ロッドが布を変形させ始めたことを示す。図１５ｃは、布がロッドの中へと姿を消し始める状態で、大きな変形下の布および布を貫通し始めたロッドを示すが、これは無効状態である。シミュレーションは、無効粒子状態に入るが、シミュレーションはクラッシュしない。図１５ｄは、貫通されたが引き裂かれなかった布を示すが、これは無効状態である。無効状態は継続するが、シミュレーションはクラッシュしない。図１５ｅは、ロッドが動きを逆にし、布を通して後退し始めることを示す一方で、シミュレーションはやはり無効状態にあるが、シミュレーションは再びクラッシュしなかった。図１５ｆは、後退が継続していることを示す。図１５ｇは、布がロッドから現われ、有効状態に戻ったことを示す。図１５ｈは、有効状態でロッドに垂れ下がる布を示すが、この場合に、シミュレーションは、有効状態から無効状態へ、さらに有効状態へと通過した。
【００６６】
ハードウェア
本明細書で解説する本発明のプロセスは、ディスプレイ２６４、キーボード２６６およびマウス２６８を備えたコンピュータ２６２を有する、図１６に表わすような従来のコンピュータシステム２６０で実行することができる。このシステムにはまた、本発明のプロセスおよびデータ構造を格納し分配できる、磁気および光ディスク、ＲＡＭ、ＲＯＭなどの永久または着脱可能記憶装置が含まれる。プロセスはまた、たとえば、インターネットなどのネットワークを通じたダウンロードを介して分配することができる。
【００６７】
概要および結論
この解説は、変形可能で自己変化する形状のシミュレーションのための新しいソルバーを提示した。制約および衝突のずれ量ゆえに、本発明者らは、系の状態を有効状態へ徐々に進める反復ソルバーを選択した。これは、シミュレーションが無効状態を受け入れることができるようにして、シミュレーションをより安定させる。ほとんどの動作は、全く単純で、ソルバーの単純なインプリメンテーションに適している。これは、特に、布などの大きな自己変化系を取り扱う場合には望ましい。
【００６８】
衝突を解決し、最小の衝突時間での衝突の衝突速度に最終速度を設定し、かつ衝突速度の時間加重平均を計算するための２つの方式に関して、本発明を説明した。重み付けされない衝突速度の平均などの他の方式または実施形態が可能である。
【００６９】
曲げおよび伸び制約の解決に関連して、本発明を説明した。曲線のためのねじれなどの他のタイプの内部エネルギーは、同じ趣旨で実行することができる。
【００７０】
本発明の多くの特徴および利点は、詳細な明細書から明白であり、かくして、本発明の真の趣旨および範囲内に入る、本発明の全てのかかる特徴および利点を包含することが、添付の特許請求の範囲によって意図されている。さらに、多くの変更および変形が当業者に容易に想到されるであろうため、図示し説明した構成および動作に本発明を正確に限定することは望ましくなく、したがって、本発明の範囲内に入る全ての適切な変更および均等物を用いてもよい。
【図面の簡単な説明】
【００７１】
【図１】形状を表わす。
【図２】法線および最近接点を示す。
【図３】ソルバープロセスを示す。
【図４】ソルバーの粒子経路および結果としての位置を示す。
【図５】従来の経路および位置を示す。
【図６】衝突ペアのタイプを表わす。
【図７】様々な粒子経路のための境界球を示す。
【図８】衝突ペアのグループ分けを表わす。
【図９】体積の符号反転を用いたエッジ衝突検出を示す。
【図１０】曲げが追加リンクによって取り扱われることを示す。
【図１１】法線間の角度を用いて取り扱われることを示す。
【図１２】物体が分離速度に基づいて分離されることを示す。
【図１３】表面貫通の取り扱いを表わす。
【図１４】本発明の全体的プロセスを示す。
【図１５ａ】無効状態を通過する粒子系の表示シーケンスを表わす。
【図１５ｂ】無効状態を通過する粒子系の表示シーケンスを表わす。
【図１５ｃ】無効状態を通過する粒子系の表示シーケンスを表わす。
【図１５ｄ】無効状態を通過する粒子系の表示シーケンスを表わす。
【図１５ｅ】無効状態を通過する粒子系の表示シーケンスを表わす。
【図１５ｆ】無効状態を通過する粒子系の表示シーケンスを表わす。
【図１５ｇ】無効状態を通過する粒子系の表示シーケンスを表わす。
【図１５ｈ】無効状態を通過する粒子系の表示シーケンスを表わす。
【図１６】本発明のハードウェアを表わす。
【図１】
2008541203.tif 000003
【図２】
2008541203.tif 000004
【図３】
2008541203.tif 000005
【図４】
2008541203.tif 000006
【図５】
2008541203.tif 000007
【図６】
2008541203.tif 000008
【図７】
2008541203.tif 000009
【図８】
2008541203.tif 000010
【図９】
2008541203.tif 000011
【図１０】
2008541203.tif 000012
【図１１】
2008541203.tif 000013
【図１２】
2008541203.tif 000014
【図１３】
2008541203.tif 000015
【図１４】
2008541203.tif 000016
【図１５ａ】
2008541203.tif 000017
【図１５ｂ】
2008541203.tif 000018
【図１５ｃ】
2008541203.tif 000019
【図１５ｄ】
2008541203.tif 000020
【図１５ｅ】
2008541203.tif 000021
【図１５ｆ】
2008541203.tif 000022
【図１５ｇ】
2008541203.tif 000023
【図１５ｈ】
2008541203.tif 000024
【図１６】
2008541203.tif 000025