(57)【特許請求の範囲】
【請求項１】
計測器等で計測することにより得られた物体の表面に分布する整列していない点群からポリゴンメッシュを自動生成するシステムであって、
前記点群の最小表面密度を計算する手段と、該最小表面密度からボクセルサイズを決定する手段と、該ボクセルサイズのボリュームモデルを生成する手段と、該ボリュームモデルを用いて前記点群内の点に基本メッシュの頂点をのせるようにして、基本メッシュの格子点を設定する手段と、該格子点からポリゴンメッシュを生成する手段とを有して、前記点群から基本ポリゴンメッシュを生成する手段と、
基本ポリゴンメッシュの面と前記点群とを関係付ける面属性を求める手段と、頂点分割操作によりポリゴンメッシュを詳細化する手段とを有して、得られた基本ポリゴンメッシュから、前記点群の点全てを頂点とする操作によりポリゴンメッシュを詳細化する手段、
を有することを特徴とするポリゴンメッシュを生成するシステム。
【請求項２】
請求項１に記載されたポリゴンメッシュを生成するシステムにおいて、前記面属性を求める手段は、点の座標と面との距離を面の属性として求めるものであることを特徴とする、ポリゴンメッシュを生成するシステム。
【請求項３】
請求項１又は２に記載されたポリゴンメッシュを生成するシステムにおいて、前記ポリゴンメッシュを詳細化する手段は、点群中の全ての点の中で、面との距離が最大である点及び該点が属する面のうち、距離エネルギーが最小となるものを詳細化することを特徴とするポリゴンメッシュを生成するシステム。
【請求項４】
計測器等で計測することにより得られた物体の表面に分布する整列していない点群からポリゴンメッシュを自動生成する方法であって、前記点群の最小表面密度を計算する手段と、該最小表面密度からボクセルサイズを決定する手段と、該ボクセルサイズのボリュームモデルを生成する手段と、該ボリュームモデルを用いて前記点群内の点に基本メッシュの頂点をのせるようにして、基本メッシュの格子点を設定する手段と、格子点からポリゴンメッシュを生成する手段により、前記点群から基本ポリゴンメッシュを生成する工程と、得られた基本ポリゴンメッシュの面と前記点群とを関係付ける面属性を求める手段と、頂点分割操作によりポリゴンメッシュを詳細化する手段により、前記点群の点全てを頂点とする操作によりポリゴンメッシュを詳細化する工程とを含むことを特徴とするポリゴンメッシュを生成する方法。
【請求項５】
請求項４に記載されたポリゴンメッシュを生成する方法において、前記面属性を求める手段は、点の座標と面との距離を面の属性として求めるものであることを特徴とするポリゴンメッシュを生成する方法。
【請求項６】
請求項４又は５に記載されたポリゴンメッシュを生成する方法において、前記頂点分割操作は、点群中の全ての点の中で、面との距離が最大である点及び該点が属する面のうち、距離エネルギーが最小となるものについて行うことを特徴とするポリゴンメッシュを生成する方法。
【請求項７】
計測器等で計測することにより得られた物体の表面に分布する整列していない点群からポリゴンメッシュを自動生成するプログラムを記録したコンピュータ読取可能な記録媒体であって、コンピュータを、前記点群の最小表面密度を計算する手段と、該最小表面密度からボクセルサイズを決定する手段と、該ボクセルサイズのボリュームモデルを生成する手段と、該ボリュームモデルを用いて前記点群内の点に基本メッシュの頂点をのせるようにして、基本メッシュの格子点を設定する手段と、該格子点からポリゴンメッシュを生成する手段とを有して、前記点群から基本ポリゴンメッシュを生成する手段と、
得られた基本ポリゴンメッシュの面と前記点群とを関係付ける面属性を求める手段と、頂点分割操作によりポリゴンメッシュを詳細化する手段とを有して、前記点群の点全てを頂点とする操作によりポリゴンメッシュを詳細化する手段と、
を有する、ポリゴンメッシュを生成するシステムとして機能させるためのプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元形状モデル生成装置、特に、既存製品の流用設計のための形状入力装置、インターネットＶＲＭＬコンテンツ作成装置、非接触測定結果解析装置に用いることができるＣＡＤ／ＣＡＭを用いた３次元形状モデル自動生成システム及び、同モデルの自動生成方法に関するものである。
【０００２】
【従来の技術】
近年、インターネット上でマルチメディア利用の広がりとともに、３次元表現の利用は拡大しており、３次元モデリングの重要性が高まっている。そのなかでも２次元イメージを基にした３次元モデリング手法が数多く提案されている。２次元イメージを基にした３次元点群の特徴としては、まばらで密度が一定していないことがあげられる。
整列していない３次元点群からポリゴンモデルを自動生成する手法としては、過去にいくつかの方法が提案されている。Hoppeらの方法［［３］Hugues Hoppe,Tony DeRose,Tom Duchamp,John McDonald,and Werner Stuetzle,Surfacereconstruction from unorganized points.In Edwin E.Catmull,editor,Computer Graphics(SIGGRAPH'92 Proceedings),volume 26,pages 71-78,July 1992.］では密度が高く一定している、測定器で取り込んだ点群を想定している。Marching Cubes法（３次元空間に格子状に存在する０か１の値をもつ参照点の集合から境界面（０と１を隔てるポリゴンメッシュ）を生成するアルゴリズムである。まず、直方体を形成するような隣接する参照点８個の集合（Cell）において、各参照点の値が０か１かを調べ、そのパターンにより部分的なポリゴンメッシュを生成する。この操作をすべてのCellにおいて行うことですべての参照点の境界面を表すポリゴンメッシュを生成することができる）［［５］William E.Lorensen and Harvey E. Cline.Marching cubes:A hige resolution 3D surface construction algorithm.In Maureen C.Stone,editor,Computer Graphics(SIGGRAPH'87 Proceedigs),volume 21,pages 163-169,July 1987.］を用いる彼らの手法では、まばらな密度が一定していない点群では最も密度が低いところに合わせて格子間隔を広げることを余儀なくされ、精度のよいメッシュを作成できない点群から生成したポリゴンメッシュは、雑音除去，特徴抽出，最適化，簡単化など様々な後処理が行われるが、精度の悪いメッシュはいずれの処理においても不利である。一般にはポリゴンメッシュ生成後も点群データを保存してそれを補うために用いており、［［１］Matthias Eck,Tony DeRose,Tom Duchamp,Hugues Hoppe,Michael Lounsbery, and Werner Stuetzle. Multiresolution analysis of arbitrary meshes.In Robert Cook,editor,SIGGRAPH 95 Conference Proceedings,Annual Conference Series,pages 173-182.ACM SIGGRAPH,Addison Wesley,August 1995.held in Los Angeles,California,06-11 August 1995.］及び、［４］Hugues Hoppe,Tony DeRose,Tom Duchamp,John McDnald,and Werner Stuetzle.Meshoptimization.In James T.Kajiya,editor,Computer Graphics(SIGGRAPH'93 Proceedings),volume 27,pages 19-26,August 1993.］の処理が複雑になる要因になっている。
一方、Veltkampの方法［［７］Remco C.Veltkamp.Boundaries through scattered points of unknown density.Graphical Models and Image processing,57(6):441-452,1995.］では、γ-neighborhood graph［［６］R.C.Veltkamp.The γ-neighborhood graph.Comput.Geom.Theory Appl.,1(4):227 -246,1992.］を用いて与えられた点群の点をすべてポリゴンメッシュの頂点にすることができる。すなわち、まばらな点群からでも精度のよいポリゴンメッシュを作成できるが、単純な位相を持った物体に限定され貫通穴などを再現できない。位相構造を失ったポリゴンメッシュは視覚的にはさほど問題がないが、工学的には構造解析できないという問題がある。３次元表現利用の拡大につれて視覚利用以外の利用方法も増加しており、この問題は拡大する傾向がある。
【０００３】
輪郭ボクセル内に点群を含むボリュームモデルの生成については、芹田らの方法［［８］芹田陽一郎,渡邊大地,and 千代倉弘明.ボリューミング手法を用いた点群データからのポリゴンおよび曲面モデル自動再生成.In 第13回 NICOGRAPH/MULTIMEDIA 論文コンテスト論文集,volume 13,pages 70-79,1997.］があるが、ボクセルサイズの大きさを自動的に決定できないため、位相構造を再現できない場合や、輪郭ボクセルの欠損が発生する場合がある。このようなボクセルやそのボクセルが生成したポリゴンメッシュでは実際の物体を再現したソリッドモデルとして構造解析などに用いることができない。
ボリュームモデルからポリゴンメッシュの生成については、前掲［８］芹田らの方法があるが、一旦ボクセルの中心同士を結んだ線上にできる中間点を頂点とするポリゴンメッシュを生成した後で、アジャストメントにより頂点をボクセル内の代表点に移動し、代表点を頂点とするポリゴンメッシュを生成している。しかし、この際、頂点の移動に伴って、面や稜線を消去しなければならない。面や稜線の除去は専用の位相構造をもったシステムを構築しない限り、煩雑な処理が必要になる。
ポリゴンメッシュの詳細度を位相構造を保存したまま変更する方法については、Hoppeら［［２］Hugues Hoppe.Progressive meshes.In Holly Rushmeier,editor,SIGGRAPH 96 Conference Proceedings,Annual Conference Series,pages 99-108.ACM SIGGRAPH,Addision Wesley,August 1996.held in New Orleans,Louisiana,04-09 August 1996.］により提案されている。ここでProgressive meshesとは、詳細なポリゴンメッシュの表示の際に、まず簡略化したメッシュを表示し、徐々に複雑なメッシュにしていくことを表現する技術である。まず詳細なポリゴンメッシュをベースとなる粗いメッシュと、詳細なメッシュから粗いメッシュに変更するまでの情報（頂点分割情報）の集まりに分解する。次に粗いメッシュの頂点を分割して稜線を元どおり復活させる（頂点分割処理）ことにより、任意の詳細度のメッシュを得ることができる。
しかし、彼らは詳細なポリゴンメッシュから簡単化する手法は提案しているが、簡単なポリゴンメッシュから詳細化する手法は簡単化の履歴を逆にたどることでしか実現していない。従って、粗いポリゴンメッシュと物体の表面に分布する点が与えられた前提では詳細化手法として使えない。
点群から任意の詳細度ポリゴンメッシュを得る方法については、前掲Eckら［１］、前掲Hoppeら［２］により提案されているが、いずれも一旦詳細なポリゴンメッシュを生成し、その後、簡単なメッシュにしていく。従って、点群から直接任意の詳細度のポリゴンメッシュを生成できないので、前処理に計算コストがかかる。
【０００４】
【発明が解決しようとする課題】
本発明は、以下の７点の問題点の解決を目的とする。
１．計測器等で計測することにより得られた位相構造を持った物体の表面に分布する整列していない点群からポリゴンメッシュを自動生成する場合、密度が一定でないまばらな点群に対してMarching Cubes法を用いると、精度が悪くなる。
２．計測器等で計測することにより得られた物体の表面に分布する整列していない点群から精度のよいポリゴンメッシュを自動生成する場合、位相構造を持った物体の表面に分布する点群に対してγ-neighborhood graphを用いると位相構造が失われてしまう。
３．計測器等で計測することにより得られた物体の表面に分布する整列していない点群からボリュームモデルを自動生成する場合、ボクセル間隔の設定が適切に行われないと、位相構造が失われてしまう。
４．計測器等で計測することにより得られた物体の表面に分布する整列していない点群からボリュームモデルを自動生成する場合、ボクセル間隔の設定が適切に行われないと、輪郭ボクセルに欠損がでてしまう。
【０００５】
５．輪郭ボクセルにより立体表面を覆い尽くしたボリュームモデルから輪郭ボクセル内の代表点を頂点とするポリゴンメッシュを自動生成する場合、ボクセルの中心点を頂点とするポリゴンメッシュを一旦生成する必要がある。
６．計測器等で計測することにより得られた物体の表面に分布する整列していない点群の一部を頂点とする粗いポリゴンメッシュから残りの点群の点を利用して詳細なポリゴンメッシュを生成する場合、従来の手法では実現できない。
７．計測器等で計測することにより得られた、物体の表面に分布する整列していない点群の一部を頂点とする任意の詳細度のポリゴンメッシュを生成する場合、点群の点をすべて利用した詳細なポリゴンメッシュを一旦生成する必要がある。
【０００６】
【課題を解決するための手段】
請求項１の発明は、計測器等で計測することにより得られた物体の表面に分布する整列していない点群からポリゴンメッシュを自動生成するシステムであって、前記点群の最小表面密度を計算する手段と、該最小表面密度からボクセルサイズを決定する手段と、該ボクセルサイズのボリュームモデルを生成する手段と、該ボリュームモデルを用いて前記点群内の点に基本メッシュの頂点をのせるようにして、基本メッシュの格子点を設定する手段と、該格子点からポリゴンメッシュを生成する手段とを有して、前記点群から基本ポリゴンメッシュを生成する手段と、基本ポリゴンメッシュの面と前記点群とを関係付ける面属性を求める手段と、頂点分割操作によりポリゴンメッシュを詳細化する手段とを有して、得られた基本ポリゴンメッシュから、前記点群の点全てを頂点とする操作によりポリゴンメッシュを詳細化する手段、を有することを特徴とするポリゴンメッシュを生成するシステムである。
【０００８】
請求項２の発明は、請求項１に記載されたポリゴンメッシュを生成するシステムにおいて、前記面属性を求める手段は、点の座標と面との距離を面の属性として求めるものであることを特徴とする、ポリゴンメッシュを生成するシステムである。
【０００９】
請求項３の発明は、請求項１又は２に記載されたポリゴンメッシュを生成するシステムにおいて、前記ポリゴンメッシュを詳細化する手段は、点群中の全ての点の中で、面との距離が最大である点及び該点が属する面のうち、距離エネルギーが最小となるものを詳細化することを特徴とするポリゴンメッシュを生成するシステムである。
【００１０】
請求項４の発明は、計測器等で計測することにより得られた物体の表面に分布する整列していない点群からポリゴンメッシュを自動生成する方法であって、前記点群の最小表面密度を計算する手段と、該最小表面密度からボクセルサイズを決定する手段と、該ボクセルサイズのボリュームモデルを生成する手段と、該ボリュームモデルを用いて前記点群内の点に基本メッシュの頂点をのせるようにして、基本メッシュの格子点を設定する手段と、格子点からポリゴンメッシュを生成する手段により、前記点群から基本ポリゴンメッシュを生成する工程と、得られた基本ポリゴンメッシュの面と前記点群とを関係付ける面属性を求める手段と、頂点分割操作によりポリゴンメッシュを詳細化する手段により、前記点群の点全てを頂点とする操作によりポリゴンメッシュを詳細化する工程とを含むことを特徴とするポリゴンメッシュを生成する方法である。
【００１１】
請求項５の発明は、請求項４に記載されたポリゴンメッシュを生成する方法において、前記面属性を求める手段は、点の座標と面との距離を面の属性として求めるものであることを特徴とするポリゴンメッシュを生成する方法である。
【００１２】
請求項６の発明は、請求項４又は５に記載されたポリゴンメッシュを生成する方法において、前記頂点分割操作は、点群中の全ての点の中で、面との距離が最大である点及び該点が属する面のうち、距離エネルギーが最小となるものについて行うことを特徴とするポリゴンメッシュを生成する方法である。
【００１５】
請求項７の発明は、計測器等で計測することにより得られた物体の表面に分布する整列していない点群からポリゴンメッシュを自動生成するプログラムを記録したコンピュータ読取可能な記録媒体であって、コンピュータを、前記点群の最小表面密度を計算する手段と、該最小表面密度からボクセルサイズを決定する手段と、該ボクセルサイズのボリュームモデルを生成する手段と、該ボリュームモデルを用いて前記点群内の点に基本メッシュの頂点をのせるようにして、基本メッシュの格子点を設定する手段と、該格子点からポリゴンメッシュを生成する手段とを有して、前記点群から基本ポリゴンメッシュを生成する手段と、得られた基本ポリゴンメッシュの面と前記点群とを関係付ける面属性を求める手段と、頂点分割操作によりポリゴンメッシュを詳細化する手段とを有して、前記点群の点全てを頂点とする操作によりポリゴンメッシュを詳細化する手段と、を有する、ポリゴンメッシュを生成するシステムとして機能させるためのプログラムを記録したコンピュータ読取可能な記録媒体である。
【００１６】
以上、本発明によれば次のような作用が得られる。
即ち、計測器等で計測することにより得られた物体の表面に分布する整列していない点群からポリゴンメッシュを自動生成するシステム及び方法において、
（１）点群内の点をすべてポリゴンの頂点とする精度のよいポリゴンメッシュ生成ができ、
（２）穴などの位相構造を持った物体の場合でも位相構造を再現でき、
（３）穴などの位相構造を持った物体の場合でも位相構造を再現できるボリュームモデルを生成できる。
（４）輪郭ボクセルにより立体を覆い尽くしたソリッドモデルを自動的に生成できる。
（５）ボクセルの中心点を頂点とするポリゴンメッシュを一旦生成することなく、直接輪郭ボクセル内の代表点をすべてポリゴンメッシュの頂点にできる。
（６）粗いポリゴンメッシュの位相構造を保存したまま詳細なポリゴンメッシュを生成できる。
（７）残りの点群の点をすべて利用した詳細なポリゴンメッシュを一旦生成することなく、任意の詳細度のポリゴンメッシュを直接生成できる。
【００１７】
【発明の実施の形態】
本発明の実施形態を図面を参照して説明する。
本発明の実施形態において、計測器等で計測することにより得られた物体の表面に分布する点群について、（１）点群は物体の表面に分布している、（２）点群は整列していない、即ち、隣の点は順番，周期などで明らかではない、（３）点群の密度は一定ではない、の各条件に合致したものであることを前提としている。
本発明を前記前提に基づき、図１のフローチャートを参照して説明する。
まず、基本メッシュの生成について説明し、その後詳細メッシュの生成について説明する。
【００１８】
１．基本メッシュ生成について、
まず、位相構造が再現された粗い基本メッシュを生成する。
基本メッシュの生成は次の工程から成っている。
（ａ）点群の最小表面密度計算（Ｓ１０１）
例えば、図５に示す点群（５０００点）の最小表面密度を計算する。
点群Ｐ＝（ｐ1，ｐ2，…，ｐn）内のある点ｐiについてｋ個の近傍の点（K-neighborhood）を求める。
K-neighborhoodとは、ある点からの距離が近い順にｋ個の点を取得したものである。
ｋは点群の性質により決定する。密度が一定の点群では比較的小さな数、密度がまばらで一定していない点群では大きな数を設定する。
K-neighborhoodの中でもとの点Ｐiから最も遠い点Ｐnfと、もとの点Ｐiの間の距離を半径とする円の面積Ａdiscを計算する。
【００１９】
【数１】
0003739209.tif 000002
【００２０】
点Ｐnfと点Ｐiの間の距離を半径とし、点Ｐiを中心とする球の内部にK-neighborhoodのすべての点は含まれる。また、点は物体の表面に分布するため、局所的には平面になるものと考えられる。従って、点Ｐiにおける表面密度ρは
【００２１】
【数２】
0003739209.tif 000003
【００２２】
となる。
以上の計算を全ての点または代表的な点について行い、その中で得られた最小の表面密度ρminを点群の最小表面密度とする。
【００２３】
（ｂ）ボクセルサイズの決定（Ｓ１０２）
ボクセルの１辺の大きさＬvxを最小表面密度ρminを用いた以下の条件を満たすように決定する。
【００２４】
【数３】
0003739209.tif 000004
【００２５】
Ｃαはマージンをあらわす１より大きな定数である。点群の最小表面密度に基づいてボクセルの大きさを決定しているので、輪郭ボクセルにより物体の表面を覆い尽くすことができる。また、貫通穴などの位相構造はボクセルサイズが大きいと再現できないことがあるが、本発明の方法だと表面を覆う輪郭ボクセルに欠損のない範囲で最小限の大きさにボクセルサイズが設定されるので、位相は全て再現できる。
【００２６】
（ｃ）ボリュームモデルの生成（Ｓ１０３）
（ｂ）で定めたボクセルサイズのボリュームモデルを生成する。ボリュームモデルの生成は前掲の芹田らの方法［８］を用いる。その結果、属性１を持ったボクセルを内部，属性０のボクセルを外部とする、例えば、図６に示すボリュームモデルが生成される。
【００２７】
（ｄ）基本メッシュの生成
格子点連結法を実施しボリュームモデルから、例えば、図７に示す基本メッシュを生成する。
我々は、基本メッシュの頂点を点群内の点にのせるため、Marching Cubes法を修正した格子点連結法（Marching Lattice Points Method）を開発した。この方法ではポリゴン生成後に頂点移動，稜線削除，面削除を行うことなく、頂点座標に点群内の点群座標を採用したポリゴンメッシュを直接生成できる。
・格子点および値の決定（Ｓ１０４）
隣接する８つのボクセルの代表点をMarching Cubesの一つのCellにあてはめ、格子点に値を設定する。格子点の値はボクセルの属性値０，１をそのまま利用する。代表点はボクセル内に含まれる点のなかから、ボクセルの中心に近い点を選ぶ。
・ポリゴン生成（Ｓ１０５）
格子点の値は属性値０が立体の外部、属性値１が立体の内部としてポリゴンを生成する。格子点の属性の組み合わせは２５６通りあるが、回転により同じ位相になるものを省くと、２３通りになる。このなかでポリゴンを生成するものは、図２に示す１３通りである。これらに従ってポリゴン生成を行う。
【００２８】
２．細密メッシュの生成
基本メッシュから以下の工程により点群の点全てを頂点とする細密メッシュを生成する。
（ａ）面属性登録（Ｓ１０６）
点群を基本メッシュを構成する面に射影することで面と関係づけ、点の座標と面との距離を面の属性として登録する。点群内の点は全て、いずれかの面の属性になる。すべての点の中で面との距離が最大である点Ｐf、およびＰfが属する面、すなわち点との距離が最大である面Ｆfについては、後述する頂点分割操作が行われても常に最新のものが参照できるように保持，更新できるようにしておく。
射影方法は三角形面の法線ベクトル方向に行い、次の条件を同時に満たす面に点を登録する。
（１）内部に射影できた三角形面
（２）最短距離で射影できた三角形面
どの面にも射影できない点に関しては、面に射影できない点と最短距離になる稜線上の点または頂点を求め、その点と元の点を結ぶベクトルと、稜線または頂点に隣接する面の法線ベクトルのなす角度が最も小さな面に属性として登録する。
【００２９】
（ｂ）頂点分割操作によるポリゴンメッシュの詳細化
基本メッシュの位相を保ちながら詳細化操作を行うために、我々は頂点分割操作（vertex split）（前掲［２］）を順方向操作に使えるようにポリゴンメッシュ変形機能として拡張した。もともと頂点分割操作（vertex split）は、前掲［２］（Progressive Mesh）における稜線分割操作（edge collapse）に対する逆操作であるが、次のような関数仕様に変更し、詳細化の基本操作として用いる。
【００３０】
【数４】
0003739209.tif 000005
【００３１】
ここで↓は入力引数を、↑は出力引数を表わす。Ｖs，Ｖt，Ｖuは頂点、Ｆl，Ｆr，Ｆlt，Ｆlu，Ｆrt，Ｆruは面、ＣVt，ＣVu，ＣVsは座標をそれぞれ表わしており、要素間の関係を図３に示す。
この頂点分割操作関数vsplitに対し、Ｖsに点との距離が最大である面Ｆf内の頂点ＶFfを、ＣVtに頂点ＶFfの座標を、ＣVuに面との距離が最大である点Ｐfの座標を、それぞれ与える。その結果、ポリゴンメッシュから最も遠い点Ｐfを新たな頂点Ｖnとする詳細化ができる（Ｓ１０８）。図４にその様子を示す。
点Ｐfが射影される面Ｆfの頂点ＶFfは３点存在する。また、Ｆlt，Ｆlu，Ｆrt，Ｆruの候補も頂点ＶFfのまわりの面の組み合わせにより複数存在する。このように、点に対する頂点分割操作にいくつかの候補があるが、頂点分割操作を行った際に距離エネルギーが最小となるような候補を選択する（Ｓ１０９）。
ポリゴンメッシュＭの距離エネルギーＥdist（Ｍ）は、点群内の点とポリゴンメッシュの面との距離の２乗和になる。頂点分割操作前後に変化する面が存在する領域は限られているので、その範囲内の面についてのみエネルギーの差分計算を行えばよい。頂点分割操作を適用した際に変化する面の範囲を図４の太線内に示す。
以上のように、ポリゴンメッシュから最も離れている点から順にポリゴンメッシュに取り込み（１１０）、その操作を取り込み点がなくなるまで続ければ、点群内のすべての点を頂点とする、例えば、図８に示す細密メッシュが得られる。
また、以上で説明したポリゴンメッシュの生成方法をコンピュータで実施することができる。即ち、前記方法をコンピュータに実施させるためのプログラムを記録媒体に記録することにより、任意のコンピュータで前記方法を容易に実施することができる。
【００３２】
【発明の効果】
請求項１乃至８に対応する効果：計測器等で計測することにより得られた位相構造を持った物体の表面に分布する整列していない密度が一定でないまばらなポリゴンメッシュを自動生成する場合、
（１）点群内の点が全て頂点になる精度のよい、もとの物体の位相構造を再現した、輪郭ボクセルに欠損のないボリュームモデルが得られる。
（２）輪郭ボクセルにより立体表面を覆い尽くしたボリュームモデルから輪郭ボクセル内の代表点を頂点とするポリゴンメッシュを自動生成する場合、ボクセルの中心点を頂点とするポリゴンメッシュを一旦生成することなしに輪郭ボクセル内の代表点を頂点とするポリゴンメッシュが得られる。
（３）計測器等で計測することにより得られた物体の表面に分布する整列していない点群の一部を頂点とする、粗いポリゴンメッシュからの残りの点群の点を利用して詳細なポリゴンメッシュが生成できる。
（４）計測器等で計測することにより得られた物体の表面に分布する整列していない点群の一部を頂点とする、粗いポリゴンメッシュからの残りの点群の点を利用して詳細度の異なるポリゴンメッシュを生成する場合に、残りの点群の点をすべて利用した詳細なポリゴンメッシュを一旦生成することなしに任意の詳細度のポリゴンメッシュが得られる。
（５）本発明を３次元ＣＡＤシステムなどに実現することによって、点群からの３次元形状モデルを自動生成できる。
請求項９，１０に対応する効果：任意のコンピュータにより、本発明のポリゴンメッシュを生成する方法を容易に実施することができる。
【図面の簡単な説明】
【図１】  本発明によるポリゴン自動作成行程を説明するためのフロー図である。
【図２】  格子点連結法におけるポリゴン生成方法を説明するための図である。
【図３】  本発明による頂点分割操作の一例を示す図である。
【図４】  本発明による頂点分割操作による詳細化の一例を示す図である。
【図５】  物体の表面に分布した点群を示す図である。
【図６】  本発明のボリュームモデルの例を示す図である。
【図７】  本発明による基本メッシュの例を示す図である。
【図８】  本発明による細密メッシュの例を示す図である。
【図１】
0003739209.tif 000006
【図２】
0003739209.tif 000007
【図３】
0003739209.tif 000008
【図４】
0003739209.tif 000009
【図５】
0003739209.tif 000010
【図６】
0003739209.tif 000011
【図７】
0003739209.tif 000012
【図８】
0003739209.tif 000013