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