(57)【要約】【課題】三次元物体同士の干渉の有無の評価と併せて、両者の隙間距離や最近傍位置の評価を高速に処理する。【解決手段】干渉チェック装置１０は、仮想空間をメッシュ分割して小さな領域に細分化する空間細分化部１１、メッシュの各頂点と基準物体オブジェクトの表面までの最短距離と方向を算出して各メッシュ頂点に付随する情報として登録することで基準物体オブジェクトまでの最短距離マップを作成する最短距離マップ作成部１２、移動物体オブジェクト上に基準物体オブジェクトまでの最短距離を評価するための評価点を設定する最短距離評価点設定部１３、最短距離評価点の座標値に基づいて最短距離マップを参照することで基準物体オブジェクトまでの最短距離を取得する干渉チェック部１４を備える。【選択図】図２
2011079105.tif 000002
【特許請求の範囲】
【請求項１】
仮想空間上で三次元形状物体同士の干渉をチェックする方法であって、
演算装置が以下の各々のステップ、すなわち、
仮想空間をメッシュ分割して小さな領域に細分化する空間細分化ステップと、
前記メッシュの各頂点と基準対象物である基準物体オブジェクトの表面までの最短距離と方向を算出し、各メッシュ頂点に付随する情報として登録することにより、基準物体オブジェクトまでの最短距離マップを作成する最短距離マップ作成ステップと、
前記仮想空間上を移動する移動物体オブジェクト上に、前記基準物体オブジェクトまでの最短距離を評価するための評価点を設定する最短距離評価点設定ステップと、
前記最短距離評価点の座標値に基づいて最短距離マップを参照することにより前記基準物体オブジェクトまでの最短距離を取得して、移動物体オブジェクトと基準物体オブジェクトとの干渉の有無を評価する干渉チェックステップと、
を実行することを特徴とする干渉チェック方法。
【請求項２】
前記干渉チェックステップにおいて、更に干渉するまでの隙間距離を評価することを特徴とする請求項１記載の干渉チェック方法。
【請求項３】
前記干渉チェックステップにおいて、評価した隙間距離が設定した閾値よりも小さいときは、前記演算装置が前記移動物体オブジェクト上の最短距離評価点の数を増やして密度が高くなるように再定義することで、前記基準物体オブジェクトとの干渉の有無及び干渉するまでの隙間距離を再評価することを特徴とする請求項１又は２記載の干渉チェック方法。
【請求項４】
前記最短距離マップ作成ステップにおいて、前記演算装置が前記基準物体オブジェクトまでの最短距離マップを作成した後、別の基準物体オブジェクトについて同様に最短距離マップを作成し、元の最短距離マップに設定されている最短距離と比較して距離の小さい方を採用することにより、最短距離マップを合成することを特徴とする請求項１乃至３のいずれか１項記載の干渉チェック方法。
【請求項５】
前記移動物体オブジェクトの移動量が、移動前に評価した隙間距離よりも小さいときは、前記演算装置が干渉チェックステップを省略することを特徴とする請求項１乃至４のいずれか１項記載の干渉チェック方法。
【請求項６】
仮想空間上で三次元形状物体同士の干渉をチェックする装置であって、
仮想空間をメッシュ分割して小さな領域に細分化する空間細分化部と、
前記メッシュの各頂点と基準対象物である基準物体オブジェクトの表面までの最短距離と方向を算出し、各メッシュ頂点に付随する情報として登録することにより、基準物体オブジェクトまでの最短距離マップを作成する最短距離マップ作成部と、
前記仮想空間上を移動する移動物体オブジェクト上に、前記基準物体オブジェクトまでの最短距離を評価するための評価点を設定する最短距離評価点設定部と、
前記最短距離評価点の座標値に基づいて最短距離マップを参照することにより前記基準物体オブジェクトまでの最短距離を取得して、移動物体オブジェクトと基準物体オブジェクトとの干渉の有無を評価する干渉チェック部と、
を備えることを特徴とする干渉チェック装置。
【請求項７】
前記干渉チェック部において、更に干渉するまでの隙間距離を評価することを特徴とする請求項６記載の干渉チェック装置。
【請求項８】
前記干渉チェック部において、評価した隙間距離が設定した閾値よりも小さいときは、前記移動物体オブジェクト上の最短距離評価点の数を増やして密度が高くなるように再定義することで、前記基準物体オブジェクトとの干渉の有無及び干渉するまでの隙間距離を再評価することを特徴とする請求項６又は７記載の干渉チェック装置。
【請求項９】
前記最短距離マップ作成部において、前記基準物体オブジェクトまでの最短距離マップを作成した後、別の基準物体オブジェクトについて同様に最短距離マップを作成し、元の最短距離マップに設定されている最短距離と比較して距離の小さい方を採用することにより、最短距離マップを合成することを特徴とする請求項６乃至８のいずれか１項記載の干渉チェック装置。
【請求項１０】
前記移動物体オブジェクトの移動量が、移動前に評価した隙間距離よりも小さいときは、干渉チェック部を使用しないことを特徴とする請求項６乃至９のいずれか１項記載の干渉チェック装置。
【請求項１１】
演算装置を、仮想空間上で三次元形状物体同士の干渉をチェックする装置として動作させる干渉チェックプログラムであって、
前記演算装置を、
仮想空間をメッシュ分割して小さな領域に細分化する空間細分化部と、
前記メッシュの各頂点と基準対象物である基準物体オブジェクトの表面までの最短距離と方向を算出し、各メッシュ頂点に付随する情報として登録することにより、基準物体オブジェクトまでの最短距離マップを作成する最短距離マップ作成部と、
前記仮想空間上を移動する移動物体オブジェクト上に、前記基準物体オブジェクトまでの最短距離を評価するための評価点を設定する最短距離評価点設定部と、
前記最短距離評価点の座標値に基づいて最短距離マップを参照することにより前記基準物体オブジェクトまでの最短距離を取得して、移動物体オブジェクトと基準物体オブジェクトとの干渉の有無を評価する干渉チェック部とを備えた干渉チェック装置として動作させることを特徴とする干渉チェックプログラム。
【請求項１２】
前記干渉チェック部において、更に干渉するまでの隙間距離を評価することを特徴とする請求項１１記載の干渉チェックプログラム。
【請求項１３】
前記干渉チェック部において、評価した隙間距離が設定した閾値よりも小さいときは、前記移動物体オブジェクト上の最短距離評価点の数を増やして密度が高くなるように再定義することで、前記基準物体オブジェクトとの干渉の有無及び干渉するまでの隙間距離を再評価することを特徴とする請求項１１又は１２記載の干渉チェックプログラム。
【請求項１４】
前記最短距離マップ作成部において、前記基準物体オブジェクトまでの最短距離マップを作成した後、別の基準物体オブジェクトについて同様に最短距離マップを作成し、元の最短距離マップに設定されている最短距離と比較して距離の小さい方を採用することにより、最短距離マップを合成することを特徴とする請求項１１乃至１３のいずれか１項記載の干渉チェックプログラム。
【請求項１５】
前記移動物体オブジェクトの移動量が、移動前に評価した隙間距離よりも小さいときは、干渉チェック部を使用しないことを特徴とする請求項１１乃至１４のいずれか１項記載の干渉チェックプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想空間上に定義された三次元オブジェクト同士の衝突の有無を判定する干渉チェック方法、干渉チェック装置、及び干渉チェックプログラムに関する。
【背景技術】
【０００２】
仮想空間上に定義された三次元オブジェクト同士の衝突の有無を判定することを一般に干渉チェックと呼んでおり、三次元ＣＡＤや、ロボットや機械の動作シミュレーション、ゲームソフトウェア、コンピュータグラフィックスなどの分野で広く使われている。
【０００３】
例えば、ロボットのシミュレーションは、実際のロボットを動作させる前にシミュレータ上で動きを確認するために使用される。垂直多関節型ロボットやスカラ型ロボットに代表されるロボットマニピュレータは、作業対象物や周辺構造物と干渉しないようにロボットの動作を設定する必要がある。そのような動作をシミュレータ上で決定するオフラインティーチングと呼ばれる作業に対して干渉チェックの機能が必要となる。この際には、単に干渉の有無の確認だけではなく、干渉が無い場合でも干渉する可能性のある物体までの最短距離や最近傍位置などの情報が得られるとオフラインティーチングの作業性を向上させることができる。
【０００４】
一般に、仮想空間上の三次元オブジェクトは、三角形状などの多角形ポリゴンで表現する。ポリゴンで構成された物体同士の干渉チェックは、各ポリゴン同士の干渉を幾何学的な条件に基づいて判定すれば可能であるが、ポリゴンの総数が増加すると膨大な計算量となることから、計算量を削減するための手法が提案されている。
【０００５】
例えば、物体オブジェクトの外形を包括する球を定義して球同士の半径を比較することで干渉チェックを行い、干渉があれば包括する球を細分化して詳細なチェックを行う方法（特許文献１参照）や、同様に球領域で干渉チェックを行う手法でも非凸形状の物体に対しても凸形状に分解することで計算効率を高めたもの（特許文献２、３参照）などが提案されている。また、球領域による干渉チェックのほかにも直方体領域で評価する手法なども知られており、評価領域を細分化することにより厳密な評価を行う手法は広く使われているものである。
【０００６】
一方、物体同士の厳密な干渉チェックを行うのではなく、動作空間をセル状に分割して障害物が無いセクタを動作可能空間として定義する方法（特許文献４参照）や、空間をセル状に細分化して物体オブジェクトが置かれている領域のセルにフラグを立てて複数の物体オブジェクトで同じセルにフラグを立てた場合は干渉と判断する方法（特許文献５参照）なども提案されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平０８−２８７２９２号公報
【特許文献２】特許第２９１５８２６号公報
【特許文献３】特許第３５５６６４４号公報
【特許文献４】特開平１０−２０９１６号公報
【特許文献５】特開２００８−３０５３４７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述した干渉チェック方法では、単純にポリゴン同士の干渉チェックを総組み合わせで行うよりも格段に少ない計算量で行える。しかし、干渉の有無の確認だけでなく物体間の最短距離や最近傍点の評価を行いたい場合には、干渉チェックの計算とは別に処理を行う必要があり、計算量の増加を招くという課題があった。
【０００９】
また、複雑な形状の物体について干渉チェックの精度を上げるためには、構成ポリゴン数を増やして三次元形状の表現精度を上げざるを得ないが、従来の技術では計算量の増加に伴い、処理速度の低下を招くという課題があった。
【００１０】
先に述べたロボットシミュレーションでは、実際にロボットを動作させる際に、並行して干渉チェックや障害物までの最短距離の評価を行い、ロボットが障害物に干渉する前に停止させる衝突防止機能として活用することも想定されるが、このような利用においてはリアルタイムに干渉チェックを行えるように、短時間で処理を完了できるようにする必要がある。
【００１１】
従って、本発明は上述した課題を解決するためになされたものであり、三次元物体同士の干渉の有無の評価と併せて、両者の隙間距離や最近傍位置の評価を高速に処理することのできる干渉チェック方法、干渉チェック装置、及び干渉チェックプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述の目的を達成するため、本発明の干渉チェック方法は、仮想空間上で三次元形状物体同士の干渉をチェックする方法であって、演算装置が以下の各々のステップ、すなわち、仮想空間をメッシュ分割して小さな領域に細分化する空間細分化ステップと、前記メッシュの各頂点と基準対象物である基準物体オブジェクトの表面までの最短距離と方向を算出し、各メッシュ頂点に付随する情報として登録することにより、基準物体オブジェクトまでの最短距離マップを作成する最短距離マップ作成ステップと、前記仮想空間上を移動する移動物体オブジェクト上に、前記基準物体オブジェクトまでの最短距離を評価するための評価点を設定する最短距離評価点設定ステップと、前記最短距離評価点の座標値に基づいて最短距離マップを参照することにより前記基準物体オブジェクトまでの最短距離を取得して、移動物体オブジェクトと基準物体オブジェクトとの干渉の有無を評価する干渉チェックステップと、を実行することを特徴とする。
【００１３】
また、本発明の干渉チェック装置は、仮想空間上で三次元形状物体同士の干渉をチェックする装置であって、仮想空間をメッシュ分割して小さな領域に細分化する空間細分化部と、前記メッシュの各頂点と基準対象物である基準物体オブジェクトの表面までの最短距離と方向を算出し、各メッシュ頂点に付随する情報として登録することにより、基準物体オブジェクトまでの最短距離マップを作成する最短距離マップ作成部と、前記仮想空間上を移動する移動物体オブジェクト上に、前記基準物体オブジェクトまでの最短距離を評価するための評価点を設定する最短距離評価点設定部と、前記最短距離評価点の座標値に基づいて最短距離マップを参照することにより前記基準物体オブジェクトまでの最短距離を取得して、移動物体オブジェクトと基準物体オブジェクトとの干渉の有無を評価する干渉チェック部と、を備えることを特徴とする。
【００１４】
更に、本発明の干渉チェックプログラムは、演算装置を、仮想空間上で三次元形状物体同士の干渉をチェックする装置として動作させる干渉チェックプログラムであって、前記演算装置を、仮想空間をメッシュ分割して小さな領域に細分化する空間細分化部と、前記メッシュの各頂点と基準対象物である基準物体オブジェクトの表面までの最短距離と方向を算出し、各メッシュ頂点に付随する情報として登録することにより、基準物体オブジェクトまでの最短距離マップを作成する最短距離マップ作成部と、前記仮想空間上を移動する移動物体オブジェクト上に、前記基準物体オブジェクトまでの最短距離を評価するための評価点を設定する最短距離評価点設定部と、前記最短距離評価点の座標値に基づいて最短距離マップを参照することにより前記基準物体オブジェクトまでの最短距離を取得して、移動物体オブジェクトと基準物体オブジェクトとの干渉の有無を評価する干渉チェック部とを備えた干渉チェック装置として動作させることを特徴とする。
【発明の効果】
【００１５】
本発明によれば、三次元物体同士の干渉の有無の評価を高速に処理することができる。
【００１６】
また、本発明によれば、三次元物体同士の隙間距離や最近傍位置の評価を高速に処理することができる。
【図面の簡単な説明】
【００１７】
【図１】基準物体オブジェクトと移動物体オブジェクトの形状を説明する斜視図。
【図２】本発明に係る干渉チェック装置の一実施の形態の機能構成を示すブロック図。
【図３】本発明に係る干渉チェック方法の一実施の形態の詳細処理を示すフロー図。
【図４】本発明に係る干渉チェック方法の一実施の形態において使用する最短距離マップ図であり、（ａ）はｘｙ断面図における最短距離マップ、（ｂ）はＡ−Ａ位置における最短距離を示すグラフ。
【図５】ＯＢＢの分割方法及び最短距離評価点の設定方法の一例を示す説明図。
【図６】ＯＢＢＴｒｅｅの一例を示す説明図。
【図７】図４の最短距離マップ図に対して基準物体オブジェクトを追加した際の最短距離マップ図であり、（ａ）はｘｙ断面図における最短距離マップ、（ｂ）はＡ−Ａ位置における最短距離を示すグラフ。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態について、図面を参照して説明する。
【００１９】
［第１の実施の形態］
三角形ポリゴン群によって構成される２つの物体オブジェクト同士の干渉チェック方法について説明する。片方のオブジェクトを環境構造物などの動かない物体とし、もう片方をその構造物の周囲を動作する移動物体とし、前者を基準物体オブジェクト、後者を移動物体オブジェクトと呼ぶものとする。
【００２０】
物体オブジェクトにはポリゴンによって構成される任意の形状のものを用いることができる。
【００２１】
本実施の形態では、図１に示すように、基準物体オブジェクト１０１をz軸方向に高さを持つ円柱形状の物体とし、移動物体オブジェクト１０２をロボットマニピュレータのハンドを想定した形状として説明する。
【００２２】
図２は、本実施の形態に係る干渉チェック装置の機能構成を示すブロック図である。
【００２３】
この干渉チェック装置１０では、仮想空間をメッシュ分割して小さな領域に細分化してメッシュ頂点を定義する空間細分化部１１、該空間細分化部１１において定義されたメッシュの各頂点のデータに基づき、基準対象物である基準物体オブジェクト１０１の表面までの最短距離と方向を算出して各メッシュ頂点に付随する情報として登録することで基準物体オブジェクト１０１までの最短距離マップを作成する最短距離マップ作成部１２、仮想空間上を移動する移動物体オブジェクト１０２上に基準物体オブジェクト１０１までの最短距離を評価するための評価点を設定する最短距離評価点設定部１３、及び最短距離評価点設定部１３で設定された最短距離評価点の座標値に基づき、最短距離マップ作成部１２において作成された最短距離マップを参照することで基準物体オブジェクト１０１までの最短距離を算出して、移動物体オブジェクト１０２と基準物体オブジェクト１０１との干渉の有無や干渉するまでの隙間距離を評価する干渉チェック部１４を備えている。
【００２４】
以下、干渉チェックの詳細処理を図３に基づき説明する。
【００２５】
（空間細分化部１１）
空間細分化部１１では、干渉チェックを行う必要のある空間範囲、つまり移動物体の移動範囲の空間をメッシュ分割することで細分化してメッシュ頂点を定義する（Ｓ２０１１）。
【００２６】
メッシュの形状や大きさは、干渉チェックの要求精度に合わせて決定すれば良く、有限要素法などで利用されるメッシュ分割のように、基準物体オブジェクトの表面周辺領域では細かく生成する。一方で、表面から遠い領域では干渉が発生することは無く厳密な干渉チェックが必要無いため、粗いメッシュを設定しても良い。以降の説明では分かりやすいようにｘｙｚ空間を等間隔の格子状にメッシュ分割したものとして説明を行う。
【００２７】
（最短距離マップ作成部１２）
次に、最短距離マップ作成部１２では、空間細分化ステップ２０１１で作成した各メッシュ頂点（ｉ）（格子状に分割した場合は各格子点）から見た基準物体オブジェクト１０１までの最短距離と最近傍点を算出する（Ｓ２０２１）。
【００２８】
ここで、メッシュ頂点（ｉ）が基準物体オブジェクト１０１の内部の点であれば、最短距離値をマイナスの値として再定義する（Ｓ２０２２）。
【００２９】
次に、メッシュ頂点（ｉ）に、最短距離、最近傍点座標を登録する（Ｓ２０２３）。
【００３０】
メッシュ頂点から物体オブジェクトまでの最短距離は、物体オブジェクトを構成するポリゴン群との距離計算を行うことで求める。各ポリゴンは頂点座標とその頂点が為す面の法線ベクトルの情報を持っているため、メッシュ頂点とポリゴンまでの距離は幾何学的な条件から求めることができ、全ポリゴンまでの距離計算を行い、最小値を求めることで最短距離を決定する。なお、このときポリゴンの位置情報に基づいて計算対象ポリゴンを絞り込んで計算量を削減しても良い。
【００３１】
ここで、メッシュ頂点が基準物体オブジェクト１０１の内部に位置する場合は、上述したように最短距離はマイナスの値として登録する。ポリゴンの面には表と裏の定義があり、物体オブジェクトの外表面がポリゴンの表となるようにした場合、最短距離算出時に対象とするポリゴン面の法線と、最短距離ベクトルとの為す角度が鋭角であれば、メッシュ頂点が基準物体オブジェクト１０１の内部の点であると判断できる。
【００３２】
なお、メッシュ頂点に登録する情報は、最短距離及び最近傍点座標ではなく、最短距離及び方向、又は、メッシュ頂点から最近傍位置を結ぶベクトル情報としても良い。このベクトルを最短距離ベクトルと呼ぶものとする。
【００３３】
本処理を全メッシュ頂点について実施する（Ｓ２０２４）ことで、基準物体オブジェクト１０１までの最短距離の空間分布のマップを作成する。
【００３４】
図４に、最短距離の空間分布のマップの一例を示す。
【００３５】
図４（ａ）のｘｙ断面図において、格子状に示した点がメッシュ頂点４０１、斜線で表した範囲が円柱形状の基準物体オブジェクト１０１のｘｙ平面断面である。基準物体オブジェクト１０１の外形に合わせて同心円状に記載した円は基準物体オブジェクト１０１からの等距離位置４０２を示したものである。あるメッシュ頂点ｐ（ｘ、ｙ）における最短距離ベクトルを４０３として図中に示す。基準物体オブジェクト１０１の内部にあるメッシュ頂点に持たせる最短距離値はマイナスの値とするため、Ａ−Ａ位置においては縦軸を最短距離とすると図４（ｂ）のグラフのようになる。最短距離値は、線４０７で示すように基準物体オブジェクト１０１の内部領域４０６の中心位置で最小値、表面位置でゼロとなり、表面から遠ざかるほど大きな値となる。
【００３６】
（最短距離評価点設定部１３）
次に、最短距離評価点設定部１３では、移動物体オブジェクト１０２の外表面または外側に干渉チェックを行う評価点を定義する。
【００３７】
ここでは、三次元オブジェクトの外形を包括する最小の直方体を定義する公知の手法として知られているＯＢＢ(Oriented Bounding Box)と、移動物体オブジェクトの外形状の近似精度を増やすためにＯＢＢを分割することにより細分化してＯＢＢの木構造を構成するＯＢＢＴｒｅｅを用いる。
【００３８】
図５にＯＢＢの細分化の手法を示す。
【００３９】
先ず、ＯＢＢＴｒｅｅを構成する全てのＯＢＢについて各立体状ＯＢＢの頂点８点を干渉チェックの評価点５０１として設定する（階層１）。次に、最上位階層のＯＢＢ（１）を分割してＯＢＢ（２）と（３）を階層２のＯＢＢとして生成する。更に、ＯＢＢ（２）、（３）をそれぞれ分割して階層３のＯＢＢとしてＯＢＢ（４）と（５）、ＯＢＢ（６）と（７）を生成する。
【００４０】
図６にＯＢＢＴｒｅｅの木構造を示す。なお、図６に記載の番号は図５のＯＢＢの番号に対応している。
【００４１】
上記手法に基づき、図５に示すように、移動物体オブジェクト１０２のＯＢＢ（階層ｎ）を作成し（Ｓ２０３１）、ＯＢＢ（階層ｎ）の頂点を最短距離評価点として定義する（Ｓ２０３２）。
【００４２】
次に、ＯＢＢ（階層ｎ）の頂点間距離が閾値以下かどうかを判定し（Ｓ２０３３）、閾値以下であれば、次ステップに移り、移動物体オブジェクト１０２を移動する（Ｓ２０４０）。閾値以下でなければＯＢＢを細分化し（Ｓ２０３４）、再度、移動物体オブジェクト１０２のＯＢＢ（階層ｎ）を作成する（Ｓ２０３１）。
【００４３】
移動物体オブジェクト１０２を移動すれば、それに合わせて評価点５０１の位置を更新する。なお、評価点の設定はＯＢＢに限定されるものではなく、移動物体オブジェクト１０２のポリゴン頂点を用いても良いし、任意に設定しても良い。
【００４４】
（干渉チェック部１４）
最後に、干渉チェック部１４では、最短距離評価点５０１の座標における最短距離情報について、最短距離マップを参照することで取得する。
【００４５】
最短距離マップは離散的なメッシュ頂点座標にしか登録されていないため、評価点座標の周囲のメッシュ頂点情報を補間することにより求める。メッシュが三次元の格子の場合、評価点座標を取り込む周囲の格子点８点に登録された最短距離情報を元に公知の線形空間補間方法により求めることができる。
【００４６】
このようにして求めた評価点の最短距離がマイナスの値であれば干渉状態、プラスの値であればその距離の隙間距離があることになる。
【００４７】
即ち、図３において、先ず、移動物体オブジェクトを移動させ（Ｓ２０４０）、全ＯＢＢ（全階層）に対応する最短距離評価点を移動させる（Ｓ２０４１）。
【００４８】
次に、ＯＢＢ（階層ｎ）に対応する最短距離評価点について、基準物体オブジェクト１０１との最短距離を評価し（Ｓ２０４２）、ＯＢＢ（階層ｎ）のうち、基準物体オブジェクト１０１との最短距離が最小となるＯＢＢを選定し（Ｓ２０４３）、この選択したＯＢＢが最下層のものかどうかを判定する（Ｓ２０４４）。最下層であれば最終的に評価したＯＢＢの頂点（評価点）において最短距離がマイナスの値かどうかを判定し（Ｓ２０４５）、最下層でなければ、選定したＯＢＢの下層ＯＢＢで詳細評価を行い（Ｓ２０４６）、ステップＳ２０４２へ戻り、再度下層ＯＢＢに対応する最短距離評価点について、基準物体オブジェクト１０１との最短距離を評価する。
【００４９】
ステップＳ２０４４では、１番上の階層のＯＢＢの頂点から評価を行い、８点の頂点（評価点）のうち干渉状態と判断された場合や、最短距離（基準物体との隙間距離）が設定した閾値よりも小さい点があった場合は、その頂点８点の中で最短距離が最も小さい頂点（評価点）を抽出し、その点を含む下層の細分化されたＯＢＢで再評価を行う。同様にして必要な精度に至るまでＯＢＢの細分化と最短距離の評価を繰り返す。
【００５０】
次に、最終的に評価したＯＢＢの頂点（評価点）において最短距離がマイナスの値かどうかを判定し（Ｓ２０４５）、マイナスの値であれば移動物体オブジェクト１０２と基準物体オブジェクト１０１とは干渉状態であると判定する（Ｓ２０４７）。逆に、ＯＢＢの頂点８点が全てプラスの値であれば非干渉状態と判定し（Ｓ２０４８）、図４に示すように、頂点８点のうち最短距離が最も小さな点を最近傍点４０４、その最短距離を両物体オブジェクトの最短距離４０５とする（Ｓ２０４９）。
【００５１】
ポリゴンの大きさよりも小さなＯＢＢは作成できないため、より詳細な干渉チェックを行いたい場合は、ポリゴンを細分化してより小さなＯＢＢを作成したり、評価点５０１をＯＢＢの頂点だけでなくポリゴン上に追加したり、などすればよい。
【００５２】
以上の処理により基準物体オブジェクト１０１と移動物体オブジェクト１０２との干渉チェックを行うことができる。
【００５３】
なお、本実施の形態では、移動物体オブジェクト１０２の形状は変化しないものとしたが、ロボットマニピュレータのように動作に伴い全体の形状が変化する場合は、稼動単位であるリンク構造毎にＯＢＢＴｒｅｅを作成して評価点５０１を定義すれば良い。
【００５４】
（本実施の形態の効果）
本実施の形態による干渉チェックでは、初めに基準物体オブジェクト１０１に対して最短距離マップの作成と移動物体オブジェクト１０２に対してＯＢＢＴｒｅｅによる評価点を作成する必要がある。しかし、一度作成してしまえば、後は移動物体オブジェクト１０２の移動量に合わせた評価点５０１の座標変換と、最短距離マップの参照および参照データの補間処理のみによって最短距離を求めることができるので、計算量が少なく高速に処理を行うことができる。また、最短距離を取得することで干渉チェックを行うため、干渉の有無だけでなく隙間距離も計算負荷を増やすことなく評価することができる。
【００５５】
また、本実施の形態による干渉チェックでは、物体オブジェクト同士の最短距離で干渉状態を判断するため、両オブジェクトの最短距離が設定した閾値よりも小さければ干渉状態と見なすこともできる。これにより、任意の隙間距離を確保することを前提とした干渉チェックを行うことができるため、例えばロボットシミュレータに適用した場合は隙間距離が保証された安全な動作設計に活用することができる。
【００５６】
上述したように本実施の形態による干渉チェックでは、メッシュ頂点４０１と基準物体オブジェクト１０１との最短距離を、基準物体オブジェクト１０１を構成するポリゴンとメッシュ頂点４０１との距離計算により求めており、物体形状に依存しない処理となっている。そのため、基準物体オブジェクト１０１の形状として上述した単純な形状の円柱体のみならず、複雑な形状の物体に対しても同様に適用することができる。
【００５７】
また、ポリゴンで構成された三次元形状オブジェクトは一般的な三次元ＣＡＤで作成することができるので、特別な前処理を必要とせずに適用することができる。
【００５８】
なお、本実施の形態では、基準物体オブジェクト１０１は静止しているものとして説明したが、移動する物体にも適用することができ、その場合は移動量に合わせて最短距離マップの位置と姿勢を更新すれば良い。
【００５９】
［第２の実施の形態］
第１の実施の形態で説明した最短距離マップ作成部１２では、単一の基準物体オブジェクト１０１に対して最短距離マップを作成した。本実施の形態では、始めに作成した最短距離マップに対し、新たに別の基準物体オブジェクトからの最短距離情報を追加する方法について説明する。
【００６０】
先ず、第１の実施の形態で説明した方法と同様に追加する基準物体オブジェクトについても、独立した最短距離マップを作成する。初めに作成した最短距離マップを最短距離マップＡ、追加で作成したものを最短距離マップＢと呼ぶものとする。元の最短距離マップＡと追加で作成した最短距離マップＢについて各メッシュ頂点に登録した最短距離情報を比較し、距離の小さい方を新たな最短距離マップＣのメッシュ頂点の情報として登録する。全メッシュ頂点において前記処理を行うことで、合成した新しい最短距離マップＣを作成する。
【００６１】
図７に、図４の最短距離マップ図に対して基準物体オブジェクト７０１を追加した際の最短距離マップ図を示す。
【００６２】
これにより、例えば、第１の実施の形態で示した円柱形状基準物体オブジェクト１０１がある空間の横に同形状の基準物体オブジェクト７０１を追加する場合、合成した最短距離マップにおいて基準物体オブジェクトからの等距離線４０２は図７（ａ）のようになる。このときの、Ａ−Ａ位置における最短距離の変化は図７（ｂ）の線４０８のようになり、線４０８で示すように基準物体オブジェクト１０１の内部領域４０６及び基準物体オブジェクト７０１の内部領域７０２の中心位置で最小値、表面位置でゼロとなる。また、２つの基準物体オブジェクトに挟まれた空間では、両オブジェクトから等距離になる位置にて最短距離が最も大きくなる。
【００６３】
なお、本実施の形態ではメッシュ頂点４０１は格子状にあるものとしたが、最短距離マップＡとＢのメッシュ形状が異なる場合は頂点位置が一致しなくなる。この場合は、両マップのメッシュ頂点をすべて含むように最短距離マップＣのメッシュ頂点を定義する。これにより必要以上にメッシュ頂点の密度が多くなる場合は、メッシュの切り方の定義に則って頂点数を間引く処理を行えば良い。
【００６４】
このように定義した最短距離マップＣのメッシュ頂点位置座標について、最短距離マップＡとＢの両方の持つ最短距離値を第１の実施の形態で示したように空間補間処理により求め、距離の小さい方を最短距離マップＣに登録してマップを合成する。
【００６５】
この合成した最短距離マップを利用することで、複数の基準物体オブジェクトがある環境においても、第１の実施の形態と同様に移動物体オブジェクトの干渉チェックを行うことができる。また、片方の基準物体オブジェクトが移動した際も、そのオブジェクト固有の最短距離マップを移動させた後に、もう片方の最短距離マップと再び合成することにより、最短距離マップを更新することができる。
【００６６】
なお、本実施の形態では２つの基準物体オブジェクトを例に記述したが、３つ以上になっても同様に処理することができる。
【００６７】
［第３の実施の形態］
第１の実施の形態では、移動物体が移動するごとに干渉チェック部１４の処理により干渉チェックを実施した。
【００６８】
しかし、移動物体オブジェクト１０２が移動する前に評価した最短距離（隙間距離）と、移動物体の移動量を比較し、移動量が隙間距離よりも小さい場合は、基準物体オブジェクトと干渉することは有り得ない。
【００６９】
そこで、上記条件が成立する場合は、干渉チェック部１４の処理を省略する。これにより、基準物体オブジェクトと移動物体オブジェクトの位置が大きく離れている場合や、隙間距離の大きさに対して移動速度が小さいときなどの干渉が発生する恐れが無い場合に、干渉チェックに必要な計算量を削減して処理の高速化を図ることができる。
【符号の説明】
【００７０】
１０…干渉チェック装置、１１…空間細分化部、１２…最短距離マップ作成部、１３…最短距離評価点設定部、１４…干渉チェック部、１０１…基準物体オブジェクト、１０２…移動物体オブジェクト、４０１…メッシュ頂点、４０２…基準物体オブジェクトからの等距離線、４０３…メッシュ頂点ｐから見た最短距離ベクトル、４０４…移動物体オブジェクトの再近傍点、４０５…最短距離ベクトル、４０６…基準物体オブジェクトの内部領域、４０７…基準物体オブジェクトまでの最短距離、４０８…基準物体オブジェクトまでの最短距離、５０１…最短距離評価点、７０１…追加の基準物体オブジェクト、７０２…追加の基準物体オブジェクトの内部領域
【図１】
2011079105.tif 000003
【図２】
2011079105.tif 000004
【図３】
2011079105.tif 000005
【図６】
2011079105.tif 000006
【図７】
2011079105.tif 000007
【図４】
2011079105.tif 000008
【図５】
2011079105.tif 000009