(57)【要約】【課題】衝突検出対象オブジェクトの正確な衝突判定を実現できる衝突検出システム、ロボットシステム、衝突検出方法及びプログラム等の提供。【解決手段】衝突検出システムは処理部と描画部を含む。描画部は、衝突検出対象オブジェクトの所定の視点から見たときの前面を描画する第１の描画処理を行って前面深度値を生成し、衝突検出対象オブジェクトの所定の視点から見たときの背面を描画する第２の描画処理を行って背面深度値を生成する。また衝突検出対象オブジェクト以外の他のオブジェクトを描画する第３の描画処理を行う。処理部は、前面深度値と背面深度値とに基づいて、所定の視点から見たときの衝突検出対象オブジェクトの前面と背面の間に、第３の描画処理により描画された他のオブジェクトが存在すると判定した場合に、衝突検出対象オブジェクトが他のオブジェクトに衝突したと判定する。【選択図】図７
2012243138.tif 000002
【特許請求の範囲】
【請求項１】
処理部と、
描画処理を行う描画部と、
を含み、
前記描画部は、
衝突検出対象オブジェクトの所定の視点から見たときの前面を描画する第１の描画処理を行って、深度情報として前面深度値を生成し、
前記衝突検出対象オブジェクトの前記所定の視点から見たときの背面を描画する第２の描画処理を行って、前記深度情報として背面深度値を生成し、
前記衝突検出対象オブジェクト以外の他のオブジェクトを描画する第３の描画処理を行い、
前記処理部は、
前記前面深度値と前記背面深度値とに基づいて、前記所定の視点から見たときの前記衝突検出対象オブジェクトの前面と背面の間に、前記第３の描画処理により描画された前記他のオブジェクトが存在すると前記処理部が判定した場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定することを特徴とする衝突検出システム。
【請求項２】
請求項１において、
前記処理部は、
前記第３の描画処理で描画された前記他のオブジェクトの処理対象ピクセルの深度値が、前記前面深度値と前記背面深度値の間の深度値であると判定した場合に、前記所定の視点から見たときの前記衝突検出対象オブジェクトの前面と背面の間に、前記他のオブジェクトが存在すると判定して、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定することを特徴とする衝突検出システム。
【請求項３】
請求項２において、
前記描画部により描画データが書き込まれる描画バッファーを含み、
前記描画部は、
前記第３の描画処理において、前記処理対象ピクセルの深度値が、前記前面深度値よりも前記所定の視点から見て後方側の深度値であり、且つ、前記背面深度値よりも前記所定の視点から見て前方側の深度値である場合に、前記処理対象ピクセルの前記描画データを前記描画バッファーに書き込み、
前記処理部は、
前記描画バッファーへの前記描画データの書き込み結果に基づいて、前記衝突検出対象オブジェクトの衝突判定を行うことを特徴とする衝突検出システム。
【請求項４】
請求項２において、
前記描画部により描画データが書き込まれる描画バッファーを含み、
前記描画部は、
前記第３の描画処理において、
前方物体を描画し後方物体を隠面消去する描画モードに設定して、前記背面深度値を参照して前記他のオブジェクトを第１の描画データで前記描画バッファーに描画し、
後方物体を描画し前方物体を隠面消去する描画モードに設定して、前記前面深度値を第２の描画データとして前記描画バッファーに上書きで描画し、
前記処理部は、
前記描画バッファーに前記第１の描画データが上書きされずに残存している場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定することを特徴とする衝突検出システム。
【請求項５】
請求項１乃至４のいずれかにおいて、
深度情報を記憶する深度バッファーを含み、
前記深度バッファーは、前記前面深度値と前記背面深度値を記憶することを特徴とする衝突検出システム。
【請求項６】
請求項１乃至５のいずれかにおいて、
前記処理部は、
前記前面深度値と前記背面深度値とに基づいて、前記所定の視点から見たときの前記衝突検出対象オブジェクトの前面と背面の間に、前記第３の描画処理により描画された前記他のオブジェクトが存在しないと判定した場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突しなかったと判定することを特徴とする衝突検出システム。
【請求項７】
請求項１乃至６のいずれかにおいて、
前記描画部は、
無限遠の前記視点での平行投影で前記第１の描画処理、前記第２の描画処理、前記第３の描画処理を行うことを特徴とする衝突検出システム。
【請求項８】
請求項１乃至７のいずれかにおいて、
第１〜第Ｎの深度値記憶部を有し、
第１〜第Ｎの深度値記憶部のうちの第ｍの深度値記憶部（１≦ｍ≦Ｎ）は、
第ｍの前面深度値を記憶する第ｍの前面深度値記憶部と、
前記第ｍの前面深度値と組となる第ｍの背面深度値を記憶する第ｍの背面深度値記憶部を有し、
前記処理部は、
前記第ｍの前面深度値記憶部の前記第ｍの前面深度値と、前記第ｍの背面深度値記憶部の前記第ｍの背面深度値とに基づいて、前記衝突検出対象オブジェクトの前記第ｍの前面深度値に対応する前面と前記第ｍの背面深度値に対応する背面の間に、前記第３の描画処理で描画された前記他のオブジェクトが存在すると判定した場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定することを特徴とする衝突検出システム。
【請求項９】
請求項８において、
前記所定の視点から見た場合における、前記衝突検出対象オブジェクトについての重なり状態を検出する重なり状態検出部を含み、
前記重なり状態検出部で検出された重なり状態の最大重なり数がＭである場合に、Ｎ≧Ｍであることを特徴とする衝突検出システム。
【請求項１０】
請求項８又は９において、
前記衝突検出対象オブジェクトについての処理対象ピクセルの深度値が、第１〜第Ｎの前面深度値記憶部のうちの第ｉの前面深度値記憶部（１≦ｉ≦Ｎ）の深度値よりも、前記所定の視点から見て前方側の深度値である場合には、第ｉ〜第Ｎ−１の前面深度値記憶部の深度値を第ｉ＋１〜第Ｎの前面深度値記憶部に順次移動し、前記第ｉの前面深度値記憶部の深度値を、前記処理対象ピクセルの深度値に更新する前面処理部と、
前記衝突検出対象オブジェクトについての前記処理対象ピクセルの深度値が、第１〜第Ｎの背面深度値記憶部のうちの第ｉの背面深度値記憶部の深度値よりも、前記所定の視点から見て後方側の深度値である場合には、第２〜第ｉの背面深度値記憶部の深度値を第１〜第ｉ−１の背面深度値記憶部に順次移動し、前記第ｉの背面深度値記憶部の深度値を、前記処理対象ピクセルの深度値に更新する背面処理部を含むことを特徴とする衝突検出システム。
【請求項１１】
請求項８乃至１０のいずれかにおいて、
前記処理部は、
前記第ｍの背面深度値記憶部の前記第ｍの背面深度値よりも、第ｍ＋１の前面深度値記憶部の第ｍ＋１の前面深度値の方が、前記所定の視点から見て前方側の深度値であると判定された場合に、前記衝突検出対象オブジェクトの自己衝突が発生したと判定することを特徴とする衝突検出システム。
【請求項１２】
請求項１乃至１１のいずれかにおいて、
前記衝突検出対象オブジェクトは、ロボットをモデル化したオブジェクトであることを特徴とする衝突検出システム。
【請求項１３】
請求項１乃至１２のいずれかに記載の衝突検出システムを含むことを特徴とするロボットシステム。
【請求項１４】
衝突検出対象オブジェクトの所定の視点から見たときの前面を描画する第１の描画処理を行って、深度情報として前面深度値を生成し、
前記衝突検出対象オブジェクトの前記所定の視点から見たときの背面を描画する第２の描画処理を行って、前記深度情報として背面深度値を生成し、
前記衝突検出対象オブジェクト以外の他のオブジェクトを描画する第３の描画処理を行い、
前記前面深度値と前記背面深度値とに基づいて、前記所定の視点から見たときの前記衝突検出対象オブジェクトの前面と背面の間に、前記第３の描画処理により描画された前記他のオブジェクトが存在すると判定した場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定することを特徴とする衝突検出方法。
【請求項１５】
処理部と、
描画処理を行う描画部として、
コンピューターを機能させ、
前記描画部は、
衝突検出対象オブジェクトの所定の視点から見たときの前面を描画する第１の描画処理を行って、深度情報として前面深度値を生成し、
前記衝突検出対象オブジェクトの前記所定の視点から見たときの背面を描画する第２の描画処理を行って、前記深度情報として背面深度値を生成し、
前記衝突検出対象オブジェクト以外の他のオブジェクトを描画する第３の描画処理を行い、
前記処理部は、
前記前面深度値と前記背面深度値とに基づいて、前記所定の視点から見たときの前記衝突検出対象オブジェクトの前面と背面の間に、前記第３の描画処理により描画された前記他のオブジェクトが存在すると前記処理部が判定した場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、衝突検出システム、ロボットシステム、衝突検出方法及びプログラム等に関する。
【背景技術】
【０００２】
物体間の衝突や近接の有無を判定することは多くの分野で必要とされている。例えばロボットなどの分野において、衝突の発生は非常に大きな問題となる。このため、従来より、実際に衝突が発生する以前に、衝突の有無や、許容された以上の近接を、コンピューターによる計算により判定する手法が研究、開発されている。このような衝突判定手法の従来技術としては、例えば特許文献１、２等に開示される技術が知られている。
【０００３】
特許文献１の手法は、その図６のフローチャートに示されている。この従来技術では、物体（オブジェクト）の３次元の配置を、横（Ｘ）と縦（Ｙ）の２次元位置と、その位置に対応する深度値（Ｚ値）として記憶する装置において、プリミティブを逐次的にレンダリングする。そして、そのレンダリングの過程で同一深度値を持つもの、つまり３次元空間的に同じ位置を占めるものが現れれば、それを衝突と判定する。
【０００４】
特許文献２の手法は、その図２、図３により説明されている。この従来技術では、ポリゴンの原点から、そのポリゴンのある方向の面までの距離を予め計算し、キューブマップとして保存する。そして、原点から衝突検出の対象となる物体との距離と、キューブマップに記憶された距離との大小により、衝突を判定する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平９−２０４５４３号公報
【特許文献２】特表２００９−５４５０７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら特許文献１の従来技術では、深度値の更新が、物体を描画する順番に依存するため、衝突の検出漏れが発生する可能性がある。例えば、前方側（手前側）に配置された物体を描画した後で、その後方側（奥側）において別の物体間で衝突が起こったとしても、深度値は既に前方側のオブジェクトの値に更新されているために、それを検出することはできないことになる。
【０００７】
また特許文献２の従来技術では、非凸であるポリゴンの衝突を正確に取り扱うのが困難であるという問題がある。即ち、原点から面までの距離を単一のキューブマップに記憶しているため、ある方向において、そのポリゴンの面が複数ある場合、つまりそのような非凸のポリゴンの場合においては、それを単一のキューブマップとしては表現できないことになる。
【０００８】
本発明の幾つかの態様によれば、衝突検出対象オブジェクトの正確な衝突判定を実現できる衝突検出システム、ロボットシステム、衝突検出方法及びプログラム等を提供できる。
【課題を解決するための手段】
【０００９】
本発明の一態様は、処理部と、描画処理を行う描画部とを含み、前記描画部は、衝突検出対象オブジェクトの所定の視点から見たときの前面を描画する第１の描画処理を行って、深度情報として前面深度値を生成し、前記衝突検出対象オブジェクトの前記所定の視点から見たときの背面を描画する第２の描画処理を行って、前記深度情報として背面深度値を生成し、前記衝突検出対象オブジェクト以外の他のオブジェクトを描画する第３の描画処理を行い、前記処理部は、前記前面深度値と前記背面深度値とに基づいて、前記所定の視点から見たときの前記衝突検出対象オブジェクトの前面と背面の間に、前記第３の描画処理により描画された前記他のオブジェクトが存在すると前記処理部が判定した場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定する衝突検出システムに関係する。
【００１０】
本発明の一態様によれば、衝突検出対象オブジェクトの前面を描画する第１の描画処理が行われて、前面深度値が生成され、衝突検出対象オブジェクトの背面を描画する第２の描画処理が行われて、背面深度値が生成される。また衝突検出対象オブジェクト以外の他のオブジェクトを描画する第３の描画処理が行われる。そして、生成された前面深度値と背面深度値とに基づいて、衝突検出対象オブジェクトの前面と背面の間に他のオブジェクトが存在すると判断されると、衝突検出対象オブジェクトが他のオブジェクトに衝突したと判定される。このようにすれば、衝突検出対象オブジェクトの前面、背面を描画することで生成された前面深度値、背面深度値を利用して、衝突検出対象オブジェクトの衝突判定が行われるようになり、衝突検出対象オブジェクトの正確な衝突判定を実現できるようになる。
【００１１】
また本発明の一態様では、前記処理部は、前記第３の描画処理で描画された前記他のオブジェクトの処理対象ピクセルの深度値が、前記前面深度値と前記背面深度値の間の深度値であると判定した場合に、前記所定の視点から見たときの前記衝突検出対象オブジェクトの前面と背面の間に、前記他のオブジェクトが存在すると判定して、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定してもよい。
【００１２】
このようにすれば、他のオブジェクトの処理対象ピクセルの深度値が、前面深度値と背面深度値の間の深度値であるか否かを判定することで、衝突検出対象オブジェクトと他のオブジェクトの衝突判定を行うことが可能になる。従って、深度値の判定処理を有効利用した衝突判定を実現できるようになる。
【００１３】
また本発明の一態様では、前記描画部により描画データが書き込まれる描画バッファーを含み、前記描画部は、前記第３の描画処理において、前記処理対象ピクセルの深度値が、前記前面深度値よりも前記所定の視点から見て後方側の深度値であり、且つ、前記背面深度値よりも前記所定の視点から見て前方側の深度値である場合に、前記処理対象ピクセルの前記描画データを前記描画バッファーに書き込み、前記処理部は、前記描画バッファーへの前記描画データの書き込み結果に基づいて、前記衝突検出対象オブジェクトの衝突判定を行ってもよい。
【００１４】
このようにすれば、処理対象ピクセルの深度値が前面深度値よりも後方側であり且つ背面深度値よりも前方側の深度値である場合に書き込まれる描画データの書き込み結果に基づいて、衝突検出対象オブジェクトの衝突判定を行うことが可能になる。従って、深度値の判定処理により描画された描画データを有効利用した衝突判定を実現できるようになる。
【００１５】
また本発明の一態様では、前記描画部により描画データが書き込まれる描画バッファーを含み、前記描画部は、前記第３の描画処理において、前方物体を描画し後方物体を隠面消去する描画モードに設定して、前記背面深度値を参照して前記他のオブジェクトを第１の描画データで前記描画バッファーに描画し、後方物体を描画し前方物体を隠面消去する描画モードに設定して、前記前面深度値を第２の描画データとして前記描画バッファーに上書きで描画し、前記処理部は、前記描画バッファーに前記第１の描画データが上書きされずに残存している場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定してもよい。
【００１６】
このようにすれば、前方物体描画モードで描画された第１の描画データが、描画バッファーに上書きされずに残存しているか否かを判定して、衝突検出対象オブジェクトの衝突判定を行うことが可能になる。従って、描画バッファーに第１、第２の描画データを描画するという簡素な描画処理で、衝突判定を実現できるようになる。
【００１７】
また本発明の一態様では、深度情報を記憶する深度バッファーを含み、前記深度バッファーは、前記前面深度値と前記背面深度値を記憶してもよい。
【００１８】
このようにすれば深度バッファーを有効利用した衝突判定を実現できるようになる。
【００１９】
また本発明の一態様では、前記処理部は、前記前面深度値と前記背面深度値とに基づいて、前記所定の視点から見たときの前記衝突検出対象オブジェクトの前面と背面の間に、前記第３の描画処理により描画された前記他のオブジェクトが存在しないと判定した場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突しなかったと判定してもよい。
【００２０】
このようにすれば、前面深度値と背面深度値とにより、衝突検出対象オブジェクトの前面と背面の間に他のオブジェクトが存在しないと判定される場合に、衝突検出対象オブジェクトと他のオブジェクトの衝突が発生していないと判定できるようになる。
【００２１】
また本発明の一態様では、前記描画部は、無限遠の前記視点での平行投影で前記第１の描画処理、前記第２の描画処理、前記第３の描画処理を行ってもよい。
【００２２】
このように、一般的な三次元画像の描画処理とは異なり、平行投影で描画処理を行うことで、より正確な衝突判定を実現できるようになる。
【００２３】
また本発明の一態様では、第１〜第Ｎの深度値記憶部を有し、第１〜第Ｎの深度値記憶部のうちの第ｍの深度値記憶部（１≦ｍ≦Ｎ）は、第ｍの前面深度値を記憶する第ｍの前面深度値記憶部と、前記第ｍの前面深度値と組となる第ｍの背面深度値を記憶する第ｍの背面深度値記憶部を有し、前記処理部は、前記第ｍの前面深度値記憶部の前記第ｍの前面深度値と、前記第ｍの背面深度値記憶部の前記第ｍの背面深度値とに基づいて、前記衝突検出対象オブジェクトの前記第ｍの前面深度値に対応する前面と前記第ｍの背面深度値に対応する背面の間に、前記第３の描画処理で描画された前記他のオブジェクトが存在すると判定した場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定してもよい。
【００２４】
このようにすれば、衝突検出対象オブジェクトの第ｍの前面深度値に対応する前面と第ｍの背面深度値に対応する背面の間に、他のオブジェクトが存在するか否かを判定して、衝突検出対象オブジェクトの衝突判定を行うことが可能になる。従って、例えば所定の視点から見て衝突検出対象オブジェクトに重なりが存在する場合にも、正確な衝突判定を実現できるようになる。
【００２５】
また本発明の一態様では、前記所定の視点から見た場合における、前記衝突検出対象オブジェクトについての重なり状態を検出する重なり状態検出部を含み、前記重なり状態検出部で検出された重なり状態の最大重なり数がＭである場合に、Ｎ≧Ｍであってもよい。
【００２６】
このようにすれば、所定の視点から見て、衝突検出対象オブジェクトに最大でＭ重の重なり状態が存在する場合にも、正確な衝突判定を実現できるようになる。
【００２７】
また本発明の一態様では、前記衝突検出対象オブジェクトについての処理対象ピクセルの深度値が、第１〜第Ｎの前面深度値記憶部のうちの第ｉの前面深度値記憶部（１≦ｉ≦Ｎ）の深度値よりも、前記所定の視点から見て前方側の深度値である場合には、第ｉ〜第Ｎ−１の前面深度値記憶部の深度値を第ｉ＋１〜第Ｎの前面深度値記憶部に順次移動し、前記第ｉの前面深度値記憶部の深度値を、前記処理対象ピクセルの深度値に更新する前面処理部と、前記衝突検出対象オブジェクトについての前記処理対象ピクセルの深度値が、第１〜第Ｎの背面深度値記憶部のうちの第ｉの背面深度値記憶部の深度値よりも、前記所定の視点から見て後方側の深度値である場合には、第２〜第ｉの背面深度値記憶部の深度値を第１〜第ｉ−１の背面深度値記憶部に順次移動し、前記第ｉの背面深度値記憶部の深度値を、前記処理対象ピクセルの深度値に更新する背面処理部を含んでもよい。
【００２８】
このようにすれば、前面処理を行うことで、第１〜第Ｎの前面深度値記憶部に第１〜第Ｎの前面深度値を適正に設定し、背面処理を行うことで、第１〜第Ｎの背面深度値記憶部に第１〜第Ｎの背面深度値を適正に設定することが可能になる。
【００２９】
また本発明の一態様では、前記処理部は、前記第ｍの背面深度値記憶部の前記第ｍの背面深度値よりも、第ｍ＋１の前面深度値記憶部の第ｍ＋１の前面深度値の方が、前記所定の視点から見て前方側の深度値であると判定された場合に、前記衝突検出対象オブジェクトの自己衝突が発生したと判定してもよい。
【００３０】
このようにすれば、衝突検出対象オブジェクトの自己衝突についても適正に判定して検出できるようになる。
【００３１】
また本発明の一態様では、前記衝突検出対象オブジェクトは、ロボットをモデル化したオブジェクトであってもよい。
【００３２】
また本発明の他の態様は、上記のいずれかに記載の衝突検出システムを含むロボットシステムに関係する。
【００３３】
本発明の他の態様は、衝突検出対象オブジェクトの所定の視点から見たときの前面を描画する第１の描画処理を行って、深度情報として前面深度値を生成し、前記衝突検出対象オブジェクトの前記所定の視点から見たときの背面を描画する第２の描画処理を行って、前記深度情報として背面深度値を生成し、前記衝突検出対象オブジェクト以外の他のオブジェクトを描画する第３の描画処理を行い、前記前面深度値と前記背面深度値とに基づいて、前記所定の視点から見たときの前記衝突検出対象オブジェクトの前面と背面の間に、前記第３の描画処理により描画された前記他のオブジェクトが存在すると判定した場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定する衝突検出方法に関係する。
【００３４】
本発明の他の態様は、処理部と、描画処理を行う描画部として、コンピューターを機能させ、前記描画部は、衝突検出対象オブジェクトの所定の視点から見たときの前面を描画する第１の描画処理を行って、深度情報として前面深度値を生成し、前記衝突検出対象オブジェクトの前記所定の視点から見たときの背面を描画する第２の描画処理を行って、前記深度情報として背面深度値を生成し、前記衝突検出対象オブジェクト以外の他のオブジェクトを描画する第３の描画処理を行い、前記処理部は、前記前面深度値と前記背面深度値とに基づいて、前記所定の視点から見たときの前記衝突検出対象オブジェクトの前面と背面の間に、前記第３の描画処理により描画された前記他のオブジェクトが存在すると前記処理部が判定した場合に、前記衝突検出対象オブジェクトが前記他のオブジェクトに衝突したと判定するプログラムに関係する。
【図面の簡単な説明】
【００３５】
【図１】図１（Ａ）〜図１（Ｃ）は深度バッファー処理の説明図。
【図２】図２（Ａ）〜図２（Ｄ）も深度バッファー処理の説明図。
【図３】図３（Ａ）〜図３（Ｃ）は従来技術の問題点についての説明図。
【図４】本実施形態の衝突検出システムの構成例。
【図５】本実施形態の衝突検出システムを含むロボットシステムの例。
【図６】図６（Ａ）、図６（Ｂ）は本実施形態の第１の衝突検出手法の説明図。
【図７】図７（Ａ）、図７（Ｂ）も本実施形態の第１の衝突検出手法の説明図。
【図８】本実施形態の第１の衝突検出手法の詳細な処理を示すフローチャート。
【図９】図９（Ａ）、図９（Ｂ）は図８の詳細な処理の説明図。
【図１０】本実施形態の第２の衝突検出手法を実現する衝突検出システムの構成例。
【図１１】図１１（Ａ）、図１１（Ｂ）は本実施形態の第２の衝突検出手法の説明図。
【図１２】図１２（Ａ）、図１２（Ｂ）も本実施形態の第２の衝突検出手法の説明図。
【図１３】本実施形態の第２の衝突検出手法の説明図。
【図１４】本実施形態の第２の衝突検出手法の詳細な処理を示すフローチャート。
【図１５】本実施形態の第２の衝突検出手法の詳細な処理を示すフローチャート。
【図１６】本実施形態の第２の衝突検出手法の詳細な処理を示すフローチャート。
【図１７】本実施形態の第２の衝突検出手法の詳細な処理を示すフローチャート。
【図１８】本実施形態の第２の衝突検出手法の詳細な処理を示すフローチャート。
【図１９】本実施形態の第２の衝突検出手法の詳細な処理を示すフローチャート。
【図２０】図２０（Ａ）〜図２０（Ｄ）は図１５、図１６の詳細な処理の説明図。
【発明を実施するための形態】
【００３６】
以下、本発明の好適な実施の形態について詳細に説明する。なお以下に説明する本実施形態は特許請求の範囲に記載された本発明の内容を不当に限定するものではなく、本実施形態で説明される構成の全てが本発明の解決手段として必須であるとは限らない。
【００３７】
１．深度バッファー処理
ロボット（マニピュレーター）の動作においては、周辺構造物や周辺機器への衝突や、自己衝突や、他のロボットへの衝突は非常に大きな問題となる。本実施形態の衝突検出手法では、このような衝突をシミュレーションにより事前に検出する。
【００３８】
このような本実施形態の衝突検出手法が用いられる形態としては、大別して、オフラインでの使用（事前確認）と、ラインタイムでの使用（予測、先読み）が考えられる。オフラインの使用では、周辺環境などが既知且つ静的であり、ロボットの動作が既知である場合に、システムの作成時に、その衝突を検証する。一方、ラインタイムの使用では、周辺環境などが動的に変化する場合（例えば周囲に複数のロボットが存在したり、作業者が存在する場合）に、ロボットの実際の動作に先行して、シミュレーションにより衝突を検出する。
【００３９】
従来では、このようなロボットにおける衝突検出手法として、ＣＰＵ（Central Processing Unit)の処理に適したアルゴリズムを使用する場合が殆どであった。ここでＣＰＵ処理に適したアルゴリズムとは、比較的に複雑な単位処理を、比較的に少数（数十から数百程度）の並列度で処理するようなアルゴリズムである。
【００４０】
しかしながら、近年では、消費電力の問題等に起因して、ＣＰＵの動作周波数の伸びは止まっている。このため、最近のＣＰＵの性能向上は、マルチコア化などの処理の並列度の向上によって実現されている。別の言い方をすれば、並列度を上げることができないアルゴリズムでは、処理性能を向上できなくなっている。
【００４１】
一方、ＧＰＵ（Graphics Processing Unit）は、ＣＰＵに比べて非常に大きな並列度を有する。例えば現在のＧＰＵは、ＡＬＵ（算術演算ユニット）を数百から千数百持ち、数万から数百万の処理を並列に実行できる能力を有する。
【００４２】
そこで本実施形態では、衝突検出のアルゴリズムとして、ＣＰＵ処理よりはＧＰＵ処理に適したアルゴリズムを採用することで、従来に比べて高性能な衝突検出を実現する。具体的には、ＧＰＵが有するハードウェアー機能であるＲＯＰ（レンダリング・アウトプット・パイプライン）の機能を最大限に利用する。即ち、このようなＲＯＰ機能を用い、深度テスト機能と深度バッファーを有効活用して衝突検出を実現する。
【００４３】
ここで深度バッファーは、ＣＧ（Computer Graphics）においては主に隠面消去のために用いられ、オブジェクトの深度情報を記憶するものである。具体的にはピクセル単位で深度値（Ｚ値）を記憶する。なお深度値とは、奥行き方向での深さを表す値であり例えばＺバッファー法におけるＺ値である。また、深度情報とは、ピクセル毎の深度値に係る情報である。以下、深度バッファーを用いた深度バッファー処理（Ｚバッファー処理）について説明する。
【００４４】
深度バッファー処理では、ある点を描画する際に、その点の深度値と、深度バッファーに記憶されている深度値を比較する。そして、その点の深度値が大きければ（右手系の場合）、その点のカラー値でカラーバッファーの値を上書きすると共に、その点の深度値で深度バッファーの値を更新する。
【００４５】
例えばオブジェクトＯＢＡ、ＯＢＢ、ＯＢＣが図１（Ａ）、図１（Ｂ）に示すように配置されていたとする。図１（Ａ）はオブジェクトＯＢＡ、ＯＢＢ、ＯＢＣを上方の視点から見た場合の図であり、図１（Ｂ）は前方斜め上の視点から見た場合の図である。ここでオブジェクトは、現実世界の物体をモデル化したものであり、例えば複数のプリミティブ面により構成される。プリミティブ面は、オブジェクトの構成要素であるプリミティブとなる面であり、例えばポリゴン、自由曲面、或いはサブディビジョンサーフェスなどである。
【００４６】
図１（Ｃ）に示すように、深度バッファーを用いた描画処理では、各ピクセルのカラー値（ＲＧＢの色情報）が描画バッファー（カラーバッファー）に書き込まれ、深度値（Ｚ値）が深度バッファー（Ｚバッファー）に書き込まれる。
【００４７】
具体的には図２（Ａ）では深度バッファーの深度値が初期値である最背面値に設定される。そして図２（Ｂ）ではオブジェクトＯＢＡが描画されている。この場合に図２（Ｂ）のＪ１に示す領域でのオブジェクトＯＢＡの各ピクセルの深度値は、図２（Ａ）での深度バッファーの深度値よりも前方側（手前側）の深度値となっている。従って、Ｊ１に示す領域では、オブジェクトＯＢＡのカラー値が描画バッファーに書き込まれると共に、オブジェクトＯＢＡの深度値が深度バッファーに書き込まれて深度値が更新される。
【００４８】
なお、最背面値は、深度値の最も後方側（奥側）の値である。また最前面値は、深度値の最も前方側（手前側）の値である。
【００４９】
図２（Ｃ）ではオブジェクトＯＢＢが描画されている。この場合に図２（Ｃ）のＪ２に示す領域でのオブジェクトＯＢＢの各ピクセルの深度値は、深度バッファーの深度値よりも後方側（奥側）の深度値となっている。従って、Ｊ２に示す領域では、オブジェクトＯＢＢは隠面消去されたと判断され、オブジェクトＯＢＢのカラー値は描画バッファーには書き込まれず、図２（Ｄ）のＪ３に示すように深度バッファーの深度値も更新されない。
【００５０】
一方、Ｊ４に示す領域でのオブジェクトＯＢＢの各ピクセルの深度値は、深度バッファーの深度値よりも前方側の深度値となっている。従って、Ｊ４に示す領域では、オブジェクトＯＢＢのカラー値が描画バッファーに書き込まれると共に、図２（Ｄ）のＪ５に示すようにオブジェクトＯＢＢの深度値が深度バッファーに書き込まれて深度値が更新される。そして、図２（Ｄ）でオブジェクトＯＢＣが描画されると、上記と同様の手法により、Ｊ６の領域ではカラー値の書き込みや深度値の更新が行われず、Ｊ７の領域ではカラー値の書き込みと深度値の更新が行われる。
【００５１】
以上のような深度バッファー処理を行うことで、描画の順番に依存せずに、奥行き方向での順番が正しく判定され、図１（Ｃ）に示すように適切な隠面消去が行われた画像が生成されるようになる。
【００５２】
さて、前述した特許文献１の従来技術においても、深度バッファーを利用して衝突判定を行っている。例えば、他のオブジェクトの描画により、深度バッファーの深度値が図３（Ａ）に示すようになっていたとする。この場合に図３（Ｂ）のＨ１に示すように、オブジェクトＯＢＡ１では、その深度値がＺバッファーの深度値とは異なるため、ＯＢＡ１は他のオブジェクトと衝突していないと判定される。一方、Ｈ２、Ｈ３に示すように、オブジェクトＯＢＡ２では、その深度値が深度バッファーの深度値と同一になっている。従って、オブジェクトＯＢＡ２は、この深度バッファーの深度値を持った他のオブジェクトと衝突していると判定される。
【００５３】
しかしながら、この特許文献１の従来技術では図３（Ｃ）に示すような問題点がある。図３（Ｃ）では、他のオブジェクトＯＢＤの描画により深度バッファーの深度値がＨ４に示すようになっている。この場合に、Ｈ５に示すようにオブジェクトＯＢＡ３はオブジェクトＯＢＤと衝突しているのにも関わらず、オブジェクトＯＢＡ３の深度値は深度バッファーの深度値と一致していないため、衝突していないと判定されてしまう。またＨ６に示すように深度値が内挿された場合には、オブジェクトＯＢＡ４はオブジェクトＯＢＤと衝突していないのに、衝突していると判定されてしまう。
【００５４】
また、他の手法として、仮想的な視点を、地面等を表す平面状のオブジェクトの背面に設定し、背面から見て、表面にあるはずのオブジェクトが描画されれば、そのオブジェクトが平面と衝突していると判定する手法も考えられる。しかしながら、この手法では、単純な平面が仮定されているが、それが平面ではなく複雑な構造を持つオブジェクト（例えば非凸）である場合には、片方の面との衝突が、別の面によって遮蔽される可能性があり、このような場合には衝突を検出できなくなる。
【００５５】
２．構成
以上のような問題を解決できる本実施形態の衝突検出システムの構成例を図４に示す。なお本実施形態の衝突検出システムの構成は図４の構成には限定されず、その一部の構成要素（例えば操作部、外部Ｉ／Ｆ部等）を省略したり、他の構成要素を追加するなどの種々の変形実施が可能である。
【００５６】
この衝突検出システムは、処理部１０と、描画処理を行う描画部３０と、記憶部５０（深度バッファー）を含む。また操作部７０、外部Ｉ／Ｆ（インターフェース）部８０、情報記憶媒体９０を含むことができる。
【００５７】
処理部１０は、各種の判定処理や制御処理などを行うものであり、例えばＣＰＵ等の各種のプロセッサー、専用回路（ＡＳＩＣ）などのハードウェアーや、プロセッサー上で実行されるプログラムなどにより実現できる。処理部１０は、オブジェクト空間設定部１２、衝突判定部１４を含む。
【００５８】
オブジェクト空間設定部１２は、複数のオブジェクトをオブジェクト空間に配置設定する処理等を行う。具体的には、ワールド座標系でのオブジェクトの位置や回転角度を決定し、その位置にその回転角度でオブジェクトを配置する。ここでオブジェクトは、ロボット等の衝突検出対象物や、周辺構造物や周辺機器などの被衝突検出対象物を、モデル化したものであり、ポリゴンや自由曲面などのプリミティブ面で構成される。
【００５９】
衝突判定部１４は、衝突検出対象オブジェクトと他のオブジェクト（被衝突検出対象オブジェクト）との間の衝突判定処理を行うものである。
【００６０】
描画部３０は、描画処理を行うものであり、例えばＧＰＵ等の各種のプロセッサー、専用回路（ＡＳＩＣ）などのハードウェアーや、プロセッサー上で実行されるプログラムなどにより実現できる。この描画部３０での描画処理は、頂点シェーダープログラムにより実現される頂点シェーダーや、ピクセルシェーダープログラムにより実現されるピクセルシェーダーにより実現してもよい。頂点シェーダーでは、頂点の移動処理、座標変換処理、クリッピング処理などが行われる。そして頂点処理後の頂点データに基づいてラスタライズ処理が行われる。またピクセルシェーダーでは、ラスタライズ処理後に、画像を構成するピクセル（フラグメント）単位での処理であるピクセル処理（フラグメント処理）が行われる。即ち、シェーディング言語によって記述されたシェーダープログラムによって、プログラマブルシェーダー処理が実現される。
【００６１】
記憶部５０は、処理部１０や描画部３０などのワーク領域となるもので、ＲＡＭ（ＳＲＡＭ、ＤＲＡＭ等）などのメモリーにより実現できる。この記憶部５０は、オブジェクトデータ記憶部５２、描画バッファー５４、深度バッファー５６を含む。深度バッファー５６は前面深度値記憶部６２、背面深度値記憶部６４を有する。
【００６２】
オブジェクトデータ記憶部５２は、オブジェクトの位置データや回転角度データや形状データなどのオブジェクトデータを記憶する。描画バッファー５４（カラーバッファー、フレームバッファー）は画像情報（描画データ）を記憶するものであり、具体的には、ピクセル単位でカラー値やα値などの画像情報を記憶する。深度バッファー５６（Ｚバッファー）は、深度情報を記憶するものであり、具体的にはピクセル単位で深度値（Ｚ値）を記憶する。これらの描画バッファー５４、深度バッファー５６は、記憶部５０を構成するメモリー上に記憶領域として確保される。
【００６３】
操作部７０は、使用者が各種の操作情報を入力するためのものである。外部Ｉ／Ｆ部８０は、外部との間で有線や無線で情報の通信処理等を行うものである。情報記憶媒体９０は（コンピューターにより読み取り可能な媒体）は、プログラムやデータなどを格納するものであり、その機能は、光ディスク、ＨＤＤ、或いはメモリーなどにより実現できる。処理部１０は、情報記憶媒体９０に格納されるプログラム（データ）に基づいて本実施形態の種々の処理を行う。即ち情報記憶媒体９０には、本実施形態の各部としてコンピューター（操作部、処理部、記憶部、出力部を備える装置）を機能させるためのプログラム（各部の処理をコンピューターに実行させるためのプログラム）が記憶される。
【００６４】
そして本実施形態の衝突検出システムでは、描画部３０は、衝突検出対象オブジェクトの前面を描画する第１の描画処理を行って、深度バッファー５６に記憶される深度情報として前面深度値を生成する。例えば深度バッファー５６の深度値を初期化した後に、後述する図６（Ｂ）のＡ１、Ａ２、Ａ３に示すように、全ての衝突検出対象オブジェクトの前面を描画することで、深度バッファー５６に、衝突検出対象オブジェクトの前面深度値ＤＰＦのプレーン（前面深度分布）を生成する。
【００６５】
また描画部３０は、衝突検出対象オブジェクトの背面を描画する第２の描画処理を行って、深度バッファー５６に記憶される深度情報として背面深度値を生成する。例えば深度バッファー５６の深度値を最前面値で初期化した後に、後述する図７（Ａ）のＢ１、Ｂ２、Ｂ３に示すように、全ての衝突検出対象オブジェクトの背面を描画することで、深度バッファー５６に、衝突検出対象オブジェクトの背面深度値ＤＰＢのプレーン（背面深度分布）を生成する。
【００６６】
なお、衝突検出対象オブジェクトの前面は、所定の視点（描画処理での視点）で見たときの前面であり、衝突検出対象オブジェクトの背面は、所定の視点（描画処理での視点）で見たときの背面である。また第１の描画処理で生成される前面深度値は、例えば、衝突検出対象オブジェクトの描画領域では、衝突検出対象オブジェクトの前面の深度値が設定され、それ以外の領域では初期値が設定される深度値のプレーンである。また第２の描画処理で生成される背面深度値は、例えば、衝突検出対象オブジェクトの描画領域では、衝突検出対象オブジェクトの背面の深度値が設定され、それ以外の領域では初期値が設定される深度値のプレーンである。これらの前面深度値（第１の深度値）、背面深度値（第２の深度値）は、各々、深度バッファー５６の前面深度値記憶部６２、背面深度値記憶部６４に記憶される。
【００６７】
また描画部３０は、衝突検出対象オブジェクト以外の他のオブジェクト（被衝突検出対象オブジェクト）を描画する第３の描画処理を行う。例えば他のオブジェクトを所与の描画データで描画する。なお描画部３０は、無限遠の視点（広義には所定の視点）での平行投影で、これらの第１、第２、第３の描画処理を行う
そして処理部１０は、生成された前面深度値と背面深度値とに基づいて、所定の視点（描画処理での視点）から見たときの衝突検出対象オブジェクトの前面と背面の間に、第３の描画処理により描画された他のオブジェクトが存在すると判定した場合に、衝突検出対象オブジェクトが他のオブジェクトに衝突したと判定する。例えば処理部１０は、上述の第３の描画処理で描画された他のオブジェクトの処理対象ピクセルの深度値が、前面深度値と背面深度値の間の深度値であると判定した場合に、所定の視点から見たときの衝突検出対象オブジェクトの前面と背面の間に、他のオブジェクトが存在すると判定する。そして、衝突検出対象オブジェクトが他のオブジェクトに衝突したと判定する。この衝突判定は処理部１０の衝突判定部１４が行う。
【００６８】
例えば後述する図７（Ｂ）のＣ１では、衝突検出対象オブジェクトＰＢ１の前面と背面の間には、他のオブジェクトが存在しないと判定される。具体的には、他のオブジェクトの処理対象ピクセルの深度値が、前面深度値ＤＰＦと背面深度値ＤＰＢの間の深度値ではないと判定される。この場合には衝突検出対象オブジェクトＰＢ１は他のオブジェクトと衝突していないと判定される。
【００６９】
一方、図７（Ｂ）のＣ２では、衝突検出対象オブジェクトＰＢ２の前面と背面の間に、他のオブジェクトＯＢ３（他のオブジェクトの面）が存在していると判定される。具体的には、他のオブジェクトの処理対象ピクセルの深度値が、前面深度値ＤＰＦと背面深度値ＤＰＢの間の深度値であると判定される。この場合には、衝突検出対象オブジェクトＰＢ２は他のオブジェクトＯＢ３と衝突していると判定される。また図７（Ｂ）のＣ３においても、衝突検出対象オブジェクトＰＢ３の前面と背面の間に、他のオブジェクトＯＢ３が存在していると判定される。従って、衝突検出対象オブジェクトＰＢ３は他のオブジェクトＯＢ３と衝突していると判定される。
【００７０】
更に具体的には本実施形態の衝突検出システムは、描画部３０により描画データが書き込まれる描画バッファー５４を含む。そして描画部３０は、上述の他のオブジェクトを描画する第３の描画処理において、処理対象ピクセルの深度値が、前面深度値よりも所定の視点から見て後方側（奥側）の深度値であり、且つ、背面深度値よりも所定の視点から見て前方側（手前側）の深度値である場合に、処理対象ピクセルの描画データ（例えば所定色を表すデータ）を描画バッファー５４に書き込む。
【００７１】
そして処理部１０は、描画バッファー５４への描画データの書き込み結果に基づいて、衝突検出対象オブジェクトの衝突判定を行う。例えば他のオブジェクトの描画データが書き込まれていた場合に、衝突検出対象オブジェクトが他のオブジェクトと衝突したと判定する。例えば図７（Ｂ）のＣ１では他のオブジェクトの描画データは書き込まれないため、衝突検出対象オブジェクトは他のオブジェクトと衝突していないと判定される。一方、図７（Ｂ）のＣ２、Ｃ３では他のオブジェクトの描画データが書き込まれているため、衝突検出対象オブジェクトが他のオブジェクトと衝突していると判定される。
【００７２】
或いは描画部３０は、他のオブジェクトを描画する第３の描画処理において、前方物体を描画し後方物体を隠面消去する描画モードに設定する。そして背面深度値を参照して、他のオブジェクトを第１の描画データ（例えば所定色のデータ）で描画バッファー５４に描画する。例えば背面深度値を参照して、深度テストを行って（深度テストを有効にして）、他のオブジェクトを描画バッファー５４に描画する。例えば後述する図８のステップＳ１０、Ｓ１１に示すような描画処理を行う。
【００７３】
また描画部３０は、後方物体を描画し前方物体を隠面消去する描画モードに設定して、前面深度値を第２の描画データとして描画バッファー５４に上書きで描画する。具体的には前面深度値を形状データのように扱って、第２の描画データ（形状データ）として、描画バッファー５４に書き込む。例えば後述する図８のステップＳ１２、Ｓ１３に示すような描画処理を行う。
【００７４】
そして処理部１０は、図８のステップＳ１４、Ｓ１６に示すように、描画バッファー５４に第１の描画データが上書きされずに残存している場合に、衝突検出対象オブジェクトが他のオブジェクトに衝突したと判定する。例えば第１の描画データに対応する所定色（例えば白））が描画バッファー５４に消されずに残っていた場合に、衝突検出対象オブジェクトが他のオブジェクトに衝突したと判定する。
【００７５】
なお、衝突検出対象オブジェクトは、他のオブジェクトとの衝突検出対象となるオブジェクトであり、例えばロボットをモデル化したオブジェクトなどである。また、プリミティブ面がポリゴンである場合を例にとると、三角形を構成する３頂点が、視点から見て例えば反時計回りに見える面が表面（front surface, front-facing surface）になり、視点から見て例えば時計回りに見える面が裏面（back surface, back-facing surface）になる。閉じたオブジェクトの表面が外を向いていることを前提にすると、表面を前面、裏面を背面と記述することができる。
【００７６】
以上のように本実施形態では、衝突検出対象オブジェクトの前面を描画することで、前面深度値が生成され、衝突検出対象オブジェクトの背面を描画することで、背面深度値が生成される。そして、これらの前面深度値と背面深度値に基づいて、衝突検出対象オブジェクトの前面と背面の間に他のオブジェクトが存在すると判定されると、衝突が発生したと判定される。即ち、本実施形態の手法は、衝突検出対象オブジェクトの前面と背面の間に、他のオブジェクトの面が描画されれば、それは衝突が発生したことを意味するという原理に基づいている。例えば図７（Ｂ）のＣ２、Ｃ３では、衝突検出対象オブジェクトＰＢ２、ＰＢ３の前面と背面の間に他のオブジェクトＯＢ３の面が描画されているため、衝突が発生したと判定できることになる。
【００７７】
以上のように本実施形態によれば、深度バッファー処理を有効活用した高速（正確）な衝突判定（近接判定）を実現できる。即ち、衝突（近接）の問題を、最新の描画ハードウェアー処理に適した遮蔽処理に置き換えることで、非常に高速に、衝突判定（近接判定）を行うことが可能になる。
【００７８】
なお本実施形態のオブジェクトの描画処理では、描画部３０は無限遠の視点（広義には所定の視点）での平行投影で描画処理（第１、第２、第３の描画処理）を行っている。
【００７９】
即ち、通常の３ＤＣＧにおいては、パースのついた画像を生成するために透視投影で描画処理を行うのが一般的である。この点、本実施形態では、３ＤＣＧの画像生成のためではなく、衝突判定のために深度バッファー処理を利用している。そして透視投影で描画処理を行うと、正確な衝突判定を実現できなくなるおそれがあり、本実施形態では、この点に着目して平行投影で描画処理を行っている。
【００８０】
図５に本実施形態の衝突検出システムを含むロボットシステムの例を示す。このロボットシステムは、制御装置３００（情報処理装置）とロボット３１０とを含む。制御装置３００はロボット３１０の制御処理を行う。具体的には、動作シーケンス情報（シナリオ情報）に基づいてロボット３１０を動作させる制御を行う。ロボット３１０は、アーム３２０及びハンド（把持部）３３０を有する。そして制御装置３００からの動作指示にしたがって動作する。例えば、図示しないパレットに載せられたワークを把持したり、移動するなどの動作を行う。また、図示しない撮像装置で取得された撮像画像情報に基づいて、ロボットの姿勢やワークの位置などの情報が検出され、検出された情報が制御装置３００に送られる。
【００８１】
本実施形態の衝突検出システムは例えば図５の制御装置３００に設けられ、例えば制御装置３００のハードウェアーやプログラムにより衝突検出システムが実現される。そして、ラインタイムの使用では、周辺環境などが動的に変化する場合に、ロボット３１０の実際の動作に先行して、本実施形態の衝突検出システムがシミュレーションにより衝突の判定処理を行う。そして制御装置３００は、ロボット３１０が周辺構造物や周辺機器などに衝突しないように、判定処理の結果に基づいてロボット３１０の制御を行う。一方、オフラインの使用では、本実施形態の衝突検出システムにより、動作シーケンス情報等の作成時にシミュレーションにより衝突を検証する。そして制御装置３００は、衝突が起こらないように作成された動作シーケンス情報（シナリオ情報）に基づいて、ロボット３１０を制御する。
【００８２】
３．本実施形態の手法
次に本実施形態の手法について図面を用いて更に詳細に説明する。
【００８３】
３．１  第１の衝突検出手法
オブジェクト（物体）が凸であり、且つ、仮定した視点（描画視点）から見て、衝突検出対象オブジェクトの重なりがない場合には、以下に説明する第１の衝突検出手法により衝突を判定できる。
【００８４】
具体的には、仮定した視点から見て衝突検出対象オブジェクトの前面を描画することで、前面深度値（第１の深度値）を得る。なお、衝突検出対象オブジェクトがない領域での前面深度値は、初期値（例えば最背面値）に設定される
また、仮定した視点から見て衝突検出対象オブジェクトの背面を描画することで、背面深度値（第２の深度値）を得る。なお、衝突検出対象オブジェクトがない領域での背面深度値は、初期値（例えば最背面値、或いは最前面値）に設定される。
【００８５】
そして、衝突検出対象オブジェクト以外の他のオブジェクトである被衝突検出対象オブジェクトを描画する。但し、上述の前面深度値よりも後方（所定の視点から見て後方）であり、背面深度値よりも前方（所定の視点から見て前方）のみを描画する。そして、被衝突検出対象オブジェクトが描画されれば、衝突が発生したと判定する。そうでなければ衝突なしと判定する。
【００８６】
更に具体的には、図４に示すように深度バッファー５６には、前面深度値記憶部６２及び背面深度値記憶部６４が設けられる。なお、これらの記憶部は等価的に同等の機能が実現されるものあれば、何でもよい。
【００８７】
そして、図８の詳細な処理で説明するように、深度バッファー５６の深度値を最背面値で初期化し、描画モードを前方物体描画モードに設定する。そして全ての衝突検出対象オブジェクトの前面を例えば黒で描画することで、前面深度値が得られる。この前面深度値は、例えば前面平面データとして保存される。
【００８８】
次に、深度バッファー５６の深度値を最前面値で初期化し、描画モードを後方物体描画モードに設定して、全ての衝突検出対象オブジェクトの背面を例えば黒で描画することで、背面深度値が得られる。
【００８９】
そして、この背面深度値を保持して参照して、描画モードを前方物体描画モードに切り替えて、全ての被衝突検出対象オブジェクト（他のオブジェクト）の両面（前面及び背面）を、例えば白のデータ（広義には第１の描画データ）で描画する。
【００９０】
次に、描画モードを後方物体描画モードに切り替えて、保存された前面平面データ（前面深度値）を、例えば黒のデータ（広義には第２の描画データ）で描画する。
【００９１】
そして、画像内（描画バッファーの画像）に、白のデータ（第１の描画データ）が残っていれば、その部分で衝突が発生したと判定する。一方、白のデータが残っていなければ、衝突が発生しなかったと判定する。
【００９２】
次に図６（Ａ）〜図７（Ｂ）を用いて本実施形態の第１の衝突検出手法について更に詳細に説明する。
【００９３】
例えば図６（Ａ）において、ＰＢ１、ＰＢ２、ＰＢ３は、衝突検出対象オブジェクトであり、ＯＢ１、ＯＢ２、ＯＢ３は、衝突検出対象オブジェクト以外の他のオブジェクト（被衝突検出対象オブジェクト）である。ロボットシステムに用いられる衝突検出システムを例にとれば、ＰＢ１、ＰＢ２、ＰＢ３は、現実世界のロボットをモデル化したロボットオブジェクト、或いはロボットオブジェクトを構成するパーツオブジェクトである。またＯＢ１、ＯＢ２、ＯＢ３は、周辺構造物や周辺機器をモデル化したオブジェクト、或いはそのパーツオブジェクトである。そして図６（Ａ）では、衝突検出対象であるオブジェクトＰＢ１は、他のオブジェクトであるＯＢ１、ＯＢ２、ＯＢ３と衝突していないが、衝突検出対象であるオブジェクトＰＢ２、ＰＢ３は、他のオブジェクトであるＯＢ３と衝突している。
【００９４】
なおパーツオブジェクトは、衝突検出対象オブジェクトなどのモデルオブジェクトを構成する部分となるオブジェクトである。例えば衝突検出対象オブジェクトなどのモデルオブジェクトは、複数のパーツオブジェクトと、パーツオブジェクト間を接続する関節部分などにより構成される。
【００９５】
図６（Ｂ）では、衝突検出対象オブジェクトＰＢ１、ＰＢ２、ＰＢ３の前面を描画する第１の描画処理が行われて、前面深度値ＤＰＦ（前面深度分布）が生成されている。この前面深度値ＤＰＦは、例えば図４の前面深度値記憶部６２に記憶される。初期状態では、前面深度値ＤＰＦは例えば最背面値に設定（初期化）される。そして図６（Ｂ）のＡ１、Ａ２、Ａ３に示すように、衝突検出対象オブジェクトＰＢ１、ＰＢ２、ＰＢ３の前面を描画する第１の描画処理により、前面深度値ＤＰＦは、ＰＢ１、ＰＢ２、ＰＢ３の前面が存在する領域では、ＰＢ１、ＰＢ２、ＰＢ３の前面の深度値に設定（更新）される。
【００９６】
図７（Ａ）では、衝突検出対象オブジェクトＰＢ１、ＰＢ２、ＰＢ３の背面を描画する第２の描画処理が行われて、背面深度値ＤＰＢ（背面深度分布）が生成されている。この背面深度値ＤＰＢは、例えば図４の背面深度値記憶部６４に記憶される。初期状態では、背面深度値ＤＰＢは例えば最背面値に設定（初期化）される。なお後述する図８のステップＳ６のように最前面値に設定してもよい。そして図７（Ａ）のＢ１、Ｂ２、Ｂ３に示すように、衝突検出対象オブジェクトＰＢ１、ＰＢ２、ＰＢ３の背面を描画する第２の描画処理により、背面深度値ＤＰＢは、ＰＢ１、ＰＢ２、ＰＢ３の背面が存在する領域では、ＰＢ１、ＰＢ２、ＰＢ３の背面の深度値に設定（更新）される。
【００９７】
次に図７（Ｂ）では、図６（Ｂ）、図７（Ａ）で生成された前面深度値ＤＰＦと背面深度値ＤＰＢに基づいて、衝突検出対象オブジェクトＰＢ１、ＰＢ２、ＰＢ３と他のオブジェクトＯＢ１、ＯＢ２、ＯＢ３の間の衝突判定が行われる。具体的には、他のオブジェクトＯＢ１、ＯＢ２、ＯＢ３を描画する第３の描画処理が行われる。そして第３の描画処理で描画された他のオブジェクトＯＢ１、ＯＢ２、ＯＢ３の面（前面又は背面）が、衝突検出対象オブジェクトＰＢ１、ＰＢ２、ＰＢ３の前面と背面の間に存在すると判定された場合には、衝突が発生したと判定する。
【００９８】
例えば図７（Ｂ）のＣ１では、衝突検出対象オブジェクトＰＢ１の前面と背面の間に、他のオブジェクトの面は存在しないため、衝突が発生していないと判定する。
【００９９】
一方、図７（Ｂ）のＣ２では、衝突検出対象オブジェクトＰＢ２の前面と背面の間に、他のオブジェクトＯＢ３の面（背面）が存在するため、衝突が発生したと判定される。同様にＣ３では、衝突検出対象オブジェクトＰＢ３の前面と背面の間に、他のオブジェクトＯＢ３の面（前面）が存在するため、衝突が発生したと判定する。
【０１００】
これらの衝突判定処理は、図６（Ｂ）、図７（Ａ）で生成された前面深度値ＤＰＦと背面深度値ＤＰＢに基づいて行われる。具体的には、第３の描画処理で描画された他のオブジェクトについての処理対象ピクセルの深度値が、前面深度値ＤＰＦと背面深度値ＤＰＢの間の深度値であると判定した場合に、衝突検出対象オブジェクトの前面と背面の間に他のオブジェクトの面が存在すると判定して、衝突が発生したと判定する。一方、他のオブジェクトについての処理対象ピクセルの深度値が、前面深度値ＤＰＦと背面深度値ＤＰＢの間の深度値ではないと判定した場合に、衝突検出対象オブジェクトの前面と背面の間に他のオブジェクトの面が存在しないと判定して、衝突が発生しなかったと判定する。
【０１０１】
図８は、本実施形態の第１の衝突検出手法の詳細な処理例を示すフローチャートである。
【０１０２】
まず深度バッファー５６の深度値を最背面値で初期化する（ステップＳ１）。そして、前方物体を描画するモードに設定する（ステップＳ２）。即ち前方物体を優先的に描画し、後方物体を隠面消去する描画モードに設定する。そして描画バッファー５４の全画面（全画面分の画素）を、黒（黒データ）で初期化する（ステップＳ３）。
【０１０３】
次に、全ての衝突検出対象オブジェクトの前面を黒で描画バッファー５４に描画して、深度バッファー５６に前面深度値を生成する（ステップＳ４）。即ち、衝突検出対象オブジェクトの前面を黒で描画する第１の描画処理を行うことで、図６（Ｂ）に示すような前面深度値ＤＰＦを生成する。そして、生成された深度バッファー５６の前面深度値（前面深度プレーン）を、前面平面データとして保存する（ステップＳ５）。即ち、前面深度値を前面平面の形状データのように見なして記憶部５０に保存する。
【０１０４】
次に、深度バッファー５６の深度値を、最前面値で初期化する（ステップＳ６）。そして、後方物体を描画するモードに設定する（ステップＳ７）。即ち後方物体を優先的に描画し、前方物体を隠面消去する描画モードに設定する。そして、描画バッファー５４の全画面を、黒で初期化する（ステップＳ８）。
【０１０５】
次に、全ての検出対象オブジェクトの背面を黒で描画バッファーに描画して、深度バッファー５６に背面深度値を生成する（ステップＳ９）。即ち、衝突検出対象オブジェクトの背面を黒で描画する第２の描画処理を行うことで、図７（Ａ）に示すような背面深度値ＤＰＢを生成する。
【０１０６】
次に、前方物体を描画するモードに設定する（ステップＳ１０）。そして、全ての被衝突検出対象オブジェクトの前面及び背面を白（第１の描画データ）で描画バッファー５４に描画する（ステップＳ１１）。即ち、他のオブジェクトである被衝突検出対象オブジェクトを描画する第３の描画処理を行う。
【０１０７】
次に、後方物体を描画するモードに設定する（ステップＳ１２）。そして、ステップＳ５で保存された前面平面データ（前面深度値）を、黒（第２の描画データ）で描画バッファー５４に上書きする（ステップＳ１３）。
【０１０８】
そして、ステップＳ１０で描画された白（第１の描画データ）は残っているか否かを判断する（ステップＳ１４）。即ち描画バッファー５４上に白の描画領域が残っているか否かを判断する。そして、残っていない場合には、衝突なしと判定して処理を終了する（ステップＳ１５）。一方、残っていた場合には、衝突ありと判定して、処理を終了する（ステップＳ１６）。
【０１０９】
図９（Ａ）、図９（Ｂ）は図８の処理を説明する図である。図９（Ａ）、図９（Ｂ）においてＰＬ１、ＰＬ２、ＰＬ３は、衝突検出対象オブジェクト以外の他のオブジェクトである被衝突検出対象オブジェクトの面（ポリゴン）を表している。
【０１１０】
図８のステップＳ４の第１の描画処理により、図９（Ａ）に示すような前面深度値ＤＰＦが生成され、ステップＳ５で、生成された前面深度値ＤＰＦが前面平面データとして保存される。またステップＳ９の第２の描画処理により、図９（Ａ）に示すような背面深度値ＤＰＢが生成される。
【０１１１】
そしてステップＳ１０で前方物体を描画し後方物体を隠面消去する描画モードに設定され、ステップＳ９で生成された背面深度値ＤＰＢを参照しながら、被衝突検出対象オブジェクトの面ＰＬ１、ＰＬ２、ＰＬ３が白のデータ（第１の描画データ）で描画バッファー５４に描画される。
【０１１２】
このように前面物体描画モードに設定されることで、図９（Ａ）の被衝突検出対象オブジェクトの面ＰＬ１のＪ１に示す部分については、背面深度値ＤＰＢに対して後方物体になるため、隠面消去される。これによりＪ１に示す部分については、描画バッファー５４に白のデータ（第１の描画データ）が残存しないようになる。
【０１１３】
一方、被衝突検出対象オブジェクトの面ＰＬ１のＪ２、Ｊ３や、面ＰＬ２のＪ４、Ｊ５、Ｊ６や、面ＰＬ３のＪ７、Ｊ８、Ｊ９に示す部分については、背面深度値ＤＰＢに対して前方物体になるため、隠面消去されない。従って、Ｊ２〜Ｊ９に示す部分については、描画バッファー６４に白のデータ（第１の描画データ）が残存するようになる。
【０１１４】
次に、図９（Ｂ）に示すように、図８のステップＳ１２で後方物体を描画し前方物体を隠面消去する描画モードに設定され、ステップＳ５で保存された前面深度値ＤＰＦが前面平面データ（第２の描画データ）として描画バッファー５４に描画される。
【０１１５】
このように後方物体描画モードに設定されて、前面深度値ＤＰＦである前面平面データが描画されると、被衝突検出対象オブジェクトの面ＰＬ１のＨ２、Ｈ３や、面ＰＬ２のＨ４、Ｈ６や、面ＰＬ３のＨ７、Ｈ８、Ｈ９に示す部分については、前面深度値ＤＰＦに対して前方物体になるため、隠面消去される。これにより、Ｈ２〜Ｈ４、Ｈ６〜Ｈ９に示す部分については、描画バッファー５４に白のデータ（第１の描画データ）が残存しないようになる。
【０１１６】
一方、被衝突検出対象オブジェクトの面ＰＬ２のＨ５に示す部分については、前面深度値ＤＰＦに対して後方物体になるため、隠面消去されず、描画バッファー６４に白のデータが残存するようになる。そして図９（Ｂ）の面ＰＬ１のＨ１に示す部分については、図９（Ａ）のＪ１に示すように隠面消去されて白のデータが残存しない。
【０１１７】
従って、結局、Ｈ５に示す部分にだけ、描画バッファー５４に白のデータ（第１の描画データ）が残存するようになる。従って、図８のステップＳ１４で、Ｈ５に示す部分について描画バッファー５４に白のデータが残存している場合には、衝突検出対象オブジェクトの前面と背面の間に、被衝突検出対象オブジェクトの面（ＰＬ２のＨ５に示す部分）が存在していると判断され、ステップＳ１６に示すように衝突が発生したと判定されるようになる。
【０１１８】
なお本実施形態の第１の衝突検出手法は図８〜図９（Ｂ）で説明した手法には限定されない。例えばピクセルシェーダー等を利用する場合には、第３の描画処理において、処理対象ピクセルの深度値が、前面深度値よりも後方側であり、且つ、背面深度値よりも前方側の深度値である場合に、処理対象ピクセルの描画データを描画バッファー５４に書き込むというシェーダープログラムを記述する。そして、描画バッファー５４への描画データの書き込み結果に基づいて、衝突検出対象オブジェクトの衝突判定を行う。即ち、図７（Ｂ）のＣ２やＣ３では、描画データが描画バッファー５４に書き込まれるため、衝突検出対象オブジェクトと他のオブジェクトが衝突したと判定できるようになる。
【０１１９】
３．２  第２の衝突検出手法
次に本実施形態の第２の衝突検出手法について説明する。オブジェクト（物体）が凸でない場合を含み、また、仮定した視点（描画視点）から見て、衝突検出対象オブジェクトに重なりがある場合には、以下に説明する第２の衝突検出手法により衝突を判定できる。
【０１２０】
まず、描画モードを単純加算とし、全ての衝突検出対象オブジェクトの色データを「１」として、衝突検出対象オブジェクトの前面のみを描画する。そして、生成された描画画像の全画面を調べ、衝突検出対象オブジェクトの重なり状態を検出する。例えば全画面中の最大値が、重なり数（自己多重度）の最大値Ｍになる。
【０１２１】
そして、Ｍ＝１ならば、上述した第１の衝突検出手法により衝突検出を行う。一方、Ｍ≧１ならば、２個で１組の深度値記憶部を少なくもＭ組用意する。即ち前面深度値記憶部（前面深度バッファー）と背面深度値記憶部（背面深度バッファー）で１組となる深度値記憶部の組を少なくともＭ組用意する。
【０１２２】
次に、全ての前面深度値記憶部の深度値を最背面値で初期化し、全ての背面深度値記憶部の深度値を最前面値で初期化する。そして、後述する図１５、図１６のフローチャートに示す処理により、各組が前面深度値記憶部及び背面深度値記憶部からなるＮ組の深度値記憶部の深度値を設定する。
【０１２３】
次に、これらの深度値記憶部の各組を用いて、全ての被衝突検出対象オブジェクト（他のオブジェクト）を描画する。この場合に、各組の深度値記憶部の前面深度値よりも後方で、且つ、各組の深度値記憶部の背面深度値よりも前方のみを描画する。そして、被衝突検出対象オブジェクトが描画されれば、衝突が発生したと判定し、そうでなければ衝突が発生しなかったと判定する。
【０１２４】
図１０は、本実施形態の第２の衝突検出手法を実現する衝突検出システムの構成例である。図１０では、図４の構成に対して、更に、処理部１０が重なり状態検出部１６、前面処理部１８、背面処理部２０を含む。また、深度バッファー５６は、第１〜第Ｎの深度値記憶部６０-1〜６０-Nを有する。
【０１２５】
具体的には、深度バッファー５６の第１の深度値記憶部６０-1は、第１の前面深度値記憶部６２-1、第１の背面深度値記憶部６４-1を有し、第２の深度値記憶部６０-2は、第２の前面深度値記憶部６２-2、第２の背面深度値記憶部６４-2を有する。同様に、第Ｎの深度値記憶部６０-Nは、第Ｎの前面深度値記憶部６２-N、第Ｎの背面深度値記憶部６４-Nを有する。即ち、第１〜第Ｎの深度値記憶部６０-1〜６０-Nのうちの第ｍの深度値記憶部（１≦ｍ≦Ｎ）は、第ｍの前面深度値を記憶する第ｍの前面深度値記憶部と、第ｍの前面深度値と組となる第ｍの背面深度値を記憶する第ｍの背面深度値記憶部を有する。
【０１２６】
処理部１０は、後述する図１９のステップＳ９６、Ｓ９８に示すように、第ｍの前面深度値記憶部の第ｍの前面深度値と、第ｍの背面深度値記憶部の第ｍの背面深度値とに基づいて、衝突検出対象オブジェクトの第ｍの前面深度値に対応する前面と、第ｍの背面深度値に対応する背面の間に、第３の描画処理で描画された他のオブジェクトが存在するか否かを判断する。そして、存在すると判断した場合に、衝突検出対象オブジェクトが他のオブジェクトに衝突したと判定する。
【０１２７】
例えば第１の前面深度値記憶部６２-1の第１の前面深度値と、第１の背面深度値記憶部６４-1の第１の背面深度値に基づいて、衝突検出対象オブジェクトの第１の前面深度値に対応する前面と、第１の背面深度値に対応する背面の間に、他のオブジェクトが存在するか否かを判断する。そして、衝突検出対象オブジェクトの前面と背面の間に他のオブジェクトが存在すると判断した場合に、衝突が発生したと判定する。以上の判定処理を、残りの第２〜第Ｎの深度値記憶部６０-2〜６０-Nの第２〜第Ｎの前面深度値記憶部６２-2〜６２-N、第２〜第Ｎの背面深度値記憶部６４-2〜６４-Nについて行う。
【０１２８】
また、重なり状態検出部１６は、所定の視点（描画視点。無限遠の視点）から見た場合における、衝突検出対象オブジェクトについての重なり状態を検出する。即ち、複数の衝突検出対象オブジェクト間の重なりや、衝突検出対象オブジェクトの自己重なりを検出する。そして重なり状態検出部１６で検出された重なり状態の最大重なり数をＭとすると、Ｎ≧Ｍとなり、望ましくはＮ＝Ｍとなる。即ち、深度バッファー５６には、前面深度値記憶部と背面深度値記憶部の組が、少なくともＭ組だけ設けられることになる。
【０１２９】
前面処理部１８は、第１〜第Ｎの前面深度値記憶部６２-1〜６２-Nへの前面深度値の設定処理を行う。具体的には、衝突検出対象オブジェクトについての処理対象ピクセルの深度値が、第１〜第Ｎの前面深度値記憶部６２-1〜６２-Nのうちの第ｉの前面深度値記憶部（１≦ｉ≦Ｎ）の深度値よりも、所定の視点（描画視点）から見て前方側の深度値であったとする。すると前面処理部１８は、後述する図１５のステップＳ４０に示すように、第ｉ〜第Ｎ−１の前面深度値記憶部６２-i〜６２-(N-1)の深度値を、第ｉ＋１〜第Ｎの前面深度値記憶部６２-(i+1)〜６２-Nに順次移動する（対応するピクセル位置に移動する）。例えば第ｉの前面深度値記憶部６２-iの深度値を、第ｉ＋１の前面深度値記憶部６２-(i+1)に移動し、第ｉ＋１の前面深度値記憶部６２-(i+1)の深度値を、第ｉ＋２の前面深度値記憶部６２-(i+2)に移動する。第ｉ＋２の前面深度値記憶部６２-(i+2)〜第Ｎ−１の前面深度値記憶部６２-(N-1)の深度値についても同様に移動する。
【０１３０】
そして前面処理部１８は、図１５のステップＳ４１に示すように、第ｉの前面深度値記憶部６２-iの深度値を、処理対象ピクセルの深度値に更新する。即ち処理対象ピクセルの深度値に書き換える。一方、第Ｎの前面深度値記憶部６２-Nの深度値については例えば破棄する。
【０１３１】
また背面処理部２０は、第１〜第Ｎの背面深度値記憶部６４-1〜６４-Nへの背面深度値の設定処理を行う。具体的には、衝突検出対象オブジェクトについての処理対象ピクセルの深度値が、第１〜第Ｎの背面深度値記憶部６４-1〜６４-Nのうちの第ｉの背面深度値記憶部６４-iの深度値よりも、所定の視点（描画視点）から見て後方側の深度値であったとする。すると背面処理部２０は、後述する図１６のステップＳ６０に示すように、第２〜第ｉの背面深度値記憶部６４-2〜６４-iの深度値を、第１〜第ｉ−１の背面深度値記憶部６４-1〜６４-(i-1)に順次移動する（対応するピクセル位置に移動する）。例えば第２の背面深度値記憶部６４-2の深度値を、第１の背面深度値記憶部６４-1に移動し、第３の背面深度値記憶部６４-3の深度値を、第２の背面深度値記憶部６４-2に移動する。第４の背面深度値記憶部６４-3〜第ｉの背面深度値６４-iについても同様に移動する。
【０１３２】
そして背面処理部２０は、図１６のステップＳ６１に示すように、第ｉの背面深度値記憶部６４-iの深度値を、処理対象ピクセルの深度値に更新する。即ち処理対象ピクセルの深度値に書き換える。一方、第１の背面深度値記憶部６４-1の深度値については例えば破棄する。
【０１３３】
以上のようにすることで、各組が前面深度値及び背面深度値からなるＮ組の深度値の組を生成して設定できるようになる。
【０１３４】
また、第ｍの背面深度値記憶部６４-mの第ｍの背面深度値よりも、第ｍ＋１の前面深度値記憶部６２-(m+1)の第ｍ＋１の前面深度値の方が、所定の視点から見て前方側の深度値であると判断されたとする。例えば第１の背面深度値記憶部６４-1の第１の背面深度値よりも、第２の前面深度値記憶部６２-2の第２の前面深度値の方が、所定の視点から見て前方側の深度値であると判断されたとする。この場合には処理部１０は、後述する図１７のステップＳ７６、Ｓ７８に示すように、衝突検出対象オブジェクトの自己衝突が発生したと判定する。即ち、この場合には、例えば第１の衝突検出対象オブジェクトの背面の方が、第１の衝突検出対象オブジェクトの後方側にあるべき第２の衝突検出対象オブジェクトの前面よりも前方側であると判断されたため、第１の衝突検出対象オブジェクトと第２の衝突検出対象オブジェクトの自己衝突（或いは衝突検出対象オブジェクトの内部的な自己衝突）が発生したと判定できる。
【０１３５】
次に図１１（Ａ）〜図１３を用いて本実施形態の第２の衝突検出手法について更に詳細に説明する。
【０１３６】
例えば図１１（Ａ）において、ＰＢ１、ＰＢ２、ＰＢ３は、衝突検出対象オブジェクトであり、ＯＢ１、ＯＢ２は、衝突検出対象オブジェクト以外の他のオブジェクト（被衝突検出対象オブジェクト）である。そして図１１（Ａ）では、衝突検出対象であるオブジェクトＰＢ２は、他のオブジェクトであるＯＢ２と衝突している。また衝突検出対象オブジェクトＰＢ１とＰＢ２や、ＰＢ３とＰＢ４は、描画処理の視点（所定の視点）から見て重なりが生じている。例えば衝突検出対象オブジェクトＰＢ１〜ＰＢ４がロボットのパーツオブジェクトである場合に、パーツオブジェクトＰＢ１とＰＢ２の間や、パーツオブジェクトＰＢ３とＰＢ４の間に、描画処理の視点から見て重なりが生じている。
【０１３７】
図１１（Ｂ）は、衝突検出対象オブジェクトの重なり状態の検出についての説明図である。重なり状態の検出のためには、例えば単純加算モードで衝突検出対象オブジェクトＰＢ１〜ＰＢ４を描画する。具体的には「１」の色データ（描画データ）で衝突検出対象オブジェクトＰＢ１〜ＰＢ４を描画する。
【０１３８】
そして図１１（Ｂ）のＤ１では、描画処理の視点から見た場合に１つの衝突検出対象オブジェクトＰＢ１だけが存在するため、重なり数（重なりの多重度）＝１になる。またＤ２では、描画処理の視点から見た場合に、２つの衝突検出対象オブジェクトＰＢ１、ＰＢ２が存在するため、重なり数＝２になる。またＤ３では、描画処理の視点から見た場合に、２つの衝突検出対象オブジェクトＰＢ３、ＰＢ４が存在すると共にＰＢ４には自己重なりが生じているため、重なり数＝３になる。従って、図１１（Ｂ）では、最大重なり数はＭ＝３になるため、少なくともＮ＝３組（Ｎ≧Ｍ＝３）の前面深度値及び背面深度値の組を設定することになる。
【０１３９】
図１２（Ａ）、図１２（Ｂ）、図１３は、３組の前面深度値及び背面深度値の例である。例えば図１２（Ａ）のＤＰＦ１、ＤＰＢ１は、第１の前面深度値、第１の背面深度値の組の例であり、図１２（Ｂ）のＤＰＦ２、ＤＰＢ２は、第２の前面深度値、第２の背面深度値の組の例である。また図１３のＤＰＦ３、ＤＰＢ３は、第３の前面深度値、第３の背面深度値の組の例である。ＤＰＦ１、ＤＰＢ１が第１深度値の組になり、ＤＰＦ２、ＤＰＢ２が第２の深度値の組になり、ＤＰＦ３、ＤＰＢ３が第３の深度値の組となる。
【０１４０】
そして、図１２（Ａ）のＥ１では、描画処理の視点から見た場合に衝突検出対象オブジェクトの前面と背面の組が１組になるため、重なり数は１になる。そしてＥ１では、衝突検出対象オブジェクトＰＢ１の前面、背面の深度値が、第１の前面深度値ＤＰＦ１、第１の背面深度値ＤＰＢ１として設定されている。
【０１４１】
また図１２（Ａ）のＦ１では、描画処理の視点から見た場合に衝突検出対象オブジェクトの前面と背面の組が２組になるため、重なり数が２になる。そして図１２（Ａ）のＦ１では、衝突検出対象オブジェクトＰＢ１の前面、背面の深度値が、第１の前面深度値ＤＰＦ１、第１の背面深度値ＤＰＢ１として設定されている。また図１２（Ｂ）のＦ２では、更に、衝突検出対象オブジェクトＰＢ２の前面、背面の深度値が、第２の前面深度値ＤＰＦ２、第２の背面深度値ＤＰＢ２として設定されている。
【０１４２】
また図１２（Ａ）のＧ１では、描画処理の視点から見た場合に衝突検出対象オブジェクトの前面と背面の組が３組になるため、重なり数が３になる。即ちＧ１では、衝突検出対象オブジェクトＰＢ４の凸部分である第１の部分と第２の部分の間に自己重なりが生じていると共に、衝突検出対象オブジェクトＰＢ３との重なりも生じている。そして図１２（Ａ）のＧ１では、衝突検出対象オブジェクトＰＢ４の第１の部分の前面、背面の深度値が、第１の前面深度値ＤＰＦ１、第１の背面深度値ＤＰＢ１として設定されている。また図１２（Ｂ）のＧ２では、衝突検出対象オブジェクトＰＢ３の前面、背面の深度値が、第２の前面深度値ＤＰＦ２、第２の背面深度値ＤＰＢ２として設定されている。また図１３のＧ３では、衝突検出対象オブジェクトＰＢ４の第２の部分の前面、背面の深度値が、第３の前面深度値ＤＰＦ３、第３の背面深度値ＤＰＢ３として設定されている。
【０１４３】
そして本実施形態では、図１２（Ａ）においては、第３の描画処理で描画される他のオブジェクトＯＢ１、ＯＢ２の処理対象ピクセルの深度値が、第１の前面深度値ＤＰＦ１と第１の背面深度値ＤＰＢ１の間にあるか否かを判断することで、衝突判定が行われる。また図１２（Ｂ）においては、他のオブジェクトＯＢ１、ＯＢ２の処理対象ピクセルの深度値が、第２の前面深度値ＤＰＦ２と第２の背面深度値ＤＰＢ２の間にあるか否かを判断することで、衝突判定が行われる。また図１３においては、他のオブジェクトＯＢ１、ＯＢ２の処理対象ピクセルの深度値が、第３の前面深度値ＤＰＦ３と第３の背面深度値ＤＰＢ３の間にあるか否かを判断することで、衝突判定が行われる。
【０１４４】
図１４〜図１９は、本実施形態の第２の衝突検出手法の詳細な処理例を示すフローチャートである。
【０１４５】
図１４は全体的な処理を示すフローチャートである。まず、全ての前面深度値記憶部の深度値を最背面値に初期化する（ステップＳ２１）。また、全ての背面深度値記憶部の深度値を最前面値に初期化する（ステップＳ２２）。即ち図１０の第１〜第Ｎの前面深度値記憶部６２-1〜６２-Nの深度値を最背面値に初期化し、第１〜第Ｎの背面深度値記憶部６４-1〜６４-Nの深度値を最前面値に初期化する。
【０１４６】
次に、全ての衝突検出対象オブジェクトの前面処理を行ったか否かを判断する（ステップＳ２３）。そして、前面処理が未処理の衝突検出対象オブジェクトがある場合には、未処理の衝突検出対象オブジェクトの前面処理を行う（ステップＳ２４）。一方、全ての衝突検出対象オブジェクトの前面処理を行った場合には、全ての衝突検出対象オブジェクトの背面処理を行ったか否かを判断する（ステップＳ２５）。そして、背面処理が未処理の衝突検出対象オブジェクトがある場合には、未処理の衝突検出対象オブジェクトの背面処理を行う（ステップＳ２６）。
【０１４７】
全ての衝突検出対象オブジェクトの背面処理を行った場合には、前面・背面の重なり検出処理を行う（ステップＳ２７）。そして、重なりが検出された場合には、自己衝突ありとして、処理を終了し、重なりが検出された場合には、他との衝突検出処理を行う（ステップＳ２８、Ｓ２９、Ｓ３０）。
【０１４８】
図１５は、図１４のステップＳ２４の前面処理の詳細を示すフローチャートである。まず、全ての処理対象ピクセルを処理したか否かを判断する（ステップＳ３１）。そして、未処理の処理対象ピクセルがある場合には、未処理の処理対象ピクセルを１つ選択する（ステップＳ３２）。一方、全ての処理対象ピクセルを処理した場合には、前面処理を終了する（ステップＳ３３）。
【０１４９】
未処理の処理対象ピクセルが選択されると、選択した処理対象ピクセルの深度値が、第１の前面深度値記憶部の深度値よりも前方か否かを判断する（ステップＳ３４）。そして、前方である場合には、ｉを１に設定して（ステップＳ３５）、ステップＳ４０に移行する。
【０１５０】
一方、選択した処理対象ピクセルの深度値が第１の前面深度値記憶部の深度値よりも前方ではない場合には、処理対象ピクセルの深度値が第２の前面深度値記憶部の深度値よりも前方か否かを判断するする（ステップＳ３６）。そして、前方である場合には、ｉを２に設定して（ステップＳ３７）、ステップＳ４０に移行する。
【０１５１】
同様の処理を順次実行して行き、選択した処理対象ピクセルの深度値が第Ｎの前面深度値記憶部の深度値よりも前方である場合には、ｉをＮに設定する（ステップＳ３８、Ｓ３９）。一方、前方ではない場合にはステップＳ３１に戻る。
【０１５２】
ステップＳ３５、Ｓ３７、Ｓ３９でｉの値が設定されると、第ｉ〜第Ｎ−１の前面深度値記憶部の深度値を、第ｉ＋１〜第Ｎの前面深度値記憶部へ、順次移動させる（ステップＳ４０）。この時、第Ｎの前面深度値記憶部の元の深度値は廃棄する。そして、第ｉの前面深度値記憶部の深度値を、処理対象ピクセルの深度値に書き換える更新を行って（ステップＳ４１）、ステップＳ３１に戻る。
【０１５３】
以上のような前面処理を行うことで、例えばＮ＝３の場合には、図１２（Ａ）〜図１３に示すような第１〜第３の前面深度値ＤＰＦ１〜ＤＰＦ３が生成されて、深度バッファー５６に設定されるようになる。
【０１５４】
図１６は、図１４のステップＳ２６の背面処理の詳細を示すフローチャートである。まず、全ての処理対象ピクセルを処理したか否かを判断する（ステップＳ５１）。そして、未処理の処理対象ピクセルがある場合には、未処理の処理対象ピクセルを１つ選択する（ステップＳ５２）。一方、全ての処理対象ピクセルを処理した場合には、背面処理を終了する（ステップＳ５３）。
【０１５５】
未処理の処理対象ピクセルが選択されると、選択した処理対象ピクセルの深度値が、第Ｎの背面深度値記憶部の深度値よりも後方か否かを判断する（ステップＳ５４）。そして、後方である場合には、ｉをＮに設定して（ステップＳ５５）、ステップＳ６０に移行する。
【０１５６】
同様の処理を順次実行して行き、処理対象ピクセルの深度値が、第２の背面深度値記憶部の深度値よりも後方である場合には、ｉを２に設定して（ステップＳ５６、Ｓ５７）、ステップＳ６０に移行する。一方、後方ではない場合には、処理対象ピクセルの深度値が、第１の背面深度値記憶部の深度値よりも後方か否かを判断し（ステップＳ５８）、後方である場合にはｉを１に設定して（ステップＳ５９）、ステップＳ６０に移行する。一方、後方でない場合にはステップＳ５１に戻る。
【０１５７】
ステップＳ５５、Ｓ５７、Ｓ５９でｉの値が設定されると、第２〜第ｉの背面深度値記憶部の深度値を、第１〜第ｉ−１の背面深度値記憶部へ、順次移動させる（ステップＳ６０）。この時、第１の背面深度値記憶部の元の深度値は廃棄する。そして、第ｉの背面深度値記憶部の深度値を、処理対象ピクセルの深度値に書き換える更新を行って（ステップＳ６１）、ステップＳ５１に戻る。
【０１５８】
以上のような背面処理を行うことで、例えばＮ＝３の場合には、図１２（Ａ）〜図１３に示すような第１〜第３の背面深度値ＤＰＢ１〜ＤＰＢ３が生成されて、深度バッファー５６に設定されるようになる。
【０１５９】
図２０（Ａ）〜図２０（Ｄ）は、図１５、図１６の前面処理、背面処理の説明図である。図２０（Ａ）〜図２０（Ｄ）において、ＤＳＦ１〜ＤＳＦ３は第１〜第３の前面深度値記憶部を表し、ＤＳＢ１〜ＤＳＢ３は第１〜第３の背面深度値記憶部を表す。またＤＰＸは処理対象ピクセルを表す。
【０１６０】
例えば図１５のステップＳ３４で、図２０（Ａ）に示すように処理対象ピクセルＤＰＸの深度値が第１の前面深度値記憶部ＤＳＦ１の深度値よりも前方と判断され、ステップＳ３５でｉ＝１に設定されたとする。するとステップＳ４０、図２０（Ａ）に示すように、第１、第２の前面深度値記憶部（第ｉ〜第Ｎ−１の前面深度値記憶部）ＤＳＦ１、ＤＳＦ２の深度値は、各々、第２、第３の前面深度値記憶部（第ｉ＋１〜第Ｎの前面深度値記憶部）ＤＳＦ２、ＤＳＦ３に順次移動し、第３の前面深度値記憶部（第Ｎの前面深度値記憶部）ＤＳＦ３の元の深度値は破棄される。そしてステップＳ４１、図２０（Ａ）に示すように、第１の前面深度値記憶部（第ｉの前面深度値記憶部）ＤＳＦ１の深度値が、処理対象ピクセルＤＰＸの深度値に書き換えられて更新される。
【０１６１】
また図１５のステップＳ３６で、図２０（Ｂ）に示すように処理対象ピクセルＤＰＸの深度値が第２の前面深度値記憶部ＤＳＦ２の深度値よりも前方（且つＤＳＦ１の後方）と判断され、ステップＳ３５でｉ＝２に設定されたとする。するとステップＳ４０、図２０（Ｂ）に示すように、第２の前面深度値記憶部ＤＳＦ２の深度値は第３の前面深度値記憶部ＤＳＦ３に移動し、第３の前面深度値記憶部ＤＳＦ３の元の深度値は破棄される。そしてステップＳ４１、図２０（Ｂ）に示すように、第２の前面深度値記憶部ＤＳＦ２の深度値が、処理対象ピクセルＤＰＸの深度値に書き換えられて更新される。
【０１６２】
また図１６のステップＳ５４で、図２０（Ｃ）に示すように処理対象ピクセルＤＰＸの深度値が第３の背面深度値記憶部ＤＳＢ３の深度値よりも後方と判断され、ステップＳ５５でｉ＝Ｎ＝３に設定されたとする。するとステップＳ６０、図２０（Ｃ）に示すように、第２、第３の背面深度値記憶部（第２〜第ｉの背面深度値記憶部）ＤＳＢ２、ＤＳＢ３の深度値は、各々、第１、第２の背面深度値記憶部（第１〜第ｉ−１の背面深度値記憶部）ＤＳＢ１、ＤＳＢ２に順次移動し、第１の背面深度値記憶部ＤＳＢ１の元の深度値は破棄される。そしてステップＳ６１、図２０（Ｃ）に示すように、第３の背面深度値記憶部（第ｉの背面深度値記憶部）ＤＳＢ３の深度値が、処理対象ピクセルＤＰＸの深度値に書き換えられて更新される。
【０１６３】
また図１６のステップＳ５６で、図２０（Ｄ）に示すように処理対象ピクセルＤＰＸの深度値が第２の背面深度値記憶部ＤＳＢ２の深度値よりも後方（且つＤＳＢ３の前方）と判断され、ステップＳ５７でｉ＝２に設定されたとする。するとステップＳ６０、図２０（Ｄ）に示すように、第２の背面深度値記憶部ＤＳＢ２の深度値は第１の背面深度値記憶部ＤＳＢ１に移動し、第１の背面深度値記憶部ＤＳＢ１の元の深度値は破棄される。そしてステップＳ６１、図２０（Ｄ）に示すように、第２の背面深度値記憶部ＤＳＢ２の深度値が、処理対象ピクセルＤＰＸの深度値に書き換えられて更新される。
【０１６４】
以上のようにすれば、処理対象ピクセルの深度値の判定処理を行って、深度値の移動処理等を行うだけで、図１２（Ａ）〜図１３に示すような第１〜第３の前面深度値ＤＳＦ１〜ＤＳＦ３、第１〜第３の背面深度値ＤＳＢ１〜ＤＳＢ３を自動的に生成して深度バッファー５６に設定できるようになる。
【０１６５】
図１７は、図１４のステップＳ２７の前面・背面の重なり検出処理の詳細を示すフローチャートである。
【０１６６】
まず、全ての処理対象ピクセルを処理したか否かを判断する（ステップＳ７１）。そして、重なりが検出されることなく全ての処理対象ピクセルの処理を完了した場合には、重なりなしとして、処理を終了する（ステップＳ７２）。一方、未処理の処理対象ピクセルがある場合には、未処理の処理対象ピクセルを１つ選択して、ｍを１に設定する（ステップＳ７３、Ｓ７４）。
【０１６７】
次に（Ｎ−１）番目までの深度値記憶部を処理したか否かを判断し（ステップＳ７５）、処理した場合にはステップＳ７１に戻る。一方、処理していない場合には、第ｍの背面深度値記憶部の深度値よりも、第ｍ＋１の前面深度値記憶部の深度値は前方か否かを判断する（ステップＳ７６）。そして、前方ではない場合には、ｍを１だけインクリメントして（ステップＳ７７）、ステップＳ７５に戻る。一方、第ｍの背面深度値記憶部の深度値よりも、第ｍ＋１の前面深度値記憶部の深度値の方が前方である場合には、重なりありとして、処理を終了する（ステップＳ７８）。この場合には図１４のステップＳ２８において重なりが検出されたと判断され、ステップＳ２９に示すように、自己衝突ありとして処理を終了する。即ちこの場合には、衝突検出対象オブジェクトの自己衝突が発生したとして処理を終了する。
【０１６８】
図１８は、図１４のステップＳ３０の他との衝突検出処理の詳細を示すフローチャートである。
【０１６９】
まず、全ての被衝突検出対象オブジェクト（他のオブジェクト）の前面及び背面の処理（両面の描画処理）を行ったか否かを判断する（ステップＳ８１）。そして、衝突が検出されることなく全ての被衝突検出対象オブジェクトの前面及び背面の処理が完了した場合には、衝突なしとして、処理を終了する（ステップＳ８２）。一方、処理が終了していない被衝突検出対象オブジェクトがある場合には、未処理の被衝突検出対象オブジェクトと衝突検出対象オブジェクトとの衝突検出処理を行う（ステップＳ８３）。そして、衝突は検出されたか否かを判断し（ステップＳ８４）、検出されなかった場合にはステップＳ８１に戻り、検出された場合には、衝突ありとして、処理を終了する（ステップＳ８５）。
【０１７０】
図１９は、図１８のステップＳ８３の衝突検出処理の詳細を示すフローチャートである。
【０１７１】
まず、全ての処理対象ピクセルを処理したか否かを判断する（ステップＳ９１）。そして、衝突が検出されることなく、全ての処理対象ピクセルの処理が完了した場合には、衝突なしとして、処理を終了する（ステップＳ９２）。一方、未処理の処理対象ピクセルがある場合には、未処理の処理対象ピクセルを１つ選択して、ｍを１に設定する（ステップＳ９３、Ｓ９４）。
【０１７２】
次に、Ｎ番目までの深度値記憶部を処理したか否かを判断し（ステップＳ９５）、処理した場合にはステップＳ９１に戻る。一方、処理していない場合には、処理対象ピクセルの深度値が、第ｍの前面深度値記憶部の深度値と第ｍの背面深度値記憶部の深度値の間にあるか否かを判断する（ステップＳ９６）。そして、これらの深度値の間にない場合には、ｍを１だけインクリメントして（ステップＳ９７）、ステップＳ９５に戻る。一方、これらの深度値の間にある場合には、衝突ありとして、処理を終了する（ステップＳ９８）。即ち図１２（Ａ）の深度値ＤＰＦ１、ＤＰＢ１の間や、図１２（Ｂ）の深度値ＤＰＦ２、ＤＰＢ２の間や、図１３の深度値ＤＰＦ３、ＤＰＢ４の間に、被衝突検出対象オブジェクト（他のオブジェクト）についての処理対象ピクセルの深度値がある場合には、衝突検出対象オブジェクトと被衝突検出対象オブジェクトの衝突が発生したと判断して、処理を終了する。
【０１７３】
なお図１９の衝突検出処理は、図８と同様の処理に置き換えることが可能である。即ち、第ｍの背面深度値記憶部の深度値を通常の深度値とし、第ｍ＋ｌの前面深度値記憶部の深度値を有する平面を描画し、実際に描画されるかどうかを判断する処理に置き換え可能である。
【０１７４】
なお、上記のように本実施形態について詳細に説明したが、本発明の新規事項および効果から実体的に逸脱しない多くの変形が可能であることは当業者には容易に理解できるであろう。従って、このような変形例はすべて本発明の範囲に含まれるものとする。例えば、明細書又は図面において、少なくとも一度、より広義または同義な異なる用語と共に記載された用語は、明細書又は図面のいかなる箇所においても、その異なる用語に置き換えることができる。また本実施形態及び変形例の全ての組み合わせも、本発明の範囲に含まれる。また衝突検出システム、ロボットシステムの構成・動作や、前面深度値・背面深度値の生成手法や、衝突検出対象オブジェクト・他のオブジェクトの描画手法や、衝突判定手法等も、本実施形態で説明したものに限定されず、種々の変形実施が可能である。
【符号の説明】
【０１７５】
ＯＢＡ〜ＯＢＣ、ＯＢＡ１〜ＯＢＡ４、オブジェクト、
ＰＢ１〜ＰＢ３  衝突検出対象オブジェクト、
ＯＢ１〜ＯＢ３  他のオブジェクト（被衝突検出対象オブジェクト）、
ＤＰＦ  前面深度値、ＤＰＢ  背面深度値、
ＤＰＦ１〜ＤＰＦ３  第１〜第３の前面深度値、
ＤＰＢ１〜ＤＰＢ３  第１〜第３の背面深度値、
１０  処理部、１２  オブジェクト空間設定部、１４  衝突判定部、
１６  重なり状態検出部、１８  前面処理部、２０  背面処理部、
３０  描画部、５０  記憶部、５２  オブジェクトデータ記憶部、
５４  描画バッファー、５６  深度バッファー、
６０-1〜６０-N  第１〜第Ｎの深度値記憶部、
６２  前面深度値記憶部、６２-1〜６２-N  第１〜第Ｎの前面深度値記憶部、
６４  背面深度値記憶部、６４-1〜６４-N  第１〜第Ｎの背面深度値記憶部、
７０  操作部、８０  外部Ｉ／Ｆ部、９０  情報記憶媒体、
３００  制御装置、３１０  ロボット、３２０  アーム、３３０  ハンド
【図１】
2012243138.tif 000003
【図２】
2012243138.tif 000004
【図３】
2012243138.tif 000005
【図４】
2012243138.tif 000006
【図５】
2012243138.tif 000007
【図６】
2012243138.tif 000008
【図７】
2012243138.tif 000009
【図８】
2012243138.tif 000010
【図９】
2012243138.tif 000011
【図１０】
2012243138.tif 000012
【図１１】
2012243138.tif 000013
【図１２】
2012243138.tif 000014
【図１３】
2012243138.tif 000015
【図１４】
2012243138.tif 000016
【図１５】
2012243138.tif 000017
【図１６】
2012243138.tif 000018
【図１７】
2012243138.tif 000019
【図１８】
2012243138.tif 000020
【図１９】
2012243138.tif 000021
【図２０】
2012243138.tif 000022