(57)【要約】  変形可能物体をシミュレートする方法は、実形状及び目的形状を定義することにより物体の変形可能な弾性をモデル化するステップと、目標形状中の点を目標形状中の対応する点の方へ引き寄せるステップとを含んでいる。【選択図】図２
2009529161.tif 000002
【特許請求の範囲】
【請求項１】
変形可能物体をモデル化する方法であって、
変形形状を定義された目的形状の方へ引き寄せることにより前記変形可能物体の変形可能な弾性をモデル化するステップを含む、方法。
【請求項２】
拡張された形状一致技術を使用して前記目的形状を定義するステップを更に含む、請求項１に記載の方法。
【請求項３】
前記変形形状中の点の相対位置と原形状中の点の相対位置とを定義するステップと、
前記原形状中の点の前記相対位置と前記変形形状中の点の前記相対位置との間の変換を計算することにより前記目的形状を定義するステップと、
を更に含む、請求項２に記載の方法。
【請求項４】
前記変換を計算する前に、前記原形状中の点の前記相対位置に変形状態を適用するステップを更に含む、請求項３に記載の方法。
【請求項５】
恒等行列を用いて前記変形状態を初期化するステップと、
回転していない参照フレームにおける前記原形状の変形に基づいて前記変形状態を更新するステップと、
を更に含む、請求項４に記載の方法。
【請求項６】
前記拡張された形状一致技術を使用して前記目的形状を定義する前記ステップが、前記目的形状を定義するために原形状を回転及び平行移動させるステップを含む、請求項２に記載の方法。
【請求項７】
前記目的形状と前記変形形状との間の重み付き最小二乗差を最小化するために、前記原形状を回転及び平行移動させる回転行列及び並進ベクトルを定義するステップを更に含む、請求項６に記載の方法。
【請求項８】
１次変換行列に極分解を実行することにより前記回転行列を定義するステップと、
前記変形形状の質量中心及び前記原形状の質量中心を計算することにより前記並進ベクトルを定義するステップと、
を更に含む、請求項７に記載の方法。
【請求項９】
１次又は２次モードに従って前記変形可能な弾性を変化させるステップを更に含む、請求項１に記載の方法。
【請求項１０】
前記１次モードに従って前記変形可能な弾性を変化させる前記ステップが、前記目的形状を定義するために原形状に１次変換を適用するステップを含む、請求項９に記載の方法。
【請求項１１】
前記２次モードに従って前記変形可能な弾性を変化させる前記ステップが、前記目的形状を定義するために原形状に２次変換を適用するステップを含む、請求項９に記載の方法。
【請求項１２】
前記変形形状を複数のクラスタとして定義するステップを更に含む、請求項１に記載の方法。
【請求項１３】
前記変形形状を前記定義された目的形状の方へ引き寄せることにより前記物体の変形可能な弾性をモデル化する前記ステップが、各前記クラスタ中のデータ点を前記目的形状内の対応するクラスタ中のデータ点の方へ引き寄せるステップを含む、請求項１２に記載の方法。
【請求項１４】
変形形状中の複数の点の位置及び速度を定義するステップと、
目的形状中の点の位置に従って前記位置及び速度を更新するステップと、
を含む、変形可能物体をシミュレートする方法。
【請求項１５】
前記位置及び速度を更新する前記ステップが、
時刻ｔでの前記変形形状中の点の速度、及び、時刻ｔでの目的点の位置と前記点の位置との間の差に基づいて、時刻ｔ＋ｈでの前記点の速度を定義するステップと、
時刻ｔでの前記点の位置、及び、時刻ｔ＋ｈでの前記点の速度に基づいて、時刻ｔ＋ｈでの前記点の位置を定義するステップと、
を含む、請求項１４に記載の方法。
【請求項１６】
変形形状中の点と目的形状中の点との間の距離に比例して物体変形に関連する弾性力を定義するステップと、
陽的な積分スキームを使用して平衡へ向かう物体変形を解析するステップと、
原形状と前記変形形状とを点毎に一致させ、その後に、前記変形形状に対応する点を前記目的形状中の対応する点の方へ引き寄せることにより、前記陽的な積分スキームを解析するステップと、
を含む、シミュレーションにおいて物体変形を表現する方法。
【請求項１７】
前記原形状と前記変形形状とを点毎に一致させる前記ステップが、
前記原形状中の点ｘｉ０の集合と、前記変形形状中の対応する点ｘｉの集合とを選択するステップと、
ｗｉが各点の重みである場合に、すべてのｉについての
（ｗｉ（Ｒ（ｘｉ０−ｔ０）＋ｔ−ｘｉ）２
の和を最小化するように回転行列Ｒと並進ベクトルｔ及びｔ０とを算出するステップと、
を含む、請求項１６に記載の方法。
【請求項１８】
ｘｃｍ０が前記原形状の質量中心であり、ｘｃｍが前記変形形状の質量中心である場合に、点ｘｉ０毎に、前記目的形状中の対応する点ｇｉの位置を
ｇｉ＝Ｒ（ｘｉ０−ｘｃｍ０）＋ｘｃｍ
として定義するステップを更に含む、請求項１７に記載の方法。
【請求項１９】
ｘｃｍ０が前記原形状の質量中心であり、ｘｃｍが前記変形形状の質量中心であり、Ａが１次変換行列であり、βが制御パラメータである場合に、点ｘｉ０毎に、前記目的形状中の対応する点ｇｉの位置を
【数１】
2009529161.tif 000048
として定義するステップを更に含む、請求項１７に記載の方法。
【請求項２０】
【数２】
2009529161.tif 000049
が２次変換行列であり、
【数３】
2009529161.tif 000050
が１次項、２次項及び混成項を含むベクトルである場合に、点ｘｉ０毎に、前記目的形状中の対応する点ｇｉの位置を
【数４】
2009529161.tif 000051
として定義するステップを更に含む、請求項１７に記載の方法。
【発明の詳細な説明】
【関連出願】
【０００１】
[0001]本出願は２００５年５月９日に出願された米国仮出願第６０／６７８，８１５号の利益を主張する。
【背景技術】
【０００２】
１．発明の分野
[0002]本発明の実施形態は一般に変形可能な物体をシミュレートする方法に関する。特に、発明の実施形態は幾何学に基づく基礎的モデルを使用して変形可能物体をシミュレートする方法に関する。
【０００３】
２．関連技術の説明
[0003]衣類、プラスチック、弾性材料、及び関節継手のような日常的な物体の実際のコンピュータシミュレーションは、これらの物体が実生活において複雑に変形する傾向があるので、生成することが非常に難しくなり得る。一般に、このような「変形可能物体」のシミュレーションでは、物体の複雑な幾何学的特徴と材料特性の両方を考慮しなければならない。
【０００４】
[0004]変形可能物体をシミュレートするためによく用いられる技術の一つは、最初に物体の仮想モデル（例えば、メッシュ又は点群）を作成し、次に張力、摩擦、重力、圧力などのようなシミュレートされた物理力を仮想モデルの離散点に適用するものである。このような仮想モデルは、種々の条件下で多種多様の材料を表現するために使用されている。例えば、研究者は衣類、プラスチック、ゴムなどの仮想モデルを開発している。更に、研究者は、破損及び融解のようなこれらの物体の複雑で特異な挙動をシミュレートするための仮想モデルも開発している。
【０００５】
[0005]変形可能物体をシミュレートするのによく用いられるアプローチには、有限差分法、質量−ばね系、境界要素法、有限要素法、陰関数曲面及びメッシュフリー粒子系がある。
【０００６】
[0006]変形可能物体をシミュレートする多数の方法が開発されているにもかかわらず、これらの方法はコンピュータゲームのようなアプリケーションに殆ど組み込まれていない。例えば、いくつかの最新ゲームは簡単な幾何学的性質を用いる衣服モデルを組み込んでいるが、一般に、パーソナルコンピュータ（ＰＣ）又はゲーム機で動く殆どのアプリケーションは剛体又は剛体物体だけをモデル化する傾向がある。実際には、複数の剛体物体が変形可能物体の運動を模倣するために組み合わされることもあるが、真の変形可能物体のシミュレーションは稀有である。
【０００７】
[0007]変形可能物体のシミュレーションがコンピュータゲームのようなアプリケーションで殆ど使用されない理由の一つは、安定したシミュレーションが一般に非効率的であるのでアプリケーションのリアルタイム要求を満たさないということである。例えば、従来のシミュレーション方法は、多くの場合に、仮想モデル内の離散点の位置を更新するために陰的な数値積分に依存する。陰的な数値積分技術は安定したシミュレーションを行うことが可能であるが、大規模かつ複雑な物理的モデルをリアルタイムで処理するためには非常に計算コストが高い。その他の物理的なモデリングアプローチは、より効率的である陽的な数値積分に依存するが、陽的な数値積分は安定したシミュレーションを保証することができない。
【０００８】
[0008]「安定性」という用語は、本明細書では処理の入力中の僅かなずれに合理的に応答する処理の傾向のことをいう。例えば、陰的な数値積分技術は、シミュレーション対象点の質量、積分の時間ステップなどのような種々の入力パラメータが変化するにつれて正確なシミュレーションを生成する。これに対して、陽的な数値積分技術は、積分の時間ステップ、シミュレーション対象点の質量、又は、シミュレーション対象物体の剛性を単に変化させることにより、系の全体的なエネルギーが誤って増加するシミュレーションを生成することがある。その結果として、陽的な数値積分技術は非常に非現実的なシミュレーション結果を生成する可能性がある。
【０００９】
[0009]安定したシミュレーション技術の効率を改善するために種々の方法が開発されている。例えば、大きい時間ステップと多重解像度モデルとを用いるロバスト積分スキームが開発されている。更に、精度と引き換えに効率を求めるモーダル解析アプローチも開発されている。更に、予め計算された状態空間ダイナミクス及び予め計算されたインパルス応答関数を組み込む方法も、シミュレーションの効率を改善するために使用されている。最後に、球、円柱、円錐、又は、超２次曲面のような基本立体形状の大域的な幾何学的変形から導出されたダイナミックモデルも、安定したシミュレーション技術の効率を改善するために導入されている。
【００１０】
[0010]図１は、陽的な数値積分を使用する変形可能物体のシミュレーションにおける不安定性の一つの現れ方を示す図である。図１では、簡単な１次元変形可能物体が質量−ばね系としてモデル化されている。多数の物理学に基づく変形可能物体のシミュレーションと同様に、質量−ばね系はニュートンの第２運動法則に依存している。ニュートンの第２運動法則によれば、真の力によって生成された物体の加速度は、真の力の方向における真の力の大きさに正比例し、物体の質量に反比例する。変形可能物体では、任意の点における真の力の少なくとも一部は平衡位置からの点の変位によって作り出される。点の平衡位置からの点の変位はポテンシャルエネルギー、すなわち、点を平衡位置の方へ引き寄せる「変形エネルギー」を作り出す。
【００１１】
[0011]図１Ａを参照すると、質量−ばね系１００は、静止長ｌ０をもつばね１０１と、共に質量「ｍ」を有する２個の質点１０２及び１０３とを備える。質点１０２は原点に固定され、質点１０３は初期時刻「ｔ」でｘ（ｔ）に位置している。初期時刻「ｔ」において、質点１０３での力の大きさはばね釣り合い式
ｆ＝−ｋ（ｘ（ｔ））−ｌ０）
によって定義され、式中、「ｋ」はばね１０１のばね定数、すなわち「剛性」である。概念上、ばね釣り合い式は、質点１０３がｘ＝ｌ０である平衡位置へ引き寄せられることを示している。
【００１２】
[0012]質点１０３の位置は、時間ステップ「ｈ」の後に、修正オイラー積分スキームによって更新される。修正オイラー積分スキームによれば、時刻「ｔ＋ｈ」における質点１０３の速度「ｖ」及び位置「ｘ」は以下の式（１）及び（２）を使用して算出される。
【数１】
2009529161.tif 000003
【数２】
2009529161.tif 000004
式（１）は陽的なオイラーステップを使用し、式（２）は陰的なオイラーステップを使用する。
【００１３】
[0013]式（１）及び（２）は、状態ベクトル［ｖ（ｔ），ｘ（ｔ）］Ｔが乗じられたシステム行列「Ｍ」として表現され、すなわち、
【数３】
2009529161.tif 000005
である。式中、システム行列「Ｍ」は以下の式（３）により定義される。
【数４】
2009529161.tif 000006
システム行列「Ｅ」は以下の式（４）及び（５）により表される固有値ｅ０及びｅ１を有する。
【数５】
2009529161.tif 000007
【数６】
2009529161.tif 000008
システム行列「Ｅ」は離散系を表現するので、システム行列「Ｅ」のスペクトル半径、すなわち固有値ｅ０及びｅ１の最大の大きさは、離散系の安定性を保証するために１より大きくてはならない。固有値ｅ０の大きさは、ｈ２ｋ→∞に関して、｜ｅ０｜＜１の状態で１に収束する。しかし、ｅ１の大きさは、時間ステップ「ｈ」が
【数７】
2009529161.tif 000009
より小さいならば、１より小さければよい。時間ステップ「ｈ」が
【数８】
2009529161.tif 000010
より大きいならば、系は不安定である。したがって、式（１）及び（２）を伴う積分スキームは条件付きで安定であるに過ぎない。
【００１４】
[0014]システム行列「Ｅ」により表される離散系の不安定性を更に説明するため、ｖ（ｔ）＝０で始まる積分ステップの実行結果を図１Ｂに示す。積分ステップは、質点１０３を、
【数９】
2009529161.tif 000011
という距離だけ動かす。時間ステップ「ｈ」か剛性「ｋ」が非常に大きいか、又は質量「ｍ」が非常に小さいならば、質点１０３は、ｘ（ｔ）とｌ０との間の距離を上回る距離だけ平衡位置ｌ０を通り過ぎる。すなわち、｜（ｘ（ｔ＋ｈ）−ｌ０｜＞｜ｘ（ｔ）−ｌ０｜である。その結果、系１００のポテンシャルエネルギーは時間ステップ「ｈ」の後に増加する。系１００は時刻「ｔ」において０という運動エネルギーを保有していたので、系の全エネルギー（すなわち、運動エネルギー＋ポテンシャルエネルギー）は時間ステップ「ｈ」の後に誤って増加してしまう。
【００１５】
[0015]一般に、陽的な積分スキームの安定性問題は、弾性力が弾性エネルギーの負の勾配である、と言い表すことができる。したがって、弾性力は平衡位置の方へ向かう。陽的なスキームは、点の変位を計算するときに弾性力を不正確に拡大縮小することがあり、点が平衡位置を大きく通り過ぎ、安定性のため必要とされる変形エネルギーを保存又は減少させるのではなく系の変形及びエネルギーを増大させる原因になる。
【００１６】
[0016]通り過ぎてしまう問題を解決する一つの方策は、各点がその平衡位置を決して行き過ぎないように点の変位を制限することである。例えば、図１の一方向ばねの例では、質点１０３の運動は平衡位置ｘ＝ｌ０を通過しないように制限され得る。このアプローチに付随する一つの問題は、多様な物理的モデルに対し、平衡位置がすべての点に対して容易に定義されないことである。例えば、立体有限要素又は幾何学的に複雑なメッシュにおいて平衡位置を定義することは困難である。
【発明の開示】
【課題を解決するための手段】
【００１７】
[0017]本発明の一実施形態によれば、変形可能物体をモデル化する方法は、変形形状を定義された目的形状の方へ引き寄せることにより物体の変形可能な弾性をモデル化するステップを含む。
【００１８】
[0018]本発明の別の実施形態によれば、変形可能物体をシミュレートする方法は、変形形状中の複数の点の位置及び速度を定義し、目的形状中の点の位置に基づいて位置及び速度を更新するステップを含む。
【００１９】
[0019]本発明の更に別の実施形態によれば、シミュレーションにおいて物体変形を表現する方法は、変形形状中の点と目的形状中の点との間の距離に比例して物体変形に伴う弾性力を定義するステップと、陽的な積分スキームを使用して平衡点へ向かう物体変形を解析するステップと、原形状と変形形状とを点毎に一致させ、その後に、変形形状に対応する点を目的形状中の対応する点の方へ引き寄せることにより、陽的な積分スキームを解析するステップとを含む。
【００２０】
[0020]本発明は添付図面に示されている様々な実施形態に関して以下に説明する。図面を通じて、類似した参照番号は類似した典型的な要素、コンポーネント、又は、ステップを示している。
【発明を実施するための最良の形態】
【００２１】
[0024]本発明の実施形態は変形可能物体をモデル化及びシミュレートする種々の方法を提供する。これらの方法は、少し例を挙げると、科学的可視化、コンピュータグラフィックス、コンピュータアニメーション映画、及び、ビデオゲームのような広範囲のコンピュータ関連アプリケーションに容易に適用できる。
【００２２】
[0025]本発明の特定の実施形態は、高レベルの計算効率を要求するアプリケーションに特に適している。例えば、本発明の一部の実施形態では、コンピュータのデータ処理帯域幅の少しの部分だけを使用して、複雑な幾何学的性質及び／又は材料特性をもつ変形可能物体に関してリアルタイムシミュレーションを実行することが可能である。
【００２３】
[0026]ビデオゲームは高レベルの計算効率が求められるアプリケーションの一つである。例えば、最先端のビデオゲームは、あたかも物理法則によって支配されているかのように環境とリアルタイムに相互作用するキャラクタ及び物体のような多種多様の現実的効果を組み込む傾向がある。このようなキャラクタ及び物体は多くの場合に、例えば、衣服、屈伸可能な材料などを含む変形可能物体によって形成されている。
【００２４】
[0027]本発明の実施形態に係る変形可能物体のシミュレーションは、通常は、少なくとも１つのマイクロプロセッサ及びメモリを含む計算プラットフォームでソフトウェアアプリケーションを実行することによって実行される。「実行する」という用語は、本明細書では、計算プラットフォームと関連付けられたハードウェア資源が（直接的又は間接的に）ソフトウェア資源の命令下で演算を実行するあらゆるプロセスのことをいう。
【００２５】
[0028]変形可能物体をシミュレートするため、ソフトウェアアプリケーションは、変形可能物体の構造と物体に作用する任意の外力とを定義する幾何学的データ及び物理的データを受信する。変形可能物体の「構造」は、例えば物体を構成する個々の要素（例えば、点、面など）の位置及び質量やそれら個々の要素の任意の接続性及び運動などを含む、物体自体のすべての物理的属性の記述として広義に定義されている。
【００２６】
[0029]ソフトウェアアプリケーションは、弾性張力のような物体の内力と、物体を構成する個々の要素の運動と、重力、圧力、摩擦、又は、他の物体との衝突による衝撃力のような物体に作用する任意の外力とに基づいて物体の構造を更新することにより、変形可能物体をシミュレートする。
【００２７】
[0030]計算プラットフォームは、典型的に、１台以上の中央処理ユニット（ＣＰＵ）及び１台以上のメモリを備える。１台以上のメモリは、ソフトウェアアプリケーションを格納し、実行のためソフトウェアアプリケーションを１台以上のＣＰＵへロードする。
【００２８】
[0031]変形可能物体のシミュレーションは２個以上のソフトウェアアプリケーションと一体になって実行されることもある。例えば、シミュレーションは、単一のＣＰＵ、２台の異なるプロセッサコア、又は、２台の異なるＣＰＵ上の２個の実行スレッド中で動く２個のソフトウェアアプリケーションによって実行され得る。このシミュレーションが２個のソフトウェアアプリケーションによって実行されるならば、アプリケーションのうちの一方は、一般に、幾何学的データ及び物理的データを定義するメインアプリケーションを備え、もう一方のアプリケーションは、一般に、メインアプリケーションと並列に動き、幾何学的データ及び物理的データを更新する物理アプリケーションを備える。
【００２９】
[0032]このようなシミュレーションを実行できる様々な計算プラットフォームは、例えば、２００３年１１月１９日に出願された米国特許出願第１０／７１５，４５９号及び第１０／７１５，４４０号と、２００４年４月２日に出願された米国特許出願第１０／８１５，７２１号と、２００４年５月６日に出願された米国特許出願第１０／８３９，１５５号と、２００４年１１月８日に出願された米国特許出願第１０／９８２，７９１号と、２００４年１１月１６日に出願された米国特許出願第１０／９８８，５８８号とに開示されている。これらの本出願と同一出願人による係属中の特許出願の主題は参照によってここに組み込まれている。
【００３０】
[0033]本明細書中、「変形可能物体」という用語は、広く、空間的関係を変えながら配置され得る要素を備える物体を表現できるデータの任意の集合を指している。例えば、変形可能物体は、メッシュ、面、又は、点の集合を含み得る。変形可能物体は、一般に、物体が変形する傾向に関係したパラメータを更に含む。例えば、変形可能物体は、変形可能物体の各要素の目的状態と、各要素がその目的状態に接近する容易さの程度を示す剛性パラメータとを含むことがある。
【００３１】
[0034]図２は、発明の一実施形態に係る、変形可能物体をモデル化しシミュレートする方法を説明する図である。説明を簡単にするため、図２の方法は２次元（２Ｄ）物体に関連して記載されている。しかし、この方法はより高い（例えば、３Ｄ）次元、又は、より低い（１Ｄ）次元で表現された物体に容易に適用できる。
【００３２】
[0035]図２を参照すると、変形可能物体２００は、変形可能物体２００の変形状態に対応する「実形状」２０２と、変形可能物体２００の非変形状態に対応する「目的形状」２０３とによってモデル化されている。実形状２０２は、４個の「実点」ｘ１、ｘ２、ｘ３及びｘ４を含み、目的形状２０３は、それぞれの実点ｘ１、ｘ２、ｘ３及びｘ４に対応する４個の「目的点」ｇ１、ｇ２、ｇ３及びｇ４を含む。実点ｘ１、ｘ２、ｘ３及びｘ４はそれぞれの質量「ｍ１」、「ｍ２」、「ｍ３」及び「ｍ４」によって特徴付けられる。
【００３３】
[0036]目的形状２０３は、４個の「原点」ｘ１０、ｘ２０、ｘ３０及びｘ４０を含む「原形状」２０１を実形状２０２中の対応する実点ｘ１、ｘ２、ｘ３及びｘ４に一致させることにより定義される。すなわち、目的形状２０３は、一致させられたバージョンの原形状２０１である。「一致」という用語は、本明細書では、目的形状２０３が実形状２０２に接近するように原形状２０１に適用される変換処理を指している。後述するように、このような変換には、例えば、１次変換、より高次の（例えば、２次）変換、又は、１次変換と高次変換との組み合わせが含まれ得る。目的形状２０３が定義されると、変形可能物体２００中の変形可能弾性は、図２の矢印で示されるように、実点ｘ１、ｘ２、ｘ３及びｘ４を対応する目的点ｇ１、ｇ２、ｇ３及びｇ４の方へ引き寄せることによりモデル化される。
【００３４】
[0037]本明細書では、ｘｉ０、ｘｉ及びｇｉという表記は、点と点の位置とを指すために使用される。例えば、実点ｘｉの位置は単純にｘｉのように表示されている。
【００３５】
[0038]原形状２０１を実形状２０２に一致させる一つの方法は、原形状２０１を回転及び平行移動させることである。回転及び平行移動の量は、目的形状２０３中の点と実形状２０２中の対応する点との間の距離を最小化することによって決定できる。例えば、平行移動及び回転は、目的形状２０３と実形状２０２との対応する点の間の重み付き最小二乗距離を最小化するように選択できる。原形状２０１と実形状２０２とにおける点間の対応関係は、一般に、例えば原形状２０１及び実形状２０２が最初に定義されるときに事前に定義される。
【００３６】
[0039]図２では、対応点は類似した添字を使ってラベル付けされている。例えば、原点ｘ１０は、実点ｘ１及び目的点ｇｌに対応している。したがって、目的形状２０３の構造は、以下の式（５）が最小化されるような回転行列Ｒと並進ベクトルｔ０及びｔとを求めることによって算出できる。
【数１０】
2009529161.tif 000012
式（５）において、ｗｉは原点ｘｉ０及び実点ｘｉに関連付けられた数学的重みを表す。一般に、各点に関連付けられている重みは点の質量である。したがって、本明細書を簡単にするため、重みｗｉは全体を通じて質量「ｍｉ」の代わりに用いられる。
【００３７】
[0040]変形可能物体２００中の各点の数学的重みｗｉが点の質量「ｍｉ」である場合に、並進ベクトルｔ０及びｔは、以下の式（６）及び（７）によって定義される原形状２０１及び実形状２０２のそれぞれの質量中心ｘｃｍ０及びｘｃｍとして定義される。
【数１１】
2009529161.tif 000013
【数１２】
2009529161.tif 000014
【００３８】
[0041]回転行列Ｒを計算するため、原形状２０１の点の相対的位置ｑｉ及び実形状２０２の点の相対的位置ｐｉが、
ｑｉ＝ｘｉ０−ｘｃｍ０  及び  ｐｉ＝ｘｉ−ｘｃｍ
として定義される。そして、以下の式（８）を最小化する１次変換行列「Ａ」が算出される。
【数１３】
2009529161.tif 000015
【００３９】
[0042]式（８）を最小化する１次変換行列「Ａ」は、「Ａ」に関して式（８）の微分をとり、微分を零に設定することによって計算される。結果として得られる１次変換行列「Ａ」は次式（９）により計算される。
【数１４】
2009529161.tif 000016
【００４０】
[0043]式（９）は第１の行列Ａｑｑ及び第２の行列Ａｐｑを定義する。第１の行列Ａｑｑは対称であり、したがって、拡大縮小成分を含んでいるが回転成分を含んでいない。これに対して、第２の行列Ａｐｑは対称成分及び回転成分の両方を含んでいる。第２の行列Ａｐｑの回転成分は回転行列Ｒであり、第２の行列Ａｐｑの対称成分は対称行列Ｓである。回転行列Ｒ及び対称行列Ｓは、Ａｐｑ＝ＲＳによって表現される極分解を用いて第２の行列Ａｐｑを分解することによって求められる。極分解では、対称行列Ｓは
【数１５】
2009529161.tif 000017
として計算され、回転行列ＲはＲ＝ＡｐｑＳ−１として計算される。回転行列Ｒが定義されると、目的点の位置ｇ１、ｇ２、ｇ３及びｇ４は次式（１０）により計算される。
【数１６】
2009529161.tif 000018
【００４１】
[0044]次に、目的点の位置ｇ１、ｇ２、ｇ３及びｇ４を計算すると、実点の位置ｘ１、ｘ２、ｘ３及びｘ４が次式（１１）及び（１２）の積分により更新される。
【数１７】
2009529161.tif 000019
【数１８】
2009529161.tif 000020
式（１１）及び（１２）において、項αは変形可能物体２００の「剛性」を表している。項αは零から１まで変化し、値α＝１は変形可能物体２００が剛体であることを示し、値α＝０は変形可能物体２００がかなり変形可能であることを示す。項ｆｅｘｔ  ｉ（ｔ）は、時刻ｔで実形状２０２の点「ｉ」に作用する真の外力を表している。
【００４２】
[0045]実形状２０２へのαの影響を説明するために、α＝１、初期速度ｖ（ｔ）＝０、真の外力ｆｅｘｔ  ｉ（ｔ）＝０と仮定する。これらの条件下で、式（１１）は、
【数１９】
2009529161.tif 000021
として評価され、式（１２）は、
【数２０】
2009529161.tif 000022
となる。すなわち、変形可能物体２００が剛体であるならば、変形可能形状２０２は目的形状２０３の構造に非常に速く接近する傾向がある。α＜１である場合、変形可能形状２０２は依然として目的形状２０３の構造に接近するが、その近づき方はより緩やかである。
【００４３】
[0046]式（１１）及び（１２）を図１に示された質量−ばね系１００に適用すると、質点１０３の速度及び位置は次式（１３）にしたがって更新される。
【数２１】
2009529161.tif 000023
【００４４】
[0047]式（１３）において、項
【数２２】
2009529161.tif 000024
は、式（３）におけるシステム行列「Ｅ」に類似するシステム行列を表す。しかし、システム行列「Ｅ」の固有値とは異なって、項
【数２３】
2009529161.tif 000025
の固有値の大きさは、α及び時間ステップｈの値とは無関係に常に１である。特に、項
【数２４】
2009529161.tif 000026
の固有値は
【数２５】
2009529161.tif 000027
として定義される。項
【数２６】
2009529161.tif 000028
の固有値は常に１に等しいので、式（１１）及び（１２）を使用する質量−ばね系１００のシミュレーションは無条件に安定する。更に、式（１１）及び（１２）を使用するシミュレーションは質量−ばね系１００に減衰をもたらさない。
【００４５】
[0048]外力を伴わない変形可能物体の３次元シミュレーションもまた、式（１１）及び（１２）の下で無条件に安定し、かつ、減衰がない。更に、変形可能物体に加えられた外力（重力のような力など）が位置に関して変わらなかったり、衝突応答力などのような外力が瞬時に加えられたりする限り、シミュレーションは同様に無条件に安定するであろう。
【００４６】
[0049]図３は本発明の実施形態に係る変形可能物体をシミュレートする方法を説明するフローチャートである。以下の説明中、典型的な方法のステップは括弧付きの（ＸＸＸ）によって表記されている。
【００４７】
[0050]図３を参照すると、この方法は、変形可能物体の変形状態に対応する実形状を定義するステップと（３０１）、変形可能物体の非変形状態に対応する目的形状を定義するステップと（３０２）、実形状中の各点を目的形状中の対応する点の方へ引き寄せることにより実形状中の各点の位置を更新するステップと（３０３）を含んでいる。
【００４８】
[0051]一般に、実形状中の実点の位置は、実形状の構造の初期化及びそれに続く更新といった、ソフトウェアアプリケーションにおけるイベントにより定義される。一方、目的形状中の目的点の位置は様々な異なる方法で計算され得る。
【００４９】
[0052]本発明の一実施形態によれば、目的形状中の目的点の位置ｇｉは、原点を含む原形状を定義し、例えば、式（１０）に記述されているように、並進ベクトル及び回転行列を使用して実形状に一致するように原形状を回転及び平行移動させることにより算出される。
【００５０】
[0053]並進ベクトルは、一般に、式（６）及び（７）に記述されているように、原形状及び実形状のそれぞれの質量中心から計算され、回転行列は、一般に、式（９）に従って計算された１次変換行列の極分解によって計算される。
【００５１】
[0054]一般に、式（１０）中の質量中心ｘｃｍ０と、式（８）及び（９）中の相対位置ｑｉとは、シミュレーションの任意の時間ステップが実行される前に計算される。その後、シミュレーションの各時間ステップで、第２の行列Ａｐｑ＝ΣｉｍｉｐｉｑｉＴが組み立てられる。シミュレートされている変形可能物体が３次元である場合には、第２の行列Ａｐｑは３×３行列である。
【００５２】
[0055]第２の行列Ａｐｑは、対称行列Ｓを
【数２７】
2009529161.tif 000029
として計算し、回転行列ＲをＲ＝ＡｐｑＳ−１として計算することによって、回転行列「Ｒ」と対称行列「Ｓ」とに分解される。項Ｓ−１、すなわち、
【数２８】
2009529161.tif 000030
は、５乃至１０回のヤコビ回転を使用して対称行列ＡｐｑＴＡｐｑを対角化することにより算出される。ここで、各ヤコビ回転の計算複雑性は一定である。
【００５３】
[0056]本発明の別の実施形態によれば、目的点の位置ｇｉは、次式（１４）に従って回転行列「Ｒ」及び１次変換行列「Ａ」を使用する１次変換によって計算される。
【数２９】
2009529161.tif 000031
式（１４）中、項βは目的点の位置ｇｉを制御するために使用される制御パラメータである。１次変換行列「Ａ」は、原形状に対する目的形状の体積が式（１４）により保存されることを保証するために、
【数３０】
2009529161.tif 000032
により除算される。１次変換行列「Ａ」は、一般に、任意のシミュレーション時間ステップが実行される前に第１の行列Ａｑｑを形成し、その後に、各時間ステップで第２の行列Ａｐｑを形成することにより構築される。
【００５４】
[0057]目的点の位置ｇｉを計算するために式（１０）ではなく式（１４）を使用する利点の一つは、式（１４）が実点ｘｉの位置により近い目的点ｇｉを生成し得ることである。したがって、式（１４）は、一般に、より大きく変形された物体、及び／又は、より剛性の低い物体をシミュレートするときにより優れている。
【００５５】
[0058]目的点ｇｉを計算する別の方法は、原点に関して２次変換を実行することに基づいている。例えば、目的点ｇｉは次式（１５）によって定義された２次変換によって算出できる。
【数３１】
2009529161.tif 000033
式（１５）において、ｇｉ∈Ｒ３かつ
【数３２】
2009529161.tif 000034
である。Ａ∈Ｒ３×３は、１次項ｑｘ、ｑｙ、ｑｚの係数を含み、Ｑ∈Ｒ３×３は純２次項ｑｘ２、ｑｙ２、ｑｚ２の係数を含み、Ｍ∈Ｒ３×３は混成項ｑｘｑｙ、ｑｙｑｚ、ｑｚｑｘの係数を含んでいる。２次変換行列
【数３３】
2009529161.tif 000035
は、好ましくは、式
【数３４】
2009529161.tif 000036
を最小化し、次式（１６）によって算出される。
【数３５】
2009529161.tif 000037
式（１６）中の対称行列
【数３６】
2009529161.tif 000038
及び、ベクトル
【数３７】
2009529161.tif 000039
は、シミュレーションが始まる前に算出可能である。同様に、制御パラメータβは目的点の位置を更に制御するために、２次変換行列
【数３８】
2009529161.tif 000040
と共に使用されうる。例えば、目的点は、式
【数３９】
2009529161.tif 000041
によって生成されることがあり、式中、式（１５）を使用する代わりに、
【数４０】
2009529161.tif 000042
である。
【００５６】
[0059]目的点ｇｉを計算する更に別の方法は、実点ｘｉを重なり合うクラスタに分割し、その後に、クラスタ毎に別個の変換行列を計算することに基づいている。例えば、体積メッシュにより表された実点ｘｉは、各クラスタが体積メッシュの共通要素（例えば、四面体）に隣接した点を含むクラスタに分割され得る。あるいは、メッシュを重なり合う立方体領域に分割し、その後に、クラスタを各立方体領域中のすべての点により形成することも可能である。
【００５７】
[0060]各時間ステップで、原点、及び各クラスタに対応する実点は、目的点ｇｉｃ（ｔ）を生成するために一致させられる。ここで、「ｉ」は各点のインデックスを表し、「ｃ」は特定のクラスタを表す。目的点ｇｉ（ｔ）の代わりに目的点ｇｉｃ（ｔ）を使用すると、式（１１）は次式（１７）となる。
【数４１】
2009529161.tif 000043
【００５８】
[0061]式（１１）及び（１７）における速度更新に伴う一つの一般的な問題は、系の挙動が時間ステップ「ｈ」に大きく依存することである。この問題を解決するための一つの方法は、τ≦ｈを時定数として、α＝ｈ／τを設定することに基づいている。
【００５９】
[0062]目的点ｇｉの位置を定義するために変換行列を計算するとき、必ずしも実形状又は原形状のすべての点が考慮されなくてもよい。例えば、変形可能物体が多数の点を含む場合、変形可能物体を定義する実点及び対応する原点の部分集合を用いて変換行列を生成することができる。その後、変換行列は、原点の全部を変換して目的点を生成するために使用され得る。
【００６０】
[0063]図３に関連して述べた方法は、プラスチック変形可能物体をシミュレートするためにも使用され得る。一般に、プラスチック変形可能物体は物体の変形状態Ｓｐを表現することによりシミュレートされる。変形状態Ｓｐは、恒等行列「Ｉ」で初期化され、その後に、シミュレーションの各時間ステップに伴って更新される。
【００６１】
[0064]変形状態Ｓｐは、式（９）の第２の行列Ａｐｑの極分解によって導かれた対称行列Ｓに基づいて更新される。対称行列Ｓは回転していない参照フレーム内での原形状の変形を表している。したがって、変形の量（すなわち、距離）｜｜Ｓ−Ｉ｜｜２が閾値ｃｙｉｅｌｄを上回る場合、状態行列Ｓｐは次式（１８）に従って更新される。
【数４２】
2009529161.tif 000044
式（１８）中、時間ステップ「ｈ」及びパラメータｃｃｒｅｅｐは変形可能物体の可塑性を制御するために使用される。可塑性は、｜｜Ｓｐ−Ｉ｜｜２が閾値ｃｍａｘを上回るかどうかをテストすることによって制限され得る。｜｜Ｓｐ−Ｉ｜｜２＞ｃｍａｘである場合、状態行列は次式（１９）により設定される。
【数４３】
2009529161.tif 000045
状態行列Ｓｐは、式（８）中のｑｉ＝ｘｉ０−ｘｃｍ０という定義を次式（２０）で置き換えることにより変形可能物体のシミュレーションに導入される。
【数４４】
2009529161.tif 000046
変形可能物体の体積がシミュレーションを通じて保存されることを保証するために、状態行列Ｓｐは、状態行列が更新される度に、
【数４５】
2009529161.tif 000047
によって除算される。Ｓｐが更新される度に、第１の行列Ａｑｑ及び第２の行列Ａｐｑも更新されなければならないことに注意されたい。
【００６２】
[0065]以上の好ましい実施形態は教示のための例である。当業者は、形式及び細部における種々の変更が請求項によって規定されるような本発明の範囲から逸脱することなく典型的な実施形態になされてもよいことを理解するであろう。
【図面の簡単な説明】
【００６３】
【図１Ａ】変形可能物体をシミュレートするため使用される従来の１次元質量−ばね系の図である。
【図１Ｂ】変形可能物体をシミュレートするため使用される従来の１次元質量−ばね系の図である。
【図２】本発明の一実施形態に係る２次元変形可能物体のシミュレーションを説明する図である。
【図３】本発明の実施形態に係る変形可能物体をシミュレートする方法を説明するフローチャートである。
【図１Ａ】
2009529161.tif 000052
【図１Ｂ】
2009529161.tif 000053
【図２】
2009529161.tif 000054
【図３】
2009529161.tif 000055