(57)【特許請求の範囲】
【請求項１】
ａ）２個の物体間の交差ボリュームＶのバウンディング多面体を決定する段階と、
ｂ）多面体の可視化軸に対し、階層化深さ画像（ＬＤＩ）アルゴリズムを適用して、接触ピクセルの組を決定する段階と、
を含む、幾何学的プリミティブを用いてモデル化される少なくとも２個のボリューム物体間の交差の相互作用シミュレーションの方法であって、
前記方法が、以下の段階：
ｃ）交差ボリュームＶのサイズを、接触ピクセルから計算する段階と；
ｄ）多面体の幾何学的プリミティブの頂点毎に、交差ボリュームＶのサイズの偏微分を、可視化軸上の頂点の座標に関して計算する段階と；
ｅ）少なくとも段階ｂ）及びｄ）を２本の他の直交軸に対して繰り返して、３本の直交軸に関する偏微分を決定する段階と；
ｆ）前記偏微分から計算される接触力ｆを、物体の幾何学的プリミティブの各頂点と関連付ける段階と；
を付加的に実行し、前記各段階がプロセッシングユニットにより実行されることを特徴とする、前記方法。
【請求項２】
可視化軸ｚ上の頂点Ａに対する交差ボリュームＶの偏微分を、以下の式：
【数１】
0005400802.tif 000014
（ここで、「ａ」はピクセルの面積であり、「Ｃ」は交差ボリュームの面を覆うフラグメントの添字の集合であり、ｚｉ，ｊは接触ピクセルの高さであり、そして、「ｄ」はＬＤＩアルゴリズムによる投影の上側ピクセルに対する２、又は、下側ピクセルに対する１にそれぞれ等しいものであるものとする）
によって定義することを特徴とする、請求項１に記載の方法。
【請求項３】
段階ｆ）において、接触力を、以下の式：
【数２】
0005400802.tif 000015
（ここで、Ｅは交差ボリュームＶの増加関数であるポテンシャルエネルギーであり、そして、ｘは頂点座標のベクトルであるものとする）
によって定義することを特徴とする、請求項１又は２に記載の方法。
【請求項４】
ポテンシャルエネルギーＥを、以下の式：
【数３】
0005400802.tif 000016
すなわち、
【数４】
0005400802.tif 000017
（ここで、ｋは正の数であるものとする）
によって定義することを特徴とする、請求項３に記載の方法。
【請求項５】
段階ｃ）において、交差ボリュームＶを、プロセッシングユニットにより、以下の式：
【数５】
0005400802.tif 000018
（ここで、「ａ」はピクセルの面積であり、「Ｃ」は交差ボリュームの面を覆うフラグメントの添字の集合であり、ｚｉ，ｊは接触ピクセルの高さであり、そして、「ｄ」はＬＤＩアルゴリズムによる投影の上側ピクセルに対する２、又は、下側ピクセルに対する１にそれぞれ等しいものであるものとする）
から計算することを特徴とする、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
段階ｃ）が段階ｅ）においても繰り返され、次の段階のため考慮されるべき交差ボリュームが、繰り返し毎に計算される交差ボリュームを加算することにより取得される値の１／３であることを特徴とする、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
段階ｂ）において、各接触ピクセルが、
−高さ値と、
−前記接触ピクセルと関連付けられる幾何学的プリミティブの識別子と、
−前記接触ピクセルが属している物体の識別子と、
−前記接触ピクセルと関連付けられる幾何学的プリミティブの法線の方向と、
−前記接触ピクセルと関連付けられる幾何学的プリミティブ上の重心座標と
に関連付けられることを特徴とする、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
幾何学的プリミティブが三角面であることを特徴とする、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
多面体が、２個の物体のそれぞれに対応する２個のバウンディングボックス間の交差から得られるボリュームとして定義されることを特徴とする、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
相互作用動的シミュレーションのため、プロセッシングユニットにより剛性マトリクスを使用して、頂点の位置の変動に応じて力の変動を符号化することを特徴とする、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
剛性マトリクスが、プロセッシングユニットにより力ｆの微分を計算することにより決定されることを特徴とする、請求項１０に記載の方法。
【請求項１２】
幾何学的プリミティブを用いてモデル化される少なくとも２個のボリューム物体間の交差の相互作用シミュレーションの装置であって、
請求項１〜１１のいずれか１項に記載の接触力を計算するための方法を実施するグラフィックス・プロセッシング・ユニットＧＰＵを備えることを特徴とする、前記装置。
【請求項１３】
交差ボリュームの計算値を保存する少なくとも１個のボリュームレジスタと、幾何学的プリミティブの各頂点について、３本の可視化軸方向での交差ボリュームの偏微分を成分とするベクトルを保存する勾配レジスタとを更に備えることを特徴とする、請求項１２に記載の装置。
【請求項１４】
グラフィックス・プロセッシング・ユニットによって計算される画像を復元することができ、そして、前記画像から２個の物体に付与されるべき力を推定することができるセントラル・プロセッシング・ユニットＣＰＵを更に備えることを特徴とする、請求項１２又は１３に記載の装置。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
本発明は、三角面によって画定される少なくとも２個のボリューム物体間の接触をシミュレートする方法に関する。
【０００２】
本発明は、ビデオゲーム又は外科手術シミュレーターのためのリアルタイム物理的シミュレーションの分野で特に有用な用途が見出される。しかし、本発明は重要な（non-trivial）図形と接触する物体に関する、任意のシミュレーションに適用できるので、範囲がより広い。
【０００３】
機械的物体のシミュレーションは、概略的に、衝突検出、接触力の計算、内力の計算、及び時間積分の４つの主要なプロセスに分類することができる。衝突検出は、多くの場合に最も集中的な処理演算であり、長年に亘って広範囲の詳細調査の課題であった。この処理は、シミュレーションの信頼性がこの処理に依存するので重要である。
【０００４】
交差の正確な幾何学的テスト及び詳細な計算は、接触面間の相互作用の力を決定するのに必要である。物体は、概して、接触プリミティブ（例えば、球又は三角形）に分類される。しかし、球プリミティブは、接触面のやや説得力のない近似を導き、残念なことに実質的なアーティファクトを生じる。三角形に基づくプリミティブは、より有効であるが、球より多くの幾何学的計算を必要とする。いずれの場合にも、反発力の計算は適用が複雑であり、不連続空間関数が現れることがある。剛体の場合、これらの不連続関数を回避するために事前に計算を実行することが可能であるが、この計算は変形可能な物体向けに想定することが難しい。衝突検出及び接触力の計算は、従って、依然として極度に難しい課題である。
【０００５】
従来技術では、衝突検出及び応答技術を開示する、Teschnerらの“Collision detection for deformable objects”, Computer Graphics Forum 24, 1(March 2005), 61-81がある。この文献は、衝突検出に内在する２次複雑性を解決するために、バウンディングボリューム階層を作成する技術を開示している。この文献では、距離フィールド技術を使用して、ロバストな衝突検出を達成する。この技術では、空間内のあらゆる点に対し、この点に最も近接する面要素である「最近接形状特徴（closest feature）」を保存して、深さ交差を許容する。実際には、この技術は剛体だけに使用される。なぜなら、シミュレーションの初期化の間で距離フィールドの先行する計算（前処理）が必要となるからである。不安定な応答を生成する可能性がある、３次元空間の面への適用の際に、不連続性の問題も依然として存在する。
【０００６】
概して、既存のデータ処理システム（例えば、パーソナルコンピュータ）は、複雑さが絶えず増加するグラフィックスコンポーネントの処理及び表示を取り扱う機能を有する、グラフィックス・カードを含んでいる。このグラフィックス・カードは、特に、３次元表示を高速化することを可能にする。このため、グラフィックス・カードは、３次元のため最適化されたプロセッサであるグラフィックス・プロセッシング・ユニット（ＧＰＵ）を含む。
【０００７】
近年、多角形の効率的なサンプリングのためのＧＰＵの計算能力及びその容量を利用するため、画像ベース法が導入された。所定のメッシュ図形に対し、画像ベース法は幾何学的プリミティブのペアを生成し、次に、前記幾何学的プリミティブのペアは、接触力を計算するためＣＰＵによって処理される。画像ベース法は、ボリュームデータ構造を使用しないので、剛体及び変形可能な物体に効果的に適用できる。接点のペアは、三角形又はボリューム内の点で構成されることができる。検出後、ＣＰＵによる付加的な計算が、交差及び接触力をモデル化するため必要とされる。
【０００８】
階層化深さ画像（ＬＤＩ；layered depth image）アルゴリズムを開示する、Heidelbergerらによる、“Real-time volumetric intersections of deforming objects”, Proceedings of Vision, Modeling, Visualization (VMV), Munich, Germany, November 19-21, 2003が知られている。このアルゴリズムは、所定の視点からの物体交差の図形の複数の層のコンパクト表現を提供する。このアルゴリズムは、交差ボリューム（intersection volume）の幾何学的モデルを構築することを可能にする。このアルゴリズムによれば、物体のバウンディングボックスが計算される。次に、衝突候補物体のペア毎に、可視化軸が選択され、各物体の面全体が種々のテクスチャでレンダリングされる（ＬＤＩ）。バウンディングボックスの交差に含まれる面は可視化され、この可視化は可視化の方向に延長されて、すべての面層を包含する。次に、衝突検出は、可視化軸に沿って、連続したテクセル（テクスチャピクセル）のペア、又は、自己衝突のためのトリプレットを考慮して実行される。この迅速かつ単純な方法は前処理演算が回避される。しかし、前記文献は衝突検出だけを扱い、接触力の計算には言及していない。
【０００９】
本発明の目的は、特に、複雑な幾何学的計算を限定することにより前記欠点を改善することである。
【００１０】
本発明の別の目的は、幾何学的前処理を必要とすることなく、シミュレーション対象の剛体及び変形可能な物体の接触力を迅速に計算する方法である。
【００１１】
前記目的のうちの少なくとも一方は、幾何学的プリミティブ（特に、三角面）によってモデル化される少なくとも２個のボリューム物体間の交差の相互作用シミュレーションの方法を用いて達成される。この方法は、
ａ）２個の物体間の交差ボリュームのバウンディング多面体を決定する段階と、
ｂ）多面体の所定の可視化軸に対し、階層化深さ画像（ＬＤＩ）のアルゴリズムを適用して、シミュレーション対象の物体の交差ボリュームの面要素である接触ピクセルの組を決定する段階と、
を含む。
【００１２】
本発明によれば、更に、以下の段階、
ｃ）交差ボリュームの（立方メートル単位での）サイズを、接触ピクセルから計算する段階と、
ｄ）多面体の幾何学的プリミティブの頂点毎に、交差ボリュームＶのサイズの偏微分（partial derivative）を、可視化軸上の頂点の座標に関して計算する段階と、
ｅ）少なくとも段階ｂ）及びｄ）を２本の他の直交する可視化軸に対して繰り返して、３本の直交軸に関する偏微分を決定し、それによって、勾配ベクトルを取得する段階と、
ｆ）前記偏微分から計算される力ｆを、物体の幾何学的プリミティブの各頂点と関連付ける段階と、
が実行される。
【００１３】
これらの段階は静的な条件下で実行され、時間積分は存在しない。
【００１４】
２個の物体は、一つの全く同じ実体の２つの部分であることができ、その結果、自己衝突を処理することができる。
【００１５】
本発明による方法の場合、ＬＤＩアルゴリズムは、３つの直交方向でサンプリングされる高さフィールドの形で、接触面をモデル化するため使用される。従って、接触面に作用する圧力を、３方向における交差ボリュームの偏微分に従って計算することができる。従来技術の文献の中で、３本の直交軸上でのＬＤＩアルゴリズムの実施と、交差ボリュームの偏微分からの力の計算とを開示している文献はない。これらの偏微分は、有利には、グラフィックス・カードの内部で作成される画像から計算することができる。その結果、標準的なグラフィックスハードウェア（例えば、パーソナルコンピュータのグラフィックス・カード）を、シミュレーション対象の物体間の接触力を計算するため使用することができる。
【００１６】
本発明は、三角形の頂点に付与される接触力の成分を直接的に計算することが可能な画像ベース方法である。より詳細には、ＬＤＩアルゴリズムは、ピクセルに基づく新しい幾何学的モデルを案出することにより拡張される。交差ボリュームがモデル化されるだけでなく、頂点の座標に関する交差ボリュームの微分もモデル化される。従って、複雑な幾何学的計算を回避しながら、深さ交差を効果的に考慮することができる。
【００１７】
更に、多面体は、２個の物体のそれぞれに対応する２個のバウンディングボックス間の交差から得られるボリュームとして定義される。
【００１８】
好ましくは、多面体は直方体であり、３本の可視化軸はこの直方体の３本の直交軸である。
【００１９】
力の計算は物体の内部ダイナミクスから独立し、そして、面は種々の物理モデルに貼り付け可能である。
【００２０】
本発明によれば、段階ｂ）において、各接触ピクセルは、
−高さ値と、
−このピクセルと関連付けられる幾何学的プリミティブの識別子と、
−このピクセルが属している物体の識別子と、
−このピクセルと関連付けられる幾何学的プリミティブへの法線の方向と、
−このピクセルと関連付けられる幾何学的プリミティブ上の重心座標と、
に関連付けられることができる。
【００２１】
交差ボリュームＶは種々の方式で計算することができる。或る実施例は長方形を使用して、可視化軸（この可視化軸は、交差ボリュームの断面図に対応する）に沿って見える交差ボリュームにより定義される面をモデル化する。この場合、段階ｃ）において、交差ボリュームＶは、以下の式：
【数１】
0005400802.tif 000002
（ここで、「ａ」はピクセルの面積であり、「Ｃ」は交差ボリュームの面を覆うピクセルの添字の集合であり、ｚｉ，ｊは接触ピクセルの高さであり、そして、「ｄ」は、上側ピクセルであるか、又は、下側ピクセルであるかによって２又は１に等しく、この上側ピクセル又は下側ピクセルという考え方は、ＬＤＩアルゴリズムにおいて規定されるものとする）
から計算される。実際に、高さフィールド表現では、衝突は、上側ピクセル及び下側ピクセルというピクセルのペアを含み、上側ピクセルに対して「ｄ」は２に等しく、下側ピクセルに対して「ｄ」は１に等しい。
【００２２】
本発明によれば、力を計算するためには、反発力は交差ボリュームを最小化する傾向がある、と仮定される。その結果、交差ボリュームＶと関連付けられるポテンシャルエネルギーＥが定義される。
【００２３】
有利には、段階ｆ）において、力は、以下の式：
【数２】
0005400802.tif 000003
（ここで、ｘは頂点座標のベクトルであるものとする）
によって定義することができる。
【００２４】
有利には、このエネルギーＥは交差ボリュームＶの増加関数である。従って、対応する力はボリュームの勾配に比例する。ポテンシャルエネルギーＥは、例えば、次式：
【数３】
0005400802.tif 000004
によって定義することができ、そして、
【数４】
0005400802.tif 000005
（ここで、ｋは正の数であるものとする）
を得る。
【００２５】
ボリューム勾配（ボリュームの偏微分）はボリュームの最大変化の方向を示すので、反発力は三角形の法線と平行であり、三角形の面積に比例する。力は、交差ボリュームの面全体に亘って積分された圧力の和であると解釈できる。
【００２６】
本発明の有利な特徴によれば、ＬＤＩの軸上の頂点Ａのｚ座標に関する交差ボリュームの偏微分は、以下の式：
【数５】
0005400802.tif 000006
によって定義される。
【００２７】
実際には、項
【数６】
0005400802.tif 000007
が、概してピクセル（ｉ，ｊ）の高さ及び色を補間するために使用されるグーロー（重心）シェーディング係数に相当することに注意されたい。
【００２８】
本発明の有利な実施態様によれば、段階ｃ）は段階ｅ）において更に繰り返され、次の段階のため考慮されるべき交差ボリュームＶは、繰り返し毎に計算される交差ボリュームを加算することにより取得される値の１／３である。この技術は、交差ボリュームの正確な値を３本の可視化軸上での交差ボリュームの平均値で近似することを可能にする。
【００２９】
有利には、装置は、交差ボリュームの計算値を保存する少なくとも１個のボリュームレジスタと、頂点１個当たりに３個のスカラ値（各々は可視化軸に関連付けられる）を含むベクトルを有する勾配レジスタとを更に備えることができる。
【００３０】
本発明の或る実施態様によれば、相互作用動的シミュレーションのため、剛性マトリクスを使用して、頂点の位置の変動に応じて力の変動を符号化することができる。この剛性マトリクスは、力ｆの微分を計算することにより決定され、先行する式から始める場合、次式：
【数７】
0005400802.tif 000008
に従って近似できる。
【００３１】
本発明の別の態様によれば、幾何学的プリミティブを用いてモデル化される少なくとも２個のボリューム物体間の交差の相互作用シミュレーション装置が提案される。本発明によれば、この装置は、接触力を計算するために上述されるような方法を実施するグラフィックス・プロセッシング・ユニットＧＰＵを備える。
【００３２】
装置は、グラフィックス・プロセッシング・ユニットＧＰＵと並んで、グラフィックス・プロセッシング・ユニットによって計算された画像を復元し、それらの画像から２個の物体に印加されるべき力を推論することができるセントラル・プロセッシング・ユニットＣＰＵを備える包括的なマシンである。
【図面の簡単な説明】
【００３３】
本発明の他の利点及び特徴は、決して限定的ではない一実施態様の詳細な説明と添付図面とを検討することにより明白になるであろう。
【図１】ＣＰＵと通信するグラフィックス・プロセッシング・ユニットの略全体図である。
【図２】ＬＤＩアルゴリズムの適用中の段階を説明する図である。
【図３】ＬＤＩアルゴリズムの適用中の段階を説明する図である。
【図４】接触力を計算する本発明による方法の種々の段階での、２個の交差する物体の２次元における略図である。
【図５】接触力を計算する本発明による方法の種々の段階での、２個の交差する物体の２次元における略図である。
【図６】接触力を計算する本発明による方法の種々の段階での、２個の交差する物体の２次元における略図である。
【図７】接触力を計算する本発明による方法の種々の段階での、２個の交差する物体の２次元における略図である。
【００３４】
限定的ではない実施例として、本発明は、三角面からピクセルの作成を対象とするグラフィックス・プロセッサＧＰＵの内部で使用できる。図１は、グラフィックス・カード１及びそれと通信するＣＰＵプロセッサ２を非常に概略的に示している。グラフィックス・カードには、特に、グラフィックス・プロセッサＧＰＵ３、メモリゾーン４、ＣＰＵ２と通信するコネクタ５及び６、並びに、表示手段（図示せず）が設けられている。このメモリゾーン４には、特に、交差ボリュームの計算値を保存するボリュームレジスタ７と、本発明による三角面の各頂点に関する偏微分を含むベクトルを保存する勾配レジスタ８とが存在する。これらのレジスタ７、８は、ＣＰＵ側のＲＡＭメモリにも存在することができる。
【００３５】
好ましくは、グラフィックス・カードはＬＤＩアルゴリズムを実行し、ＬＤＩアルゴリズムからの出力データは、本発明による残りの演算のためにプロセッサＣＰＵによって復元され、その後に処理される。
【００３６】
同様に、本発明による方法全体をプロセッサＣＰＵで直接実行することもできる。
【００３７】
次に、２個の交差する物体に適用されるＬＤＩ技術を、図２及び３を参照しながら説明する。最初に、バウンディングボックス９、１０が各物体１１、１２の周りで定義される。次に、２個のバウンディングボックス９及び１０の間の交差である直方体１３が特定される。この直方体１３は、物体１１の一部分及び物体１２の一部分によって満たされた交差ボリュームを含む。図２において、交差ボリューム１４は破線により表示されている。
【００３８】
最初に、物体１１及び１２は３次元でシミュレートされる。しかし、図２では、可視化軸が、物体１１及び１２が２次元で表示されるように選択されている。直方体１３では、接触面は物体１１と１２とを画定する線によって表示される。次に、図２の平面内に含まれているこれらの面がサンプリングされる。前記サンプリングは図３に示されるように、規則的なサンプリングであり、各サンプル又はピクセルは、水平直線と直方体１３に含まれる線（又は面）との間の交点として決定される。図３は、物体１１及び１２を画定する線とクロスする複数のこれらの水平直線１５を、サンプル又はピクセル１６ａ−１６ｄとして示している。次に、これらのピクセル１６ａ−１６ｄの投影は、水平方向に実行される。面は、高さフィールドとして表現される。複数の面が一つの同じ点に投影されることがあるので、複数の層が使用される。第１の層ｃ１は、１次サンプル１６ａ、すなわち、各水平直線１５と直方体１３の中の線との間の１回目のクロッシングから得られるサンプルにより構成される。層ｃ２は、各水平直線１５と直方体１３の内部の線との間の２回目のクロッシングに対応する２次サンプル１６ｂを含む。同じことがサンプル１６ｃを含む層ｃ３、及び、（直方体１３の中の面と４回目にクロスする１本の線１５から取得される）１個のサンプル１６ｄを含む層ｃ４に当てはまる。接触ピクセルは交差ボリューム１４を画定するサンプルである。
【００３９】
各サンプルは、サンプルの高さ、関連付けられた幾何学的プリミティブの識別子、サンプルが属している物体の識別子、関連付けられた幾何学的プリミティブの法線の方向、及び、関連付けられた幾何学的プリミティブ上の重心座標を含む。
【００４０】
次の図は、接触力を計算し付与する方法を詳細に示す。
【００４１】
図４〜７は、２個の物体１７と１８との間の別の交差の実施例を示す。物体１７は、ほぼ完全に物体１８に包含されている。各物体は、三角形プリミティブに従ってモデル化され、実際には、図４〜７において物体１７及び１８を表す多角形の頂点である頂点Ａ〜Ｍが識別可能である。交差ボリューム１９は、物体１７の面と物体１８の１つの接線とによって主に画定される破線２３を使って描かれた多角形によって図示される。この破線２３は、２個の物体間の接触面を表す。ゾーン２０及び２１は、接触力を図示する。ゾーン２０は、物体１８によって付与される接触力を表す。ゾーン２１は、物体１７によって付与される接触力を表す。本発明によれば、ＬＤＩアルゴリズムは、３本の可視化軸又は直交投影軸に沿って、物体１７及び１８の交差に適用される。開示内容を簡単にするため、図５及び６は、２本の直交軸、すなわち、図５における水平及び図６における垂直に沿った投影だけを図示している。
【００４２】
図５は、垂直方向での面のサンプリングを示す。各線はピクセルである。サンプリングは、水平チャネルに沿って実行される。ボックス２２は、高さフィールドとして表され、すなわち、２個の物体１７及び１８の面でサンプリングされるピクセルの層の形態で表される。ボックス２２の中の「＋」及び「−」の標示は、対応するピクセルでの反発圧の方向に対応している。ボックス２２は、物体間の交差の特定、及び、接触ピクセル、すなわち、接触面のピクセルの特定に役立つ。図５及び６において、接触ピクセルのそれぞれは、反発圧を表す矢印を担っている。図６は、垂直投影を図示する。図５の場合と同様に、サンプリング後に取得されるピクセルは、短い線によって表わされるが、この場合には、短い線は水平である。接触ピクセルも、反発圧を表す矢印を担っている。
【００４３】
各頂点Ａ〜Ｍでの接触力の計算は、３本の可視化軸に沿って交差ボリューム１９を計算することを含む。この計算は、図６における垂直投影に対して示されるだけである。計算は他の可視化軸についても同じである。本発明によれば、ボリュームは以下の式：
【数８】
0005400802.tif 000009
から計算される。
【００４４】
実際には、「ａ」は各接触ピクセルの面積であり、ｉ、ｊは図６における各接触ピクセルの識別情報を提供する。例えば、（物体１７の接線に位置している）接触ピクセル２４の場合、このピクセルに関連付けられる高さｚｉ，ｊは、図６に示されているように基準点ｚでのこのピクセルの高さであり（投影軸に平行な座標軸）、「ｄ」は１に等しい。これに対し、（物体１８の接線に位置している）接触ピクセル２５の場合、このピクセルに関連付けられる高さｚｉ，ｊは、図６に示されているように基準点ｚでのこのピクセルの高さであり、「ｄ」は２に等しい。接触ピクセル２４及び２５に対し、交差ボリュームの計算は、結局、図６における影付き部分のボリュームの計算になることがわかる。２４は下側接触ピクセルであり、２５は上側接触ピクセルである。
【００４５】
交差ボリュームは、１本の可視化軸に沿って、又は、可視化軸毎に計算され、後者の場合には、交差ボリュームの３つの計算値の平均が使用されることになる。
【００４６】
ボリュームが計算されると、高さに関するボリュームの偏微分が、可視化軸毎に、かつ、各頂点Ａ−Ｍのレベルで計算され、図６の実施例において、この偏微分は、投影軸であるｚ軸に関する偏微分である。このため、有利には、以下の式：
【数９】
0005400802.tif 000010
が使用される。
【００４７】
従って、この式は、３本の可視化軸に沿って各頂点に適用される。
【００４８】
従って、勾配ベクトルは、このようにして、
【数１０】
0005400802.tif 000011
という形式で取得される。
【００４９】
本発明によれば、ポテンシャルエネルギーが、
【数１１】
0005400802.tif 000012
によって定義される。次に、接触力は、
【数１２】
0005400802.tif 000013
（ここで、ｋは正の数であるものとする）
である。
【００５０】
実際には、事前に計算される勾配ベクトルを復元し、−ｋＶを乗じれば十分である。
【００５１】
従って、本発明は、機械的物体のシミュレーションにおいて接触力を計算することを可能にする。シミュレーション対象の物体は、物体が相互に交差する場合に、相互に交差する接触面が設けられる。本発明は、３つの直交方向でサンプリングされる高さフィールドの形式で接触面をモデル化し、次に、直交方向に３つのＬＤＩを使用して、空間内の各方向において三角形の頂点の座標に関して交差ボリュームの微分を計算することで構成される。接触面に作用する圧力は、その後、これらの偏微分に従って計算できる。
【００５２】
当然ながら、本発明は上述された実施例に限定されることがなく、発明の範囲を越えることなく、これらの実施例に種々の調整を行うことができる。
【図１】
0005400802.tif 000019
【図２】
0005400802.tif 000020
【図３】
0005400802.tif 000021
【図４】
0005400802.tif 000022
【図５】
0005400802.tif 000023
【図６】
0005400802.tif 000024
【図７】
0005400802.tif 000025