(57)【要約】【課題】反転や自己干渉の無い複数の部分的なオフセット曲面を生成することにより、形状データの致命的な欠陥を回避するオフセット処理装置を提供する。【解決手段】３次元形状の元曲面データとオフセット値とから該元曲面に対するオフセット曲面を生成するオフセット処理装置であって、前記元曲面を通常領域およびねじれ領域に分割する曲面領域分割処理部と、前記通常領域に対するオフセット曲面を生成する通常領域オフセット処理部と、前記ねじれ領域に対するオフセット曲面を生成するねじれ領域オフセット処理部とを備え、前記通常領域に対するオフセット曲面と前記ねじれ領域に対するオフセット曲面とを合成して、１枚の曲面に対して、反転や自己干渉の無い複数の曲面としてオフセット形状を生成するようにした。【選択図】図１
2006091950.tif 000002
【特許請求の範囲】
【請求項１】
３次元形状の元曲面データとオフセット値とから該元曲面に対するオフセット曲面を生成するオフセット処理装置において、前記元曲面を通常領域およびねじれ領域に分割する曲面領域分割処理部と、前記通常領域に対するオフセット曲面を生成する通常領域オフセット処理部と、前記ねじれ領域に対するオフセット曲面を生成するねじれ領域オフセット処理部とを備え、１枚の曲面に対して、反転や自己干渉の無い複数の曲面としてオフセット形状を生成することを特徴とするオフセット処理装置。
【請求項２】
請求項１に記載のオフセット処理装置において、前記曲面領域分割処理部は、反転領域を間にはさむ２本の等パラメータ線によって、ねじれ領域と残りの２つの通常領域とに１枚の曲面を分割することを特徴とするオフセット処理装置。
【請求項３】
請求項１または２に記載のオフセット処理装置において、前記曲面領域分割処理部は、反転区間の両端において求めた２本の等パラメータ線と、それぞれの等パラメータ線に対してオフセット曲線を求め、等パラメータ線と対応するオフセット曲線との間にそれぞれルールド曲面を生成し、どちらのオフセット曲線も相手側のルールド曲面と干渉し、かつ、２つのオフセット曲線同士が交わっている場合、それらのオフセット曲線に対応した２つの等パラメータ線の間にある元曲面上の領域をねじれ領域とし、それ以外の元曲面上の領域を通常領域と判定することを特徴とするオフセット処理装置。
【請求項４】
請求項２または３に記載のオフセット処理装置において、前記曲面領域分割処理部は、元曲面の境界曲線上の各点について元曲面上の主曲率を求め、
（１）０＜１／最大主曲率＜オフセット値、または、
（２）０＞１／最小主曲率＞オフセット値
のいずれかを満す点を反転区間にある点であるとみなして、反転区間を検出するようにしたことを特徴とするオフセット処理装置。
【請求項５】
請求項３に記載のオフセット処理装置において、前記オフセット曲線は、複数の３次Ｂｅｚｉｅｒ曲線セグメントから構成される近似オフセット曲線として求めることを特徴とするオフセット処理装置。
【請求項６】
請求項１に記載のオフセット処理装置において、前記通常領域オフセット処理部は、２つのそれぞれの通常領域について近似オフセット曲面を生成し、これらの近似オフセット曲面同士の干渉線を境にそれぞれの近似オフセット曲面を分割して不要な部分を除去することによって、通常領域に対して反転や自己干渉の無い２枚の曲面を生成することを特徴とするオフセット処理装置。
【請求項７】
請求項１に記載のオフセット処理装置において、前記ねじれ領域オフセット処理部は、ねじれ領域に含まれる２つの区間のうち、反転区間とは異なる区間について元曲面の境界曲線をオフセットした１本の近似オフセット曲線と、ねじれ領域の境となる２つの等パラメータ線について求めた近似オフセット曲線を互いの干渉点で分割し、反転区間の両端点をオフセットした点とは異なる側にある２本の近似オフセット曲線とからなる３本の近似オフセット曲線を生成し、ねじれ領域の境となる２つの等パラメータ線について求めた近似オフセット曲線の干渉点に対応した点を、この２つの等パラメータ線上にそれぞれ求めてねじれ領域を２つに分割し、この２つに分割されたねじれ領域のうち、反転区間とは異なる側の領域を元曲面とし、前記３本の近似オフセット曲線を境界曲線として近似オフセット曲面を生成することを特徴とするオフセット処理装置。
【請求項８】
３次元形状の元曲面データとオフセット値とから該元曲面に対するオフセット曲面を生成するオフセット処理方法において、前記元曲面を通常領域およびねじれ領域に分割し、前記通常領域に対してオフセット曲面を生成し、前記ねじれ領域に対してオフセット曲面を生成することにより、１枚の曲面に対して、反転や自己干渉の無い複数の曲面としてオフセット形状を生成することを特徴とするオフセット処理方法。
【請求項９】
コンピュータに、請求項１乃至７のいずれかに記載のオフセット処理装置の機能を実行させるためのプログラム。
【請求項１０】
請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オフセット処理装置、オフセット処理方法、プログラムおよび記録媒体に関し、より詳細には、３次元ＣＡＤ/ＣＡＭにおける一枚面の曲面形状のオフセット形状を反転や自己干渉の無い複数の曲面として生成する技術に関する。
【背景技術】
【０００２】
３Ｄ  ＣＡＤ等に代表される３次元の形状モデリングシステムは、そのモデリング機能の発展とともに、近年、産業界に広く浸透しつつある。なかでも曲面をオフセットする機能は、工業製品として厚さ一定の形状を設計する場合や、金型製造でカッターパスを計算する場合など、非常に多くの場面で利用されている。
【０００３】
次の式（１）は、１枚の曲面ｒ(u, v) (以下、元曲面という)に対するオフセット曲面ｒｏ(u, v) を表したものである。
ｒｏ(u, v) =ｒ(u, v) +ｎ(u, v)d            （１）
ここで、d はオフセットする距離であり、0 以外の実数である(以下、ｄをオフセット値という)。n(u, v) は、 (u, v) における曲面 r(u, v) 上の正規化された法線ベクトルであり、次式（２）で与えられる。
【０００４】
【数１】
2006091950.tif 000003
【０００５】
つまり、オフセット曲面とは、元曲面上のすべての点を、その点における法線ベクトルの方向に一定距離d だけ移動した点からなる集合である。また、式（２）の通り、表現式に自乗根が含まれることや、元曲面上のへそ点による縮退、カスプ、自己干渉などが発生する場合があることから、一般に、オフセット曲面は元曲面に比べて複雑である。
この複雑さが一因し、多くの場面で利用されているものの、曲面をオフセットする機能では、オフセット曲面の反転や自己干渉に起因する問題がしばしば起こっている。
【０００６】
図１６は、オフセット曲面が反転して自己干渉する例である。図１６（Ａ）のような元曲面を図１６（Ｂ）のように内側へオフセットした場合、図１６(Ｃ)の太線で囲われた領域は、元曲面と法線ベクトルの向きが反対になる（つまり反転している）。図１６(Ｄ)の太線部分は、オフセット曲面が自分自身と交わっている（つまり自己干渉している）。
このようなオフセット曲面が設計形状に含まれると、物理的に存在し得ない形状を表現してしまうことになり、カッターパスを計算する場合にこのようなオフセット曲面を利用すると、金型や製品を削り過ぎて製品の加工に失敗する。
【０００７】
このようにオフセット曲面が反転したり自己干渉すると、形状データに致命的な欠陥が生じるという問題が起こるので、３次元の形状モデリングシステムで曲面をオフセットする際は、この反転や自己干渉を取り除く必要がある。
【０００８】
このオフセット曲面の反転や自己干渉を取り除く方法については、既に研究や調査がなされており、回転面や押出面のオフセットについては、一般曲面では特別な場合については既に解決されているが、すべてが解決されている訳ではない。
【０００９】
一方、オフセット曲面が反転するケースは、元曲面上の法曲率を調べることにより判明する。オフセット曲面を表す式（１）において、元曲面上の任意の点(u、v)における法曲率κは次の式（３）で示される。
【００１０】
【数２】
2006091950.tif 000004
【００１１】
ここで、式（３）の右辺の分母は第一基本形式、分子は第二基本形式であり、Ｅ、Ｆ、Ｇおよび、Ｌ、Ｍ、Ｎは、次式（４）で与えられる。
【００１２】
【数３】
2006091950.tif 000005
【００１３】
ここで、オフセット値d に対し、κ > 0 かつ d > 0、あるいは、κ < 0 かつ d < 0の場合、曲率半径 1/κ の絶対値が d の絶対値より小さいとき、その点においてオフセット曲面は反転する。そこで、このような点だけからなる元曲面上の領域を「反転領域」と呼ぶ。また、元曲面上の４本の境界曲線r(u, 0), r(1, v), r(u, 1), r(0, v)において、反転領域に含まれる連続した区間を「反転区間」と呼ぶ。
【００１４】
一方、オフセット曲面が自己干渉するケースには、図１６のように反転領域を挟んでオフセット曲面が自己干渉する「局所自己干渉」と、図１７のように反転領域とは関係無くオフセット曲面が自己干渉する「大域自己干渉」があるが、以下、本発明の対象である「局所自己干渉」の場合について説明する。
【００１５】
ここで、元曲面に反転領域が１つだけ存在する状況を、元曲面の境界曲線に着目して、次の５つのパターンに分類する。
【００１６】
(パターン１)境界曲線を１つ含む場合。
(パターン２)境界曲線を２つ含む場合。
(パターン３)境界曲線を３つ含む場合。
(パターン４)境界曲線を４つ含む場合。
(パターン５)境界曲線を含まない場合。
【００１７】
図１８は、元曲面r(u, v) 上に反転領域が１つだけ存在する状況を、元曲面r(u, v) のパラメータ空間上で示したものである。太線で囲われた領域が反転領域であり、この状況は、パターン５に該当する。
また、(u1, v1) と (u2, v2) のそれぞれにおける u 方向と v 方向の等パラメータ線とで囲われる領域を１つの元曲面と見た場合、反転領域の状況はパターン４に該当する。
同様に、(u1, v1) と (u2, 1) の場合はパターン３、(u1, v1) と (1, 1)、および、(0, v1) と (1, v2) の場合はそれぞれパターン２、(0, v1) と (1, 1) の場合はパターン１に該当する。
【００１８】
ここで、１つの境界曲線に２つ以上の反転区間は存在しないと仮定し、反転区間の両端における元曲面上の２本の異なる等パラメータ線に着目し、パターン１を次の２つに分類する。
【００１９】
(パターン１１)等パラメータ線が反転領域の内部を通過しない（図１９（Ａ）参照）。
(パターン１２)等パラメータ線が反転領域の内部を通過する（図１９（Ｂ）参照）。
【００２０】
図２０は、パターン１１に該当する例であり、局所自己干渉を起こしている。図２１は、図２０における反転区間を含む境界曲線のオフセット曲線を前方、側方および上方の各視点から見たものであり、太線で示した曲線がオフセット曲線である。このオフセット曲線は、図１６と異なり、それ自身では自己干渉していない。
【００２１】
非特許文献１は、反転や自己干渉の無いオフセット曲面の生成方法に関する比較的最近の研究である。この非特許文献１では、先ず、元曲面の幾つかの等パラメータ線上にサンプル点をとり、そのサンプル点をオフセットしている。次に、サンプル点をとった等パラメータ線ごとに、そのサンプル点をオフセットした点列間を直線で補間することにより折れ線を生成している。そして、各折れ線が自己干渉するかどうかを検出し、自己干渉していれば、自己干渉しないよう折れ線から不要な部分を取り除く。最後に、不要な部分を取り除いた折れ線から新たなサンプル点を抽出し、近似された１枚のオフセット曲面を生成している。
【非特許文献１】G.V.V.Ravi Kumar, K.G.Shastry, B.G.Prakash著,「Computing non-self-intersecting offsets of NURBS surfaces」,Computer Aided Design, Vol.34, No.3, 2002年, pp.209-228.
【発明の開示】
【発明が解決しようとする課題】
【００２２】
しかしながら、非特許文献１の方法では、図２０の場合、反転区間を含む境界曲線において上述の折れ線が自己干渉を起こさないため、反転や自己干渉を取り除くことができない。
【００２３】
本発明は、上記のような実情を考慮してなされたものであって、下記の２つの条件を満たすケースを処理の対象とし、反転や自己干渉の無い複数の部分的なオフセット曲面を生成することにより、形状データの致命的な欠陥を回避するオフセット処理装置、オフセット処理方法、プログラムおよび記録媒体を提供することを目的とする。
【００２４】
(条件１)等パラメータ線が反転領域の内部を通過しない（パターン１１となる）元曲面上に反転領域が１つ存在する。
(条件２)局所自己干渉は起こすが、大域自己干渉は起こさない。
【課題を解決するための手段】
【００２５】
上記課題を解決するために、請求項１に記載の発明は、３次元形状の元曲面データとオフセット値とから該元曲面に対するオフセット曲面を生成するオフセット処理装置において、前記元曲面を通常領域およびねじれ領域に分割する曲面領域分割処理部と、前記通常領域に対するオフセット曲面を生成する通常領域オフセット処理部と、前記ねじれ領域に対するオフセット曲面を生成するねじれ領域オフセット処理部とを備え、１枚の曲面に対して、反転や自己干渉の無い複数の曲面としてオフセット形状を生成することを特徴とする。
【００２６】
請求項２に記載の発明は、請求項１に記載のオフセット処理装置において、前記曲面領域分割処理部は、反転領域を間にはさむ２本の等パラメータ線によって、ねじれ領域と残りの２つの通常領域とに１枚の曲面を分割することを特徴とする。
【００２７】
請求項３に記載の発明は、請求項１または２に記載のオフセット処理装置において、前記曲面領域分割処理部は、反転区間の両端において求めた２本の等パラメータ線と、それぞれの等パラメータ線に対してオフセット曲線を求め、等パラメータ線と対応するオフセット曲線との間にそれぞれルールド曲面を生成し、どちらのオフセット曲線も相手側のルールド曲面と干渉し、かつ、２つのオフセット曲線同士が交わっている場合、それらのオフセット曲線に対応した２つの等パラメータ線の間にある元曲面上の領域をねじれ領域とし、それ以外の元曲面上の領域を通常領域と判定することを特徴とする。
【００２８】
請求項４に記載の発明は、請求項２または３に記載のオフセット処理装置において、前記曲面領域分割処理部は、元曲面の境界曲線上の各点について元曲面上の主曲率を求め、
（１）０＜１／最大主曲率＜オフセット値、または、
（２）０＞１／最小主曲率＞オフセット値
のいずれかを満す点を反転区間にある点であるとみなして、反転区間を検出するようにしたことを特徴とする。
【００２９】
請求項５に記載の発明は、請求項３に記載のオフセット処理装置において、前記オフセット曲線は、複数の３次Ｂｅｚｉｅｒ曲線セグメントから構成される近似オフセット曲線として求めることを特徴とする。
【００３０】
請求項６に記載の発明は、請求項１に記載のオフセット処理装置において、前記通常領域オフセット処理部は、２つのそれぞれの通常領域について近似オフセット曲面を生成し、これらの近似オフセット曲面同士の干渉線を境にそれぞれの近似オフセット曲面を分割して不要な部分を除去することによって、通常領域に対して反転や自己干渉の無い２枚の曲面を生成することを特徴とする。
【００３１】
請求項７に記載の発明は、請求項１に記載のオフセット処理装置において、前記ねじれ領域オフセット処理部は、ねじれ領域に含まれる２つの区間のうち、反転区間とは異なる区間について元曲面の境界曲線をオフセットした１本の近似オフセット曲線と、ねじれ領域の境となる２つの等パラメータ線について求めた近似オフセット曲線を互いの干渉点で分割し、反転区間の両端点をオフセットした点とは異なる側にある２本の近似オフセット曲線とからなる３本の近似オフセット曲線を生成し、ねじれ領域の境となる２つの等パラメータ線について求めた近似オフセット曲線の干渉点に対応した点を、この２つの等パラメータ線上にそれぞれ求めてねじれ領域を２つに分割し、この２つに分割されたねじれ領域のうち、反転区間とは異なる側の領域を元曲面とし、前記３本の近似オフセット曲線を境界曲線として近似オフセット曲面を生成することを特徴とする。
【００３２】
請求項８に記載の発明は、３次元形状の元曲面データとオフセット値とから該元曲面に対するオフセット曲面を生成するオフセット処理方法において、前記元曲面を通常領域およびねじれ領域に分割し、前記通常領域に対してオフセット曲面を生成し、前記ねじれ領域に対してオフセット曲面を生成することにより、１枚の曲面に対して、反転や自己干渉の無い複数の曲面としてオフセット形状を生成することを特徴とする。
【００３３】
請求項９に記載の発明は、コンピュータに、請求項１乃至７のいずれかに記載のオフセット処理装置の機能を実行させるためのプログラムである。
請求項１０に記載の発明は、請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００３４】
本発明によれば、下記の２つの条件を満たすケースを処理対象とした場合、１枚の曲面に対して、反転や自己干渉の無い複数の曲面としてオフセット形状を生成することができる。
【００３５】
(条件１)等パラメータ線が反転領域の内部を通過しない（パターン１１となる）元曲面上に反転領域が１つ存在する。
(条件２)局所自己干渉は起こすが、大域自己干渉は起こさない。
【発明を実施するための最良の形態】
【００３６】
以下、図面を参照して、本発明のオフセット処理装置に係る好適な実施形態について説明する。
【００３７】
本発明のオフセット処理装置では、まず、反転領域を間にはさむ２本の等パラメータ線によって、１枚の曲面を３つの領域に分割する。このとき、２本の等パラメータ線によって挟まれる領域を「ねじれ領域」と呼び、残りの２つの領域のことを「通常領域」と呼ぶ。そして、それぞれの領域に対してオフセット処理を行なうことにより、反転や自己干渉の無い複数の曲面を生成し、一枚面のオフセット処理を行うようにした。
【００３８】
図１は、本発明の実施形態に係るオフセット処理装置の機能構成を示すブロック図であり、同図において、オフセット処理装置は、入力処理部１、曲面領域分割処理部２、通常領域オフセット処理部３、ねじれ領域オフセット処理部４、出力処理部５を含んでなっている。
【００３９】
これらの処理部は、概略、次のような処理を行う。
入力処理部１は、記憶装置や３次元形状処理装置等のアプリケーション等から、元曲面の曲面データ、オフセット値、近似許容誤差、反転区間検出閾値等の入力データを受け取り、曲面領域分割処理部２にデータを渡す。
曲面領域分割処理部は、入力処理部１より受け取った曲面データを、「通常領域」および「ねじれ領域」の２種類の領域に分割し、「通常領域」のデータは通常領域オフセット処理部３に渡し、「ねじれ領域」のデータはねじれ領域オフセット処理部４に渡す。
通常領域オフセット処理部３は、曲面領域分割処理部２より受け取った「通常領域」のデータに対してオフセット処理を行ない、結果を出力処理部５に渡す。
ねじれ領域オフセット処理部４は、曲面領域分割処理部２より受け取った「ねじれ領域」のデータに対してオフセット処理を行ない、結果を出力処理部５に渡す。
出力処理部５は、通常領域オフセット処理部３、および、ねじれ領域オフセット処理部４より受け取ったデータを１つのデータにまとめ、外部に出力する。
【００４０】
以下、曲面領域分割処理部２、通常領域オフセット処理部３、ねじれ領域オフセット処理部４のそれぞれの処理ついて詳細に説明する。
【００４１】
（Ａ）曲面領域分割処理部１：
図２に示すフローチャートを用いて、曲面領域分割処理部１の処理動作を説明する。なお、等パラメータ線は、以下の説明では元曲面上の境界曲線を含まないものとする。
【００４２】
まず、元曲面上の境界曲線のオフセット曲線を生成する（ステップＳ１０）。
オフセット曲線は、式（１）によって理論的に表現できるが、元曲面が平面や円柱面など、解析的に表現できる場合を除き、理論上のオフセット曲線を実際に求めるのは困難である。このような場合、オフセット曲線は、理論上のオフセット曲線を近似した曲線として生成する(以下、近似オフセット曲線という)。このとき、オフセット曲線を求める対象となる曲線のことを「元曲線」と呼ぶ。本発明でも、オフセット曲線を近似オフセット曲線として求める。
【００４３】
生成したオフセット曲線の情報を利用して反転区間を検出する（ステップＳ１１）。この反転区間の検出方法については後述する。
反転区間が検出されないか、または、２つ以上の反転区間が検出されたり、既に反転区間が検出された他の境界曲線が存在する場合（ステップＳ１２のＮＯ）、本発明の対象ではないと判断して処理を終了する。
【００４４】
一方、反転区間が１つ見つかった場合（ステップＳ１２のＹＥＳ）、反転区間の両端において、２本の等パラメータ線を求め、それぞれの等パラメータ線に対するオフセット曲線を求める(図３（Ａ）参照)（ステップＳ１３）。
【００４５】
上記の等パラメータ線に対して求めたオフセット曲線と、それと対応する等パラメータ線との間にそれぞれルールド曲面を生成する(図３（Ｂ）参照)（ステップＳ１４）。
このルールド曲面は、例えば、公知の技術「Les A. Piegl and Wayne Tiller著, 「The NURBS Book」, Springer-Verlag, 1995.」によって生成することができる。
【００４６】
等パラメータ線に対して生成したオフセット曲線と、ルールド曲面との干渉計算を行う（ステップＳ１５）。
この干渉計算は、一方のルールド曲面上のオフセット曲線と、もう一方のルールド曲面との間でそれぞれ行う。つまり、線―面間の干渉計算を２回実行することになる（図４参照）。
【００４７】
上記干渉計算の結果に応じ、次の３つのケースのうちのいずれかを実行する（ステップＳ１６）。
【００４８】
（ケース１）どちらのオフセット曲線も相手側のルールド曲面と干渉し、かつ、２つのオフセット曲線同士が交わっている場合、それらのオフセット曲線に対応した２つの等パラメータ線の間にある元曲面上の領域をねじれ領域とし、それ以外の元曲面上の領域を通常領域とする。
【００４９】
（ケース２）どちらのオフセット曲線も相手側のルールド曲面と干渉していない場合、あるいは、(ケース１）とは異なり、どちらのオフセット曲線も相手側のルールド曲面と干渉している場合、本発明の対象ではないと判断して処理を中断する。
【００５０】
（ケース３）一方のオフセット曲線のみが干渉する場合、干渉するオフセット曲線と対応する反転区間の端点について、反転区間が広がる方向にその端点を移動し、新しい反転区間とする(図５参照)。このとき、移動後の端点における等パラメータ線のオフセット曲線が、ステップＳ１５において干渉しなかったオフセット曲線と交差するよう、その端点の位置を移動させ（端点の移動方法については後述する）、新しい反転区間の両端における２本の等パラメータ線に挟まれた元曲面上の領域をねじれ領域とし、それ以外の領域を通常領域とする。
【００５１】
図６のフローチャートを用いて、オフセット曲線を求める処理について説明する。
このオフセット曲線は、上述したように近似オフセット曲線として求められるが、ここでは近似オフセット曲線を、複数の３次Ｂｅｚｉｅｒ曲線セグメントから構成される区分Ｂｅｚｅｉｒ曲線として生成する。このとき、近似誤差の許容値としては、理論上のオフセット曲線との距離の許容誤差(近似許容誤差)を与える。
【００５２】
まず、元曲線の両端点をオフセットした点(以下、オフセット点という)を求め、それらの点を両端点とする１本のＢｅｚｉｅｒ曲線セグメントを生成する（ステップＳ２０）。
このとき、両端点における接線ベクトルの向きは、次式（５）で得られるオフセット点上の偏微分ベクトルの向きとする。
【００５３】
【数４】
2006091950.tif 000006
【００５４】
各Ｂｅｚｉｅｒ曲線セグメントを４つに分割する点をサンプル点とし、それらの点が、オフセット曲線上の点として許容誤差を満たしているかどうかを評価する（ステップＳ２１）。
評価した結果、すべてのサンプル点が許容誤差を満たす場合（ステップＳ２２のＹＥＳ）、求められた各Ｂｅｚｉｅｒ曲線セグメントを近似オフセット曲線として処理を終了する。
【００５５】
評価した結果、許容誤差を満たしていないサンプル点が存在する場合（ステップＳ２２のＮＯ）、このＢｅｚｉｅｒ曲線セグメントに対応した元曲線を２分割し、その分割した点のオフセット点を求める（ステップＳ２３）。
許容誤差を満たしていないサンプル点が存在するＢｅｚｉｅｒ曲線セグメントの両端点とステップＳ２３で求めたオフセット点とから、新たにＣ１連続な２本のＢｅｚｉｅｒ曲線セグメントを生成し、許容誤差を満たしていないサンプル点を含むＢｅｚｉｅｒ曲線セグメントと置き換え（ステップＳ２４）、ステップＳ２１へ戻る。ここで求めたオフセット点における接線ベクトルの向きは、式(１)と同様に求める。
【００５６】
次に、図７のフローチャートを用いて、反転区間の検出処理について説明する。
元曲面の境界曲線に対して生成された近似オフセット曲線である各Ｂｅｚｉｅｒ曲線セグメントの端点に対応する境界曲線上の点を求め、それらの点を境界曲線に沿った１つの点列（以下、点列Ａという）とし、この点列Ａ上の各点について元曲面上の主曲率を求める（ステップＳ３０）。このとき、オフセット値 d が正の値の場合は最大主曲率κｍａｘを求め、負の値の場合は最小主曲率κｍｉｎを求める。
【００５７】
上記点列Ａ中の各点のうち、反転区間にある点を取り出す（ステップＳ３１）。上記点列Ａ中のすべての点について、（１）d > 0 かつ κｍａｘ > 0 で 1/κｍａｘ < d 、または、（２）d < 0 かつ κｍｉｎ < 0 で 1/κｍｉｎ > d のいずれを満すかを判断し、条件を満たした場合、この点を反転区間の点であるとみなす。
【００５８】
反転区間の点が複数検出された場合、反転区間の点だけからなる一続きの点列Ｂを、点列Ａから点の重複なく取り出す（図８参照）（ステップＳ３２）。ここで、点列Ｂが複数取り出された場合は、反転区間も複数存在することになる。
【００５９】
ステップＳ３２で取り出した点列Ｂのそれぞれについて、反転区間と通常区間（反転区間とならなかった境界曲線上の区間をいう）との境界の端点をみつけ、反転区間を検出する（ステップＳ３３）。
この反転区間と通常区間との境界の端点は、次のような処理を繰り返して求める。
【００６０】
まず、この点列Ｂの両端の点、この両端点と点列Ａにおいて隣り合い、反転区間とはみなされなかった点Ｃによって区切られる元曲面上の境界曲線の区間について、その区間をパラメータ空間で２分割する点Ｐを求めて点列Ａに加える。
次に、分割点Ｐが反転区間の点かどうかを上記ステップＳ３０、Ｓ３１と同様に調べ、反転区間の点とみなされた場合、点Ｐを反転区間の点列Ｂへ加え、点Ｐと点列Ａにおいて隣り合い、反転区間とはみなされなかった点を取り出す。一方、分割点Ｐが反転区間の点とみなされなかった場合は、点Ｐと点列Ａにおいて隣り合い、反転区間とみなされた点を取り出す。
【００６１】
この取り出した点を上記の点Ｃとみなし、点列Ｂの両端点とこの点Ｃとで上記の手順を繰り返す。この繰り返し操作は、上記分割点Ｐで２分割された後の境界曲線の区間が、パラメータ空間で十分小さくなるまで行なう。十分小さいかどうかは、あらかじめパラメータ長さの閾値（例えば、１０−３などの値）を設定しておき、その閾値との比較を行なうことにより判断する(反転区間判定閾値)。
【００６２】
次に、反転区間の端点は、次の手順で移動処理を行う。
移動させる端点につながる通常区間において、通常区間をパラメータで２分割する点を求める（ステップＳ４０）。
求めた点における等パラメータ線の近似オフセット曲線を求め、干渉していたルールド曲面との干渉計算を行う（ステップＳ４１）。
【００６３】
ステップＳ４１の干渉計算の結果に応じて、次の３つのケースのいずれかを行なう。
（ケース１）ルールド曲面と干渉し、かつ、近似オフセット曲線同士が交わる場合、ステップＳ４１の等パラメータ線を求めた点に反転区間の端点を移動させる。
【００６４】
（ケース２）ルールド曲面と干渉し、かつ、近似オフセット曲線同士が交わらない場合、等パラメータ線を境に反転区間側の通常区間を２分割する点を求め、ステップＳ４１以降の手順を繰り返す。
【００６５】
（ケース３）ルールド曲面と干渉しない場合、等パラメータ線を境に反転区間とは異なる側の通常区間を２分割する点を求め、ステップＳ４１以降の手順を繰り返す。
【００６６】
（Ｂ）通常領域オフセット処理部３：
図９に示すフローチャートを用いて、通常領域オフセット処理部３の処理動作を説明する。
２つのそれぞれの通常領域について、１つの通常領域を囲む４本の曲線に対して、それぞれ近似オフセット曲線を求め（図１０参照）、求めた近似オフセット曲線を境界として、公知の技術「佐藤 直之, 徳山 喜政著,「微小要素の発生を抑制した複数面のオフセット方法」,情報処理学会論文誌, Vol.44, No.9, 2003年、pp.2374-2382.」により内部に近似オフセット曲面を生成する(ステップＳ４０)。
【００６７】
２つの通常領域に対して求めた近似オフセット曲面同士の干渉線を求め、この干渉線を境にそれぞれの近似オフセット曲面を分割して２つの領域に分ける（ステップＳ４１）。
このとき、等パラメータ線をオフセットした近似オフセット曲面の境界同士は互いに交わる。つまり、干渉線の一方の端点は、近似オフセット曲面の境界に位置する。しかし、もう一方の端点は両方の近似オフセット曲面の境界に位置するとは限らない。このため、どちらか一方の近似オフセット曲面は、干渉線を境に分割することができない場合がある。このような場合、分割することができた方の近似オフセット曲面と元曲面との間にルールド曲面を生成し、生成したルールド曲面と分割できなかった方の近似オフセット曲面との干渉線を求める。このルールド曲面は、分割することができた方の近似オフセット曲面に対応した通常領域において、反転区間に接続する通常区間と、その近似オフセット曲線との間に生成する(図１１（Ａ）参照)。そして、求めた干渉線と合わせて分割できなかった近似オフセット曲面を分割する。
【００６８】
２つの領域に分割された各近似オフセット曲面について、オフセット値が正の実数の場合、互いの近似オフセット曲面の裏側に位置する領域を不要とみなして除去し、オフセット値が負の実数の場合、互いの近似オフセット曲面の表側に位置する領域を不要とみなして除去する(図１１（Ｂ）参照)（ステップＳ４２）。
【００６９】
これにより、通常領域に対して反転や自己干渉の無い２枚の曲面が生成される。
【００７０】
（Ｃ）ねじれ領域オフセット処理部４：
図１２に示すフローチャートを用いて、ねじれ領域オフセット処理部４の処理動作を説明する。
まず、３本の近似オフセット曲線を生成する（ステップＳ５０）。このうち、１本は、ねじれ領域に含まれる２つの区間のうち、反転区間とは異なる区間について元曲面の境界曲線をオフセットした近似オフセット曲線である(図１３（Ａ）参照)。他の２本は、ねじれ領域の境となる２つの等パラメータ線について、それぞれ近似オフセット曲線を求め、求めた近似オフセット曲線を互いの干渉点で分割し、４本の近似オフセット曲線とし、分割後の近似オフセット曲線のうち、反転区間の両端点をオフセットした点とは異なる側にある２つの近似オフセット曲線である(図１３（Ｂ）参照)。
【００７１】
後述する方法で、ねじれ領域を２つの領域に分割する（ステップＳ５１）。
この２つに分割されたねじれ領域のうち、反転区間とは異なる側の領域を元曲面として近似オフセット曲面を生成する（ステップＳ５２）。ただし、このとき、近似オフセット曲面の境界となる近似オフセット曲線には、ステップＳ５０で求めた３本の近似オフセット曲線を与え、また、ねじれ領域を２つに分割した曲線上のオフセット点は、すべて、ねじれ領域の境となる２つの等パラメータ線について求めた近似オフセット曲線の干渉点の位置に集中するものとして処理を行なう。
これにより、ねじれ領域に対して反転や自己干渉の無い曲面が生成される。
【００７２】
以上により求められた通常領域オフセット処理部３とねじれ領域オフセット処理部４で生成したオフセット曲面に合成することによって、反転や自己干渉の無い複数の曲面として生成する一枚面のオフセット処理を実現することが可能となる。
【００７３】
次に、ステップＳ５１におけるねじれ領域を２つの領域に分割する処理について説明する。
ステップＳ５０で求めた２本の近似オフセット曲線について、各Ｂｅｚｉｅｒ曲線セグメントの端点が対応している等パラメータ線上の点を求める(図１４（Ａ）参照)（ステップＳ６０）。
【００７４】
ステップＳ６０で求めた、等パラメータ線上の各点のパラメータ位置 (u, v) について、この等パラメータ線とは異なる方向(u方向またはv方向)のパラメータ値を取り出し、それらを整列して、u または v 方向に関する１つのパラメータ値の列を求める（ステップＳ６１）。
【００７５】
ねじれ領域の境となる２つの等パラメータ線について求められた近似オフセット曲線の干渉点に対応した点を、この２つの等パラメータ線上にそれぞれ求める(図１４（Ｂ）参照)（ステップＳ６２）。
【００７６】
ステップＳ６１で求めたパラメータ値の列から、次の（ａ）および（ｂ）の条件をともに満たすパラメータ値を取り出す（ステップＳ６３）。
（ａ）元曲面のパラメータ空間において、ステップＳ６２で求めた２つの点のどちらよりも反転区間から遠くに位置する。
（ｂ）元曲面のパラメータ空間において、ステップＳ６２で求めたで求めた２つの点のどちらか一方に最も近くなる。
【００７７】
ステップＳ６３で取り出したパラメータ値において、ねじれ領域を２つに分割する等パラメータ線をねじれ領域内に求め(図１４（Ｂ）参照)、その等パラメータ線に対応する近似オフセット曲線を求める（ステップＳ６４）。
【００７８】
ステップＳ６４で求めた等パラメータ線を元曲面の境界と見た場合、この等パラメータ線上に反転区間が存在するかどうかを、ステップＳ６４で求めた近似オフセット曲線の情報を利用して、上述した反転区間の検出方法によって調べる（ステップＳ６５）。
【００７９】
ステップＳ６５において反転区間が存在しなかった場合、ステップＳ６４で求めた等パラメータ線をもって、ねじれ領域を２つに分割する。一方、反転区間が存在した場合、ステップＳ６４で着目したパラメータ値の次に、上記条件（ｂ）を満たすパラメータ値を、ステップＳ６１で求めたパラメータ値の列から取り出す（ステップＳ６６）。ただし、このとき、上記の条件（ａ）は満たすものとする。
【００８０】
ステップＳ６６で求めたパラメータ値を、ステップＳ６３で取り出したパラメータ値の代わりに与え、ステップＳ６４以降の処理を繰り返す。
【００８１】
本発明のオフセット処理装置を使って、図２０の元曲面に対してオフセット曲面を生成すると、図１５のような結果を得る。図１５（Ａ）はオフセット曲面をワイヤーフレーム表示したものであり、図１５（Ｂ）はシェーディング表示したものである。それぞれ、反転や自己干渉の無い３枚の曲面（図１５（Ｃ），（Ｄ），（Ｅ）参照）によりオフセット形状が生成されており、形状データの致命的欠陥が回避されている。
【００８２】
さらに、本発明は上述した実施形態のみに限定されたものではない。上述した実施形態のオフセット処理装置を構成する各機能をそれぞれプログラム化し、あらかじめＣＤ−ＲＯＭ等の記録媒体に書き込んでおき、このＣＤ−ＲＯＭをＣＤ−ＲＯＭドライブのような媒体駆動装置を搭載したコンピュータに装着して、これらのプログラムをコンピュータのメモリあるいは記憶装置に格納して、実行することによって、本発明の目的を達成することができる。
【００８３】
なお、記録媒体としては半導体媒体（例えば、ＲＯＭ、不揮発性メモリカード等）、光媒体（例えば、ＤＶＤ、ＭＯ、ＭＤ、ＣＤ−Ｒ等）、磁気媒体（例えば、磁気テープ、フレキシブルディスク等）のいずれであってもよい。
【００８４】
また、ロードしたプログラムの指示に基づき、オペレーティングシステムやアプリケーションプログラム等が実際の処理の一部または全部を行い、その処理によって上述した実施形態の機能が実現される場合も含まれる。
【００８５】
また、上述したプログラムをサーバコンピュータの磁気ディスク等の記憶装置に格納しておき、ネットワークで接続された利用者のコンピュータからダウンロードして頒布する場合、また、サーバコンピュータから配信して頒布する場合、このサーバコンピュータの記憶装置も本発明の記録媒体に含まれる。
このように、本発明の機能をプログラムして、記録媒体に記録し頒布することによって、コスト、可搬性、汎用性を向上させることができる。
【図面の簡単な説明】
【００８６】
【図１】本発明の実施形態に係るオフセット処理装置の機能構成を示すブロック図である。
【図２】曲面領域分割処理部の処理動作を説明するフローチャートである。
【図３】反転区間における等パラメータ線に対する（Ａ）近似オフセット曲線および（Ｂ）ルールド曲面の生成例である。
【図４】オフセット曲線とルールド曲面の干渉計算の例である。（Ａ）右側のオフセット曲線と左側のルールド曲面（Ｂ）左側のオフセット曲線と右側のルールド曲面
【図５】干渉点および反転区間の端点の移動方向を示す例である。
【図６】オフセット曲線を求める処理を説明するフローチャートである。
【図７】反転区間の検出処理を説明するフローチャートである。
【図８】反転区間とみなされた点のみからなる点列の例である。
【図９】通常領域オフセット処理部の処理動作を説明するフローチャートである。
【図１０】２つの通常領域を囲む４本の曲線に対して求めた近似オフセット曲線の例である。（Ａ）左側の通常領域の近似オフセット曲線（Ｂ）右側の通常領域の近似オフセット曲線
【図１１】２つの通常領域に対応して２つの領域に分けられた近似オフセット曲面を求める例である。（Ａ）干渉線を求めるためのルールド曲面（Ｂ）不要な領域を除去した後の近似オフセット曲面
【図１２】ねじれ領域オフセット処理部の処理動作を説明するフローチャートである。
【図１３】生成された３本の近似オフセット曲線の例である。（Ａ）ねじれ領域と１本の近似オフセット曲線（Ｂ）残り２本の近似オフセット曲線(太線)
【図１４】ねじれ領域を２つの領域に分割する処理を説明する例である。（Ａ）近似オフセット曲線のＢｅｚｉｅｒ曲線セグメントの各端点に対応した等パラメータ線上の点（Ｂ）近似オフセット曲線どうしの干渉点に対応した等パラメータ線上の点、および、ねじれ領域を２つに分割する等パラメータ線
【図１５】図２０を元曲面としたオフセット曲面の生成例である。（Ａ）ワイヤーフレーム表示（Ｂ）シェーディング表示（Ｃ）通常領域の近似オフセット面(左側)（Ｄ）ねじれ領域の近似オフセット面（Ｅ）通常領域の近似オフセット面(右側)
【図１６】反転と自己干渉の例である。（Ａ）元曲面（Ｂ）オフセット曲面（Ｃ）反転（Ｄ）自己干渉
【図１７】大域自己干渉の例である。（Ａ）元曲面（Ｂ）オフセット曲面
【図１８】反転領域の説明図である。
【図１９】等パラメータ線と反転領域との関係を示す図である。（Ａ）パターン１１（Ｂ）パターン１２
【図２０】パターン１１の例である。（Ａ）元曲面（Ｂ）オフセット曲面
【図２１】反転区間を含んだ境界曲線のオフセット曲線の例である。（Ａ）前方図（Ｂ）側方図（Ｃ）上方図
【符号の説明】
【００８７】
１…入力処理部、２…曲面領域分割処理部、３…通常領域オフセット処理部、４…ねじれ領域オフセット処理部、５…出力処理部。
【図１】
2006091950.tif 000007
【図２】
2006091950.tif 000008
【図３】
2006091950.tif 000009
【図４】
2006091950.tif 000010
【図５】
2006091950.tif 000011
【図６】
2006091950.tif 000012
【図７】
2006091950.tif 000013
【図８】
2006091950.tif 000014
【図９】
2006091950.tif 000015
【図１０】
2006091950.tif 000016
【図１１】
2006091950.tif 000017
【図１２】
2006091950.tif 000018
【図１３】
2006091950.tif 000019
【図１４】
2006091950.tif 000020
【図１５】
2006091950.tif 000021
【図１６】
2006091950.tif 000022
【図１７】
2006091950.tif 000023
【図１８】
2006091950.tif 000024
【図１９】
2006091950.tif 000025
【図２０】
2006091950.tif 000026
【図２１】
2006091950.tif 000027