(57)【要約】【課題】  操作対象としての仮想物体と、その他の仮想物体との干渉判定処理をより高速に行う為の技術を提供すること。【解決手段】  記録モードが設定されている間は、操作対象仮想物体に対する操作履歴をメモリに記録する（Ｓ３０１，Ｓ３０２）。記録モードが解除された後、操作対象仮想物体と同じ仮想空間中に存在する複数の仮想要素のうち、操作対象仮想物体との干渉判定の対象とする仮想要素を、操作履歴に基づいて選択する（Ｓ３０３）。選択した１以上の仮想要素のそれぞれと、操作対象仮想物体との干渉判定処理を行う（Ｓ３０４）。干渉判定結果を出力する（Ｓ３０５）。【選択図】  図３
2008059375.tif 000002
【特許請求の範囲】
【請求項１】
記録モードが設定されているときに、操作対象仮想物体に対する操作履歴をメモリに記録する記録工程と、
前記操作対象仮想物体と同じ仮想空間中に存在する複数の仮想要素のうち、前記操作対象仮想物体との干渉判定の対象とする仮想要素を、前記記録工程で記録した操作履歴に基づいて選択する選択工程と、
前記選択工程で選択した１以上の仮想要素のそれぞれと、前記操作対象仮想物体との干渉判定処理を行う干渉判定工程と、
前記干渉判定工程による結果を出力する出力工程と
を備えることを特徴とする情報処理方法。
【請求項２】
前記記録モードの設定は、ユーザ指示によって行われることを特徴とする請求項１に記載の情報処理方法。
【請求項３】
前記操作履歴は前記操作対象仮想物体の移動軌跡であり、
前記選択工程では、前記移動軌跡の近傍に存在する仮想要素を干渉判定の対象として選択することを特徴とする請求項１に記載の情報処理方法。
【請求項４】
前記記録工程では、記録開始時から記録終了時までの間で予め決められた時間間隔毎に前記操作対象仮想物体の位置を前記メモリに記録することを特徴とする請求項１に記載の情報処理方法。
【請求項５】
前記記録工程では、記録開始時から記録終了時までの間で予め決められた距離間隔毎に前記操作対象仮想物体の位置を前記メモリに記録することを特徴とする請求項１に記載の情報処理方法。
【請求項６】
前記選択工程では、前記記録工程で記録された各位置の近傍に位置する仮想要素を、前記操作対象仮想物体との干渉判定の対象として選択することを特徴とする請求項４又は５に記載の情報処理方法。
【請求項７】
前記仮想要素は、前記操作対象仮想物体以外の仮想物体、若しくは当該仮想物体を構成する構成単位であることを特徴とする請求項１に記載の情報処理方法。
【請求項８】
前記仮想物体がポリゴンでもって構成されている場合、前記構成単位はポリゴンであることを特徴とする請求項７に記載の情報処理方法。
【請求項９】
更に、前記操作対象仮想物体、及び前記操作対象仮想物体以外の仮想要素を表示装置に表示させる表示制御工程を備え、
前記表示制御工程では、前記選択工程で選択された構成要素と選択されていない構成要素とを異なる表示方法でもって表示することを特徴とする請求項１に記載の情報処理方法。
【請求項１０】
更に、
前記記録モードが設定されている間は、前記干渉判定工程が行う干渉判定処理よりも簡便な方法でもって、前記操作対象仮想物体と前記複数の仮想要素との干渉判定処理を行う第２の干渉判定工程と、
前記第２の干渉判定工程による結果を出力する第２の出力工程と
を備えることを特徴とする請求項１に記載の情報処理方法。
【請求項１１】
記録モードが設定されているときに、操作対象仮想物体に対する操作履歴をメモリに記録する記録手段と、
前記操作対象仮想物体と同じ仮想空間中に存在する複数の仮想要素のうち、前記操作対象仮想物体との干渉判定の対象とする仮想要素を、前記記録手段が記録した操作履歴に基づいて選択する選択手段と、
前記選択手段が選択した１以上の仮想要素のそれぞれと、前記操作対象仮想物体との干渉判定処理を行う干渉判定手段と、
前記干渉判定手段による結果を出力する出力手段と
を備えることを特徴とする情報処理装置。
【請求項１２】
コンピュータに請求項１乃至１０の何れか１項に記載の情報処理方法を実行させるためのプログラム。
【請求項１３】
請求項１２に記載のプログラムを格納したことを特徴とする、コンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、干渉判定技術に関し、特に、仮想物体同士の干渉判定技術に関するものである。
【背景技術】
【０００２】
従来より、コンピュータ内の仮想３次元空間において機械装置の組立／分解などの作業シミュレーションを行う技術があり、係る技術では、物体同士の接触を検知するために仮想物体の干渉判定を用いていた（特許文献１を参照）。
【０００３】
また、干渉判定処理の順序を変更して、過去に干渉したことがある物体の組をより先に処理することで、処理の高速化を図る技術があった（特許文献２を参照）。
【特許文献１】特開平９−３１１８８３号公報
【特許文献２】特公平８−５０２８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
干渉判定処理は形状要素の各組み合わせについて干渉の有無を判定するため、一般的に干渉判定処理の対象となるデータ量の増加に対してｎ！のオーダーで処理時間が増加する。
【０００５】
特に、仮想物体に対して移動・回転などの操作をインタラクティブに行いながら作業シミュレーションを行う場合、干渉判定処理の時間増大は深刻な問題となる。なぜなら、干渉判定処理に大きく時間がかかってしまうと、作業者の操作する物体がこの操作に直ちに反応しなくなり、物体の挙動が現実世界と大きくかけ離れ、現実世界をシミュレートするという目的自体を果たせなくなるからである。
【０００６】
また、干渉判定を行うためには、仮想世界のＣＧ描画のためのデータとは別の構造のデータをメモリ上に展開しなければならないという場合がある。従って、干渉判定の対象となるデータが増加すると、メモリ使用量が著しく増大する。
【０００７】
例えば、上記特許文献２では、形状要素の組み合わせの順番を変更することによって干渉判定処理を高速化する技術を開示しているが、順番の変更が完了するまでは干渉判定処理に時間がかかるという問題がある。また係る技術では、処理の順序を変更するのみであって、データの量は減少していないので、メモリ空間を圧迫するという問題は解決していない。
【０００８】
本発明は以上の問題に鑑みてなされたものであり、操作対象としての仮想物体と、その他の仮想物体との干渉判定処理をより高速に行う為の技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の目的を達成するために、例えば、本発明の情報処理方法は以下の構成を備える。
【００１０】
即ち、記録モードが設定されているときに、操作対象仮想物体に対する操作履歴をメモリに記録する記録工程と、
前記操作対象仮想物体と同じ仮想空間中に存在する複数の仮想要素のうち、前記操作対象仮想物体との干渉判定の対象とする仮想要素を、前記記録工程で記録した操作履歴に基づいて選択する選択工程と、
前記選択工程で選択した１以上の仮想要素のそれぞれと、前記操作対象仮想物体との干渉判定処理を行う干渉判定工程と、
前記干渉判定工程による結果を出力する出力工程と
を備えることを特徴とする。
【００１１】
本発明の目的を達成するために、例えば、本発明の情報処理装置は以下の構成を備える。
【００１２】
即ち、記録モードが設定されているときに、操作対象仮想物体に対する操作履歴をメモリに記録する記録手段と、
前記操作対象仮想物体と同じ仮想空間中に存在する複数の仮想要素のうち、前記操作対象仮想物体との干渉判定の対象とする仮想要素を、前記記録手段が記録した操作履歴に基づいて選択する選択手段と、
前記選択手段が選択した１以上の仮想要素のそれぞれと、前記操作対象仮想物体との干渉判定処理を行う干渉判定手段と、
前記干渉判定手段による結果を出力する出力手段と
を備えることを特徴とする。
【発明の効果】
【００１３】
本発明の構成によれば、操作対象としての仮想物体と、その他の仮想物体との干渉判定処理をより高速に行うことができる。
【発明を実施するための最良の形態】
【００１４】
以下添付図面を参照して、本発明をその好適な実施形態に従って詳細に説明する。
【００１５】
［第１の実施形態］
本実施形態では、例えば機械装置に部品を取り付ける作業を仮想空間内でシミュレートする。取り付ける部品に相当する仮想物体（操作対象仮想物体）は、３次元現実世界中で自身の位置姿勢が計測可能なセンサと固定の相対位置姿勢を保って動く。従って作業者はこのセンサを移動・回転させることによって、操作対象仮想物体を移動・回転させる作業を模擬することが出来る。
【００１６】
次に、本実施形態の概要について説明する。
【００１７】
図１は、操作対象仮想物体を含む複数の部品の仮想物体が配置された仮想空間の断面図である。同図において１０１は操作対象仮想物体であり、その周囲には機械部品を模した仮想物体１０２，１０４，１０５，１０７，１０９が配置されている。また、その更に外周には、機械部品を模した仮想物体１０３，１０６，１０８，１１０が配置されている。
【００１８】
係る配置状態の場合、例えば操作対象仮想物体１０１を仮想物体１０３に取り付けようとすべく移動させると、操作対象仮想物体１０１は仮想物体１０４と干渉（接触）してしまう可能性がある。また、操作対象仮想物体１０１を仮想物体１０６に取り付けようとすべく移動させると、操作対象仮想物体１０１は仮想物体１０５と干渉（接触）してしまう可能性がある。また、操作対象仮想物体１０１を仮想物体１０８に取り付けようとすべく移動させると、操作対象仮想物体１０１は仮想物体１０７と干渉（接触）してしまう可能性がある。また、操作対象仮想物体１０１を仮想物体１１０に取り付けようとすべく移動させると、操作対象仮想物体１０１は仮想物体１０２や仮想物体１０９と干渉（接触）してしまう可能性がある。
【００１９】
従って、操作対象仮想物体１０１を仮想物体１０３，１０６，１０８，１１０の何れかに取り付けようとすべく移動させる際に、操作対象仮想物体１０１との干渉判定の対象となる仮想物体は、仮想物体群１０２，１０４，１０５，１０７，１０９となる。
【００２０】
このように、仮想空間中に配置されている全ての仮想物体を干渉判定の対象とするのではなく、その一部を対象とすると、仮想空間を体感させるための処理全体をより高速に行うことができる。
【００２１】
本実施形態では、仮想空間中に存在する全ての仮想物体のうち操作対象仮想物体１０１との干渉判定の対象となる仮想物体を、操作対象仮想物体１０１とその他の仮想物体との配置関係に基づいて選択する。これにより、操作対象仮想物体１０１との干渉判定の対象としての仮想物体の数を削減する。
【００２２】
以下の説明では、操作対象仮想物体以外の仮想物体は静止しているものとして説明する。ここでの「静止」とは、仮想空間における位置、姿勢、サイズが変更されないという意味である。
【００２３】
図２は、本実施形態に係るシステムのハードウェア構成を示すブロック図である。同図に示す如く、本実施形態に係るシステムは、コンピュータ２００と位置姿勢センサ２１０とで構成されている。
【００２４】
先ず、位置姿勢センサ２１０について説明する。位置姿勢センサ２１０は、自身の位置姿勢を計測するものであり、計測した結果はデータとしてコンピュータ２００に送出される。位置姿勢センサ２１０としては磁気センサや光学式センサ、超音波センサなどを用いることができ、例えばPolhemus社のFastrakを用いることができる。しかし、これに限るものではなく６自由度が計測可能な任意のセンサを用いることが可能である。
【００２５】
ユーザは、この位置姿勢センサ２１０を手に持ち、その位置姿勢を自在に変化させることができる。この位置姿勢センサ２１０の位置姿勢は後述するように、操作対象仮想物体の位置姿勢に反映される。即ちユーザは、この位置姿勢センサ２１０を用いて、操作対象仮想物体の位置姿勢を自在に制御することができる。
【００２６】
次に、コンピュータ２００について説明する。
【００２７】
ＣＰＵ２０１は、メモリ２０２に格納されているプログラムやデータを用いてコンピュータ２００全体の制御を行うと共に、コンピュータ２００が行うものとして説明する後述の各処理を実行する。
【００２８】
メモリ２０２は、外部記憶装置２０５からロードされたプログラムやデータ、位置姿勢センサ２１０から取得した位置姿勢データ等を一時的に記憶する為のエリアを有する。更にメモリ２０２は、ＣＰＵ２０１が各種の処理を実行する際に用いるワークエリアも有する。このようにメモリ２０２は、各種のエリアを適宜提供することができる。２０３はバスである。
【００２９】
外部記憶装置２０５には、ＯＳ（オペレーティングシステム）や、コンピュータ２００が行うものとして説明する後述の各処理をＣＰＵ２０１に実行させるためのプログラムやデータが保存されている。外部記憶装置２０５に保存されている各種の情報はＣＰＵ２０１による制御に従って適宜メモリ２０２にロードされ、ＣＰＵ２０１による処理対象となる。
【００３０】
キーボード２０６，マウス２０７はそれぞれＣＰＵ２０１に対して各種の指示を入力するためのポインティングデバイスの一例であり、これ以外のものを用いることもできる。
【００３１】
表示部２０８は、ＣＲＴや液晶画面などにより構成されており、ＣＰＵ２０１による処理結果を画像や文字などでもって表示することができる。
【００３２】
Ｉ／Ｏ２０９は、位置姿勢センサ２１０をコンピュータ２００に接続するためのものであり、位置姿勢センサ２１０からの位置姿勢データはこのＩ／Ｏ２０９を介してメモリ２０２や外部記憶装置２０５に送出される。
【００３３】
インターフェース２０４には、上記外部記憶装置２０５、キーボード２０６、マウス２０７、表示部２０８、Ｉ／Ｏ２０９が接続されていると共に、上記バス２０３もこのインターフェース２０４に接続されている。
【００３４】
次に、操作対象仮想物体を仮想空間内で移動させる場合に、この操作対象仮想物体との干渉判定対象としての仮想物体を特定する為の処理について、同処理のフローチャートを示す図３を用いて説明する。なお、同図のフローチャートに従った処理をＣＰＵ２０１に実行させるためのプログラムやデータは外部記憶装置２０５に保存されている。このプログラムやデータは、ＣＰＵ２０１による制御に従って適宜メモリ２０２にロードされる。そしてＣＰＵ２０１はこのロードされたプログラムやデータを用いて処理を実行することで、コンピュータ２００は以下説明する各ステップにおける処理を実行することになる。
【００３５】
先ずステップＳ３００では、操作対象仮想物体やその他の仮想物体に係るデータを、外部記憶装置２０５からメモリ２０２にロードする。
【００３６】
図４は、各仮想物体に係るデータの構成例を示す図である。１つの形状モデルは形状要素として少なくとも１つの「部品」から構成され、モデルデータは各部品のデータを並べた形式で記述される。本実施形態では、操作対象仮想物体、操作対象仮想物体以外の仮想物体は、この１つの部品を模した仮想物体のことである。
【００３７】
例えば、形状モデルがｎ個の部品を持っているとすると、図４では、１番目の部品のデータが領域４０１、２番目の部品のデータが領域４０６、３番目から（ｎ−１）番目の部品のデータが領域４０７、ｎ番目の部品のデータが領域４０８に登録される。即ち、各部品の仮想物体のデータが、対応する領域内に登録されていることになる。
【００３８】
領域４０１を例に取り、１番目の部品に対応する仮想物体（仮想物体１）に係るデータについて説明する。
【００３９】
領域４０２には、仮想物体１に係るデータの開始位置を示す開始デリミタが格納されている。同様に領域４０５には、仮想物体１に係るデータの終了位置を示す終了デリミタが格納されている。領域４０３には、仮想物体１に固有の識別情報（部品ＩＤ）が格納されている。なお、識別情報としてはこれ以外にも考えられ、例えば、部品ごとに異なる整数値、あるいは部品ごとに異なる部品名称を表す文字列を、この識別情報として用いても良い。領域４０４には、仮想物体１の幾何的形状情報が格納されている。例えば、仮想物体１がポリゴンでもって構成されている場合、領域４０４には、ポリゴンを構成する各頂点の位置データ、ポリゴンのカラーデータ、ポリゴンの法線データ、そして、テクスチャマッピングを行う場合には、テクスチャデータ等が格納されている。更に、領域４０４には、仮想物体１の仮想空間中における配置位置姿勢も格納されている。
【００４０】
このように、各領域内には、各仮想物体について、仮想物体に係るデータが格納されている。
【００４１】
なお、図３に示したフローチャートに従った処理と並行して行われる描画処理では、この幾何的形状情報を用いて各仮想物体の画像を生成し、表示部２０８の表示画面上に表示する。各仮想物体の画像の生成は、各仮想物体を対応する幾何的形状情報（配置位置姿勢）に従って仮想空間中に配置し、設定された視点から係る仮想空間を見た場合の画像を生成することによりなされるものである。この視点の位置や姿勢は、キーボード２０６やマウス２０７を用いて指示する。
【００４２】
なお、視点の位置姿勢の指示についてはこれに限定するものではない。例えば、表示部２０８が周知のＨＭＤ（ヘッドマウントディスプレイ）に搭載されているものである場合には、このＨＭＤを装着したユーザの目の位置近傍に取り付けられた位置姿勢センサにより計測された位置姿勢を、視点の位置姿勢として用いても良い。
【００４３】
なお、設定された視点から見える仮想空間の画像を生成するための技術については周知のものであるので、これ以上の詳細な説明は省略する。
【００４４】
図３に戻って、各仮想物体の画像を表示した後、先ずユーザはキーボード２０６やマウス２０７を用いて、記録モードを設定する指示を入力するので、ステップＳ３０１では先ず、この入力された指示に従って、記録モードを設定する。また、ＣＰＵ２０１は、記録モードの設定と共に後述の「記録時刻」を「０」に初期化した後、記録時刻の計時処理を開始する。
【００４５】
記録モードの設定後、ユーザは位置姿勢センサ２１０を手に持ち、表示部２０８の表示画面上に表示されている仮想空間を見ながら、操作対象仮想物体を所望の位置に移動させるべく、位置姿勢センサ２１０を移動させる。上述の通り、位置姿勢センサ２１０により計測された自身の位置姿勢を示す位置姿勢データはＩ／Ｏ２０９を介してメモリ２０２に送出され、ＣＰＵ２０１はこの位置姿勢データに基づいた位置姿勢でもって操作対象仮想物体を配置する。ステップＳ３０１では、計時処理開始後所定時間（Δｔ）毎に、操作対象仮想物体の重心の位置姿勢を操作履歴としてメモリ２０２上に記録する処理を行う。
【００４６】
ここで、操作対象仮想物体の配置位置と操作対象仮想物体の重心位置との位置関係は固定であるので、係る位置関係は予め測定しておき、オフセットとして外部記憶装置２０５に登録しておく。従ってステップＳ３０１では、位置姿勢センサ２１０から得られた位置姿勢データに基づいた位置姿勢にこのオフセットを加算した結果を、操作対象仮想物体の重心の位置姿勢として求め、現在の記録時刻とセットにして、操作履歴としてメモリ２０２に記録する。
【００４７】
なお、記録モードが設定されている間は、操作対象仮想物体とその他の仮想物体との干渉判定は行わない。
【００４８】
次にステップＳ３０２では、上記記録処理を終了すべく、キーボード２０６やマウス２０７を用いて記録モードの解除が指示されたか否かをチェックする。このチェックの結果、解除されていない場合には、処理をステップＳ３０１に戻し、Δｔ毎の操作対象仮想物体の重心位置姿勢を記録する処理を繰り返す。
【００４９】
一方、記録モードの解除が指示されてる場合には処理をステップＳ３０３に進める。ステップＳ３０３に進んだ時点で、メモリ２０２には、記録時刻０における操作対象仮想物体の重心位置、記録時刻Δｔにおける操作対象仮想物体の重心位置、記録時刻２Δｔにおける操作対象仮想物体の重心位置、…が記録されていることになる。
【００５０】
ステップＳ３０３では、仮想空間中に配置した各仮想物体のうち、操作対象仮想物体との干渉判定の対象となる仮想物体を選択する処理を、上記操作履歴に基づいて行う。本ステップにおける処理の詳細については後述する。
【００５１】
次にステップＳ３０４では、操作対象仮想物体と、ステップＳ３０３で選択した各仮想物体との干渉判定処理を行う。干渉判定処理については周知の技術であるので、係る技術についての説明は省略する。そしてステップＳ３０５では、操作対象仮想物体と干渉している仮想物体について、ステップＳ３００でロードされたデータを参照し、このデータ中の部品ＩＤを、メモリ２０２や外部記憶装置２０５に出力する。この出力した部品ＩＤの取り扱いについては特に限定するものではないが、例えば、上記描画処理において、ステップＳ３０５で出力した部品ＩＤを有する仮想物体の幾何的形状情報を用いてこの仮想物体を変形させたり、移動、回転させたりする。なお、部品ＩＤの出力先についてはこれに限定するものではない。
【００５２】
次にステップＳ３０６では、本処理の終了条件が満たされた、若しくはユーザがキーボード２０６やマウス２０７を用いて本処理の終了指示を入力したか否かをチェックする。係るチェックの結果、本処理の終了条件が満たされた、若しくはユーザがキーボード２０６やマウス２０７を用いて本処理の終了指示を入力した場合には本処理を終了する。一方、本処理の終了条件は満たされていないし、ユーザがキーボード２０６やマウス２０７を用いて本処理の終了指示を入力していない場合には、処理をステップＳ３０４に戻し、以降の処理を繰り返す。
【００５３】
次に、上記ステップＳ３０３における処理の詳細について説明する。図７は、上記ステップＳ３０３における処理の詳細を示すフローチャートである。
【００５４】
先ずステップＳ７０１では、記録時刻を示す変数ｔを０に初期化する。次にステップＳ７０２では上記操作履歴を参照し、記録時刻ｔにおける操作対象仮想物体の重心位置Ｇｔを取得する。
【００５５】
次にステップＳ７０３では、重心位置Ｇｔを含み、記録時刻ｔ近傍での操作対象仮想物体の重心の移動軌跡に対して垂直な平面Ｐｔを求める。平面Ｐｔを求めるための方法については様々なものが考えられる。
【００５６】
例えば、重心位置Ｇｔにおける操作対象仮想物体の姿勢は記録モードにおいて記録されているので、この姿勢成分を法線ベクトルとし、重心位置Ｇｔを含む平面を平面Ｐｔとして求める。
【００５７】
またその他の方法としては、例えば、重心位置Ｇ（ｔ−Δｔ）から重心位置Ｇ（ｔ＋Δｔ）に向かう方向ベクトルを法線ベクトルとし、重心位置Ｇｔを含む平面を平面Ｐｔとして求める。この場合、記録時刻ｆがｆ＝０〜Ｆである場合に、重心位置Ｇ０における平面Ｐ０は、重心位置Ｇ０から重心位置ＧΔｔに向かう方向ベクトルを法線ベクトルとし、重心位置Ｇ０を含む平面を平面Ｐ０として求める。また、重心位置ＧＦにおける平面ＰＦは、重心位置Ｇ（Ｆ−Δｔ）から重心位置ＧＦに向かう方向ベクトルを法線ベクトルとし、重心位置ＧＦを含む平面を平面ＰＦとして求める。もちろん、移動軌跡に垂直な平面を求める方法は係る方法に限定するものではない。
【００５８】
図５は、各重心位置Ｇｔにおける平面Ｐｔを示す図である。同図において５０１は、各重心位置Ｇｔを通る操作対象仮想物体の重心の移動軌跡を示すものであり、５０２，５０４がそれぞれ、各記録時刻における重心位置Ｇｔである。また、５０３，５０５はそれぞれ、重心位置５０２を含み、この位置における移動軌跡５０１の方向ベクトルを法線ベクトルとする平面、重心位置５０４を含み、この位置における移動軌跡５０１の方向ベクトルを法線ベクトルとする平面である。
【００５９】
なお、本実施形態では、操作履歴で記録した記録時刻ｔ＝０，Δｔ、２Δｔ、…のそれぞれについて平面を計算しているが、任意の記録時刻における平面を計算するようにしても良い。この場合、ｔ＝０、Δｔ、２Δｔ、…の各記録時刻における重心位置を通る曲線をスプライン補間処理などを用いて求め、この曲線上における任意の位置における点を含み、この点における曲線の方向ベクトルを法線ベクトルとする平面を求める。もちろん、この方法に限定するものではない。
【００６０】
図７に戻って次にステップＳ７０４では、重心位置Ｇｔから伸びる平面Ｐｔ上の半直線Ｌの方程式を算出する。係る半直線Ｌは、重心位置Ｇｔから放射状にのびる複数本について求めることになる。
【００６１】
次にステップＳ７０５では先ず、ステップＳ７０４で求めた複数本の半直線Ｌのうち１つを選択し、選択した半直線Ｌと最初に交差する仮想物体の部品ＩＤを特定する。そして、特定した部品ＩＤを、操作対象仮想物体との干渉判定の対象としての仮想物体の部品ＩＤを登録するためのリストに登録する。係るリストは、メモリ２０２内に保持されている。
【００６２】
図６は、平面Ｐｔによる仮想空間の断面図である。同図において６０１が重心位置Ｇｔを示す。６０２〜６１０はそれぞれ、操作対象仮想物体以外の仮想物体である。６５０〜６５７はそれぞれ、重心位置Ｇｔからのびる平面Ｐｔ上の半直線である。同図では８本の半直線を求めている。即ち、半直線間を４５度ずつあけているが、これに限定するものではなく、半直線の数を増やすことで半直線間の角度をより密にしても良いし、半直線の数を減らすことでより疎にしても良い。
【００６３】
図６の場合、上記ステップＳ７０４では、係る８本の半直線について求めることになる。そしてステップＳ７０５では、各半直線について、重心位置Ｇｔから最初に交差する仮想物体を特定し、特定した仮想物体の部品ＩＤをリストに登録する。
【００６４】
例えば、半直線６５０の場合、半直線６５０と最初に交差するのは仮想物体６０４である。従ってこの場合、仮想物体６０４の部品ＩＤをリストに登録する。また、半直線６５１の場合、半直線６５１と最初に交差するのは仮想物体６０５である。従ってこの場合、仮想物体６０５の部品ＩＤをリストに登録する。また、半直線６５２，６５３の場合、半直線６５２，６５３と最初に交差するのは仮想物体６０５である。しかし、仮想物体６０５の部品ＩＤは既にリストに登録されているので、リストへの部品ＩＤの登録処理は行わない。
【００６５】
このような処理を全ての半直線について行うと、仮想物体６０２，６０４，６０５，６０７，６０９の部品ＩＤはリストに登録され、それ以外の仮想物体の部品ＩＤはリストには登録されない。即ち、仮想物体６０２，６０４，６０５，６０７，６０９以外の仮想物体については、操作対象仮想物体との干渉判定の対象にはならないことになる。
【００６６】
このようにして、各半直線について、最初に交差する仮想物体を特定し、特定した仮想物体の部品ＩＤをリストに登録する。そしてこのリストに登録された部品ＩＤを有する仮想物体は、上記ステップＳ３０４で、操作対象仮想物体との干渉判定処理を行う対象となる。
【００６７】
なお、ステップＳ７０５で行う、直線と交差する仮想物体の検出は、例えばMercury社のシーングラフライブラリOpen Inventorを用いて実現することが出来る。
【００６８】
図７に戻って次にステップＳ７０６では、ステップＳ７０４で求めた複数本の半直線のそれぞれについてステップＳ７０５における処理を行ったか否かをチェックする。係るチェックの結果、全てについて行っていない場合には処理をステップＳ７０５に戻し、未だ処理対象となっていない半直線を１つを選択し、選択した半直線Ｌと最初に交差する仮想物体の部品ＩＤを特定する処理を行う。
【００６９】
一方、全てについて行った場合には、処理をステップＳ７０７に進める。ステップＳ７０７では、変数ｔにΔｔを加算する処理を行う。そしてステップＳ７０８では、変数ｔが示す時刻が、上記ステップＳ３０１における記録処理の終了時刻Ｔよりも前（小さい）か否かをチェックする。このチェックの結果、ｔ＞Ｔである場合には本処理を終了し、ｔ≦Ｔである場合には処理をステップＳ７０２に戻し、以降の処理を繰り返す。
【００７０】
以上の説明により、本実施形態によれば、操作対象仮想物体との干渉判定となる仮想物体の数を軽減させることができるので、干渉判定処理、ひいては、仮想空間を体感させるための処理全体を高速化することが出来る。
【００７１】
また、記録モードの設定時には干渉判定を行わないため、処理の負荷を軽減することができる。
【００７２】
そしてこれらにより、作業者の対話的操作を容易にすることが出来る。
【００７３】
なお、上記説明において操作対象仮想物体の重心位置の代わりに、操作対象仮想物体を包含する直方体などの立体の中心位置を用いても良い。
【００７４】
また、本実施形態では、操作対象仮想物体の重心位置からのびる半直線と交差する全ての仮想物体を、操作対象仮想物体との干渉判定の対象とした。しかし、操作対象仮想物体の重心位置からのびる半直線と交差する全ての仮想物体のうち、操作対象仮想物体の重心位置から所定の距離以内に配置されている仮想物体を、操作対象仮想物体との干渉判定の対象としても良い。
【００７５】
また、１本の半直線と交差する仮想物体を選択するのではなく、所定本数以上の半直線と交差する仮想物体を、操作対象仮想物体との干渉判定の対象として選択するようにしても良い。
【００７６】
また、本実施形態では、記録モードの設定後、Δｔ毎の操作対象仮想物体の重心位置姿勢を、記録時刻とセットにして操作履歴として記録している。しかし、操作対象仮想物体の重心位置が所定の距離移動する毎に、その位置姿勢と記録時刻とをセットにして操作履歴として記録するようにしても良い。
【００７７】
また、本実施形態では、記録モードの設定時には操作対象仮想物体とその他の仮想物体との干渉判定は行わないものとした。しかし記録モード時には、記録モードが解除された後に行う干渉判定処理よりも簡便な方法を用いた干渉判定処理を行うようにしても良い。そして記録モード時に操作対象仮想物体と干渉した仮想物体の部品ＩＤを上記リストに登録するようにしても良い。
【００７８】
［第２の実施形態］
以下では、本実施形態が第１の実施形態とは異なる点のみについて説明する。
【００７９】
図８は、平面Ｐｔによる仮想空間の断面図である。本実施形態では、操作対象仮想物体との干渉判定の対象とする仮想物体を選択する為の処理が、以下説明する点で第１の実施形態とは異なる。
【００８０】
同図において８０１は操作対象仮想物体、８０２〜８０６はそれぞれ操作対象仮想物体以外の仮想物体である。また、８０７は操作対象仮想物体の重心位置を示す。
【００８１】
本実施形態でも第１の実施形態と同様に、操作対象仮想物体の重心位置から放射状に半直線を設定する。しかし本実施形態では半直線設定後先ず、半直線が操作対象仮想物体と交差した点の位置と、操作対象仮想物体以外の仮想物体と交差した点の位置とを求める。例えば半直線８５１の場合、半直線が操作対象仮想物体と交差した点の位置は８０８で示されており、操作対象仮想物体以外の仮想物体と交差した点の位置は８０９で示されている。そして次にこの求めた２点間の距離を求める。図８では点８０８と点８０９との間の距離を求める。そして求めた距離が距離閾値以下であれば、この仮想物体を操作対象仮想物体との干渉判定の対象とする。同図では、点８０８と点８０９との間の距離は距離閾値以下であるので、仮想物体８０２は操作対象仮想物体との干渉判定の対象として選択される。
【００８２】
一方、半直線８５２の場合、操作対象仮想物体と交差する点８１０と、この半直線８５２が仮想物体８０５と交差する点８１１との間の距離は距離閾値以下ではないので、仮想物体８０５は、操作対象仮想物体との干渉判定の対象としては選択しない。
【００８３】
このように、本実施形態では、操作対象仮想物体の重心位置からのびる半直線が操作対象仮想物体と交差する点と、この半直線が交差する仮想物体におけるこの交差点との間の距離を求める。そして求めた距離が閾値以下であれば、この仮想物体を操作対象仮想物体との干渉判定の対象として選択する。
【００８４】
なお、操作対象仮想物体がその他の仮想物体と既に干渉していた場合には、この仮想物体と操作対象仮想物体との間の距離（それぞれの仮想物体における半直線との交差点間の距離）には負の符号を付ける。このようにすることにより、交点間の距離が必ず距離閾値以下となるので、操作対象仮想物体と干渉している仮想物体は必ず干渉判定対象として選択される。
【００８５】
なお本実施形態では、操作対象仮想物体を仮想空間内で移動させる場合に、この操作対象仮想物体との干渉判定対象としての仮想物体を特定する為には、図３のフローチャートに従った処理を行う。しかし、ステップＳ３０３における処理のみが第１の実施形態とは異なる。
【００８６】
図９は、本実施形態に係るステップＳ３０３における処理のフローチャートである。同図において図７に示したステップと同じステップについては同じステップ番号を付けており、その説明は省略する。
【００８７】
ステップＳ９０１では、ステップＳ７０４で設定した複数の半直線のうち１つを選択し、選択した半直線と操作対象仮想物体との交点のうち、重心位置Ｇｔから最も遠い点Ｍを求める。次にステップＳ９０２では、操作対象仮想物体以外の複数の仮想物体のうち、この半直線と交差する仮想物体を特定し、特定した仮想物体の部品ＩＤと、交差した点のうち最も点Ｍに近い点の座標位置とをセットにしてメモリ２０２に格納する。
【００８８】
次にステップＳ９０３では、ステップＳ９０２でメモリ２０２に格納した１以上のセット中の座標位置を参照し、点Ｍとの距離が閾値未満である座標位置とセットになっている部品ＩＤを特定する。そしてこの特定した部品ＩＤを第１の実施形態と同様に、操作対象仮想物体との干渉判定の対象としての仮想物体の部品ＩＤを登録するためのリストに登録する。
【００８９】
以上の処理を行うことで、操作対象仮想物体の大きさを考慮して、操作対象仮想物体との干渉判定の対象を選択することができる。従って、操作対象仮想物体と干渉する可能性の高い仮想物体のみを、干渉判定の対象として選択することができるので、更に、処理全体を高速化することが可能である。
【００９０】
なお、上記距離閾値は予め定められた固定値としても良いし、ユーザがキーボード２０６やマウス２０７を用いて適宜設定しても良い。
【００９１】
［第３の実施形態］
第１，２の実施形態では、１回の記録モードにおける記録処理の結果得られる操作履歴を用いて、操作対象仮想物体との干渉判定の対象を選択している。しかし、複数回の記録処理により得られる複数の操作履歴を用いて、操作対象仮想物体との干渉判定の対象を選択しても良い。
【００９２】
その場合、それぞれの操作履歴について第１実施形態、若しくは第２の実施形態を適用する。これにより、操作対象仮想物体の動かし方についてより多くのバリエーションを反映して干渉判定対象が選択されることになる。その結果、干渉判定対象を限定したことによる判定の抜けを防ぐことが出来る。
【００９３】
また、操作対象仮想物体以外の仮想物体毎に、何れかの方法でもって干渉判定対象として選択された回数をカウントしておき、そのカウント値が所定値以上の仮想物体を、最終的に操作対象仮想物体との干渉判定対象とするようにしても良い。この場合、操操作対象仮想物体が稀にしか通らない軌跡近傍における仮想物体を干渉判定対象の選定から外すことになり、効率的に干渉判定対象を限定することが出来る。
【００９４】
なお、記録処理回数は固定ではなく、変更可能としてもよい。
【００９５】
［第４の実施形態］
第２の実施形態では、各半直線に対して操作対象物体と静止物体との距離を閾値と比較している。これに替えて、静止物体の各部品について、各部品と操作対象物体との距離の平均を算出し、平均距離が所定の閾値未満の部品を干渉判定対象として選択する。
【００９６】
更に、第３の実施形態で説明したように、複数回の記録処理でもって得られる複数の操作履歴を用いて、各操作履歴に対する平均距離を求め、更に全ての操作履歴について求めた平均距離の更に平均距離（第２の平均距離）を求める。そして、第２の平均距離以下の距離である仮想物体を、操作対象仮想物体との干渉判定対象として選択する。
【００９７】
係る構成によれば、操作対象仮想物体が稀にしか仮想物体の近傍を通らない場合、この仮想物体を干渉判定対象の選定から外すことになり、効率的に干渉判定対象を限定することが出来る。
【００９８】
［第５の実施形態］
上記各実施形態では、操作対象仮想物体との干渉判定対象の単位を、仮想物体とした。しかし、干渉判定対象を、仮想物体の構成要素としても良い。例えば、仮想物体がポリゴンで構成されている場合、操作対象仮想物体との干渉判定対象の単位をポリゴンとしても良い。
【００９９】
例えば第１の実施形態の場合、半直線と交差する点を含むポリゴンを、操作対象仮想物体との干渉判定対象とする。
【０１００】
係る構成によれば、干渉判定対象の範囲をさらに限定することになり、干渉判定処理の高速化が図られる。
【０１０１】
また、仮想物体毎に、操作対象仮想物体との干渉判定対象の単位を、仮想物体本体とするのか、構成要素とするのかをユーザが適宜キーボード２０６やマウス２０７を用いて設定しても良い。
【０１０２】
［第６の実施形態］
操作対象仮想物体との干渉判定対象として選択された仮想物体（構成要素）と、選択されていない仮想物体（構成要素）とを視覚的に区別させるために、前者と後者とで表示方法を異ならせても良い。例えば、一方と他方とで表示色を変えても良いし、前者を不透明、後者を半透明で描画しても良いし、前者のみを平面パッチに赤色でワイヤフレームを重畳表示するようにしても良い。
【０１０３】
［第７の実施形態］
上記各実施形態では、操作対象仮想物体以外の仮想物体は静止しているものとしたが、これに限定するものではなく、位置、姿勢、サイズが適宜変更されても良い。
【０１０４】
この場合、記録モードでは、操作対象仮想物体の重心位置姿勢、記録時刻に加え、そのときの各仮想物体の位置、姿勢、拡大／縮小率（オリジナルのサイズに対する拡大／縮小率）をセットにして記録する。
【０１０５】
そして、記録時刻ｔにおける「操作対象仮想物体との干渉判定対象」を選択する際、先ず、記録時刻ｔにおける各仮想物体の位置、姿勢、拡大／縮小率に基づいて各仮想物体の位置姿勢、サイズを変更する。そして、上記各実施形態で説明した「操作対象仮想物体との干渉判定対象選択処理」を行う。
【０１０６】
もちろん、記録モードで、操作対象仮想物体の重心位置姿勢、記録時刻に加え、操作対象仮想物体の拡大／縮小率をセットにして記録しても良い。これにより、記録時刻ｔにおける「操作対象仮想物体との干渉判定対象」を選択する際、先ず、記録時刻ｔにおける操作対象仮想物体の拡大／縮小率に基づいて操作対象仮想物体のサイズを変更する。そして、上記各実施形態で説明した「操作対象仮想物体との干渉判定対象選択処理」を行う。係る構成によれば、操作対象仮想物体のサイズは適宜変更しても良いことになる。
【０１０７】
また、操作対象仮想物体は１つに限定するものではなく、複数であっても良い。この場合、それぞれの操作対象仮想物体に対して上記各実施形態を適用すればよい。
【０１０８】
また、上記各実施形態は適宜組み合わせて用いても良い。
【０１０９】
［その他の実施形態］
また、本発明の目的は、以下のようにすることによって達成されることはいうまでもない。即ち、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記録媒体（または記憶媒体）を、システムあるいは装置に供給する。そして、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に格納されたプログラムコードを読み出し実行する。この場合、記録媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記録した記録媒体は本発明を構成することになる。
【０１１０】
また、コンピュータが読み出したプログラムコードを実行することにより、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム（ＯＳ）などが実際の処理の一部または全部を行う。その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１１１】
さらに、記録媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれたとする。その後、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１１２】
本発明を上記記録媒体に適用する場合、その記録媒体には、先に説明したフローチャートに対応するプログラムコードが格納されることになる。
【図面の簡単な説明】
【０１１３】
【図１】操作対象仮想物体を含む複数の部品の仮想物体が配置された仮想空間の断面図である。
【図２】本発明の第１の実施形態に係るシステムのハードウェア構成を示すブロック図である。
【図３】操作対象仮想物体を仮想空間内で移動させる場合に、この操作対象仮想物体との干渉判定としての仮想物体を特定する為の処理のフローチャートである。
【図４】各仮想物体に係るデータの構成例を示す図である。
【図５】各重心位置Ｇｔにおける平面Ｐｔを示す図である。
【図６】平面Ｐｔによる仮想空間の断面図である。
【図７】ステップＳ３０３における処理の詳細を示すフローチャートである。
【図８】平面Ｐｔによる仮想空間の断面図である。
【図９】本発明の第２の実施形態に係るステップＳ３０３における処理のフローチャートである。
【図１】
2008059375.tif 000003
【図２】
2008059375.tif 000004
【図３】
2008059375.tif 000005
【図４】
2008059375.tif 000006
【図５】
2008059375.tif 000007
【図６】
2008059375.tif 000008
【図７】
2008059375.tif 000009
【図８】
2008059375.tif 000010
【図９】
2008059375.tif 000011