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

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

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4934789号 (P4934789)
登録日 平成24年3月2日(2012.3.2)
発行日 平成24年5月16日(2012.5.16)
発明の名称または考案の名称 補間処理方法および補間処理装置
国際特許分類 G06T  15/00        (2011.01)
G06F  17/50        (2006.01)
FI G06T 15/00 100A
G06F 17/50 620A
請求項の数または発明の数 21
全頁数 40
出願番号 特願2007-554883 (P2007-554883)
出願日 平成19年1月15日(2007.1.15)
国際出願番号 PCT/JP2007/050433
国際公開番号 WO2007/083602
国際公開日 平成19年7月26日(2007.7.26)
優先権出願番号 2006014379
優先日 平成18年1月23日(2006.1.23)
優先権主張国 日本国(JP)
審査請求日 平成22年1月12日(2010.1.12)
特許権者または実用新案権者 【識別番号】504182255
【氏名又は名称】国立大学法人横浜国立大学
発明者または考案者 【氏名】前川 卓
【氏名】松本 泰典
【氏名】並木 謙
個別代理人の代理人 【識別番号】100101915、【弁理士】、【氏名又は名称】塩野入 章夫
審査官 【審査官】千葉 久博
参考文献・文献 特開平11-065628(JP,A)
特開平05-035826(JP,A)
調査した分野 G06T 15/00-15/87
G06F 17/50
G06T 19/00,19/20
特許請求の範囲 【請求項1】
制御点により定義される曲線又は曲面によって点群を補間する補間処理方法において、
曲線あるいは曲面上において、制御ポリゴンの制御点の近傍にある点を近傍点として求める幾何アルゴリズムの演算を行う第1の補間工程と、
前記制御点の位置から前記近傍点における法線方向又は前記近傍点から初期ポリゴンへ向かう方向に、前記近傍点と初期制御点との距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行う第2の補間工程とを含み、
前記第1の補間工程は、幾何アルゴリズムの演算により曲線又は曲面上において初期制御点から最短距離にある点を近傍点として求め、
前記演算処理を前記幾何アルゴリズムを組み込んだ演算手段により行うことを特徴とする、補間処理方法。
【請求項2】
前記第1の補間工程は、初期制御点から制御ポリゴンにより定義される曲線あるいは曲面上に垂線を下ろし、当該垂線の曲線あるいは曲面上の垂線の足の位置を近傍点とする幾何アルゴリズムの演算を行い、
前記第2の補間工程は、前記垂線の方向を法線方向とし、前記垂線の足と初期制御点との間の距離を求め、現時点における曲線又は曲面を定義する制御点を曲線又は曲面の法線方向に前記距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行うことを特徴とする請求項1に記載の補間処理方法。
【請求項3】
前記演算処理で得た制御点に基づいて曲線又は曲面を求め、
初期制御点である補間点と前記求めた曲線又は曲面との距離としきい値とを比較し、前記距離がしきい値を満たす、又はしきい値よりも小さくなるまで、前記第1の補間工程と第2の補間工程とを繰り返すことを特徴とする、請求項1又は2に記載された補間処理方法。
【請求項4】
前記しきい値と比較する距離は、各初期制御点における垂線の足と制御点に対応する初期制御ポリゴンである補間点との間の距離の平均自乗距離、又は最大自乗距離であることを特徴とする、請求項に記載の補間処理方法。
【請求項5】
第1回目に行う第1の補間工程及び第2の補間工程において、
前記点群を初期制御ポリゴンとし、当該初期制御ポリゴンを制御ポリゴンとし、前記幾何アルゴリズムの演算を行い、
第2回目以降に行う第1の補間工程及び第2の補間工程において、
補間工程で得た制御点を制御ポリゴンとし、前記幾何アルゴリズムの演算を行うことを特徴とする、請求項1から請求項のいずれかに記載された補間処理方法。
【請求項6】
前記曲面は、B-Spline曲面、三角形メッシュによるLoop細分割、四角形メッシュによるCatmull-Clark細分割、Doo-Sabin細分割の何れかで定められる制御点により定義されることを特徴とする、請求項1から請求項の何れかに記載された補間処理方法。
【請求項7】
前記曲線は、Chaikin細分割又はB-Spline曲線で定められる制御点により定義されることを特徴とする、請求項1から請求項の何れかに記載された補間処理方法。
【請求項8】
制御点により定義される曲線又は曲面によって点群を補間する補間処理装置において、
曲線あるいは曲面上において、初期制御点の近傍にある点を近傍点として求める幾何アルゴリズムにより第1の補間工程を行う第1の幾何演算手段と、
曲線又は曲面を定義する制御点の位置から前記近傍点における法線方向又は前記近傍点から初期ポリゴンへ向かう方向に、前記近傍点と初期制御点との距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムにより第2の補間工程を行う第2の幾何演算手段とを備え、
前記第1の幾何演算手段は、幾何アルゴリズムの演算により曲線又は曲面上において初期制御点から最短距離にある点を近傍点として求め、
前記第1の幾何演算手段及び第2の幾何演算手段は、各幾何アルゴリズムをソフトウエアで実行するためのCPU及び記憶装置、又は各幾何アルゴリズムをハードウエアで実行するための回路を備えることを特徴とする、補間処理装置
【請求項9】
前記第1の幾何演算手段は、初期制御ポリゴンの各初期制御点から制御ポリゴンにより定義される曲線あるいは曲面上に垂線を下ろし、当該垂線の曲線あるいは曲面上の垂線の足の位置を近傍点とする幾何アルゴリズムの演算を行い、
前記第2の幾何演算手段は、前記垂線の方向を法線方向とし、前記垂線の足と初期制御点との間の距離を求め、現時点における曲線又は曲面を定義する制御点を曲線又は曲面から法線方向で前記距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行うことを特徴とする請求項に記載の補間処理装置。
【請求項10】
前記第1の幾何演算手段と第2の幾何演算手段は、
前記演算処理で得た制御点に基づいて曲線又は曲面を求め、
初期制御点である補間点と曲線又は曲面との距離としきい値とを比較し、前記距離がしきい値を満たす、又はしきい値よりも小さくなるまで、前記第1の幾何演算手段と第2の幾何演算手段とを繰り返し行うことを特徴とする、請求項8又は9に記載された補間処理装置。
【請求項11】
前記しきい値と比較する距離は、各初期制御点における垂線の足と初期制御点である補間点との間の距離の平均自乗距離、又は最大自乗距離であることを特徴とする、請求項10に記載の補間処理装置。
【請求項12】
前記第1の幾何演算手段及び第2の幾何演算手段は、第1回目の幾何演算において、点群を初期制御ポリゴンとして入力し、この初期制御ポリゴンを制御ポリゴンとして幾何アルゴリズムの演算を行い、第2回目以降の幾何演算において、補間工程で得た制御点を制御ポリゴンとして幾何アルゴリズムの演算を行うことを特徴とする、請求項8から請求項11のいずれかに記載された補間処理装置。
【請求項13】
前記曲面は、B-Spline曲面、三角形メッシュによるLoop細分割、四角形メッシュによるCatmull-Clark細分割、Doo-Sabin細分割の何れかで定められる制御点により定義されることを特徴とする、請求項8から請求項12の何れかに記載された補間処理装置。
【請求項14】
前記曲線は、Chaikin細分割又はB-Spline曲線で定められる制御点により定義されることを特徴とする、請求項8から請求項12の何れかに記載された補間処理装置。
【請求項15】
制御点により定義される曲線又は曲面によって点群を補間する補間処理方法において、
曲線あるいは曲面上において、初期制御ポリゴンの制御点の近傍にある点を近傍点として求める幾何アルゴリズムの演算を行う第1の補間工程と、
前記制御点の位置から前記近傍点における法線方向又は前記近傍点から初期ポリゴンへ向かう方向に、前記近傍点と初期制御点との距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行う第2の補間工程とを含み、
前記第1の補間工程は、幾何アルゴリズムの演算により曲線又は曲面上において初期制御点から最短距離にある点を近傍点として求める処理であり、
前記演算処理をコンピュータがソフトウエアで実行するための前記幾何アルゴリズムを組み込んだプログラムを記憶したことを特徴とする、プログラム媒体。
【請求項16】
前記第1の補間工程は、初期制御点から制御ポリゴンにより定義される曲線あるいは曲面上に垂線を下ろし、当該垂線の曲線あるいは曲面上の垂線の足の位置を近傍点とする幾何アルゴリズムの演算を行い、
前記第2の補間工程は、前記垂線の方向を法線方向とし、前記垂線の足と初期制御点との間の距離を求め、現時点における曲線又は曲面を定義する制御点を曲線又は曲面から法線方向で前記距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行うことを特徴とする請求項15に記載のプログラム媒体。
【請求項17】
前記第1の補間工程と第2の補間工程は、
前記演算処理で得た制御点に基づいて曲線又は曲面を求め、
初期制御点である補間点と曲線又は曲面との距離としきい値とを比較し、前記距離がしきい値を満たす、又はしきい値よりも小さくなるまで、繰り返して行うことを特徴とする、請求項15又は16に記載されたプログラム媒体。
【請求項18】
前記しきい値と比較する距離は、各初期制御点における垂線の足と初期制御ポリゴンである補間点との間の距離の平均自乗距離、又は最大自乗距離であることを特徴とする、請求項17に記載のプログラム媒体。
【請求項19】
第1回目に行う第1の補間工程及び第2の補間工程、前記点群を初期制御ポリゴンとし、当該初期制御ポリゴンを制御ポリゴンとする幾何アルゴリズムの演算であり
第2回目以降に行う第1の補間工程及び第2の補間工程、補間工程で得た制御点を制御ポリゴンとする幾何アルゴリズムの演算であることを特徴とする、請求項15から請求項18のいずれかに記載されたプログラム媒体。
【請求項20】
前記曲面は、B-Spline曲面、三角形メッシュによるLoop細分割、四角形メッシュによるCatmull-Clark細分割、Doo-Sabin細分割の何れかで定められる制御点により定義されことを特徴とする、請求項15から請求項19の何れかに記載されたプログラム媒体。
【請求項21】
前記曲線は、Chaikin細分割又はB-Spline曲線で定められる制御点により定義されことを特徴とする、請求項15から請求項19の何れかに記載されたプログラム媒体。
発明の詳細な説明 【技術分野】
【0001】
本発明は、点群データを補間して曲線あるいは曲面を生成する補間処理方法、補間処理装置、およびこの補間処理をCPUに実行させるプログラムに関する。また、補間処理方法で得られる細分割曲面ならびにポリゴンメッシュの頂点における微分幾何学的形状を評価する方法、装置、およびこの評価をCPUに実行させるプログラムを記憶するプログラム媒体に関する。
【背景技術】
【0002】
自由曲面は、船、自動車、飛行機等、様々な工業製品のボディに用いられており、機能性と美しさの両方を兼ね備えるものであり、家庭電気製品や多くの消費材の外観など意匠的に美しい形状のデザイン設計に用いられる。
【0003】
近年、3Dレーザスキャナによって高密度の点群データを高速かつ容易に収集することができるようになり、物体形状を高精度で測定できることが可能と成っている。例えば、3Dモデリングの分野においては、デザイナが手作業で作成したモックアップモデルを3Dレーザスキャナで計測し、コンピュータに取り込んだ点群データやポリゴンデータをもとに製品として生産するために必要な曲面データなどのCADデータを作成していくという、いわゆるリバースエンジニアリングの手法が行われている。
【0004】
一般に、3DモデルはポリゴンモデルまたはNURBSやB-Splineなどの曲面パッチによりコンピュータ上で表現される。
【0005】
このポリゴンモデルは位相変化などの形状処理を行う上で効率的であるが、平面で構成されるため滑らかな表面を表現することができず、さらに形状を詳細に表現するほどデータ量が膨大になるなどの問題がある。
【0006】
曲面パッチは少ない制御パラメータで滑らかな曲面が表現できる反面、パッチ形状が四角形に限定される上にパッチ間の連続性を保つことが困難であるなどの問題がある。そこで、ポリゴンモデルと曲面パッチの利点を併せ持つ細分割手法が自由な幾何形状モデリングの有効な手法として注目されており、すでにアニメーションの分野では盛んに利用されている。
【0007】
細分割手法とは、初期ポリゴンメッシュに対して繰り返し規則的な分割を行うことによりその形状を滑らかにし、究極的には滑らかな曲面を得る手法である。その曲面は細分割曲面(Subdivision Surface)または極限曲面と呼ばれる。細分割手法は任意の位相を持つモデルに対しても簡単に滑らかな曲面を生成できるという特徴を持ち、さらにどの部分においても曲面が滑らかなに定義されるためモデリングなど幅広い利用が進んでいる。
【0008】
リバースエンジニアリングの分野において、従来、細分割曲面を用いて測定した点群データを近似あるいは補間して曲面を生成する方法が提案されている。この細分割曲面を用いて点群データを補間する従来提案される方法では、点群データから得られる初期制御点と生成される曲面との距離誤差が最小となるように制御点を逐次求める演算処理を行っている。この制御点を求める演算は、点群の列をS、この点群を近似する曲面と生成するための制御点の列をP、曲面を定める基底関数マトリックスをAとしたとき、AP=Sで表される線形の行列式を解くことで行われる。
【0009】
従来提案されている補間方法として、例えば、Halstedらが提案する多面体メッシュに対するCatmull-Clark細分割曲面の補間手法が知られている(非特許文献1)。この手法は大規模な線形システムを解く必要があるばかりでなく、さらにフェアリングと呼ばれる曲面修正のために最小化問題を解く必要があり、計算コストが嵩む要因となっている。
【0010】
また、Hoppeらは、点群データに対するLoop細分割曲面の近似手法として、細分割操作を行ったポリゴンメッシュを線形近似した細分割曲面とみなし、その曲面に対して各点からの正射影を行うことでパラメータ化し、各点とそれに対する線形近似した細分割曲面上の点との距離が最小となる最小自乗問題として扱う手法を提案している(非特許文献2)。
【0011】

【非特許文献1】M.Halsted.M.Kass,and T.DeRose.Efficient,fair interpolation using Cattmull-Clark surfaces.In Eugene Fiume,editor.Proceedings of SIGGRAPH 1993,pages47-61.ACM,ACM Press / ACM SIGGRAPH, 1993
【非特許文献2】H.Hoppe,T.DeRpse.T.Duehamp,and M.Halsted. Piecewise smooth surface reconstruction.In Proceedings of SIGGRAPH 1994,pages 47-61.ACM,ACM Press / ACM SIGGRAPH, 1994
【非特許文献3】C.T.Loop.Smooth subdivision surface based on triangle.Masters thesis,Department of Mathematics. University of Utha.1987/.
【非特許文献4】E.Catmull and J.Clark. Recusively generated b-spline surfaces on arbitrary topological meshes.Computer-Aided Design,10(6):350-355,1987.
【非特許文献5】D.Doo and M.Sabin. Behavior of recursive division surfaces near extraordinary points.Computer-Aided Design,10(6):356-360,1978.
【非特許文献6】G.M.Chaikin.An algorithim for high-speed curve generation. Computer Graphics and Image Processing,3:346-349,1974.
【非特許文献7】J.Stam.Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values. In Proceedings of SIGGRAPH 1998,pages 395-404.AVM,ACM Press/ACM SIGGRAPH,1998.
【非特許文献8】M.Marinov and L.Kobbbelt, Optimization methods for scattered data approximation with subdivision surface,Graphical Models 67,2005,452-473.
【非特許文献9】R.P.Brent.Algorithims for Minimization without Deriviatives. Prentice-Half,Englewood Cliffts,N.J,1986.4.
【発明の開示】
【発明が解決しようとする課題】
【0012】
上記した、細分割曲面を用いて点群データを補間する従来提案される方法に用いられる演算は行列式を解くといった線形システムの解法であるため、その演算の性質上、点群及び制御点の個数が増加するほど演算回数が増加する。一般に、3Dモデリングに要する点群及びこの点群から形成される制御点の個数は多数であるため、点群から曲面を生成する演算は大規模な線形システムを解く演算となり、多くの計算時間を要するという問題がある。
【0013】
さらに、円滑な曲面を得るには、初期制御点と生成される曲面との距離誤差が最小となるまで、大規模な線形システムを解く演算処理を繰り返す必要があり、所望とする円滑な曲面を得るには多くの時間を要することになる。
【0014】
また、補間処理では補正結果に望ましくない歪みが発生するという問題がある。この歪みを解消するために、非特許文献1ではフェアリングと呼ばれる曲面修正の処理を行っている。このように、従来の補間処理では、補間処理に加えて曲面修正処理が必要となるため処理工程が増えるという問題がある。
【0015】
そこで、点群の補間処理において、多大な演算処理を要さず、また、処理工程を増やすことなく、歪みの少ない補間結果を得ることが望まれる。
【0016】
また、現在、CAD/CAMや、コンピューターグラフィックス(CG)の分野などでは、滑らかな曲面をポリゴンメッシュとして表現する手法が広く用いられている。曲面をポリゴンメッシュに近似することによってコンピューター上での処理が容易になるという利点があり、さらにそのメッシュをFEMへ適用することも可能である。しかしながら、ポリゴンメッシュは点群を線形補間することにより表現されるモデルであるため、B-Splineなどのように微分幾何学を用いて解析的に形状を評価することができない。
【0017】
そこで、本発明は前記した従来の問題点を解決し、点群の補間処理において、多大な演算処理を要さず、また、処理工程を増やすことなく、歪みが少ない補間結果を得ることを目的とする。
【0018】
また、点群を補間する細分割曲面の生成において、短い演算時間で歪みが少ない補間結果を得ることを目的とする。
【0019】
また、線形システムを解くことなく点群を補間する細分割曲面を生成する方法及び装置を提案することを目的とする。
【0020】
また、ポリゴンメッシュの各頂点における微分幾何学的形状を解析的に評価することを目的とする。
【課題を解決するための手段】
【0021】
本発明は、点群から得られる初期ポリゴンを制御ポリゴンとし、この制御ポリゴンの制御点を、この制御ポリゴンで生成される極限曲面と補間点である初期制御ポリゴンとの最短距離だけ法線方向にオフセットすることによって、細分割曲面を初期ポリゴンに補間させる新たな制御点の位置を求めることによって点群を補間する細分割曲面を生成するものであり、各初期制御点と最短距離にある細分割曲面上の点を求める第1の過程と、制御点を曲面から法線方向に曲面上の点と初期制御点との距離だけ移動させてオフセットさせる第2の過程を、はじめの点群と曲面上の点との距離がしきい値を満たすあるいはそれよりも小さくなるまで繰り返すことによって、初期ポリゴンを補間する細分割曲面を生成する。
【0022】
なお、本発明では、入力したポリゴンデータMNΔにより構成される制御ポリゴンを初期制御ポリゴンMNC、オフセットした制御点により構成されるポリゴンを単に制御ポリゴンとし、初期制御ポリゴンの制御点は補間点とも呼ぶことにする。
【0023】
本発明の方法は局所的に各制御点を扱うことになるため、線形システム自体を必要としない上に、幾何学的なプロセスのみで補間曲面を生成することができる。したがって、従来の方法と比べ高速に補間曲面を生成することができる。また、この操作は制御ポリゴンを初期位相に保ったまま拡大する操作であるため、従来の線形システムを解く手法に比べ自然な手法であるため、生成される曲面にゆがみが生じることがなく、高品質な曲面が得られる。
【0024】
なお、本発明は、3次元に限らず2次元についても同様に適用することができ、三次元上の点群を補正する細分割曲面を生成するほか、二次元上の点群を補間する曲線の生成にも適用することができる。
【0025】
また、本発明は、補間処理に関して方法、装置、およびこの補間処理をコンピュータに実行させるためのプログラムを記憶するプログラム媒体の各態様とすることができる。
【0026】
ここでは、主に補間処理方法について示す。補間処理装置は、この補間処理方法をソフトウエアあるいはハードウエアによって実行させるために各手段を備え、また、プログラム媒体は、本発明の補間処理方法をコンピュータに実行させるためのプログラムを記憶するものであるため、ここでは、詳細な説明は省略する。
【0027】
本発明の補間処理方法は、点群を補間し、制御点により定義される曲線又は曲面を生成する補間処理方法において、曲線あるいは曲面上において、初期制御ポリゴンの制御点の近傍にある点を近傍点として求める幾何アルゴリズムの演算を行う第1の補間工程と、現時点における曲線又は曲面を定義する制御点の位置から近傍点における法線方向に向かって、近傍点と初期制御点との距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行う第2の補間工程とを含む。この演算理は幾何アルゴリズムを組み込んだ演算手段により行うことができる。
【0028】
本発明の補間処理方法が備える2つの補間工程において、第1の補間工程は、幾何アルゴリズムの演算により曲線又は曲面上において初期制御点から最短距離にある点を近傍点として求めるものである。
【0029】
この曲線又は曲面上の近傍点は、初期制御点からの距離が最短距離でない点も含むことができ、最短距離にある点に代えて、初期制御点の近傍にある細分割された曲線又は曲面上において任意に定めた点としても良い。ここで、近傍は、細分割された複数の曲線又は曲面の内で初期制御点に近いということを意味し、この近傍にある曲線又は曲面上の点を近傍点としている。この近傍点は最短距離点が望ましいが、かならずしも最短距離である必要はなく、例えば極限曲面あるいは細分割曲面Si上の中心点や重心点等の任意の点としてもよく、曲線の場合には最短距離の他に例えば中間点としてもよい。
【0030】
第1の補間工程は、曲線又は曲面上で近傍点を求める演算処理であり、制御ポリゴンの各初期制御点から曲線あるいは曲面上に垂線を下ろし、この垂線の曲線あるいは曲面上の垂線の足の位置を近傍点とする、幾何アルゴリズムの演算処理である。
【0031】
また、第2の補間工程は、制御点の新たな位置を求める演算処理であり、垂線の足と初期制御点との間の距離を求め、垂線の方向を法線方向とし、現時点における現在の曲線又は曲面を定義している制御点を曲線又は曲面から法線方向に前記距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算である。
【0032】
上記した補間工程により得た制御点を制御ポリゴンの制御点として、新たに曲線又は曲面を求めると、求めた新たな曲線又は曲面上の点は当初の点群に近づき、補間前の曲線又は曲面よりも点群をより正確に補間する。
【0033】
点群と曲線又は曲面との距離を求め、この距離と予め定めたしきい値とを比較し、距離がしきい値を満たす、又はしきい値よりも小さくなるまで、第1の補間工程と第2の補間工程とを繰り返す。しきい値は、点群と曲線又は曲面との間の設定誤差に相当し、点群と曲線又は曲面との距離がこのしきい値を満たす、又はしきい値よりも小さくなった場合には、曲線又は曲面は点群をしきい値で定める許容誤差内にあることが保証される。
【0034】
点群と曲線又は曲面との距離は、各初期制御点における垂線の足と初期制御点との間の距離の平均自乗距離、又は最大自乗距離とすることができる。
【0035】
補間の補間処理において、第1回目に行う第1の補間工程及び第2の補間工程では、点群を初期制御ポリゴンとし、この初期制御ポリゴンを制御ポリゴンとし、幾何アルゴリズムの演算を行い、第2回目以降に行う第1の補間工程及び第2の補間工程では、補間工程で得た制御点を制御ポリゴンとして幾何アルゴリズムの演算を行う。
【0036】
曲面は、B-Spline曲面や、三角形メッシュによるLoop細分割(非特許文献3)、四角形メッシュによるCatmull-Clark細分割(非特許文献4)、Doo-Sabin細分割(非特許文献5)等の再分割等で定められる制御点により定義することができる。
【0037】
また、曲線については、B-Spline曲線や、Chaikin細分割(非特許文献6)で定められる制御点により定義することができる。なお、Chaikin細分割は2次のB-Spline曲線に収束し、一般的にn次のB-Splien曲線についても補間を行うことができる。
【0038】
本発明のポリゴンメッシュの各頂点における微分幾何学的形状の解析的な評価は、最大主曲率κ1や最小主曲率κ2、細分割曲面の主方向を曲面の形状を評価する評価値とする。
【0039】
最大主曲率κ1や最小主曲率κ2は、パラメータで表される細分割曲面のパラメトリック曲面r(u,v)上において、曲面r(u,v)の任意のパラメータu,vについて導関数ru、rv、ruu、uv、rvvを求める演算と、求めた導関数を用いてE=ru・ru、F=ru・rv、G=rv・rv、L=ruu・N、M=ruv・N、G=rvv・Nを求める演算と、最大主曲率κ1=H+(H2-K)1/2、及び/又は、最小主曲率κ2=H-(H2-K)1/2を求める演算を、プログラム又は演算回路で実行することで得ることができる。なお、ここでKはガウス曲率、Hは平均曲率である。
【0040】
また、3次元空間における細分割曲面の主方向は、曲面r(u,v)のuv平面おける最大、最小主曲率κ1又はκ2を、p=(ru+λrv)/(|ru+λrv|)の中のκに代入してuv平面から3次元空間への変換処理を、プログラム又は演算回路で実行することで得ることができる。
【0041】
本発明のポリゴンメッシュの各頂点における微分幾何学的形状の解析的な評価によれば、従来法よりも高精度に評価することができる。
【発明の効果】
【0042】
以上説明したように、本発明によれば、点群の補間処理において、多大な演算処理を要さず、また、処理工程を増やすことなく、歪みが少ない補間結果を得ることができる。
【0043】
また、本発明によれば、線形システムを解くことなく点群を補間する細分割曲面を生成することができる。
【0044】
また、本発明によれば、ポリゴンメッシュの各頂点における微分幾何学的形状の解析的の評価を高精度で行うことができる。
【図面の簡単な説明】
【0045】
【図1】本発明の補間処理の概略を説明するための概略図である。
【図2】本発明の補間処理の概略を説明するためのフローチャートである。
【図3】本発明の補間処理の第1、第2の補間工程を説明するための図である。
【図4】本発明の補間処理装置の概略構成図である。
【図5】二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を説明するためのフローチャートである。
【図6】二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を説明するための制御点と曲線との概略図である。
【図7】二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を説明するための制御点と曲線との概略図である。
【図8】二次元の点群を補間する曲線例を示す図である。
【図9】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するためのフローチャートである。
【図10】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図11】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図12】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図13】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図14】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図15】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図16】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図17】オフセットごとのニュートン法の繰り返し回数に対する頂点数のヒストグラムである。
【図18】一モデルにおけるオフセット回数に対する誤差の変化を示す図である。
【図19】562点のbunnyモデルの例である。
【図20】本発明の補間処理結果の一例を示す図である。
【図21】本発明の補間処理結果の一例を示す図である。
【図22】本発明の補間処理結果の一例を示す図である。
【図23】補間結果例を示す図である。
【図24】本発明による補間頂点数に対する計算時間を示す図である。
【図25】本発明の補間処理によって求めた法線ベクトルのオフセットごとの誤差を示す図である。
【符号の説明】
【0046】
1…入力手段
2…記憶手段
2a…データ記憶部
2b…演算ツールプログラム記憶部
2c…演算処理プログラム記憶部
2d…一次記憶部
2e…演算結果記憶部
3…演算手段
4…表示手段
5…出力手段
【発明を実施するための最良の形態】
【0047】
以下、本発明の実施の形態について、図を参照しながら詳細に説明する。
【0048】
図1,図2,図3は、本発明の補間処理の概略を説明するための概略図、フローチャート、第1、第2の補間工程を説明するための図であり、図4は本発明の補間処理装置の概略構成図である。
【0049】
図1,図2、は、点群PNから極限曲面Sを求める手順を概略的に示している。なお、ここでは、3Dレーザスキャナ(3次元形状測定機)等から得られた高密度・不規則な点群データ(点群PN)から開始し、この点群PNを補間する最終的な極限曲面Sを得る手順によって示しているが、点群PNから得られたポリゴンメッシュから開始して極限曲面Sを得る手順としてもよい。これは、本発明の補間処理が、微分幾何学の演算装置によって計算された法線からポリゴンの制御点を修正し、修正した制御ポリゴンから極限曲面Sを得る処理であり、点群PNから得られたポリゴンメッシュから開始することができるからである。
【0050】
ここでは、入力したポリゴンデータMNΔにより構成される制御ポリゴンを初期制御ポリゴンMNC、オフセットした制御点により構成されるポリゴンを単に制御ポリゴンとし、また、初期制御ポリゴンの制御点を補間点とも呼ぶ。
【0051】
なお、ここでは、主に曲面について説明するが、曲線についても同様に扱うことができる。
【0052】
はじめに、3Dレーザスキャナ等によって与えられた点群PNを用いてメッシュ化してポリゴンメッシュを生成する。ポリゴンメッシュは、三角形ポリゴンメッシュや四角形ポリゴンメッシュを用いることができる。このメッシュ化の処理は既存の手法を用いることができる。ここでは、三角形ポリゴンメッシュMNΔを用いて説明する(S1)。
【0053】
この三角形ポリゴンメッシュMNΔを初期制御ポリゴンメッシュMNCとして制御点を定める(S2)。この初期制御ポリゴンメッシュMNCを用いて細分割処理を行って初期メッシュに基づいて極限曲面S0を生成する(S3)。S3で生成した初期メッシュに基づいて極限曲面S0に補間処理を施し、制御点の位置をオフセットして修正し(S4)、修正した制御点の位置に基づいてi回目の制御メッシュに基づいて細分割曲面Siを生成する(S5)。
【0054】
生成した細分割曲面Siと初期制御ポリゴンメッシュMNCとを比較し、対応する点間の距離の誤差が収束するまでS4の補間工程を繰り返す。この収束は、距離誤差があらかじめ設定しておいたしきい値を満たすまでS4の補間工程を繰り返す(S6)。
【0055】
補間処理によって距離誤差が収束したときに得られる極限曲面Sは、初期制御ポリゴンメッシュMNCを補間する細分割曲面となる(S7)。
【0056】
S4の補間処理は2つの補間工程S4aとS4bと備える。第1の補間工程S4aでは、制御点から極限曲面あるいは細分割曲面Si上の近傍点を求める。この近傍点は、ある初期制御点の近傍にある極限曲面あるいは細分割曲面Si上にある点であり、例えば極限曲面あるいは細分割曲面Si上において、初期制御点からの距離が最短となる最短距離点として定めることができる。
【0057】
なお、近傍点は最短距離点が望ましいが、かならずしも最短距離である必要はなく、例えば極限曲面あるいは細分割曲面Si上の中心点や重心点等、任意の点としてもよい。曲線の場合には、最短距離の他に例えば中間点としてもよい。
【0058】
ポリゴンメッシュを十分に小さく設定した場合には、多くの場合、最短距離にある点から中心点や重心点との誤差はわずかとなり、近傍点が最短距離の点からずれることにより生じる誤差はわずかと推定される。
【0059】
図3(a)は第1の補間処理S4aの工程を説明するための図であり、図3(b)は第2の補間処理S4bの工程を説明するための図である。なお、図3では二次元上で示している。また、図3では、シフト前の制御点をPa、シフト後の制御点をPbで示し、曲線C上で求めた近傍点をFで示している。
【0060】
図3(a)に示す第1の補間処理S4aの工程において、はじめに初期制御点Paが与えられているとする。なお、第1回目の補間処理では、制御点Paは点群PNから得られる初期ポリゴンメッシュMNCの制御点であり、第2回目の補間処理では、前回の補間処理によって位置がシフトされた制御ポリゴンの制御点である。
【0061】
この制御点Paを用いて細分割を行うことによって細分割曲面S0が生成される。なお、最初に生成される極限曲面は極限曲面S0であり、2回目以降に生成されるi回目の極限曲面は極限曲面Siである。
【0062】
極限曲面(S0,S1,…Si,…)において、初期制御点Paに対応する近傍点Fを求める。近傍点Fは、初期制御点Paから極限曲面(S0,S1,…Si,…)上に垂線を下ろし、その垂線の足の点とすることができる。
【0063】
次に、図3(b)に示す第2の補間処理S4bの工程において、初期制御点Paの位置をシフトして新たな位置に制御点Pbを求める。制御点Pbの新たな位置は、初期制御点Paと近傍点Fと距離だけ、初期制御点Paの位置から所定方向に向かってオフセットさせた位置である。この所定方向は、例えば近傍点Fにおける法線方向とすることができる。図3(b)において、極限曲面から初期制御点Paへの距離ベクトルをVdで表し、初期制御点Paから制御Pbへ位置をオフセットさせるアップデートをVuで表し、極限曲面上の近傍点Fにおける法線をNで表している。
【0064】
図中において、ベクトルVu+は、N・Vd>0のとき法線Nの正方向に制御点の位置をオフセットし、ベクトルVu-は、N・Vd<0のとき法線Nの負方向に制御点の位置をオフセットする。また、方向を含むアップデートベクトルは、
JP0004934789B2_000002t.gifで表される。
【0065】
補間工程S4は、この第1の補間工程S4aと第2の補間工程S4bを繰り返して行われる。この第2の補間工程S4bで得られた制御点Pを用いることで、前記したS5の工程によって制御ポリゴンメッシュMNCを細分割して極限曲面iを生成する。
【0066】
この曲面の細分割処理として、例えば、三角形メッシュによるLoop細分割、四角形メッシュによるCatmull-Clark細分割、Doo-Sabin細分割等を用いることができ、また、B-Spline曲面についても適用することができる。
【0067】
曲線の細分割として、例えば、Chaikin細分割を用いることができる他、n次のB-Spline曲線についても適用することができる。なお、Chaikin細分割は2次のB-Spline曲線に収束する。
【0068】
本発明の補間によれば、計算コスト、曲面品質、演算の一般性の点で以下の利点がある。
【0069】
本発明の補間のアルゴリズムは、初期ポリゴンと補間して得られた曲面との距離を算出する幾何学的演算、及び、制御点の位置をオフセットする幾何学的演算である。幾何学的演算であるため、計算コストは、補間頂点数N、オフセット回数MによるO(MN)である。一方、従来の線形システムによる計算コストは、補間頂点数Nに対して指数のオーダーで増加する。通常、M≪Nであるため、本発明の補間によれば、計算コストの増加率は従来の方法より大幅に低減させることができ、計算速度の点から見ると、非常に高速な補間曲面の生成が可能となる。
【0070】
本発明の補間のアルゴリズムは、他の補間手法のように生成した補間曲面にうねりが生じることがない。
【0071】
また、本発明の補間のアルゴリズムは、単純な幾何プロセスにより曲面生成を行っており、分割曲面のみならず、B-Spline曲面や曲線など、制御点により定義される曲線、曲面に対して適用することができ、曲面生成について一般性を有する。
【0072】
図4は、本発明の補間処理のソフトウエアを記憶したプログラムをコンピュータで実行させる場合の一構成例を示している。
【0073】
入力手段1は、点群PNのデータ、あるいは点群PNから生成される制御ポリゴンメッシュMNΔを入力し、記憶手段2中のデータ記憶部2aに記憶する。記憶手段2は、データ記憶部2aの他に、微分幾何学演算を行う演算ツールのプログラムを記憶する演算ツールプログラム記憶部2b、補間処理の微分幾何学演算の他、細分割処理等の演算処理のプログラムを記憶する演算処理プログラム記憶部2c、途中演算結果等を一時的に記憶する一次記憶部2d、補間処理等によって得られた曲面の演算結果を記憶する演算結果記憶部2e等を備える。
【0074】
演算手段3は、データ記憶部2aに記憶された点群PNあるいは制御ポリゴンメッシュMNΔのデータを用い、演算処理プログラム記憶部2cに記憶されるプログラムによる演算手順に従い、また、このプログラムに指定される演算ツールのプログラムを演算ツールプログラム記憶部2bから逐次読み出して演算処理を行う。
【0075】
演算結果記憶部2eに記憶された演算結果は、読み出されて表示手段4に表示したり、出力手段5に出力される。出力手段5は、演算結果を記録媒体に記録する記録装置、例えば加工装置等の演算結果を用いて所定動作を行う外部装置等とすることができる。
【0076】
なお、上記、ソフトウエア処理を行う構成は、専用のソフトウエア処理装置や、通常のパーソナルコンピュータに適用することができる。
【0077】
また、上記構成において、記憶手段を含む演算手段で実施される機能を回路で構成することでハードウエアにより実施することもできる。
【0078】
次に、本発明の補間処理の詳細について、二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合と、三次元の点群あるいは制御ポリゴンメッシュにより曲面を生成する場合について説明する。
【0079】
以下、はじめに、二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を、図5のフローチャート,図6,7の制御点と曲線との概略図、図8の曲線の補間例の図を用いて説明し、次に、三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を、図9のフローチャート,図10~図16の制御点と曲線との概略図を用いて説明する。
【0080】
はじめに、二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合について説明する。なお、以下のフローは一例であり、本発明の第1の補間処理及び第2の補間処理を実施する工程及び手順であれば他のフローで構成としてもよい。
【0081】
点群PNから二次元の制御ポリゴンを取得する。なお、予め求めて記憶手段に記憶しておいた二次元の制御ポリゴンを読み出しても良い。(S11)。図6(a)はS11の状態を示している。取得した制御ポリゴンを初期制御ポリゴンPiとして記憶部2aに記憶し(S12)、この初期制御ポリゴンPiを制御点Pk-1iとして記憶する(S13)。記憶した制御点Pk-1iを用いて細分割処理を行い、曲線Cを生成する。ここで上付き文字k-1はオフセットの繰り返し回数である。細分割処理は、例えばB-Spline曲線補間を用いることができる。この細分割処理は、演算処理プログラム記憶部2cから演算処理プログラムを読み出すと共に、この演算処理プログラムに演算ツールが記述されている場合には、演算ツールプログラム記憶部2bに記憶される演算ツールを用いて、制御点Piを用いて微分幾何学演算を実行する。図6(b)はS14の状態を示している。
【0082】
以下、S15,S16の第1の補間処理とS17~S19の第2の補間処理を繰り返して、点群を補間する曲線Cを生成する。
【0083】
第1の補間処理において、初期制御ポリゴンの初期制御点Piから曲線C(S14の工程で生成した曲線C、あるいはS20の工程で生成した曲線C)上に垂線を下ろし垂線の足fkiを求め(S15)、初期制御点Piと垂線の足fkiとの間の距離∥Pi-fki∥を求める。求めた垂線の足fkiは、曲線C上における初期制御点Piの近傍点である。垂線及び距離を求める演算は、幾何学演算によって求めることができる(S16)。図6(c)は、はじめての補間処理において初期制御ポリゴンPiを制御ポリゴンとしたときのS15,S16の状態を示し、図7(b)は二回目以降の補間処理におけるS15,S16の状態を示している。
【0084】
なお、垂線は初期制御点から曲線または曲面へ下ろし、最初に垂線を下ろすときだけ、曲線または曲面を定義する制御点と、垂線を下ろす初期制御点が同じものとなる。
【0085】
次に、第2の補間処理において、曲線C上の垂線の足fkiでの法線を求め(S17)、求めた法線方向へ、S16で求めた初期制御点Piと垂線の足fkiとの間の距離∥Pi-fki∥だけ、現在の曲線を定義している制御点Pk-1iの位置をオフセットし(S18)、オフセットした位置を制御点Pk-1iの新たな位置とする。法線を求める演算、及び制御点の位置をオフセットする演算は、微分幾何学演算によって求めることができる(S19)。図6(d)は、はじめての補間処理において初期制御ポリゴンPiを制御ポリゴンとしたときのS17~S19の状態を示し、図7(c)は二回目以降の補間処理におけるS17~S19の状態を示している。
【0086】
S19で得た制御点Pk-1iの新たな位置に基づいて細分割処理を行って曲線Cを生成する(S20)。図7(a)は、はじめての補間処理において初期制御ポリゴンPiを制御ポリゴンとしたときのS20の状態を示している。
【0087】
S20で求めた曲線Cと初期制御ポリゴンPiとの距離を求め、求めた距離が予め定めたしきい値とを比較し、距離がしきい値を満たす、あるいはしきい値以下となるまで、前記S15~S21の工程を繰り返す。図7(d)は、二回目以降の補間処理におけるS20の状態を示している。
【0088】
S21で求めた曲線Cと初期制御ポリゴンPiとの距離は、点群を補間する曲線と点群との誤差を表しており、しきい値は点群を補間する曲線に対して許容することができる許容誤差に相当する。
【0089】
点群と曲線又は曲面との距離は、各初期制御点における垂線の足と初期制御点との間の距離の平均自乗距離、又は最大自乗距離とすることができる。
【0090】
したがって、S22の比較工程において、距離がしきい値以下となったことを確認することで、得られた曲線Cは点群を許容誤差範囲内で補間するものとなる(S23)。
【0091】
本発明による補間のアルゴリズムは優れた収束性を有しており、2,3回の補間処理で制御点をオフセットすることより高精度な補間曲線を生成することができる。なお、尖った形状などでは滑らかな部分に比べ収束が遅くなる傾向がある。そのような部分に対しては全体のオフセットにより補間曲線を生成した後、収束が遅い頂点のみ選び出して、局所的にオフセットを繰り返すことにより高精度の補間曲線へと仕上げることができる。
【0092】
図8は、二次元(平面)の曲線補間の一例であり、人のシルエットの点群を補間する曲線を生成した一例である。図8(a)は全体図を示し、図8(b)は一部拡大図を示している。図8において、点は点群を示し、曲線はこの点群を補間している。また、直線は、曲線を生成する制御点を結んでいる。
【0093】
次に、三次元の点群あるいは制御ポリゴンメッシュにより曲面を生成する場合について説明する。なお、以下のフローは一例であり、本発明の第1の補間処理及び第2の補間処理を実施する工程及び手順であれば他のフローで構成としてもよい。
【0094】
補間のアルゴリズムの流れは、与えられた任意形状をもつ三角形ポリゴンメッシュを初期制御ポリゴンとして、それから生成される極限曲面を得る。次に、初期制御点から制御ポリゴン(1回目は初期制御点、2回目以降はオフセットした制御点)より生成される極限曲面に垂線を下ろし最短距離を測り、さらに極限曲面上の垂線の足における法線を求め、初期制御点と極限曲面との最短距離だけ法線方向ヘオフセットする。この工程を繰り返すことにより、極限曲面を初期制御ポリゴンヘ補間させる制御点位置を求める。
【0095】
図9のフローチャートにおいて、点群PNから三次元の制御ポリゴンMNΔを得する。なお、予め求めて記憶手段に記憶しておいた三次元の制御ポリゴンMNΔを読み出しても良い。三次元の制御ポリゴンとしては、例えば、三角形ポリゴンメッシュや四角形ポリゴンメッシュを用いることができ、三角形ポリゴンメッシュの細分割手法としてはLoop細分割(非特許文献3)が知られ、四角形メッシュの細分割手法としてはCatmull-Clark細分割(非特許文献4)、Doo-Sabin細分割(非特許文献5)等が知られている(S31)。
【0096】
図10(a)はS31の状態を示している。取得した制御ポリゴンMNΔを初期制御ポリゴンMNCとして記憶部2aに記憶し(S32)、この初期制御ポリゴンメッシュMNCを制御点Pk-1iとして記憶する(S33)。
【0097】
記憶した制御点Pik-1を用いて細分割処理を行い、極限曲面S0を生成する。ここで最初に垂線を下ろすときはPik-1=Piとなる。細分割処理は、例えば三角形ポリゴンメッシュの場合には前記したLoop細分割補間を用いることができる(S34)。図10(a)はS34の状態を示している。この細分割処理は、演算処理プログラム記憶部2cから演算処理プログラムを読み出すと共に、この演算処理プログラムに演算ツールが記述されている場合には、演算ツールプログラム記憶部2bに記憶される演算ツールを用いて、初期制御点Piを用いて微分幾何学演算を実行する。図10(b)はS35の状態を示している。
【0098】
以下、S35,S36の第1の補間処理とS37~S39の第2の補間処理を繰り返して、点群を補間する曲面Siを生成する。
【0099】
第1の補間処理において、初期制御点Piから曲面S(S34の工程で生成した場合には曲面S0、あるいはS40の工程で生成した制御点Pk-1iにより定義される曲面Si)上に垂線を下ろし垂線の足fkiを求める。なお、最初に垂線を下ろすときのみPi=Pk-1iとなる(S35)。初期制御点Piと垂線の足fkiとの間の距離∥Pi-fki∥を求める。求めた垂線の足fkiは、曲面S(S0,Si)上における初期制御点Piの近傍点である。垂線及び距離を求める演算は、幾何学演算によって求めることができる(S36)。図10(b)は、補間処理において垂線及び距離を求める演算のS35,S36の状態を示している。
【0100】
なお、前記した二次元での第1の補間処理と同様に、垂線は初期制御点から曲線または曲面へ下ろす。最初に垂線を下ろすときだけ、曲面を定義する制御点と、垂線を下ろす初期制御点が同じものとなる。
【0101】
次に、第2の補間処理において、曲線曲面S(S0,Si)上の垂線の足fkiでの法線を求め(S37)、求めた法線方向へ、S36で求めた初期制御点Piと垂線の足fkiとの間の距離∥Pi-fki∥だけ、現在の極限曲面を定義する制御点Pk-1iの位置をオフセットし(S38)、オフセットした位置を制御点Pk-1iの新たな位置とする。
【0102】
法線を求める演算、及び制御点の位置をオフセットする演算は、微分幾何学演算によって求めることができる(S39)。図10(c)は、補間処理において制御点Pk-1iの位置をオフセットし、オフセットした位置を制御点Pk-1iの新たな位置とするS37~S39の状態を示している。
【0103】
S39で得た制御点Pk-1iの新たな位置に基づいて細分割処理を行って曲面Siを生成する(S40)。図10(d)は、初期制御ポリゴンPiを制御ポリゴンとしたときのS40の状態を示している。
【0104】
S40で求めた曲面Siと初期制御ポリゴンPiとの距離を求め、求めた距離が予め定めたしきい値とを比較し、距離がしきい値を満たす、あるいはしきい値以下となるまで、前記S35~S41の工程を繰り返す。
【0105】
S41で求めた曲面Siと初期制御ポリゴンPiとの距離は、点群を補間する曲面と点群との誤差を表しており、しきい値は点群を補間する曲面に対して許容することができる許容誤差に相当する。
【0106】
点群と曲線又は曲面との距離は、各初期制御点における垂線の足と制御点に対応する点との間の距離の平均自乗距離、又は最大自乗距離とすることができる
【0107】
したがって、S42の比較工程において、距離がしきい値以下となったことを確認することで、得られた曲面Siは点群(初期制御ポリゴン)を許容誤差範囲内で補間するものとなる(S43)。
【0108】
上記した第1の補間処理について、図11~図16を用いてより詳細に説明する。
【0109】
前記したように、第1の補間処理では、初期制御点Piから極限曲面Sへ垂線を下ろすことで初期制御点Piと極限曲面Sとの最短距離を求める。この最短距離の演算は、制御点から極限曲面上への正射影の計算に相当する。この計算には当たり、Stamの理論(非特許文献7)を適用することができる。このStamの理論では、パラメータ領域となる三角形パッチに属する特異点の数が高々1つでなければならない。なお、特異点を含まない正則な曲面は12個の制御点により定義される。
【0110】
図11は、特異点を備える三角形パッチの細分割処理を説明するための図である。図11(a)は2個の特異点(図中のA,B)を含む三角形パッチを示している。
【0111】
ここで、三角形パッチに属する特異点の数を高々1つとするために、対象となる制御点まわりのポリゴンに対して局所的にLoop細分割手法を1回適用する。図11(b)は、対象となる制御点について1回の細分割した三角形パッチを示し、図11(c)~図11(f)は、この細分割により生成される4つの細分割パッチを示している。この4つの細分割パッチの内で、図11(c),図11(d)に示す細分割パッチは1つの特異点を有し、図11、(e),図11(f)に示す細分割パッチは特異点を有していない。
【0112】
したがって、対象となる制御点まわりのポリゴンに対して局所的にLoop細分割手法を1回適用することによって、パラメータ領域となる三角形パッチに属する特異点の数を高々1つとすることができる。
【0113】
対象となる制御点の位数(valence)がNの場合、その制御点周りのLoop細分割パッチもN個であり、最初にその中から垂線を下ろす極限曲面を生成する三角形パッチ(以後パラメータ領域と呼ぶ)を選び出す必要がある。しかしながら、前もってそのパラメータ領域を選ぶことは困難である。
【0114】
ここでは、Half-Edge構造体を利用して、その制御点から最初に参照される面のLoop細分割パッチにおいて制御点に最も近いパラメータ領域とする。なお、Half-Edge構造体は、頂点(Vertex)、稜線(Edge)、面(Face)により構成されるポリゴンメッシュの要素を効率的に扱うためのデータ構造の一つであり、一般的に面(Face)、稜線(Edge)、半稜線(Half-Edge)、頂点(Vertex)、ループ(Loop)の5種類のデータ構造からなるソリッドモデル用データ構造である。なお、Half-Edge構造体は5種類のデータ構造の他に、ループや稜線のデータ構造を含まない構造とするものもある。このデータ構造では、1本の稜線に対して向きの異なる1対の半稜線(Half-Edge)を定義し、この半稜線により稜線の両端の頂点や稜線を挟む面のデータを効率的に扱うことができる。
【0115】
図12において、黒丸で示す点は初期制御点(補間点)、この制御点を通る太い実線は制御点周りにおける分割前のポリゴン、細い実線および破線は1回細分割を行ったポリゴンを示している。また、薄い地模様の部分は垂線が下りる極限曲面パッチを生成し得る細分割パッチ(パラメータ領域)、濃い地模様の部分は制御点からHalf-Edge構造体を利用して最初に参照される面における細分割パッチを示している。図12(b)において、濃い地模様で示される細分割パッチ上の白抜きの点は初期値となるパラメータ位置を示している。
【0116】
つまり、初期制御ポリゴンに対して1回Loop細分割手法を適用して得られる細分割パッチにおいて、対象となる頂点に近い局所的な細分割パッチから構成される制御ポリゴンによって生成される極限曲面パッチヘ垂線を下ろすことになる。
【0117】
次にパラメータ領域において垂線の足となる点を求める。図13は、パラメータ領域に対する垂線を説明するための図である。図13において、Tpは接平面、Pは初期制御ポリゴンの頂点、D(v,w)はパラメータ(v,w)における極限曲面上の点、(Δv,Δw)は曲面のアップデートパラメータ、iは制御点番号、jはニュートン法の繰り返し回数をそれぞれ示している。
【0118】
1つの制御点から極限曲面への垂線は次式により与えられる。
[(P-D(v,w))・Dv (v,w)]=0
[(P-D(v,w))・Dw (v,w)]=0 …(1)
【0119】
なお、vとwは曲面のパラメータであり、Dv、Dwは細分割曲面Dのv、w方向の微分を示している。
【0120】
各制御点Pから、それらによって張られる細分割曲面D上の最短距離となる点は、Marinov and Kobbelt(非特許文献7)によると、Pから接平面への垂線は曲面のパラメータ(Δv、Δw)に関する以下の線形システムを解くことにより求めることができる。
[P-(D(v,w)+Dv(v,w)Δv+Dw(v,w)Δw)]・Dv(v,w)]ij=0
[P-(D(v,w)+Dv(v,w)Δv+Dw(v,w)Δw)]・Dw(v,w)]ij=0 …(2)
【0121】
ここで、iは制御点番号、jはパラメータ化におけるニュートン法の繰返し回数である。また、式(2)は線形であるため、次のように(△v,△w)について解くことができる。
Δv=
[(P-Dv(v,w))・Dw(v,w) Dv(v,w)・Dv(v,w)-(P-Dv(v,w))・Dv(v,w)Dw(v,w)・Dw(v,w)]/Det
Δw=
[(P-Dv(v,w))・Dw(v,w) Dv(v,w)・Dw(v,w)-(P-Dv(v,w))・Dw(v,w)Dv(v,w)・Dv(v,w)]/Det
…(3)
【0122】
JP0004934789B2_000003t.gif
【0123】
式(3)について、(△v,△w)→(0,0)となるようにニュートン法で逐次パラメータ修正を行う。
【0124】
また、2回目のニュートン法の初期値はそのパラメータ領域の重心におけるパラメータとし、2回目以降の計算では初期値は前回の計算で垂線の足となる極限曲面上のパラメータとした。したがって、2回目以降の計算は新たにパラメータ領域を探す必要もなく初期値も近傍点のパラメータに近いため、さらに高速に垂線を下ろすことができる。
【0125】
ここで、Marinov and Kobbelt(非特許文献7)によると、MarinovとKobbelt[19]によると、パラメータ(△v,△w)に関して次の3つの場合わけを考慮する必要がある。
【0126】
1.パラメータ(v+△v,w+△w) ijが同じパラメータ領域内にあるとき、その領域内でニュートン法を繰り返す。
2.パラメータ(v+△v,w+△w) ijが前回計算したパラメータ領域に隣接する別のパラメータ領域にあるとき、0<λ<1となる係数λにより(△v,△w) ijをスケーリングすることで、(v+λ△v,w+λ△w) ijを現在のパラメータ領域の境界上に置く。これは次のニュートン法のアップデートベクトル(v+λ△v,w+λ△w) ij+1が前回のアップデートベクトルと同じ方向を向くか、反対の方向を向くかを予測することは困難だからで
ある。
3.すでにパラメータ(v+λ△v,w+λ△w) ijが境界上にあり、隣接するパラメータ領域に属しているときはその領域内でニュートン法を行う。
【0127】
通常、ニュートン法によりパラメータ修正を行うことで収束へ向かえば初期制御点と曲面との距離が小さくなるが、期待するパラメータヘ向かわない場合がある。つまり、∥Pi-D(v,w) ij+1∥>∥Pi-D(v,w) ij∥となることがある。このような場合、通常はパラメータ修正におけるアップデートベクトルの長さが正しくないことを意味しており、これは多変数関数の根を求めるアルゴリズムにおいて共通した挙動である。ロバストな方法でこのような状況を扱うために、ここでは信頼性が高い単変数の最適化手法であるBrent法(非特許文献8)により、初期制御点と曲面との距離関数g(h)=∥Pi-D(v,w) ij+1+hqi,j∥,h∈(0,1)において最小のhを求める。ここでqi,j∥=(Δv,Δw)ijである。最終的に、Brent法により求まるhによりパラメータは(v+hΔv,w+hΔw) ijとなる。
【0128】
ここで、パラメータ修正の具体的な例について言及する。はじめに、各細分割パッチにおける面積座標系の定義について説明する。図14は細分割パッチ上の面積座標系を示している。図14において、パラメータ領域となる細分割パッチを示し、斜線を施した頂点(最外郭にある3つの頂点)が頂点分割により生成される点(vertex point)であり、白抜きの頂点(大きな三角形の辺上にある頂点)が面分割により生成される(edge point)点である。斜線を施した頂点は分割前の位数を保持するため特異点となることがあるが、白抜きの頂点は位数6の正則点となる。Stamの理論を用いるにあたり、特異点における面積座標(barycentric coordinate)をu=1.0と定めるため、このアルゴリズムにおいてはHalf-Edge構造体との兼ね合いもあり、図14に示すように定義している。また、このような領域の順序付けはパラメータ修正ごとに行うものではなく、あらかじめ各面において行っている。
【0129】
はじめに、同じ面内における移動について説明する。
【0130】
図15(a),(b)は対象となる制御点が特異点である場合について、1つの面が定義するパラメータ領域間の移動について示したものである。
【0131】
図15(a)において、ニュートン法の初期値は対象となる制御点に最も近いパラメータ領域(図中(a))としている。各パラメータ領域(a)~(d)の面積座標系は図14に示したとおりである。
【0132】
パラメータ領域(a)におけるニュートン法でu<0.0、つまりv+w>1.0となったときの領域(a)から領域(d)へのパラメータ領域の変更を示している。例えば、v<0.0となった場合は向かって右側の隣接面の定義するパラメータ領域に、w<0.0となった場合は向かって左側の隣接面の定義するパラメータ領域に変更する。さらに、パラメータ領域(d)のニュートン法においてu<0.0となれば領域(c)へ、w<0.0となれば、領域(d)へさらにパラメータ領域が変更される。
【0133】
次に、特異点を共有する隣接面への移動について説明する。図15(c),(d)は対象となる制御点が特異点かつ隣接面の定義するパラメータ領域へ変更する場合を示している。
【0134】
パラメータ領域(a)におけるニュートン法でv<0.0となった場合、図15(c)のように向かって右側の隣接面の定義するパラメータ領域へ変更する。ここで、前回ニュートン法を行ったパラメータ領域を定義する面と移動先の隣接面が同じ特異点を共有している場合は、隣接面のパラメータ領域(a),(b),(c),(d)は一意的に決定する。
【0135】
次に、共有する特異点以外にも特異点を含む隣接面への移動について、図16(a),(b)を用いて説明する。
【0136】
図16(a),(b)に示すように、移動先の隣接面が移動前の面と共有する特異点以外にも特異点を持つ場合、移動先の隣接面のパラメータ領域は一意的に決定することはできない。
【0137】
パラメータ領域の順序付けはあらかじめ行われており、例えば、特異点が2つある場合には図16(c),(d)のように2通りの順序付けが考えられる。この2つの順序付けではパラメータ領域(d)の面積座標系が異なってしまうため、移動先のパラメータ領域がどのように順序付けされているかを判別する必要がある。
【0138】
上記した処理を含めた、近傍点を求める第1の補間処理は、以下のアルゴリズムとなる。
【0139】
ステップ1:制御点から極限曲面へ垂線を下ろすにあたり、あらかじめどの曲面パッチに垂線が下りるか予測できないため、初期パラメータ領域をHalf-Edgeより最初に参照される面と仮定し、その面に対して細分割を適用することによりパラメータ領域(細分割パッチ)を定義する。また、Half-Edgeのループ方向に従い、パラメータ領域の順序付けを行う(図14)。
ステップ2:ニュートン法の初期値として、対象とする制御点に最も近いパラメータ領域の重心におけるパラメータを選ぶ(図12(b))。
ステップ3:各パラメータ領域においてパラメトリック曲面を定義するための制御点を選び出す。図11(c)~(f)に示すように4つの制御ポリゴンを定義する(図は特異点が2つある場合の例を示している)。
ステップ4:Stamの理論より現在のパラメータにおける曲面上の位置や微分量を計算し、それらをもとに式(3)に従ってニュートン法によりパラメータのアップデート量(△v,△w)を求め、新たなパラメータ(v,w)を算出する。
ステップ5:アップデートベクトル(△v,△w)がしきい値内に収束すれば、そのパラメータにおける曲面上の点を初期制御点からの近傍点とみなし終了する。収束しなければステップ6以降を行う。
ステップ6:前回のパラメータにおける曲面上の位置とアップデート後の位置を比較し、初期制御点との距離が大きくなった場合、Brent法により補正を行う。
ステップ7:もしアップデートによりパラメータ(v,w)がパラメータ領域から外へ出た場合には、例えば、現在属する面が定義する別のパラメータ領域へ移動、現在属する面の隣接面が定義するパラメータ領域へ移動等の他のパラメータ領域への移動を行う。
ステップ8:パラメータ領域の変更がなければ、ステップ4へ戻り同じパラメータ領域内で計算を繰り返す。パラメータ領域の変更があった場合はステップ3へ戻り、あらたなパラメータ領域に対する制御点を選び出す。
【0140】
ここで、ニュートン法の収束性について説明する。ここではオフセットごとのニュートン法の繰り返し回数を示すことにより、ニュートン法の収束性を検討する。なお、2回目以降のニュートン法の計算では新たにパラメータ領域を探す必要がないため、さらに高速に垂線を下ろすことができる。
【0141】
図17(a)~(c)は、頂点数4948点のモデル(HappyBuddhaモデル)に対し、細分割曲面補間を行ったときのオフセットごとのニュートン法の繰り返し回数に対する頂点数をヒストグラムにまとめたものである。
【0142】
1回目のオフセットではパラメータ領域を探す必要があるため、平均約10回のニュートン法を繰り返しているが、2回目以降は約5回、9回目は約2回で収束する。グラフ中、繰り返し数20回となる頂点があるが、このような場合は大抵、垂線の下り得る点が複数点あることが経験的に分かっている。例えば、初期制御点と曲面との位置関係から垂線を複数の採り得る場合には、ニュートン法では垂線の足となる複数の点間で振動を起こし、どちらか一方に収束することがない。また、図17(d)は補間回数の演算時間の変化を示している。
【0143】
本発明の補間のアルゴリズムによれば、図17のグラフからも分かるように、オフセットを繰り返していくと、このような点は非常に少なくなり、さらに初期ポリゴンメッシュを構成する頂点数が多くなるほど、このような頂点はさらに少なくなるため、垂線の足となり得る点のどれを扱っても曲面品質への影響は小さいと考えられる。
【0144】
したがって、本発明による補間のアルゴリズムは優れた収束性を有しており、2,3回の補間処理で制御点をオフセットすることより高精度な補間曲線を生成することができる。なお、尖った形状などでは滑らかな部分に比べ収束が遅くなる傾向がある。そのような部分に対しては全体のオフセットにより補間曲線を生成した後、収束が遅い頂点のみ選び出して、局所的にオフセットを繰り返すことにより高精度の補間曲線へと仕上げることができる。
【0145】
次に、本発明の制御点をオフセットする第2の補間処理においてさらに説明する。
【0146】
図3(b)で示したように、オフセット方向を垂線の足における単位法線ベクトルNと距離ベクトルVd(=Pi-fi)の内積N・Vd=(N・(Pi-fi))の符号により、オフセットベクトル(アップデートベクトル)Vを以下のように定義され、
(N・(Pi-fi))>0:Vu+
(N・(Pi-fi))<0:Vu- …(4)
Qオフセットベクトルは
=(N・(Pi-fi))N …(5)
となるので、このベクトルを現在の制御点位置に加えることにより、次のようにオフセット後の新たな制御点位置を求めることができる。
i(k+1)=Pi(k)+V
【0147】
なお図3では2次元で示しているが、3次元の曲面補間においても全体のオフセットを行った後、収束が遅く、高精度に補間することができなかった頂点に対して局所的にオフセットを繰り返すことで、高精度な曲面補間を行うことができる。
【0148】
次に本発明の補間処理の収束性の解析的な証明について説明し、実際のモデルにおける収束性例を示す。
【0149】
ここでは2次の一様B-Spline曲線を用い、その中点を垂線の足として解析を行うが、B-Spline曲面や細分割曲面についても適用することができる。
【0150】
2次の一様B-Spline曲線は次のように定義される。
r(t)=Pj-10(t)+Pj1(t)+Pj+12(t) …(6)
【0151】
ここで、Pj-1、Pj、Pj+1は制御点、N0(t)、N1(t)、N2(t)は以下で与えられる2次のB-Splineにおける基底関数である。
0(t)=1/2(1-t)2、N1(t)=1/2+t-t2、N2(t)=1/2t2 …(7)
【0152】
ここで、制御点Pj から曲線への垂線の足を曲線の中点とすると
fj(1)=r(1/2)=1/8(Pj-1+6Pj+Pj+1) …(8)
となり、制御点Pj と垂線の足fj(1)との距離ベクトルは
d j(1)=Pj-fj(1)=1/8(-Pj-1+2Pj-Pj+1) …(9)
で与えられる。
【0153】
新たな制御点位置は現在の制御点位置に曲線までの距離d j を加えたものとなるから
j(2)=Pj(1)+d j(1)=1/8(-Pj-1+10Pj-Pj+1) …(10)
で与えられる。さらに同様にして
j-1(2)=Pj-1+d j-1(1)=1/8(-Pj+2+10Pj-1-Pj) …(11)
j+1(2)=Pj+1+d j+1(1)=1/8(-Pj+10Pj+1-Pj+2) …(12)
が得られる。式(8)により、新たな垂線の足は
j(2)=1/8(Pj-1(2)+6Pj(2)+Pj+1(2)) …(13)
となり、距離ベクトル
d j(2)=1/8(Pj-1(2)+6Pj(2)+Pjj+1(2)) …(14)
を得ることができる。
【0154】
この幾何プロセスを距離ベクトルがある閾値よりも小さくなるまで繰り返す。
【0155】
表1に5回までのオフセットにおける距離ベクトルの係数を示す。
【表1】
JP0004934789B2_000004t.gif

【0156】
また、帰納的に次の漸化式が得られる。
【数2】
JP0004934789B2_000005t.gif
…(15)
【0157】
式(15)においてkが大きくなるにつれ距離ベクトルが零に収束すればよい。Pj(i=k)が最も大きい係数となるため、この係数の収束性について検討する。k回目のオフセットにおいてPjの係数は
【数3】
JP0004934789B2_000006t.gif
…(16)
となる。k+1回目のオフセットにおける係数との比は
ak+1/ak=(2k+1)/(4(k+1)) …(17)
となり、式(15)は収束することがわかる。結果としてkが無限大になれば式(15)は零に収束する。したがって、本発明の補間処理の幾何アルゴリズムが初期ポリゴンを補間することが証明される。
【0158】
次に、実際のモデルにおける収束性の例に説明する。
【0159】
図18は、一モデルにおけるオフセット回数に対する誤差の変化を示している。図18において、細い実線は頂点数が562の例を示し、太い実線は頂点数が4988の例を示している。なお、ここで示すモデルは、図19に示した562点のbunnyモデルの例である。誤差は頂点と補間曲面との距離のbounding box(モデルが含まれる最小の直方体)の対角線に対する割合を平均した平均自乗距離誤差を用いて評価を行った。
【0160】
頂点数562の粗いbunnyモデルにおいても、1回のオフセットにより誤差の割合を0.05%程度まで小さくすることができる。また、頂点数4988のモデルは頂点数が多く、元形状をより詳細に表現しているため誤差の減少率は小さくなるが、どちらも数回程度のオフセットで十分な精度が得られる。
【0161】
従来の手法はパラメータ修正やフィッティングの最適化を何度も行うのに対し、本発明の補間処理によれば数回のオフセットにより高い精度で曲面補間を行うことができ高い収束性をもつ。
【0162】
本発明の補間処理は上記のように制御ポリゴン全体をオフセットして補間を行うだけでなく、収束が遅く精度よく補間できなかった曲面部分に対して、その曲面に影響を与える局所的な制御点のオフセットを繰り返すことにより、精度の改善を行うことも可能である。
【0163】
また、このように局所的なオフセットを行うことにより、すでに十分な精度で補間できている部分を除いて形状処理を行うことができるため、曲面生成時間の短縮につながる。
【0164】
図20~図22は、本発明の補間処理結果の一例を示している。図20はRocker-Armの例であり、http://Cyberware/samplesを参照している。
【0165】
また、図21はStanford Bunnyの例であり、図22はHappy Buddhaの例であり、http://graphics.stanford.edu/data/3Dscanrep/を参照している。
【0166】
各図は、入力した初期メッシュ、初期メッシュと補間した細分割曲面、補間した細分割曲面を示している。
【0167】
これらの各図に補間頂点数、全体のオフセット回数、最大自乗距離誤差、平均自乗距離誤差、計算時間を以下の表2に示す。
【0168】
【表2】
JP0004934789B2_000007t.gif

【0169】
図23は補間結果例であり、円環形状の補間例を示している。図23(a)は円環形状を粗いポリゴンで表したメッシュ図であり、図23(b)は従来の補間によって得られる補間結果を示し、図23(c)は本発明の補間によって得られる補間結果を示し、図23(d)は補間で得られた円環と制御ポリゴンとの関係を示している。
【0170】
図23(b)に示す従来の補間で得られた円環形状には歪みが生じることが確認される。これに対して、図23(c)に示す本発明の補間で得られた円環形状には歪みを含まず、円滑な形状を得ることができる。
【0171】
図23に示すように、本発明の補間処理によれば、従来の補正処理で見られた歪みの発生を解消することができる。
【0172】
図24は補間頂点数に対する計算時間を示している。本発明の補間処理の計算コストは頂点数Nと全体のオフセット回数Mのかけ合わせであるO(NM)であると考えられる。図24に示すグラフからもその線形性を確認することができる。従来の曲面フィッティング手法の解法としてはCG法(Conjugate Gradient Method)やSVD(Singular Value Decomposition)などがあげられるが、これらの手法の計算コストはO(N)~ O(2)である。本発明の補間処理における全体のオフセット回数は、入力したポリゴンメッシュの詳細度や形状の複雑さにもよるが、M≪Nであるため、従来手法と比較しても計算コストを削減あるいは同程度とすることができている。
【0173】
本発明の補間処理と従来の補間処理とを、処理時間および歪みの発生との関係で比較すると、本発明の補間処理によれば、歪みを発生させることなく、従来の補間処理と同程度で、あるいは条件によっては高速で処理することができ、従来の補間処理後のフェアリング処理による歪みの除去処理を考慮すると、十分に高速で処理することができる。
【0174】
例えば、補正後の形状誤差を0.01%~0.05%程度とする場合には、本発明の補間処理は従来の補間処理よりも短時間、あるいは同程度の時間で処理することができる。また、形状誤差を0.01%を下回る程度とした場合には、本発明の補間処理は従来の補間処理より処理時間を要するが、歪みを発生させることなく良好な補間結果を得ることができる。
【0175】
上記説明ではLoop細分割曲面補間を用いて説明したが、Catmull-Clark細分割曲面に対しても全く同様のアルゴリズムで曲面補間を行うことができる。また、平面曲線についても補間が可能であり、本発明の補間処理はが制御点で定義される曲線および曲面に対して有効に適用することができる。
【0176】
次に、細分割曲面の形状評価方法について説明する。
【0177】
曲面の幾何学的に評価は、曲面の法線や曲率で表すことができる。
【0178】
パラメトリック曲面r=r(u,v)において、弧長dsは
ds=|ru・du/dt+rv・dv/dt|dt
=(Edu2+2Fdudv+Gdv21/2 …(18)
【0179】
ここで、ruはrのパラメータuについていの偏微分、rvはrのパラメータvについていの偏微分を表し、E,F,Gは第一基本形式係数と呼ばれ、
E=ru・ru、F=ru・rv、G=rv・rv …(19)
で表され、第一基本形式(弧長I)は
I=ds2=Edu2+2Fdudv+Gdv2 …(20)
で表される。
【0180】
また、法曲率κは
κ=(Ldu2+2Mdudv+Ndv2)/(Edu2+2Fdudv+Gdv2)…(21)
で表され、式(21)の分子は第二基本形式と呼ばれる。
【0181】
ここで、L,M,Nは第二基本形式係数と呼ばれ、
L=ruu・N、M=ruv・N、G=rvv・N …(22)
で表され、λ=du/dvとおくと、法曲率κは、
κ=(L+2Mλ+Nλ2)/(E+2Fλ+Gλ2) …(23)
と表される。
【0182】
この法曲率κの極値κ1,κ2を求めると、
κ1=H+(H2-K)1/2 …(24)
κ2=H-(H2-K)1/2 …(25)
となり、最大主曲率はκ1、最小主曲率はκ2である。
ここでKはガウス曲率、Hは平均曲率である。
【0183】
また、接平面上で法曲率が最大値、最小値をとる方向を主方向であり、
uv平面における最大、最小主曲率の主方向は
λ=(L-κnE)/(M-κnF) …(26)
又は
λ=(M-κnF)/(N-κnG) …(27)
である。
【0184】
ここで、κnにκ1,κ2を代入することで、最大、最小主曲率の主方向に対応するλが得られる。
【0185】
三次元空間上への変換は
p=(ru+λrv)/|ru+λrv| …(28)
で行うことができる。
【0186】
したがって、曲面r(u,v)のuv平面おける前記最大、最小主曲率κ1又はκ2を前記式(24),(25)の演算、式(28)中のκに代入してuv平面から3次元空間への変換処理を、それぞれプログラム又は演算回路で行い、求めたpを3次元空間における細分割曲面の主方向を評価する評価値として出力することで、細分割曲面の形状評価を行うことができる。
【0187】
図25は、本発明の補間処理によって求めた法線ベクトルのオフセットごとにおける誤差を示している。また、Angle Weighted法によって得られた結果(ほぼ0.78度)を比較として示している。
【0188】
オフセットなしで法線を求めた場合、つまり、初期ポリゴンにより定義される極限曲面で法線を求めた場合、解析解との誤差は約0.97度であったが、1度オフセットを行うと約0.35度まで誤差を小さくすることができる。
【0189】
それ以上オフセットを数回繰り返しても明確な精度の向上は見られなかった。これは、形状が単純な場合やポリゴンが荒くない場合、1回のオフセットだけで初期ポリゴンと極限曲面との誤差を十分小さくできると考えられるためである。
【0190】
また、Angle Weighted法では解析解との平均誤差は約0.78度であった。この手法は比較的精度のよい手法であり、本発明の補間処理がポリゴンメッシュの法線を求める上で他の手法よりも有効な手法である。
【産業上の利用可能性】
【0191】
本発明は、3Dモデリングの分野におけるリバースエンジニアリングに適用することができる。
図面
【図2】
0
【図3】
1
【図4】
2
【図5】
3
【図6】
4
【図7】
5
【図9】
6
【図12】
7
【図13】
8
【図14】
9
【図15】
10
【図16】
11
【図17】
12
【図18】
13
【図25】
14
【図1】
15
【図8】
16
【図10】
17
【図11】
18
【図19】
19
【図20】
20
【図21】
21
【図22】
22
【図23】
23
【図24】
24