(57)【要約】【課題】複数の３次元モデル間の衝突を、実時間で検知する。【解決手段】制御手段で仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を操作し、ラスタライザ群で仮想視点から見た３次元モデルを距離データからなる距離画像として生成し、並列ソータはラスタライザ群からの３次元モデルデータの距離画像をもとに画素毎に視点からの距離の順に並び替え、差分算出手段は並び替えた各距離データの隣り合う２個の距離データの差分を求め、衝突判定手段は求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する。各３次元モデルにそれらを識別する識別コードを付与して、距離データとともに並び替え、衝突したモデルを識別できる。各モデルに各色と不透明度を与えて、アルファブレンディングすることもできる。色と不透明度をテーブルにより選択するようにしても良い。【選択図】  図1
2005327125.tif 000002
【特許請求の範囲】
【請求項１】
２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する方法であって、
操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御過程と、
仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成する複数のラスタライズ過程と、
前記ラスタライズ過程により生成した距離画像をもとに３次元モデルデータを画素毎に視点からの距離の順に並び替える並び替え過程と、
前記並び替え過程により並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出過程と、
前記差分算出過程により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定過程とからなることを特徴とする衝突検知方法。
【請求項２】
２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する装置であって、
操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御手段と、
仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成するラスタライザ群と、
前記ラスタライザ群により生成した距離画像をもとに３次元モデルデータを画素毎に視点からの距離の順に並び替える並列ソータと、
前記並列ソータにより並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出手段と、
前記差分算出手段により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定手段とからなることを特徴とする衝突検知装置。
【請求項３】
それぞれの３次元モデルを識別する識別コードを与えられた、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する方法であって、
操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御過程と、
仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成するとともに、それぞれの距離画像に３次元モデルデータを識別する識別コードを与える複数のラスタライズ過程と、
前記ラスタライズ過程により生成し識別コードが与えられた距離画像をもとに当該距離画像及び識別コードとともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並び替え過程と、
前記並び替え過程により並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出過程と、
前記差分算出過程により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定過程と、
前記衝突判定過程により衝突を判定されたモデルの識別コードを出力する衝突モデル識別コード出力過程と
からなることを特徴とする衝突検知方法。
【請求項４】
それぞれの３次元モデルを識別する識別コードを与えられた、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する装置であって、
操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御手段と、
仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成するとともに、それぞれの距離画像に３次元モデルデータを識別する識別コードを与えるラスタライザ群と、
前記ラスタライザ群により生成し識別コードが与えられた距離画像をもとに当該距離画像及び識別コードとともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並列ソータと、
前記並列ソータにより並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出手段と、
前記差分算出手段により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定手段と、
前記衝突判定手段により衝突を判定されたモデルの識別コードを出力する衝突モデル識別コード出力手段と
からなることを特徴とする衝突検知装置。
【請求項５】
それぞれの色と不透明度を与えられた、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する方法であって、
操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御過程と、
仮想の視点から見た各３次元モデルを距離データからなる距離画像及び色と不透明度を含む２次元画像として生成する複数のラスタライズ過程と、
前記ラスタライズ過程により生成した距離画像をもとに色と不透明度とともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並び替え過程と、
前記並び替え過程により並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出過程と、
前記差分算出過程により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定過程と、
前記並び替え過程により並び替えた順及び色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするアルファブレンディング過程と、
前記衝突判定過程により衝突を判定された画素に対して予め定めた色を優先的に選択する色選択過程と
からなることを特徴とする衝突検知方法。
【請求項６】
それぞれの色と不透明度を与えられた、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する装置であって、
操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御手段と、
仮想の視点から見た各３次元モデルを距離データからなる距離画像及び色と不透明度を含む２次元画像として生成するラスタライザ群と、
前記ラスタライザ群により生成した距離画像をもとに色と不透明度とともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並列ソータと、
前記並列ソータにより並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出手段と、
前記差分算出手段により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定手段と、
前記並列ソータにより並び替えた順及び色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするアルファブレンディング手段と、
前記衝突判定手段により衝突を判定された画素に対して予め定めた色を優先的に選択する色選択手段と
からなることを特徴とする衝突検知装置。
【請求項７】
それぞれの３次元モデルを識別する識別コードを与えられ、かつ、前記識別コードに対して色と不透明度を対応付けたテーブルを有し、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する方法であって、
操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御過程と、
仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成するとともに、それぞれの距離画像に３次元モデルデータを識別する識別コードを与える複数のラスタライズ過程と、
前記ラスタライズ過程により生成し識別コードが与えられた距離画像をもとに当該距離画像及び識別コードとともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並び替え過程と、
前記並び替え過程により並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出過程と、
前記差分算出過程により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定過程と、
前記テーブルから前記並び替え過程において並び替えた識別コードに対応する色と不透明度を得るテーブル検索過程と、
前記並び替え過程により並び替えた順及び前記テーブル検索過程により決定された色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするアルファブレンディング過程と、
前記衝突判定過程により衝突を判定された画素に対して予め定めた色を優先的に選択する色選択過程と
からなることを特徴とする衝突検知方法。
【請求項８】
請求項７記載の衝突検知方法において、さらに、衝突判定過程により衝突を判定されたモデルの識別コードを出力する衝突モデル識別コード出力過程を有することを特徴とする衝突検知方法。
【請求項９】
それぞれの３次元モデルを識別する識別コードを与えられ、かつ、前記識別コードに対して色と不透明度を対応付けたテーブルを有し、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する装置であって、
操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御手段と、
仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成するとともに、それぞれの距離画像に３次元モデルデータを識別する識別コードを与えるラスタライザ群と、
前記ラスタライザ群により生成し識別コードが与えられた距離画像をもとに当該距離画像及び識別コードとともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並列ソータと、
前記並列ソータにより並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出手段と、
前記差分算出手段により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定手段と、
前記テーブルから前記並列ソータにおいて並び替えた識別コードに対応する色と不透明度を得るテーブル検索手段と、
前記並列ソータにより並び替えた順及び前記テーブル検索手段により決定された色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするアルファブレンディング手段と、
前記衝突判定手段により衝突を判定された画素に対して予め定めた色を優先的に選択する色選択手段と
からなることを特徴とする衝突検知装置。
【請求項１０】
請求項９記載の衝突検知装置において、さらに、衝突判定手段により衝突を判定されたモデルの識別コードを出力する衝突モデル識別コード出力手段を備えたことを特徴とする衝突検知装置。
【請求項１１】
衝突判定過程において画素毎に衝突を判定されたときはインクリメントし、衝突していないときは値を保持して、画像内の衝突している画素数をカウンタによりカウントするカウント過程とカウント値出力過程を備えることを特徴とする請求項１又は請求項３又は請求項５又は請求項７又は請求項８のいずれか１に記載の衝突検知方法。
【請求項１２】
衝突判定手段により画素毎に衝突を判定されたときはインクリメントし、衝突していないときは値を保持して、画像内の衝突している画素数をカウントするカウンタとカウント値出力手段を備えたことを特徴とする請求項２又は請求項４又は請求項６又は請求項９又は請求項１０のいずれか１に記載の衝突検知装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、３次元コンピュータグラフィックスの手法により定義された３次元モデル及びステレオ写真測量やＸ線コンピュータトモグラフィ等の手法により計測された３次元画像データ及びボリュームデータを対象とし、手術シミュレータにおけるメス等の術具と臓器との当たり検知、３次元ＣＡＤにおけるモデル間の干渉の検出、フライトシミュレータにおける自機と地形との距離計算などに利用される方法及びその装置に関するものである。
【背景技術】
【０００２】
３次元モデルは、物体の形状をポリゴンで構成することにより表現することが多いが、モデルが複雑になるとポリゴン数が増え、また、モデル数が増えるに従い組み合わせの数が急激に増え、ポリゴンの交差判定計算が膨大になる問題がある。衝突検知を行うための従来技術は３種類に分類される。
（１）  ３次元モデルを内包する球、直方体など、データ量の少ない簡易なモデルで代替させ、ソフトウェアにより衝突判定の計算を行う。複雑な形状のモデルでは多数の球や直方体が必要となり処理時間がかかる。また、形状の精度にも限界がある。
（２）  ツリー構造などを用いて３次元モデルを階層的に空間分割し、計算の対象となるモデルを減らしてソフトウェアにより衝突判定の計算を行う。複雑な形状のモデルでは階層が深くなり処理時間がかかる。
（３）  ３次元モデルをＺバッファ法によりラスタライズし、フレームバッファのＺ値を読み出してソフトウェアにより衝突を判定する。高速なグラフィックスエンジンを利用すればラスタライズは短時間に処理できるが、対象となるモデルをラスタライズするたびにソフトウェア処理によりフレームバッファのＺ値を読み出し、画素毎に判定する処理が必要となり、処理時間がかかる。
以上のように、従来の技術では、衝突検知処理を実時間で行うことはできなかった。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明が解決しようとする課題は、複数の３次元モデル間の衝突を、実時間で検知する方法及びその装置を提供することにある。
【課題を解決するための手段】
【０００４】
上記課題を解決するため請求項１に係る衝突検知方法は、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する方法であって、操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御過程と、仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成する複数のラスタライズ過程と、前記ラスタライズ過程により生成した距離画像をもとに３次元モデルデータを画素毎に視点からの距離の順に並び替える並び替え過程と、前記並び替え過程により並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出過程と、前記差分算出過程により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定過程とからなることを特徴とするものである。
【０００５】
請求項２に係る衝突検知装置は、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する装置であって、操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御手段と、仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成するラスタライザ群と、前記ラスタライザ群により生成した距離画像をもとに３次元モデルデータを画素毎に視点からの距離の順に並び替える並列ソータと、前記並列ソータにより並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出手段と、前記差分算出手段により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定手段とからなることを特徴とするものである。
【０００６】
請求項３に係る衝突検知方法は、それぞれの３次元モデルを識別する識別コードを与えられた、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する方法であって、操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御過程と、仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成するとともに、それぞれの距離画像に３次元モデルデータを識別する識別コードを与える複数のラスタライズ過程と、前記ラスタライズ過程により生成し識別コードが与えられた距離画像をもとに当該距離画像及び識別コードとともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並び替え過程と、前記並び替え過程により並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出過程と、前記差分算出過程により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定過程と、前記衝突判定過程により衝突を判定されたモデルの識別コードを出力する衝突モデル識別コード出力過程とからなることを特徴とするものである。
【０００７】
請求項４に係る衝突検知装置は、それぞれの３次元モデルを識別する識別コードを与えられた、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する装置であって、操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御手段と、仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成するとともに、それぞれの距離画像に３次元モデルデータを識別する識別コードを与えるラスタライザ群と、前記ラスタライザ群により生成し識別コードが与えられた距離画像をもとに当該距離画像及び識別コードとともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並列ソータと、前記並列ソータにより並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出手段と、前記差分算出手段により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定手段と、前記衝突判定手段により衝突を判定されたモデルの識別コードを出力する衝突モデル識別コード出力手段とからなることを特徴とするものである。
【０００８】
請求項５に係る衝突検知方法は、それぞれの色と不透明度を与えられた、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する方法であって、操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御過程と、仮想の視点から見た各３次元モデルを距離データからなる距離画像及び色と不透明度を含む２次元画像として生成する複数のラスタライズ過程と、前記ラスタライズ過程により生成した距離画像をもとに色と不透明度とともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並び替え過程と、前記並び替え過程により並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出過程と、前記差分算出過程により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定過程と、前記並び替え過程により並び替えた順及び色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするアルファブレンディング過程と、前記衝突判定過程により衝突を判定された画素に対して予め定めた色を優先的に選択する色選択過程とからなることを特徴とするものである。
【０００９】
請求項６に係る衝突検知装置は、それぞれの色と不透明度を与えられた、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する装置であって、操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御手段と、仮想の視点から見た各３次元モデルを距離データからなる距離画像及び色と不透明度を含む２次元画像として生成するラスタライザ群と、前記ラスタライザ群により生成した距離画像をもとに色と不透明度とともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並列ソータと、前記並列ソータにより並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出手段と、前記差分算出手段により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定手段と、前記並列ソータにより並び替えた順及び色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするアルファブレンディング手段と、前記衝突判定手段により衝突を判定された画素に対して予め定めた色を優先的に選択する色選択手段とからなることを特徴とするものである。
【００１０】
請求項７に係る衝突検知方法は、それぞれの３次元モデルを識別する識別コードを与えられ、かつ、前記識別コードに対して色と不透明度を対応付けたテーブルを有し、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する方法であって、操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御過程と、仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成するとともに、それぞれの距離画像に３次元モデルデータを識別する識別コードを与える複数のラスタライズ過程と、前記ラスタライズ過程により生成し識別コードが与えられた距離画像をもとに当該距離画像及び識別コードとともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並び替え過程と、前記並び替え過程により並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出過程と、前記差分算出過程により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定過程と、前記テーブルから前記並び替え過程において並び替えた識別コードに対応する色と不透明度を得るテーブル検索過程と、前記並び替え過程により並び替えた順及び前記テーブル検索過程により決定された色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするアルファブレンディング過程と、前記衝突判定過程により衝突を判定された画素に対して予め定めた色を優先的に選択する色選択過程とからなることを特徴とするものである。
【００１１】
請求項８に係る衝突検知方法は、請求項７記載のものにおいて、さらに、衝突判定過程により衝突を判定されたモデルの識別コードを出力する衝突モデル識別コード出力過程を有することを特徴とするものである。
【００１２】
請求項９に係る衝突検知装置は、それぞれの３次元モデルを識別する識別コードを与えられ、かつ、前記識別コードに対して色と不透明度を対応付けたテーブルを有し、２個以上の３次元モデル画像データを対象とし、モデル間の衝突を検知する装置であって、操作に従って仮想の視点の位置、視線方向、視野角、３次元モデルの位置、姿勢、大きさ、形状のいずれかあるいは複数を制御する制御手段と、仮想の視点から見た各３次元モデルを距離データからなる距離画像として生成するとともに、それぞれの距離画像に３次元モデルデータを識別する識別コードを与えるラスタライザ群と、前記ラスタライザ群により生成し識別コードが与えられた距離画像をもとに当該距離画像及び識別コードとともに３次元モデルデータを画素毎に視点からの距離の順に並び替える並列ソータと、前記並列ソータにより並び替えた各距離データの隣り合う２個の距離データの差分を求める差分算出手段と、前記差分算出手段により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定手段と、前記テーブルから前記並列ソータにおいて並び替えた識別コードに対応する色と不透明度を得るテーブル検索手段と、前記並列ソータにより並び替えた順及び前記テーブル検索手段により決定された色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするアルファブレンディング手段と、前記衝突判定手段により衝突を判定された画素に対して予め定めた色を優先的に選択する色選択手段とからなることを特徴とするものである。
【００１３】
請求項１０に係る衝突検知装置は、請求項９記載のものにおいて、さらに、衝突判定手段により衝突を判定されたモデルの識別コードを出力する衝突モデル識別コード出力手段を備えたことを特徴とするものである。
【００１４】
請求項１１に係る衝突検知方法は、請求項１又は請求項３又は請求項５又は請求項７又は請求項８のいずれか１に記載のものにおいて、衝突判定過程において画素毎に衝突を判定されたときはインクリメントし、衝突していないときは値を保持して、画像内の衝突している画素数をカウンタによりカウントするカウント過程を備えることを特徴とするものである。
【００１５】
請求項１２に係る衝突検知装置は、請求項２又は請求項４又は請求項６又は請求項９又は請求項１０のいずれか１に記載のものにおいて、衝突判定手段により画素毎に衝突を判定されたときはインクリメントし、衝突していないときは値を保持して、画像内の衝突している画素数をカウントするカウンタを備えたことを特徴とするものである。
【発明の効果】
【００１６】
請求項１に係る衝突検知方法は、複数のラスタライズ過程により生成した距離画像をもとに３次元モデルデータを画素毎に視点からの距離の順に並び替えて、各距離データの隣り合う２個の距離データの差分を求めて、差分の大きさにより画素毎に衝突を判定するから、画素単位に実時間で衝突検知を行うことができる。さらに、仮想の視点の位置を操作することにより関心のある場所へ視点を移動でき、仮想の視点の視線方向を操作することにより関心のある対象物を視野に入れることができ、仮想の視点の視野角を操作することにより、関心のある小領域を拡大したり、あるいは、広い領域を概観することができ、また、３次元モデルの位置や姿勢を操作することにより、例えば外科医がメスを扱うときの動きを模擬でき、さらに、３次元モデルの位置、姿勢、大きさ、形状を操作することにより、例えば人体の心臓の拍動や弁の動きを模擬できる。
【００１７】
請求項２に係る衝突検知装置は、ラスタライザ群により生成した距離画像をもとに、並列ソータにより３次元モデルデータを画素毎に視点からの距離の順に並び替えて、差分算出手段で各距離データの隣り合う２個の距離データの差分を求めて、衝突判定手段において差分の大きさにより画素毎に衝突を判定するから、画素単位に実時間で衝突検知を行うことができる。さらに、仮想の視点の位置を操作することにより関心のある場所へ視点を移動でき、仮想の視点の視線方向を操作することにより関心のある対象物を視野に入れることができ、仮想の視点の視野角を操作することにより、関心のある小領域を拡大したり、あるいは、広い領域を概観することができ、また、３次元モデルの位置や姿勢を操作することにより、例えば外科医がメスを扱うときの動きを模擬でき、さらに、３次元モデルの位置、姿勢、大きさ、形状を操作することにより、例えば人体の心臓の拍動や弁の動きを模擬できる。
【００１８】
請求項３に係る衝突検知方法は、複数のラスタライズ過程により生成した距離画像をもとに３次元モデルデータを画素毎に視点からの距離の順に並び替えて、各距離データの隣り合う２個の距離データの差分を求めて、差分の大きさにより画素毎に衝突を判定し、衝突している画素を占める３次元モデルに与えられる識別コードを出力しているから、画素単位に実時間で衝突検知を行うことができるとともに、衝突しているモデルを知ることができる。さらに、仮想の視点の位置を操作することにより関心のある場所へ視点を移動でき、仮想の視点の視線方向を操作することにより関心のある対象物を視野に入れることができ、仮想の視点の視野角を操作することにより、関心のある小領域を拡大したり、あるいは、広い領域を概観することができ、また、３次元モデルの位置や姿勢を操作することにより、例えば外科医がメスを扱うときの動きを模擬でき、さらに、３次元モデルの位置、姿勢、大きさ、形状を操作することにより、例えば人体の心臓の拍動や弁の動きを模擬できる。
【００１９】
請求項４に係る衝突検知装置は、ラスタライザ群により生成した距離画像をもとに、並列ソータにより３次元モデルデータを画素毎に視点からの距離の順に並び替えて、差分算出手段で各距離データの隣り合う２個の距離データの差分を求めて、衝突判定手段において差分の大きさにより画素毎に衝突を判定し、衝突している画素を占める３次元モデルに与えられる識別コードを衝突モデル識別コード出力手段により出力しているから、画素単位に実時間で衝突検知を行うことができるとともに、衝突しているモデルを知ることができる。さらに、仮想の視点の位置を操作することにより関心のある場所へ視点を移動でき、仮想の視点の視線方向を操作することにより関心のある対象物を視野に入れることができ、仮想の視点の視野角を操作することにより、関心のある小領域を拡大したり、あるいは、広い領域を概観することができ、また、３次元モデルの位置や姿勢を操作することにより、例えば外科医がメスを扱うときの動きを模擬でき、さらに、３次元モデルの位置、姿勢、大きさ、形状を操作することにより、例えば人体の心臓の拍動や弁の動きを模擬できる。
【００２０】
請求項５に係る衝突検知方法は、前述の請求項１の効果を奏するとともに、並び替えた順及び色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をし、衝突判定過程により衝突を判定された画素に対して予め定めた色を優先的に選択するから、３次元モデルを所定の不透明度で透過した状態で確認することができ、衝突している画素部分を所定の色表示から判断することができる。
【００２１】
請求項６に係る衝突検知装置は、前述の請求項２の効果を奏するとともに、並列ソータにより並び替えた順及び色と不透明度に基づいて、アルファブレンディング手段において３次元モデルに対しアルファブレンディング合成による色計算をし、衝突判定手段により衝突を判定された画素においては色選択手段が予め定めた色を優先的に選択するから、３次元モデルを所定の不透明度で透過した状態で確認することができ、衝突している画素部分を所定の色表示から判断することができる。
【００２２】
請求項７に係る衝突検知方法は、前述の請求項５の効果を奏するとともに、識別コードに対して色と不透明度を対応付けたテーブルを有し、並び替え過程により並び替えた順及びテーブル検索過程により決定された色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするから、色と不透明度をテーブルにおいて容易に変更することができ、状況に応じて変更させて用いることができる。
【００２３】
請求項８に係る衝突検知方法は、前述の請求項７の効果を奏するとともに、衝突している画素を占める３次元モデルに与えられる識別コードを出力しているから、画素単位に実時間で衝突検知を行うことができるとともに、衝突しているモデルを知ることができる。
【００２４】
請求項９に係る衝突検知装置は、前述の請求項６の効果を奏するとともに、識別コードに対して色と不透明度を対応付けたテーブルを有し、並び替え手段により並び替えた順及びテーブル検索手段により決定された色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成手段による色計算をするから、色と不透明度をテーブルにおいて容易に変更することができ、状況に応じて変更させて用いることができる。
【００２５】
請求項１０に係る衝突検知装置は、前述の請求項９の効果を奏するとともに、衝突している画素を占める３次元モデルに与えられる識別コードを衝突モデル識別コード出力手段により出力しているから、画素単位に実時間で衝突検知を行うことができるとともに、衝突しているモデルを知ることができる。
【００２６】
請求項１１に係る衝突検知方法は、前述の請求項１又は請求項３又は請求項５又は請求項７又は請求項８のいずれかの効果を奏するとともに、衝突判定過程において画素毎に衝突を判定されたときはインクリメントし、衝突していないときは値を保持して、画像内の衝突している画素数をカウンタによりカウントするから、カウンタが保持する値で３次元モデルが衝突し接触している領域の大きさ及び接触している箇所数を知ることができる。
【００２７】
請求項１２に係る衝突検知装置は、前述の請求項２又は請求項４又は請求項６又は請求項９又は請求項１０のいずれかの効果を奏するとともに、衝突判定手段により画素毎に衝突を判定されたときは、カウンタでインクリメントし、衝突していないときは値を保持して、画像内の衝突している画素数をカウントするから、カウンタが保持する値で３次元モデルが衝突し接触している領域の大きさ及び接触している箇所数を知ることができる。
【実施例１】
【００２８】
図１は、実施例１を説明する構成図、図２は同フロー図である。
図１において、１０１は３次元モデルデータを格納する記憶装置、１０２は操作に従って３次元モデルの位置と姿勢及び仮想の視点の位置、視線方向及び視野角を操作するジョイスティック等からなる入出力手段である。１０３は前記入出力手段１０２と記憶装置１０１に接続して制御する制御装置である。１０４１〜１０４４は、ＣＰＵとメモリと３次元グラフィックスボードで構成するＰＣ（コンピュータ）からなるラスタライザであり、３次元モデルの数に応じて設けられる。各ラスタライザ１０４１〜１０４４は、制御装置１０３とイーサネット（登録商標）などの通信手段で接続され、記憶装置１０１から読み出された３次元モデルデータに基づいて前記入出力手段１０２の操作に応じて仮想の視点から見て変化する３次元モデルの距離画像を生成する。距離画像は、仮想の視点からの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄからなり、３次元グラフィックスボードで計算し、距離画像をディジタルビデオ信号として生成し、同時に出力する。１０５は前記ラスタライザ１０４１〜１０４４からの画素毎の距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄを同時に入力して並べ替える並列ソータ、１０６は演算処理部、１０７は、前記演算処理部１０６に含まれ、前記並列ソータ１０５で並び替えた距離データＤ０，Ｄ１，Ｄ２，Ｄ３の隣り合う２個の距離データの差分を求める差分算出手段、１０８は、前記演算処理部１０６に含まれ、前記差分算出手段１０７により求めた差分が０または所定の範囲の大きさであることにより画素毎に衝突を判定する衝突判定手段である。衝突を判定する前記所定の範囲の大きさである閾値は、前記制御装置１０３により予め設定されている。
【００２９】
以下、図１、図２を参照しつつ、動作を説明する。ジョイスティック等からなる入出力手段１０２を操作することにより、図示しない表示装置に、入出力手段１０２に関連付けられた３次元モデル例えば手術用のメスがその操作量に従って仮定した環境の中、例えば臓器の近傍を移動変化する画像が、表示される。入出力手段１０２の操作により、３次元モデルの位置と姿勢及び仮想の視点の位置、視線方向及び視野角が制御される（図２のＰ１０１）。
それら視点、モデルの位置等のデータ、モデルデータは、モデル毎に各ラスタライザ１０４１〜１０４４のそれぞれに入力される。例えば、モデルＡ、Ｂ、Ｃ、Ｄのそれぞれのデータは、ラスタライザ１０４１，１０４２，１０４３，１０４４のそれぞれに入力され、保持される。各ラスタライザ１０４１〜１０４４は、入出力手段１０２の操作に応じた視点から見た各３次元モデルを構成するポリゴンまでの距離データを画素毎に計算して、距離画像を生成する（図２のＰ１０２）。
例えば、図３に示すように、組織Ａ、組織Ｂ、組織Ｃ、メスＤを仮想視点ｅから見た画像において、仮想視点ｅからメスＤの刃先の点を通る直線を伸ばすとき、組織Ａ、組織Ｂ、組織Ｃとこの直線との交点が存在すれば、仮想視点ｅから各交点までの距離データが算出される。なお、図３において、（ｉ）は仮想視点ｅとメスＤの刃先を結ぶ直線を伸ばし、組織Ａと交わる点、（ｉｉ）は仮想視点ｅとメスＤの刃先を結ぶ直線を伸ばし、組織Ｂと交わる点、及び、（ｉｉｉ）は仮想視点ｅとメスＤの刃先を結ぶ直線を伸ばし、組織Ｃと交わる点である。仮想視点ｅから見た画像内において、前記メスＤの刃先の点と交点群は、同一画素に対応しており、例えばラスタライザ１０４１〜１０４４がＺバッファ法に基づいている場合、仮想視点ｅから前記メスＤの刃先の点及び交点群までの距離データはＺ値（またはデプス値ともいう）として得られる。各ラスタライザ１０４１〜１０４４は、画面の同一座標位置にある距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄ（便宜上各モデルからの距離データを１個として説明する）を順次１画素分毎に出力する。
各ラスタライザ１０４１〜１０４４で生成された同一座標位置からの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄは、同時に並列ソータ１０５に取り入れられ、視点からの距離の順に並び替えられる（図２のＰ１０３）。
例えば、Ｄｃ≦Ｄａ≦Ｄｂ≦Ｄｄである場合、並列ソータ１０５は、小さい順に、Ｄ０（＝Ｄｃ），Ｄ１（＝Ｄａ），Ｄ２（＝Ｄｂ），Ｄ３（＝Ｄｄ）に並び替え、これらを演算処理部１０６に出力する。
演算処理部１０６の差分算出手段１０７は、前記並列ソータ１０５からの距離データＤ０，Ｄ１，Ｄ２，Ｄ３の隣り合う２個の距離データの差分を求める（図２のＰ１０４）。
すなわち、差分出力のそれぞれには、例えば、差分Ｄ３−Ｄ２，Ｄ２−Ｄ１，Ｄ１−Ｄ０が出力される。
衝突判定手段１０８は、差分と予め設定されている閾値とを比較して、差分が０又は閾値内であるときは衝突と判定する（図２のＰ１０５）。
差分を取る距離データＤ０（＝Ｄｃ），Ｄ１（＝Ｄａ），Ｄ２（＝Ｄｂ），Ｄ３（＝Ｄｄ）は、同一座標位置にある同一画素についてのデータであるから、これらの差分が０又は所定の閾値内であるときは、そのモデルの当該画素の点は視点から同一距離にあるもの、すなわち衝突あるいは接触していると判定する。衝突判定手段１０８は、衝突と判定した場合、衝突検知信号を出力する。必要により、衝突と判定された画素のスクリーン座標（Ｘ，Ｙ）を出力する。
入出力手段１０２の操作によりモデルを移動させ、モデル同士が衝突するか、しないかを判定することができる。
【実施例２】
【００３０】
図４は、実施例２を説明する構成図、図５は同フロー図である。実施例２は前述した実施例１のものにおいて、３次元モデルにそれぞれを識別する識別コードを付与した場合の処理に関し、参照符号は特に言及しない場合は図１のものと同様であり、機能動作も同様である。
図４において、４０１はそれぞれを識別する識別コードを付与した３次元モデルデータを格納する記憶装置、４０３は入出力手段４０２と記憶装置４０１に接続して制御する制御装置である。４０４１〜４０４４は、ＣＰＵとメモリと３次元グラフィックスボードで構成するＰＣ（コンピュータ）からなるラスタライザであり、３次元モデルの数に応じて設けられる。各ラスタライザ４０４１〜４０４４は、制御装置４０３とイーサネット（登録商標）などの通信手段で接続され、記憶装置４０１から読み出された３次元モデルデータに基づいて前記入出力手段４０２の操作に応じて仮想の視点から見て変化する３次元モデルの画像を生成する。画像は、仮想の視点からの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄからなり、３次元グラフィックスボードで計算し、距離画像をディジタルビデオ信号として生成し、それぞれの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄを識別コードＩａ，Ｉｂ，Ｉｃ，Ｉｄとともに同時に出力する。４０５は前記ラスタライザ４０４１〜４０４４からの画素毎の距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄと識別コードＩａ，Ｉｂ，Ｉｃ，Ｉｄを同時に入力して距離データの順序に従って識別コードとともに並べ替える並列ソータ、４０９は演算処理部４０６に含まれ、衝突判定手段４０８により衝突を判定されたモデルの識別コードを出力する衝突モデル識別コード出力手段である。
【００３１】
以下、図４、図５を参照しつつ、動作を説明する。各構成部分の動作機能は、実施例１の場合と同様なものがあり、それらを省略する場合があり、実施例２に特徴的なものを説明する。
ジョイスティック等からなる入出力手段４０２を操作することにより、図示しない表示装置に入出力手段４０２に関連付けられた３次元モデル例えば手術用のメスがその操作量に従って仮定した環境の中、例えば臓器の近傍を移動変化する画像が表示される。入出力手段４０２の操作により、３次元モデルの位置と姿勢及び仮想の視点の位置、視線方向及び視野角が制御される（図５のＰ５０１）。
それら視点、モデルの位置等のデータ、及びモデルデータが、モデル毎に各ラスタライザ４０４１〜４０４４のそれぞれに入力される。各ラスタライザ４０４１〜４０４４は、入出力手段４０２の操作に応じた視点から見た各３次元モデルを構成するポリゴンまでの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄを画素毎に計算して、距離画像を生成するとともに、それぞれの距離画像に識別コードＩａ，Ｉｂ，Ｉｃ，Ｉｄを与えて出力する（図５のＰ５０２）。
例えば、図３に示すように、組織Ａ、組織Ｂ、組織Ｃ、メスＤを仮想視点ｅから見た画像において、仮想視点ｅからメスＤの刃先の点を通る直線を伸ばすとき、組織Ａ、組織Ｂ、組織Ｃとこの直線との交点が存在すれば、仮想視点ｅから各交点までの距離データが算出される。なお、図３において、（ｉ）は仮想視点ｅとメスＤの刃先を結ぶ直線を伸ばし、組織Ａと交わる点、（ｉｉ）は仮想視点ｅとメスＤの刃先を結ぶ直線を伸ばし、組織Ｂと交わる点、及び、（ｉｉｉ）は仮想視点ｅとメスＤの刃先を結ぶ直線を伸ばし、組織Ｃと交わる点である。仮想視点ｅから見た画像内において、前記メスＤの刃先の点と交点群は、同一画素に対応しており、例えばラスタライザ４０４１〜４０４４がＺバッファ法に基づいている場合、仮想視点ｅから前記メスＤの刃先の点及び交点群までの距離データはＺ値（またはデプス値ともいう）として得られる。各ラスタライザ４０４１〜４０４４は、画面の同一座標位置にある距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄ（便宜上各モデルからの距離データを１個として説明する）を順次１画素毎に出力するとともに、その距離データが属する３次元モデルの識別コードＩａ，Ｉｂ，Ｉｃ，Ｉｄも出力する。
各ラスタライザ４０４１〜４０４４で生成された同一座標位置からの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄと識別コードＩａ，Ｉｂ，Ｉｃ，Ｉｄは、同時に並列ソータ４０５に取り入れられ、視点からの距離の順に並び替えられ、このとき識別コードＩａ，Ｉｂ，Ｉｃ，Ｉｄも距離データの順序に従って並び替えられる（図５のＰ５０３）。
例えば、距離データについてＤｃ≦Ｄａ≦Ｄｂ≦Ｄｄである場合、並列ソータ４０５は、小さい順に、Ｄ０（＝Ｄｃ），Ｄ１（＝Ｄａ），Ｄ２（＝Ｄｂ），Ｄ３（＝Ｄｄ）に並び替え、これにともなって識別コードもＩ０（＝Ｉｃ），Ｉ１（＝Ｉａ），Ｉ３（＝Ｉｂ），Ｉ４（＝Ｉｄ）に並び替えて、これらを演算処理部４０６に出力する。
演算処理部４０６の差分算出手段４０７は、前記並列ソータ４０５からの距離データＤ０，Ｄ１，Ｄ２，Ｄ３の隣り合う２個の距離データの差分を求める（図５のＰ５０４）。
すなわち、差分出力のそれぞれには、例えば、差分Ｄ３−Ｄ２，Ｄ２−Ｄ１，Ｄ１−Ｄ０が出力される。
衝突判定手段４０８は、差分と予め設定されている閾値とを比較して、差分が０又は閾値内であるときは衝突と判定する（図５のＰ５０５）。
差分を取る距離データＤ０（＝Ｄｃ），Ｄ１（＝Ｄａ），Ｄ２（＝Ｄｂ），Ｄ３（＝Ｄｄ）は、識別コードが同一のものについて対象とせず、それぞれ異なる３次元モデルのデータであり、かつ、同一座標位置にある同一画素についてのデータであるから、これらの差分が０又は所定の閾値内であるときは、そのモデルの当該画素の点は視点から同一距離にあるもの、すなわち衝突あるいは接触していると判定する。衝突判定手段４０８は、衝突と判定した場合、衝突検知信号を出力する。
衝突モデル識別コード出力手段４０９は、前記衝突判定手段４０８が衝突あるいは接触を判定したときの距離データの識別コードを得て、衝突している２以上のモデルの識別コードを出力する（図５のＰ５０６）。
入出力手段４０２の操作によりモデルを移動させ、モデル同士が衝突するか、しないかを判定することができる。衝突した場合は、識別コードによりモデルを特定することができる。
【実施例３】
【００３２】
図６は、実施例３を説明する構成図、図７は同フロー図である。実施例３は前述した実施例１のものにおいて、２個以上の３次元モデル画像データを対象とし、それぞれのモデルにそれぞれの色と不透明度を与えられた（透明度により表現してもよい。）場合の処理に関し、参照符号は特に言及しない場合は図１のものと同様であり、機能動作も同様である。
図６において、６０３は入出力手段６０２と記憶装置６０１に接続して制御するとともに、予め各３次元モデルに対しそれぞれの色と不透明度を指定し、衝突を判定された画素に予め定めた色を指定する制御装置である。６０４１〜６０４４は、ＣＰＵとメモリと３次元グラフィックスボードで構成するＰＣ（コンピュータ）からなるラスタライザであり、３次元モデルの数に応じて設けられる。各ラスタライザ６０４１〜６０４４は、制御装置６０３とイーサネット（登録商標）などの通信手段で接続され、記憶装置６０１から読み出された３次元モデルデータに基づいて前記入出力手段６０２の操作に応じて仮想の視点から見て変化する３次元モデルの画像を生成する。画像は、仮想の視点からの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄからなり、制御装置６０３で指定された色と不透明度を備えており、３次元グラフィックスボードで計算し、距離画像をディジタルビデオ信号として生成し、それぞれの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄを色と不透明度のデータとともに同時に出力する。６０５は前記ラスタライザ６０４１〜６０４４からの画素毎の距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄと色と不透明度のデータを同時に入力して距離データの順序に並べ替える並列ソータ、６１０は、演算処理部６０６に含まれ、前記並列ソータ６０５により並び替えた距離データの順及び色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするアルファブレンディング手段、６１１は、衝突判定手段６０８により衝突を判定された画素に対して予め定めた色を優先的に選択する色選択手段である。以上により決定した画素の色が可視化画像として出力される。
【００３３】
以下、図６、図７を参照しつつ、動作を説明する。各構成部分の動作機能は、実施例１の場合と同様なものがあり、それらを省略する場合があり、実施例３に特徴的なものを説明する。
ジョイスティック等からなる入出力手段６０２を操作することにより、３次元モデルの位置と姿勢及び仮想の視点の位置、視線方向及び視野角が制御される（図７のＰ７０１）。
それら視点、モデルの位置等のデータ、モデルデータが、モデル毎に各ラスタライザ６０４１〜６０４４のそれぞれに入力する。各ラスタライザ６０４１〜６０４４は、入出力手段６０２の操作に応じた視点から見た各３次元モデル表示及びこれらを構成するポリゴンまでの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄを画素毎に計算して、距離画像を生成して出力する（図７のＰ７０２）。
例えば、図３に示すように、組織Ａ、組織Ｂ、組織Ｃ、メスＤを仮想視点ｅから見た画像において、仮想視点ｅからメスＤの刃先の点を通る直線を伸ばすとき、組織Ａ、組織Ｂ、組織Ｃとこの直線との交点が存在すれば、仮想視点ｅから各交点までの距離データが算出される。なお、図３において、（ｉ）は仮想視点とメスＤの刃先を結ぶ直線を伸ばし、組織Ａと交わる点、（ｉｉ）は仮想視点とメスＤの刃先を結ぶ直線を伸ばし、組織Ｂと交わる点、及び、（ｉｉｉ）は仮想視点とメスＤの刃先を結ぶ直線を伸ばし、組織Ｃと交わる点である。仮想視点ｅから見た画像内において、前記メスＤの刃先の点と交点群は、同一画素に対応しており、例えばラスタライザ６０４１〜６０４４がＺバッファ法に基づいている場合、仮想視点ｅから前記メスＤの刃先の点及び交点群までの距離データはＺ値（またはデプス値ともいう）として得られる。各ラスタライザ６０４１〜６０４４は、画面の同一座標位置にある距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄ（便宜上各モデルからの距離データを１個として説明する）を順次１画素毎に出力するとともに、その距離データが属する３次元モデルの色Ｃａ，Ｃｂ，Ｃｃ，Ｃｄと不透明度Ｏａ，Ｏｂ，Ｏｃ，Ｏｄのデータも出力する。
各ラスタライザ６０４１〜６０４４で生成された同一座標位置からの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄと色Ｃａ，Ｃｂ，Ｃｃ，Ｃｄと不透明度Ｏａ，Ｏｂ，Ｏｃ，Ｏｄのデータは、同時に並列ソータ６０５に取り入れられ、視点からの距離の順に並び替えられ、このとき色と不透明度のデータも距離データの順序に従って並び替えられる（図７のＰ７０３）。
例えば、距離データについてＤｃ≦Ｄａ≦Ｄｂ≦Ｄｄである場合、並列ソータ６０５は、小さい順に、Ｄ０（＝Ｄｃ），Ｄ１（＝Ｄａ），Ｄ２（＝Ｄｂ），Ｄ３（＝Ｄｄ）に並び替えて演算処理部６０６に出力する。
演算処理部６０６の差分算出手段６０７は、前記並列ソータ６０５からの距離データＤ０，Ｄ１，Ｄ２，Ｄ３の隣り合う２個の距離データの差分を求める（図７のＰ７０４）。
すなわち、差分出力のそれぞれには、例えば、差分Ｄ３−Ｄ２，Ｄ２−Ｄ１，Ｄ１−Ｄ０が出力される。
衝突判定手段６０８は、差分と予め設定されている閾値とを比較して、差分が０又は閾値内であるときは衝突と判定する（図７のＰ７０５）。
差分を取る距離データＤ０（＝Ｄｃ），Ｄ１（＝Ｄａ），Ｄ２（＝Ｄｂ），Ｄ３（＝Ｄｄ）は、同一座標位置にある同一画素についてのデータであるから、これらの差分が０又は所定の閾値内であるときは、そのモデルの当該画素の点は視点から同一距離にあるもの、すなわち衝突あるいは接触していると判定する。衝突判定手段６０８は、衝突と判定した場合、衝突検知信号を出力する。
アルファブレンディング手段６１０は前記並列ソータ６０５により並び替えた距離データＤ０，Ｄ１，Ｄ２，Ｄ３の順及び色Ｃ０，Ｃ１，Ｃ２，Ｃ３と不透明度Ｏ０，Ｏ１，Ｏ２，Ｏ３のデータに基づいて３次元モデルに対しアルファブレンディング合成による色計算をする（図７のＰ７０６）。
色選択手段６１１は、衝突を判定された画素に対し制御装置６０３から優先的に指定する色を予め指定されており、衝突判定手段６０８から衝突を判定されたとき、前記アルファブレンディング手段６１０の出力ではなく、衝突した当該画素に前記指定された色を選択する（図７のＰ７０７）。
図８にアルファブレンディング合成と衝突している部分を指定色で表示する例を示す。
図８（ａ）は、アルファブレンディング合成をせず、図３の組織ＡとメスＤのみが表示されている。
図８（ｂ）は、アルファブレンディング合成により、組織Ａを透過して組織Ｂが、また組織Ａと組織Ｂを透過して組織Ｃが表示されている。また、メスＤの刃と組織Ａの接触している部分が指定色により強調表示されている。図８（ｂ）では、指定色の強調は太線で表している。
【実施例４】
【００３４】
図９は、実施例４を説明する構成図、図１０は同フロー図である。実施例４は前述した実施例２のものにおいて、２個以上の３次元モデル画像データを対象とし、３次元モデルにそれぞれを識別する識別コードを付与し、それぞれのモデルにそれぞれの色と不透明度を与えられた場合の処理に関し、参照符号は特に言及しない場合は図１、図４のものと同様であり、機能動作も同様である。
図９において、９０３は入出力手段９０２と記憶装置９０１に接続して制御するとともに、衝突を判定された画素に予め定めた色と不透明度を指定する制御装置である。９０４１〜９０４４は、ＣＰＵとメモリと３次元グラフィックスボードで構成するＰＣ（コンピュータ）からなるラスタライザであり、３次元モデルの数に応じて設けられる。各ラスタライザ９０４１〜９０４４は、制御装置９０３とイーサネット（登録商標）などの通信手段で接続され、記憶装置９０１から読み出された３次元モデルデータに基づいて前記入出力手段９０２の操作に応じて仮想の視点から見て変化する３次元モデルの画像を生成する。画像は、仮想の視点からの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄからなり、３次元グラフィックスボードで計算し、距離画像をディジタルビデオ信号として生成し、それぞれの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄを識別コードＩａ，Ｉｂ，Ｉｃ，Ｉｄとともに同時に出力する。９０５は前記ラスタライザ９０４１〜９０４４からの画素毎の距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄを同時に入力して距離データの順序に並べ替える並列ソータ、９１０は前記並列ソータ９０５により並び替えた距離データの順及び後述するルックアップテーブル９１２に指定される色と不透明度に基づいて３次元モデルに対しアルファブレンディング合成による色計算をするアルファブレンディング手段、９１１は、衝突判定手段９０８により衝突を判定された画素に対して予め定めた色を優先的に選択する色選択手段、９１２は、各３次元モデルに対し予め与えられた識別コードに対応付けられた色と不透明度を有するルックアップテーブル、９１３は、前記ルックアップテーブル９１２から前記並列ソータ９０５において並び替えた識別コードに対応する色と不透明度を読み出すテーブル検索手段である。
【００３５】
必要により、衝突モデル識別コード出力手段９０９を設ける。
【００３６】
以下、図９、図１０を参照しつつ、動作を説明する。各構成部分の動作機能は、実施例２の場合と同様なものがあり、それらを省略する場合があり、実施例４に特徴的なものを説明する。
ジョイスティックからなる入出力手段９０２を操作することにより、３次元モデルの位置と姿勢及び仮想の視点の位置と視線方向が制御される（図１０のＰ１００１）。
それら視点、モデルの位置等のデータ、モデルデータが、モデル毎に各ラスタライザ９０４１〜９０４４のそれぞれに入力する。各ラスタライザ９０４１〜９０４４は、入出力手段９０２の操作に応じた視点から見た各３次元モデル表示及びこれらを構成するポリゴンまでの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄを画素毎に計算して、距離画像を生成するとともに、それぞれの距離画像に識別コードＩａ，Ｉｂ，Ｉｃ，Ｉｄを与えて出力する（図１０のＰ１００２）。
例えば、図３に示すように、組織Ａ、組織Ｂ、組織Ｃ、メスＤを仮想視点ｅから見た画像において、仮想視点ｅからメスＤの刃先の点を通る直線を伸ばすとき、組織Ａ、組織Ｂ、組織Ｃとこの直線との交点が存在すれば、仮想視点ｅから各交点までの距離データが算出される。なお、図３において、（ｉ）は仮想視点ｅとメスＤの刃先を結ぶ直線を伸ばし、組織Ａと交わる点、（ｉｉ）は仮想視点ｅとメスＤの刃先を結ぶ直線を伸ばし、組織Ｂと交わる点、及び、（ｉｉｉ）は仮想視点ｅとメスＤの刃先を結ぶ直線を伸ばし、組織Ｃと交わる点である。仮想視点ｅから見た画像内において、前記メスＤの刃先の点と交点群は、同一画素に対応しており、例えばラスタライザ９０４１〜９０４４がＺバッファ法に基づいている場合、仮想視点ｅから前記メスＤの刃先の点及び交点群までの距離データはＺ値（またはデプス値ともいう）として得られる。各ラスタライザ９０４１〜９０４４は、画面の同一座標位置にある距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄ（便宜上各モデルからの距離データを１個として説明する）を順次１画素毎に出力するとともに、その距離データが属する３次元モデルの識別コードＩａ，Ｉｂ，Ｉｃ，Ｉｄも出力する。
各ラスタライザ９０４１〜９０４４で生成された同一座標位置からの距離データＤａ，Ｄｂ，Ｄｃ，Ｄｄと識別コードＩａ，Ｉｂ，Ｉｃ，Ｉｄは、同時に並列ソータ９０５に取り入れられ、視点からの距離の順に並び替えられ、このとき識別コードも距離データの順序に従って並び替えられる（図１０のＰ１００３）。
例えば、距離データについてＤｃ≦Ｄａ≦Ｄｂ≦Ｄｄである場合、並列ソータ９０５は、小さい順に、Ｄ０（＝Ｄｃ），Ｄ１（＝Ｄａ），Ｄ２（＝Ｄｂ），Ｄ３（＝Ｄｄ）に並び替え、これにともなって識別コードもＩ０（＝Ｉｃ），Ｉ１（＝Ｉａ），Ｉ３（＝Ｉｂ），Ｉ４（＝Ｉｄ）に並び替えて、これらを演算処理部９０６に出力する。
演算処理部９０６の差分算出手段９０７は、前記並列ソータ９０５からの距離データＤ０，Ｄ１，Ｄ２，Ｄ３の隣り合う２個の距離データの差分を求める（図１０のＰ１００４）。
すなわち、差分出力のそれぞれには、例えば、差分Ｄ３−Ｄ２，Ｄ２−Ｄ１，Ｄ１−Ｄ０が出力される。
衝突判定手段９０８は、差分と予め設定されている閾値とを比較して、差分が０又は閾値内であるときは衝突と判定する（図１０のＰ１００５）。
差分を取る距離データＤ０（＝Ｄｃ），Ｄ１（＝Ｄａ），Ｄ２（＝Ｄｂ），Ｄ３（＝Ｄｄ）は、識別コードが同一のものについて対象とせず、それぞれ異なる３次元モデルのデータであり、かつ、同一座標位置にある同一画素についてのデータであるから、これらの差分が０又は所定の閾値内であるときは、そのモデルの当該画素の点は視点から同一距離にあるもの、すなわち衝突あるいは接触していると判定する。衝突判定手段９０８は、衝突と判定した場合、衝突検知信号を出力する。
テーブル検索手段９１３は、前記ルックアップテーブル９１２から識別コードに対応する色と不透明度を読み出しておく（図１０のＰ１００６）。
ルックアップテーブル９１２の色と不透明度は、制御装置９０３から予め指定されている。
アルファブレンディング手段９１０は前記並列ソータ９０５により並び替えた距離データＤ０，Ｄ１，Ｄ２，Ｄ３の順及び前記テーブル検索手段９１３がルックアップテーブル９１２から識別コードに対応して読み出した色と不透明度のデータに基づいて３次元モデルに対しアルファブレンディング合成による色計算をする（図１０のＰ１００７）。
色選択手段９１１は、衝突を判定された画素に対し制御装置９０３から優先的に指定する色を予め指定されており、衝突判定手段９０８から衝突を判定されたとき、前記アルファブレンディング手段９１０の出力ではなく、衝突した当該画素に前記指定された色を選択する（図１０のＰ１００８）。
図８にアルファブレンディング合成と衝突している部分を指定色で表示する例を示す。
図８（ａ）は、アルファブレンディング合成をせず、図３の組織ＡとメスＤのみが表示されている。
図８（ｂ）は、アルファブレンディング合成により、組織Ａを透過して組織Ｂが、また組織Ａと組織Ｂを透過して組織Ｃが表示されている。また、メスＤの刃と組織Ａの接触している部分が指定色により強調表示されている。図８（ｂ）では、指定色の強調は太線で表している。
入出力手段９０２の操作によりモデルを移動させ、モデル同士が衝突するか、しないかを判定することができる。衝突した場合は、識別コードによりモデルを特定することができる。
【００３７】
衝突モデル識別コード出力手段９０９は、前記衝突判定手段９０８が衝突あるいは接触を判定したときの距離データの識別コードを得て、衝突している２以上のモデルの識別コードを出力する（図１０のＰ１００９）。
【実施例５】
【００３８】
図１１は、実施例５を説明する構成図、図１２は同フロー図である。実施例５は前述した実施例１〜実施例４のものにおいて、衝突画素数をカウントする手段及びカウント値を出力する手段を付加するものである。
図１１は、図１、図４、図６及び図９に用いる演算処理部１０６，４０６，６０６，９０６の部分を示し、他の構成部分を省略したものであり、図１２は、図２のＰ１０５、図５のＰ５０５、図７のＰ７０５、図１０のＰ１００５とそれぞれにおける各過程の後方との間に位置する過程である。図１１において、１１１３は、前記演算処理部１０６，４０６，６０６，９０６に含まれるカウンタである。
カウンタ１１１３は、画面ごとの処理の開始時にクリアし、衝突判定手段１０８（４０８，６０８，９０８）により画素毎に衝突を判定されたときはインクリメントし、衝突していないときは値を保持して、画像内の衝突している画素数をカウントする（図１２のＰ１２０１）。
画面ごとの処理の終了時にカウント値を出力する（図１２のＰ１２０２）。
衝突箇所が複数、あるいは例えば、メスが臓器内部まで入り臓器表面とメスとが連続して接触している場合にも、複数画素について衝突が発生していて、これをカウントして、接触箇所の数あるいは接触範囲の大きさを知ることができる。
【産業上の利用可能性】
【００３９】
上記説明では、主に手術シミュレータにおけるメスと臓器の当たり（衝突）判定について説明したが、本発明はこれに限らず、３次元ＣＡＤにおけるモデル間の干渉を検出するためのシミュレーション、フライトシミュレータにおける自機と地形との距離計算などに、利用することができる。
また、ポリゴンで表現した３次元モデルに加えて、ステレオ写真測量やＸ線コンピュータトモグラフィ等の手法により計測された３次元画像データやボリュームデータを本発明の３次元モデルとして扱うことができ、本発明を利用することができる。
【図面の簡単な説明】
【００４０】
【図１】衝突検知装置の構成図である。（実施例１）
【図２】衝突検知の方法を説明するフロー図である。（実施例１）
【図３】最終画像及びモデルを説明する図である。
【図４】衝突検知装置の構成図である。（実施例２）
【図５】衝突検知の方法を説明するフロー図である。（実施例２）
【図６】衝突検知装置の構成図である。（実施例３）
【図７】衝突検知の方法を説明するフロー図である。（実施例３）
【図８】アルファブレンディング合成した画像の例を示す。
【図９】衝突検知装置の構成図である。（実施例４）
【図１０】衝突検知の方法を説明するフロー図である。（実施例４）
【図１１】衝突検知装置の部分構成図である。（実施例５）
【図１２】衝突検知の方法を説明するフロー図の一部分である。（実施例５）
【符号の説明】
【００４１】
１０１，４０１，６０１，９０１…記憶装置、１０２，４０２，６０２，９０２…入出力手段、１０３，４０３，６０３，９０３…制御装置、１０４１〜１０４４，４０４１〜４０４４，６０４１〜６０４４，９０４１〜９０４４…ラスタライザ、１０５，４０５，６０５，９０５…並列ソータ、１０６，４０６，６０６，９０６…演算処理部、１０７，４０７，６０７，９０７…差分算出手段、１０８，４０８，６０８，９０８…衝突判定手段、４０９，９０９…衝突モデル識別コード出力手段、６１０，９１０…アルファブレンディング手段、６１１，９１１…色選択手段、９１２…ルックアップテーブル、９１３…テーブル検索手段、１１１３…カウンタ。
【図１】
2005327125.tif 000003
【図２】
2005327125.tif 000004
【図３】
2005327125.tif 000005
【図４】
2005327125.tif 000006
【図５】
2005327125.tif 000007
【図６】
2005327125.tif 000008
【図７】
2005327125.tif 000009
【図８】
2005327125.tif 000010
【図９】
2005327125.tif 000011
【図１０】
2005327125.tif 000012
【図１１】
2005327125.tif 000013
【図１２】
2005327125.tif 000014