(57)【要約】【課題】凹形状を含む任意形状の物体間に形成される接触多角形群を算出する。【解決手段】凸形状でない凹形状多面体を複数の凸断片に凸分解し、凸断片複合体として取り扱う。各物体の凸包間の最近傍点又は最浸透点からなる凸包衝突代表点対を算出し、該凸包衝突代表点対の中点を通り、該凸包衝突代表点対を結ぶ直線方向を法線ベクトルとする仮想接触平面を決定する。凸断片毎に該仮想接触平面との接触形状を与える半接触多角形をそれぞれ求め、凸断片の組み合わせ毎に、半接触多角形を重ね合わせた積領域を求め、各積領域を統合して物体間の接触多角形を決定する。【選択図】  図２７
2008040580.tif 000002
【特許請求の範囲】
【請求項１】
接触状態にある任意形状の２物体間の接触形状を算出する接触形状算出装置であって、
各物体を凸断片群に分解し、又は凸断片群に分解された物体の情報を入力する凸断片複合体取得手段と、
衝突又は接触する物体間において、衝突又は接触している凸断片を検出する凸断片間衝突検出手段と、
衝突又は接触する各物体の凸包の共通領域を通過する仮想接触平面を決定する仮想接触平面決定手段と、
衝突又は接触している各凸断片と該仮想接触平面との接触状態をそれぞれ個別の半接触問題として解く半接触問題解決手段と、
前記半接触問題解決手段によって凸断片毎に求められた半接触問題の解を統合して、衝突又は接触する物体間の接触多角形を決定する接触多角形決定手段と、
を具備することを特徴とする接触形状算出装置。
【請求項２】
前記仮想接触平面決定手段は、衝突又は接触する各物体の凸包間の最近傍点又は最浸透点からなる凸包衝突代表点対を算出し、該凸包衝突代表点対の中点を通り、該凸包衝突代表点対を結ぶ直線方向を法線ベクトルとする仮想接触平面を決定する、
ことを特徴とする請求項１に記載の接触形状算出装置。
【請求項３】
前記半接触問題解決手段は、他の凸断片と衝突又は接触している凸断片毎に該仮想接触平面との接触形状を与える半接触多角形をそれぞれ求め、
前記接触多角形決定手段は、衝突又は接触している凸断片の組み合わせ毎に、半接触多角形を重ね合わせた積領域を求め、各積領域を統合して物体間の接触多角形を決定する、
ことを特徴とする請求項２に記載の接触形状算出装置。
【請求項４】
凸断片毎に頂点の接続関係を表した隣接頂点グラフを保持し、
前記半接触問題解決手段は、処理対象とする凸断片に関する隣接頂点グラフを探索して、半接触多角形内に存在する頂点集合を求め、適当な頂点を起点として、仮想セッション平面内に存在しない頂点に到達するまで隣接頂点グラフを再帰的に局所的探索し、半接触多角形内に存在する頂点集合を求める、
ことを特徴とする請求項３に記載の接触形状算出装置。
【請求項５】
前記半接触問題解決手段は、処理対象とする凸断片のうち前記法線ベクトル方向に接触相手となる凸断片に最も浸透した頂点を隣接頂点グラフ局所探索の起点に設定する、
ことを特徴とする請求項４に記載の接触形状算出装置。
【請求項６】
前記半接触問題解決手段は、前記法線ベクトル方向又はその逆方向のサポート写像から得られる頂点を隣接頂点グラフ局所探索の起点に設定する、
ことを特徴とする請求項５に記載の接触形状算出装置。
【請求項７】
前記半接触問題解決手段は、処理対象とする凸断片の頂点のうち、仮想接触平面より接触相手となる凸断片側に存在する頂点を半接触多角形内に存在する頂点として抽出する、
ことを特徴とする請求項４に記載の接触形状算出装置。
【請求項８】
前記半接触問題解決手段は、他の凸断片と衝突又は接触している凸断片において抽出された頂点集合のうち、半接触多角形の内部に存在する頂点を取り除く、
ことを特徴とする請求項４に記載の接触形状算出装置。
【請求項９】
前記半接触問題解決手段は、半接触多角形内に存在するとして抽出された頂点集合を該仮想接触平面に正射影し、正射影した頂点群を包含する最小の凸多角形頂点集合を得るための演算を実行して、該仮想接触頂点上で内部の点を含まない、半接触多角形の輪郭頂点集合を算出する、
ことを特徴とする請求項８に記載の接触形状算出装置。
【請求項１０】
各物体の凸包を所定のオフセット量だけ膨張させた膨張物体を生成する物体膨張手段をさらに備え、
前記凸断片間衝突検出手段は、膨張物体間の衝突又は接触に基づいて衝突又は接触している凸断片を検出し、
前記半接触問題解決手段は、膨張前の原物体の凸断片と、仮想接触平面を平行移動させたオフセット仮想接触平面との間の半接触多角形を算出する、
ことを特徴とする請求項３に記載の接触形状算出装置。
【請求項１１】
前記凸断片間衝突検出手段は、膨張物体間で衝突又は接触が生じている原物体間における最近接点対を算出し、
前記仮想接触平面決定手段は、該最近接点対の中点を通り、該最近接点対を結ぶ直線方向を法線ベクトルとする仮想接触平面を決定する、
ことを特徴とする請求項１０に記載の接触形状算出装置。
【請求項１２】
前記半接触問題解決手段は、前記仮想接触平面設定手段により設定された仮想接触平面を前記法線ベクトル方向に前記オフセット量だけ平行移動させたオフセット仮想接触平面を設定する、
ことを特徴とする請求項１１に記載の接触形状算出装置。
【請求項１３】
前記物体膨張手段は、オフセット仮想接触平面と原物体が必ず交点を有するようにオフセット量を設定し、
前記半接触問題解決手段は、前記法線ベクトルに沿って原物体側に該オフセット量だけ仮想接触平面を平行移動させたオフセット仮想接触平面と凸断片との半接触多角形を算出する、
ことを特徴とする請求項１１に記載の接触形状算出装置。
【請求項１４】
接触状態にある任意形状の２物体間の接触形状を算出する接触形状算出方法であって、
各物体を凸断片群に分解し、又は凸断片群に分解された物体の情報を入力する凸断片複合体取得ステップと、
衝突又は接触する物体間において、衝突又は接触している凸断片を検出する凸断片間衝突検出ステップと、
衝突又は接触する各物体の凸包の共通領域を通過する仮想接触平面を決定する仮想接触平面決定ステップと、
衝突又は接触している各凸断片と該仮想接触平面との接触状態をそれぞれ個別の半接触問題として解く半接触問題解決ステップと、
前記半接触問題解決ステップにおいて凸断片毎に求められた半接触問題の解を統合して、衝突又は接触する物体間の接触多角形を決定する接触多角形決定ステップと、
を具備することを特徴とする接触形状算出方法。
【請求項１５】
接触状態にある任意形状の２物体間の接触形状を算出するための処理をコンピュータ上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、前記コンピュータに対し、
各物体を凸断片群に分解し、又は凸断片群に分解された物体の情報を入力する凸断片複合体取得手順と、
衝突又は接触する物体間において、衝突又は接触している凸断片を検出する凸断片間衝突検出手順と、
衝突又は接触する各物体の凸包の共通領域を通過する仮想接触平面を決定する仮想接触平面決定手順と、
衝突又は接触している各凸断片と該仮想接触平面との接触状態をそれぞれ個別の半接触問題として解く半接触問題解決手順と、
前記半接触問題解決手順において凸断片毎に求められた半接触問題の解を統合して、衝突又は接触する物体間の接触多角形を決定する接触多角形決定手順と、
を実行させることを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の３次元物体間の接触を検出し、接触状態にある２物体間の接触形状を算出する接触形状算出装置及び接触形状算出方法、並びにコンピュータ・プログラムに係り、特に、２つの物体が衝突又は接触している状況において、両者の間に形成される接触多角形を算出する接触形状算出装置及び接触形状算出方法、並びにコンピュータ・プログラムに関する。
【０００２】
さらに詳しくは、本発明は、複雑形状の物体間の接触多角形を高速且つ完全に算出する接触形状算出装置及び接触形状算出方法、並びにコンピュータ・プログラムに係り、特に、凹形状を含む任意形状の物体間に形成される接触多角形群を頑健且つ厳密に算出する接触形状算出装置及び接触形状算出方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００３】
仮想環境内に複数の物体が共存し、それらの間の衝突や接触といった物理的相互作用を計算機上で再現する力学シミュレーションなどを取り入れることにより、物体間の衝突が発生したことを検出するとともに、物体間の接触状態を把握して、衝突箇所に適切な反力を作用させる必要がある。
【０００４】
例えば、ヒューマノイドのような脚式移動ロボットにおいては、両脚の足平と床面、あるいは作業環境内に存在する複数の物体との間における衝突又は接触を検出するとともに、床面や物体とロボット間が相互に力を及ぼす領域の形状すなわち「接触多角形」をより厳密に算出し、衝突や接触といった物理的相互作用を計算機上で再現する力学シミュレーションなどを取り入れることにより、立体間の衝突が発生したことを検出するとともに、物体間の接触状態を把握して、衝突箇所に適切な反力を作用させる必要がある。
【０００５】
例えば、図４２に示すように、２つの立方体ＡとＢが接触しているときは、接触形状を構成するｖ１、ｖ２、ｖ３、ｖ４の各頂点に反力を作用させる必要がある。２つの立体が接触状態にあるとき、図形ｖ１ｖ２ｖ３ｖ４のような２つの立方体間の接触部の形状が接触多角形である。
【０００６】
しかしながら、物体間の衝突検出及び衝突箇所算出に用いられる周知の衝突検出アルゴリズムの多くは、２立体間の衝突点の一部しか得ることができず、接触多角形を完全に算出することはできない。例えば、図４３に示すような１衝突当たりその代表点１点（通常、最も浸透した点（最浸透点、貫通深度）、若しくは最も近接した点（最近傍点））、あるいは、図４４に示すような衝突を発生した３角形メッシュといった、安定した力学シミュレーションを実行するには不完全な出力しか提供することができない。
【０００７】
不十分な衝突検出アルゴリズムの結果を直接用いて力学シミュレーションを実行すると不都合を生じる。ここで、立方体が水平な床上に置かれている場合を例にとって考察してみる。例えば、図４５に示すように代表点Ｐのみに反力を作用させるとき、床反力モデルが復元力を有さない場合には、図４５（Ａ）に示すように、Ｐ点の他端が支持されないために、立方体はＰ点回りに回転しながら他端が徐々に床に浸透していってしまう。そして、シミュレーションが１フレームだけ進むとＱ点が最も浸透した点となり、Ｐ点に代わってＱ点に反力が作用するため、Ｑ点を中心として回転し、今度はＰ点がさらに浸透する。以上のような状態を繰り返すと、立方体は際限無く床面に浸透していってしまう。また、床反力モデルが復元力を有している場合には、図４５（Ｂ）に示すように浸透はある一定量以上には及ばないものの、作用点がＰ点とＱ点の間で右往左往し、振動が発生してしまうため、良好なシミュレーション結果が得られ難い。
【０００８】
また、実世界に存在する物体の多くは凹形状を含む物体であるから、凸形状だけでなく、凹形状を含むより一般的な形状に対応する必要がある。ところが、凹形状物体の干渉検出は凸形状物体の干渉検出に比し、計算量が多く、形状の複雑化、オブジェクト数の増加に従い、シミュレーションのリアルタイム性が大きく損なわれる可能性がある。
【０００９】
例えば、凸包アルゴリズム（Ｃｏｎｖｅｘ  Ｈｕｌｌアルゴリズム）や（例えば、非特許文献１を参照のこと）、軸平行境界ボックス（ＡＡＢＢ）（例えば、非特許文献２を参照のこと）、境界球（例えば、非特許文献３を参照のこと）、有向境界ボックス（例えば、非特許文献４を参照のこと）、離散方向ポリトープ（ｋ−ＤＯＰ）（例えば、非特許文献５を参照のこと）などの各種境界ボリューム手法を用いて、凹形状を含む物体を凸形状に近似した形状により衝突検出を行なうことはできる。しかしながら、より現実感のある力学シミュレーションや複雑環境下での移動ロボットの精密なリアルタイム動作計画を実現するためには、凹形状のまま衝突検出を行ない、より正確な物体間接触多角形群を算出する必要がある。
【００１０】
また、３次元空間内の物体を位置に関して階層的に表現したソリッドモデルすなわちＯｃｔｒｅｅを物体毎に生成し、各々のＯｃｔｒｅｅを並列にたどることによって衝突を検出する衝突検出装置について提案がなされている（例えば、特許文献１を参照のこと）。同装置では、Ｏｃｔｒｅｅの３種類のノードの定義を、凹形状を含んだ物体のＯｃｔｒｅｅ生成が可能なように変更（拡張）することによって、凹形状を含んだ物体のＯｃｔｒｅｅ生成を実現している。しかしながら、物体を形成する面数が多い場合、Ｏｃｔｒｅｅ生成時間が非常に長くなってしまい、グリッド・コンピューティング（ｇｒｉｄｃｏｍｐｕｔｉｎｇ）などの複数のコンピュータでの分散・並列処理が必要となり、高速性、リアルタイム性の点で難がある
【００１１】
【特許文献１】特開２００５−３１００２１号公報
【非特許文献１】Ｂａｒｂｅｒ，Ｃ．Ｂｒａｄｆｏｒｄ，Ｄａｖｉｄ  Ｄｏｂｋｉｎ，Ｈａｎｎｕ  Ｈｕｈｄａｎｐａａ，“Ｔｈｅ  Ｑｕｉｃｋｈｕｌｌ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ＣｏｎｖｅｘＨｕｌｌｓ”（ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｍａｔｈｅｍａｔｉｃａｌ  Ｓｏｆｔｗａｒｅ，ｖｏｌ．２２，ｎｏ．４，ｐｐ．４６９−４８３，１９９６）
【非特許文献２】Ｃ．Ｅｒｉｃｓｏｎ，“Ｒｅａｌ−Ｔｉｍｅ  Ｃｏｌｌｉｓｉｏｎ  Ｄｅｔｅｃｔｉｏｎ”（Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ  Ｐｕｂｌｉｓｈｅｒｓ，２００５）
【非特許文献３】Ｒｉｔｔｅｒ，Ｊａｃｋ，“Ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｂｏｕｎｄｅｒｉｎｇ  Ｓｐｈａｒｅ”（ｉｎ  Ａｎｄｒｅｗ  Ｇｌａｓｓｎｅｒ（ｅｄ．），Ｇｒａｐｈｉｃｓ  Ｇｅｍｓ，Ａｃａｄｅｍｉｃ  Ｐｒｅｓｓ，ｐｐ．３０１−３０３，１９９０）
【非特許文献４】Ｅｒｉｃ  Ｌｅｎｇｙｅｌ，“Ｍａｔｈｅｍａｔｉｃｓ  ｆｏｒ  ３ｄ  Ｇａｍｅ  Ｐｒｏｇｒａｍｍｉｎｇ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ”（Ｃｈａｒｌｅｓ  Ｒｉｖｅｒ  Ｍｅｄｉａ，２００１）
【非特許文献５】Ｋｏｎｅｃｎｙ，Ｐｅｔｒ．Ｋａｒｅｌ  Ｚｉｋａｎ，“Ｌｏｗｅｒ  Ｂｏｕｎｄ  ｏｆ  Ｄｉｓｔａｎｃｅ  ｉｎ  ３Ｄ”（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＷＳＣＧ  １９９７，ｖｏｌ．３，ｐｐ．６４０−６４９，１９９７）
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明の目的は、複雑形状の物体間の接触多角形を高速且つ完全に算出することができる、優れた接触形状算出装置及び接触形状算出方法、並びにコンピュータ・プログラムを提供することにある。
【００１３】
本発明のさらなる目的は、凹形状を含む任意形状の物体間に形成される接触多角形群を頑健且つ厳密に算出することができる、優れた接触形状算出装置及び接触形状算出方法、並びにコンピュータ・プログラムを提供することにある。
【課題を解決するための手段】
【００１４】
本発明は、上記課題を参酌してなされたものであり、その第１の側面は、接触状態にある任意形状の２物体間の接触形状を算出する接触形状算出装置であって、
各物体を凸断片群に分解し、又は凸断片群に分解された物体の情報を入力する凸断片複合体取得手段と、
衝突又は接触する物体間において、衝突又は接触している凸断片を検出する凸断片間衝突検出手段と、
衝突又は接触する各物体の凸包の共通領域を通過する仮想接触平面を決定する仮想接触平面決定手段と、
衝突又は接触している各凸断片と該仮想接触平面との接触状態をそれぞれ個別の半接触問題として解く半接触問題解決手段と、
前記半接触問題解決手段によって凸断片毎に求められた半接触問題の解を統合して、衝突又は接触する物体間の接触多角形を決定する接触多角形決定手段と、
を具備することを特徴とする接触形状算出装置である。
【００１５】
力学シミュレーションの分野では、複数の物体が共存する仮想環境内で、物体間の衝突や接触といった物理的相互作用を計算機上で再現する。ここで、物体同士の衝突が発生したときに、衝突箇所に適切な反力をリアルタイムで作用させるためには、物体間のより正確な接触多角形を高速に求める必要がある。
【００１６】
しかしながら、周知の衝突検出アルゴリズムの多くは、１衝突当たり代表点Ｐを１点（通常は最も浸透した点、若しくは最も近接した点）、あるいは接触を発生した３角形メッシュＭといったように、２立体間の衝突点の一部しか得ることができず、接触多角形を完全に算出することはできない。このように不十分な衝突検出アルゴリズムの結果を直接用いて力学シミュレーションを実行すると、不都合を生じる。
【００１７】
また、実世界に存在する物体の多くは凹形状を含む物体であるから、凸形状だけでなく、凹形状を含むより一般的な形状に対応する必要がある。ところが、凹形状物体の干渉検出は凸形状物体の干渉検出に比し、計算量が多く、形状の複雑化、オブジェクト数の増加に従い、シミュレーションのリアルタイム性が大きく損なわれる可能性がある。
【００１８】
これに対し、本発明は、既存の衝突検出アルゴリズムから得られた衝突代表点対（最浸透点対若しくは最近傍点対）から、その周辺探索のみを行なうことによって、精密な接地多角形を高速に算出するようにした。
【００１９】
衝突又は接触が検出された２物体間の接触状態を直接的に扱うと、さまざまな組み合わせが存在するために問題が複雑となり、計算負荷が高くなる。そこで、本発明では、２物体の共通領域を通過する接触平面を定義し、各物体と接触平面との半接触問題を個別に解いて、各物体と接触平面との半接触問題の解を統合することによって、所望する２物体間の接触形状を算出することができる。
【００２０】
また、凹形状を含む物体間に形成される接触多角形を算出するときには、凸形状でない凹形状多面体を複数の凸断片に凸分解して、凹形状物体を複数の凸断片群より構成される複合体として取り扱うことにより、凸形状物体に対する効率のよいアルゴリズムを凹形状物体間の衝突判定に利用する。
【００２１】
接触する凸断片の組み合わせ毎に独立して衝突検出処理及び接触多角形算出処理をそれぞれ実行すると、凸断片単位での算出結果としては良好なシミュレーションが実行可能である。しかしながら、凹形状物体間で複数の凸断片で接触する場合などにおいて、衝突又は接触する凸断片の組み合わせ毎に独立して設定される接触平面の法線方向が一致しないことがあり、それぞれの接触多角形の各頂点に接触平面の法線方向の力を作用させると、力の作用点及び作用方向は互いに向き合うことがあり、浸透した状態が解消されず、良好なシミュレーション結果を得ることができない。
【００２２】
そこで、本発明では、浸透を解消する方向を考慮して、衝突又は接触が検出された凸断片毎の接触問題を解決することで、凸断片複合体（凹形状物体）間の浸透解消問題も解決するようにした。
【００２３】
具体的には、前記仮想接触平面決定手段は、衝突又は接触する各物体の凸包間の最近傍点又は最浸透点からなる凸包衝突代表点対を算出し、該凸包衝突代表点対の中点を通り、該凸包衝突代表点対を結ぶ直線方向を法線ベクトルとする仮想接触平面を決定する。そして、前記半接触問題解決手段は、他の凸断片と衝突又は接触している凸断片毎に該仮想接触平面との接触形状を与える半接触多角形をそれぞれ求め、前記接触多角形決定手段は、衝突又は接触している凸断片の組み合わせ毎に、半接触多角形を重ね合わせた積領域を求め、各積領域を統合して物体間の接触多角形を決定するようにする。
【００２４】
したがって、衝突又は接触が検出された凸断片のすべての組み合わせについて、衝突を解消する方向に法線ベクトルを持つ統一した仮想接触平面を用いて接触問題を解決するので、物理的根拠のある複数の接触多角形の頂点に同時に反力が作用することから、振動し難く、安定な力学シミュレーションを実行することができる。
【００２５】
凸断片複合体取得手段により取得した凸断片毎に頂点の接続関係を表した隣接頂点グラフを保持している。そして、前記半接触問題解決手段は、処理対象とする凸断片に関する隣接頂点グラフを探索して、半接触多角形内に存在する頂点集合を求め、適当な頂点を起点として、仮想セッション平面内に存在しない頂点に到達するまで隣接頂点グラフを再帰的に局所的探索し、半接触多角形内に存在する頂点集合を求める。全探索に代えて局所的探索を行なうことによって、少ない計算量で高速に半接触多角形を求めることができる。
【００２６】
ここで言う適当な起点として、処理対象とする凸断片のうち前記法線ベクトル方向に接触相手となる凸断片に最も浸透した頂点を起点に設定することができる。このような起点は、前記法線ベクトル方向又はその逆方向のサポート写像から求めることができる。
【００２７】
このようにして設定された起点から隣接頂点リストの局所探索を開始して、接触平面より接触相手となる物体側にある頂点を半接触多角形内に存在する頂点として順次抽出していけばよい。そして、既に調査済みの頂点や、接触平面より上方に存在する頂点に到達したら、それ以上は隣接頂点グラフをたどる必要はない。そのときまでに得られた、接触平面より下方にある頂点の集を半接触多角形の周上の点及びその内部の点からなる頂点集合として用いる。
【００２８】
また、上述した手順に従って隣接頂点グラフ上を探索して得られた頂点集合には、一般に、半接触多角形の内部に存在する点も含まれてしまう。そこで、前記半接触問題解決手段は、抽出された凸断片の頂点のうち、半接触多角形の内部に存在する頂点などの冗長な点を頂点集合から取り除くようにしている。例えば、半接触多角形内に存在するとして抽出された頂点集合を仮想接触平面へ正射影し、正射影した頂点群を包含する最小の凸多角形頂点集合を得るための演算を実行して、接触平面上で内部の点を含まない、半接触多角形の輪郭頂点集合を算出することができる。
【００２９】
また、多くの力学シミュレーションでは、物体が相互に浸透することがないように反力を発生させることが多い。このような非浸透型モデルを扱う場合には、各物体を球の半径（ｒ）分だけ膨張させた図形に対して衝突検出を行ない、仮想接触平面を法線ベクトル方向にオフセットさせた平面（オフセット仮想接触平面）と、凸断片との間の半接触多角形を算出し、それぞれの凸断片から得られた半接触多角形のインターセクションを求めるように構成すればよい。
【００３０】
原物体間が干渉していない場合、既存の衝突検出アルゴリズムにより、衝突代表点対として、最浸透点対の代わりに、２物体上の最近接点対を算出することができる。したがって、非浸透型モデルでは、仮想接触平面を最近接点対の中点を通り、両点を結ぶ直線方向を法線ベクトルとするように定義される。
【００３１】
ここで、オフセット量ｒの決定方法はさまざまであるが、オフセット仮想接触平面と原物体が必ず交点を有するように設定するのが好ましい。このような場合、それぞれの凸断片について半接触多角形を算出する際には、該当する物体側にｒだけ仮想接触平面をオフセットさせたオフセット仮想接触平面を設定して、上記と同様の手法によりそれぞれの凸断片について隣接頂点グラフの探索を実行することができる。
【００３２】
また、本発明の第２の側面は、接触状態にある任意形状の２物体間の接触形状を算出するための処理をコンピュータ上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、前記コンピュータに対し、
各物体を凸断片群に分解し、又は凸断片群に分解された物体の情報を入力する凸断片複合体取得手順と、
衝突又は接触する物体間において、衝突又は接触している凸断片を検出する凸断片間衝突検出手順と、
衝突又は接触する各物体の凸包の共通領域を通過する仮想接触平面を決定する仮想接触平面決定手順と、
衝突又は接触している各凸断片と該仮想接触平面との接触状態をそれぞれ個別の半接触問題として解く半接触問題解決手順と、
前記半接触問題解決手順において凸断片毎に求められた半接触問題の解を統合して、衝突又は接触する物体間の接触多角形を決定する接触多角形決定手順と、
を実行させることを特徴とするコンピュータ・プログラムである。
【００３３】
本発明の第２の側面に係るコンピュータ・プログラムは、コンピュータ・システム上で所定の処理を実現するようにコンピュータ可読形式で記述されたコンピュータ・プログラムを定義したものである。換言すれば、本発明の第２の側面に係るコンピュータ・プログラムをコンピュータ・システムにインストールすることによって、コンピュータ・システム上では協働的作用が発揮され、本発明の第１の側面に係る接触形状算出装置と同様の作用効果を得ることができる。
【発明の効果】
【００３４】
本発明に係る接触多角形算出装置によれば、凸形状物体だけでなく、凹形状を含む任意形状の物体間の干渉検出を実行することが可能となり、現実世界に存在するオブジェクトを広範に扱うことが可能になる。
【００３５】
本発明に係る接触多角形算出方法によれば、より正確な接触多角形群を求めることができる。したがって、従来の干渉検出アルゴリズムで得られていた、衝突代表点対や単一の接触多角形の頂点のみに力を作用させるのに比較して、物理的根拠のある複数の接触多角形の頂点に同時に反力が作用することから、振動し難く、安定な力学シミュレーションを実行することができる。
【００３６】
また、本発明に係る接触多角形算出方法によれば、衝突又は接触が検出された物体の全頂点を探索することなく、局所的な探索のみによって、凸断片に対し凸形状接触多角形の算出が遂行され、さらにその凸断片間衝突検出が、凸形状ベースの効率のよい干渉検出アルゴリズムから構成することができ、高速なシミュレーションが可能となる。すなわち、安定性、頑健性、高速性を兼ね備えた力学シミュレーションを実現することができる。
【００３７】
本発明に係る接触形状検出装置は、移動ロボットのように、周囲の環境との物理的接触状態が多様に変化し、その状態をリアルタイムで把握する必要のあるシステムに対して、好適に適用することができる。すなわち、画像処理やセンシング処理（レンジ・センサ）により得られた環境形状と、移動ロボット自身の３次元形状モデルに対して、本発明に係る接触形状検出処理を適用することにより、移動ロボットと環境間の複雑な接触状態を高速に求めることができ、より一般化された姿勢安定制御や、多様な環境下での動作計画の実現が可能となる。
【００３８】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施形態や添付する図面に基づくより詳細な説明によって明らかになるであろう。
【発明を実施するための最良の形態】
【００３９】
以下、図面を参照しながら本発明の実施形態について詳解する。
【００４０】
本発明は、衝突又は接触している状況下において、凸形状だけでなく凹形状を含む任意形状の物体間に形成される接触多角形を高速に求める接触多角形算出方法に関する。本発明では、物体間の接触検出には、従来の衝突検出アルゴリズムを適用することができる。ここでは、衝突検出アルゴリズムとして、ＧＪＫ（Ｇｉｌｂｅｒｔ−Ｊｏｈｎｓｏｎ−Ｋｅｅｒｔｈｉｄｉｓｔａｎｃｅ ａｌｇｏｒｉｔｈｍ）を想定する。ＧＪＫアルゴリズムは、凸形図形間距離を算出するための反復的な方法であり、衝突代表点対（最近傍点対又は最浸透点対）を、干渉検出結果として出力する。図４６には、ＧＪＫアルゴリズムの概略図を示している。図４６Ａは最近傍点算出処理であり、図４６Ｂは最浸透点算出処理を表している。同図では、簡素化のため２次元空間表現を用いているが、３次元空間においても成立することを十分理解されたい。
【００４１】
ＧＪＫアルゴリズムの詳細については、例えば、Ｇ．ｖａｎ ｄｅｎ Ｂｅｒｇｅｎ著“Ａ Ｆａｓｔ ａｎｄ Ｒｏｂｕｓｔ ＧＪＫ ｉｍｐｌｅｍｅｎｔａｔｉｏｎｆｏｒ Ｃｏｌｌｉｓｉｏｎ Ｄｅｔｅｃｔｉｏｎ ｏｆ Ｃｏｎｖｅｘ Ｏｂｊｅｃｔｓ”（Ｊｏｕｒｎａｌ ｏｆ Ｇｒａｐｈｉｃｓ Ｔｏｏｌｓ，４（２），ｐｐ．７−２５，２００１）を参照されたい。
【００４２】
但し、最近傍点と最浸透点をそれぞれ算出するアルゴリズムやその使用目的は異なる。すなわち、物体同士が浸透していない場合には最近傍点算出アルゴリズムとしてＧＪＫ  ｄｉｓｔａｎｃｅアルゴリズムが用いられ、物体同士が浸透している場合には、最浸透点算出アルゴリズムとしてＥＰＡ（Ｅｘｐａｎｄｉｎｇ  Ｐｏｌｙｔｏｐｅ  Ａｌｇｏｒｉｔｈｍ）が用いられる。本明細書では、特に断りがない限り、最近傍点や最浸透点を算出するアルゴリズムをＧＪＫアルゴリズムと総称して取り扱うことにする。
【００４３】
本発明は、凸形状だけでなく凹形状を含む任意形状の物体間の接触多角形を算出するものであるが、まず、凸形状をなす物体間に形成される接触多角形の算出方法について説明する。簡単のために、図４２に示したように、２つの立方体ＡとＢが干渉している場合において、その接触多角形（ｖ１，ｖ２，ｖ３，ｖ４）を求める方法について例示しながら説明する。
【００４４】
図１には、物体Ａ及び物体Ｂの接触部を横から見た拡大図を示している。上記の衝突検出アルゴリズムにより、接触状態にある２物体間において接触を生じている代表点対（すなわち、相互に最も浸透した点の対）Ｐａ及びＰｂが算出されているとする。本発明に係る接触形状算出方法では、この衝突代表点対に関する情報を出発点とし、接触多角形を構成するすべての頂点ｖ１、ｖ２、ｖ３、ｖ４を求める。
【００４５】
接触状態を知る第１のステップとして、物体Ａ及び物体Ｂの接触部位における法線ベクトルｎを用意する。法線ベクトルｎは、通常、衝突代表点対ＰａとＰｂを結ぶ単位ベクトルとして良く近似できることが知られており、下式（１）で求めることができる。
【００４６】
【数１】
2008040580.tif 000003
【００４７】
さらに、これら衝突代表点対Ｐａ及びＰｂ間を結ぶ線分の中点を通り、法線ベクトルをｎとする平面ＣＰを定義し、「接触平面」と呼ぶこととする。
【００４８】
２つの物体Ａと物体Ｂの接触状態を直接的に扱うと、さまざまな組合せが存在し、問題が複雑となる。そこで、物体間の接触状態を知る第２ステップとして、図２に示すように、この問題を接触平面ＣＰと一方の物体Ａの接触問題と、及び接触ＣＰと物体Ｂの接触問題という、２つの独立な問題に分割することにより、直感的に扱う際に生じる複雑な組み合わせ問題を回避し、接触状態を効率的に求める。
【００４９】
また、平面と凸形状の物体の接触状態の把握に関しては、物体の頂点のうち、平面上に存在するものをすべて調べるなどの処理により、比較的容易に接触面形状を得ることができる。すなわち、図２に示すように、物体毎に接触平面との接触面形状を与える頂点集合(ｖａ１，ｖａ２，ｖａ３，ｖａ４） 及び頂点集合（ｖｂ１，ｖｂ２，ｖｂ３，ｖｂ４）を得る原理を構成し易い。本明細書では、物体Ａ及び物体Ｂのそれぞれと接触平面ＣＰとの接触形状を与える多角形のことを「半接触多角形」と呼ぶことにする。
【００５０】
物体Ａ及び物体Ｂのそれぞれについてすべての頂点に対して接触平面上に存在するかどうか探索を行なうことにより、半接触多角形を得ることができる（例えば、Ｆｒａｎｃｏ  Ｐ．Ｐｒｅｐａｒａｔａ，Ｍｉｃｈａｅｌ  Ｉａｎ  Ｓｈａｍｏｓ，“Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｇｅｏｍｅｔｒｙ  Ａｎ  Ｉｎｔｒｏｄｕｃｔｉｏｎ”（Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ  ＧｍｂＨ＆Ｃｏ．ＫＧ．，１９９０）を参照のこと）。ところが、このように頂点の全探索を行なうと、物体の頂点数が多くなるにつれて、頂点探索に要する計算量が増大してしまう。形状が複雑になるにつれて接触多角形の算出速度が低下することは、力学シミュレーション並びらロボットの制御への応用の双方においても実時間処理の障害となるから望ましくない。
【００５１】
そこで、本実施形態では、局所的探索のみを行なうことによって、少ない計算量で高速に半接触多角形を求める方法を適用することにした。効率的に実装された衝突検出アルゴリズムＧＪＫでは、各物体の衝突代表点Ｐａ及びＰｂの情報とともに、その周辺の物体Ａ及び物体Ｂそれぞれについて頂点の接続関係を表すグラフ（すなわち、隣接頂点グラフ）を保持している。Ｐａ及びＰｂから隣接頂点グラフ上の適切な起点を算出し、ここを起点として隣接頂点グラフ上の一部のみを探索することで、半接触多角形を構成する。
【００５２】
衝突検出アルゴリズムによってそれぞれの物体から得られる代表点Ｐａ及びＰｂは、図３に示すように、必ずしも各物体Ａ、Ｂの頂点上に存在するとは限らない。このため、まず、代表点Ｐａ及びＰｂから隣接頂点グラフ上の適切な起点を算出しなければならないが。これは各物体Ａ、Ｂに対して法線ベクトルｎ（又はその逆の−ｎ）方向へのサポート写像を算出することで、その結果として、サポート・ポイントＳpを得ることができる。サポート写像とは、物体の頂点のうち、あるベクトル方向に最も遠のいた頂点（サポート・ポイント）を得る演算である。図４には、ある物体Ｒに対し矢印で示したベクトル方向へのサポート写像を得る様子を示している。図３に示した例では、法線ベクトルと逆方向への立体Ａのサポート写像は例えばｐａ１となる。また、法線ベクトル方向への立体Ｂのサポート写像は例えばｐｂ１となる。そして、サポート写像により得られたこれらの点を立体Ａ、Ｂそれぞれの隣接頂点グラフ探索の起点とすることができる。
【００５３】
サポート写像は衝突検出アルゴリズム（ＧＪＫ）内部でも用いられている。したがって、衝突検出計算の途中結果を用いることにより、上記法線ベクトル方向のサポート写像を高速に得ることができる。なお、サポート写像の算出方法自体は本発明の要旨ではないので、詳細はＧ．ｖａｎｄｅｎ Ｂｅｒｇｅｎ著“Ａ Ｆａｓｔ ａｎｄ Ｒｏｂｕｓｔ ＧＪＫ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｆｏｒ Ｃｏｌｌｉｓｉｏｎ Ｄｅｔｅｃｔｉｏｎ ｏｆ ＣｏｎｖｅｘＯｂｊｅｃｔｓ”（Ｊｏｕｒｎａｌ ｏｆ Ｇｒａｐｈｉｃｓ Ｔｏｏｌｓ，４（２），ｐｐ．７−２５，２００１）を参照されたい。
【００５４】
続いて、上記のように法線ベクトル（又はその逆）方向へのサポート写像から得られた頂点（サポート・ポイント）を起点として、物体Ａ及び物体Ｂそれぞれの隣接頂点グラフ上の探索を行なう。図５を参照しながら説明すると、まず、起点ｐａ１に対し、これが接触平面ＣＰの下方にあるかどうか調べる。下方にあれば、頂点ｐａ１は半接触多角形内に存在する点と判断することができる。ここで、ある頂点ｘがある平面（法線ベクトルｎ、ｐを通る平面）の正領域にあるか負領域にあるかは、下式（２）を用いて判定を行なうことができる。
【００５５】
【数２】
2008040580.tif 000004
【００５６】
次に、ｐａ１に隣接した頂点ｐａ２及びｐａ４についても、同様の方法で接触平面の下方に存在するかどうかを調べる。このように再帰的に隣接頂点グラフを辿りながら、接触平面と頂点との位置関係を調査していく。そして、既に調査済みの頂点や、接触平面より上方に存在する頂点に到達したら、それ以上は隣接頂点グラフを辿る必要はない。そのときまでに得られた、接触平面より下方にある頂点の集合が半接触多角形の周上の点及びその内部の点の集合を与える。
【００５７】
このように、法線ベクトル（又はその逆）方向へのサポート写像から得られた頂点を起点とした隣接頂点グラフの局所的探索によれば、隣接頂点グラフ中で接触平面より下方の頂点の調査のみ行なうことから、ごく少数の頂点の調査のみで済み、物体の頂点について全探索を行なう手法に比べて大幅な計算速度の向上を図ることができる。
【００５８】
図５に示した例では、破線以下の４つの点ｐａ１、ｐａ２、ｐａ５、ｐａ６が物体Ａと接触平面との接触形状を与える半接触多角形として最終的に得られる。また、処理対象となる物体Ａがさらに複雑な形状でｐａ３、ｐａ４、ｐａ７、ｐａ８よりも上部に頂点が存在したとしても、上述したアルゴリズムに従って適当な頂点を起点とした隣接頂点グラフの局所的探索を行なうことにより、これ以上の範囲に探索が及ぶことがないことを十分理解されたい。
【００５９】
また、もう一方の接触問題として物体Ｂと接触平面ＣＰの半接触多角形についても同様に、法線方向へのサポート写像により代表点Ｐｂに最も近い頂点ｐｂ１を求めた後、ｐｂ１を起点として接触平面より下方に存在する頂点に到達するまで再帰的に隣接頂点グラフを辿っていくことによって、接触平面ＣＰより上方にある頂点集合を局所探索のみで得ることができる。
【００６０】
上述した手順に従って隣接頂点グラフ上を探索して得られた頂点集合には、一般に、半接触多角形の内部に存在する点も含まれる。例えば、図６に示すように、物体の面としての多角形を構成する頂点ａ、ｂ、ｃ、ｄの他に、面の中心にもう１点だけ頂点ｅが設定されている場合、当該面が接触平面となるときには、上述した頂点探索の結果として得られる頂点集合は（ａ，ｂ，ｃ，ｄ，ｅ）の５点となり、半接触多角形内部の点ｅを含み、冗長なものとなる。
【００６１】
本実施形態では、物体間の接触状態を知るための第３のステップとして、このような半接触多角形内部の点を探索結果から取り除くようにしている。具体的には、半接触多角形内に存在するとして抽出された頂点集合を接触平面ＣＰへ正射影し、正射影した頂点群（ａ０，ｂ０，ｃ０，ｄ０，ｅ０）に対して２次元凸包演算を施す。ここでいう凸包演算とは、頂点集合を包含する最小の凸多角形頂点集合を得るための演算であり、Ｇｒａｈａｍ法などを用いることができる。Ｇｒａｈａｍ法については、例えば、ＲｏｎａｌｄＧｒａｈａｍ，“Ａｎ Ｅｆｆｉｃｉｅｎｔ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｄｅｔｅｒｍｉｎｉｎｇ ｔｈｅ Ｃｏｎｖｅｘ Ｈｕｌｌ ｏｆ ａ Ｆｉｎｉｔｅ ＰｌａｎａｒＳｅｔ”（Ｉｎｆｏ．Ｐｒｏｃ．Ｌｅｔｔｅｒｓ，１，ｐｐ．１３２−１３３，１９７２）を参照されたい。
【００６２】
このように半接触多角形内部の点を頂点集合から取り除く処理を行なった結果、図６に示した例では、頂点ｅ’ が取り除かれ、内部の点を含まない、半接触多角形の輪郭（ａ’，ｂ’，ｃ’，ｄ’）を得ることができる。物体Ｂと接触平面ＣＰとの間でも同様にして、接触平面上で内部の点を含まない、半接触多角形の境界頂点集合（すなわち輪郭頂点集合）を算出しておく。
【００６３】
そして、最後に、上述した手順に従って得られた、物体Ａ及び物体Ｂそれぞれの半接触多角形を接触平面上で重ね合わせ、そのオーバラップ領域（インターセクション領域、積領域）を求める。このオーバラップ領域が２物体間の接触多角形を与える。
【００６４】
図２に示した例の場合、接触平面上における物体Ａ及び物体Ｂそれぞれの半接触多角形は、図７に示すように、（ｖａ１，ｖａ２，ｖａ３，ｖａ４）、並びに（ｖｂ１，ｖｂ２，ｖｂ３，ｖｂ４）のようになる。したがって、そのオーバラップ領域は、（ｖ１，ｖ２，ｖ３，ｖ４）のようになる。
【００６５】
なお、２つの２次元多角形のオーバラップ領域を効率良く求めるには、例えば、Ｏ’Ｒｏｕｋｅ，ｅｔ．ａｌ，“Ａ ｎｅｗ ｌｉｎｅａｒ ａｌｇｏｒｉｔｈｍｆｏｒ ｉｎｔｅｒｓｅｃｔｉｎｇ ｃｏｎｖｅｘ ｐｏｌｙｇｏｎｓ”（Ｃｏｍｐｕｔ．Ｇｒａｐｈ．Ｉｍａｇｅ Ｐｒｏｃｅｓｓ．，１９，ｐｐ．３８４−３９１，１９８２）に記載されている方法を用いることができる。
【００６６】
凸形状の物体間に形成される接触多角形を高速に求める接触多角形算出方法に関しては、本出願人に既に譲渡されている特願２００５−２８９５９８号明細書にも詳解されている。
【００６７】
続いて、凹形状を含む物体間に形成される接触多角形の算出方法について説明する。
【００６８】
図８Ａ及び図８Ｂに示すような、凹形状を持つ２つの物体Ａ及び物体Ｂに関して、さまざまな接触状態を想定する。図９Ａ及び図９Ｂには、図８Ａ及び図８Ｂに示した各３次元物体の２次元表現をそれぞれ示している。
【００６９】
衝突検出を行なう物体が凸形状である場合、その判定は凹形状である場合に比し、高速に行なうことができる（例えば、非特許文献２を参照のこと）。そこで、本実施形態でも、凸形状物体に対する効率のよいアルゴリズムを凹形状物体間の衝突判定に利用する。すなわち、図８及び図９に示したような凸形状でない凹形状多面体を複数の凸断片に凸分解して、凹形状物体を複数の凸断片群より構成される複合体（以下では、「凸断片複合体」と呼ぶ）として取り扱う。すなわち、図８Ａ及び図８Ａに示した物体Ａは、図１０Ａ及び図１０Ｃに示すように、３つの凸断片Ａ１、Ａ２、Ａ３の複合体として取り扱い、図８Ｂ及び図９Ｂに示した物体Ｂは、図１０Ｂ及び図１０Ｄに示すように、２つの凸断片Ｂ１、Ｂ２の複合体として扱う。
【００７０】
なお、本発明の要旨は、特定の凸分解アルゴリズムに限定されるものではない。凸分解アルゴリズムの詳細に関しては、例えば、Ｂｅｌｏｖ，Ｇｌｅｂ，“Ａ  Ｍｏｄｉｆｉｅｄ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｃｏｎｖｅｘ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｏｆ  ３Ｄ  Ｐｏｌｙｈｅｄｒａ”（Ｔｅｃｈｎｉｃａｌ  ｒｅｐｏｒｔ  ＭＡＴＨ−ＮＭ−０３−２００２，Ｉｎｓｔｉｔｕｔｅ  ｆｏｒ  Ｎｕｍｅｒｉｓｃｈｅ  Ｍａｔｈｅｍａｔｉｋ，Ｔｅｃｈｎｉｃｈｅ  Ｕｎｉｖｅｒｓｉｔａｔ，Ｄｒｅｓｄｅｎ．Ｍａｒｃｈ  ２００２）、Ｌｕ，Ｙｏｕｇ．ＲａｊｉｔＧｄｈ，“Ｃｏｎｓｔｒａｉｎｅｄ  ａｎｄ  Ａｇｇｒｅｇａｔｅｄ  Ｈａｌｆ  Ｓｐａｃｅ  Ｖｏｌｕｍｅ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ：Ｇｅｎｅｒａｔｉｎｇ  Ｃｕｔｔｉｎｇ  Ｐａｔｃｈｅｓ  ｗｉｔｈ  ‘Ｉｎｔｅｒｎａｌ’  ａｎｄ  ‘Ｅｘｔｅｒｎａｌ’  Ｅｘｔｅｎｄｉｎｇ”（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｅｉｇｈｔｈ  Ｐａｃｉｆｉｃ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ（ＰＧ  ００），ｐｐ．２６２−２７１，２０００），Ｓｔａｐｈｅｎ  Ａ．Ｅｈｍａｎｎ  ａｎｄ  Ｍｉｎｇ  Ｃ．Ｌｉｎ，“Ａｃｃｕｒａｔｅ  ａｎｄ  Ｆａｓｔ  Ｐｒｏｘｉｍｉｔｙ  Ｑｕｅｒｕｅｓ  Ｂｅｔｗｅｅｎ  Ｐｏｌｙｈｅｄｒａ  Ｕｓｉｎｇ  Ｃｏｎｖｅｘ  Ｓｕｒｆａｃｅ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ”（ＥＵＲＯＧＲＡＰＨＩＣＳ  ２００１）などを参照されたい。
【００７１】
実際の凹形状多面体の凸分解アルゴリズムは、非常に計算負荷が高く、力学シミュレーション中のリアルタイム実行は困難である。そこで、シミュレーションを行なう前の前処理として、移動ロボットや環境下に存在する凹形状物体について凸分解を実施し、得られた凸断片の面、線、頂点といった形状データや凸断片間の接続情報などの計算結果を所定のファイル形式で保持しておき、シミュレーション実行時に適宜ファイルを読み込むという形態をとるようにしてもよい。
【００７２】
ここで、物体Ａと物体Ｂが図１１に示すような具合で衝突を起こしている場合について考察する。上述したように、物体ＡをＡ１〜Ａ３からなる凸断片複合体、物体ＢをＢ１〜Ｂ２からなる凸断片複合体として取り扱う場合、凸断片Ａ１とＢ１間で衝突を起こしている。この場合、図１２に示すように、凸断片Ａ１とＢ１間における上述した干渉検出処理（接触多角形算出処理）のみを行なえばよい。すなわち、第１のステップとして、物体Ａと物体Ｂの接触部位における接触平面ＣＰを算出する。まず、接触状態にある凸断片Ａ１と凸断片Ｂ１の衝突代表点Ｐａ及びＰｂを衝突検出アルゴリズムにより算出し、衝突代表点Ｐａ及びＰｂを結ぶ法線ベクトルｎを求める。そして、法線ベクトルｎを法線とし、衝突代表点Ｐａ及びＰｂの中点を通る接触平面ＣＰを求める。
【００７３】
続く第２のステップとして、接触平面ＣＰと凸断片Ａ１、及び、接触平面ＣＰと凸断片Ｂ１の接触問題という２つの独立な問題に分割し、それぞれにおいて接触形状を与える頂点集合｛ＶA1_1，ＶA1_2｝、及び｛ＶB1_1，ＶB1_2｝からなる半接触多角形を算出する。図１３Ａ及び図１３Ｂには、局所的探索により得られた、接触平面ＣＰの正領域に存在する｛ＶA1_1，ＶA1_2｝及び｛ＶB1_1，ＶB1_2｝をそれぞれ示している。
【００７４】
続く第３のステップとして、半接触多角形内に存在するとして抽出された各頂点集合｛ＶA1_1，ＶA1_2｝、｛ＶB1_1，ＶB1_2｝を接触平面ＣＰへ正射影し、正射影した頂点群に対して、Ｇｒａｈａｍ法などを用いて２次元凸包演算を施して、頂点集合を包含する最小の凸多角形頂点集合を得る。図１４Ａ及びＢには、図１３Ａ及びＢに示した頂点集合｛ＶA1_1，ＶA1_2｝及び｛ＶB1_1，ＶB1_2｝を接触平面ＣＰに正射影した頂点群｛ＰA1_1，ＰA1_2｝及び｛ＰB1_1，ＰB1_2｝をそれぞれ示している。接触平面ＣＰに正射影された頂点群｛ＰA1_1，ＰA1_2｝及び｛ＰB1_1，ＰB1_2｝に２次元凸包演算を施して、半接触多角形の境界頂点集合（すなわち輪郭頂点集合）を得ることができる。
【００７５】
そして、最後のステップとして、これまでの処理により得られた各凸断片Ａ１及びＢ１それぞれの半接触多角形を接触平面ＣＰ上で重ね合わせ、そのオーバラップ領域（インターセクション領域、積領域）を求める。このオーバラップ領域がこれら凸断片間の接触多角形を与える。図１５には、図１４Ａ及び図１４Ｂにそれぞれ示した半接触多角形の積領域をとって求められた接触多角形を示している。図示の例では、図１４Ｂに示した輪郭頂点集合｛ＰB1_1，ＰB1_2｝が、凸断片Ａ１及びＢ１、すなわち物体Ａと物体Ｂ間の接触多角形となる。
【００７６】
上記で算出した接触多角形の各頂点に力（例えば、接触に対する反力又は復元力）を作用させることにより（図１６Ａを参照のこと）、物体Ａと物体Ｂの接触に伴う物理的相互作用における良好な力学シミュレーションを実行することができる（図１６Ｂを参照のこと）。
【００７７】
これまでは、物体Ａと物体Ｂがそれぞれ１つの凸断片で接触する例について接触多角形の算出処理について説明してきたが、次に、図１７に示すように凹形状物体間で複数の凸断片で接触する場合について考察する。同図に示す例では、凸断片Ｂ２と凸断片Ａ１、及び、凸断片Ｂ２と凸断片Ａ３で衝突を起こしている。
【００７８】
まず、上述した例と同様に、接触する凸断片の組み合わせ毎に独立して衝突検出処理及び接触多角形算出処理をそれぞれ実行することにする。
【００７９】
この場合、第１のステップでは、凸断片Ｂ２と凸断片Ａ１の衝突検出処理により衝突代表点対｛ＰA1，ＰB2_1｝が求められ、これに基づいて接触平面ＣＰ1が算出される（図１８Ａを参照のこと）。同様に、凸断片Ｂ２と凸断片Ａ３の衝突検出処理により衝突代表点対｛ＰA3，ＰB2_1｝が求められ、これに基づいて接触平面ＣＰ2が算出される（図１８Ｂを参照のこと）。
【００８０】
続く第２のステップでは、接触平面ＣＰ1を判定条件に用い、凸断片Ａ１及び凸断片Ｂ２の接触問題をそれぞれ独立して解いて、それぞれにおいて接触形状を与える頂点集合｛ＶA1_1，ＶA1_2｝及び｛ＶB2_3，ＶB2_4｝からなる半接触多角形を算出する（図１９Ａ及び図１９Ｂを参照のこと）。同様に、接触平面ＣＰ1を判定条件に用い、凸断片Ａ３及び凸断片Ｂ２の接触問題をそれぞれ独立して解いて、それぞれにおいて接触形状を与える頂点集合｛ＶA3_1，ＶA3_2｝及び｛ＶB2_1，ＶB2_2｝からなる半接触多角形を算出する（図２０Ａ及び図２０Ｂを参照のこと）。
【００８１】
続く第３のステップでは、半接触多角形内に存在するとして抽出された各頂点集合｛ＶA1_1，ＶA1_2｝及び｛ＶB2_3，ＶB2_4｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して、半接触多角形の境界頂点集合｛ＰA1_1，ＰA1_2｝及び｛ＰB2_3，ＰB2_4｝を得る（図２１Ａ及び図２１Ｂを参照のこと）。同様に、半接触多角形内に存在するとして抽出された各頂点集合｛ＶA3_1，ＶA3_2｝及び｛ＶB2_1，ＶB2_1｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して、半接触多角形の境界頂点集合｛ＰA3_1，ＰA3_2｝及び｛ＰB2_1，ＰB2_2｝を得る（図２２Ａ及び図２２Ｂを参照のこと）。
【００８２】
そして、最後のステップでは、各凸断片Ａ１及びＢ２それぞれの半接触多角形を接触平面ＣＰ1上で重ね合わせて、そのオーバラップ領域を求めるとともに（図２３を参照のこと）、各凸断片Ａ３及びＢ２それぞれの半接触多角形を接触平面ＣＰ2上で重ね合わせて、そのオーバラップ領域を求める（図２４を参照のこと）。
【００８３】
図２３及び図２４に示したような接触多角形は、凸断片単位での算出結果としては良好なシミュレーションが実行可能であるが、凸断片複合体、すなわち元の物体Ａと物体Ｂとしてシミュレーションを行なうには問題がある。
【００８４】
図２５Ａに示すように、凸断片Ａ１と凸断片Ｂ２、凸断片Ａ３と凸断片Ｂ２の接触多角形の各頂点に接触平面の法線方向の力を作用させると、力の作用点及び作用方向は互いに向き合うため、物体Ａと物体Ｂの浸透が解消されることになる。これは期待に反した結果であり、図２５Ｂに示すような状態に陥り、物体Ｂが物体Ａのなすコの字内側に浸透した状態が解消されないままとなり、あるいは最悪の場合には、振動が発生し、良好なシミュレーション結果を得ることができない。このような結果は、凸断片複合体（凹形状物体）間の浸透解消問題において、浸透を解消する方向を考慮していないことに依拠する。
【００８５】
そこで、本発明者は、凹形状物体を含む衝突検出問題を扱う際における、物体間の浸透解消の定義を、凸形状物体間の衝突検出問題で用いられるものとは別に、新たに定義し直す必要がある、と思料する。
【００８６】
一般に、凸形状物体間の衝突検出問題では、幾何学的な物体間の浸透の解消（浸透深度、貫通深度）は、以下のように定義される（例えば、Ｇｉｎｏ  ｖａｎ  ｄｅｎ  Ｂｅｒｇｅｎ，“Ｃｏｌｌｉｓｉｏｎ  Ｄｅｔｅｃｔｉｏｎ  ｉｎ    Ｉｎｔｅｒａｃｔｉｖｅ  ３Ｄ  Ｅｎｖｉｒｏｎｍｅｎｔｓ”（Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ  Ｐｕｂｌｉｓｈｅｒｓ，２００３）を参照のこと）。
【００８７】
《定義》浸透深度（貫通深度）
凸形状物体間の浸透をキャンセルするのに必要とされる、大域的な最小ベクトル。但し、φは空集合を現す。
【００８８】
【数３】
2008040580.tif 000005
【００８９】
これに対し、本実施形態では、衝突検出対象である物体Ａ及び物体Ｂを凸形状物体に限定することなく、凹形状物体に関しても適用可能な定義を導入する。
【００９０】
《定義》
凹形状を含めた任意形状物体間の浸透をキャンセルするのに必要とされる、大域的な最小ベクトル。但し、ｃｏｎｖ（・）は、物体Ａの点集合の凸包（Ｃｏｎｖｅｘ  Ｈｕｌｌ）を表す。
【００９１】
【数４】
2008040580.tif 000006
【００９２】
本明細書では、上式（４）のベクトルｄを「仮想浸透深度ベクトル」（若しくは「仮想貫通深度ベクトル」）と呼ぶことにする。この仮想浸透深度ベクトルを用いて浸透を解消する適当な方向を設定して、凹形状物体間の浸透を解消することができる。
【００９３】
ここで、図１７に示したような、凹形状物体間で複数の凸断片で接触する場合について、再び考察する。凸断片Ｂ２と凸断片Ａ１、及び、凸断片Ｂ２と凸断片Ａ３で衝突を起こしている。
【００９４】
まず、凸断片Ｂ２と凸断片Ａ１の衝突検出処理と、凸断片Ｂ２と凸断片Ａ３の衝突検出処理を実行する。これと同時に、凹形状物体Ａ及びＢについてそれぞれ凸包Ａ及び凸包Ｂを求め（図２６を参照のこと）、凸包Ａと凸包Ｂについての干渉検出問題を取り扱い、凸包Ａと凸包Ｂ間の衝突代表点対｛Ｐa，Ｐb｝を算出する。そして、第１のステップとして、衝突代表点対｛Ｐa，Ｐb｝の中点を通り、且つ上式（１）で表される法線ベクトルを法線とする平面を「仮想接触平面」として決定する（図２７を参照のこと）。
【００９５】
続く第２のステップでは、この仮想接触平面を、凸断片Ｂ２と凸断片Ａ１、並びに凸断片Ｂ２と凸断片Ａ３における接触平面に設定して、上式（２）に示した判定条件の下で、頂点探索を行なう。この頂点探索を行なうに際し、その探索の基点として、凸包間衝突問題で算出した衝突代表点対｛Ｐa，Ｐb｝と上式（１）より算出したベクトルｎに関するサポート写像の結果（サポート・ポインタ）を用い、局所的な頂点探索を行なう。
【００９６】
図２８Ａ及び図２８Ｂには、凸断片Ａ１及び凸断片Ｂ２において、サポート・ポイントを用いて局所的頂点探索処理を行なう様子を示している。ここでは、半接触多角形の形状を与える頂点集合｛ＶA1_1，ＶA1_2｝及び｛ＶB2_3，ＶB2_4｝が算出される。また、図２９Ａ及び図２９Ｂには、凸断片Ａ３及び凸断片Ｂ２において、サポート・ポイントを用いて局所的頂点探索処理を行なう様子を示している。ここでは、半接触多角形の形状を与える頂点集合｛ＶA3_1，ＶA3_2｝及び｛ＶB2_1，ＶB2_2｝が算出される。
【００９７】
なお、説明の便宜上、凸断片Ｂ２において半接触多角形ＶB2_3，ＶB2_4｝及び｛ＶB2_1，ＶB2_2｝が算出されるとしたが、判定条件に用いる接触平面は同じであることから、これらは同一の半接触多角形を表す。したがって、実際の処理では、１つの凸断片について重複して半接触多角形の算出を行なう必要はない。
【００９８】
続く第３のステップでは、これら半接触多角形の頂点集合を、第２のステップで設定した仮想接触平面へ正射影し、正射影した頂点集合に対して２次元凸包演算を施す。この結果、図３０Ａ及び図３０Ｂ、並びに図３１Ａ及び図３１Ｂに示すような境界頂点集合｛ＰA1_1，ＰA1_2｝、｛ＰB2_3，ＰB2_4｝、｛ＰA3_1，ＰA3_2｝、｛ＰB2_1，ＰB2_2｝を得ることができる。
【００９９】
そして、最後のステップでは、凸断片Ａ１と凸断片Ｂ２間、及び凸断片Ａ３と凸断片Ｂ２間でそれぞれ求められたこれら半接触多角形の境界頂点集合を仮想接触平面上で重ね合わせる。この結果、凸断片Ａ１と凸断片Ｂ２間、及び凸断片Ａ３と凸断片Ｂ２間で、それぞれ図３２及び図３３に示すオーバラップ領域｛ＰB2_3，ＰA1_2｝及び｛ＰA3_1，ＰB2_2｝を得ることができる。
【０１００】
このようにして求めた凸断片毎の接触多角形の境界頂点に対し、図３４Ａに示すように、力を作用させる。すると、図３４Ｂに示すように、凸断片複合体を含む物体間の浸透問題（幾何学的な物体間浸透問題）は解決され、期待した良好なシミュレーション結果を得ることができる。
【０１０１】
図３５には、凹形状を含む任意形状の物体間に形成される接触多角形群を算出する接触形状算出装置の機能的構成を模式的に示している。図示の接触形状算出装置１は、座標系設定部１０と、干渉検出部２０を備えている。
【０１０２】
座標系設定部１０は、各物体の運動を決定する手段であり、例えば、力学シミュレーション・エンジンなどで構成される。
【０１０３】
干渉検出部２０は、シーンデータ蓄積部２１と、計算幾何学演算部２２と、凸包間干渉検出部２３と、凸断片間干渉検出部２４と、接触平面決定部２５と、凸断片間接触多角形決定部２６で構成される。
【０１０４】
シーンデータ蓄積部２１は、仮想環境に存在するすべての物体に関し、各物体上に設定された座標系のワールド座標系内での位置・姿勢（座標情報）と、その形状に関する情報を保持している。形状データとしては、頂点や面などに関する３次元形状モデル、凸断片複合体の凸包を構成する頂点がどの頂点と接続されているかを示し、且つ、頂点探索を高速に行なうためのデータ構造として、凸包隣接頂点グラフ（３次元凸包形状モデル）、各凸断片それぞれを構成する頂点の接続関係を記述するための隣接頂点グラフ、凸断片複合体を構成する凸断片群リストが保持される。座標系情報は、各物体の運動を決定する外部の座標系決定部１０によって、必要に応じて書き換えられる。
【０１０５】
計算幾何学演算部２２は、ＧＪＫアルゴリズム実行部２２Ａと、サポート写像実行部２２Ｂを備えている。
【０１０６】
サポート写像実行部２２Ｂは、図４に示したように、任意の物体の頂点のうち、あるベクトル方向に最も遠のく点を算出する、計算幾何学における基本演算を実行する。
【０１０７】
ＧＪＫアルゴリズム実行部２２Ａは、干渉検出処理を行なうにあたり必要となるコア演算を実行する。
【０１０８】
計算幾何学演算部２２では、サポート写像実行部２２Ｂにより繰り返されるサポート写像を繰り返し用い、シーンデータ蓄積部２１内の物体の接触・衝突を起こした物体のペアに対して衝突判定を行なうとともに、衝突代表点（ＥＰＡアルゴリズムより最浸透点、若しくはＧＪＫ  ｄｉｓｔａｎｃｅアルゴリズムより最近傍点）の算出を行なう。
【０１０９】
凸包間干渉検出部２３は、シーンデータ蓄積部２１内の座標系情報と３次元凸包形状モデルを基に、計算幾何学演算部２２における基本演算の結果を用いて、凸断片複合体（物体のオリジナル形状の凸包）間の衝突検出を行ない、その衝突検出の結果として、仮想衝突代表点対を出力する。
【０１１０】
凸断片間干渉検出部２４は、ＧＪＫアルゴリズムに従って衝突判定処理を行なって、凸断片同士が衝突しているか否かを判定し、各物体間の衝突凸断片対リストを結果として出力する。また、衝突代表点対リストも出力するように構成してもよい。
【０１１１】
接触平面決定部２５は、凸包間干渉検出部２３より得られた仮想衝突代表点対から、その衝突代表点を結ぶベクトルを法線とし、且つ、代表点対の中点を通る平面を算出して、仮想接触平面を求める。この仮想接触平面が、２物体間の衝突を起こしているすべての凸断片対についての接触平面として設定される。
【０１１２】
凸断片間接触多角形決定部２６は、探索起点決定部２６Ａと、頂点探索実行部２６Ｂと、半接触多角形決定部２６Ｃと、接触多角形決定部２６Ｄで構成される。
【０１１３】
探索起点決定部２６Ａは、衝突を起こした２物体（凸断片対）それぞれの半接触多角形を求める衝突探索処理の準備として、その探索起点となる頂点を求める。探索起点には、各凸断片の接触平面の法線方向（若しくはその逆方向）へのサポート写像の結果、すなわち、サポート・ポイントを用いる。
【０１１４】
頂点探索実行部２６Ｂは、探索起点決定部２６Ａで求めた探索起点を起点として、シーングラフの物体情報である隣接頂点グラフを用い、接触平面よりも接触相手物体側に存在する頂点集合を、高速な局所的探索により求める。
【０１１５】
半接触多角形決定部２６Ｃは、頂点探索実行部２６Ｂより得られた頂点集合を、接触平面の境界頂点集合（輪郭形状）を抽出することで、２物体（凸断片）間それぞれの半接触多角形を決定する。
【０１１６】
接触多角形決定部２６Ｄは、半接触多角形決定部２６Ｃで算出した、凸断片間各々の半接触多角形を接触平面上で重ね合わせ、そのインターセクション領域を求める。このようにして得られた接触平面上のインターセクション領域（積領域）を接触多角形として出力する。
【０１１７】
接触形状算出装置１は、衝突検出の結果として、すべての衝突に関する衝突代表点対リストとともに、接触多角形リストを出力する。衝突を起こしたすべての物体の組み合わせ、及び衝突を起こしたすべての凸断片対に対して、各機能モジュール２２〜２６による処理手順を実行することで、シーンデータ蓄積部２１内で発生したすべての物体間衝突に関して接触多角形を得ることができる。
【０１１８】
図３６には、接触形状算出装置１で実行される接触多角形決定処理の手順をフローチャートの形式で示している。
【０１１９】
まず、座標系設定ステップ（Ｓ１）では、シーンデータ蓄積部２１内の書く物体の位置・姿勢情報を設定する。座標系設定部１０は、例えば、力学シミュレーション・エンジンで構成され、各物体の運動を決定する。
【０１２０】
続く仮想接触平面決定ステップ（Ｓ２）では、後続の凸断片間接触多角形決定ステップで用いられる仮想接触平面を決定する。
【０１２１】
そして、凸断片間接触多角形決定ステップ（Ｓ３）では、仮想接触平面決定ステップで決定した仮想接触平面を基に、各凸断片間の接触平面を決定し、各凸断片間の接触多角形を決定する。
【０１２２】
図３７には、ステップＳ２で実行される仮想接触平面決定処理の詳細な手順をフローチャートの形式で示している。
【０１２３】
凸断片間干渉検出ステップ（Ｓ１１）では、計算幾何学演算部２２内のＧＪＫアルゴリズム実行部２２Ａにより、シーンデータ蓄積部２１内で接触又は衝突を起こした物体の組み合わせ、及び凸断片の組み合わせをすべて求める。また、ここで、各凸断片対に対して衝突代表点対（最も浸透した点の組、若しくは最も近接した点の組）を求めておいてもよい。
【０１２４】
凸包間干渉検出ステップ（Ｓ１２）では、先行する凸断片間干渉検出ステップで求めた、凸断片複合体の凸包形状間の干渉検出処理を、計算幾何学演算部２２Ｂ内のＧＪＫアルゴリズム実行部２２Ａにより実行し、シーンデータ蓄積部２１内で接触又は衝突を起こした物体（凸断片複合体）に対して、衝突代表点対（最も浸透した点の組、若しくは最も近接した点の組）を求める。
【０１２５】
そして、仮想接触平面決定ステップ（Ｓ１３）では、先行する凸包間干渉検出ステップで求めた、衝突代表点対を基に、その衝突代表点を結ぶベクトルを法線ベクトルとし、且つ、代表点の中点を通る平面の方程式を求める。求めた平面を仮想接触平面として出力する。
【０１２６】
図３８には、図３６で示したフローチャートのステップＳ３で実行される凸断片間接触多角形決定処理の詳細な手順をフローチャートの形式で示している。
【０１２７】
まず、凸断片複合体間において、接触又は衝突した状態にある凸断片対が存在するかどうかを判定する（Ｓ２１）。接触又は衝突状態にある凸断片対が存在する場合には、後続のステップＳ２２に進むが、存在しない場合には、それまでに求めた凸断片間の接触多角形の組を凸断片間接触多角形決定処理の結果として出力し、本処理ルーチンを終了する。
【０１２８】
探索起点決定ステップ（Ｓ２２）では、凸断片の隣接頂点グラフの探索起点を求める。探索起点は、図３６に示したフローチャートの仮想接触平面決定ステップ（Ｓ１３）で求めた仮想接触平面を接触平面に設定し、その接触平面の法線方向（若しくはその逆方向）へのサポート写像の結果（サポート・ポイント）とする。
【０１２９】
続く頂点探索実行ステップ（Ｓ２３）では、先行する探索起点決定ステップで設定したサポート・ポイントを探索の起点として、凸断片の隣接頂点グラフを局所的に探索し、接触平面よりも衝突相手（対をなす他方の凸断片）側に存在する頂点集合を求める。
【０１３０】
続く半接触多角形決定ステップ（Ｓ２４）では、先行する頂点探索実行ステップで探索した、接触平面よりも衝突相手側に存在する頂点集合を接触平面飢えに正射影し、その平面上で２次元凸包演算を施し、その輪郭形状を境界頂点集合として抽出して、半接触多角形を計算する。
【０１３１】
そして、接触多角形決定ステップ（Ｓ２５）では、先行する半接触多角形決定ステップで算出した、それぞれの凸断片対の半接触多角形対のインターセクション領域（積領域）を求め、これを接触多角形として出力する。
【０１３２】
図３９には、図３８に示したフローチャートのステップＳ２２〜Ｓ２４で実行される、各凸断片の局所探索処理の詳細な手順をフローチャートの形式で示している。
【０１３３】
まず、ステップＳ２１における探索起点決定ステップにより決定された探索起点を、凸断片間接触多角形処理の起点に設定し（Ｓ３１）、起点とした頂点に探索済みフラグを立てるとともに（Ｓ３２）、候補点リストに追加する（Ｓ３３）。
【０１３４】
次いで、上式（２）を用いて、探索対象点が接触平面に対し、接触相手物体側に存在するか否かを判定する（Ｓ３４）。
【０１３５】
探索対象点が接触平面に対し、接触相手物体側に存在する場合には（Ｓ３４のＹｅｓ）、さらに、現在探索中の頂点に隣接する頂点が存在するか否かを、隣接頂点グラフを基に探索する（Ｓ３５）。
【０１３６】
現在探索中の頂点に隣接する頂点が存在する場合には（Ｓ３５のＹｅｓ）、探索対象となる頂点を、現在の頂点からステップＳ３５で検出された新しい頂点に変更する（Ｓ３６）。そして、別途定義した頂点調査処理を実行してから（Ｓ３７）、ステップＳ３５に戻る。
【０１３７】
一方、探索対象点が接触平面に対し接触相手物体側に存在しない場合（Ｓ３４のＮｏ）、又は、現在探索中の頂点に隣接する頂点が存在しない場合には（Ｓ３５のＮｏ）、候補点を接触平面へ正射影し（Ｓ３８）、セッション平面に正射影された頂点群に２次元凸包演算を施して、半接触多角形の境界頂点集合（すなわち輪郭頂点集合）を得る（Ｓ３９）。
【０１３８】
図４０には、図３９で示したフローチャートのステップＳ３７で実行される頂点調査処理の詳細な手順をフローチャートの形式で示している。
【０１３９】
まず、調査対象の頂点が探索済み、すなわち探索済みフラグが立てられているかどうかを確認する（Ｓ４１）。探索済みであれば、Ｓ３７に戻る。
【０１４０】
一方、当該頂点が探索済みでない場合には（Ｓ４１のＮｏ）、探索済みフラグを立てる（Ｓ４２）。
【０１４１】
次いで、ステップＳ３４と同様に、上式（２）を用いて、探索対象点が接触平面に対し、接触相手物体側に存在するか否かを判定する（Ｓ４３）。接触相手物体側に存在しない場合は、Ｓ３７に戻る。
【０１４２】
一方、探索対象点が接触平面に対し、接触相手物体側に存在する場合には（Ｓ４３のＹｅｓ）、現在調査中の頂点を候補リストに追加する（Ｓ４４）。
【０１４３】
次いで、現在探索中の頂点に隣接する頂点が存在するか否かを、隣接頂点グラフを基に探索する（Ｓ４５）。現在探索中の頂点に隣接する頂点が存在しない場合は、Ｓ３７に戻る。
【０１４４】
一方、現在探索中の頂点に隣接する頂点が存在する場合には（Ｓ４５のＹｅｓ）、探索対象となる頂点を、現在の頂点からステップＳ４５で検出された新しい頂点に変更する（Ｓ４６）。そして、この新しい頂点に関しても、当該頂点調査処理を再帰的に実行する。
【０１４５】
これまでは、衝突を起こす物体相互に浸透が発生した場合に対して接触多角形を算出する方法について説明してきた。しかし、実世界同様に、多くの力学シミュレーションでは、物体が相互に浸透することがないように、反力を作用させる。これは、主に効率の面からの対応でもある。
【０１４６】
物体が相互に浸透することがないように反力を発生させる場合、図４１に示すように、各物体の凸包形状と球のＭｉｎｋｗｓｋｙ和、すなわち、物体の凸包を球の半径のｒ分だけ膨張させた図形に対して干渉検出を行ない、仮想接触平面を求め、仮想接触平面を法線ベクトル方向にオフセットさせた平面（すなわちオフセット仮想接触平面）を定義する。そして、このオフセット仮想接触平面と、膨張前の原物体の形状、すなわち凸断片との間の半接触多角形を算出し、インターセクションを求めるように構成する。
【０１４７】
原物体間が干渉を起こしていない場合、衝突検出アルゴリズムであるＧＪＫアルゴリズムでは、衝突代表点対として２物体間の最近棒点を算出する。したがって、非浸透型モデルでは、仮想接触平面は、最近傍点対の中点を通り、両点を結ぶ方向を法線ベクトルとするように定める。
【０１４８】
仮想接触平面のオフセット量の決定方法はさまざまであるが、オフセット仮想接触平面と原物体が必ず交点を有するように設定することが好ましい。例えば、物体Ａ（凸断片Ａ１）との半接触多角形を算出する際には、物体Ａ側のＭｉｎｋｏｗｓｋｙ和をとる球の半径ｒだけオフセットさせた仮想接触平面を考える。また、物体Ｂ（凸断片Ｂ２）との半接触多角形を算出する際には、逆方向にｒだけオフセットさせた平面を考えればよい。上式（２）の判定を、これらのオフセット仮想接触平面と原物体（凸断片）の頂点間で実行するように、隣接頂点グラフの探索を実行する。
【０１４９】
探索起点となる頂点の選定や、２次元凸包演算による半接触多角形内部の点の諸居、インターセクション演算による半接触多角形共通領域の算出など、その他の処理に関しては、浸透型モデルの場合と同一の手順で実行すればよい。
【産業上の利用可能性】
【０１５０】
以上、特定の実施形態を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施形態の修正や代用を成し得ることは自明である。
【０１５１】
本発明に係る接触形状検出装置は、移動ロボットのように、周囲の環境との物理的接触状態が多様に変化し、その状態をリアルタイムで把握する必要のあるシステムに対して、好適に適用することができる。すなわち、画像処理やセンシング処理（レンジ・センサ）により得られた環境形状と、移動ロボット自身の３次元形状モデルに対して、本発明に係る接触形状検出処理を適用することにより、移動ロボットと環境間の複雑な接触状態を高速に求めることができ、より一般化された姿勢安定制御や、多様な環境下出の動作計画の実現が可能となる。
【０１５２】
要するに、例示という形態で本発明を開示してきたのであり、本明細書の記載内容を限定的に解釈するべきではない。本発明の要旨を判断するためには、特許請求の範囲を参酌すべきである。
【図面の簡単な説明】
【０１５３】
【図１】図１は、立体Ａ及びＢの接触部を横から見た拡大図である。
【図２】図２は、立体Ａ及びＢ間の接触問題を接触平面ＣＰと一方の立体Ａの接触問題と、及び接触ＣＰと立体Ｂの接触問題に分割した様子を示した図である。
【図３】図３は、衝突検出アルゴリズムによってそれぞれの立体から得られる代表点Ｐａ及びＰｂを示した図である。
【図４】図４は、ある立体Ｒに対し矢印で示したベクトル方向へのサポート写像を得る様子を示した図である。
【図５】図５は、適当な頂点を起点として隣接頂点グラフを局所探索し、立体Ａと接触平面との最終的な半接触多角形を得た様子を示した図である。
【図６】図６は、立方体の面面の中心に頂点が設定され、頂点探索の結果として含まれる様子を示した図である。
【図７】図７は、接触平面上における立体Ａ及びＢそれぞれの半接触多角形からオーバラップ領域を求める様子を示した図である。
【図８Ａ】図８Ａは、凹形状を持つ物体Ａの斜視図である。
【図８Ｂ】図８Ｂは、凹形状を持つ物体Ｂの斜視図である。
【図９Ａ】図９Ａは、凹形状を持つ物体Ａの平面図である。
【図９Ｂ】図９Ｂは、凹形状を持つ物体Ｂの平面図である。
【図１０Ａ】図１０Ａは、凹形状を持つ物体Ａを凸断片群に凸分解した様子を示した図である。
【図１０Ｂ】図１０Ｂは、凹形状を持つ物体Ｂを凸断片群に凸分解した様子を示した図である。
【図１０Ｃ】図１０Ｃは、凹形状を持つ物体Ａを凸断片群に凸分解した様子を示した図である。
【図１０Ｄ】図１０Ｄは、凹形状を持つ物体Ｂを凸断片群に凸分解した様子を示した図である。
【図１１】図１１は、物体Ａと物体Ｂが衝突を起こしている様子を示した図である。
【図１２】図１２は、物体Ａと物体Ｂが図１１に示すように衝突を起こしているときの干渉検出処理方法を説明するための図である。
【図１３Ａ】図１３Ａは、局所的探索により得られた、接触平面ＣＰの正領域に存在する｛ＶA1_1，ＶA1_2｝を示した図である。
【図１３Ｂ】図１３Ｂは、局所的探索により得られた、接触平面ＣＰの正領域に存在する｛ＶB1_1，ＶB1_2｝を示した図である。
【図１４Ａ】図１４Ａは、図１３Ａに示した頂点集合｛ＶA1_1，ＶA1_2｝を接触平面ＣＰに正射影して得られた頂点群｛ＰA1_1，ＰA1_2｝を示した図である。
【図１４Ｂ】図１４Ｂは、図１３Ｂに示した頂点集合｛ＶB1_1，ＶB1_2｝を接触平面ＣＰに正射影して得られた頂点群｛ＰB1_1，ＰB1_2｝を示した図である。
【図１５】図１５は、図１４Ａ及び図１４Ｂにそれぞれ示した半接触多角形の積領域をとって求められた接触多角形を示した図である。
【図１６Ａ】図１６Ａは、図１５に示した接触多角形の各頂点に力を作用させる様子を示した図である。
【図１６Ｂ】図１６Ｂは、図１５に示した接触多角形の各頂点に力を作用させて、物体Ａと物体Ｂの接触に伴う物理的相互作用における力学シミュレーションを実行する様子を示した図である。
【図１７】図１７は、物体Ａと物体Ｂが複数の凸断片で接触する様子を示した図である。
【図１８Ａ】図１８Ａは、凸断片Ｂ２と凸断片Ａ１の衝突検出処理により求められた衝突代表点対｛ＰA1，ＰB2_1｝及び接触平面ＣＰ1を示した図である。
【図１８Ｂ】図１８Ｂは、凸断片Ｂ２と凸断片Ａ３の衝突検出処理により求められた衝突代表点対｛ＰA3，ＰB2_1｝及び接触平面ＣＰ2を示した図である。
【図１９Ａ】図１９Ａは、局所的探索により得られた、接触平面ＣＰ1の正領域に存在する｛ＶA1_1，ＶA1_2｝を示した図である。
【図１９Ｂ】図１９Ｂは、局所的探索により得られた、接触平面ＣＰ1の正領域に存在する｛ＶB2_3，ＶB2_4｝を示した図である。
【図２０Ａ】図２０Ａは、局所的探索により得られた、接触平面ＣＰ2の正領域に存在する｛ＶA3_1，ＶA3_2｝を示した図である。
【図２０Ｂ】図２０Ｂは、局所的探索により得られた、接触平面ＣＰ2の正領域に存在する｛ＶB2_1，ＶB2_2｝を示した図である。
【図２１Ａ】図２１Ａは、図２０Ａに示した頂点集合｛ＶA1_1，ＶA1_2｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して得られた半接触多角形の境界頂点集合｛ＰA1_1，ＰA1_2｝を示した図である。
【図２１Ｂ】図２１Ｂは、図２０Ｂに示した頂点集合｛ＶB2_3，ＶB2_4｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して得られた半接触多角形の境界頂点集合｛ＰB2_3，ＰB2_4｝を示した図である。
【図２２Ａ】図２２Ａは、半接触多角形内に存在するとして抽出された頂点集合｛ＶA3_1，ＶA3_2｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して得られた半接触多角形の境界頂点集合｛ＰA3_1，ＰA3_2｝を示した図である。
【図２２Ｂ】図２２Ｂは、半接触多角形内に存在するとして抽出された頂点集合｛ＶB2_1，ＶB2_1｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して得られた半接触多角形の境界頂点集合｛ＰB2_1，ＰB2_2｝を示した図である。
【図２３】図２３は、各凸断片Ａ１及びＢ２それぞれの半接触多角形を接触平面ＣＰ1上で重ね合わせて求められたオーバラップ領域を示した図である。
【図２４】図２４は、各凸断片Ａ３及びＢ２それぞれの半接触多角形を接触平面ＣＰ1上で重ね合わせて求められたオーバラップ領域を示した図である。
【図２５Ａ】図２５Ａは、凸断片Ａ１と凸断片Ｂ２、凸断片Ａ３と凸断片Ｂ２の接触多角形の各頂点に接触平面の法線方向の力を作用させる様子を示した図である。
【図２５Ｂ】図２５Ｂは、凸断片Ａ１と凸断片Ｂ２、凸断片Ａ３と凸断片Ｂ２の接触多角形の各頂点に接触平面の法線方向に作用させた力の作用点及び作用方向は互いに向き合う様子を示した図である。
【図２６Ａ】図２６Ａは、凹形状物体Ａについて凸包Ａを求めた様子を示した図である。
【図２６Ｂ】図２６Ｂは、凹形状物体Ｂについて凸包Ｂを求めた様子を示した図である。
【図２７】図２７は、凸包Ａ及び凸包Ｂ間に仮想接触平面を決定した様子を示した図である。
【図２８Ａ】図２８Ａは、凸断片Ａ１及び凸断片Ｂ２において、サポート・ポイントを用いて局所的頂点探索処理を行ない、半接触多角形の形状を与える頂点集合｛ＶA1_1，ＶA1_2｝を算出する様子を示した図である。
【図２８Ｂ】図２８Ｂは、凸断片Ａ１及び凸断片Ｂ２において、サポート・ポイントを用いて局所的頂点探索処理を行ない、半接触多角形の形状を与える頂点集合｛ＶB2_3，ＶB2_4｝を算出する様子を示した図である。
【図２９Ａ】図２９Ａは、凸断片Ａ３及び凸断片Ｂ２において、サポート・ポイントを用いて局所的頂点探索処理を行ない、半接触多角形の形状を与える頂点集合｛ＶA3_1，ＶA3_2｝を算出する様子を示した図である。
【図２９Ｂ】図２９Ｂは、凸断片Ａ３及び凸断片Ｂ２において、サポート・ポイントを用いて局所的頂点探索処理を行ない、半接触多角形の形状を与える頂点集合｛ＶB2_1，ＶB2_2｝を算出する様子を示した図である。
【図３０Ａ】図３０Ａは、半接触多角形の形状を与える頂点集合｛ＶA1_1，ＶA1_2｝を仮想接触平面へ正射影し、正射影した頂点集合に対して２次元凸包演算を施して得られる境界頂点集合｛ＰA1_1，ＰA1_2｝を示した図である。
【図３０Ｂ】図３０Ｂは、半接触多角形の形状を与える頂点集合｛ＶB2_3，ＶB2_4｝を仮想接触平面へ正射影し、正射影した頂点集合に対して２次元凸包演算を施して得られる境界頂点集合｛ＰB2_3，ＰB2_4｝を示した図である。
【図３１Ａ】図３１Ａは、半接触多角形の形状を与える頂点集合｛ＶA1_1，ＶA1_2｝を仮想接触平面へ正射影し、正射影した頂点集合に対して２次元凸包演算を施して得られる境界頂点集合｛ＰA3_1，ＰA3_2｝を示した図である。
【図３１Ｂ】図３１Ｂは、半接触多角形の形状を与える頂点集合｛ＶB2_1，ＶB2_2｝を仮想接触平面へ正射影し、正射影した頂点集合に対して２次元凸包演算を施して得られる境界頂点集合｛ＰB2_1，ＰB2_2｝を示した図である。
【図３２】図３２は、図３０Ａに示した境界頂点集合｛ＰA1_1，ＰA1_2｝と図３０Ｂに示した境界頂点集合｛ＰB2_3，ＰB2_4｝を仮想接触平面上で重ね合わせて得られたオーバラップ領域｛ＰB2_3，ＰA1_2｝を示した図である。
【図３３】図３３は、図３１Ａに示した境界頂点集合ＰA3_1，ＰA3_2｝と図３１Ｂに示した境界頂点集合｛ＰB2_3，ＰB2_4｝を仮想接触平面上で重ね合わせて得られたオーバラップ領域｛ＰB2_1，ＰB2_2｝を示した図である。
【図３４Ａ】図３４Ａは、凸断片毎の接触多角形の境界頂点に対して力を作用した様子を示した図である。
【図３４Ｂ】図３４Ｂは、凸断片毎の接触多角形の境界頂点に対して力を作用して、凸断片複合体を含む物体間の浸透問題が解決される様子を示した図である。
【図３５】図３５は、凹形状を含む任意形状の物体間に形成される接触多角形群を算出する接触形状算出装置の機能的構成を模式的に示した図である。
【図３６】図３６は、接触形状算出装置１で実行される接触多角形決定処理の手順を示したフローチャートである。
【図３７】図３７は、仮想接触平面決定処理の詳細な手順を示したフローチャートである。
【図３８】図３８は、凸断片間接触多角形決定処理の詳細な手順を示したフローチャートである。
【図３９】図３９は、凸断片間接触多角形決定処理における、各凸断片の局所探索処理の詳細な手順を示したフローチャートである。
【図４０】図４０は、図３９に示したフローチャートのステップＳ３７で実行される頂点調査処理の詳細な手順を示したフローチャートである。
【図４１】図４１は、物体の凸包を球の半径のｒ分だけ膨張させた非浸透型モデルを用いて干渉検出と接触問題を解決する方法を説明するための図である。
【図４２】図４２は、２つの立方体ＡとＢが接触しているときに構成される接触計上を示した図である。
【図４３】図４３は、周知の衝突検出アルゴリズムで得られる、２立体間の１衝突当たりその代表点１点を示した図である。
【図４４】図４４は、周知の衝突検出アルゴリズムで得られる、２立体間で衝突を発生した３角形メッシュを示した図である。
【図４５】図４５は、立方体が水平な床上に置かれている場合において、代表点Ｐのみに反力を作用させた様子（床反力モデルが復元力を有さない場合、並びに床反力モデルが復元力を有する場合）を示した図である。
【図４６Ａ】図４６Ａは、最近傍点算出処理により得られる２物体間の最近傍点対を示した図である。
【図４６Ｂ】図４６Ｂは、最浸透点算出処理により得られる２物体間の最浸透点対を示した図である。
【符号の説明】
【０１５４】
１…接触形状算出装置
１０…座標系設定部
２０…干渉検出部
２１…シーンデータ蓄積部
２２…計算幾何学演算部
２３…凸包間干渉検出部
２４…凸断片間干渉検出部
２５…接触平面決定部
２６…凸断片間接触多角形決定部
【図４】
2008040580.tif 000007
【図８Ａ】
2008040580.tif 000008
【図８Ｂ】
2008040580.tif 000009
【図９Ａ】
2008040580.tif 000010
【図９Ｂ】
2008040580.tif 000011
【図１０Ａ】
2008040580.tif 000012
【図１０Ｂ】
2008040580.tif 000013
【図１０Ｃ】
2008040580.tif 000014
【図１０Ｄ】
2008040580.tif 000015
【図１１】
2008040580.tif 000016
【図１７】
2008040580.tif 000017
【図３６】
2008040580.tif 000018
【図３７】
2008040580.tif 000019
【図３８】
2008040580.tif 000020
【図３９】
2008040580.tif 000021
【図４０】
2008040580.tif 000022
【図４３】
2008040580.tif 000023
【図４６Ａ】
2008040580.tif 000024
【図４６Ｂ】
2008040580.tif 000025
【図１】
2008040580.tif 000026
【図２】
2008040580.tif 000027
【図３】
2008040580.tif 000028
【図５】
2008040580.tif 000029
【図６】
2008040580.tif 000030
【図７】
2008040580.tif 000031
【図１２】
2008040580.tif 000032
【図１３Ａ】
2008040580.tif 000033
【図１３Ｂ】
2008040580.tif 000034
【図１４Ａ】
2008040580.tif 000035
【図１４Ｂ】
2008040580.tif 000036
【図１５】
2008040580.tif 000037
【図１６Ａ】
2008040580.tif 000038
【図１６Ｂ】
2008040580.tif 000039
【図１８Ａ】
2008040580.tif 000040
【図１８Ｂ】
2008040580.tif 000041
【図１９Ａ】
2008040580.tif 000042
【図１９Ｂ】
2008040580.tif 000043
【図２０Ａ】
2008040580.tif 000044
【図２０Ｂ】
2008040580.tif 000045
【図２１Ａ】
2008040580.tif 000046
【図２１Ｂ】
2008040580.tif 000047
【図２２Ａ】
2008040580.tif 000048
【図２２Ｂ】
2008040580.tif 000049
【図２３】
2008040580.tif 000050
【図２４】
2008040580.tif 000051
【図２５Ａ】
2008040580.tif 000052
【図２５Ｂ】
2008040580.tif 000053
【図２６Ａ】
2008040580.tif 000054
【図２６Ｂ】
2008040580.tif 000055
【図２７】
2008040580.tif 000056
【図２８Ａ】
2008040580.tif 000057
【図２８Ｂ】
2008040580.tif 000058
【図２９Ａ】
2008040580.tif 000059
【図２９Ｂ】
2008040580.tif 000060
【図３０Ａ】
2008040580.tif 000061
【図３０Ｂ】
2008040580.tif 000062
【図３１Ａ】
2008040580.tif 000063
【図３１Ｂ】
2008040580.tif 000064
【図３２】
2008040580.tif 000065
【図３３】
2008040580.tif 000066
【図３４Ａ】
2008040580.tif 000067
【図３４Ｂ】
2008040580.tif 000068
【図３５】
2008040580.tif 000069
【図４１】
2008040580.tif 000070
【図４２】
2008040580.tif 000071
【図４４】
2008040580.tif 000072
【図４５】
2008040580.tif 000073
【手続補正書】
【提出日】平成19年10月31日(2007.10.31)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
本発明に係る接触形状算出装置によれば、凸形状物体だけでなく、凹形状を含む任意形状の物体間の干渉検出を実行することが可能となり、現実世界に存在するオブジェクトを広範に扱うことが可能になる。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
本発明に係る接触形状算出装置は、移動ロボットのように、周囲の環境との物理的接触状態が多様に変化し、その状態をリアルタイムで把握する必要のあるシステムに対して、好適に適用することができる。すなわち、画像処理やセンシング処理（レンジ・センサ）により得られた環境形状と、移動ロボット自身の３次元形状モデルに対して、本発明に係る接触形状検出処理を適用することにより、移動ロボットと環境間の複雑な接触状態を高速に求めることができ、より一般化された姿勢安定制御や、多様な環境下での動作計画の実現が可能となる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００４８
【補正方法】変更
【補正の内容】
【００４８】
２つの物体Ａと物体Ｂの接触状態を直接的に扱うと、さまざまな組合せが存在し、問題が複雑となる。そこで、物体間の接触状態を知る第２ステップとして、図２に示すように、この問題を接触平面ＣＰと一方の物体Ａの接触問題と、及び接触平面ＣＰと物体Ｂの接触問題という、２つの独立な問題に分割することにより、直感的に扱う際に生じる複雑な組み合わせ問題を回避し、接触状態を効率的に求める。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００６９
【補正方法】変更
【補正の内容】
【００６９】
衝突検出を行なう物体が凸形状である場合、その判定は凹形状である場合に比し、高速に行なうことができる（例えば、非特許文献２を参照のこと）。そこで、本実施形態でも、凸形状物体に対する効率のよいアルゴリズムを凹形状物体間の衝突判定に利用する。すなわち、図８及び図９に示したような凸形状でない凹形状多面体を複数の凸断片に凸分解して、凹形状物体を複数の凸断片群より構成される複合体（以下では、「凸断片複合体」と呼ぶ）として取り扱う。すなわち、図８Ａ及び図９Ａに示した物体Ａは、図１０Ａ及び図１０Ｃに示すように、３つの凸断片Ａ１、Ａ２、Ａ３の複合体として取り扱い、図８Ｂ及び図９Ｂに示した物体Ｂは、図１０Ｂ及び図１０Ｄに示すように、２つの凸断片Ｂ１、Ｂ２の複合体として扱う。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００８１
【補正方法】変更
【補正の内容】
【００８１】
続く第３のステップでは、半接触多角形内に存在するとして抽出された各頂点集合｛ＶA1_1，ＶA1_2｝及び｛ＶB2_3，ＶB2_4｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して、半接触多角形の境界頂点集合｛ＰA1_1，ＰA1_2｝及び｛ＰB2_3，ＰB2_4｝を得る（図２１Ａ及び図２１Ｂを参照のこと）。同様に、半接触多角形内に存在するとして抽出された各頂点集合｛ＶA3_1，ＶA3_2｝及び｛ＶB2_1，ＶB2_2｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して、半接触多角形の境界頂点集合｛ＰA3_1，ＰA3_2｝及び｛ＰB2_1，ＰB2_2｝を得る（図２２Ａ及び図２２Ｂを参照のこと）。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１０１
【補正方法】変更
【補正の内容】
【０１０１】
図３５には、凹形状を含む任意形状の物体間に形成される接触多角形群を算出する接触形状算出装置の機能的構成を模式的に示している。図示の接触形状算出装置１は、座標系設定部１０と、シーンデータ蓄積部２１と、計算幾何学演算部２２と、凸包間干渉検出部２３と、凸断片間干渉検出部２４と、接触平面決定部２５と、凸断片間接触多角形決定部２６を備えている。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１０３
【補正方法】変更
【補正の内容】
【０１０３】
シーンデータ蓄積部２１と、計算幾何学演算部２２と、凸包間干渉検出部２３と、凸断片間干渉検出部２４と、接触平面決定部２５と、凸断片間接触多角形決定部２６により干渉検出部が構成される。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１１９
【補正方法】変更
【補正の内容】
【０１１９】
まず、座標系設定ステップ（Ｓ１）では、シーンデータ蓄積部２１内の各物体の位置・姿勢情報を設定する。座標系設定部１０は、例えば、力学シミュレーション・エンジンで構成され、各物体の運動を決定する。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１２４
【補正方法】変更
【補正の内容】
【０１２４】
凸包間干渉検出ステップ（Ｓ１２）では、先行する凸断片間干渉検出ステップで求めた、凸断片複合体の凸包形状間の干渉検出処理を、計算幾何学演算部２２内のＧＪＫアルゴリズム実行部２２Ａにより実行し、シーンデータ蓄積部２１内で接触又は衝突を起こした物体（凸断片複合体）に対して、衝突代表点対（最も浸透した点の組、若しくは最も近接した点の組）を求める。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１３０
【補正方法】変更
【補正の内容】
【０１３０】
続く半接触多角形決定ステップ（Ｓ２４）では、先行する頂点探索実行ステップで探索した、接触平面よりも衝突相手側に存在する頂点集合を接触平面上に正射影し、その平面上で２次元凸包演算を施し、その輪郭形状を境界頂点集合として抽出して、半接触多角形を計算する。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１３３
【補正方法】変更
【補正の内容】
【０１３３】
まず、ステップＳ２２における探索起点決定ステップにより決定された探索起点を、凸断片間接触多角形決定処理の起点に設定し（Ｓ３１）、起点とした頂点に探索済みフラグを立てるとともに（Ｓ３２）、候補点リストに追加する（Ｓ３３）。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１４６
【補正方法】変更
【補正の内容】
【０１４６】
物体が相互に浸透することがないように反力を発生させる場合、図４１に示すように、各物体の凸包形状と球のＭｉｎｋｏｗｓｋｉ和、すなわち、物体の凸包を球の半径のｒ分だけ膨張させた図形に対して干渉検出を行ない、仮想接触平面を求め、仮想接触平面を法線ベクトル方向にオフセットさせた平面（すなわちオフセット仮想接触平面）を定義する。そして、このオフセット仮想接触平面と、膨張前の原物体の形状、すなわち凸断片との間の半接触多角形を算出し、インターセクションを求めるように構成する。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０１４７
【補正方法】変更
【補正の内容】
【０１４７】
原物体間が干渉を起こしていない場合、衝突検出アルゴリズムであるＧＪＫアルゴリズムでは、衝突代表点対として２物体間の最近傍点を算出する。したがって、非浸透型モデルでは、仮想接触平面は、最近傍点対の中点を通り、両点を結ぶ方向を法線ベクトルとするように定める。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０１４８
【補正方法】変更
【補正の内容】
【０１４８】
仮想接触平面のオフセット量の決定方法はさまざまであるが、オフセット仮想接触平面と原物体が必ず交点を有するように設定することが好ましい。例えば、物体Ａ（凸断片Ａ１）との半接触多角形を算出する際には、物体Ａ側のＭｉｎｋｏｗｓｋｉ和をとる球の半径ｒだけオフセットさせた仮想接触平面を考える。また、物体Ｂ（凸断片Ｂ２）との半接触多角形を算出する際には、逆方向にｒだけオフセットさせた平面を考えればよい。上式（２）の判定を、これらのオフセット仮想接触平面と原物体（凸断片）の頂点間で実行するように、隣接頂点グラフの探索を実行する。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０１４９
【補正方法】変更
【補正の内容】
【０１４９】
探索起点となる頂点の選定や、２次元凸包演算による半接触多角形内部の点の消去、インターセクション演算による半接触多角形共通領域の算出など、その他の処理に関しては、浸透型モデルの場合と同一の手順で実行すればよい。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０１５１
【補正方法】変更
【補正の内容】
【０１５１】
本発明に係る接触形状算出装置は、移動ロボットのように、周囲の環境との物理的接触状態が多様に変化し、その状態をリアルタイムで把握する必要のあるシステムに対して、好適に適用することができる。すなわち、画像処理やセンシング処理（レンジ・センサ）により得られた環境形状と、移動ロボット自身の３次元形状モデルに対して、本発明に係る接触形状算出処理を適用することにより、移動ロボットと環境間の複雑な接触状態を高速に求めることができ、より一般化された姿勢安定制御や、多様な環境下出の動作計画の実現が可能となる。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０１５３
【補正方法】変更
【補正の内容】
【０１５３】
【図１】図１は、立体Ａ及びＢの接触部を横から見た拡大図である。
【図２】図２は、立体Ａ及びＢ間の接触問題を接触平面ＣＰと一方の立体Ａの接触問題と、及び接触平面ＣＰと立体Ｂの接触問題に分割した様子を示した図である。
【図３】図３は、衝突検出アルゴリズムによってそれぞれの立体から得られる代表点Ｐａ及びＰｂを示した図である。
【図４】図４は、ある立体Ｒに対し矢印で示したベクトル方向へのサポート写像を得る様子を示した図である。
【図５】図５は、適当な頂点を起点として隣接頂点グラフを局所探索し、立体Ａと接触平面との最終的な半接触多角形を得た様子を示した図である。
【図６】図６は、立方体の面面の中心に頂点が設定され、頂点探索の結果として含まれる様子を示した図である。
【図７】図７は、接触平面上における立体Ａ及びＢそれぞれの半接触多角形からオーバラップ領域を求める様子を示した図である。
【図８Ａ】図８Ａは、凹形状を持つ物体Ａの斜視図である。
【図８Ｂ】図８Ｂは、凹形状を持つ物体Ｂの斜視図である。
【図９Ａ】図９Ａは、凹形状を持つ物体Ａの平面図である。
【図９Ｂ】図９Ｂは、凹形状を持つ物体Ｂの平面図である。
【図１０Ａ】図１０Ａは、凹形状を持つ物体Ａを凸断片群に凸分解した様子を示した図である。
【図１０Ｂ】図１０Ｂは、凹形状を持つ物体Ｂを凸断片群に凸分解した様子を示した図である。
【図１０Ｃ】図１０Ｃは、凹形状を持つ物体Ａを凸断片群に凸分解した様子を示した図である。
【図１０Ｄ】図１０Ｄは、凹形状を持つ物体Ｂを凸断片群に凸分解した様子を示した図である。
【図１１】図１１は、物体Ａと物体Ｂが衝突を起こしている様子を示した図である。
【図１２】図１２は、物体Ａと物体Ｂが図１１に示すように衝突を起こしているときの干渉検出処理方法を説明するための図である。
【図１３Ａ】図１３Ａは、局所的探索により得られた、接触平面ＣＰの正領域に存在する｛ＶA1_1，ＶA1_2｝を示した図である。
【図１３Ｂ】図１３Ｂは、局所的探索により得られた、接触平面ＣＰの正領域に存在する｛ＶB1_1，ＶB1_2｝を示した図である。
【図１４Ａ】図１４Ａは、図１３Ａに示した頂点集合｛ＶA1_1，ＶA1_2｝を接触平面ＣＰに正射影して得られた頂点群｛ＰA1_1，ＰA1_2｝を示した図である。
【図１４Ｂ】図１４Ｂは、図１３Ｂに示した頂点集合｛ＶB1_1，ＶB1_2｝を接触平面ＣＰに正射影して得られた頂点群｛ＰB1_1，ＰB1_2｝を示した図である。
【図１５】図１５は、図１４Ａ及び図１４Ｂにそれぞれ示した半接触多角形の積領域をとって求められた接触多角形を示した図である。
【図１６Ａ】図１６Ａは、図１５に示した接触多角形の各頂点に力を作用させる様子を示した図である。
【図１６Ｂ】図１６Ｂは、図１５に示した接触多角形の各頂点に力を作用させて、物体Ａと物体Ｂの接触に伴う物理的相互作用における力学シミュレーションを実行する様子を示した図である。
【図１７】図１７は、物体Ａと物体Ｂが複数の凸断片で接触する様子を示した図である。
【図１８Ａ】図１８Ａは、凸断片Ｂ２と凸断片Ａ１の衝突検出処理により求められた衝突代表点対｛ＰA1，ＰB2_1｝及び接触平面ＣＰ1を示した図である。
【図１８Ｂ】図１８Ｂは、凸断片Ｂ２と凸断片Ａ３の衝突検出処理により求められた衝突代表点対｛ＰA3，ＰB2_1｝及び接触平面ＣＰ2を示した図である。
【図１９Ａ】図１９Ａは、局所的探索により得られた、接触平面ＣＰ1の正領域に存在する｛ＶA1_1，ＶA1_2｝を示した図である。
【図１９Ｂ】図１９Ｂは、局所的探索により得られた、接触平面ＣＰ1の正領域に存在する｛ＶB2_3，ＶB2_4｝を示した図である。
【図２０Ａ】図２０Ａは、局所的探索により得られた、接触平面ＣＰ2の正領域に存在する｛ＶA3_1，ＶA3_2｝を示した図である。
【図２０Ｂ】図２０Ｂは、局所的探索により得られた、接触平面ＣＰ2の正領域に存在する｛ＶB2_1，ＶB2_2｝を示した図である。
【図２１Ａ】図２１Ａは、図１９Ａに示した頂点集合｛ＶA1_1，ＶA1_2｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して得られた半接触多角形の境界頂点集合｛ＰA1_1，ＰA1_2｝を示した図である。
【図２１Ｂ】図２１Ｂは、図１９Ｂに示した頂点集合｛ＶB2_3，ＶB2_4｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して得られた半接触多角形の境界頂点集合｛ＰB2_3，ＰB2_4｝を示した図である。
【図２２Ａ】図２２Ａは、半接触多角形内に存在するとして抽出された頂点集合｛ＶA3_1，ＶA3_2｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して得られた半接触多角形の境界頂点集合｛ＰA3_1，ＰA3_2｝を示した図である。
【図２２Ｂ】図２２Ｂは、半接触多角形内に存在するとして抽出された頂点集合｛ＶB2_1，ＶB2_2｝を接触平面ＣＰ1へ正射影し、さらに正射影した頂点群に対して２次元凸包演算を施して得られた半接触多角形の境界頂点集合｛ＰB2_1，ＰB2_2｝を示した図である。
【図２３】図２３は、各凸断片Ａ１及びＢ２それぞれの半接触多角形を接触平面ＣＰ1上で重ね合わせて求められたオーバラップ領域を示した図である。
【図２４】図２４は、各凸断片Ａ３及びＢ２それぞれの半接触多角形を接触平面ＣＰ1上で重ね合わせて求められたオーバラップ領域を示した図である。
【図２５Ａ】図２５Ａは、凸断片Ａ１と凸断片Ｂ２、凸断片Ａ３と凸断片Ｂ２の接触多角形の各頂点に接触平面の法線方向の力を作用させる様子を示した図である。
【図２５Ｂ】図２５Ｂは、凸断片Ａ１と凸断片Ｂ２、凸断片Ａ３と凸断片Ｂ２の接触多角形の各頂点に接触平面の法線方向に作用させた力の作用点及び作用方向は互いに向き合う様子を示した図である。
【図２６Ａ】図２６Ａは、凹形状物体Ａについて凸包Ａを求めた様子を示した図である。
【図２６Ｂ】図２６Ｂは、凹形状物体Ｂについて凸包Ｂを求めた様子を示した図である。
【図２７】図２７は、凸包Ａ及び凸包Ｂ間に仮想接触平面を決定した様子を示した図である。
【図２８Ａ】図２８Ａは、凸断片Ａ１及び凸断片Ｂ２において、サポート・ポイントを用いて局所的頂点探索処理を行ない、半接触多角形の形状を与える頂点集合｛ＶA1_1，ＶA1_2｝を算出する様子を示した図である。
【図２８Ｂ】図２８Ｂは、凸断片Ａ１及び凸断片Ｂ２において、サポート・ポイントを用いて局所的頂点探索処理を行ない、半接触多角形の形状を与える頂点集合｛ＶB2_3，ＶB2_4｝を算出する様子を示した図である。
【図２９Ａ】図２９Ａは、凸断片Ａ３及び凸断片Ｂ２において、サポート・ポイントを用いて局所的頂点探索処理を行ない、半接触多角形の形状を与える頂点集合｛ＶA3_1，ＶA3_2｝を算出する様子を示した図である。
【図２９Ｂ】図２９Ｂは、凸断片Ａ３及び凸断片Ｂ２において、サポート・ポイントを用いて局所的頂点探索処理を行ない、半接触多角形の形状を与える頂点集合｛ＶB2_1，ＶB2_2｝を算出する様子を示した図である。
【図３０Ａ】図３０Ａは、半接触多角形の形状を与える頂点集合｛ＶA1_1，ＶA1_2｝を仮想接触平面へ正射影し、正射影した頂点集合に対して２次元凸包演算を施して得られる境界頂点集合｛ＰA1_1，ＰA1_2｝を示した図である。
【図３０Ｂ】図３０Ｂは、半接触多角形の形状を与える頂点集合｛ＶB2_3，ＶB2_4｝を仮想接触平面へ正射影し、正射影した頂点集合に対して２次元凸包演算を施して得られる境界頂点集合｛ＰB2_3，ＰB2_4｝を示した図である。
【図３１Ａ】図３１Ａは、半接触多角形の形状を与える頂点集合｛ＶA3_1，ＶA3_2｝を仮想接触平面へ正射影し、正射影した頂点集合に対して２次元凸包演算を施して得られる境界頂点集合｛ＰA3_1，ＰA3_2｝を示した図である。
【図３１Ｂ】図３１Ｂは、半接触多角形の形状を与える頂点集合｛ＶB2_1，ＶB2_2｝を仮想接触平面へ正射影し、正射影した頂点集合に対して２次元凸包演算を施して得られる境界頂点集合｛ＰB2_1，ＰB2_2｝を示した図である。
【図３２】図３２は、図３０Ａに示した境界頂点集合｛ＰA1_1，ＰA1_2｝と図３０Ｂに示した境界頂点集合｛ＰB2_3，ＰB2_4｝を仮想接触平面上で重ね合わせて得られたオーバラップ領域｛ＰB2_3，ＰA1_2｝を示した図である。
【図３３】図３３は、図３１Ａに示した境界頂点集合｛ＰA3_1，ＰA3_2｝と図３１Ｂに示した境界頂点集合｛ＰB2_1，ＰB2_2｝を仮想接触平面上で重ね合わせて得られたオーバラップ領域｛ＰA3_1，ＰB2_2｝を示した図である。
【図３４Ａ】図３４Ａは、凸断片毎の接触多角形の境界頂点に対して力を作用した様子を示した図である。
【図３４Ａ】図３４Ａは、凸断片毎の接触多角形の境界頂点に対して力を作用して、凸断片複合体を含む物体間の浸透問題が解決される様子を示した図である。
【図３５】図３５は、凹形状を含む任意形状の物体間に形成される接触多角形群を算出する接触形状算出装置の機能的構成を模式的に示した図である。
【図３６】図３６は、接触形状算出装置１で実行される接触多角形決定処理の手順を示したフローチャートである。
【図３７】図３７は、仮想接触平面決定処理の詳細な手順を示したフローチャートである。
【図３８】図３８は、凸断片間接触多角形決定処理の詳細な手順を示したフローチャートである。
【図３９】図３９は、凸断片間接触多角形決定処理における、各凸断片の局所探索処理の詳細な手順を示したフローチャートである。
【図４０】図４０は、図３９に示したフローチャートのステップＳ３７で実行される頂点調査処理の詳細な手順を示したフローチャートである。
【図４１】図４１は、物体の凸包を球の半径のｒ分だけ膨張させた非浸透型モデルを用いて干渉検出と接触問題を解決する方法を説明するための図である。
【図４２】図４２は、２つの立方体ＡとＢが接触しているときに構成される接触形状を示した図である。
【図４３】図４３は、周知の衝突検出アルゴリズムで得られる、２立体間の１衝突当たりその代表点１点を示した図である。
【図４４】図４４は、周知の衝突検出アルゴリズムで得られる、２立体間で衝突を発生した３角形メッシュを示した図である。
【図４５Ａ】図４５Ａは、立方体が水平な床上に置かれている場合において、代表点Ｐのみに反力を作用させた様子（床反力モデルが復元力を有さない場合）を示した図である。
【図４５Ｂ】図４５Ｂは、立方体が水平な床上に置かれている場合において、代表点Ｐのみに反力を作用させた様子（床反力モデルが復元力を有する場合）を示した図である。
【図４６Ａ】図４６Ａは、最近傍点算出処理により得られる２物体間の最近傍点対を示した図である。
【図４６Ｂ】図４６Ｂは、最浸透点算出処理により得られる２物体間の最浸透点対を示した図である。