Top > Search of International Patents > APPROXIMATION PROCESSING METHOD AND APPROXIMATION PROCESSING DEVICE

APPROXIMATION PROCESSING METHOD AND APPROXIMATION PROCESSING DEVICE

Foreign code F110002379
File No. YNU07088B
Posted date Jan 17, 2011
Country WIPO
International application number 2009JP053252
International publication number WO 2009/142037
Date of international filing Feb 24, 2009
Date of international publication Nov 26, 2009
Priority data
  • P2008-135643 (May 23, 2008) JP
Title APPROXIMATION PROCESSING METHOD AND APPROXIMATION PROCESSING DEVICE
Abstract An approximation processing method for approximating a point group by a curved line or curved surface defined by a control point is equipped with a process of forming an approximated curved line (or approximated curved surface) using the control point for reserving the characteristics of a shape, a first calculation process for calculating points closest to data points on the approximated curved line (or approximate curved surface), a second calculation process of calculating error vectors connecting the data points, from the points closest to the data points which have been obtained in the first calculation process, and a third calculation process of moving the control point based on the error vectors obtained in the second calculation process and calculating the modified control point. By repeating the process of forming an approximated curved line (or approximated curved surface) and the first to third calculation processes, the approximated curved line (or approximated curved surface) is approximated to a curved line (or curved surface) consisting of the data points. By calculating the control point using a simple geometrical algorithm in the modification of the control point, the number of times of calculations for making the control point converge is reduced and thereby a curved line or curved surface which approximates the data points, which are a point group, can be generated in a short time without solving a linear system.
Scope of claims (In Japanese)
【請求項1】 制御点により定義される曲線又は曲面によって点群のデータ点を近似する近似処理方法において、
 形状の特徴を保存する制御点を用いて近似曲線又は近似曲面を形成する工程と、
 前記近似曲線又は近似曲面上において、前記データ点に最も近い最近点を算出する第1の算出工程と、
 前記第1の算出工程で求めた最近点から前記データ点を結ぶ誤差ベクトルを算出する第2の算出工程と、
 前記第2の算出工程で求めた誤差ベクトルに基づいて前記制御点を移動し修正後の制御点を算出する第3の算出工程とを備え、
 前記近似曲線又は近似曲面を形成する工程および各算出工程は、幾何アルゴリズムを組み込んだ演算手段により行い、
 前記近似曲線又は近似曲面の形成工程と前記第1~第3の算出工程を繰り返すことによって、前記近似曲線又は近似曲面をそれぞれ対象とするデータ点が構成する曲線又は曲面に近似させることを特徴とする近似処理方法。

【請求項2】 前記第1の算出工程は、ニュートン法によって近似曲線又は近似曲面上において前記データ点に最も近い最近点を算出することを特徴とする請求項1に記載の近似処理方法。

【請求項3】 前記第3の算出工程は、前記第2の算出工程で算出した複数の誤差ベクトルの内、修正を行う制御点の周囲にある最近点について算出した誤差ベクトルに重み付け処理を行い、当該重み付けした誤差ベクトルをベクトル加算し、当該ベクトル加算された加算ベクトルを移動ベクトルとして前記制御点を移動し、移動後の制御点を修正後制御点として算出することを特徴とする請求項1又は2に記載の近似処理方法。

【請求項4】 前記第3の算出工程における重み付け処理は、前記制御点の周囲の最近点について求めた誤差ベクトルに係数を乗じる演算処理であり、
 前記係数は制御点と最近点との距離に応じて、制御点に近い程ほど大きな値を設定することを特徴とする請求項3に記載の近似処理方法。

【請求項5】 前記係数は、重心座標系(barycentric coordinate)に従って定めることを特徴とする請求項4に記載の近似処理方法。

【請求項6】 前記データ点と当該データ点に対応する近似曲線又は近似曲面上の最近点との距離に基づいて、近似曲線又は近似曲面の近似誤差を算出し、
 前記近似誤差が所定値未満となるまで前記第1~第3の算出工程を繰り返すことを特徴とする請求項1から5の何れか一つに記載の近似処理方法。

【請求項7】 前記制御点の算出処理の繰り返し回数が所定回数を超えた場合には、面分割による制御点の個数を増加させ、
 前記近似誤差が所定値未満となるまで前記制御点の算出工程と前記面分割による制御点の増加を繰り返すことを特徴とする請求項6に記載の近似処理方法。

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

【請求項9】 点群のデータ点を結んで折れ線又はメッシュを形成する工程と、
 当該折れ線又はメッシュの特徴をとらえた頂点を求め、当該頂点を初期制御点とする工程とを備え、
 前記近似曲線又は近似曲面を形成する工程は、前記初期制御点を用いて第1回目の近似曲線又は近似曲面の形成を行うことを特徴とする請求項1から請求項8の何れか一つに記載の近似処理方法。

【請求項10】 制御点により定義される曲線又は曲面によって点群を近似する近似処理装置において、
 形状の特徴点を保存する制御点を用いて近似曲線又は近似曲面を形成する工程と、
 前記近似曲線又は近似曲面上において、前記データ点に最も近い最近点を算出する第1の算出工程と、
 前記第1の算出工程で求めた最近点から前記データ点を結ぶ誤差ベクトルを算出する第2の算出工程と、
 前記第2の算出工程で求めた誤差ベクトルに基づいて前記制御点を移動し修正後の制御点を算出する第3の算出工程の各工程を行う演算手段を備え、
 前記演算手段は、前記近似曲線又は近似曲面を形成する工程、および前記各算出工程を行う幾何アルゴリズムをソフトウエアで実行するためのCPU及び記憶装置、又は各幾何アルゴリズムをハードウエアで実行するための回路を備え、前記近似曲線又は近似曲面の形成工程と前記第1~第3の算出工程を繰り返すことによって、前記近似曲線又は近似曲面をそれぞれ対象とする曲線又は曲面に近似させることを特徴とする近似処理装置。
  • Applicant
  • ※All designated countries except for US in the data before July 2012
  • NATIONAL UNIVERSITY CORPORATION YOKOHAMA NATIONAL UNIVERSITY
  • Inventor
  • MAEKAWA, Takashi
  • NISHIYAMA, Yuu
  • MORIOKA, Masayuki
IPC(International Patent Classification)
Specified countries AE(UTILITY MODEL),AG,AL(UTILITY MODEL),AM(PROVISIONAL PATENT)(UTILITY MODEL),AO(UTILITY MODEL),AT(UTILITY MODEL),AU,AZ(UTILITY MODEL),BA,BB,BG(UTILITY MODEL),BH(UTILITY MODEL),BR(UTILITY MODEL),BW(UTILITY MODEL),BY(UTILITY MODEL),BZ(UTILITY MODEL),CA,CH,CN(UTILITY MODEL),CO(UTILITY MODEL),CR(UTILITY MODEL),CU(INVENTOR'S CERTIFICATE),CZ(UTILITY MODEL),DE(UTILITY MODEL),DK(UTILITY MODEL),DM(UTILITY MODEL),DO(UTILITY MODEL),DZ,EC(UTILITY MODEL),EE(UTILITY MODEL),EG(UTILITY MODEL),ES(UTILITY MODEL),FI(UTILITY MODEL),GB,GD,GE(UTILITY MODEL),GH(UTILITY CERTIFICATE),GM,GT(UTILITY MODEL),HN,HR(CONSENSUAL PATENT),HU(UTILITY MODEL),ID,IL,IN,IS,JP(UTILITY MODEL),KE(UTILITY MODEL),KG(UTILITY MODEL),KM,KN,KP(INVENTOR'S CERTIFICATE)(UTILITY MODEL),KR(UTILITY MODEL),KZ(PROVISIONAL PATENT)(UTILITY MODEL),LA,LC,LK,LR,LS(UTILITY MODEL),LT,LU,LY,MA,MD(UTILITY MODEL),ME,MG,MK,MN,MW,MX(UTILITY MODEL),MY(UTILITY-INNOVATION),MZ(UTILITY MODEL),NA,NG,NI(UTILITY MODEL),NO,NZ,OM(UTILITY MODEL),PG,PH(UTILITY MODEL),PL(UTILITY MODEL),PT(UTILITY MODEL),RO,RS(PETTY PATENT),RU(UTILITY MODEL),SC,SD,SE,SG,SK(UTILITY MODEL),SL(UTILITY MODEL),SM,ST,SV(UTILITY MODEL),SY,TJ(UTILITY MODEL),TM(PROVISIONAL PATENT),TN,TR(UTILITY MODEL),TT(UTILITY CERTIFICATE),TZ,UA(UTILITY MODEL),UG(UTILITY CERTIFICATE),US,UZ(UTILITY MODEL),VC(UTILITY CERTIFICATE),VN(PATENT FOR UTILITY SOLUTION),ZA,ZM,ZW,EP(AT,BE,BG,CH,CY,CZ,DE,DK,EE,ES,FI,FR,GB,GR,HR,HU,IE,IS,IT,LT,LU,LV,MC,MK,MT,NL,NO,PL,PT,RO,SE,SI,SK,TR),OA(BF(UTILITY MODEL),BJ(UTILITY MODEL),CF(UTILITY MODEL),CG(UTILITY MODEL),CI(UTILITY MODEL),CM(UTILITY MODEL),GA(UTILITY MODEL),GN(UTILITY MODEL),GQ(UTILITY MODEL),GW(UTILITY MODEL),ML(UTILITY MODEL),MR(UTILITY MODEL),NE(UTILITY MODEL),SN(UTILITY MODEL),TD(UTILITY MODEL),TG(UTILITY MODEL)),AP(BW(UTILITY MODEL),GH(UTILITY MODEL),GM(UTILITY MODEL),KE(UTILITY MODEL),LS(UTILITY MODEL),MW(UTILITY MODEL),MZ(UTILITY MODEL),NA(UTILITY MODEL),SD(UTILITY MODEL),SL(UTILITY MODEL),SZ(UTILITY MODEL),TZ(UTILITY MODEL),UG(UTILITY MODEL),ZM(UTILITY MODEL),ZW(UTILITY MODEL)),EA(AM,AZ,BY,KG,KZ,MD,RU,TJ,TM)
(In Japanese)掲載特許について詳しくお知りになりたい方はHPの「お問い合わせ」ページにてお問い合わせください。

PAGE TOP

close
close
close
close
close
close