(57)【特許請求の範囲】
【請求項１】
曲線を近似するポリラインを生成する３次元形状処理装置において、
生成されたポリラインの節点数が予め設定された節点数の上限を超えている場合、前記ポリライン上の節点であって隣接する２つの節点をつないだ線分と前記曲線との距離が最も小さくなる節点を間引く処理を少なくとも一回以上行い、前記ポリラインの節点数が前記上限以下になるように前記ポリラインの節点を間引く手段と、
前記節点を直線で結ぶことにより前記ポリラインを生成するポリライン生成手段と、を備えたこと特徴とする３次元形状処理装置。
【請求項２】
曲面の境界曲線を近似するポリラインを生成することにより曲面を近似するポリゴンを生成する３次元形状処理装置において、
曲面を近似するポリゴンの数に上限がある場合、該上限を満たすように曲面の境界曲線を近似するポリラインの節点数の上限を設定し、前記ポリライン上の節点であって隣接する２つの節点をつないだ線分と前記境界曲線との距離が最も小さくなる節点を間引く処理を少なくとも一回以上行うことで前記上限を満たすポリラインを生成するポリライン生成手段と、
前記ポリラインを用いてポリゴンを生成するポリゴン生成手段と、
を備えたことを特徴とする３次元形状処理装置。
【請求項３】
曲線を近似するポリラインを生成するポリライン生成プログラムにおいて、
生成されたポリラインの節点数が予め設定された節点数の上限を超えている場合、前記ポリラインの節点数が前記上限に収まるように、前記ポリライン上の節点であって隣接する２つの節点をつないだ線分と前記曲線との距離が最も小さくなる節点を間引く処理を少なくとも一回以上行い、前記ポリラインの節点を間引くことを特徴とするポリライン生成プログラム。
【請求項４】
曲面の境界曲線を近似するポリラインを生成することにより曲面を近似するポリゴンを生成するポリゴン生成プログラムにおいて、
曲面を近似するポリゴンの数に上限がある場合、該上限を満たすように曲面の境界曲線を近似するポリラインの節点数の上限を設定し、前記ポリライン上の節点であって隣接する２つの節点をつないだ線分と前記境界曲線との距離が最も小さくなる節点を間引く処理を少なくとも一回以上行い、前記ポリラインの節点を間引くことで前記上限を満たす前記ポリラインを生成し、前記ポリラインを用いてポリゴンを生成することを特徴とするポリゴン生成プログラム。
【請求項５】
請求項３記載のポリライン生成プログラム、または請求項４記載のポリゴン生成プログラムを記憶したことを特徴とする記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、専用の３次元形状処理装置や、パーソナルコンピュータなど情報処理装置において実施される、曲線を近似するポリライン生成技術などに係わり、特に、ポリラインの数や曲面を近似するポリゴンの数に上限がある場合のポリライン生成技術などに関する。
【０００２】
【従来の技術】
グラフィクス表示装置とコンピュータとを用いたＣＡＤ／ＣＡＭ装置など３次元形状処理装置では、従来より、３次元立体形状を生成したり、生成されている３次元立体形状を変形させたり、その他、様々な処理を行っている。なお、３次元立体形状とは、例えば境界表現形式のソリッドモデルデータとして生成された形状を指し、その境界表現形式のソリッドモデルとは、稜線や頂点や面というような要素により３次元空間上に閉じた領域を定義し、中身の詰まった立体を表現したものである。
本発明は、このような３次元形状処理装置などにおいて従来より行われている３次元形状処理の一つである曲線・曲面生成に係わり、特に、曲線を近似するポリライン（複数の直線）や曲面を表現する境界曲線を近似するポリラインの生成に関する。
なお、従来、このような生成技術では、曲線をポリラインで近似するとき、分割数を指定し、その分割数に従って曲線を等分に分割してその分割点を節点とし、その節点を線分でつなぐことにより、曲線を近似するポリラインを得ていた。
例えば、特開平２−１０４７６号公報に示された曲線近似方法では、曲線上の適当な一点を分割点として求め、曲線の始点と終点とを結ぶ直線と分割点との距離を計算し、その距離が所定値以上の場合には分割されたそれぞれの部分曲線に対してこの処理を繰り返し、距離が所定値未満になった場合には前記のようにして得られた部分曲線の始点および終点を分割点とする。
また、特開平５−２０５０４１号公報に示された曲線近似方法では、曲線上の複数の点を分割点とし、前記曲線の始点と終点とを結ぶ直線と各分割点との距離を計算し、そのうちの最大の距離が所定値以上の場合には分割されたそれぞれの部分曲線に対して前記した処理を繰り返し、所定値未満になった部分曲線についてはそれ以上の分割を止め、得られた部分曲線の始点および終点を分割点とする。
また、特開２０００−１８７７３９公報に示されたポリゴン生成方法では、近似する対象となる曲面と生成するポリゴン（多角形）との間の距離が所定値以下となるようにポリゴンを生成するための内点を格子状に配置するとともに、曲面の境界を表す曲線とそれを近似するポリラインとの間の距離が所定値以下になるようなポリラインを生成し、前記内点とポリラインの節点に基づいてポリゴンを生成する。
【０００３】
【発明が解決しようとする課題】
しかしながら、前記した従来技術による方法では、曲線を分割する際の分割数に上限がある場合、曲線の形状を的確に表現するポリラインを得ることは困難であった。同様に、曲面のポリゴン近似においても、曲面の境界曲線を前記した方法で分割したポリラインで表現すると、その分割数に上限がある場合、曲面の形状を的確に表現するポリゴンを得ることは困難であった。
つまり、少ないポリライン数，ポリゴン数で元の形状をいかに表現するかが課題なのである。
本発明の目的は、このような従来技術の問題を解決することにあり、具体的には、曲線の分割数に上限がある場合に、曲線の形状を的確に表現するポリラインを得ることができる３次元形状処理装置およびポリライン生成プログラムを提供することにある。
【０００４】
【課題を解決するための手段】
前記の課題を解決するための、請求項１の発明では、曲線を近似するポリラインを生成する３次元形状処理装置において、生成されたポリラインの節点数が予め設定された節点数の上限を超えている場合、前記ポリライン上の節点であって隣接する２つの節点をつないだ線分と前記曲線との距離が最も小さくなる節点を間引く処理を少なくとも一回以上行い、前記ポリラインの節点数が前記上限以下になるように前記ポリラインの節点を間引く手段と、前記節点を直線で結ぶことにより前記ポリラインを生成するポリライン生成手段と、を備えたことを特徴とする。
また、請求項２の発明では、面の境界曲線を近似するポリラインを生成することにより曲面を近似するポリゴンを生成する３次元形状処理装置において、曲面を近似するポリゴンの数に上限がある場合、該上限を満たすように曲面の境界曲線を近似するポリラインの節点数の上限を設定し、前記ポリライン上の節点であって隣接する２つの節点をつないだ線分と前記境界曲線との距離が最も小さくなる節点を間引く処理を少なくとも一回以上行うことで前記上限を満たすポリラインを生成するポリライン生成手段と、前記ポリラインを用いてポリゴンを生成するポリゴン生成手段と、を備えたことを特徴とする。
また、請求項３の発明では、曲線を近似するポリラインを生成するポリライン生成プログラムにおいて、生成されたポリラインの節点数が予め設定された節点数の上限を超えている場合、前記ポリラインの節点数が前記上限に収まるように、前記ポリライン上の節点であって隣接する２つの節点をつないだ線分と前記曲線との距離が最も小さくなる節点を間引く処理を少なくとも一回以上行い、前記ポリラインの節点を間引くことを特徴とする。
また、請求項４の発明では、曲面の境界曲線を近似するポリラインを生成することにより曲面を近似するポリゴンを生成するポリゴン生成プログラムにおいて、曲面を近似するポリゴンの数に上限がある場合、該上限を満たすように曲面の境界曲線を近似するポリラインの節点数の上限を設定し、前記ポリライン上の節点であって隣接する２つの節点をつないだ線分と前記境界曲線との距離が最も小さくなる節点を間引く処理を少なくとも一回以上行い、前記ポリラインの節点を間引くことで前記上限を満たす前記ポリラインを生成し、前記ポリラインを用いてポリゴンを生成することを特徴とする。
また、請求項５の発明では、請求項３記載のポリライン生成プログラム、または請求項４記載のポリゴン生成プログラムを記憶した記憶媒体を特徴とする。
【０００５】
また、請求項４記載の発明では、請求項３記載の発明において、節点を間引く際、間引く節点に隣接する２つの節点をつないだ線分と近似対象の曲線の距離が最も小さくなる節点を間引く処理を繰り返す構成にしたことを特徴とする。
また、請求項５記載の発明では、曲面の境界曲線を近似するポリラインを生成することにより曲面を近似するポリゴンを生成するポリゴン生成プログラムにおいて、曲面を近似するポリゴンの数に上限がある場合、その上限を満たすように曲面の境界曲線を近似するポリラインの節点数の上限を設定し、その上限を満たす前記ポリラインを生成し、そのポリラインを用いてポリゴンを生成する構成にしたことを特徴とする。
また、請求項６記載の発明では、プログラムを記憶した記憶媒体において、請求項３または請求項４記載のポリライン生成プログラム、または請求項５記載のポリゴン生成プログラムを記憶したことを特徴とする。
【０００６】
【発明の実施の形態】
以下、図面により本発明の実施の形態を詳細に説明する。
図１は本発明が実施される３次元形状処理装置のハードウェア構成図である。
図示したように、この実施例の３次元形状処理装置は、表示装置に表示された複数の断面形状のなかから操作対象の断面形状を指定したりするマウスやデータを入力するキーボードなど入力装置１、記憶されている３次元形状データに基づいて断面形状など３次元形状を出力する、表示装置やプリンタなど出力装置２、プログラムに従って本発明に係わる３次元形状処理を実行したり３次元形状処理装置全体を制御したりするＣＰＵ３、前記プログラムや各種データを一時的に記憶するメモリ（例えばＲＡＭ）４、設計対象物などの形状を表現した複数の３次元形状データや前記プログラムを記憶しておく記憶装置（例えばハードディスク装置）５、前記プログラムや３次元形状データなどを記憶した記憶媒体からそれらを読み込む媒体駆動装置６などを備えている。
また、この実施例では、請求項記載の曲線分割手段、ポリライン生成手段、およびポリゴン生成手段が、メモリ４に記憶されたプログラムとそのプログラムに従って動作するＣＰＵ３により実現される。
図２は、本発明の一実施例を示す動作フロー図である。以下、図２などに従って、本発明の一実施例を、まず、曲線を近似するポリラインの節点の数に上限がある場合のポリラインの生成方法について説明する。
【０００７】
図３（ａ）に、近似対象の曲線を示す。この実施例では、まず、ポリライン生成手段がこのような曲線をポリラインで近似する際に許容される許容誤差を指定させる（Ｓ１）。なお、許容誤差としては、曲線の長さに対して十分に小さい値（例えば曲線の長さの１００分の１くらい）とする。
続いて、ポリライン生成手段に属する曲線分割手段が曲線のパラメータ空間において曲線を中点で分割し、その点を節点とする（図３（ｂ）参照）（Ｓ２）。
次に、曲線分割手段は曲線の端点とその節点をつないだ線分と曲線の距離（図３（ｂ）参照）を計算する（Ｓ３）。そして、その距離が前記許容誤差以下であれば（Ｓ４でＹｅｓ）適切な表現となる近似であると判定し、ステップＳ５へ進む。それに対して、その距離が許容誤差より大きい場合には（Ｓ４でＮｏ）、分割された線分の両端点を新たな曲線の端点としてステップＳ２から繰り返す（図３（ｂ）（ｃ）参照）。
ここまでの処理で、曲線が複数の節点をつないだポリラインで近似されるが（図３（ｄ）参照）、ここで、曲線分割手段は節点の数が分割数の上限を超えているか否かを判定する（Ｓ５）。そして、超えている場合（Ｓ５でＹｅｓ）、節点の数が上限となるように超過分の一つを間引く（Ｓ６）。この際、両端点以外が間引きの対象になるが、ある節点を間引いた場合、その節点に隣接する節点をつないだ線分があらたな線分となるので、この線分と曲線の距離が一番小さくなる節点を見つけて節点を間引くのである（図３（ｅ）参照）。節点の数が分割数の上限を超えている限り（Ｓ５でＹｅｓ）、これを繰り返し（Ｓ６）、節点の数が分割数の上限以下の場合（Ｓ５でＮｏ）、これで近似の終了となる（図３（ｆ）参照）。
【０００８】
次に、図４により、曲面を近似するポリゴン（多角形）の数に上限がある場合の曲面の境界曲線（曲面の周囲の境界を示す曲線）を近似するポリラインの生成について説明する。
この場合にはまず、ポリゴン生成手段が、境界曲線を近似するポリラインの節点の数から曲面を近似するポリゴンの数を予想し、境界曲線の節点の上限を決定する（Ｓ１１）。例えば、ポリゴン数１００００で曲面を近似する場合、  ポリゴンの形を３角形とすると、境界曲線分割数の上限は約７０となる（たて横が７０分割され、且つ、そのようにして生成された４辺からなるマス目が２分割により３角形メッシュにされるので、７０×７０×２≒１００００）。
次に、曲面をポリゴンで近似するためにポリラインのメッシュを生成するに当たり、ポリライン生成手段は、例えば図５（ａ）に示したような４本の境界曲線Ｅ１，Ｅ２，Ｅ３，Ｅ４を図２に示した方法によりステップＳ１１で決定した節点の上限の半分で分割する（Ｓ１２）。そして、境界曲線Ｅ１とＥ３の節点をマージする（対をつくる）（Ｓ１３）。境界曲線Ｅ１の節点位置と境界曲線Ｅ３の節点位置は異なるので、境界曲線Ｅ１の節点のＥ３側対向位置に新たに節点が追加され、境界曲線Ｅ３の節点のＥ１側対向位置にも新たに節点が追加されるのである。同様に、境界曲線Ｅ２とＥ４の節点をマージする（Ｓ１３）。マージした結果を図５（ｂ）に示す。
続いて、ポリゴン生成手段が、節点をマージしたポリラインをもとに曲面を図５（ｃ）に示したようにメッシュで分割する（Ｓ１４）。さらに、ポリゴン生成手段はそれぞれのマス目を対角線で分割し（Ｓ１５）、図５（ｄ）に示したような３角形のポリゴンを生成する。
以上、本発明の一実施例について説明したが、説明したようなポリライン生成方法またはポリゴン生成方法に従ってプログラミングしたプログラムを例えば着脱可能な記憶媒体に記憶し、その記憶媒体をこれまで本発明によったポリライン生成またはポリゴン生成を行えなかったパーソナルコンピュータなど情報処理装置に装着することにより、または、そのようなプログラムをネットワークを介してそのような情報処理装置へ転送することにより、その情報処理装置においても本発明によったポリライン生成またはポリゴン生成を行うことができる。
【０００９】
【発明の効果】
以上説明したように、本発明によれば、請求項１および請求項３記載の発明では、曲線を近似するポリラインを生成する際、生成されたポリラインの節点数が予め設定された節点数の上限を超えていた場合、そのポリラインの節点数が設定された上限に収まるようにポリラインの節点を間引いて残りの節点により近似対象の曲線が分割され、その節点を直線で結ぶことによりポリラインが生成されるので、曲線の分割数を設定された上限に収めることができる。また、節点を間引く際、間引く節点に隣接する２つの節点をつないだ線分と近似対象の曲線の距離が最も小さくなる節点を間引く処理が繰り返されるので、近似精度の高いポリラインを生成することができる。
また、請求項２および請求項４記載の発明では、曲面の境界曲線を近似するポリラインを生成して曲面をポリゴンで近似する際、曲面を近似するポリゴンの数に上限がある場合、その上限を満たすように曲面の境界曲線を近似するポリラインの節点数の上限が設定され、その上限を満たすポリラインが生成され、そのポリラインを用いてポリゴンが生成されるので、曲面を近似するポリゴンの数を上限に収めることができる。
また、節点を間引く際、間引く節点に隣接する２つの節点をつないだ線分と近似対象の曲線の距離が最も小さくなる節点を間引く処理が繰り返されるので、近似精度の高いポリラインを生成することができる。
また、請求項５記載の発明では、請求項３記載のポリライン生成プログラム、または請求項４記載のポリゴン生成プログラムが着脱可能な記憶媒体に記憶されるので、その記憶媒体をこれまで請求項３記載の発明によったポリライン生成、または請求項４記載の発明によったポリゴン生成を行えなかったパーソナルコンピュータなど情報処理装置に装着することにより、その情報処理装置においても請求項３又は請求項４記載の発明の効果を得ることができる。
【図面の簡単な説明】
【図１】本発明が実施される３次元形状処理装置のハードウェア構成図である。
【図２】本発明の一実施例を示すポリライン生成プログラムのフロー図である。
【図３】本発明の一実施例を示すポリライン生成方法の説明図である。
【図４】本発明の一実施例を示すポリゴン生成プログラムのフロー図である。
【図５】本発明の一実施例を示すポリゴン生成方法の説明図である。
【符号の説明】
１  入力装置、２  出力装置、３  ＣＰＵ、４  メモリ、５  記憶装置、６  媒体駆動装置
【図１】
0004027646.tif 000002
【図２】
0004027646.tif 000003
【図３】
0004027646.tif 000004
【図４】
0004027646.tif 000005
【図５】
0004027646.tif 000006