(57)【特許請求の範囲】
【請求項１】
複数の物体のうちの面取りされた第１の物体の表面の形状を示す複数の多角形のうちの一部の多角形を判定対象の多角形として選択する選択部と、
前記選択された判定対象の多角形を包含する閉曲面であって、前記判定対象の多角形に対応する或る点又は前記判定対象の多角形に対応する第１の線分との距離が一定である閉曲面と、前記複数の物体のうちの第２の物体の表面の形状を示す第２の線分との干渉を前記距離に基づいて判定する判定部と、
を備える干渉判定装置。
【請求項２】
前記第２の線分とは、前記第２の物体の表面の形状を示す複数の多角形のうちの１つの多角形の１つの辺である
請求項１に記載の干渉判定装置。
【請求項３】
前記判定対象の多角形の形状に基づいて、前記或る点との距離が一定である閉曲面と、前記第１の線分との距離が一定である閉曲面とのいずれか一方を、前記判定対象の多角形を包含する閉曲面として設定する閉曲面設定部、
を備える請求項１又は２に記載の干渉判定装置。
【請求項４】
前記閉曲面設定部は、前記距離を表す近接判定値に基づいて、前記或る点との距離が一定である閉曲面と、前記第１の線分との距離が一定である閉曲面とのいずれか一方を、前記判定対象の多角形を包含する閉曲面として設定する
請求項３に記載の干渉判定装置。
【請求項５】
前記選択部は、複数の物体のうちの第１の物体の表面の形状を示す複数の多角形のうち、前記判定部による前記干渉の判定に用いられた前記閉曲面に包含されていない多角形を、前記判定対象の多角形として選択する
請求項１から４のいずれか一項に記載の干渉判定装置。
【請求項６】
前記第１の物体の表面の形状を示す複数の多角形のうちの一部の多角形を、前記距離に基づいて複数の多角形に分割する分割部
を備え、
前記選択部は、前記分割部による分割後の複数の多角形のうちの少なくとも１つの多角形を、前記判定対象の多角形として選択する
請求項１から５のいずれか一項に記載の干渉判定装置。
【請求項７】
前記分割部は、前記第１の物体の表面の形状を示す複数の多角形のうちの一部の多角形を複数の多角形に分割するか否かを、前記距離に基づいて判定する
請求項６に記載の干渉判定装置。
【請求項８】
前記分割部は、前記第１の物体の表面の形状を示す複数の多角形のうちの一部の多角形を、前記距離に基づいて２つから５つの多角形に分割する
請求項６又は７に記載の干渉判定装置。
【請求項９】
前記分割部による分割前の複数の多角形のうちの一部の多角形とは、三角形であり、
前記分割部は、前記分割前の多角形のうちの一部の三角形を、当該三角形の１つの中線により前記分割後の複数の多角形としての２つの三角形に分割する
請求項６から８のいずれか一項に記載の干渉判定装置。
【請求項１０】
前記判定部は、前記或る点又は前記第１の線分と前記閉曲面との距離、及び前記或る点又は前記第１の線分と前記第２の線分との距離の比較に基づいて前記干渉を判定する
請求項１から９のいずれか一項に記載の干渉判定装置。
【請求項１１】
選択部が、複数の物体のうちの面取りされた第１の物体の表面の形状を示す複数の多角形のうちの一部の多角形を判定対象として選択する選択過程と、
判定部が、前記選択された判定対象の多角形を包含する閉曲面であって、前記判定対象の多角形に対応する或る点又は前記判定対象の多角形に対応する第１の線分との距離が一定である閉曲面と、前記複数の物体のうちの第２の物体の表面の形状を示す第２の線分との干渉を前記距離に基づいて判定する判定過程と、
を有する干渉判定方法。
【請求項１２】
コンピュータに、
複数の物体のうちの面取りされた第１の物体の表面の形状を示す複数の多角形のうちの一部の多角形を判定対象として選択する選択手順と、
前記選択された判定対象の多角形を包含する閉曲面であって、前記判定対象の多角形に対応する或る点又は前記判定対象の多角形に対応する第１の線分との距離が一定である閉曲面と、前記複数の物体のうちの第２の物体の表面の形状を示す第２の線分との干渉を前記距離に基づいて判定する判定手順と、
を実行させるための干渉判定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、干渉判定装置、干渉判定方法、及び干渉判定プログラムに関する。
【背景技術】
【０００２】
従来、３次元仮想空間内に複数の物体を配置して、当該物体同士の干渉や近接の検証を行うシミュレーションが行われている。なお、本明細書において、干渉とは複数の物体が同じ空間を占有することであり、近接とは複数の物体が所定距離以内まで接近することである。このような干渉や近接の検証は、設備やロボットなどの間での衝突の防止の他、機械による物体の把持の判定、光センサーの判定など幅広い用途に用いられている。
【０００３】
３次元仮想空間内の物体の表面の形状は、三角形などの多角形（ポリゴン）を繋ぎ合わせることで表現されることがある。このような物体同士の干渉を判定する方法の１つは、一方の物体の表面の形状を示す多角形と、もう一方の物体の表面の形状を示す多角形の辺とが交差するか否かという幾何学的計算を行うことである。また、その他にも物体間の干渉をより高速に判定するための技術が開示されている（特許文献１）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−２５０１２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の技術では、物体同士の干渉や近接の判定に要する計算量が多い場合があった。例えば、三角形を繋ぎ合わせて曲面を表現する場合、その精密さを高めれば高めるほど、必要な三角形の数は飛躍的に増加する。そのため、上記のような幾何学的な計算を用いて干渉や近接の判定を行うと、その計算量は膨大となってしまう。このように、複数の物体間の干渉や近接を少ない計算量で判定することができない場合があった。
【０００６】
本発明は上記の点に鑑みてなされたものであり、複数の物体間の干渉や近接を少ない計算量で判定する干渉判定装置、干渉判定方法、及び干渉判定プログラムを提供する。
【課題を解決するための手段】
【０００７】
本発明は上記の課題を解決するためになされたものであり、本発明の一態様は、複数の物体のうちの第１の物体の表面の形状を示す複数の多角形のうち、少なくとも１つの多角形を判定対象の多角形として選択する選択部と、前記選択された判定対象の多角形を包含する閉曲面であって、前記判定対象の多角形に対応する或る点又は前記判定対象の多角形に対応する第１の線分との距離が一定である閉曲面と、前記複数の物体のうちの第２の物体の表面の形状を示す第２の線分との干渉を前記距離に基づいて判定する判定部と、を備える干渉判定装置である。
【０００８】
また、本発明の一態様は、上記の干渉判定装置において、前記第２の線分とは、前記第２の物体の表面の形状を示す複数の多角形のうちの１つの多角形の１つの辺である。
【０００９】
また、本発明の一態様は、上記の干渉判定装置において、前記判定対象の多角形のうちの少なくとも１つの多角形が三角形である。
【００１０】
また、本発明の一態様は、上記の干渉判定装置において、前記第１の線分とは、前記判定対象の三角形の３辺のうちの２辺各々の中点を通る線分である。
【００１１】
また、本発明の一態様は、上記の干渉判定装置において、前記第１の線分の長さは、前記判定対象の三角形の１つの辺の長さである。
【００１２】
また、本発明の一態様は、上記の干渉判定装置において、前記或る点とは、前記判定対象の三角形の外心である。
【００１３】
また、本発明の一態様は、上記の干渉判定装置において、前記選択部は、複数の物体のうちの第１の物体の表面の形状を示す複数の多角形のうち、前記判定部が前記第２の線分との干渉を判定するための前記閉曲面としての第１の閉曲面に包含されない少なくとも１つの多角形を、前記判定対象の多角形として選択し、前記判定部は、前記閉曲面としての第２の閉曲面と前記第２の線分との干渉を判定する。
【００１４】
また、本発明の一態様は、上記の干渉判定装置において、前記第１の物体の表面の形状を示す複数の多角形のうちの少なくとも１つの多角形を、前記距離に基づいて複数の多角形に分割する分割部を備え、前記選択部は、前記分割部による分割後の複数の多角形のうちの少なくとも１つの多角形を、前記判定対象として選択する。
【００１５】
また、本発明の一態様は、上記の干渉判定装置において、前記分割部は、前記第１の物体の表面の形状を示す複数の多角形のうちの少なくとも１つの多角形を、前記距離に基づいて２つから５つの多角形に分割する。
【００１６】
また、本発明の一態様は、上記の干渉判定装置において、前記分割部による分割前の複数の多角形のうちの少なくとも１つの多角形とは、三角形であり、前記分割部は、前記分割前の多角形のうちの少なくとも１つの三角形を、当該三角形の１つの中線により前記分割後の複数の多角形としての２つの三角形に分割する。
【００１７】
また、本発明の一態様は、上記の干渉判定装置において、前記判定部は、前記或る点又は前記第１の線分と前記閉曲面との距離、及び前記或る点又は前記第１の線分と前記第２の線分との距離の比較に基づいて前記干渉を判定する。
【００１８】
また、本発明の一態様は、選択部が、複数の物体のうちの第１の物体の表面の形状を示す複数の多角形のうちの少なくとも１つの多角形を判定対象として選択する選択過程と、判定部が、前記選択された判定対象の多角形を包含する閉曲面であって、前記判定対象の多角形に対応する或る点又は前記判定対象の多角形に対応する第１の線分との距離が一定である閉曲面と、前記複数の物体のうちの第２の物体の表面の形状を示す第２の線分との干渉を前記距離に基づいて判定する判定過程と、を有する干渉判定方法である。
【００１９】
また、本発明の一態様は、コンピュータに、複数の物体のうちの第１の物体の表面の形状を示す複数の多角形のうちの少なくとも１つの多角形を判定対象として選択する選択手順と、前記選択された判定対象の多角形を包含する閉曲面であって、前記判定対象の多角形に対応する或る点又は前記判定対象の多角形に対応する第１の線分との距離が一定である閉曲面と、前記複数の物体のうちの第２の物体の表面の形状を示す第２の線分との干渉を前記距離に基づいて判定する判定手順と、を実行させるための干渉判定プログラムである。
【発明の効果】
【００２０】
本発明によれば、複数の物体間の干渉や近接を少ない計算量で判定することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施形態に係る干渉判定装置の使用環境の一例を説明する概要図である。
【図２】第１の実施形態に係る干渉判定装置の機能構成の一例を示すブロック図である。
【図３】第１の実施形態に係る干渉判定装置が行う干渉の判定の処理の一例を示すフローチャートである。
【図４】第１の実施形態に係る三次元仮想空間内の物体の表面の形状を示す判定対象の三角形を包含する閉曲面の一例を示す模式図である。
【図５】第１の実施形態に係る判定部の閉曲面設定部が判定対象の多角形に閉曲面を設定する処理の一例を示すフローチャートである。
【図６】本発明の第２の実施形態に係る干渉判定装置の機能構成の一例を示すブロック図である。
【図７】第２の実施形態に係る三次元仮想空間内の物体の表面の形状を示す判定対象の多角形の分割方法の一例を示す模式図である。
【図８】第２の実施形態に係る干渉判定装置が判定対象の多角形に閉曲面を設定する処理の一例を示すフローチャートである。
【図９】本発明の第３の実施形態に係る干渉判定装置の機能構成の一例を示すブロック図である。
【図１０】第３の実施形態に係る閉曲面設定テーブルの一例を示す表である。
【発明を実施するための形態】
【００２２】
＜第１の実施形態＞
［干渉判定装置の使用環境］
以下、図面を参照しながら本発明の第１の実施形態について詳しく説明する。図１は、本発明の第１の実施形態に係る干渉判定装置１００の使用環境の一例を説明する概要図である。本実施形態における干渉判定装置１００は、製造ラインの設計に係る製造ラインシミュレーターである。干渉判定装置１００が干渉や近接の判定を行う対象は、３次元仮想空間内に製造ラインを再現したポリゴンデータ２００である。例えば、ポリゴンデータ２００には、その表面の形状が多角形（ポリゴン）で表現された製造ラインの各設備やロボット２１０（Ａ）〜２１０（Ｂ）、製品２２０（Ａ）〜２２０（Ｂ）などが仮想空間内に配置された様子が記述されている。干渉判定装置１００は、ポリゴンデータ２００について、仮想空間内に配置されている各物体同士の干渉や近接を判定することで、製造ラインを構成する各要素を正しく動作・移動・配置させることができる。
【００２３】
実際の製造ラインでは、各要素が適切なタイミングで連続して動作したり、移動したりすることが求められる。このような動きのある製造ラインについてのシミュレーションに対して、干渉判定装置１００は、干渉や近接の判定を行う。従って、干渉判定装置１００は、製造ライン３００の各構成要素の配置が適切か否かを判定し、当該構成要素を動作・移動させる制御プログラムが適切か否かを判定することができる。
【００２４】
［構成］
図２は、干渉判定装置１００の機能構成の一例を示すブロック図である。干渉判定装置１００は、ポリゴン取得部１１０と、選択部１２０と、判定部１４０と、出力部１５０とを備える。さらに、判定部１４０は、閉曲面設定部１４２と、干渉演算部１４４と、干渉判定部１４６と、を備える。なお、図示はしていないが、干渉判定装置１００は、コンピュータが一般的に備えるＣＰＵ（Central  Processing  Unit）や記憶部、入力部、出力部などを備えている。近接判定値４００は、記憶部に格納されており、判定部１４０の処理に使用される。
【００２５】
干渉判定装置１００の各機能部は、例えば、干渉判定装置１００が備えるＣＰＵが記憶部に格納されたプログラムを実行することにより機能するソフトウェア機能部である。また、これらの機能部の一部又は全部は、ＬＳＩ（Large  Scale  Integration）やＡＳＩＣ（Application  Specific  Integrated  Circuit）等のハードウェア機能部であってもよい。記憶部は、例えば、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリ、レジスタなどであり、ＨＤＤ（Hard  Disk  Drive）などのドライブ装置や外部メモリなどであってもよい。記憶部には、近接判定値４００の他、各機能部の処理結果や処理の途中で生じる一時的なデータ、ＣＰＵによって実行されるプログラムなどが記憶される。
【００２６】
［処理の概要］
以下、各機能ブロックによる処理の概要を示す。ポリゴン取得部１１０は、３次元空間内にポリゴンで表現される複数の物体が配置されたポリゴンデータ２０２を取得し、選択部１２０に出力する。選択部１２０は、ポリゴン取得部１１０から入力されたポリゴンデータに記述されている複数の物体から、干渉や近接の判定を行う２つの物体を選択する。次に、選択部１２０は、選択した２つの物体のうちの１つの物体（第１の物体）の表面の形状を示す複数の多角形のうち、少なくとも１つの多角形を判定対象の多角形として選択する。すなわち、選択部１２０は、複数の物体のうちの第１の物体の表面の形状を示す複数の多角形のうち、少なくとも１つの多角形を判定対象の多角形として選択する。そして、選択部１２０は、選択した判定対象の多角形を示す情報を判定部１４０の閉曲面設定部１４２に出力する。また、選択部１２０は、干渉や近接の判定を行う２つの物体のうちのもう１つの物体（第２の物体）から、その表面の形状を示す線分（第２の線分）を選択し、当該第２の線分を示す情報を判定部１４０の干渉演算部１４４に出力する。
【００２７】
なお、判定対象の多角形を示す情報とは、例えば、当該多角形に固有に定められた識別子（後述）や当該多角形の頂点の座標などである。また、第２の線分とは、例えば、第２の物体の表面の形状を示す稜線である。また、第２の線分を示す情報とは、例えば、当該線分の２つの端点の座標である。
【００２８】
閉曲面設定部１４２は、まず、選択部１２０から判定対象の多角形を示す情報と、記憶部に格納されている近接判定値４００とを取得する。次に、閉曲面設定部１４２は、選択された判定対象の多角形を包含する閉曲面を設定する。また、この閉曲面は、当該閉曲面と判定対象の多角形に対応する点又は判定対象の多角形に対応する線分（第１の線分）との距離が近接判定値４００が示す距離になるように設定される。すなわち、判定部１４０の閉曲面設定部１４２は、選択された判定対象の多角形を包含する閉曲面であって、判定対象の多角形に対応する或る点又は判定対象の多角形に対応する第１の線分との距離が一定である閉曲面を設定する。そして、閉曲面設定部１４２は、設定した閉曲面を示す情報を干渉演算部１４４に出力する。ここで、閉曲面を示す情報とは、例えば、当該閉曲面の中心に位置する或る点の座標や、当該閉曲面の中心に位置する第１の線分の２つの端点の座標などである。
【００２９】
干渉演算部１４４は、選択部１２０から第２の線分を示す情報と、閉曲面設定部１４２から閉曲面を示す情報とを取得する。次に、干渉演算部１４４は、第２の線分と判定対象の多角形に対応する或る点又は第１の線分との距離を算出する。干渉演算部１４４は、算出した距離を干渉判定部１４６に出力する。
【００３０】
干渉判定部１４６は、干渉演算部１４４から干渉演算部１４４が算出した距離を取得し、記憶部から近接判定値４００を取得する。次に、干渉判定部１４６は、干渉演算部１４４により算出された距離と近接判定値４００が示す距離とを比較する。そして、干渉判定部１４６は、算出された距離が近接判定値４００が示す距離以下であれば、判定対象の三角形に対応する閉曲面と第２の線分とが「干渉する」と判定する。算出された距離が近接判定値４００が示す距離より大きければ、干渉判定部１４６は、判定対象の三角形に対応する閉曲面と第２の線分とが「干渉しない」と判定する。
【００３１】
すなわち、判定部１４０は、選択された判定対象の多角形を包含する閉曲面であって、判定対象の多角形に対応する或る点又は判定対象の多角形に対応する第１の線分との距離が一定である閉曲面と、複数の物体のうちの第２の物体の表面の形状を示す第２の線分との干渉を近接判定値４００が示す距離に基づいて判定する。また、判定部１４０は、或る点又は第１の線分と閉曲面との距離、及び或る点又は第１の線分と第２の線分との距離の比較に基づいて干渉を判定する。干渉判定部１４６は、判定結果を出力部１５０に出力する。
【００３２】
出力部１５０は、干渉判定部１４６から判定結果を取得する。出力部１５０は、取得した判定結果に基づいて、干渉を示した物体やその部品を報知するための情報を生成し、出力する。或いは、出力部１５０は、干渉しないことを報知するための情報を生成し、出力する。出力部１５０は、例えば、液晶ディスプレイや有機ＥＬ（Electroluminescence）ディスプレイなどを備え、視覚的に上記判定結果を表示してもよい。
【００３３】
なお、ポリゴン取得部１１０が取得するポリゴンデータ２０２は、例えば、ＣＡＤ（Computer  aided  design、コンピュータ支援設計）システムやＣＡＭ（Computer  aided  manufacturing、コンピュータ支援製造）システムなどによって用意されるが、そのデータ構造は、特定の形式に限定されない。また、ポリゴンデータ内で記述される物体の表面の形状を示す多角形の頂点の数は、特定の数に限定されない。本発明は、当該多角形が四角形や五角形などであったとしても適用することができるが、以下では、当該多角形が三角形である場合について説明する。すなわち、判定対象の多角形のうちの少なくとも１つの多角形が三角形である。
【００３４】
また、ポリゴンデータ２０２において、例えば、個々の物体やその表面の形状を示す複数の多角形各々、或いは当該多角形の辺や頂点などには、それぞれを示す識別子が割り当てられている。従って、干渉判定装置１００各機能部は、各物体やその一部を識別し、選択することや座標を取得することができる。また、ポリゴン取得部１１０が、ポリゴンデータ２０２を取得した後で、上記のような識別子の割り当てを行ってもよい。また、干渉判定装置１００は、多角形以外で表現される、例えば、自由曲面で表現される物体のデータを、ポリゴンによる表現に変換する機能を有していてもよい。また、干渉判定装置１００は、ＣＡＤシステムやＣＡＭシステムを備え、装置内でポリゴンデータ２０２や干渉の判定結果の授受を行い、ポリゴンデータ２０２の内容を変更してもよい。
【００３５】
また、第２の線分は、第２の物体の表面の形状を示すものであればよい。従って、第２の線分は、例えば、第２の物体の表面の形状を示す三角形について、当該三角形の内部或いは近傍に位置する２つの点を結んだ線分であったり、当該三角形の中点を結んだ線分であったりしてもよい。
【００３６】
［具体的な処理の流れ］
以下、干渉判定装置１００が行う具体的な処理の一例について説明する。図３は、干渉判定装置１００による干渉の判定の処理の一例を示すフローチャートである。
（ステップＳ３００）まず、ポリゴン取得部１１０は、ポリゴンデータ２０２を取得し、選択部１２０に出力する。
（ステップＳ３０２）次に、選択部１２０は、ポリゴン取得部１１０から入力されたポリゴンデータに記述されている複数の物体から、干渉や近接の判定を行う対象としての２つの物体の第１の物体と第２の物体とを選択する。
（ステップＳ３０４）次に、選択部１２０は、第１の物体について、その表面の形状を示す複数の三角形のうちの１つの三角形を判定対象として選択する。選択部１２０は、選択した判定対象の三角形の３つの頂点の座標を閉曲面設定部１４２に出力する。この判定対象の三角形の３つの頂点の座標とは、上記の判定対象の多角形を示す情報の一例である。
【００３７】
（ステップＳ３０６）次に、閉曲面設定部１４２は、選択部から入力された判定対象の三角形の３つの頂点の座標と、記憶部から取得した近接判定値４００とに基づいて、閉曲面を設定する。閉曲面の設定については、後述する。そして、閉曲面設定部１４２は、設定した閉曲面の中心に位置する点の座標又は第１の線分の２つの端点の座標を干渉演算部１４４に出力する。これら閉曲面の中心に位置する点の座標又は第１の線分の２つの端点の座標とは、上記の閉曲面を示す情報の一例である。
【００３８】
（ステップＳ３０８）次に、選択部１２０は、第２の物体の稜線の１つを第２の線分として選択する。すなわち、この一例において、第２の線分とは、第２の物体の表面の形状を示す複数の多角形のうちの１つの多角形の１つの辺である。そして、選択部１２０は、選択した第２の線分の２つの端点の座標を干渉演算部１４４に出力する。この第２の線分の２つの端点の座標とは、上記の第２の線分を示す情報の一例である。
【００３９】
（ステップＳ３１０）次に、干渉演算部１４４は、選択部１２０から入力された第２の線分を示す情報と、閉曲面設定部１４２から入力された閉曲面を示す情報とに基づいて、第２の線分と閉曲面の中心に位置する或る点又は第１の線分との距離を算出する。当該距離の算出については、後述する。干渉演算部１４４は、算出した第２の線分と閉曲面との距離を干渉判定部１４６に出力する。
【００４０】
（ステップＳ３１２）次に、干渉判定部１４６は、近接判定値４００が示す距離と干渉演算部１４４が算出した距離との比較を行う。干渉演算部１４４が算出した距離が近接判定値４００が示す距離以下のとき（ステップＳ３１２；ＹＥＳ）、干渉判定部１４６は、判定対象の三角形と第２の線分は干渉すると判定し、出力部１５０に判定結果を出力する。その後、ステップＳ３１４に遷移する。干渉演算部１４４が算出した距離が近接判定値４００が示す距離より大きいとき（ステップＳ３１２；ＮＯ）、干渉判定部１４６は、判定対象の三角形と第２の線分は干渉しないと判定し、ステップＳ３１６に遷移する。
【００４１】
（ステップＳ３１４）次に、出力部１５０は、干渉判定部１４６の判定結果に基づいて、干渉があることを示す情報を出力する。当該情報は、例えば、判定対象の三角形や第２の線分の識別子や座標を含んでもよく、干渉演算部１４４が算出した閉曲面の中心と第２の線分との距離などの干渉の程度を示す情報を含んでもよい。
（ステップＳ３１６）次に、選択部１２０は、第２の物体の表面の形状を示すすべての稜線について、第１の物体の判定対象の三角形と干渉を調べたかを確認する。第２の表面の形状を示すすべての稜線について調べているとき（ステップＳ３１６；ＹＥＳ）、ステップＳ３１８に遷移する。第２の物体の表面の形状を示すすべての稜線について調べていないとき（ステップＳ３１６；ＮＯ）、ステップＳ３０８に戻る。
【００４２】
（ステップＳ３１８）次に、選択部１２０は、第１の物体の表面の形状を示すすべての三角形について、第２の物体との干渉を調べたか否かを確認する。第１の物体の表面の形状を示すすべての三角形について干渉を調べているとき（ステップＳ３１８；ＹＥＳ）、ステップＳ３２０に遷移する。第１の物体の表面の形状を示すすべての三角形について干渉を調べていないとき（ステップＳ３１８；ＮＯ）、ステップＳ３０４に戻る。
（ステップＳ３２０）出力部１５０は、干渉判定部１４６の判定結果に基づいて、干渉がないことを報知する情報を出力する。
【００４３】
なお、上記のフローチャートには図示していないが、ステップＳ３０６において、閉曲面設定部１４２が判定対象の三角形に対して閉曲面を設定しなかった場合、干渉演算部１４４は、従来技術に則って、当該三角形と第２の線分との交差を計算する。これについても、詳しくは後述する。また、上記のフローチャートは、仮想空間内に配置された複数の物体のうちの２つの物体についての干渉を調べる場合について記述している。仮想空間内の構成要素全体について干渉の判定を行う場合は、判定対象とする２つの物体の組み合わせを網羅的に選択し、各組み合わせで干渉を判定すればよい。この場合、干渉が検出されるたびに判定結果を出力してもよいし、すべての構成要素について干渉を判定してから、まとめて判定結果を出力してもよい。
【００４４】
また、構成要素を動かす制御プログラムのテストを行う場合は、まず、例えば、制御プログラムの指示に従って、ポリゴンデータ２０２の内容を更新し、仮想空間内の構成要素を動かす。次に、干渉判定装置１００は、上記の処理により第１の物体と第２の物体を選択し、当該物体同士の干渉や近接を判定する。このように、ポリゴンデータ２０２の更新と干渉や近接の判定を繰り返すことで、制御プログラムのテストを行うことができる。
【００４５】
［閉曲面の設定］
以下、閉曲面の設定について詳述する。図４は、三次元仮想空間内の物体の表面の形状を示す判定対象の三角形を包含する閉曲面の一例を示す模式図である。図４において示されているｘ軸ｙ軸ｚ軸は、それぞれ直交する３次元仮想空間の座標を示す軸である。図４（ａ）及び（ｂ）の模式図は、それぞれｚ軸方向から見たものであり、本例では、三角形２３０の法線と三角形２４０の法線とは、ｚ軸方向にそれぞれ一致している。ｄは近接判定値４００によって示される距離である。図４（ａ）は、判定対象の三角形を包含する閉曲面が球型であるときを示している。ｄ２は判定対象の三角形の外接円の半径の大きさである。図４（ｂ）は、判定対象の三角形を包含する閉曲面がカプセル型であるときを示している。ｄ３は、判定対象の三角形の最も長い辺（最長辺）の端点ではない頂点から最長辺に下ろした垂線の長さである。ただし、三角形が最長辺を２つ以上持つときは、そのいずれか１つを最長辺とする。
【００４６】
図４（ａ）において、判定対象の三角形２３０は、判定対象の三角形の外接円の半径の大きさｄ２が近接判定値４００によって示される距離ｄ以下（ｄ２≦ｄ）である三角形である。当該三角形２３０を包含する閉曲面２３４は、当該三角形２３０の外心２３２からの距離がｄとなるように設定される球型の閉曲面である。すなわち、この一例において、或る点とは、判定対象の三角形２３０の外心である。
【００４７】
なお、以下においては、判定対象の三角形に対応する或る点とは、三角形の外心であるとして説明するが、当該或る点は三角形の外心でなくてもよく、例えば、垂心や重心などであってもよい。また、判定対象の三角形に対応する或る点は、当該三角形と同一平面上になくてもよい。ただし、近接判定値４００が同一の条件で、判定対象の三角形に対応する或る点が外心である閉曲面は、他の方法で設定される球型の閉曲面よりも多様な形状の三角形を包含できるため、計算量をさらに低減することができる。
【００４８】
図４（ｂ）において、判定対象の三角形２４０は、判定対象の三角形の最長辺の端点ではない頂点から最長辺に下ろした垂線の長さｄ３が近接判定値４００によって示される距離ｄの２倍以下（ｄ３≦２×ｄ）である三角形である。当該三角形２４０に対応する第１の線分２４２は、当該三角形２４０の最長辺以外の２辺それぞれの中点を通る線分である。また、第１の線分２４２の長さは、当該三角形２４０の最長辺の長さである。また、第１の線分２４２の中点は、当該三角形２４０の最長辺の垂直２等分線上に存在する。そして、判定対象の三角形２４０を包含する閉曲面２４４は、第１の線分２４２からの距離がｄとなるように設定されるカプセル型の閉曲面である。すなわち、この一例において、第１の線分２４２とは、判定対象の三角形２４０の３辺のうちの２辺各々の中点を通る線分である。また、この一例において、第１の線分２４２の長さは、判定対象の三角形２４０の１つの辺の長さである。
【００４９】
なお、以下においては、第１の線分は、判定対象の三角形２４０の３辺のうちの２辺各々の中点を通る線分であり、その長さが判定対象の三角形２４０の最長辺の長さの線分であるとして説明するが、判定対象の三角形に対応する第１の線分は上記の通りでなくてもよく、例えば、最長辺と別の一辺それぞれの中点を結ぶ線分であってもよい。また、第１の線分は、例えば、上述の図４（ｂ）の例のものよりも長い線分であってもよい。また、第１の線分は、判定対象の三角形と同一平面上になくてもよい。ただし、近接判定値４００が同一の条件で、判定対象の三角形に対応する第１の線分が上述の図４（ｂ）の例のように設定される閉曲面は、他の方法で設定されるカプセル型の閉曲面よりも多様な形状の三角形を包含できるため、計算量をさらに低減することができる。また、当該閉曲面は、過剰に大きくないため、判定対象の三角形の干渉や近接を過大に評価しない。
【００５０】
以下、干渉判定装置１００による閉曲面の設定方法について説明する。この処理は、図３のステップＳ３０６に対応する。図５は、判定部１４０の閉曲面設定部１４２による判定対象の多角形に閉曲面を設定する処理の一例を示すフローチャートである。
（ステップＳ５００）閉曲面設定部１４２は、記憶部から近接判定値４００を取得する。
（ステップＳ５０２）次に、閉曲面設定部１４２は、選択部１２０が選択した判定対象の三角形の各頂点の座標から、当該三角形の外接円の半径の大きさｄ２とを算出する。
【００５１】
（ステップＳ５０４）次に、閉曲面設定部１４２は、近接判定値４００によって示される距離ｄと算出した外接円の半径の大きさｄ２とを比較し、外接円の半径の大きさｄ２が距離ｄ以下（ｄ２≦ｄ）か否かを判定する。ｄ２≦ｄであるとき（ステップＳ５０４；ＹＥＳ）、ステップＳ５０６に遷移する。ｄ２≦ｄではないとき（ステップＳ５０４；ＮＯ）、ステップＳ５０８に遷移する。
（ステップＳ５０６）次に、閉曲面設定部１４２は、判定対象の三角形の頂点の座標から、当該三角形の外心の座標を算出する。そして、閉曲面設定部１４２は、当該三角形の識別子と算出した外心の座標とを対応付けて記憶部に記憶させ、干渉演算部１４４に出力する。
【００５２】
（ステップＳ５０８）次に、閉曲面設定部１４２は、判定対象の三角形の頂点のうちの最長辺の端点ではない頂点から最長辺に下ろした垂線の長さｄ３を算出する。
（ステップＳ５１０）次に、閉曲面設定部１４２は、近接判定値４００によって示される距離ｄとステップＳ５０８で算出した垂線の長さｄ３とを比較し、垂線の長さｄ３が距離ｄの２倍以下（ｄ３≦２×ｄ）か否かを判定する。ｄ３≦２×ｄであるとき（ステップＳ５１０；ＹＥＳ）、ステップＳ５１２に遷移する。ｄ３≦２×ｄではないとき（ステップＳ５１０；ＮＯ）、ステップＳ５１４に遷移する。
【００５３】
（ステップＳ５１２）次に、閉曲面設定部１４２は、最長辺以外の２辺それぞれの中点を通る線分であり、その長さが最長辺の長さであり、その中点が最長辺の垂直２等分線上に存在する線分の２つの端点の座標を算出する。そして、閉曲面設定部１４２は、当該三角形の識別子と算出した線分の２つの端点の座標とを対応付けて記憶部に記憶させ、干渉演算部１４４に出力する。
（ステップＳ５１４）次に、閉曲面設定部１４２は、判定対象の三角形に適する閉曲面はないと判定する。そして、閉曲面設定部１４２は、当該三角形の識別子と閉曲面を設定しないことを示す情報とを対応付けて記憶部に記憶させ、干渉演算部１４４に出力する。
【００５４】
なお、ステップＳ５０２とステップＳ５０４との間に、ステップＳ５０３として、閉曲面設定部１４２は、判定対象の三角形の３つの辺の長さが距離ｄの２倍以下か否かを判定してもよい。不図示のステップＳ５０３において、当該各辺の長さが距離ｄの２倍以下の場合、ステップＳ５０４に遷移する。不図示のステップＳ５０３において、当該各辺の長さが距離ｄの２倍以下ではない場合、ステップＳ５０８に遷移する。このようにすることで、計算量の多い外接円の半径の大きさｄ２の算出処理を避けることができる場合があり、干渉判定装置１００は、計算量をさらに低減することができる。
【００５５】
［干渉演算］
以下、図３のステップＳ３１０における第２の線分と閉曲面の中心に位置する或る点又は第１の線分との距離の算出について説明する。干渉演算部１４４は、閉曲面設定部１４２による処理結果（図３のステップＳ３０６及び図５）に基づいて、以下の３つの計算（ア）〜（ウ）のうちのいずれかを行う。
【００５６】
なお、以下に示す式において、計算の量は、乗除算の回数で示す。これは、コンピュータに数値計算を行わせる場合、加減算に比較して乗除算の負荷は極めて大きいため、計算の量は乗除算の回数で比較されることが多いためである。また、閉曲面と第２の線分との干渉の演算（図３のステップＳ３１０）の前に予め算出可能な値は、記憶部に記憶しておくことにより計算を省略することができるため、計算回数に数えない。このような値には、例えば、第１の線分の長さの２乗や第２の線分の長さの２乗、判定対象の三角形の面積の２倍、近接判定値４００が示す距離の２乗などがある。また、計算の過程で同じ値同士の乗除算が複数回ある場合は、当該乗除算の結果を記憶部に記憶し、計算を省略することができるため、１回の乗除算とみなす。また、以下に示す式では、ベクトルの内積計算を用いるが、各ベクトルは３次元ベクトルであるため、１回の内積計算は３回の乗算に相当する。
【００５７】
また、以下の計算（ア）及び（イ）では、それぞれ、点と線分の距離及び２本の線分間の距離を算出する。干渉判定部１４６は、当該算出された距離と近接判定値４００が示す距離と比較し、当該算出された距離が近接判定値４００が示す距離以下の場合に干渉すると判定する。当該算出された距離が近接判定値４００が示す距離以下ではない場合に干渉しないと判定する。なお、近接判定値４００が示す距離の２乗は予め計算しておくことができるため、上記距離の比較は距離の２乗同士で行う。
【００５８】
（ア）閉曲面設定部１４２が判定対象の三角形に球型の閉曲面を設定したとき（図５のステップＳ５０６）、干渉演算部１４４は、以下の式（１）〜（４）に基づいて、第２の線分と判定対象の三角形の外心との距離を算出する。この演算処理は、点と線分との距離を求めることに相当する。Ｐ０及びＰ１を第２の線分の２つの端点のベクトルとし、Ｑを判定対象の三角形の外心を示すベクトルとする。また、第２の線分のベクトルをＰ１０とする。第２の線分の延長線に点Ｑから下ろした垂線と第２の線分とは直交する。従って、第２の線分のベクトルＰ１０の内分パラメータｔを用いて、当該垂線の足をＰｔとすると、以下の式（１）が成り立つ。
【００５９】
【数１】
0005878907.tif 000002
【００６０】
内分パラメータｔは、式（１）を展開することで得られる以下の式（２）により算出される。
【００６１】
【数２】
0005878907.tif 000003
【００６２】
式（２）のうちのＰ１０・Ｐ１０の値は予め算出しておくことができるため、上述の通り、計算回数に含めない。そのため、内分パラメータｔは、１回の内積計算と１回の除算で算出される。従って、内分パラメータｔの算出に掛かる乗除算の回数は４回である。内分パラメータｔが０より小さいとき（ｔ＜０）、点Ｐｔは第２の線分のベクトルＰ１０上に存在しないため、点Ｑから最も近い点Ｐ０との距離が、点Ｑと第２の線分との距離となる。従って、当該距離の２乗Ｄ２は点ベクトルＱと点ベクトルＰ０との内積であり、この計算に基づく乗除算の回数は３回である。
【００６３】
内分パラメータｔが１より大きいとき（ｔ＞１）、点Ｐｔは第２の線分のベクトルＰ１０上に存在しないため、点Ｑから最も近い点Ｐ１と点Ｑとの距離が点Ｑと第２の線分との距離となる。従って、当該距離の２乗Ｄ２は点ベクトルＱと点ベクトルＰ１との内積であり、この計算に基づく乗除算の回数は３回である。内分パラメータｔが０以上１以下（０≦ｔ≦１）のとき、点Ｐｔは第２の線分上に存在する。点Ｐｔのベクトルは、以下の式（３）で算出される。
【００６４】
【数３】
0005878907.tif 000004
【００６５】
点Ｑと第２の線分との最短距離は、点Ｑから第２の線分に下ろした垂線の長さとなり、当該最短距離の２乗Ｄ２は以下の式（４）で算出される。
【００６６】
【数４】
0005878907.tif 000005
【００６７】
式（３）に基づくＰｔの算出に掛かる乗除算の回数は３回である。また、式（４）に基づく距離の２乗Ｄ２の算出に掛かる乗除算の回数は３回である。従って、（ア）の計算全体に掛かる乗除算の回数は、内分パラメータｔが０以上１以下のときは１０回であり、内分パラメータｔが０より小さい又は１より大きいときは７回である。
【００６８】
（イ）閉曲面設定部１４２が判定対象の三角形にカプセル型の閉曲面を設定したとき（図５のステップＳ５１２）、干渉演算部１４４は、以下の式（５）〜（１３）に基づいて、第２の線分と判定対象の三角形に対応付けられた第１の線分との距離を算出する。この演算処理は、２本の線分間の距離を求めることに相当する。Ｐ０及びＰ１を第２の線分の２つの端点を示すベクトルとし、Ｑ０及びＱ１を第１の線分の２つの端点を示すベクトルとすると、２つの線分の延長線の最短距離を結ぶ線分は、第２の線分のベクトルＰ１０の及び第１の線分のベクトルＱ１０の両方に直交する。従って、第２の線分のベクトルＰ１０の及び第１の線分のベクトルＱ１０について、それぞれの内分パラメータｓ、ｔを用いることにより、以下の式（５）及び（６）が成り立つ。
【００６９】
【数５】
0005878907.tif 000006
【００７０】
この式を展開すると、以下の式（７）及び（８）が得られる。
【００７１】
【数６】
0005878907.tif 000007
【００７２】
従って、内分パラメータｓ、ｔは以下の式（９）及び（１０）で算出される。
【００７３】
【数７】
0005878907.tif 000008
【００７４】
なお、式（９）及び（１０）において、ａ＝Ｐ１０・Ｐ１０、ｂ＝−Ｐ１０・Ｑ１０、ｃ＝（Ｑ０―Ｐ０）・Ｐ１０、ｄ＝Ｐ１０・Ｑ１０、ｅ＝―Ｑ１０・Ｑ１０、ｆ＝（Ｑ０―Ｐ０）・Ｑ１０であり、ａ〜ｆは式（９）及び（１０）の各項に対応している。このうちのａ及びｅは、予め算出しておくことができるため、上述の通り、計算回数に含めない。また、ｂ及びｄは、重複する計算を含むため、上述の通り、合わせて１回の内積計算とする。従って、ａ〜ｆの内積計算は３回であり、ａ〜ｆの算出に掛かる乗除算の回数は９回である。また、式（９）及び（１０）の右辺の分母は重複しているため、上述の通り、式（９）及び（１０）の分母の値の算出は合わせて数える。そのため、式（９）及び（１０）の分母の値の算出に掛かる乗算の回数は、ｂｄ及びａｅの計算に掛かる２回である。従って、式（９）及び（１０）に基づいて行われる計算の乗除算の回数は合わせて５回である。以上より、内分パラメータｓ、ｔの算出にかかる乗除算の回数は、合計１７回である。
【００７５】
次に、干渉演算部１４４は、内分パラメータｓ、ｔの値に応じて異なる計算を行う。内分パラメータｓとｔがともに０より小さい又は１より大きいとき、第１の線分と第２の線分との最短距離はそれぞれの線分の端点同士の距離である。従って、当該最短距離の２乗Ｄ２は、点ベクトル同士の内積計算により算出される。この計算に基づく乗除算の回数は３回である。
【００７６】
内分パラメータｓが０以上１以下且つ、ｔが０より小さい又は１より大きいとき、第１の線分と第２の線分との最短距離は、第１の線分の端点と第２の線分との距離である。従って、上記の計算（ア）と同様の計算を行うことで第１の線分と第２の線分との距離の２乗Ｄ２を求めることができる。この計算に基づく乗除算の回数は、最も多いとき、１０回である。内分パラメータｔが０以上１以下且つ、ｓが０より小さい又は１より大きいときも同様であり、この計算に基づく乗除算の回数は、最も多いとき、１０回である。
【００７７】
内分パラメータｓとｔがともに０以上１以下のとき、干渉演算部１４４は、第１の線分と第２の線分との最短距離を示す線分の両端のベクトルＰｓとＱｔを以下の式（１１）及び（１２）に基づいて算出する。式（１１）及び（１２）の計算の乗除算回数はそれぞれ３回である。
【００７８】
【数８】
0005878907.tif 000009
【００７９】
従って、第１の線分と第２の線分との最短距離の２乗Ｄ２は以下の式（１３）に基づいて算出される。
【００８０】
【数９】
0005878907.tif 000010
【００８１】
式（１３）に基づく距離の２乗Ｄ２の算出に掛かる乗除算の回数は３回である。そのため、内分パラメータｓとｔがともに０以上１以下のとき、式（１１）〜（１３）に基づく計算の乗除算の回数は９回である。従って、（イ）の計算全体に掛かる乗除算の回数は、内分パラメータｓとｔがともに０より小さい又は１より大きいときは、最も多いとき、２０回である。また、内分パラメータｓが０以上１以下且つｔが０より小さい又は１より大きいときは２７回である。また、内分パラメータｔが０以上１以下且つｓが０より小さい又は１より大きいときは２７回である。また、内分パラメータｓとｔがともに０以上１以下のときは２６回である。
【００８２】
（ウ）閉曲面設定部１４２が判定対象の三角形に閉曲面を設定しなかったとき（図５のステップＳ５１４）、干渉演算部１４４は、以下の式（１４）〜（１６）に基づいて、判定対象の三角形が属する平面と第２の線分と交点を算出し、その座標を干渉判定部１４６に出力する。干渉判定部１４６は、干渉演算部１４４によって算出された交点の座標が、判定対象の三角形の内部の点か否かを判定することで、判定対象の三角形との干渉を判定する。なお、この計算は従来技術に属する一般的なものであるが、以下に一例を示す。
【００８３】
判定対象の三角形の各頂点のベクトルをＱ０、Ｑ１、及びＱ２とし、第２の線分の２つの端点のベクトルをＰ０及びＰ１とすると、判定対象の三角形が属する平面と第２の線分との交点Ｐｔは、内分パラメータｔを用いて、上述の式（３）で表される。Ｐｔは、判定対象の三角形と同一平面上に存在する。従って、判定対象の三角形の法線ベクトルＮとの間に、以下の式（１４）が成り立つ。なお、判定対象の三角形の法線ベクトルＮの値は予め算出しておくことができるため、上述の通り、計算回数に含めない。
【００８４】
【数１０】
0005878907.tif 000011
【００８５】
次に、式（１４）をｔについて解くことで、以下の式（１５）からｔが算出される。
【００８６】
【数１１】
0005878907.tif 000012
【００８７】
式（３）に基づくＰｔの算出に掛かる乗除算の回数は３回である。また、式（１５）に基づくｔの算出に掛かる計算は、内積計算２回と除算１回であり、これらを合わせた乗除算の回数は７回である。従って、Ｐｔの算出までに掛かる乗除算の回数は、式（３）及び（１５）に基づき、合わせて１０回である。次に、判定対象の三角形の各頂点Ｑ０、Ｑ１、Ｑ２各々の組と交点Ｐｔが作る三角形（Ｑ０Ｑ１Ｐｔ、Ｑ１Ｑ２Ｐｔ、Ｑ０Ｑ２Ｐｔ）の面積Ｓ０、Ｓ１、Ｓ２の和を算出し、判定対象の三角形Ｑ０Ｑ１Ｑ２の面積Ｓと比較する。そして、面積Ｓが面積Ｓ０、Ｓ１、Ｓ２の和よりも大きいとき（Ｓ＞Ｓ０＋Ｓ１＋Ｓ２）、干渉判定部１４６は、判定対象の三角形と第２の線分とが干渉しないと判定する。面積Ｓが面積Ｓ０、Ｓ１、Ｓ２の和以下のとき（Ｓ≦Ｓ０＋Ｓ１＋Ｓ２）、干渉判定部１４６は、判定対象の三角形と第２の線分とが干渉しないと判定する。
【００８８】
三角形の面積は、三角形の２辺を示す線分のベクトルの外積を２で除算することで算出される。３次元ベクトル同士の外積の算出には、１回当り６回の乗除算が必要となる。また、干渉判定部１４６は、三角形の面積同士を比較するので、上記三角形の面積の算出における２で除算する処理を省くことができる。また、予め算出しておくことができる判定対象の三角形Ｑ０Ｑ１Ｑ２の面積Ｓの２倍（２×Ｓ）の算出に必要な計算を除いた、３つの三角形（Ｑ０Ｑ１Ｐｔ、Ｑ１Ｑ２Ｐｔ、Ｑ０Ｑ２Ｐｔ）の面積Ｓ０、Ｓ１、Ｓ２各々の２倍（２×Ｓ０、２×Ｓ１、２×Ｓ２）の算出には、１回の外積計算と１回の内積計算とが掛かるため、９回の乗除算が必要となる。以上より（ウ）の計算には、Ｐｔの算出までの１０回と３つの三角形の面積の２倍の算出に掛かる２７回とを合わせた３７回の乗除算が必要となる。
【００８９】
以上のように、（ア）球型の閉曲面を用いたときの計算の量は、最多の場合で１０回、（イ）カプセル型の閉曲面を用いたときの計算の量は、最多の場合で２７回、（ウ）従来技術を用いたときの計算の量は３７回である。そのため、干渉演算部１４４は、従来技術である（ウ）の計算量に比較して（ア）の場合は１／４程度、（イ）の場合は２／３程度の計算量で干渉の判定に必要な値を算出することができる。従って、干渉判定装置１００は、少ない計算量で、第１の物体と第２の物体の干渉や近接を判定することができる。
【００９０】
また、干渉判定装置１００は、より多くの三角形を閉曲面で包含することで、干渉の判定に必要な計算の量をさらに少なくすることができる。そのためには、近接判定値４００を大きく設定し、大きな三角形も閉曲面で包含できるようにすればよい。その一方、近接判定値４００が大きくなると閉曲面と稜線との干渉判定が甘くなり、第１の物体と第２の物体の近接の判定精度が低くなる。従って、干渉判定装置１００は、近接判定値４００が小さくても、多くの三角形が閉曲面により包含されるような表面形状を持つ物体の干渉や近接の判定に最適である。
【００９１】
このような物体には、例えば、曲面を持つ物体が挙げられる。製造ラインにおける設備やロボットは、人との衝突時の安全性や強度などを考慮して、面取りがなされている。このような面取りがなされている曲面をポリゴンで表現する場合、当該曲面部には、平面部に比べて、極めて大量の小さな三角形や針状の細長い三角形が存在する。そのため、干渉判定装置１００は、面取りがなされている物体の表面の形状を示す三角形に対して、多くの閉曲面を設定する。従って、干渉判定装置１００は、面取りがなされている物体の干渉や近接の判定に要する計算量を低減することができる。また、面取りは、上記に挙げた設備やロボット以外にも、美観などを考慮して、工業製品一般に行われる。従って、製造ラインシミュレータに限らず、異なる技術分野に適用した場合においても、干渉判定装置１００は、計算量を低減する効果を奏することができる。
【００９２】
以上説明したように、第１の実施形態の干渉判定装置１００によれば、選択部１２０は、複数の物体のうちの第１の物体の表面の形状を示す複数の三角形のうち、少なくとも１つの三角形を判定対象の三角形として選択し、判定部１４０は、選択された判定対象の三角形を包含する閉曲面であって、判定対象の三角形に対応する或る点又は判定対象の三角形に対応する第１の線分との距離が一定である閉曲面と、複数の物体のうちの第２の物体の表面の形状を示す第２の線分との干渉を近接判定値４００が示す距離に基づいて判定する。従って、干渉判定装置１００は、少ない計算量で第１の物体と第２の物体の干渉や近接を判定することができる。
【００９３】
また、第１の実施形態の判定部１４０の閉曲面設定部１４２によれば、第１の線分とは判定対象の三角形の３辺のうちの２辺各々の中点を通る線分である。従って、閉曲面設定部１４２は、より多くの三角形を包含する閉曲面を設定することができるため、干渉判定装置１００は、さらに少ない計算量で第１の物体と第２の物体の干渉や近接を判定することができる。
【００９４】
また、第１の実施形態の判定部１４０の閉曲面設定部１４２によれば、第１の線分の長さは、前記判定対象の三角形の１つの辺の長さである。従って、閉曲面設定部１４２は、過度に大きな閉曲面を設定しないため、干渉判定装置１００は、設定した近接距離を、干渉や近接の判定に正しく反映することができる。また、干渉判定装置１００は、第１の線分の長さを改めて算出しなくてよく、計算量を低減できる。
【００９５】
また、第１の実施形態の判定部１４０の閉曲面設定部１４２によれば、判定対象の三角形に対応する或る点とは、判定対象の三角形の外心である。従って、閉曲面設定部１４２は、より多くの三角形を包含する閉曲面を設定することができるため、干渉判定装置１００は、さらに少ない計算量で第１の物体と第２の物体の干渉や近接を判定することができる。
【００９６】
なお、近接判定の精度と計算量の低減効果を両立させるために、干渉判定装置１００は、近接判定値４００を適切に設定する機能を備えていてもよい。例えば、干渉判定装置１００は、第１の物体の表面の形状を示す三角形の大きさ（例えば、外接円の半径など）を予め調べておき、そのうちの、例えば、２割から３割の三角形を包含できるように近接判定値４００を設定してもよい。また、干渉判定装置１００は、当該三角形を大きさなどに基づいてクラスタリングし、大きさの小さな三角形のクラスを閉曲面が包含できるように近接判定値４００を設定してもよい。また、近接判定値４００は、干渉判定装置１００のユーザが任意に設定してもよく、物体毎や三角形毎などで変更してもよい。
【００９７】
＜第２の実施形態＞
［構成］
以下、第２の実施形態に係る干渉判定装置について詳しく説明する。図６は、第２の実施形態に係る干渉判定装置１００ｂの機能構成の一例を示すブロック図である。本実施形態に係る干渉判定装置１００ｂ（図６）と第１の実施形態に係る干渉判定装置１００（図２）とを比較すると、干渉判定装置１００ｂが分割部１３０を備える点が異なる。また、本実施形態の干渉判定装置１００ｂが分割部１３０を備えることによって、選択部１２０ｂ及び判定部１４０ｂの閉曲面設定部１４２ｂが行う処理が、第１の実施形態の対応する機能部である選択部１２０及び判定部１４０の閉曲面設定部１４２とは異なっている。具体的には、干渉判定装置１００ｂの選択部１２０ｂは、判定対象の多角形を選択し、当該多角形を示す情報を、分割部１３０に出力する機能を備える。また、判定部１４０ｂの閉曲面設定部１４２ｂは、分割部１３０から分割後の多角形を示す情報を取得する機能を備える。
【００９８】
しかし、他の機能部（ポリゴン取得部１１０、干渉演算部１４４、干渉判定部１４６、及び出力部１５０）が持つ機能は第１の実施形態と同じである。第１の実施形態と同じ機能の説明は省略する。また、これらの機能部は、例えば、干渉判定装置１００ｂが備えるＣＰＵが記憶部に格納されたプログラムを実行することにより機能するソフトウェア機能部である。また、これらの機能部の一部又は全部は、ＬＳＩやＡＳＩＣ等のハードウェア機能部であってもよい。
【００９９】
［処理の概要］
判定対象の多角形を包含する閉曲面の設定に際して、干渉判定装置１００ｂは、当該多角形に複数の閉曲面を設定する機能を有する。以下、干渉判定装置１００ｂによる処理の概要を説明する。選択部１２０ｂは、判定対象の多角形を選択し、当該多角形を示す情報を分割部１３０に出力する。分割部１３０は、まず、選択部１２０ｂから判定対象の多角形を示す情報を、記憶部から近接判定値４００を取得する。次に、分割部１３０は、判定対象の多角形を近接判定値４００が示す距離に基づいて、複数の多角形に分割する。すなわち、分割部１３０は、第１の物体の表面の形状を示す複数の多角形のうちの少なくとも１つの多角形を、距離に基づいて複数の多角形に分割する。そして、分割部１３０は、閉曲面設定部１４２ｂに分割後の多角形を示す情報を出力する。なお、分割後の多角形を示す情報とは、例えば、分割後の多角形の各頂点の座標や分割後の多角形に固有に割り当てられた識別子である。
【０１００】
選択部１２０ｂは、分割部による分割後の複数の多角形のうちの１つの多角形を判定対象として選択する。すなわち、選択部１２０ｂは、分割部１３０による分割後の複数の多角形のうちの少なくとも１つの多角形を、判定対象として選択する。閉曲面設定部１４２ｂは、分割部１３０から分割後の多角形を示す情報を取得する。そして、閉曲面設定部１４２ｂは、分割後の多角形のうち選択部１２０ｂによって判定対象として選択された多角形に対して、第１の実施形態における閉曲面設定部１４２と同様に、閉曲面を設定する。以降の処理は、第１の実施形態と同様であるため省略する。
【０１０１】
［多角形の分割と閉曲面の設定］
以下、多角形の分割と閉曲面の設定について詳述する。図７は、三次元仮想空間内の物体の表面の形状を示す判定対象の多角形の分割方法の一例を示す模式図である。図７において示されているｘ軸ｙ軸ｚ軸は、それぞれ直交する３次元仮想空間の座標を示す軸である。図７（ａ）及び（ｂ）の模式図は、それぞれｚ軸方向から見たものであり、本例では、三角形２５０の法線と三角形２６０の法線とは、ｚ軸方向にそれぞれ一致している。図７（ａ）は、判定対象の三角形を２つの三角形に分割する様子を説明する図である。図７（ｂ）は、判定対象の三角形を３つの三角形に分割する様子を説明する図である。
【０１０２】
図７（ａ）において、判定対象の三角形２５０は、最長辺の長さが近接判定値４００によって示される距離ｄの２倍より大きく４倍以下であり、残りの２辺の長さが距離ｄの２倍以下である三角形である。このような三角形は閉曲面の設定条件を満たさないため、第１の実施形態における干渉判定装置１００は当該三角形には閉曲面を設定しない。干渉判定装置１００ｂの分割部１３０は、判定対象の三角形２５０を、当該三角形２５０の最長辺の中点と最長辺の端点ではない頂点とを結ぶ線分２５６によって２つの三角形に分割する。すなわち、分割部１３０による分割前の複数の多角形のうちの少なくとも１つの多角形とは、三角形であり、分割部１３０は、分割前の多角形のうちの少なくとも１つの三角形を、当該三角形の１つの中線により分割後の複数の多角形としての２つの三角形に分割する。
【０１０３】
分割後の２つの三角形の各辺の長さは、いずれも距離ｄの２倍以下である。従って、分割後の三角形の外心２５８（Ａ）及び２５８（Ｂ）を中心とする閉曲面を設定すると、当該閉曲面は、分割後の三角形各々を包含することができる場合がある。上記の通り、球型の閉曲面について干渉演算部１４４が行う計算量は、最も多い場合、１０回である。そのため、図７（ａ）のように三角形を２つに分割したとしても、分割後の三角形各々に球型の閉曲面を設定したときの計算量は、最も多い場合、２０回である。従って、干渉演算部１４４は、従来技術の３７回の計算量よりも少ない計算量で干渉の判定に必要な値を算出することができる。
【０１０４】
図７（ｂ）において、判定対象の三角形２６０は、２辺の長さが近接判定値４００によって示される距離ｄの２倍より大きく４倍以下であり、残りの１辺の長さが距離ｄの２倍以下である三角形である。このような三角形は閉曲面の設定条件を満たさないため、第１の実施形態における干渉判定装置１００は当該三角形には閉曲面を設定しない。干渉判定装置１００ｂの分割部１３０は、判定対象の三角形２６０を、当該三角形２６０の最長辺の中点２６９と最長辺の端点ではない頂点とを結ぶ線分２６６によって、閉曲面の設定条件を満たす２つの三角形に分割する。さらに、分割部１３０は、当該分割後の２つの三角形のうち、最長辺の長さが近接判定値４００によって示される距離ｄの２倍より大きい三角形を、当該三角形の最長辺の中点と最長辺の端点ではない頂点２６９とを結ぶ線分２６７によって分割する。すなわち、分割部１３０は、第１の物体の表面の形状を示す複数の多角形のうちの少なくとも１つの多角形を、距離に基づいて２つから５つのうちの３つの多角形に分割する。
【０１０５】
分割後の３つの三角形の各辺の長さは、いずれも距離ｄの２倍以下である。従って、分割後の三角形の外心２６８（Ａ）〜２６８（Ｃ）を中心とする閉曲面を設定すると、当該閉曲面は、分割後の三角形各々を包含することができる場合がある。上記の通り、球型の閉曲面について干渉演算部１４４が行う計算量は、最も多いとき、１０回である。そのため、図７（ａ）のように三角形を３つに分割したとしても、分割後の三角形各々に球型の閉曲面を設定したときの計算量は、最も多いとき、２０回である。従って、干渉演算部１４４は、従来技術の３７回の計算量よりも少ない計算量で干渉の判定に関する値を算出することができる。
【０１０６】
［三角形の分割と閉曲面の設定処理］
以下、干渉判定装置１００ｂによる三角形の分割と閉曲面の設定方法について説明する。図８は、干渉判定装置１００ｂによる判定対象の三角形に閉曲面を設定する処理の一例を示すフローチャートである。図８において、ステップＳ８００、Ｓ８０２、Ｓ８０４、Ｓ８０６、Ｓ８２０、Ｓ８２２、Ｓ８２４、及びＳ８２６各々は、図５のステップＳ５００、Ｓ５０２、Ｓ５０４、Ｓ５０６、Ｓ５０８、Ｓ５１０、Ｓ５１２、及びＳ５１４にそれぞれ対応するため、説明を省略する。また、ステップＳ８０４における判定がＮＯのときは、ステップＳ８０８に遷移する。
【０１０７】
（ステップＳ８０８）分割部１３０は、近接判定値４００によって示される距離ｄと判定対象の三角形の各辺の長さとを比較し、当該三角形の最長辺の長さが距離ｄの２倍より大きく４倍以下（２×ｄ＜最長辺≦４×ｄ）であり、１辺の長さが距離ｄの２倍以下（１辺≦２×ｄ）か否かを判定する。２×ｄ＜最長辺≦４×ｄ且つ１辺≦２×ｄであるとき（ステップＳ８０８；ＹＥＳ）、ステップＳ８１０に遷移する。２×ｄ＜最長辺≦４×ｄ且つ１辺≦２×ｄであるときではないとき（ステップＳ８０８；ＮＯ）、ステップＳ８１４に遷移する。
【０１０８】
（ステップＳ８１０）次に、分割部１３０は、判定対象の三角形を、当該三角形の最長辺の中点と最長辺の端点ではない頂点とを結ぶ線分で２つの三角形に分割し、それぞれの三角形に識別子を割り当てる。分割部１３０は、分割後の三角形各々の頂点の座標と識別子とを対応付けて記憶部に記憶させる。選択部１２０ｂは、分割後の２つの三角形各々を判定対象として選択する。
【０１０９】
（ステップＳ８１２）次に、分割部１３０は、近接判定値４００によって示される距離ｄと分割後の判定対象の三角形の最長辺の長さとを比較し、当該三角形の最長辺の長さが距離ｄの２倍より大きく４倍以下（２×ｄ＜最長辺≦４×ｄ）であるか否かを判定する。２×ｄ＜最長辺≦４×ｄであるとき（ステップＳ８１２；ＹＥＳ）、ステップＳ８１０に戻る。２×ｄ＜最長辺≦４×ｄではないとき（ステップＳ８１２；ＮＯ）、ステップＳ８１４に遷移する。
（ステップＳ８１４）次に、閉曲面設定部１４２ｂは、判定対象の三角形の頂点の座標から、当該三角形の外心の半径の大きさｄ２’を算出する。
【０１１０】
（ステップＳ８１６）次に、閉曲面設定部１４２ｂは、近接判定値４００によって示される距離ｄとステップＳ８１４で算出された判定対象の三角形の外接円の半径の大きさｄ２’とを比較し、当該三角形の外接円の半径の大きさｄ２’が距離ｄより小さい（ｄ２’≦ｄ）か否かを判定する。ｄ２’≦ｄのとき（ステップＳ８１６；ＹＥＳ）、ステップＳ８１８に遷移する。ｄ２’≦ｄではないとき（ステップＳ８１６；ＮＯ）、ステップＳ８２０に遷移する。
（ステップＳ８１８）次に、閉曲面設定部１４２ｂは、識別子と算出した外心の座標とを対応付けて記憶部に記憶させ、干渉演算部１４４に出力する。
【０１１１】
なお、多角形の分割方法は、上記の方法に限定されない。三角形であれば、例えば、中線で分割してもよいし、重心から各辺に下ろした垂線で分割してもよい。また、分割後の複数の多角形それぞれに形状の異なる閉曲面を設定してもよい。例えば、球型の閉曲面について干渉演算部１４４が行う計算の量は、最も多いとき、１０回であり、カプセル型の閉曲面について干渉演算部１４４が行う計算の量は、最も多いとき、２７回であるため、多角形を２つに分割し、分割後の多角形をそれぞれ球型の閉曲面とカプセル型の閉曲面で包含した場合の計算量は、最も多いとき、３７回である。従って、従来の３７回よりも少ない計算量で干渉を判定できる場合がある。
【０１１２】
また、分割部１３０は、多角形をより細かく分割してもよい。例えば、球型の閉曲面について干渉演算部１４４が行う計算の量は、最も少ないとき、７回である。そのため、５つに分割された三角形を球型の閉曲面で包含したときの計算量は、最も少なくて３５回であり、計算量の低減が見込める場合がある。従って、干渉判定装置１００ｂは、多角形を２つから５つに分割することで、より多くの多角形に対して閉曲面を設定し、計算量の低減することができる。また、分割を行う際の条件は、分割の方法に合わせて適宜設定してよい。
【０１１３】
[まとめ]
以上のように、第２の実施形態の干渉判定装置１００ｂによれば、分割部１３０は、第１の物体の表面の形状を示す複数の多角形のうちの少なくとも１つの多角形を、前記距離に基づいて複数の多角形に分割し、選択部１２０ｂは、分割部１３０による分割後の複数の多角形のうちの少なくとも１つの多角形を、判定対象として選択する。従って、干渉判定装置１００ｂは、第１の実施形態における干渉判定装置１００よりも、大きな三角形に対して閉曲面を設定できるため、さらに少ない計算量で第１の物体と第２の物体の干渉や近接を判定することができる。
【０１１４】
＜第３の実施形態＞
［干渉判定装置の使用環境］
以下、第３の実施形態に係る干渉判定装置について詳しく説明する。本実施形態に係る干渉判定装置１００ｃは、第１及び第２の実施形態に係る干渉判定装置１００及び１００ｂと同様に取得したポリゴンデータについて干渉の判定を行う製造ラインシミュレータであるが、その運用方法が異なる。本実施形態に係る干渉判定装置１００ｃは、例えば、製造ラインの動きと同期しており、製造ラインの構成要素の動きを先駆けて模擬する。例えば、図１に示す製造ラインにおいて、ロボット３１０（Ａ）が右向きに回転し、ロボット３１０（Ｂ）が左向きに回転するとする。ロボット３１０（Ａ）とロボット３１０（Ｂ）は位置が近いため、回転のタイミングによっては衝突する危険性がある。この動きをシミュレータで、実際の製造ラインの動きに先駆けて模擬し、干渉を判定することができれば、ロボット３１０（Ａ）又はロボット（Ｂ）の動きを遅くしたり、停止したりすることで、ロボット同士の衝突を避けることができる。このように、第３の実施形態に係る干渉判定装置１００ｃは、製造ラインの動きと同期して行うシミュレーションにおいて、リアルタイムでの干渉判定を行う。
【０１１５】
このような使用環境において、干渉判定装置１００ｃは、より短時間に干渉の判定を完了させることが求められる。従って、事前に行うことができる処理は、予め完了させておくことが望ましい。そこで、干渉判定装置１００ｃは、第１の物体の表面の形状を示す多角形について、予め閉曲面を設定する。
【０１１６】
［構成］
図９は、第３の実施形態に係る干渉判定装置１００ｃの機能構成の一例を示すブロック図である。本実施形態に係る干渉判定装置１００ｃ（図９）は、第２の実施形態に係る干渉判定装置１００ｂ（図６）に対応する各機能部を備えており、選択部１２０ｃは選択部１２０ｂに、判定部１４０ｃは判定部１４０ｂに、閉曲面設定部１４２ｃは閉曲面設定部１４２ｂに、干渉演算部１４４ｃは干渉演算部１４４にそれぞれ対応する。また、干渉判定装置１００ｃは、例えば、移動ベクトル取得部１６０と、座標変換部１７０とを備える。また、閉曲面設定テーブル４１０は、記憶部に格納されている。干渉判定装置１００ｃの各機能部（ポリゴン取得部１１０、分割部１３０、干渉判定部１４６、及び出力部１５０）が持つ機能は第１及び第２の実施形態における各機能部が持つ機能と同じであり、同じ機能の説明は省略する。これらの機能部は、例えば、干渉判定装置１００ｃが備えるＣＰＵが記憶部に格納されたプログラムを実行することにより機能するソフトウェア機能部である。また、これらの機能部の一部又は全部は、ＬＳＩやＡＳＩＣ等のハードウェア機能部であってもよい。
【０１１７】
［処理の概要］
以下、干渉判定装置１００ｃによる処理について説明する。干渉判定装置１００ｃは、第２の実施形態における処理と同様に、判定対象の多角形に対応する閉曲面を設定する。ただし、干渉判定装置１００ｃは、重複した処理を減らすため、或る多角形に対して既に設定された閉曲面に、別の多角形が包含される場合は、その多角形について干渉計算を行わない機能を持つ。この処理については後述する。閉曲面設定部１４２ｃは、判定対象の多角形の識別子と対応する閉曲面の設定情報とを対応付けて、閉曲面設定テーブル４１０(後述)として記憶部に記憶させる。選択部１２０ｃは、閉曲面設定テーブル４１０を参照して第１の物体のうちの判定対象と第２の線分とを選択し、当該判定対象を示す情報を干渉演算部１４４ｃに出力する。干渉演算部１４４ｃは、当該判定対象について、第１の実施形態の式（１）〜（１５）で示した計算を行う。
【０１１８】
製造ラインの動きと同期するリアルタイムの干渉判定では、仮想空間内の各構成要素及びその一部の動きに関する移動ベクトルデータが随時更新され、更新された移動ベクトルデータは、移動ベクトル取得部１６０によって取得される。移動ベクトル取得部１６０は、取得した移動ベクトルデータを記憶部に記憶させ、座標変換部１７０に出力する。座標変換部１７０は、移動ベクトル取得部１６０から取得した移動ベクトルデータが示す移動ベクトルに基づいて、閉曲面設定テーブル内に記憶された閉曲面の座標や三角形の座標を変換し、製造ラインの動きを仮想空間の構成要素の配置に反映させる。選択部１２０ｃは、更新された閉曲面設定テーブルを参照し、判定対象を選択する。以上を繰り返し行うことで、干渉判定装置１００ｃは、リアルタイムの干渉判定を行うことができる。
【０１１９】
図１０は、閉曲面設定テーブルの一例を示す表である。図１０において、列ｔ１００は三角形の識別子、列ｔ１０２は閉曲面の種類、列ｔ１０４は閉曲面の中心の座標、列ｔ１０６は干渉演算を低減するための事前計算値、列ｔ１０８は干渉判定を行ったか否かを示す。この例において、「１」の識別子で示される三角形は、図８のステップＳ８０６において球型の閉曲面を設定されている。このとき、列ｔ１０４の該当項目には、例えば、当該三角形の外心の座標が記憶される。「２」の識別子で示される三角形は、図８のステップＳ８２４においてカプセル型の閉曲面を設定されている。このとき、列ｔ１０４の該当項目には、例えば、当該閉曲面の第１の線分の２つの端点の座標が記憶される。また、列ｔ１０６の該当項目には、当該閉曲面の第１の線分の長さの２乗が記憶されている。干渉判定部１４６は、この値を利用することで、判定対象の三角形「２」と第２の線分との干渉を少ない計算量で判定することができる。
【０１２０】
「３」の識別子で示される三角形は、図８のステップＳ８１０において２つに分割され、図８のステップＳ８１８においてそれぞれに対応する球型の閉曲面を設定をされている。本実施形態では、分割後の２つの三角形各々に新たに識別子「３−１」及び「３−２」が割り当てられ、当該三角形各々に閉曲面が対応付けられている。従って、列ｔ１０４の該当項目には、例えば、同一の識別子「３」に分割後の２つの三角形の外心の座標が記憶される。
【０１２１】
「４」の識別子で示される三角形は、図８のステップＳ８２６において閉曲面を設定されなかった三角形である。列ｔ１０４の該当項目には、例えば、当該三角形の３つの頂点の座標が記憶される。また、列ｔ１０６の該当項目には、当該三角形の面積の２倍の値が記憶されている。判定部１４０ｃは、この値を利用することで、判定対象の三角形「４」と第２の線分との干渉を少ない計算量で判定することができる。「５」の識別子で示される三角形は、或る多角形に対して既に設定された閉曲面に包含されるため、干渉や近接の判定を行わないとして判定された三角形である。
【０１２２】
例えば、「５」の識別子で示される三角形が「１」の識別子で示される三角形に対応する閉曲面に包含されるか否かを判定する場合、閉曲面設定部１４２ｃは、「１」の閉曲面の座標（ｔ１０４）と「５」の三角形の各頂点との距離を算出する。閉曲面設定部１４２ｃは、当該算出した距離を近接判定値４００が示す距離と比較して、そのいずれも近接判定値４００が示す距離よりも小さければ、「５」の三角形は、「１」の三角形に対応する閉曲面に包含されると判定する。「２」のようなカプセル型の閉曲面の場合も同様に、閉曲面に対応する第１の線分と判定対象の三角形の各頂点との距離を算出し、当該算出した距離を近接判定値４００が示す距離と比較することで、判定対象の三角形が既に設定されている閉曲面に包含されるか否かを判定することができる。
【０１２３】
このように、第３の実施形態において、既に判定対象として選択された三角形に設定された閉曲面に包含される三角形は、判定対象とはされない。すなわち、選択部１２０ｃは、複数の物体のうちの第１の物体の表面の形状を示す複数の多角形のうち、判定部１４０ｃが第２の線分との干渉を判定するための第１の閉曲面に包含されない少なくとも１つの多角形を、判定対象の多角形として選択し、判定部１４０ｃは、当該多角形を包含する第２の閉曲面と第２の線分との干渉を判定する。従って、干渉判定装置１００ｃは、第２の実施形態における干渉判定装置１００ｂに比べて干渉や近接の判定を行う対象となる三角形を少なくすることができるため、第１の物体と第２の物体との干渉や近接の判定に行う計算の量を、さらに少なくすることができる。
【０１２４】
また、干渉判定装置１００ｃは、干渉判定を行う対象となる多角形を予め絞り込んでよい。例えば、干渉判定装置１００ｃは、取得した移動ベクトルを解析し、干渉が発生する恐れのある物体やその一部分を特定したうえで、特定された物体やその一部分を構成する多角形に対してのみ干渉や近接の判定を行ってもよい。また、干渉判定装置１００ｃは、例えば、物体全体或いはその一部を覆う閉曲面で簡単に干渉や近接の判定を行うことでさらに詳細な判定を行う物体やその一部分を特定し、特定された物体やその一部分を構成する多角形に対してのみ干渉や近接の判定を行ってもよい。このような判定対象の多角形の絞り込みは、特定の方法に限定せずに、利用してよい。
【０１２５】
以上、図面を参照してこの発明の一実施形態について詳しく説明してきたが、具体的な構成は上記のものに限られることはなく、この発明の要旨を逸脱しない範囲内において様々な設計変更等をすることが可能である。例えば、本発明の干渉判定装置は、製造ラインシミュレータの他にも機構設計システムや工業製品の設計、３次元マップ、ゲームソフトなどコンピュータグラフィックスを利用する様々な分野に適用することができる。また、以上説明した３つの実施形態の各機能を、組み合わせてもよい。例えば、第３の実施形態で説明した閉曲面を予め設定する方法は、第１の実施形態でも適用することができる。また、例えば、閉曲面同士で干渉や近接を判定してもよい。
【符号の説明】
【０１２６】
１００、１００ｂ、１００ｃ…干渉判定装置、１１０…ポリゴン取得部、１２０、１２０ｂ、１２０ｃ…選択部、１３０…分割部、１４０、１４０ｂ、１４０ｃ…判定部、１４２、１４２ｂ、１４２ｃ…閉曲面設定部、１４４、１４４ｃ…干渉演算部、１４６…干渉判定部、１５０…出力部、１６０…移動ベクトル取得部、１７０…座標変換部、２０２…ポリゴンデータ、２０４…移動ベクトルデータ、４００…近接判定値、４１０…閉曲面設定テーブル
【図２】
0005878907.tif 000013
【図３】
0005878907.tif 000014
【図４】
0005878907.tif 000015
【図５】
0005878907.tif 000016
【図６】
0005878907.tif 000017
【図７】
0005878907.tif 000018
【図８】
0005878907.tif 000019
【図９】
0005878907.tif 000020
【図１０】
0005878907.tif 000021
【図１】
0005878907.tif 000022