三次元ＣＡＤデータの近似および表示方法、その方法を実行するシステム
３次元ＣＡＤデータの近似方法であって、ＣＡＤデータの立体の面をメッシュ分割し、該面の境界稜線をポリライン化し、該ポリラインの境界点における接線ベクトルを設定し、メッシュ分割の格子点のうちポリラインの内側に存在する内点を抽出し、内点同士および内点と境界点を結んで多角形ポリゴンを生成し、該多角形ポリゴン上にベジェ曲面を生成し、該ベジェ曲面がＣＡＤデータの面から所定の誤差範囲内に位置するかを判断し、誤差範囲内に乗っていない場合には、再度分割メッシュすることを特徴とする。
【発明の詳細な説明】
【技術分野】
この発明は、３次元ＣＡＤデータの近似及び表示方法、そのシステム、コンピュータソフトウエアプログラム媒体に関するものである。
【背景技術】
近年、自動車産業や航空機産業を中心として、ＣＡＤを利用した部品データの三次元化が進んでおり、これを利用してレイアウトや干渉の検討等の作業が行なわれるようになっている。
一般に、ＣＡＤデータのデータ量は、詳細になればなるほど増加し、最近ではハードウエアの進化に勝るスピードで巨大化を続けている。また、マイクロソフトウィンドウズ（登録商標）搭載の通常のＰＣには所謂２ＧＢの壁があり、巨大なＣＡＤデータについては読み込む事さえ出来ないと問題がある。
このための方法として、ＣＡＤデータを三角形ポリゴンデータに変換して軽くし、これを用いて干渉検討等を行なうことが行われている。この場合、ＣＡＤデータを幾何と位相で表現したプレサイス表現を元に、指定した誤差で表示用および計測用のポリゴンデータを生成する。このポリゴン生成を一般にポリゴン分割という。
しかし、この場合、ＣＡＤデータとポリゴンの２重でデータを持つ必要がある。また、ポリゴン分割処理は処理負荷が重く、処理時間がかかり、従って読み込み処理に時間がかかる。
このような不都合をなくすため、一度計算されたポリゴンデータをメモリ内部に保持して置き、図形の回転等のリアルタイムの表示が必要な場合には保持されたポリゴンデータを用いて再計算の負荷を省略することが行われる。しかし、高い精度で扱う、つまり元のＣＡＤデータとの誤差を小さくしようとすると、生成されたポリゴンのデータ量が増大し、視点を変えた場合等における描画処理が著しく遅くなる。このデータ量の増加は、許容誤差に対して指数的なものであり、許容誤差を小さくすればするほど、データ量の増加が著しくなる。
したがって、ＣＡＤデータを表示するに際して、使用メモリを小さくし、ある程度の精度を確保し、かつ読み込みも早くできる方法が望まれている。
発明の概要
この発明は、このような事情に鑑みて成されたものであり、従来、メモリの限界等により表示できなかった複雑なＣＡＤデータを近似しＰＣ等により表示できる、３次元ＣＡＤデータの近似方法及びその表示方法を提供することを目的とする。
この発明の主要な側面によれば、三次元ＣＡＤデータの近似方法であって、（ａ）指定した変換精度に対し、所定の粗い精度でＣＡＤデータを構成する立体の面をメッシュ分割する工程と、（ｂ）前記面の境界稜線を、前記変換精度を用いて曲線で近似し、さらに各曲線を前記の粗い精度でポリライン分割したときの端点・通過点、およびその点での接線ベクトルを設定する工程と、（ｃ）メッシュ分割にかかる各交点のうち前記境界稜線内の内点同士、若しくは前記内点と境界稜線上の端点・通過点すなわち境界点とを結んで、３または４の頂点を有する多角形ポリゴンを生成する工程と、（ｄ）前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを格納する工程と、（ｅ）前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定する工程と、（ｆ）前記三角または四角の曲面がＣＡＤデータの前記面から所定の誤差範囲内に位置するかを判断し、誤差範囲内に乗っていない場合には、当該曲面の周辺を、分割数を増やし分割幅を小さくして再度メッシュ分割し、前記（ｃ）〜（ｅ）及びこの（ｆ）工程を再度実行させる工程とを有することを特徴とする前記方法が提供される。なお、前記多角形ポリゴンは、三角形ポリゴンであることが好ましい。
このような構成によれば、前記ＣＡＤデータを三角または四角の多角ポリゴンデータに変換すると共に、前記保持する多角ポリゴンデータが所望の変換精度よりも粗い精度で生成したものでよいので、保持するべきデータ量を減らすことができる。そして、三角または四角の曲面への変換により、少ない量のポリゴンデータであってもより精密な描画表現を行なうことができ、かつ、境界稜線部分の近似については、前記ＣＡＤデータの稜線を近似した曲線とその接線データのみを利用しているから、この境界稜線で隣り合う面の間に隙間が空く事がない。以上のことにより、より少ないデータ量で、非常に精度の高い描画表現を行なうことができるのである。
さらに、この発明の１の実施形態によれば、前記方法は、（ｇ）前記多角形のうち異なる面に属し前記境界稜線を挟んで隣り合う２つの多角形ポリゴン同士を接合する工程をさらに有し、この（ｇ）工程は、前記境界稜線上の端点・通過点を２つの多角形ポリゴン間で関連付けるものである。
この発明の別の実施態様によれば、前記（ｃ）工程は、各頂点の座標と、頂点のうち内点同士を結ぶ稜線についてはそれぞれの点の法線ベクトル、頂点のうち内点と境界点を結ぶ稜線についてはそれぞれの点の法線ベクトル、頂点のうち境界点同士を結ぶ稜線については始点・終点の接線ベクトルを用い、各頂点間に曲線の制御点を生成し、三角または四角の曲面を生成する工程を含むものである。
更なる別の実施態様によれば、この三次元ＣＡＤデータの近似方法は、さらに、（ｈ） 前記（ｄ）工程で格納された前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定し、その制御点を利用して前記多角形ポリゴンを詳細多角形ポリゴンに再分割する工程と、（ｉ） 前記詳細多角形ポリゴンで構成される立体形状を表示する３次元データ表示工程とを有する。
この発明の第２の主要な側面によれば、（ｊ）前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを受取って格納する工程と、（ｋ）前記（ｊ）工程で格納された前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定し、その制御点を利用して前記多角形ポリゴンを詳細多角形ポリゴンに再分割する工程と、（ｌ）前記詳細多角形ポリゴンで構成される立体形状を表示する３次元データ表示工程とを有する方法が提供される。また、この表示方法は、（ｍ）表示方法を切り替える切替工程を有し、この切替工程は、表示形状の大きさを含む表示条件を取得し、この取得した表示条件に基づき、細かく表示する必要があると判断した場合には、前記（ｊ）〜（ｌ）の工程を実行し、組かく表示する必要がないと判断した場合には、前記取得した三角ポリゴンをそのまま表示するものであることが好ましい。
このような構成であれば、少ない量のポリゴンデータであっても、三角または四角の曲面への変換により、より精密な描画表現を行なうことができ、かつ、境界稜線部分の近似については、前記ＣＡＤデータの稜線を近似した曲線とその接線データのみを利用しているから、この境界稜線で隣り合う面の間に隙間が空く事がない。以上のことにより、より少ないデータ量で、非常に精度の高い描画表現を行なうことができる。
【図面の簡単な説明】
図１は、この発明の一実施形態に係るシステム構成を示す概略構成図である。
図２は、同じく処理手順を示すフローチャートである。
図３は、ＣＡＤデータを構成する立体の例を示す斜視図である。
図４（ａ）、（ｂ）、（ｃ）は、上記立体の面をメッシュ分割し、三角ポリゴンを生成する工程を示した工程図である。
図５（ａ）、（ｂ）は、三角ポリゴンから３次の三角ベジェ曲面の制御点を生成する工程を示した工程図である。
図５（ｃ）は、３次の三角ベジェ曲面の制御点を用いて、この曲面を複数の三角ポリゴンに再分割する工程を示した工程図である。
図６（ａ）は、別々の面に属し境界稜線を挟んで隣り合う２つの三角ポリゴンを示した模式図である。（ｂ）は、その２つの三角ポリゴンを境界稜線で接合した状態を示す模式図である。
図７は、この実施形態のデータ格納形式の例を示す模式図である。
図８は、この実施形態の形状表示工程を示すフローチャートである。
【発明を実施するための最良の形態】
以下、この発明の一実施形態を図面を参照して説明する。
（基本構成）
図１は、この実施形態に係るコンピュータ処理システム１を示す概略構成図である。
このシステム１では、ＣＰＵ２、ＲＡＭ３、入出力インタフェース４、及び通信デバイス５が接続されているバス６に、プログラム格納部７とデータ格納部８が接続されている。
まず、データ格納部８には、この図に示すように、処理の対象となるＣＡＤデータ１０と、このＣＡＤデータ１０からこの実施形態の処理により生成された三角形ポリゴンデータ１１と、同じく生成された境界稜線の端点・通過点及び接線データ１２と、変換精度等の属性情報１３が格納される。
また、前記プログラム格納部７には、ＯＳ等のメインプログラム１５の他、この発明に関係する構成のみ挙げると、ＣＡＤデータ呼出処理部１６、粗精度メッシュ分割処理部１７、境界稜線処理部１８、三角形ポリゴン生成処理部１９、三角ポリゴンデータ格納処理部２０、三角ベジェ曲面生成処理部２１、誤差修正処理部２２、三角形ポリゴン接合処理部２３、画像表示処理部２４、及び三次元データ送信部２５が格納されている。
これらプログラム格納部７に格納された各構成要素１５〜２５は、実際には、所定のプログラミング言語で記述されハードウエア等の記憶媒体に格納されたコンピュータソフトウエアプログラムであり、前記ＣＰＵ２によって適宜前記ＲＡＭ３上に呼び出され実行されることで、この発明の構成要素として機能するようになっている。以下、上記各構成要素の構成及び機能を、図２に示す実際の処理手順と共に詳しく説明する。
図２は、このシステムによる処理手順を示したフローチャートであり、図中の符号Ｓ１〜Ｓ１２は、以下の説明中のステップＳ１〜Ｓ１２にそれぞれ対応する。
（ＣＡＤデータ呼出処理部１６）
前記ＣＡＤデータ呼出処理部１６は、前記データ格納部８に格納されたＣＡＤデータ１０を、データ形式に基づいて前記ＲＡＭ３上に呼び出して展開する（ステップＳ１）。ＣＡＤデータ１０は、一般に、「幾何データ」（ＰＯＩＮＴ／ＣＵＲＶＥ／ＳＵＲＦＡＣＥ）、「位相データ」（ＢＯＤＹ／ＳＨＥＬＬ／ＦＡＣＥ／ＥＤＧＥ／ＶＥＲＴＥＸ）、「アセンブリ構造」「フィーチャ」「属性データ」等からなる。このとき、処理に必要な部分のみを順次呼び出すようにしても良い。
（粗精度メッシュ分割処理部１７）
以下の工程では、所望の精度（変換精度）よりも１桁程度精度を落とした状態（粗精度）で、ＣＡＤデータ１０を三角ポリゴンに分割する。例えば、ユーザが指定した変換精度が０．０１ｍｍである場合には、所定のアルゴリズムにより例えば粗精度を０．１ｍｍに設定する。
このため、この粗精度メッシュ分割処理部１７では、まず、前記データ格納部８から、属性条件１３としての指定変換精度を取り出す（ステップＳ２）。ユーザは、所定のインタフェースを通してこの変換精度を指定できるようになっており、指定した変換精度はこのデータ格納部８に格納されるようになっている。
そして、この粗精度メッシュ分割処理部１７は、前記ＣＡＤデータ１０の立体が持つそれぞれ面（ＦＡＣＥ）について、その境界稜線を考慮しないで、前記指定変換精度に基づいて所定の割合で「甘くした精度」、すなわち粗精度を満たすようにメッシュ状に分割する（ステップＳ３）。図３中２６は、ＣＡＤデータ１０を構成する立体の例、図４（ａ）〜図４（ｃ）は、前記立体２６の１つの面２７をメッシュ状に分割する工程を模式的に示したものである。以下、この面２７を囲む線を、境界稜線２８と称する。そして、境界稜線２８内に位置するメッシュ分割の格子点を白抜きの丸で示し、この点を、以下、「内点」２９と呼ぶ。
（境界稜線処理部１８）
前記境界稜線処理部１８は、前記面２７の境界稜線２８を前記指定変換精度（「甘くしない精度」）で、３次ベジェ曲線の列に分割する。そして、それぞれの３次ベジェ曲線を前記粗精度（「甘くした精度」）を満たすようにポリライン（折れ線）に分割する（ステップＳ４）。図４（ｂ）に黒丸で示すのが、ポリラインの端点と通過点であり、これらを以下、「境界点」３０と呼ぶ。さらに、ポリラインの前記境界点同士を結ぶ各線分に対して、その始点・終点における３次ベジェ曲線の接線ベクトルを計算し設定する（ステップＳ５）。
（三角形ポリゴン生成処理部１９）
次に、この三角形ポリゴン生成処理部１９は、上記で求めた内点及び境界点を使用し、図４（ｃ）に示すように、前記面を三角形ポリゴンに分割する（ステップＳ６）。この場合、まず、境界稜線のポリライン（折れ線）の内側に存在する内点２９を抽出する。内点２９同士はメッシュ分割と同様に規則正しく結び、内点２９と境界点３０は三角形になるように新しく線分を生成して結ぶ。
（三角ポリゴンデータ格納処理部２０）
上記で、各面２７を三角ポリゴンに分割したが、次に、この三角ポリゴンデータ格納処理部２０は、各三角形ポリゴンの頂点（内点２９と境界点３０）に対して元ＣＡＤデータの面２７の形状（曲面）から法線ベクトルを計算し設定する。また、前記頂点のうち、境界点３０については、その点につながる他の境界点を特定する情報、および２つの境界点を結ぶ線分の始点・終点の接線ベクトルを前記三角ポリゴンデータとして前記データ格納部８に格納する（ステップＳ７）。
図５（ａ）は、三角ポリゴンの例を示すものである。図５中、３２は、内点Ｐ０と２個の境界点３０（Ｐ１、Ｐ２）を頂点とする三角形ポリゴンである。内点Ｐ０には法線ベクトルＮ０、境界点Ｐ１には法線ベクトルＮ１、境界点Ｐ２には法線ベクトルＮ１が割り付けられている。また、Ｐ１を始点としＰ２を終点とする境界線分については、前記始点Ｐ１に法線ベクトルＴ１が割り付けられ、Ｐ２を始点としＰ１を終点とする境界線分については、前記始点Ｐ２に法線ベクトルＴ２が割り付けられている。
（三角ベジェ曲面生成処理部２１）
次に、この三角ベジェ曲面生成処理部２１は、上記で生成した三角ポリゴンの情報から、法線ベクトル（Ｎ０〜Ｎ２）及び接線ベクトル（Ｔ１、Ｔ２）の情報を用いて３次の三角ベジェ曲面を生成する（ステップＳ８）。この三角ベジェ曲面の生成方法については、ＡＴＩ Ｔｅｃｈｎｏｌｏｐｇｙ Ｗｈｉｔｅ Ｐａｐｅｒ：ｈｔｔｐ：／／ｗｗｗ．ａｔｉ．ｃｏｍ／ｐｒｏｄｕｃｔｓ／ｐｄｆ／ｔｒｕｆｏｒｍ．ｐｄｆ（２００１年）に詳しく説明されており、この文献はこの参照により、全体的にこの明細書に組み込まれたものとする。
上記文献に開示された三角ベジェ曲面のための１０個の制御点を生成するのに、三角ポリゴンの各頂点における法線ベクトルを使用している。これに対して、この実施形態では、三角ベジェ曲面の制御点を生成するのに、内点同士を結ぶ稜線についてはそれぞれの法線ベクトル、内点と境界点を結ぶ稜線についてはそれぞれの法線ベクトル、境界点同士を結ぶ稜線については始点・終点の接線ベクトルを用いる。境界点同士を結ぶ接線に関する制御点を生成するには、例えば以下のようにして行なう。
すなわち、境界線の始点と終点、始点における接線ベクトル、終点における接線ベクトルが定まると、当該境界線に関する３次ベジェ曲線が一意に定まる。この場合、始点に近い側の制御点は、始点から伸ばした接線ベクトルの１／３の地点と一致する。終点に近い側の制御点は、終点から伸ばした接線ベクトルの１／３の地点と一致する。
これにより、まず、各稜線上（各頂点間）に２つの制御点を生成され、図５（ｂ）に示すように、３次の三角ベジェ曲面が持つ１０個の制御点のうち、３つの頂点Ｐ０〜Ｐ２と一致する３個の制御点（ＰＰ１〜ＰＰ３）と、それらの頂点Ｐ０〜Ｐ２間を結ぶ稜線上の２個ずつ合計６個の制御点（ＰＰ４〜ＰＰ９）の、合計９個が決まる。残りの１つ（ＰＰ１０）は、他の９個の制御点を平均して決定する。
（誤差修正処理部２２）
次に、前記誤差修正部２２が、上記で生成した三角ベジェ曲面について，元ＣＡＤデータの面の形状（曲面）に、変換精度の範囲内で乗っているかどうかを調べる（ステップＳ９）。
まず、三角ベジェ曲面の３つの頂点ＰＰ１〜ＰＰ３については必ず曲面に乗っている。そこで、三角ベジェ曲面の３本の稜線の中点，および三角曲面の中心について、変換精度で面上に乗っているかどうかを調べる。ただし、境界点同士を結ぶ稜線は，元ＣＡＤデータの稜線の形状（曲線）を指定変換精度（「甘くしない精度」）に入るように３次ベジェ曲線で近似しているので、この曲線は中点も含めて精度内で面上に乗っているはずである．
調べた結果，１箇所でも指定変換精度で乗っていない場合は，粗精度（「甘くした精度」）をより厳しく、つまり小さくして、縦横のメッシュ分割幅を細かくして分割やりなおす（ステップＳ１０）。
なお、このとき、前記ステップＳ５の境界稜線の分割はやりなおさない。つまり、粗精度を小さくしたのち、指定変換精度にのるまで上記ステップＳ６〜ステップＳ１０を繰り返す。
（三角ポリゴン接合処理部２３）
上記ステップＳ１〜ステップＳ９の工程を終え、すべての面について所定の指定変換精度を満たすと判断されたならば、次に、この三角ポリゴン接合処理部２３が、各面について生成した三角ポリゴンを境界稜線で接合する。
ＣＡＤデータの立体は，通常１本の稜線の左右両側に面が１枚ずつ存在している。上記ステップＳ４、Ｓ５の境界稜線処理工程で説明したポリライン分割は，元ＣＡＤデータの稜線の形状（曲線）のみを参照し、面の形状（曲面）は参照していない。したがって、１本の稜線の両側にある２枚の面は、隙間なく三角形ポリゴンでつなぐことができる。
図６（ａ）は、この境界稜線を挟んで隣り合う２つの三角形ポリゴン３２，３３を示したものである。１つのポリゴン３２は、前述した面２７上の三角ポリゴン（Ｐ０、Ｐ１、Ｐ２）であり、３３は、前記面２７と境界稜線を共有する別の面に属する三角形ポリゴンである。この別の三角形ポリゴン３３は、内点Ｐ５、及び２個の境界点Ｐ３、Ｐ４から構成され、前記面２７上の三角形ポリゴン３２と同様に、各点に法線ベクトルＮ５、Ｎ３、及びＮ４が割当てられている。
ここで、境界点Ｐ３及びＰ４は、それぞれＰ１とＰ２と同一の点であり、かつ、前記ステップＳ４及びＳ５の処理により、前記接線ベクトルＴ１、Ｔ２と同一の接線ベクトルＴ３、Ｔ４が与えられている。したがって、この三角形ポリゴン接合処理部２３は、図６に示すように、Ｐ３、Ｐ４をＰ１及びＰ２と置き換えることで、２つの三角形ポリゴン３２，３３の境界稜線同士を接合する。
このことにより、前記データ格納部に格納される三角形ポリゴンデータのデータ格納形式は、例えば、図７に示すようなものになる。
頂点・法線情報としては、図７（ａ）に示すように、三角形ポリゴンを構成する３頂点を一組として、各頂点毎にインデックス番号３５、頂点の位置情報３６及び法線ベクトル３７が格納される。境界稜線情報としては、図７（ｂ）に示すように、始点のインデックス情報３８、終点のインデックス情報３９及び始点における接線ベクトルの情報４０が一組として格納される。
以上より、ＣＡＤデータは三角ポリゴンデータに変換され、そして、
内点：１つの法線ベクトル
境界点：その点の周りにあった元ＣＡＤデータの面（曲面）の数だけの法線ベクトル
隣り合う境界点を結ぶ境界線：始点・終点の接線ベクトル
が設定された状態になる。また、この実施形態では、上記データの格納は、前記三角形ポリゴンデータ格納処理部２０を通して行われる。
このように構成されたシステムにより生成された三角ポリゴンデータは、基本的に指定の変換精度よりも甘い精度（粗精度）で変換されたポリゴンデータであるので、データ量を非常に小さくすることができる。また、表示を行う場合には、３次の三角ベジェ曲面への変換を行うことで、高精度な表示を行うことが可能になる。
次に、この表示を行う表示処理部２４について、図８に示したフローチャートを参照して説明する。
（表示処理部２４）
この表示処理部２４は、形状を粗く見るときと、細かく見るときとで、表示方法を切り換えるための表示切替部４１と、表示を細かく表示する際に作動する三角ベジェ曲面生成処理部４２とを有する。
このため、この表示処理部２４は、図８のステップＳ１３に示すように、表示の際のシステム環境、すなわち表示条件をシステムから取得する。この表示条件には、形状の大きさ、画面の解像度（ウインドウの縦横のピクセル数）、表示の拡大率等、表示の細かさに関する項目が含まれるが、これに限定されるものではない。
ついで、この表示切替部４１は、前記表示条件に応じて、形状を粗く表示するか細かく表示するかの判断を行なう（ステップＳ１４）。この判断は、例えば、上記表示条件の各項目に設定した閾値を参照して行なわれる。そして、形状を粗く表示する場合には、前記ステップＳ６、Ｓ７のポリゴン分割で生成した三角ポリゴンとその法線とをそのまま使用して表示を行う（ステップＳ１５）。すなわち、前記ステップＳ１４における判断（閾値の設定等）は、前記粗精度で分割した三角ポリゴンをそのまま表示した場合でも違和感がないかどうかを基準に行なわれるべきである。例えば、画面の解像度や形状の拡大率を参照した場合に、表示画面の大きさに比較して表示するべき面の占める面積が小さい場合には、そのまま粗精度の三角ポリゴンを表示しても形状がカクカクには見えない。したがって、そのようなアルゴリズムにより上記判断を行なうようにしてもよい。
一方、三角ポリゴンデータをそのまま表示したのでは形状がカクカクしてしまう場合、すなわち形状を細かく表示するべき場合には三角ベジェ曲面生成処理部４２を起動する（ステップＳ１６、Ｓ１７）。
この場合、この三角ベジェ曲面生成部４２は、上記したのと同様の手法で、三角ポリゴンの法線及び接線ベクトルの情報から三角ベジェ曲面を生成する（ステップＳ１６、図５（ｂ）参照）。そして、この三角ベジェ曲面の１０個の制御点を用い、前記三角ポリゴンの再分割を行なう。この再分割における分割レベルは、表示されるコンピュータ画面上で、形状がカクカクにならずに、滑らかに面が表示されるという観点で決定される。つまり、前記分割レベルは、形状の大きさ、画面の解像度（ウインドウの縦横のピクセル数）、表示の拡大率等の表示条件を、所定の閾値と比較することにより、表示のつど決めることになる。図５（ｃ）は、前記三角ポリゴンを、前記１０個の制御点を参照して、１６個の三角形ポリゴンに再分割した例（レベル３：各稜線が４分割される状態）を示したものである。また、この三角ベジェ曲面生成部４２は、再分割後の各三角ポリゴンの各頂点の法線ベクトルについては、元の三角ポリゴンの３頂点Ｐ０〜Ｐ２に設定されていた法線ベクトルを１次補間して計算する。そして、それら再分割三角ポリゴンを使用して形状の表示を行う（ステップＳ１７）。
このような構成によれば、形状を細かく表示する場合であっても、三角ベジェ曲面を生成して表示を行うので、前述したように、精度の高い表示を行える。特に、境界稜線における、隣り合う三角ポリゴン同士の接合が予め考慮された処理が行われているので、表示精度を上げた場合であっても境界稜線部分に隙間が生じることがない。
（データ送信部２５）
このデータ送信部２５は、前記ステップＳ１〜Ｓ１２で生成したデータを、例えば、イントラネットやインターネット等の送信媒体を介して別のコンピュータや記憶媒体に送信する機能を有するものである。
この場合、このデータの送信を受けたコンピュータは、前記画像表示処理部２４に対応するデータ再生プログラムのみを有し、データのレンダリング及び表示及び操作を行うようになっていても良い。
なお、この発明は上記一実施形態に限定されるものではなく、その要旨を変更しない範囲で種々変形可能であることはいうまでもない。
例えば、上記一実施形態では、三角形ポリゴンを用いてＣＡＤデータを構成する三次元形状の近似を行ったが、四角形ポリゴンを用いるようにしても良い。この場合、前記３次の三角ベジェ曲面生成処理は、四角ベジェ曲面を用いるようにすればよい。
さらに、上記実施形態においてベジェ曲面の表現次数は３次であったが、これに限定されるものではない。また、従って、制御点は１０個に限定されるものではない。さらに、三角又は四角のポリゴンの近似においては、ベジェ曲線・曲面による表現式を使わなくてもよい。たとえば、Ｂ−スプライン曲面やＮＵＲＢＳ曲面などの曲面式を使うことも可能である。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【技術分野】
この発明は、３次元ＣＡＤデータの近似及び表示方法、そのシステム、コンピュータソフトウエアプログラム媒体に関するものである。
【背景技術】
近年、自動車産業や航空機産業を中心として、ＣＡＤを利用した部品データの三次元化が進んでおり、これを利用してレイアウトや干渉の検討等の作業が行なわれるようになっている。
一般に、ＣＡＤデータのデータ量は、詳細になればなるほど増加し、最近ではハードウエアの進化に勝るスピードで巨大化を続けている。また、マイクロソフトウィンドウズ（登録商標）搭載の通常のＰＣには所謂２ＧＢの壁があり、巨大なＣＡＤデータについては読み込む事さえ出来ないと問題がある。
このための方法として、ＣＡＤデータを三角形ポリゴンデータに変換して軽くし、これを用いて干渉検討等を行なうことが行われている。この場合、ＣＡＤデータを幾何と位相で表現したプレサイス表現を元に、指定した誤差で表示用および計測用のポリゴンデータを生成する。このポリゴン生成を一般にポリゴン分割という。
しかし、この場合、ＣＡＤデータとポリゴンの２重でデータを持つ必要がある。また、ポリゴン分割処理は処理負荷が重く、処理時間がかかり、従って読み込み処理に時間がかかる。
このような不都合をなくすため、一度計算されたポリゴンデータをメモリ内部に保持して置き、図形の回転等のリアルタイムの表示が必要な場合には保持されたポリゴンデータを用いて再計算の負荷を省略することが行われる。しかし、高い精度で扱う、つまり元のＣＡＤデータとの誤差を小さくしようとすると、生成されたポリゴンのデータ量が増大し、視点を変えた場合等における描画処理が著しく遅くなる。このデータ量の増加は、許容誤差に対して指数的なものであり、許容誤差を小さくすればするほど、データ量の増加が著しくなる。
したがって、ＣＡＤデータを表示するに際して、使用メモリを小さくし、ある程度の精度を確保し、かつ読み込みも早くできる方法が望まれている。
発明の概要
この発明は、このような事情に鑑みて成されたものであり、従来、メモリの限界等により表示できなかった複雑なＣＡＤデータを近似しＰＣ等により表示できる、３次元ＣＡＤデータの近似方法及びその表示方法を提供することを目的とする。
この発明の主要な側面によれば、三次元ＣＡＤデータの近似方法であって、（ａ）指定した変換精度に対し、所定の粗い精度でＣＡＤデータを構成する立体の面をメッシュ分割する工程と、（ｂ）前記面の境界稜線を、前記変換精度を用いて曲線で近似し、さらに各曲線を前記の粗い精度でポリライン分割したときの端点・通過点、およびその点での接線ベクトルを設定する工程と、（ｃ）メッシュ分割にかかる各交点のうち前記境界稜線内の内点同士、若しくは前記内点と境界稜線上の端点・通過点すなわち境界点とを結んで、３または４の頂点を有する多角形ポリゴンを生成する工程と、（ｄ）前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを格納する工程と、（ｅ）前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定する工程と、（ｆ）前記三角または四角の曲面がＣＡＤデータの前記面から所定の誤差範囲内に位置するかを判断し、誤差範囲内に乗っていない場合には、当該曲面の周辺を、分割数を増やし分割幅を小さくして再度メッシュ分割し、前記（ｃ）〜（ｅ）及びこの（ｆ）工程を再度実行させる工程とを有することを特徴とする前記方法が提供される。なお、前記多角形ポリゴンは、三角形ポリゴンであることが好ましい。
このような構成によれば、前記ＣＡＤデータを三角または四角の多角ポリゴンデータに変換すると共に、前記保持する多角ポリゴンデータが所望の変換精度よりも粗い精度で生成したものでよいので、保持するべきデータ量を減らすことができる。そして、三角または四角の曲面への変換により、少ない量のポリゴンデータであってもより精密な描画表現を行なうことができ、かつ、境界稜線部分の近似については、前記ＣＡＤデータの稜線を近似した曲線とその接線データのみを利用しているから、この境界稜線で隣り合う面の間に隙間が空く事がない。以上のことにより、より少ないデータ量で、非常に精度の高い描画表現を行なうことができるのである。
さらに、この発明の１の実施形態によれば、前記方法は、（ｇ）前記多角形のうち異なる面に属し前記境界稜線を挟んで隣り合う２つの多角形ポリゴン同士を接合する工程をさらに有し、この（ｇ）工程は、前記境界稜線上の端点・通過点を２つの多角形ポリゴン間で関連付けるものである。
この発明の別の実施態様によれば、前記（ｃ）工程は、各頂点の座標と、頂点のうち内点同士を結ぶ稜線についてはそれぞれの点の法線ベクトル、頂点のうち内点と境界点を結ぶ稜線についてはそれぞれの点の法線ベクトル、頂点のうち境界点同士を結ぶ稜線については始点・終点の接線ベクトルを用い、各頂点間に曲線の制御点を生成し、三角または四角の曲面を生成する工程を含むものである。
更なる別の実施態様によれば、この三次元ＣＡＤデータの近似方法は、さらに、（ｈ） 前記（ｄ）工程で格納された前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定し、その制御点を利用して前記多角形ポリゴンを詳細多角形ポリゴンに再分割する工程と、（ｉ） 前記詳細多角形ポリゴンで構成される立体形状を表示する３次元データ表示工程とを有する。
この発明の第２の主要な側面によれば、（ｊ）前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを受取って格納する工程と、（ｋ）前記（ｊ）工程で格納された前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定し、その制御点を利用して前記多角形ポリゴンを詳細多角形ポリゴンに再分割する工程と、（ｌ）前記詳細多角形ポリゴンで構成される立体形状を表示する３次元データ表示工程とを有する方法が提供される。また、この表示方法は、（ｍ）表示方法を切り替える切替工程を有し、この切替工程は、表示形状の大きさを含む表示条件を取得し、この取得した表示条件に基づき、細かく表示する必要があると判断した場合には、前記（ｊ）〜（ｌ）の工程を実行し、組かく表示する必要がないと判断した場合には、前記取得した三角ポリゴンをそのまま表示するものであることが好ましい。
このような構成であれば、少ない量のポリゴンデータであっても、三角または四角の曲面への変換により、より精密な描画表現を行なうことができ、かつ、境界稜線部分の近似については、前記ＣＡＤデータの稜線を近似した曲線とその接線データのみを利用しているから、この境界稜線で隣り合う面の間に隙間が空く事がない。以上のことにより、より少ないデータ量で、非常に精度の高い描画表現を行なうことができる。
【図面の簡単な説明】
図１は、この発明の一実施形態に係るシステム構成を示す概略構成図である。
図２は、同じく処理手順を示すフローチャートである。
図３は、ＣＡＤデータを構成する立体の例を示す斜視図である。
図４（ａ）、（ｂ）、（ｃ）は、上記立体の面をメッシュ分割し、三角ポリゴンを生成する工程を示した工程図である。
図５（ａ）、（ｂ）は、三角ポリゴンから３次の三角ベジェ曲面の制御点を生成する工程を示した工程図である。
図５（ｃ）は、３次の三角ベジェ曲面の制御点を用いて、この曲面を複数の三角ポリゴンに再分割する工程を示した工程図である。
図６（ａ）は、別々の面に属し境界稜線を挟んで隣り合う２つの三角ポリゴンを示した模式図である。（ｂ）は、その２つの三角ポリゴンを境界稜線で接合した状態を示す模式図である。
図７は、この実施形態のデータ格納形式の例を示す模式図である。
図８は、この実施形態の形状表示工程を示すフローチャートである。
【発明を実施するための最良の形態】
以下、この発明の一実施形態を図面を参照して説明する。
（基本構成）
図１は、この実施形態に係るコンピュータ処理システム１を示す概略構成図である。
このシステム１では、ＣＰＵ２、ＲＡＭ３、入出力インタフェース４、及び通信デバイス５が接続されているバス６に、プログラム格納部７とデータ格納部８が接続されている。
まず、データ格納部８には、この図に示すように、処理の対象となるＣＡＤデータ１０と、このＣＡＤデータ１０からこの実施形態の処理により生成された三角形ポリゴンデータ１１と、同じく生成された境界稜線の端点・通過点及び接線データ１２と、変換精度等の属性情報１３が格納される。
また、前記プログラム格納部７には、ＯＳ等のメインプログラム１５の他、この発明に関係する構成のみ挙げると、ＣＡＤデータ呼出処理部１６、粗精度メッシュ分割処理部１７、境界稜線処理部１８、三角形ポリゴン生成処理部１９、三角ポリゴンデータ格納処理部２０、三角ベジェ曲面生成処理部２１、誤差修正処理部２２、三角形ポリゴン接合処理部２３、画像表示処理部２４、及び三次元データ送信部２５が格納されている。
これらプログラム格納部７に格納された各構成要素１５〜２５は、実際には、所定のプログラミング言語で記述されハードウエア等の記憶媒体に格納されたコンピュータソフトウエアプログラムであり、前記ＣＰＵ２によって適宜前記ＲＡＭ３上に呼び出され実行されることで、この発明の構成要素として機能するようになっている。以下、上記各構成要素の構成及び機能を、図２に示す実際の処理手順と共に詳しく説明する。
図２は、このシステムによる処理手順を示したフローチャートであり、図中の符号Ｓ１〜Ｓ１２は、以下の説明中のステップＳ１〜Ｓ１２にそれぞれ対応する。
（ＣＡＤデータ呼出処理部１６）
前記ＣＡＤデータ呼出処理部１６は、前記データ格納部８に格納されたＣＡＤデータ１０を、データ形式に基づいて前記ＲＡＭ３上に呼び出して展開する（ステップＳ１）。ＣＡＤデータ１０は、一般に、「幾何データ」（ＰＯＩＮＴ／ＣＵＲＶＥ／ＳＵＲＦＡＣＥ）、「位相データ」（ＢＯＤＹ／ＳＨＥＬＬ／ＦＡＣＥ／ＥＤＧＥ／ＶＥＲＴＥＸ）、「アセンブリ構造」「フィーチャ」「属性データ」等からなる。このとき、処理に必要な部分のみを順次呼び出すようにしても良い。
（粗精度メッシュ分割処理部１７）
以下の工程では、所望の精度（変換精度）よりも１桁程度精度を落とした状態（粗精度）で、ＣＡＤデータ１０を三角ポリゴンに分割する。例えば、ユーザが指定した変換精度が０．０１ｍｍである場合には、所定のアルゴリズムにより例えば粗精度を０．１ｍｍに設定する。
このため、この粗精度メッシュ分割処理部１７では、まず、前記データ格納部８から、属性条件１３としての指定変換精度を取り出す（ステップＳ２）。ユーザは、所定のインタフェースを通してこの変換精度を指定できるようになっており、指定した変換精度はこのデータ格納部８に格納されるようになっている。
そして、この粗精度メッシュ分割処理部１７は、前記ＣＡＤデータ１０の立体が持つそれぞれ面（ＦＡＣＥ）について、その境界稜線を考慮しないで、前記指定変換精度に基づいて所定の割合で「甘くした精度」、すなわち粗精度を満たすようにメッシュ状に分割する（ステップＳ３）。図３中２６は、ＣＡＤデータ１０を構成する立体の例、図４（ａ）〜図４（ｃ）は、前記立体２６の１つの面２７をメッシュ状に分割する工程を模式的に示したものである。以下、この面２７を囲む線を、境界稜線２８と称する。そして、境界稜線２８内に位置するメッシュ分割の格子点を白抜きの丸で示し、この点を、以下、「内点」２９と呼ぶ。
（境界稜線処理部１８）
前記境界稜線処理部１８は、前記面２７の境界稜線２８を前記指定変換精度（「甘くしない精度」）で、３次ベジェ曲線の列に分割する。そして、それぞれの３次ベジェ曲線を前記粗精度（「甘くした精度」）を満たすようにポリライン（折れ線）に分割する（ステップＳ４）。図４（ｂ）に黒丸で示すのが、ポリラインの端点と通過点であり、これらを以下、「境界点」３０と呼ぶ。さらに、ポリラインの前記境界点同士を結ぶ各線分に対して、その始点・終点における３次ベジェ曲線の接線ベクトルを計算し設定する（ステップＳ５）。
（三角形ポリゴン生成処理部１９）
次に、この三角形ポリゴン生成処理部１９は、上記で求めた内点及び境界点を使用し、図４（ｃ）に示すように、前記面を三角形ポリゴンに分割する（ステップＳ６）。この場合、まず、境界稜線のポリライン（折れ線）の内側に存在する内点２９を抽出する。内点２９同士はメッシュ分割と同様に規則正しく結び、内点２９と境界点３０は三角形になるように新しく線分を生成して結ぶ。
（三角ポリゴンデータ格納処理部２０）
上記で、各面２７を三角ポリゴンに分割したが、次に、この三角ポリゴンデータ格納処理部２０は、各三角形ポリゴンの頂点（内点２９と境界点３０）に対して元ＣＡＤデータの面２７の形状（曲面）から法線ベクトルを計算し設定する。また、前記頂点のうち、境界点３０については、その点につながる他の境界点を特定する情報、および２つの境界点を結ぶ線分の始点・終点の接線ベクトルを前記三角ポリゴンデータとして前記データ格納部８に格納する（ステップＳ７）。
図５（ａ）は、三角ポリゴンの例を示すものである。図５中、３２は、内点Ｐ０と２個の境界点３０（Ｐ１、Ｐ２）を頂点とする三角形ポリゴンである。内点Ｐ０には法線ベクトルＮ０、境界点Ｐ１には法線ベクトルＮ１、境界点Ｐ２には法線ベクトルＮ１が割り付けられている。また、Ｐ１を始点としＰ２を終点とする境界線分については、前記始点Ｐ１に法線ベクトルＴ１が割り付けられ、Ｐ２を始点としＰ１を終点とする境界線分については、前記始点Ｐ２に法線ベクトルＴ２が割り付けられている。
（三角ベジェ曲面生成処理部２１）
次に、この三角ベジェ曲面生成処理部２１は、上記で生成した三角ポリゴンの情報から、法線ベクトル（Ｎ０〜Ｎ２）及び接線ベクトル（Ｔ１、Ｔ２）の情報を用いて３次の三角ベジェ曲面を生成する（ステップＳ８）。この三角ベジェ曲面の生成方法については、ＡＴＩ Ｔｅｃｈｎｏｌｏｐｇｙ Ｗｈｉｔｅ Ｐａｐｅｒ：ｈｔｔｐ：／／ｗｗｗ．ａｔｉ．ｃｏｍ／ｐｒｏｄｕｃｔｓ／ｐｄｆ／ｔｒｕｆｏｒｍ．ｐｄｆ（２００１年）に詳しく説明されており、この文献はこの参照により、全体的にこの明細書に組み込まれたものとする。
上記文献に開示された三角ベジェ曲面のための１０個の制御点を生成するのに、三角ポリゴンの各頂点における法線ベクトルを使用している。これに対して、この実施形態では、三角ベジェ曲面の制御点を生成するのに、内点同士を結ぶ稜線についてはそれぞれの法線ベクトル、内点と境界点を結ぶ稜線についてはそれぞれの法線ベクトル、境界点同士を結ぶ稜線については始点・終点の接線ベクトルを用いる。境界点同士を結ぶ接線に関する制御点を生成するには、例えば以下のようにして行なう。
すなわち、境界線の始点と終点、始点における接線ベクトル、終点における接線ベクトルが定まると、当該境界線に関する３次ベジェ曲線が一意に定まる。この場合、始点に近い側の制御点は、始点から伸ばした接線ベクトルの１／３の地点と一致する。終点に近い側の制御点は、終点から伸ばした接線ベクトルの１／３の地点と一致する。
これにより、まず、各稜線上（各頂点間）に２つの制御点を生成され、図５（ｂ）に示すように、３次の三角ベジェ曲面が持つ１０個の制御点のうち、３つの頂点Ｐ０〜Ｐ２と一致する３個の制御点（ＰＰ１〜ＰＰ３）と、それらの頂点Ｐ０〜Ｐ２間を結ぶ稜線上の２個ずつ合計６個の制御点（ＰＰ４〜ＰＰ９）の、合計９個が決まる。残りの１つ（ＰＰ１０）は、他の９個の制御点を平均して決定する。
（誤差修正処理部２２）
次に、前記誤差修正部２２が、上記で生成した三角ベジェ曲面について，元ＣＡＤデータの面の形状（曲面）に、変換精度の範囲内で乗っているかどうかを調べる（ステップＳ９）。
まず、三角ベジェ曲面の３つの頂点ＰＰ１〜ＰＰ３については必ず曲面に乗っている。そこで、三角ベジェ曲面の３本の稜線の中点，および三角曲面の中心について、変換精度で面上に乗っているかどうかを調べる。ただし、境界点同士を結ぶ稜線は，元ＣＡＤデータの稜線の形状（曲線）を指定変換精度（「甘くしない精度」）に入るように３次ベジェ曲線で近似しているので、この曲線は中点も含めて精度内で面上に乗っているはずである．
調べた結果，１箇所でも指定変換精度で乗っていない場合は，粗精度（「甘くした精度」）をより厳しく、つまり小さくして、縦横のメッシュ分割幅を細かくして分割やりなおす（ステップＳ１０）。
なお、このとき、前記ステップＳ５の境界稜線の分割はやりなおさない。つまり、粗精度を小さくしたのち、指定変換精度にのるまで上記ステップＳ６〜ステップＳ１０を繰り返す。
（三角ポリゴン接合処理部２３）
上記ステップＳ１〜ステップＳ９の工程を終え、すべての面について所定の指定変換精度を満たすと判断されたならば、次に、この三角ポリゴン接合処理部２３が、各面について生成した三角ポリゴンを境界稜線で接合する。
ＣＡＤデータの立体は，通常１本の稜線の左右両側に面が１枚ずつ存在している。上記ステップＳ４、Ｓ５の境界稜線処理工程で説明したポリライン分割は，元ＣＡＤデータの稜線の形状（曲線）のみを参照し、面の形状（曲面）は参照していない。したがって、１本の稜線の両側にある２枚の面は、隙間なく三角形ポリゴンでつなぐことができる。
図６（ａ）は、この境界稜線を挟んで隣り合う２つの三角形ポリゴン３２，３３を示したものである。１つのポリゴン３２は、前述した面２７上の三角ポリゴン（Ｐ０、Ｐ１、Ｐ２）であり、３３は、前記面２７と境界稜線を共有する別の面に属する三角形ポリゴンである。この別の三角形ポリゴン３３は、内点Ｐ５、及び２個の境界点Ｐ３、Ｐ４から構成され、前記面２７上の三角形ポリゴン３２と同様に、各点に法線ベクトルＮ５、Ｎ３、及びＮ４が割当てられている。
ここで、境界点Ｐ３及びＰ４は、それぞれＰ１とＰ２と同一の点であり、かつ、前記ステップＳ４及びＳ５の処理により、前記接線ベクトルＴ１、Ｔ２と同一の接線ベクトルＴ３、Ｔ４が与えられている。したがって、この三角形ポリゴン接合処理部２３は、図６に示すように、Ｐ３、Ｐ４をＰ１及びＰ２と置き換えることで、２つの三角形ポリゴン３２，３３の境界稜線同士を接合する。
このことにより、前記データ格納部に格納される三角形ポリゴンデータのデータ格納形式は、例えば、図７に示すようなものになる。
頂点・法線情報としては、図７（ａ）に示すように、三角形ポリゴンを構成する３頂点を一組として、各頂点毎にインデックス番号３５、頂点の位置情報３６及び法線ベクトル３７が格納される。境界稜線情報としては、図７（ｂ）に示すように、始点のインデックス情報３８、終点のインデックス情報３９及び始点における接線ベクトルの情報４０が一組として格納される。
以上より、ＣＡＤデータは三角ポリゴンデータに変換され、そして、
内点：１つの法線ベクトル
境界点：その点の周りにあった元ＣＡＤデータの面（曲面）の数だけの法線ベクトル
隣り合う境界点を結ぶ境界線：始点・終点の接線ベクトル
が設定された状態になる。また、この実施形態では、上記データの格納は、前記三角形ポリゴンデータ格納処理部２０を通して行われる。
このように構成されたシステムにより生成された三角ポリゴンデータは、基本的に指定の変換精度よりも甘い精度（粗精度）で変換されたポリゴンデータであるので、データ量を非常に小さくすることができる。また、表示を行う場合には、３次の三角ベジェ曲面への変換を行うことで、高精度な表示を行うことが可能になる。
次に、この表示を行う表示処理部２４について、図８に示したフローチャートを参照して説明する。
（表示処理部２４）
この表示処理部２４は、形状を粗く見るときと、細かく見るときとで、表示方法を切り換えるための表示切替部４１と、表示を細かく表示する際に作動する三角ベジェ曲面生成処理部４２とを有する。
このため、この表示処理部２４は、図８のステップＳ１３に示すように、表示の際のシステム環境、すなわち表示条件をシステムから取得する。この表示条件には、形状の大きさ、画面の解像度（ウインドウの縦横のピクセル数）、表示の拡大率等、表示の細かさに関する項目が含まれるが、これに限定されるものではない。
ついで、この表示切替部４１は、前記表示条件に応じて、形状を粗く表示するか細かく表示するかの判断を行なう（ステップＳ１４）。この判断は、例えば、上記表示条件の各項目に設定した閾値を参照して行なわれる。そして、形状を粗く表示する場合には、前記ステップＳ６、Ｓ７のポリゴン分割で生成した三角ポリゴンとその法線とをそのまま使用して表示を行う（ステップＳ１５）。すなわち、前記ステップＳ１４における判断（閾値の設定等）は、前記粗精度で分割した三角ポリゴンをそのまま表示した場合でも違和感がないかどうかを基準に行なわれるべきである。例えば、画面の解像度や形状の拡大率を参照した場合に、表示画面の大きさに比較して表示するべき面の占める面積が小さい場合には、そのまま粗精度の三角ポリゴンを表示しても形状がカクカクには見えない。したがって、そのようなアルゴリズムにより上記判断を行なうようにしてもよい。
一方、三角ポリゴンデータをそのまま表示したのでは形状がカクカクしてしまう場合、すなわち形状を細かく表示するべき場合には三角ベジェ曲面生成処理部４２を起動する（ステップＳ１６、Ｓ１７）。
この場合、この三角ベジェ曲面生成部４２は、上記したのと同様の手法で、三角ポリゴンの法線及び接線ベクトルの情報から三角ベジェ曲面を生成する（ステップＳ１６、図５（ｂ）参照）。そして、この三角ベジェ曲面の１０個の制御点を用い、前記三角ポリゴンの再分割を行なう。この再分割における分割レベルは、表示されるコンピュータ画面上で、形状がカクカクにならずに、滑らかに面が表示されるという観点で決定される。つまり、前記分割レベルは、形状の大きさ、画面の解像度（ウインドウの縦横のピクセル数）、表示の拡大率等の表示条件を、所定の閾値と比較することにより、表示のつど決めることになる。図５（ｃ）は、前記三角ポリゴンを、前記１０個の制御点を参照して、１６個の三角形ポリゴンに再分割した例（レベル３：各稜線が４分割される状態）を示したものである。また、この三角ベジェ曲面生成部４２は、再分割後の各三角ポリゴンの各頂点の法線ベクトルについては、元の三角ポリゴンの３頂点Ｐ０〜Ｐ２に設定されていた法線ベクトルを１次補間して計算する。そして、それら再分割三角ポリゴンを使用して形状の表示を行う（ステップＳ１７）。
このような構成によれば、形状を細かく表示する場合であっても、三角ベジェ曲面を生成して表示を行うので、前述したように、精度の高い表示を行える。特に、境界稜線における、隣り合う三角ポリゴン同士の接合が予め考慮された処理が行われているので、表示精度を上げた場合であっても境界稜線部分に隙間が生じることがない。
（データ送信部２５）
このデータ送信部２５は、前記ステップＳ１〜Ｓ１２で生成したデータを、例えば、イントラネットやインターネット等の送信媒体を介して別のコンピュータや記憶媒体に送信する機能を有するものである。
この場合、このデータの送信を受けたコンピュータは、前記画像表示処理部２４に対応するデータ再生プログラムのみを有し、データのレンダリング及び表示及び操作を行うようになっていても良い。
なお、この発明は上記一実施形態に限定されるものではなく、その要旨を変更しない範囲で種々変形可能であることはいうまでもない。
例えば、上記一実施形態では、三角形ポリゴンを用いてＣＡＤデータを構成する三次元形状の近似を行ったが、四角形ポリゴンを用いるようにしても良い。この場合、前記３次の三角ベジェ曲面生成処理は、四角ベジェ曲面を用いるようにすればよい。
さらに、上記実施形態においてベジェ曲面の表現次数は３次であったが、これに限定されるものではない。また、従って、制御点は１０個に限定されるものではない。さらに、三角又は四角のポリゴンの近似においては、ベジェ曲線・曲面による表現式を使わなくてもよい。たとえば、Ｂ−スプライン曲面やＮＵＲＢＳ曲面などの曲面式を使うことも可能である。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【特許請求の範囲】
【請求項１】
三次元ＣＡＤデータの近似方法であって、
（ａ） 指定した変換精度に対し、所定の粗い精度でＣＡＤデータを構成する立体の面をメッシュ分割する工程と、
（ｂ） 前記面の境界稜線を、前記変換精度を用いて曲線で近似し、さらに各曲線を前記の粗い精度でポリライン分割したときの端点・通過点、およびその点での接線ベクトルを設定する工程と、
（ｃ） メッシュ分割にかかる各交点のうち前記境界稜線内の内点同士、若しくは前記内点と境界稜線上の端点・通過点すなわち境界点とを結んで、３または４の頂点を有する多角形ポリゴンを生成する工程と、
（ｄ） 前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを格納する工程と、
（ｅ） 前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定する工程と、
（ｆ） 前記三角または四角の曲面がＣＡＤデータの前記面から所定の誤差範囲内に位置するかを判断し、誤差範囲内に乗っていない場合には、当該曲面の周辺を、分割数を増やし分割幅を小さくして再度メッシュ分割し、前記（ｃ）〜（ｅ）及びこの（ｆ）工程を再度実行させる工程と
を有することを特徴とする前記方法。
【請求項２】
請求項１記載の三次元ＣＡＤデータの近似方法において、
（ｇ）前記多角形のうち、異なる面に属し前記境界稜線を挟んで隣り合う２つの多角形ポリゴン同士を接合する工程
をさらに有し、
この（ｇ）工程は、前記境界稜線上の端点・通過点を２つの多角形ポリゴン間で関連付けるものである方法。
【請求項３】
請求項１記載の三次元ＣＡＤデータの近似方法において、
前記多角形ポリゴンは、三角形ポリゴンであることを特徴とする方法。
【請求項４】
請求項１記載の三次元ＣＡＤデータの近似方法において、
前記曲線はベジェ曲線であることを特徴とする方法。
【請求項５】
請求項１記載の三次元ＣＡＤデータの近似方法において、
前記曲面はベジェ曲面であることを特徴とする方法。
【請求項６】
請求項１記載の方法において、
前記（ｃ）工程は、各頂点の座標と、頂点のうち内点同士を結ぶ稜線についてはそれぞれの点の法線ベクトル、頂点のうち内点と境界点を結ぶ稜線についてはそれぞれの点の法線ベクトル、頂点のうち境界点同士を結ぶ稜線については始点・終点の接線ベクトルを用い、各頂点間に曲線の制御点を生成し、三角または四角の曲面を生成する工程を含むものである
ことを特徴とする方法。
【請求項７】
請求項１記載の三次元ＣＡＤデータの近似方法において、
さらに、
（ｈ） 前記（ｄ）工程で格納された前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定し、その制御点を利用して前記多角形ポリゴンを詳細多角形ポリゴンに再分割する工程と、
（ｉ） 前記詳細多角形ポリゴンで構成される立体形状を表示する３次元データ表示工程と
を有する前記方法。
【請求項８】
三次元ＣＡＤデータの表示方法であって、
（ｊ） 前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを受取って格納する工程と、
（ｋ） 前記（ｊ）工程で格納された前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定し、その制御点を利用して前記多角形ポリゴンを詳細多角形ポリゴンに再分割する工程と、
（ｌ） 前記詳細多角形ポリゴンで構成される立体形状を表示する３次元データ表示工程と
を有する前記方法。
【請求項９】
請求項８記載の三次元ＣＡＤデータの表示方法であって、
前記多角形ポリゴンは、三角形ポリゴンであることを特徴とする方法。
【請求項１０】
請求項８記載の三次元ＣＡＤデータの表示方法において、
前記曲線はベジェ曲線であることを特徴とする方法。
【請求項１１】
請求項８記載の三次元ＣＡＤデータの表示方法において、
前記曲面はベジェ曲面であることを特徴とする方法。
【請求項１２】
請求項８記載の三次元ＣＡＤデータの表示方法において、
（ｍ）表示方法を切り替える切替工程を有し、
この切替工程は、表示形状の大きさを含む表示条件を取得する工程と、
前記取得した表示条件に基づき、細かく表示する必要があると判断した場合には、前記（ｊ）〜（ｌ）の工程を実行し、細かく表示する必要がないと判断した場合には、前記取得した三角ポリゴンをそのまま表示するものである
ことを特徴とする方法。
【請求項１３】
コンピュータシステムに三次元ＣＡＤデータの近似を行なわせるためのコンピュータソフトウエアプログラム製品であって、
記憶媒体と、
指定した変換精度に対し、所定の粗い精度でＣＡＤデータを構成する立体の面をメッシュ分割させる指令と、
前記面の境界稜線を、前記変換精度を用いて曲線で近似し、さらに各曲線を前記の粗い精度でポリライン分割したときの端点・通過点、およびその点での接線ベクトルを設定する指令と、
メッシュ分割にかかる各交点のうち前記境界稜線内の内点同士、若しくは前記内点と境界稜線上の端点・通過点すなわち境界点とを結んで、３または４の頂点を有する多角形ポリゴンを生成する指令と、
前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを格納する指令と、
前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定する指令と、
前記三角または四角の曲面がＣＡＤデータの前記面から所定の誤差範囲内に位置するかを判断し、誤差範囲内に乗っていない場合には、当該曲面の周辺を、分割数を増やし分割幅を小さくして再度メッシュ分割し、前記指令を再度実行させる工程と
を有することを特徴とする前記コンピュータソフトウエアプログラム製品。
【請求項１４】
コンピュータシステムに三次元ＣＡＤデータの近似を行なわせるためのコンピュータソフトウエアプログラム製品であって、
記憶媒体と、
前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを受取って格納する指令と、
前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定し、その制御点を利用して前記多角形ポリゴンを詳細多角形ポリゴンに再分割する指令と、
前記詳細多角形ポリゴンで構成される立体形状を表示する３次元データ表示指令とと
を有するコンピュータソフトウエアプログラム製品。
【請求項１】
三次元ＣＡＤデータの近似方法であって、
（ａ） 指定した変換精度に対し、所定の粗い精度でＣＡＤデータを構成する立体の面をメッシュ分割する工程と、
（ｂ） 前記面の境界稜線を、前記変換精度を用いて曲線で近似し、さらに各曲線を前記の粗い精度でポリライン分割したときの端点・通過点、およびその点での接線ベクトルを設定する工程と、
（ｃ） メッシュ分割にかかる各交点のうち前記境界稜線内の内点同士、若しくは前記内点と境界稜線上の端点・通過点すなわち境界点とを結んで、３または４の頂点を有する多角形ポリゴンを生成する工程と、
（ｄ） 前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを格納する工程と、
（ｅ） 前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定する工程と、
（ｆ） 前記三角または四角の曲面がＣＡＤデータの前記面から所定の誤差範囲内に位置するかを判断し、誤差範囲内に乗っていない場合には、当該曲面の周辺を、分割数を増やし分割幅を小さくして再度メッシュ分割し、前記（ｃ）〜（ｅ）及びこの（ｆ）工程を再度実行させる工程と
を有することを特徴とする前記方法。
【請求項２】
請求項１記載の三次元ＣＡＤデータの近似方法において、
（ｇ）前記多角形のうち、異なる面に属し前記境界稜線を挟んで隣り合う２つの多角形ポリゴン同士を接合する工程
をさらに有し、
この（ｇ）工程は、前記境界稜線上の端点・通過点を２つの多角形ポリゴン間で関連付けるものである方法。
【請求項３】
請求項１記載の三次元ＣＡＤデータの近似方法において、
前記多角形ポリゴンは、三角形ポリゴンであることを特徴とする方法。
【請求項４】
請求項１記載の三次元ＣＡＤデータの近似方法において、
前記曲線はベジェ曲線であることを特徴とする方法。
【請求項５】
請求項１記載の三次元ＣＡＤデータの近似方法において、
前記曲面はベジェ曲面であることを特徴とする方法。
【請求項６】
請求項１記載の方法において、
前記（ｃ）工程は、各頂点の座標と、頂点のうち内点同士を結ぶ稜線についてはそれぞれの点の法線ベクトル、頂点のうち内点と境界点を結ぶ稜線についてはそれぞれの点の法線ベクトル、頂点のうち境界点同士を結ぶ稜線については始点・終点の接線ベクトルを用い、各頂点間に曲線の制御点を生成し、三角または四角の曲面を生成する工程を含むものである
ことを特徴とする方法。
【請求項７】
請求項１記載の三次元ＣＡＤデータの近似方法において、
さらに、
（ｈ） 前記（ｄ）工程で格納された前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定し、その制御点を利用して前記多角形ポリゴンを詳細多角形ポリゴンに再分割する工程と、
（ｉ） 前記詳細多角形ポリゴンで構成される立体形状を表示する３次元データ表示工程と
を有する前記方法。
【請求項８】
三次元ＣＡＤデータの表示方法であって、
（ｊ） 前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを受取って格納する工程と、
（ｋ） 前記（ｊ）工程で格納された前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定し、その制御点を利用して前記多角形ポリゴンを詳細多角形ポリゴンに再分割する工程と、
（ｌ） 前記詳細多角形ポリゴンで構成される立体形状を表示する３次元データ表示工程と
を有する前記方法。
【請求項９】
請求項８記載の三次元ＣＡＤデータの表示方法であって、
前記多角形ポリゴンは、三角形ポリゴンであることを特徴とする方法。
【請求項１０】
請求項８記載の三次元ＣＡＤデータの表示方法において、
前記曲線はベジェ曲線であることを特徴とする方法。
【請求項１１】
請求項８記載の三次元ＣＡＤデータの表示方法において、
前記曲面はベジェ曲面であることを特徴とする方法。
【請求項１２】
請求項８記載の三次元ＣＡＤデータの表示方法において、
（ｍ）表示方法を切り替える切替工程を有し、
この切替工程は、表示形状の大きさを含む表示条件を取得する工程と、
前記取得した表示条件に基づき、細かく表示する必要があると判断した場合には、前記（ｊ）〜（ｌ）の工程を実行し、細かく表示する必要がないと判断した場合には、前記取得した三角ポリゴンをそのまま表示するものである
ことを特徴とする方法。
【請求項１３】
コンピュータシステムに三次元ＣＡＤデータの近似を行なわせるためのコンピュータソフトウエアプログラム製品であって、
記憶媒体と、
指定した変換精度に対し、所定の粗い精度でＣＡＤデータを構成する立体の面をメッシュ分割させる指令と、
前記面の境界稜線を、前記変換精度を用いて曲線で近似し、さらに各曲線を前記の粗い精度でポリライン分割したときの端点・通過点、およびその点での接線ベクトルを設定する指令と、
メッシュ分割にかかる各交点のうち前記境界稜線内の内点同士、若しくは前記内点と境界稜線上の端点・通過点すなわち境界点とを結んで、３または４の頂点を有する多角形ポリゴンを生成する指令と、
前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを格納する指令と、
前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定する指令と、
前記三角または四角の曲面がＣＡＤデータの前記面から所定の誤差範囲内に位置するかを判断し、誤差範囲内に乗っていない場合には、当該曲面の周辺を、分割数を増やし分割幅を小さくして再度メッシュ分割し、前記指令を再度実行させる工程と
を有することを特徴とする前記コンピュータソフトウエアプログラム製品。
【請求項１４】
コンピュータシステムに三次元ＣＡＤデータの近似を行なわせるためのコンピュータソフトウエアプログラム製品であって、
記憶媒体と、
前記多角形ポリゴンの各頂点、その頂点における前記面の法線ベクトル、及び前記境界接線上の端点・通過点については前記法線ベクトルに加えて接線ベクトルを受取って格納する指令と、
前記多角形ポリゴンの頂点の位置、法線ベクトル、接線ベクトルの各データを用い、当該多角形ポリゴン上に、三角または四角の曲面に変換するための複数の制御点を設定し、その制御点を利用して前記多角形ポリゴンを詳細多角形ポリゴンに再分割する指令と、
前記詳細多角形ポリゴンで構成される立体形状を表示する３次元データ表示指令とと
を有するコンピュータソフトウエアプログラム製品。
【国際公開番号】ＷＯ２００５／０６６８５２
【国際公開日】平成１７年７月２１日（２００５．７．２１）
【発行日】平成１９年８月２３日（２００７．８．２３）
【国際特許分類】
【出願番号】特願２００５−５１３１０８（Ｐ２００５−５１３１０８）
【国際出願番号】ＰＣＴ／ＪＰ２００３／０１７０７５
【国際出願日】平成１５年１２月２６日（２００３．１２．２６）
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【出願人】（５９８０７６６０５）ラティス・テクノロジー株式会社 (7)
【Ｆターム（参考）】
【国際公開日】平成１７年７月２１日（２００５．７．２１）
【発行日】平成１９年８月２３日（２００７．８．２３）
【国際特許分類】
【国際出願番号】ＰＣＴ／ＪＰ２００３／０１７０７５
【国際出願日】平成１５年１２月２６日（２００３．１２．２６）
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【出願人】（５９８０７６６０５）ラティス・テクノロジー株式会社 (7)
【Ｆターム（参考）】
[ Back to top ]