JP4960757B2 - 干渉計算装置およびその制御方法 - Google Patents

Description

本発明は、干渉計算装置およびその制御方法に関し、特に、仮想空間におけるオブジェクトの干渉判定技術に関するものである。

ＣＧ技術の発展に伴い、仮想空間内でさまざまな作業をするアプリケーションが増えてきている。近年では、３Ｄ−ＣＡＤはもとより、仮想現実（Virtual Reality、以下、ＶＲ）や複合現実（Mixed Reality、以下、ＭＲ）の分野も活発である。これらの分野のアプリケーションでは、仮想物体の表示を行うだけではなく、仮想物体同士の干渉も考慮に入れるようになっているものがある。

例えば、部品同士が干渉していると、物理的に製造が不可能であるので、３Ｄ−ＣＡＤ使用者は設計時に干渉チェックを行って、部品同士が干渉を起こしていないかをチェックする。これは特定の部品配置にした上で、干渉箇所を一気に調べる方法で、静的干渉チェックと呼ばれる。また、機構シミュレーションを行いながら干渉箇所を調べることもあり、これは動的干渉チェックと呼ばれる。このような動的干渉チェックの場合、可動部品の位置姿勢は限られている。そのため、時間をかけて干渉箇所を計算し、その結果を履歴として保存しておき、全計算が終わった後、ユーザに提示することが可能である（特許文献１）。これは前述の静的干渉チェックでも同様である。

ところが、ＶＲやＭＲアプリケーションでの干渉チェック機構は、静的干渉チェック及び動的干渉チェックのいずれとも異なっている。即ち、ＶＲやＭＲアプリケーションでは、仮想空間や複合現実空間において、物体間の干渉をユーザに提示することにより、より自然な体験をさせる。例えば、製品の組立教育用のアプリケーションであれば、ユーザの持つハンドツールと組立対象物との間の干渉を提示することにより、ユーザは作業感覚をより容易に把握することができる。このように、ＶＲやＭＲの分野では、干渉対象物体の一方は前記のようなハンドツールであるとか、あるいはユーザの手そのものといったように、その位置姿勢は６自由度を持っている場合が多い。本明細書ではこのような干渉チェックのことを自由動的干渉チェックと呼ぶことにする。
特開2004-302927号公報 Open Inventor from Mercury reference manual:SoIntersectionDetectionActionの項，Mercury Computer Systems, Inc.

自由動的干渉チェックの場合、ユーザがその場その場で、干渉対象物体の一方を任意に動かせるため、あらかじめ可動物体が存在し得る全ての位置姿勢における干渉を計算しておくことは不可能である。

一般的な自由動的干渉チェックについて、Mercury Computer Systems, Inc.のOpenInventorという製品を例に説明する。このOpenInventorでは、まず、ある静止状態のシーングラフが用意され、そのシーングラフ内で干渉箇所が計算され、干渉箇所の提示、およびシーングラフのレンダリングが行われる。そして次のタイミングにおける物体の位置を反映させるために、シーングラフを更新した上で、再びシーングラフ内で干渉箇所を計算する。つまり、静的干渉チェックをフレーム毎に実行することにより、自由動的干渉チェックが行われる。このような方法は、特にOpenInventorのための手法と言うわけではなく、一般的なものである。例えば、DDDGroupPlc.のSmartCllisionという製品やAGEIA Technologies IncのPhysXという製品でも、このような手法が採用されている。

一般に詳細な干渉チェックの計算には、多くの計算資源を必要とするため、１秒あたりの干渉結果の提示回数であるところの提示速度が低いという課題がある。ＶＲやＭＲといったリアルタイム性が要求されるシステムにおいては、提示速度が低いということは、致命的である。一方、干渉結果の提示速度を上げようとすると、粗い干渉チェックの計算しか行えないという課題があった。

本発明は、上記の課題に鑑みてなされたものであり、干渉チェックの精度及び計算速度を共に向上する干渉計算装置及び方法を提供することを目的とする。

上記の目的を達成するために、本発明の一態様による干渉計算装置は、以下の構成を備える。即ち、
３次元空間における可動物体と他の物体との間の干渉計算を実行する干渉計算装置であって、
前記可動物体の検出された位置姿勢に基づいて、前記可動物体と前記他の物体との間の干渉計算を実行する干渉計算手段と、
前記可動物体の前記他の物体に対する相対位置姿勢と、当該相対位置姿勢に対する前記干渉計算手段による干渉計算の結果とが記録された、複数の干渉データレコードを格納する干渉データ記憶手段と、
前記可動物体の新たに検出された位置姿勢に基づいて得られた、前記可動物体の前記他の物体に対する新たな相対位置姿勢と、前記複数の干渉データレコードの各々に記録されている相対位置姿勢との差異の大きさを算出する算出手段と、
前記複数の干渉データレコードに前記算出手段で算出された差異の大きさが所定範囲内で且つ最小となる干渉データレコードを選択し、選択された干渉データレコードに記録されている干渉計算の結果を、前記新たに検出された位置姿勢に関する干渉計算の結果として出力する干渉データ選択手段とを備える。

また、上記の目的を達成するために、本発明の他の態様による干渉計算方法は、
３次元空間における可動物体と他の物体との間の干渉計算を実行する干渉計算装置による干渉計算方法であって、
前記干渉計算装置の干渉計算手段が、前記可動物体の検出された位置姿勢に基づいて、前記可動物体と前記他の物体との間の干渉計算を実行する干渉計算工程と、
前記干渉計算装置の干渉データ記憶手段が、前記可動物体の前記他の物体に対する相対位置姿勢と、当該相対位置姿勢に対する前記干渉計算工程による干渉計算の結果とが記録された、複数の干渉データレコードを格納する干渉データ記憶工程と、
前記干渉計算装置の算出手段が、前記可動物体の新たに検出された位置姿勢に基づいて得られた、前記可動物体の前記他の物体に対する新たな相対位置姿勢と、前記複数の干渉データレコードの各々に記録されている相対位置姿勢との差異の大きさを算出する算出工程と、
前記干渉計算装置の干渉データ選択手段が、前記算出工程で算出された差異の大きさが所定範囲内で且つ最小となる干渉データレコードを選択し、選択された干渉データレコードに記録されている干渉計算の結果を、前記新たに検出された位置姿勢に関する干渉計算の結果として出力する干渉データ選択工程とを有する。

本発明によれば、干渉チェックの精度及び計算速度を共に向上することができる。

以下、添付の図面を参照して本発明の好適な実施形態を説明する。

＜第１実施形態＞
図１は第１実施形態による干渉計算装置１００の構成を表すブロック図である。なお、以下に示される干渉計算装置１００の各構成の一部或いは全てが、不図示のＣＰＵが不図示のＲＯＭ或いはＲＡＭに格納された制御プログラムを実行することにより実現されてもよい。即ち、干渉計算装置１００は一般的なコンピュータにおいて後述する処理を実行させる制御プログラムを実行させることにより実現されても良い。

図１に示されるように、位置姿勢管理部１０１には位置姿勢受信部１０２が設けられている。位置姿勢受信部１０２は、干渉計算装置１００の外部から与えられる、可動物体の３次元空間における６自由度の位置姿勢の検出信号（位置姿勢信号）を受信する。本実施形態は、可動物体と、その他の物体との干渉を計算する装置に関するものである。例えば、ある装置に対する作業教育を支援するためのＭＲアプリケーションであれば、可動物体とは例えばユーザの握っているハンドツール等であり、その他の物体とはユーザが作業しようとしている装置の仮想物体となる。なお、干渉計算の対象は仮想物体同士の干渉であっても良いし、仮想物体と現実の物体の干渉であってもよい。例えば、ハンドツールに装着された仮想物体を用いてある装置を操作するような状況であった場合に、ある装置が仮想物体であれば仮想物体同士の干渉計算となる。可動物体の位置姿勢は位置姿勢センサと呼ばれるセンサを用いる。そのような位置姿勢センサとしては例えば、Polhemus社のFastrakシステムがあり、これは、数センチ角ほどの大きさをしたレシーバの位置及び姿勢の６自由度が計測できる。

位置姿勢受信部１０２が受信した可動物体の位置姿勢信号は、位置姿勢データに変換され、干渉計算用データの現在位置姿勢を上書きすることによって保持される。干渉計算用データは、いくつかの干渉計算に必要なデータからなり、干渉計算用データ記憶部１０３に記憶されている。干渉計算用データの代表的なものを図２に示す。図２は、干渉計算用データ記憶部１０３に格納された干渉計算用データ２００の構成例を示している。

図２において、現在位置姿勢２０１は、前述の通り、位置姿勢受信部によって更新が行われ、可動物体の最新の位置姿勢を表す位置姿勢データである。干渉計算用位置姿勢２０２は、後述の干渉計算部１０４が干渉計算を行う際に、可動物体の位置姿勢として用いられる。これは、干渉計算部１０４が干渉計算を行っている間に、計算に用いる可動物体の位置姿勢データが変化してしまうのを防ぐためである。干渉計算用３Ｄデータ２０３は、後述の干渉計算部１０４が干渉計算を行う際に用いる３Ｄデータである。例えば、干渉計算部１０４が物体同士の干渉を、それらを構成するポリゴン同士の干渉から算出するような場合、干渉計算用３Ｄデータ２０３には物体を構成するポリゴンの情報が収められている。干渉計算用３Ｄデータ２０３は干渉計算のアルゴリズムに依存しており、また干渉計算装置１００は干渉計算のアルゴリズムに依存しないため、干渉計算用３Ｄデータの詳細は割愛する。

さて、干渉計算用データ記憶部１０３に格納された干渉計算用データ２００を元に、干渉計算部１０４は干渉計算を行う。そして、干渉計算の結果として干渉データ管理部１０５は、干渉データ記憶部１０６に干渉データレコードを追加する。これらの動作については後述するが、干渉データ記憶部１０６は、干渉データレコードの集合であるところの干渉データを保持している。

干渉データレコードの一つ一つは、一つの干渉計算結果に対応している。言い換えると、干渉計算の結果は干渉データレコードとしてまとめられ、その集合である干渉データが、干渉データ記憶部１０６によって保持されている。

図３は干渉データ記憶部１０６に格納される干渉データ３００（干渉データレコードの集合）の例を示す図である。

図３に示されるように、干渉データレコードには、いくつかのフィールドがある。“干渉対象部品”とは、可動物体と干渉している部品（物体）である。「干渉が起きている」ことは２物体の干渉に分解することができる。例えば、Ａ、Ｂ、Ｃの３物体が互いに干渉しているとすると、ＡとＢ、ＢとＣ、ＣとＡの３つの干渉に分けられる。本実施形態の干渉計算装置が１００が想定している干渉は、「可動物体」と「その他の物体」との間の干渉である。前述の例でＡを可動物体とした場合、その他の物体はＢ，Ｃである。従って、ＡとＢ、ＡとＣの２つの干渉が検出され、その結果として２つの干渉データレコードが生成されることになる。その際に、干渉対象部品にはそれぞれ、「Ｂ」と「Ｃ」が記録されることになる。

“詳細レベル”は干渉計算の際に用いた詳細度である。一般に干渉計算は計算負荷がかかるため、粗い干渉チェックを行う場合がある。例えば、時間をかけてまで詳細な干渉計算の結果を必要としていない場合には粗い干渉計算が行われることになる。或いは、詳細な干渉計算を行う際に干渉が起こっていないことが明白な部分を干渉計算の対象から除外することにより計算速度を向上させたい場合も、粗い干渉計算が行われることになる。

図４に詳細度の例を示す。元物体と他の物体との間の干渉を計算する場合に、詳細度「低」で表した物体（例えば、バウンディングボックス）との間の干渉を計算する。ここで干渉が起きていなければ、元物体との間の干渉は明らかに起きていないことが保証されるので、さらなる干渉計算を行う必要はない。さらなる干渉計算を行う場合は、詳細度「高」で示したように元物体を例えば３つの物体に分割し、各々の物体との間の干渉計算を行う。ここでは詳細度「高」の場合に、３つの直方体に分割したが、より適した分割法は干渉計算のアルゴリズムによるため、詳細な説明は割愛する。

アプリケーションによっては、詳細度が低い場合の干渉結果は不要であることがある。しかしながら、リアルタイム性が要求されるＶＲやＭＲアプリケーションにおいては、詳細度が低い場合の干渉結果も有用である場合が多い。そのため、干渉計算装置１００は、詳細度が低い場合の干渉計算の結果も、干渉データレコードとして保持する。

図３に戻り、“干渉部分”は、干渉計算の結果、干渉している箇所を示す情報であり、干渉提示をするのに十分な情報である。例えば、どの部品と干渉しているのかさえわかればよいのであれば、“干渉部分”は部品番号でもよく、干渉対象部品の情報を代わりに用いるのであれば“干渉部分”は不要となる。また、干渉している箇所をポリゴンで表示するようなシステムであれば、“干渉部分”は干渉している箇所を表すポリゴン情報である。また、干渉箇所の形状を細かく見ることができるようなシステムであれば、干渉箇所に対応した新たな物体を生成し、その情報（部品番号、ポリゴンを用いた３Ｄ情報等）を“干渉部分”とする。なお、「ＣＣ００１」、「ＣＣ００３」等は、部品番号を用いた場合の例を示している。

また、干渉していない場合には、干渉していないことを表すため“干渉部分”＝「なし」という場合もあり得る。

次に、図３の“一致限界”について説明する。本実施形態は、過去の干渉計算の結果を干渉データレコードとして保持しておき、新たに干渉計算を行う代わりに過去の干渉結果を利用することにより、干渉計算の負荷を減らす。そして、その際に過去のどの干渉データレコードを代わりの干渉結果として用いるのか、また用いることができないのか、を判断するための指標を一致限界と称する。

過去の干渉データレコードの干渉結果と同じ結果を出すためには、この干渉データレコードの干渉計算を行う際に用いた、干渉対象部品および部品間の相対位置姿勢が同じであればよい。すなわち、これらの情報を入力として何らかの指標を得て、その指標の値が過去の干渉データレコードの指標と同一であればよい。本実施形態では、距離関数を用いてこの指標を得る。この距離関数は干渉計算に用いたときと同じ干渉対象部品、同じ相対位置姿勢（またはこれらを特定できる情報）を与えたときに、最小値、あるいは最大値を返す。ここでは最小値として０をとるものとする。

可動物体の現在位置姿勢から計算した、干渉対象部品との相対位置姿勢を距離関数に与えて０が返ってくれば、その干渉データレコードを現在の状況を反映した干渉結果として用いることができる。また、ちょうど同じ相対位置姿勢ではなくとも、似たような相対位置姿勢であれば、その干渉データレコードを現在の状況を反映した干渉結果として用いてもよい。相対位置姿勢がどの程度であれば、その干渉データレコードを用いることができるのかの限界を与えるのが一致限界である。

この様子を図５で説明する。図５は入力を相対位置姿勢とした場合の距離関数の値を示している。なお、相対位置姿勢は本来６自由度を持っているが、ここではわかり易くするために１自由度としている。距離関数が０を返すときの相対位置姿勢ζを中心として、相対位置姿勢がζから離れるに従い、距離関数の値は大きくなっていく。この値が一致限界以下、つまり相対位置姿勢がαとβの間である範囲では、相対位置姿勢がζの干渉データレコードを代わりに用いることができる。

なお、距離関数の最小値が０ではなく、D_minの場合は、距離関数がD_minを返す相対位置姿勢をζとすればよい。また距離関数が干渉計算に用いたときと同じ干渉対象部品、同じ相対位置姿勢（またはこれらを特定できる情報）を与えたときに、最大値D_maxを返す場合は、図５において上に凸なグラフとなるので、距離関数がD_maxを返す時の相対位置姿勢をζとする。そして、一致限界との比較においては、距離関数の値が一致限界以上の値を取る場合に、相対位置姿勢がζの干渉データレコードを代わりに用いるようにすればよい。

一般に距離関数は、干渉アルゴリズムや、可動物体や干渉対象部品の形状に依存する。ここで、詳細は割愛するが、距離関数の例を挙げておく。本実施形態は干渉計算のコストを下げるのが目的であるため、あまりにも複雑な距離関数を用いることは好ましくない。そこで、ここでは表引きによる、高速な検索を実現しやすい距離関数を考える。

相対位置姿勢をヨー、ピッチ、ロールの角度成分とｘ、ｙ、ｚの平行移動成分で表した値をa, p, r, x, y, zとする。またζの各成分をa_ζ, p_ζ, r_ζ, x_ζ, y_ζ, z_ζとする。重みをwとして、距離関数fは、次のように定義できる。

次に、図３の干渉データレコードに含まれる“同一視閾値”について説明する。同一視閾値も考え方は、一致限界と同様である。同一視閾値とは、干渉計算を行った際の相対位置姿勢がζである干渉データレコードが干渉データにあるとき、詳細レベルが同一であり、かつ相対位置姿勢がζ’である新たな干渉データレコードを干渉データに追加すべきか否かを判断する指標である。

新たな干渉データレコードを干渉データに追加すべきか否かを判断する必要が生ずるかどうかは、干渉計算のアルゴリズムによる。例えば、詳細レベルがＬ、相対位置姿勢がＰでの干渉計算を行う際に、詳細レベル（Ｌ−１）、相対位置姿勢Ｐを中間結果として出すような場合を考える。これは前述したような、より粗い詳細度における干渉計算を行うことにより、干渉が起きていない範囲を除外するような干渉計算のアルゴリズムでの場合にはあてはまる。このような場合には、新たな干渉データレコードの追加を抑制する仕組みがないと、干渉データの量が爆発的に大きくなってしまう。

ζ’がζと非常に近い場合、つまり、距離関数にζ’を与えたときに返す値が同一視閾値以下である場合には、相対位置姿勢がζ’である干渉データレコードを干渉データに追加しないようにする。この様子を図５に示す。γ≦ζ’≦δの場合には、相対位置姿勢がζ’である干渉データレコードを干渉データに追加しない。

なお、距離関数の最小値が０ではなく、D_minの場合は、距離関数がD_minを返す相対位置姿勢をζとすればよいことは既に述べた。また距離関数が干渉計算に用いたときと同じ干渉対象部品、同じ相対位置姿勢（またはこれらを特定できる情報）を与えたときに、最大値D_maxを返す場合は、距離関数がD_maxを返す時の相対位置姿勢をζとする。そして、距離関数にζ’を与えたときに返す値が同一視閾値以上である場合には、相対位置姿勢がζ’’である干渉データレコードを干渉データに追加しないようにするようにすればよい。

図１に戻り、干渉データ選択部１０７は、干渉データ記憶部１０６に格納されている干渉データレコードの中から１つの干渉データレコードを選択する。干渉データ選択部１０７は、例えば、現在位置姿勢２０１から可動物体の干渉対象部品（その他の物体）との間の位置姿勢（相対位置姿勢）を求め、この相対位置姿勢に基づいて干渉データレコードを選択する。なお、干渉データには、あらかじめ定義された以下のような干渉データレコード（図３の干渉データレコード３０１）が含まれているものとする。
定義済み干渉データレコード：
詳細レベル＝L_min
干渉箇所＝不明
距離関数値＝いかなる場合も一致限界以下
ここで、干渉計算部１０４が干渉計算を行う際の詳細レベルは、L_minよりも高いことを仮定している。定義済み干渉データレコードの詳細レベルは、干渉計算部１０４が干渉計算を行ったどの結果よりも低い詳細レベルを持っていることになる。なお、以下の説明では、L_min＝０で、干渉計算部が干渉計算を行う際の詳細レベルは１から順に整数値をとるものとする。

詳細レベルL_minの場合、距離関数はいかなる相対位置姿勢に対しても、一致限界以下を返す。これには、一致限界を非常に大きな値にしてもよいし、距離関数が０を返すようにしてもよい。

また、干渉箇所が不明とは、干渉が起こっているか起こっていないかが不明ということである。干渉箇所が不明な場合、このことをどのように提示するかは、本発明の範囲外であるが、最も詳細度の低い干渉計算が終わるまでの間のことであり、この間は非常に短いと考えられるので、干渉箇所がないものとして提示してもよい。

干渉データレコードの選択に先立ち、まず干渉計算用データ２００の中から可動物体の現在の位置姿勢である現在位置姿勢２０１を取得する。そして干渉データに含まれる全干渉データレコードの中から、図６の手順で干渉データレコードを１つ選択する。

まず、ステップＳ６０１において、選択された干渉データレコードを記録しておくための変数「マッチしたレコード」をクリアしておく。次いで、ステップＳ６０２〜Ｓ６０４において、詳細レベルが最も高い干渉データレコードの集合に対して、以下の条件に合うものを抽出し、「マッチしたレコード」に記録する。
・条件：「指定された詳細レベル、および現在位置姿勢２０１から求めた相対位置姿勢を距離関数に入力して得られる値が一致限界以下である干渉データレコードのうち、得られた値が最も小さい干渉データレコード」
もし、マッチしたレコードがなければ、詳細レベルの値が１小さい干渉データレコードの集合に対して同様なことを繰り返す。上述した定義済みの干渉データレコード３０１は必ず条件に合うため、以上の手順を実行すれば、最終的には「マッチしたレコード」が見つかることになる。この「マッチしたレコード」を、干渉データ選択部１０７は選択する。

なお、ここでは距離関数は干渉計算に用いたときと同じ干渉対象部品、同じ相対位置（またはこれらを特定できる情報）を与えたときに、最小値を返すものとしたが、最大値を返す場合には、上記条件を以下のようにすればよい。
・条件：「指定された詳細レベル、および現在位置姿勢２０１から求めた相対位置姿勢を距離関数に入力して得られる値が一致限界以上である干渉データレコードのうち、得られた値が最も大きい干渉データレコード」
図１に戻り、干渉部分送信部１０８は、干渉データ選択部１０７が選択した干渉データレコードに含まれる情報のうち、少なくとも「干渉部分」を外部のアプリケーションに送信する。外部のアプリケーションは干渉部分送信部１０８が送信した「干渉部分」を基に干渉提示を行うことになる。

干渉計算判断部１０９では、干渉データ選択部１０７が選択した干渉データレコードに基づき、干渉計算部１０４がどのような干渉計算を行うべきかを判断する。上述したように、干渉データ選択部１０７が選択した干渉データレコードは、干渉データ３００に含まれている、一致限界の条件を満足する干渉データレコードのうち、最も詳細度が高いものである。そこで、干渉計算判断部１０９は、その詳細度よりも高い詳細度の干渉計算を行うべきであると判断する。例えば、干渉計算判断部１０９は、干渉データレコードに含まれている詳細度よりも、１レベル高い詳細度での干渉計算を行うよう判断する。一方、干渉計算判断部１０９は、干渉データレコードに含まれている詳細度が最大の詳細度であった場合は、干渉計算の実行を禁止するようにしてもよい。

また、干渉計算判断部１０９は、干渉データ選択部１０７が選択した干渉データレコードの「干渉部分」が「なし」である場合には、干渉計算部１０４に新たな干渉計算を禁止すると判断してもよい。これは前述の干渉計算のアルゴリズムによるが、ある詳細レベルにおける干渉計算の結果が以下のような場合、不要な計算を抑制するという効果がある。
・「干渉あり」の場合→より詳細な干渉計算の結果、干渉がある可能性がある。
・「干渉なし」の場合→より詳細な干渉計算を行っても、干渉がない。

干渉計算判断部１０９の判断を受け、干渉計算部１０４では干渉計算を行う。一般に干渉計算は時間のかかる処理であり、干渉計算判断部１０９が干渉計算を行う判断を下した時点で、干渉計算部１０４において直前の干渉計算が終了していない場合がある。即ち、干渉計算の必要が発生した時点で、干渉計算部１０４が別の干渉計算を実行中である場合がある。この場合、干渉計算部１０４は、（１）現在計算中の干渉計算を直ちに打ち切り、干渉計算判断部１０９が判断した干渉計算を実行するか、或いは、（２）現在計算中の干渉計算が終了するのを待って、干渉計算判断部１０９が判断した干渉計算を実行する。

（１）の場合、比較的素早く干渉結果が得られるが、干渉データ記憶部１０６に含まれる干渉データレコードの数が少ないうちは、干渉データ選択部１０７によって高い詳細レベルの干渉データレコードが選択されない。そのため、干渉計算判断部１０９により新たな干渉計算を行うよう判断され、再度干渉計算が打ち切られてしまう可能性がある。その結果、なかなか干渉データに含まれる干渉データレコードの数が増えず、詳細な干渉結果を素早く求めるという本発明の効果が十分発揮できないことがある。

一方、（２）の場合、干渉データに含まれる干渉データレコードの数が少ないうちは、干渉データレコードの数を増やすため、干渉データが充実するという効果がある。しかし、十分に干渉データレコードが蓄積されている状態では、干渉計算が終了するまで待ちつづけるため、干渉結果を素早く得ることができない。

そこで、干渉計算部１０４は、干渉計算中の詳細レベルと干渉計算判断部１０９によって判断された干渉計算の詳細レベルに基づいて、干渉計算の継続、打ち切りを制御するようにしてもよい。例えば、干渉計算部１０４において、現在計算中の干渉計算の詳細レベルが干渉計算判断部１０９によって判断された干渉計算の詳細レベルよりも高い場合には、干渉計算部１０４は現在計算中の干渉計算を打ち切る。また、干渉計算部１０４において、現在計算中の干渉計算の詳細レベルが干渉計算判断部１０９によって判断された干渉計算の詳細レベル以下の場合には現在計算中の干渉計算を続行する。このような制御により、干渉データ内で、より詳細レベルの低い干渉データレコードを優先的に充実させることができ、干渉データの充実と素早い干渉結果の出力を両立させることができる。

なお、干渉計算部１０４は、干渉計算を行っている最中に可動物体の位置姿勢が変化してしまわないよう、干渉計算用データ２００内にある干渉計算用位置姿勢２０２を、干渉計算用データ２００内にある現在位置姿勢２０１でもって、更新しておく。そして、干渉計算部１０４は、更新された干渉計算用位置姿勢２０２と、干渉計算用データ２００内にある干渉計算用３Ｄデータ２０３と、干渉計算判断部１０９が判断した詳細レベルを用いて、干渉計算を実行する。

干渉データ管理部１０５は、干渉計算部１０４が行った干渉計算の結果から、干渉データレコードを生成し、干渉データ３００に追加する。

但し、干渉データ管理部１０５は、干渉計算部１０４が行った全ての干渉計算の結果を干渉データレコードにして干渉データ３００に追加することはせず、前述のように、同一視閾値との比較に基づいて一部の干渉計算の結果を破棄する。あるいは、最近のデータを優先するという観点から、上記の手法により破棄する代わりに、対応する既存の干渉データレコードを、干渉計算の結果から作成した新たな干渉データレコードによって更新してもよい。なお、干渉データレコードの登録や更新は、干渉計算部１０４による干渉計算が完了できた場合に実施されるものであり、上記のように干渉計算が中断された場合は実施されないことは言うまでもない。

また、干渉データ管理部１０５は、干渉データ３００内に干渉データレコードが、際限なく増えてしまうことを抑制するために、いくつかの抑制機構を備えてもよい。

例えば、干渉データ管理部１０５が、干渉データレコードの総数を制限するようにしてもよい。この場合、干渉データレコードの総数を超えて新たに干渉データレコードを追加しようとする際に、既存の干渉データレコードのいずれかが削除されることになる。削除対象となる干渉データレコードとしては、例えば、干渉データ選択部１０７によって最も長い期間選択されていないものを選択する方法が考えられる。干渉データ３００内の干渉データレコードは、干渉データ選択部１０７によって選択されるために存在しているのであり、長い期間選択されていないということは、その干渉データレコードの有用性が下がっていると考えられるからである。

あるいは詳細度が高い干渉データレコードを優先的に削除するという方法もある。これは、詳細度の低い干渉データレコードは、仮想空間あるいは複合現実空間内のより広い範囲における干渉結果として用いることができるという考えに立脚している。

また、干渉データ内の干渉データレコードの総数ではなく、詳細レベル毎に総数を規定してもよい。これは、ごく狭い範囲での干渉チェックが主体となるようなアプリケーションにおいては、有効である。この場合、各詳細レベルにおける削除すべき干渉データレコードの選択には、「干渉データ選択部１０７によって最も長い期間選択されていないもの」という条件を適用すればよい。またほとんど静止しているような画像の場合は、詳細レベルが最も高い干渉結果を得たいが、自由動的干渉チェックの場合、対応する干渉データレコードが、干渉データ選択部１０７によって再度選択される可能性は低い。例えば、可動物体を手で持っているような場合、三次元空間中で同一の位置姿勢を保つことは非常に困難である。そのため、位置姿勢の値が同一の値を維持し続けることはほとんどあり得ず、常に値はふらついており、詳細レベルが高くなり、一致限界が狭くなると、そのような干渉データレコードは再選択される可能性が低い。そのため、干渉計算部１０４が計算可能な最も高い詳細レベルの干渉データレコードの総数を１つ、２つといったようなごく少数に制限することも有効である。

図１０は、干渉計算装置１００によって実行される干渉計算処理を説明するフローチャートである。以下、図１０に示される処理手順に従って上述した干渉計算装置１００の干渉計算処理について更に説明する。

ステップＳ１０１において、位置姿勢管理部１０１は、位置姿勢受信部１０２で受信した、可動物体の新たな位置姿勢信号に基づいて、図２に示すような干渉計算用データ２００を生成し、これを干渉計算用データ記憶部１０３に格納する。

干渉データ記憶部１０６には、図３に示されるように、可動物体と他の物体（干渉対象部品）との相対位置姿勢及びその干渉計算結果を含む複数の干渉データレコードが格納されている。ステップＳ１０２において、干渉データ選択部１０７は、新たに検出された可動物体の位置姿勢に基づいて得られた新たな相対位置姿勢と、干渉データ記憶部１０６に格納されている複数の干渉データレコードの相対位置姿勢との間の距離を算出する。なお、可動物体の位置姿勢は、上記実施形態の説明では、位置姿勢受信部１０２が受信した位置姿勢信号から生成されるものであり、相対位置姿勢とは区別していた。しかしながら、干渉対象部品が現実空間に固定されている場合は、位置姿勢信号から得られる位置姿勢データと相対位置姿勢は１対１に対応する。従ってそのような場合、干渉データレコードの“相対位置姿勢”として、位置姿勢受信部１０２が受信した位置姿勢信号から生成される位置姿勢を登録することも可能である。

ステップＳ１０３において、干渉データ選択部１０７は、ステップＳ１０２で算出された距離に基づいて１つの干渉データレコードを選択する。上記実施形態では、干渉データレコードに含まれる“一致限界”の値と算出された距離との比較により、干渉データレコードが選択される。

ステップＳ１０４において、干渉部分送信部１０８は、干渉データ選択部１０７により選択された干渉データレコードに、干渉計算結果（干渉部分）として有効な値が記述されているか否かを判定する。有効な値が記述されている場合は、ステップＳ１１０において、選択された干渉データレコードに記述されている“干渉部分”の値を、干渉計算の結果として外部へ出力する。有効な値を含まない干渉データレコード（予め定義された干渉データレコード３０１）が選択された場合は、ステップＳ１１０はスキップされる。

ステップＳ１０５において、干渉計算判断部１０９は、選択された干渉データレコードに基づいて、干渉計算部１０４に、新たに検出された位置姿勢による干渉計算を実行させるか否かを判断する。例えば、新たな相対位置姿勢を同一視閾値の範囲に含む干渉データレコードであって、最高の詳細レベルの干渉データレコードが存在する場合は、当該新たな相対位置姿勢に関して干渉計算を行わないと判断する。或いは、上述したように、ステップＳ１０４で選択された干渉データレコードが干渉部分「なし」を示す場合に、干渉計算を行なわないと判定してもよい。干渉計算を行わないと判定された場合は、本処理を終了する。

一方、干渉計算を実行させると判定された場合、干渉計算判断部１０９は、ステップＳ１０６において、干渉計算の詳細レベルを決定する。例えば、新たな相対位置姿勢を同一視閾値の範囲に含む干渉データレコードのうち最高の詳細レベルより１上のレベルで干渉計算を行うよう設定される。そして、ステップＳ１０７において、干渉計算部１０４は、干渉計算用データ記憶部１０３に格納されている干渉計算用データを用いて干渉計算を実行する。

ステップＳ１０８において、干渉データ管理部１０５は、干渉計算部１０４によってなされた新たな位置姿勢データについての干渉計算の結果に基づいて、干渉データ記憶部１０６の内容を更新するか否かを判定する。更新すると判定された場合、ステップＳ１０９において、干渉データ管理部１０５は、干渉データ記憶部１０６を更新する。即ち、干渉計算部１０４で得られた計算結果や、干渉計算部１０４で用いられた干渉計算用データに基づいて、干渉データレコードを追加、或いは更新する。ステップＳ１０８及びＳ１０９による干渉データ記憶部１０６の更新は、干渉データ管理部１０５に関して上述したとおりである。

以上のような第１実施形態の干渉計算装置によれば、干渉計算の結果を干渉データレコードとして保持することにより、過去に算出した干渉計算の結果を有効に利用できる。このため、迅速に干渉結果を出力することが可能となる。また、干渉データレコードに、当該干渉計算の詳細度を示す“詳細レベル”を記録しておき、順次に高い詳細レベルの干渉データレコードが蓄積されていくように構成したので（Ｓ１０６）、装置を使用している間に干渉データの精度が向上する。従って、干渉チェックの精度及び計算速度を共に向上することができる。

＜第２実施形態＞
上記第１実施形態においては、干渉計算部１０４は干渉計算を始める時点の現在位置姿勢２０１を用いて干渉計算を行っていた。しかし、干渉計算は一般に計算負荷が高く、結果が出るまでに時間がかかる。そのため、せっかく干渉計算を行っても、その結果が出た頃には既に現在位置姿勢が変わってしまっていて、干渉データ選択部１０７によって選択されないという場合が出てくる。また、現在位置姿勢があまり変化していなければ、計算した干渉データレコードは何度も使用され、その間により詳細な干渉計算を行うことができる。前者の課題を克服するため、また後者の効果をあげるためには、干渉計算を行う際に用いる干渉計算用位置姿勢２０２として、現在位置姿勢２０１ではなく、近未来を予測した現在位置姿勢を用いることが考えられる。

図７は第２実施形態による干渉計算装置７００の構成を表すブロック図である。参照番号の７０１〜７０９の構成は第１実施形態（図１）の１０１〜１０９に示される構成に対応している。位置姿勢管理部７０１には位置姿勢予測部７１１がある。位置姿勢予測部７１１は、位置姿勢受信部７０２が受信した可動物体の位置姿勢を受け取り、過去および現在の可動物体の位置姿勢を基に近未来の可動物体の位置姿勢を予測する。なお、予測手法としては、カルマンフィルタを用いた手法等、周知の技術を適用でき、その詳細な説明は割愛する。位置姿勢予測部７１１は予測した近未来の可動物体の位置姿勢で、干渉計算用データ記憶部７０３の干渉計算用データにある予測位置姿勢を更新する。図８は、第２実施形態の干渉計算用データ記憶部７０３に記憶される干渉計算用データ８００の構成例を示す図である。図８に示されるように、予測位置姿勢８０１が干渉計算用データに含まれる。この場合、干渉計算部７０４は、新たな位置姿勢での干渉計算を行うのに先立ち、予測位置姿勢８０１でもって、干渉計算用位置姿勢２０２を更新することになる。

なお、第１実施形態では、干渉計算用データ２００には、可動物体がどれであるかの情報は干渉計算用３Ｄデータ２０３に含まれているとしている。これに対して、第２実施形態では、干渉計算装置７００の柔軟性を高めるため、位置姿勢受信部７０２が受信する位置姿勢がどの可動物体に対応するものなのかを設定することができるようにしている。この場合、図８に示されるように、干渉計算用データ８００は、位置姿勢受信部７０２が受信する位置姿勢がどの可動物体に対応するものなのかを示す可動物体指示情報８０２として保持している。可動物体登録部７１２は、位置姿勢受信部７０２が受信する位置姿勢がどの可動物体に対応するものなのかを、可動物体指示情報に登録する。さらに干渉計算部７０４では、干渉計算用データ８００のうち、干渉計算用位置姿勢２０２、干渉計算用３Ｄデータ２０３に加えて、可動物体指示情報８０２も用いて、干渉計算を実行する。また可動物体登録部７１２は、ユーザの利便性を考え、グラフィカルなユーザインターフェース（ＧＵＩ：Graphical User Interface）として実装されていてもよい。

なお、第１実施例では可動物体が１つの場合を想定してきた。しかし、本発明は可動物体の数を制限するものではない。複数の可動物体がある場合は、干渉計算用データのうち、現在位置姿勢、干渉計算用位置姿勢、また必要に応じて予測位置姿勢および可動物体指示情報を可動物体の数だけ持つ。そしてさらに干渉データレコードには、図９に示されるように、可動物体を識別するための識別情報を格納するフィールド“可動物体”が追加されている。追加された可動物体フィールドは、干渉計算部７０４、干渉データ管理部７０５、干渉データ選択部７０７や干渉計算判断部７０９によって用いられることになる。即ち、可動物体毎に、第１、第２実施形態で説明した干渉計算が実行されることになる。

また、上述した一致限界や同一視閾値は、詳細レベル毎に予め設定されていてもよいし、学習などにより動的に設定されるようにしてもよい。

また、第１実施形態では、全ての干渉計算や干渉データレコードに対する処理に対して、同じ距離関数を用いていたが、これに限られるものではない。より精度の高い距離関数を用いるために、各干渉データレコードにその干渉レコードに対する処理で用いるべき距離関数を指定するようにしてもよい。この様子を図９に示す。図９の干渉データレコードにおいて、“距離関数”のフィールドには、距離関数として用いるべき関数を特定する情報が含まれている。

以上のように、上記各実施形態によれば、過去の計算結果を有効に活用することができ、計算資源をより詳細な干渉計算に利用することができる。その結果、リアルタイム性が要求される自由動的干渉チェックを行う際に、干渉結果の提示速度を高めると共に、詳細な干渉チェックを行える、という利点がある。

以上、実施形態を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能である。具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。

尚、本発明は、ソフトウェアのプログラムをシステム或いは装置に直接或いは遠隔から供給し、そのシステム或いは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによって前述した実施形態の機能が達成される場合を含む。この場合、供給されるプログラムは実施形態で図に示したフローチャートに対応したプログラムである。

従って、本発明の機能処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、本発明は、本発明の機能処理を実現するためのコンピュータプログラム自体も含まれる。

その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等の形態であっても良い。

プログラムを供給するための記録媒体としては以下が挙げられる。例えば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−Ｒ）などである。

その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続し、該ホームページから本発明のコンピュータプログラムをハードディスク等の記録媒体にダウンロードすることが挙げられる。この場合、ダウンロードされるプログラムは、圧縮され自動インストール機能を含むファイルであってもよい。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明に含まれるものである。

また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布するという形態をとることもできる。この場合、所定の条件をクリアしたユーザに、インターネットを介してホームページから暗号を解く鍵情報をダウンロードさせ、その鍵情報を使用して暗号化されたプログラムを実行し、プログラムをコンピュータにインストールさせるようにもできる。

また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどとの協働で実施形態の機能が実現されてもよい。この場合、ＯＳなどが、実際の処理の一部または全部を行ない、その処理によって前述した実施形態の機能が実現される。

さらに、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれて前述の実施形態の機能の一部或いは全てが実現されてもよい。この場合、機能拡張ボードや機能拡張ユニットにプログラムが書き込まれた後、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行なう。

第１実施形態による干渉計算装置の構成を示すブロック図である。 第１実施形態の干渉計算で用いる干渉計算用データの構成例を示す図である。 第１実施形態の干渉計算で干渉データレコードを説明する図である。 実施形態の干渉計算における詳細度を説明する図である。 実施形態の干渉計算で用いられる距離関数を説明する図である。 第１実施形態の干渉データ選択部の動作を表したフローチャートである。 第２実施形態による干渉計算装置の構成を示すブロック図である。 第２実施形態における干渉計算用データの構成を表した図である。 第２実施形態における干渉データレコードを説明する図である。 実施形態による干渉計算処理を説明するフローチャートである。

Claims (14)

1. ３次元空間における可動物体と他の物体との間の干渉計算を実行する干渉計算装置であって、
   前記可動物体の検出された位置姿勢に基づいて、前記可動物体と前記他の物体との間の干渉計算を実行する干渉計算手段と、
   前記可動物体の前記他の物体に対する相対位置姿勢と、当該相対位置姿勢に対する前記干渉計算手段による干渉計算の結果とが記録された、複数の干渉データレコードを格納する干渉データ記憶手段と、
   前記可動物体の新たに検出された位置姿勢に基づいて得られた、前記可動物体の前記他の物体に対する新たな相対位置姿勢と、前記複数の干渉データレコードの各々に記録されている相対位置姿勢との差異の大きさを算出する算出手段と、
   前記複数の干渉データレコードに前記算出手段で算出された差異の大きさが所定範囲内で且つ最小となる干渉データレコードを選択し、選択された干渉データレコードに記録されている干渉計算の結果を、前記新たに検出された位置姿勢に関する干渉計算の結果として出力する干渉データ選択手段とを備えることを特徴とする干渉計算装置。
2. 前記選択された干渉データレコードに基づいて、前記新たに検出された位置姿勢による干渉計算を前記干渉計算手段に実行させるか否か、または実行させるべき干渉計算の種類を判断する干渉計算判断手段を更に備えることを特徴とする請求項１に記載の干渉計算装置。
3. 前記干渉計算手段の前記新たに検出された位置姿勢に対する干渉計算の結果を用いて、前記干渉データ記憶手段に格納されている干渉データレコードを更新する干渉データ管理手段を更に備えることを特徴とする請求項１又は２に記載の干渉計算装置。
4. 前記可動物体の位置姿勢の検出信号を受信する受信手段を更に備え、
   前記新たに検出された位置姿勢は、前記受信手段によって受信された前記可動物体の最新の位置姿勢であることを特徴とする請求項１乃至３の何れか１項に記載の干渉計算装置。
5. 前記可動物体の位置姿勢の検出信号を受信する受信手段と、
   前記受信手段で受信した最新および過去の前記可動物体の位置姿勢から前記可動物体の位置姿勢を予測する位置姿勢予測手段とを更に備え、
   前記新たに検出された位置姿勢は、前記位置姿勢予測手段により予測された位置姿勢であることを特徴とする請求項１乃至３の何れか１項に記載の干渉計算装置。
6. 干渉計算の対象となる可動物体をユーザに指示させるインターフェース手段を更に備え、
   前記複数の干渉データレコードの各々は、可動物体を識別する識別情報を含み、
   前記干渉データ選択手段は、指定された可動物体を前記識別情報として含む干渉データレコードの中から、前記算出手段で算出された差異の大きさが前記所定範囲内で且つ最小となる干渉データレコードを選択することを特徴とする請求項１乃至５の何れか１項に記載の干渉計算装置。
7. 前記複数の干渉データレコードの各々は、干渉計算の結果が同一であるとみなしてもよいかどうかを判定するための、相対位置姿勢の差異の大きさに関する閾値を更に含み、
   前記データ選択手段は、前記算出手段で算出された差異の大きさと前記閾値との比較により、差異の大きさが前記所定範囲内である干渉データレコードを選択することを特徴とする請求項１乃至６の何れか１項に記載の干渉計算装置。
8. 前記複数の干渉データレコードの各々は、干渉計算結果を新たな干渉データレコードとして追加するか否かを判定するための、相対位置姿勢に関する差異の大きさの閾値を更に含み、
   前記干渉データ管理手段は、前記新たな相対位置姿勢に関して前記算出手段で算出された差異の大きさと前記選択された干渉レコードに含まれる閾値との比較により、前記干渉計算手段による前記新たに検出された位置姿勢についての干渉計算の結果に基づく新たな干渉データレコードを前記干渉データ記憶手段に格納するか否かを判断することを特徴とする請求項３に記載の干渉計算装置。
9. 前記複数の干渉データレコードの各々は、前記算出手段で用いるべき距離関数を特定する情報を更に含み、
   前記算出手段は、前記可動物体の前記他の物体に対する新たな相対位置姿勢と、前記複数の干渉データレコードの各々に記録されている相対位置姿勢との間の差異の大きさを、当該干渉データレコードによって特定される距離関数を用いて算出することを特徴とする請求項１乃至８の何れか１項に記載の干渉計算装置。
10. 前記干渉データレコードは干渉計算の詳細度を表す詳細レベルを更に含み、
    前記干渉計算判断手段は、前記新たに検出された位置姿勢に関して、前記干渉データ選択手段が選択した干渉データレコードの詳細レベルよりも高い詳細レベルの干渉計算を前記干渉計算手段に実行させることを特徴とする請求項２に記載の干渉計算装置。
11. 前記干渉計算判断手段は、前記干渉データ選択手段が選択した干渉データレコードが干渉部分のないことを示す場合、前記干渉計算における前記新たに検出された位置姿勢による干渉計算の実行を禁止することを特徴とする請求項２に記載の干渉計算装置。
12. 前記干渉データレコードは干渉計算の詳細度を表す詳細レベルを更に含み、
    前記干渉計算手段は、新たな干渉計算の必要が発生したときに別の干渉計算を実行中であった場合に、前記別の干渉計算の詳細レベルが前記新たな干渉計算の詳細レベルよりも高い場合には、前記別の干渉計算を打ち切り、
    前記別の干渉計算の詳細レベルが前記新たな干渉計算の詳細レベルと等しいか低い場合には、前記別の干渉計算が終了してから前記新たな干渉計算を実行することを特徴とする請求項２に記載の干渉計算装置。
13. ３次元空間における可動物体と他の物体との間の干渉計算を実行する干渉計算装置による干渉計算方法であって、
    前記干渉計算装置の干渉計算手段が、前記可動物体の検出された位置姿勢に基づいて、前記可動物体と前記他の物体との間の干渉計算を実行する干渉計算工程と、
    前記干渉計算装置の干渉データ記憶手段が、前記可動物体の前記他の物体に対する相対位置姿勢と、当該相対位置姿勢に対する前記干渉計算工程による干渉計算の結果とが記録された、複数の干渉データレコードを格納する干渉データ記憶工程と、
    前記干渉計算装置の算出手段が、前記可動物体の新たに検出された位置姿勢に基づいて得られた、前記可動物体の前記他の物体に対する新たな相対位置姿勢と、前記複数の干渉データレコードの各々に記録されている相対位置姿勢との差異の大きさを算出する算出工程と、
    前記干渉計算装置の干渉データ選択手段が、前記算出工程で算出された差異の大きさが所定範囲内で且つ最小となる干渉データレコードを選択し、選択された干渉データレコードに記録されている干渉計算の結果を、前記新たに検出された位置姿勢に関する干渉計算の結果として出力する干渉データ選択工程とを有することを特徴とする干渉計算装置の制御方法。
14. コンピュータを、請求項１乃至１２のいずれか１項に記載の干渉計算装置の各手段として機能させることを特徴とするコンピュータプログラム。

Images