Top > Search of Japanese Patents > (In Japanese)補間処理方法および補間処理装置

(In Japanese)補間処理方法および補間処理装置 commons foreign

Patent code P110005006
Posted date Aug 18, 2011
Application number P2007-554883
Patent number P4934789
Date of filing Jan 15, 2007
Date of registration Mar 2, 2012
International application number JP2007050433
International publication number WO2007083602
Date of international filing Jan 15, 2007
Date of international publication Jul 26, 2007
Priority data
  • P2006-014379 (Jan 23, 2006) JP
Inventor
  • (In Japanese)前川 卓
  • (In Japanese)松本 泰典
  • (In Japanese)並木 謙
Applicant
  • (In Japanese)国立大学法人横浜国立大学
Title (In Japanese)補間処理方法および補間処理装置 commons foreign
Abstract (In Japanese)
点群から得られる初期ポリゴンを制御ポリゴンとし、この制御ポリゴンの制御点を、この制御ポリゴンで生成される極限曲面との最短距離だけ法線方向にオフセットすることによって、細分割曲面を初期ポリゴンに補間させる新たな制御点の位置を求めることによって点群を補間する細分割曲面を生成する。各制御点と最短距離にある細分割曲面上の点を求める第1の過程と、制御点を曲面から法線方向に曲面上の点と初期制御点との距離だけ移動させてオフセットさせる第2の過程を、はじめの点群と曲面上の点との距離がしきい値を満たすあるいはそれよりも小さくなるまで繰り返して、初期ポリゴンを補間する細分割曲面を生成する。これによって、線形システムを解くことなく、点群を補間する細分割曲の生成を短い演算時間で行う。
Outline of related art and contending technology (In Japanese)


自由曲面は、船、自動車、飛行機等、様々な工業製品のボディに用いられており、機能性と美しさの両方を兼ね備えるものであり、家庭電気製品や多くの消費材の外観など意匠的に美しい形状のデザイン設計に用いられる。



近年、3Dレーザスキャナによって高密度の点群データを高速かつ容易に収集することができるようになり、物体形状を高精度で測定できることが可能と成っている。例えば、3Dモデリングの分野においては、デザイナが手作業で作成したモックアップモデルを3Dレーザスキャナで計測し、コンピュータに取り込んだ点群データやポリゴンデータをもとに製品として生産するために必要な曲面データなどのCADデータを作成していくという、いわゆるリバースエンジニアリングの手法が行われている。



一般に、3DモデルはポリゴンモデルまたはNURBSやB-Splineなどの曲面パッチによりコンピュータ上で表現される。



このポリゴンモデルは位相変化などの形状処理を行う上で効率的であるが、平面で構成されるため滑らかな表面を表現することができず、さらに形状を詳細に表現するほどデータ量が膨大になるなどの問題がある。



曲面パッチは少ない制御パラメータで滑らかな曲面が表現できる反面、パッチ形状が四角形に限定される上にパッチ間の連続性を保つことが困難であるなどの問題がある。そこで、ポリゴンモデルと曲面パッチの利点を併せ持つ細分割手法が自由な幾何形状モデリングの有効な手法として注目されており、すでにアニメーションの分野では盛んに利用されている。



細分割手法とは、初期ポリゴンメッシュに対して繰り返し規則的な分割を行うことによりその形状を滑らかにし、究極的には滑らかな曲面を得る手法である。その曲面は細分割曲面(Subdivision Surface)または極限曲面と呼ばれる。細分割手法は任意の位相を持つモデルに対しても簡単に滑らかな曲面を生成できるという特徴を持ち、さらにどの部分においても曲面が滑らかなに定義されるためモデリングなど幅広い利用が進んでいる。



リバースエンジニアリングの分野において、従来、細分割曲面を用いて測定した点群データを近似あるいは補間して曲面を生成する方法が提案されている。この細分割曲面を用いて点群データを補間する従来提案される方法では、点群データから得られる初期制御点と生成される曲面との距離誤差が最小となるように制御点を逐次求める演算処理を行っている。この制御点を求める演算は、点群の列をS、この点群を近似する曲面と生成するための制御点の列をP、曲面を定める基底関数マトリックスをAとしたとき、AP=Sで表される線形の行列式を解くことで行われる。



従来提案されている補間方法として、例えば、Halstedらが提案する多面体メッシュに対するCatmull-Clark細分割曲面の補間手法が知られている(非特許文献1)。この手法は大規模な線形システムを解く必要があるばかりでなく、さらにフェアリングと呼ばれる曲面修正のために最小化問題を解く必要があり、計算コストが嵩む要因となっている。



また、Hoppeらは、点群データに対するLoop細分割曲面の近似手法として、細分割操作を行ったポリゴンメッシュを線形近似した細分割曲面とみなし、その曲面に対して各点からの正射影を行うことでパラメータ化し、各点とそれに対する線形近似した細分割曲面上の点との距離が最小となる最小自乗問題として扱う手法を提案している(非特許文献2)。



【非特許文献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.

Field of industrial application (In Japanese)


本発明は、点群データを補間して曲線あるいは曲面を生成する補間処理方法、補間処理装置、およびこの補間処理をCPUに実行させるプログラムに関する。また、補間処理方法で得られる細分割曲面ならびにポリゴンメッシュの頂点における微分幾何学的形状を評価する方法、装置、およびこの評価をCPUに実行させるプログラムを記憶するプログラム媒体に関する。

Scope of claims (In Japanese)
【請求項1】
 
制御点により定義される曲線又は曲面によって点群を補間する補間処理方法において、
曲線あるいは曲面上において、制御ポリゴンの制御点の近傍にある点を近傍点として求める幾何アルゴリズムの演算を行う第1の補間工程と、
前記制御点の位置から前記近傍点における法線方向又は前記近傍点から初期ポリゴンへ向かう方向に、前記近傍点と初期制御点との距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行う第2の補間工程とを含み、
前記第1の補間工程は、幾何アルゴリズムの演算により曲線又は曲面上において初期制御点から最短距離にある点を近傍点として求め、
前記演算処理を前記幾何アルゴリズムを組み込んだ演算手段により行うことを特徴とする、補間処理方法。

【請求項2】
 
前記第1の補間工程は、初期制御点から制御ポリゴンにより定義される曲線あるいは曲面上に垂線を下ろし、当該垂線の曲線あるいは曲面上の垂線の足の位置を近傍点とする幾何アルゴリズムの演算を行い、
前記第2の補間工程は、前記垂線の方向を法線方向とし、前記垂線の足と初期制御点との間の距離を求め、現時点における曲線又は曲面を定義する制御点を曲線又は曲面の法線方向に前記距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行うことを特徴とする請求項1に記載の補間処理方法。

【請求項3】
 
前記演算処理で得た制御点に基づいて曲線又は曲面を求め、
初期制御点である補間点と前記求めた曲線又は曲面との距離としきい値とを比較し、前記距離がしきい値を満たす、又はしきい値よりも小さくなるまで、前記第1の補間工程と第2の補間工程とを繰り返すことを特徴とする、請求項1又は2に記載された補間処理方法。

【請求項4】
 
前記しきい値と比較する距離は、各初期制御点における垂線の足と制御点に対応する初期制御ポリゴンである補間点との間の距離の平均自乗距離、又は最大自乗距離であることを特徴とする、請求項3に記載の補間処理方法。

【請求項5】
 
第1回目に行う第1の補間工程及び第2の補間工程において、
前記点群を初期制御ポリゴンとし、当該初期制御ポリゴンを制御ポリゴンとし、前記幾何アルゴリズムの演算を行い、
第2回目以降に行う第1の補間工程及び第2の補間工程において、
補間工程で得た制御点を制御ポリゴンとし、前記幾何アルゴリズムの演算を行うことを特徴とする、請求項1から請求項4のいずれかに記載された補間処理方法。

【請求項6】
 
前記曲面は、B-Spline曲面、三角形メッシュによるLoop細分割、四角形メッシュによるCatmull-Clark細分割、Doo-Sabin細分割の何れかで定められる制御点により定義されることを特徴とする、請求項1から請求項5の何れかに記載された補間処理方法。

【請求項7】
 
前記曲線は、Chaikin細分割又はB-Spline曲線で定められる制御点により定義されることを特徴とする、請求項1から請求項5の何れかに記載された補間処理方法。

【請求項8】
 
制御点により定義される曲線又は曲面によって点群を補間する補間処理装置において、
曲線あるいは曲面上において、初期制御点の近傍にある点を近傍点として求める幾何アルゴリズムにより第1の補間工程を行う第1の幾何演算手段と、
曲線又は曲面を定義する制御点の位置から前記近傍点における法線方向又は前記近傍点から初期ポリゴンへ向かう方向に、前記近傍点と初期制御点との距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムにより第2の補間工程を行う第2の幾何演算手段とを備え、
前記第1の幾何演算手段は、幾何アルゴリズムの演算により曲線又は曲面上において初期制御点から最短距離にある点を近傍点として求め、
前記第1の幾何演算手段及び第2の幾何演算手段は、各幾何アルゴリズムをソフトウエアで実行するためのCPU及び記憶装置、又は各幾何アルゴリズムをハードウエアで実行するための回路を備えることを特徴とする、補間処理装置

【請求項9】
 
前記第1の幾何演算手段は、初期制御ポリゴンの各初期制御点から制御ポリゴンにより定義される曲線あるいは曲面上に垂線を下ろし、当該垂線の曲線あるいは曲面上の垂線の足の位置を近傍点とする幾何アルゴリズムの演算を行い、
前記第2の幾何演算手段は、前記垂線の方向を法線方向とし、前記垂線の足と初期制御点との間の距離を求め、現時点における曲線又は曲面を定義する制御点を曲線又は曲面から法線方向で前記距離だけ移動させ、移動後の位置を制御点の新たな位置として定める幾何アルゴリズムの演算を行うことを特徴とする請求項8に記載の補間処理装置。

【請求項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の何れかに記載されたプログラム媒体。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2007554883thum.jpg
State of application right Registered
(In Japanese)掲載特許について詳しくお知りになりたい方はHPの「お問い合わせ」ページにてお問い合わせください。


PAGE TOP

close
close
close
close
close
close
close