(57)【特許請求の範囲】
【請求項１】
３次元モデル表面の凹形状を含むＮ辺形領域にあてはめる曲面を生成する曲面生成装置であって、
上記Ｎ辺形領域に基づいて局所座標系を設定し、生成する曲面の範囲を規定する境界平面を作成する平面生成部と、
上記Ｎ辺形領域の境界稜線上の複数の点から上記境界平面へ延びる横断線分を生成する線分生成部と、
下記の事項(G1)及び(G2)の何れに該当するかを判定する判定部と、
上記判定部で上記事項(G1)又は(G2)に該当すると判断された場合に、事項(G1)又は(G2)に関連する境界稜線に属する横断線分を削除し、当該境界稜線についてオフセット曲線を設定し、このオフセット曲線と当該境界稜線とで新たな横断線分を再生成する線分再構成部と、
上記横断線分とその境界平面との交点からＮ辺形領域にあてはめる曲面の境界曲線を生成する境界曲線生成部と、
上記境界曲線と上記横断線分上の各点から上記Ｎ辺形領域にあてはめる曲面を生成する曲面生成部と、
を備えたことを特徴とする、曲面生成装置。
Ｇ１：前記境界稜線が、前記Ｎ辺形領域内側へ入り込む角部を構成する縁である。
Ｇ２：前記線分生成部に基づいて生成された境界稜線上の点から延びた横断線分同士が交差している。
【請求項２】
前記境界曲線生成部が、前記事項(G1),(G2)に関連しない境界稜線に属する横断線分に基づいて前記境界曲線を生成することを特徴とする、請求項１に記載の曲面生成装置。
【請求項３】
３次元モデル表面の凹形状を含むＮ辺形領域にあてはめる曲面を生成する曲面生成プログラムであって、
コンピュータを、
上記Ｎ辺形領域に基づいて局所座標系を設定し、生成する曲面の範囲を規定する境界平面を作成する平面生成部、
上記Ｎ辺形領域の境界稜線上の複数の点から上記境界平面へ延びる横断線分を生成する線分生成部、
下記の事項(G1)及び(G2)の何れに該当するかを判定する判定部、
上記判定部で上記事項(G1)又は(G2)に該当すると判断された場合に、事項(G1)又は(G2)に関連する境界稜線に属する横断線分を削除し、当該境界稜線についてオフセット曲線を設定し、このオフセット曲線と当該境界稜線とで新たな横断線分を再生成する線分再構成部、
上記横断線分とその境界平面との交点からＮ辺形領域にあてはめる曲面の境界曲線を生成する境界曲線生成部、
上記境界曲線と上記横断線分上の各点から上記Ｎ辺形領域にあてはめる曲面を生成する曲面生成部、
として機能させることを特徴とする、曲面生成プログラム。
Ｇ１：前記境界稜線が、前記Ｎ辺形領域内側へ入り込む角部を構成する縁である。
Ｇ２：前記線分生成部に基づいて生成された境界稜線上の点から延びた横断線分同士が交差している。
【請求項４】
前記境界曲線生成部が、前記事項(G1),(G2)に関連しない境界稜線に属する横断線分に基づいて前記境界曲線を生成することを特徴とする、請求項３に記載の曲面生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元モデル表面のＮ辺形領域に曲面をあてはめる曲面内挿技術に係り、特に凹形状を含むＮ辺形領域にフィットする曲面を生成する曲面生成装置及び曲面生成プログラムに関する。
【背景技術】
【０００２】
３次元CADシステムにおける形状変形操作では、トリム曲面が生成されることが多い。曲面をトリミングしている境界稜線は、曲面上に許容誤差範囲内で乗っている曲線である。従って、曲面制御点とトリミングしている境界稜線とを別々に変形すると、曲面と境界稜線との整合性が失われる。そのため、曲面制御点を直接移動したり、境界稜線の形状を変形したりする場合には、トリム曲面としての整合性を維持しながら変形する必要があり、形状変形上の大きな制約となっている。
【０００３】
ダイレクトモデリングを用いて稜線を直接変形したい場合、変形後の稜線が許容誤差範囲内で乗るような制約条件で、曲面の制御点を移動しなければならない。
【０００４】
一般にトリム曲面上に乗る稜線列で構成される閉領域は、Ｎ辺形領域である。Ｎ辺形領域の境界稜線を局所変形した後で、変形後の稜線が許容誤差以内で乗るように曲面制御点を移動することは、容易ではない。そのため、局所変形後に、幾何学的な整合性を維持できるような自由曲面を新しく当てはめる手法が有効である。
【０００５】
一般に、標準規格部品の形状モデルは、図１８に示すように、切り欠き形状を含んでいる場合が多い。図１８（ａ）は標準規格部品の３次元モデルである。図１８（ｂ）は、図１８（ａ）の一つの面Ｓ１を取り出して、制御点Ｃ１０を表示したものである。この図１８（ｂ）から、面Ｓ１は元の曲面を切り欠いた切欠形状として表現されている。
【０００６】
Ｎ辺形領域に対して、曲面を当てはめる手法は、曲面内挿法ベースとN-side Filling法ベースとに大別される（非特許文献１）。曲面内挿法ベースは、閉領域の境界と自由曲面の境界曲線が一致するような自由曲面を生成する手法である。N-side Filling 法ベースは、境界曲線で囲まれる閉領域を包含する４辺形のトリム曲面を生成する手法である。
【０００７】
先ず、曲面内挿法ベースの手法について記述する。非特許文献２には、角度許容誤差εを導入し、隣接するパッチ間の共有境界稜線上の任意の点における法線ベクトルの角度がε未満となる曲面当てはめ手法が提案されている。また、非特許文献３には、非特許文献２の「曲面当てはめ手法」を有理曲線でも扱えるように拡張した手法が提案されている。また、非特許文献４は、NURBSの持つ位相についての制約を緩和し、幾何学的に重要でない制御点を間引いたT-splineを提案している。T-splineはＴ字接続を許すため制御点を大幅に削減できる。
【０００８】
これらの非特許文献２〜４の提案手法は、非特許文献５の細分割手法に基づいてＮ辺形領域の内部に中心点と分割曲線を発生させて、Ｎ辺形領域をＮ枚の４辺形面に分割し、各４辺形領域に曲面当てはめをする手法である。例えば、図１９に示すＮ辺形領域Ｒ５について説明する。Ｎ辺形領域Ｒ５は、その外周を画する５本の凸状の稜線Ｌ１〜Ｌ５と、切欠形状を画する１本の稜線Ｌ６とから構成されている。上記手法（非特許文献２〜４）に基づいて、図１９のＮ辺形領域Ｒ５に曲面を当てはめようとすると、閉領域を表す境界稜線Ｌ６の形状によっては歪んだ形状の内部曲線Ｌ´が生成される。その結果、歪んだ曲面が生成される。また、穴を含む場合は対応できないという問題がある。
【０００９】
非特許文献６では、Ｎ辺形領域を星型のパラメータｆで制御可能なＮ辺形パッチと４辺形パッチに分割し、任意のＮ辺形領域へ曲面当てはめ手法が提案されている。
【００１０】
非特許文献６の手法は、星型のＮ辺形領域を表す境界稜線を入力として、領域の内部に複数のパッチを当てはめる手法である。図２０に示すように、４辺形で構成されるｎ枚の規則的なパッチXnを、星型のＮ辺形パッチ２０１の周りに生成する。この４辺形で構成されるパッチXnは、隣接するパッチと共通の領域Ｌを保持するため、４辺形パッチ間の連続性は保たれる。
【００１１】
非特許文献６の手法は、パッチ間の境界をB-spline（以下、Ｂ−スプラインと表す場合もある。）に一致させることで、パッチ間の連続性を考慮した曲面当てはめが可能である。また、領域の内部に生成する星型のＮ辺形パッチ２０１の大きさはパラメータｆで制御でき、任意のＮ辺形形状に対して曲面当てはめが可能となる。図２１は、同一の境界稜線で表す領域に対して、ｆの値を変化させることで形状を制御した図である。図２１（ｂ）のようにｆの値を小さくすると内部のＮ辺形パッチ２０１は小さくなり、図２１（ｃ）に示すようにｆの値を大きくすると内部のＮ辺形パッチ２０１は大きくなる。つまり、直感的な形状操作が可能である。
【００１２】
次に、トリム曲面ベースの手法について記述する。特許文献１及び非特許文献７には、Ｎ辺形領域を覆う１枚の双３次B-spline曲面をＮ辺形領域に当てはめる手法が提案されている。
【００１３】
特許文献１及び非特許文献７の手法は、Ｎ辺形領域を覆うようなB-spline曲面と、接平面に基づいたサンプル点を利用して、曲面フィッティング手法（非特許文献８）によって曲面をＮ辺形領域に当てはめる。具体的には、図２２（ａ）のように、境界稜線Ｂ１１〜Ｂ１４で囲まれたＮ辺形領域２１０への曲面当てはめは、以下の手順Step 1− Step 5による。
【００１４】
（１）Step 1について
図２２（ａ）に示すように、境界稜線Ｂ１１〜Ｂ１４を囲む４つの境界平面２２１，２２２，２２３，２２４を求める。Ｎ辺形領域２１０の境界稜線列の中心と境界稜線列から算出した単位法線ベクトルｎを用いて平面を生成する。そして、その平面上に境界稜線列を射影し、ＸＹ平面上にバウンディングボックス２３０を得る。単位法線ベクトルｎをＺ軸とし、バウンディングボックス２３０からＺ軸に平行な４つの境界平面２２１，２２２，２２３，２２４を得る。
【００１５】
（２）Step 2について
境界稜線Ｂ１１〜Ｂ１４上のサンプル点とその点における境界横断導関数（非特許文献９）から、境界を横断する方向に直線を生成し、直線と境界平面２２１，２２２，２２３，２２４の交点２４１，２４２，２４３，２４４を算出する。図２２（ｂ）に示すように、境界稜線Ｂ１１〜Ｂ１４上のサンプル点と、直線と境界平面の交点２４１，２４２，２４３，２４４を両端点とする線分を横断線分２５１，２５２，２５３，２５４とする。
【００１６】
（３）Step 3について
図２２（ｃ）に示すように、各境界平面２２１，２２２，２２３，２２４に乗る複数の横断線分の端点をB-spline曲線で補間し（非特許文献８）、Ｎ辺形領域２１０を囲む４辺形領域２１０Ａを生成する。生成した４辺形領域２１０Ａは、当てはめるB-spline曲面の境界曲線２６１，２６２，２６３，２６４となる。
【００１７】
（４）Step 4について
図２２（ｄ）に示すように、横断線分２５１，２５２，２５３，２５４上に複数の点２７１，２７２，２７３，２７４（以下、点群と呼ぶ。）を発生する。発生した点群は、境界稜線上のサンプル点における接平面上に乗る。
【００１８】
（５）Step 5について
Step 3で生成したB-spline曲面の境界曲線２６１，２６２，２６３，２６４と、Step 4で生成した点群を利用し、最小二乗法によりB-spline曲面の内部制御点を導出する（非特許文献８）。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】特開２００３−３３０９７９号公報
【非特許文献】
【００２０】
【非特許文献１】Y. Muraki, K. Konno, Y. Tokuyama: “A STUDY OF SUBDIVISION METHOD TO THREE AND FIVE SIDED FACES BASED ON REGULAR POLYGON”, Proc. of IWAIT2009, (2009)
【非特許文献２】L. Piegl, W. Tiller: “Fillingn-sided regions with NURBS patches”, The VisualComputer, Vol.2, No.15, pp.77-89, (1999)
【非特許文献３】Yi-Jun. Yang, Jun-Hai. Yong, Hui. Zhang, Jean-Claude. Paul, Jia-Guang. Sun: “A rational extensionof Piegl’s method for filling n-sided holes”, ComputerAided Design, Vol.38, No.11, pp.1166-1178, (2006)
【非特許文献４】T. W. Sederberg, D. L. Cardon, G. T. Finnigan, N. S. North, J. Zheng, and T. Lyche: “T-spline Simplification andLocal Refinement”, SIGGRAPH 2004, Vol.23, No.3, pp.276-283, (2004)
【非特許文献５】E. Catmull, J. Clark “Recursively generatedB-spline surfaces on arbitrary topologicalmeshes”, ComputerAided Design, Vol.10, No.6, pp.350-355, (1978)
【非特許文献６】N. Pla-Garcia, M. Vigo-Anglada, J. Cotrina-Navau: “N-sided patches with B-spline boundaries”, Computers& Graphics, Vol.30, No.6, pp.959-970, (2006)
【非特許文献７】Y. Tokuyama, K. Konno: “Filling N-sided Region with a B-spline Surface”,Information ProcessingSociety ofJapan, Vol.43, No.10,pp.3209-3218, (2002)
【非特許文献８】L. Piegl, W. Tiller: TheNURBS Book, Springer-Verlag, (1995)
【非特許文献９】K. Konno, Y. Tokuyama, H. Chiyokura: “AG1 connectionaround complicatedcurve meshesusing C1 NURBS Boundary Gregory Patches”, Computer AidedDesign, Vol.33, No.4, pp.293-306, (2001)
【非特許文献１０】K. Ueda: “Meannormal vectorto a surface boundedby Beziercurves”, ComputerAided GeometricDesign, Vol.13, No.5, pp.441-451, (1996)
【非特許文献１１】G. Farin: Curvesand Surfacesfor ComputerAided GeometricDesign A Practical Guide, Academic Press, (1996)
【発明の概要】
【発明が解決しようとする課題】
【００２１】
非特許文献６の手法は、星型多角形のような形状には曲面当てはめが可能である。しかし、図２３に示すＬ字型のような凹形状を有するＮ辺形領域３１０に、非特許文献６の手法を適用することは難しい。ここで、Ｎ辺形領域３１０は、外周を画する境界稜線の内、４本の稜線Ｌ１１〜Ｌ１４がＮ辺形領域外側へ膨らむ凸稜線であり、２本の稜線Ｌ１５，Ｌ１６がＮ辺形領域内側方向へ入り込む角部４００を構成する。以下、この角部を凹頂点４００と呼ぶ。これらの稜線Ｌ１５，Ｌ１６によって切欠部分が形成されている。
また、非特許文献６の手法を、穴を含む形状に適用すると、内部にＮ辺形パッチを生成できず、その結果、曲面が生成できないという問題がある。
【００２２】
非特許文献７の手法は、図２３に示す凹形状を有するＮ辺形領域３１０に適用すると、図２４に示すように生成される曲面３５０は歪んでしまうという問題がある。また、穴を含む形状に対する処理方法は，文献７には記載されていない。
【００２３】
生成される曲面の形状が歪む原因は、以下の２つ（Ｉ，ＩＩ）であると考えられる。
（Ｉ）横断線分（図２２の符号２５１〜２５４参照）から発生した点群（図２２の符号２７１〜２７４参照）が、凹頂点近傍では領域の内側に生成されること。
（ＩＩ）B-spline曲面の境界稜線の生成方法が限定的であり、凹形状を含んだＮ辺形領域に対応されていないこと。
【００２４】
上記（Ｉ）に関して、図２５（ａ）で符号Ｃ１、Ｃ２の円内に示すように、凹頂点４００につながる２本の稜線Ｌ１５、Ｌ１６上のサンプル点から延びた横断線分３５１，３５２はＮ辺形領域３１０の内側へ延びている。つまり、境界横断導関数がねじれている。これにより、横断線分から発生した点群もＮ辺形領域３１０の内側に生成される。
【００２５】
上記（ＩＩ）に関して、図２５（ｂ）、（ｃ）で符号Ｃ３，Ｃ４の円内に示すように、凹形状の境界稜線Ｌ１７，Ｌ１８から発生する横断線分３７０，３８０は、互いに交差やねじれの関係になることがある。そのため、横断線分の端点から得られる点列から境界曲線を生成すると、境界曲線が歪んでしまう。
【００２６】
以上の原因（Ｉ，ＩＩ）のために、非特許文献７の手法は凸状の境界稜線だけから成るＮ辺形領域に対して歪みのないB-spline曲面を生成できるが、図２５に示すような凹形状を含んだＮ辺形領域３１１〜３１２に対しては、歪んだ曲面が生成されることになる。
【００２７】
次に、形状と空間の姿勢について考慮すると、特許文献１及び非特許文献７の手法では、４つの境界平面が境界曲線列の３次元空間上の姿勢に依存しているため、３次元空間上の３次元モデルの姿勢によって得られる結果が変わる。
【００２８】
本発明は以上の点に鑑みて創作されたもので、凹形状を含むＮ辺形領域にあてはめる曲面を生成する、曲面生成装置及び曲面生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２９】
上記目的を達成するため、本発明の第１の構成は、３次元モデル表面の凹形状を含むＮ辺形領域にあてはめる曲面を生成する曲面生成装置であって、Ｎ辺形領域に基づいて局所座標系を設定し、生成する曲面の範囲を規定する境界平面を作成する平面生成部と、Ｎ辺形領域の境界稜線上の複数の点から境界平面へ延びる横断線分を生成する線分生成部と、下記の事項(G1)及び(G2)の何れに該当するかを判定する判定部と、判定部で事項(G1)又は(G2)に該当すると判断された場合に、事項(G1)又は(G2)に関連する境界稜線に属する横断線分を削除し、当該境界稜線についてオフセット曲線を設定し、このオフセット曲線と当該境界稜線とで新たな横断線分を再生成する線分再構成部と、横断線分とその境界平面との交点からＮ辺形領域にあてはめる曲面の境界曲線を生成する境界曲線生成部と、曲面の境界曲線と横断線分上の各点からＮ辺形領域にあてはめる曲面を生成する曲面生成部と、を備えたことを特徴としている。
Ｇ１：前記境界稜線が、前記Ｎ辺形領域内側へ入り込む角部を構成する縁である。
Ｇ２：前記線分生成部に基づいて生成された境界稜線上の点から延びた横断線分同士が交差している。
なお、本明細書では切欠部分,穴、また後述する凹頂点、凹稜線を１つでも含む形状を総称して凹形状と定義する。
【００３０】
本発明の曲面生成装置において、好ましくは、境界曲線生成部が、前記事項(G1),(G2)に関連しない境界稜線に属する横断線分に基づいて前記境界曲線を生成する。
【００３１】
上記目的を達成するために、本発明の第２の構成は、３次元モデル表面の凹形状を含むＮ辺形領域にあてはめる曲面を生成する曲面生成プログラムであって、コンピュータを、Ｎ辺形領域に基づいて局所座標系を設定し、生成する曲面の範囲を規定する境界平面を作成する平面生成部、Ｎ辺形領域の境界稜線上の複数の点から境界平面へ延びる横断線分を生成する線分生成部、下記の事項(G1)及び(G2)の何れに該当するかを判定する判定部、判定部で事項(G1)又は(G2)に該当すると判断された場合に、事項(G1)又は(G2)に関連する境界稜線に属する横断線分を削除し、当該境界稜線についてオフセット曲線を設定し、このオフセット曲線と当該境界稜線とで新たな横断線分を再生成する線分再構成部、横断線分とその境界平面との交点からＮ辺形領域にあてはめる曲面の境界曲線を生成する境界曲線生成部、境界曲線と上記横断線分上の各点から上記Ｎ辺形領域にあてはめる曲面を生成する曲面生成部、として機能させることを特徴としている。
Ｇ１：前記境界稜線が、前記Ｎ辺形領域内側へ入り込む角部を構成する縁である。
Ｇ２：前記線分生成部に基づいて生成された境界稜線上の点から延びた横断線分同士が交差している。
【００３２】
本発明の曲面生成プログラムにおいて、好ましくは、境界曲線生成部が、前記事項(G1),(G2)に関連しない境界稜線に属する横断線分に基づいて境界曲線を生成する。
【発明の効果】
【００３３】
本発明によれば、凹形状を有するＮ辺形領域の曲面生成に当たり、凹頂点近傍の横断線分を再生する。これにより、Ｎ辺形領域に適切にフィットして内挿可能な曲面を生成することができる。
【００３４】
さらに、従来、凹形状はトリム曲面で表現されており，凹形状を直接変形するようなダイレクトモデリングでは境界稜線列と元の曲面との幾何学的整合性を崩さないような限定的な制約条件の下で扱われてきたが、本発明のトリム曲面への曲線メッシュ方法によるダイレクトモデリング手法を使うとトリム曲面を容易に再構成することが可能となるため、従来、モデリング作業の困難性が高く制約が多かった境界稜線の形状変更の作業等の自由度が本発明により拡大し、顕著な効果が得られる。
【図面の簡単な説明】
【００３５】
【図１】本発明の実施形態に係る曲面生成装置１のブロック図である。
【図２】本発明の実施形態に係る平面生成分の機能を説明するための図である。
【図３】本発明の実施形態に係る線分生成分の機能を説明するための図である。
【図４】本発明の実施形態に係る線分生成分の機能を説明するための図である。
【図５】本発明の実施形態に係る判定部の機能を説明するための図である。
【図６】本発明の実施形態に係る判定部の機能を説明するための図である。
【図７】本発明の実施形態に係る線分再構成部の機能を説明するための図である。
【図８】凹状部を有するＮ辺形領域に対して従来の手法で横断線分を生成した状態を示す図である。
【図９】凹状部を有するＮ辺形領域に対して本発明の手法で横断線分を生成した状態を示す図である。
【図１０】本発明の実施形態に係る線分再構成部の機能を説明するための図である。
【図１１】本発明の実施形態に係る線分再構成部の機能を説明するための図である。
【図１２】本発明の実施形態に係る線分再構成部の機能を説明するための図である。
【図１３】本発明の実施形態に係る線分再構成部の機能を説明するための図である。
【図１４】本発明の実施形態に係る線分再構成部の機能を説明するための図である。
【図１５】本発明の実施形態に係る境界曲線生成部の機能を説明するための図である。
【図１６】本発明の実施形態に係る境界曲線生成部の機能を説明するための図である。
【図１７】本発明の実施形態に曲面生成装置のフローチャートである。
【図１８】一般の形状モデルを示す図である。
【図１９】凹状部を有するＮ辺形領域を示す図である。
【図２０】従来の曲面内挿手法を説明するための図である。
【図２１】従来の曲面内挿手法を説明するための図である。
【図２２】従来の曲面内挿手法を説明するための図である。
【図２３】従来の曲面内挿手法の問題を説明するための図である。
【図２４】従来の曲面内挿手法の問題を説明するための図である。
【図２５】従来の曲面内挿手法の問題を説明するための図である。
【発明を実施するための形態】
【００３６】
以下、本発明の実施形態について、必要箇所では図面を参照しつつ詳細に説明する。
【００３７】
図１は本発明の実施形態に係る曲面生成装置１のブロック図である。
曲面生成装置１は、平面生成部１０と線分生成部２０と判定部３０と線分再構成部４０と境界曲線生成部５０と曲面生成部６０とを備えている。
以下、構成別に説明する。
【００３８】
平面生成部１０は、図２に示すように、曲面の範囲を規定する４つの境界平面１１１〜１１４を作成する。ここで、曲面とは、３次元モデル表面のＮ辺形領域ＲにあてはめるB-spline曲面である。
本実施形態では、平面生成部１０は、形状データ等の３次元モデルが存在する３次元空間上の姿勢に依存しない４つの境界平面１１１〜１１４を生成する。本実施形態の平面生成部１０は、先ず局所座標系（ｄｘ軸、ｄｙ軸、ｄｚ軸）を設定し、その後に４つの境界平面１１１〜１１４を生成する。
【００３９】
局所座標系の設定は以下の手順（A1）〜（A5）による。
（A1）Ｎ辺形領域Ｒの境界稜線Ｂ１〜Ｂ６の列の中心と境界稜線列から算出した単位法線ベクトルｎを用いて、平均平面１１０を生成する（非特許文献１０）。平均平面１１０はｄｘ軸とｄｙ軸とにそれぞれ平行な平面である。
（A2）境界稜線列を平均平面１１０に射影して、射影境界稜線列を生成する。
（A3）射影境界稜線列から一番長い稜線を選択する。式（１）に示すように、選択した稜線の始点p0と終点p1を利用し、Ｘ軸（図２中のｄｘ軸）を決定する。
【数１】
0005458440.tif 000002
（A4）下記式（２）に示すように、ベクトルＸとｎの外積ベクトルを計算し、Ｙ軸（図２中のｄｙ軸）を決定する。これにより、平均平面上に局所座標系のＸＹ座標軸を設定する。
【数２】
0005458440.tif 000003
（A5）設定したＸＹ座標軸と、単位平均法線ベクトルｎをＺ軸（図２中のｄｚ軸）として、ＸＹＺ軸からなる局所座標系を設定する。
【００４０】
本実施形態の平面生成部１０は、局所座標系に基づいて、射影稜線列のバウンディングボックスＢ′を得る。図２では、バウンディングボックスＢ′は、４つの線１１０ａ，１１０ｂ，１１０ｃ，１１０ｄで囲われている。バウンディングボックスＢ′とｄｚ軸を利用して４つの境界平面１１１〜１１４を求める。具体的には、バウンディングボックスＢ′を構成する各線１１０ａ，１１０ｂ，１１０ｃ，１１０ｄから、ｄｚ軸方向に線をスイープさせることで、各境界平面１１１〜１１４が構成される。
得られた４つの境界平面１１１〜１１４は、境界曲線列の３次元空間上の姿勢と独立したものとなる。すなわち、境界平面１１１〜１１４の求め方はアフィン不変となる。
【００４１】
次に線分生成部２０について説明する。
線分生成部２０は、図３に示すように、Ｎ辺形領域Ｒの境界稜線Ｂ１〜Ｂ６上の複数の点から上記境界平面１１１〜１１４へ延びる横断線分１１５を生成する。具体的には、線分生成部２０は、従来技術と同様に、各境界稜線Ｂ１〜Ｂ６上に複数のサンプル点ＳＰを設定し、各サンプル点ＳＰにおける境界横断導関数（非特許文献９）から、境界、つまり境界稜線Ｂ１〜Ｂ６を横断する方向に直線を生成し、直線と境界平面１１１〜１１４の交点１１１Ｂ〜１１４Ｂを算出する。図３に示すように、境界稜線上のサンプル点ＳＰと、直線と境界平面の交点１１１Ｂ〜１１４Ｂを両端点とする線分を横断線分１１５とする。
また、線分生成部２０は、図４に示すように、各横断線分１１５を例えば４分割した点群をサンプル点ＳＰ′として生成する。このサンプル点ＳＰ′は曲面当てはめに利用される。
【００４２】
次に、判定部３０について説明する。
判定部３０は、以下の事項Ｇ１及びＧ２の何れに該当するかを判定する。
Ｇ１：境界稜線Ｂ１〜Ｂ６がＮ辺形領域Ｒの内側へ入り込む角部を構成する縁である。
Ｇ２：線分生成部２０に基づいて生成された境界稜線Ｂ１〜Ｂ６のサンプル点ＳＰから延びた直線、つまり横断線分１１５同士が交差している。
【００４３】
本実施形態の判定部３０は、判定事項Ｇ１を次のようにして判断する。
例えば、図５（ａ）に示すように、注目する頂点をＰとする。
頂点Ｐを共有する２本の稜線Ｂ５、Ｂ５における頂点Ｐの単位接線ベクトルを、図５（ｂ）に示すように、v1,v2とする。v1,v2の外積ベクトルＶを式（３）のように求める。式（４）に示すように、ベクトルＶとＮ辺形領域Ｒの境界稜線列の平均法線ベクトルｎとの内積を計算し、内積値が正の場合は凸頂点とし、それ以外ならば凹頂点とする。
【数３】
0005458440.tif 000004
【数４】
0005458440.tif 000005
このように、境界稜線Ｂ１〜Ｂ６中に一つでも凹頂点がある場合、その境界稜線をイレギュラーラインと判定する。図２に示すＮ辺形領域に関しては、境界稜線Ｂ５、Ｂ６がイレギュラーラインと判断される。
【００４４】
また、本実施形態の判定部３０は、判定事項Ｇ２を次のようにして判断する。
例えば、境界平面１１１〜１１４を求めた局所座標軸で定義されるＸＹ平面、つまり図２の平面１１０に、全ての境界稜線Ｂ１〜Ｂ６と横断線分１１５を射影する。次に、全ての横断線分同士の干渉点を得る。
ここで、図６（Ａ）に示すＮ辺形領域Ｒ１を例に説明する。Ｎ辺形領域Ｒ１は、内側へ入り込むように湾曲した凹形状の境界稜線Ｂ７を備えている。このような凹形状の境界稜線Ｂ７に、サンプル点ＳＰを設定し、横断線分１１５を生成した状態が、図６（ｂ）である。この図６（ｂ）に矢印αで示すように、Ｎ辺形領域Ｒ１の凹形状の境界稜線Ｂ７から生成される複数の横断線分１１５上には、干渉点Ｋが１点以上存在することになる。判定部３０は、このような干渉点Ｋを有する横断線分１１５が属する境界稜線Ｂ７も、イレギュラーラインと判定する。
【００４５】
次に、線分再構成部４０は、前述の判定部３０でイレギュラーラインと判定した境界稜線の横断線分を再生成する。具体的には、上記の線分生成部２０で生成されイレギュラーラインと判定された境界稜線に属する全ての横断線分を削除し、後述の境界横断導関数に基づいて横断線分を再生成する。
図２に示すＮ辺形領域Ｒに関しては、境界稜線Ｂ５、Ｂ６がイレギュラーラインとみなされるため、これらの境界稜線Ｂ５、Ｂ６に属する全ての横断線分１１５、詳細には図３中のβ１〜β４の各横断線分１１５が全て削除され、線分再構成部４０によって横断線分が再生成される。
【００４６】
例えば、図７に示すように、境界稜線上のそれぞれのサンプル点における接平面の法線ベクトルａと接線ベクトルｂの外積を式（５）のように求める。得られるベクトルｃを横断線分の方向にする。最後に、横断線分の方向ベクトルと４つの境界平面との交点を求め、最も近い交点とサンプル点で新たな横断線分を生成する。
【数５】
0005458440.tif 000006
以上の操作を図８に示す凹形状を有するＮ辺形領域Ｒ，Ｒ１，Ｒ２に対して適用すると、各Ｎ辺形領域Ｒ，Ｒ１，Ｒ２のイレギュラーラインに属する横断線分が図９のように再生成される。
【００４７】
次に、本実施形態の線分再構成部４０における横断線分の再構成について詳述する。
図１０に示すように、境界稜線Ｂ５、Ｂ６の端点の一方が凹頂点４００の場合、Tangent Ribbon（非特許文献１１）はねじれた状態、つまり非特許文献９の境界横断導関数はある位置から逆向きに導出される。図１０のＮ辺形領域Ｒの場合、図１０で符号β２、β４で示すように、凹頂点４００近傍部分の境界横断導関数a0がＮ辺形領域Ｒの内部に向かって生成されている。そこで、凹頂点４００を含む境界稜線Ｂ５、Ｂ６上の任意のサンプル点ＳＰから、境界横断導関数を領域の外部へ向かって生成するために、本実施形態では基礎パッチ法（非特許文献９）を用いる。
【００４８】
図１１は、接続する２枚の曲面Ｓ1、Ｓ2を表している。
境界稜線上の点から得られる境界横断導関数は、式（６）を満たす必要がある。
【数６】
0005458440.tif 000007
ただし、ｋ（ｖ）、ｈ（ｖ）はｖのスカラー関数、Ｓ２ｕは曲面Ｓ２におけるｕ方向の微分ベクトル、Ｓ１ｕは曲面Ｓ１におけるｕ方向の微分ベクトル、Ｓ１ｖは曲面Ｓ１におけるｖ方向の微分ベクトルである。
式（６）にｖ＝０、ｖ＝１をそれぞれ代入すると式（７）が得られる。
【数７】
0005458440.tif 000008
ただし、ｋ０、ｋ１、ｈ０、ｈ１は実数である。本手法では、ｈ０＝０、ｈ１＝０と仮定すると式（８）が得られる。
【数８】
0005458440.tif 000009
ここで、式（７）を満たすためにｖに関するスカラー関数ｋ（ｖ）を式（９）に示すように１次式と仮定する。
【数９】
0005458440.tif 000010
式（６）、式（９）より次式（１０）が得られる。
【数１０】
0005458440.tif 000011
式（１０）は、図１１に表す曲面制御点間のベクトルを用い、次式（１１）のように書き換えることができる。ただし、Ｂ３ｉ（ｖ）は、Bernstein基底関数である。
【数１１】
0005458440.tif 000012
式（１１）の右辺は４次式になるので、ａｉの部分の次数を２次に制限する。具体的には、ａ０、ａ２は境界から、ａ１は次式（１２）で求める。
【数１２】
0005458440.tif 000013
【００４９】
以上の式により、境界横断導関数Ｓ２ｕ（０，ｖ）は次式（１３）で表される。
【数１３】
0005458440.tif 000014
【００５０】
図１０のＮ辺形領域Ｒにおける凹頂点４００では、境界横断導関数が逆向きに生成されているため、Ｓ１ｕ（１、０）＝−ａと表される。
式（１３）にｖ＝０を代入すると、式（１４）が得られる。
【数１４】
0005458440.tif 000015
【００５１】
以上で求めた式より、境界稜線上の点の境界横断導関数を求める。境界稜線上の各点から得られた境界横断導関数Ｓ２ｕ（０，ｖ）を正規化し、同じ長さｔだけ伸ばした点群を用い、オフセット曲線を生成する。境界稜線上のパラメータｖにおける点をＣｖ（ｖ）とすると、オフセット曲線生成に用いる点Ｐ（ｖ）は、次式（１５）で表される。
【数１５】
0005458440.tif 000016
【００５２】
本実施形態の線分再構成部４０は、イレギュラーラインと判断された境界稜線、例えば、図２のＮ辺形領域Ｒの境界稜線Ｂ５、Ｂ６に対してそれぞれ、上記式（１５）に基づいて、図１２に示すように、境界稜線Ｂ５、Ｂ６からＮ辺形領域外側方向へ離れた位置に補助線、つまりオフセット曲線ＳＬ１、ＳＬ２を生成する。具体的には、式（１５）に基づいて再生成した横断線分の端点集合をB-spline曲線で近似し、オフセット曲線とする。
【００５３】
線分再構成部４０は、さらに、オフセット曲線ＳＬ１、ＳＬ２と対応する境界稜線Ｂ５、Ｂ６との間に、図１３に示すように、境界稜線Ｂ５、Ｂ６上のサンプル点からＮ辺形領域外側へ延びる直線を引く。これにより、横断線分１１５′が再生成される。
【００５４】
さらに、線分再構成部４０は、再生成した全ての横断線分１１５′を、例えば４分割した点群をサンプル点として生成する。このサンプル点は曲面当てはめに利用される。
【００５５】
ここで、Ｌ字型に切り欠いた形状、例えば凹頂点を有する形状に適用した場合、図１３に矢印β５で示すように、凹頂点４００近傍領域に再生成した横断線分１１５′同士の干渉が生じる。生成した横断線分１１５′同士が干渉すると、オフセット曲線が歪んでしまう。そこで、本実施形態の線分再構成部４０は、再生成した横断線分１１５′同士が干渉する場合、図１４（ａ）に矢印β６で示すように干渉していた横断線分１１５′だけを削除する。例えば、線分再構成部４０における、横断線分１１５′同士が干渉するかの判断手法は、前述したと同様に、ＸＹ平面１１０に各横断線分１１５′を投影して、干渉点Ｋが存在するかで判断する。
【００５６】
本実施形態の線分再構成部４０は、さらに、データの補充処理を行う。これは、例えば、図１４（ａ）に示すように干渉する横断線分を削除した場合、データ不足が生じるためである。線分再構成部５０は、データ不足が生じる凹頂点近傍において、図１４（ｂ）に示すように、オフセット曲線からの逆探索を行い、横断線分を再生成する。例えば、オフセット曲線上の曲率が最も高い点４０１と、凹頂点４００を端点と結ぶ横断線分１１５″を追加し、さらにその線分を例えば４等分する点をサンプル点として生成する。
【００５７】
このように、本実施形態の線分再構成部４０は、凹頂点近傍の境界稜線に対して、はじめに凹頂点を含む境界稜線上の点から境界横断導関数に基づき同じ長さだけ伸ばした線分を生成し、その後で、生成した線分の端点集合をB-spline曲線で近似することにより、オフセット曲線を生成する。つまり、オフセット曲線は、境界稜線における接平面に基づいて生成される。本手法では、オフセット曲線をTangent Ribbon（非特許文献１１）と考えて、横断線分を生成することによって、凹頂点近傍についても閉領域の外側に点群を発生できる。
【００５８】
次に、境界曲線生成部５０について説明する。
境界曲線生成部５０は、B-spline曲面の４本の境界曲線を生成する。境界曲線生成部５０は、凹形状を画する境界稜線に属する横断線分を利用しない。境界曲線生成部５０は、外側へ膨らむ線（以下、凸稜線と呼ぶ。）から得られる横断線分のみを利用して境界曲線を生成する。つまり、判定部３０でイレギュラーラインと判断された境界稜線に属する横断線分は、本実施形態では利用しない。これは、非特許文献７の手法が、凹頂点を含む稜線や凹稜線から生成する横断線分が互いに交差やねじれの関係になり、このような横断線分と境界平面の交差により得られる点列が波打ったり、ループしたりするため、境界曲線が歪む問題があるためである。
そこで、本実施形態では、凸稜線から得られる横断線分のみを利用することで、境界曲線の歪みを回避する。
【００５９】
Ｌ字型の凹形状を有するＮ辺形領域Ｒを例に説明する。図１５（ａ）は凹頂点近傍を除いた凸稜線から横断線分を求め、B-spline曲面の境界曲線１５１〜１５４を生成した結果である。
ここで、４本のB-spline曲線１５１〜１５４はそれぞれ独立した曲線であるため、各曲線１５１〜１５４の端部を、各境界平面同士が交差するコーナー部１６０で一致させて、閉じた領域を生成する必要がある。
【００６０】
本実施形態の境界曲線生成部は、図１５（ｂ）に示すように、境界曲線１５１〜１５４の端点をそれぞれ一致させるために、各境界曲線１５１〜１５４の端点を隣接する境界平面まで、端点の接線方向に延長する。例えば、境界平面上の点をＰ１、Ｐ２とすると、これらの点の平均をとった点Ｐ３を各境界曲線１５１〜１５４の端点とする。その後、横断線分における境界平面上の端点に、点Ｐ３を加えた点列を与えて、再フィッティングする。図１６は閉じた境界曲線を生成した結果を示す。凹頂点につながる稜線や凹稜線から生成する横断線分の端点を含まないようにすることで、境界曲線が自己干渉する問題を解決する。
【００６１】
次に、曲面生成部６０について説明する。
曲面生成部６０は、境界曲線生成部５０によって生成されたB-spline曲面の境界稜線１５１〜１５４と、線分生成部２０によって生成された横断線分上のサンプル点及び線分再構成部４０によって再生成された横断線分上のサンプル点を利用して、最小二乗法によりB-spline曲面の内部制御点を導出し、B-spline曲面を生成する。
【００６２】
以上の曲面生成装置１は例えばコンピュータから構成される。このコンピュータは、前もってインストールされたソフトウェアとしての曲面生成プログラムを実行することで、上記の手法、即ちB-spline曲面の生成を実現する。具体的には、コンピュータが曲面生成プログラムを実行することで、コンピュータが前述の平面生成部１０と、線分生成部２０と、判定部３０と、線分再構成部４０と、境界曲線生成部５０と、曲面生成部６０として機能する。なお、プログラムは、通信回線を介してダウンロードしたものや、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ、携帯型記憶装置などの記憶媒体に記憶されているものを利用する。
【００６３】
なお、複数のコンピュータをＬＡＮやインターネット、公衆回線網等を介して相互に接続して、平面生成部１０と、線分生成部２０と、判定部３０と、線分再構成部４０と、境界曲線生成部５０と、曲面生成部６０との動作を複数のパーソナルコンピュータによって分散処理させてもよい。コンピュータは従来公知の構成のものを使用することができ、ＲＡＭ，ＲＯＭ，ハードディスクなどの記憶装置と、キーボード，ポインティング・デバイスなどの操作装置と、操作装置等からの指示により記憶装置に格納されたデータやソフトウェアを処理する中央処理装置（ＣＰＵ）と、処理結果等を表示するディスプレイなどを備えている。このコンピュータは汎用の装置であっても、専用の装置として構成されたものであってもよい。
【００６４】
次に、本発明の実施形態に係る曲面生成装置１の動作について図１７を用いて説明する。
先ず、Ｎ辺形領域を指定する（ステップＳ１）。この指定はユーザーによって行われる。例えば、コンピュータがプログラムを実行させて、ディスプレイに対象とする３次元モデルを表示し、ユーザーがマウスなどを操作してＮ辺形領域を指定する。指定されたＮ辺形領域のデータはＲＡＭやハードディスクなどの格納部に保存される。
【００６５】
このように、Ｎ辺形領域の指定を契機に、コンピュータは曲面生成プログラムの処理を開始する。
先ず、平面生成部１０が、デフォルトのＸＹＺ座標系中に配置されているＮ辺形領域のデータに基づいて、局所座標系を設定する（ステップＳ２）。
【００６６】
平面生成部１０が境界平面を作成する（ステップＳ３）。具体的には平面生成部１０は、局所座標系のＸＹ平面に、Ｎ辺形領域の各境界稜線を投影させて、バウンディングボックス（射影曲線列に外接する境界箱）を作成する。例えば、バウンディングボックスはＸ，Ｙ軸に平行な四辺形である。そして、平面生成部１０はバウンディングボックスの各辺をＺ軸方向へスイープして４つの境界平面を生成する。
【００６７】
線分生成部２０はＮ辺形領域の境界曲線に基づいた横断線分を生成する（ステップＳ４）。線分生成部２０は、先ず各境界曲線上に複数個のサンプル点を生成する。次に、線分生成部２０は、各サンプル点と、そのサンプル点における境界横断導関数（非特許文献９）から、境界稜線を横断する方向に直線を生成する。さらに、線分生成部２０は、この直線と境界平面との交点を算出する。そして、境界稜線上のサンプル点と、直線と境界平面の交点とを両端点とする線分、つまり横断線分を生成する。線分生成部２０は、横断線分を、例えば４分割した点群をサンプル点として生成する。
【００６８】
判定部３０が、判定事項Ｇ１、Ｇ２を判定する（ステップＳ５）。
Ｇ１：各境界稜線が、角形領域内側へ入り込む角部を構成する縁である。
Ｇ２：線分生成部２０に基づいて生成された境界稜線のサンプル点から延びた直線同士が交差している。
【００６９】
上記判定部３０で境界稜線がイレギュラーラインであると判断された場合（ステップＳ５でＮＧと判断された場合）、本実施形態は例外処理を行う（ステップＳ６）。つまり、線分再構成部４０が、イレギュラーラインと判断された境界稜線に関する横断線分を作り直す。具体的には、イレギュラーラインの境界稜線に対して、前述の非特許文献９の境界横断導関数を利用せずに、前述の式（１５）を用いて当該境界稜線からＮ辺形領域外側方向へ離れた位置に補助線、つまりオフセット曲線を作成する。そして、このオフセット曲線と当該境界稜線とを結ぶ、新たな横断線分を生成する。線分再構成部４０は、再生成した全ての横断線分を、例えば４分割した点群をサンプル点として生成する。
【００７０】
境界曲線生成部５０がB-spline曲面の境界曲線を生成する（ステップＳ７）。ここで、前述の判定部３０で一部の境界稜線がイレギュラーラインであると判断された場合には、非イレギュラーライン、つまり直線や外側へ膨らむ凸状の境界稜線に基づいて作成された横断線分だけを利用して、境界曲線を生成する。
【００７１】
曲面生成部６０は、境界曲線生成部５０によって生成されたB-spline曲面の境界稜線と、線分生成部２０によって生成された横断線分上のサンプル点及び線分再構成部４０によって再生成された横断線分上のサンプル点を利用して、B-spline曲面を生成する（ステップＳ８）。具体的には、境界曲線を境界とする最小２乗法により近似曲面をＢ−スプライン曲面として生成する。
【００７２】
このような本実施形態によれば、凹頂点、凹稜線を１つでも含む形状、つまり凹形状を有するＮ辺形領域に対して、例えば以下の処理を行う。
（１）図８（ａ）の形状のように、境界稜線の端点のいずれかが凹頂点の場合は、その境界稜線に属する横断線分をオフセット曲線に基づいて生成する。
（２）図８（ｂ）の形状のように境界稜線が凹稜線の場合、又は図８（ｃ）の形状のように複数の境界稜線の横断線分同士が干渉する場合、その境界稜線に属する横断線分をオフセット曲線に基づいて生成する。
【００７３】
従来技術では、凹形状近傍で接平面に基づいた点群がＮ辺形領域の内側に生成される。そして、横断線分の交差やねじれによって点群が空間に散らばり、例えば本当の表面でないところに点群が発生してフィッティングが曖昧になる。
一方、本発明の実施形態に係る曲面生成装置１によれば、凹形状を有するＮ辺形領域の曲面生成に当たり、例えば凹頂点近傍の横断線分を再生する。これにより、Ｎ辺形領域に適切にフィットして内挿可能な曲面を生成することができる。
【００７４】
〔実験結果〕
本手法を、凹形状を含む切欠形状を表すＮ辺形領域へ適用した。
下記の表１は、標準規格部品から得られた切欠形状を含む９種類の曲面形状に対して形状評価をした結果である。
【表１】
0005458440.tif 000017
生成した曲面と元の曲面の距離の平均である平均誤差値、距離の最大である最大誤差値、バウンディングボックスの大きさと最大距離の割合を示した。また、生成した曲面と元の境界稜線の距離の平均である平均誤差値、距離の最大である最大誤差値、バウンディングボックスの大きさと最大距離の割合を示した。表１から分かるように、トリム曲面を良い精度で近似できている。
【００７５】
以上詳述したが、本発明は発明の趣旨を逸脱しない範囲において様々な形態で実施できる。
Ｎ辺形領域の形状は、図示例に限定されるものではない。
【符号の説明】
【００７６】
１  曲面生成装置
１０  平面生成部
２０  線分生成部
３０  判定部
４０  線分再構成部
５０  境界曲線生成部
６０  曲面生成部
【図１】
0005458440.tif 000018
【図２】
0005458440.tif 000019
【図３】
0005458440.tif 000020
【図４】
0005458440.tif 000021
【図５】
0005458440.tif 000022
【図６】
0005458440.tif 000023
【図７】
0005458440.tif 000024
【図８】
0005458440.tif 000025
【図９】
0005458440.tif 000026
【図１０】
0005458440.tif 000027
【図１１】
0005458440.tif 000028
【図１２】
0005458440.tif 000029
【図１３】
0005458440.tif 000030
【図１４】
0005458440.tif 000031
【図１５】
0005458440.tif 000032
【図１６】
0005458440.tif 000033
【図１７】
0005458440.tif 000034
【図１８】
0005458440.tif 000035
【図１９】
0005458440.tif 000036
【図２０】
0005458440.tif 000037
【図２１】
0005458440.tif 000038
【図２２】
0005458440.tif 000039
【図２３】
0005458440.tif 000040
【図２４】
0005458440.tif 000041
【図２５】
0005458440.tif 000042