(57)【特許請求の範囲】
【請求項１】
３次元ポリゴンモデルで示された第１の部品と第２の部品の情報を入力するポリゴンデータ入力部と、
前記第１の部品を前記第１の部品の表面を構成する平面に分割し、前記第２の部品を前記第２の部品の表面を構成する平面に分割する分割部と、
前記分割部による分割によって得られた各平面について少なくとも輪郭の情報を当該平面に関する情報として作成するとともに、前記分割部によって得られた平面を内包する平面状の境界ボリュームを作成し、前記平面状の境界ボリュームを用いて前記第１の部品から得られた平面と前記第２の部品から得られた平面との交線を求める平面情報作成部と、
前記第１の部品から得られた平面の輪郭と前記第２の部品から得られた平面の輪郭との比較および、前記交線と前記輪郭との関係に基づいて前記第１の部品と前記第２の部品との干渉状態を判定する平面干渉判定部と
を備えたことを特徴とする干渉判定装置。
【請求項２】
前記第１の部品の境界ボリュームと前記第２の部品の境界ボリュームとを比較して干渉判定を行なう境界ボリューム干渉判定部をさらに備え、前記平面干渉判定部は、前記境界ボリューム干渉判定部による判定の結果、干渉の可能性がある場合に前記干渉判定を行うことを特徴とする請求項１に記載の干渉判定装置。
【請求項３】
前記分割部は、法線が同一方向である複数のポリゴンを１つの平面とすることを特徴とする請求項１または２に記載の干渉判定装置。
【請求項４】
前記平面情報作成部は、前記平面の輪郭について当該輪郭が前記平面の外縁であるか内縁であるかを識別する情報をさらに作成し、前記平面干渉判定部は、前記輪郭が外縁であるか内縁であるかをさらに用いて前記干渉状態の判定を行なうことを特徴とする請求項１〜３のいずれか一つに記載の干渉判定装置。
【請求項５】
３次元ポリゴンモデルで示された第１の部品と第２の部品の情報を入力するステップと、
前記第１の部品を前記第１の部品の表面を構成する平面に分割し、前記第２の部品を前記第２の部品の表面を構成する平面に分割するステップと、
前記分割するステップで得られた各平面について少なくとも輪郭の情報を当該平面に関する情報として作成するステップと、
前記分割するステップで得られた各平面を内包する平面状の境界ボリュームを作成するステップと、
前記平面状の境界ボリュームを用いて前記第１の部品から得られた平面と前記第２の部品から得られた平面との交線を求めるステップと、
前記第１の部品から得られた平面の輪郭と前記第２の部品から得られた平面の輪郭との比較および、前記交線と前記輪郭との関係に基づいて前記第１の部品と前記第２の部品との干渉状態を判定するステップと
を含んだことを特徴とする干渉判定方法。
【請求項６】
コンピュータに、
３次元ポリゴンモデルで示された第１の部品と第２の部品の情報を入力する手順と、
前記第１の部品を前記第１の部品の表面を構成する平面に分割し、前記第２の部品を前記第２の部品の表面を構成する平面に分割する分割手順と、
前記分割手順で得られた各平面について少なくとも輪郭の情報を当該平面に関する情報として作成する手順と、
前記分割手順で得られた各平面を内包する平面状の境界ボリュームを作成する手順と、
前記平面状の境界ボリュームを用いて前記第１の部品から得られた平面と前記第２の部品から得られた平面との交線を求める手順と、
前記第１の部品から得られた平面の輪郭と前記第２の部品から得られた平面の輪郭との比較および、前記交線と前記輪郭との関係に基づいて前記第１の部品と前記第２の部品との干渉状態を判定する手順と
を実行させることを特徴とする干渉判定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、干渉判定装置、干渉判定方法および干渉判定プログラムに関する。
【背景技術】
【０００２】
従来、３次元ＣＡＤ（Computer Added Design）／ＣＡＭ（Computer Added Manufacturing）やコンピュータグラフィックシステム等が使用されてきた。これらの技術により、シミュレーションや組み立て性の検証など様々な局面で、３次元形状データを有効活用する機会が増えている。中でも複数のモデルから構成されるアセンブリにおいて、その個々のモデル間の干渉を検出する機能は、設計ミスや入力ミスをチェックするために有用な機能である。
【０００３】
３次元形状ビューワーにおいて形状を表現するために利用されるデータは、多くの場合、自由曲面データから近似生成されたポリゴンメッシュである。ポリゴンメッシュを利用して干渉状態の検出を行う場合、空間に大量の物体が存在すると各組み合わせを全て判定するには時間を要していた。大規模アセンブリで任意のポリゴンメッシュ同士が交差しているかどうかを判定する為に、個々のモデルを構成するポリゴンメッシュ同士で総当りの干渉チェックを実施すると組み合わせの数が多くなるためである。
【０００４】
そこで従来から高速かつ正確に干渉判定を行なう場合には、ポリゴンメッシュでの交差判定を実行する前に、オブジェクトの境界ボリュームによる重なり判定、いわゆる交差判定を行なって対象を絞り込んだ後にポリゴンメッシュ同士の判定を行っていた。
【０００５】
境界ボリューム（Bounding Volume）は単体の単純なボリュームでより複雑な１つ以上のオブジェクトを包んでいる。より単純なボリュームという考え方を用いることで、それらが覆っている複雑なオブジェクトを用いる場合と比べて重なりがあるかどうかの判定にかかる時間を短縮することができる。
【０００６】
境界ボリュームとしては、球体を用いる技術の他、軸平行境界ボックス（AABB:Axis-Aligned Bounding Box)、有向境界ボックス（OBB:Oriented Bounding Box)を用いる技術が知られている。この中では、ＯＢＢが対象のオブジェクトの形状を最も反映し、交差判定の精度が高いため、ポリゴンメッシュでの交差判定を行なうことなくオブジェクトの分離が確認できる可能性が高い。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００１−２８２８７７号公報
【特許文献２】特開２００３−２７１６８７号公報
【非特許文献】
【０００８】
【非特許文献１】Christer Ericson著  中村達也訳  「ゲームプログラミングのためのリアルタイム衝突判定」株式会社ボーンデジタル  2005年10月25日発行
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、従来のＯＢＢ利用では、ポリゴン形状を分割し、分割したポリゴンを包含するＯＢＢを木構造で有していた。このため、オブジェクトとなるモデルの複雑度によってはメモリ消費がポリゴン形状のみと比べ２〜１０倍程度まで膨れ上がるという問題点があった。
【００１０】
また、近年ではより一層の処理速度向上のために、ＯＢＢの第１回目の分割作成後、面単位にさらに分割して３次元のＯＢＢを作成することで、ＯＢＢとモデルの形状との差異を少なくしてＯＢＢ作成総数を減らし、処理速度の向上を図る技術があった。しかしながら、末端までＯＢＢを作成することが求められる点については変わらず、依然としてＯＢＢによる消費メモリが多い状態であった。
【００１１】
また、面単位で分割して３次元のＯＢＢを作成した場合、面に他の面が接触していると干渉しているのかが不明であるため、隣接ポリゴンを利用したチェックを行なうことが求められていた。
【００１２】
このように従来の技術では、３次元形状の干渉判定において、メモリ消費が大きくなるという問題点があった。
【００１３】
開示の技術は、上記に鑑みてなされたものであって、３次元形状の干渉判定におけるメモリ消費を抑制する干渉判定装置、干渉判定方法および干渉判定プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本願の開示する干渉判定装置、干渉判定方法および干渉判定プログラムは、３次元ポリゴンモデルで示された第１の部品と第２の部品をそれぞれの表面を構成する平面に分割する。開示の装置、方法、プログラムは、分割によって得られた各平面について輪郭の情報を当該平面に関する情報として作成し、第１の部品から得られた平面の輪郭と第２の部品から得られた平面の輪郭とを比較して第１の部品と第２の部品との干渉状態を判定する。
【発明の効果】
【００１５】
本願の開示する装置、方法、プログラムによれば、３次元形状の干渉判定におけるメモリ消費を抑制する干渉判定装置、干渉判定方法および干渉判定プログラムを得ることができるという効果を奏する。
【図面の簡単な説明】
【００１６】
【図１】図１は、実施例１にかかる干渉判定装置の概要構成図である。
【図２】図２は、実施例２にかかる干渉判定装置の概要構成図である。
【図３】図３は、３次元の境界ボリュームの説明図である。
【図４】図４は、３次元の境界ボリュームによる干渉判定の説明図である。
【図５】図５は、境界ボリュームの階層化の説明図である。
【図６】図６は、部品に対するＯＢＢの作成についての説明図である。
【図７】図７は、分割の具体例の説明図である。
【図８】図８は、輪郭ラインと属性の生成についての説明図である。
【図９】図９は、ラインデータの具体例である。
【図１０】図１０は、輪郭面角度の算出についての説明図である。
【図１１】図１１は、ＯＢＳの作成についての説明図である。
【図１２】図１２は、ＯＢＳの干渉チェックについての説明図である。
【図１３】図１３は、ＯＢＳのデータの具体例である。
【図１４】図１４は、ＯＢＳの交線の算出についての説明図である。
【図１５】図１５は、ＯＢＳ交線データの具体例である。
【図１６】図１６は、交点の抽出の具体例である。
【図１７】図１７は、交線の始点、終点、交点の座標データの一例である。
【図１８】図１８は並び替えられた始点、終点、交点の座標データである。
【図１９】図１９は、始点および終点と交点との間が平面ｓＡ１の平面形状内にあるかの比較結果データの説明図である。
【図２０】図２０は、二次対象線分の抽出の説明図である。
【図２１】図２１は、角度判定部４３による判定の説明図である。
【図２２】図２２は、角度判定部４３が使用する平面のデータ例と面角度の具体例である。
【図２３】図２３は、角度判定部４３による比較の具体例である。
【図２４】図２４は、対象判定部４４による判定の説明図である。
【図２５】図２５は、ＯＢＳの作成について説明するフローチャートである。
【図２６】図２６は、干渉の判定処理を説明するフローチャートである。
【図２７】図２７は、図２６に示した平面での干渉判定処理を示すフローチャートである。
【図２８】図２８は、図２７に示した二次対象線分に基く干渉判定処理を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下に、本願の開示する干渉判定装置、干渉判定方法および干渉判定プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。
【実施例１】
【００１８】
図１は、実施例１にかかる干渉判定装置の概要構成図である。図１に示したように、干渉判定装置１は、ポリゴンデータ入力部１１、分割部１２、平面情報作成部１３および平面干渉判定部１４を有する。
【００１９】
ポリゴンデータ入力部１１は、３次元ポリゴンモデルで示された複数の部品の情報を入力する。この部品をモデル、あるいはオブジェクトという。分割部１２は、各部品を当該部品の表面を構成する平面に分割する。平面情報作成部１３は、分割部１２による分割によって得られた各平面について輪郭の情報を当該平面に関する情報として作成する。
【００２０】
平面干渉判定部１４は、干渉の可能性のある２つの部品を選択し、それぞれから得られた平面の輪郭を比較して干渉状態の有無を判定する。平面干渉判定部１４が部品の組み合わせを順次変更して行なうことで、ポリゴンデータ入力部１１から入力された各部品について干渉の有無を判定することができる。
【００２１】
上述してきたように、本実施例１に示した干渉判定装置は、３次元ポリゴンで示された部品を平面に分割し、平面の輪郭線を用いて判定することで、メモリ消費を抑制しつつ３次元形状の干渉判定を行なうことができる。
【実施例２】
【００２２】
・装置の構成
図２は、実施例２にかかる干渉判定装置の概要構成図である。干渉判定装置２は、内部にモデルデータベース２１、部品境界ボリューム管理部２２、分割部２３、境界ボリューム干渉判定部２４、記録部２５、出力部２６、平面情報作成部３０および平面干渉判定部４０を有する。
【００２３】
モデルデータベース２１は、３次元ポリゴンモデルで示された複数の部品の情報を入力装置３から入力されて保持する。部品境界ボリューム管理部２２は、モデルデータベース２１が保持する各部品について、３次元の境界ボリュームを作成する。境界ボリューム干渉判定部２４は、作成した境界ボリュームを元の部品の情報に対応付けて境界ボリューム干渉判定部２４および分割部２３に出力する。
【００２４】
分割部２３は、各部品を当該部品の表面を構成する平面に分割し、平面情報作成部３０に出力する。具体的には、分割部２３は、法線が同一方向である複数のポリゴンを１つの平面として出力する。
【００２５】
平面情報作成部３０は、輪郭ライン生成部３１、分割可否判定部３２、ライン属性生成部３３、ライン角度属性生成部３４、平面境界ボリューム管理部３５を有する。
【００２６】
輪郭ライン生成部３１は、分割部２３による分割によって得られた各平面について輪郭の情報を当該平面に関する情報として作成する。分割可否判定部３２は、分割によって得られた平面の輪郭線の数が所定数よりも多い場合に当該平面をさらに複数の平面に分割するよう分割部２３に指示する。分割可否判定部３２は、最終的に得られた輪郭線の数が所定数以内の平面について輪郭線の情報を平面境界ボリューム管理部３５に出力する。
【００２７】
ライン属性生成部３３は、輪郭ライン生成部３１が生成した平面の輪郭について当該輪郭が平面の外縁、すなわちアウターラインであるか、内縁すなわちインナーラインであるかを識別するライン属性を生成する。ライン角度属性生成部３４は、各輪郭について当該輪郭を共用する同一部品の他の平面との角度を示すライン角度属性を作成する。
【００２８】
平面境界ボリューム管理部３５は、平面、輪郭線、ライン属性、ライン角度属性を元の部品の情報に対応付けて管理する。加えて、平面境界ボリューム管理部３５は、各平面について、当該平面を内包する平面状の境界ボリュームを作成し、作成した平面状の境界ボリュームを元の部品に対応付けて管理する。
【００２９】
境界ボリューム干渉判定部２４は、部品境界ボリューム管理部２２が出力した３次元の境界ボリュームを用いて部品間における干渉の可能性を判定し、干渉の可能性がある部品の組み合わせと、当該組み合わせにかかる部品の情報を平面干渉判定部４０に出力する。
【００３０】
平面干渉判定部４０は、平面境界ボリューム管理部３５が管理する各種情報に基づいて部品間の干渉の有無を判定し、干渉する部品の情報を記録部２５に出力する。平面干渉判定部４０は、輪郭境界干渉判定部４１、内外判定部４２、角度判定部４３、対象判定部４４を有する。
【００３１】
輪郭境界干渉判定部４１は、干渉の可能性のある部品の一方から分割した平面の平面境界ボリュームと、他方の部品から分割した平面の平面境界ボリュームとを比較する。平面境界ボリュームに交線が存在する場合、２つの平面は干渉している可能性がある。内外判定部４２は、干渉している可能がある２つの平面について、平面境界ボリュームと輪郭線の交点から２つの平面が共有する二次対象線分を求めて、二次対象線分を輪郭線として有する平面の数を求める。
【００３２】
二次対象線分を輪郭線として有する平面の数が０である場合、すなわち、２つの平面が輪郭よりも内側で交差している場合、内外判定部４２は、その部品の組み合わせが干渉しているとして記録部２５に記録する。
【００３３】
また、二次対象線分を輪郭線として有する平面の数が２である場合、すなわち、２つの平面がそれぞれの輪郭で接している場合、内外判定部４２は、角度判定部４３に干渉の判定を行なわせる。
【００３４】
そして、二次対象線分を輪郭線として有する平面の数が１である場合、すなわち、一方の平面の輪郭が他方の平面の輪郭よりも内側に接している場合、内外判定部４２は、対象判定部４４に干渉の判定を行なわせる。
【００３５】
角度判定部４３は、二次対象線分で接する２つの平面の輪郭について、それぞれの輪郭のライン角度属性を参照し、その部品の組み合わせが干渉しているかを判定する。その部品の組み合わせが干渉している場合は、角度判定部４３は、その部品の組み合わせを記録部２５に記録する。
【００３６】
角度判定部４３は、二次対象線分で接する２つの平面の輪郭について、それぞれの輪郭のライン角度属性を参照し、その部品の組み合わせが干渉しているかを判定する。その部品の組み合わせが干渉している場合は、角度判定部４３は、その部品の組み合わせを記録部２５に記録する。
【００３７】
対象判定部４４は、輪郭が二次対象線分線上にある面の方向と、輪郭が二次対象線分上にない面の法線方向とを比較して、その部品の組み合わせが干渉しているかを判定する。その部品の組み合わせが干渉している場合は、対象判定部４４は、その部品の組み合わせを記録部２５に記録する。
【００３８】
記録部２５には干渉する部品についての情報が格納される。出力部２６は、記録部２５に格納された干渉する部品についての情報を出力する処理を行なう。具体的には、出力部２５は、干渉する部品についての情報を表示するディスプレイであっても良いし、他の装置に対して干渉する部品についての情報を提供するように構成してもよい。
【００３９】
このように干渉判定装置２は、３次元の境界ボリュームによって干渉の可能性を判定し、干渉の可能性のある部品の組み合わせについて、部品を平面に分割して干渉の判定を行なう。
【００４０】
・３次元の境界ボリュームによる判定
図３は、３次元の境界ボリュームの説明図である。また、図４は、３次元の境界ボリュームによる干渉判定の説明図である。境界ボリュームとしての具体例として図３には、球体（SPHERE）、軸平行境界ボックス（AABB:Axis-Aligned Bounding Box）、有向境界ボックス（OBB:Oriented Bounding Box）を例示した。例示の中では、SPHERE、ＡＡＢＢ、ＯＢＢの順に対象のオブジェクトの形状を反映し、交差判定の精度が高くなる。
【００４１】
境界ボリュームが球体である場合、境界ボリュームのデータ構造として中心座標と半径を有する。球体の境界ボリューム同士における交差、すなわち干渉を判定する場合は、中心間の距離を計算し、平方した距離が半径の合計よりも小さい場合に球は交差していると判定する。この球体の境界ボリュームによる干渉の判定は、ＡＡＢＢの判定よりも数値演算が２，３回多くなる。
【００４２】
境界ボリュームが軸並行境界ボックス（ＡＡＢＢ）である場合、境界ボリュームのデータ構造は、各軸に対する最小値と最大値となる。もしくは、ボックスの中心と各軸での半径を境界ボリュームのデータ構造として採用することもできる。
【００４３】
ＡＡＢＢのデータ構造が最大値と最小値で示されている場合、２つのＡＡＢＢが３つの軸のいずれかで分離している場合は交差なし、全ての軸で重なっている場合に干渉ありと判定する。また、ＡＡＢＢのデータ構造が中心と半径で得られている場合にも同様に、全ての軸で重なっている場合に交差と判定する。
【００４４】
境界ボリュームが有向境界ボックス（ＯＢＢ）である場合、境界ボリュームのデータ構造は、３つの傾きＶ(x,y,z)、中心座標 Ｃ (x,y,z)、３つの半径で示される。ＯＢＢでは、分離軸オブジェクＡの３つの座標軸と、オブジェクトＢの３つの座標軸と、それぞれのオブジェクトの軸に対して垂直な９つの軸が全て分離している場合は、交差していないと判定することができる。
【００４５】
ＯＢＢの単純な干渉判定では、ボックスＡの頂点のすべてがボックスＢの面によって定義される平面の外にあるかどうかを判定する。ＯＢＢの分離軸判定では、２つのOBBが離れているのは、ある軸Ｌに対して、それら２つのOBBをＬに投影して得られる半径の和が、射影した中心間の距離よりも短い場合に重なりがあると判定する。
【００４６】
２つ境界ボリュームが干渉する場合、境界ボリュームが各々内包するオブジェクトが干渉している可能性がある。オブジェクトが干渉するかの判定をポリゴンで行なう方法には、オブジェクトを構成する線分の交差、片方のオブジェクトの領域（空間内）にもう一方のオブジェクトの頂点が含まれているか（包含判定）等がある。また、双方のオブジェクトを構成する線分や頂点がもう一方のオブジェクトの線分や頂点と重なっているかによる交差判定も知られている。
【００４７】
次に、境界ボリュームの階層化について説明する。図５は、境界ボリュームの階層化の説明図である。境界ボリュームをツリー状の階層構造（木構造）に配置させることにより、干渉していない状態を早期に除外が可能になり実行する判定の数に対して時間的な複雑さを対数的に減少させることができる。このように境界ボリュームを階層化してオブジェクトの形状に近づける処理を刈り込みという。
【００４８】
一般的には精度と速度を重視した場合、ＯＢＢをツリー状の階層構造をもたせるのが一般的である。図５に示した例では、オブジェクト全体を包含するトップのＯＢＢを左右２つのＯＢＢに分割した場合を例示している。トップのＯＢＢは、オブジェクト全体を包含する。したがって、ポリゴンＰ１〜Ｐ４を含む全てのポリゴンはトップのＯＢＢ内部に存在する。
【００４９】
トップの次の階層として、オブジェクトをポリゴンＰ１，Ｐ２を含む左側のＯＢＢとポリゴンＰ３，Ｐ４を含む右側のＯＢＢを作ることで、トップのＯＢＢよりもオブジェクトの形状に近い境界ボリュームの組み合わせを得ることが出来る。
【００５０】
同様に階層化を繰り返し、ポリゴンＰ１を含むＯＢＢ、ポリゴンＰ２を含むＯＢＢ、ポリゴンＰ３を含むＯＢＢ、ポリゴンＰ４を含むＯＢＢを作成すれば、さらにオブジェクトの形状に近い境界ボリュームの組み合わせを得ることが出来る。
【００５１】
しかしながらＯＢＢをツリー状の階層構造（木構造）に配置させることは、ＯＢＢを各階層で作成することとなり、ポリゴンの干渉チェック前の事前処理においてＯＢＢ作成によるメモリ消費及び作成時間が増大する。
【００５２】
また、近年ではオブジェクトは形状を詳細にモデル化している。このため、小さな装置でも消費メモリが増加しており、干渉チェックによって消費メモリが増加すると、３２ｂｉｔＯＳの限界であるメモリ空間をオーバするモデルが存在する可能性がある。
【００５３】
ポリゴン単位同士の総当たりで干渉の判定を行なうと計算負荷が高く、処理時間を多く消費するので処理速度を向上させるために境界ボリュームが利用されるが、境界ボリュームを木構造で使用するとメモリ消費が大きくなる。
【００５４】
ＯＢＢを利用した場合、ポリゴン形状を分割し、分割したポリゴンを包含するＯＢＢを木構造で有すると、モデルの複雑度によりメモリ消費がポリゴン形状のみと比べ２〜１０倍程度まで膨れ上がる。
【００５５】
また、近年ではより一層の処理速度向上のために、ＯＢＢの第一回目の分割作成に次いで、面単位に分割してＯＢＢを作成することで、ＯＢＢとモデルの形状との差異を少なくしてＯＢＢ作成総数を少なくして処理速度の向上を図ってきた。しかしながら、末端までのＯＢＢ作成が要求され、依然としてＯＢＢによる消費メモリが多い状態であった。加えて、面単位の場合、面上に接した面は干渉しているのかが不明であるため、隣接ポリゴンを利用したチェックが要求されていた。
【００５６】
これに対し、開示の技術では、ＯＢＢは平面単位のみで作成し、詳細なチェックは平面同士の交差線分を利用することで、境界ボリューム作成を抑えることができる。すなわち開示の技術では、処理速度を維持しながらメモリ消費を抑えるため、ＯＢＢ作成を平面単位（隣接するポリゴンの中で同一法線を持つ物を集めた単位）で行い、末端までのＯＢＢ作成は必要とはしない。すなわち、ＯＢＢをツリー状の階層構造（木構造）で配置するのではなく、同一階層にＯＢＢを展開することで中間階層に存在するＯＢＢを作成しない。そして、干渉チェック自体は平面同士の交差線分と平面形状のアウターラインとインナーラインを利用して行う。
【００５７】
これにより、ＯＢＢ作成数の低減及び、末端までの階層移動時間の削減が可能になり、処理速度を維持または低減を行いながら、メモリ消費を大幅に削減することができる。なお、アウターラインとは、共有しないポリゴンのエッジを連続的に結び、閉じループの内側にポリゴンが存在する境界ラインを言う。また、インナーラインとは、上記閉じループの外側にポリゴンが存在する境界ラインをいう。また、平面境界、すなわち厚みがないＯＢＢをＯＢＳ(Oriented Bounding Surface)という。
【００５８】
・具体例
図６は、部品に対するＯＢＢの作成についての説明図である。図６は、部品境界ボリューム管理部２２が作成す３次元のＯＢＢの一例である。部品境界ボリューム管理部２２は、部品ｏＡと部品ｏＢについて、それぞれのモデル外形のＯＢＢを作成する。このＯＢＢの作成については、従来の技術を適用することができる。
【００５９】
図７は、分割の具体例の説明図である。分割部２３は、モデル（部品）を平面形状単位に分割して、モデル（部品）外形のＯＢＢ配下に置く。この時、隣接するポリゴンの中で同一法線を持つポリゴンを集めた集団と同一平面とする。図７では、部品ｏＢの分割と円筒モデルの分割を例示している。
【００６０】
図８は、輪郭ラインと属性の生成についての説明図である。輪郭ライン生成部３１は、分割部２３が作成した平面から輪郭を生成する。具体的には、輪郭ライン生成部３１は、平面上で異なるポリゴン同士で共有されない境界線を連続で見つけて閉じループを作成し、輪郭線とする。図８に示した例では、平面には外側の輪郭と内側の輪郭を有する。外側の輪郭線を平面形状のアウターラインといい、内側の輪郭線をインナーラインという。
【００６１】
ライン属性生成部３３は、輪郭線にアウターラインであるかインナーラインであるかを示す属性を付与する。具体的には、ライン属性生成部３３は、作成した輪郭の閉じループから、境界線の内側にポリゴンが存在する場合をアウターとし、外側にポリゴンが存在する場合をインナーとして抽出する。またこの際に各境界線に対して、ポリゴンが存在する方向に境界線に垂直で、平面上に形状方向を示す単位ベクトルを設定する。
【００６２】
図９は、ラインデータの具体例である。図９に示した例は、図８の平面から得られた輪郭ラインEdge1〜8を示しており、各輪郭ラインに始点座標（X,Y,Z）、終点座標（X,Y,Z）、形状方向ベクトル、隣接面角度、アウター、の項目を有する。ここで、始点座標（X,Y,Z）、終点座標（X,Y,Z）、形状方向ベクトルは、モデルの原点を基準とする。また、アウターの項目は、輪郭線がアウターラインである場合にTrue、インナーラインである場合にFalseの値をとる。
【００６３】
図９に示した例では、輪郭ラインEdge1は、始点座標（X,Y,Z）が（0,1,0）、終点座標（X,Y,Z）が（-5,1,1）、形状方向ベクトルが（0.2,0.0,0.98）、隣接面角が90、アウターの値がTrueである。
【００６４】
また、輪郭ラインEdge2は、始点座標（X,Y,Z）が（-5,1,1）、終点座標（X,Y,Z）が（-5,1,3）、形状方向ベクトルが（1.0,0.0,0.0）、隣接面角90、アウターの値がTureである。輪郭ラインEdge3は、始点座標（X,Y,Z）が（-5,1,3）、終点座標（X,Y,Z）が（0,1,6）、形状方向ベクトルが（-0.51,0.0,-0.86）、隣接面角が90、アウターの値がTrueである。
【００６５】
輪郭ラインEdge4は、始点座標（X,Y,Z）が（0,1,6）、終点座標（X,Y,Z）が（0,1,0）、形状方向ベクトルが（-1.0,0.0,0.0）、隣接面角90、アウターの値がTureである。輪郭ラインEdge5は、始点座標（X,Y,Z）が（-1,1,1）、終点座標（X,Y,Z）が（-2,1,1）、形状方向ベクトルが（0.0,0.0,-1.0）、隣接面角90、アウターの値がFalseである。
【００６６】
輪郭ラインEdge6は、始点座標（X,Y,Z）が（-2,1,1）、終点座標（X,Y,Z）が（-2,1,3）、形状方向ベクトルが（-1.0,0.0,0.0）、隣接面角90、アウターの値がFalseである。輪郭ラインEdeg7は、始点座標（X,Y,Z）が（-2,1,3）、終点座標（X,Y,Z）が（-1,1,3）、形状方向ベクトルが（0.0,0.0,1.0）、隣接面角90、アウターの値がfalseである。輪郭ラインEdeg8は、始点座標（X,Y,Z）が（-1,1,3）、終点座標（X,Y,Z）が（-1,1,1）、形状方向ベクトルが（1.0,0.0,0.0）、隣接面角90、アウターの値がfalseである。
【００６７】
ここで、図９に示した隣接面角度の算出について説明する。図１０は、輪郭面角度の算出についての説明図である。隣接面角度は、ライン角度属性生成部３４によって求められる。具体的には、ライン角度属性生成部３４は、対象平面の法線と境界線の形状方向ベクトルの外積を求め、回転軸方向を一時的に決める。次にライン角度属性生成部３４は、対象平面の境界線の形状方向ベクトルと、隣接平面の境界線の形状方向ベクトルで外積を求め、角度を抽出する。その際に外積のベクトル方向が一時的の求めた外積と同一方向であれば、ライン角度属性生成部３４は、そのままの値を利用し、異なる場合は180度付加して、現在の平面をから隣接平面の角度を抽出する。なお、同一境界線でも隣接平面が異なる場合は境界線を分割して管理する。
【００６８】
また、分割可否判定部３２は、一つの平面形状内に属する境界線を集計し、所定数よりも多い場合は、平面を分割して再度同様な処理をする。そして、平面境界ボリューム管理部３５は、平面形状の属性ができたら図１１に示したように、平面のＯＢＢ、すなわちＯＢＳを作成する。ＯＢＳはＯＢＢの１軸成分（３軸の内１軸）がない形状となる。
【００６９】
以上の処理を、対象モデル（部品）の平面がなくなるまで繰り返し、次にモデル（アセンブリ、部品）がなくなるまで繰り返すことで、全てのＯＢＢ及びＯＢＳを作成する。なお、全てのＯＢＢとＯＢＳは部品のローカル座標系で作成される。
【００７０】
次に、干渉チェックについて説明する。干渉チェックでは、モデル（アセンブリ、部品）単位のＯＢＢ同士で干渉チェックを行ない、干渉したモデル同士で平面のＯＢＳ同士の干渉チェックを行なう。
【００７１】
ＯＢＳの干渉チェックでは、まず、２つの平面の法線方向をチェックする。図１２に示したように、２つの平面の法線方向が真逆なら接触はあるが干渉なしとして判断する。法線方向が同一であれば、干渉の可能性がある。
【００７２】
干渉の可能性があるＯＢＳについては、通常の０ＢＢ同士と同様に分離軸の作成が可能かをチェックし、分離軸が作成できない場合は干渉の可能性ありと判断する。ここで、交差判定時には部品のＯＢＢやＯＢＳをローカル座標から絶対座標に変換して行なう。
【００７３】
図１３は、ＯＢＳのデータの具体例である。図１３に示した例では、モデルｏＡは、相対座標の法線ベクトルが（0,1,0）のSurface1、法線ベクトルが（1,0,0）のSurface2、法線ベクトルが（0,0,1）のSurface3、法線ベクトルが（0,-1,0）のSurface4を有する。
【００７４】
また、モデルｏＡのSurface1は、相対座標で始点(X,Y,Z)=(0,1,0)、終点(X,Y,Z)=(-5,1,0)のEdge1、始点(X,Y,Z)=(-5,1,0)、終点(X,Y,Z)=(-5,1,6)のEdge2、始点(X,Y,Z)=(-5,1,6)、終点(X,Y,Z)=(0,1,6)のEdge3、始点(X,Y,Z)=(0,1,6)、終点(X,Y,Z)=(0,1,0)のEdge4を有する。
【００７５】
同様に、モデルｏＢのSurface1は、相対座標で始点(X,Y,Z)=(0,1,0)、終点(X,Y,Z)=(-5,1,0)のEdge1、始点(X,Y,Z)=(-5,1,0)、終点(X,Y,Z)=(-5,1,6)のEdge2、始点(X,Y,Z)=(-5,1,6)、終点(X,Y,Z)=(0,1,6)のEdge3、始点(X,Y,Z)=(0,1,6)、終点(X,Y,Z)=(0,1,0)のEdge4を有する。
【００７６】
分離軸による干渉チェックでは、これらのＯＢＳデータを絶対座標に変換して分離軸の算出を行なう。分離軸による干渉チェックの結果、干渉の可能性がある場合には、輪郭境界干渉判定部４１は、２つＯＢＳの交線を抽出する。
【００７７】
図１４は、ＯＢＳの交線の算出についての説明図であり、図１５は、ＯＢＳ交線データの具体例である。図１４に示した例では、モデルｏＡの平面の一つである平面ｓＡ１のＯＢＳと、モデルｏＢの平面の一つである平面ｓＢ１のＯＢＳとの交線、すなわち交差線分を示している。
【００７８】
図１５に示したように、ＯＢＳの交線データは、始点の座標と終点の座標が絶対座標で示されている。図１５の例では、始点の絶対座標は（X,Y,Z）＝（50,100,40）であり、
終点の絶対座標は（X,Y,Z）＝（50,100,44）である。
【００７９】
内外判定部４２は、抽出した交線と相手側の平面内のアウターとインナーの交点を抽出する。この時、交線を無限線分として交点を抽出する。図１６は、交点の抽出の具体例である。図１６に示した例では、交線の始点と終点との間に交点１が存在し、終点側の延長線上に交点２が存在する。
【００８０】
内外判定部４２は、交線の始点、終点、交点の座標を抽出する。図１７は、交線の始点、終点、交点の座標データの一例である。図１７に示した例では、始点と終点の座標は図１５のままであり、交点１の絶対座標は（X,Y,Z）＝（50,100,41）、交点２の絶対座標は（X,Y,Z）＝（50,100,45）である。また、交点１，交点２は、それぞれアウターラインとの交点である。
【００８１】
内外判定部４２は、交線の始点、終点、交点を並び替えて一次線分を抽出する。図１８は並び替えられた始点、終点、交点の座標データである。図１８に示した例では、始点、交点１、終点、交点２の順に並べられている。この並び順は、図１６に示した状態と対応している。
【００８２】
内外判定部４２は、始点および終点と交点との間が平面ｓＡ１の平面形状内にあるかを判定する。この判定は各点から見た次の点が有る方向と、交点があるエッジの形状方向ベクトル方向を比較することで行なう。具体的には、交点からのベクトルが形状ベクトルに対して両サイド90度以下の場合が平面ｓＡ１の平面形状内にある場合であり、その線分は一次対象線分として抽出の対象となる。
【００８３】
図１９は、始点および終点と交点との間が平面ｓＡ１の平面形状内にあるかの比較結果データの説明図である。図１９に示したように、交点１と始点との間は、交点からのベクトルが（0,0,-1）、形状方向ベクトルが（0,0,1）であり、抽出対象はFalse、すなわち交点１と始点との間は平面ｓＡ１の平面形状内に無い。
【００８４】
交点１と終点との間は、交点からのベクトルが（0,0,1）、形状方向ベクトルが（0,0,1）であり、抽出対象はTrue、すなわち交点１と終点との間は平面ｓＡ１の平面形状内にある。
【００８５】
そして、交点２と終点との間は、交点からのベクトルが（0,0,1）、形状方向ベクトルが（0,0,-1）であり、抽出対象はFalse、すなわち交点２と終点との間は平面ｓＡ１の平面形状内に無い。
【００８６】
内外判定部４２は、形状方向に線分がある場合、すなわち抽出対象がTrueである場合にその線分を一次対象線分として記録する。次に現在の交点とその次の交点を同様に繰り返して端点まで繰り返す。
【００８７】
内外判定部４２は、抽出した一次対象線分を利用して、もう片方の平面内のアウターとインナーに対して同様の処理を行い、最終的に残った線分を二次対象線分とする。図２０は、二次対象線分の抽出の説明図である。２つの平面をそれぞれ包含する２つのＯＢＳの交線と一方の平面との重複部分が一次対象線分である。言い換えれば、一次対象線分は、一方の平面と他方のＯＢＳとの重複部分である。二次対象線分は、一次対象線分と他方の平面との重複部分である。すなわち、二次対象線分は、２つの平面の重複部分である。図２０に示した例では、始点と交点２との間が二次対象線分となっている。
【００８８】
内外判定部４２は、二次対象線分の全てが片面ずつ平面のアウターインナー上にあるかをチェックする。２平面共にない場合は、内外判定部４２は、二次対象線分を干渉線分として記録する。
【００８９】
二次対象線分が２平面共にある場合は、角度判定部４３が二次対象線分に属しているアウターインナーから隣接平面角度を抽出して干渉を判定する。図２１は、角度判定部４３による判定の説明図である。
【００９０】
図２１に示した例では、角度判定部４３は、平面ｓＡ１を０度とし、平面ｓＡ１の境界線の隣接角度、すなわち平面ｓＡ１と同一部品の隣接平面ｓＡ２との角度を抽出する。次に平面ｓＡ１の法線と境界線の形状方向ベクトルの外積を求め、回転軸方向を一時的に決める。次に平面ｓＡ１の境界線の形状方向ベクトルと、平面ｓＢ１の境界線の形状方向ベクトルで外積を求め、角度を抽出する。その際に外積のベクトル方向が一時的に求めた外積と同一方向であれば、そのままの値を利用し、異なる場合は１８０度付加して抽出する。
【００９１】
そして、平面ｓＢ１の法線と境界線の形状方向ベクトルの外積を求め、回転軸方向を一時的に決める。平面ｓＡ１の軸方向と平面ｓＢ１の軸方向が異なる場合は、平面ｓＢ１の隣接角度、すなわち平面ｓＢ１と同一部品の隣接平面ｓＢ２との角度を加えて抽出し、同一の場合は角度を引いて抽出する。これにより、平面ｓＡ１を基準に各面の接続角度から干渉の有無を判断する。干渉であれば二次対象線分を干渉線分として記録する。
【００９２】
図２２は、角度判定部４３が使用する平面のデータ例と面角度の具体例である。図２２に示した例では、平面ｓＡ１のEdge1と平面ｓＢ１のEdge１とが接している。平面ｓＡ１のEdge1は、始点座標が（X,Y,Z）＝（0,1,0）、終点座標が（X,Y,Z）＝（-5,1,1）、形状方向ベクトルが（0.2,0.0,0.98）、隣接面角度が30、アウターがTrueである。平面ｓＢ１のEdge1は、始点座標が（X,Y,Z）＝（0,1,0）、終点座標が（X,Y,Z）＝（-5,1,1）、形状方向ベクトルが（0.2,0.0,0.98）、隣接面角度が50、アウターがTrueである。
【００９３】
平面ｓＡ１と平面ｓＢ１の面角度を比較すると、対象面である平面ｓＡ１が０度に対して、対象面である平面ｓＢ１が１５０度である。また、平面ｓＡ１の隣接面である平面ｓＡ２の角度は３０度であり、平面ｓＢ１の隣接面である平面ｓＢ２の角度は１００度となる。対象面と隣接面の角度のうち低い値から高い値の範囲を部品が存在する範囲とする。すなわち、０〜３０度が平面ｓＡ１を有する部品の存在する範囲であり、１００〜１５０度が平面ｓＢ１を有する部品の存在する範囲である。角度判定部４３は、この角度範囲を比較して重なる範囲がある場合を干渉ありと判断する。
【００９４】
図２３は、角度判定部４３による比較の具体例である。図２３に示した例では、平面Ｂｘの隣接角度をプラスすると360度を超える場合を示している。具体的には、対象面である平面Ａｘと平面Ｂｘについて、平面Ａｘを０度とすると、平面Ａｘの隣接面が３０度、平面Ｂｘが３３０度、平面Ｂｘの隣接面が３８０度である。このように上限の数値が３６０度を超える場合、角度判定部４３は、平面Ｂｘと隣接面の角度から３６０度引いて判断する。したがって、平面Ａｘを有する部品は０〜３０度を角度範囲として持ち、平面Ｂｘを有する部品は−３０〜２０度を角度範囲として持つものとして干渉を判定する。
【００９５】
内外判定部４２による判定の結果、二次対象線分が一つの平面上にのみある場合は、対象判定部４４が干渉を判定する。図２４は、対象判定部４４による判定の説明図である。対象判定部４４は、対象の二次対象線分と重複するアウターラインもしくはインナーラインの形状方向ベクトルを抽出し、もう片側の平面の法線と比較する。法線との差異が９０度以上有る場合は干渉とし、干渉であれば二次対象線分を干渉線分として記録する。
【００９６】
図２４に示した例では、絶対座標系においての平面ｓＡ１の法線ベクトルと平面ｓＢ１上の対象エッジの形状方向ベクトルとの内積から角度を抽出して判定している。図２４に示した例では、平面ｓＢ１の境界線が平面ｓＡ１の裏面に接触しているので、対象判定部４４は干渉ありと判定する。
【００９７】
・処理のフローチャート
図２５は、ＯＢＳの作成について説明するフローチャートである。部品境界ボリューム管理部２２は、モデルデータベース２１から部品を選択し（Ｓ１０１）、選択した部品の３次元境界ボリューム、例えばＯＢＢを作成する（Ｓ１０２）。
【００９８】
分割部２３は、部品境界ボリューム管理部２２が選択した部品のポリゴンを平面単位に並列に分割する（Ｓ１０３）。平面情報作成部３０は、分割によって得られた平面を一つ選択する（Ｓ１０４）。選択した平面の輪郭線を輪郭ライン生成部３１が作成し、ライン属性生成部３３がラインの属性を生成することで、アウターラインとインナーラインを抽出する（Ｓ１０５）。
【００９９】
ライン角度属性生成部３４は、アウターラインとインナーラインの隣接面角度を抽出する（Ｓ１０６）。また、分割可否判定部３２は、アウターとインナーのライン数を抽出し（Ｓ１０７）、ライン数が所定の範囲内であるかを判定する（Ｓ１０８）。ライン数が所定範囲内でなければ（Ｓ１０８，Ｎｏ）、選択中の平面を分割部２３がさらに分割し（Ｓ１０９）、ステップＳ１０４に戻る。ライン数が所定数の範囲内であれば（Ｓ１０８，Ｙｅｓ）、平面境界ボリューム管理部３５が選択中の平面を内包する平面境界ボリューム（ＯＢＳ）を作成する（Ｓ１１０）。
【０１００】
ＯＢＳの作成後、選択中の部品にＯＢＳを作成していない平面が残っていれば（Ｓ１１１，Ｙｅｓ）、再びステップＳ１０４に戻る。選択中の部品の全ての平面についてＯＢＳを作成した場合（Ｓ１１１，Ｎｏ）、部品境界ボリューム管理部２２は、ＯＢＳの作成を行なっていない部品が残っているかを判定する（Ｓ１１２）。ＯＢＳを作成していない部品が残っているならば（Ｓ１１２，Ｙｅｓ）、部品境界ボリューム管理部２２はステップＳ１０１に戻って部品の選択を行なう。そして、モデルデータベース２１に登録された全ての部品についてＯＢＳを作成した場合（Ｓ１１２，Ｎｏ）に処理を終了する。
【０１０１】
図２６は、干渉の判定処理を説明するフローチャートである。境界ボリューム干渉判定部２４は、モデルデータベース２１に登録された部品から２つの部品を選択し、干渉チェック対象とする（Ｓ２０１）。境界ボリューム干渉判定部２４は、干渉チェック対象として選択した２つの部品について部品境界ボリューム２２が作成した境界ボリュームの干渉判定を行なう（Ｓ２０２）。
【０１０２】
境界ボリュームが干渉している場合（Ｓ２０３，Ｙｅｓ）、平面干渉判定部４０が干渉チェック対象の２つの部品から平面を１つずつ選択し（Ｓ２０５）、平面の境界ボリューム（ＯＢＳ）で干渉判定を行なう（Ｓ２０６）。判定の結果、ＯＢＳに干渉がある場合（Ｓ２０７，Ｙｅｓ）、平面干渉判定部４０は、平面での干渉判定を実行する（Ｓ２０９）。
【０１０３】
平面での干渉判定（Ｓ２０９）の後、もしくはＯＢＳに干渉がない場合（Ｓ２０７，Ｎｏ）、平面干渉判定部４０は、干渉チェック対象の部品に判定をしていない平面が残っているかを判定する（Ｓ２０８）。判定をしていない平面が残っていれば（Ｓ２０８，Ｙｅｓ）、辺面干渉判定部４０は、ステップＳ２０５に戻って平面の選択を行なう。
【０１０４】
境界ボリュームに干渉がない場合（Ｓ２０３，Ｎｏ）、もしくは平面干渉判定部４０が干渉チェック対象の部品の全ての平面について判定を行った場合（Ｓ２０８，Ｎｏ）、境界ボリューム干渉判定部２４は、モデルデータベース２１に登録された部品の全ての組み合わせについて干渉判定を行なったかを判定する（Ｓ２０４）。干渉判定を行っていない部品の組み合わせが残っていれば（Ｓ２０４，Ｎｏ）、境界ボリューム干渉判定部２４は、ステップＳ２０１に戻り、部品の選択を行なう。そして、全ての部品の組み合わせについて干渉判定を行った場合（Ｓ２０４，Ｙｅｓ）に処理を終了する。
【０１０５】
図２７は、図２６に示した平面での干渉判定処理を示すフローチャートである。平面での干渉判定処理が開始されると、輪郭境界干渉判定部４１が２つのＯＢＳの交線を抽出する（Ｓ３０１）。つぎに、内外判定部４２が一方の平面のアウターラインとＯＢＳの交線から交点を抽出し（Ｓ３０２）、同じ平面のインナーラインとＯＢＳの交線から交点を抽出する（Ｓ３０３）。
【０１０６】
内外判定部４２は、端点、すなわち始点および終点と交点を順番に並べ（Ｓ３０４）、順に並べた点のうち、平面の領域内の線分を一次対象線分として抽出する（Ｓ３０５）。内外判定部４２は、全ての点の間について判定済みでなければ（Ｓ３０６，Ｎｏ）、ステップＳ３０５に戻って処理を繰り返す。そして、全ての点の間について判定を行なった後（Ｓ３０６，Ｙｅｓ）、内外判定部４２は、一次対象線分があるか否かを判定する（Ｓ３０７）。
【０１０７】
一次対象線分が有る場合（Ｓ３０７，Ｙｅｓ）、内外判定部４２は、他方の平面のアウターラインと一次対象線分との交点を抽出し（Ｓ３０８）、同じ平面のインナーラインと一次対象線分から交点を抽出する（Ｓ３０９）。
【０１０８】
内外判定部４２は、端点と交点を順番に並べ（Ｓ３１０）、順に並べた点のうち、平面の領域内の線分を二次対象線分として抽出する（Ｓ３１１）。内外判定部４２は、全ての点の間について判定済みでなければ（Ｓ３１２，Ｎｏ）、ステップＳ３１１に戻って処理を繰り返す。そして、全ての点の間について判定を行なった後（Ｓ３１２，Ｙｅｓ）、内外判定部４２は、二次対象線分があるか否かを判定する（Ｓ３１３）。
【０１０９】
二次対象線分がある場合（Ｓ３１３，Ｙｅｓ）、内外判定部４２は、二次対象線分に基く干渉判定を実行し（Ｓ３１４）、平面での干渉判定処理を終了する。また、一次対象線分がない場合（Ｓ３０７，Ｎｏ）や二次対象線分がない場合（Ｓ３１３，Ｎｏ）には、内外判定部４２は、そのまま平面での干渉判定処理を終了する。
【０１１０】
図２８は、図２７に示した二次対象線分に基く干渉判定処理を示すフローチャートである。二次対象線分に基く干渉判定処理を開始した内外判定部４２は、二次対象線分を選択し（Ｓ４０１）、二次対象線分が輪郭線上にある平面を抽出する（Ｓ４０２）。抽出の結果、二次対象線分が輪郭線上にある平面の数が０である場合（Ｓ４０４，Ｙｅｓ）、内外判定部４２は、当該二次対象線分を干渉として記録部２５に記録する（Ｓ４０４）。
【０１１１】
一方、二次対象線分が輪郭線上にある平面の数が０ではなく（Ｓ４０３，Ｎｏ）、２である場合（Ｓ４０６，Ｙｅｓ）、角度判定部４３が双方の平面の隣接面角度を抽出して（Ｓ４０７）、重なる領域が存在する場合に（Ｓ４０８，Ｙｅｓ）、当該二次対象線分を干渉として記録部２５に記録する（Ｓ４０４）。
【０１１２】
また、二次対象線分が輪郭線上にある平面の数が２ではなく（Ｓ４０６，Ｎｏ）、１である場合、対象判定部４４は二次対象線分が輪郭ではない面の法線を抽出する（Ｓ４０９）。また、対象判定部４４は、二次対象線分が輪郭である面の平面内部方向を抽出する（Ｓ４１０）。そして、対象判定部４４は、平面内部方向と法線との差が９０度以内でなければ（Ｓ４１１，Ｎｏ）、当該二次対象線分を干渉として記録部２５に記録する（Ｓ４０４）。
【０１１３】
ステップＳ４０４の後、もしくは対象判定部４４による判定の結果、平面内部方向と法線との差が９０度以内である場合（Ｓ４１１，Ｙｅｓ）、また、角度判定部４３による判定の結果、重なる領域がない場合（Ｓ４０８，Ｎｏ）、内外判定部４２は、全ての二次対象線分に対して判定を行なったかを判定する（Ｓ４０５）。
【０１１４】
内外判定部４２は、判定を行なっていない二次対象線分が残っている場合（Ｓ４０５，Ｎｏ）、ステップＳ４０１に戻る。そして、全ての二次対象線分に対して判定を行った場合（Ｓ４０５，Ｙｅｓ）に、内外判定部４２は二次対象線分に基く干渉判定処理を終了する。
【０１１５】
上述してきたように、本実施例２に開示した干渉判定装置２は、３次元の境界ボリュームによって干渉の可能性を判定し、干渉の可能性のある部品の組み合わせについて、部品を平面に分割して干渉の判定を行なう。このため、ポリゴン形状と境界ボリュームが同一化するように末端形状までツリー状の階層構造に境界ボリュームの配置する必要が無く、境界ボリュームを保持するメモリ消費を低減することができ、３次元形状の干渉判定におけるメモリ消費を抑制することができる。
【０１１６】
メモリ消費や処理時間はモデル数なども関係するが、一例を挙げると総チェック数として８２．７％〜９４．６％の削減が可能となり、ＯＢＢによる消費メモリの６２．８％〜８４．２％の削減、処理時間の１３％〜４３．１％の短縮が実現できる。また、３２ｂｉｔＯＳにおける１つのアプリケーションで利用可能なメモリとして１．５ＧＢ〜２．０ＧＢの上限があるが、この上限のため従来は利用できなかったモデルに対しても干渉チェックが利用できるようになる。
【０１１７】
また、本実施例２に開示した干渉判定装置２は、法線が同一方向である複数のポリゴンを１つの平面とすることで、簡易に平面を得ることができる。また、本実施例２に開示した干渉判定装置２は、分割によって得られた平面を内包する平面状の境界ボリュームであるＯＢＳを作成し、ＯＢＳの交線と輪郭との関係に基づいて干渉状態の判定を行なうことで、処理の効率化を実現する。
【０１１８】
また、本実施例２に開示した干渉判定装置２は、平面の輪郭について当該輪郭が平面の外縁であるか内縁であるかを識別する情報をさらに作成し、干渉状態の判定を行なうことで、孔部を有する部品についても境界ボリュームを階層化することなく精度を保った判定が可能となり、境界ボリュームを保持するメモリ消費を低減できる。
【０１１９】
また、本実施例２に開示した干渉判定装置２は、平面の輪郭について当該輪郭を共用する同一部品の他の平面との角度を用いて干渉状態の判定を行なうことで、二つの部品が輪郭で接する状態であっても干渉を判定することができる。
【０１２０】
また、本実施例２に開示した干渉判定装置２は、分割によって得られた平面の輪郭線の数が所定数よりも多い場合に当該平面を複数の平面に分割することで、精度・速度・メモリ消費のバランスがとれた干渉チェックが可能となる。
【０１２１】
また、本実施例２に開示した干渉判定装置２は、１つの部品の平面の内側に他の部品の輪郭線が接する場合に平面に基づいて干渉状態の判定を行なうことで、平面内部に他の部品の輪郭が接する状態であっても干渉の判定を行なうことができる。
【０１２２】
なお、本実施例２に開示した各処理をＣＰＵに実行させ、本実施例２に開示した各情報をメモリなどの任意の記録媒体に格納することで、コンピュータ装置を干渉判定装置として動作させる干渉判定プログラムを得ることができる。コンピュータは、演算装置とメモリを有する装置であれば、例えば携帯電話端末など任意の装置であってよい。
【０１２３】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１２４】
（付記１）３次元ポリゴンモデルで示された第１の部品と第２の部品の情報を入力するポリゴンデータ入力部と、
前記第１の部品を前記第１の部品の表面を構成する平面に分割し、前記第２の部品を前記第２の部品の表面を構成する平面に分割する分割部と、
前記分割部による分割によって得られた各平面について少なくとも輪郭の情報を当該平面に関する情報として作成する平面情報作成部と、
前記第１の部品から得られた平面の輪郭と前記第２の部品から得られた平面の輪郭とを比較して前記第１の部品と前記第２の部品との干渉状態を判定する平面干渉判定部と
を備えたことを特徴とする干渉判定装置。
【０１２５】
（付記２）前記第１の部品の境界ボリュームと前記第２の部品の境界ボリュームとを比較して干渉判定を行なう境界ボリューム干渉判定部をさらに備え、前記平面干渉判定部は、前記境界ボリューム干渉判定部による判定の結果、干渉の可能性がある場合に前記干渉判定を行うことを特徴とする付記１に記載の干渉判定装置。
【０１２６】
（付記３）前記分割部は、法線が同一方向である複数のポリゴンを１つの平面とすることを特徴とする付記１または２に記載の干渉判定装置。
【０１２７】
（付記４）前記平面情報作成部は、前記分割部によって得られた平面を内包する平面状の境界ボリュームを作成し、前記平面状の境界ボリュームを用いて前記第１の部品から得られた平面と前記第２の部品から得られた平面との交線を求め、当該交線と前記輪郭との関係に基づいて前記干渉状態の判定を行なうことを特徴とする付記１〜３のいずれか一つに記載の干渉判定装置。
【０１２８】
（付記５）前記平面情報作成部は、前記平面の輪郭について当該輪郭が前記平面の外縁であるか内縁であるかを識別する情報をさらに作成し、前記平面干渉判定部は、前記輪郭が外縁であるか内縁であるかをさらに用いて前記干渉状態の判定を行なうことを特徴とする付記１〜４のいずれか一つに記載の干渉判定装置。
【０１２９】
（付記６）前記平面情報作成部は、前記平面の輪郭について当該輪郭を共用する同一部品の他の平面との角度を示す情報をさらに作成し、前記平面干渉判定部は、前記角度を示す情報をさらに用いて前記干渉状態の判定を行なうことを特徴とする付記１〜４のいずれか一つに記載の干渉判定装置。
【０１３０】
（付記７）前記分割部は、分割によって得られた平面の輪郭線の数が所定数よりも多い場合に当該平面を複数の平面に分割することを特徴とする付記１〜６のいずれか一つに記載の干渉判定装置。
【０１３１】
（付記８）前記平面干渉判定部は、前記第１の部品から得られた平面の輪郭線の内側に前記第２の部品から得られた平面の輪郭線が接する場合に前記第１の部品から得られた平面の法線に基づいて前記干渉状態の判定を行なうことを特徴とする付記１〜７のいずれか一つに記載の干渉判定装置。
【０１３２】
（付記９）３次元ポリゴンモデルで示された第１の部品と第２の部品の情報を入力するステップと、
前記第１の部品を前記第１の部品の表面を構成する平面に分割し、前記第２の部品を前記第２の部品の表面を構成する平面に分割するステップと、
前記分割部による分割によって得られた各平面について少なくとも輪郭の情報を当該平面に関する情報として作成するステップと、
前記第１の部品から得られた平面の輪郭と前記第２の部品から得られた平面の輪郭とを比較して前記第１の部品と前記第２の部品との干渉状態を判定するステップと
を含んだことを特徴とする干渉判定方法。
【０１３３】
（付記１０）コンピュータに、
３次元ポリゴンモデルで示された第１の部品と第２の部品の情報を入力する手順と、
前記第１の部品を前記第１の部品の表面を構成する平面に分割し、前記第２の部品を前記第２の部品の表面を構成する平面に分割する分割手順と、
前記分割部による分割によって得られた各平面について少なくとも輪郭の情報を当該平面に関する情報として作成する手順と、
前記第１の部品から得られた平面の輪郭と前記第２の部品から得られた平面の輪郭とを比較して前記第１の部品と前記第２の部品との干渉状態を判定する手順と
を実行させることを特徴とする干渉判定プログラム。
【符号の説明】
【０１３４】
１，２  干渉判定装置
３  入力装置
１１  ポリゴンデータ入力部
１２  分割部
１３  平面情報作成部
１４  平面干渉判定部
２１  モデルデータベース
２２  部品境界ボリューム管理部
２３  分割部
２４  境界ボリューム干渉判定部
２５  記録部
２６  出力部
３０  平面情報作成部
３１  輪郭ライン生成部
３２  分割可否判定部
３３  ライン属性生成部
３４  ライン角度属性生成部
３５  平面境界ボリューム管理部
４０  平面干渉判定部
４１  輪郭境界干渉判定部
４２  内外判定部
４３  角度判定部
４４  対象判定部
【図１】
0005434651.tif 000002
【図２】
0005434651.tif 000003
【図３】
0005434651.tif 000004
【図４】
0005434651.tif 000005
【図５】
0005434651.tif 000006
【図６】
0005434651.tif 000007
【図７】
0005434651.tif 000008
【図８】
0005434651.tif 000009
【図９】
0005434651.tif 000010
【図１０】
0005434651.tif 000011
【図１１】
0005434651.tif 000012
【図１２】
0005434651.tif 000013
【図１３】
0005434651.tif 000014
【図１４】
0005434651.tif 000015
【図１５】
0005434651.tif 000016
【図１６】
0005434651.tif 000017
【図１７】
0005434651.tif 000018
【図１８】
0005434651.tif 000019
【図１９】
0005434651.tif 000020
【図２０】
0005434651.tif 000021
【図２１】
0005434651.tif 000022
【図２２】
0005434651.tif 000023
【図２３】
0005434651.tif 000024
【図２４】
0005434651.tif 000025
【図２５】
0005434651.tif 000026
【図２６】
0005434651.tif 000027
【図２７】
0005434651.tif 000028
【図２８】
0005434651.tif 000029