(57)【要約】点群から得られる初期ポリゴンを制御ポリゴンとし、この制御ポリゴンの制御点を、この制御ポリゴンで生成される極限曲面との最短距離だけ法線方向にオフセットすることによって、細分割曲面を初期ポリゴンに補間させる新たな制御点の位置を求めることによって点群を補間する細分割曲面を生成する。各制御点と最短距離にある細分割曲面上の点を求める第１の過程と、制御点を曲面から法線方向に曲面上の点と初期制御点との距離だけ移動させてオフセットさせる第２の過程を、はじめの点群と曲面上の点との距離がしきい値を満たすあるいはそれよりも小さくなるまで繰り返して、初期ポリゴンを補間する細分割曲面を生成する。これによって、線形システムを解くことなく、点群を補間する細分割曲の生成を短い演算時間で行う。
2007083602.tif 000002
【特許請求の範囲】
【請求項１】
制御点により定義される曲線又は曲面によって点群を補間する補間処理方法において、
曲線あるいは曲面上において、制御ポリゴンの制御点の近傍にある点を近傍点として求める幾何アルゴリズムの演算を行う第１の補間工程と、
前記制御点の位置から前記近傍点における法線方向又は前記近傍点から初期ポリゴンへ向かう方向に、前記近傍点と初期制御点との距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行う第２の補間工程とを含み、
前記演算処理を前記幾何アルゴリズムを組み込んだ演算手段により行うことを特徴とする、補間処理方法。
【請求項２】
前記第１の補間工程は、幾何アルゴリズムの演算により曲線又は曲面上において初期制御点から最短距離にある点を近傍点として求めることを特徴とする、請求項１に記載の補間処理方法。
【請求項３】
前記第１の補間工程は、幾何アルゴリズムの演算により、曲線上の中間点、又は、曲面上で定める領域内の中心点又は重心点を、近傍点として求めることを特徴とする、請求項１に記載の補間処理方法。
【請求項４】
前記第１の補間工程は、初期制御点から制御ポリゴンにより定義される曲線あるいは曲面上に垂線を下ろし、当該垂線の曲線あるいは曲面上の垂線の足の位置を近傍点とする幾何アルゴリズムの演算を行い、
前記第２の補間工程は、前記垂線の方向を法線方向とし、前記垂線の足と初期制御点との間の距離を求め、現時点における曲線又は曲面を定義する制御点を曲線又は曲面の法線方向に前記距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行うことを特徴とする請求項１又は２に記載の補間処理方法。
【請求項５】
前記演算処理で得た制御点に基づいて曲線又は曲面を求め、
初期制御点である補間点と前記求めた曲線又は曲面との距離としきい値とを比較し、前記距離がしきい値を満たす、又はしきい値よりも小さくなるまで、前記第１の補間工程と第２の補間工程とを繰り返すことを特徴とする、請求項１から請求項４のいずれかに記載された補間処理方法。
【請求項６】
前記しきい値と比較する距離は、各初期制御点における垂線の足と制御点に対応する初期制御ポリゴンである補間点との間の距離の平均自乗距離、又は最大自乗距離であることを特徴とする、請求項５に記載の補間処理方法。
【請求項７】
第１回目に行う第１の補間工程及び第２の補間工程において、
前記点群を初期制御ポリゴンとし、当該初期制御ポリゴンを制御ポリゴンとし、前記幾何アルゴリズムの演算を行い、
第２回目以降に行う第１の補間工程及び第２の補間工程において、
補間工程で得た制御点を制御ポリゴンとし、前記幾何アルゴリズムの演算を行うことを特徴とする、請求項１から請求項６のいずれかに記載された補間処理方法。
【請求項８】
前記曲面は、Ｂ−Ｓｐｌｉｎｅ曲面、三角形メッシュによるＬｏｏｐ細分割、四角形メッシュによるＣａｔｍｕｌｌ−Ｃｌａｒｋ細分割、Ｄｏｏ−Ｓａｂｉｎ細分割の何れかで定められる制御点により定義されることを特徴とする、請求項１から請求項７の何れかに記載された補間処理方法。
【請求項９】
前記曲線は、Ｃｈａｉｋｉｎ細分割又はＢ−Ｓｐｌｉｎｅ曲線で定められる制御点により定義されることを特徴とする、請求項１から請求項７の何れかに記載された補間処理方法。
【請求項１０】
パラメータで表される細分割曲面のパラメトリック曲面ｒ（ｕ，ｖ）上において、
曲面ｒ（ｕ，ｖ）の任意のパラメータｕ，ｖについて導関数ｒu、ｒｖ、ｒuu、uv、ｒvvを求める演算と、
前記導関数を用いてＥ＝ｒu・ｒu、Ｆ＝ｒu・ｒv、Ｇ＝ｒv・ｒv、Ｌ＝ｒuu・Ｎ、Ｍ＝ｒuv・Ｎ、Ｇ＝ｒvv・Ｎを求める演算と、
最大主曲率κ1＝Ｈ＋（Ｈ2−Ｋ）1/2、及び／又は、最小主曲率κ2＝Ｈ−（Ｈ2−Ｋ）1/2
を求める演算を、プログラム又は演算回路により行い、
前記演算で得た最大主曲率κ1及び／又は最小主曲率κ2を曲面の形状を評価する評価値として出力することを特徴とする、細分割曲面の形状評価方法。ここでKはガウス曲率、Hは平均曲率。
【請求項１１】
前記曲面ｒ（ｕ，ｖ）のｕｖ平面おける前記最大、最小主曲率κ1又はκ2を、
ｐ＝（ｒu＋λｒｖ）／（｜ｒu＋λｒｖ｜）
の中のκに代入してｕｖ平面から３次元空間への変換処理を、プログラム又は演算回路で行い、
当該ｐを３次元空間における細分割曲面の主方向を評価する評価値として出力することを特徴とする、請求項１０に記載の細分割曲面の形状評価方法。
【請求項１２】
制御点により定義される曲線又は曲面によって点群を補間する補間処理装置において、
曲線あるいは曲面上において、初期制御点の近傍にある点を近傍点として求める幾何アルゴリズムにより第１の補間工程を行う第１の幾何演算手段と、
曲線又は曲面を定義する制御点の位置から前記近傍点における法線方向又は前記近傍点から初期ポリゴンへ向かう方向に、前記近傍点と初期制御点との距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムにより第２の補間工程を行う第２の幾何演算手段とを備え、
前記第１の幾何演算手段及び第２の幾何演算手段は、各幾何アルゴリズムをソフトウエアで実行するためのＣＰＵ及び記憶装置、又は各幾何アルゴリズムをハードウエアで実行するための回路を備えることを特徴とする、補間処理装置。
【請求項１３】
前記第１の幾何演算手段は、幾何アルゴリズムの演算により曲線又は曲面上において初期制御点から最短距離にある点を近傍点として求めるプログラム又は回路構成を備えることを特徴とする、請求項１２に記載の補間処理装置。
【請求項１４】
前記第１の幾何演算手段は、幾何アルゴリズムの演算により、曲線上の中間点、又は、曲面上で定める領域内の中心点又は重心点を、近傍点として求めるプログラム又は回路構成を備えることを特徴とする、請求項１２に記載の補間処理装置。
【請求項１５】
前記第１の幾何演算手段は、初期制御ポリゴンの各初期制御点から制御ポリゴンにより定義される曲線あるいは曲面上に垂線を下ろし、当該垂線の曲線あるいは曲面上の垂線の足の位置を近傍点とする幾何アルゴリズムの演算を行うプログラム又は回路構成を備え、
前記第２の幾何演算手段は、前記垂線の方向を法線方向とし、前記垂線の足と初期制御点との間の距離を求め、現時点における曲線又は曲面を定義する制御点を曲線又は曲面から法線方向で前記距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行うプログラム又は回路構成を備えことを特徴とする請求項１２又は１３に記載の補間処理装置。
【請求項１６】
前記演算処理で得た制御点に基づいて曲線又は曲面を求め、
初期制御点である補間点と曲線又は曲面との距離としきい値とを比較し、前記距離がしきい値を満たす、又はしきい値よりも小さくなるまで、前記第１の幾何演算手段と第２の幾何演算手段とを繰り返し行わせるプログラム又は回路構成を有した制御手段を備えることを特徴とする、請求項１２から請求項１５のいずれかに記載された補間処理装置。
【請求項１７】
前記制御手段は、各初期制御点における垂線の足と初期制御点である補間点との間の距離の平均自乗距離、又は最大自乗距離を幾何演算するプログラム又は回路構成を備えることを特徴とする、請求項１６に記載の補間処理装置。
【請求項１８】
前記第１の幾何演算手段及び第２の幾何演算手段は、第１回目の幾何演算において、点群を初期制御ポリゴンとして入力し、この初期制御ポリゴンを制御ポリゴンとして幾何アルゴリズムの演算を行い、第２回目以降の幾何演算において、補間工程で得た制御点を制御ポリゴンとして幾何アルゴリズムの演算を行うプログラム又は回路構成を備えることを特徴とする、請求項１２から請求項１７のいずれかに記載された補間処理装置。
【請求項１９】
前記曲面は、Ｂ−Ｓｐｌｉｎｅ曲面、三角形メッシュによるＬｏｏｐ細分割、四角形メッシュによるＣａｔｍｕｌｌ−Ｃｌａｒｋ細分割、Ｄｏｏ−Ｓａｂｉｎ細分割の何れかで定められる制御点により定義するプログラム又は回路構成を備えることを特徴とする、請求項１２から請求項１８の何れかに記載された補間処理装置。
【請求項２０】
前記曲線は、Ｃｈａｉｋｉｎ細分割又はＢ−Ｓｐｌｉｎｅ曲線で定められる制御点により定義するプログラム又は回路構成を備えることを特徴とする、請求項１２から請求項１８の何れかに記載された補間処理装置。
【請求項２１】
パラメータで表される細分割曲面のパラメトリック曲面ｒ（ｕ，ｖ）上において、
曲面ｒ（ｕ，ｖ）の任意のパラメータｕ，ｖについて導関数ｒu、ｒｖ、ｒuu、uv、ｒvvを求める演算と、
前記導関数を用いてＥ＝ｒu・ｒu、Ｆ＝ｒu・ｒv、Ｇ＝ｒv・ｒv、Ｌ＝ｒuu・Ｎ、Ｍ＝ｒuv・Ｎ、Ｇ＝ｒvv・Ｎを求める演算と、
最大主曲率κ1＝Ｈ＋（Ｈ2−Ｋ）1/2、及び／又は、最小主曲率κ2＝Ｈ−（Ｈ2−Ｋ）1/2
を求める演算を行うプログラム又は演算回路を備え、
前記最大主曲率κ1及び／又は最小主曲率κ2を曲面の形状を評価する評価値として出力することを特徴とする、細分割曲面の形状評価装置。ここでKはガウス曲率、Hは平均曲率。
【請求項２２】
前記曲面ｒ（ｕ，ｖ）のｕｖ平面おける前記最大、最小主曲率κ1又はκ2を、
ｐ＝（ｒu＋λｒｖ）／（｜ｒu＋λｒｖ｜）
の中のκに代入してｕｖ平面から３次元空間への変換処理を行うプログラム又は演算回路を備え、
当該ｐを３次元空間における細分割曲面の主方向を評価する評価値として出力することを特徴とする、請求項２１に記載の細分割曲面の形状評価装置。
【請求項２３】
制御点により定義される曲線又は曲面によって点群を補間する補間処理方法において、
曲線あるいは曲面上において、初期制御ポリゴンの制御点の近傍にある点を近傍点として求める幾何アルゴリズムの演算を行う第１の補間工程と、
前記制御点の位置から前記近傍点における法線方向又は前記近傍点から初期ポリゴンへ向かう方向に、前記近傍点と初期制御点との距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行う第２の補間工程とを含み、
前記演算処理をＣＰＵに実行させる前記幾何アルゴリズムを組み込んだプログラムを記憶したことを特徴とする、プログラム媒体。
【請求項２４】
前記第１の補間工程は、幾何アルゴリズムの演算により曲線又は曲面上において初期制御点から最短距離にある点を近傍点として求める処理であり、当該処理をＣＰＵに実行させるプログラムを記憶したことを特徴とする、請求項２３に記載のプログラム媒体。
【請求項２５】
前記第１の補間工程は、幾何アルゴリズムの演算により、曲線上の中間点、又は、曲面上で定める領域内の中心点又は重心点を、近傍点として求める処理であり、当該処理をＣＰＵに実行させるプログラムを記憶したことを特徴とする、請求項２３に記載のプログラム媒体。
【請求項２６】
前記第１の補間工程は、初期制御点から制御ポリゴンにより定義される曲線あるいは曲面上に垂線を下ろし、当該垂線の曲線あるいは曲面上の垂線の足の位置を近傍点とする幾何アルゴリズムの演算を行い、
前記第２の補間工程は、前記垂線の方向を法線方向とし、前記垂線の足と初期制御点との間の距離を求め、現時点における曲線又は曲面を定義する制御点を曲線又は曲面から法線方向で前記距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行うＣＰＵに実行させるプログラムを記憶したことを特徴とする請求項２３又は２４に記載のプログラム媒体。
【請求項２７】
前記演算処理で得た制御点に基づいて曲線又は曲面を求め、
初期制御点である補間点と曲線又は曲面との距離としきい値とを比較し、前記距離がしきい値を満たす、又はしきい値よりも小さくなるまで、前記第１の補間工程と第２の補間工程とをＣＰＵに繰り返して実行させるプログラムを記憶したことを特徴とする、請求項２３から請求項２６のいずれかに記載されたプログラム媒体。
【請求項２８】
前記しきい値と比較する距離は、各初期制御点における垂線の足と初期制御ポリゴンである補間点との間の距離の平均自乗距離、又は最大自乗距離であり、当該距離をＣＰＵに実行させるプログラムを記憶したことを特徴とする、請求項２７に記載のプログラム媒体。
【請求項２９】
第１回目に行う第１の補間工程及び第２の補間工程において、
前記点群を初期制御ポリゴンとし、
当該初期制御ポリゴンを制御ポリゴンとする幾何アルゴリズムの演算、
及び、
第２回目以降に行う第１の補間工程及び第２の補間工程において、
補間工程で得た制御点を制御ポリゴンとする幾何アルゴリズムの演算をＣＰＵに実行させるプログラムを記憶したことを特徴とする、請求項２３から請求項２８のいずれかに記載されたプログラム媒体。
【請求項３０】
前記曲面は、Ｂ−Ｓｐｌｉｎｅ曲面、三角形メッシュによるＬｏｏｐ細分割、四角形メッシュによるＣａｔｍｕｌｌ−Ｃｌａｒｋ細分割、Ｄｏｏ−Ｓａｂｉｎ細分割の何れかで定められる制御点により定義され、当該定義による処理を行うＣＰＵに実行させるプログラムを記憶したことを特徴とする、請求項２３から請求項２９の何れかに記載されたプログラム媒体。
【請求項３１】
前記曲線は、Ｃｈａｉｋｉｎ細分割又はＢ−Ｓｐｌｉｎｅ曲線で定められる制御点により定義され、当該定義による処理をＣＰＵに実行させるプログラムを記憶したことを特徴とする、請求項２３から請求項２９の何れかに記載されたプログラム媒体。
【請求項３２】
パラメータで表される細分割曲面のパラメトリック曲面ｒ（ｕ，ｖ）上において、
曲面ｒ（ｕ，ｖ）の任意のパラメータｕ，ｖについて導関数ｒu、ｒｖ、ｒuu、uv、ｒvvを求める演算と、
前記導関数を用いてＥ＝ｒu・ｒu、Ｆ＝ｒu・ｒv、Ｇ＝ｒv・ｒv、Ｌ＝ｒuu・Ｎ、Ｍ＝ｒuv・Ｎ、Ｇ＝ｒvv・Ｎを求める演算と、
最大主曲率κ1＝Ｈ＋（Ｈ2−Ｋ）1/2、及び／又は、最小主曲率κ2＝Ｈ−（Ｈ2−Ｋ）1/2
を求める演算を、プログラム又は演算回路により行い、
前記演算で得た最大主曲率κ1及び／又は最小主曲率κ2を曲面の形状を評価する評価値として出力するプログラムを記憶したことを特徴とする、細分割曲面の形状評価のプログラム媒体。ここでKはガウス曲率、Hは平均曲率。
【請求項３３】
前記曲面ｒ（ｕ，ｖ）のｕｖ平面おける前記最大、最小主曲率κ1又はκ2を、
ｐ＝（ｒu＋λｒｖ）／（｜ｒu＋λｒｖ｜）
の中のκに代入してｕｖ平面から３次元空間への変換処理をＣＰＵに実行させ、当該ｐを３次元空間における細分割曲面の主方向を評価する評価値として出力するプログラムを記憶したことを特徴とする、請求項２９に記載の細分割曲面の形状評価のプログラム媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、点群データを補間して曲線あるいは曲面を生成する補間処理方法、補間処理装置、およびこの補間処理をＣＰＵに実行させるプログラムに関する。また、補間処理方法で得られる細分割曲面ならびにポリゴンメッシュの頂点における微分幾何学的形状を評価する方法、装置、およびこの評価をＣＰＵに実行させるプログラムを記憶するプログラム媒体に関する。
【背景技術】
【０００２】
自由曲面は、船、自動車、飛行機等、様々な工業製品のボディに用いられており、機能性と美しさの両方を兼ね備えるものであり、家庭電気製品や多くの消費材の外観など意匠的に美しい形状のデザイン設計に用いられる。【０００３】
近年、３Ｄレーザスキャナによって高密度の点群データを高速かつ容易に収集することができるようになり、物体形状を高精度で測定できることが可能と成っている。例えば、３Ｄモデリングの分野においては、デザイナが手作業で作成したモックアップモデルを３Ｄレーザスキャナで計測し、コンピュータに取り込んだ点群データやポリゴンデータをもとに製品として生産するために必要な曲面データなどのＣＡＤデータを作成していくという、いわゆるリバースエンジニアリングの手法が行われている。【０００４】
一般に、３ＤモデルはポリゴンモデルまたはＮＵＲＢＳやＢ−Ｓｐｌｉｎｅなどの曲面パッチによりコンピュータ上で表現される。【０００５】
このポリゴンモデルは位相変化などの形状処理を行う上で効率的であるが、平面で構成されるため滑らかな表面を表現することができず、さらに形状を詳細に表現するほどデータ量が膨大になるなどの問題がある。【０００６】
曲面パッチは少ない制御パラメータで滑らかな曲面が表現できる反面、パッチ形状が四角形に限定される上にパッチ間の連続性を保つことが困難であるなどの問題がある。そこで、ポリゴンモデルと曲面パッチの利点を併せ持つ細分割手法が自由な幾何形状モデリングの有効な手法として注目されており、すでにアニメーションの分野では盛んに利用されている。【０００７】
細分割手法とは、初期ポリゴンメッシュに対して繰り返し規則的な分割を行うことによりその形状を滑らかにし、究極的には滑らかな曲面を得る手法である。その曲面は細分割曲面（Subdivision Surface）または極限曲面と呼ばれる。細分割手法は任意の位相を持つモデルに対しても簡単に滑らかな曲面を生成できるという特徴を持ち、さらにどの部分においても曲面が滑らかなに定義されるためモデリングなど幅広い利用が進んでいる。【０００８】
リバースエンジニアリングの分野において、従来、細分割曲面を用いて測定した点群データを近似あるいは補間して曲面を生成する方法が提案されている。この細分割曲面を用いて点群データを補間する従来提案される方法では、点群データから得られる初期制御点と生成される曲面との距離誤差が最小となるように制御点を逐次求める演算処理を行っている。この制御点を求める演算は、点群の列をＳ、この点群を近似する曲面と生成するための制御点の列をＰ、曲面を定める基底関数マトリックスをＡとしたとき、ＡＰ＝Ｓで表される線形の行列式を解くことで行われる。【０００９】
従来提案されている補間方法として、例えば、Halstedらが提案する多面体メッシュに対するCatmull-Clark細分割曲面の補間手法が知られている（非特許文献１）。この手法は大規模な線形システムを解く必要があるばかりでなく、さらにフェアリングと呼ばれる曲面修正のために最小化問題を解く必要があり、計算コストが嵩む要因となっている。【００１０】
また、Hoppeらは、点群データに対するLoop細分割曲面の近似手法として、細分割操作を行ったポリゴンメッシュを線形近似した細分割曲面とみなし、その曲面に対して各点からの正射影を行うことでパラメータ化し、各点とそれに対する線形近似した細分割曲面上の点との距離が最小となる最小自乗問題として扱う手法を提案している（非特許文献２）。【００１１】
【非特許文献１】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
【非特許文献２】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
【非特許文献３】C.T.Loop.Smooth subdivision surface based on triangle.Masters thesis,Department of Mathematics. University of Utha.1987/.
【非特許文献４】E.Catmull and J.Clark. Recusively generated b-spline surfaces on arbitrary topological meshes.Computer-Aided Design,10(6):350-355,1987.
【非特許文献５】D.Doo and M.Sabin. Behavior of recursive division surfaces near extraordinary points.Computer-Aided Design,10(6):356-360,1978.
【非特許文献６】G.M.Chaikin.An algorithim for high-speed curve generation. Computer Graphics and Image Processing,3:346-349,1974.
【非特許文献７】J.Stam.Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values. In Proceedings of SIGGRAPH 1988,pages 395-404.AVM,ACM Press/ACM SIGGRAPH,1998.
【非特許文献８】M.Marinov and L.Kobbbelt, Optimization methods for scattered data approximation with subdivision surface,Graphical Models 67,2005,452-473.
【非特許文献９】R.P.Brent.Algorithims for Minimization without Deriviatives.Prentice-Half,Englewood Cliffts,N.J,1986.4.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
上記した、細分割曲面を用いて点群データを補間する従来提案される方法に用いられる演算は行列式を解くといった線形システムの解法であるため、その演算の性質上、点群及び制御点の個数が増加するほど演算回数が増加する。一般に、３Ｄモデリングに要する点群及びこの点群から形成される制御点の個数は多数であるため、点群から曲面を生成する演算は大規模な線形システムを解く演算となり、多くの計算時間を要するという問題がある。【００１３】
さらに、円滑な曲面を得るには、初期制御点と生成される曲面との距離誤差が最小となるまで、大規模な線形システムを解く演算処理を繰り返す必要があり、所望とする円滑な曲面を得るには多くの時間を要することになる。【００１４】
また、補間処理では補正結果に望ましくない歪みが発生するという問題がある。この歪みを解消するために、非特許文献１ではフェアリングと呼ばれる曲面修正の処理を行っている。このように、従来の補間処理では、補間処理に加えて曲面修正処理が必要となるため処理工程が増えるという問題がある。【００１５】
そこで、点群の補間処理において、多大な演算処理を要さず、また、処理工程を増やすことなく、歪みの少ない補間結果を得ることが望まれる。【００１６】
また、現在、ＣＡＤ／ＣＡＭや、コンピューターグラフィックス（ＣＧ）の分野などでは、滑らかな曲面をポリゴンメッシュとして表現する手法が広く用いられている。曲面をポリゴンメッシュに近似することによってコンピューター上での処理が容易になるという利点があり、さらにそのメッシュをＦＥＭへ適用することも可能である。しかしながら、ポリゴンメッシュは点群を線形補間することにより表現されるモデルであるため、Ｂ−Ｓｐｌｉｎｅなどのように微分幾何学を用いて解析的に形状を評価することができない。【００１７】
そこで、本発明は前記した従来の問題点を解決し、点群の補間処理において、多大な演算処理を要さず、また、処理工程を増やすことなく、歪みが少ない補間結果を得ることを目的とする。【００１８】
また、点群を補間する細分割曲面の生成において、短い演算時間で歪みが少ない補間結果を得ることを目的とする。【００１９】
また、線形システムを解くことなく点群を補間する細分割曲面を生成する方法及び装置を提案することを目的とする。【００２０】
また、ポリゴンメッシュの各頂点における微分幾何学的形状を解析的に評価することを目的とする。
【課題を解決するための手段】
【００２１】
本発明は、点群から得られる初期ポリゴンを制御ポリゴンとし、この制御ポリゴンの制御点を、この制御ポリゴンで生成される極限曲面と補間点である初期制御ポリゴンとの最短距離だけ法線方向にオフセットすることによって、細分割曲面を初期ポリゴンに補間させる新たな制御点の位置を求めることによって点群を補間する細分割曲面を生成するものであり、各初期制御点と最短距離にある細分割曲面上の点を求める第１の過程と、制御点を曲面から法線方向に曲面上の点と初期制御点との距離だけ移動させてオフセットさせる第２の過程を、はじめの点群と曲面上の点との距離がしきい値を満たすあるいはそれよりも小さくなるまで繰り返すことによって、初期ポリゴンを補間する細分割曲面を生成する。【００２２】
なお、本発明では、入力したポリゴンデータＭNΔにより構成される制御ポリゴンを初期制御ポリゴンＭNC、オフセットした制御点により構成されるポリゴンを単に制御ポリゴンとし、初期制御ポリゴンの制御点は補間点とも呼ぶことにする。【００２３】
本発明の方法は局所的に各制御点を扱うことになるため、線形システム自体を必要としない上に、幾何学的なプロセスのみで補間曲面を生成することができる。したがって、従来の方法と比べ高速に補間曲面を生成することができる。また、この操作は制御ポリゴンを初期位相に保ったまま拡大する操作であるため、従来の線形システムを解く手法に比べ自然な手法であるため、生成される曲面にゆがみが生じることがなく、高品質な曲面が得られる。【００２４】
なお、本発明は、３次元に限らず２次元についても同様に適用することができ、三次元上の点群を補正する細分割曲面を生成するほか、二次元上の点群を補間する曲線の生成にも適用することができる。【００２５】
また、本発明は、補間処理に関して方法、装置、およびこの補間処理をコンピュータに実行させるためのプログラムを記憶するプログラム媒体の各態様とすることができる。【００２６】
ここでは、主に補間処理方法について示す。補間処理装置は、この補間処理方法をソフトウエアあるいはハードウエアによって実行させるために各手段を備え、また、プログラム媒体は、本発明の補間処理方法をコンピュータに実行させるためのプログラムを記憶するものであるため、ここでは、詳細な説明は省略する。【００２７】
本発明の補間処理方法は、点群を補間し、制御点により定義される曲線又は曲面を生成する補間処理方法において、曲線あるいは曲面上において、初期制御ポリゴンの制御点の近傍にある点を近傍点として求める幾何アルゴリズムの演算を行う第１の補間工程と、現時点における曲線又は曲面を定義する制御点の位置から近傍点における法線方向に向かって、近傍点と初期制御点との距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行う第２の補間工程とを含む。この演算理は幾何アルゴリズムを組み込んだ演算手段により行うことができる。【００２８】
本発明の補間処理方法が備える２つの補間工程において、第１の補間工程は、幾何アルゴリズムの演算により曲線又は曲面上において初期制御点から最短距離にある点を近傍点として求めるものである。【００２９】
この曲線又は曲面上の近傍点は、初期制御点からの距離が最短距離でない点も含むことができ、最短距離にある点に代えて、初期制御点の近傍にある細分割された曲線又は曲面上において任意に定めた点としても良い。ここで、近傍は、細分割された複数の曲線又は曲面の内で初期制御点に近いということを意味し、この近傍にある曲線又は曲面上の点を近傍点としている。この近傍点は最短距離点が望ましいが、かならずしも最短距離である必要はなく、例えば極限曲面Ｓ0あるいは細分割曲面Ｓi上の中心点や重心点等の任意の点としてもよく、曲線の場合には最短距離の他に例えば中間点としてもよい。【００３０】
第１の補間工程は、曲線又は曲面上で近傍点を求める演算処理であり、制御ポリゴンの各初期制御点から曲線あるいは曲面上に垂線を下ろし、この垂線の曲線あるいは曲面上の垂線の足の位置を近傍点とする、幾何アルゴリズムの演算処理である。【００３１】
また、第２の補間工程は、制御点の新たな位置を求める演算処理であり、垂線の足と初期制御点との間の距離を求め、垂線の方向を法線方向とし、現時点における現在の曲線又は曲面を定義している制御点を曲線又は曲面から法線方向に前記距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算である。【００３２】
上記した補間工程により得た制御点を制御ポリゴンの制御点として、新たに曲線又は曲面を求めると、求めた新たな曲線又は曲面上の点は当初の点群に近づき、補間前の曲線又は曲面よりも点群をより正確に補間する。【００３３】
点群と曲線又は曲面との距離を求め、この距離と予め定めたしきい値とを比較し、距離がしきい値を満たす、又はしきい値よりも小さくなるまで、第１の補間工程と第２の補間工程とを繰り返す。しきい値は、点群と曲線又は曲面との間の設定誤差に相当し、点群と曲線又は曲面との距離がこのしきい値を満たす、又はしきい値よりも小さくなった場合には、曲線又は曲面は点群をしきい値で定める許容誤差内にあることが保証される。【００３４】
点群と曲線又は曲面との距離は、各初期制御点における垂線の足と初期制御点との間の距離の平均自乗距離、又は最大自乗距離とすることができる。【００３５】
補間の補間処理において、第１回目に行う第１の補間工程及び第２の補間工程では、点群を初期制御ポリゴンとし、この初期制御ポリゴンを制御ポリゴンとし、幾何アルゴリズムの演算を行い、第２回目以降に行う第１の補間工程及び第２の補間工程では、補間工程で得た制御点を制御ポリゴンとして幾何アルゴリズムの演算を行う。【００３６】
曲面は、Ｂ−Ｓｐｌｉｎｅ曲面や、三角形メッシュによるＬｏｏｐ細分割（非特許文献３）、四角形メッシュによるＣａｔｍｕｌｌ−Ｃｌａｒｋ細分割（非特許文献４）、Ｄｏｏ−Ｓａｂｉｎ細分割（非特許文献５）等の再分割等で定められる制御点により定義することができる。【００３７】
また、曲線については、Ｂ−Ｓｐｌｉｎｅ曲線や、Ｃｈａｉｋｉｎ細分割（非特許文献６）で定められる制御点により定義することができる。なお、Ｃｈａｉｋｉｎ細分割は２次のＢ−Ｓｐｌｉｎｅ曲線に収束し、一般的にｎ次のB-Splien曲線についても補間を行うことができる。【００３８】
本発明のポリゴンメッシュの各頂点における微分幾何学的形状の解析的な評価は、最大主曲率κ1や最小主曲率κ2、細分割曲面の主方向を曲面の形状を評価する評価値とする。【００３９】
最大主曲率κ1や最小主曲率κ2は、パラメータで表される細分割曲面のパラメトリック曲面ｒ（ｕ，ｖ）上において、曲面ｒ（ｕ，ｖ）の任意のパラメータｕ，ｖについて導関数ｒu、ｒｖ、ｒuu、uv、ｒvvを求める演算と、求めた導関数を用いてＥ＝ｒu・ｒu、Ｆ＝ｒu・ｒv、Ｇ＝ｒv・ｒv、Ｌ＝ｒuu・Ｎ、Ｍ＝ｒuv・Ｎ、Ｇ＝ｒvv・Ｎを求める演算と、最大主曲率κ1＝Ｈ＋（Ｈ2−Ｋ）1/2、及び／又は、最小主曲率κ2＝Ｈ−（Ｈ2−Ｋ）1/2を求める演算を、プログラム又は演算回路で実行することで得ることができる。なお、ここでKはガウス曲率、Hは平均曲率である。【００４０】
また、３次元空間における細分割曲面の主方向は、曲面ｒ（ｕ，ｖ）のｕｖ平面おける最大、最小主曲率κ1又はκ2を、ｐ＝（ｒu＋λｒｖ）／（｜ｒu＋λｒｖ｜）の中のκに代入してｕｖ平面から３次元空間への変換処理を、プログラム又は演算回路で実行することで得ることができる。【００４１】
本発明のポリゴンメッシュの各頂点における微分幾何学的形状の解析的な評価によれば、従来法よりも高精度に評価することができる。
【発明の効果】
【００４２】
以上説明したように、本発明によれば、点群の補間処理において、多大な演算処理を要さず、また、処理工程を増やすことなく、歪みが少ない補間結果を得ることができる。【００４３】
また、本発明によれば、線形システムを解くことなく点群を補間する細分割曲面を生成することができる。【００４４】
また、本発明によれば、ポリゴンメッシュの各頂点における微分幾何学的形状の解析的の評価を高精度で行うことができる。
【図面の簡単な説明】
【００４５】
【図１】本発明の補間処理の概略を説明するための概略図である。
【図２】本発明の補間処理の概略を説明するためのフローチャートである。
【図３】本発明の補間処理の第１、第２の補間工程を説明するための図である。
【図４】本発明の補間処理装置の概略構成図である。
【図５】二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を説明するためのフローチャートである。
【図６】二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を説明するための制御点と曲線との概略図である。
【図７】二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を説明するための制御点と曲線との概略図である。
【図８】二次元の点群を補間する曲線例を示す図である。
【図９】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するためのフローチャートである。
【図１０】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲線との概略図である。
【図１１】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲線との概略図である。
【図１２】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲線との概略図である。
【図１３】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲線との概略図である。
【図１４】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲線との概略図である。
【図１５】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲線との概略図である。
【図１６】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲線との概略図である。
【図１７】オフセットごとのニュートン法の繰り返し回数に対する頂点数のヒストグラムである。
【図１８】一モデルにおけるオフセット回数に対する誤差の変化を示す図である。
【図１９】562点のbunnyモデルの例である。
【図２０】本発明の補間処理結果の一例を示す図である。
【図２１】本発明の補間処理結果の一例を示す図である。
【図２２】本発明の補間処理結果の一例を示す図である。
【図２３】補間結果例を示す図である。
【図２４】本発明による補間頂点数に対する計算時間を示す図である。
【図２５】本発明の補間処理によって求めた法線ベクトルのオフセットごとの誤差を示す図である。
【符号の説明】
【００４６】
１…入力手段
２…記憶手段
２ａ…データ記憶部
２ｂ…演算ツールプログラム記憶部
２ｃ…演算プログラム処理プログラム部
２ｄ…一次記憶部
２ｅ…演算記憶部
３…演算手段
４…表示手段
５…出力手段
【発明を実施するための最良の形態】
【００４７】
以下、本発明の実施の形態について、図を参照しながら詳細に説明する。【００４８】
図１，図２，図３は、本発明の補間処理の概略を説明するための概略図、フローチャート、第１、第２の補間工程を説明するための図であり、図４は本発明の補間処理装置の概略構成図である。【００４９】
図１，図２、は、点群ＰNから極限曲面Ｓ∞を求める手順を概略的に示している。なお、ここでは、３Ｄレーザスキャナ（３次元形状測定機）等から得られた高密度・不規則な点群データ（点群ＰN）から開始し、この点群ＰNを補間する最終的な極限曲面Ｓ∞を得る手順によって示しているが、点群ＰNから得られたポリゴンメッシュから開始して極限曲面Ｓ∞を得る手順としてもよい。これは、本発明の補間処理が、微分幾何学の演算装置によって計算された法線からポリゴンの制御点を修正し、修正した制御ポリゴンから極限曲面Ｓ∞を得る処理であり、点群ＰNから得られたポリゴンメッシュから開始することができるからである。【００５０】
ここでは、入力したポリゴンデータＭNΔにより構成される制御ポリゴンを初期制御ポリゴンＭNC、オフセットした制御点により構成されるポリゴンを単に制御ポリゴンとし、また、初期制御ポリゴンの制御点を補間点とも呼ぶ。【００５１】
なお、ここでは、主に曲面について説明するが、曲線についても同様に扱うことができる。【００５２】
はじめに、３Ｄレーザスキャナ等によって与えられた点群ＰNを用いてメッシュ化してポリゴンメッシュを生成する。ポリゴンメッシュは、三角形ポリゴンメッシュや四角形ポリゴンメッシュを用いることができる。このメッシュ化の処理は既存の手法を用いることができる。ここでは、三角形ポリゴンメッシュＭNΔを用いて説明する（Ｓ１）。【００５３】
この三角形ポリゴンメッシュＭNΔを初期制御ポリゴンメッシュＭNCとして制御点を定める（Ｓ２）。この初期制御ポリゴンメッシュＭNCを用いて細分割処理を行って極限曲面Ｓ0を生成する（Ｓ３）。Ｓ３で生成した極限曲面Ｓ0に補間処理を施し、制御点の位置をオフセットして修正し（Ｓ４）、修正した制御点の位置に基づいて細分割曲面Ｓiを生成する（Ｓ５）。【００５４】
生成した細分割曲面Ｓiと初期制御ポリゴンメッシュＭNCとを比較し、対応する点間の距離の誤差が収束するまでＳ４の補間工程を繰り返す。この収束は、距離誤差があらかじめ設定しておいたしきい値を満たすまでＳ４の補間工程を繰り返す（Ｓ６）。【００５５】
補間処理によって距離誤差が収束したときに得られる極限曲面Ｓ∞は、初期制御ポリゴンメッシュＭNCを補間する細分割曲面となる（Ｓ７）。【００５６】
Ｓ４の補間処理は２つの補間工程Ｓ４ａとＳ４ｂとをを備える。第１の補間工程Ｓ４ａでは、制御点から極限曲面Ｓ0あるいは細分割曲面Ｓi上の近傍点を求める。この近傍点は、ある初期制御点の近傍にある極限曲面Ｓ0あるいは細分割曲面Ｓi上にある点であり、例えば極限曲面Ｓ0あるいは細分割曲面Ｓi上において、初期制御点からの距離が最短となる最短距離点として定めることができる。【００５７】
なお、近傍点は最短距離点が望ましいが、かならずしも最短距離である必要はなく、例えば極限曲面Ｓ0あるいは細分割曲面Ｓi上の中心点や重心点等、任意の点としてもよい。曲線の場合には、最短距離の他に例えば中間点としてもよい。【００５８】
ポリゴンメッシュを十分に小さく設定した場合には、多くの場合、最短距離にある点から中心点や重心点との誤差はわずかとなり、近傍点が最短距離の点からずれることにより生じる誤差はわずかと推定される。【００５９】
図３（ａ）は第１の補間処理Ｓ４ａの工程を説明するための図であり、図３（ｂ）は第２の補間処理Ｓ４ｂの工程を説明するための図である。なお、図３では二次元上で示している。また、図３では、シフト前の制御点をＰa、シフト後の制御点をＰbで示し、曲線Ｃ上で求めた近傍点をＦで示している。【００６０】
図３（ａ）に示す第１の補間処理Ｓ４ａの工程において、はじめに初期制御点Ｐaが与えられているとする。なお、第１回目の補間処理では、制御点Ｐaは点群ＰNから得られる初期ポリゴンメッシュＭNCの制御点であり、第２回目の補間処理では、前回の補間処理によって位置がシフトされた制御ポリゴンの制御点である。【００６１】
この制御点Ｐaを用いて細分割を行うことによって極限曲面Ｓが生成される。なお、最初に生成される極限曲面は極限曲面Ｓ0であり、２回目以降に生成される極限曲面は極限曲面Ｓiである。【００６２】
極限曲面（Ｓ0，Ｓi）において、初期制御点Ｐaに対応する近傍点Ｆを求める。近傍点Ｆは、初期制御点Ｐaから極限曲面（Ｓ0，Ｓi）上に垂線を下ろし、その垂線の足の点とすることができる。【００６３】
次に、図３（ｂ）に示す第２の補間処理Ｓ４ｂの工程において、初期制御点Ｐaの位置をシフトして新たな位置に制御点Ｐbを求める。制御点Ｐbの新たな位置は、初期制御点Ｐaと近傍点Ｆと距離だけ、初期制御点Ｐaの位置から所定方向に向かってオフセットさせた位置である。この所定方向は、例えば近傍点Ｆにおける法線方向とすることができる。図３（ｂ）において、極限曲面から初期制御点Ｐaへの距離ベクトルをＶｄで表し、初期制御点Ｐaから制御Ｐbへ位置をオフセットさせるアップデートをＶｕで表し、極限曲面上の近傍点Ｆにおける法線をＮで表している。【００６４】
図中において、ベクトルＶu+は、Ｎ・Ｖｄ＞０のとき法線Ｎの正方向に制御点の位置をオフセットし、ベクトルＶu-は、Ｎ・Ｖｄ＜０のとき法線Ｎの負方向に制御点の位置をオフセットする。また、方向を含むアップデートベクトルは、
2007083602.tif 000003
で表される。【００６５】
補間工程Ｓ４は、この第１の補間工程Ｓ４ａと第２の補間工程Ｓ４ｂを繰り返して行われる。この第２の補間工程Ｓ４ｂで得られた制御点Ｐを用いることで、前記したＳ５の工程によって制御ポリゴンメッシュＭNCを細分割して細分割曲面Ｓiを生成する。【００６６】
この曲面の細分割処理として、例えば、三角形メッシュによるＬｏｏｐ細分割、四角形メッシュによるＣａｔｍｕｌｌ−Ｃｌａｒｋ細分割、Ｄｏｏ−Ｓａｂｉｎ細分割等を用いることができ、また、Ｂ−Ｓｐｌｉｎｅ曲面についても適用することができる。【００６７】
曲線の細分割として、例えば、Ｃｈａｉｋｉｎ細分割を用いることができる他、ｎ次のＢ−Ｓｐｌｉｎｅ曲線についても適用することができる。なお、Ｃｈａｉｋｉｎ細分割は２次のＢ−Ｓｐｌｉｎｅ曲線に収束する。【００６８】
本発明の補間によれば、計算コスト、曲面品質、演算の一般性の点で以下の利点がある。【００６９】
本発明の補間のアルゴリズムは、初期ポリゴンと補間して得られた曲面との距離を算出する幾何学的演算、及び、制御点の位置をオフセットする幾何学的演算である。幾何学的演算であるため、計算コストは、補間頂点数Ｎ、オフセット回数ＭによるＯ（ＭＮ）である。一方、従来の線形システムによる計算コストは、補間頂点数Ｎに対して指数のオーダーで増加する。通常、Ｍ≪Ｎであるため、本発明の補間によれば、計算コストの増加率は従来の方法より大幅に低減させることができ、計算速度の点から見ると、非常に高速な補間曲面の生成が可能となる。【００７０】
本発明の補間のアルゴリズムは、他の補間手法のように生成した補間曲面にうねりが生じることがない。【００７１】
また、本発明の補間のアルゴリズムは、単純な幾何プロセスにより曲面生成を行っており、分割曲面のみならず、B-Spline曲面や曲線など、制御点により定義される曲線、曲面に対して適用することができ、曲面生成について一般性を有する。【００７２】
図４は、本発明の補間処理のソフトウエアを記憶したプログラムをコンピュータで実行させる場合の一構成例を示している。【００７３】
入力手段１は、点群ＰNのデータ、あるいは点群ＰNから生成される制御ポリゴンメッシュＭNΔを入力し、記憶手段２中のデータ記憶部２ａに記憶する。記憶手段２は、データ記憶部２ａの他に、微分幾何学演算を行う演算ツールのプログラムを記憶する演算ツール記憶部２ｂ、補間処理の微分幾何学演算の他、細分割処理等の演算処理のプログラムを記憶する演算処理プログラム記憶部２ｃ、途中演算結果等を一時的に記憶する一次記憶部２ｄ、補間処理等によって得られた曲面の演算結果を記憶する演算結果記憶部２ｅ等を備える。【００７４】
演算手段３は、データ記憶部２ａに記憶された点群ＰNあるいは制御ポリゴンメッシュＭNΔのデータを用い、演算処理プログラム記憶部２ｃに記憶されるプログラムによる演算手順に従い、また、このプログラムに指定される演算ツールのプログラムを演算ツール記憶部２ｂから逐次読み出して演算処理を行う。【００７５】
演算結果記憶部２ｅに記憶された演算結果は、読み出されて表示手段４に表示したり、出力手段５に出力される。出力手段５は、演算結果を記録媒体に記録する記録装置、例えば加工装置等の演算結果を用いて所定動作を行う外部装置等とすることができる。【００７６】
なお、上記、ソフトウエア処理を行う構成は、専用のソフトウエア処理装置や、通常のパーソナルコンピュータに適用することができる。【００７７】
また、上記構成において、記憶手段を含む演算手段で実施される機能を回路で構成することでハードウエアにより実施することもできる。【００７８】
次に、本発明の補間処理の詳細について、二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合と、三次元の点群あるいは制御ポリゴンメッシュにより曲面を生成する場合について説明する。【００７９】
以下、はじめに、二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を、図５のフローチャート，図６，７の制御点と曲線との概略図、図８の曲線の補間例の図を用いて説明し、次に、三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を、図９のフローチャート，図１０〜図１６の制御点と曲線との概略図を用いて説明する。【００８０】
はじめに、二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合について説明する。なお、以下のフローは一例であり、本発明の第１の補間処理及び第２の補間処理を実施する工程及び手順であれば他のフローで構成としてもよい。【００８１】
点群ＰNから二次元の制御ポリゴンを取得する。なお、予め求めて記憶手段に記憶しておいた二次元の制御ポリゴンを読み出しても良い。（Ｓ１１）。図６（ａ）はＳ１１の状態を示している。取得した制御ポリゴンを初期制御ポリゴンＰiとして記憶部２ａに記憶し（Ｓ１２）、この初期制御ポリゴンＰiを制御点Ｐk-1iとして記憶する（Ｓ１３）。記憶した制御点Ｐk-1iを用いて細分割処理を行い、曲線Ｃを生成する。ここで上付き文字k-1はオフセットの繰り返し回数である。細分割処理は、例えばＢ−Spline曲線補間を用いることができる。この細分割処理は、演算処理プログラム記憶部２ｃから演算処理プログラムを読み出すと共に、この演算処理プログラムに演算ツールが記述されている場合には、演算ツールプログラム記憶部２ｂに記憶される演算ツールを用いて、制御点Ｐiを用いて微分幾何学演算を実行する。図６（ｂ）はＳ１４の状態を示している。【００８２】
以下、Ｓ１５，Ｓ１６の第１の補間処理とＳ１７〜Ｓ１９の第２の補間処理を繰り返して、点群を補間する曲線Ｃを生成する。【００８３】
第１の補間処理において、初期制御ポリゴンの初期制御点Ｐiから曲線Ｃ（Ｓ１４の工程で生成した曲線Ｃ、あるいはＳ２０の工程で生成した曲線Ｃ）上に垂線を下ろし垂線の足ｆkiを求め（Ｓ１５）、初期制御点Ｐiと垂線の足ｆkiとの間の距離‖Ｐi−ｆki‖を求める。求めた垂線の足ｆkiは、曲線Ｃ上における初期制御点Ｐiの近傍点である。垂線及び距離を求める演算は、幾何学演算によって求めることができる（Ｓ１６）。図６（ｃ）は、はじめての補間処理において初期制御ポリゴンＰiを制御ポリゴンとしたときのＳ１５，Ｓ１６の状態を示し、図７（ｂ）は二回目以降の補間処理におけるＳ１５，Ｓ１６の状態を示している。【００８４】
なお、垂線は初期制御点から曲線または曲面へ下ろし、最初に垂線を下ろすときだけ、曲線または曲面を定義する制御点と、垂線を下ろす初期制御点が同じものとなる。【００８５】
次に、第２の補間処理において、曲線Ｃ上の垂線の足ｆkiでの法線を求め（Ｓ１７）、求めた法線方向へ、Ｓ１６で求めた初期制御点Ｐiと垂線の足ｆkiとの間の距離‖Ｐi−ｆki‖だけ、現在の曲線を定義している制御点Ｐk-1iの位置をオフセットし（Ｓ１８）、オフセットした位置を制御点Ｐk-1iの新たな位置とする。法線を求める演算、及び制御点の位置をオフセットする演算は、微分幾何学演算によって求めることができる（Ｓ１９）。図６（ｄ）は、はじめての補間処理において初期制御ポリゴンＰiを制御ポリゴンとしたときのＳ１７〜Ｓ１９の状態を示し、図７（ｃ）は二回目以降の補間処理におけるＳ１７〜Ｓ１９の状態を示している。【００８６】
Ｓ１９で得た制御点Ｐk-1iの新たな位置に基づいて細分割処理を行って曲線Ｃを生成する（Ｓ２０）。図７（ａ）は、はじめての補間処理において初期制御ポリゴンＰiを制御ポリゴンとしたときのＳ２０の状態を示している。【００８７】
Ｓ２０で求めた曲線Ｃと初期制御ポリゴンＰiとの距離を求め、求めた距離が予め定めたしきい値とを比較し、距離がしきい値を満たす、あるいはしきい値以下となるまで、前記Ｓ１５〜Ｓ２１の工程を繰り返す。図７（ｄ）は、二回目以降の補間処理におけるＳ２０の状態を示している。【００８８】
Ｓ２１で求めた曲線Ｃと初期制御ポリゴンＰiとの距離は、点群を補間する曲線と点群との誤差を表しており、しきい値は点群を補間する曲線に対して許容することができる許容誤差に相当する。【００８９】
点群と曲線又は曲面との距離は、各初期制御点における垂線の足と初期制御点との間の距離の平均自乗距離、又は最大自乗距離とすることができる。【００９０】
したがって、Ｓ２２の比較工程において、距離がしきい値以下となったことを確認することで、得られた曲線Ｃは点群を許容誤差範囲内で補間するものとなる（Ｓ２３）。【００９１】
本発明による補間のアルゴリズムは優れた収束性を有しており、２，３回の補間処理で制御点をオフセットすることより高精度な補間曲線を生成することができる。なお、尖った形状などでは滑らかな部分に比べ収束が遅くなる傾向がある。そのような部分に対しては全体のオフセットにより補間曲線を生成した後、収束が遅い頂点のみ選び出して、局所的にオフセットを繰り返すことにより高精度の補間曲線へと仕上げることができる。【００９２】
図８は、二次元（平面）の曲線補間の一例であり、人のシルエットの点群を補間する曲線を生成した一例である。図８（ａ）は全体図を示し、図８（ｂ）は一部拡大図を示している。図８において、点は点群を示し、曲線はこの点群を補間している。また、直線は、曲線を生成する制御点を結んでいる。【００９３】
次に、三次元の点群あるいは制御ポリゴンメッシュにより曲面を生成する場合について説明する。なお、以下のフローは一例であり、本発明の第１の補間処理及び第２の補間処理を実施する工程及び手順であれば他のフローで構成としてもよい。【００９４】
補間のアルゴリズムの流れは、与えられた任意形状をもつ三角形ポリゴンメッシュを初期制御ポリゴンとして、それから生成される極限曲面を得る。次に、初期制御点から制御ポリゴン(１回目は初期制御点、２回目以降はオフセットした制御点)より生成される極限曲面に垂線を下ろし最短距離を測り、さらに極限曲面上の垂線の足における法線を求め、初期制御点と極限曲面との最短距離だけ法線方向ヘオフセットする。この工程を繰り返すことにより、極限曲面を初期制御ポリゴンヘ補間させる制御点位置を求める。【００９５】
図９のフローチャートにおいて、点群ＰＮから三次元の制御ポリゴンＭNΔを得する。なお、予め求めて記憶手段に記憶しておいた三次元の制御ポリゴンＭNΔを読み出しても良い。三次元の制御ポリゴンとしては、例えば、三角形ポリゴンメッシュや四角形ポリゴンメッシュを用いることができ、三角形ポリゴンメッシュの細分割手法としてはＬｏｏｐ細分割（非特許文献３）が知られ、四角形メッシュの細分割手法としてはＣａｔｍｕｌｌ−Ｃｌａｒｋ細分割（非特許文献４）、Ｄｏｏ−Ｓａｂｉｎ細分割（非特許文献５）等が知られている（Ｓ３１）。【００９６】
図１０（ａ）はＳ３１の状態を示している。取得した制御ポリゴンＭNΔを初期制御ポリゴンＭNCとして記憶部２ａに記憶し（Ｓ３２）、この初期制御ポリゴンメッシュＭNCを制御点Ｐk-1iとして記憶する（Ｓ３３）。【００９７】
記憶した制御点Ｐk-1iを用いて細分割処理を行い、極限曲面Ｓ0を生成する。ここで最初に垂線を下ろすときはＰk-1i＝Ｐiとなる。細分割処理は、例えば三角形ポリゴンメッシュの場合には前記したＬｏｏｐ細分割補間を用いることができる（Ｓ３４）。図１０（ａ）はＳ３４の状態を示している。この細分割処理は、演算処理プログラム記憶部２ｃから演算処理プログラムを読み出すと共に、この演算処理プログラムに演算ツールが記述されている場合には、演算ツールプログラム記憶部２ｂに記憶される演算ツールを用いて、初期制御点Ｐiを用いて微分幾何学演算を実行する。図１０（ｂ）はＳ３４の状態を示している。【００９８】
以下、Ｓ３５，Ｓ３６の第１の補間処理とＳ３７〜Ｓ３９の第２の補間処理を繰り返して、点群を補間する曲面Ｓiを生成する。【００９９】
第１の補間処理において、初期制御点Ｐiから曲面Ｓ（Ｓ３４の工程で生成した場合には曲面Ｓ0、あるいはＳ４０の工程で生成した制御点Pk-1iにより定義される曲面Ｓi）上に垂線を下ろし垂線の足ｆkiを求める。なお、最初に垂線を下ろすときのみＰi＝Ｐk-1iとなる（Ｓ３５）。初期制御点Ｐiと垂線の足ｆkiとの間の距離‖Ｐi−ｆki‖を求める。求めた垂線の足ｆkiは、曲面Ｓ（Ｓ0，Ｓi）上における初期制御点Ｐiの近傍点である。垂線及び距離を求める演算は、幾何学演算によって求めることができる（Ｓ３６）。図１０（ｂ）は、補間処理において垂線及び距離を求める演算のＳ３５，Ｓ３６の状態を示している。【０１００】
なお、前記した二次元での第１の補間処理と同様に、垂線は初期制御点から曲線または曲面へ下ろす。最初に垂線を下ろすときだけ、曲面を定義する制御点と、垂線を下ろす初期制御点が同じものとなる。【０１０１】
次に、第２の補間処理において、曲線曲面Ｓ（Ｓ0，Ｓi）上の垂線の足ｆkiでの法線を求め（Ｓ３７）、求めた法線方向へ、Ｓ３６で求めた初期制御点Ｐiと垂線の足ｆkiとの間の距離‖Ｐi−ｆki‖だけ、現在の極限曲面を定義する制御点Ｐk-1iの位置をオフセットし（Ｓ３８）、オフセットした位置を制御点Ｐk-1iの新たな位置とする。【０１０２】
法線を求める演算、及び制御点の位置をオフセットする演算は、微分幾何学演算によって求めることができる（Ｓ３９）。図１０（ｃ）は、補間処理において制御点Ｐk-1iの位置をオフセットし、オフセットした位置を制御点Ｐk-1iの新たな位置とするＳ３７〜Ｓ３９の状態を示している。【０１０３】
Ｓ３９で得た制御点Ｐk-1iの新たな位置に基づいて細分割処理を行って曲面Ｓiを生成する（Ｓ４０）。図１０（ｄ）は、初期制御ポリゴンＰiを制御ポリゴンとしたときのＳ４０の状態を示している。【０１０４】
Ｓ４０で求めた曲面Ｓiと初期制御ポリゴンＰiとの距離を求め、求めた距離が予め定めたしきい値とを比較し、距離がしきい値を満たす、あるいはしきい値以下となるまで、前記Ｓ３５〜Ｓ４１の工程を繰り返す。【０１０５】
Ｓ４１で求めた曲面Ｓiと初期制御ポリゴンＰiとの距離は、点群を補間する曲面と点群との誤差を表しており、しきい値は点群を補間する曲面に対して許容することができる許容誤差に相当する。【０１０６】
点群と曲線又は曲面との距離は、各初期制御点における垂線の足と制御点に対応する点との間の距離の平均自乗距離、又は最大自乗距離とすることができる【０１０７】
したがって、Ｓ４２の比較工程において、距離がしきい値以下となったことを確認することで、得られた曲面Ｓiは点群（初期制御ポリゴン）を許容誤差範囲内で補間するものとなる（Ｓ４３）。【０１０８】
上記した第１の補間処理について、図１１〜図１６を用いてより詳細に説明する。【０１０９】
前記したように、第１の補間処理では、初期制御点Ｐiから極限曲面Ｓへ垂線を下ろすことで初期制御点Ｐiと極限曲面Ｓとの最短距離を求める。この最短距離の演算は、制御点から極限曲面上への正射影の計算に相当する。この計算には当たり、Stamの理論（非特許文献７）を適用することができる。このStamの理論では、パラメータ領域となる三角形パッチに属する特異点の数が高々１つでなければならない。なお、特異点を含まない正則な曲面は１２個の制御点により定義される。【０１１０】
図１１は、特異点を備える三角形パッチの細分割処理を説明するための図である。図１１（ａ）は２個の特異点（図中のＡ，Ｂ）を含む三角形パッチを示している。【０１１１】
ここで、三角形パッチに属する特異点の数を高々１つとするために、対象となる制御点まわりのポリゴンに対して局所的にLoop細分割手法を１回適用する。図１１（ｂ）は、対象となる制御点について１回の細分割した三角形パッチを示し、図１１（ｃ）〜図１１（ｆ）は、この細分割により生成される４つの細分割パッチを示している。この４つの細分割パッチの内で、図１１（ｃ），図１１（ｄ）に示す細分割パッチは１つの特異点を有し、図１１、（ｅ），図１１（ｆ）に示す細分割パッチは特異点を有していない。【０１１２】
したがって、対象となる制御点まわりのポリゴンに対して局所的にLoop細分割手法を１回適用することによって、パラメータ領域となる三角形パッチに属する特異点の数を高々１つとすることができる。【０１１３】
対象となる制御点の位数(valence)がＮの場合、その制御点周りのLoop細分割パッチもＮ個であり、最初にその中から垂線を下ろす極限曲面を生成する三角形パッチ(以後パラメータ領域と呼ぶ)を選び出す必要がある。しかしながら、前もってそのパラメータ領域を選ぶことは困難である。【０１１４】
ここでは、Half−Edge構造体を利用して、その制御点から最初に参照される面のLoop細分割パッチにおいて制御点に最も近いパラメータ領域とする。なお、Half−Edge構造体は、頂点(Vertex)、稜線(Edge)、面(Face)により構成されるポリゴンメッシュの要素を効率的に扱うためのデータ構造の一つであり、一般的に面(Face)、稜線(Edge)、半稜線(Half−Edge)、頂点(Vertex)、ループ(Loop)の５種類のデータ構造からなるソリッドモデル用データ構造である。なお、Half-Edge構造体は５種類のデータ構造の他に、ループや稜線のデータ構造を含まない構造とするものもある。このデータ構造では、１本の稜線に対して向きの異なる１対の半稜線(Half−Edge)を定義し、この半稜線により稜線の両端の頂点や稜線を挟む面のデータを効率的に扱うことができる。【０１１５】
図１２において、黒丸で示す点は初期制御点（補間点）、この制御点を通る太い実線は制御点周りにおける分割前のポリゴン、細い実線および破線は１回細分割を行ったポリゴンを示している。また、薄い地模様の部分は垂線が下りる極限曲面パッチを生成し得る細分割パッチ(パラメータ領域)、濃い地模様の部分は制御点からHalf-Edge構造体を利用して最初に参照される面における細分割パッチを示している。図１２（ｂ）において、濃い地模様で示される細分割パッチ上の白抜きの点は初期値となるパラメータ位置を示している。【０１１６】
つまり、初期制御ポリゴンに対して１回Loop細分割手法を適用して得られる細分割パッチにおいて、対象となる頂点に近い局所的な細分割パッチから構成される制御ポリゴンによって生成される極限曲面パッチヘ垂線を下ろすことになる。【０１１７】
次にパラメータ領域において垂線の足となる点を求める。図１３は、パラメータ領域に対する垂線を説明するための図である。図１３において、Ｔpは接平面、Ｐは初期制御ポリゴンの頂点、Ｄ（v,w）はパラメータ（v,w）における極限曲面上の点、（Δｖ，Δw）は曲面のアップデートパラメータ、ｉは制御点番号、ｊはニュートン法の繰り返し回数をそれぞれ示している。【０１１８】
1つの制御点から極限曲面への垂線は次式により与えられる。
［（Ｐ−Ｄ(v,w)）・Ｄｖ (v,w)］＝０
［（Ｐ−Ｄ(v,w)）・Ｄｗ (v,w)］＝０                          …（１）【０１１９】
なお、ｖとｗは曲面のパラメータであり、Ｄｖ、Ｄwは細分割曲面Ｄのｖ、ｗ方向の微分を示している。【０１２０】
各制御点Ｐから、それらによって張られる細分割曲面Ｄ上の最短距離となる点は、Marinov and  Kobbelt（非特許文献７）によると、Ｐから接平面への垂線は曲面のパラメータ（Δｖ、Δｗ）に関する以下の線形システムを解くことにより求めることができる。
［Ｐ−(Ｄ(v,w)＋Ｄｖ(v,w)Δｖ＋Ｄｗ(v,w)Δｗ)］・Ｄｖ(v,w)］ij＝０  
［Ｐ−(Ｄ(v,w)＋Ｄｖ(v,w)Δｖ＋Ｄｗ(v,w)Δｗ)］・Ｄｗ(v,w)］ij＝０  …（２）【０１２１】
ここで、iは制御点番号、jはパラメータ化におけるニュートン法の繰返し回数である。また、式(２)は線形であるため、次のように(△ｖ,△ｗ)について解くことができる。
Δv＝
［（Ｐ−Ｄｖ(v,w)）Ｄｗ(v,w)・Ｄｗ(v,w)−（Ｐ−Ｄｖ(v,w)）Ｄｗ(v,w)・Ｄｗ(v,w)］／Det                                                            
Δv＝
［（Ｐ−Ｄｖ(v,w)）Ｄｗ(v,w)・Ｄｗ(v,w)−（Ｐ−Ｄｖ(v,w)）Ｄｗ(v,w)・Ｄｗ(v,w)］／Det                                                            …（３）【０１２２】
ここで、Detは
【数１】
2007083602.tif 000004
により示され、式（２）を展開することにより得られる係数行列の行列式である。【０１２３】
式(３)について、(△ｖ,△ｗ)→(０，０)となるようにニュートン法で逐次パラメータ修正を行う。【０１２４】
また、２回目のニュートン法の初期値はそのパラメータ領域の重心におけるパラメータとし、２回目以降の計算では初期値は前回の計算で垂線の足となる極限曲面上のパラメータとした。したがって、２回目以降の計算は新たにパラメータ領域を探す必要もなく初期値も近傍点のパラメータに近いため、さらに高速に垂線を下ろすことができる。【０１２５】
ここで、Marinov and  Kobbelt（非特許文献７）によると、MarinovとKobbelt[19]によると、パラメータ(△ｖ,△ｗ）に関して次の３つの場合わけを考慮する必要がある。【０１２６】
１．パラメータ(ｖ+△ｖ,ｗ＋△ｗ) ijが同じパラメータ領域内にあるとき、その領域内でニュートン法を繰り返す。
２．パラメータ(ｖ+△ｖ,ｗ＋△ｗ) ijが前回計算したパラメータ領域に隣接する別のパラメータ領域にあるとき、０＜λ＜１となる係数λにより(△ｖ,△ｗ) ijをスケーリングすることで、(ｖ+λ△v,ｗ＋λ△w) ijを現在のパラメータ領域の境界上に置く。これは次のニュートン法のアップデートベクトル(ｖ+λ△v,ｗ＋λ△w) ij+1が前回のアップデートベクトルと同じ方向を向くか、反対の方向を向くかを予測することは困難だからで
ある。
３．すでにパラメータ(ｖ+λ△v,ｗ＋λ△w) ijが境界上にあり、隣接するパラメータ領域に属しているときはその領域内でニュートン法を行う。【０１２７】
通常、ニュートン法によりパラメータ修正を行うことで収束へ向かえば初期制御点と曲面との距離が小さくなるが、期待するパラメータヘ向かわない場合がある。つまり、‖Ｐi−Ｄ(v,w) ij+1‖＞‖Ｐi−Ｄ(v,w) ij‖となることがある。このような場合、通常はパラメータ修正におけるアップデートベクトルの長さが正しくないことを意味しており、これは多変数関数の根を求めるアルゴリズムにおいて共通した挙動である。ロバストな方法でこのような状況を扱うために、ここでは信頼性が高い単変数の最適化手法であるBrent法（非特許文献８）により、初期制御点と曲面との距離関数g(h)＝‖Ｐi−Ｄ(v,w) ij+1＋hｑi,j‖，h∈（０，１）において最小のｈを求める。ここでｑi,j‖＝（Δv,Δw）ijである。最終的に、Brent法により求まるｈによりパラメータは(ｖ＋hΔv,w＋hΔw) ijとなる。【０１２８】
ここで、パラメータ修正の具体的な例について言及する。はじめに、各細分割パッチにおける面積座標系の定義について説明する。図１１は細分割パッチ上の面積座標系を示している。図１１において、パラメータ領域となる細分割パッチを示し、斜線を施した頂点（最外郭にある３つの頂点）が頂点分割により生成される点(vertex point)であり、白抜きの頂点（大きな三角形の辺上にある頂点）が面分割により生成される(edge point)点である。斜線を施した頂点は分割前の位数を保持するため特異点となることがあるが、白抜きの頂点は位数６の正則点となる。Stamの理論を用いるにあたり、特異点における面積座標(barycentric coordinate)をu＝1.0と定めるため、このアルゴリズムにおいてはHalf−Edge構造体との兼ね合いもあり、図１４に示すように定義している。また、このような領域の順序付けはパラメータ修正ごとに行うものではなく、あらかじめ各面において行っている。【０１２９】
はじめに、同じ面内における移動について説明する。【０１３０】
図１５（ａ），（ｂ）は対象となる制御点が特異点である場合について、１つの面が定義するパラメータ領域間の移動について示したものである。【０１３１】
図１５（ａ）において、ニュートン法の初期値は対象となる制御点に最も近いパラメータ領域（図中（ａ））としている。各パラメータ領域（ａ）〜（ｄ）の面積座標系は図１４に示したとおりである。【０１３２】
パラメータ領域（ａ）におけるニュートン法でｕ＜0.0、つまりv+w＞1.0となったときの領域（ａ）から領域（ｄ）へのパラメータ領域の変更を示している。例えば、ｖ＜0.0となった場合は向かって右側の隣接面の定義するパラメータ領域に、ｗ＜0.0となった場合は向かって左側の隣接面の定義するパラメータ領域に変更する。さらに、パラメータ領域（ｄ）のニュートン法においてｕ＜0.0となれば領域（ｃ）へ、ｗ＜0.0となれば、領域（ｄ）へさらにパラメータ領域が変更される。【０１３３】
次に、特異点を共有する隣接面への移動について説明する。図１５（ｃ），（ｄ）は対象となる制御点が特異点かつ隣接面の定義するパラメータ領域へ変更する場合を示している。【０１３４】
パラメータ領域（ａ）におけるニュートン法でｖ＜0.0となった場合、図１５（ｃ）のように向かって右側の隣接面の定義するパラメータ領域へ変更する。ここで、前回ニュートン法を行ったパラメータ領域を定義する面と移動先の隣接面が同じ特異点を共有している場合は、隣接面のパラメータ領域（ａ），（ｂ），（ｃ），（ｄ）は一意的に決定する。【０１３５】
次に、共有する特異点以外にも特異点を含む隣接面への移動について、図１６（ａ），（ｂ）を用いて説明する。【０１３６】
図１６（ａ），（ｂ）に示すように、移動先の隣接面が移動前の面と共有する特異点以外にも特異点を持つ場合、移動先の隣接面のパラメータ領域は一意的に決定することはできない。【０１３７】
パラメータ領域の順序付けはあらかじめ行われており、例えば、特異点が２つある場合には図１６（ｃ），（ｄ）のように２通りの順序付けが考えられる。この２つの順序付けではパラメータ領域（ｄ）の面積座標系が異なってしまうため、移動先のパラメータ領域がどのように順序付けされているかを判別する必要がある。【０１３８】
上記した処理を含めた、近傍点を求める第１の補間処理は、以下のアルゴリズムとなる。【０１３９】
ステップ１：制御点から極限曲面へ垂線を下ろすにあたり、あらかじめどの曲面パッチに垂線が下りるか予測できないため、初期パラメータ領域をHalf−Edgeより最初に参照される面と仮定し、その面に対して細分割を適用することによりパラメータ領域(細分割パッチ)を定義する。また、Half-Edgeのループ方向に従い、パラメータ領域の順序付けを行う(図１４)。
ステップ２：ニュートン法の初期値として、対象とする制御点に最も近いパラメータ領域の重心におけるパラメータを選ぶ(図１２（ｂ）)。
ステップ３：各パラメータ領域においてパラメトリック曲面を定義するための制御点を選び出す。図１１（ｃ）〜（ｆ）に示すように４つの制御ポリゴンを定義する(図は特異点が２つある場合の例を示している)。
ステップ４：Stamの理論より現在のパラメータにおける曲面上の位置や微分量を計算し、それらをもとに式(３)に従ってニュートン法によりパラメータのアップデート量(△ｖ,△ｗ)を求め、新たなパラメータ(v,w)を算出する。
ステップ５：アップデートベクトル(△ｖ,△ｗ)がしきい値内に収束すれば、そのパラメータにおける曲面上の点を初期制御点からの近傍点とみなし終了する。収束しなければステップ６以降を行う。
ステップ６：前回のパラメータにおける曲面上の位置とアップデート後の位置を比較し、初期制御点との距離が大きくなった場合、Brent法により補正を行う。
ステップ７：もしアップデートによりパラメータ(v,w)がパラメータ領域から外へ出た場合には、例えば、現在属する面が定義する別のパラメータ領域へ移動、現在属する面の隣接面が定義するパラメータ領域へ移動等の他のパラメータ領域への移動を行う。
ステップ８：パラメータ領域の変更がなければ、ステップ４へ戻り同じパラメータ領域内で計算を繰り返す。パラメータ領域の変更があった場合はステップ３へ戻り、あらたなパラメータ領域に対する制御点を選び出す。【０１４０】
ここで、ニュートン法の収束性について説明する。ここではオフセットごとのニュートン法の繰り返し回数を示すことにより、ニュートン法の収束性を検討する。なお、２回目以降のニュートン法の計算では新たにパラメータ領域を探す必要がないため、さらに高速に垂線を下ろすことができる。【０１４１】
図１７(a)〜(c)は、頂点数4948点のモデル（HappyBuddhaモデル）に対し、細分割曲面補間を行ったときのオフセットごとのニュートン法の繰り返し回数に対する頂点数をヒストグラムにまとめたものである。【０１４２】
１回目のオフセットではパラメータ領域を探す必要があるため、平均約１０回のニュートン法を繰り返しているが、２回目以降は約５回、９回目は約２回で収束する。グラフ中、繰り返し数２０回となる頂点があるが、このような場合は大抵、垂線の下り得る点が複数点あることが経験的に分かっている。例えば、初期制御点と曲面との位置関係から垂線を複数の採り得る場合には、ニュートン法では垂線の足となる複数の点間で振動を起こし、どちらか一方に収束することがない。また、図１７（ｄ）は補間回数の演算時間の変化を示している。【０１４３】
本発明の補間のアルゴリズムによれば、図１７のグラフからも分かるように、オフセットを繰り返していくと、このような点は非常に少なくなり、さらに初期ポリゴンメッシュを構成する頂点数が多くなるほど、このような頂点はさらに少なくなるため、垂線の足となり得る点のどれを扱っても曲面品質への影響は小さいと考えられる。【０１４４】
したがって、本発明による補間のアルゴリズムは優れた収束性を有しており、２，３回の補間処理で制御点をオフセットすることより高精度な補間曲線を生成することができる。なお、尖った形状などでは滑らかな部分に比べ収束が遅くなる傾向がある。そのような部分に対しては全体のオフセットにより補間曲線を生成した後、収束が遅い頂点のみ選び出して、局所的にオフセットを繰り返すことにより高精度の補間曲線へと仕上げることができる。【０１４５】
次に、本発明の制御点をオフセットする第２の補間処理においてさらに説明する。【０１４６】
図３（ｂ）で示したように、オフセット方向を垂線の足における単位法線ベクトルＮと距離ベクトルＶｄ（＝Ｐi−ｆi）の内積Ｎ・Ｖｄ＝（Ｎ・（Ｐi−ｆi））の符号により、オフセットベクトル（アップデートベクトル）Ｖu±を以下のように定義され、
（Ｎ・（Ｐi−ｆi））＞０：Ｖu+
（Ｎ・（Ｐi−ｆi））＜０：Ｖu-              …（４）
Ｑオフセットベクトルは
Ｖu±＝（Ｎ・（Ｐi−ｆi））Ｎ    …（５）
となるので、このベクトルを現在の制御点位置に加えることにより、次のようにオフセット後の新たな制御点位置を求めることができる。
Ｐi(k+1)＝Ｐi(k)＋Ｖu±【０１４７】
なお図３では２次元で示しているが、３次元の曲面補間においても全体のオフセットを行った後、収束が遅く、高精度に補間することができなかった頂点に対して局所的にオフセットを繰り返すことで、高精度な曲面補間を行うことができる。【０１４８】
次に本発明の補間処理の収束性の解析的な証明について説明し、実際のモデルにおける収束性例を示す。【０１４９】
ここでは２次の一様B-Spline曲線を用い、その中点を垂線の足として解析を行うが、B-Spline曲面や細分割曲面についても適用することができる。【０１５０】
２次の一様B-Spline曲線は次のように定義される。
ｒ(t)＝Ｐj-1Ｎ0(t)＋ＰjＮ1(t)＋Ｐj+1Ｎ2(t)                        …（６）【０１５１】
ここで、Ｐj-1、Ｐj、Ｐj+1は制御点、Ｎ0(t)、Ｎ1(t)、Ｎ2(t)は以下で与えられる２次のB-Splineにおける基底関数である。
Ｎ0(t)＝1/2（１−ｔ）2、Ｎ1(t)＝1/2＋ｔ−ｔ2、Ｎ2(t)＝1/2ｔ2    …（７）【０１５２】
ここで、制御点Ｐj から曲線への垂線の足を曲線の中点とすると
ｆj(1)＝ｒ(1/2)＝1/8（Ｐj-1＋６Ｐj＋Ｐj+1)                        …（８）
となり、制御点Ｐj と垂線の足ｆj(1)との距離ベクトルは
d j(1)＝Ｐj−ｆj(1)＝1/8（−Ｐj-1＋２Ｐj−Ｐj+1)              …（９）
で与えられる。【０１５３】
新たな制御点位置は現在の制御点位置に曲線までの距離d j を加えたものとなるから
Ｐj(2)＝Ｐj(1)＋d j(1)＝1/8（−Ｐj-1＋１０Ｐj−Ｐj+1)    …（１０）
で与えられる。さらに同様にして
Ｐj-1(2)＝Ｐj-1＋d j-1(1)＝1/8（−Ｐj+2＋１０Ｐj-1−Ｐj)         …（１１）
Ｐj+1(2)＝Ｐj+1＋d j+1(1)＝1/8（−Ｐj＋１０Ｐj+1−Ｐj+2)        …（１２）
が得られる。式(８)により、新たな垂線の足は
ｆj(2)＝1/8（Ｐj-1(2)＋６Ｐj(2)＋Ｐj+1(2))            …（１３）
となり、距離ベクトル
d j(2)＝1/8（Ｐj-1(2)＋６Ｐj(2)＋Ｐjj+1(2))            …（１４）
を得ることができる。【０１５４】
この幾何プロセスを距離ベクトルがある閾値よりも小さくなるまで繰り返す。【０１５５】
表１に5回までのオフセットにおける距離ベクトルの係数を示す。
【表１】
2007083602.tif 000005
【０１５６】
また、帰納的に次の漸化式が得られる。
【数２】
2007083602.tif 000006
…（１５）【０１５７】
式(１５)においてｋが大きくなるにつれ距離ベクトルが零に収束すればよい。Ｐj(i=k)が最も大きい係数となるため、この係数の収束性について検討する。ｋ回目のオフセットにおいてＰjの係数は
【数３】
2007083602.tif 000007
…（１６）
となる。ｋ+1回目のオフセットにおける係数との比は
ａｋ＋１/ａｋ＝（２ｋ＋１）/（４（ｋ＋１））                        …（１７）
となり、式（１５)は収束することがわかる。結果としてｋが無限大になれば式(１５)は零に収束する。したがって、本発明の補間処理の幾何アルゴリズムが初期ポリゴンを補間することが証明される。【０１５８】
次に、実際のモデルにおける収束性の例に説明する。【０１５９】
図１８は、一モデルにおけるオフセット回数に対する誤差の変化を示している。図１８において、細い実線は頂点数が562の例を示し、太い実線は頂点数が4988の例を示している。なお、ここで示すモデルは、図１９に示した562点のbunnyモデルの例である。誤差は頂点と補間曲面との距離のbounding box(モデルが含まれる最小の直方体)の対角線に対する割合を平均した平均自乗距離誤差を用いて評価を行った。【０１６０】
頂点数562の粗いbunnyモデルにおいても、1回のオフセットにより誤差の割合を0.05％程度まで小さくすることができる。また、頂点数4988のモデルは頂点数が多く、元形状をより詳細に表現しているため誤差の減少率は小さくなるが、どちらも数回程度のオフセットで十分な精度が得られる。【０１６１】
従来の手法はパラメータ修正やフィッティングの最適化を何度も行うのに対し、本発明の補間処理によれば数回のオフセットにより高い精度で曲面補間を行うことができ高い収束性をもつ。【０１６２】
本発明の補間処理は上記のように制御ポリゴン全体をオフセットして補間を行うだけでなく、収束が遅く精度よく補間できなかった曲面部分に対して、その曲面に影響を与える局所的な制御点のオフセットを繰り返すことにより、精度の改善を行うことも可能である。【０１６３】
また、このように局所的なオフセットを行うことにより、すでに十分な精度で補間できている部分を除いて形状処理を行うことができるため、曲面生成時間の短縮につながる。【０１６４】
図２０〜図２２は、本発明の補間処理結果の一例を示している。図２０はRocker-Armの例であり、http://Cyberware/samplesを参照している。【０１６５】
また、図２１はStanford Bunnyの例であり、図２２はHappy Buddhaの例であり、http://graphics.stanford.edu/data/3Dscanrep/を参照している。【０１６６】
各図は、入力した初期メッシュ、初期メッシュと補間した細分割曲面、補間した細分割曲面を示している。【０１６７】
これらの各図に補間頂点数、全体のオフセット回数、最大自乗距離誤差、平均自乗距離誤差、計算時間を以下の表２に示す。【０１６８】
【表２】
2007083602.tif 000008
【０１６９】
図２３は補間結果例であり、円環形状の補間例を示している。図２３（ａ）は円環形状を粗いポリゴンで表したメッシュ図であり、図２３（ｂ）は従来の補間によって得られる補間結果を示し、図２３（ｃ）は本発明の補間によって得られる補間結果を示し、図２３（ｄ）は補間で得られた円環と制御ポリゴンとの関係を示している。【０１７０】
図２３（ｂ）に示す従来の補間で得られた円環形状には歪みが生じることが確認される。これに対して、図２３（ｃ）に示す本発明の補間で得られた円環形状には歪みを含まず、円滑な形状を得ることができる。【０１７１】
図２３に示すように、本発明の補間処理によれば、従来の補正処理で見られた歪みの発生を解消することができる。【０１７２】
図２４は補間頂点数に対する計算時間を示している。本発明の補間処理の計算コストは頂点数Ｎと全体のオフセット回数Ｍのかけ合わせであるＯ（ＮＭ)であると考えられる。図２１に示すグラフからもその線形性を確認することができる。従来の曲面フィッティング手法の解法としてはCG法(Conjugate Gradient Method)やSVD(Singular Value Decomposition)などがあげられるが、これらの手法の計算コストはＯ(Ｎ)〜 Ｏ(Ｎ２)である。本発明の補間処理における全体のオフセット回数は、入力したポリゴンメッシュの詳細度や形状の複雑さにもよるが、Ｍ≪Ｎであるため、従来手法と比較しても計算コストを削減あるいは同程度とすることができている。【０１７３】
本発明の補間処理と従来の補間処理とを、処理時間および歪みの発生との関係で比較すると、本発明の補間処理によれば、歪みを発生させることなく、従来の補間処理と同程度で、あるいは条件によっては高速で処理することができ、従来の補間処理後のフェアリング処理による歪みの除去処理を考慮すると、十分に高速で処理することができる。【０１７４】
例えば、補正後の形状誤差を0.01％〜0.05％程度とする場合には、本発明の補間処理は従来の補間処理よりも短時間、あるいは同程度の時間で処理することができる。また、形状誤差を0.01％を下回る程度とした場合には、本発明の補間処理は従来の補間処理より処理時間を要するが、歪みを発生させることなく良好な補間結果を得ることができる。【０１７５】
上記説明ではLoop細分割曲面補間を用いて説明したが、Catmull-Clark細分割曲面に対しても全く同様のアルゴリズムで曲面補間を行うことができる。また、平面曲線についても補間が可能であり、本発明の補間処理はが制御点で定義される曲線および曲面に対して有効に適用することができる。【０１７６】
次に、細分割曲面の形状評価方法について説明する。【０１７７】
曲面の幾何学的に評価は、曲面の法線や曲率で表すことができる。【０１７８】
パラメトリック曲面ｒ＝ｒ（u,v）において、弧長ｄsは
ｄs＝｜ｒｕ・ｄu/ｄt＋ｒｖ・ｄv/ｄt｜ｄt
＝（Ｅｄu2＋２Ｆｄuｄv＋Ｇｄv2）1/2                    …（１８）【０１７９】
ここで、ｒｕはｒのパラメータｕについていの偏微分、ｒｖはｒのパラメータｖについていの偏微分を表し、Ｅ，Ｆ，Ｇは第一基本形式係数と呼ばれ、
Ｅ＝ｒｕ・ｒｕ、Ｆ＝ｒｕ・ｒｖ、Ｇ＝ｒｖ・ｒｖ                  …（１９）
で表され、第一基本形式（弧長Ｉ）は
Ｉ＝ｄｓ2＝Ｅｄu2＋２Ｆｄuｄv＋Ｇｄv2                      …（２０）
で表される。【０１８０】
また、法曲率κは
κ＝（Ｌｄu2＋２Ｍｄuｄv＋Ｎｄv2）／（Ｅｄu2＋２Ｆｄuｄv＋Ｇｄv2）…（２１）
で表され、式（２１）の分子は第二基本形式と呼ばれる。【０１８１】
ここで、Ｌ，Ｍ，Ｎは第二基本形式係数と呼ばれ、
Ｌ＝ｒｕｕ・Ｎ、Ｍ＝ｒｕｖ・Ｎ、Ｇ＝ｒｖｖ・Ｎ                  …（２２）
で表され、λ＝ｄu/ｄvとおくと、法曲率κは、
κ＝（Ｌ＋２Ｍλ＋Ｎλ2）／（Ｅ＋２Ｆλ＋Ｇλ2）            …（２３）
と表される。【０１８２】
この法曲率κの極値κ1，κ2を求めると、
κ1＝Ｈ＋（Ｈ2−Ｋ）1/2                                  …（２４）
κ2＝Ｈ−（Ｈ2−Ｋ）1/2                                  …（２５）
となり、最大主曲率はκ1、最小主曲率はκ2である。
ここでKはガウス曲率、Hは平均曲率である。【０１８３】
また、接平面上で法曲率が最大値、最小値をとる方向を主方向であり、
ｕｖ平面における最大、最小主曲率の主方向は
λ＝（Ｌ−κnＥ）／（Ｍ−κnＦ）                          …（２６）
又は
λ＝（Ｍ−κnＦ）／（Ｎ−κnＧ）                          …（２７）
である。【０１８４】
ここで、κｎにκ1，κ2を代入することで、最大、最小主曲率の主方向に対応するλが得られる。【０１８５】
三次元空間上への変換は
ｐ＝（ｒｕ＋λｒｖ）／｜ｒｕ＋λｒｖ｜                      …（２８）
で行うことができる。【０１８６】
したがって、曲面ｒ（ｕ，ｖ）のｕｖ平面おける前記最大、最小主曲率κ1又はκ2を前記式（２４），（２５）の演算、式（２８）中のκに代入してｕｖ平面から３次元空間への変換処理を、それぞれプログラム又は演算回路で行い、求めたｐを３次元空間における細分割曲面の主方向を評価する評価値として出力することで、細分割曲面の形状評価を行うことができる。【０１８７】
図２５は、本発明の補間処理によって求めた法線ベクトルのオフセットごとにおける誤差を示している。また、Angle Weighted法によって得られた結果（ほぼ0.78度）を比較として示している。【０１８８】
オフセットなしで法線を求めた場合、つまり、初期ポリゴンにより定義される極限曲面で法線を求めた場合、解析解との誤差は約0.97度であったが、1度オフセットを行うと約0.35度まで誤差を小さくすることができる。【０１８９】
それ以上オフセットを数回繰り返しても明確な精度の向上は見られなかった。これは、形状が単純な場合やポリゴンが荒くない場合、1回のオフセットだけで初期ポリゴンと極限曲面との誤差を十分小さくできると考えられるためである。【０１９０】
また、Angle Weighted法では解析解との平均誤差は約0.78度であった。この手法は比較的精度のよい手法であり、本発明の補間処理がポリゴンメッシュの法線を求める上で他の手法よりも有効な手法である。
【産業上の利用可能性】
【０１９１】
本発明は、３Ｄモデリングの分野におけるリバースエンジニアリングに適用することができる。
【図２】
2007083602.tif 000009
【図３】
2007083602.tif 000010
【図４】
2007083602.tif 000011
【図５】
2007083602.tif 000012
【図６】
2007083602.tif 000013
【図７】
2007083602.tif 000014
【図９】
2007083602.tif 000015
【図１２】
2007083602.tif 000016
【図１３】
2007083602.tif 000017
【図１４】
2007083602.tif 000018
【図１５】
2007083602.tif 000019
【図１６】
2007083602.tif 000020
【図１７】
2007083602.tif 000021
【図１８】
2007083602.tif 000022
【図２５】
2007083602.tif 000023
【図１】
2007083602.tif 000024
【図８】
2007083602.tif 000025
【図１０】
2007083602.tif 000026
【図１１】
2007083602.tif 000027
【図１９】
2007083602.tif 000028
【図２０】
2007083602.tif 000029
【図２１】
2007083602.tif 000030
【図２２】
2007083602.tif 000031
【図２３】
2007083602.tif 000032
【図２４】
2007083602.tif 000033
【手続補正書】
【提出日】平成20年7月25日(2008.7.25)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
【非特許文献１】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
【非特許文献２】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
【非特許文献３】C.T.Loop.Smooth subdivision surface based on triangle.Masters thesis,Department of Mathematics. University of Utha.1987/.
【非特許文献４】E.Catmull and J.Clark. Recusively generated b-spline surfaces on arbitrary topological meshes.Computer-Aided Design,10(6):350-355,1987.
【非特許文献５】D.Doo and M.Sabin. Behavior of recursive division surfaces near extraordinary points.Computer-Aided Design,10(6):356-360,1978.
【非特許文献６】G.M.Chaikin.An algorithim for high-speed curve generation. Computer Graphics and Image Processing,3:346-349,1974.
【非特許文献７】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.
【非特許文献８】M.Marinov and L.Kobbbelt, Optimization methods for scattered data approximation with subdivision surface,Graphical Models 67,2005,452-473.
【非特許文献９】R.P.Brent.Algorithims for Minimization without Deriviatives.   Prentice-Half,Englewood Cliffts,N.J,1986.4.
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】変更
【補正の内容】
【００２９】
この曲線又は曲面上の近傍点は、初期制御点からの距離が最短距離でない点も含むことができ、最短距離にある点に代えて、初期制御点の近傍にある細分割された曲線又は曲面上において任意に定めた点としても良い。ここで、近傍は、細分割された複数の曲線又は曲面の内で初期制御点に近いということを意味し、この近傍にある曲線又は曲面上の点を近傍点としている。この近傍点は最短距離点が望ましいが、かならずしも最短距離である必要はなく、例えば極限曲面Ｓ∞あるいは細分割曲面Ｓi上の中心点や重心点等の任意の点としてもよく、曲線の場合には最短距離の他に例えば中間点としてもよい。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正の内容】
【００４５】
【図１】本発明の補間処理の概略を説明するための概略図である。
【図２】本発明の補間処理の概略を説明するためのフローチャートである。
【図３】本発明の補間処理の第１、第２の補間工程を説明するための図である。
【図４】本発明の補間処理装置の概略構成図である。
【図５】二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を説明するためのフローチャートである。
【図６】二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を説明するための制御点と曲線との概略図である。
【図７】二次元の点群あるいは制御ポリゴンメッシュにより曲線を生成する場合を説明するための制御点と曲線との概略図である。
【図８】二次元の点群を補間する曲線例を示す図である。
【図９】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するためのフローチャートである。
【図１０】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図１１】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図１２】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図１３】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図１４】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図１５】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図１６】三次元の点群あるいは制御ポリゴンメッシュにより面線を生成する場合を説明するための制御点と曲面との概略図である。
【図１７】オフセットごとのニュートン法の繰り返し回数に対する頂点数のヒストグラムである。
【図１８】一モデルにおけるオフセット回数に対する誤差の変化を示す図である。
【図１９】562点のbunnyモデルの例である。
【図２０】本発明の補間処理結果の一例を示す図である。
【図２１】本発明の補間処理結果の一例を示す図である。
【図２２】本発明の補間処理結果の一例を示す図である。
【図２３】補間結果例を示す図である。
【図２４】本発明による補間頂点数に対する計算時間を示す図である。
【図２５】本発明の補間処理によって求めた法線ベクトルのオフセットごとの誤差を示す図である。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００４６
【補正方法】変更
【補正の内容】
【００４６】
１…入力手段
２…記憶手段
２ａ…データ記憶部
２ｂ…演算ツールプログラム記憶部
２ｃ…演算処理プログラム記憶部
２ｄ…一次記憶部
２ｅ…演算結果記憶部
３…演算手段
４…表示手段
５…出力手段
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００５３
【補正方法】変更
【補正の内容】
【００５３】
この三角形ポリゴンメッシュＭNΔを初期制御ポリゴンメッシュＭNCとして制御点を定める（Ｓ２）。この初期制御ポリゴンメッシュＭNCを用いて細分割処理を行って初期メッシュに基づいて極限曲面Ｓ0を生成する（Ｓ３）。Ｓ３で生成した初期メッシュに基づいて極限曲面Ｓ0に補間処理を施し、制御点の位置をオフセットして修正し（Ｓ４）、修正した制御点の位置に基づいてｉ回目の制御メッシュに基づいて細分割曲面Ｓiを生成する（Ｓ５）。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
Ｓ４の補間処理は２つの補間工程Ｓ４ａとＳ４ｂとを備える。第１の補間工程Ｓ４ａでは、制御点から極限曲面Ｓ∞あるいは細分割曲面Ｓi上の近傍点を求める。この近傍点は、ある初期制御点の近傍にある極限曲面Ｓ∞あるいは細分割曲面Ｓi上にある点であり、例えば極限曲面Ｓ∞あるいは細分割曲面Ｓi上において、初期制御点からの距離が最短となる最短距離点として定めることができる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００５７
【補正方法】変更
【補正の内容】
【００５７】
なお、近傍点は最短距離点が望ましいが、かならずしも最短距離である必要はなく、例えば極限曲面Ｓ∞あるいは細分割曲面Ｓi上の中心点や重心点等、任意の点としてもよい。曲線の場合には、最短距離の他に例えば中間点としてもよい。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００６１
【補正方法】変更
【補正の内容】
【００６１】
この制御点Ｐaを用いて細分割を行うことによって細分割曲面Ｓ0が生成される。なお、最初に生成される極限曲面は極限曲面Ｓ0であり、２回目以降に生成されるｉ回目の極限曲面は極限曲面Ｓiである。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
極限曲面（Ｓ0，Ｓ1，…Ｓi，…）において、初期制御点Ｐaに対応する近傍点Ｆを求める。近傍点Ｆは、初期制御点Ｐaから極限曲面（Ｓ0，Ｓ1，…Ｓi，…）上に垂線を下ろし、その垂線の足の点とすることができる。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】変更
【補正の内容】
【００６５】
補間工程Ｓ４は、この第１の補間工程Ｓ４ａと第２の補間工程Ｓ４ｂを繰り返して行われる。この第２の補間工程Ｓ４ｂで得られた制御点Ｐを用いることで、前記したＳ５の工程によって制御ポリゴンメッシュＭNCを細分割して極限曲面Ｓiを生成する。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
入力手段１は、点群ＰNのデータ、あるいは点群ＰNから生成される制御ポリゴンメッシュＭNΔを入力し、記憶手段２中のデータ記憶部２ａに記憶する。記憶手段２は、データ記憶部２ａの他に、微分幾何学演算を行う演算ツールのプログラムを記憶する演算ツールプログラム記憶部２ｂ、補間処理の微分幾何学演算の他、細分割処理等の演算処理のプログラムを記憶する演算処理プログラム記憶部２ｃ、途中演算結果等を一時的に記憶する一次記憶部２ｄ、補間処理等によって得られた曲面の演算結果を記憶する演算結果記憶部２ｅ等を備える。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００７４
【補正方法】変更
【補正の内容】
【００７４】
演算手段３は、データ記憶部２ａに記憶された点群ＰNあるいは制御ポリゴンメッシュＭNΔのデータを用い、演算処理プログラム記憶部２ｃに記憶されるプログラムによる演算手順に従い、また、このプログラムに指定される演算ツールのプログラムを演算ツールプログラム記憶部２ｂから逐次読み出して演算処理を行う。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００９７
【補正方法】変更
【補正の内容】
【００９７】
記憶した制御点Ｐik-1を用いて細分割処理を行い、極限曲面Ｓ0を生成する。ここで最初に垂線を下ろすときはＰik-1＝Ｐiとなる。細分割処理は、例えば三角形ポリゴンメッシュの場合には前記したＬｏｏｐ細分割補間を用いることができる（Ｓ３４）。図１０（ａ）はＳ３４の状態を示している。この細分割処理は、演算処理プログラム記憶部２ｃから演算処理プログラムを読み出すと共に、この演算処理プログラムに演算ツールが記述されている場合には、演算ツールプログラム記憶部２ｂに記憶される演算ツールを用いて、初期制御点Ｐiを用いて微分幾何学演算を実行する。図１０（ｂ）はＳ３５の状態を示している。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０１２１
【補正方法】変更
【補正の内容】
【０１２１】
ここで、ｉは制御点番号、ｊはパラメータ化におけるニュートン法の繰返し回数である。また、式(２)は線形であるため、次のように(△ｖ,△ｗ)について解くことができる。
Δv＝
［（Ｐ−Ｄｖ(v,w)）・Ｄｗ(v,w) Ｄｖ(v,w)・Ｄｖ(v,w)−（Ｐ−Ｄｖ(v,w)）・Ｄｖ(v,w)Ｄｗ(v,w)・Ｄｗ(v,w)］／Det 
Δｗ＝
［（Ｐ−Ｄｖ(v,w)）・Ｄｗ(v,w) Ｄｖ(v,w)・Ｄｗ(v,w)−（Ｐ−Ｄｖ(v,w)）・Ｄｗ(v,w)Ｄｖ(v,w)・Ｄｖ(v,w)］／Det
…（３）
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０１２２
【補正方法】変更
【補正の内容】
【０１２２】
2007083602.tif 000034
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０１２８
【補正方法】変更
【補正の内容】
【０１２８】
ここで、パラメータ修正の具体的な例について言及する。はじめに、各細分割パッチにおける面積座標系の定義について説明する。図１４は細分割パッチ上の面積座標系を示している。図１４において、パラメータ領域となる細分割パッチを示し、斜線を施した頂点（最外郭にある３つの頂点）が頂点分割により生成される点(vertex point)であり、白抜きの頂点（大きな三角形の辺上にある頂点）が面分割により生成される(edge point)点である。斜線を施した頂点は分割前の位数を保持するため特異点となることがあるが、白抜きの頂点は位数６の正則点となる。Stamの理論を用いるにあたり、特異点における面積座標(barycentric coordinate)をu＝1.0と定めるため、このアルゴリズムにおいてはHalf−Edge構造体との兼ね合いもあり、図１４に示すように定義している。また、このような領域の順序付けはパラメータ修正ごとに行うものではなく、あらかじめ各面において行っている。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０１５５
【補正方法】変更
【補正の内容】
【０１５５】
表１に5回までのオフセットにおける距離ベクトルの係数を示す。
【表１】
2007083602.tif 000035
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】０１７２
【補正方法】変更
【補正の内容】
【０１７２】
図２４は補間頂点数に対する計算時間を示している。本発明の補間処理の計算コストは頂点数Ｎと全体のオフセット回数Ｍのかけ合わせであるＯ（ＮＭ)であると考えられる。図２４に示すグラフからもその線形性を確認することができる。従来の曲面フィッティング手法の解法としてはCG法(Conjugate Gradient Method)やSVD(Singular Value Decomposition)などがあげられるが、これらの手法の計算コストはＯ(Ｎ)〜 Ｏ(Ｎ2)である。本発明の補間処理における全体のオフセット回数は、入力したポリゴンメッシュの詳細度や形状の複雑さにもよるが、Ｍ≪Ｎであるため、従来手法と比較しても計算コストを削減あるいは同程度とすることができている。
【手続補正１９】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2007083602.tif 000036
【手続補正２０】
【補正対象書類名】図面
【補正対象項目名】図４
【補正方法】変更
【補正の内容】
【図４】
2007083602.tif 000037
【国際調査報告】
2007083602.tif 000038
2007083602.tif 000039
2007083602.tif 000040
2007083602.tif 000041