(57)【要約】【課題】単一曲面の自己干渉を簡単なアルゴリズムで検出する。【解決手段】曲面上に格子点を生成する格子点生成手段２０と、生成した格子点情報からポリゴンと境界の線分とを抽出するポリゴン生成手段２２と、前記抽出したポリゴンおよび線分の情報を用いて干渉の有無を判定する干渉判定手段２４とを備えた。【選択図】      図２
2004303042.tif 000002
【特許請求の範囲】
【請求項１】
単一曲面における自己干渉を判定する装置であって、曲面上に格子点を生成する格子点生成手段と、該格子点生成手段により生成した格子点情報からポリゴンと境界の線分とを抽出するポリゴン生成手段と、該ポリゴン生成手段により抽出したポリゴンおよび線分の情報を用いて干渉の有無を判定する干渉判定手段とを備えたことを特徴とする自己干渉判定装置。
【請求項２】
前記格子点生成手段は、前記曲面の形状に応じた間隔で格子点を生成することを特徴とする請求項１記載の自己干渉判定装置。
【請求項３】
前記ポリゴン生成手段は、前記格子点情報から３角形のポリゴンを生成し、生成したポリゴンおよび該ポリゴンの稜線となす線分の情報とを抽出することを特徴とする請求項１または２記載の自己干渉判定装置。
【請求項４】
前記干渉判定手段は、前記抽出したポリゴンと線分との交点を求め、該交点がポリゴン内の平面上にあるとき干渉すると判定することを特徴とする請求項１、２または３記載の自己干渉判定装置。
【請求項５】
単一曲面における自己干渉を判定する方法であって、曲面上に格子点を生成する格子点生成ステップと、該格子点生成ステップにより生成した格子点情報からポリゴンと境界の線分とを抽出するポリゴン生成ステップと、該ポリゴン生成ステップにより抽出したポリゴンおよび線分の情報を用いて干渉の有無を判定する干渉判定ステップとを備えたことを特徴とする自己干渉判定方法。
【請求項６】
前記格子点生成ステップは、前記曲面の形状に応じた間隔で格子点を生成することを特徴とする請求項５記載の自己干渉判定方法。
【請求項７】
前記ポリゴン生成ステップは、前記格子点情報から３角形のポリゴンを生成し、生成したポリゴンおよび該ポリゴンの稜線となす線分の情報とを抽出することを特徴とする請求項５または６記載の自己干渉判定方法。
【請求項８】
前記干渉判定ステップは、前記抽出したポリゴンと線分との交点を求め、該交点がポリゴン内の平面上にあるとき干渉すると判定することを特徴とする請求項５、６または７記載の自己干渉判定方法。
【請求項９】
請求項５乃至８の何れか一項に記載の自己干渉判定方法をコンピュータが制御可能にプログラミングしたことを特徴とする自己干渉判定プログラム。
【請求項１０】
請求項９に記載の自己干渉判定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば３次元ＣＡＤシステム等の３次元形状を扱う技術分野における曲面の自己干渉の判定技術に関する。
【０００２】
【従来の技術】
３次元ＣＡＤシステムでは、３次元形状を作成していく際、基本形状の平面や曲面の一部を持ち上げたり、へこましたりする変形操作を繰り返して、所望の形状を得るというモデリング手法をとることが多い。この際、変形した部分が他の曲面や平面、あるいは変形操作を施している自己の曲面に食い込む、いわゆる自己干渉を起こしてしまうことがある。自己干渉が起った立体はコンピュータの中だけに存在する形状であり、実世界には存在しない立体なので、これを検出する必要がある。
上述のような問題の解決策として、自己干渉を検出して、干渉線を求め、不要な領域を削除する技術が特許文献１に記載されている。また、非特許文献１には、立体形状を構成する面どうしの自己干渉計算手法が紹介されている。
【特許文献１】特開２００２−２４５１００公報
【非特許文献１】鳥谷浩志・千代倉弘明編著、「３次元ＣＡＤの基礎と応用」、初版、共立出版株式会社、１９９１年２月２５日、ｐ．９３−１１８
【０００３】
【発明が解決しようとする課題】
ところで、曲面同士の干渉チェック技法はさまざま存在するものの、その前提には、それぞれの曲面が自己干渉していないことが確認されている必要がある。本発明は、与えられた単一曲面の自己干渉を簡単なアルゴリズムで検出することを目的とする。
【０００４】
【課題を解決するための手段】
上記の課題を解決するために、本発明の請求項１は、単一曲面における自己干渉を判定する装置であって、曲面上に格子点を生成する格子点生成手段と、該格子点生成手段により生成した格子点情報からポリゴンと境界の線分とを抽出するポリゴン生成手段と、該ポリゴン生成手段により抽出したポリゴンおよび線分の情報を用いて干渉の有無を判定する干渉判定手段とを備えたことを特徴とする。こうすることにより、簡単なアルゴリズムで単一曲面における自己干渉を判定することができる。
また、本発明の請求項２は、請求項１記載の自己干渉判定装置において、前記格子点生成手段は、前記曲面の形状に応じた間隔で格子点を生成することを特徴とする。
こうすることにより、ポリゴンと線分の数を減少させることができ、干渉判定に要する時間を短縮できる。
また、本発明の請求項３は、請求項１または２記載の自己干渉判定装置において、前記ポリゴン生成手段は、前記格子点情報から３角形のポリゴンを生成し、生成したポリゴンおよび該ポリゴンの稜線となす線分の情報とを抽出することを特徴とする。
こうすることにより、平面が決定でき、しかも近似による誤差を減少させることができる。
また、本発明の請求項４は、請求項１、２または３記載の自己干渉判定装置において、前記干渉判定手段は、前記抽出したポリゴンと線分との交点を求め、交点がポリゴン内の平面上にあるとき干渉すると判定することを特徴とする。
こうすることにより、単一曲面の自己干渉を簡単なアルゴリズムで判定できる。
また、本発明の請求項５は、単一曲面における自己干渉を判定する方法であって、曲面上に格子点を生成する格子点生成ステップと、該格子点生成ステップにより生成した格子点情報からポリゴンと境界の線分とを抽出するポリゴン生成ステップと、該ポリゴン生成ステップにより抽出したポリゴンおよび線分の情報を用いて干渉の有無を判定する干渉判定ステップとを備えたことを特徴とする。
また、本発明の請求項６は、請求項５記載の自己干渉判定方法において、前記格子点生成ステップは、前記曲面の形状に応じた間隔で格子点を生成することを特徴とする。
また、本発明の請求項７は、請求項５または６記載の自己干渉判定方法において、前記ポリゴン生成ステップは、前記格子点情報から３角形のポリゴンを生成し、生成したポリゴンおよび該ポリゴンの稜線となす線分の情報とを抽出することを特徴とする。
また、本発明の請求項８は、請求項５、６または７記載の自己干渉判定方法において、前記干渉判定ステップは、前記抽出したポリゴンと線分との交点を求め、交点がポリゴン内の平面上にあるとき干渉すると判定することを特徴とする。
また、本発明の請求項９は、請求項５乃至８の何れか一項に記載の自己干渉判定方法をコンピュータが制御可能にプログラミングしたことを特徴とする。
また、本発明の請求項１０は、請求項９に記載の自己干渉判定プログラムを記録したコンピュータ読み取り可能な記録媒体である。
【０００５】
【発明の実施の形態】
以下、図面を参照して、本発明の実施形態を具体的に説明する。
図１は、本発明の自己干渉判定装置を実現するハードウエア構成を示す図である。本装置は各部を集中的に制御するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０を備えており、このＣＰＵ１０には、ＢＩＯＳなどを記憶した読出し専用メモリであるＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１５と、各種データを書換え可能に記憶してＣＰＵ１０の作業エリアとして機能するワークエリアＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１６とがバスで接続されており、マイクロコンピュータを構成している。さらにバスには、各種プログラムやデータが記憶されたハードディスク装置１４と、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）−ＲＯＭ１２やフレキシブルディスク１３を読み取るリムーバブル記憶装置１１と、プリンタやネットワーク等との通信を司るネットワークインターフェース１９とが接続されている。また、本装置へのデータや指示を入力するための、キーボードとマウスで構成された入力装置１８と処理結果等を表示するＣＲＴあるいはＬＣＤ等の表示装置１７も備えている。
図１に示すＣＤ−ＲＯＭ１２は、この発明の自己干渉判定プログラムを記憶する記録媒体であり、所定の処理プログラムが記憶されている。ＣＰＵ１０は、ＣＤ−ＲＯＭ１２に記憶されている処理プログラムをリムーバブル記憶装置１１で読み取り、ハードディスク装置１４にインストールする。これにより、自己干渉判定処理を行うことが可能な状態となる。
なお、記録媒体としては、ＣＤ−ＲＯＭ１２のみならず、ＤＶＤなどの各種の光ディスク、各種光磁気ディスク、フレキシブルディスクなどの各種磁気ディスク、半導体メモリ等、各種方式のメディアを用いることができる。また、インターネットなどのネットワークからプログラムをダウンロードし、ハードディスク装置１４にインストールするようにしてもよい。この場合に、送信側のサーバでプログラムを記憶している記憶装置も、この発明の自己干渉判定プログラムを記憶する記録媒体である。なお、プログラムは、所定のＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）上で動作するものであってもよいし、ＯＳなどを構成する一群のプログラムファイルの一部として含まれているものであってもよい。
【０００６】
次に本発明の自己干渉判定装置の機能構成を詳細に説明する前に、アルゴリズムの概要を説明する。まず、前提として、曲面を近似するポリゴンを利用して曲面の自己干渉を判定する場合、曲面が自己干渉するときは、曲面を近似するポリゴンも自己干渉する。つまり、曲面を近似するポリゴンと他のポリゴンの稜線が干渉する。また、曲面が自己干渉しないときは、曲面を近似するポリゴンも自己干渉しない。つまり、曲面を近似するポリゴンと他のポリゴンの稜線も干渉しない。
以上の例につき、図３から図６を参照して本発明の自己干渉判定処理の概要を説明する。図３は自己干渉を起こしている曲面の例を示す図である。この図では、帯状の曲面が右端で裏側に曲がり、再び前面に突き出している様子を示している。そして、更に前面に突き出した部分は若干下方に下がっており、下端部分は同一平面上にはないという状態の例である。そこで、曲面を近似するために格子を生成する（図４）。図４は図３の曲面を８分割して格子を生成した状態を示している。このようにして生成した格子からポリゴンとポリゴンの境界の線分を抽出する。そして、抽出したすべてのポリゴンと線分の干渉（交差）を総当たりの組み合わせで調べる。ポリゴンと線分が干渉していると判定される組み合わせが存在すれば、曲面は自己干渉すると判定する。この例の場合、図５および図６の左側（ａ）で太線と太線のマス目が交差していることが見つかる。図６右側（ｂ）は、マス目を更に三角形に分割した例であり、３角形と太線の線分が干渉している。結果として、曲面が自己干渉していると判定される。
【０００７】
それでは、上述の処理を行うための一実施形態を説明する。図２は本発明の自己干渉判定装置の機能構成を示すブロック図である。格子点生成手段２０は、曲面を格子状に分割したときの各格子点の座標値を格子点テーブル２１に保存する。例えばパラメトリック空間で定義された曲面の場合は、パラメーター空間であるＵＶ空間を格子状に分割したときの各格子点の実空間での座標値のテーブルを保存する。例えば４分割の格子とした場合、図７の（ａ）ように格子が生成される。点Ｐ１からＰ２５までの２５個の格子点ができる。格子の各点は図１０のようにテーブルに保存され、インデックスで参照することができる。インデックスは図７（ａ）のＰの後ろの番号と一致している。次に保存された格子点テーブル２１のインデックスの組み合わせで格子のマス目を表現し、マス目のテーブルを保存する（図１１）。
なお、格子への分割では、図７（ｂ）のように必ずしも等間隔に分割する必要はない。この場合、次の点を生成する際、前の点から所定の間隔で曲面のＺ座標を調べ、途中に大きく値が変化するところがなければ広い間隔で格子点を設定してもよい。こうすることにより、干渉判定の計算量を削減することができる。
ポリゴン生成手段２２は、格子点生成手段２０が生成した格子点テーブル２１から、マス目を対角線に分割して２つの３角形のポリゴンとそれらのポリゴンの境界を表す５本の線分を抽出しポリゴン・線分テーブル２３へ保存する。図８は、ポリゴンと線分の抽出を説明する図である。ポリゴンの境界を表す線分は隣接するポリゴンがあるときにはテーブル内で重複するので重複を排除する必要がある。図１２は線分テーブル、図１３はポリゴンテーブルの例を示したものである。円筒のようなルールド曲面のように４角形の平面ポリゴンで近似できる場合は、３角形の抽出は不要となり、マス目の４角形をそのまま利用できる。この場合は線分の抽出は４本となる（図９）。
【０００８】
干渉判定手段２４は、ポリゴン・線分テーブル２３、格子点テーブル２１を参照してポリゴンと線分の干渉を判定する。図１４は干渉判定手段２４の処理内容を示すフローチャートである。以下同図を用いて干渉判定の手順を説明する。
初期設定として、ＯＵＴを０（ゼロ）に設定する（ステップＳ５０１）。ゼロは干渉を示す値とする。次に、保存されているポリゴンすべてと、保存されている線分すべての組み合わせで干渉の判定を繰り返す。まず、ポリゴンＩを決める（ステップＳ５０２）。なお、図１４ではループの表記を簡略化してある。ステップＳ５０２からステップＳ５１０までは、Ｉを１からポリゴンの数まで、順にＩを１ずつ増加させながら処理を繰り返すループが構成されている。このポリゴンループの中では次の処理を行う。
ポリゴンＩを含む平面式を求める（ステップＳ５０３）。３角形ポリゴンの実空間の点Ｐ１（ｘ１，ｙ１，ｚ１）、Ｐ２（ｘ２，ｙ２，ｚ２）、Ｐ３（ｘ３，ｙ３，ｚ３）で構成される平面の方程式を求める手順は次のように行う。
平面の法線方向は、Ｎ＝（Ｐ３−Ｐ２）×（Ｐ２−Ｐ１）＝（ｎｘ，ｎｙ，ｎｚ）となり（×は外積）、その平面上の任意の点をＰ（ｘ，ｙ，ｚ）とすると、（Ｐ−Ｐ１）・Ｎ＝（Ｐ−Ｐ２）・Ｎ＝（Ｐ−Ｐ３）・Ｎ＝０の関係があるので（・は内積）、平面の方程式は、
（ｘ−ｘ１）ｎｘ＋（ｙ−ｙ１）ｎｙ＋（ｚ−ｚ１）ｎｚ＝０    （式１）
で表される。
上記のようにして、求めた平面と線分が干渉するかを、ポリゴン生成手段２２が抽出した線分との組み合わせに対して判定する。この判定処理は、ステップＳ５０４からステップＳ５０９のループで行い、ここでもＪを１から線分の数まで、１ずつ増加させて線分ＪとポリゴンＩとの組み合わせで判定を行う。なお、図では省略したが、組み合わせの中には、ポリゴンとそのポリゴンの境界を表す線分の組み合わせが含まれるので、それらの組み合わせは計算を行わないように排除する。この線分ループでは次の処理を行う。
【０００９】
まず、線分Ｊの直線式を求める（ステップＳ５０５）。２点Ｐ４（ｘ４，ｙ４，ｚ４）、Ｐ５（ｘ５，ｙ５，ｚ５）を通る直線の方程式は、その直線上の任意の点を（ｘ，ｙ，ｚ）とすると、
（ｘ−ｘ４）／（ｘ４−ｘ５）＝（ｙ−ｙ４）／（ｙ４−ｙ５）＝（ｚ−ｚ４）／（ｚ４−ｚ５）＝ｔ    （式２）
とおき、
また、ｘ、ｙ、ｚは、
ｘ＝ｘ４＋（ｘ４−ｘ５）ｔ    （式３）
ｙ＝ｙ４＋（ｙ４−ｙ５）ｔ    （式４）
ｚ＝ｚ４＋（ｚ４−ｚ５）ｔ    （式５）
で表される。ｔは媒介変数である。
次に、以上のようにして求めた線分ＪとポリゴンＩを含む平面との交点を求める（ステップＳ５０６）。平面と直線の交点は、平面と直線が平行でなければ（平行の場合は次の線分との組み合わせに移る）、式３、式４、式５を式１に代入して、媒介変数ｔの値を求め、そのｔの値を式３、式４、式５に代入して求める。求まった交点をＭとする（図１５）。図１５はポリゴンを含む平面と線分との交点Ｍの位置関係を示している。左から順に説明すると、線分範囲内に平面との交点Ｍは存在するが、ポリゴンの外部である場合であり干渉していない、次は交点Ｍがポリゴン内に存在し、かつ線分の範囲内である場合であって干渉している状態である。右の２つの場合は、交点Ｍがポリゴン内に存在はするが、線分の延長上であり、干渉していない状態を示している。交点が求まらないときは平面と直線が平行であるときである（つまり干渉しない）。
【００１０】
次に、上述した方法で求めた交点Ｍが線分内であるかをチェックする（ステップＳ５０７）。線分は直線の一部なので、平面と直線の交点Ｍが線分上の内分点であるかを調べて、内分点ならば、線分は平面と干渉すると判断する。内分点かどうかは、次の式で判定できる。
（Ｐ４とＭの距離）＋（Ｐ５とＭの距離）≦（Ｐ４とＰ５の距離）
この式が成立しないときはＭは線分内に存在しない（図１６）。図１６で左側の例ではＭがＰ４とＰ５の間にないので、上の式を満足しない。
交点Ｍが線分内でないときは（ステップＳ５０７でＮｏ）、すべての線分が終了したかをチェックする（ステップＳ５０９）。交点Ｍが線分内のときは（ステップＳ５０７でＹｅｓ）、次に交点Ｍがポリゴン内にあるかをチェックする（ステップＳ５０８）。
交点Ｍがポリゴン内にあるかをチェックするには、平面上でポリゴンの各辺と交点で構成される３つの３角形の面積を計算すれば良い。３点Ｐ６（ｘ６，ｙ６，ｚ６）、Ｐ７（ｘ７，ｙ７，ｚ７）、Ｐ８（ｘ８，ｙ８，ｚ８）、で構成される３角形の面積をＳとする。点Ｍと３点Ｐ６、Ｐ７、Ｐ８でできる３つの３角形の面積をＳ１、Ｓ２、Ｓ３とすると、それぞれはヘロンの公式を用いて計算できる。また、Ｓも同様である。図１７（ａ）は交点Ｍが３角形内にある場合、（ｂ）はＭが３角形の外にある場合を示しており、３つの３角形の面積の和が元の３角形の面積Ｓより大きいとき、交点Ｍはポリゴンの外にあると判断する。つまり、
Ｓ１＋Ｓ２＋Ｓ３≦Ｓ
が成立しないときは、交点Ｍは３角形の外にあるので３角形と線分は交点をもたない。図１８はポリゴンが４角形の場合の判定方法を示している、４角形の場合でも、３角形と同様に判定できる。
【００１１】
ステップＳ５０８で交点Ｍがポリゴン内と判断された場合は（ステップＳ５０８でＹｅｓ）、干渉が起っていることが判明したので、これ以上のチェックは必要なく、処理を終了する。この場合ステップＳ５０１でＯＵＴが０にセットされているので、このＯＵＴの値を呼び出したプログラムに渡すことになる。
ステップＳ５０８で交点Ｍがポリゴンの外と判断された場合は（ステップＳ５０８でＮｏ）、まだ干渉が発見されていないので、未チェックの線分があれば同様にチェックを行うべく、ステップＳ５０４から処理を繰り返す。
すべての線分のチェックが終了したら（ステップＳ５０９でＹｅｓ）、未チェックのポリゴンがあれば（ステップＳ５１０でＹｅｓ）、同様にチェックを行うべく、ステップＳ５０２から処理を繰り返す。そして、すべてのポリゴンのチェックが終了したら（ステップＳ５１０でＹｅｓ）、干渉は見つからなかったということで、ＯＵＴを１にセットして（ステップＳ５１１）、処理を終了する。
【００１２】
【発明の効果】
以上説明したように本発明によれば、単一曲面の自己干渉を簡単なアルゴリズムで検出することができる。
【図面の簡単な説明】
【図１】本発明の自己干渉判定装置を実現するハードウエア構成を示す図である。
【図２】本発明の自己干渉判定装置の機能構成を示すブロック図である。
【図３】自己干渉を起こしている曲面の例を示す図である。
【図４】図３の曲面を８分割して格子を生成した状態を示す図である。
【図５】ポリゴンと線分が干渉している状態を示す図である。
【図６】ポリゴンと線分が干渉している状態を示す図である。
【図７】曲面の格子分割を説明する図である。
【図８】ポリゴンと線分の抽出を説明する図である。
【図９】４角形のポリゴンと線分の抽出を説明する図である。
【図１０】格子点テーブルの例を示す図である。
【図１１】格子テーブルの例を示す図である。
【図１２】線分テーブルの例を示す図である。
【図１３】ポリゴンテーブルの例を示す図である。
【図１４】干渉判定手段の処理内容を示すフローチャートである。
【図１５】ポリゴンを含む平面と線分との交点の位置関係を示す図である。
【図１６】線分と交点の位置関係を示す図である。
【図１７】ポリゴンと交点の位置関係を示す図である。
【図１８】４角形のポリゴンと交点の位置関係を示す図である。
【符号の説明】
１０  ＣＰＵ、１１  リムーバブル記憶装置、１２  ＣＤ−ＲＯＭ、１３  フレキシブルディスク、１４  ハードディスク装置、１５  ＲＯＭ、１６  ワークエリアＲＡＭ、１７  表示装置、１８  入力装置、１９  ネットワークインターフェース、２０  格子点生成手段、２１  格子点テーブル、２２  ポリゴン生成手段、２３  ポリゴン・線分テーブル、２４  干渉判定手段
【図１】
2004303042.tif 000003
【図２】
2004303042.tif 000004
【図３】
2004303042.tif 000005
【図４】
2004303042.tif 000006
【図５】
2004303042.tif 000007
【図６】
2004303042.tif 000008
【図７】
2004303042.tif 000009
【図８】
2004303042.tif 000010
【図９】
2004303042.tif 000011
【図１０】
2004303042.tif 000012
【図１１】
2004303042.tif 000013
【図１２】
2004303042.tif 000014
【図１３】
2004303042.tif 000015
【図１４】
2004303042.tif 000016
【図１５】
2004303042.tif 000017
【図１６】
2004303042.tif 000018
【図１７】
2004303042.tif 000019
【図１８】
2004303042.tif 000020