(57)【要約】【課題】  ３次元モデルのスキャニングから得た特徴稜線部を含む複雑な形状の高密度測定点群に対して、高精度かつ頑健、高速に適切なLoop細分割曲面の初期制御メッシュ（ICM）を生成する。【解決手段】  本発明は、３次元物理モデルのスキャニングデータを入力し、高密度測定点群を生成し、この高密度測定点群に対してMarching cubes法を適用してボリュームベース・メッシュを生成し、さらにこれにShrink-wrapping法を適用して高密度メッシュの生成し、この高密度メッシュに対して特徴境界の抽出処理を行い、続いてこの特徴境界を用いて、高密度メッシュの簡略化による特徴境界を保存した初期制御メッシュシードを生成し、Quasi-interpolationによりこの初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成する技術である。【選択図】      図２
2006277712.tif 000002
【特許請求の範囲】
【請求項１】
３次元物理モデルのスキャニングデータを入力し、高密度測定点群を生成する高密度測定部と、
前記高密度測定部の生成した高密度測定点群に対して高密度メッシュを生成する高密度メッシュ構築部と、
前記高密度メッシュ構築部の生成した高密度メッシュに対して特徴境界の抽出処理を行う特徴境界抽出部と、
前記特徴境界抽出部の抽出した特徴境界を用いて、前記高密度メッシュの簡略化による特徴境界を保存した初期制御メッシュシードを生成する初期制御メッシュシード生成部と、
前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成して出力する初期制御メッシュ幾何改良部とを備えた３次元モデルのフィッティング装置。
【請求項２】
前記高密度メッシュ構築部は、前記高密度測定部の生成した高密度測定点群に対してＭａｒｃｈｉｎｇ  ｃｕｂｅｓ法を適用してボリュームベース・メッシュを生成し、さらにこれにＳｈｒｉｎｋ−ｗｒａｐｐｉｎｇ法を適用して高密度メッシュを生成し、
前記初期制御メッシュ幾何改良部は、Ｑｕａｓｉ−ｉｎｔｅｒｐｏｌａｔｉｏｎにより前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成することを特徴とする請求項１に記載の３次元モデルのフィッティング装置。
【請求項３】
３次元物理モデルのスキャニングデータを入力し、高密度測定点群を生成する高密度測定ステップと、
前記高密度測定点群に対して高密度メッシュを生成する高密度メッシュ生成ステップと、
前記高密度メッシュに対して特徴境界の抽出処理を行う特徴境界抽出ステップと、
前記特徴境界を用いて、前記高密度メッシュの簡略化による特徴境界を保存した初期制御メッシュシードを生成する初期制御メッシュシード生成ステップと、
前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成する初期制御メッシュ幾何改良ステップとを有する３次元モデルのフィッティング方法。
【請求項４】
前記高密度メッシュ生成ステップでは、前記高密度測定点群に対してＭａｒｃｈｉｎｇ  ｃｕｂｅｓ法を適用してボリュームベース・メッシュを生成し、さらにこれにＳｈｒｉｎｋ−ｗｒａｐｐｉｎｇ法を適用して高密度メッシュを生成し、
前記初期制御メッシュ幾何改良ステップでは、Ｑｕａｓｉ−ｉｎｔｅｒｐｏｌａｔｉｏｎにより前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成することを特徴とする請求項３に記載の３次元モデルのフィッティング方法。
【請求項５】
３次元物理モデルのスキャニングデータを入力し、高密度測定点群を生成する高密度測定処理と、
前記高密度測定点群に対して高密度メッシュを生成する高密度メッシュ生成処理と、
前記高密度メッシュに対して特徴境界の抽出処理を行う特徴境界抽出処理と、
前記特徴境界を用いて、前記高密度メッシュの簡略化による特徴境界を保存した初期制御メッシュシードを生成する初期制御メッシュシード生成処理と、
前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成する初期制御メッシュ幾何改良処理とをコンピュータに実行させる３次元モデルのフィッティングプログラム。
【請求項６】
前記高密度メッシュ生成処理では、前記高密度測定点群に対してＭａｒｃｈｉｎｇ  ｃｕｂｅｓ法を適用してボリュームベース・メッシュを生成し、さらにこれにＳｈｒｉｎｋ−ｗｒａｐｐｉｎｇ法を適用して高密度メッシュを生成し、
前記初期制御メッシュ幾何改良処理では、Ｑｕａｓｉ−ｉｎｔｅｒｐｏｌａｔｉｏｎにより前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成することを特徴とする請求項５に記載の３次元モデルのフィッティングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元モデルのフィッティング装置、方法及びプログラムに関する。
【背景技術】
【０００２】
リバースエンジニアリング（ＲＥ）とは、３次元スキャンあるいはＸ線ＣＴスキャンなどによって３次元物理モデルなどを測定し、得られた測定点群にフィットする曲面モデルを生成する手法であり、スタイルデザインにおいてＣＡＤシステムにより直接設計することが困難であるような曲面モデルの生成や、内部構造をもつ解析用モデルの生成に適している。
【０００３】
従来、ＲＥにおけるフィッティング曲面モデルとして、ポリゴン曲面近似モデルや４辺形パラメトリック曲面が主として用いられてきた。しかしながら、前者は面分数が莫大となるため幾何演算に時間がかかり、しかも滑らかな曲面を表現することができない問題点があった。後者は単一の４辺形曲面パッチのみによる、点群にフィットする滑らかな曲面の生成が困難で、また複数パッチ間を滑らかに接続するための処理が複雑となる問題点があった。
【０００４】
このような問題点の解決手法として、文献「Schroder, P.: "Subdivision for modeling and animation." Course notes of SIGGRAPH 98. 1998」（非特許文献１）では、細分割曲面を測定点群に対するフィッティング曲面モデルとして利用する技術が提案されている。細分割曲面は、任意の接続性をもつメッシュ上に単一の滑らかな曲面を生成できるなど、ＲＥのフィッティング曲面モデルとしての魅力的な特徴が多くある。また近年では、細分割曲面のモデリング機能を有する商用３Ｄモデリングソフトウェアも数多く存在し、さらに機械系ＣＡＤシステムにおいても細分割曲面を用いた意匠設計機能をもつものも現れている。
【０００５】
細分割曲面のＲＥ問題とは、細分割極限曲面が測定点群にフィットするような初期制御メッシュを導出する問題と定義できる。非接触測定器の発達により、近年では、多様なソースから得られた大規模かつ複雑な測定データに対する高性能なフィッティング能力を有することが細分割曲面のＲＥ問題にも要求されている。これらの機能要求は、以下の４つである。
【０００６】
第１の機能要求は、複雑な幾何構造をもつ物体に対する頑健なフィッティングである。スタイルデザインで作られるデザインモックアップは、ボタン穴や放熱穴といった任意のしかも複雑な幾何形状を含むものが多い。また、Ｘ線ＣＴスキャンで測定された物体は、多重シェルや冷却管路のような複雑な内部構造をもつことがある。このような場合にも対応する複雑な初期制御メッシュを導出しなければならない。
【０００７】
第２の機能要求は、フィッティング誤差の管理である。フィッティング誤差は、生成される細分割曲面の品質を保つために、直接的または間接的に制御されなければならない。
【０００８】
第３の機能要求は、莫大な測定点群に対する高速なフィッティングである。フィッティング処理は、数百万点程度の莫大な測定点群に対してもできるだけ短時間で完了することが望ましい。
【０００９】
第４の機能要求は、特徴稜線部に対する高精度なフィッティングである。デザインモックアップや工業製品の３次元物理モデルには、「特徴稜線」と呼ばれる、表面の曲率が急激に変化する領域が数多く存在する。これらの領域は、完全にシャープな稜線としてではなく、実際には微小半径のフィレットとして存在している。それゆえ、これらの微小半径のフィレットを認識し、適切な位相と幾何形状をもつ初期制御メッシュを導出して、このようなフィレットとして存在する特徴稜線部をその細分割曲面の極限曲面において再現する必要がある。
【００１０】
文献「Hoppe, H. et al.: "Surface reconstruction from unorganized points." SIGGRAPH 92 Conference Proceedings, (1992) 71-78.」（非特許文献２）、文献「Hoppe, H. et al.: "Piecewise smooth surface reconstruction." SIGGRAPH 94 Conference Proceedings, (1994) 295-302.」（非特許文献３）には、測定点群から細分割曲面を生成するＲＥの代表的な手法が記載されている。この手法では、エネルギー最小化を用いて、稜線がタグづけされたＬｏｏｐ細分割曲面を点群から生成し、タグづけされた稜線方向には異なる細分割ルールを適用することで、完全にシャープな特徴稜線を表現できる。また、文献『竹内真悟、鈴木宏正ほか:「点群および多面体データに基づく細分割曲面の生成手法」、日本機械学会論文誌Ｃ編、 67, 653 (2001) 284-289』（非特許文献４）では、単純な幾何形状で少ない面分数の初期制御メッシュをもとにフィッティングしていき、初期制御メッシュは、誤差エネルギー関数の最小化および制御頂点の挿入を繰り返すことでその幾何・位相構造を改良し、その細分割極限点を測定点群にフィットするように調節する手法が提案されている。しかし、この手法は高速であるが、正確なフィッティングのためには、マニュアルで初期制御メッシュを定義しなければならない問題点があった。
【００１１】
文献「Joeng, W. et al.: "Direct reconstruction of displaced subdivision surface from unorganized points." Pacific Graphics 01 Conference Proceedings, (2001) 160-168.」（非特許文献５）では、測定点群からのＤｉｓｐｌａｃｅｄ  ｓｕｂｄｉｖｉｓｉｏｎ  ｓｕｒｆａｃｅ（ＤＳＳ）の生成を提案している。ＤＳＳは滑らかな細分割曲面にスカラー・ディスプレイスメント・マップを重ね合わせることで、モデルの詳細を表現する手法である。この手法では、文献「Kobbelt, L. P. et al.: "A shrink wrapping approach to remeshing Polygonal Surfaces." EUROGRAPHICS 99 Proceedings, (1999) 119-130.」（非特許文献６）で提案されているＳｈｒｉｎｋ−ｗｒａｐｐｉｎｇ技法、及び、文献「Garland, M. et al.: "Surface simplification using quadric error metrics." SIGGRAPH 92 Conference Proceedings, (1992) 209-216.」（非特許文献７）で提案されているＱｕａｄｒｉｃ  ｅｒｒｏｒ  ｍｅｔｒｉｃｓ（ＱＥＭ）技法に基づく簡略化を用いて測定点群から初期制御メッシュを直接生成することが可能であるが、任意の種数をもつ物体の測定点群に細分割曲面をフィットできない。文献「Razdan, A. et al.: "Reverse Engineering Using a Subdivision Surface Scheme." 3D Modelling 03 Proceedings (2003)」（非特許文献８）にもＤＳＳに対するフィッティングが提案されているが、このアルゴリズムは高密度メッシュを入力として用いており、測定点群には対応していない。文献「Kanai, T: MeshToSS: "Converting Subdivision Surfaces from Dense Meshes." 6th International Fall Workshop on Vision, Modeling and Visualization 01 proceedings, (2001) 325-332.」（非特許文献９）では、初期制御メッシュは、細分割極限点に対するＱＥＭに基づいた高密度メッシュの簡略化によって生成する手法が提案されている。しかし、この手法は、安定して高密度メッシュから初期制御メッシュを生成することができるが、測定点群からのフィッティングについては議論されておらず、また微小なフィレット領域を認識した正確なフィッティング能力に限界がある問題点があった。
【００１２】
以上のような既存技術は、コンピュータ・グラフィックスへの応用を目的とした点群からの細分割曲面の生成手法としては優れた方法であるといえ、上記の４つの機能要求を同時にすべて満足し得るものはなかった。
【非特許文献１】Schroder, P.: "Subdivision for modeling and animation." Course notes of SIGGRAPH 98 (1998).
【非特許文献２】Hoppe, H. et al.: "Surface reconstruction from unorganized points." SIGGRAPH 92 Conference Proceedings, (1992) 71-78.
【非特許文献３】Hoppe, H. et al.: "Piecewise smooth surface reconstruction." SIGGRAPH 94 Conference Proceedings, (1994) 295-302.
【非特許文献４】竹内真悟、鈴木宏正ほか、「点群および多面体データに基づく細分割曲面の生成手法」、日本機械学会論文誌Ｃ編、６７、６５３、２００１、２８４−２８９。
【非特許文献５】Joeng, W. et al.: "Direct reconstruction of displaced subdivision surface from unorganized points." Pacific Graphics 01 Conference Proceedings, (2001) 160-168.
【非特許文献６】Kobbelt, L. P. et al.: "A shrink wrapping approach to remeshing Polygonal Surfaces." EUROGRAPHICS 99 Proceedings, (1999) 119-130.
【非特許文献７】Garland, M. et al.: "Surface simplification using quadric error metrics." SIGGRAPH 92 Conference Proceedings, (1992) 209-216.
【非特許文献８】Razdan, A. et al.: "Reverse Engineering Using a Subdivision Surface Scheme." 3D Modelling 03 Proceedings (2003).
【非特許文献９】Kanai, T: MeshToSS: "Converting Subdivision Surfaces from Dense Meshes." 6th International Fall Workshop on Vision, Modeling and Visualization 01 proceedings, (2001) 325-332.
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明は、上述のような従来技術の問題点に鑑みてなされたものであり、３次元モデルのスキャニングから得た特徴稜線部を含む複雑な形状の高密度測定点群に対しても、高精度かつ頑健、高速に適切なＬｏｏｐ細分割曲面の初期制御メッシュ（ＩＣＭ）を生成でき、また、上述の４つの機能要求をすべて満たし、複雑かつ高密度な測定点群に対して頑健かつ高精度、高速にＬｏｏｐ細分割曲面をフィットさせることができる３次元モデルのフィッティング技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
請求項１の発明の３次元モデルのフィッティング装置は、３次元物理モデルのスキャニングデータを入力し、高密度測定点群を生成する高密度測定部と、前記高密度測定部の生成した高密度測定点群に対して高密度メッシュを生成する高密度メッシュ構築部と、前記高密度メッシュ構築部の生成した高密度メッシュに対して特徴境界の抽出処理を行う特徴境界抽出部と、前記特徴境界抽出部の抽出した特徴境界を用いて、前記高密度メッシュの簡略化による特徴境界を保存した初期制御メッシュシードを生成する初期制御メッシュシード生成部と、前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成して出力する初期制御メッシュ幾何改良部とを備えたものである。
【００１５】
請求項２の発明は、請求項１の３次元モデルのフィッティング装置において、前記高密度メッシュ構築部は、前記高密度測定部の生成した高密度測定点群に対してＭａｒｃｈｉｎｇ  ｃｕｂｅｓ法を適用してボリュームベース・メッシュを生成し、さらにこれにＳｈｒｉｎｋ−ｗｒａｐｐｉｎｇ法を適用して高密度メッシュを生成し、前記初期制御メッシュ幾何改良部は、Ｑｕａｓｉ−ｉｎｔｅｒｐｏｌａｔｉｏｎにより前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成することを特徴とするものである。
【００１６】
請求項３の発明の３次元モデルのフィッティング方法は、３次元物理モデルのスキャニングデータを入力し、高密度測定点群を生成する高密度測定ステップと、前記高密度測定点群に対して高密度メッシュを生成する高密度メッシュ生成ステップと、前記高密度メッシュに対して特徴境界の抽出処理を行う特徴境界抽出ステップと、前記特徴境界を用いて、前記高密度メッシュの簡略化による特徴境界を保存した初期制御メッシュシードを生成する初期制御メッシュシード生成ステップと、前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成する初期制御メッシュ幾何改良ステップとを有するものである。
【００１７】
請求項４の発明は、請求項３の３次元モデルのフィッティング方法において、前記高密度メッシュ生成ステップでは、前記高密度測定点群に対してＭａｒｃｈｉｎｇ  ｃｕｂｅｓ法を適用してボリュームベース・メッシュを生成し、さらにこれにＳｈｒｉｎｋ−ｗｒａｐｐｉｎｇ法を適用して高密度メッシュを生成し、前記初期制御メッシュ幾何改良ステップでは、Ｑｕａｓｉ−ｉｎｔｅｒｐｏｌａｔｉｏｎにより前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成することを特徴とするものである。
【００１８】
請求項５の発明の３次元モデルのフィッティングプログラムは、３次元物理モデルのスキャニングデータを入力し、高密度測定点群を生成する高密度測定処理と、前記高密度測定点群に対して高密度メッシュを生成する高密度メッシュ生成処理と、前記高密度メッシュに対して特徴境界の抽出処理を行う特徴境界抽出処理と、前記特徴境界を用いて、前記高密度メッシュの簡略化による特徴境界を保存した初期制御メッシュシードを生成する初期制御メッシュシード生成処理と、前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成する初期制御メッシュ幾何改良処理とをコンピュータに実行させるものである。
【００１９】
請求項６の発明は、請求項５の３次元モデルのフィッティングプログラムにおいて、前記高密度メッシュ生成処理では、前記高密度測定点群に対してＭａｒｃｈｉｎｇ  ｃｕｂｅｓ法を適用してボリュームベース・メッシュを生成し、さらにこれにＳｈｒｉｎｋ−ｗｒａｐｐｉｎｇ法を適用して高密度メッシュを生成し、前記初期制御メッシュ幾何改良処理では、Ｑｕａｓｉ−ｉｎｔｅｒｐｏｌａｔｉｏｎにより前記初期制御メッシュシードの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュを生成することを特徴とするものである。
【発明の効果】
【００２０】
本発明によれば、極限曲面は任意位相で単一の滑らかな曲面を表現でき、細分割計算は内分点生成と頂点位置更新するだけであるので単純であってコンピュータの負荷を軽くでき、かつ詳細度（ＬＯＤ）制御が容易である利点がある。
【００２１】
また、本発明によれば、穴や特徴稜線を含む複雑形状の高密度測定点群に対し、メッシュ上の曲率評価に基づいて、微小フィレットとなる特徴稜線部に対しても適切な位相構造をもつ初期制御メッシュを推定し、高精度かつ高速なＬｏｏｐ細分割曲面へのフィッティングが可能な技術を提供できる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施の形態を図に基づいて詳説する。図１は本発明の１つの実施の形態の３次元モデルのフィッティング装置のブロック図であり、図２は、この３次元モデルのフィッティング装置が実行するフィッティング処理のシーケンス図である。
【００２３】
本実施の形態の３次元モデルのフィッティング装置は、３次元物理モデルをスキャンニングする３Ｄスキャナあるいは３ＤＣＴスキャナのような装置の３次元モデル測定部１０１、この３次元モデル測定部１０１から測定データを入力し、高密度測定点群Ｕを生成する高密度測定部１０２、この高密度測定部１０２からの高密度測定点群Ｕに対して３次元ボクセルモデルを用いた高密度メッシュの構築処理を実行する高密度メッシュ構築部１０３、この高密度メッシュ構築部１０３の生成する高密度メッシュＭ１に対して特徴境界の抽出処理を行う特徴境界抽出部１０４、高密度メッシュの簡略化による特徴境界を保存した初期制御メッシュシードを生成する初期制御メッシュシード生成部１０５、Ｑｕａｓｉ−ｉｎｔｅｒｐｏｌａｔｉｏｎによる初期制御メッシュの幾何改良を実行してＬｏｏｐ細分割曲面初期制御メッシュＭ３を出力する初期制御メッシュ幾何改良部１０６、そして各部で算出した諸データを保存し、また各部からの読出しにより該当データを出力する記憶装置１１０を備えている。
【００２４】
本実施の形態の３次元モデルのフィッティング装置による３次元モデルのフィッティング方法は次の通りである。なお、本装置はコンピュータシステムに下記の演算処理を実行する３次元モデルのフィッティングプログラムをインストールすることによって当該方法を実施するものであるが、ここでは演算処理ごとに分けて説明する。
【００２５】
本実施の形態の３次元モデルのフィッティング方法は、ボクセルモデルを用いた高密度メッシュの構築（ステップＳＱ０１）、特徴境界の抽出（ステップＳＱ０２）、高密度メッシュの簡略化による特徴境界を保存した初期制御メッシュシードの生成（ステップＳＱ０３）、Ｑｕａｓｉ−ｉｎｔｅｒｐｏｌａｔｉｏｎによる初期制御メッシュの幾何改良（ステップＳＱ０４）の４つのステップから構成される。
【００２６】
ステップＳＱ０１は高密度メッシュの生成ステップである。３次元スキャナ１０１でスキャニングされ、高密度測定部１０２でこのスキャニングデータから生成された複雑形状の高密度測定点群に対し、高精度に細分割曲面をフィットさせるには、点群が表す形状の位相構造、幾何特徴を良く反映し、かつ少ない頂点数の初期制御メッシュシード（初期制御メッシュ推定形状）を安定に生成することが必要である。本実施の形態では、このシード生成の前処理として、高密度メッシュ構築部１０３が以下の処理手順によって、高密度メッシュを生成する。
【００２７】
図３はＭａｒｃｈｉｎｇ  Ｃｕｂｅｓの概要の説明図である。Ｍａｒｃｈｉｎｇ  Ｃｕｂｅｓによる概略メッシュ生成は、図３（ａ）に示すように高密度測定部１０２からの入力となる高密度測定点群Ｕを、間隔のボクセル空間内に配置し、各ボクセルのＵに対する内外判定を行う。ボクセル格子点を中心とする辺長ｗの立方体空間に測定点が含まれる場合には、図３（ｂ）に示すように格子点属性値に１を、それ以外の格子点には格子点属性値に０を割り当てる。その後さらに格子点をｘ，ｙ，ｚ方向に走査して、図３（ｃ）に示すように属性値１の格子点群で囲まれた空間内にある格子点の属性値を１に変える。各ボクセルの格子点属性値パターンに基づき、文献「Lorensen, W. E. et al.: "Marching cubes: A high resolution 3D surface construction algorithm." Computer Graphics, 21, 4 (1987) 163-169.」に開示されているＭａｒｃｈｉｎｇ  ｃｕｂｅｓ法を適用することで、図３（ｄ）に示すように点群の形状を正しくとらえたボリュームベース・メッシュＭ０を生成する。図４は、このボリュームベース・メッシュの生成時に用いる格子点属性値に基づく面生成基本パターンテーブルを示している。
【００２８】
次に、非特許文献６に開示されているＳｈｒｉｎｋ  ｗｒａｐｐｉｎｇ法を用いてボリューム・メッシュＭ０から高密度メッシュＭ１を生成する。図５は、このＳｈｒｉｎｋ  ｗｒａｐｐｉｎｇ法の概要を示すシーケンス図、図６はその原理を示している。以下の４つのステップにより、高密度メッシュＭ１の各頂点が測定点群Ｕ内のある１点と同位置になり、高密度メッシュＭ１を測定点群Ｕに正確にフィットする。
【００２９】
ステップＳＱ１１では、ボリューム・メッシュＭ０の各頂点ｖにおける頂点位置νを数１式によって緩和する。
【数１】
2006277712.tif 000003
【００３０】
ここで、ｎｂｈｄ（ｖ）は各頂点ｖの１近傍頂点集合、ｄｊはｖｊの１近傍稜線長の平均、α∈［０，１］はリラクゼーション係数で、本実施の形態ではα＝０．５としている。
【００３１】
ステップＳＱ１２では、各頂点ｖを測定点群Ｕにフィッティングする。ボリューム・メッシュＭ０における各頂点ｖの平均法線ｎｖ方向の直線に最も近い点ｕｎｅａｒ∈Ｕの位置に各頂点ｖの頂点位置を修正する。
【００３２】
ステップＳＱ１３では、ボリューム・メッシュＭ０の測定点群Ｕに対する誤差判定を行う。本実施の形態では、ボリューム・メッシュＭ０の測定点群Ｕに対する誤差を、測定点群Ｕ内の各点と、その点に最も近いボリューム・メッシュＭ０上の面との距離として定義する。図７に示すように、平均誤差がメッシュ生成トレランスτｍより小さければ、ボリューム・メッシュＭ０を高密度メッシュＭ１として出力する。そうでなければ、ステップＳＱ１４を実行する。このステップＳＱ１４では、ボリューム・メッシュＭ０を１回Ｌｏｏｐ細分割し、ステップＳＱ１２〜ＳＱ１３を繰り返す。図８（ａ）はボリュームベース・メッシュの画像を示し、同図（ｂ）はＳｈｒｉｎｋ  Ｗｒａｐｐｉｎｇ法により生成した高密度メッシュの画像を示している。
【００３３】
次に、特徴境界抽出部１０４が実行する図２のシーケンスにおけるステップＳＱ０２について説明する。デザインモックアップや工業製品のような３次元物理モデルの表面には、多数の特徴稜線が存在し、これらの稜線は、実際には微小半径のフィレット領域として実現されている。そこで、このような領域（特徴領域）の測定点群に対しても細分割曲面が適切にフィットできるように、その初期制御メッシュの位相構造や幾何形状を適切に導出する。図９、図１０は、その特徴境界稜線抽出処理の説明図である。図９（ａ）に示すように高密度メッシュＭ１は、これを初期制御メッシュとして用いるには面分数が多すぎるので、簡略化によって面分数を減らさなければならない。図９（ｂ）に示すように簡略化処理が進むと、特徴領域Ａ０上の小さな三角形面分数は減少し、１箇所の特徴領域Ａ０は１本の特徴稜線Ａ１に縮退してしまう。しかしながら、このような簡略化を用いて生成された初期制御メッシュから得られる細分割極限曲面Ａ２は、特徴稜線Ａ１の周辺で過度に平滑化されるため、図９（ｃ）に示すようにこれらの周辺部での点群に対する極限曲面のフィッティング精度が落ちる。この問題を解決するため、本実施の形態では、図１０（ａ）に示す同じ高密度メッシュＭ１から、図１０（ｂ）に示すように簡略化の結果において特徴領域Ａ０の両端に１本ずつ特徴境界稜線Ｂ１が残るようにする必要がある。このように特徴境界稜線Ｂ１の対を保存することによって、図１０（ｃ）に示すように特徴領域Ａ０の周辺でのフィッティング精度が向上する。
【００３４】
本実施の形態では、まず高密度メッシュＭ１上の特徴境界を、高密度メッシュＭ１の頂点における曲率を評価することで抽出し、この曲率に基づいた稜線コラプス操作によって、特徴境界Ｂ１を保存したまま高密度メッシュＭ１を簡略化する。このメッシュ簡略化によって、適切な特徴境界Ｂ１をもつ初期制御メッシュシードＭ２を得ることができる。
【００３５】
高密度メッシュＭ１の特徴領域Ａ０では、主曲率の絶対値の最大が高密度メッシュＭ１のその他の領域のそれより大きい。このため、高密度メッシュＭ１の各頂点の曲率を評価することにより高密度メッシュＭ１の特徴領域Ａ０を抽出することができる。本実施の形態では、文献「Alliez, P. et al.: "Anisotropic polygonal remeshing." SIGGRAPH 03 Conference Proceedings, (2003) 485-493.」で提案されている手法によってこの曲率評価を行う。数３式の曲率テンソル
【数２】
2006277712.tif 000004
【００３６】
から、その固有値の絶対値の最大をＭ１の頂点ｖでの主曲率の評価値ｋ（ｖ）とする。
【数３】
2006277712.tif 000005
【００３７】
ここで、Ｂは頂点ｖを中心とした半径ｒの球内に含まれる面分の集合、｜Ｂ｜はＢに含まれる面分面積の総和、β（ｅ）は稜線ｅを共有する２面分の符号付き２面角、｜ｅ∩Ｂ｜はｅのＢに含まれる部分の稜線長、
【数４】
2006277712.tif 000006
【００３８】
はｅと同じ方向の単位列ベクトルである。主曲率評価値κ（ｖ）を用いて、以下のステップによって高密度メッシュＭ１上の特徴境界稜線Ｂ１を抽出する。
【００３９】
図１１は、頂点曲率評価による特徴境界線Ｂ１抽出処理の説明図である。図１１（ａ）に示すようにＭ１の各頂点ｖに対しκ（ｖ）を求め、図１１（ｂ）のようにユーザが定義した曲率評価トレランスτｃとκ（ｖ）を比較し、各頂点ｖに対し属性値φ（ｖ）を数５式で設定する。
【数５】
2006277712.tif 000007
【００４０】
次に、各頂点ｖの１近傍の頂点がすべて属性値１（またはすべて−１）である場合は、φ（ｖ）＝０に変更し、図１１（ｃ）に示すように両端頂点の属性値が共に１である稜線を特徴境界Ｂ１とする。
【００４１】
次に、本実施の形態の初期制御メッシュシード生成部１０５の実行する初期制御メッシュシード生成処理のステップＳＱ０３について説明する。得られた高密度メッシュＭ１は面分数が多いため、これを直接細分割曲面の初期制御メッシュとして用いることは有効でない。そこで、高密度メッシュＭ１を簡略化することで、点群の形状を近似し、かつ面分数の少ないメッシュ、初期制御メッシュシードＭ２を生成する。本実施の形態では、ＱＥＭを評価し、かつ特徴境界Ｂ１を保存する新しい稜線コラプスアルゴリズムを採用している。
【００４２】
Ｑｕａｄｒｉｃ  ｅｒｒｏｒ  ｍｅｔｒｉｃｓ（ＱＥＭ）に基づく稜線コラプス（ＥＣ）によるメッシュの簡略化は、文献「Garland, M. et al.: "Surface simplification using quadric error metrics." SIGGRAPH 92 Conference Proceedings, (1992) 209-216.
」に提案されており、現在広く用いられている。１回のＥＣにおいて、頂点ｉ，ｊを接続する稜線（ｉ，ｊ）は、以下のように、（ｉ，ｊ）に対する数６式のコスト
【数６】
2006277712.tif 000008
【００４３】
を計算することにより、頂点ｋに縮退させる。
【００４４】
各頂点ｉに対し数７式のＱｉで表されるｆｕｎｄａｍｅｎｔａｌ  ｑｕａｄｒｉｃ
【数７】
2006277712.tif 000009
【００４５】
の要素Ａｉ，Ｖｉ，Ｃｉを数８式で計算する。
【数８】
2006277712.tif 000010
【００４６】
ここで、ｐｉは頂点ｉの位置を表す列ベクトル、ｎｆは三角形面分ｆの単位法線列ベクトル、ｆ＊（ｉ）は頂点ｉに接続されている面分の集合を表す。
【００４７】
各稜線（ｉ，ｊ）に対し、稜線の縮退（ｉ，ｊ）→ｋにかかる数６式のコストＱｉｊ（ｋ）を数９式で計算する。
【数９】
2006277712.tif 000011
【００４８】
ここで、ｐｋは新しい頂点位置で、数１０式で表される。
【数１０】
2006277712.tif 000012
【００４９】
コストＱｉｊ（ｋ）が最も小さい稜線（ｉ，ｊ）を新しい頂点ｋに縮退させ、
【数１１】
2006277712.tif 000013
【００５０】
とする。そして、数９式〜数１１式を繰り返す。
【００５１】
上述したＱＥＭに基づくＥＣによる簡略化では、高密度メッシュＭ１上の特徴境界が保存される保証はない。そこで、本実施の形態では、これを保存するための新たなＥＣのアルゴリズムを採用している。
【００５２】
図１２に示すように、ＥＣ（ｉ，ｊ）→ｋにおける稜線の縮退コストと新しい頂点位置を以下のルールを用いて定める。
【００５３】
（ａ）図１２の（ａ）に示す稜線のように、稜線（ｉ，ｊ）の２頂点ｉ，ｊがともに特徴境界上になく、かつ稜線（ｉ，ｊ）自身も特徴境界でない場合、稜線の縮退コストＱｉｊ（ｋ）は数９式の値とし、新頂点位置は数１０式の値とする。
【００５４】
（ｂ）図１２の（ｂ）に示す稜線のように、稜線（ｉ，ｊ）が特徴境界である場合、稜線の縮退コストＱｉｊ（ｋ）は特徴境界との誤差も含んだ以下のコストに変える。
【数１２】
2006277712.tif 000014
【００５５】
ここで
【数１３】
2006277712.tif 000015
【００５６】
は特徴境界である稜線ｅの単位方向ベクトル、
【数１４】
2006277712.tif 000016
【００５７】
は頂点ｉに接続されている特徴境界である稜線の集合である。
【数１５】
2006277712.tif 000017
【００５８】
の代わりに
【数１６】
2006277712.tif 000018
【００５９】
を用いて、数９式からコストを計算し、また数１０式から新頂点位置を求める。
【００６０】
（ｃ）図１２の（ｃ）に示すような稜線、つまり稜線（ｉ，ｊ）が特徴境界ではなく、２頂点ｉ，ｊのうちどちらかが特徴境界上にある場合、数９式によって稜線（ｉ，ｊ）の縮退コストを計算し、新頂点位置はｉ，ｊのうち特徴境界上にある頂点の位置と一致させる。
【００６１】
（ｄ）図１２の（ｄ）に示すような稜線、つまり稜線（ｉ，ｊ）が特徴境界ではなく、２頂点ｉ，ｊがともに異なる特徴境界上にあるとき、この稜線は縮退させない。
【００６２】
このような新しいＥＣ操作を適用することによって、特徴境界を保存したまま面分数が減少した初期制御メッシュシードＭ２を生成する。
【００６３】
次に、初期制御メッシュ幾何改良部１０６による初期制御メッシュ幾何改良処理のステップＳＱ０４について説明する。図１３は、本実施の形態の初期制御メッシュの幾何改良処理の説明図である。上の処理で得た初期制御メッシュＭ２に対してＬｏｏｐ細分割を行うと、極限曲面は測定点群を通過しない。そこで、文献「Levin, A. et al.: "Polynomial generation and quasi-interpolation in stationary non-uniform subdivision." CAGD 03 proceedings, 20, 1 (2003) 41-60.」に記載されているＱｕａｓｉ−ｉｎｔｅｒｐｏｌａｔｉｏｎ（ＱＩ）を用いて細分割極限点が初期制御メッシュＭ２の頂点に一致するように初期制御メッシュＭ２の頂点位置を修正する。ＱＩは、初期制御メッシュ上の頂点及びその１近傍頂点群に対応する細分割極限点位置から、局所的な計算により高速に初期制御メッシュの頂点位置を逆算する。ＱＩを用いた初期制御メッシュＭ２の各頂点ｖの位置の修正は、数１７式によって定義される。
【数１７】
2006277712.tif 000019
【００６４】
ここで、ｋはｖの価数、γ＝−１／（２ｋ）である。
【００６５】
初期制御メッシュＭ２に対してＱＩを適用したものをＬｏｏｐ細分割曲面の初期制御メッシュＭ３とし、これを最終的な出力とする。
【００６６】
本実施の形態の実験結果を示す。図１４にＩＴ機器筐体のデザインモックアップから得られた測定点群Ｕに対する、本実施の形態によるＬｏｏｐ細分割曲面フィッティング結果を示す。図１４（ａ）の写真に示すデザインモックアップに対して、３次元スキャナによって同図（ｂ）に示す高密度測定点群Ｕを取得した。同図（ｃ）は、この測定点群Ｕから得たボリュームベース・メッシュＭ０であり、同図（ｄ）は高密度メッシュＭ１である。そして同図（ｅ）は初期制御メッシュシードＭ２であり、同図（ｆ）はこれから得た初期制御メッシュＭ３である。そして同図（ｇ）はＬｏｏｐ細分割曲面を示している。この図１４（ｇ）に示すように極限曲面において、特徴領域となる微小フィレット面が正しく再現されていることが分かる。
【００６７】
図１５（ａ）に本実施の形態の結果のフィッティング誤差分布、図１５（ｂ）に簡略化としてＱＥＭのみに基づくＥＣを用いた場合のフィッティング誤差分布をそれぞれ示す。特徴稜線部に対応する特徴領域周辺でのフィッティング精度が本手法において向上していることが分かる。
【００６８】
図１６に、携帯電話のフロントパネルのＣＡＤデータの表面をサンプリングして得られた測定点群に対する本フィッティング手法を適用した結果を示す。同図（ａ）のモデルには複雑な穴や特徴領域が含まれるが、本実施の形態によれば、同図（ｂ）に示すように点群のもつこのような幾何形状を適切に反映した細分割曲面初期制御メッシュが生成でき、これを用いることで同図（ｃ）に示すように極限曲面を正しくフィッティングすることができることが分かる。
【００６９】
図１７にタービンブレードのＣＴスキャンから得られた測定点群Ｕに対する本実施の形態の適用結果を示す。このモデルは、非常に複雑な冷却管路を内部に含んでいるが、得られた細分割曲面は適切にこれを反映している。
【００７０】
なお、以上３つの結果にかかった処理時間は、Ｗｉｎｄｏｗｓ（登録商標）  ＰＣ（３ＧＨｚ  Ｄｕａｌ  ＣＰＵ、２ＧＢ  ＲＡＭ）を用いていずれも５分以内に完了した。図１８に、測定点群の点数、フィッティングされた細分割曲面の初期制御メッシュの面分数、極限曲面の正規化フィッティング誤差の最大・平均を示す（測定点群のバウンディングボックスの対角線長で正規化）。１０−３程度の正規化誤差を保ちながら、１００分の１から５００分の１程度の頂点数の初期制御メッシュによってフィッティングが可能である。
【００７１】
以上のように本実施の形態によれば、穴や特徴稜線を含む複雑形状の高密度測定点群に対し、メッシュ上の曲率評価に基づいて、微小フィレットとなる特徴稜線部に対しても適切な位相構造をもつ初期制御メッシュを推定し、高精度かつ高速なＬｏｏｐ細分割曲面へのフィッティングが可能であり、その有効性も計算機実験により確認できた。
【図面の簡単な説明】
【００７２】
【図１】本発明の１つの実施の形態の３次元モデルのフィッティング装置のブロック図。
【図２】上記実施の形態において処理する３次元モデルのフィッティング処理のシーケンス図。
【図３】Ｍａｒｃｈｉｎｇ  Ｃｕｂｅｓの概要の説明図。
【図４】ボリュームベース・メッシュの生成時に用いる格子点属性値に基づく面生成基本パターンテーブルの説明図。
【図５】Ｓｈｒｉｎｋ  ｗｒａｐｐｉｎｇ法のシーケンス図。
【図６】Ｓｈｒｉｎｋ  ｗｒａｐｐｉｎｇ法の原理を示す説明図。
【図７】Ｓｈｒｉｎｋ  ｗｒａｐｐｉｎｇ法の説明図。
【図８】ボリュームベース・メッシュの画像及びＳｈｒｉｎｋ  Ｗｒａｐｐｉｎｇ法により生成した高密度メッシュの画像。
【図９】従来の特徴境界稜線抽出処理の説明図。
【図１０】上記実施の形態による特徴境界稜線抽出処理の説明図
【図１１】上記実施の形態において実施する頂点曲率評価による特徴境界線抽出処理の説明図。
【図１２】ＥＣにおける稜線の縮退コストと新しい頂点位置の定める方法についての説明図。
【図１３】上記実施の形態において実施する初期制御メッシュの幾何改良の処理の説明図。
【図１４】Ｌｏｏｐ細分割曲面フィッティング結果を示す図。
【図１５】フィッティング誤差分布を示す図。
【図１６】フィッティング手法を適用した結果を示す図。
【図１７】タービンブレードのＣＴスキャンから得られた測定点群に対する本実施の形態の適用結果を示す図。
【図１８】測定点群の点数、フィッティングされた細分割曲面の初期制御メッシュの面分数、極限曲面の正規化フィッティング誤差の最大・平均を示す表。
【符号の説明】
【００７３】
１０１  ３次元モデル測定部
１０２  高密度測定部
１０３  高密度メッシュ構築部
１０４  特徴境界抽出部
１０５  初期制御メッシュシード生成部
１０６  初期制御メッシュ幾何部
【図１】
2006277712.tif 000020
【図２】
2006277712.tif 000021
【図３】
2006277712.tif 000022
【図４】
2006277712.tif 000023
【図５】
2006277712.tif 000024
【図６】
2006277712.tif 000025
【図７】
2006277712.tif 000026
【図８】
2006277712.tif 000027
【図９】
2006277712.tif 000028
【図１０】
2006277712.tif 000029
【図１１】
2006277712.tif 000030
【図１２】
2006277712.tif 000031
【図１３】
2006277712.tif 000032
【図１４】
2006277712.tif 000033
【図１５】
2006277712.tif 000034
【図１６】
2006277712.tif 000035
【図１７】
2006277712.tif 000036
【図１８】
2006277712.tif 000037