(57)【要約】【課題】部分モデルや面の境界箱情報を１つの座標系を基準とする値で境界箱テーブルに保持することにより、干渉チェックに要する処理時間を削減することができる干渉モデル検出方法を提供する。【解決手段】ポリゴンメッシュで表現される、３次元形状アセンブリモデルを構成する部分モデル間の干渉状態を検出する干渉モデル検出方法において、干渉検出対象の３次元形状アセンブリモデルの各部分モデル、その部分モデルを構成している面、およびその面を構成しているポリゴンについて、前記３次元形状アセンブリモデル内で共通の座標系を基準とする座標値の境界箱情報を求めてその境界箱情報をテーブルに格納しておき（ステップＳ１）、その境界箱情報を用いて、部分モデル、面、ポリゴンの順でラフ干渉チェックを行うことにより部分モデル間の干渉を検出する（ステップＳ２〜ステップＳ１１）構成にした。【選択図】　　　図３
2004062546.tif 000002
【特許請求の範囲】
【請求項１】
ポリゴンメッシュで表現される、３次元形状アセンブリモデルを構成する部分モデル間の干渉状態を検出することができる３次元形状処理装置において、干渉検出対象の３次元形状アセンブリモデルの各部分モデル、その部分モデルを構成している面、およびその面を構成しているポリゴンについて、前記３次元形状アセンブリモデル内で共通の座標系を基準とする座標値の境界箱情報を求める境界箱算出手段と、その境界箱情報を用いて、部分モデル、面、ポリゴンの順でラフ干渉チェックを行うことにより部分モデル間の干渉を検出する干渉検出手段とを備えたことを特徴とする３次元形状処理装置。
【請求項２】
ポリゴンメッシュで表現される、３次元形状アセンブリモデルを構成する部分モデル間の干渉状態を検出する干渉モデル検出方法において、干渉検出対象の３次元形状アセンブリモデルの各部分モデル、その部分モデルを構成している面、およびその面を構成しているポリゴンについて境界箱情報を求めておき、その境界箱情報を用いて、部分モデル、面、ポリゴンの順でラフチェックを行うことにより部分モデル間の干渉を検出することを特徴とする干渉モデル検出方法。
【請求項３】
請求項２記載の干渉モデル検出方法において、部分モデル、面、ポリゴンの境界箱情報として、干渉検出対象の３次元形状アセンブリモデル内で共通の座標系を基準とする座標値を用いることを特徴とする干渉モデル検出方法。
【請求項４】
請求項３記載の干渉モデル検出方法において、部分モデルの境界箱情報を求める際には、その部分モデルの各面を構成しているすべてのポリゴンに含まれる頂点座標値を、前記共通の座標系を基準とする頂点座標値に変換し、変換した頂点座標値から３次元空間上のＸ、Ｙ、Ｚ各軸方向の成分の最大値および最小値を検出することにより境界箱情報を求めることを特徴とする干渉モデル検出方法。
【請求項５】
請求項３記載の干渉モデル検出方法において、面の境界箱情報を求める際には、その面を構成しているポリゴンに含まれる頂点座標値を、前記共通の座標系を基準とする頂点座標値に変換し、変換した頂点座標値から３次元空間上のＸ、Ｙ、Ｚ各軸方向の成分の最大値および最小値を検出することにより境界箱情報を求めることを特徴とする干渉モデル検出方法。
【請求項６】
情報処理装置上で実行されるプログラムにおいて、請求項２乃至請求項５のいずれか１項に記載の干渉モデル検出方法を実行させるようにプログラミングされていることを特徴とするプログラム。
【請求項７】
プログラムを記憶した記憶媒体において、請求項６記載のプログラムを記憶したことを特徴とする記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＣＡＤ（Ｃｏｍｐｕｔｅｒ　Ａｄｄｅｄ　Ｄｅｓｉｇｎ）／ＣＡＭ（Ｃｏｍｐｕｔｅｒ　Ａｄｄｅｄ　Ｍａｎｕｆａｃｔｕｒｉｎｇ）システムにおける形状評価などに用いることができる３次元形状の干渉モデル検出方法に関する。
【０００２】
【従来の技術】
近年、３次元ＣＡＤ／ＣＡＭ／ＣＧシステムなどの普及により３次元形状データの利用者層が拡大するとともに、サブアセンブリや部品など部分モデルの干渉（重なり・ぶつかり状態）を検出するシミュレーションや組み立て性の検証など様々な局面で３次元形状データを有効活用する機会が増えており、ＣＡＤシステムなどにより生成された３次元形状データを製造工程へ移行する前に、コンピュータ上で解析／検証するのは今やあたりまえになりつつある。なかでも、複数の部分モデル（サブアセンブリや部品に相当）から構成されるアセンブリモデルについて、その個々の部分モデル間の干渉を検出する機能は、ＣＡＤ／ＣＡＭシステムにおいて設計ミスや入力ミスをチェックする形状評価などに有用な機能である。
ところで、３次元形状表示において形状を表現するために利用されるデータは、多くの場合、自由曲面をポリゴンメッシュで近似生成したデータである。そのようなことから、それぞれポリゴンメッシュにより表現される複数の部分モデルの干渉状態を検出する場合、最終的にはポリゴン間の干渉計算を実施して、部分モデル同士が干渉しているかどうかを判定する必要がある。
しかし、個々の部分モデルを構成するポリゴン同士で総当りの干渉チェックを実施するとなると、大規模アセンブリでは膨大な処理時間が必要となり、対話的な操作性を著しく損なうことになる。
そのため、特開平９−２７０４６号公報では、非凸部を含む多面体間の干渉チェックの場合について、まず、凸部を検出し、その凸部における干渉チェックを行い、干渉しているときのみその近接ポリゴンについてポリゴン間の干渉チェックを行う方法が開示されている。
また、特開平９−１７９８９６号公報では、干渉の有無を検査する検査点を定義し、その検査点における立体角を用いてその検査点が他方の図形に含まれるか否かを判定することにより干渉の有無を検査する方法が開示されている。
【０００３】
【発明が解決しようとする課題】
しかしながら、前記した特開平９−２７０４６号公報に示された従来技術においては、凸部を検出する処理が必要であるので、サブアセンブリのような複雑な形状では計算が複雑になるという問題点がある。また、特開平９−１７９８９６号公報に示された従来技術では検査点を定義する場合にしか有効でない。
そこで、当出願者により最近出願された発明では、コストのかかるポリゴン間の干渉検出を行う前に、部分モデルを含む３次元空間上の最小外郭を表現する直方体領域である境界箱を利用してラフチェックを行うことにより、干渉していない状態を早期に除外することができ、全体の処理速度を向上させることができる。なお、境界箱とは、幾何情報が定義される３次元空間上のＸＹ平面、ＹＺ平面、ＺＸ平面それぞれに平行な面をもち、対象とする３次元形状に外接する直方体を意味し、各方向（Ｘ、Ｙ、Ｚ）の最小値および最大値から成る計６値により表現される。また、境界箱同士の干渉状態については、Ｘ、Ｙ、Ｚいずれかの方向でいずれか一方の最小値が他方の最大値を上回れば干渉していないという判定方法を用いることができ、したがって、少ない計算コストでラフチェック（干渉の可能性がない状態の検出）を実施することができる。
本発明では、さらに、部分モデルおよび面の境界箱情報を１つの座標系を基準とする値で境界箱テーブルに保持して、干渉チェック処理内の座標変換の回数を削減することにより、干渉チェックに要する処理時間を削減することができる干渉モデル検出方法などを提供する。
【０００４】
【課題を解決するための手段】
前記の課題を解決するために、請求項１記載の発明では、ポリゴンメッシュで表現される、３次元形状アセンブリモデルを構成する部分モデル間の干渉状態を検出することができる３次元形状処理装置において、干渉検出対象の３次元形状アセンブリモデルの各部分モデル、その部分モデルを構成している面、およびその面を構成しているポリゴンについて、前記３次元形状アセンブリモデル内で共通の座標系を基準とする座標値の境界箱情報を求める境界箱算出手段と、その境界箱情報を用いて、部分モデル、面、ポリゴンの順でラフ干渉チェックを行うことにより部分モデル間の干渉を検出する干渉検出手段とを備えた。
したがって、個々の部分モデルを構成するポリゴン同士で総当りの干渉チェックを実施する必要がなくなり、大規模アセンブリであっても膨大な処理時間を必要とせず、そのため、対話的な操作性も損なわれないし、干渉チェック処理内の座標変換の回数を削減できることから、干渉チェックに要する処理時間をさらに削減することができる。
また、請求項２記載の発明では、ポリゴンメッシュで表現される、３次元形状アセンブリモデルを構成する部分モデル間の干渉状態を検出する干渉モデル検出方法において、干渉検出対象の３次元形状アセンブリモデルの各部分モデル、その部分モデルを構成している面、およびその面を構成しているポリゴンについて境界箱情報を求めておき、その境界箱情報を用いて、部分モデル、面、ポリゴンの順でラフチェックを行うことにより部分モデル間の干渉を検出する構成にした。
したがって、ラフチェックに必要な境界箱情報の計算の重複が除かれ、その分、処理時間が削減される。
また、請求項３記載の発明では、請求項２記載の発明において、部分モデル、面、ポリゴンの境界箱情報として、干渉検出対象の３次元形状アセンブリモデル内で共通の座標系を基準とする座標値を用いる構成にした。
これにより、個々の部分モデルで座標系が異なっていてもあらかじめ作成した境界箱情報を用いてラフチェックを行うことができ、したがって、そのような場合でも境界箱情報の計算の重複が除かれ、その分、処理時間が削減される。
【０００５】
また、請求項４記載の発明では、請求項３記載の発明において、部分モデルの境界箱情報を求める際には、その部分モデルの各面を構成しているすべてのポリゴンに含まれる頂点座標値を、前記共通の座標系を基準とする頂点座標値に変換し、変換した頂点座標値から３次元空間上のＸ、Ｙ、Ｚ各軸方向の成分の最大値および最小値を検出することにより境界箱情報を求める構成にした。
これにより、共通の座標系を基準とする頂点座標値を面間のラフ干渉検出の際にも共通に用いることにより処理時間を削減することができる。
また、請求項５記載の発明では、請求項３記載の発明において、面の境界箱情報を求める際には、その面を構成しているポリゴンに含まれる頂点座標値を、前記共通の座標系を基準とする頂点座標値に変換し、変換した頂点座標値から３次元空間上のＸ、Ｙ、Ｚ各軸方向の成分の最大値および最小値を検出することにより境界箱情報を求める構成にした。
これにより、共通の座標系を基準とする頂点座標値を部分モデルのラフ干渉検出の際にも共通に用いることにより処理時間を削減することができる。
また、請求項６記載の発明では、情報処理装置上で実行されるプログラムにおいて、請求項２乃至請求項５のいずれか１項に記載の干渉モデル検出方法を実行させるようにプログラミングした。
これにより、情報処理装置を用いて請求項２乃至請求項５のいずれか１項に記載の効果を得ることができる。
また、請求項７記載の発明では、プログラムを記憶した記憶媒体において、請求項６記載のプログラムを記憶した。
これにより、その記憶媒体をこれまで請求項２乃至請求項５のいずれか１項に記載の発明によった干渉モデル検出を行なえなかったパーソナルコンピュータなど情報処理装置に装着することにより、その情報処理装置においても請求項２乃至請求項５のいずれか１項に記載の発明の効果を得ることができる。
【０００６】
【発明の実施の形態】
以下、図面により本発明の実施の形態を詳細に説明する。
図１は本発明が実施される３次元形状処理装置のハードウェア構成図である。図示したように、この３次元形状処理装置は、プログラムに従って動作するＣＰＵ１、プログラムや各種データを一時的に記憶するメモリ（例えばＲＡＭ）２、前記プログラムや各種データを保存しておく外部記憶装置（例えばハードディスク装置）３、着脱可能な記憶媒体からデータを読み込む読み込み装置、キーボード、マウスなどを有して３次元形状データを含む各種データや指示を入力する入力装置４、３次元形状モデルなどを表示する表示装置５などを備える。
図２は、前記したようなハードウェアと前記プログラム（ソフトウェア）により実現される、本発明の一実施例を示す３次元形状処理システムのシステム構成図である。図示したように、この実施例の３次元形状処理システムは、入力装置４から３次元形状データを含む各種データや指示を入力させる入力部１１、入力された３次元形状データを取得して形状記憶部に格納する入力読み取り部１２、３次元形状データなどを一時的に記憶するメモリ領域である形状記憶部１３、干渉検出対象の３次元形状アセンブリモデルの各部分モデル、その各部分モデルを構成している面、およびその各面を構成しているポリゴンの境界箱情報を求める境界箱情報生成部１４、境界箱情報を用いて各部分モデル間の干渉チェックを行って干渉の有無を判定するモデル境界干渉判定部１５、同様に面間の干渉チェックを行って干渉の有無を判定する面境界干渉判定部１６、同様にポリゴン間の干渉チェックを行って干渉の有無を判定するポリゴン境界干渉判定部１７、表示データを生成して表示装置５に３次元形状モデルなどを表示させる形状表示部１８を備える。なお、この実施例では、請求項１記載の境界箱算出手段が前記境界箱情報生成部１４により実現され、干渉検出手段が、モデル境界干渉判定部１５、面境界干渉判定部１６、およびポリゴン境界干渉判定部１７により実現される。また、前記部分モデル（以下、単にモデルと称す）とは、３次元形状アセンブリを構成するサブアセンブリや部品を３次元形状データで表現したものである。
【０００７】
図３に、前記したような３次元形状処理システムによって実行される干渉モデル検出の動作を示す。以下、図３に従って、この動作を説明する。
まず、アセンブリモデルを構成する各モデル、各モデルを構成する各面（Ｆａｃｅ）、さらに各面を構成する各ポリゴンについて、それぞれの単位で境界箱情報を生成し、モデルの識別子（以下、ＩＤと称す）や面ＩＤ、ポリゴンＩＤにより参照可能にした境界箱情報を、モデル境界箱情報テーブル、面境界箱情報テーブル、およびポリゴン境界箱情報テーブルに各々格納する（ステップＳ１）。
その際、モデルや面の境界箱情報は、モデルや面を構成するポリゴンメッシュのすべての頂点座標値を含むような直方体領域として生成してもよいし、また、ＣＡＤシステムなど外部のシステムから当該形状データについてモデルや面の境界箱情報を取得できる場合には、それを用いてもよい。例えばモデルの境界箱情報をポリゴンメッシュの頂点座標値から生成する場合には、頂点座標値の各成分（Ｘ、Ｙ、Ｚ）ごとに最小値（Ｘ−ｍｉｎ、Ｙ−ｍｉｎ、Ｚ−ｍｉｎ）、最大値（Ｘ−ｍａｘ、Ｙ−ｍａｘ、Ｚ−ｍａｘ）を求めることで境界箱情報が得られる。なお、ポリゴンメッシュの頂点座標値から境界箱情報を生成するとき、その頂点座標値が１つの座標系を基準としていない場合、例えば頂点座標値がアセンブリモデル中のモデルごとにローカルな座標系を基準とする値である場合は、アセンブリモデルの最上位にあたるトップアセンブリモデルを基準としてモデルごとに変換を施し、すべて共通の座標系基準の値に直した上で、各成分ごとの最大値および最小値を検索して格納する。また、ＣＡＤシステムなど外部のシステムから取得されるモデルや面の境界箱情報が、アセンブリモデル内で１つの座標系を基準とするものでない場合も、同様にしてポリゴンメッシュの頂点座標値から境界箱を生成する。
【０００８】
次に、境界箱情報を用いて干渉状態（重なり・ぶつかり状態）を調査するラフチェックを行う。前記モデル境界箱情報テーブル、面境界箱情報テーブル、およびポリゴン境界箱情報テーブルを適宜参照することにより、以下に示すようなラフチェックを行うのである。
まず、アセンブリモデルから２つのモデルを抽出するすべての組み合わせ中の一つの組み合わせについて、モデルの境界箱同士が干渉するかどうかを調べる（ステップＳ２）。モデルの境界箱情報をステップＳ１において生成したモデル境界箱情報テーブルより参照し、Ｘ、Ｙ、Ｚいずれかの方向でいずれか一方の境界箱の最小値が他方の境界箱の最大値を上回れば干渉していないと判定するのである。そして、一つの組み合わせのモデルの境界箱が干渉しないと判定された場合は（ステップＳ３でＮＯ）、次のモデルの組み合わせに処理を移す（ステップＳ２）。
それに対して、モデルの境界箱が干渉していると判定された場合（ステップＳ３でＹＥＳ）、当該２モデルは干渉の可能性があるとみて、当該２モデルについて、それぞれから１面づつ抽出するすべての組み合わせ中の一つについて面の境界箱が干渉するかどうかを調べる（ステップＳ４）。なお、この際、面の境界箱情報は、ステップＳ１において生成した面境界箱情報テーブルより参照する。そして、当該２面の境界箱が干渉しないと判定された場合は（ステップＳ５でＮＯ）、次の面の組み合わせに処理を移す（ステップＳ４）。
【０００９】
それに対して、当該２面の境界箱が干渉すると判定された場合（ステップＳ５でＹＥＳ）、当該２面は干渉の可能性があるとみて、当該２面について、それぞれから１つづつポリゴンを抽出するすべての組み合わせ中の一つについて、ポリゴンの境界箱が干渉するかどうかを調べる（ステップＳ６）。なお、その際、ポリゴンの境界箱情報は、ステップＳ１において生成したポリゴン境界箱情報テーブルより参照する。そして、当該２ポリゴンの境界箱が干渉しないと判定される場合は（ステップＳ７でＮＯ）、次のポリゴンの組み合わせに処理を移す（ステップＳ６）。
それに対して、当該２ポリゴンの境界箱が干渉すると判定された場合（ステップＳ７でＹＥＳ）、当該２ポリゴンは干渉の可能性があるとみて、当該２ポリゴンについてポリゴン自身が干渉状態にあるかどうかをチェックする（ステップＳ８）。なお、ポリゴン間の干渉チェックの方法は、一般的に知られた幾何解析的手法を用いればよい。例えば、一方のポリゴンを構成する頂点間を結ぶ線分と他方のポリゴンの乗る平面との干渉計算を実施し、得られる交点がそのポリゴン内に存在するかどうかを判定するのである。そして、ポリゴンが干渉していると判定された場合には、当該２モデルが、当該２面の当該２ポリゴンの位置で干渉しているという結果が得られる。
一つのポリゴンの組みについて干渉検出処理が終了すると、ポリゴンの組み合わせすべてについて干渉チェックが終了したか否かを判定し（ステップＳ９）、終了していなければ（ステップＳ９でＮＯ）、次のポリゴンの組み合わせに処理を移す（ステップＳ６）。そして、当該２面のポリゴンの組み合わせすべてについて干渉チェックが終了すると（Ｓステップ９でＹＥＳ）、当該２モデルの面の組み合わせすべてについて干渉チェックが終了したかどうかを判定し（ステップＳ１０）、修了していなければ（ステップＳ１０でＮＯ）次の面の組み合わせに処理を移す（ステップＳ４）。
こうして、当該２モデルの面の組み合わせすべてについて干渉チェックが修了すると（ステップＳ１０でＹＥＳ）、モデルの組み合わせすべてについて干渉チェックが終了したかどうかを判定し（ステップＳ１１）、修了していなければ（ステップＳ１１でＮＯ）次のモデルの組み合わせに処理を移す（ステップＳ２）。そして、モデルの組み合わせすべてについて干渉チェックが終了すると（ステップＳ１１でＹＥＳ）、この動作フローを修了させる。
【００１０】
以上、図２に示したシステム構成の場合で本発明の一実施例を説明したが、説明したような干渉モデル検出方法に従ってプログラミングしたプログラムを着脱可能な記憶媒体に記憶し、その記憶媒体をこれまで本発明によった干渉モデル検出を行なえなかったパーソナルコンピュータなど情報処理装置に装着することにより、または、そのようなプログラムをネットワークを介してそのような情報処理装置へ転送することにより、その情報処理装置においても本発明によった干渉モデル検出を行うことができる。
【００１１】
【発明の効果】
以上説明したように、本発明によれば、請求項１記載の発明では、ポリゴンメッシュで表現される、３次元形状アセンブリモデルを構成する部分モデル間の干渉状態を検出する際、干渉検出対象の３次元形状アセンブリモデルの各部分モデル、その部分モデルを構成している面、およびその面を構成しているポリゴンについて、３次元形状アセンブリモデル内で共通の座標系を基準とする座標値の境界箱情報が求められ、その境界箱情報を用いて、部分モデル、面、ポリゴンの順でラフ干渉チェックを行うことにより部分モデル間の干渉が検出されるので、個々の部分モデルを構成するポリゴン同士で総当りの干渉チェックを実施する必要がなくなり、したがって、大規模アセンブリであっても膨大な処理時間を必要としせず、そのため、対話的な操作性も損なわれないし、干渉チェック処理内の座標変換の回数を削減できることから、干渉チェックに要する処理時間をさらに削減することができる。
また、請求項２記載の発明では、ポリゴンメッシュで表現される、３次元形状アセンブリモデルを構成する部分モデル間の干渉状態を検出する際、干渉検出対象の３次元形状アセンブリモデルの各部分モデル、その部分モデルを構成している面、およびその面を構成しているポリゴンについてあらかじめ境界箱情報が算出・記憶され、その境界箱情報を用いて、部分モデル、面、ポリゴンの順でラフチェックを行うことにより部分モデル間の干渉が検出されるので、ラフチェックに必要な境界箱情報の計算の重複が除かれ、その分、処理時間が削減される。
また、請求項３記載の発明では、請求項２記載の発明において、部分モデル、面、ポリゴンの境界箱情報として、干渉検出対象の３次元形状アセンブリモデル内で共通の座標系を基準とする座標値が用いられるので、個々の部分モデルで座標系が異なっていてもあらかじめ作成した境界箱情報を用いてラフチェックを行うことができ、したがって、そのような場合でも境界箱情報の計算の重複が除かれ、その分、処理時間が削減される。
【００１２】
また、請求項４記載の発明では、請求項３記載の発明において、部分モデルの境界箱情報を求める際には、その部分モデルの各面を構成しているすべてのポリゴンに含まれる頂点座標値が前記共通の座標系を基準とする頂点座標値に変換され、変換された頂点座標値から３次元空間上のＸ、Ｙ、Ｚ各軸方向の成分の最大値および最小値が検出され、その数値を用いて境界箱情報が求められるので、共通の座標系を基準とする頂点座標値を面間のラフ干渉検出の際にも共通に用いることにより処理時間を削減することができる。
また、請求項５記載の発明では、請求項３記載の発明において、面の境界箱情報を求める際には、その面を構成しているポリゴンに含まれる頂点座標値が前記共通の座標系を基準とする頂点座標値に変換され、変換された頂点座標値から３次元空間上のＸ、Ｙ、Ｚ各軸方向の成分の最大値および最小値が検出され、その数値を用いて境界箱情報が求められるので、共通の座標系を基準とする頂点座標値を部分モデルのラフ干渉検出の際にも共通に用いることにより処理時間を削減することができる。
また、請求項６記載の発明では、情報処理装置上で実行されるプログラムが請求項２乃至請求項５のいずれか１項に記載の干渉モデル検出方法を実行させるようにプログラミングされているので、情報処理装置を用いて請求項２乃至請求項５のいずれか１項に記載の効果を得ることができる。
また、請求項７記載の発明では、請求項６記載のプログラムを着脱可能な記憶媒体に記憶することができるので、その記憶媒体をこれまで請求項２乃至請求項５のいずれか１項に記載の発明によった干渉モデル検出を行なえなかったパーソナルコンピュータなど情報処理装置に装着することにより、その情報処理装置においても請求項２乃至請求項５のいずれか１項に記載の発明の効果を得ることができる。
【図面の簡単な説明】
【図１】本発明が実施される３次元形状処理装置のハードウェア構成図である。
【図２】本発明の一実施例を示す３次元形状処理システムのシステム構成図である。
【図３】本発明の一実施例を示す干渉モデル検出方法の動作フロー図である。
【符号の説明】
１　ＣＰＵ、２　メモリ、３　外部記憶装置、４　入力装置、５　表示装置、１１　入力部、１３　形状記憶部、１４　境界箱情報生成部、１５　モデル境界干渉判定部、１６　面境界干渉判定部、１７　ポリゴン境界干渉判定部、１８　形状表示部
【図１】
2004062546.tif 000003
【図２】
2004062546.tif 000004
【図３】
2004062546.tif 000005