(57)【要約】【課題】  仮想空間に配置されたオブジェクト同士の干渉を簡易な演算により演算可能な３次元オブジェクト制御装置または３次元オブジェクト制御プログラムを提供する。【解決手段】  ３次元オブジェクト制御装置５０において、オブジェクト制御部５２は、仮想空間に配置されたオブジェクトのうち、注目オブジェクトと、該注目オブジェクトの２箇所以上において同時に干渉し得る周辺オブジェクトとの干渉を判定する。干渉すると判定された場合に、表示出力部５８または応答出力部６０は、干渉することを報知する。【選択図】  図７
2006302098.tif 000002
【特許請求の範囲】
【請求項１】
仮想空間に配置されたオブジェクトのうち、注目オブジェクトと、該注目オブジェクトの２箇所以上において同時に干渉し得る周辺オブジェクトとの干渉を判定する干渉判定手段と、
前記干渉判定手段により干渉すると判定された場合に、干渉することを報知する干渉報知手段を備えることを特徴とする３次元オブジェクト制御装置。
【請求項２】
仮想空間に配置された非干渉状態におけるオブジェクト間の最近傍点を結ぶ最近傍ベクトルを算出する最近傍ベクトル演算手段と、
前記注目オブジェクトが前記周辺オブジェクトと干渉しているものとした場合に、前記注目オブジェクトの位置である干渉位置に対して前記注目オブジェクトが前記周辺オブジェクトとの干渉を解消する極小近傍の位置である極小近傍非干渉位置から、前記干渉位置へ向かうベクトルである干渉深度ベクトルを、前記最近傍ベクトルから算出するベクトル演算手段とをさらに備え、
前記干渉報知手段は、前記干渉深度ベクトルから干渉を報知することを特徴とする請求項１に記載の３次元オブジェクト制御装置。
【請求項３】
前記干渉位置を干渉位置ｒｐ、前記オブジェクトが前記周辺オブジェクトからεだけ離れた位置を非干渉位置ｒとした場合、
前記ベクトル演算手段は、前記非干渉位置ｒのうち、前記干渉位置ｒｐから前記非干渉位置ｒへの距離が極小となるときまたは極小と近似されるときの極小近傍位置ｒｑを演算する極小近傍演算手段を有し、
前記ベクトル演算手段は、前記干渉位置ｒｐから極小近傍位置ｒｑへ向かうベクトル、および前記極小近傍位置ｒｑにある注目オブジェクトと前記周辺オブジェクトの間の最近傍点を結ぶ最近傍ベクトルから、前記干渉深度ベクトルを算出することを特徴とする請求項２に記載の３次元オブジェクト制御装置。
【請求項４】
オブジェクトを前記仮想空間において移動または回転する移動回転手段をさらに備え、
前記移動回転手段は、前記干渉深度ベクトルを用いて、干渉する１つ以上のオブジェクトを該干渉が解消する位置へ移動または回転し、
前記干渉報知手段は、仮想空間に配置された複数のオブジェクトを画面に表示する表示出力手段を有し、前記表示出力手段は、移動または回転された前記オブジェクトを画面に表示することにより干渉することを報知することを特徴とする請求項１から３のいずれかに記載の３次元オブジェクト制御装置。
【請求項５】
前記干渉報知手段は、仮想空間に配置された複数のオブジェクトを画面に表示する表示出力手段を有し、前記表示出力手段は、干渉すると判定された場合に、前記干渉深度ベクトルを用いて、干渉することを画面に表示することにより干渉することを報知することを特徴とする請求項１から３のいずれかに記載の３次元オブジェクト制御装置。
【請求項６】
前記干渉報知手段は、入力された情報に応じて作動するアクチュエータに情報を出力する応答出力手段を備え、
前記応答出力手段は、干渉すると判定された場合に、前記干渉深度ベクトルを用いた情報を前記アクチュエータに出力して前記アクチュエータを作動させることにより、干渉することを報知することを特徴とする請求項２から５のいずれかに記載の３次元オブジェクト制御装置。
【請求項７】
前記干渉報知手段は、前記干渉深度ベクトルに応じた方向に作動し、前記干渉深度ベクトルのスカラー量である干渉深度に応じた力で作動するアクチュエータに情報を出力する応答出力手段を備え、
前記応答出力手段は、干渉すると判定された場合に、前記干渉深度ベクトルおよび前記干渉深度を前記アクチュエータに出力して前記アクチュエータを作動させることにより、干渉することを報知することを特徴とする請求項２または３に記載の３次元オブジェクト制御装置。
【請求項８】
仮想空間に配置された非干渉状態におけるオブジェクト間の最近傍点を結ぶ最近傍ベクトルを算出する機能と、
仮想空間に配置されたオブジェクトのうち、注目オブジェクトと、該注目オブジェクトの２箇所以上において同時に干渉し得る周辺オブジェクトにおいて、前記注目オブジェクトが前記周辺オブジェクトと干渉しているものとした場合に、前記注目オブジェクトの位置である干渉位置に対して前記注目オブジェクトが前記周辺オブジェクトとの干渉を解消する極小近傍の位置である極小近傍非干渉位置から、前記干渉位置へ向かうベクトルである干渉深度ベクトルを、前記最近傍ベクトルから算出する機能とをコンピュータに実現せしめることを特徴とする３次元オブジェクト制御プログラム。
【請求項９】
仮想空間に配置された非干渉状態におけるオブジェクト間の最近傍点を結ぶ最近傍ベクトルを算出する機能と、
仮想空間に配置されたオブジェクトのうち、注目オブジェクトと、該注目オブジェクトの２箇所以上において同時に干渉し得る周辺オブジェクトにおいて、前記注目オブジェクトが前記周辺オブジェクトと干渉しているものとした場合であって、前記注目オブジェクトの位置を干渉位置ｒｐとし、前記注目オブジェクトが前記周辺オブジェクトからεだけ離れた位置を非干渉位置ｒとした場合、前記非干渉位置ｒのうち、前記干渉位置ｒｐから前記非干渉位置ｒへの距離が極小となるときまたは極小と近似されるときの極小近傍位置ｒｑを演算する機能と、
前記干渉位置ｒｐから極小近傍位置ｒｑへ向かうベクトル、および前記極小近傍位置ｒｑにある注目オブジェクトと前記周辺オブジェクトの間の最近傍点を結ぶ最近傍ベクトルから、前記干渉深度ベクトルを算出する機能とをコンピュータに実現せしめることを特徴とする３次元オブジェクト制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元オブジェクト制御装置等に関し、仮想空間に配置されたオブジェクトの干渉の演算手段を有する３次元オブジェクト制御装置および３次元オブジェクト制御プログラム等に関する。
【背景技術】
【０００２】
コンピュータ上に設けられた３次元仮想空間において、３次元オブジェクトの移動などを行うコンピュータ・グラフィックス（以下、「ＣＧ」という。）技術が、コンピュータの演算処理能力の飛躍的な向上に伴い、近年急速に発展してきている。これに伴い、３次元仮想空間において３次元オブジェクト同士が接触または干渉する場合における正確かつ迅速な３次元オブジェクト制御のニーズもまた高まっている。
【０００３】
３次元仮想空間において、複数の多面体が干渉する場合に、その干渉の方向や大きさを干渉深度（Penetration Depth；以下必要に応じて「ＰＤ」と記載する。）、または干渉深度ベクトルとしてよく定義され、コンピュータにより演算された干渉深度に応じて３次元オブジェクトの制御を行っている。この干渉深度の応用分野としては、例えばロボット工学（Ｒobotics）、ハプティクス（Haptics）、インタラクティブ・コンピュータ・ゲーム（interactive computer games）などがあり、この干渉深度に関する研究結果が、例えば非特許文献１及至非特許文献７などに記載されている。
【非特許文献１】Young J.Kim, Ming C.Lin, Dinesh Manocha、「DEEP: Dual-space Expansion for Estimating Penetration depth between convex polytopes」
【非特許文献２】Young J.Kim, Miguel A. Otaduy, Ming C.Lin, Dinesh Manocha、「ix-Degree-of-Freedom Haptic Rendering Using Incremental and Localized Computations」
【非特許文献３】Pankaj K.Agarwal, Leonidas J.Guibas, Sariel Har-Peled、「Penetration Depth of Two Convex Polytopes in 3D」、２０００年１０月１１日
【非特許文献４】Stephen Cameron、「Enhancing GJK: Computing Minimum and Penetration Distances between Convex Polyhedra」、Int Conf Robotics and Automation
【非特許文献５】Stephen A. Ehmann and Ming C.Lin、「Accurate and Fast Proximity Queries Between Polyhedra Using Convex Surface Decomposition」
【非特許文献６】Willian A.McNeely, Kevin D. Puterbaugh, James J. Troy、「Six Degree-of-Freedom Haptic Rendering Using Voxel Sampling」、The Boeing Company
【非特許文献７】足立吉隆,池本明夫,熊野宜弘、「力覚仮想環境における非凸形状物体の操作」、日本ロボット学会誌Vol.21
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、まず、上記文献のいずれにおいても、凸多面体などの凸オブジェクトと２以上の凸多面体などの凸オブジェクトとの干渉については記載されていない。また、例えば非特許文献１及至非特許文献４の大部分の記載は２つの凸多面体同士の干渉についての説明であり、非特許文献３および非特許文献４の記載においては、非凸多面体の干渉については記載されていない。非特許文献１および非特許文献２においては、非凸多面体への拡張も試みられているが、これらの文献に記載される技術は、あくまでも凸多面体の干渉における干渉深度を用いて非凸多面体の干渉深度を算出する技術である。このように非凸多面体を凸多面体に分解し、個々の凸多面体同士の間で計算された干渉深度から、全体の干渉深度を求めることができるという理論的な根拠はなく、確立された手法とは到底いうことはできない。
【０００５】
また、非特許文献６は、Point Shell and Normals Vs. Voxmap の干渉判定に基づく非凸多面体を対象としたHapticsアプリケーションの事例であり、非特許文献７は、点群と三角形群の間の距離の計算をもとにした接触判定に基づく非凸多面体を対象としたHapticsアプリケーションの事例である。しかし、これらのアプリケーションは、いずれも直接非凸多面体同士の干渉判定は取り扱っているわけではなく、３次元の立体的なオブジェクト間の干渉を仮想的に再現するには十分ではない。
【０００６】
以上より、例えば、凸オブジェクトと２以上の凸オブジェクトとの干渉や、凸または非凸オブジェクトと非凸オブジェクトとの干渉など、注目オブジェクトと、該注目オブジェクトの２箇所以上において同時に干渉し得る周辺オブジェクトとの干渉を判定する手法が確立されているということはできない。
【０００７】
本発明はこうした課題に鑑みてなされたものであり、その目的は、仮想空間に配置されたオブジェクト同士の干渉を簡易な演算により演算可能な３次元オブジェクト制御装置または３次元オブジェクト制御プログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明のある態様の３次元オブジェクト制御装置は、仮想空間に配置されたオブジェクトのうち、注目オブジェクトと、該注目オブジェクトの２箇所以上において同時に干渉し得る周辺オブジェクトとの干渉を判定する干渉判定手段と、干渉判定手段により干渉すると判定された場合に、干渉することを報知する干渉報知手段を備える。この態様によれば、注目オブジェクトと、該注目オブジェクトの２箇所以上において同時に干渉し得る周辺オブジェクトとの干渉を確認することができ、よりリアルな３次元オブジェクトの制御が可能となる。
【０００９】
「注目オブジェクトと、該注目オブジェクトの２箇所以上において同時に干渉し得る周辺オブジェクトとの干渉」とは、１対の凸オブジェクト同士の干渉以外の干渉であってもよく、例えば、凸オブジェクトと２以上の凸オブジェクトとの干渉や、凸または非凸オブジェクトと非凸オブジェクトとの干渉などを含んでもよい。「凸オブジェクト」とは、外周面が凸部のみで構成されたオブジェクトでもよく、例えば凸多面体などでもよい。「非凸オブジェクト」とは、外周面に凹部を含むオブジェクトでもよく、例えば非凸多面体などでもよい。
【００１０】
「オブジェクト」には、例えば凸多面体および非凸多面体を含む多面体、サーフィス・オブジェクト、プリミティブ・オブジェクト、およびこれらが結合した結合オブジェクトなどが含まれてもよい。「サーフィス・オブジェクト」とは、例えば任意の三角形の集合から構成されるオブジェクトなど、閉じられていないものや、厚さの定義を有さないものなどが含まれてもよい。また、「プリミティブ・オブジェクト」とは、例えばプリミティブ、またはプリミティブを組み合わせて得られるオブジェクトなどが含まれてもよい。この「プリミティブを組み合わせて得られるオブジェクト」は、互いに干渉することが判定可能で、互いに最近傍点ベクトルが計算可能なプリミティブを組み合わせて得られるオブジェクトが含まれてもよい。
【００１１】
仮想空間に配置された非干渉状態におけるオブジェクト間の最近傍点を結ぶ最近傍ベクトルを算出する最近傍ベクトル演算手段と、注目オブジェクトが周辺オブジェクトと干渉しているものとした場合に、注目オブジェクトの位置である干渉位置に対して注目オブジェクトが周辺オブジェクトとの干渉を解消する極小近傍の位置である極小近傍非干渉位置から、干渉位置へ向かうベクトルである干渉深度ベクトルを、最近傍ベクトルから算出するベクトル演算手段とをさらに備えてもよい。干渉報知手段は、干渉深度ベクトルから干渉を報知してもよい。
【００１２】
この態様によれば、干渉深度ベクトルの演算のために、例えば従来から存在する最近傍ベクトル演算手段を適用することができるなど、簡易に干渉深度ベクトルを算出することができ、また注目オブジェクトと、該注目オブジェクトの２箇所以上において同時に干渉し得る周辺オブジェクトとの干渉を判定することも可能となる。
【００１３】
３次元オブジェクト制御装置のベクトル演算手段は、注目オブジェクトが周辺オブジェクトと干渉しているものとした場合に、注目オブジェクトの位置を干渉位置と定義し、この干渉位置とは別に、注目オブジェクトが周辺オブジェクトと干渉しない非干渉位置を定義することにより、周辺オブジェクトに対する注目オブジェクトの干渉深度ベクトルを演算してもよい。これにより、周辺オブジェクトに対する注目オブジェクトの非干渉位置における演算を行うことにより、周辺オブジェクトに対する注目オブジェクトの干渉深度ベクトルを演算することが可能となる。
【００１４】
干渉位置を干渉位置ｒｐ、オブジェクトが周辺オブジェクトからεだけ離れた位置を非干渉位置ｒとした場合、ベクトル演算手段は、非干渉位置ｒのうち、干渉位置ｒｐから非干渉位置ｒへの距離が極小となるときまたは極小と近似されるときの極小近傍位置ｒｑを演算する極小近傍演算手段を有してもよい。ベクトル演算手段は、干渉位置ｒｐから極小近傍位置ｒｑへ向かうベクトル、および極小近傍位置ｒｑにある注目オブジェクトと周辺オブジェクトの間の最近傍点を結ぶ最近傍ベクトルから、干渉深度ベクトルを算出してもよい。この態様によれば、干渉深度ベクトルの演算のために、例えば従来から存在する最近傍ベクトル演算手段をより明確に適用することができ、簡易に干渉深度ベクトルを算出することができる。
【００１５】
オブジェクトを仮想空間において移動または回転する移動回転手段をさらに備えてもよい。移動回転手段は、干渉深度ベクトルを用いて、干渉する１つ以上のオブジェクトを該干渉が解消する位置へ移動または回転し、報知手段は、仮想空間に配置された複数のオブジェクトを画面に表示する表示出力手段を有し、表示出力手段は、移動または回転されたオブジェクトを画面に表示することにより干渉することを報知してもよい。この態様によれば、ユーザの視覚に対してオブジェクトが干渉することを報知することができる。干渉する１以上のオブジェクトの非干渉位置への移動または回転は、相互に干渉するオブジェクトの一方を、干渉深度ベクトルの方向および大きさ以上に移動または回転させることにより行っても良く、また、相互に干渉するオブジェクトの双方を相対的に干渉深度ベクトルの方向および大きさ以上に移動または回転させることにより行っても良い。
【００１６】
報知手段は、仮想空間に配置された複数のオブジェクトを画面に表示する表示出力手段を有し、表示出力手段は、干渉すると判定された場合に、干渉深度ベクトルを用いて、干渉することを画面に表示することにより干渉することを報知してもよい。この態様によれば、例えば干渉するオブジェクトの色などの表示態様を変更することにより干渉することを報知することも可能となる。
【００１７】
報知手段は、入力された情報に応じて作動するアクチュエータに情報を出力する応答出力手段を備えてもよい。応答出力手段は、干渉すると判定された場合に、干渉深度ベクトルを用いた情報をアクチュエータに出力してアクチュエータを作動させることにより、干渉することを報知してもよい。この態様によれば、例えばユーザの触覚に対してオブジェクトが干渉することを報知することができる。
【００１８】
報知手段は、干渉深度ベクトルに応じた方向に作動し、干渉深度ベクトルのスカラー量である干渉深度に応じた力で作動するアクチュエータに情報を出力する応答出力手段を備えてもよい。応答出力手段は、干渉すると判定された場合に、干渉深度ベクトルおよび干渉深度をアクチュエータに出力してアクチュエータを作動させることにより、干渉することを報知してもよい。この態様によれば、例えばユーザの触覚に対してよりリアルにオブジェクトが干渉することを報知することができる。
【発明の効果】
【００１９】
本発明の３次元オブジェクト制御装置または３次元オブジェクト制御プログラムによれば、仮想空間に配置されたオブジェクト同士の干渉を簡易な演算により演算可能な３次元オブジェクト制御装置または３次元オブジェクト制御プログラムを提供することができる。
【発明を実施するための最良の形態】
【００２０】
図１は、一般的な干渉深度の定義を示す図であり、（ａ）はある一般的な干渉深度の定義を示す図であり、（ｂ）は他の一般的な干渉深度の定義を示す図である。図１（ａ）において、干渉深度ＰＤは、オブジェクトＡとオブジェクトＢが相互に干渉しているときにおける、オブジェクトＡとオブジェクトＢを干渉しない状態にするための最小の距離である。干渉深度ＰＤをｄとした場合、以下の式１により定義される。
【００２１】
【数１】
2006302098.tif 000003
【００２２】
また、図１（ｂ）において、干渉深度は、オブジェクトＡとオブジェクトＢのＣＳＯ（Configuration Space Obstacle）の原点から最も近い点までの距離として定義される。ＣＳＯは、オブジェクトＡとreflection of B （-B）のMinkowski sumとして、以下の式２のように定義される。
【００２３】
【数２】
2006302098.tif 000004
【００２４】
オブジェクトＡがＰＡ１、ＰＡ２、およびＰＡ３の３点を頂点とする三角形を断面に持つ３次元オブジェクトであり、オブジェクトＢがＬＢ１、ＬＢ２、ＬＢ３、およびＬＢ４の４辺を有する四角形を断面に持つ３次元オブジェクトであるとすると、ＣＳＯは、オブジェクトＢの４辺であるＬＢ１、ＬＢ２、ＬＢ３、およびＬＢ４上を、オブジェクトＡの頂点ＰＡ３が移動したときのオブジェクトＡの軌跡となる。以下の説明において、理解を容易にするため、３次元オブジェクトの断面により説明を行う。
【００２５】
図２は、オブジェクトＡとオブジェクトＢとが干渉している場合のグローバル・ミニマム（Global Minimum）とローカル・ミニマム（Local Minmum）との関係を示す図であり、（ａ）はオブジェクトＡとオブジェクトＢとが干渉した状態におけるグローバル・ミニマムとローカル・ミニマムを例示する図であり、（ｂ）はＣＳＯにおけるグローバル・ミニマムとローカル・ミニマムを例示する図である。オブジェクトＡが頂点ＰＡ１、ＰＡ２、ＰＡ３を持ち、辺ＬＡ１、ＬＡ２、ＬＡ３、ＬＡ４を持つ三角形であり、オブジェクトＢが頂点ＰＢ１、ＰＢ２、ＰＢ３、ＰＢ４を持ち、辺ＬＢ１、ＬＢ２、ＬＢ３、ＬＢ４を持つ四角形であるものとする。なお、ＬＡ２とＬＢ２が平行であり、オブジェクトＢの断面は、ＬＢ４とＬＢ２、ＬＢ１とＬＢ３がそれぞれ平行な長方形であるとする。
【００２６】
図２（ａ）において、例えば、オブジェクトＡがオブジェクトＢとの干渉を解消するために移動した場合に、オブジェクトＡがオブジェクトＢとの干渉を解消するための移動距離が極小値をとるときの干渉深度ベクトルを表したものが、本図における第１ベクトルＶ１から第５ベクトルＶ５となり、これらのベクトルの長さをローカル・ミニマムとする。この場合、まず第１ベクトルＶ１は、辺ＬＢ４から辺ＬＡ２に向かう最短距離のベクトルとなる。また第２ベクトルＶ２は、辺ＬＢ３から頂点ＰＡ２に向かう最短距離のベクトルとなる。また第３ベクトルＶ３は、辺ＬＢ１から頂点ＰＡ３へ向かう最短距離のベクトルとなる。また第４ベクトルＶ４は、頂点ＰＢ２から辺ＬＡ３へ向かう最短距離のベクトルとなる。また第５ベクトルＶ５は、辺ＬＢ２から辺ＰＡ１へ向かう最短距離のベクトルとなる。
【００２７】
前記の第１ベクトルＶ１から第５ベクトルＶ５をＣＳＯにおいて表した場合、各々のベクトルは、ＣＳＯの原点からＣＳＯの各辺に向かう最短距離のベクトルとして表される。図２（ａ）において示される相互に干渉するオブジェクトＡとオブジェクトＢのＣＳＯを表したものが図２（ｂ）に示される図となる。この場合のＣＳＯは、辺ＬＣ１、ＬＣ２、ＬＣ３、ＬＣ４、ＬＣ５、ＬＣ６を有する図形となり、前述の第１ベクトルＶ１から第５ベクトルＶ５は、ＣＳＯ原点からこれら各辺へ向かう最短距離のベクトルとなる。すなわち、第１ベクトルＶ１はＣＳＯ原点から辺ＬＣ３へ向かう最短距離のベクトルとなり、また第２ベクトルＶ２はＣＳＯ原点から辺ＬＣ２へ向かう最短距離のベクトルとなり、また第３ベクトルＶ３はＣＳＯ原点から辺ＬＣ４へ向かう最短距離のベクトルとなり、また第４ベクトルＶ４はＣＳＯ原点から辺ＬＣ５へ向かう最短距離のベクトルとなり、また第５ベクトルＶ５はＣＳＯ原点から辺ＬＣ６へ向かう最短距離のベクトルとなる。
【００２８】
３次元オブジェクトにおいて、オブジェクト同士の干渉を示す干渉深度は、一般にＣＳＯの原点から最も近い点までの距離として定義される。したがって、図２（ｂ）においては、第１ベクトルＶ１の距離が干渉深度となる。この場合の第１ベクトルＶ１の距離をグローバル・ミニマムとする。
【００２９】
図３は、干渉を始めた位置と最適な干渉深度の関係を例示する図である。前述のように、ローカル・ミニマムは第１ベクトルＶ１から第５ベクトルＶ５のように複数存在し、グローバル・ミニマムを求めるには、すべてのローカル・ミニマムを比較して、最小の値を求める必要がある。実用上の応用においては、オブジェクト同士が干渉を始めた時点の干渉深度を初期値として、初期値に最も近い最適な干渉深度を求めることが必要十分条件となる場合が多い。
【００３０】
図３（ａ）に示されるように、オブジェクトＡの辺ＬＡ２とオブジェクトＢの辺ＬＢ４とが干渉を始めて本図における干渉に至った場合は、干渉深度は、辺ＬＢ４から辺ＬＡ２へと向かう最短ベクトルである第１ベクトルＶ１の長さとなる。また、図３（ｂ）に示されるように、オブジェクトＡの頂点ＰＡ２とオブジェクトＢの辺ＬＢ３とが干渉を始めて本図における干渉に至った場合は、干渉深度は、辺ＬＢ３から頂点ＰＡ２へと向かう最短ベクトルである第２ベクトルＶ２の長さとなる。また、図３（ｃ）に示されるように、オブジェクトＡの頂点ＰＡ３とオブジェクトＢの辺ＬＢ１とが干渉を始めて本図における干渉に至った場合は、干渉深度は、辺ＬＢ１から頂点ＰＡ３へと向かう最短ベクトルである第３ベクトルＶ３の長さとなる。また、図３（ｄ）に示されるように、オブジェクトＡの辺ＬＡ３とオブジェクトＢの頂点ＰＢ２とが干渉を始めて本図における干渉に至った場合は、干渉深度は、頂点ＰＢ２から辺ＬＡ３へと向かう最短ベクトルである第４ベクトルＶ４の長さとなる。また、図３（ｅ）に示されるように、オブジェクトＡの頂点ＰＡ１とオブジェクトＢの辺ＬＢ２とが干渉を始めて本図における干渉に至った場合は、干渉深度は、辺ＬＢ２から頂点ＰＡ１へと向かう最短ベクトルである第５ベクトルＶ５の長さとなる。
【００３１】
図４は、非凸多面体が多面体と干渉する場合の部分干渉深度を例示する図であり、（ａ）は非凸多面体Ｃと凸多面体Ｄが干渉する前の状態を例示する図であり、（ｂ）は非凸多面体Ｃと凸多面体Ｄが干渉した後の状態を例示する図である。非凸多面体Ｃは、ＬＣ１からＬＣ８の８辺により形成され、辺ＬＣ１、ＬＣ２、ＬＣ３、ＬＣ４、ＬＣ８から形成される長方形から辺ＬＣ５、ＬＣ６、ＬＣ７から形成される長方形が切り取られた凹部を有する形状を断面に有する３次元オブジェクトとする。凸多面体Ｄは、ＬＤ１からＬＤ４の４辺により形成された長方形の断面を有する３次元オブジェクトとする。非凸多面体Ｃの対向する辺である辺ＬＣ４およびＬＣ８と凸多面体Ｄの対向する辺である辺ＬＤ２およびＬＤ４は平行であるものとする。また、非凸多面体Ｃの凹部の幅である辺ＬＣ５から辺ＬＣ７までの長さは、凸多面体Ｄの幅である辺ＬＤ１から辺ＬＤ３への長さより短いものとする。また、凸多面体Ｄは非凸多面体Ｃの凹部に向かって図４（ａ）に示される矢印の方向に移動しているものとする。
【００３２】
前述のように凸多面体Ｄが非凸多面体Ｃに向かって移動すると、まず凸多面体Ｄの辺ＬＤ２が非凸多面体Ｃの辺ＬＣ４および辺ＬＣ８に干渉し始める。やがて凸多面体Ｄの辺ＬＤ２に対向する辺である辺ＬＤ４も非凸多面体Ｃの辺ＬＣ４および辺ＬＣ８を通過するまで干渉が進行し、図４（ｂ）に示すような干渉状態となる。このように、非凸多面体と多面体とが干渉する場合、複数の箇所で干渉が生じる可能性がある。このような場合に、非凸多面体を凸多面体の集合として取り扱い、凸多面体の干渉深度から非凸多面体の干渉深度を計算しようと試みる場合、複数の凸多面体同士についての部分干渉深度ＰＤｐの情報から、全体干渉深度ＰＤｗを計算する必要がある。例えば、本図における非凸多面体Ｃと凸多面体Ｄの例においては、非凸多面体Ｃと凸多面体Ｄが干渉する第１部分干渉深度ＰＤｐ１および第２部分干渉深度ＰＤｐ２から、全体干渉深度ＰＤｗを計算することとなる。しかし、第１部分干渉深度ＰＤｐ１および第２部分干渉深度ＰＤｐ２のような部分干渉深度ＰＤｐから全体干渉深度ＰＤｗを求めることができるという理論的根拠はなく、その手法も確立されていない。なお、本図の説明において述べた非凸多面体の全体干渉深度ＰＤｗとは、前述のグローバル・ミニマムの干渉深度とは異なるものである。
【００３３】
図５は、非凸多面体が多面体と干渉する場合の全体干渉深度をＣＳＯにより例示する図である。本図に示されるように、非凸多面体Ｃと凸多面体Ｄが干渉する場合、非凸多面体Ｃは凹部を有しているが、ＣＳＯは長方形となる。したがって、ローカル・ミニマムはＣＳＯ原点からＣＳＯの各辺への最短距離で表すことができる。ここで、凸多面体Ｄの辺ＬＤ２が非凸多面体の辺ＬＣ４およびＬＣ８に干渉し始めて本図のような干渉状態に至っていることから、最適な干渉深度は、ＣＳＯ原点からＣＳＯの上辺への最短距離で表すことができる。
【００３４】
このような現象に鑑み、本発明者らは、３次元オブジェクト制御において、非凸多面体と多面体との干渉、および多面体の複数の多面体との干渉を把握するため鋭意研究を重ね、その結果、非干渉状態におけるオブジェクト間の最短距離や最近傍ベクトルと干渉深度の関係に着目するに至った。以下、図面を参照して本発明の実施の形態（以下、「実施形態」という。）について詳細に説明する。
【００３５】
（第１の実施形態）
図６は、第１の実施形態にかかる３次元オブジェクト制御装置５０を含むコンピュータシステム１００の外観図である。コンピュータシステム１００は、コンピュータ本体１０、ディスプレイ１２、マウス１４、キーボード１６、３次元入出力装置２０などにより構成される。コンピュータ本体１０は、内部に図示しないハードディスク、メモリ、ＣＰＵ（Central Processing Unit）などを有している。コンピュータ本体１０には、インターフェースを介してディスプレイ１２、マウス１４、キーボード１６、３次元入出力装置２０などが接続されている。
【００３６】
コンピュータ本体１０のハードディスクには、複数のオブジェクトの形状データや位置データ等が格納されている。コンピュータ本体１０は、このオブジェクトの各データをハードディスクから読み出し、メモリに格納する。コンピュータ本体１０には、これらのオブジェクトの位置や形状を制御する後述する３次元オブジェクト制御装置５０を有している。この３次元オブジェクト制御装置５０は、メモリおよびＣＰＵなどにより構成される。ハードディスクから読み出されたオブジェクトは、この３次元オブジェクト制御装置５０により仮想空間に配置された状態としてディスプレイ１２に表示出力される。操作者がマウス１４、キーボード１６を操作することにより、３次元オブジェクト制御装置５０にオブジェクトの座標などが入力され、メモリに格納されたオブジェクトのうち操作対象のオブジェクトを移動させたり回転させたりすることが可能となっている。また、操作者は、後述する３次元入出力装置２０の操作部３０を３次元空間において動かすことにより、操作対象のオブジェクトを仮想空間内で操作部３０の動きと同様に動かすことができる。
【００３７】
３次元入出力装置２０は、テーブル３６、第１ロッド３４、第２ロッド３２、操作部３０などにより構成される。第１ロッド３４は、テーブル３６に垂直方向の軸を中心として回転可能に支持されている。また、第１ロッド３４は、第１回転摺動部２６により、水平方向の軸を中心として回転可能とされている。第１ロッド３４と第２ロッド３２は、第２回転摺動部２４により、水平方向の軸を中心として回転可能とされている。第２ロッド３２と操作部３０も第３回転摺動部２２により、水平方向の軸を中心として回転可能とされている。これにより、操作者が操作部３０を操作することにより、操作部３０を様々な姿勢にすることができる。
【００３８】
テーブル３６、第１回転摺動部２６、第２回転摺動部２４、および第３回転摺動部には、ぞれぞれ図示しないエンコーダなどの回転センサが設けられており、３次元入出力装置２０を操作する者が操作部３０を操作することにより、操作部３０の姿勢に関する情報が各回転センサの回転情報としてコンピュータ本体１０内の３次元オブジェクト制御装置５０に送信される。３次元オブジェクト制御装置５０は、操作部３０の姿勢に関する情報の入力を受けて、操作部３０の姿勢に応じて仮想空間におけるオブジェクトの移動および回転を行う。以上のように、３次元入出力装置２０は、操作対象のオブジェクトを仮想空間内で操作部３０の動きと同様に動かすことができ、３軸座標入力センサとして機能する。
【００３９】
また、テーブル３６、第１回転摺動部２６、第２回転摺動部２４、および第３回転摺動部には、ぞれぞれ図示しないモータなどのアクチュエータが設けられている。例えば仮想空間における操作対象のオブジェクトが他のオブジェクトに干渉すると３次元オブジェクト制御装置５０により判断された場合に、操作対象のオブジェクトの干渉に関する情報が３次元入出力装置２０に出力される。３次元入出力装置２０は、操作対象のオブジェクトの干渉に関する情報の入力を受け、操作対象のオブジェクトの干渉の方向や大きさに応じて、各アクチュエータを作動させる。例えば、操作者が操作部３０を操作することにより、操作対象のオブジェクトが仮想空間における他のオブジェクトに干渉した場合、干渉を解消するための最短距離の方向に操作部３０に力を与えるように、３次元オブジェクト制御装置５０は各アクチュエータを作動する。なお、この際３次元オブジェクト制御装置５０は、前述の干渉深度に比例した力を操作部３０に与えるよう、各アクチュエータを作動する。なお、操作部３０に力を与える方向は、干渉したときの操作方向と逆の方向でもよい。この場合においても、前述の干渉深度に比例した力を操作部３０に与えるよう、各アクチュエータを作動させてもよい。以上のように、３次元入出力装置２０は、反力フィードバック装置として機能する。
【００４０】
図７は、第１の実施形態にかかる３次元オブジェクト制御装置５０の機能ブロック図である。３次元オブジェクト制御装置５０は、オブジェクト制御部５２、最短距離演算部５４、干渉深度ベクトル演算部５６、表示出力部５８、応答出力部６０などにより構成される。
【００４１】
オブジェクト制御部５２は、オブジェクトの移動や回転などを制御する移動回転制御部、およびオブジェクトの形状を制御する形状制御部を有している。移動回転制御部は、メモリに格納された操作対象のオブジェクトの位置データとマウス１４、キーボード１６、３次元入出力装置２０からの入力に基づいて、ＣＰＵにより操作対象のオブジェクトの、移動または回転された位置を演算する。これにより操作者は、仮想空間内のオブジェクトを移動または回転することが可能となる。
【００４２】
最短距離演算部５４は、メモリに格納されたオブジェクトの位置データおよび形状データから、ＣＰＵにより、複数のオブジェクトの最近傍点の距離である最短距離、および複数のオブジェクトの最近傍点を結ぶベクトルである最近傍ベクトルを演算する。このオブジェクト間の最短距離および最近傍ベクトルの演算は、既存の計算ライブラリを用いることができる。ここで、既存の計算ライブラリとは、例えばＳＷＩＦＴ＋＋やＰＱＰなどをいう。これらの既存の計算ライブラリを用いることにより、オブジェクト間の最短距離および最近傍ベクトルを簡易に演算することが可能となる。
【００４３】
干渉深度ベクトル演算部５６は、仮想空間に配置された複数のオブジェクトの干渉深度ベクトルを演算する。干渉深度ベクトルとは、干渉するオブジェクトのうちの一つのオブジェクトの位置である干渉位置に対して一つのオブジェクトが干渉を解消する最も近い位置である最近傍非干渉位置から、干渉位置へ向かうベクトルをいう。干渉深度ベクトル演算部５６は、最短距離演算部５４により演算されたオブジェクト間の最短距離および最近傍ベクトルの演算結果を用いて干渉深度ベクトルを演算する。これにより、既存の計算ライブラリを用いて干渉深度ベクトルを算出することができるため、簡易に干渉深度ベクトルを算出することができる。
【００４４】
算出された干渉深度ベクトルは、オブジェクト制御部５２に送信される。オブジェクト制御部５２は、仮想空間に配置された複数のオブジェクトが干渉するかを判定する干渉判定部を有している。干渉判定部は、入力を受けた干渉深度ベクトルに基づいて、オブジェクト同士が干渉するかを判定する。その結果、オブジェクト同士が干渉すると判定された場合は、干渉深度ベクトルを用いて、干渉する１以上の多面体を非干渉位置へ移動または回転させる。干渉する１以上の多面体の非干渉位置への移動または回転は、相互に干渉する多面体の一方を、干渉深度ベクトルと平行な方向に干渉深度をゼロにするまでまたはそれ以上に移動または回転させることにより行っても良い。また、相互に干渉する多面体の双方を相対的に干渉深度ベクトルと平行な方向に干渉深度をゼロにするまでまたはそれ以上に移動または回転させることにより行っても良い。
【００４５】
オブジェクト制御部５２により演算されたオブジェクトのに関する情報は、表示出力部５８に入力される。表示出力部５８は、入力を受けたオブジェクトに関する情報から、ディスプレイ１２に表示出力を行う。表示出力の入力を受けたディスプレイ１２は、画面１２ａにオブジェクトの画像を表示する。表示出力部は、一定周波数で表示の更新を行い、例えば３次元入出力装置２０により、操作対象のオブジェクトの移動や回転などの操作が行われた場合に、オブジェクトが移動する状況や回転する状況が画面１２ａに表示される。したがって、オブジェクト同士が干渉すると判定され、干渉する１以上の多面体を非干渉位置へ移動または回転させられた場合もその状況が画面１２ａに表示される。このため、３次元オブジェクト制御装置５０は、操作者に操作対象のオブジェクトが干渉する旨を報知することができ、操作者は視覚によりその干渉を認識することが可能となる。
【００４６】
また、オブジェクト同士が干渉すると判定された場合は、オブジェクト制御部５２は、応答出力部６０に、干渉深度ベクトルの方向および大きさのデータなど、干渉深度ベクトルに関する情報を出力する。応答出力部６０は、干渉深度ベクトルの方向および大きさのデータに対応する情報を３次元入出力装置２０に出力する。干渉深度ベクトルに関する情報の入力を受けた３次元入出力装置２０は、入力された情報に応じてアクチュエータを作動させる。例えば、応答出力部６０は、３次元入出力装置２０の操作部３０に干渉深度ベクトルの方向と逆方向に力がかかるように各アクチュエータに情報を出力し、各アクチュエータを動作させることができる。また、応答出力部６０は、干渉深度ベクトルの大きさに比例した力を発生するように、各アクチュエータに情報を出力し、各アクチュエータを動作させる。これにより、操作部３０を操作することによりオブジェクトを操作する操作者に、操作対象のオブジェクトが他のオブジェクトに干渉した旨を報知することができ、操作者は触覚によりその干渉を認識することが可能となる。
【００４７】
図８は、第１の実施形態にかかる３次元オブジェクト制御装置５０において、多面体同士の干渉深度の計算を行うための各変数などを表す図であり、（ａ）は後述する｜ｒ−ｒｐ｜が極小値をとらない場合を例示する図であり、（ｂ）は｜ｒ−ｒｐ｜が極小値をとる場合を例示する図である。本図において、オブジェクトＡおよびオブジェクトＢは凸多面体であり、オブジェクトＡを注目オブジェクト、オブジェクトＢをオブジェクトＡとの干渉の判定対象とな周辺オブジェクトとする。なお、オブジェクトＢを注目オブジェクトとし、オブジェクトＡを周辺オブジェクトとしてもよいことは勿論である。オブジェクトＢに対するオブジェクトＡの干渉深度ベクトルをＰＤ（Ａ，Ｂ）とする。また、オブジェクトＡの干渉位置をｒｐとし、オブジェクトＡがオブジェクトＢからεだけ離れた位置をｒとする。この場合、オブジェクトＡからオブジェクトＢの最近傍点へ向かうベクトルである最近傍ベクトルの単位ベクトルをｎとする。図８（ａ）に示されるように、｜ｒ−ｒｐ｜が極小値をとらない場合は、ｒ−ｒｐがｎと平行にならない。しかし、オブジェクトＡの非干渉位置ｒが｜ｒ−ｒｐ｜が極小値をとる極小近傍位置にあるとき、図８（ｂ）に示されるように、ｒ−ｒｐがｎと平行になり、以下の式３が成立する。
【００４８】
【数３】
2006302098.tif 000005
【００４９】
このとき、単位ベクトルｎ、ｒ−ｒｐ、干渉深度ベクトルＰＤ（Ａ，Ｂ）はすべて平行になり、干渉深度ベクトルＰＤ（Ａ，Ｂ）は以下の式４で与えられる。
【００５０】
【数４】
2006302098.tif 000006
【００５１】
このとき、干渉深度は、干渉深度ベクトルの絶対値｜ＰＤ（Ａ，Ｂ）｜により与えられる。これにより、｜ｒ−ｒｐ｜が極小値をとるときの極小近傍位置であるｒを求めることにより、干渉深度を求めることが可能となる。この場合、単位ベクトルｎの演算は、例えば既存の計算ライブラリを用いて計算することができる。
【００５２】
図９は、第１の実施形態にかかる干渉深度ベクトルを演算する処理を示すフローチャートである。本フローチャートにおける処理は、所定時間ごとに開始し、繰り返される。
【００５３】
３次元オブジェクト制御装置５０は、オブジェクトＡの入力位置ｒｉを取得しメモリに格納する（Ｓ１１）。３次元オブジェクト制御装置５０は、メモリに格納されたオブジェクトＡおよびオブジェクトＢの位置情報から、オブジェクトＡがオブジェクトＢと干渉するか判定する（Ｓ１２）。オブジェクトＡとオブジェクトＢが干渉しないと判定された場合は（Ｓ１２のＮ）、３次元オブジェクト制御装置５０は、オブジェクトＡとオブジェクトＢの最近傍ベクトルＤ（ｒ）Ｎ（ｒ）を計算し保存する（Ｓ１８）。オブジェクトＡとオブジェクトＢが干渉すると判定された場合は（Ｓ１２のＹ）、３次元オブジェクト制御装置５０は、ｒｐ＝ｒｉとする（Ｓ１３）。ｒｐ＝ｒｉとされると、３次元オブジェクト制御装置５０は、メモリに保存されていたオブジェクトＡとオブジェクトＢの最近傍ベクトルＤ（ｒ）Ｎ（ｒ）から、オブジェクトＡがオブジェクトＢからε離れた位置ｒを定義する（Ｓ１４）。rが定義されると、３次元オブジェクト制御装置５０は、｜ｒ−ｒｐ｜を演算し、｜ｒ−ｒｐ｜が極小値を取るときの極小近傍非干渉位置であるｒと、そのときの最近傍ベクトルの単位ベクトルｎを算出する（Ｓ１５）。最近傍ベクトルの単位ベクトルｎが算出されると、３次元オブジェクト制御装置５０は、式４から、干渉深度ベクトルＰ（Ａ，Ｂ）を算出する（Ｓ１６）。
【００５４】
３次元オブジェクト制御装置５０のオブジェクト制御部５２は、オブジェクトＡの入力位置とその時の干渉深度ベクトルＰ（Ａ，Ｂ）の情報から、３次元オブジェクト制御装置５０のオブジェクト制御部５２は、干渉を解消するようにオブジェクトＡの位置を制御する。具体的には、オブジェクトＡをオブジェクトＢの非干渉位置まで移動または回転することにより、干渉を解消するようにオブジェクトＡの位置を制御する。オブジェクト制御部５２により位置が制御されたオブジェクトＡは、表示出力部５８を介してディスプレイ１２に表示出力され、ディスプレイ１２の画面１２ａにオブジェクトＡのが表示される（Ｓ１７）。これにより、ユーザはディスプレイ１２の画面１２ａを通じて、視覚により３次元仮想空間におけるオブジェクト同士の干渉を確認することができる。なお、オブジェクト制御部５２は、オブジェクトＡおよびオブジェクトＢの双方を非干渉位置まで移動または回転することにより干渉を解消するようにオブジェクトＡおよびオブジェクトＢの位置を制御してもよいことは勿論である。
【００５５】
また、３次元オブジェクト制御装置５０のオブジェクト制御部５２は、オブジェクトＡの入力位置とその時の干渉深度ベクトルＰ（Ａ，Ｂ）の情報から、応答出力部６０に干渉深度ベクトルに関する情報を出力する（Ｓ１７）。応答出力部６０は、干渉深度ベクトルの方向および大きさのデータに対応する情報を３次元入出力装置２０に出力し、干渉深度ベクトルに関する情報の入力を受けた３次元入出力装置２０は、入力された情報に応じてアクチュエータを作動させる。これにより、ユーザは３次元入出力装置２０により、触覚により３次元仮想空間におけるオブジェクト同士の干渉を確認することができる。
【００５６】
図１０は、第１の実施形態にかかる３次元オブジェクト制御装置５０において、多面体同士の干渉深度の計算を行うための各変数などを表す図である。本実施形態においては、３次元オブジェクト制御装置５０は、凸多面体同士が干渉した場合の干渉深度の計算を行う。
【００５７】
本図において、オブジェクトＡがオブジェクトＢからεだけ離れた位置をｒｎとして、初期設定におけるｒｎをｒ０とする。凸多面体同士の場合は、εは任意の値をとることができる。この場合、式３を満たすようなｒを、以下の式５に示される計算アルゴリズムにより算出する。
【００５８】
【数５】
2006302098.tif 000007
【００５９】
なお、ｐｎ・ｎｎはベクトルｐｎとベクトルｎｎの内積を表す。Δｈｎがゼロになるまで上記の計算が反復して行われる。Δｈｎがゼロになると、解が収束され、上記の計算は終了する。ここで、Ｎ（ｒ）は、仮想空間に配置された非干渉状態におけるオブジェクト間の最近傍点を結ぶ最近傍ベクトルを算出する最近傍ベクトルを示し、本図における例においては、オブジェクトＡがｒにあるときのオブジェクトＡからオブジェクトＢの最近傍点に向かう最近傍ベクトルの単位ベクトルを示す。また、Ｄ（ｒ）は、仮想空間に配置された非干渉状態におけるオブジェクト間の最短距離を示し、本図における例においては、オブジェクトＡがｒにあるときのオブジェクトＡからオブジェクトＢの最近傍点までの最短距離を示す。仮想空間に配置されたオブジェクトが相互に干渉する場合、Ｄ（ｒ）はゼロ以下の値を返す。Ｎ（ｒ）とＤ（ｒ）は、例えば既存の最短距離の計算ライブラリを用いて計算することができる。Δｈｎがゼロになった時点のｎｎおよびｐｎにより、干渉深度ベクトルは、以下の式６で与えられる。
【００６０】
【数６】
2006302098.tif 000008
【００６１】
図１１は、第１の実施形態にかかるオブジェクト間の干渉深度ベクトルの計算アルゴリズムにおける計算の経過を示す図であり、（ａ）は干渉深度ベクトルの計算のある過程を示す図であり、（ｂ）は干渉深度ベクトルの計算の次の過程を示す図である。図１１（ａ）および（ｂ）において、理解を容易にするため、オブジェクトＡの位置は、頂点ＰＡ６を基準に図示する。図１１（ａ）および（ｂ）においては、オブジェクトＡを注目オブジェクト、オブジェクトＢを前述の周辺オブジェクトとする。なお、オブジェクトＢを注目オブジェクトとし、オブジェクトＡを周辺オブジェクトとしてもよいことは勿論である。オブジェクトＡは、オブジェクトＢに対して、オブジェクトＡの辺ＬＡ６が辺ＬＡ６と平行なオブジェクトＢの辺ＬＢ６に干渉をし始め、干渉位置であるｒｐに位置しているものとする。この場合、干渉深度ベクトルＰＤ（Ａ，Ｂ）は、図１１（ａ）および（ｂ）に示されるように辺ＬＢ６から辺ＬＡへ向かうベクトルとなる。
【００６２】
これに対し、図１１（ａ）に示されるように、オブジェクトＡの非干渉位置を、オブジェクトＢの辺ＬＢ６ではなく辺ＬＢ５に対してεだけ離れた位置であるｒｎとした場合、オブジェクトＡとオブジェクトＢとの距離は、オブジェクトＡの頂点ＰＡ７と辺ＬＢ５との距離となる。ここで、３次元オブジェクト制御装置５０は、式５のΔｈｎがゼロとなるオブジェクトＡの位置ｒ’ｎを算出する。次に、３次元オブジェクト制御装置５０は、既存の最短距離の計算ライブラリを用いて、Ｎ（ｒ’ｎ）Ｄ（ｒ’ｎ）を算出し、オブジェクトＡをオブジェクトＢからεの離れた位置であるｒｎ＋１までＮ（ｒ’ｎ）と平行な方向に移動する。次に３次元オブジェクト制御装置５０は、図１１（ｂ）に示されるように、式５のΔｈｎ＋１がゼロとなるオブジェクトＡの位置ｒ’ｎ＋１を算出する。このｒ’ｎ＋１ではオブジェクトＡとオブジェクトＢの距離はεのままなので、ｒ’ｎ＋１はｒｎ＋２となる。これにより、｜ｒ−ｒｐ｜が極小値をとるオブジェクトＡの位置であるｒを算出することができる。したがって、算出されたｒｎ＋２から式６により干渉深度ベクトルＰＤ（Ａ，Ｂ）を算出することができ、また干渉深度ベクトルＰＤ（Ａ，Ｂ）の絶対値を求めることにより干渉深度を求めることができる。
【００６３】
（第２の実施形態）
図１２は、第２の実施形態にかかるオブジェクト間の干渉深度ベクトルの計算アルゴリズムにおける計算の経過を示す図であり、（ａ）は干渉深度ベクトルの計算のある過程を示す図であり、（ｂ）は干渉深度ベクトルの計算の次の過程を示す図である。前述と同様に、オブジェクトＡを注目オブジェクト、オブジェクトＢを前述の周辺オブジェクトとする。なお、オブジェクトＢを注目オブジェクトとし、オブジェクトＡを周辺オブジェクトとしてもよいことは勿論である。オブジェクトＡは、頂点ＰＡ１１、ＰＡ１２、ＰＡ１３を有し、ＰＡ１２が角度が９０°より大きい非凸多面体である。オブジェクトＢも頂点ＰＢ１１、ＰＢ１２、ＰＢ１３を有し、ＰＢ１２が角度が９０°より大きい非凸多面体である。図１２（ａ）および（ｂ）において、理解を容易にするため、オブジェクトＡの位置は、頂点ＰＡ１１を基準に図示する。
【００６４】
このように、非凸多面体同士の干渉、またはいずれか一方が非凸多面体である多面体同士の干渉における干渉深度ベクトルを算出するための非干渉位置ｒを以下の式７を用いて算出することができる。
【００６５】
【数７】
2006302098.tif 000009
【００６６】
式７において、前述と同様に、Ｎ（ｒ）は、仮想空間に配置された非干渉状態におけるオブジェクト間の最近傍点を結ぶ最近傍ベクトルを算出する最近傍ベクトルを示す。また、Ｄ（ｒ）は、仮想空間に配置された非干渉状態におけるオブジェクト間の最短距離を示す。仮想空間に配置されたオブジェクトが相互に干渉する場合、Ｄ（ｒ）はゼロ以下の値を返す。また、εは許容誤差であり、αは定数であり、ゼロより大きく０．５より小さい値が設定される。ｒ０は、干渉するオブジェクトの、干渉されるオブジェクトに対する非干渉位置の初期位置を表す。ｍｉｎ（αε，｜Δｈｎ｜）とは、αεと｜Δｈｎ｜のうち小さい方の値を表す。計算アルゴリズムの対象となるオブジェクトが凸多面体同士でない場合は、Δｈの移動により非干渉オブジェクトが干渉する場合がある。そのため、｜Δｈ｜の大きさをεより小さい値であるαε以下にすることにより、非干渉オブジェクトが干渉しないようにする。ｍｉｎ（αε,｜Δｈ｜）＜εは常に成立する。
【００６７】
図１２（ａ）および（ｂ）に示されるように、オブジェクトＡがオブジェクトＢに干渉し、干渉位置ｒｐにあるものとする。図１２（ａ）において、３次元オブジェクト制御装置５０は、オブジェクトＡがオブジェクトＢの表面からεｎｎだけ離れた位置ｒｎの非干渉位置を定義する。本図の例においては、ｒｎは、オブジェクトＡの頂点ＰＡ１１がオブジェクトＢの辺ＬＢ１１からεの距離を持つ位置として定義される。３次元オブジェクト制御装置５０は、ｒｎからαεΔｈｎ／｜Δｈｎ｜とΔｈｎのうち小さい方だけ移動した位置ｒ’ｎを算出する。本図の例においては、αεΔｈｎ／｜Δｈｎ｜の方が小さいのでｒ’ｎはｒｎからαεΔｈｎ／｜Δｈｎ｜だけ移動した位置となる。
【００６８】
ここで、１つの多面体と２以上の多面体との干渉、または１つの多面体と１つ以上の非凸多面体との干渉を考える場合、ｒｎからｒ’ｎに移動することにより他の多面体または同一の多面体の他の部分に近づくまたは干渉する可能性がある。本図の例においては、ｒｎからｒ’ｎに移動することにより、オブジェクトＡの頂点ＰＡ１３がオブジェクトＢの辺ＬＢ１２にεより小さい距離まで近づく。このため、３次元オブジェクト制御装置５０は、オブジェクトＡをＮ（ｒ’ｎ）Ｄ（ｒ’ｎ）だけ移動した位置であるｒｎ＋１まで移動する。これにより、オブジェクトＡの位置ｒｎ＋１は、オブジェクトＢのある表面からεｎｎ＋１だけ離れた位置となる。
【００６９】
次に、図１２（ｂ）に示されるように、３次元オブジェクト制御装置５０は、ｒｎ＋１からαεΔｈｎ／｜Δｈｎ｜とΔｈｎのうち小さい方だけ移動した位置ｒ’ｎ＋１を算出する。本図の例においては、やはりαεΔｈｎ／｜Δｈｎ｜の方が小さいのでｒ’ｎ＋１はｒｎ＋１からαεΔｈｎ／｜Δｈｎ｜だけ移動した位置となる。
【００７０】
凸オブジェクト同士の場合は、Δｈｎの移動により、Ｄ（ｒ）が減少することはない。しかし、少なくとも一方が凹オブジェクトであるオブジェクト同士、および一つのオブジェクトの周辺に複数のオブジェクトが存在する場合のオブジェクト同士なども含む、一般的なオブジェクト同士の場合は、Δｈｎの移動により、Ｄ（ｒ）が減少したり、干渉が生じて最短距離が計算できない場合がある。したがって、Δｈｎをεよりも小さい値であるｍｉｎ（αε，｜Δｈｎ｜）Δｈｎ ／｜Δｈｎ｜に修正する。また、（ｐｎ・ｎｎ）＜０となる場合があるが、この場合は、Δｈｎ  ＝−ｐｎとする。Ｄ（ｒ’ｎ）がεよりも小さくなった場合は、ｒ’に補正（ε−Ｄ（ｒ’ｎ））ｇ／ｇ・ｎｎ＋１を行う。Ｄ（ｒ’’ｎ）がεよりも小さくなった場合は、ｒ’’に補正（ε−Ｄ（ｒ’’ｎ））ｆ／ｆ・Ｎ（ｒ’’ｎ）を行う。ここで、ｇはｎｎ＋１からｎｎに平行な成分を引いたベクトルであり、ｇ・ｎｎ＝０が成り立つ。ｆは、ｎｎとｎｎ＋１に垂直なベクトルであり、ｆ・ｎｎ＝０、ｆ・ｎｎ＋１＝０が成り立つ。
【００７１】
本実施形態においては、オブジェクトＡがｒｎ＋１からｒ’ｎ＋１に移動することにより、オブジェクトＡの頂点ＰＡ１１がオブジェクトＢの辺ＬＢ１１にεより小さい距離まで近づく。これにより、Ｄ（ｒ）がεよりも小さくなるので、（ε−Ｄ（ｒ’ｎ））／（ｇ＊ｎｎ＋１）による補正が行われる。以上より、オブジェクトＡはｒ’ｎ＋１からオブジェクトＢのある表面からεｎｎ＋１だけ離れた位置であるｒｎ＋２へ移動する。アルゴリズム中で、干渉が発生する場合は、オブジェクトＡを（ε−Ｄ（ｒ））Ｎ（ｒ）移動させることによって、最近傍点が変化したときに発生する可能性がある。この場合は、最近傍点を再計算する。
【００７２】
一般的な多面体同士の場合、Δｈｎはゼロになるとは限らないが、解がローカル・ミニマムの近傍に達したときは、Ｄ（ｒ’’ｎ）がεより小さくなった場合や、｜ｐｎ＋１｜が｜ｐｎ｜よりも大きくなる場合がある。このとき解が収束したとみなし、干渉深度ベクトルの近似値は、以下の式８により与えられる。Ｄ（ｒ’ｎ）≦０、Ｄ（ｒ’’ｎ）≦０、Ｄ（ｒ’’’ｎ）≦０、となった場合も、ローカル・ミニマムの近傍に達したとみなし、ｒｎを収束解とする。なお、あるεで計算した収束解を初期値として、より小さい値をεに設定することによって、より精度の高い結果を得ることも可能である。
【００７３】
【数８】
2006302098.tif 000010
【００７４】
図１３は、第２の実施形態における多面体オブジェクト間の実際の干渉深度の計算の例を示す図であり、（ａ）は計算に用いられたオブジェクトを示す図であり、（ｂ）は算出された干渉深度と計算時間を示す図である。本計算は、図１３（ａ）に示される凸多面体同士の干渉における干渉深度の計算を例としている。図１３（ｂ）において、Ｐ１は従来の計算アルゴリズムであるＳＷＩＦＴ＋＋とＤＥＥＰの計算ライブラリを用いた場合おける干渉深度であり、Ｐ２は本実施形態における計算アルゴリズムにおいて、α＝０．９、ε＝０．００１、反復数１でＳＷＩＦＴ＋＋の計算ライブラリを用いた場合の干渉深度であり、Ｐ３は本実施形態における計算アルゴリズムにおいて、α＝０．９、ε＝０．００１、反復数１でＰＱＰの計算ライブラリを用いた場合の干渉深度である。本図に示されるように、算出された干渉深度はいずれもほぼ同じ値となっている。
【００７５】
Ｔ１はＰ１の計算時間、Ｔ２はＰ２の計算時間、Ｔ３はＰ３の計算時間である。本実施形態における計算アルゴリズムによる計算時間Ｔ３は、従来の計算アルゴリズムによる計算時間Ｔ１よりも大きい。しかし、本実施形態における計算アルゴリズムによる別の計算時間Ｔ２では、従来の計算アルゴリズムによる計算時間Ｔ１よりも小さくなっている。これにより、適切な計算ライブラリを選択することにより、干渉深度の計算時間を短縮化することが可能となる。
【００７６】
図１４は、第２の実施形態における多面体オブジェクト間の実際の干渉深度の計算の例を示す図であり、（ａ）は計算に用いられたオブジェクトを示す図であり、（ｂ）は算出された干渉深度と計算時間を示す図である。本計算は、図１４（ａ）に示される非凸多面体と多面体との干渉における干渉深度の計算を例としている。図１４（ｂ）において、Ｐ４は本実施形態における計算アルゴリズムにおいて、ε＝０．０１、反復数１でＳＷＩＦＴ＋＋の計算ライブラリを用いた場合の干渉深度であり、Ｐ５は本実施形態における計算アルゴリズムにおいて、ε＝０．０１、反復数１でＰＱＰの計算ライブラリを用いた場合の干渉深度である。本図に示されるように、本実施形態における３次元オブジェクト制御装置によれば、非凸多面体と多面体との干渉深度の計算も行うことが可能となる。算出された干渉深度はいずれの場合もほぼ同じ値となっている。
【００７７】
Ｔ４はＰ４の計算時間、Ｔ５はＰ５の計算時間である。Ｔ５は、Ｔ４よりも大きくなっており、適切な計算ライブラリを選択することにより、より短時間で非凸多面体と多面体との干渉深度の計算を行うことができる。
【００７８】
以上、本発明を実施形態をもとに説明した。これらの実施形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下、そうした例をあげる。
【００７９】
オブジェクト同士が干渉することの報知は、干渉する一方または双方のオブジェクトの形状を変形させて干渉を解消し、変形させられたオブジェクトをディスプレイ１２の画面１２ａに表示することにより行ってもよい。この場合、オブジェクトの形状を変形させることは、オブジェクト制御部５２の形状制御部により行われる。
【００８０】
また、オブジェクト同士が干渉することの報知は、干渉深度ベクトルを画面１２ａに表示する、干渉が生じたオブジェクトの色を変更するなど表示態様を変更して画面１２ａに表示する、などにより行っても良い。
【図面の簡単な説明】
【００８１】
【図１】一般的な干渉深度の定義を示す図であり、（ａ）はある一般的な干渉深度の定義を示す図であり、（ｂ）は他の一般的な干渉深度の定義を示す図である。
【図２】オブジェクトＡとオブジェクトＢとが干渉している場合のグローバル・ミニマムとローカル・ミニマムとの関係を示す図であり、（ａ）はオブジェクトＡとオブジェクトＢとが干渉した状態におけるグローバル・ミニマムとローカル・ミニマムを例示する図であり、（ｂ）はＣＳＯにおけるグローバル・ミニマムとローカル・ミニマムを例示する図である。
【図３】干渉を始めた位置と最適な干渉深度の関係を例示する図である。
【図４】非凸多面体が多面体と干渉する場合の部分干渉深度を例示する図であり、（ａ）は非凸多面体Ｃと凸多面体Ｄが干渉する前の状態を例示する図であり、（ｂ）は非凸多面体Ｃと凸多面体Ｄが干渉した後の状態を例示する図である。
【図５】非凸多面体が多面体と干渉する場合の全体干渉深度をＣＳＯにより例示する図である。
【図６】第１の実施形態にかかる次元オブジェクト制御装置を含むコンピュータシステムの外観図である。
【図７】第１の実施形態にかかる次元オブジェクト制御装置の機能ブロック図である。
【図８】第１の実施形態にかかる次元オブジェクト制御装置において、多面体同士の干渉深度の計算を行うための各変数などを表す図であり、（ａ）は｜ｒ−ｒｐ｜が極小値をとらない場合を例示する図であり、（ｂ）は｜ｒ−ｒｐ｜が極小値をとる場合を例示する図である。
【図９】第１の実施形態にかかる干渉深度ベクトルを演算する処理を示すフローチャートである。
【図１０】第１の実施形態にかかる次元オブジェクト制御装置において、多面体同士の干渉深度の計算を行うための各変数などを表す図である。
【図１１】第１の実施形態にかかるオブジェクト間の干渉深度ベクトルの計算アルゴリズムにおける計算の経過を示す図であり、（ａ）は干渉深度ベクトルの計算のある過程を示す図であり、（ｂ）は干渉深度ベクトルの計算の次の過程を示す図である。
【図１２】第２の実施形態にかかるオブジェクト間の干渉深度ベクトルの計算アルゴリズムにおける計算の経過を示す図であり、（ａ）は干渉深度ベクトルの計算のある過程を示す図であり、（ｂ）は干渉深度ベクトルの計算の次の過程を示す図である。
【図１３】第２の実施形態における多面体オブジェクト間の実際の干渉深度の計算の例を示す図であり、（ａ）は計算に用いられたオブジェクトを示す図であり、（ｂ）は算出された干渉深度と計算時間を示す図である。
【図１４】第２の実施形態における多面体オブジェクト間の実際の干渉深度の計算の例を示す図であり、（ａ）は計算に用いられたオブジェクトを示す図であり、（ｂ）は算出された干渉深度と計算時間を示す図である。
【符号の説明】
【００８２】
１０  コンピュータ本体、  １２  ディスプレイ、  ２０  ３次元入出力装置、  ５０  ３次元オブジェクト制御装置、  ５２  オブジェクト制御部、  ５４  最短距離演算部、  ５６  干渉深度ベクトル演算部、  ５８  表示出力部、  ６０  応答出力部。
【図１】
2006302098.tif 000011
【図２】
2006302098.tif 000012
【図３】
2006302098.tif 000013
【図４】
2006302098.tif 000014
【図５】
2006302098.tif 000015
【図６】
2006302098.tif 000016
【図７】
2006302098.tif 000017
【図８】
2006302098.tif 000018
【図９】
2006302098.tif 000019
【図１０】
2006302098.tif 000020
【図１１】
2006302098.tif 000021
【図１２】
2006302098.tif 000022
【図１３】
2006302098.tif 000023
【図１４】
2006302098.tif 000024