TOP > 国内特許検索 > 補間処理方法、および補間処理装置 > 明細書

明細書 :補間処理方法、および補間処理装置

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5218993号 (P5218993)
登録日 平成25年3月15日(2013.3.15)
発行日 平成25年6月26日(2013.6.26)
発明の名称または考案の名称 補間処理方法、および補間処理装置
国際特許分類 G06F  17/50        (2006.01)
G06T  17/00        (2006.01)
FI G06F 17/50 624A
G06T 17/00
請求項の数または発明の数 10
全頁数 22
出願番号 特願2009-539033 (P2009-539033)
出願日 平成20年10月24日(2008.10.24)
国際出願番号 PCT/JP2008/069306
国際公開番号 WO2009/057517
国際公開日 平成21年5月7日(2009.5.7)
優先権出願番号 2007282122
優先日 平成19年10月30日(2007.10.30)
優先権主張国 日本国(JP)
審査請求日 平成23年10月19日(2011.10.19)
特許権者または実用新案権者 【識別番号】504182255
【氏名又は名称】国立大学法人横浜国立大学
発明者または考案者 【氏名】前川 卓
【氏名】呉服 秀一
【氏名】田村 重文
個別代理人の代理人 【識別番号】100101915、【弁理士】、【氏名又は名称】塩野入 章夫
審査官 【審査官】田中 幸雄
参考文献・文献 国際公開第2007/83602(WO,A1)
調査した分野 G06F 17/50
G06T 17/00
特許請求の範囲 【請求項1】
制御点を用いて表される曲線または曲面によって点群を補間する補間処理方法において、
前記点群は、補間点の位置情報と、当該補間点における法線方向または法線方向に対して所定の角度関係を有した方向のみの情報を有するベクトル情報とを有し、
前記補間処理は、制御点により定義される前記曲線あるいは前記曲面において、
前記補間点の位置情報に基づいて、補間点から前記曲線上または前記曲面上に下ろした垂線の足を第1の点として求める幾何アルゴリズムの演算を行う第一の補間工程と、
前記ベクトル情報に基づいて、補間点における法線ベクトルまたは法線方向に対して所定の角度関係を有したベクトルと垂直に交わる前記曲線の接線または前記曲面の接平面との接点を第2の点として求める幾何アルゴリズムの演算を行う第二の補間工程と、
前記第1の点から前記補間点に向かうベクトル、前記第2の点から前記補間点に向かうベクトル、前記第2の点から前記第1の点に向かうベクトルを移動ベクトルとして求め、前記曲線または前記曲面を定義する制御点の位置を前記移動ベクトルから選択した何れか一つの移動ベクトルを用いて移動し、移動後の位置を新たな曲線または曲面の制御点の位置として定める幾何アルゴリズムの演算を行う第三の補間工程とを含み、
前記各補間工程を行う演算処理を、前記幾何アルゴリズムを組み込んだ演算手段において、前記位置情報、前記ベクトル情報、前記演算処理で得られるベクトルを用いて、記憶手段に記憶した前記幾何アルゴリズムの演算処理のプログラムをCPUに実行させることを特徴とする、補間処理方法。
【請求項2】
記憶手段に記憶した前記幾何アルゴリズムの演算処理のプログラムをCPUに実行させ
前記演算処理で得た制御点に基づいて新たな曲線又は曲面を求め、補間点と求めた曲線又は曲面との距離としきい値とを比較し、前記距離がしきい値を満たす、又はしきい値よりも小さくなるまで、前記第一の補間工程と第二の補間工程と第三の補間工程を繰り返すことを特徴とする、請求項に記載の補間処理方法。
【請求項3】
記憶手段に記憶した前記幾何アルゴリズムの演算処理のプログラムをCPUに実行させ
前記演算処理で得た制御点に基づいて新たな曲線又は曲面を求め、各補間点に設定された補間点における法線ベクトルまたは法線方向に対して所定の角度関係を有したベクトルと、前記第一の補間工程で求めた垂線の足となる第1の点における曲線または曲面の法線ベクトルとの角度差としきい値とを比較し、前記角度差がしきい値を満たす、又はしきい値よりも小さくなるまで、前記第一の補間工程と第二の補間工程と第三の補間工程を繰り返すことを特徴とする、請求項に記載の補間処理方法。
【請求項4】
前記憶手段に記憶した前記幾何アルゴリズムの演算処理のプログラムをCPUに実行させ
第1回目に行う第一の補間工程、第二の補間工程及び第三の補間工程において、
前記点群の補間点を初期制御点とし、前記各幾何アルゴリズムの演算を行い、
第2回目以降に行う第一の補間工程、第二の補間工程及び第三の補間工程において、
補間工程で得た制御点の位置を新たな制御点の位置とし、前記幾何アルゴリズムの演算を行うことを特徴とする、請求項1から請求項のいずれか一つに記載の補間処理方法。
【請求項5】
前記曲線はB-Spline曲線であり、前記曲面はB-Spline曲面あるいは細分割曲面であることを特徴とする、請求項1から請求項のいずれか一つに記載の補間処理方法。
【請求項6】
制御点を用いて表される曲線または曲面によって点群を補間する補間処理装置において、
前記点群は、補間点の位置情報と、当該補間点において法線方向または法線方向に対して所定の角度関係を有した方向のみの情報を有するベクトル情報とを有し、
制御点により定義される前記曲線あるいは前記曲面において、
前記補間点の位置情報に基づいて、補間点から曲線上または曲面上に下ろした垂線の足を第1の点として求める幾何アルゴリズムによって第一の補間工程を行う第一の幾何演算手段と、
前記ベクトル情報に基づいて、補間点における法線ベクトルまたは法線方向に対して所定の角度関係を有したベクトルと垂直に交わる前記曲線の接線または前記曲面の接平面との接点を第2の点として求める幾何アルゴリズムによって第二の補間工程を行う第二の幾何演算手段と、
前記第1の点から前記補間点に向かうベクトル、前記第2の点から前記補間点に向かうベクトル、前記第2の点から前記第1の点に向かうベクトルを移動ベクトルとして求め、曲線または曲面を定義する制御点の位置を前記何れか一つの移動ベクトルを用いて移動し、移動後の位置を新たな曲線または曲面の制御点の位置として定める幾何アルゴリズムによって第三の補間工程を行う第三の幾何演算手段とを備え、
前記第一の幾何演算手段、第二の幾何演算手段及び第三の幾何演算手段は、各幾何アルゴリズムをソフトウェアで実行するためのCPU及び記憶装置、又は各幾何アルゴリズムをハードウエアで実行するための回路を備えることを特徴とする、補間処理装置。
【請求項7】
前記演算処理で得た制御点に基づいて曲線又は曲面を求め、補間点と前記求めた曲線又は曲面との距離としきい値とを比較する比較手段と、
前記比較結果に基づいて、前記距離がしきい値を満たす、又はしきい値よりも小さくなるまで、前記第一の幾何演算手段と第二の幾何演算手段と第三の幾何演算手段とを繰り返して行わせるプログラム又は回路構成を有した制御手段を備えることを特徴とする、請求項に記載の補間処理装置。
【請求項8】
前記演算処理で得た制御点に基づいて曲線又は曲面を求め、各補間点に与えた法線ベクトルと、前記求めた垂線の足となる点における曲線または曲面の法線ベクトルとの角度差としきい値とを比較する比較手段と、
前記角度差がしきい値を満たす、又はしきい値よりも小さくなるまで、前記第一の幾何演算手段と第二の幾何演算手段と第三の幾何演算手段を繰り返して行わせるプログラム又は回路構成を有した制御手段を備えることを特徴とする、請求項に記載の補間処理装置。
【請求項9】
前記第一の幾何演算手段、第二の幾何演算手段及び第三の幾何演算手段は、
第1回目に行う演算において、前記点群を初期制御点とし前記幾何アルゴリズムの演算を行い、
第2回目以降に行う演算において、前記第1回目の演算で得た制御点位置を新たな制御点位置とし、前記幾何アルゴリズムの演算を行うことを特徴とする、請求項から請求項のいずれか一つに記載された補間処理装置。
【請求項10】
前記曲線はB-Spline曲線であり、前記曲面はB-Spline曲面あるいは細分割曲面であることを特徴とする、請求項から請求項のいずれか一つに記載の補間処理装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、点群データを補間・近似して曲線あるいは曲面を生成するフィッティング処理方法、フィッティング処理装置、およびこのフィッティング処理をCPUに実行させるプログラムに関する。
【背景技術】
【0002】
自由曲面は、船、自動車、飛行機等、様々な工業製品のボディに用いられており、機能性と美しさの両方を兼ね備えるものであり、家庭電気製品や多くの消費材の外観など意匠的に美しい形状のデザイン設計に用いられる。
【0003】
近年、3Dレーザスキャナによって高密度の点群データを高速かつ容易に収集することができるようになり、物体形状を高精度で測定できることが可能と成っている。例えば、3Dモデリングの分野においては、デザイナが手作業で作成したモックアップモデルを3Dレーザスキャナで計測し、コンピュータに取り込んだ点群データやポリゴンデータをもとに製品として生産するために必要な曲面データなどのCADデータを作成していくという、いわゆる形状のリバースエンジニアリングの手法が行われている。
【0004】
一般に、3DモデルはポリゴンモデルまたはNURBSやB-Splineなどの曲面パッチによりコンピュータ上で表現される。
【0005】
CAD/CAMにおいて点群の位置情報からB-Spline、NURBS、細分割等の曲線・曲面曲を補間・近似する方法が知られている(非特許文献1、特許文献1)。この補間・近似において、各点の位置情報に加えて法線情報を付加することによって設計の自由度を上げ、オフセット曲線・曲面の近似精度を向上させることが可能である。

【非特許文献1】Les Piegel, Wayne Tiller “The NURBS Book”P373~P376 Springer-Verlag Berlin Heidenberg 1995 and 1997
【特許文献1】特開2004-192209号公報
【発明の開示】
【発明が解決しようとする課題】
【0006】
法線を含む補間では、制御点の個数が点群の位置のみを補正する場合と比較して増加する。例えば、制御点の点数は、曲線の場合には補間点数の約2倍、曲面の場合には補間点数の約3倍となる。
【0007】
さらに、法線を指定するために用いる接線ベクトルにおいて、方向に係わる情報に加えて大きさの情報についても各補間点で指定する必要がある。この接線ベクトルの大きさの指定は、各補間点での接線ベクトルの大きさの指定と、指定した大きさによって得られる曲線あるいは曲面の補間結果の評価とを人手によって繰り返すことによって行うため、補間処理の多大な時間と負担を要する。
【0008】
したがって、点群の位置情報に加えて法線情報を付加することによって行う補間処理では、制御点の増加や、接線ベクトルにおける方向と大きさの指定等によって、設定を要するデータ数が増加するという問題がある。このデータ数の増加は、演算処理の処理時間の増加を招く他、人が行う処理も多大となるという問題がある。
【0009】
また、制御点が増加すると、曲線に不要な振動が生じる場合がある。
【0010】
そこで、本発明は前記した従来の問題点を解決し、点群の位置情報と法線情報を用いた補間処理において、処理データのデータ量を低減することを目的とする。
【0011】
さらに詳細には、点群の位置情報と法線情報を用いた補間処理において、制御点の増加を抑制することを目的とし、また、接線ベクトルの大きさの指定を不要とすることを目的とする。
【課題を解決するための手段】
【0012】
本発明は、フィッティング対象となる点群が与えられた状態から、この点群を補間する曲線あるいは曲面を求めるものである。はじめに、フィッティング対象となる点群を初期制御点群とし、この制御点群の制御点を用いて曲線、あるいは曲面を生成する。この制御点で表される曲線は、B-Spline曲線を適用することができ、また、制御点で表される曲面は、B-Spline曲面や細分割曲面を適用することができる。
【0013】
次に、同じ点群を補間点として、曲線、あるいは曲面の生成時に得られた制御点を移動させることによって、生成した曲線又は曲面を用いて補間点を補間するものである。以下、曲線あるいは曲面を曲線・曲面と表記して説明する。
【0014】
本発明による補間処理では、生成した曲線・曲面を用いて補間点を補間する際に、点群を構成する補間点の位置情報と、各補間点に設定された単位方向ベクトルのベクトル情報を用いて、制御点を移動させる移動ベクトルを算出し、この移動ベクトルの移動方向に移動量だけ制御点を移動させる。
【0015】
上記した、補間点を補間する曲線・曲面の生成と制御点の移動の工程を繰り返すことによって、曲線・曲面を点群の位置および単位方向ベクトルについてフィッティングさせる新たな制御点位置を求める。
【0016】
本発明は、各点群から最短距離となる曲線・曲面上の点を求める第一の工程と、設定された単位方向ベクトルと曲線・曲面上の接線が垂直となる接線を有する点を求める第二の工程、第二の工程で求めた点から各点群へ向かうベクトルを求め、このベクトル分だけ各制御点を移動させる第三の工程を、補間点に定められた位置と方向について位置誤差と角度誤差が所定した大きさよりも小さくなるまで繰り返す。
【0017】
位置誤差については、点群と曲線・曲面との距離が、しきい値を満たすまで、またそれよりも小さくなるまで繰り返すことで減少させる。また、角度誤差については、曲線・曲面上の点であって、点群から最短距離となる点における法線ベクトルと、補間点に設定された単位方向ベクトルとの角度差が、しきい値を満たすまで、またそれよりも小さくなるまで繰り返すことで減少させる。これによって、点群にフィッティングする曲線・曲面を生成する。
【0018】
本発明は、補間処理方法の態様と補間処理装置の態様とを有する。
【0019】
補間処理方法の態様は、制御点で定義される曲線または曲面によって点群を補間する補間処理方法であって、点群は、補間点の位置情報と、この補間点における曲線または曲面の方向を定める単位方向ベクトルのベクトル情報とを有する。
【0020】
補間処理は、制御点により定義される曲線・曲面において、補間点の位置情報に基づいて、補間点から曲線・曲面上に下ろした垂線の足を第1の点として求める幾何アルゴリズムの演算を行う第一の補間工程と、ベクトル情報に基づいて、単位方向ベクトルと垂直に交わる曲線の接線または曲面の接平面との接点を第2の点として求める幾何アルゴリズムの演算を行う第二の補間工程と、第1の点から補間点に向かうベクトル、第2の点から前記補間点に向かうベクトル、第2の点から第1の点に向かうベクトルを移動ベクトルとして求め、曲線または曲面を定義する制御点の位置を前記した3つの移動ベクトルから選択した移動ベクトルを用いて移動し、移動後の位置を新たな曲線または曲面の制御点の位置として定める幾何アルゴリズムの演算を行う第三の補間工程とを含んでいる。これら各補間工程を行う演算処理は、幾何アルゴリズムを組み込んだ演算手段により行われる。
【0021】
また、補間処理装置の態様では、制御点で定義される曲線または曲面によって点群を補間する補間処理装置であって、点群は、補間点の位置情報と、この補間点において曲線または曲面の方向および曲率を定める単位方向ベクトルのベクトル情報とを有する。
【0022】
補間処理装置、補間処理を行う構成として第一~第三の幾何演算手段を備える。
【0023】
第一の幾何演算手段は、制御点により定義される曲線あるいは曲面において、補間点の位置情報に基づいて、補間点から曲線上または曲面上に下ろした垂線の足を第1の点として求める幾何アルゴリズムによって第一の補間工程を行う。
【0024】
第二の幾何演算手段は、ベクトル情報に基づいて、単位方向ベクトルと垂直に交わる曲線の接線または曲面の接平面との接点を第2の点として求める幾何アルゴリズムによって第二の補間工程を行う。
【0025】
第三の幾何演算手段は、第1の点から補間点に向かうベクトル、第2の点から補間点に向かうベクトル、第2の点から第1の点に向かうベクトルを移動ベクトルとして求め、曲線または曲面を定義する制御点の位置を何れか一つの移動ベクトルを用いて移動し、移動後の位置を新たな曲線または曲面の制御点の位置として定める幾何アルゴリズムによって第三の補間工程を行う。
【0026】
ここで、第一の幾何演算手段、第二の幾何演算手段及び第三の幾何演算手段は、各幾何アルゴリズムをソフトウェアで実行するためのCPU及び記憶装置、又は各幾何アルゴリズムをハードウェアで実行するための回路を備える構成とすることができる。
【0027】
本発明において、曲線・曲面の方向や曲率を定める単位方向ベクトルは、方向のみの情報を有し、大きさについては情報を有していない。また、この単位方向ベクトルは、補間点を補間する曲線又は曲面上における補間点での法線ベクトルとする他、法線ベクトルから所定の角度関係を有した方向ベクトルとしてもよい。
【0028】
補間処理の終了は、曲線・曲面が補間点を十分に補間したと判断される時点まで繰り返す。この繰り返しによる収斂は、距離と角度差を指標として行うことができる。
【0029】
距離を指標として繰り返しを行う場合には、演算処理で得た制御点に基づいて新たな曲線・曲面を求め、補間点と求めた曲線又は曲面との距離としきい値とを比較し、この距離がしきい値を満たすまで、又はしきい値よりも小さくなるまで、第一の補間工程と第二の補間工程と第三の補間工程を繰り返す。
【0030】
また、角度を指標として繰り返しを行う場合には、演算処理で得た制御点に基づいて新たな曲線・曲面を求め、各補間点に設定された単位方向ベクトルと、第一の補間工程で求めた垂線の足となる第1の点における曲線または曲面の法線ベクトルとが形成する角度差とを求め、この両ベクトルの角度差としきい値とを比較し、角度差がしきい値を満たすまで、又はしきい値よりも小さくなるまで、第一の補間工程と第二の補間工程と第三の補間工程を繰り返す。
【0031】
上記した距離を指標とする収斂と、角度差を指標とする収斂は、それぞれ単独で行う他に、両方を組み合わせて行っても良い。
【0032】
また、本発明の補間処理では、はじめに点群が与えられた状態で開始する場合には、第1回目に行う各補間工程では、与えられた点群の補間点を初期制御点として曲線・曲面を生成し、各幾何アルゴリズムの演算を行うことで制御点を生成する。次に、第2回目以降で行う補間工程では、補間工程で得た制御点の位置を新たな制御点の位置として、各幾何アルゴリズムの演算を行うことで制御点を修正し、これを繰り返す。
【0033】
本発明による補間処理は、局所的に各制御点を扱うことになるため、線形システム自体を必要としない上に、幾何学的なプロセスのみで点群にフィッティングする曲線・曲面を生成することができる。そのため、本発明の補間処理によれば、従来の手法にくらべ曲線・曲面を定義する制御点の数を、曲線では二分の一、曲面では三分の一に減少させることができる。
【0034】
また、本発明による補間処理では、補間点に設定する単位方向ベクトルはベクトル情報として方向のみを含み、大きさについては不要である。従来の接線ベクトルを用いた処理では、曲線又は曲面上の各点において接線ベクトルの大きさの変更を、曲線又は曲面の形状を目視で観察しながら逐次行ってフィッティングを行う必要があり、多くの労力と時間を有していたが、本発明によれば、プロセスの開始から終了までの間で人の介入なしに曲線・曲面のフィッティングを行うことができる。なお、ここでフィッティングとは補間と近似の両方を含むものとする。
【発明の効果】
【0035】
以上説明したように、本発明によれば、点群の位置情報と法線情報を用いた補間処理において、制御点の増加を抑制し、処理データのデータ量を低減することができる。
【0036】
また、点群の位置情報と法線情報を用いた補間処理において、接線ベクトルの大きさの指定を不要とし、自動的な補間を容易とすることができる。
【0037】
また、制御点の増加に伴って生じていた、補間の際の不必要な振動を抑えることができる。
【図面の簡単な説明】
【0038】
【図1】本発明の補間処理の概略を説明するための概略図である。
【図2】本発明の補間処理の概略を説明するためのフローチャートである。
【図3】本発明の補間処理の第一、第二の補間工程を説明するための図である。
【図4】本発明の補間処理の第三の補間工程を説明するための図である。
【図5】本発明の補間処理装置の概略構成図である。
【図6】本発明の二次元の点群より曲線を生成する場合を説明するためのフローチャートである。
【図7】本発明の二次元の点群より曲線を生成する場合を説明するための制御点と曲線との概略図である。
【図8】本発明の二次元の点群より曲線を生成する場合を説明するための制御点と曲線との概略図である。
【図9】本発明の二次元の点群より曲線を生成する場合を説明するための制御点と曲線との概略図である。
【図10】本発明の二次元の点群を補間する曲線例を示す図である。
【図11】本発明による補間結果と従来法による補間結果を比較する図である。
【図12】本発明による補間結果と従来法による補間結果を比較する図である。
【図13】三次元の点群より曲面を生成する場合を説明するためのフローチャートである。
【符号の説明】
【0039】
1…入力手段
2…記憶手段
2a…データ記憶部
2b…演算ツールプログラム記憶部
2c…演算処理プログラム記憶部
2d…一次記憶部
2e…演算結果記憶部
3…演算手段
4…表示手段
5…出力手段
【発明を実施するための最良の形態】
【0040】
以下、本発明の実施の形態について、図を参照しながら詳細に説明する。なお、以下では、制御点によって定義される曲線・曲面として、主にB-Spline曲線・曲面について説明するが、本発明は、B-Spline曲線・曲面に限られるものではなく、制御点を用いて表現される細分割曲面等の曲線・曲面についても同様に適用することができる。
【0041】
図1は本発明の補間処理を説明するための概略図であり、図2は本発明の補間処理を説明するためのフローチャートであり、図3、図4は、本発明の補間処理を説明するための図である。また、図5は本発明の補間処理装置の概略構成図である。
【0042】
図1、図2、図3、図4は、位置情報および単位方向ベクトルのベクトル情報を含む点群Qが与えられ、この点群QからB-Spline曲線を求める手順を概略的に示している。なお、以下では、単位方向ベクトルとして法線ベクトルの例について説明する。単位方向ベクトルが法線ベクトル以外のベクトルである場合には、法線ベクトルに対して所定に角度関係を設定することで、その方向を定めることができる。
【0043】
また、ここでは、補間対象となる点群を単に点群と呼び、入力で各点群に与える法線ベクトルを単に法線ベクトルと呼ぶ。
【0044】
なお、ここでは主に曲線について説明するが、曲面においても同様に扱うことができる。
【0045】
以下、図1の概略図と図2のフローチャートを用いて、与えられた点群QからB-Spline曲線・曲面を生成する手順を説明する。
【0046】
はじめに、与えられた点群Qを初期制御点P0とする。点群Qは、各点の位置情報と、各点に設定された方向情報とを含んでいる。方向情報は、点群を補間する曲線又は曲面の方向や曲率を定めるものであり、単位方向ベクトルで表すことができる。単位方向ベクトルは、方向のみの情報を有し、大きさの情報は有していない。単位方向ベクトルは、例えば、その点における法線ベクトルとする他に、この法線ベクトルに対して所定の角度関係を有したベクトルとしてもよい。以下では、単位方向ベクトルとして法線ベクトルの例について説明する。図1中で(S1)で示す箇所の左方は、点群Qとその点における法線ベクトルN*(図中Nの上に矢印として表記)を示し、右方は、この点群Qを初期制御点とし、これらの初期制御点を直線で繋いだときの形状を示している(S1)。
【0047】
第1回目のB-Spline曲線・曲面の生成では、制御点が設定されていないため、与えられた点群を初期制御点とし、この初期制御点をもとにB-Spline曲線C0を生成する。図1中において、(S2)を付した矢印は、初期制御点を繋いで形成された形状からB-Spline曲線・曲面を生成する状態を示している(S2)。
【0048】
次に、補間処理によって制御点を移動し、補間点をより忠実に補間するB-Spline曲線・曲面を形成する。
【0049】
この補間処理では、B-Spline曲線・曲面上の点と補間点との関係から移動ベクトルを求め、求めた移動ベクトルを用いて制御点の位置を移動することで行う。より詳細には、後述するように3つの補間工程(S3a)~(S3c)によって行う。図1中において、(S3)を付した矢印は、補間工程によって新たな制御点を求めた状態を示している(S3)。
【0050】
S3の補間処理によって制御点の位置を移動した後、移動した制御点に基づいてB-Spline曲線Cnを生成する。図1中において、(S4)を付した矢印は、移動後の制御点を用いてB-Spline曲線・曲面を生成する状態を示している。(S4)。
【0051】
生成したB-Spline曲線・曲面と点群Qとを比較し、B-Spline曲線・曲面が点群Qを良好に補間するまでS3の補間処理を繰り返す。このS3の補間処理の繰り返しは、点群Qの各点と、B-Spline曲線・曲面上で当該点群Qと対応する点との間の距離誤差や、点群Qの各点に付与された法線ベクトルと、B-Spline曲線・曲面上で当該点群Qの対応する点での法線の角度差が収束するまで行う。この収束は距離誤差、法線の角度差がしきい値を満たすまでS3の行程を繰り返すことで行う。
【0052】
上記したB-Spline曲線・曲面の収束は、点間の距離誤差を収束条件と法線間の角度差を収束条件の両収束条件を用いて行う他に、何れか一方の収束条件を用いて行っても良い(S5)。
【0053】
以下、上記したS3の補間処理について説明する。S3の補間処理は三つの補間工程S3aとS3bとS3cを備える。
【0054】
第一の補間工程S3aでは、補間点からB-Spline曲線・曲面上へ垂線を下ろしたときの垂線の足を求める。この垂線の足は、B-Spline曲線・曲面上において補間点からの距離が最短となる最短距離点として定めることができる。
【0055】
第二の補間工程S3bでは、各補間点に与えられた法線ベクトルとB-Spline曲線・曲面上の接線あるいは接平面が垂直に交わるとき、そのような接線あるいは接平面を有する曲線・曲面上の接点を求める。
【0056】
第三の補間工程S3cでは、第一の補間工程および第二の補間工程で求めたB-Spline曲線・曲面上の点と補間点との間で形成されるベクトルを求め、求めたベクトルを移動ベクトルとして制御点の位置を移動させて新たな制御点を設定する。
【0057】
以下、S3の補間処理について、図3、4を用いて説明する。
【0058】
図3(a)は第一の補間工程S3aの工程を説明するための図であり、図3(b)は第二の補間工程S3bの工程を説明するための図であり、図4は第三の補間工程S3cの工程を説明するための図である。
【0059】
また、図3、4では、シフト前の制御点をPa、シフト後の制御点をPbで示し、曲線Cn上で求めた近傍点をFnで示している。また、法線ベクトルをN*(図中Nの上に矢印として表記)として示し、法線ベクトルN*と垂直に交わる接線を有する曲線Cn上の点をGnで示す。また、以下では、B-Spline曲線を用いて説明する。
【0060】
図3(a)に示す第一の補間工程S3aにおいて、第一回目の補間工程では、制御点Paは与えられた点群の補間点Qと同じ位置の点であり、第二回目以降の補間工程では、前回の補間工程によって位置がシフトされた制御点である。
【0061】
第一の補間工程S3aでは、制御点により定義されるB-Spline曲線Cnにおいて、補間点Qの位置情報に基づいて、補間点QからB-Spline曲線Cn上に下ろした垂線の足を第1の点Fnを幾何アルゴリズムの演算処理によって求める。
【0062】
次に、図3(b)に示す第二の補間工程S3bにおいて、法線ベクトルN*は各点群Qに与えられている。
【0063】
第二の補間工程S3bでは、法線ベクトルN*と垂直に交わる接線を有する曲線上の接点をFnの近傍で求め、第2の点Gnとする。曲面の場合には、法線ベクトルと垂直に交わる曲面の接平面との接点を第2の点Gnとして、幾何アルゴリズムの演算によって求める。
【0064】
図4は第三の補間工程S3cで行う制御点の移動形態の3例を示している。
【0065】
第三の補間工程S3cでは、第一の補間工程で求めた第1のFnと、第二の補間工程で求めた第2の点Gnと、補間点Qとの間で形成されるベクトルを求め、求めたベクトルを移動ベクトルとして制御点の位置を移動させ新たな制御点を設定する。
【0066】
図4(a)は、第2の点Gnから補間点Qに向かうベクトルを移動ベクトルとして制御点Pを移動させる移動形態を示し、図4(b)は、第2の点Gnから第1の点Fnに向かうベクトルを移動ベクトルとして制御点Pを移動させる移動形態を示し、図4(c)は、第1の点Fnから補間点Qに向かうベクトルを移動ベクトルとして制御点Pを移動させる移動形態を示している。
【0067】
第三の補間工程S3cでは、これら各移動形態の移動ベクトルの何れかを用いて制御点を移動させることで新たな制御点を求める。この第三の補間工程は幾何アルゴリズムの演算によって実行することができ、この演算処理は幾何アルゴリズムを組み込んだ演算手段により行うことができる。
【0068】
次に、制御点Paの位置をシフトして新たな位置に制御点Pbを求める第三の補間工程において、図4(a)に示す移動形態では、第二の補間工程S3bの工程で求めた第2の点Gnから対応する補間点Qへ向かうベクトルA(図中の破線で示す)を求め、このベクトルAを移動ベクトルとして制御点Paを移動し、新たな制御点Pbを求める。
【0069】
図4(b)に示す移動形態では、第二の補間工程S3bの工程で求めた第2の点Gnから第一の補間処理S3aの工程で求めた第1の点Fnへ向かうベクトルB(図中の破線で示す)を求め、このベクトルBを移動ベクトルとして制御点Paを移動し、新たな制御点Pbを求める。
【0070】
図4(c)に示す移動形態では、第一の補間工程S3aの工程で求めた第1の点Fnから対応する補間点Qへ向かうベクトルC(図中の破線で示す)を求め、このベクトルCを移動ベクトルとして制御点Paを移動し、新たな制御点Pbを求める。
【0071】
これら3つの移動形態から一つを選択して制御点を移動し、新たな制御点の位置を定める。この制御点移動位置の選択は、以下のようにして行うことができる。
【0072】
図4(a)で示すように、第2の点Gnから対応する補間点Qへ向かうベクトル分だけ移動させた位置にシフトする補間処理を繰り返した際に、補間点Qとの曲線Cnとの距離誤差が小さくなると、法線ベクトルの角度差が制御点Paを移動しても小さくならない場合がある。
【0073】
このような状態になった場合に、図4(b)で示すように、第2の点Gnから第1の点Fnへ向かうベクトル分だけ制御点Paを移動させた位置にシフトすることで、角度差を小さくすることができる。
【0074】
また、逆に、角度差が十分小さくなり、距離誤差が制御点Pをシフトさせても小さくならない場合には、制御点Pを第1の点Fnから補間点Qへ向かうベクトル分だけ移動させた位置にシフトすることで、距離誤差を小さくする。これら各移動形態は、状況に合わせて選択することができる。
【0075】
補間処理S3はこの第一の補間工程S3aと第二の補間工程S3bと第三の補間工程S3cを繰り返して行われる。この第三の工程で得られた制御点Pbを用いることで前記したS4の工程によりB-Spline曲線・曲面が生成される。
【0076】
S5の工程では、生成したB-Spline曲線・曲面と点群の距離ならびに法線ベクトルを比較し、対応する点間の距離誤差、対応する法線ベクトルの角度差、が収束するまでS3の補間工程を繰り返す。この収束は、距離誤差と法線ベクトルの角度差がそれぞれあらかじめ設定しておいたしきい値を満たすまで、又はしきい値よりも小さくなるまで繰り返す。
【0077】
補間処理によって距離誤差ならびに法線ベクトルの角度差が収束したときに得られるB-Spline曲線・曲面は、補間点の位置を補間するとともに、補間点での法線ベクトルが、設定された法線ベクトルと同様となる曲線・曲面となる。
【0078】
図5は、本発明の補間処理のソフトウェアを記憶したプログラムをコンピュータで実行させる場合の一構成例を示している。
【0079】
入力手段1は、点群Q、法線ベクトルN*のデータを入力し、記憶手段2中のデータ記憶部2aに記憶する。記憶手段2は、データ記憶部2aの他に、微分幾何学演算を行う演算ツールのプログラムを記憶する演算ツールプログラム記憶部2b、補間処理の微分幾何学演算の他、B-spline曲線・曲面生成処理等の演算処理のプログラムを記憶する演算処理プログラム記憶部2c、途中演算結果等を一時的に記憶する一次記憶部2d、補間処理等によって得られた曲面の演算結果を記憶する演算結果記憶部2e等を備える。
【0080】
演算手段3は、データ記憶部2aに記憶された点群Qのデータを用い、演算処理プログラム記憶部2cに記憶されるプログラムによる演算手順に従うと共に、このプログラムに指定される演算ツールのプログラムを演算ツールプログラム記憶部2bから逐次読み出して演算処理を行う。
【0081】
演算結果記憶部2eに記憶された演算結果は、読み出して表示手段4に表示したり、出力手段5に出力することができる。出力手段5は、演算結果を記録媒体に記録する記録装置、例えば加工装置等の、演算結果を用いて所定動作を実行する外部装置とすることができる。
【0082】
なお、上記、ソフトウェア処理を行う構成は、専用のソフトウェア処理装置や、通常のパーソナルコンピュータに適用することができる。
【0083】
また、上記構成において、記憶手段を含む演算手段で実施される機能を回路で構成することでハードウェアにより実施することもできる。
【0084】
次に、本発明の補間処理の詳細について、二次元の点群(位置、法線情報を含む)からB-Spline曲線を生成する場合と、三次元の点群(位置、法線情報を含む)からB-Spline曲面を生成する場合について説明する。
【0085】
以下、はじめに、二次元の点群(位置、法線情報を含む)からB-Spline曲線を生成する場合を、図6のフローチャート、図7~9の制御点と曲線の関係を説明する概略図、図10~12の曲線補間の例の図を用いて説明し、次に、三次元の点群(位置、法線情報を含む)からB-Spline曲面を生成する場合を、図13のフローチャートを用いて説明する。
【0086】
はじめに、二次元の点群(位置、法線情報を含む)からB-Spline曲線を生成する場合について説明する。なお、以下のフローチャートは一例であり、本発明の第一の補間工程及び第二の補間工程及び第三の補間工程を実施する工程及び手順であれば他のフローで構成してもよい。
【0087】
二次元の点群データ(位置、法線ベクトル)を取得し(S11)、点群の位置をQiとて記憶し、法線ベクトルをN*として記憶する(S12)。図7(a)はS12の状態を示している。得られた補間点Qiを初期制御点P0iとして記憶する(S13)。
【0088】
制御点Pk-1iからB-Spline曲線Ck-1を生成する。ここで、上付き文字Kは補間処理の回数を示す。第1回目では、制御点Pが設定されていないため、与えられた補間点補間点Qiを初期制御点P0iとし、この初期制御点P0iを用いてB-Spline曲線・曲面を生成する。図7(b)は初期制御点P0iを用いてB-Spline曲線・曲面を生成した状態を示している(S14)。
【0089】
以下、S15,S16に示す第一の補間工程とS17、S18に示す第二の補間工程とS21~S23に示す第三の補間工程の中からいずれかの工程を繰り返すことにより点群を位置ならびに法線ベクトルについて補間するB-Spline曲線Cを生成する。
【0090】
第一の補間工程において、補間点Qから曲線C上に垂線を降ろし、この垂線の足を求め、求めた第1の点Fkiとする。ここで、垂線を下ろす曲線Cは、初回ではS13の工程で得た制御点P0から生成される曲線C0であり、二回目以降はS21~S23のいずれかの工程でシフトされた制御点Pkiによって生成される曲線CKである(S15)。
【0091】
補間点QiとS14で求めた垂線の足である第1の点Fkiとの距離//Qi-Fki//(=Δd)を求める。垂線および距離を求める演算は、微分幾何学演算により求めることができる。図7(c)は、初回の第一の補間工程のS15、S16の状態を示している(S16)。
【0092】
次に、第二の補間工程において、各補間点Qに与えられた法線ベクトルNi*と垂線の足の第1のFkiにおける曲線Cの法線ベクトルの角度差Δθを求め(S17)、法線ベクトルNi*と垂直に交わる接線と接する曲線上の接点を第2のGkiとして求める。角度差および法線ベクトルと垂直に交わる接線と接する曲線上の点は、微分幾何学演算により求めることができる。図7の(d)は初回の補間工程のS18の状態を示している(S18)。
【0093】
次に、第三の補間工程において、S16で求めた距離ΔdとS18で求めた角度差ΔθからS22~S24の三つの補正工程の内から一つを選択して実行する。
【0094】
補間点と曲線の距離誤差Δd、および法線ベクトルの角度差Δθは共にしきい値を満たさない場合には(S19、S21)、S18で求めた曲線上の第2の点Gkiから補間点Qiに向かうベクトルAの方向および大きさの分だけ、現在の曲線を定義している制御点Pk-1iの位置をシフトし、シフトした位置を新たな制御点Pkiの位置とする。図8(a)はこの補正工程による移動状態を示している(S22)。
【0095】
補間点と曲線の距離誤差Δdはしきい値を満たすが(S19)、法線ベクトルの角度差Δθがしきい値を満たさない場合には(S20)、S18で求めた曲線上の第2の点GkiからS15で求めた垂線の足の第1の点Fkiへ向かうベクトルBの方向および大きさの分だけ、現在の曲線を定義している制御点Pk-1iの位置をシフトし、シフトした位置を新たな制御点Pkiの位置とする。図8(b)はこの補正工程による移動状態を示している(S24)。
【0096】
補間点と曲線の距離誤差Δdはしきい値を満たさない(S19)が、法線ベクトルの角度差Δθはしきい値を満たす場合には(S21)、S15で求めた垂線の足である第1の点Fkiから補間点Qiへ向かうベクトルCの方向および大きさの分だけ、現在の曲線を定義している制御点Pk-1iの位置をシフトし、シフトした位置を新たな制御点Pkiの位置とする。図8(c)はこの補正工程による移動状態を示している(S23)。
【0097】
制御点をシフトする演算は、幾何学的演算によって求めることができる。図8(a)は初回の補間処理におけるS21の状態を示している。図8(b)は初回の補間処理におけるS22の状態を示し、図8(c)は初回の補間処理におけるS23の状態を示している。
【0098】
また、図9(a),(c)は二回目以降の補間処理のS14によってB-Spline曲線C(1),C(2)を生成した状態を示している。また、図9(b)は二回目以降の補間処理のS21によって制御点P(1)を制御点P(2)に移動させた状態を示している。
【0099】
S14で求めた曲線Cが補間点Qiとの距離誤差Δd、法線ベクトルNi*と垂線の足の第1の点Fkiにおける曲線Cの法線ベクトルの角度差Δθ、がそれぞれのしきい値を満たすまでS14~S23までの工程を繰り返す。距離誤差Δd、角度差Δθのしきい値は、それぞれ点群を補間する曲線に対して許容できる許容距離誤差、および法線の角度差に対して許容できる許容法線ベクトル角度差に相当する。
【0100】
したがって、S19、S20、S21の比較工程において距離、法線ベクトルの角度差がしきい値を満たすことを確認することで、曲線Cは点群を与えた位置ならびに法線ベクトルについて許容誤差範囲内で補間するものとする。
【0101】
図10は、二次元(平面)の曲線補間の一例であり、Bowditch曲線とTrochoid曲線から点群とその点における法線ベクトルを抽出し、点群の位置ならびに法線ベクトルについて補間したものである。図10(a),(c)には、補間対象となる点群の各点と、線分で示した法線ベクトルを示している。図10(b)(d)には、本発明によりそれぞれ点群を位置ならびに法線ベクトルについて三次のB-Spline曲線で補間した結果を示している。
【0102】
本発明の手法における計算結果を表1に、点の位置のみについて従来の手法(非特許文献1)で補間した結果を表2に示す。ここで、距離誤差については各モデルにおけるbounding boxの対角線を基準として%で示す。距離誤差について結果を見るとほぼゼロになっていることがわかる。角度差についてみると本発明の手法を用いた場合では、最大角度差がBowditch曲線で 0.024°程度、Trochoid曲線は0.005°程度となっているのに対し、従来法の場合、Bowditch曲線では2.0°程度、Trochoid曲線では0.14°程度であった。本発明による方が最大角度差を小さく抑えていることがわかる。なお、表2において*印は計算時間が0.01秒未満であったことを示している。
【0103】
【表1】
JP0005218993B2_000002t.gif

【0104】
【表2】
JP0005218993B2_000003t.gif

【0105】
次に、Trochoid曲線について、図11(a)に本発明による補間を行った曲線の曲率線図を、図11(b)に従来の手法(非特許文献1)で補間を行ったものを、図11(c)に従来の手法(エルミート補間)で補間を行ったものを示している。
【0106】
従来の手法(非特許文献1)は補間点に対し制御点を曲線で約二倍、曲面で約三倍にする必要があり、制御点が多くなるために曲線が不必要な振動を起こしている(図11(b))。その点、本発明による補間では、制御点は補間点とほぼ同数であるためそのような不必要な振動を抑えることができる(図11(a))。
【0107】
また、従来法では、各点での接線ベクトルの大きさを入力する必要があったが、本発明ではそのような必要はなく、人の介入なしに補間処理の一切をおこなうことができ、処理の自動化ができる。
【0108】
図12(a)に、図11(a)に示した本発明による補間を行った曲線の曲率線図の一部を拡大したものを示し、図12(b)に、図11(c)で示した従来の手法(エルミート補間)で補間を行った曲線の曲率線図の一部を拡大したものを示す。
【0109】
本発明による補間は三次のB-Spline曲線を用いており、三次のB-Spline曲線はC2連続まで保障されるため曲率が連続になっている(図12(a))(ここで、C2とは曲率連続性を示し、上記曲線をあらわすCと区別する)。従来の手法(エルミート補間)は曲率の連続を保証していないために、図中の丸で囲んだ箇所で示すように、曲線の所々で曲率が不連続になっている(図12(b))。
【0110】
上記したように本発明による補間は従来方法に比べ曲率が連続で滑らかなな曲線を生成することができる。
【0111】
次に、三次元の点群(位置、法線情報を含む)よりB-Spline曲面を生成する場合について、図13のフローチャートを用いて説明する。なお、以下の図13に示すフローチャートは一例であり、本発明の第一の補間処理及び第二の補間処理及び第三の補間処理を実施する工程及び手順であれば他のフローで構成してもよい。
【0112】
点群から位置をQ、法線ベクトルをN*として記憶する(S31、S32)。得られた補間点Qiを初期制御点P0iとして記憶する(S33)。制御点Pk-1iからB-Spline曲面Sk-1を生成する。ここで、上付き文字Kは補間処理の回数を示している。
【0113】
以下、S35,S36に示す第一の補間処理とS37、S38に示す第二の補間処理とS42~S44に示す第三の補間処理の中からいずれかの工程を繰り返すことにより点群を位置ならびに法線ベクトルについて補間するB-Spline曲面Sを生成する。
【0114】
第一の補間処理において、補間点から曲面S上に垂線を降ろし垂線の足となる第1の点Fkiを求める。なお、曲面Sは、初回の補間処理ではS33の工程で得た制御点P0から生成される曲面S0であり、二回目以降の補間処理ではS41~S43のいずれかの工程でシフトされた制御点Pkiから生成される曲面Skである(S35)。補間点Qiと垂線の足の第1のFkiとの距離//Qi-Fki//(=Δd)を求める(S36)。垂線および距離を求める演算は、微分幾何学演算により求めることができる。
【0115】
次に、第二の補間処理において、各補間点に与えられた法線ベクトルNi*と垂線の足の第1の点Fkiにおける曲面Sの法線ベクトルの角度差Δθを求める(S37)。法線ベクトルNi*と垂直に交わる接平面と接する曲面上の接点Gkiを第2の点として求める(S38)。角度差Δθ、および法線ベクトルと垂直に交わる接平面と接する曲面上の点は、微分幾何学演算により求めることができる。
【0116】
次に、第三の補間処理において、S36で求めた距離誤差ΔdとS38で求めた角度差ΔθからS41~S43の三つの工程の内から一つを選択し実行する。補間点Qと曲線との距離誤差Δd、法線ベクトル角度差Δθが共にしきい値を満たさない場合には(S39,S41)、S18で求めた曲面上の点Gkiから補間点Qiに向かうベクトル分だけ、現在の曲面を定義している制御点Pk-1iの位置をシフトし、シフトした位置を新たな制御点Pkiの位置とする(S42)。
【0117】
補間点Qと曲面の距離誤差Δdはしきい値を満たすが(S39)、法線ベクトルの角度差Δθはしきい値を満たさない場合には(S40)、S38で求めた曲面上の点GkiからS35で求めた垂線の足の第1の点Fkiへ向かうベクトル分だけ、現在の曲面を定義している制御点Pk-1iの位置をシフトし、シフトした位置を新たな制御点Pkiの位置とする(S44)。
【0118】
補間点Qと曲面の距離誤差Δdはしきい値を満たさないが(S39)、法線ベクトルの角度差はしきい値を満たす場合(S41)、S35で求めた垂線の足の点Fkiから補間点Qiへ向かうベクトル分だけ、現在の曲面を定義している制御点Pk-1iの位置をシフトし、シフトした位置を新たな制御点Pkiの位置とする(S43)。制御点をシフトする演算は、幾何学的演算によって求めることができる。
【0119】
S34で求めた曲面Sが補間点Qiとの距離誤差Δd、法線ベクトルNi*と垂線の足の第1の点Fkiにおける曲面Sの法線ベクトルの角度差Δθ、がそれぞれのしきい値を満たすまでS34~S44までの工程を繰り返す。距離誤差、角度差のしきい値は、それぞれ点群を補間する曲面に対する距離誤差に対して許容できる許容距離誤差、法線の角度差に対して許容できる許容法線ベクトル角度差に相当する。
【0120】
したがって、S39、S40、S41の比較工程において距離誤差、法線ベクトルの角度差がしきい値を満たすことを確認することで、曲面Sは点群を与えた位置ならびに法線ベクトルについて許容誤差範囲内で補間するものとする。
【0121】
本発明の一適用例としてオフセット曲線・曲面への適用がある。本発明を利用することにより、オフセット曲線・曲面をB-Spline曲線・曲面で表現する場合の精度向上が図ることができる。
【0122】
オフセット曲線・曲面とは、ある曲線・曲面を法線方向へ一定の距離シフトした曲線・曲面である。一般的に市販されているCAD/CAMソフトウェアには必ずプルダウンメニューとしてオフセット機能が装備されており、現実にNC切削加工などで入力したCAD/CAMデータから工具半径を考慮した工具中心の軌跡すなわちツールパスを求めるときに、CAD/CAMデータ上の曲線・曲面のオフセット曲線・曲面が用いられる。ここで、一般にオフセット曲線・曲面は多項式で表現できないため、区分多項式で表現されるB-Spline曲線・曲面では直接表現することができない。この場合、オフセット曲線・曲面を一定の点群としてサンプリングを行い、得られた点群をB-Spline曲線・曲面で補間するという作業が必要である。このとき、オフセット曲線・曲面はその性質上容易にサンプリングした点での法線が取り出せるので、位置のみではなく法線ベクトルについてもB-Spline曲線・曲面で補間することで、よりオフセット曲線・曲面に近いB-Spline曲線・曲面を得ることや、必要なサンプリング点を減少させることができる。この法線を含めたB-Spline曲線・曲面の補間を行うときに、本発明を用いることで不必要な振動の少ない高品質の曲線が得られ、CAD/CAMソフト上のオフセット機能の精度の向上が図られる。また、接線ベクトルの大きさを必要としないので、人の介入なく自動で補間処理を行うことができる。
【0123】
別の適用例として、CAD/CAM上でモデリングを行うときに、位置のほかその位置における法線を指定する機能の実装に導入することがあげられる。現在CAD/CAMモデルを作成するプロセスでは、位置指定のみを行うのが一般的である。よって、位置情報のみを操作してデザインや仕様の変更を行う必要がある。ここで、位置のみならず法線に対して曲線・曲面を補間することができれば、法線情報を指定する機能を付加することができ、操作可能なパラメータを増やすことができるため、設計の自由度をあげることができる。
【0124】
本発明を用いることで、人の介入なく自動で補間処理を行うことができ、また、曲線・曲面を曲率連続で不必要な振動の少ない高品質なものとすることができる。
【産業上の利用可能性】
【0125】
本発明は、CAD・CAMモデリングの分野、NC加工等に適用することができる。
図面
【図2】
0
【図3】
1
【図4】
2
【図5】
3
【図6】
4
【図7】
5
【図8】
6
【図9】
7
【図12】
8
【図13】
9
【図1】
10
【図10】
11
【図11】
12