(57)【要約】【課題】２つの曲面の干渉線を求める際、閉じた干渉線が複数存在する場合でも、開いた干渉線と閉じた干渉線が混在する場合でも、干渉線を効率良く求めることができるようにする。【解決手段】曲面タイプ変換部１３は干渉線を求める対象となる曲面が自由曲面でない場合に該曲面を自由曲面に変換し、干渉線上点計算部１４は２つの自由曲面を対象にして該２つの曲面のそれぞれの境界曲線上に位置する境界点となる干渉線上点、および前記境界曲線の内側に位置する内点となる干渉線上点を求め、干渉線上点登録部１５は求められた干渉線上点を境界点であるか内点であるかを区別して登録し、干渉線追跡部１６は登録された前記干渉線上点のうちから追跡開始点、通過点および追跡終了点を順次抽出することで干渉線を追跡する。その際、抽出された干渉線上点には使用済みフラグを付ける。【選択図】図２
2007140998.tif 000002
【特許請求の範囲】
【請求項１】
２つの曲面の干渉線を求めることができる３次元形状処理装置において、２つの自由曲面を対象にして該２つの曲面のそれぞれの境界曲線上に位置する境界点となる干渉線上点、および前記境界曲線の内側に位置する内点となる干渉線上点を求める干渉線上点計算手段と、前記干渉線上点を、前記境界点であるか前記内点であるかを区別して登録する登録手段と、登録された前記干渉点のうちから追跡開始点、通過点および追跡終了点を順次抽出することにより干渉線を追跡する干渉線追跡手段と、を備えたことを特徴とする３次元形状処理装置。
【請求項２】
請求項１記載の３次元形状処理装置において、前記干渉線を求める対象となる曲面が自由曲面でない場合に該曲面を自由曲面に変換する変換手段を備えたことを特徴とする３次元形状処理装置。
【請求項３】
請求項１または２記載の３次元形状処理装置において、前記干渉線追跡手段は、前記追跡開始点をもとに求めた通過点と登録された内点の位置関係を調べることにより登録された内点の１つを追跡中の干渉線の通過点とすることを特徴とする３次元形状処理装置。
【請求項４】
請求項３記載の３次元形状処理装置において、前記干渉線追跡手段は、追跡中の干渉線の通過点とした内点に使用済みであることを示すフラグを付加することを特徴とする３次元形状処理装置。
【請求項５】
請求項１または２記載の３次元形状処理装置において、前記干渉線追跡手段は、前記内点を追跡開始点とする干渉線の追跡時に、求められた通過点と前記追跡開始点の位置関係を調べて一致するとみなせる場合には当該干渉線の追跡を終了させることを特徴とする３次元形状処理装置。
【請求項６】
請求項１または２記載の３次元形状処理装置において、前記干渉線追跡手段は、前記境界点を追跡開始点とする干渉線の追跡時に、求められた通過点と登録された境界点の位置関係を調べて追跡中の干渉線の追跡終了点とみなせる境界点があれば追跡を終了することを特徴とする３次元形状処理装置。
【請求項７】
２つの曲面どうしの干渉線を求める３次元形状処理方法において、対象となる曲面が自由曲面でなければ自由曲面に変換し、２つの自由曲面を対象にして該２つの曲面のそれぞれの境界曲線上に位置する境界点となる干渉線上点、および前記境界曲線の内側に位置する内点となる干渉線上点を求め、求めた干渉線上点を、前記境界点であるか前記内点であるかを区別して登録した後、登録された前記干渉点のうちから追跡開始点、通過点および追跡終了点を順次抽出することにより干渉線を追跡することを特徴とする３次元形状処理方法。
【請求項８】
請求項７記載の３次元形状処理方法において、干渉線の追跡において、求められた通過点とテーブルに登録された内点の位置関係を調べて、追跡中の干渉線の通過点とみなせる内点があれば、その内点を追跡開始点から除外することを特徴とする３次元形状処理方法。
【請求項９】
請求項７記載の３次元形状処理方法において、前記内点を追跡開始点とする干渉線の追跡時に、求められた通過点と前記追跡開始点の位置関係を調べて一致するとみなせる場合には当該干渉線の追跡を終了させることを特徴とする３次元形状処理方法。
【請求項１０】
請求項７記載の３次元形状処理方法において、前記境界点を追跡開始点とする干渉線の追跡時に、求められた通過点と登録された境界点の位置関係を調べて追跡中の干渉線の追跡終了点とみなせる境界点があれば追跡を終了することを特徴とする３次元形状処理方法。
【請求項１１】
コンピュータプログラムにおいて、請求項７至請求項１０のいずれか１項に記載の３次元形状処理方法によった３次元形状処理を実行させることを特徴とするプログラム。
【請求項１２】
プログラムを記録した記憶媒体において、請求項１１記載のプログラムをコンピュータが読取可能な形式に記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元ＣＡＤ／ＣＡＭ／ＣＡＥ／ＣＧなどにおける３次元形状の生成・変形技術に係り、特に、２つの曲面の干渉線を求める干渉線生成技術に関する。
【背景技術】
【０００２】
媒介変数表現（パラメータ表現）された曲面どうしの干渉線を得る代表的な方法としては次の２つが広く知られている。なお、媒介変数表現（パラメータ表現）では、４つの境界曲線Ｋ（図６参照）で囲まれた曲面上の座標を２次元的に表現するに当たり、境界曲線Ｋどうしの４つの交点を（０，０）、（１，０）、（１，１）、（０，１）と２次元の座標値（Ｕ，Ｖ）で表現し、曲面上の他の座標については、Ｕ方向およびＶ方向とも一方の境界曲線上の位置から対向する他方の境界曲線上の位置までを等分して０から１までの間の座標値で表現する。
Ａ．対象となる曲面を再帰的に細分割していき、平面形状とみなすことできる微小曲面パッチ間で干渉計算を実施し、それらを繋げて干渉線を成す曲線列を求める（再帰分割法）。
Ｂ．干渉線上の通過点を追跡することにより得られる点群をもとに干渉線を成す曲線列を求める（追跡法）。
これら２つのうち追跡法には、３次元ＣＡＤ／ＣＡＭ／ＣＡＥ／ＣＧシステムの多くで採用されているトリム曲面を扱う場合に適応が容易であるというような利点がある。なお、トリム曲面とは、次の２つの構成要素から成る表現方法であり、穴や複雑な境界形状をもつ曲面形状を簡単に表現できる。
Ａ．媒介変数表現された曲面（母曲面）の形状
Ｂ．母曲面上で有効範囲を示す境界曲線列
トリム曲面を対象とする場合、再帰分割法では、一旦母曲面に対して処理を適用して干渉線を求めた後、境界曲線列の内側のみを抽出する必要がある。それに対して、追跡法は、後述するとおり、境界曲線をはじめから考慮した手法である。
追跡法に係る従来技術としては、特許文献１およびその文献に引用されている文献などが公知である。これらの従来技術によれば、まず、干渉線上の点のうち境界線上に位置する端点群を抽出して、それらを追跡の開始点または終了点とする。干渉線上の点のうち境界線上に位置する端点群を抽出できるのは干渉線が開いた曲線（列）を成す場合である。但し、干渉線が閉じた曲線（列）となる場合にも、この手法を適用することができる。つまり、開始点と終了点が一致する特別な場合と考えればよい。特許文献１でも、端点テーブルに登録すべき点の求め方の一つとして「内部の干渉点計算により求まった点」という表現で、この場合にも適用できることを示唆している。
【特許文献１】特許第３０５９４９５号
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、特許文献１などに示された従来技術においては、追跡の足掛かりとなる端点に関して、開いた曲線列となる場合には端点が１本の干渉線につき両端の２点になるに対して、閉じた曲線列となる場合の端点（より正確には通過点）は多数となる。これは、それぞれの求め方の違いにも依存する。開いた曲線列となる場合には、対象曲面のうちの一方の曲面と他方の曲面の境界曲線どうしの干渉点として求めることができる。開いた曲線列となる干渉線の端点は対象曲面のいずれかの境界曲線上にあるので、境界曲線と曲面のすべての組について調べれば必ず２点が求まる。これに対して、閉じた曲線列となる場合、干渉線上の１点のみを求めれば十分であるが、開いた曲線列となる場合のように効率よく求める計算方法がない。また、干渉線上の点が求まった段階、つまり追跡を開始する前では、閉じた曲線列となる干渉線が複数本ある場合に、それぞれがどの干渉線上のものかを識別できない。そもそも閉じた曲線列となる干渉線が何本あるかが分からない。
このように、閉じた曲線列となる場合の干渉線を得る処理については、考慮すべき点が多く、従来技術のままでは開いた曲線列となる場合と同じようには処理することができない。
本発明は、このような従来技術の問題を解決しようとするものであり、具体的には、２つの曲面どうしの干渉線について、閉じた曲線列となる干渉線が複数存在する場合でも干渉線を効率良く求めることができるし、さらには開いた曲線列を成すものと閉じた曲線列を成すものが混在する場合でも、干渉線を効率良く求めることができる３次元形状処理装置および３次元形状処理方法を提供することを目的とする。
【課題を解決するための手段】
【０００４】
前記した課題を解決するために、請求項１記載の３次元形状処理装置は、２つの曲面の干渉線を求めることができる３次元形状処理装置において、２つの自由曲面を対象にして該２つの曲面のそれぞれの境界曲線上に位置する境界点となる干渉線上点、および前記境界曲線の内側に位置する内点となる干渉線上点を求める干渉線上点計算手段と、干渉線上点を、前記境界点であるか前記内点であるかを区別して登録する登録手段と、登録された前記干渉点のうちから追跡開始点、通過点および追跡終了点を順次抽出することにより干渉線を追跡する干渉線追跡手段とを備える。
請求項２記載の３次元形状処理装置は、請求項１記載の３次元形状処理装置において、前記干渉線を求める対象となる曲面が自由曲面でない場合に該曲面を自由曲面に変換する変換手段を備える。
請求項３記載の３次元形状処理装置は、請求項１または２記載の３次元形状処理装置において、前記干渉線追跡手段は、前記追跡開始点をもとに求めた通過点と登録された内点の位置関係を調べることにより登録された内点の１つを追跡中の干渉線の通過点とする構成にする。
請求項４記載の３次元形状処理装置は、請求項３記載の３次元形状処理装置において、前記干渉線追跡手段は、追跡中の干渉線の通過点とした内点に使用済みであることを示すフラグを付加する構成にする。
請求項５記載の３次元形状処理装置は、請求項１または２記載の３次元形状処理装置において、前記干渉線追跡手段は、前記内点を追跡開始点とする干渉線の追跡時に、求められた通過点と前記追跡開始点の位置関係を調べて一致するとみなせる場合には当該干渉線の追跡を終了させる構成にする。
請求項６記載の３次元形状処理装置は、請求項１または２記載の３次元形状処理装置において、前記干渉線追跡手段は、前記境界点を追跡開始点とする干渉線の追跡時に、求められた通過点と登録された境界点の位置関係を調べて追跡中の干渉線の追跡終了点とみなせる境界点があれば追跡を終了する構成にする。
【０００５】
請求項７記載の方法は、２つの曲面どうしの干渉線を求める３次元形状処理方法において、対象となる曲面が自由曲面でなければ自由曲面に変換し、２つの自由曲面を対象にして該２つの曲面のそれぞれの境界曲線上に位置する境界点となる干渉線上点、および前記境界曲線の内側に位置する内点となる干渉線上点を求め、求めた干渉線上点を、前記境界点であるか前記内点であるかを区別して登録した後、登録された前記干渉点のうちから追跡開始点、通過点および追跡終了点を順次抽出することにより干渉線を追跡する構成にする。
請求項８記載の方法は、請求項７記載の３次元形状処理方法において、干渉線の追跡において、求められた通過点とテーブルに登録された内点の位置関係を調べて、追跡中の干渉線の通過点とみなせる内点があれば、その内点を追跡開始点から除外する構成にする。
請求項９記載の方法は、請求項７記載の３次元形状処理方法において、前記内点を追跡開始点とする干渉線の追跡時に、求められた通過点と前記追跡開始点の位置関係を調べて一致するとみなせる場合には当該干渉線の追跡を終了させる構成にする。
請求項１０記載の方法は、請求項７記載の３次元形状処理方法において、前記境界点を追跡開始点とする干渉線の追跡時に、求められた通過点と登録された境界点の位置関係を調べて追跡中の干渉線の追跡終了点とみなせる境界点があれば追跡を終了する構成にする。
請求項１１記載のプログラムは、コンピュータプログラムにおいて、請求項７至請求項１０のいずれか１項に記載の３次元形状処理方法によった３次元形状処理を実行させる構成にする。
請求項１２記載の記録媒体は、プログラムを記録した記録媒体において、請求項１１記載のプログラムを記録した構成にする。
【発明の効果】
【０００６】
本発明によれば、２つの曲面の干渉線を求める際、干渉線上点を求めて登録するときに境界点であるか内点であるかがわかるように登録でき、また干渉線上点を追跡するとき、一度用いた干渉線上点（内点）を追跡開始点から除外するので、開いた曲線列を成すものと閉じた曲線列を成すものが混在する場合でも干渉線を効率良く求めることができ、また、閉じた曲線列となる干渉線が複数存在する場合でも干渉線を効率良く求めることができる。
【発明を実施するための最良の形態】
【０００７】
以下、図面により本発明の実施形態を詳細に説明する。但し、この実施形態に記載される構成要素、種類、組み合わせ、形状、その相対位置などは特定的な記載がない限りこの説明の範囲をそれのみに限定する主旨ではなく、単なる説明例に過ぎない。
図１は、本発明の一実施形態を示す情報処理装置（例えばパーソナルコンピュータ）の構成図である。図示したように、この情報処理装置は、プログラムに従って演算や処理を行うＣＰＵ１、そのプログラムおよび各種データを一時的に記憶するメモリ（例えばＲＡＭ）２、プログラムやデータなどを入力するキーボード３、図形や文字などを画面上に表示する表示装置４、その表示装置４に表示された、一般にマウスカーソルと呼ばれる目印を人の操作に基づき移動させると共に、その移動に基づくデータを入力するためのポインティングデバイスであるマウス５、フロッピー（登録商標）ディスクやハードディスクなどの記憶媒体を収容する外部記憶装置６、それらを相互に接続するバスライン７を備えている。
このような構成で、この情報処理装置では、メモリ２や外部記憶装置６内に記憶された３次元形状データに基づいて３次元形状の図形を表示装置４に表示でき、キーボード３やマウス５を用いて図形編集などの操作を行うことができる。
以下、このような情報処理装置を利用した本発明の３次元形状処理装置の実施例を説明する。
【０００８】
＜実施例＞
図２は、この実施例の３次元形状処理装置の機能構成を示すブロック図である。各部はＣＰＵ１およびメモリ２などハードウェアとメモリ２に読み出されたプログラム（ソフトウェア）により実現され、図示したように、入力部１１、曲面タイプ判定部１２、曲面タイプ変換部１３、干渉線上点計算部１４、干渉線上点登録部１５、干渉線追跡部１６、出力部１７などから構成される。ここで、入力部１１はキーボード３、表示装置４、マウス５など入出力装置１０を介した作業者からの指示を入力したり、外部記憶装置６に保存された３次元形状データを入力したりする。また、出力部１７は表示装置４へ結果形状の図形を表示させたり外部記憶装置６に結果形状の図形データを保存したりする。なお、この実施例では、請求項記載の変換手段、干渉線上点計算手段、登録手段、および干渉線追跡手段がそれぞれ、曲面タイプ変換部１３、干渉線上点計算部１４、干渉線上点登録部１５、および干渉線追跡部１６により実現される。
【０００９】
図３は、２つの曲面Ｓ１とＳ２の干渉線（図６参照）を追跡法により求める処理において、干渉線上点を求めてテーブルに登録する処理の動作フロー図である。以下、この動作フローを説明する。
まず、入力部１１が曲面Ｓ１とＳ２の配置された３次元形状の形状データを取得し（ステップ１）、曲面タイプ判定部１２がその形状データをもとに曲面Ｓ１とＳ２が共に平面形状で平行か否かを調べる（ステップ２）。そして、平行な平面形状どうしであれば（ステップ２でＹＥＳ）、Ｓ１とＳ２は干渉しないかまたは重なり合って干渉線が存在しないケースであるので、処理を終了する。
それに対して、Ｓ１とＳ２のうち少なくとも一方が平面形状でないか、両者とも平面形状でも平行ではないならば（ステップ２でＮＯ）、曲面タイプ判定部１２は両者の干渉の有無を調べる（ステップ３）。例えば両者とも平面形状ではないならば曲面Ｓ１の凸包と曲面Ｓ２の凸包の干渉（ぶつかり）の有無を調べるのである。そして、凸包どうしに干渉がなければ、曲面どうしが干渉する可能性はないので（ステップ３でＮＯ）、処理を終了する。また、曲面が平面形状の場合には、凸包ではなく、その平面が乗る無限平面を使って、相手の曲面の凸包または無限平面との干渉の有無を調べ、干渉がなければ（ステップ３でＮＯ）処理を終了する。
一方、干渉があれば（ステップ３でＹＥＳ）、タイプ判定部１２は曲面Ｓ１が自由曲面か否かを判定する（ステップ４）。そして、自由曲面でないと判定されたならば（例えば平面や自然２次曲面などの場合）（ステップ４でＮＯ）、曲面タイプ変換部１３が等価な自由曲面（媒介変数で表現された曲面）に変換する（ステップ５）。同様に、曲面Ｓ２が自由曲面でないと判定されたならば（ステップ６でＮＯ）、曲面タイプ変換部１３が等価な自由曲面に変換する（ステップ７）。この実施例では、このように干渉線を求める対象とする曲面が自由曲面でなければ自由曲面に変換するので、対象とする曲面を自由曲面以外にも拡大できる。
【００１０】
続いて、干渉線上点計算部１４が自由曲面Ｓ１の各境界曲線Ｋ（図６参照）と自由曲面Ｓ２とが干渉するか否かを調べる干渉計算を行い、干渉点があれば、干渉線上点登録部１５がその干渉点の座標値などをメモリ２内に設けられたテーブルＴ１に端点（境界点）として登録する（ステップ８）。詳細には、登録される各点について以下の情報をテーブルＴ１に書き込む。
（Ａ）開いた曲線列を成す干渉線の端点であるか、閉じた曲線列を成す干渉線の通過点であるかを示すフラグ
（Ｂ）追跡に使用されたか否かを示すフラグ（登録時にはすべての点について「使用されていない」という意味のＦＡＬＳＥが設定される）
（Ｃ）実空間上における位置（座標値）
（Ｄ）自由曲面Ｓ１における位置（媒介変数値）
（Ｅ）自由曲面Ｓ２における位置（媒介変数値）
同様にして、干渉線上点計算部１４は自由曲面Ｓ２の各境界曲線と自由曲面Ｓ１の干渉計算を行い、干渉点があれば、干渉線上点登録部１５がその干渉点の座標値を境界曲線上にある端点（境界点）としてテーブルＴ１に登録する（ステップ９）。
次に、自由曲面Ｓ１と自由曲面Ｓ２の境界曲線上以外にある干渉点群を求め、それらを境界曲線列の内側に位置する内点としてテーブルＴ１に登録する（ステップ１０）。なお、内点となる干渉線上の通過点は、自由曲面Ｓ１を多面体近似する各平面要素と自由曲面Ｓ２を多面体近似する各平面要素の干渉計算で得られる点を近似点とする幾何的Ｎｅｗｔｏｎ−Ｒａｐｈｓｏｎ法により求めることができる。
この後は干渉線追跡部１６により干渉線追跡処理を行うが、これについては図４および図５に示した動作フロー図に従って説明する。
【００１１】
図４および図５に示した干渉線追跡処理では、媒介変数表現された２つの自由曲面Ｓ１とＳ２の干渉線を追跡法により求める処理において、テーブルＴ１に登録された干渉線上の通過点群（境界点も含む）をもとに干渉線を追跡する。
ここではまず、干渉線追跡部１６が自由曲面Ｓ１およびＳ２の形状データおよびテーブルＴ１内に登録されているデータを読み出す（ステップ２１）。
ステップ２２では、テーブルＴ１に登録されている点群のうち境界点つまり開いた曲線列を成す干渉線の端点となるもので、まだ追跡に使用されていない点（ＦＡＬＳＥの点）Ｐ０があるか否かを判定する。そして、そのような点Ｐ０があれば（ステップ２２でＹＥＳ）（この時点では当然そのような点がある）、点Ｐ０のデータを取り出す。このとき、点Ｐ０について、追跡に使用されたか否かを示すフラグの値をＴＲＵＥに設定する。
続いて、干渉線追跡部１６は点Ｐ０を開始点として干渉線の追跡を開始する（ステップ２３）。当該点Ｐｉにおいて、次の点（Ｐｉ＋１）への追跡方向は、当該点Ｐｉにおける自由曲面Ｓ１と自由曲面Ｓ２の接平面どうしの干渉計算で得られる。また、次の点（Ｐｉ＋１）は、当該点Ｐｉから追跡方向にある距離進んだ点を近似点とする幾何的Ｎｅｗｔｏｎ−Ｒａｐｈｓｏｎ法により求めることができる。
追跡の過程で、当該点Ｐｉの次の点（Ｐｉ＋１）を得たならば（ステップ２４）、干渉線追跡部１６は点（Ｐｉ＋１）の近傍にある点をテーブルＴ１中の未追跡の点群から探す（ステップ２５）。そして、該当するものがなければ（ステップ２５でＮＯ）、追跡を続ける。つまり点（Ｐｉ＋１）をもとに次の点（Ｐｉ＋２）を求める（ステップ２４）。
それに対して、テーブルＴ１に登録された点のなかに点（Ｐｉ＋１）の近傍に位置するものがある場合（ステップ２５でＹＥＳ）、その点Ｑにおける自由曲面Ｓ１と自由曲面Ｓ２の接平面どうしの干渉計算から点Ｑが現在追跡している干渉線上の点であるか否かを調べる。そして、点Ｑが現在追跡している干渉線上の点でない場合には、他に該当するものがないかどうかを調べ、なければステップ２４へ戻り、追跡を続ける。
一方、点Ｑが現在追跡している干渉線上の点である場合には、その点が境界点であれば（ステップ２６でＹＥＳ）、点Ｑについて追跡に使用されたか否かを示すフラグの値をＴＲＵＥに設定した上で、その干渉線の追跡を終了し、その時点までに追跡で得られた点群をもとに曲線列を構成し、テーブルＴ２に登録する（ステップ２８）。そして、ステップ２２から繰り返す。また、点Ｑが内点であれば（ステップ２６でＮＯ）、点Ｑについて追跡に使用されたか否かを示すフラグの値をＴＲＵＥに設定した上で（ステップ２７）ステップ２４へ戻り、追跡を続ける。なお、前記したようなフラグを付加するのは不要な重複処理を避けるためであり、これにより曲線列を効率的に求めることができる。
【００１２】
以上、ステップ２２からステップ２８までの一連の処理が終了した時点で、テーブルＴ２には自由曲面Ｓ１と自由曲面Ｓ２の干渉線のうち、開いた曲線列をなすもののすべてが求まっている。また、テーブルＴ１に登録された各点の、追跡に使用されたか否かを示すフラグの値は、以下のいずれかである。
（Ａ）すべての点がＴＲＵＥになっている。
（Ｂ）内点についてはＦＡＬＳＥのままのものがある。
（Ｂ）となっている場合（ステップ２９でＹＥＳ）、自由曲面Ｓ１と自由曲面Ｓ２の干渉線には閉じた曲線列を成すものがあることを意味している。そこで、干渉線追跡部１６はさらに以下の処理（図５参照）を実施する。
テーブルＴ１に登録されている点群のうち、内点でまだ追跡に使用されていない点Ｒ０（そのような点であればどれでもよい）を取り出す。このとき、点Ｒ０について、追跡に使用されたか否かを示すフラグの値をＴＲＵＥに設定する。そして、点Ｒ０を開始点として干渉線の追跡を開始する（ステップ３０）。こうして、この追跡の過程で当該点Ｒｉの次の点（Ｒｉ＋１）を求め（ステップ３１）、その点（Ｒｉ＋１）の近傍にその干渉線の追跡の開始点とした点Ｒ０が位置しないかどうかを調べる（ステップ３２）。その結果、点Ｒ０が点（Ｒｉ＋１）の近傍にあると判定されたならば（ステップ３２でＹＥＳ）、その干渉線の追跡を終了して、その時点までに追跡で得られた点群で曲線列を構成し、テーブルＴ２に登録する（ステップ３３）。
この後は、ステップ２９へ戻り、繰り返す。
【００１３】
一方、点Ｒ０が点（Ｒｉ＋１）の近傍にないと判定された場合には（ステップ３２でＮＯ）、点（Ｒｉ＋１）の近傍にある点をテーブルＴ１のなかの未追跡の点群から探し（ステップ３４）、該当するものがなければ（ステップ３４でＮＯ）、ステップ３１へ戻り、追跡を続ける。つまり、点（Ｒｉ＋１）をもとに次の点（Ｒｉ＋２）を求める。
それに対して、テーブルＴ１に登録された点のなかに点（Ｒｉ＋１）の近傍に位置するものがある場合（ステップ３４でＹＥＳ）、その点Ｕにおける自由曲面Ｓ１と自由曲面Ｓ２の接平面どうしの干渉計算から点Ｕが現在追跡している干渉線上の点であるか否かを調べる。そして、点Ｕが現在追跡している干渉線上の点でない場合には他に該当するものがないかどうかを調べ、なければステップ３１へ戻り、追跡を続ける。また、点Ｕが現在追跡している干渉線上の点である場合には、点Ｕについて追跡に使用されたか否かを示すフラグの値をＴＲＵＥに設定する（当該点を追跡済みにする）（ステップ３５）。そして、ステップ３１へ戻り、追跡を続ける。
以上のステップ２９からステップ３５までの一連の処理が終了した時点で、テーブルＴ２には自由曲面Ｓ１と自由曲面Ｓ２の干渉線のうち、閉じた曲線列を成すもののすべてが求まっている。つまり、この時点で、テーブルＴ２には曲面Ｓ１と曲面Ｓ２のすべての干渉線が求まっている。
このように、この実施例によれば、２つの曲面の干渉線を求める際、干渉線上点を求めて登録するときに境界点であるか内点であるかがわかるように登録でき、また干渉線上点を追跡するとき、一度用いた干渉線上点は使用済みを示すフラグをつけるので、開いた曲線列を成すものと閉じた曲線列を成すものが混在する場合でも干渉線を効率良く求めることができ、また、閉じた曲線列となる干渉線が複数存在する場合でも干渉線を効率良く求めることができる。
【００１４】
以上、本発明の一実施例を説明したが、説明したような３次元形状処理方法に従ってプログラミングしたプログラムを着脱可能な記録媒体に記録し、その記録媒体をこれまで本発明によった３次元形状処理を行えなかったパーソナルコンピュータなど情報処理装置に装着することにより、または、そのようなプログラムをネットワークを介してそのような情報処理装置へ転送することにより、そのような情報処理装置においても本発明によった３次元形状処理を行うことができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施形態を示す情報処理装置の構成図である。
【図２】本発明の一実施例を示す３次元形状処理装置の機能構成に関するブロック図である。
【図３】本発明の一実施例を示す３次元形状処理装置における干渉線上点算出・登録処理の動作フロー図である。
【図４】本発明の一実施例を示す３次元形状処理装置における干渉線追跡処理に関する動作フロー図である。
【図５】本発明の一実施例を示す３次元形状処理装置における干渉線追跡処理に関する他の動作フロー図である。
【図６】本発明の３次元形状処理に係る説明図である。
【符号の説明】
【００１６】
１  ＣＰＵ、４  表示装置、６  外部記憶装置、１１  入力部、１３  曲面タイプ変換部、１４  干渉線上点計算部、１５  干渉線上点登録部、１６  干渉線追跡部、１７  出力部
【図１】
2007140998.tif 000003
【図２】
2007140998.tif 000004
【図３】
2007140998.tif 000005
【図４】
2007140998.tif 000006
【図５】
2007140998.tif 000007
【図６】
2007140998.tif 000008