(57)【特許請求の範囲】
【請求項１】
少なくとも１つの数値的にシミュレートされた第１多面体オブジェクト１０と、少なくとも１つの数値的にシミュレートされた第２多面体オブジェクト２０との衝突を検出するとともに、前記第１、第２オブジェクト間の近接および接触についての幾何学的情報を構築するコンピュータ実装システムであって、
前記システムは、
前記数値的にシミュレートされた第１、第２多面体オブジェクト１０、２０を、Ｒnにおける干渉し合わない単体的複体Ｋ1、Ｋ2の形式で表わす（ただし、Ｒnは、実数体をそれ自体ｎ倍（ｎは２または３）して得られるカルテシアン積を示す）表示手段と、
各単体的複体Ｋについて、頂点の座標を固定座標系で示す前処理手段１１０と、
を提供する指示を実行する機能を有するプロセッサを備え、
前記前処理手段１１０は、少なくとも、前記各単体的複体Ｋの各フェースσについて、前記各フェースσに関連づけられた強い意味での複数の法線（数１）に対応する多面錐の幾何学的表記を計算する手段１１１と、前記フェースσが属する接触クラスのラベルを決定する手段と、各単体的複体Ｋについて、前記単体的複体Ｋのフェースσの位置と、前記強い意味で関連づけられた法線（数２）の集合との両方から、前記単体的複体Ｋで表された前記オブジェクトの包含体積の木を求める手段と、を備え、
前記プロセッサはさらに、前記前処理手段１１０に関連づけられ、局所最短距離（ＬＭＤ）と疑似局所最短距離（疑似ＬＭＤ）とを計算する演算手段１２０を提供する指示を実行する機能を有し、局所最短距離（ＬＭＤ）は、距離関数を前記単体的複体（Ｋ1，Ｋ2）のカルテシアン積に限定した場合の局所最小値を形成する点の対によって、および前記ＬＭＤを特徴づける正の実数ｄ（ａ，ｂ）によって、定義され、前記疑似局所最短距離はそれぞれ別個のオブジェクトに属する点の対に対応し、前記点の対は、一方のオブジェクトの他方のオブジェクトに対する相対位置が所定のしきい値未満のわずかな角度γmaxで回転した場合に局所最短距離（ＬＭＤ）を定義し、
前記システムは、グラフィカル・ユーザ・インターフェース、マウス、動き感知周辺装置、フォースフィードバック・インターフェース、タッチ式インターフェース、およびオーディオ・インターフェースを含むグループから選択される少なくとも１つの周辺装置１４０に接続されている、システム。
【数１】
0005424883.tif 000074
【数２】
0005424883.tif 000075
【請求項２】
機械的解決手段１３０に接続していることを特徴とする、請求項１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、数値的にシミュレートされた有限個のオブジェクト、すなわち仮想オブジェクト間の衝突を検出するとともに、これらオブジェクト間の接触、より一般的には近接についての幾何学的情報を構築し、視覚化する方法およびシステムに関する。
【背景技術】
【０００２】
米国特許第６８６２０２６号（特許文献１）は、すでに、所望により移動すると考えられるべき仮想オブジェクトを含むボックスを構成し、オブジェクト間の衝突を検出する方法を提案している。この先行技術による方法では、それぞれオブジェクトを含む２つのボックスに重複部分があるかどうかを検証し、適宜、各ボックスをより小さな２つのボックスに分割する。一方のオブジェクトの軸と一致する軸を有するボックスを用いて最適化が実行される。この方法では、オブジェクト間の距離は用いない。
【０００３】
さらに、非特許文献１より、三次元空間における境界を三角形分割法で表した３次元多面体オブジェクト間の局所最短距離を求める方法が公知である。しかし、この方法は、ある特定の用途について述べたものであり、比較的長い計算が必要なため、リアルタイムのシミュレーションには適さない。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第６８６２０２６号明細書
【非特許文献】
【０００５】
【非特許文献１】Ｄ．ジョンソン、およびＥ．コーエン（D. Johnson and E. Cohen）著、 「空間法線錐階層（Spatialized Normal Cone Hierarchies）」、３Ｄグラフィックスに関するＡＣＭシンポジウム２００１（2001 ACM Symposium on Interactive 3D Graphics）予稿、ノースカロライナ州リサーチ・トライアングル・パーク（Research Triangle Park, NC）、２００１年３月１９日−２０日、ｐ．１２９−１３４
【非特許文献２】Ｊ．Ｒ．ムンクレ（J.R. Munkres）著、「代数的位相幾何学の要素（Elements of Algebraic Topology）」、 アドバンスト・ブック・プログラム（Advanced Book Program）、パーソス・パブリッシング（Perseus Publishing）、マサチューセッツ州ケンブリッジ、１９８４年
【非特許文献３】Ｄ．Ｐ．バートセカス（D.P. Bertsekas）著、「凸分析と最適化（Convex Analysis and Optimization）」、アテナ・サイエンティフィック（Athena Scientific）マサチューセッツ州ベルモント、２００３年
【非特許文献４】Ｅ．ラーセン、Ｓ．ゴーツチョーク、Ｍ．リン、およびＤ．マノチャ（E. Larsen, S. Gottschalk, M. Lin, and D. Manocha）著、「スイープされた球体体積を伴う高速近接クエリー（Fast Proximity Queries with Swept Sphere Volumes）」、テクニカルレポートＴＲ９９−０１８、ノースカロライナ大学、コンピュータサイエンス学部、（Department of Computer Science, University of N. Carolina）、チャペルヒル
【非特許文献５】http://www.cs.unc.edu/~geom/SSV/
【非特許文献６】Ｃ．エリクソン（C. Ericson）著、「リアルタイム衝突検出（Real Time Collision Detection）」、エルゼビア、ＭＫプレス（Elsevier, MK Press）２００５年
【非特許文献７】ニーナ・アメンタ、スンギー・チョイ、およびラビ・コルリ（Nina Amenta, Sunghee Choi, and Ravi Kolluri）著、「パワークラスト（The Power Crust）」、第６回ソリッドモデリングおよびアプリケーションに関するＡＣＭシンポジウム（Sixth ACM Symposium on Solid Modeling and Applications）、２００１年、ｐ．２４９−２６０
【非特許文献８】ニーナ・アメンタ、スンギー・チョイ、およびラビ・コルリ（Nina Amenta, Sunghee Choi, and Ravi Kolluri）著、「パワークラスト、球体の和集合および中間軸トランスフォーム（The Power Crust, unions of balls, and the medial axis transform）」、コンピュータジオメトリ：理論と応用（Computation Geometry: Theory and Applications）、２００１年、１９（２−３）、ｐ．１２７−１５３、（表面再構築に関する特別号）(special issue on surface reconstruction)
【発明の概要】
【０００６】
そこで、本発明は、上記問題点を改善し、数値的にシミュレートされた有限個のオブジェクト間の衝突の検出、またはそれらオブジェクト間の近接もしくは接触についての幾何学的情報の構築、処理速度の最適化、および、これら仮想オブジェクトの移動や回転に対応した非常に強力なソリューションの提供を実現することにより、とりわけ、その性質上予想が困難なユーザとのインタラクションによる図形レンダリングや視覚レンダリングの安定性を損なわないようにすることを目的とする。
【課題を解決するための手段】
【０００７】
この目的を達成するため、本発明は、少なくとも１つの数値的にシミュレートされた第１多面体オブジェクトと、少なくとも１つの数値的にシミュレートされた第２多面体オブジェクトとの衝突を検出するとともに、前記第１、第２オブジェクト間の近接および接触についての幾何学的情報を構築する方法であって、
前記数値的にシミュレートされた第１、第２多面体オブジェクトは、Ｒnにおける単体的複体の形式で表され（ただし、Ｒnは、実数体をそれ自体ｎ倍（ｎは２または３）して得られるカルテシアン積を示す）、
各単体的複体について、頂点の座標を固定座標系で示す前処理ステップを実行し、
前記前処理ステップは、少なくとも、前記各単体的複体の各フェースについて、前記各フェースに関連づけられた強い意味での複数の法線に対応する多面錐の幾何学的表記を計算するステップと、前記フェースが属する接触クラスのラベルを決定するステップと、前記各単体的複体について、前記単体的複体のフェースの位置と、前記強い意味で関連づけられた法線の集合との両方から、前記単体的複体で表された前記オブジェクトの包含体積の木（ツリー）を求めるステップとを含み、
前記方法はさらに、前記前処理ステップ後に得た情報から、局所最短距離と疑似局所最短距離とを計算するステップを含み、前記疑似局所最短距離はそれぞれ別個のオブジェクトに属する点の対に対応し、一方のオブジェクトの他方のオブジェクトに対する相対位置が所定のしきい値未満のわずかな角度で回転した場合に局所最短距離を定めることを特徴とする。
【０００８】
上記方法は、数値的にシミュレートされた剛性または変形可能な多面体オブジェクトに適用できる。
【０００９】
前処理ステップと、局所最短距離（ＬＭＤ）および疑似局所最短距離（疑似ＬＭＤ）を計算するステップは、リアルタイムで実行することができる。
【００１０】
また、本発明は、少なくとも１つの数値的にシミュレートされた第１多面体オブジェクトと、少なくとも１つの数値的にシミュレートされた第２多面体オブジェクトとの衝突を検出するとともに、前記第１、第２オブジェクト間の近接および接触についての幾何学的情報を構築するシステムであって、
前記システムは、前記数値的にシミュレートされた第１、第２多面体オブジェクト１０、２０を、Ｒnにおける単体的複体の形式で表わす（ただし、Ｒnは、実数体をそれ自体ｎ倍（ｎは２または３）して得られるカルテシアン積を示す）表示手段と、
各単体的複体について、頂点の座標を固定座標系で示す前処理手段とを備え、
前記前処理手段は、少なくとも、前記各単体的複体の各フェースについて、前記各フェースに関連づけられた強い意味での複数の法線に対応する多面錐の幾何学的表記を計算する手段と、前記フェースが属する接触クラスのラベルを決定する手段と、各単体的複体について、前記単体的複体のフェースの位置と、前記強い意味で関連づけられた法線の集合との両方から、前記単体的複体で表された前記オブジェクトの包含体積の木を求める手段と、を備え、
前記システムはさらに、前記前処理手段に関連づけられ、局所最短距離と疑似局所最短距離とを計算する演算手段を備え、前記疑似局所最短距離はそれぞれ別個のオブジェクトに属する点の対に対応し、一方のオブジェクトの他方のオブジェクトに対する相対位置が所定のしきい値未満のわずかな角度で回転した場合に局所最短距離を定めることを特徴とするシステム、に関する。
【００１１】
このシステムは、機械的解決手段（solveur mecanique）に接続することができる。
【００１２】
このシステムと機械的解決手段との組み合わせは、周辺装置、特に、グラフィカル・ユーザ・インターフェース、マウス、動き感知周辺装置、フォースフィードバック・インターフェース、タッチ式インターフェース、およびオーディオ・インターフェースを含む少なくとも１つの周辺装置に接続することができる。
【発明の効果】
【００１３】
特に、本発明によると、（スプリアスな変動がなく）機械的挙動を安定的にシミュレートできるとともに、その場の状況における「感覚」を忠実に再現できる手堅い触覚レンダリングを選択することができる。
【００１４】
このソリューションは、オブジェクトの移動や回転に合わせて調整しながら接触エリアを特定するため、次に何が起こるかを予想することができる。このように接触問題を処理することにより、事象ベースの手法に頼らずに、安定したソリューションを生み出すことが可能になる。事象ベースの場合は、接触時間を計算したり、数値積分器の時間進行を接触時間の日時に応じて適合させる必要がある。
【００１５】
ここで提案されたソリューションの利点は、リアルタイムで移動する仮想オブジェクト用に安定性の高いソリューションを提供するだけでなく、シミュレーションが難しい状況も解消できることである。シミュレーションが難しい状況とは、例えば、オブジェクト同士が衝突したり相互に透過したりすることのない適合接触個所を検索する（例えば、平面オブジェクトの上に別の平面オブジェクトを置いて、２つのオブジェクトの面接触を検出する）、接触および／または妨害エリアを避けるような、構成要素の追加／除外経路を検索する、ある位置の近傍でわずかな角度変化や移動があった場合に、安定したソリューションによって、オブジェクト、特に凹型オブジェクトに対し接触エリアを提示する、といった状況である。
【００１６】
本発明によると、点接触の検出に限らず、２つのオブジェクト間の線接触または面接触といった、位相が異なる場合の適合接触個所も検出できる。また、交差や、条件によっては相互透過の深さも検出できる。
【図面の簡単な説明】
【００１７】
本発明のその他の特徴および利点は、以下に例示した特定の実施形態の説明により明らかになる。以下、添付図面を参照して説明する。
【図１】本発明の方法の１つの側面を説明する図であり、２次元平面において、２つの仮想オブジェクト間のそれぞれ異なる複数の局所最短距離（ＬＭＤ）を選択的に抽出する、または排除する例を示す。
【図２】本発明の方法のステップにおいて用いることのできる向き付けられた木の例を示す。
【図３】本発明の方法により視覚化することのできる、数値的にシミュレートされた立方体の第１オブジェクトと平面の第２オブジェクトとの相対位置を示す。
【図４】本発明の方法により視覚化することのできる、数値的にシミュレートされた立方体の第１オブジェクトと平面の第２オブジェクトとの相対位置を示す。
【図５】本発明の方法により視覚化することのできる、数値的にシミュレートされた立方体の第１オブジェクトと平面の第２オブジェクトとの相対位置を示す。
【図６】本発明の方法により視覚化することのできる、数値的にシミュレートされた立方体の第１オブジェクトと平面の第２オブジェクトとの相対位置を示す。
【図７】本発明の方法により視覚化することのできる、数値的にシミュレートされた立方体の第１オブジェクトと平面の第２オブジェクトとの相対位置を示す。
【図８】本発明のシステムの例を示すブロック図である。
【発明を実施するための形態】
【００１８】
本発明の方法およびシステムを詳細に説明する前に、いくつかの有用な定義を以下に示す。すなわち、標準的な定義：科学技術の世界で広く受け入れられている一般的な概念を対象とし、その統一用語が科学技術文献において定着している定義、および、より特殊な定義：比較的一般的な概念ではあるが、人によって用語にばらつきがある定義、を示す。また、本発明独自の定義、本発明の方法の適用分野独自の定義についても若干示す。
【００１９】
１．標準的な定義
以下において、Ｒnは、実数体をそれ自体ｎ倍（ｎは狭義の正の整数）して得られるカルテシアン積を示す。Ｒnで表されるこの空間は、本質的にユークリッド構造を有すると考えられる。Ｒnの単位球面はＳn-1で表される。
【００２０】
相対内部および相対エッジ
位相幾何学的概念である。ＡをＲnの部分とする。Ａの相対内部とは、Ａによって生じるＲnのアフィン部分空間の自然位相（すなわち、ユークリッド構造から導かれる位相：topologie naturelle）におけるＡの内部である。Ａの相対内部はＲｉ（Ａ）で表される。
【００２１】
同様に、Ａの相対エッジ（または相対境界）は、Ａによって生じるＲnのアフィン部分空間の自然位相におけるＡのエッジである。
【００２２】
単体
幾何学的概念である。ｄを正またはゼロの整数とする。Ｒnの単体（または、ｄ単体もしくはｄ次元単体）は、Ｒnのアフィン的に独立した（ｄ＋１）個の点からなる凸包と定義される。
【００２３】
ただし、ｄ単体の位相次元はｄに等しい。
【００２４】
単体のフェース
ＳをＲnのアフィン的に独立した点｛ｐ０， …, ｐｄ｝の集合からなる凸包と定義されたｄ単体とする。｛ｐ０， …, ｐｄ｝を構成する部分集合の凸包と定義される複数の単体を、単体Ｓのフェースという。
【００２５】
単体Ｓは、Ｓの特定のフェースである。単体Ｓそれ自体ではない単体Ｓの複数のフェースを、Ｓに固有のフェースという。これらフェースの和集合を、Ｓの単体エッジ（または単体境界）といい、ＢｄＳと表す。Ｓの単体内部は、ＳにおけるＢｄＳの補集合と定義される。
【００２６】
【数１】
0005424883.tif 000002
【００２７】
ある単体の単体内部および単体エッジは、それぞれ、その単体の相対内部および相対エッジと一致する。
【００２８】
単体的複体
Ｒnにおける単体的複体Ｋは、以下の２つの条件を満たすＲnの単体の集合である。
・Ｋの要素であるフェースはいずれもＫ内にある。
・Ｋの単体のうちいずれの２つをとっても、その交差部分は各単体のフェースである。
【００２９】
単体的複体の要素を、その複体のフェースという。単体的複体の次元は、そのフェースの最大次元と定義される。
【００３０】
単体的複体Ｋのフェースの和集合を、複体体Ｋといい、｜Ｋ｜と表す。
【００３１】
単体的複体のフェースの相対内部が、その複体体のパーティションを形成していることを示すことは容易である。
【００３２】
この点については、非特許文献２の７ページを参照のこと。
【００３３】
ポリトープ
代数的位相幾何学に由来する定義である。ＫをＲnにおける単体的複体とする。Ｋの各フェースσが自身の自然位相（すなわち、Ｒnの自然位相によりσ上に誘導された位相）を有していると仮定すると、Ｋ体は以下のとおり定義された位相を持つことができる。すなわち、｜Ｋ｜の部分集合Ａは、Ｋのいずれのフェースσについても、Ａ∩σがσにおいて閉じているとき、かつそのときに限り、｜Ｋ｜において閉じているとみなされる。このように定義した位相空間を常に｜Ｋ｜と表し、Ｋの基となる位相空間、またはＫのポリトープという。
【００３４】
多面体
代数的位相幾何学に由来する定義である。有限の単体的複体のポリトープである位相空間を多面体という。
【００３５】
錐
凸分析に由来する定義である。狭義の正の実数を乗算することにより得られる一定の実数体上のベクトル空間の任意の部分Ｃを錐という。錐が原点を含む場合、その錐は先が尖っているという。
【００３６】
注）Ｒnの錐は、必ずしも回転体、凸体、または閉体とは限らない。
【００３７】
極錐（Cone polaire）
凸分析に由来する定義である。ＡはＲnの部分とする。Ａ*で表され、以下の数式で定義される組み合わせをＡの極錐、または単にＡの極という。
【００３８】
【数２】
0005424883.tif 000003
【００３９】
これは閉半空間の交差部分であるから凸錐である。なお、Ａの極、Ａの凸包の極、およびＡにより生成される凸錐の極は一致する。
【００４０】
接錐（Cone tangent）
凸分析に由来する定義である。ＡをＲnの部分、ｘをＡの要素とする。Ｒnのベクトルｙは、以下の２つの条件のうち１つを満たす場合、点ｘにおいてＡの接線方向にあるという。
・ｙはゼロベクトルである。
・ｙはゼロではなく、以下の（数４）(数５)で表されるような、Ａ＼｛ｘ｝において値をとる一連の（数３）が存在する。
【００４１】
【数３】
0005424883.tif 000004
【００４２】
【数４】
0005424883.tif 000005
【００４３】
【数５】
0005424883.tif 000006
【００４４】
ｘにおいてＡの接線方向にあるベクトルの集合を、ｘにおけるＡの接錐といい、ＴA（ｘ）で表す。
【００４５】
これは閉錐であり、必ずしも凸ではない。
【００４６】
接錐の詳細、および法線錐の厳密な定義については、非特許文献３を参照のこと。
【００４７】
膨張 （Dilatation）
数理形態学分野の概念である。Ｅを距離ｄの距離空間とする。半径εの膨張（ε膨張ともいう）演算は、Ｅのいずれの部分Ａとも関連する。Ｅの膨張部分（ε膨張したＡという）は、Ａのある要素を中心とする半径εの球体の和集合からなる。
【００４８】
パーティション
集合理論の用語である。ある集合をＥとする。Ｅの複数の部分からなる集合Ｐは、以下の３つの条件を満たす場合、Ｅのパーティションである。
・Ｐの要素がＥの空でない部分である。
・Ｐの要素それぞれ２つずつが互いに素である。
・Ｐの要素の和集合がＥに等しい。
【００４９】
重複部分（Recouvrement）
集合理論の用語である。ある集合をＥとする。Ｅのある部分Ａの重複部分とは、Ｅの複数の部分の和集合がＡを含むような、これら複数の部分の集合体（collection）である。
【００５０】
集合ＥのパーティションはいずれもＥの重複部分である。
【００５１】
階層
集合理論の用語である。Ｅを有限集合とする。Ｅについての階層は、以下の３つの条件を満たすＥの複数の部分からなる集合Ｈである。
・ＨがＥの複数の単集合を含む。
・ＨがＥを含む。
・ＡとＢがＨの２つの要素であり、Ｅの互いに素な部分ではない場合、ＡがＢを含む、またはＢがＡを含む。
【００５２】
向き付けられた木（Arbre oriente）
グラフ理論の概念である。向き付けられた木とは、いずれの頂点の入次数（この頂点を端点とするエッジの数）も１以下である、閉路のない向き付けられた連結グラフである。
【００５３】
向き付けられた木には１つだけ入次数が０の頂点があり、それ以外の頂点はすべて入次数が１である。この唯一の頂点のことを、木の根という。
【００５４】
図２は、向き付けられた木の例を示している（この木のノード（節点）にはラベルがふってある）。
【００５５】
向き付けられた木の経路の最大長を、木の深さという。
【００５６】
各ノードには、根を始点とし、そのノードに到る唯一の経路が存在する。この経路の長さを、その木におけるノードの深さという。したがって、根の深さは０である。図２の例において、ノード８は深さ２、ノード４は深さ３である。
【００５７】
出次数がゼロのノードを、その木の葉という。図２の例において、この木の葉はノード３、４、５、７、８、および９である。
【００５８】
ａを向き付けられた木のノードとする。ａを始点とするエッジを終端するノードを、ノードａの子という。したがって、葉は子を持たないノードのことである。
【００５９】
向き付けられた木において、１つのノードの持つ子の最大数のことを、その木のアリティ（引数の個数）という。
【００６０】
注）衝突検出の分野で多く用いられる木は、低アリティの木、例えば、２分木（アリティ２）、３分木（アリティ３）、４分木（アリティ４）である。
【００６１】
２．特殊な定義
多面体オブジェクト
多面体オブジェクトとは、先に定義した意味において、可能な幾何学的表現の１つが「多面体」である物体である。これは、２次元の物理的な基準空間でも３次元の空間でもあてはまり、その場合の多面体は、それぞれＲ2またはＲ3の多面体である。
【００６２】
単体のフェースに直交するユニタリベクトル
ＳをＲnのｄ単体とする。ただし、ｄ＞０、σは（ｄ−１）次元のＳのフェース、ｖはσに対向しているＳの頂点である。ａを、σによって生成されるＲnのアフィン部分空間上のｖの正射影とする。点ａとｖは互いに離れている。このユニタリベクトル（数６）を単体Ｓのフェースσに直交するユニタリベクトルといい、ｕs（σ）で表す。
【００６３】
【数６】
0005424883.tif 000007
【００６４】
ユニタリ球面上の錐の跡
ＣをＲnの錐とする。ユニタリ球面上のＣの跡は、ＣとＳn-1との交差部分である。Ｃが原点を含む場合、ユニタリ球面上のＣの跡によって生成される先の尖った錐は、Ｃに等しい。
【００６５】
強い意味での法線ベクトル
ＡをＲnの部分とする。ベクトルＲnは、ＴA（ｘ）*の極に属する場合、点ｘにおいて強い意味でＡに垂直であるという。したがって、点ｘにおいて強い意味でＡに垂直であるベクトルの集合は凸錐ＴA（ｘ）*であり、これを点ｘにおいて強い意味でＡに垂直な錐といい、ｎA（ｘ）と表す。
【００６６】
ＢをＡの部分とする。Ｒnのベクトルｙは、ｙがＴA（ｘ）*に属するようなＢの点ｘが存在する場合、Ｂに関連づけられたＡに強い意味で垂直であるという。Ｂに関連づけられたＡに強い意味で垂直なベクトルの集合をｎA（Ｂ）と表す。
【００６７】
よって、以下が成立する。
【００６８】
【数７】
0005424883.tif 000008
【００６９】
相互透過（または干渉）
幾何学的概念である。ＡおよびＢをＲnの２つのコンパクト集合とする。ＡおよびＢは、その内部が互いに素でない場合、相互透過（または干渉）するという。
【００７０】
点接触
機械的接触現象のモデリング分野に由来する用語である。ここでは、点接触の幾何学的概念を数学的に公式化する際の定義について述べる。
【００７１】
ＡおよびＢをＲnの２つのコンパクト集合とする。ＡとＢとの点接触は、ＡとＢとの共通部分の孤立点と定義される。
【００７２】
適合接触（Contact conformant）
機械的接触現象のモデリング分野に由来する用語である。ここでは、適合接触の幾何学的概念を数学的に公式化する際の定義について述べる。
【００７３】
ＡおよびＢをＲnの２つのコンパクト集合とする。ＡとＢとの適合接触は、ＡとＢとの共通部分の、複数の弧で連結された構成要素と定義される。ただし、内部は空であり、点にはならない。
【００７４】
局所最短距離
Ｅを距離ｄを有する距離空間とする。ＡおよびＢをＥの２つの部分とする。ＡとＢとの局所最短距離（以下ＬＭＤと略す）は、それ自体Ｅのカルテシアン積によって定義される関数ｄを、ＡとＢとのカルテシアン積に限定した場合の局所最小値と定義される。このような局所最小値を形成する点の対（ａ，ｂ）∈Ａ×Ｂを、当該局所最短距離の台（support）といい、一方、正の実数ｄ（ａ，ｂ）をＬＭＤ値という。
【００７５】
隙間（Interstice）
機械的接触現象のモデリング分野に由来する用語である。ここでは、隙間の幾何学的概念を数学的に公式化する際の定義について述べるが、一般化して言うと、隙間は、必ずしも凸でない体である。
【００７６】
ＡおよびＢをＲnの２つのコンパクト集合とする。ＡとＢとの間の隙間は、定義上、ＡとＢの間のＬＭＤの値である。
【００７７】
向き付けられた部分木または枝
グラフ理論に由来する用語である。それ自体向き付けられた木である、向き付けられた木Ｔの部分グラフのことを、Ｔの向き付けられた部分木またはＴの枝という。
【００７８】
包含体積（Volume englobant）
衝突検出の分野に由来する概念である。ここでは、数学的公式化について述べる。
【００７９】
包含体積は、Ｒnの部分の重複部分の要素である。衝突検出の分野では一般的ではないが、この包含体積は、Ｓn-1またはＲn×Ｓn-1の部分の重複部分の要素を指定するのにも用いられる。
【００８０】
包含体積階層
衝突検出の分野に由来する概念である。ＡをＥの部分とする。ただし、ＥはＲn、Ｓn-1、またはＲn×Ｓn-1を指す。「Ａの包含体積の階層」という表現は、包含体積とよばれるＥの複数の部分からなるいずれかの有限の群Ｈ＝（Ｖ1，…，ＶN）を指している。これは、向き付けられた木Ｔ、または包含体積の木と関連づけられており、そのノードはＨの要素と１対１の関係にあり、かつ以下の特性を満たしている。すなわち、Ｔと同じ根を持つＴの向き付けられた部分木Ｔ’のいずれについても、Ｔ’の葉に関連づけられたＨの要素がＡの重複部分を形成する。
【００８１】
このように定義した結果、木Ｔの葉に関連づけられた包含体積は、Ａの重複部分を形成する。同様に、Ｔの根に関連づけられた包含体積は、それだけでＡと重複する。
【００８２】
Ｅの部分Ａの包含体積の階層を簡単に構築するには、集合論の観点では、まず、Ａのパーティションについて階層Ｈ'を構築することから始める。この一般的な方法では、Ａから連続的に全体を細分割していき、Ａのパーティションから連続的に集約していく。次に、Ｈ'の各要素の再結合体にＨの要素を重複させることによって、Ａの包含体積の階層を、Ｈ'から構築することができる。これは、Ｈ'の階層構造に直接由来しているＨに関連づけられた、向き付けられた木構造である。
【００８３】
次に、本発明独自の３つの概念について紹介する。
【００８４】
強い意味で垂直な、関連づけられたベクトルを備えたＲnの部分の部分
Ｒnの部分をＡ、Ａの部分をＢとすると、ＢとｎA（Ｂ）のカルテシアン積によって形成されるＲn×Ｒnの部分が存在する場合、Ｂは、Ａに対する（Ｂに対しては言うまでもない）強い意味での関連づけられた法線を有するといえる。ただし、ｎA（Ｂ）が空になるとすぐに、この集合も空になる。
【００８５】
接触クラス
Ｋを単体的複体とする。Ｋの複数のフェースは、それらの位相次元によって０から７までの接触クラスに分類される。この位相次元とは、自身の相対内部と関連づけられた、強い意味でＫ体に垂直なベクトルの集合からなる単位球面との共通部分の位相次元であり、場合によっては、Ｋにおける星（スター）とＫ体の（Ｒnにおける）境界との交差部分の幾何学的形状である。
【００８６】
下記の表１は、ｎ＝３の場合を示す。
【００８７】
【表１】
0005424883.tif 000009
【００８８】
ｎ＝２の場合については、以下の表２を用いる。
【００８９】
【表２】
0005424883.tif 000010
【００９０】
空集合の位相次元は、１と決まっている。
【００９１】
疑似ＬＭＤ（回転に合わせて調整）
干渉し合わない２つの単体的複体の膨張同士の局所最短距離という概念を展開したものである。疑似ＬＭＤを公式化するのに必要な要素について述べた後、その定義について以下に説明する。
【００９２】
次に、本発明の方法について詳細に説明する。
【００９３】
本発明の方法は、階層的に見て、時間的に独立した２つのステップに区別することができる。これら２つのステップはさらに下位ステップに分かれる。上記２つのステップとは以下のステップである。
１．事前計算ステップ
このステップは、厳密な意味でのシミュレーションの準備中に実行される。このステップでは、第２ステップで実行される処理演算の効率化（つまり迅速化）に必要なデータを計算する。
２．ＬＭＤ計算ステップ
このステップでは、事前計算した情報を用いて、本発明の方法に必要な計算を加速するとともに、リアルタイム・シミュレーションに適合した性能レベルを実現する。
【００９４】
本発明の方法の理解のため、まず、２つの単体的複体間の局所最短距離という概念と、ある単体的複体の点または部分に（強い意味で）垂直な関連づけられたベクトルの集合という概念とのつながりを立証する様々な成果について以下に述べる。続いて、厳密な意味での本発明の方法について説明する。
【００９５】
本発明では、以下の重要な成果を考慮に入れている。
【００９６】
Ｋ1およびＫ2をＲnにおける２つの単体的複体とする。ｘ1およびｘ2をそれぞれ、Ｋ1体およびＫ2体の２つの点とする。この１対の点（ｘ1、ｘ2）は、以下の２つの条件が満たされるとき、かつそのときに限り、Ｋ1体とＫ2体とのＬＭＤの台である。
【００９７】
【数８】
0005424883.tif 000011
【００９８】
【数９】
0005424883.tif 000012
【００９９】
ＫをＲnにおける単体的複体とする。ｘをＫ体の点とする。σｘを相対内部がｘを含むＫ唯一のフェースとする。
【０１００】
・点ｘにおけるＫ体の接錐は、（数１０）により生成される錐に等しい。
【０１０１】
【数１０】
0005424883.tif 000013
【０１０２】
・点ｘにおけるＫ体の接錐は、ｘがＲnにおける｜Ｋ｜の内部に属するとすぐに、Ｒnに等しくなる。
【０１０３】
【数１１】
0005424883.tif 000014
【０１０４】
・したがって、ｘおよびｙが、Ｋの同じフェースσの相対内部に含まれるＫ体の２つの点であるなら、点ｘおよびｙにおけるＫ体の接錐は等しい。つまり、
【０１０５】
【数１２】
0005424883.tif 000015
【０１０６】
・（数１３）は多面錐である。
【０１０７】
【数１３】
0005424883.tif 000016
【０１０８】
以上の成果より以下の帰結が導かれる。
【０１０９】
さらに、Ｋ1体およびＫ2体は互いに素であると仮定する。その場合、以下の２つの条件を満たすとき、かつ満たすときに限り、１対の点（ｘ1、ｘ2）は、Ｋ1体とＫ2体とのＬＭＤの台である。
【０１１０】
・（数１４）は（数１５）に属する。
・（数１６）は（数１７）に属する。
【０１１１】
【数１４】
0005424883.tif 000017
【０１１２】
【数１５】
0005424883.tif 000018
【０１１３】
【数１６】
0005424883.tif 000019
【０１１４】
【数１７】
0005424883.tif 000020
【０１１５】
以上により、Ｋ1体とＫ2体との局所最短距離の台である１対の点（ｘ1、ｘ2）は、（数１５）および（数１７）が｛０｝にならないような点であることが、特に導かれる。
【０１１６】
Ｋ1およびＫ2を、互いに素な体を有するＲnにおける２つの単体的複体とする。Ａ1およびＡ2をそれぞれ、Ｋ1体およびＫ2体の部分とする。Ａ1×Ａ2において、Ｋ1体とＫ2体とのＬＭＤの台である２点（ｘ1、ｘ2）の対が少なくとも１つ存在する場合、以下の３つの条件が満たされる。すなわち、
１．Ｐ1（Ａ1，Ａ2）：（数１８）と（数１９）との共通部分は｛０｝にならない。
２．Ｐ2（Ａ1，Ａ2）：（数１８）と、Ａ2−Ａ1により生成される錐との共通部分は｛０｝にならない。
３．Ｐ3（Ａ1，Ａ2）：（数１９）と、Ａ2−Ａ1により生成される錐との共通部分は｛０｝にならない。
【０１１７】
【数１８】
0005424883.tif 000021
【０１１８】
【数１９】
0005424883.tif 000022
【０１１９】
本発明の方法の主要な側面について説明する。
【０１２０】
本発明の方法は、剛性の多面体オブジェクトおよび変形可能な多面体オブジェクトに適用可能である。ただし、変形というのは、基礎となる単体的複体の頂点の移動に対応する。
【０１２１】
本発明は、３次元における境界を三角形分割法で表わした固体の多面体オブジェクト間の局所最短距離を計算するのに用いられる、非特許文献１で提案された方法を改良、発展させたものである。
【０１２２】
本発明は、確立した凸分析理論を用いて、このような多面体の境界のある点における（強い意味での）関連づけられた法線の定義を訂正、明確化するものである。
【０１２３】
本発明は、非特許文献１で提案された方法を、２次元および３次元における（必要に応じ、２次元および３次元に膨張した）単体的複体の一般的な状況にまで発展させたものであり、特に以下のような状況を含む。
・面状の多面体オブジェクト（平板、殻、パネルなど）
・線状の多面体オブジェクト（ケーブル、光線など）
・混合位相の多面体オブジェクト（骨格など）
・複数の点の雲状塊（球体の和集合など）
【０１２４】
膨張を導入することにより、多面体複体の概念を構築する幾何学モデルの表現の可能性が広がる。したがって、純粋に面状の多面体複体を膨張すると、殻の半値厚を表し、純粋に線状の複体を膨張すると、ケーブルの平均半径を表すことなどができる。
【０１２５】
本発明を一般化して中心軸（axe median）による表現に当てはめることが可能である。
【０１２６】
以上述べたような重要な成果により、互いに素な体を有する２つの単体的複体Ｋ1とＫ2の体同士の局所最短距離の計算ベースの検索の対象を、（数２０）や（数２１）が｛０｝にならないようなＫ1体およびＫ2体の２点（ｘ1，ｘ2）の対にのみ限定することができる。しかし、この手法では、テスト対象の点の対を無数に表すことができるため、このような点の対の候補に基づいて、２つの単体的複体間のＬＭＤを計算する方法を採用することはできない。
【０１２７】
【数２０】
0005424883.tif 000023
【０１２８】
【数２１】
0005424883.tif 000024
【０１２９】
そこで、上述した最後の成果は、Ｋ1体とＫ2体の局所最短距離の特定に用いることのできる必要条件を提供するため、本方法の作用にとって重要な追加要素となる。
【０１３０】
Ｋ1体およびＫ2体には、有限のパーティションＰ1およびＰ2がそれぞれ存在すると仮定する。Ｋ1体とＫ2体とのＬＭＤの台となる点の対として可能な位置を制限する計算方法では、各対（Ａ1，Ａ2）∈Ｐ1×Ｐ2について上述した条件１〜３に対応する述語Ｐ1、Ｐ2、Ｐ3を評価する。テスト対象の対の数は、Ｐ1およびＰ2の基数の積に等しい。
【０１３１】
ここで、複体Ｋ1およびＫ2が有限（すなわち、有限個のフェースを有する）と仮定する。すると、パーティションＰ1（Ｐ2についてもそれぞれ）について可能な選択肢は、Ｋ1（Ｋ2についてもそれぞれ）のフェースの単体内部の集合である。よって、テスト対象の対は、（Ｉｎｔσ1，Ｉｎｔσ2）となる（ただし、σ1はＫ1に属する、σ2はＫ2に属する）。さらに、（（数２２）または（数２２））が｛０｝になり次第、述語Ｐ1（Ｉｎｔσ1，Ｉｎｔσ2）は偽になるため、実行すべきテストは、（（数２２）および（数２２））が｛０｝にならないような対（Ｉｎｔσ1，Ｉｎｔσ2）に限定されることになる。このようなフェースの対に関する処理を加速するという観点から、本発明の方法では、以下に述べる包含体積の階層を用いる。
【０１３２】
【数２２】
0005424883.tif 000025
【０１３３】
まず、一対のフェース（σ1，σ2）∈Ｋ1×Ｋ2について考える。以下の２つの条件が満たされるとき、かつそのときに限り、一対の点（ｘ1，ｘ2）∈（Ｉｎｔσ1，Ｉｎｔσ2）が、｜Ｋ1｜と｜Ｋ2｜とのＬＭＤの台であると示すことができる。すなわち、（ｘ1，ｘ2）はＩｎｔσ1とＩｎｔσ2とのＬＭＤの台である。
【０１３４】
【数２３】
0005424883.tif 000026
【０１３５】
【数２４】
0005424883.tif 000027
【０１３６】
以上の成果をふまえて、ベクトルｘ2−ｘ1が（数２５）に属するとき、かつそのときに限り、一対の点（ｘ1，ｘ2）∈Ｉｎｔσ1×Ｉｎｔσ2は、σ1とσ2とのＬＭＤの台であることがわかる。したがって、このような点の対は、Ａｆｆσ1，Ａｆｆσ2とのＬＭＤでもある。さらに厳密には、（ｘ1、ｘ2）がＩｎｔσ1×Ｉｎｔσ2に属し、ｘ2−ｘ1が（数２５）に属するとき、かつそのときに限り、一対の点（ｘ1，ｘ2）∈Ａｆｆσ1×Ａｆｆσ2はＩｎｔσ1とＩｎｔσ2とのＬＭＤである。
【０１３７】
【数２５】
0005424883.tif 000028
【０１３８】
上記２段落において示した成果により、｜Ｋ1｜と｜Ｋ2｜とのＬＭＤである点の対（ｘ1，ｘ2）∈Ｉｎｔσ1×Ｉｎｔσ2の計算のために実際的な方法を構築することができる。すなわち、
・ｘ2−ｘ1が（数２６）に属するような点（ｘ1，ｘ2）∈Ａｆｆσ1×Ａｆｆσ2の位置を計算する。
・この位置とＩｎｔσ1×Ｉｎｔσ2との交差部分を計算する。
【０１３９】
【数２６】
0005424883.tif 000029
【０１４０】
このようにして求めた集合の要素（ｘ1、ｘ2）のうち、（数２７）および（数２８）を満たす要素のみ保持しておく。
【０１４１】
【数２７】
0005424883.tif 000030
【０１４２】
【数２８】
0005424883.tif 000031
【０１４３】
よって、｜Ｋ1｜と｜Ｋ2｜とのＬＭＤである点の対（ｘ1，ｘ2）∈Ｉｎｔσ1×Ｉｎｔσ2が正確に求められる。
【０１４４】
なお、上記方法で連続的に計算した点の対の集合は無限であってもよい。その場合は、膨張した多面体オブジェクト間の適合接触に対応する。Ｒ3およびＲ2（これらは多面体の集合である）についても、このような点の対の集合を簡単な幾何学的表記で表すことができるが、最終的に求められたＬＭＤの数が無限であるという特徴により、多面立体間の接触という現象のシミュレーションを目的とした数値法においては、これら無限のＬＭＤそれぞれを、隙間形式で「明示的に」考慮することができなくなる。しかしながら、オブジェクト同士の非相互透過という片側拘束を必ず遵守するために、これらＬＭＤ各々を考慮に入れる必要はないということを、簡単な凸分析論証を用いて示すことは可能である。なぜなら、本発明の方法においては、幾何学的な観点から、Ａｆｆσ1とＡｆｆσ2とが平行な場合にしか対応していないこのような状況を無視しているからである。
【０１４５】
以下の表３および４は、Ｒ3およびＲ2について、Ｉｎｔσ1とＩｎｔσ2とのＬＭＤの可能な数を示している。
【０１４６】
【表３】
0005424883.tif 000032
【０１４７】
【表４】
0005424883.tif 000033
【０１４８】
上記２つの表の各ケースの処理に関連した実際の計算について、以下に詳細に説明する。その前に、必須事項について述べておく。
【０１４９】
台集合がＩｎｔσ1×Ｉｎｔσ2である｜Ｋ1｜と｜Ｋ2｜とのＬＭＤの数がそれでもなお有限集合である特殊な場合において、接触個所において乾燥摩擦のない剛性の固体同士の接触点の集合を構築するような状況では、これらＬＭＤを事実上無視することができる。これらＬＭＤを削除することにより、剛性の固体同士の相互透過を生じかねないエラーを発生させずに、使用する接触点の数を減らすことができる（よって、接触処理をおこなう数値的解決手段で用いられる数値的手法の計算回数が減る）。実際、問題となる特別なケースとは、膨張された多面固体同士の適合接触の相対内部を通過するＬＭＤに対応している。したがって、このようにＬＭＤを削除することは、膨張された多面固体同士の適合接触の凸包の相対エッジと交差するか、あるいはこれら固体同士の点接触を通過するＬＭＤだけを保持することに対応する。図１は、最終的に２次元で保持される場合の典型例を示している。
【０１５０】
２つのオブジェクトの表示２１０、２２０の間には、４つのＬＭＤ２３１〜２３４がある。この例において、ＬＭＤ（太い点線）２３１、２３２、２３４は保持され、無用なＬＭＤ（細い点線）２３２は排除されている。
【０１５１】
接触にかかわる旋回（evolution）の問題を解消するアルゴリズムは、以下の２つに大別できる。すなわち、事象ベースアルゴリズム（分離と接触との遷移の瞬間を正確に計算する）と、時間発展アルゴリズム（前もって定めた積算時間ステップ（pas de temps d’integration）を用いる）である。今のところ、無限の集積によって得られる大きな接触数（公知のゼノン効果）についてリアルタイムで実行できるのは時間発展アルゴリズムだけである（ゼノン効果というのは、重力を受ける剛性の球体が、厳密に弾性率０〜１を有する平面上をはねる場合のように、有限の時間内に遷移が無限に起こる現象に対応するものである）。
【０１５２】
時間発展アルゴリズムでは、対象となる接触点だけが、平面上に置かれ重力を受けている単純な立方体とその平面とのＬＭＤに由来している場合に、その立方体によって表現される多面体オブジェクトの安定化が困難であることは明白である。唯一立方体の安定化が可能なケースとは、立方体と平面との間に厳密に２つ以上のＬＭＤが同時に存在しているケースに対応する。つまり、立方体のフェースと平面とが平行であるケースである。このような場合、立方体と平面との間に無限のＬＭＤが存在する（立方体におけるＬＭＤの台集合は、その立方体の1つのフェース全体に相当する）。上記必須事項によると、接触点の有限集合を求めるには、平面上の立方体の四隅に対応する４つのＬＭＤのみを保持しておくだけで十分である。しかし、平行な場合というのは、マシンコードで表された実数間の同等性の述語を正確に（または、十分にうまく管理された状態で）評価することを意味するため、数値化するのが難しい。それに止まらず、平面上で立方体のフェースが安定化すると、その立方体のフェースがいずれも平面と平行でない状態を、シミュレーションの間、安定して経ることを示さざるを得なくなる。ただし、わずかな回転があれば、（時間ステップ中に）そのような状態を経ることができるであろう。この場合、立方体のフェースは平面に対し「ほぼ平行」であり、必要な４つのＬＭＤ（おそらく時間的に完全に分離）を存在させるには、わずかな回転で十分である。これは、本発明が疑似ＬＭＤという概念を導入しているからであり、あるオブジェクトの他のオブジェクトに対する相対位置がわずかな角度で回転する場合、この疑似ＬＭＤは、ＬＭＤの台となる一対の点に対応する。このわずかな角度の最大測定値が、本方法のパラメータである。
【０１５３】
接触の問題には無用のＬＭＤを排除する、または疑似ＬＭＤを考慮に入れることは、以下に示す適合性と角度調整をまとめた表（表５）に示された接触クラスを公式化した簡単な局所基準に従って体系化することができる。
【０１５４】
なお、本発明の方法は様々な分野で活用できるという事実に加え、本発明の方法には、疑似ＬＭＤという概念の利用、および接触の問題には無用なＬＭＤを排除できるということから生じる基本的な利点がある。
【０１５５】
さらに、集合（数２９）は、剛体の場合にはあらかじめ計算可能な多面錐である。
【０１５６】
【数２９】
0005424883.tif 000034
【０１５７】
最後に、本発明は、すべての点の対（σ1，σ2）∈Ｋ1×Ｋ2を調べても意味がなく、それぞれ強い意味での関連づけられた法線を備えた｜Ｋ1｜および｜Ｋ1｜の包含体積の階層を用いることで、そのような調査の高速化が図れるという事実を考慮にいれたものである。剛体の場合、包含体積の階層は完全にあらかじめ計算することができる。有限の単体的複体Ｋによって表される変形体の場合、以下のソリューションが適用できる。すなわち、
・基準となる変形状態について、包含体積Ｈの階層を構築するために、Ｋのフェースの単体内部を形成する｜Ｋ｜のパーティションについての階層Ｈ’を利用する。
・同じ構造の２つの変形状態の間で、Ｈ’に基づく包含体積の階層を保持し、Ｋのフェースの変形に合わせるために各包含体積の幾何学的形状を単に更新する。
【０１５８】
包含体積の階層の使用は、衝突検出の分野では標準的な手法である。本発明では、非特許文献１が提案している方法を改良したものを用いている。
【０１５９】
次に、本発明の方法における事前計算ステップについて詳細に説明する。
【０１６０】
以下において、ｎは２または３の整数とする。
【０１６１】
入力データは、Ｒnの単体的複体の有限の群により構築されている。
【０１６２】
出力データは以下を含む。すなわち、
各単体的複体Ｋの各フェースσについて、
・多面錐（数３０）の幾何学的表記
・そのフェースが属する接触クラスのラベル
【０１６３】
【数３０】
0005424883.tif 000035
【０１６４】
入力された各単体的複体Ｋについて、
・強い意味での関連づけられた法線を備えた単体的複体体の包含体積の木
【０１６５】
したがって、包含体積はＲn×Ｒnの部分である。本発明で用いる各包含体積は、Ｒnの球体とＲnの錐とのカルテシアン積である。Ｒ3の場合、対象となる錐は、場合によりゼロの開口（ほとんど、または完全にまっすぐな線分）を備えた、単または双回転体である。Ｒ2の場合、対象となる錐は、その錐とその回転軸を含む平面との交差による３次元的状況から得られる。
【０１６６】
木の各葉ノードは、Ｋの１つまたは複数のフェースと関連づけられている。Ｋのフェースは、木の複数の葉と関連づけられている。厳密にいうと、木の葉に関連づけられたＫのフェースとは、Ｋ体に対する強い意味での関連づけられた法線の集合が空でないようなフェースのことである。葉ノードに関連づけられた包括体積は、その葉と関連づけられたＫのフェースの単体内部の和集合により形成された、関連づけられた法線を備えた、Ｋ体の部分と重複する。
【０１６７】
木の各ノード（葉ノードか否かは問わない）は以下に関連づけられている。
・そのノードにより生成される木の枝の葉と関連づけられたＫのフェースの単体内部の和集合により形成された、関連づけられた法線を備えた、Ｋの体の部分と重複する包含体積。
・ラベルｉ（ｉは０から７）の各接触クラスについて、以下の述語の評価に等しいブール値。このノードにより生成される木の枝の葉の中には、クラスラベルがｉであるＫの少なくとも１つのフェースと関連づけられた少なくとも１つの葉が存在する。
【０１６８】
入力された各単体的複体Ｋに対しておこなう処理について以下に述べる。Ｋの頂点の座標が固定座標系にあると仮定する。剛体の場合、その体と結びついた軸系を選ぶのが自然であり都合がよい。変形体の場合、例えば、いわゆる基準変形状態（例えば、挙動法則が弾性である体の静止状態）にあるＫの頂点の座標を固定するために、基準軸系を選ぶことができる。
【０１６９】
本発明の方法の前処理段階における第１のステップでは、強い意味での法線と接触クラスを計算する。
【０１７０】
この計算には必然的にＫの各フェースについて、（数３１）の幾何学的表記の計算を伴う。
【０１７１】
【数３１】
0005424883.tif 000036
【０１７２】
以下の成果を思いだしてもらいたい。
【０１７３】
【数３２】
0005424883.tif 000037
【０１７４】
この種の多面錐をマシンコードで表すには、いくつか選択肢がある。ＬＭＤの検索段階で必要な計算において、ベクトル部分空間（数３３）はマシンコードで表す必要がないとする。凸錐（数３４）の表現で十分である。
【０１７５】
【数３３】
0005424883.tif 000038
【０１７６】
【数３４】
0005424883.tif 000039
【０１７７】
剛体の場合、その体に結びつけられた座標系で作業し、（数３５）の極座標表現を用いるのが得策である。そうすることで結果的に、その錐のエッジによって、すなわち、同じ凸錐を生成する（数３６）の最小の部分集合によって、生成された凸錐（数３７）を表わすことができるからである。
【０１７８】
【数３５】
0005424883.tif 000040
【０１７９】
【数３６】
0005424883.tif 000041
【０１８０】
【数３７】
0005424883.tif 000042
【０１８１】
変形体の場合、（数３８）によって生成された凸錐のエッジを指すベクトルの部分集合は変動しうる。したがって、極座標表現においてすべての（数３９）を保持するのがより得策である。
【０１８２】
【数３８】
0005424883.tif 000043
【０１８３】
【数３９】
0005424883.tif 000044
【０１８４】
例えば、Ｒ3における多面複体の頂点であるフェースσを調べることができる。そのとき、（数４０）が成立し、よって、（数４１）が成立する。
【０１８５】
【数４０】
0005424883.tif 000045
【０１８６】
【数４１】
0005424883.tif 000046
【０１８７】
続いて（数４２）の計算をした後、そこから同じ凸錐を生成する最小部分集合を抽出する。これは、（数４３）によって生成される凸多面錐のフェースを構成する平面を検索することにより簡単に実行することができる。その結果、この錐のエッジのディレクタ・ベクトルでない（数４２）を連続的に排除することになる。これら平面は、（数４２）のなかから取り出した独立ベクトルの対により生成され、その他すべての（数４２）がこれら平面の同じ側にあるような面である。
【０１８８】
【数４２】
0005424883.tif 000047
【０１８９】
【数４３】
0005424883.tif 000048
【０１９０】
いくつかの可能性がある。
【０１９１】
１．（数４４）は空である。よって、（数４５）となる。したがって、σの接触クラスはラベル０のクラスである。
【０１９２】
【数４４】
0005424883.tif 000049
【０１９３】
【数４５】
0005424883.tif 000050
【０１９４】
２．（数４６）は独立したベクトルを有していない。この場合、さらに２つの可能性がある。
【０１９５】
【数４６】
0005424883.tif 000051
【０１９６】
ａ．すべての（数４７）が同じ方向を指している。そのうち１つだけを保持すれば十分であり、σの接触クラスのラベルは０である。
【０１９７】
ｂ．反対方向にも（数４７）が存在する。その場合、（数４７）により生成される錐はまっすぐな線分であるベクトルであり、σの接触クラスのラベルは１である。
【０１９８】
【数４７】
0005424883.tif 000052
【０１９９】
３．同じ開半空間にその他すべての（数４８）を配置することのできる独立ベクトル（数４８）の対によって生成される平面が存在する。（数４８）によって生成される凸錐がまっすぐな線分であるベクトルを含まないことを示すことができる。すると、同じ特性を満たす平面を生成するその他のベクトル（数４８）の対を検索することが必要になる。対象となるベクトルは、円形に配列することができる。それ以外のベクトルは錐の内部にあって、所望の最小表現の部分を構成しない。σの接触クラスはラベル０である。
【０２００】
【数４８】
0005424883.tif 000053
【０２０１】
４．同じ開半空間ではなく、同じ閉半空間にその他すべての（数４９）を配置することのできる独立ベクトル（数４９）の対によって生成される平面が存在する。すると、この平面には少なくとも３つの（数４９）がある。この３つのケースは以下のとおり。
【０２０２】
【数４９】
0005424883.tif 000054
【０２０３】
ａ．この平面に含まれる（数５０）は、この平面と等しい凸錐を生成する。この場合、以下の２つの可能性がある。
【０２０４】
ｉ．この平面にない（数５０）が存在する。実は、所望の凸錐は、すでに見つかった平面により区切られた半空間であり、σの接触クラスはラベル３である。
ｉｉ．すべての（数５０）はすでに見つかった平面内にある。所望の凸錐は、この平面と等しく、σの接触クラスはラベル４である。
【０２０５】
【数５０】
0005424883.tif 000055
【０２０６】
ｂ．この平面の（数５１）は、閉半平面と等しい凸錐を生成する。この場合、以下の２つの可能性がある。
【０２０７】
【数５１】
0005424883.tif 000056
【０２０８】
ｉ．この平面にない（数５２）が存在する。（数５２）により生成される凸錐は、ちょうど２つのフェースを有し、他に見つけるべき平面がちょうど１つ残っている。σの接触クラスはラベル１である。
ｉｉ．すべての（数５２）がこの平面内にある。所望の凸錐は、すでに見つかった閉半平面と全く等しく、σの接触クラスはラベル１である。
【０２０９】
【数５２】
0005424883.tif 000057
【０２１０】
ｃ．この平面に含まれる（数５３）は、半平面に厳密に含まれる角をなす扇形の平面である。この扇形のエッジベクトルだけが保持され、上記３の状態に戻る。
【０２１１】
【数５３】
0005424883.tif 000058
【０２１２】
５．（数５４）の対によって生成された平面はいずれも、同じ半空間内に（数５４）すべてを配置することはできない。そして、（数５４）は、事実上Ｒ3全体である凸錐を生成し、（数５５）となる。σの接触クラスはラベル７である。
【０２１３】
【数５４】
0005424883.tif 000059
【０２１４】
【数５５】
0005424883.tif 000060
【０２１５】
本発明の方法の前処理段階における第２のステップについて以下に述べる。この第２ステップは、包含体積の階層の構築に関するものである。
【０２１６】
包含体積の階層の構築については様々なアプローチが可能である。主として、連続細分割によるトップダウン・アプローチと、集約によるボトムアップ・アプローチに大別することができる。なお、非特許文献１は、このタスクの実行にあたってＰＱＰライブラリ（非特許文献４および５）に依存している。しかし、ＰＱＰは、階層の構築のために幾何学的基本要素（点、エッジ、三角形）の位置にのみ基づくもので、関連づけられた法線は用いていない。
【０２１７】
本発明は、単体的複体のフェースσの位置と、関連づけられた法線（数５６）の集合の両方を用いることを提案するものである。そのため、各（数５６）について、包含する回転錐を事前に計算することが有益である。そうすれば必然的に、基本的な幾何学的計算だけをすればよくなり、当業者にとって特に問題を提起することにはならないからである。
【０２１８】
【数５６】
0005424883.tif 000061
【０２１９】
本発明は、以下のステップを提案するものである。その目的は、自身のフェースの単体内部により形成されるＫ体のパーティションの（集合論の意味における）階層を構築することである。これは、このパーティションの要素の集合を細分割することにより帰納的に演算するトップダウンの手法であり、パーティションの全要素の集合から処理を始めるため、木の根に関連づけられている。反復を中止する基準は、木の葉に関連づけられた基数１（単集合、すなわち、単一のＩｎｔσ）のパーティションの要素の集合を処理することに相当する。
【０２２０】
細分割プロセスは以下のような形態をとる。位置および向きという意味において二者択一的に（または、使用状況に依存する発見的手法により）、最大慣性軸の中心という標準的基準に従って、この細分割が実行される（非特許文献１参照）。「位置という意味において」という表現は、σの重心を用いるという意味に解釈しなくてはならない。「向きという意味において」という表現は、（数５７）を包含する回転錐の軸を用いるという意味に解釈しなくてはならない。
【０２２１】
【数５７】
0005424883.tif 000062
【０２２２】
実験的には、効率的な発見的手法として、まず位置による細分割を３、４回おこなってから、位置による細分割と向きによる細分割とを交互におこなうとよい（いわゆるスプリットという細分割の手法である）。
【０２２３】
いったん階層が構築されると、階層の各ノードについて包含体積を計算すれば十分である。ノードに関連づけられたフェースの位置を包含する球面に関して、以下の２つの手法が可能である。
１．各ノードに関連づけられたフェースを包含する最小半径の球面を計算する。
２．木の葉について最小球面を計算した後、包含球面の階層上の包含関係に従い木を連続的に昇っていく。
【０２２４】
いずれの場合も、確立した方法が存在し、その文献は入手可能である。剛体の場合、ソリューション１がより効果的である。変形体の場合、包含体積の階層の効率的な更新を追求するには、混合型のソリューションが好ましい。すなわち、木の「最下部」ではソリューション１を用い、「最上部」ではソリューション２を用いるとよい。木における最上部と最下部とを区別するには、ノードの深さを基準として用いることができ、深さのしきい値は、試行錯誤により調整される。
【０２２５】
ノードに関連づけられたフェースの法線の集合を包含しなくてはならない回転錐に関しては、ソリューションとして、ソリューション２に類似したソリューションが、実装の簡単さという点で利点がある（単に錐の対を包含する錐を計算すればよい）。
【０２２６】
効率面を考慮した場合も同様に、様々な接触クラスに属するフェースの帰属に関する情報を包含する体積の階層を昇っていくことが望ましい（上記参照）。このような階層の上昇により、後述するノード毎のテストを堅固にできるため、階層の下降がより選択的になって、処理スピードが上がる。このような処理をおこなってもなんら問題は生じない。８つのクラスそれぞれについて、そのクラスに属する少なくとも１つのフェースのノードと関連づけられた複数のフェースの中に存在することを示す８つのブール値の集まりを、各ノードと関連づければ十分である。
【０２２７】
最後に、剛体の場合にのみ、各フェースのクラスは、初期化の時点で明確に決定される。したがって、以下で説明するように、ラベル７のクラスに属するフェースはＬＭＤの台にも疑似ＬＭＤの台にもなることはできないため省いてもよい。
【０２２８】
前処理に続き（疑似）局所最短距離を計算する本発明の方法のステップについて、以下に述べる。
【０２２９】
この時点で導入する本方法の２つのパラメータは、必要に応じ２つのリクエストのいずれかに修正することができ、この修正により、先におこなった事前計算ステップが無効になることはない。
【０２３０】
第１のパラメータγmaxは、疑似ＬＭＤの概念（いかなるＬＭＤも疑似ＬＭＤである）を定義する正またはゼロの角度の値である。第２のパラメータｄmaxは、疑似ＬＭＤの計算を、しきい値未満の値を有する疑似ＬＭＤにのみ限定するような（正またはゼロ、無限大も可の）距離のしきい値である。
【０２３１】
２つの単体的複体Ｋ1およびＫ2は以下のように考える。ここで述べる一対の複体の演算は、入力された複体のうち、それぞれ別個の複体の対それぞれに適用しなくてはならない。
【０２３２】
本発明のこのステップは、非特許文献１で提案された方法のステップと類似しているが、本発明では以下の拡張を導入している。
【０２３３】
ノード毎のテストでは、複体Ｋ1およびＫ2の値をそれぞれε1およびε2として、それら複体に適用した膨張すべてを考慮に入れる。したがって、ノードの相対位置のテストは、関連づけられた包含球面同士の中心が、最大Ｒ1＋Ｒ2＋ε1＋ε2＋ｄmaxの距離で離れていることを検証することからなる。ただし、Ｒ1およびＲ2はそれら球面の半径である。一方、双錐（非特許文献１参照）は、膨張されていない球面に基づいている。
【０２３４】
ノード毎のテストでは、位置ずれγmaxの許容範囲を考慮に入れる。したがって、様々な錐の交差のテストにおいて、法線を包含する回転錐は、頂点の半開口をγmaxだけ増加させた、同軸の錐と置換しなくてはならない。
【０２３５】
ノード毎のテストは、接触クラスに基づく追加テストを含む。テスト対象の２つのノードは、接触クラスｃ1およびｃ2に属するフェースと依属関係にあるブール値のベクトルを含む。そのようなベクトルのｉ番目の成分は、ノードに関連づけられたフェースの中に、ラベルｉのクラスに属する少なくとも１つのフェースが存在するかどうかを示すブール値である。このテストは、ブール値ｃ1TＣｃ2を評価することからなる。ここで、Ｃは以下に示す対称型のブール行列であり、接触クラス間の適合性行列という。
【０２３６】
【数５８】
0005424883.tif 000063
【０２３７】
その結果得られるブール値が１のとき、かつそのときに限り、このテストは有効となる。
【０２３８】
葉毎のテストは、複体の膨張と、位置ずれγmaxの許容範囲を考慮に入れる。これらテストを実現する基本原理は、まず、テスト済みの２つのフェースによって生成されるアフィン空間同士の唯一のＬＭＤを計算し（上述したように、平行の場合は、排除される）、次に、その台が２つのフェースの単体内部の積上にあることを検証することである。これは、当業者ならよく知っている基礎的な幾何学的計算であり、例えば、非特許文献６に詳細に述べられている。これらフェースの単体内部間のＬＭＤ（ｘ1，ｘ2）∈Ｉｎｔσ1×Ｉｎｔσ2が見つかった場合、上述したように、そのＬＭＤが、フェースの単体内部と関連づけられた強い意味での法線の錐に適合していることを検証しなくてはならない。すなわち、ｘ2−ｘ1が（数５９）に属しているか、ｘ1−ｘ2が（数６０）に属しているかテストしなくてはならない。このテストの実行は容易である。なぜなら、事前計算ステップによりすでに、そのタイプのベクトル（数６１）の有限集合の極という形式で（数５９）と（数６０）とを表現しているからである。最大位置ずれγmaxを考慮に入れるには、この極錐への帰属に関する制約を緩和しなくてはならない。このγmaxは、そのベクトル（数６１）の極錐（すなわち、各（数６１）と少なくともπ／２の角度を形成するベクトルの集合）ではなく、各（数６１）と少なくともπ／２−γmaxの角度を形成するベクトルの集合を考慮して簡単に近似することができる。このような制約の緩和はすべてのケースにおいて実行する必要はないが、以下の表５に示すルールに従っておこなわなくてはならない。
【０２３９】
【数５９】
0005424883.tif 000064
【０２４０】
【数６０】
0005424883.tif 000065
【０２４１】
【数６１】
0005424883.tif 000066
【０２４２】
【表５】
0005424883.tif 000067
【０２４３】
表５は、疑似ＬＭＤを定義するための角度調整ルールを示している。この表は複式記入の表として利用しなくてはならない。この表の各ボックスには、一対のブール値または記号（数６２）が記入されている。ボックス内に一対のブール値が記入されている場合、左側の値（または右側の値のそれぞれ）は、フェースσ1（またはσ2それぞれ）に関連づけられたベクトル（数６３）の極錐を、γmaxの値によって設定したパラメータを有する上述の集合で置換しなくてはならないかどうかを示している。記号（数６２）は、排除しなくてはならないケース（上述の無用なケース）を示している。
【０２４４】
【数６２】
0005424883.tif 000068
【０２４５】
【数６３】
0005424883.tif 000069
【０２４６】
変形体の場合、変形状態を修正した後で包含体積（球面と回転錐）の幾何学的形状を更新しなくてはならないが、この更新には標準的な更新方法が直接適用できるため、何ら難しいことではない。
【０２４７】
本発明の変形例によると、近接エリアを目立たせるためにオブジェクト間の距離を計算するだけでなく、相対移動速度の計算もおこなう。そうすることで、距離のしきい値を自動的、局所的に適応させることができる。
【０２４８】
また、本発明の別の変形例によると、リアルタイム・シミュレーションのスピード向上を図るため、例えばマルチプルコア・プロセッサに基づき、平行アーキテクチャを最大限に利用するための計算が並行しておこなわれる。
【０２４９】
さらに、本発明の別の変形例によると、本発明の方法を、多面体の中心軸により表現されるオブジェクトに一般化する（例えば、非特許文献７および８を参照）。
【０２５０】
疑似ＬＭＤを用いた本発明の方法の利点は、並進や回転に合わせて調整できる点である。これにより、仮想オブジェクトの移動や回転に対して非常に強力なソリューションをもたらすことになる。したがって、図形レンダリングおよび／または視覚レンダリングの安定性が、本質的に予想が困難なユーザとのインタラクションによって損なわれることはない。
【０２５１】
本方法の別の利点は、計算を速くおこなうことができるため、リアルタイム・シミュレータへの統合が可能な点である。したがって、本発明によると、機械的挙動にスプリアスな変動のない、安定したシミュレーションが可能になる。
【０２５２】
本発明の方法の実施の形態について、図３〜７を参照しながら説明する。
【０２５３】
これらの図面は、数値的にシミュレートされた２つのオブジェクト１０、２０、すなわち立方体１０と平面２０の画像を示しているが、もちろん本発明は様々な形態のオブジェクトに適用可能である。
【０２５４】
図３〜７は、２つの仮想オブジェクト間に相対的な動きがある場合の、両オブジェクト間の接触または近接エリアを様々な形に視覚化したものを示している。
【０２５５】
図３〜７は、立方体オブジェクト１０に関連づけられたＸＹＺ軸系を表している。本実施の形態において、平面は固定されており、２つのオブジェクト１０と２０との相対的な動きは、立方体オブジェクト１０の移動（回転または並進）によってのみ決まるものとする。
【０２５６】
立方体オブジェクト１０は角Ａ、Ｂ、Ｃ、Ｄを呈するフェースを有する。
【０２５７】
立方体１０の角Ａが平面２０に向かって移動すると（図３）、接触エリア、および／または平面２０に最も近い立方体１０の角Ａの位置にある接点が視覚化される。図３において、大きな矢印ＦAで表される。
【０２５８】
立方体１０が回転すると（図４）、別の角Ｂが平面２０の表面に向かって移動する。これは、小さな矢印ｆBで表される。
【０２５９】
続く中間ステップ（図５）では、立方体１０のエッジ（または、必要に応じてフェース）が平面２０に対して平行になる。したがって、図５において、角ＡとＢとの間にあるエッジの点はすべて平面２０に対して同じ距離にある。これは、角ＡとＢにおいて、大きな矢印ＦA、ＦBによって表される。よって、この系において、平面２０に平行な立方体１０のエッジ（またはフェース）全体が視覚化されている。
【０２６０】
立方体１０が回転し続けると、最初の状況と対称な状況、例えば、立方体１０の角ＣとＤが平面２０に向かって動き、角ＡとＢが依然平面２０から一定距離に位置にあるといった状況が生じる。小さい矢印ｆCおよびｆDは、角ＣおよびＤの平面２０への動きを表している。本実施例においては、この回転の最後には（図７）、角Ａ、Ｂ、Ｃ、Ｄによって区切られた立方体１０のフェースが平面２０と平行になる。このときの距離は、角Ａ、Ｂ、Ｃ、Ｄにおいて大きな矢印ＦA、ＦB、ＦC、ＦDによって表される。
【０２６１】
先行技術においては、立方体の１つの角から別の角への推移は不連続であったため、立方体のわずかな角度変化によって非常に不安定になっていた。
【０２６２】
一方、本発明によると、立方体１０の点ＡからエッジＡＢへ、次に別の角Ｂへ、さらにフェースＡ、Ｂ、Ｃ、Ｄへと連続的に推移する。これは、連続的というだけでなく、オブジェクトのわずかな角回転や、わずかな並進に応じて調整することができる方法である。
【０２６３】
この例は、本発明のソリューションの効果を示すものである。凹状オブジェクトと別のオブジェクトとの接触の場合、先行技術のソリューションでは、例えば、異なる接触点の間での変動となって不安定性が生じることになる（接触点が１つの脚から別の脚へと推移する傾いた椅子の場合、または平面上の立方体の場合）。一方、本発明によると、接触の前後に近接エリアが特定されるため、点接触に限定した検出につきものの不安定性を解消することができる。
【０２６４】
図８は、本発明の方法を実現するシステム１００の例を示している。
【０２６５】
このシステムは、Ｒn（ｎは２または３）における単体的複体Ｋ1、Ｋ2という形式で定義することのできるオブジェクトを数値的に表現するモジュール１０１を備えている。
【０２６６】
有限個の仮想オブジェクト間の衝突を検出し、近接および接触に関する幾何学的情報を構築するこのシステム１００は、前演算処理モジュール１１０および正規の演算処理モジュール１２０とを備えている。
【０２６７】
頂点の座標が固定座標系で示されている各単体的複体Ｋのための前演算処理モジュール１１０は、以下を備えている。各単体的複体Ｋの各フェース６について、そのフェースに関連づけられた強い意味での複数の法線（数６４）に対応する多面錐の幾何学的表記を計算する手段１１１、このフェース（σ）が属する接触クラスのラベルを定める手段１１２、および各単体的複体Ｋについて、その単体的複体Ｋのフェースσの位置と、強い意味での関連づけられた法線（数６４）の集合との両方から、その単体的複体Ｋであるオブジェクトの包含体積の木を決定する手段１１３、とを備えている。
【０２６８】
【数６４】
0005424883.tif 000070
【０２６９】
演算処理モジュール１２０は、前演算処理モジュール１１０の結果を利用する計算手段を備え、上述したような方法で、局所最短距離（ＬＭＤ）および疑似局所最短距離（疑似ＬＭＤ）とを計算する。
【０２７０】
モジュール１０１、１１０、１２０の組み合わせは、機械的解決手段１３０に接続されると有利である。
【０２７１】
モジュール１０１、１１０、１２０と機械的解決手段１３０との組み合わせは、優先的に周辺装置１１０に接続される。この周辺装置１１０は、グラフィカル・ユーザ・インターフェース、および／または、例えば、標準的な２Ｄマウス、６段階調節機能付き３Ｄマウス、動き感知周辺装置、バーチャル・リアリティ周辺装置、フィードバックフォース・インターフェース、タッチ式インターフェース、およびオーディオ・インターフェースといった１つまたは複数のその他の周辺装置１４０からなる。
【０２７２】
仮想オブジェクト間の疑似局所最短距離を評価することにより、本発明においては、オブジェクト、すなわち、３次元または２次元空間で定義された剛性または変形可能な固体をモデル化した仮想オブジェクト間で、規格化された接触空間を構築する。
【０２７３】
Ｃ1体とＣ2体間の衝突を検出する際の問題は、様々な形で公式化することができ、それぞれ「リクエスト・タイプ」に対応している。最も頻繁に発生するリクエスト・タイプは以下のとおりである。
・干渉リクエスト：述語（数６５）の評価
【０２７４】
【数６５】
0005424883.tif 000071
【０２７５】
・干渉計算：コンパクトＣ1∩Ｃ2の決定  
【０２７６】
Ｃ1とＣ2が互いに素な場合、
・グローバルな近接性のリクエスト、または分離距離（もしくはグローバル最短距離）の計算：（数６６）を満たす点の対（ａ1，ｂ2）∈Ｃ1×Ｃ2の検索。
【０２７７】
【数６６】
0005424883.tif 000072
【０２７８】
・グローバルな近接性のリクエスト、または局所最短距離の計算：以下の関数のすべての局所最小値の検索。
【０２７９】
【数６７】
0005424883.tif 000073
【０２８０】
Ｃ1およびＣ2の位相次元がｎであり、干渉しあっている場合、
・グローバルな相互透過の深さの計算：最小ノルムベクトルに沿った並進によるＣ1の画像がＣ2とは互いに素であるような最小ノルムベクトルを検索。
・局所的な相互透過の深さの計算：同じ計算、ただし、Ｃ1（およびＣ2それぞれ）を、Ｃ1∩Ｃ2の連結成分の近傍を有するＣ1（およびＣ2それぞれ）の交差と置換。
【０２８１】
Ｃ1とＣ2が互いに素な場合、
・インパクト日時の計算：Ｃ1が、時間パラメータに伴い軌線に沿ってＣ2に対して相対的に動いていると仮定した場合、また、Ｃ1およびＣ2が当初互いに素であると仮定した場合、Ｃ1とＣ2が干渉し始める最も早い瞬間があるとしたら、その日時を計算。
・インパクト点の計算：インパクト日時におけるコンパクト空間Ｃ1∩Ｃ2を決定。
【０２８２】
本発明では、このように様々なリクエストを考慮に入れることができ、特に、以下の基本要素の２つの集合間の局所最短距離の計算に関連している。
・２次元においては、基本要素は、点とまっすぐな線分（エッジという）である。
・３次元においては、基本要素は、点と、まっすぐな線分（エッジという）と、三角形である。
【０２８３】
目標とするアプリケーションが、このような集合で幾何学的に表される剛性または変形可能な固体間の接触空間の構築である場合、本発明では、以下の問題についても考慮に入れる。
・局所最短距離から構築された接触空間を調整する。
・剛体同士のすべり接触において、この空間のサイズを最小にする。
【０２８４】
接触空間が調整されておらず、時間発展方法を用いて接触問題を解決する場合には、特に適合接触において不安定性が生じる可能性がある。本発明では、この問題を解決し、適合接触の処理をおこなう。
【０２８５】
体同士の接触のモデルがすべり接触で、体が剛性の場合、接触問題を変えずに接触空間のサイズを縮小することができる。
【０２８６】
本発明の方法によると、様々な側面において先行技術に改善をもたらすことができる。
【０２８７】
特に、以下の効果がある。
・各基本要素について、法線フィールドの評価領域を、明確に定義された厳密な方法で計算する。
・本方法全体を通じて対象となる基本要素は、点、エッジ（両端を除く）、三角形（頂点を除く）と、基本要素を1つだけ含む葉の包含体積である。
・基本要素の位置の分割だけでなく向きにも基づいてトップダウンで連続的に分割することにより、包含体積の木を構築する。
・向きという意味での包含体積は、単または双回転錐である。
・処理対象としては、３次元における３つのエッジを有する多面体の表面、２次元における多角形の曲線といったケースを含む。
・３次元においては、多面エンベロープ（包絡）で表される体積も処理対象となり、同様に２次元においては、多角形の輪郭で表されるエリアも対象となる。
・単および双錐体の交差条件を、領域のタイプによって近接条件と置換することで、局所最短距離から構築した接触空間を回転に合わせて調整する。次に、局所最短距離を、回転と相関して疑似局所最短距離に置換する。この調整概念は、並進に合わせて厳密に接触の局所最短距離を形成する際の調整に似ている。
・すべり接触する剛体の場合：比較的厳密に凸な基本要素の対に依存している疑似局所最短距離だけを保持し、疑似局所最短距離に基づいて調整した接触空間の次元を下げる。接触空間の次元は、基本要素の性質およびその評価領域の位相次元にしたがって基本要素を分類することにより下げることができる。適合条件は、基本要素のクラス間で定められる。各クラスの要素の木のノードに存在するかどうかの情報を計算し、適合性のテストを、木を降下する際にノード間の近接テストに加える。
【図１】
0005424883.tif 000076
【図２】
0005424883.tif 000077
【図３】
0005424883.tif 000078
【図４】
0005424883.tif 000079
【図５】
0005424883.tif 000080
【図６】
0005424883.tif 000081
【図７】
0005424883.tif 000082
【図８】
0005424883.tif 000083