(57)【特許請求の範囲】
【請求項１】
物理シミュレーションを行う方法であって、該方法は、複数のメモリアレイを含むメモリと、少なくとも１つのグラフィックスプロセッサユニット（ＧＰＵ）とを含むシステムによって実行され、該少なくとも１つのＧＰＵは、該複数のメモリアレイと通信するように適合されており、かつ、少なくとも１つのピクセルプロセッサを含み、
該方法は、
該グラフィックスプロセッサユニットが、少なくとも１つのメッシュに関連した該メモリに格納された物理パラメータを該複数のメモリアレイにマッピングすることによって、該メモリに格納されたシーンに描写された該少なくとも１つのメッシュの運動を支配する線形方程式系を格納することと、
該グラフィックスプロセッサユニットが、該少なくとも１つのピクセルプロセッサを用いて該複数のメモリアレイ中のデータに演算を行うことによって、ある時刻に対する線形方程式系を解くことと
を包含し、
該演算は、該少なくとも１つのメッシュに関連した該物理パラメータ間の相補的なジョイント力に対して演算を行う一組の同一のレンダリングサブパスを実行することを含み、
該時刻に対する該線形方程式系の解を表す変更されたデータは、該複数のメモリアレイに格納される、方法。
【請求項２】
前記グラフィックスプロセッサユニットが、前記複数のメモリアレイ中の前記変更されたデータに基づいて、前記時刻に対する前記シーンにおいて描写される、前記少なくとも１つのメッシュの運動を更新することをさらに含む、請求項１に記載の方法。
【請求項３】
前記グラフィックスプロセッサユニットが、前記時刻に対する前記少なくとも１つのメッシュを含む、少なくとも１つの衝突を識別することと、
該グラフィックスプロセッサユニットが、（ｉ）前記複数のメモリアレイ中の前記変更されたデータ、および、（ｉｉ）該識別された少なくとも１つの衝突に基づいて、前記時刻に対する前記シーン中に描写される前記少なくとも１つのメッシュの運動を更新することと
をさらに含む、請求項１に記載の方法。
【請求項４】
前記グラフィックスプロセッサユニットが、前記ピクセルプロセッサを用いて前記変更されたデータに演算を行うことによって、次の時刻に対する前記線形方程式系を解くことをさらに含み、該次の時刻に対する該線形方程式系の解を表すさらなる変更されたデータは、前記複数のメモリアレイに格納される、請求項１に記載の方法。
【請求項５】
前記グラフィックスプロセッサユニットが、前記複数のメモリアレイ中の前記さらなる変更されたデータに基づいて、前記次の時刻に対する前記シーン中に描写される前記少なくとも１つのメッシュの運動を更新することをさらに含む、請求項４に記載の方法。
【請求項６】
前記グラフィックスプロセッサユニットが、前記次の時刻に対する前記少なくとも１つのメッシュを含む少なくとも１つの衝突を識別することと、
前記グラフィックスプロセッサユニットが、（ｉ）前記複数のメモリアレイ中の前記さらなる変更されたデータ、および、（ｉｉ）該識別された少なくとも１つの衝突に基づいて、前記次の時刻に対する前記シーン中に描写される前記少なくとも１つのメッシュの運動を更新することと
をさらに含む、請求項４に記載の方法。
【請求項７】
前記演算を行うことは、
前記グラフィックスプロセッサユニットが、前記少なくとも１つのピクセルプロセッサを用いて前記複数のメモリアレイ中の前記データに演算を行うことによって、インプリシットに前記線形方程式系を積分することによって、ある時刻に対する該線形方程式系を解くことを含み、
該時刻に対する該線形方程式系の解を表す変更されたデータは、該複数のメモリアレイに格納される、請求項１に記載の方法。
【請求項８】
前記格納することは、
前記グラフィックスプロセッサユニットが、前記複数のメモリアレイにデータを格納することによって、線形方程式系を設定することを含み、該線形方程式系は、
【数１４１】
0005616060.tif 000177
によって与えられ、シーンにおいて描写される少なくとも１つのメッシュの運動を支配し、ここで、
【数１４２】
0005616060.tif 000178
Ｉは、恒等行列であり、Ｍは、該少なくとも１つのメッシュの質量の対角行列であり、
【数１４３】
0005616060.tif 000179
は、ｔｋ時における該少なくとも１つのメッシュの幾何学的状態を表すベクトルであり、
【数１４４】
0005616060.tif 000180
は、ｔｋ時における該少なくとも１つのメッシュ中の各点の速度を表すベクトルであり、
【数１４５】
0005616060.tif 000181
は、ｔｋ時における該少なくとも１つのメッシュの各点上のネット力を表すベクトルである、請求項１に記載の方法。
【請求項９】
前記方法は、前記マッピングに先立って、
前記システムが、ソフトウェアダイナミクスソルバーからシーンを捕捉し、該シーン中に描写される少なくとも１つのメッシュに付けられた属性およびフィールドを前記複数のメモリアレイにマッピングされる前記物理パラメータに変換することと、
前記グラフィックスプロセッサユニットが、該ソフトウェアダイナミクスソルバーのシーングラフにシミュレーション結果をインポートすることと
をさらに含み、
該シミュレーション結果は、前記少なくとも１つのピクセルプロセッサによって演算された前記時刻に対する前記線形方程式系の解に対応する、請求項１に記載の方法。
【請求項１０】
前記グラフィックスプロセッサユニットが、前記少なくとも１つのＧＰＵで実行するシェーダーとして、前記シーンにおいて描写される前記メッシュ上に作用する力を表すことをさらに含む、請求項１に記載の方法。
【請求項１１】
コンピュータプログラムが記録されたコンピュータ読取可能格納媒体であって、該コンピュータプログラムは、少なくとも１つのグラフィックスプロセッサユニット（ＧＰＵ）に物理シミュレーションを行わせる制御ロジックを含み、該少なくとも１つのＧＰＵは、複数のメモリアレイと通信するように適合されており、かつ、少なくとも１つのピクセルプロセッサを含み、
該制御ロジックは、
コンピュータ読取可能第１プログラムコードであって、該コードは、該少なくとも１つのＧＰＵに、少なくとも１つのメッシュに関連した該コンピュータ格納媒体に格納された物理パラメータを該複数のメモリアレイにマッピングさせることによって、シーンに描写された該少なくとも１つのメッシュの運動を支配する線形方程式系を格納する、コンピュータ読取可能第１プログラムコードと、
コンピュータ読取可能第２プログラムコードであって、該コードは、該少なくとも１つのピクセルプロセッサを用いて、該少なくとも１つのＧＰＵに、該複数のメモリアレイ中のデータに演算を行わせることによって、ある時刻に対する該線形方程式系を解く、コンピュータ読取可能第２プログラムコードと
を備え、
該第２プログラムコードは、該少なくとも１つのＧＰＵに、該少なくとも１つのメッシュに関連した該物理パラメータ間の相補的なジョイント力に対して演算を行う一組の同一のレンダリングサブパスを実行することをさらに行わせ、
該時刻に対する該線形方程式系の解を表す変更されたデータは、該複数のメモリアレイに格納される、コンピュータ読取可能格納媒体。
【請求項１２】
前記制御ロジックは、
コンピュータ読取可能第３プログラムコードであって、該コードは、前記複数のメモリアレイ中の前記変更されたデータに基づいて、前記少なくとも１つのＧＰＵに、前記時刻に対する前記シーン中に描写される前記少なくとも１つのメッシュの運動を更新させる、コンピュータ読取可能第３プログラムコードをさらに備える、請求項１１に記載のコンピュータ読取可能格納媒体。
【請求項１３】
前記制御ロジックは、
コンピュータ読取可能第３プログラムコードであって、該コードは、前記少なくとも１つのＧＰＵに、前記時刻に対する前記少なくとも１つのメッシュを含む少なくとも１つの衝突を識別させる、コンピュータ読取可能第３プログラムコードと、
コンピュータ読取可能第４プログラムコードであって、該コードは、（ｉ）前記複数のメモリアレイ中の前記変更されたデータ、および、（ｉｉ）該コンピュータ読取可能第３プログラムコードによって識別された前記少なくとも１つの衝突に基づいて、該少なくとも１つのＧＰＵに、該時刻に対する該シーン中に描写される該少なくとも１つのメッシュの運動を更新させる、コンピュータ読取可能第４プログラムコードと
をさらに備える、請求項１１に記載のコンピュータ読取可能格納媒体。
【請求項１４】
前記制御ロジックは、
コンピュータ読取可能第３プログラムコードであって、該コードは、前記少なくとも１つのＧＰＵに、前記変更されたデータに演算を行わせることによって、次の時刻に対する前記線形方程式系を解く、コンピュータ読取可能第３プログラムコードをさらに含み、
該次の時刻に対する該線形方程式系の解を表すさらなる変更されたデータは、前記複数のメモリアレイに格納される、請求項１１に記載のコンピュータ読取可能格納媒体。
【請求項１５】
前記制御ロジックは、
コンピュータ読取可能第４プログラムコードであって、該コードは、前記複数のメモリアレイ中の前記さらなる変更されたデータに基づいて、前記少なくとも１つのＧＰＵに、前記次の時刻に対する前記シーン中に描写される前記少なくとも１つのメッシュの運動を更新させる、コンピュータ読取可能第４プログラムコードをさらに備える、請求項１４に記載のコンピュータ読取可能格納媒体。
【請求項１６】
前記制御ロジックは、
コンピュータ読取可能第４プログラムコードであって、該コードは、前記少なくとも１つのＧＰＵに、前記次の時刻に対する前記少なくとも１つのメッシュを含む少なくとも１つの衝突を識別させる、コンピュータ読取可能第４プログラムコードと、
コンピュータ読取可能第５プログラムコードであって、該コードは、（ｉ）前記複数のメモリアレイ中の前記さらなる変更されたデータ、および、（ｉｉ）該コンピュータ読取可能第４プログラムコードによって識別された該少なくとも１つの衝突に基づいて、該少なくとも１つのＧＰＵに、該次の時刻に対する該シーン中に描写される該少なくとも１つのメッシュの運動を更新させる、コンピュータ読取可能第５プログラムコードと
をさらに備えている、請求項１４に記載のコンピュータ読取可能格納媒体。
【請求項１７】
前記コンピュータ読取可能第２プログラムコードは、
コードであって、前記少なくとも１つのＧＰＵに、前記複数のメモリアレイ中の前記データに演算を行わせることによって、インプリシットに前記線形方程式系を積分することによって、ある時刻に対する該線形方程式系を解くコードを含み、
該時刻に対する該線形方程式系の解を表す変更されたデータは、該複数のメモリアレイに格納される、請求項１１に記載のコンピュータ読取可能格納媒体。
【請求項１８】
前記コンピュータ読取可能第１プログラムコードは、
コードであって、前記少なくとも１つのＧＰＵに、複数のメモリアレイにデータを格納させることによって、線形方程式系を設定するコードを備え、該線形方程式系は、
【数１４６】
0005616060.tif 000182
によって与えられ、シーンにおいて描写される前記少なくとも１つのメッシュの運動を支配し、ここで、
【数１４７】
0005616060.tif 000183
Ｉは、恒等行列であり、Ｍは、前記少なくとも１つのメッシュの質量の対角行列であり、
【数１４８】
0005616060.tif 000184
は、ｔｋ時における該少なくとも１つのメッシュの幾何学的状態を表すベクトルであり、
【数１４９】
0005616060.tif 000185
は、ｔｋ時における該少なくとも１つのメッシュ中の各点の速度を表すベクトルであり、
【数１５０】
0005616060.tif 000186
は、ｔｋ時における該少なくとも１つのメッシュ中の各点上のネット力を表すベクトルである、請求項１１に記載のコンピュータ読取可能格納媒体。
【請求項１９】
前記制御ロジックは、
コンピュータ読取可能第３プログラムコードであって、該コードは、前記少なくとも１つのＧＰＵに、ソフトウェアダイナミクスソルバーからシーンを捕捉させ、該シーン中に描写される少なくとも１つのメッシュに付けられた属性およびフィールドを前記複数のメモリアレイにマッピングされる前記物理パラメータに変換する、コンピュータ読取可能第３プログラムコードと、
コンピュータ読取可能第４プログラムコードであって、該コードは、該少なくとも１つのＧＰＵに、該ソフトウェアダイナミクスソルバーのシーングラフにシミュレーション結果をインポートさせる、コンピュータ読取可能第４プログラムコードと
をさらに備え、
該シミュレーション結果は、前記時刻に対する前記線形方程式系の解に対応する、請求項１１に記載のコンピュータ読取可能格納媒体。
【請求項２０】
前記制御ロジックは、
前記少なくとも１つのＧＰＵに、前記シーンにおいて描写される前記メッシュに作用する力をシミュレーションさせるコンピュータ読取可能第３プログラムコードをさらに備える、請求項１１に記載のコンピュータ読取可能格納媒体。
【請求項２１】
システムであって、該システムは、
少なくとも１つのメッシュに関連した物理パラメータを表すデータを格納する複数のメモリアレイを含むメモリであって、該複数のメモリアレイは、該データを格納することによって、該メモリに格納されたシーンにおいて描写される該少なくとも１つのメッシュの運動を支配する線形方程式系を格納する、メモリと、
物理シミュレーションを行うように構成され、かつ、該メモリと通信するように適合された少なくとも１つのグラフィックスプロセッサユニット（ＧＰＵ）であって、該少なくとも１つのＧＰＵのそれぞれは、該複数のメモリアレイにおける該データに演算を行うことによってある時刻に対する該線形方程式系を解く、該メモリに結合された少なくとも１つのピクセルプロセッサを含む、少なくとも１つのグラフィックスプロセッサユニット（ＧＰＵ）と
を備え、
該少なくとも１つのＧＰＵは、該少なくとも１つのメッシュに関連した該物理パラメータ間の相補的なジョイント力に対して演算を行う一組の同一のレンダリングサブパスを実行するようにさらに構成され、
該時刻に対する該線形方程式系の解を表す変更されたデータは、該複数のメモリアレイに格納される、システム。
【請求項２２】
レンダリングエンジンであって、前記複数のメモリアレイにおける前記変更されたデータに基づいて、前記時刻に対する前記シーンにおいて描写される前記少なくとも１つのメッシュの描写を更新する、レンダリングエンジンをさらに備える、請求項２１に記載のシステム。
【請求項２３】
前記少なくとも１つのピクセルプロセッサは、前記時刻に対する前記少なくとも１つのメッシュを含む少なくとも１つの衝突を識別し、前記システムは、
レンダリングエンジンであって、（ｉ）前記複数のメモリアレイにおける前記変更されたデータ、および、（ｉｉ）該時刻において識別された該少なくとも１つの衝突に基づいて、該時刻に対する前記シーンにおいて描写される前記少なくとも１つのメッシュの描写を更新する、レンダリングエンジンをさらに備える、請求項２１に記載のシステム。
【請求項２４】
前記少なくとも１つのピクセルプロセッサは、前記変更されたデータに演算を行うことによって、次の時刻に対する前記線形方程式系を解き、該次の時刻に対する該線形方程式系の解を表すさらなる変更されたデータは、前記複数のメモリアレイに格納される、請求項２１に記載のシステム。
【請求項２５】
前記複数のメモリアレイにおける前記さらなる変更されたデータに基づいて、前記次の時刻に対する前記シーンにおいて描写される前記少なくとも１つのメッシュの描写を更新するレンダリングエンジンをさらに備える、請求項２４に記載のシステム。
【請求項２６】
前記少なくとも１つのピクセルプロセッサは、前記次の時刻に対する前記少なくとも１つのメッシュを含む少なくとも１つの衝突を識別し、前記システムは、
（ｉ）前記複数のメモリアレイにおける前記さらなる変更されたデータ、および、（ｉｉ）該次の時刻において識別された該少なくとも１つの衝突に基づいて、該次の時刻に対する前記シーンにおいて描写される前記少なくとも１つのメッシュの描写を更新するレンダリングエンジンをさらに備える、請求項２４に記載のシステム。
【請求項２７】
前記少なくとも１つのピクセルプロセッサは、前記複数のメモリアレイにおける前記データに演算を行うことによって、前記線形方程式系をインプリシットに積分して該線形方程式系を解くことによって、ある時刻に対する該線形方程式系を解き、該時刻に対する該線形方程式系の解を表す変更されたデータは、該複数のメモリアレイに格納される、請求項２１に記載のシステム。
【請求項２８】
前記線形方程式系は、
【数１５１】
0005616060.tif 000187
によって与えられ、ここで
【数１５２】
0005616060.tif 000188
Ｉは、恒等行列であり、Ｍは、前記少なくとも１つのメッシュの質量の対角行列であり、
【数１５３】
0005616060.tif 000189
は、ｔｋ時における該少なくとも１つのメッシュの幾何学的状態を表すベクトルであり、
【数１５４】
0005616060.tif 000190
は、ｔｋ時における該少なくとも１つのメッシュ中の各点の速度を表すベクトルであり、
【数１５５】
0005616060.tif 000191
は、ｔｋ時における該少なくとも１つのメッシュ中の各点上のネット力を表すベクトルである、請求項２１に記載のシステム。
【請求項２９】
ソフトウェアダイナミクスソルバーからシーンを捕捉し、該シーンにおいて描写される少なくとも１つのメッシュに付けられた属性およびフィールドを前記複数のメモリアレイにおいて格納される前記物理パラメータに変換するシーンエクスポーターと、
該ソフトウェアダイナミクスソルバーのシーングラフにシミュレーション結果をインポートするシーンインポーターと
をさらに備え、
該シミュレーション結果は、前記少なくとも１つのピクセルプロセッサによって演算された前記時刻に対する前記線形方程式系の解に対応する、請求項２１に記載のシステム。
【請求項３０】
前記少なくとも１つのＧＰＵ上で、前記シーンにおいて描写される前記メッシュに作用する力を表すために実行するシェーダーをさらに備える、請求項２１に記載のシステム。
【請求項３１】
少なくとも１つのグラフィクスプロセッサユニット（ＧＰＵ）を生成するための命令を含む、コンピュータ読取可能格納媒体であって、該少なくとも１つのＧＰＵは、複数のメモリアレイと通信するように適合されており、かつ、少なくとも１つのピクセルプロセッサを含み、該命令は、実行されるときには、該少なくとも１つのＧＰＵを作成するように適合され、
該少なくとも１つのＧＰＵは、
少なくとも１つのメッシュに関連した物理パラメータを該複数のメモリアレイにマッピングすることによって、シーンに描写された該少なくとも１つのメッシュの運動を支配する線形方程式系を格納し、
該少なくとも１つのピクセルプロセッサを用いて該複数のメモリアレイ中のデータに演算を行うことによって、ある時刻に対する該線形方程式系を解く
ように適合され、
該少なくとも１つのＧＰＵは、該少なくとも１つのメッシュに関連した該物理パラメータ間の相補的なジョイント力に対して演算を行う一組の同一のレンダリングサブパスを実行するようにさらに適合され、
該時刻に対する該線形方程式系の解を表す変更されたデータは、該複数のメモリアレイに格納される、コンピュータ読取可能格納媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概してグラフィックス処理装置に向けられ、より具体的には、グラフィックスプロセッサを用いてゲームの物理シミュレーションを行うことに向けられる。
【背景技術】
【０００２】
コンピュータ系上で作動しているビデオゲームなどのアプリケーションは、物理シミュレーションおよびグラフィックスレンダリングの両方を必要とし得る。例えば、図１は、ビデオゲームのシーンにおいて描かれる１つ以上のキャラクターの運動を演算し、そして表示するための、典型的なパイプラインのブロック図１００を図示する。ステップ１１０において、物理シミュレーションが行われることによって、そのシーンに描かれる１つ以上のキャラクターの運動を決定する。次いでステップ１２０において、物理シミュレーションの結果が、エンドユーザーによって視覚化されるために図形として描写される。
【０００３】
概して、ステップ１１０の物理シミュレーションは、中央処理装置（ＣＰＵ）上、またはコンピュータ系の専用デバイス上で実行される、物理エンジンによって行われる。次いで、ステップ１２０のグラフィックスレンダリングが、グラフィックスプロセッシングユニット（ＧＰＵ）によって行われる。しかし、最終的には、物理エンジンによってもたらされた結果は、ビデオゲーム（または、より一般的には、アプリケーション）のグラフィックスを修正するために用いられ、故に、何らかの形式において、ＧＰＵに伝えられることとなる。物理エンジンからの結果は、レンダリングのためにＧＰＵに伝えられなくてはならないので、待ち時間および帯域幅の問題が起こり得る。さらに、一般的なプロセッシングユニットのように、ＣＰＵは、ＧＰＵの並列処理能力を有さない。
【０００４】
上述の事項をふまえると、必要なものは、１つ以上のＧＰＵ上で物理シミュレーションを行う方法、コンピュータプログラム製品および系である。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明の実施形態は、方法、コンピュータプログラム製品、およびシステムを含み得、ＧＰＵ上で利用可能な並行処理能力を利用することによって、一般的なＣＰＵ上で実行される物理シミュレーションと比較して、より速いフレーム速度を可能にする。さらに、そのような方法、コンピュータプログラム製品、およびシステムは、物理シミュレーションの実行において、インプリシットな積分技術を利用することによって、エクスプリシットな積分技術において必要な、相対的に小さな時間ステップを防止する。さらに、手続上の力およびトルクは、ＧＰＵ上で実行するシェーダープログラムとして表され得る。加えて、ＧＰＵベースの物理シミュレーターは、通常はコンピュータシステムで物理シミュレーションを実行する、従来型のソフトウェアダイナミクスソルバーを自動的に置換することが可能であり得る。本発明の実施形態は、１つ以上のＧＰＵ上で物理シミュレーションを行うための、方法、コンピュータプログラム製品、およびシステムを提供することによって、上記に識別されたニーズを満たす。１つ以上のＧＰＵ上で物理シミュレーションを行うための、そのような方法、コンピュータプログラム製品、およびシステムは、ＧＰＵ上で利用可能な並行処理能力を利用することによって、通常のＣＰＵ上で実行される物理シミュレーションと比較してより速いフレーム速度を可能にする。さらに、そのような方法、コンピュータプログラム製品、およびシステムは、実施形態においてインプリシットな積分技術を利用することによって、物理シミュレーションを行い、これによって、エクスプリシットな積分技術において必要な、相対的に小さな時間ステップを防止する。さらに、本発明の実施形態に従うと、手続き上の力および／またはトルクは、ＧＰＵ上で実行するシェーダープログラムとして表すことが可能である。加えて、本発明の実施形態に従ったＧＰＵベースの物理シミュレーターは、通常はコンピュータシステム上で物理シミュレーションを実行する、従来型のソフトウェアダイナミクスソルバーを自動的に置換するために用いられ得る。
【０００６】
本発明の実施形態に従うと、少なくとも１つのＧＰＵ上で物理シミュレーションを行うための方法が提供される。該方法は、以下のステップを含む。まず、少なくとも１つのメッシュに関連した物理属性を表すデータは、複数のビデオメモリアレイに格納されることによって、シーンに描写される少なくとも１つのメッシュの運動を支配する線形方程式系を設定する。ついで、少なくとも１つのピクセルプロセッサを用いて複数のビデオメモリアレイにおけるデータに演算が行われることによって、時刻に対する線形方程式系を解く。ここで、時刻に対する線形方程式系に対する解を表す修正済みデータは、複数のビデオデータメモリに格納される。
【０００７】
本発明の別の実施形態に従うと、コンピュータプログラム製品が提供され、該コンピュータプログラム製品は、制御ロジックを中に格納し、少なくとも１つのＧＰＵに物理シミュレーションを行わせる、コンピュータ使用可能媒体を備える。該制御ロジックは、コンピュータ読取可能な第１および第２のプログラムコードを含む。コンピュータ読取可能第１プログラムコードは、少なくとも１つのＧＰＵに、複数のビデオデータアレイに、少なくとも１つのメッシュに関連した物理属性を表すデータを格納することによって、シーンに描写される少なくとも１つのメッシュの運動を支配する、線形方程式系を設定する。コンピュータ読取可能第２プログラムコードは、少なくとも１つのＧＰＵに、複数のビデオメモリアレイにおけるデータに演算を行わせることによって、時刻に対する線形方程式系を解く。ここで、時刻に対する線形方程式系に対する解を表す修正済みデータは、複数のビデオデータメモリに格納される。
【０００８】
本発明のさらなる実施形態に従うと、物理シミュレーションを行うためのシステムが提供される。該システムは、複数のビデオメモリアレイを格納するメモリと、該メモリに結合された少なくとも１つのピクセルプロセッサとを含む。複数のビデオメモリアレイは、少なくとも１つのメッシュに関連した物理パラメータを表すデータを格納することによって、シーンに描写される少なくとも１つのメッシュの運動を支配する線形方程式系を設定する。少なくとも１つのピクセルプロセッサは、複数のビデオメモリアレイにおけるデータに演算を行うことによって、時刻に対する線形方程式系を解き、その結果として、時刻に対する線形方程式系に対する解を表す修正済みデータをもたらす。
【０００９】
本発明のさらなる機能および有用性、ならびに本発明のさまざまな実施形態の構造および動作は、添付の図面を参照しながら、以下に詳述される。本発明は、本明細書に記述された特定の実施形態に限定されるものではないことに留意されたい。そのような実施形態は、例示目的のためだけに、本明細書において提示される。追加的な実施形態は、本明細書に含まれる教示を基に、当業者に明確である。
【００１０】
添付の図面は、本明細書において具体化され、明細書の一部を構成し、本発明を例示し、本記述とともに、本発明の原理を説明するためにさらに役立ち、当業者が本発明を作成および利用することを可能にする。
（項目１）
少なくとも１つのグラフィックスプロセッサユニット（ＧＰＵ）上で物理シミュレーションを行う方法であって、該方法は、
少なくとも１つのメッシュに関連した物理パラメータを複数のメモリアレイにマッピングすることによって、シーンに描写された該少なくとも１つのメッシュの運動を支配する線形方程式系を設定することと、
少なくとも１つのピクセルプロセッサを用いて該複数のメモリアレイ中のデータに演算を行うことによって、ある時刻に対する線形方程式系を解くことと
を包含し、
該時刻に対する線形方程式系の該解を表す変更されたデータは、該複数のメモリアレイに格納される、方法。
（項目２）
上記複数のメモリアレイ中の上記変更されたデータに基づいて、上記時刻に対する上記シーンにおいて描写される、上記１つ以上のメッシュの運動を更新することをさらに含む、項目１に記載の方法。
（項目３）
上記時刻に対する上記少なくとも１つのメッシュを含む、少なくとも１つの衝突を識別することと、
（ｉ）上記複数のメモリアレイ中の上記変更されたデータ、および（ｉｉ）該識別された少なくとも１つの衝突、に基づいて、上記時刻に対する上記シーン中に描写される上記少なくとも１つのメッシュの運動を更新することと
をさらに含む、項目１に記載の方法。
（項目４）
上記ピクセルプロセッサを用いて上記変更されたデータに演算を行うことによって、次の時刻に対する線形方程式系を解くことをさらに含み、該次の時刻に対する線形方程式系に対する解を表す変更されたデータは、上記複数のメモリアレイに格納される、項目１に記載の方法。
（項目５）
上記複数のメモリアレイ中の上記さらなる変更されたデータに基づいて、上記次の時刻に対する上記シーン中に描写される少なくとも１つのメッシュの運動を更新することをさらに含む、項目４に記載の方法。
（項目６）
上記次の時刻に対する上記少なくとも１つのメッシュを含む、少なくとも１つの衝突を識別することと、
（ｉ）上記複数のメモリアレイ中の上記変更されたデータ、および（ｉｉ）該識別された少なくとも１つの衝突、に基づいて、上記次の時刻に対する上記シーン中に描写される上記少なくとも１つのメッシュの運動を更新することと
をさらに含む、項目４に記載の方法。
（項目７）
演算を行うことは、
少なくとも１つのピクセルプロセッサを用いて上記複数のメモリアレイ中のデータに演算を行うことによって、インプリシットに上記線形方程式系を積分することによって、ある時刻に対する該線形方程式系を解くことを含み、
上記時刻に対する該線形方程式系の該解を表す変更されたデータは、該複数のメモリアレイに格納される、項目１に記載の方法。
（項目８）
上記格納することは、
複数のメモリアレイにデータを格納することによって、線形方程式系を設定することを含み、該線形方程式系は、
【数１４１】
0005616060.tif 000002
によって与えられ、シーンにおいて描写される少なくとも１つのメッシュの運動を支配し、ここで、
【数１４２】
0005616060.tif 000003
であり、Ｉは、恒等行列であり、Ｍは該少なくとも１つのメッシュの質量の直交行列であり、
【数１４３】
0005616060.tif 000004
は、ｔｋ時における該少なくとも１つのメッシュの幾何学的状態を表すベクトルであり、
【数１４４】
0005616060.tif 000005
は、ｔｋ時における該少なくとも１つのメッシュ中の各点の速度を表すベクトルであり、
【数１４５】
0005616060.tif 000006
は、ｔｋ時における該少なくとも１つのメッシュの各点上のネット力を表すベクトルである、項目１に記載の方法。
（項目９）
上記方法は、マッピングに先立って、さらに、
ソフトウェアダイナミクスソルバーからシーンを捕捉し、該シーン中に描写される少なくとも１つのメッシュに付けられた属性およびフィールドを、上記複数のメモリアレイにマッピングされる物理パラメータに変換することと、
該ソフトウェアダイナミクスソルバーのシーングラフにシミュレーション結果をインポートすることと
をさらに含み、
該シミュレーション結果は、上記少なくとも１つのピクセルプロセッサによって演算された上記時刻に対する上記線形方程式系に対する解に対応する、項目１に記載の方法。
（項目１０）
上記少なくとも１つのＧＰＵで実行するシェーダーとして、該シーンにおいて描写される該メッシュ上に作用する力を表すことをさらに含む、項目１に記載の方法。
（項目１１）
制御ロジックを中に格納しているコンピュータ使用可能媒体を備え、少なくとも１つのグラフィックスプロセッサユニット（ＧＰＵ）に物理シミュレーションを行わせるコンピュータプログラム製品であって、該制御ロジックは、
コンピュータ読取可能第１プログラムコードであって、該コードは、該少なくとも１つのＧＰＵに、少なくとも１つのメッシュに関連した物理パラメータを複数のメモリアレイにマッピングさせることによって、シーンに描写された該少なくとも１つのメッシュの運動を支配する線形方程式系を設定する、コンピュータ読取可能第１プログラムコードと、
コンピュータ読取可能第２プログラムコードであって、該コードは、該少なくとも１つのＧＰＵに、該複数のメモリアレイ中のデータに演算を行わせることによって、ある時刻の線形方程式系を解く、コンピュータ読取可能第２プログラムコードと
を備え、
該時刻に対する線形方程式系に対する解を表す変更されたデータは、該複数のメモリアレイに格納される、コンピュータプログラム製品。
（項目１２）
コンピュータ読取可能第３プログラムコードであって、該コードは、上記複数のメモリアレイ中の上記変更されたデータに基づいて、上記少なくとも１つのＧＰＵに、上記時刻に対する上記シーン中に描写される上記少なくとも１つのメッシュの運動を更新させる、コンピュータ読取可能第３プログラムコードをさらに備える、項目１１に記載のコンピュータプログラム製品。
（項目１３）
コンピュータ読取可能第３プログラムコードであって、該コードは、上記少なくとも１つのＧＰＵに、上記時刻の上記少なくとも１つのメッシュを含む少なくとも１つの衝突を識別させる、コンピュータ読取可能第３プログラムコードと、
コンピュータ読取可能第４プログラムコードであって、該コードは、（ｉ）上記複数のメモリアレイ中の上記変更されたデータ、および（ｉｉ）該識別された少なくとも１つの衝突、に基づいて、該少なくとも１つのＧＰＵに、該時刻に対する該シーン中に描写される該少なくとも１つのメッシュの運動を更新させる、コンピュータ読取可能第４プログラムコードとをさらに備える、項目１１に記載のコンピュータプログラム製品。
（項目１４）
コンピュータ読取可能第３プログラムコードであって、該コードは、上記少なくとも１つのＧＰＵに、上記変更されたデータに演算を行わせることによって、次の時刻に対する線形方程式系を解く、コンピュータ読取可能第３プログラムコードをさらに含み、
該次の時刻に対する該線形方程式系に対する解を表すさらなる変更されたデータは、上記複数のメモリアレイに格納される、項目１１に記載のコンピュータプログラム製品。
（項目１５）
コンピュータ読取可能第４プログラムコードであって、該コードは、上記複数のメモリアレイ中の上記さらなる変更されたデータに基づいて、上記少なくとも１つのＧＰＵに、上記次の時刻に対する上記シーン中に描写される上記少なくとも１つのメッシュの運動を更新させる、コンピュータ読取可能第４プログラムコードをさらに備える、項目１４に記載のコンピュータプログラム製品。
（項目１６）
コンピュータ読取可能第４プログラムコードであって、該コードは、上記少なくとも１つのＧＰＵに、上記次の時刻に対する上記少なくとも１つのメッシュを含む少なくとも１つの衝突を識別させる、コンピュータ読取可能第４プログラムコードと、
コンピュータ読取可能第５プログラムコードであって、該コードは、（ｉ）上記複数のメモリアレイ中の上記さらなる変更されたデータ、および（ｉｉ）該コンピュータ読取可能第４プログラムコードによって識別された該少なくとも１つの衝突、に基づいて、該少なくとも１つのＧＰＵに、該次の時刻に対する該シーン中に描写される該少なくとも１つのメッシュの運動を更新させる、コンピュータ読取可能第５プログラムコードと
をさらに備えている、項目１４に記載のコンピュータプログラム製品。
（項目１７）
上記コンピュータ読取可能第２プログラムコードは、
コードであって、上記少なくとも１つのＧＰＵに、上記複数のメモリアレイ中の上記データに演算を行わせることによって、インプリシットに上記線形方程式系を積分することによって、ある時刻に対する該線形方程式系を解くコードを含み、
該時刻に対する線形方程式系に対する解を表す変更されたデータは、該複数のメモリアレイに格納される、項目１１に記載のコンピュータプログラム製品。
（項目１８）
上記コンピュータ読取可能第１プログラムコードは、
コードであって、上記少なくとも１つのＧＰＵに、複数のメモリアレイにデータを格納させることによって、線形方程式系を設定する、コードを備え、該線形方程式系は、
【数１４６】
0005616060.tif 000007
によって与えられ、シーンにおいて描写される上記少なくとも１つのメッシュの運動を支配し、ここで、
【数１４７】
0005616060.tif 000008
であり、ここで、Ｉは、恒等行列であり、Ｍは上記少なくとも１つのメッシュの質量の直交行列であり、
【数１４８】
0005616060.tif 000009
は、ｔｋ時における該少なくとも１つのメッシュの幾何学的状態を表すベクトルであり、
【数１４９】
0005616060.tif 000010
は、ｔｋ時における該少なくとも１つのメッシュ中の各点の速度を表すベクトルであり、
【数１５０】
0005616060.tif 000011
は、ｔｋ時における該少なくとも１つのメッシュ中の各点上のネット力を表すベクトルである、項目１１に記載のコンピュータプログラム製品。
（項目１９）
コンピュータ読取可能第３プログラムコードであって、該コードは、上記少なくとも１つのＧＰＵに、ソフトウェアダイナミクスソルバーからシーンを捕捉させ、該シーン中に描写される少なくとも１つのメッシュに付けられた属性およびフィールドを、上記複数のメモリアレイにマッピングされる上記物理パラメータに変換する、コンピュータ読取可能第３プログラムコードと、
コンピュータ読取可能第４プログラムコードであって、該コードは、該少なくとも１つのＧＰＵに、該ソフトウェアダイナミクスソルバーのシーングラフにシミュレーション結果をインポートさせる、コンピュータ読取可能第４プログラムコードと
をさらに備え、
該シミュレーション結果は、上記時刻に対する上記線形方程式系に対する解に対応する、項目１１に記載のコンピュータプログラム製品。
（項目２０）
上記少なくとも１つのＧＰＵに、上記シーンにおいて描写される上記メッシュに作用する力をシミュレーションさせるコンピュータ読取可能第３プログラムコードをさらに備える、項目１１に記載のコンピュータプログラム製品。
（項目２１）
物理シミュレーションを行うためのシステムであって、該システムは、
メモリであって、少なくとも１つのメッシュに関連した物理パラメータを表すデータを格納する複数のメモリアレイを含み、シーンにおいて描写される該少なくとも１つのメッシュの運動を支配する線形方程式系を設定するための、メモリと、
該複数のメモリアレイにおける該データに演算を行うことによってある時刻に対する該線形方程式系を解く、該メモリに結合された少なくとも１つのピクセルプロセッサと
を備え、
該時刻に対する該線形方程式系の該解を表す変更されたデータは、該複数のメモリアレイに格納される、システム。
（項目２２）
レンダリングエンジンであって、上記複数のメモリアレイにおける上記変更されたデータに基づいて、上記時刻に対する上記シーンにおいて描写される上記少なくとも１つのメッシュの描写を更新する、レンダリングエンジンをさらに備える、項目２１に記載のシステム。
（項目２３）
上記ピクセルプロセッサは、上記時刻に対する上記少なくとも１つのメッシュを含む少なくとも１つの衝突を識別し、該システムは、
レンダリングエンジンであって、（ｉ）上記複数のメモリアレイにおける上記変更されたデータ、および（ｉｉ）該時刻において識別された該少なくとも１つの衝突に基づいて、該時刻に対する上記シーンにおいて描写される上記少なくとも１つのメッシュの描写を更新する、レンダリングエンジンをさらに備える、項目２１に記載のシステム。
（項目２４）
上記ピクセルプロセッサは、上記変更されたデータに演算を行うことによって、次の時刻に対する線形方程式系を解き、該次の時刻に対する該線形方程式系に対する解を表すさらなる変更されたデータは、上記複数のメモリアレイに格納される、項目２１に記載のシステム。
（項目２５）
レンダリングエンジンであって、上記複数のメモリアレイにおける上記さらなる修正済みのデータに基づいて、上記次の時刻に対する上記シーンにおいて描写される上記少なくとも１つのメッシュの描写を更新する、レンダリングエンジンをさらに備える、項目２４に記載のシステム。
（項目２６）
上記ピクセルプロセッサは、上記次の時刻に対する上記少なくとも１つのメッシュを含む少なくとも１つの衝突を識別し、該システムは、
レンダリングエンジンであって、（ｉ）上記複数のメモリアレイにおける上記変更されたデータ、および（ｉｉ）該次の時刻において識別された該少なくとも１つの衝突に基づいて、該次の時刻に対する上記シーンにおいて描写される上記少なくとも１つのメッシュの描写を更新する、レンダリングエンジンをさらに備える、項目２４に記載のシステム。
（項目２７）
上記ピクセルプロセッサは、上記複数のメモリアレイにおける上記データに演算を行うことによって、上記線形方程式系をインプリシットに積分することによってある時刻に対する該線形方程式系を解き、該時刻に対する該線形方程式系に対する該解を表す変更されたデータは、該複数のメモリアレイに格納される、項目２１に記載のシステム。
（項目２８）
上記線形方程式系は、
【数１５１】
0005616060.tif 000012
によって与えられ、ここで
【数１５２】
0005616060.tif 000013
であり、Ｉは、恒等行列であり、Ｍは上記少なくとも１つのメッシュの質量の直交行列であり、
【数１５３】
0005616060.tif 000014
は、ｔｋ時における該少なくとも１つのメッシュの幾何学的状態を表すベクトルであり、
【数１５４】
0005616060.tif 000015
は、ｔｋ時における該少なくとも１つのメッシュ中の各点の速度を表すベクトルであり、
【数１５５】
0005616060.tif 000016
は、ｔｋ時における該少なくとも１つのメッシュ中の各点上のネット力を表すベクトルである、項目２１に記載のシステム。
（項目２９）
シーンエクスポーターであって、ソフトウェアダイナミクスソルバーからシーンを捕捉し、該シーンにおいて描写される少なくとも１つのメッシュに付けられた属性およびフィールドを、上記複数のメモリアレイにおいて格納される上記物理パラメータに変換する、シーンエクスポーターと、
シーンインポーターであって、該ソフトウェアダイナミクスソルバーのシーングラフにシミュレーション結果をインポートする、シーンインポーターと
をさらに備え、
該シミュレーション結果は、上記少なくとも１つのピクセルプロセッサによって演算された上記時刻に対する上記線形方程式系に対する上記解に対応する、項目２１に記載のシステム。
（項目３０）
少なくとも１つのＧＰＵ上で、上記シーンにおいて描写される上記メッシュに作用する力を表すために実行するシェーダーをさらに備える、項目２１に記載のシステム。
（項目３１）
少なくとも１つのグラフィックスプロセッサユニット（ＧＰＵ）上で物理シミュレーションを行うための方法であって、該方法は、
該少なくとも１つのＧＰＵにシミュレーション定義データを送信することと、
該転送されたシミュレーション定義に応答する該少なくとも１つのＧＰＵからのシミュレーション結果を受け取ることと
を包含する、方法。
（項目３２）
上記少なくとも１つのＧＰＵにシミュレーション定義データを転送することは、該少なくとも１つのＧＰＵに、シーンデータ、シミュレーションデータ、アクターデータ、ジョイントデータ、およびフィードバックデータのうちの少なくとも１つを送信することを含む、項目３１に記載の方法。
（項目３３）
上記送信は、上記少なくとも１つのＧＰＵに、マークアップ言語フォーマットのシミュレーション定義データを送信することを含む、項目３１に記載の方法。
（項目３４）
少なくとも１つのグラフィックスプロセッサユニット（ＧＰＵ）上で物理シミュレーションを行うための方法であって、該方法は、
シミュレーション定義データをアプリケーションプログラミングインタフェース（ＡＰＩ）コマンドに変換することと、
該変換されたシミュレーション定義データに応答して、該少なくとも１つのＧＰＵ上で物理シミュレーションを行うことによって、シミュレーション結果データを生成することと
を包含する、方法。
（項目３５）
上記変換することは、上記シミュレーション定義データからシーンデータ構造を生成することを含む、項目３４に記載の方法。
（項目３６）
上記物理シミュレーションを行うことは、
上記シミュレーション定義データに対応する線形方程式系を設定することと、
該線形方程式系を解くことと、
該線形方程式系に対する解に基づいて衝突を検出することと
を含む、項目３４に記載の方法。
（項目３７）
物理シミュレーションを行うための、コンピュータベースの方法であって、該方法は、
ソフトウェアダイナミクスソルバーデータを、少なくとも１つのグラフィクスプロセッサユニット（ＧＰＵ）に対するシミュレーション定義データに変換することと、
該変換されたデータに応答して、該少なくとも１つのＧＰＵ上で物理シミュレーションを行うことによって、シミュレーション結果データを生成することと
を包含する、方法。
（項目３８）
上記シミュレーション結果データをアプリケーションに送信することをさらに含む、項目３７に記載の方法。
（項目３９）
上記送信することは、上記シミュレーション結果データを上記ソフトウェアダイナミクスソルバーのフォーマットに変換することを含む、項目３８に記載の方法。
（項目４０）
追加的なソフトウェアダイナミクスソルバーデータに応答して、ソフトウェアダイナミクスソルバーに基づく別の物理シミュレーションを行うことをさらに含む、項目３７に記載の方法。
（項目４１）
少なくとも１つのグラフィクスプロセッサユニット（ＧＰＵ）を生成するための命令を含む、コンピュータ読取可能媒体であって、該命令は、実行されるときには、該少なくとも１つのＧＰＵを作成するように適合され、該少なくとも１つのＧＰＵは、
少なくとも１つのメッシュに関連した物理パラメータを複数のメモリアレイにマッピングすることによって、シーンに描写された該少なくとも１つのメッシュの運動を支配する線形方程式系を設定し、
少なくとも１つのピクセルプロセッサを用いて該複数のメモリアレイ中のデータに演算を行うことによって、ある時刻に対する線形方程式系を解く
ように適合され、該時刻に対する該線形方程式系に対する解を表す変更されたデータは、該複数のメモリアレイに格納される、コンピュータ読取可能媒体。
（項目４２）
少なくとも１つのグラフィクスプロセッサユニット（ＧＰＵ）を生成するための命令を含む、コンピュータ読取可能媒体であって、該命令は、実行されるときには、該少なくとも１つのＧＰＵを作成するように適合され、該少なくとも１つのＧＰＵは、
該少なくとも１つのＧＰＵにシミュレーション定義データを送信し、
該送信されたシミュレーション定義データに応答する該少なくとも１つのＧＰＵからのシミュレーション結果を受け取る
ように適合される、コンピュータ読取可能媒体。
（項目４３）
少なくとも１つのグラフィクスプロセッサユニット（ＧＰＵ）を生成するための命令を含む、コンピュータ読取可能媒体であって、該命令は、実行されるときには、該少なくとも１つのＧＰＵを作成するように適合され、該少なくとも１つのＧＰＵは、
ソフトウェアダイナミクスソルバーデータを、該少なくとも１つのＧＰＵに対するシミュレーション定義データに変換し、
該変換されたデータに応答して、該少なくとも１つのＧＰＵ上で物理シミュレーションを行うことによって、シミュレーション結果データを生成する
ように適合される、コンピュータ読取可能媒体。
【図面の簡単な説明】
【００１１】
【図１】図１は、一般的なグラフィクスパイプラインを例示する、ブロック図を図示する。
【図２】図２は、本発明の実施形態に従った、ＧＰＵ上で物理シミュレーションを行うための例示的なワークフローのブロック図を図示する。
【図３】図３は、本発明の実施形態に従った例示的なピクセルプロセッサのブロック図を図示する。
【図４】図４は、本発明の実施形態に従った、例示的な物理／レンダリングパイプラインのブロック図を示す。
【図５】図５は、本発明の実施形態に従った、ＧＰＵ上で行われる例示的な物理シミュレーションパイプラインのブロック図を図示する。
【図６】図６は、本発明の実施形態に従った、ソフトウェアダイナミクスソルバーをバイパスし、これによってＧＰＵ上で物理シミュレーションを行う、例示的なワークフローのブロック図を図示する。
【図７】図７は、本発明の実施形態に従った、ＧＰＵ上で物理シミュレーションを行うための例示的な方法を示す、ブロック図を図示する。
【図８】図８は、本発明の実施形態に従った、クロスをモデル化するための例示的な点メッシュを図示する。
【図９】図９は、本発明の実施形態に従った、ＧＰＵ上で物理をシミュレーションするための、例示的な高レベルな流れ図を図示する。
【図１０】図１０は、本発明の実施形態に従った、ビデオメモリに点メッシュに関連した物理パラメータをマッピングするための、例示的な２ステップの流れ図を図示する。
【図１１】図１１は、本発明の実施形態に従った、ジョイント毎にネット力およびヤコブ行列の対角線上にない部分を決定するための、例示的な流れ図を図示する。
【図１２】図１２は、本発明の実施形態に従った、ジョイント毎にヤコブ行列の対角線上の部分を決定するための、例示的な流れ図を図示する。
【図１３】図１３は、本発明の実施形態が実装され得る、例示的なコンピュータシステムのブロック図を図示する。
【図１４Ａ】図１４Ａは、本発明の実施形態に従った、頂点バッファの内容が３×３の成分のアレイ上にマッピングされる、例示的な方法を図示する。
【図１４Ｂ】図１４Ｂは、本発明の実施形態に従った、インデックスバッファの内容が３×２のグリッド上にマッピングされる、例示的な方法を図示する。
【図１５Ａ】図１５Ａは、頂点バッファが、８個の頂点位置を格納する例を図示する。
【図１５Ｂ】図１５Ｂは、図１５Ａに図示された例示的な頂点バッファに格納された頂点位置に対応する、５個の面をインデックスバッファが格納する例を図示する。
【発明を実施するための形態】
【００１２】
本発明の機能および有用性は、図面と共に取り入れられるとき、以下に述べられた詳細な記述から、より明確となる。該図面において、同様の参照文字は、一貫して対応する要素を識別する。図面において、同様の参照番号は、概して同一で、機能的に類似した、かつ／または構造的に類似した要素を示す。要素が最初に現れる図面は、対応する参照番号において、最も左側の桁によって示される。
【００１３】
Ｉ．１つ以上のＧＰＵ上での物理シミュレーションのあらまし
Ａ．１つ以上のＧＰＵ上で物理シミュレーションを行うための例示的なワークフロー
Ｂ．物理シミュレーションを実行する例示的なＧＰＵ
ＩＩ．例示的な物理シミュレーションインターフェース
Ａ．例示的な物理シミュレーションソフトウェアインターフェース（ＦＹＳＩ）
Ｂ．例示的な物理シーン記述言語（ＦＹＳＬ）
Ｃ．ポイントメッシュ関連の物理パラメータが受信され得る例示的な方法
ＩＩＩ．１つ以上のＧＰＵ上での物理シミュレーションを行うための例示的な方法
Ａ．方法の概観
Ｂ．クロスシミュレーションのための例示的な物理的モデル
Ｃ．ＧＰＵ上でクロスをシミュレートするための例示的な実装
Ｄ．ＦＹＳＬで書き込まれている例示的なコード
ＩＶ．例示的なコンピュータ実装
Ｖ．結び
Ｉ．１つ以上のＧＰＵ上での物理シミュレーションのあらまし
本発明の実施形態は、１つ以上のＧＰＵ上で物理シミュレーションを行うための方法、コンピュータプログラム製品、および系に向けられる。そのような物理シミュレーションは、例えば、（ビデオゲームなどの）アプリケーションのゲーム演算を行うために用いられ得る。本発明の実施形態に従って１つ以上のＧＰＵ上で物理シミュレーションを行うために、メッシュに関連した物理パラメータが、直接的にビデオメモリにマップされる。メッシュは、固体のオブジェクト、容量、流体、またはクロス（ｃｌｏｔｈ）などのあらゆる物理的なオブジェクトを表し得る。ここで詳細に提示されるものは、１つ以上のＧＰＵ上でクロスの物理シミュレーションを行う、例示的な方法である。メッシュがビデオメモリにマッピングされた後に、ＧＰＵの少なくとも１つのピクセルプロセッサが、コンパイル済みシェーダープログラムを用いてビデオメモリ中のデータに演算を行う。ＧＰＵで直接的に物理シミュレーションを行うことは、ＣＰＵ上で行われる典型的な物理シミュレーションに関連する待ち時間および帯域幅の問題を減少させ得る。
【００１４】
明細書を通じて、１つ以上のＧＰＵ上で物理シミュレーションを行うための方法、コンピュータプログラム製品、および系は、例示的な物理シミュレーションソフトウェアインターフェース（ＦＹＳＩと呼ばれる）および物理シーン記述言語（ＦＹＳＬと呼ばれる）の点から記述される。しかし、本発明は、ＦＹＳＩおよびＦＹＳＬに限定されるものではない。本記述に基づいて、１つ以上のＧＰＵ上で物理シミュレーションを行うための方法、コンピュータプログラム製品、および系が、他の種類の物理シミュレーションソフトウェアインタフェースおよび他の種類の物理シーン記述言語を用いて実装され得ることを、当業者は理解されたい。
【００１５】
明細書中の「一実施形態」、「一つの実施形態」、「例示的な実施形態」などへの参照は、記述される実施形態が、特定の機能、構造または特性を含み得ることを示すが、全ての実施形態が、必ずしも特定の機能、構造または特性を含み得るとは限らないことに留意されたい。さらに、そのような表現は、必ずしも同一の実施形態を参照するものではない。また、１つの実施形態に関連して特定の機能、構造または特性が記述されるときには、明記されていようとなかろうと、そのような機能、構造または特性を他の実施形態に関連させて作用させることは、当業者の知識の範囲内であることが提示される。
【００１６】
以下に詳述されるものは、１つ以上のＧＰＵ上において物理シミュレーションをマッピングするための、本発明の実施形態である。第ＩＩ章において、このマッピングを行うための例示的なインターフェースが記述される。第ＩＩＩ章は、１つ以上のＧＰＵ上において物理シミュレーションをおこなうための例示的な方法を提示し、ＧＰＵ上でクロスをシミュレーションするための例示的な方法についての詳しい実装を含む。第ＩＶ章においては、１つ以上のＧＰＵ上で物理シミュレーションを実装するための例示的なコンピュータ系が記述される。しかし、本発明の実施形態を詳述する前に、１つ以上のＧＰＵ上で物理シミュレーションを行う例示的なワークフロー、および物理シミュレーションを実装するための例示的なＧＰＵのあらましを記述することが有用である。
【００１７】
Ａ．１つ以上のＧＰＵ上で物理シミュレーションを行うための例示的なワークフロー
図２は、ＧＰＵ上で物理シミュレーションを行うための例示的なワークフローのブロック図２００を図示する。ブロック図２００は、様々なソフトウェア要素、例えばアプリケーション２１０、物理シミュレーションソフトウェアインターフェース２１２、アプリケーションプログラミングインターフェース２１４、およびドライバ２１６を含み、それらは、力トコンピュータ系上で実行され、ＧＰＵ２１８、（オプション）ＧＰＵ２２０、および／または複数のＧＰＵ（不図示）などのグラフィックスハードウェア要素と相互作用することによって、物理的現象をシミュレーションし、ディスプレイ２２２への出力のためのフレームをレンダリングする。ブロック図２００の個々の要素が、ここにより詳細に記述される。
【００１８】
図２に示されるように、ブロック図２００は、アプリケーション２１０を含む。アプリケーション２１０は、エンドユーザーアプリケーションであり、ビデオゲームアプリケーションなどのグラフィックス処理能力を必要とする。アプリケーション２１０は、物理シミュレーションソフトウェアインターフェース２１２を呼び出す。実施形態において、物理シミュレーションソフトウェアインターフェース２１２は、ＡＴＩ  Ｔｅｃｈｎｏｌｏｇｉｅｓ  Ｉｎｃによって開発されたＦＹＳＩと呼ばれるインターフェースである。ＦＹＳＩが、ここにより詳細に記述される。しかし、上述のように、本発明は、ＦＹＳＩに限定されるものではない。当業者に明確であるように、本発明の真意および範囲から逸脱することなく、他の物理シミュレーションソフトウェアインターフェースをも用いられ得る。物理シミュレーションソフトウェアインターフェース２１２は、物理シミュレーションが行われる、簡単で拡張性のある抽象マシーン（ＳＥＡＭ）を作成する。
【００１９】
物理シミュレーションソフトウェアインターフェース２１２は、ＡＰＩ２１２と通信する。いくつかのＡＰＩは、グラフィックス処理関連における使用のために入手可能である。ＡＰＩは、アプリケーション２１０などのアプリケーションソフトウェアと該アプリケーションソフトウェアが作動するグラフィックスハードウェアとの間での媒介物として開発された。新たなチップセットおよび全く新しいハードウェア技術が勢いを増しながら現れる中で、アプリケーションの開発者にとって、最新のハードウェアの機能を考慮に入れたり、利用することは、困難なことである。また、それぞれのハードウェアの予見可能なセットのために特別にアプリケーションを書き込むことは、ますます困難になりつつある。ＡＰＩは、アプリケーションがあまりにもハードウェアに特有のものであらねばないことを防止する。該アプリケーションは、ハードウェアに直接的に行うのではなく、標準化されたフォーマットでグラフィックスデータおよびコマンドを、ＡＰＩに出力することが可能である。物理シミュレーションソフトウェアインターフェース２１２が、直接的にＡＰＩ２１４と通信するため、利用可能なＡＰＩを修正する必要がない。利用可能なＡＰＩの例としては、ＤｉｒｅｃｔＸ（Ｒ）またはＯｐｅｎＧＬ（Ｒ）を含む。ＡＰＩ２１０は、グラフィックスアプリケーションをランさせる利用可能なＡＰＩのうちのいずれのものでもあり得る。当業者に認識されるように、本発明の代替的な実施形態は、物理シミュレーションソフトウェアインターフェース２１２をＡＰＩ２１４中に集約し、故に単一のソフトウェアインターフェースを用いてアプリケーション２１０を作動させることが可能であり得る。そのような実施形態において、次いでドライバ２１６が修正されることによって、ＡＰＩ２１４を備える物理シミュレーションソフトウェアインターフェース２１２の局面を組み込む単一のインターフェースに応じ得る。
【００２０】
ＡＰＩ２１０は、ドライバ２１６と通信する。ドライバ２１６は、通常はグラフィックスハードウェアの製造者によって書き込まれ、ＡＰＩから受信した標準コードを、グラフィックスハードウェアによって理解されるネイティブのフォーマットに翻訳する。ドライバ２１６はまた、グラフィックスハードウェアへのパフォーマンス設定を指示するための入力を受け取る。そのような入力は、ユーザー、アプリケーションまたはプロセスによって提供され得る。例えば、ユーザーは、グラフィカルユーザーインターフェース（ＧＵＩ）などのユーザーインターフェース（ＵＩ）を用いて入力を提供し得、該グラフィカルユーザーインターフェースは、ドライバ２１６と共にユーザーに供給される。
【００２１】
ドライバ２１６は、第１のＧＰＵ２１８および／または第２のＧＰＵ２２０と通信する。第１のＧＰＵ２１８および第２のＧＰＵ２２０は、グラフィックスチップであり、それぞれが、シェーダーならびに物理シミュレーションおよびグラフィックスレンダリングを行う他の関連ハードウェアを含む。一実施形態において、物理シミュレーションおよびグラフィックスレンダリングは、第１のＧＰＵ２１８などの単一のＧＰＵ上で行われる。代替的な実施形態において、物理シミュレーションは第１のＧＰＵ２１８などの１つのＧＰＵ（またはコア）において実行され、グラフィックスは、第２のＧＰＵ２１０などの別のＧＰＵ（またはコア）においてレンダリングされる。さらなる実施形態において、物理シミュレーションおよびグラフィックスレンダリングは、複数のＧＰＵによって行われる。物理シミュレーションの後に、レンダリングされたグラフィックは、表示ユニット２２２に送られ、表示される。ＧＰＵ２１８およびＧＰＵ２２０は、それぞれ次の章に記述されるように実装され得る。
【００２２】
Ｂ．物理シミュレーションを実行するための例示的なＧＰＵ
本発明の実施形態に従ったＧＰＵのアーキテクチャーは、単一命令多数データ（ＳＩＭＤ）技術を使用可能にし、その結果として、データレベル並列処理をもたらす。そのようなＧＰＵは、プロセッサと、テクスチャ（またはビデオメモリ）を含む。プロセッサは、テクスチャ内のデータに基づきオペレーションを行う。該オペレーションの結果は、レンダーターゲット（ビデオメモリの一部）に書き込まれる。レンダーターゲットは、テクスチャまたは後続演算として再割り当てされ得る。テクスチャは、メモリの１Ｄ−、２Ｄ−、３Ｄ−アレイなどのように、メモリのアレイに配列される。シェーダーは、プロセッサがテクスチャ内のデータに基づき特定の演算を行うために書き込まれた、小さなプログラムまたは一組の命令である。
【００２３】
図３は、ブロック図３００を図示し、本発明の実施形態に従った、１つ以上のＧＰＵ上で物理シミュレーションを実行するための例示的なピクセルプロセッサを説明する。ブロック図３００に含まれるものは、６つのテクスチャ３１０ａ−３１０ｆ、８つの定数ストレージレジスタ３０８ａ−３０８ｈ、および１つのピクセルプロセッサ３０６である。メモリアレイ（１Ｄ−、２Ｄ−、３Ｄ−メモリアレイなど）のテクスチャ座標３０２は、テクスチャ３１０に書き込まれ得る。対照的に、定数データ値は、定数ストレージレジスタ３０８に記憶される。ピクセルプロセッサ３０６は、テクスチャ３１０内および／または定数ストレージレジスタ３０８内のデータに基づきオペレーションを行う。これらのオペレーションを行った後に、ピクセルプロセッサ３０６は、テクスチャ３１０にデータを書き込み得、かつ／または、出力３１４を生成し得る。ピクセルプロセッサ３０６によって行われるオペレーションは、ＣＰＵアッセンブリ言語命令に似た命令によって特定される。
【００２４】
ここで、ＧＰＵ頂点プロセッサにおいてメッシュが表現される、例示的な方法について記述する。メッシュは、１対の１次元リスト、すなわち頂点バッファおよびインデックスバッファから成る。図１５Ａに例示されるように、頂点バッファは、頂点位置を保持する。図１５Ａに示される実施形態は、７つの頂点位置を例示している。図１５Ａは、例示目的のみに用いられ、限定的に用いられるものではない。当業者に明確なように、異なる数の頂点位置が、頂点バッファに記憶され得る。図１５Ｂに例示されるように、インデックスバッファは、面のインデックスを記憶する。図１５Ｂは、例示目的のみに用いられ、限定のために用いられるものではない。当業者に明確なように、異なる数の面のインデックスが、インデックスバッファ記憶され得る。面は、三角形を表し、該面は、頂点バッファに点を載せる。例えば、インデックスバッファに記憶された面は、３つの頂点を含み得、０、１および２と分類される。これら分類された頂点のそれぞれは、頂点バッファの別個の位置を指し示す。
【００２５】
ここで、メッシュがビデオメモリにマッピングされる例示的な方法について記述する。この例示的な方法は、例示目的のみに提示され、限定のためではない。メッシュをビデオメモリにマッピングするための他の方法は、本明細書に含まれる記載を基にして、当業者に明確となる。頂点およびインデックスのリストはそれぞれ、ビデオメモリにおける最適化されたＮ次元のアレイにマッピングされることにより、ピクセルエンジン並列処理がより良く利用される。最適化されたＮ次元のアレイは、該最適化されたＮ次元のアレイが、物理シミュレーションを行うために用いられるＧＰＵの最大アドレス指定能力に適合するようになっている。頂点バッファは、ｎ×ｍの要素のアレイ上にマッピングを行い、インデックスバッファは、ｌ×ｋグリッド上にマッピングを行う。ビデオメモリ内のそれぞれの要素（例えばピクセル）は、４成分ベクターから成る。はじめの３つの成分は、位置のｘ、ｙおよびｚ成分を表し、４つ目の成分は、境界タグ（以下に記述される）である。
【００２６】
一実施形態において、頂点およびインデックスのリストは、それぞれ、図１４Ａおよび図１４Ｂに示されるように、それぞれがビデオメモリにおける最適化された２次元アレイ上にマッピングされる。本実施形態において、頂点バッファは、３×３成分のアレイ上にマッピングを行い、インデックスバッファは、３×２グリッド上にマッピングを行う。
【００２７】
１つのシーンにおける複数のメッシュの場合には、全メッシュが、本発明の実施形態に従った、１つの２次元複合メッシュに一体化される。複合メッシュは、それぞれのサブメッシュに固有の識別子（「ｉｄ」）をタグ付けすることによって、サブメッシュ境界をビデオメモリに記録する。該ｉｄは、それぞれのグリッド要素の第４の構成要素として記録される。メッシュの複合は、ビデオメモリへの小型サイズメッシュのダウンロードに関連したオーバーヘッドを緩和し、かつ、テクスチャ使用の総数によるハードウェアリソースのプレッシャーを軽減する。
【００２８】
ＩＩ．例示的な物理シミュレーションインターフェース
図２に関して上述されたように、物理シミュレーションソフトウェアインターフェース２１２は、アプリケーション２１０が、ＧＰＵ２１８、ＧＰＵ２２０および／または複数のＧＰＵ上で物理シミュレーションを行うことを可能にする。この章では、例示的な物理シミュレーションインターフェースが記述される。まず、ＦＹＳＩと呼ばれる、例示的な物理シミュレーションソフトウェアインターフェースが記述される。続いて、ＦＹＳＩにおいて具現化される象徴的なコンセプトを表現するための、ＦＹＳＬと呼ばれる例示的なシーン記述言語が記述される。最後に、ＦＹＳＩを用いて１つ以上のＧＰＵ上で物理シミュレーションを行い、それにより、従来のソフトウェアダイナミックソルバーを回避するための、物理パラメータと属性をＦＹＳＬに変換する例示的な方法が記述される。しかし、認識されたいのは、これらの実施形態は、例示的目的のみに提示され、限定のためではないということである。本明細書に含まれる記述を基に、当業者は、１つ以上のＧＰＵ上で物理シミュレーションを行うための、他の種類の物理シミュレーションソフトウェアインターフェースの実装方法を理解することとなる。
【００２９】
Ａ．例示的な物理シミュレーションソフトウェアインターフェース（ＦＹＳＩ）
ＦＹＳＩ−例示的な物理シミュレーションソフトウェアインターフェース系は、従来のＣＰＵベースのシミュレーション関連の演算をＧＰＵ上でマッピングするための伝達手段である。ＦＹＳＩを用いることによって、ゲーム物理において一般に経験されるものよりも、より高いインタラクション速度が達成され得る。ＦＹＳＩは、グラフィックスハードウェア上に衝突の検知および解消をマッピングする従来の閉鎖クエリモダリティからはずれたものである。代替的に、ＦＹＳＩは、ますます増えつつあるハードウェアでのプログラミングが可能なシェーディング力を強化する、グローバルシミュレーション解決法を提案する。
【００３０】
図４は、拡張グラフィックスパイプラインのブロック図４００を図示し、これによって、物理シミュレーションステージ４１０が視覚レンダリングステージ４２０をフィードスル。物理シミュレーションステージ４１０は、物理記述象徴概念を取り入れる。該記述は、シミュレーションおよびシーンの両方の定義を提供する。シーンは、アクター（ａｃｔｏｒ）から成り、それぞれのアクターは、それ自身の一組の形状、ダイナミクス、および物質の特性を有する。該形状は、参加中のアクターの幾何学的な性質を確立させ、ダイナミクスは、物理的な挙動を構成し、物質は、物質関係の特性を備え付けさせる。加えて、該シーンは、随意的にジョイント（ｊｏｉｎｔ）を宣言し、これによって１対のアクターの運動の制約を導入する。シミュレーションの工程は、反復的で別々の一律のステップ、すなわち時間様式によって開始される。物理記述象徴概念は、ＦＹＳＬと呼ばれる言語の形式をとり、これは、物理シーン記述言語の略である。ＦＹＳＬは、プラットフォームから独立しており、拡張性があり、かつコンストラクトを提供することによって、必要に応じて複数のＧＰＵに渡ってシミュレーションタスクを分割する。
【００３１】
レンダリングブロック４２０において、物理ブロック４１０からのシミュレーション結果は、視覚化のためにレンダリングされる。一般的には、いくつかの物理シミュレーションのステップが、レンダリングフレーム毎に行われる。故に、シミュレーションおよび視覚レンダリングの両方のタスクの累積のフレーム速度が、ユーザーに対する最終的なインタラクティブ速度を決定する。ＦＹＳＩは、物理シミュレーション要件を提供するためのソフトウェア開発環境である。まず、ＦＹＳＬ入力象徴概念は、解析され、内部シーンデータ構造の集合に変換される。次いでシミュレーションは、ＧＰＵにおいて開始される。シミュレーション結果は、共有テクスチャを用いて視覚レンダリングスレッドに直接的に進まされるか、または、随意的にプログラマーによって読み返されるように利用可能である。最後に、ＦＹＳＩは、拡張性を容易にするために、グラフィックスハードウェアインターフェースの頂部に演算象徴概念層（ＣＡＬ）ラッパー（ｗｒａｐｐｅｒ）を実装する。一実施形態において、ＦＹＳＩは、マイクロソフトＤｉｒｅｃｔＸ（Ｒ）（バージョン９．０および１０．０）とインターフェースで接続するが、当業者は、ＦＹＳＩがＯｐｅｎＧＬ（Ｒ）または他のいくつかのＡＰＩとインターフェースで接続し得ることを認識されたい。
【００３２】
ゲームにおける物理シミュレーションフィールドは、幾分幅広いものであり、大量の域におけるトピックを範囲に入れる。それらの中には、剛体、クロス、流体、および、一般的には変形可能体のシミュレーションが含まれる。物理シミュレーションの種類は、シミュレーションステージから視覚レンダリングステージ上に移されたデータのフォーマットを示す。剛体の場合には、ＦＹＳＩは、視覚スレッド変換データに進み、該データは、最近のシミュレーションセッションに入力されたオブジェクトの増分的状態変化を表す。クロスのモデルは、摂動を加えられた元の粒子の位置に戻り、流体または変形可能な体については、結果的にシミュレートされた形状は、初期の形状とはほとんど関連性のないものとなっている。通常、物理シミュレーションの工程は、ＣＰＵバウンドであり、物理シミュレーションの工程から視覚レンダリングスレッド上への帯域幅要件は、相対的に限定的である。
【００３３】
図５に示されるように、比較的に高いレベルにおいて、包括パイプライン５００が形成され、前述の物理シミュレーション局面のほとんどに適用され得る。パイプライン５００は、系セットアップステージ５１０、ソルバーステージ５２０、および衝突ステージ５３０を含む。系セットアップステージ５１０において、入力は、初期シーン記述、または該シーンの増分的な状態の更新のいずれかである。系セットアップステージ５１０の役割は、物理モデルの統合を行い、方式Ａ＊ｘ＝ｂの線形系に到達することである。ここで、Ａは行列、ｘは未知数、ｂは既知のベクトルである。
【００３４】
ソルバーステージ５２０において、線形系は解かれ、描写されるシーンの状態は、該線形系に対する解に基づいて更新される。線形系は、関連する当業者に利用可能な数値技術を用いることによって解かれる。一実施形態において、線形系は、以下に詳細に記述される修正共役勾配方法、およびＤａｖｉｄ  ＢａｒａｆｆおよびＡｎｄｒｅｗ  Ｗｉｔｋｉｎによる「Ｌａｒｇｅ  Ｓｔｅｐｓ  ｉｎ  Ｃｌｏｔｈ  Ｓｉｍｕｌａｔｉｏｎ」、Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｅｄｉｎｇｓ、ｐｐ４３−５４（１９９８年７月１９〜２４日）（以降「Ｂａｒａｆｆ引例」と呼ぶ）を用いて解決され、本明細書においてその全体を参照として援用する。
【００３５】
衝突ステージ５３０において、更新されたモデルは、可能性のある衝突のために試験される。算定された接触の結果として、シーンの状態がさらに修正される。衝突検出が、対の点が交差するか否かをチェックすることによって行われる。衝突検出技術は、当業者に周知である。例えば、Ｂａｒａｆｆ引例の５０ページを参照されたい。
【００３６】
物理パイプライン５００は、そのステージ全体を、シミュレーションステージのそれぞれのために繰り返し実行される。一般的に、シーンの中のアクターは、個別に、またはグループベースのいずれかにおいて考慮される。剛体の場合におけるなどの個別のアクターは、パイプライン５００の系セットアップステージ５１０およびソルバーステージ５２０を通過し、衝突ステージ５３０のみを行う。クロス、流体および変形可能なエンティティーは、一般的に、明確な相互作用モデルを有するアクターの集合と考えられる。故に、ほとんどの場合において、それらはパイプライン５００の全てのステージを実行するように意図される。クロスが物理パイプライン５００を通過する例が、第ＩＩＩ章に記述される。
【００３７】
Ｂ．例示的な物理シーン記述言語（ＦＹＳＬ）
ＦＹＳＩ物理シミュレーションインターフェースライブラリへの入力象徴概念は、ＦＹＳＬと呼ばれるカスタム化シーン記述フォーマットにおいて表される。ＦＹＳＬは、ＸＭＬフォーマットにおいて表され、シーン、シミュレーション、アクター、ジョイント、およびフィードバックの５つのセクションから成る。これらのＦＹＳＬセクションのそれぞれは、スキーマタグおよび随意的価値割当を含む。スキーマタグおよび随意的価値割当は、以下に記述される。ＦＹＳＬプログラムの見本は、この小節の終わりに提供される。
【００３８】
ＦＹＳＬの最初のセクションは、シーンである。このセクションにおいて、描写されるシーンが定義される。例示的なグローバルシーンタグは、表１に提示される。
【００３９】
【表１】
0005616060.tif 000017
ＦＹＳＬの第２のセクションは、シミュレーションである。ＦＹＳＩにおけるシミュレーションの工程は、個別的であり、ステップにおいて開始される。ＦＹＳＬシミュレーション特性は、種類およびシミュレーションステップ間の時間間隔を含む。
【００４０】
加えて、全てのシーンのアクターに同じように作用している力を表すグローバルフィールドが、シミュレーション定義に随意的に加えられ得る。本実施形態において、ＦＹＳＬは、ドラッグフィールド、方向性フィールド、および手続きフィールドの、３種類の力フィールドタグを提供する。ドラッグフィールドは、３つのスカラー値（それぞれの次元に１つ）から成るベクトルであり、該ベクトルは、アクターの線形速度に基づいた制動力を及ぼす。方向性フィールドは、シミュレーションを通して一定な単一成分の力であり、該力は、ベクトルによって特定された方向において作用する。例示的な方向性フィールドは、重力である。手続きフィールドは、時間および空間の両方において変化し得る、より入り組んだフィールドを表す。手続きフィールドに取り付けられたストリングは、ＧＰＵ上で実行されるシェーダープログラムのコードにさらに翻訳される、機能である。
【００４１】
例示的なシミュレーションタグは、表２に示されており、例示的なフィールドタグは、表３に示される。
【００４２】
【表２】
0005616060.tif 000018
ＦＹＳＬの第３のセクションはアクターである。アクターの一群は、通常は１、２または３次元であり得る論理グリッドにおいて構成される。グリッドは、ＧＰＵビデオメモリにおいてアクターの特性を展開する手段として役立つ。表４に示されるように、グリッドタグは、幅、高さ、および深さの値を含む。
【００４３】
【表３】
0005616060.tif 000019
アクターは、グローバルおよび特定の形状およびダイナミクスの特性によって特定される。形状は、対に関する衝突の検出を決定するために用いられ、ダイナミクス特性は、物理的挙動を容易にすることによって応答を解決する。ＦＹＳＬおよびＦＹＳＩは、形状の定義のために左手座標系を用いる。表５に示されるように、グローバルなアクタータグは、名前、種類、およびｉｄの値を含む。
【００４４】
【表４】
0005616060.tif 000020
アクターｉｄ（識別子）は、正の整数であり、かつ、同一の階層のアクターの群に渡って固有のものであることが求められる。大体において、ＦＹＳＩは、ＦＹＳＬ記述において欠いているシーン特性のために、デフォルトのシーン特性を割り当てるように求められる。
【００４５】
記述されたＦＹＳＬ実施形態において支持される形状の定義は、ボックス（軸に対して整列または配向されている）、球、メッシュ、および四面体を含む。アクター形状は、ローカルの基準座標系において定義される。体積を境界付けるボックスおよび球は、１対の中心および半径として表される（中心および半径は、それぞれベクトルまたはスカラーのいずれかである）。メッシュおよび四面体は、頂点位置（四面体については、頂点の数は４に固定されている）および１組の面のインデックス（四面体についてはインプリシット）の集合の形態をとる。メッシュに関しては、面はエクスプリシットであり、一方で、四面体に関しては、面はインプリシットである。形状は、ワールド（ｗｏｒｌｄ）座標空間へのローカルの座標系の変換を特定する行列と関連している（以下の論述を参照されたい）。表６から表１０は、形状に特有のタグを例示する。
【００４６】
【表５】
0005616060.tif 000021
体積を境界付ける質量の中心は、形状の定義によってエクスプリシットである。メッシュおよび四面体については、ＦＹＳＩは、質量の中心が、線形の運動特性のセットにおいて提供されない限り、質量の中心をインプリシットに演算する。メッシュの質量中心のパラメータは、必ずしもユーザーによって提供される必要はないが、それがあれば、ＦＹＳＩが内部的に演算したものを上書きする。
【００４７】
シミュレーションは、ワールド座標空間において行われる。形状の変換は、平行移動および回転の成分の連結であり、アクターに線形および角の運動のそれぞれを適用する効果によるものである。結果的な行列は、ローカルからワールドの座標空間へと、形状を変換する。変換行列は、視覚レンダリング工程のためにＦＹＳＩクライアントによって用いられる。
【００４８】
ＦＹＳＬボックスの形状は、ＦＹＳＩ内部において、軸に対して整列した（ＡＡＢＢ）または方向性を有した（ＯＢＢ）、いずれかの演算経路を取り得る。該選択は、どちらかと言えば動的であり、シミュレーションのステップによって変わり得る。例えば、接触応答に基づき得る。一般的には、衝突検出のためのＡＡＢＢ経路は、ＯＢＢ経路に比べてより効率的である。
【００４９】
動的属性は、線形、角、および物質の種類の任意の組み合わせであり得る。動的属性は、質量、速度、エクスプリシットな質量中心の位置、配向、および及ばされる力を含む、運動学的特性を定義する。加えて、動的特性は、復元および摩擦などの、接触応答物質属性を提供する。線形、角および物質の種類のための動的タグは、表１１、表１２、および表１３にそれぞれ提供される。
【００５０】
【表６】
0005616060.tif 000022
剛体は、行われた物理的な挙動の規則の基礎となる、ＦＹＳＩに対し、点質量と仮定される。線形の運動および外部的な力は、本体の質量中心に作用し、角運動は、接触点に適用される。
【００５１】
ＦＹＳＬトルクは、それが存在するときには、あらゆるボックスまたはメッシュの形状の頂点に適用される。また、トルクは粒子ベースのアクターの場合にも有意義であり、ここでは、それぞれの粒子が、ゼロ半径の球として定義される。トルクは、アクター（または粒子の場合は親アクター）の質量中心に対する位置に依存する。該トルクは、結果として起こるアクターの角運動に影響する。ＦＹＳＬトルクは、粒子ベースのアクター（例えば、空間的な範囲を有さない無形のアクター）に対して有意義である。該トルクは、トップレベルアクターの実質的な質量中心に対する位置に依存する。トルクは、粒子の角運動に影響する。
【００５２】
アクターに対する配向は、行と列が単位長さの、直交行列であることが求められる。
【００５３】
オメガ動的特性は、ラジアンにおける角度のベクトルである。任意の軸に対する正の角度は、軸を中心に反時計回りの回転をもたらし、負の角度は、軸を中心に時計回りの回転をもたらす。
【００５４】
メッシュのインデックスおよび四面体の面のインデックスは、ゼロベースであり、それぞれは、反時計回りで三角形を表す。
【００５５】
アクターのグリッド展開は、ＧＰＵに固有のデータパラレルアーキテクチャを利用する。グリッドはまた、物理的に割り当てられたＧＰＵから読み返される最終的な画像の解像度を提供し、該物理的に割り当てられたＧＰＵは、視覚的レンダリングを行うＣＰＵまたはピアＧＰＵ上にシミュレーション結果を移動させる。１Ｄグリッドは、ＧＰＵ上では非常に非効率的であり、通常は用いられることはない。通常は、アクターは、２Ｄグリッド上に分配される。３Ｄグリッドが用いられるのは、例えば、２Ｄグリッドのアドレス指定能力がＧＰＵの限界を超えた場合である。グリッドの次元は、２のべき乗である必要はない。最後に、アクターの数は、グリッドセルの数に必ずしも一致する必要はないかもしれない（例えば、後者は、階層におけるアクターの数と等しいかそれ以上でなくてはならない）。結果として、２Ｄグリッドが、完全に場所を占有されていない最後の行を有し得、３Ｄグリッドの最後のスライスは、完全に占有されていないかもしれない。ＦＹＳＩは、全ての生じたスライバをダミーアクターで埋める。
【００５６】
アクターは、階層的に作られ得、それぞれの階層レベルにおけるアクターの集合は、グローバルな属性を共有し得る。グリッドは、各レベルにおいて、アクターの集合に付属させられることが求められる。より高い階層レベルでの形状は、より粗い幾何学的表現となると想定される。これは、トップ−ダウンシミュレーションを開始することと連動し、早期の衝突検出が除かれることは、全体的な工程の効率を向上させる。また、アクターの動的特性は、各階層レベルにおいて固有のものにすることができ、その結果、順応性のある物理的特性を実行する自由を提供する。ジョイント（後に記述）は、制約条件をシミュレーションするためにアクターの群に随意的に適用され得る。例えば、ジョイントは、クロスのシミュレーションにおいて用いられ、このことは以下の第ＩＩＩ章に詳述される。
【００５７】
ＦＹＳＬの第４のセクションは、ジョイントである。ジョイントは、１対のアクターの間の相互作用の制約を定義する。ジョイントは、本質的にアクターの動作を制限する。ジョイントは、共通のパラメータおよび／またはその種類に基づく固有のパラメータを有し得る。共通のパラメータには、ジョイントの種類、および１対のアクターのメンバーそれぞれに対するハンドルを含む。ジョイントは、ＦＹＳＬ記述フォーマットにおいてアクターと同一のタグレベルにある。従って、ジョイントは、トップのシーンレベルおよび任意のアクター階層の両方において定義され得る。例示的なジョイントタグは、表１４、表１５、および表１６に提供される。
【００５８】
【表７】
0005616060.tif 000023
ＦＹＳＬの第５のセクションは、フィードバックである。ＦＹＳＬ記述のフィードバックセクションは、シミュレーション結果の戻り経路に対して、ＦＹＳＩによってのみ提供される。複数ステップのシミュレーションセッションにおいて、ステップごとにフィードバックセクションがある。例示的なフィードバックタグは、表１７に示される。
【００５９】
【表８】
0005616060.tif 000024
例示的実施形態は、上記のタグを含み得るが、代替的な実施形態においては、他のタグの種類も用いられ得る。サンプル＃１。以下に提供されるものは、ＦＹＳＬで書かれたコードの例示的なセクションである。コードのこのセクションは、それぞれ角度的および線形のダイナミクスを有する、１対のメッシュ形状のアクターを有する衝突検出物理シミュレーションシーンを図示する。
【００６０】
【表９】
0005616060.tif 000025
【００６１】
【表１０】
0005616060.tif 000026
サンプル＃２。以下に提供されるものは、ＦＹＳＬで書かれた例示的なコードの別のセクションである。このコードのセクションは、２×２のグリッドレイアウトの粒子ベースのアクターのための、２つのレベルの階層を例示する。これは、クロスおよび流体のエンティティーを定義するための基本的な構造である。
【００６２】
【表１１】
0005616060.tif 000027
【００６３】
【表１２】
0005616060.tif 000028
【００６４】
【表１３】
0005616060.tif 000029
Ｃ．メッシュに関連する物理パラメータが受信され、ＦＹＳＬに変換され得る、例示的な方法
ソフトウェアダイナミクスソルバー（Ｃａｌｉｆｏｒｎｉａ州、Ｓａｎ  ＲａｆａｅｌのＡｕｔｏｄｅｓｋ（Ｒ）所有、Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓなど）は、ＣＰＵによって実行される物理シミュレーションを行うために存在する。本発明の実施形態に従うと、プラグインが用いられることによって、そのようなソフトウェアダイナミクスソルバーを迂回し、これによって、本明細書に記述されるようにＧＰＵ上で物理シミュレーションを行う。本実施形態において、プラグインは、シーンを捕捉し、該シーンに描写されるアクターに関連する属性およびフィールドをＦＹＳＬに変換する。その結果、物理シミュレーションが、ＦＹＳＩを用いてＧＰＵ上で行われ得る。別の実施形態において、ユーザーは、物理シミュレーションが、ＧＰＵによって行われるか、またはソフトウェアダイナミクスソルバーによって行われるかを選択してよい。さらなる実施形態において、ＧＰＵの有効性および／または所定の機能に対するソフトウェアサポートなど、所定の基準に基づいて、ＧＰＵまたはソフトウェアダイナミクスソルバーが自動的に選択され、物理シミュレーションが行われる。例えば、ＧＰＵは、剛体およびクロスの物理シミュレーションを行うために用いられ得るが、ソフトウェアダイナミクスソルバーは、流体の物理シミュレーションを行うために用いられ得る。物理シミュレーションをＧＰＵまたはソフトウェアダイナミクスソルバーによって行うことによって、より速いフレーム速度が達成され得る。特定のソフトウェアダイナミクスソルバー（すなわち、Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓ）を迂回するための例示的なプラグインが、本章に記述されるが、まず、Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓのあらましが提供される。
【００６５】
Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓは、現実世界の物理的特性をシミュレーションすることによって運動を生成する、一種の技術である。Ｍａｙａ（Ｒ）におけるダイナミクスは、多様であり力強く、また、モデリング、アニメーションおよびレンダリングに一致した重要性レベルのツールセットを所有する。一般的に、Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓのコンセプトは、キーフレームを用いないシミュレーションベースのアニメーションを含意する。Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓのファミリーには、剛体および軟体、粒子系、クロス、流体および髪メンバーを含む。Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓは、物理的原理に基づく、視覚的に強い印象を与える効果を作成するために、ゲームにおいて用いられる。
【００６６】
図６は、ブロック図を図示しており、ここでは、ＧＰＵを利用することによって、Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓなどのソフトウェアダイナミクスソルバーと比較して頑強性を妥協することなく、より高いシミュレーション速度を達成する、例示的なワークフロー６００を図示している。該ワークフローは、大部分がＭａｙａ（Ｒ）Ｄｙｎａｍｉｃｓへのプラグインによって制御されている。そのようなプラグインには、シーンエクスポーター（ｅｘｐｏｒｔｅｒ）、ＧＰＵ  ＤｙｎａｍｉｃｓシミュレーターＦＹＳＩ、およびシーンインポーター（ｉｍｐｏｒｔｅｒ）が含まれる。
【００６７】
ワークフロー６００は、ステップ６１０から始まり、ここでは、シーンエクスポーターが、アーティストによってシーンオブジェクトに添付された属性およびフィールドを受け取る。属性には、初期速度、スピン、配向、および物質の摩擦を含む。フィールドは、運動に影響し、ドラッグ、重力または手続き上定義されたものを含む力を表し、運動は、ＧＰＵシェーダープログラムにおいて表される。ユーザーは、ＧＰＵベースのシミュレーションを開始するために、全てのシーンオブジェクトまたはそのサブセットのいずれかを選択する。エクスポーターは、オブジェクトの幾何学的形状および動的特性を、ＧＰＵ向けの物理シミュレーションフォーマットに変換する。ＧＰＵ向きの物理シミュレーションフォーマットは、一実施形態においては、ＦＹＳＬである。
【００６８】
ステップ６２０において、物理シミュレーションは、ＦＹＳＬを用いてＧＰＵ上で行われる。一旦適切なＦＹＳＩプラグインが現れると、ＧＰＵベースのシミュレーターが、シームレスにソフトウェアダイナミクスソルバーノード（例えばＭａｙａ（Ｒ）Ｄｙｎａｍｉｃｓ（Ｒ）統合ソルバー）に取って代わる。ＧＰＵシミュレーターは、多数の別個のフレームにおいて、再帰的にシミュレーションを実行させる。シミュレーション中に、現在のシーン状態が解決され、ＦＹＳＬ動的アクターのそれぞれの対の中での衝突検出が調べられる。衝突する対は、さらに処理されることにより、関連するアクターの運動に影響するであろう、接触応答を起こす。ＦＹＳＩ  ＧＰＵ援助の物理シミュレーションは、主に頂点プロセッサよりもより高い度合いの同時処理を活用するピクセルエンジンを利用する。ＧＰＵ上での物理シミュレーションは、グリッドベースであり、ここでは、通信バリヤーは、格子セルに渡ってほとんどまたは全くない。関係する演算カーネルは、大部分において、高い算数効力特性を有し、従って、同等のＣＰＵ実装と比較して、改良スピードアップをデモンストレーションするための好ましい候補である。このシミュレーション工程は、効率を向上させるために単一または多数のＧＰＵを活用し、ソフトウェアダイナミクスソルバーとやりとりしているアーティストには、全てがトランスペアレントである。ＦＹＳＩは、エクスポーターが送ったものと、同一のＦＹＳＬ表現フォーマットにとなる。ＦＹＳＩ結果は、完全なシミュレーションセッションのために内部的にキャッシュされ、Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓにおいて再使用されるために完全に公開される。
【００６９】
ステップ６３０において、フレーム毎のシミュレーター結果は、Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓのシーングラフにインポートによって戻される。ステップ６３０の間、幾何学的形状および変換データのみが重要である。ＦＹＳＩは、シミュレーションステップ毎に、形状の位置的更新および変換の更新の両方を提供する。変換データは、入信してくるシーンの位置および配向に関連する。剛体の場合には、Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓからの変換シーングラフのノードを更新することで十分である。変形する物体（クロスおよび流体など）に対しては、Ｍａｙａ（Ｒ）Ｄｙｎａｍｉｃｓによって提供されるシーンプリミティブのノードにおいて、更新は、全てのメッシュ頂点またはインデックスについて行われる。
【００７０】
ステップ６４０において、シミュレーション結果は、視覚化ためにレンダリングされる。ＧＰＵまたはソフトウェアベースのレンダラーが呼び出されることによって、シミュレーション効果を視覚化する。一実施形態において、視覚レンダリングタスクを実行するためのＧＰＵは、物理シミュレーションを行うＧＰＵから物理的に離れている。これは、この場合においても、より高いレベルにおいて並列処理を容易にするためである。
【００７１】
ステップ６５０において、レンダリングされた結果は、シーンにおいて再生される。
【００７２】
ＩＩＩ．１つ以上のＧＰＵ上での物理シミュレーションを行うための例示的方法
Ａ．方法の概観
ここに、ＦＹＳＩおよびＦＹＳＬを用いた、１つ以上のＧＰＵ上での物理シミュレーションを行うための例示的方法を記述する。図７は、ブロック図を図示し、本発明の実施形態に従って、１つ以上のＧＰＵ上でゲーム物理シミュレーションを行うための例示的な方法７００を例示している。方法７００は、ステップ７１０から始まり、ここでは、メッシュに関連した物理パラメータが、ビデオメモリにマッピングされることによって、シーンに図示されたメッシュの運動を決定する線形方程式系をセットアップする。ビデオメモリは、図３に関連して上述された、テクスチャ３１０を含み得る。当業者に明らかなように、メッシュは、個体のオブジェクト、体積、流体、クロス、または他の種類の物理的オブジェクトなどの、あらゆる種類の物理的なオブジェクトを表し得る。
【００７３】
ステップ７２０において、少なくとも１つのピクセルプロセッサを用いて、演算が、ビデオメモリにおけるデータに基づいて行われることによって、その時刻の線形方程式系を解く。その時刻の線形方程式系への解を表す修正済みデータは、次いでビデオメモリに記憶される。一実施形態において、修正済みデータは、テクスチャ３１０に記憶され、次いで別のシェーダーが該修正済みデータに対応するグラフィックスをレンダリングする。本実施形態においては、単一のＧＰＵが物理シミュレーションおよびグラフィックスのレンダリングを行う。別の実施形態においては、修正済みデータが、第１のＧＰＵの出力として提供され、次いで第２のＧＰＵのテクスチャに書き込まれる。本実施形態においては、第１のＧＰＵが、物理シミュレーションを行い、第２のＧＰＵがグラフィックスのレンダリングを行う。代替的に、第１のＧＰＵは、第２のＧＰＵ（例えば第１のＧＰＵのビデオメモリあるいは系メモリ）にアクセス可能なメモリの領域に修正済みデータを書き込み得る。
【００７４】
方法７００は、あらゆる種類の物理的オブジェクトをシミュレーションするために実装され得る。以下に提供されるものは、１つ以上のＧＰＵにクロスをシミュレーションするための例示的な実装である。この例示的実装は、例示目的のみに提供され、限定の目的に提供されるものではない。本明細書に含まれる記載に基づいて、当業者は、ＧＰＵ上で他の種類の物理的オブジェクトのシミュレーションを行う方法を理解することとなる。
【００７５】
ここで、１つ以上のＧＰＵでクロスをシミュレーションするためのインプリシットな技術を記述する。まず、クロスの物理モデル、および離散時間にそのモデルをシミュレーションする２つのアプローチが提示される。第２に、インプリシットな離散時間シミュレーションの３ステップ工程が記述される。第３に、この３ステップ工程をＧＰＵにマッピングする方法が提示される。
【００７６】
（クロスシミュレーションのための例示的物理モデル）
クロスは、内在する粒子系によってシミュレーションされ得る。そのような内在型粒子系は、内部的な伸張力および減衰力を受ける、点質量のアレイとして表され得る。これら力は、近傍の点の相対的変位および速度に依存する。そのような点質量のアレイは、本明細書において点メッシュと参照される。図８は、例示的な点メッシュを図示する。
【００７７】
点メッシュ８００を考慮すると、以下の、点メッシュ８００に関連した物理パラメータが定義され得る。
【００７８】
【数１】
0005616060.tif 000030
あるいは、Ｍは、ブロックとして解釈され得、それは、それぞれの要素が｛３×３｝対角行列である｛ｎ×ｎ｝対角行列である。
【００７９】
ニュートンの第２の法則（すなわち、Ｆ＝ｍａ）は、点メッシュ８００に対して以下のように書かれ得る。
【００８０】
【数２】
0005616060.tif 000031
線形減衰を有する二次質量ばね系に対しては、粒子ｉに作用するネット力は、相対位置
【００８１】
【数３】
0005616060.tif 000032
および全て（通常は近傍）の粒子の速度
【００８２】
【数４】
0005616060.tif 000033
の関数である。故に、方程式１におけるネット力の各成分は、
【００８３】
【数５】
0005616060.tif 000034
と書かれ得る。そして、点メッシュ８００の運動は以下の方程式によって決定される。
【００８４】
【数６】
0005616060.tif 000035
故に、方程式２の解は、点メッシュ８００の運動をシミュレーションするために用いられ得る。
【００８５】
方程式２が一連のコンピュータの工程（例えば、ＧＰＵにおける少なくとも１つのピクセルプロセッサによって行われる工程）によって解かれるためには、方程式２は、離散時間型問題に変換されなくてはならない。時間離散型問題においては、系の次の状態が、その以前の状態によって与えられる。具体的には、時刻ｔｋ
【００８６】
【数７】
0005616060.tif 000036
における系の位置および速度が与えられると、最も単純な一次時間離散型問題は、時刻ｔｋ＋１
【００８７】
【数８】
0005616060.tif 000037
における系の位置および速度を決定する。時間離散型問題に対する解は、時間離散型積分を必要とする。少なくとも２つの一般的な種類の時間離散型積分があり、それらは、エクスプリシットな方法およびインプリシットな方法である。
【００８８】
エクスプリシットな方法は、導関数の前進投射を用い、以前の状態の直接的外挿から次の時間のステップにおける状態を演算する。例えば、一次オイラー前進差分は、以下のように近似する。
【００８９】
【数９】
0005616060.tif 000038
離散時間導関数の右辺は、以前の時間ステップにおける値によって左辺において束縛される。将来的な状態は、状態の関数として再び書かれる事となり得、すなわち、以下の通りとなる。
【００９０】
【数１０】
0005616060.tif 000039
方程式３の形式を点メッシュ８００に適用すると、点メッシュ８００の運動を決定する方程式の系（すなわち方程式２）は、
【００９１】
【数１１】
0005616060.tif 000040
によって与えられる、時間ステップ毎に適用される、単純な独立した更新の方程式のセットとして書き換えられ得る。
【００９２】
エクスプリシットな積分スキームに対する主な欠点は、数値安定度である。一般的に、前進近似を保つために、方程式３の関数ａ（ｔ）は、
【００９３】
【数１２】
0005616060.tif 000041
に関してあまり急激に変化してはならない。すなわち、積
【００９４】
【数１３】
0005616060.tif 000042
は、閾値より下でなくてはならない。ｂｋが大きい場合、該系は、「剛（ｓｔｉｆｆ）」と言われ、
【００９５】
【数１４】
0005616060.tif 000043
は、比較的に小さくされなくてはならない。
【００９６】
インプリシットな方法は、第２種類目の時間離散型積分技術を担う。インプリシットな方法は、外挿された結果から、幾分かの「可逆性」を表す方程式の系からの次の時間ステップにおける状態を演繹する。言い換えると、将来の状態の後退導関数が、以前の状態に対して同時に検証される。例えば、一次オイラー前進差分は、以下のように近似する。
【００９７】
【数１５】
0005616060.tif 000044
巧妙なことに、ここで、時間離散型導関数の右辺は、将来の値によって左辺に同時に束縛されるということである。直接的な結果として、将来の状態は、以前の状態の単純な関数としては表現できない。
【００９８】
点メッシュ８００に適用されることによって、系の支配方程式（すなわち、方程式２）は、３ｎの未知数
【００９９】
【数１６】
0005616060.tif 000045
の同時的な系になり、それは、時間ステップ毎に解かれなくてはならない。
【０１００】
【数１７】
0005616060.tif 000046
このタスクは、難題のように見えるかもしれないが、このアプローチは、２つの重要な利点を有する。まず、インプリシットな技術は、ほとんど無条件的に一定している。つまり、インプリシットな技術は、現実的なクロスシミュレーションの特徴的に「剛（ｓｔｉｆｆ）」方程式によって影響されることがより少なく、それ故により大きな時間ステップをサポートすることが可能である。次に、結果的な系は、疎かつ対称的な傾向があり、これらの種類の系は、効率的な数値法を用いて難なく解かれる。
【０１０１】
方程式４に表されるエクスプリシットな積分法か、方程式５に表されるインプリシットな積分法のいずれかにおいて、ネットの内力のベクトル
【０１０２】
【数１８】
0005616060.tif 000047
を求めなくてはならない。一般的には、
【０１０３】
【数１９】
0005616060.tif 000048
は、クロスの内部的な拘束をモデル化する、非線形の関数である。離散時間において、
【０１０４】
【数２０】
0005616060.tif 000049
は、常に現在の状態の関数である。
【０１０５】
【数２１】
0005616060.tif 000050
エクスプリシットな積分を用いて、
【０１０６】
【数２２】
0005616060.tif 000051
が、直接的に求められることによって、
【０１０７】
【数２３】
0005616060.tif 000052
が更新される。具体的には、方程式４に示されるように、以下となる。
【０１０８】
【数２４】
0005616060.tif 000053
しかし、安定度を確実にするために、
【０１０９】
【数２５】
0005616060.tif 000054
は、
【０１１０】
【数２６】
0005616060.tif 000055
の「剛性（ｓｔｉｆｆｎｅｓｓ）」を反映させるために選択されなくてはならない。残念なことに、現実的な内力は、比較的に堅く、比較的に小さな時間ステップを必要とする。先述のＢａｒａｆｆの引例によって証明されたように、現実的に剛の方程式に必要な、これら小さな時間ステップにおける多くの更新の累積のコストは、より粗い時間ステップにおいて大型で疎な線形系を解くコストを次第に超える。Ｄａｖｉｄ  ＢａｒａｆｆおよびＡｎｄｒｅｗ  Ｗｉｔｋｉｎの「Ｌａｒｇｅ  Ｓｔｅｐｓ  ｉｎ  Ｃｌｏｔｈ  Ｓｉｍｕｌａｔｉｏｎ」、ＳＩＧＧＲＡＰＨ  ９８の集録、ｐｐ．４３−５４（１９９８）を参照されたい。結果的に、インプリシットなアプローチが、現実的なクロスシミュレーションで主となっている。
【０１１１】
インプリシットな積分技術は、複雑性がないという訳ではない。特に、インプリシットな積分技術は、
【０１１２】
【数２７】
0005616060.tif 000056
ではなく、
【０１１３】
【数２８】
0005616060.tif 000057
に対する式を必要とする。この場合には、近似が用いられる。具体的には、
【０１１４】
【数２９】
0005616060.tif 000058
が、その一次テイラー展開式によって近似される。
【０１１５】
【数３０】
0005616060.tif 000059
方程式６における第１の項は、エクスプリシットの場合におけるように求められ、一方で、第２および第３項は、ヤコビ行列
【０１１６】
【数３１】
0005616060.tif 000060
に依存し、最後の時間ステップにおいて求められる。外力から独立はしているものの、これらヤコブ行列は、大きく、相対的に数値を求めにくい。ヤコブ行列は、実際に、｛３×３｝サブ行列要素の｛ｎ×ｎ｝である。
【０１１７】
ヤコブ行列は、以下の形式を有する。
【０１１８】
【数３２】
0005616060.tif 000061
ここで、
【０１１９】
【数３３】
0005616060.tif 000062
であるので、
【０１２０】
【数３４】
0005616060.tif 000063
の要素は、それ自体は、形式
【０１２１】
【数３５】
0005616060.tif 000064
の｛３×３｝ヤコブ行列によって与えられる。
【０１２２】
【数３６】
0005616060.tif 000065
の数値が求められると仮定すると、時間ステップ毎に解く必要のある線形系（すなわち、方程式５）は、
【０１２３】
【数３７】
0005616060.tif 000066
の項において、以下のように書き換えられる。
【０１２４】
【数３８】
0005616060.tif 000067
ここでは、Ｉは、恒等行列であり、Ｍはメッシュの質量の直交行列であり、
【０１２５】
【数３９】
0005616060.tif 000068
は、ｔｋ時におけるメッシュ幾何学的状態を表すベクトルであり、
【０１２６】
【数４０】
0005616060.tif 000069
は、ｔｋ時におけるメッシュ中の各点の速度を表すベクトルであり、
【０１２７】
【数４１】
0005616060.tif 000070
は、ｔｋ時におけるメッシュの各点上のネット力を表すベクトルである。従って、点メッシュ８００の物理シミュレーションを行うためのインプリシットな積分法は、各時間ステップ
【０１２８】
【数４２】
0005616060.tif 000071
に対する方程式８を解く事である。
【０１２９】
方程式８は、
【０１３０】
【数４３】
0005616060.tif 000072
と書かれ得、ここで、
【０１３１】
【数４４】
0005616060.tif 000073
である。
【０１３２】
図５を参照して述べたように、ＦＹＳＩを用いてＧＰＵ上で物理シミュレーションを行うことは、以下の３つのステップを含む。すなわち、（ｉ）系セットアップステップ、（ｉｉ）ソルバーステップ、および（ｉｉｉ）衝突ステップ、である。
【０１３３】
系セットアップステップは、
【０１３４】
【数４５】
0005616060.tif 000074
における
【０１３５】
【数４６】
0005616060.tif 000075
に対する値を決定することを伴い、ここでは、定数の時間ステップ
【０１３６】
【数４７】
0005616060.tif 000076
と、直交質量行列Ｍと、点メッシュの現在の位置
【０１３７】
【数４８】
0005616060.tif 000077
および速度
【０１３８】
【数４９】
0005616060.tif 000078
とが与えられる。これらの入力から、
【０１３９】
【数５０】
0005616060.tif 000079
に対する中間値が求められ、それらは、方程式９によって与えられる
【０１４０】
【数５１】
0005616060.tif 000080
に関連している。このサブセクションの残りは、これら中間値の評価を詳述する。
【０１４１】
矩形の点メッシュ８００に対する線形の二つ１組の力モデルが用いられる。点メッシュ８００に対する線形の二つ１組の力モデルにおいて、ｉ点とｊ点との間の稜は、ジョイントと呼ばれており、結合したばねと減衰材を表す。ｉｊ＝ｊｉの場合には、２つのジョイントは、相補的であり、その場合には、等しいが相反する力（すなわち、ニュートンの第３の法則）が頂点であるｉおよびｊに適用され、それぞれは
【０１４２】
【数５２】
0005616060.tif 000081
で与えられる。ジョイントがｉおよびｊの頂点の間にて定義されないか、またはｉ＝ｊである場合には、
【０１４３】
【数５３】
0005616060.tif 000082
であることは明白である。最後に、ｉ番目の点に作用するネットの内力および
【０１４４】
【数５４】
0005616060.tif 000083
に対するそのヤコビアンに対する式は、以下のように与えられる。
【０１４５】
【数５５】
0005616060.tif 000084
実際には、ジョイントは、近傍の点の間においてのみ定義され、規則的なパターンで存在する。例えば、図８の点メッシュ８００において示されるジョイントトポロジーは、１点につき１２個のジョイントまで含む（境界条件によって異なる）。
【０１４６】
ジョイント毎の力はその頂点のみに依存しているので、
【０１４７】
【数５６】
0005616060.tif 000085
の行は、疎であるということが示され得る。すなわち、
【０１４８】
【数５７】
0005616060.tif 000086
であり、
【０１４９】
【数５８】
0005616060.tif 000087
の左上と右下とを結ぶ対角線上にない要素（すなわちｊ≠ｉ）に対する式は、以下になる。
【０１５０】
【数５９】
0005616060.tif 000088
対角線上（すなわち、ｊ＝ｉ）では、
【０１５１】
【数６０】
0005616060.tif 000089
および
【０１５２】
【数６１】
0005616060.tif 000090
に対する元来の式が当てはまり、点ｉに対して１つのジョイントのみが存在する場合には、要素は、ゼロ以外となる。従って、ｉｊがジョイントではない場合には、対角線上にない
【０１５３】
【数６２】
0005616060.tif 000091
であるので、
【０１５４】
【数６３】
0005616060.tif 000092
の行は、点ｉに対して定義されたジョイントの数に１をプラスしたものと等しい数だけの、ゼロ以外の要素のみを有し得る。例えば、図８において示されるジョイントトポロジーに対して、点メッシュの次元にかかわりなく、結果的なヤコビアンは、せいぜい１３（＝１＋点毎の１２ジョイント）のゼロ以外の要素を有することとなる。
【０１５５】
点メッシュ８００の運動を支配する線形方程式系が、「合致した」系を表すためには、行列Ａは、（ｉ）疎であり、かつ（ｉｉ）対称的でなくてはならない。（ｉ）項に関しては、Ａは、疎である。なぜならば、Ａは、ヤコブ行列
【０１５６】
【数６４】
0005616060.tif 000093
に線形に依存しており、これらヤコブ行列のそれぞれは、疎であることが証明されているからである。（ｉｉ）項に関しては、
【０１５７】
【数６５】
0005616060.tif 000094
のヤコビアンは、以下の
【０１５８】
【数６６】
0005616060.tif 000095
が非対角線部分に実施され得る場合には、それ自体は対照的である。
【０１５９】
故に、方程式１０が当てはまる場合には、Ａは、疎かつ対称的であり、従って、線形方程式系は、効率的に解くことができる。
【０１６０】
【数６７】
0005616060.tif 000096
および
【０１６１】
【数６８】
0005616060.tif 000097
の両方であるという基準は、特定の物理的な仮定における誘導的な因子であることが分かるであろう。
【０１６２】
図８を参照すると、点メッシュ８００における点の間のジョイント力は、（ｉ）引っ張りジョイント８０６、（ｉｉ）せん断ジョイント８０４、および（ｉｉｉ）曲げジョイント８０２の、３つの種類に分類され得る。隣接するノード間に定義され、引っ張りジョイント８０６は、最も強い内力をモデル化する。引っ張りジョイント８０６は、領域における面内変化に抵抗する。対角線上のノード間に定義され、せん断ジョイント８０４は、２番目に強力である内力をモデル化する。せん断ジョイント８０４は、クロスが角で引っ張られたときに内方向に狭くなる傾向に抵抗する。最後に、交互のノード間に定義され、曲げジョイント８０２は、最も弱い内力をモデル化する。曲げジョイント８０２は、折りたたみに対して抵抗する。
【０１６３】
より多くの現実的な定義がなされているが、上に提示された、対式ジョイント力毎モデルは、前述のＢａｒａｆｆ引例と、Ｋｗａｎｇ−Ｊｉｎ  ＣｈｏｉおよびＨｙｅｏｎｇ−Ｓｅｏｋ  Ｋｏ（「Ｓｔａｂｌｅ  ｂｕｔ  Ｒｅｓｐｏｎｓｉｖｅ  Ｃｌｏｔｈ」、Ｉｎ  ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｇｒａｐｈｉｃｓ、ＳＩＧＧＲＡＰＨ  ２００２、ｐｐ．６０４−１１（２００２））によって教示された対に関するジョイント力のモデルとの混合によって影響され、本明細書においてその全体を参照として援用する。本明細書に開示のモデルに従うと、全てのジョイントは、同一の関数によってモデル化されるが、ジョイントの種類（すなわち、引っ張り、せん断、および曲げ）は、剛性ｋｓ、減衰ｋｄ、および自然長Ｌに対する異なる値によって、グローバルにパラメータで表され得る。ジョイント毎に、ばね（ｋｓおよびＬによってパラメータで表される）の作用および減衰（ｋｄによってパラメーターで表される）は、線形に独立しており、別個のものと考慮してよい。
【０１６４】
一般的に、ばね力または減衰力のいずれかに対するジョイント力
【０１６５】
【数６９】
0005616060.tif 000098
は、２つのプロパティを満たす。すなわち、（ｉ）ジョイント毎の力
【０１６６】
【数７０】
0005616060.tif 000099
は、ジョイントの方向
【０１６７】
【数７１】
0005616060.tif 000100
に沿って作用し、（ｉｉ）ジョイント毎の力
【０１６８】
【数７２】
0005616060.tif 000101
は、条件関数
【０１６９】
【数７３】
0005616060.tif 000102
に比例する。これら２つのプロパティは、数学的に以下のように書かれ得る。
【０１７０】
【数７４】
0005616060.tif 000103
【０１７１】
【数７５】
0005616060.tif 000104
ここで、
【０１７２】
【数７６】
0005616060.tif 000105
であるので、対称に対する基準
【０１７３】
【数７７】
0005616060.tif 000106
は、
【０１７４】
【数７８】
0005616060.tif 000107
に対して、以下のものが実施されることを必要とする。
【０１７５】
【数７９】
0005616060.tif 000108
ここで、ジョイント毎の力
【０１７６】
【数８０】
0005616060.tif 000109
のばね成分が記述される。理想的な線形移動のばねは、変形の間にエネルギーに抵抗し、かつ該エネルギーを蓄えるものであり、該ばねは、蓄えられたエネルギーを放つように作用する、復原力の作用の表れである反応性の機械的なデバイスである。「移動」とは、含まれる機械的な力の種類に関連する。本明細書に記載のクロスシミュレーションに対するモデルにおいて、力は、ジョイントの方向
【０１７７】
【数８１】
0005616060.tif 000110
に沿って作用する。「線形」とは、変形（すなわち、ｘにおける変化）に直接比例する、復原力に関連する。最後に、「理想的な」とは、変形と復原とのサイクルの間に、エネルギーが全く失われないことを意味する。
【０１７８】
最も単純化された理想の線形移動ばね
【０１７９】
【数８２】
0005616060.tif 000111
に一致するジョイント毎のばね条件関数が定義される。
【０１８０】
【数８３】
0005616060.tif 000112
は、現在の頂点位置のみに依存し、
【０１８１】
【数８４】
0005616060.tif 000113
の両方に対する対称の基準を満たし、かつ、以下の方程式によって与えられた、剛性係数ｋｓおよび自然長Ｌによってパラメータで表される。
【０１８２】
【数８５】
0005616060.tif 000114
【０１８３】
【数８６】
0005616060.tif 000115
ここで、ジョイント毎の力
【０１８４】
【数８７】
0005616060.tif 000116
の減衰成分が記述される。ダンパーとは、変形に対して抵抗する、受動的な機械的デバイスであるが、ばねとは対照的に、エネルギーを蓄えたり、復原力を表すことはない。その代わりに、ダンパーは、熱という形で加えられたエネルギーを放散させることによって、変形に抵抗する。この特性は、速度の変化に比例する、純粋な抵抗力によって生み出される。
【０１８５】
本明細書において記述されたクロスのシミュレーションに対するモデルにおいて、理想的な線形移動ダンパーは、ジョイントの方向
【０１８６】
【数８８】
0005616060.tif 000117
に沿った抵抗力を表し、該ジョイントは、その頂点の速度
【０１８７】
【数８９】
0005616060.tif 000118
における相対的な変化に直接比例する。より具体的には、該ダンパーは、ジョイント方向における速度
【０１８８】
【数９０】
0005616060.tif 000119
の相対的な変化に比例する抵抗力を表す。減衰係数ｋｄによってパラメータで表される、ジョイント毎のダンパー条件関数
【０１８９】
【数９１】
0005616060.tif 000120
が定義される。このジョイント毎のダンパー条件関数は、
【０１９０】
【数９２】
0005616060.tif 000121
の両方に対する対称の基準を満たす。このステートメントは、数学的に、以下のように表され得る。
【０１９１】
【数９３】
0005616060.tif 000122
【０１９２】
【数９４】
0005616060.tif 000123
ここで、点メッシュ８００にかかる外力の応答および効果が記述される。外力の例としては、重力、風、および衝突（自身および環境との両方）を含む。外力の応答および効果の間において、明確な区別が存在するということを理解されたい。応答には、現在の状態
【０１９３】
【数９５】
0005616060.tif 000124
に対する即座の変化が含まれる。故に、応答は、モデル化することが比較的容易である。対照的に、力の効果は、将来の状態を拘束する（すなわち、ファブリックがピン留めされているために、将来の自由度を制限する）。故に、効果は、モデル化することが比較的難しい。
【０１９４】
外力の応答および効果を解くためのいくつかのアプローチが公知であり、それらには、縮小された座標（ｒｅｄｕｃｅｄ  ｃｏｏｒｄｉｎａｔｅｓ）を用いるアプローチ、ペナルティ法、および／または言語乗算器を含む。例えば、前述のＢａｒａｆｆ引例を参照されたい。Ｂａｒｒａｆｆ引例において議論される別のアプローチは、モデル化された点メッシュにおける所定の点の質量に拘束を与える。上述のように、対角質量行列
【０１９５】
【数９６】
0005616060.tif 000125
のブロック単位毎の解釈は、ｉ番目の粒子の質量を、｛３×３｝の対角行列
【０１９６】
【数９７】
0005616060.tif 000126
として表す。しかし、質量が、異方性の質量であり、方向とともに変化するものであると仮定される場合には、方程式１１は、
【０１９７】
【数９８】
0005616060.tif 000127
として書かれ得る。方程式１２において与えられる質量に基づいて、点メッシュに対する運動方程式は、
【０１９８】
【数９９】
0005616060.tif 000128
となる。故に、異方性質量を効率的に定義するということは、ｘｙ面に対する
【０１９９】
【数１００】
0005616060.tif 000129
の効果を効果的に拘束するということとなり、ｚ方向においては、加速は不可能となる。
【０２００】
Ｂａｒａｆｆ引例において開発されたアプローチは、線形系の対称に対して、かかわりを有し、結果的に、効率的な可解性を有する。これらの問題は、修正共役勾配（「修正ＣＧ」）法を用いることによって解決され得、該法は、質量ベースの拘束を実施するためのフィルタリング演算を導入する。別のアプローチは、質量ベースの拘束および修正ＣＧ法の両方を用い、これは、Ｋｗａｎｇ−Ｊｉｎ  ＣｈｏｉおよびＨｙｅｏｎｇ−Ｓｅｏｋ  Ｋｏ（「Ｓｔａｂｌｅ  ｂｕｔ  Ｒｅｓｐｏｎｓｉｖｅ  Ｃｌｏｔｈ」、Ｉｎ  ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｇｒａｐｈｉｃｓ、ＳＩＧＧＲＡＰＨ  ２００２、ｐｐ．６０４−１１（２００２））に記述されており、本明細書においてその全体を参照として援用する。
【０２０１】
Ｂ．ＧＰＵ上でクロスをシミュレーションするための例示的な実装
インプリシットにクロスをシミュレーションするためのモデルを記述したが、ここで、ＧＰＵ上での各離散時間ステップに対してクロスのシミュレーションを実装するための、３ステップの方法が記述される。図９は、本発明の実施形態に従った、ＧＰＵ上でクロスのシミュレーションを実装するための、例示的な流れ図を描写する。言い換えると、図９は、図４を参照して上述された物理シミュレーションブロック４１０の、特定の実装に関する高レベルな描写である。図９において、大きな円は、テクスチャまたはビデオメモリの配列を表し、図３を参照して上述された、テクスチャ３１０に類似し得る。テクスチャへのデータの特定のマッピングは、以下の通りである。（ｉ）円９０２（Ｍと分類される）は、点メッシュ８００における各点の質量に関連したデータを含む、テクスチャを表す。（ｉｉ）円９０４（Ｐと分類される）は、点メッシュ８００における各点の位置に関するデータを含むテクスチャを表す。（ｉｉｉ）円９０６（Ｖと分類される）は、点メッシュ８００における各点の速度に関するデータを含むテクスチャを表す。（ｉｖ）円９０８（Ｆと分類される）は、点メッシュ８００における各点に作用するネット力に関するデータを含むテクスチャを表す。そして、（ｖ）円９１２（Ｊと分類される）は、ヤコビアン行列に関するデータを含むテクスチャを表す。影つきの円９１０は、カーネル演算（１つ以上のＧＰＵによって行われる数学的演算など）を表す。
【０２０２】
ＧＰＵ上でクロスのシミュレーションを実装するための第１のステップには、図９に示されるように、点メッシュの運動を支配する線形方程式系を設定するために、点メッシュに関連した物理パラメータのテクスチャ（すなわち、ビデオメモリ）へのマッピングが含まれる。インプリシットな積分技術を適用することによって、上述されたことは、点メッシュの運動を支配する線形方程式系は、
【０２０３】
【数１０１】
0005616060.tif 000130
と書かれ得るということであり、ここでは、
【０２０４】
【数１０２】
0005616060.tif 000131
となる。モデル化された点メッシュの質量、位置および初期速度は、シーンを作成しているアーティストによって確立される。結果として、テクスチャ９０２ａ、９０４ａおよび９０６ａ（それぞれ、質量、位置、および初期速度に相当）は、直ちに満たされ得る。対照的に、ヤコビアン行列およびネット力の全ての成分は、アーティストによって確立はされない。結果として、カーネル演算９１０ａは、テクスチャ９０４ａ、９０６ａおよび９０８ａからの入力に基づいて、力およびヤコビアン行列
【０２０５】
【数１０３】
0005616060.tif 000132
を評価する。この評価の結果は、テクスチャ９０８ｂおよび９１２ｂに書き込まれる。これらの結果がテクスチャ９０８ｂおよび９１２ｂに書き込まれた後に、システムセットアップのステップが、この時間ステップに対して完了する。
【０２０６】
ＧＰＵ上でクロスのシミュレーションを実装するための第２のステップには、図９に示されるように、位置および速度の更新済みの値
【０２０７】
【数１０４】
0005616060.tif 000133
に対する線形系を解くことが含まれる。カーネル演算９１０ｂは、テクスチャ９０２ａ、９０４ａ、９０６ａ、９０８ｂおよび９１２ｂからの入力に基づいて、線形方程式系を解く。この解に基づいて、位置および速度の更新済みの値は、それぞれテクスチャ９０４ｂおよび９０６ｂに書き込まれる。更新済みの値が書き込まれた後に、システムソルバーステップが、この時間ステップに対して完了する。
【０２０８】
ＧＰＵ上でクロスのシミュレーションを実装するための最終ステップには、図９に示されるように、衝突検出が含まれる。カーネル演算９１０ｃは、テクスチャ９０２ａ、９０４ｂ、９０６ｂおよび９０８ｂからの入力に基づいて、衝突が起こるか否かを決定する。カーネル演算９１０ｃの結果は、テクスチャ９０２ｂ、９０４ｃ、９０６ｃおよび９０８ｃに書き込まれる。これらの結果が書き込まれた後に、衝突応答ステップが、この時間ステップに対して完了する。
【０２０９】
ここで、ＧＰＵ上でクロスのシミュレーションを実装するためのステップのそれぞれが、より詳細に記述される。
【０２１０】
ｉ．ステップ１：システムセットアップ
ＧＰＵ実装の設計上の大きな難問は、コンパクトであり、かつ単一命令多重データ（ＳＩＭＤ）パラレル化を容易にする、系方程式のテクスチャ表現の開発である。本発明の１つの実施形態は、検討中の矩形点メッシュから直接的に得られた構造を有する、１７の持続性テクスチャを利用する。しかし、本発明は、１７のテクスチャに限定はされない。本発明の精神および範囲から逸脱することなく、異なる数のテクスチャを用いてＧＰＵ上に物理シミュレーションを行う方法を、当業者は理解することとなる。
【０２１１】
本明細書に記述された、クロスをシミュレーションするために用いられるテクスチャは、点メッシュ８００に対応する、「ｒｏｗｓ」の高さおよび「ｃｏｌｓ」の幅を有するｎ個のテクセルの２次元テクスチャである。点メッシュ８００は、それぞれ「ｒｏｗｓ」および「ｃｏｌｓ」の要素である、行および列に組織化される。従って、各テクスチャの各テクセル位置は、点メッシュ８００の特定の点に１対１にマッピングする。各テクスチャは、左から右へ、かつ上から下へと順序付けられる。一般的には、個別のテクスチャが、同一のテクスチャ座標｛ｓ、ｔ｝における同一点ｉに属する、異なるプロパティを格納する（明確にするために、本文は、全てのテクスチャ座標を、高さ＝‘ｒｏｗｓ’および幅＝‘ｃｏｌｓ’によって境界付けられた非正規整数として描写する）。点番号から点のテクスチャ座標への、およびその逆のマッピングは、以下によって与えられる。
【０２１２】
【数１０５】
0005616060.tif 000134
さらに、境界の状態を条件として、図８に示されるジョイントトポロジーの点オフセットも、表１８に示されるように、２次元テクスチャオフセットにマッピングする。
【０２１３】
【表１４】
0005616060.tif 000135
１７のテクスチャは、Ｐ、Ｖ、Ｆ、Ａ＃、Ｂ＃、Ｃ、およびＤに分類され、ここでは、Ａ＃およびＢ＃は、それぞれ６つのテクスチャの集結である。それぞれの
【０２１４】
【数１０６】
0005616060.tif 000136
に対し、１７のテクスチャコンテンツは、次いで以下の定義によって与えられる。第１に、テクスチャＰ、ＶおよびＦは、それぞれ
【０２１５】
【数１０７】
0005616060.tif 000137
を表す。特に、
・Ｐは、点の現在位置
【０２１６】
【数１０８】
0005616060.tif 000138
の３成分を格納し、
・Ｖは、点の現在速度
【０２１７】
【数１０９】
0005616060.tif 000139
の３成分を格納し、
・Ｆは、点の現在のネット力ベクトル
【０２１８】
【数１１０】
0005616060.tif 000140
の３成分を格納する。第２に、Ａ＃およびＢ＃は、それぞれ、
【０２１９】
【数１１１】
0005616060.tif 000141
の下三角（対角線上にない要素）を表す。特に、
・Ａ＃は、
【０２２０】
【数１１２】
0005616060.tif 000142
に対応する｛３×３｝行列を格納し、
・Ｂ＃は、
【０２２１】
【数１１３】
0005616060.tif 000143
に対応する｛３×３｝行列を格納し、ここでは、Ａ０−Ａ５およびＢ０−Ｂ５は、以下の６つのジョイントのそれぞれに対して定義される。
【０２２２】
【数１１４】
0005616060.tif 000144
第３に、テクスチャＣおよびＤは、それぞれ、
【０２２３】
【数１１５】
0005616060.tif 000145
の対角線上の要素を表す。特に、
・Ｃは、
【０２２４】
【数１１６】
0005616060.tif 000146
に対応する｛３×３｝行列を格納し、
・Ｄは、
【０２２５】
【数１１７】
0005616060.tif 000147
に対応する｛３×３｝行列を格納する。
【０２２６】
１７のテクスチャを定義したので、ここで、これらのテクスチャを埋めるための（すなわち、図９のシステムセットアップのステップを行うための）２段階工程が記述される。図１０は、点メッシュ８００の運動を支配する線形方程式系を設定するための、２段階工程の流れ図を図示する。図１０に含まれるのは、入力テクスチャ１００２ａおよび１００４ａ
【０２２７】
【数１１８】
0005616060.tif 000148
および出力テクスチャ１００６ａ、１００８ａ、１０１２ａ、１０１４ａ、および１０１６ａ
【０２２８】
【数１１９】
0005616060.tif 000149
である。
【０２２９】
図１０の第１の段階は、６つの同一のサブパスを含み、該サブパスは、ジョイントの相補的な対のジョイントに対して演算を行う、カーネル演算１０１０ａ−１０１０ｆによって表される。この第１段階において、ネット力ベクトル
【０２３０】
【数１２０】
0005616060.tif 000150
（すなわち、テクスチャＦ）および
【０２３１】
【数１２１】
0005616060.tif 000151
（すなわち、テクスチャＡ０−Ａ５およびＢ０−Ｂ５）の下三角（対角線上にない要素）が、決定される。すなわち、カーネル演算１０１０ａ−１０１０ｆの結果は、テクスチャ１００６ｂ、１００８ｂおよび１０１２ｂに書き込まれる。
【０２３２】
図１０の第２の段階は、カーネル演算１０１０ｇおよび１０１０ｈによって表される、２つの同一のサブパスを含み、該カーネル演算は、
【０２３３】
【数１２２】
0005616060.tif 000152
（すなわち、テクスチャＣおよびＤ）の対角線上要素を、その下三角の対角線上にない要素（すなわち、テクスチャＡ０−Ａ５およびＢ０−Ｂ５）から決定する。すなわち、カーネル演算１０１０ｇおよび１０１０ｈの結果は、それぞれ、テクスチャ１０１６ｂおよび１０１４ｂに書き込まれる。第１の段階および第２の段階は、それぞれ以下により詳細に記述される。
【０２３４】
システムセットアップの第１の段階（図１０）は、ネット力ベクトル
【０２３５】
【数１２３】
0005616060.tif 000153
（すなわち、テクスチャＣ）および
【０２３６】
【数１２４】
0005616060.tif 000154
（すなわち、テクスチャＡ０−Ａ５およびＢ０−Ｂ５）の下三角（対角線上にない要素）の決定を含む。図１０に示されるように、これら出力の評価は、カーネル演算１０１０ａ−１０１０ｆによって表されるような、ジョイント毎の解析の膨大な重複を含み得る。結果として、この第１の段階は、図１１に表されるように、６つの同一のジョイント毎のサブパスに分けられ得る。
【０２３７】
図１１は、ジョイントパスｍを表す、流れ図１１００を図示する。各ジョイントパスは、２つのサブパスを含み、第１カーネル１１１０ａ（ＥｖａＪｏｉｎｔと分類）および第２カーネル１１１０ｂ（ｕｐｄａｔｅＦと分類）によって表される。第１カーネル１１１０ａは、それぞれ一時的なテクスチャＴ、Ａｍ、およびＢｍに書き込まれる、
【０２３８】
【数１２５】
0005616060.tif 000155
に対するジョイント毎の値を計算する。サブパス毎に解析される特定のジョイントは、
【０２３９】
【数１２６】
0005616060.tif 000156
によって、テクスチャＡｍおよびＢｍに関連する。
【０２４０】
第１カーネル１１１０ａ（ｅｖａｌＪｏｉｎｔ）は、以下の事実を利用する。
【０２４１】
（１）ジョイント毎の値は、共に、最も容易に評価され、
（２）ＡｍおよびＢｍに格納された
【０２４２】
【数１２７】
0005616060.tif 000157
の対角線上にない要素は、実際には独立しており、
【０２４３】
【数１２８】
0005616060.tif 000158
に等しく、
（３）対称性
【０２４４】
【数１２９】
0005616060.tif 000159
によって、相補的なジョイントには、同一の解析が行われる。従って、我々のトポロジーにおけるジョイントの固有の半分を解析することが理想的（すなわち、作業の重複がない）である。さらに、対称によって、テクスチャＡ０−Ａ５およびＢ０−Ｂ５に格納された
【０２４５】
【数１３０】
0005616060.tif 000160
の下三角（対角線上にない要素）は、ヤコビアンにおける全ての対角線上にない要素を表すのに十分である。
【０２４６】
第２カーネル１１１０ｂ（ｕｐｄａｔｅＦと分類）は、解析されているジョイントの力を用いて、ネット力
【０２４７】
【数１３１】
0005616060.tif 000161
（または、テクスチャＣ）を更新する。第２カーネル（ｕｐｄａｔｅＦ）は、現時点でＴに格納されているジョイント毎の力
【０２４８】
【数１３２】
0005616060.tif 000162
の寄与を、（別のサブパスから来るか、または外力を含む）入力ネット力ベクトル
【０２４９】
【数１３３】
0005616060.tif 000163
またはテクスチャＣに加える。これには、特に、ジョイント力の線形独立およびニュートンの第３の法則によって提供される対称性を利用する。各サブパスは、ジョイントの相補的な対の力を効率的に計算するので、第２カーネル１１１０ｂ（ｕｐｄａｔｅＦ）は、両方の寄与を適切に考慮するためにＴをアドレスしなくてはならない（境界条件により、Ｔ中のジョイント力毎のある値が不規則であり得る）。
【０２５０】
再び図１０を参照すると、システムセットアップの第２および最終の段階は、
【０２５１】
【数１３４】
0005616060.tif 000164
（すなわち、テクスチャＣおよびＤ）の対角線上の要素の決定を含む。この第２の段階において、これらの対角線上の要素がそれらの対角線上にない要素の有利に構成された累積であるという事実は、強化される。特に、以下の累積のそれぞれは、最大１２項まで含み、各ジョイントに対するもの（境界条件によって変わる）は、テクスチャＡ０−Ａ５およびＢ０−Ｂ５において容易に入手できる。
【０２５２】
【数１３５】
0005616060.tif 000165
図１２に図解式に図示されるように、方程式１３ａにおける累積は、カーネル１２５０ａによって評価され（ｅｖａｌＤｉａｇｏｎａｌＣと分類）、方程式１３ｂにおける累積は、カーネル１２５０ｃによって評価される（ｅｖａｌＤｉａｇｏｎａｌＤと分類）。カーネル１２５０ａおよび１２５０ｃは、独立しており、それらの入力と出力だけが異なる。カーネル１２５０ａは、テクスチャ１２０２ａ、１２０４ａ、１２０６ａ、１２０８ａ、１２１０ａおよび１２１２ａから、入力としてのデータを取得し、それらテクスチャは、集合的に、ヤコブ行列
【０２５３】
【数１３６】
0005616060.tif 000166
の対角線上にない要素を表す。カーネル１２５０ｃの出力は、テクスチャ１２１４ｂ（すなわちテクスチャＣ）に書き込まれる。カーネル１２５０ｃは、テクスチャ１２２２ａ、１２２４ａ、１２２６ａ、１２２８ａ、１２３０ａおよび１２３２ａから、入力としてのデータを取得し、それらテクスチャは、集合的に、ヤコブ行列
【０２５４】
【数１３７】
0005616060.tif 000167
の対角線上にない要素を表す。
【０２５５】
ｉｉ．ステップ２：システムソルバー
再び図８を参照すると、ＧＰＵ上でのクロスのシミュレーションにおける第２のステップは、システムソルバーステップである。システムソルバーステップに対する最も有力なアプローチは、前述のＢａｒａｆｆ引例に記述された、線形系
【０２５６】
【数１３８】
0005616060.tif 000168
を反復的に解く、共役勾配（ＣＧ）法を用いることである。大型で疎、対称的かつ正定値の系に最適であり、ＣＧ法は、
【０２５７】
【数１３９】
0005616060.tif 000169
が、ユーザー定義の閾値より下回るまで、
【０２５８】
【数１４０】
0005616060.tif 000170
を手続き上で近似することを含む。本明細書に記述される例示的方法は、システムソルバーステップに対してＣＧ法を用いるが、他の方法もまた、当業者に認識されるように、本発明の精神および範囲から逸脱することなく、用いられ得る。
【０２５９】
ｉｉｉ．ステップ３：衝突応答
再び図８を参照すると、ＧＰＵ上でのクロスのシミュレーションにおける第３および最終のステップは、衝突応答ステップである。衝突検出スキームは、シミュレーションされているメッシュ（例えば点メッシュ８００）からの点の対が、（ｉ）メッシュからの別の点の対、または（ｉｉ）シミュレーションされている別のオブジェクト（例えば、点メッシュ８００として同一のシーンに描写されているボール）からの点の対、のいずれかと交わるかどうかを決定することによって、衝突が起きたかどうかを確認する。前述のＢａｒａｆｆ引例によって例示されるように、衝突検出スキームは、当業者に周知である。当業者に公知のあらゆる衝突検出スキームが、本発明の精神および範囲から逸脱することなく、用いられ得る。
【０２６０】
Ｃ．ＦＹＳＬで書かれた例示的コード
以下に提供されるものは、ＦＹＳＬで書かれたコードの例示的セクションである。特に、以下に提供されるものは、（ｉ）ＦＹＳＬで書かれた高レベルシーン記述、（ｉｉ）チャイルドアクター展開、および（ｉｉｉ）ファブリックジョイントのプロトタイプ展開、である。
【０２６１】
ｉ．ＦＹＳＬで書かれた高レベルシーン記述
【０２６２】
【表１５】
0005616060.tif 000171
【０２６３】
【表１６】
0005616060.tif 000172
ｉｉ．チャイルドアクター展開
【０２６４】
【表１７】
0005616060.tif 000173
【０２６５】
【表１８】
0005616060.tif 000174
【０２６６】
【表１９】
0005616060.tif 000175
ｉｉｉ．ファブリックジョイントのプロトタイプ展開
【０２６７】
【表２０】
0005616060.tif 000176
ＩＶ．例示的なコンピュータ実装
本発明の実施形態は、ハードウェア、ソフトウェア、またはそれらの組み合わせを用いて実装され得、また、１つ以上のコンピュータシステムまたは他のプロセッシングシステムにおいて実装され得る。しかし、本発明によって行われる操作は、加算や比較などに関して、頻繁に参照されたが、それらは、一般的に、人間のオペレーターによって行われる、頭の中で行うオペレーションに関連する。本発明の一部を形成する、本明細書に記述されるオペレーションのいずれにおいても、そのような人間のオペレーターの能力はなにも必要なく、または、ほとんどの場合において望まれない。むしろ、オペレーションは、機械的なオペレーションである。本発明のオペレーションを行うために有用な機械は、デジタルコンピュータを含み、例えば、パーソナルコンピュータ、ビデオゲームコンソール、携帯電話、携帯情報端末、または同様のデバイスなどである。
【０２６８】
実際に、一実施形態において、本発明は、本明細書に記述された機能性を実行することが可能な１つ以上のコンピュータシステムに向けられている。コンピュータシステム１３００の例は、図１３に示される。
【０２６９】
コンピュータシステム１３００は、１つ以上のプロセッサ、例えばプロセッサ１３０４を含む。プロセッサ１３０４は、汎用プロセッサ（ＣＰＵなど）、または専用プロセッサ（ＧＰＵなど）であり得る。プロセッサ１３０４は、通信インフラストラクチャ１３０６（例えば、通信バス、クロスオーバーバー、またはネットワーク）に接続される。様々なソフトウェアの実施形態は、この例示的なコンピュータシステムの点から記述される。本記述を読んだ後は、他のコンピュータシステムおよび／またはアーキテクチャーを用いて本発明を実装する方法が、当業者には明らかとなる。
【０２７０】
コンピュータシステム１３００は、ディスプレイインターフェース１３０２を含み、該ディスプレイインターフェース１３０２は、ディスプレイユニット１３３０に表示するために、通信インフラストラクチャ１３０６（または不図示のフレームバッファ）から、グラフィックス、テキスト、および他のデータを転送する。
【０２７１】
コンピュータシステム１３００はまた、メインメモリ１３０８、好ましくは、ランダムアクセスメモリ（ＲＡＭ）を含み、また、二次メモリ１３１０をも含み得る。二次メモリ１３１０は、例えば、ハードディスクドライブ１３１２および／またはリムーバブルストレージドライブ１３１４を含み得、フロッピー（登録商標）ディスクドライブ、磁気テープドライブ、光学ディスクドライブなどが、その代表である。リムーバブルストレージドライブ１３１４は、周知の方法で、リムーバブルストレージユニット１３１８との読み取りおよび書き込みを行う。リムーバブルストレージユニット１３１８は、フロッピー（登録商標）ディスク、磁気テープ、光学ディスクなどを表し、これは、リムーバブルストレージドライブ１３１４によって読み書きがされる。認識されるように、リムーバブルストレージユニット１３１８は、コンピュータソフトウェアおよび／またはデータをその中に格納した、コンピュータ使用可能媒体を含む。
【０２７２】
代替的な実施形態において、二次メモリ１３１０は、コンピュータシステム１３００にコンピュータプログラムまたは他の命令をロードさせる、他の同様のデバイスを含み得る。そのようなデバイスは、例えば、リムーバブルストレージユニット１３２２およびインターフェース１３２０を含み得る。そのような例は、プログラムカートリッジおよびカートリッジインターフェース（ビデオゲーム機に見受けられるようなものなど）、リムーバブルメモリチップ（消去可能プログラマブル読取り専用メモリ（ＥＰＲＯＭ）またはプログラマブル読取り専用メモリ（ＰＲＯＭ）など）および関連ソケット、ならびに他のリムーバブルストレージユニット１３２２およびインターフェース１３２０を含み得、これらは、リムーバブルストレージユニット１３２２からコンピュータシステム１３００にソフトウェアおよびデータを転送することを可能にする。
【０２７３】
コンピュータシステム１３００はまた、通信インターフェース１３２４を含み得る。通信インターフェース１３２４は、コンピュータシステム１３００と外部デバイスとの間でのソフトウェアおよびデータの転送を可能にする。通信インターフェース１３２４の例は、モデム、ネットワークインターフェース（イーサネット（登録商標）カードなど）、通信ポート、パーソナルコンピュータメモリカードインターナショナルアソシエーション（ＰＣＭＣＩＡ）スロットおよびカードなどを含み得る。通信インターフェース１３２４を介して転送されるソフトウェアおよびデータは、信号１３２８の形式をとり、該信号は、電子、電磁気、光学、または通信インターフェース１３２４によって受信可能な他の信号であり得る。これらの信号１３２８は、通信パス（例えばチャネル）１３２６を介して通信インターフェース１３２４に提供される。このチャネル１３２６は信号１３２８を運び、ワイヤまたはケーブル、光ファイバー、電話線、セルラーリンク、無線周波数（ＲＦ）リンクおよび他の通信チャネルを用いて実装され得る。
【０２７４】
本文において、「コンピュータプログラム媒体」および「コンピュータ使用可能媒体」という用語は、概して、リムーバブルストレージドライブ１３１４、ハードディスクドライブ１３１２にインストールされたハードディスクなどの媒体および信号１３２８を指すために用いられる。これらコンピュータプログラム製品は、コンピュータシステム１３００にソフトウェアを提供する。本発明は、そのようなコンピュータプログラム製品に向けられる。
【０２７５】
コンピュータプログラム（コンピュータ制御ロジックとも呼ばれる）は、メインメモリ１３０８および／または二次メモリ１３１０に格納される。コンピュータプログラムはまた、通信インターフェース１３２４を介して受信され得る。そのようなコンピュータプログラムは、実行されたときには、コンピュータシステム１３００が本明細書に議論されたように本発明の機能を行えるようにする。特に、コンピュータプログラムは、実行されたときには、プロセッサ１３０４が本発明の機能を行えるようにする。従って、そのようなコンピュータプログラムは、コンピュータシステム１３００のコントローラを表す。
【０２７６】
ソフトウェアを用いて本発明が実装される実施形態において、該ソフトウェアは、リムーバブルストレージドライブ１３１４、ハードドライブ１３１２、または通信インターフェース１３２４を用いて、コンピュータプログラム製品に格納され、コンピュータシステム１３００にロードされ得る。プロセッサ１３０４によって実行されるときには、制御ロジック（ソフトウェア）は、プロセッサ１３０４に、本明細書に記述されたように本発明の機能を行わせる。
【０２７７】
別の実施形態において、本発明は、例えば、ＧＰＵなどのハードウェア構成要素を用いて、主にハードウェアに実装される。本明細書に記述された機能を行うためのハードウェアステートマシーンの実装は、当業者に明らかであろう。
【０２７８】
さらに別の実施形態において、本発明は、ハードウェアおよびソフトウェアの両方の組み合わせを用いて実装される。
【０２７９】
Ｖ．結論
概要および要約の章ではなく、実施形態の章は、請求項を解釈するために用いられることを意図するということを、認識されたい。概要および要約の章は、発明者によって意図されるように、本発明の、全てではないが、１つ以上の例示的な実施形態を述べ得る。故に、概要および要約の章は、あらゆる方法において、本発明および添付の請求項を限定する意図はない。
【図１】
0005616060.tif 000192
【図２】
0005616060.tif 000193
【図３】
0005616060.tif 000194
【図４】
0005616060.tif 000195
【図５】
0005616060.tif 000196
【図６】
0005616060.tif 000197
【図７】
0005616060.tif 000198
【図８】
0005616060.tif 000199
【図９】
0005616060.tif 000200
【図１０】
0005616060.tif 000201
【図１１】
0005616060.tif 000202
【図１２】
0005616060.tif 000203
【図１３】
0005616060.tif 000204
【図１４Ａ】
0005616060.tif 000205
【図１４Ｂ】
0005616060.tif 000206
【図１５Ａ】
0005616060.tif 000207
【図１５Ｂ】
0005616060.tif 000208