(57)【特許請求の範囲】
【請求項１】
距離画像から３角形メッシュを生成して３次元形状を生成する３次元形状生成装置の３次元形状生成方法において、
距離画像ボリューム生成手段が、輪郭・内部・外部の３つの属性値のいずれかを持つ個々のボクセルから成るボリュームモデルを距離画像から生成する工程と、
基本メッシュ生成手段が、隣接する８ボクセル属性値から三角形生成情報と回転情報を取得し、取得した回転情報により８ボクセルを回転変換させ、回転変換させた８ボクセルと三角形生成情報とを用いて基本３角形メッシュを生成する工程と、
頂点フィッティング手段が、前記基本３角形メッシュの頂点として薄板境界頂点、非多様体稜線接続頂点、非多様体頂点、および一般頂点のうち、少なくとも２種類以上の頂点を検出し、検出した頂点の種類に応じて異なった頂点移動方法を選択し、前記基本３角形メッシュの頂点を移動させて３角形メッシュを生成する工程と、薄板境界頂点まわりの複数の基本３角形メッシュを薄板境界稜線に沿って切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより薄板境界頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する工程と、
を実行することを特徴とする３次元形状生成方法。
【請求項２】
請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから薄板境界稜線を検出する工程と、検出された薄板境界稜線から前記薄板境界頂点を検出する工程と、を実行することを特徴とする３次元形状生成方法。
【請求項３】
請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから非多様体稜線を検出する工程と、前記非多様体稜線接続頂点を検出する工程と、を実行することを特徴とする３次元形状生成方法。
【請求項４】
請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、非多様体稜線接続頂点を挟んで直交する２本の一般稜線を選択し、選択された２本の一般稜線に沿って前記非多様体稜線接続頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体稜線接続頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する工程を実行することを特徴とする３次元形状生成方法。
【請求項５】
請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから非多様体頂点を検出する工程を実行することを特徴とする３次元形状生成方法。
【請求項６】
請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、非多様体頂点を挟んで直交する稜線２本を１組とする稜線の組を複数組選択し、選択された複数組の稜線の各組の稜線に沿って前記非多様体頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体頂点を移動し、その移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する工程を実行することを特徴とする３次元形状生成方法。
【請求項７】
請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから面構成パターンを選択する工程と、選択された面構成パターン毎に新たに頂点と稜線を生成する工程と、を実行し、新たに生成した頂点を距離画像メッシュ上にのるまで移動することにより、前記一般頂点を移動することを特徴とする３次元形状生成方法。
【請求項８】
請求項１乃至請求項７のいずれか１項に記載の３次元形状生成方法において、前記頂点フィッティング手段が、頂点に隣接する基本３角形メッシュの平均法線ベクトルを計算し、求まった平均法線ベクトルから対角線ベクトルを取得し、対角線ベクトルに沿って距離画像メッシュと交差するまで頂点を移動させることにより前記頂点を距離画像メッシュ上にのるまで移動する工程を実行することを特徴とする３次元形状生成方法。
【請求項９】
コンピュータに請求項１乃至８の何れか１項に記載の工程を実行させるためのプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１０】
距離画像から３角形メッシュを生成して３次元形状を生成する３次元形状生成装置において、
輪郭・内部・外部の３つの属性値のいずれかを持つ個々のボクセルから成るボリュームモデルを距離画像から生成する距離画像ボリューム生成手段と、
隣接する８ボクセル属性値から三角形生成情報と回転情報を取得し、取得した回転情報により８ボクセルを回転変換させ、回転変換させた８ボクセルと三角形生成情報とを用いて基本３角形メッシュを生成する基本メッシュ生成手段と、
前記基本３角形メッシュの頂点として、薄板境界頂点、非多様体稜線接続頂点、非多様体頂点、および一般頂点のうち、少なくとも２種類以上の頂点を検出し、検出した頂点の種類に応じて異なった頂点移動方法を選択し、前記基本３角形メッシュの頂点を移動させて３角形メッシュを生成する手段と、薄板境界頂点まわりの複数の基本３角形メッシュを薄板境界稜線に沿って切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより薄板境界頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段と、を有する頂点フィッティング手段と、
を備えたことを特徴とする３次元形状生成装置。
【請求項１１】
請求項１０に記載の３次元形状生成装置において、
前記頂点フィッティング手段は、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから薄板境界稜線を検出する手段と、検出された薄板境界稜線から前記薄板境界頂点を検出する手段と、を備えたことを特徴とする３次元形状生成装置。
【請求項１２】
請求項１０に記載の３次元形状生成装置において、
前記頂点フィッティング手段は、前記２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから非多様体稜線を検出する手段と、前記非多様体稜線接続頂点を検出する手段と、を備えたことを特徴とする３次元形状生成装置。
【請求項１３】
請求項１０に記載の３次元形状生成装置において、
前記頂点フィッティング手段は、非多様体稜線接続頂点を挟んで直交する２本の一般稜線を選択し、選択された２本の一般稜線に沿って前記非多様体稜線接続頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体稜線接続頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段を備えたことを特徴とする３次元形状生成装置。
【請求項１４】
請求項１０に記載の３次元形状生成装置において、
前記頂点フィッティング手段は、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから非多様体頂点を検出する手段を備えたことを特徴とする３次元形状生成装置。
【請求項１５】
請求項１０に記載の３次元形状生成装置において、
前記頂点フィッティング手段は、非多様体頂点を挟んで直交する稜線２本を１組とする稜線の組を複数組選択し、選択された複数組の稜線の各組の稜線に沿って前記非多様体頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体頂点を移動し、その移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段を備えたことを特徴とする３次元形状生成装置。
【請求項１６】
請求項１０に記載の３次元形状生成装置において、
前記頂点フィッティング手段は、
２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから面構成パターンを選択する手段と、選択された面構成パターン毎に新たに頂点と稜線を生成する手段と、を備え、新たに生成した頂点を距離画像メッシュ上にのるまで移動することにより、前記一般頂点を移動することを特徴とする３次元形状生成装置。
【請求項１７】
請求項１０乃至請求項１６のいずれか１項に記載の３次元形状生成装置において、前記頂点フィッティング手段は、頂点に隣接する基本３角形メッシュの平均法線ベクトルを計算し、求まった平均法線ベクトルから対角線ベクトルを取得し、対角線ベクトルに沿って距離画像メッシュと交差するまで頂点を移動させることにより前記頂点を距離画像メッシュ上にのるまで移動することを特徴とする３次元形状生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、専用の３次元形状処理装置やパーソナルコンピュータなど情報処理装置などで実施される３次元形状生成方法に係わり、特に、３角形メッシュ生成方法に関する。
【０００２】
【従来の技術】
近年、インターネット上でのマルチメディア利用の広がりとともに、グラフィクス表示装置とコンピュータとを用いて構成される３次元形状処理システムが普及し、記憶されている３次元形状データ読み出して３次元形状モデルを表示させたり、３次元形状を生成したり、生成されている３次元形状を変形させたり、３次元形状の体積や重心などを計算したりすることが広く行われている。
そのような中で、最近、３次元測定器などを用いて取り込んだ３次元の点群データや距離画像をもとにして符号付き距離関数を生成し、マーチングキューブス法（参考文献［１］参照）などの同位相面生成手法を用いて３角形メッシュで表現される３次元形状モデルを自動生成する手法が提案されている（参考文献［２］,［３］参照）。これらの手法の長所を以下に示す。
貫通穴などの位相構造を持った形状でも生成できる。
欠落している点群がある場合でも、その穴を埋める面を生成できる。
３次元測定器の性質や測定条件による誤差がある場合でも、誤差の影響を受けにくい。
測定したサンプル点の分布に偏りがある非一様な場合でも、関数化することで一様な分布のサンプル点を得ることができる。
しかしながら、この手法には以下のような欠点がある。
鋭角の特徴の再現性が弱い。鋭角の稜線を持った機械部品など人工的に作成したものでも、常に丸みを帯びた形状として再現される。
薄い形状や細い形状の再現性が弱い。再現性が格子の位置に依存するので、特に、薄さや細さが格子間隔以下の形状では形状が必ず再現できるとは言えない。
前記した、鋭角の特徴の再現性に関して補足すると、マーチングキューブス法では３角形メッシュの頂点位置が格子軸上に限定されているので、鋭角の稜線などの特徴を十分に捉え切れないのである。また、３角形メッシュの頂点位置がボクセル内で自由に配置できる格子点連結法（参考文献［４］参照）でも、凸部分の鋭角稜線は再現できるが、凹部分の鋭角稜線は再現できない。また、薄い形状や細い形状の再現性に関しては、マーチングキューブス法では、図32に示すように格子の設定位置により、形状が再現できる場合（ｂ）とそうでない場合（ａ）があり、一般的には格子間隔以下の薄い形状や細い形状の再現性は保証されない。
【０００３】
【発明が解決しようとする課題】
前記のように、従来技術においては、３次元測定器などで測定することにより得られる距離画像から３角形メッシュを生成する際に、角張った形状の鋭角の稜線、特に凹部分の鋭角稜線が失われる、格子間隔以下の薄い形状と細い形状が失われるというような問題がある。
本発明の目的は、このような従来技術の問題を解決し、３次元測定器などで測定することにより得られる距離画像から３角形メッシュを生成する際に、角張った形状の鋭角の稜線、特に凹部分の鋭角稜線が失われるという問題、格子間隔以下の薄い形状と細い形状が失われるという問題、格子位置により形状が変化してしまうという問題などを解消できる３次元形状生成方法を提供することにある。
【０００４】
【課題を解決するための手段】
前記の課題を解決するために、請求項１記載の発明では、距離画像から３角形メッシュを生成して３次元形状を生成する３次元形状生成装置の３次元形状生成方法において、距離画像ボリューム生成手段が、輪郭・内部・外部の３つの属性値のいずれかを持つ個々のボクセルから成るボリュームモデルを距離画像から生成する工程と、基本メッシュ生成手段が、隣接する８ボクセル属性値から三角形生成情報と回転情報を取得し、取得した回転情報により８ボクセルを回転変換させ、回転変換させた８ボクセルと三角形生成情報とを用いて基本３角形メッシュを生成する工程と、頂点フィッティング手段が、前記基本３角形メッシュの頂点として薄板境界頂点、非多様体稜線接続頂点、非多様体頂点、および一般頂点のうち、少なくとも２種類以上の頂点を検出し、検出した頂点の種類に応じて異なった頂点移動方法を選択し、前記基本３角形メッシュの頂点を移動させて３角形メッシュを生成する工程と、薄板境界頂点まわりの複数の基本３角形メッシュを薄板境界稜線に沿って切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより薄板境界頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する工程と、を実行することを特徴とする。
また、請求項２記載の発明では、請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから薄板境界稜線を検出する工程と、検出された薄板境界稜線から前記薄板境界頂点を検出する工程と、を実行することを特徴とする。
また、請求項３記載の発明では、請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから非多様体稜線を検出する工程と、前記非多様体稜線接続頂点を検出する工程と、を実行することを特徴とする。
また、請求項４記載の発明では、請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、非多様体稜線接続頂点を挟んで直交する２本の一般稜線を選択し、選択された２本の一般稜線に沿って前記非多様体稜線接続頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体稜線接続頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する工程を実行することを特徴とする。
【０００５】
また、請求項５記載の発明では、請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから非多様体頂点を検出する工程を実行することを特徴とする。
また、請求項６記載の発明では、請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、非多様体頂点を挟んで直交する稜線２本を１組とする稜線の組を複数組選択し、選択された複数組の稜線の各組の稜線に沿って前記非多様体頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体頂点を移動し、その移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する工程を実行することを特徴とする。
また、請求項７記載の発明では、請求項１に記載の３次元形状生成方法において、前記頂点フィッティング手段が、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから面構成パターンを選択する工程と、選択された面構成パターン毎に新たに頂点と稜線を生成する工程と、を実行し、新たに生成した頂点を距離画像メッシュ上にのるまで移動することにより、前記一般頂点を移動することを特徴とする。
また、請求項８記載の発明では、請求項１乃至請求項７のいずれか１項に記載の３次元形状生成方法において、前記頂点フィッティング手段が、頂点に隣接する基本３角形メッシュの平均法線ベクトルを計算し、求まった平均法線ベクトルから対角線ベクトルを取得し、対角線ベクトルに沿って距離画像メッシュと交差するまで頂点を移動させることにより前記頂点を距離画像メッシュ上にのるまで移動する工程を実行することを特徴とする。
また、請求項９記載の発明では、コンピュータに請求項１乃至８の何れか１項に記載の工程を実行させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体を特徴とする。
また、請求項１０記載の発明では、距離画像から３角形メッシュを生成して３次元形状を生成する３次元形状生成装置において、輪郭・内部・外部の３つの属性値のいずれかを持つ個々のボクセルから成るボリュームモデルを距離画像から生成する距離画像ボリューム生成手段と、隣接する８ボクセル属性値から三角形生成情報と回転情報を取得し、取得した回転情報により８ボクセルを回転変換させ、回転変換させた８ボクセルと三角形生成情報とを用いて基本３角形メッシュを生成する基本メッシュ生成手段と、前記基本３角形メッシュの頂点として、薄板境界頂点、非多様体稜線接続頂点、非多様体頂点、および一般頂点のうち、少なくとも２種類以上の頂点を検出し、検出した頂点の種類に応じて異なった頂点移動方法を選択し、前記基本３角形メッシュの頂点を移動させて３角形メッシュを生成する手段と、薄板境界頂点まわりの複数の基本３角形メッシュを薄板境界稜線に沿って切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより薄板境界頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段と、を有する頂点フィッティング手段と、を備えたことを特徴とする。
請求項１１記載の発明では、請求項１０に記載の３次元形状生成装置において、前記頂点フィッティング手段は、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから薄板境界稜線を検出する手段と、検出された薄板境界稜線から前記薄板境界頂点を検出する手段と、を備えたことを特徴とする。
また、請求項１２記載の発明では、請求項１０に記載の３次元形状生成装置において、
前記頂点フィッティング手段は、前記２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから非多様体稜線を検出する手段と、前記非多様体稜線接続頂点を検出する手段と、を備えたことを特徴とする。
また、請求項１３記載の発明では、請求項１０に記載の３次元形状生成装置において、前記頂点フィッティング手段は、非多様体稜線接続頂点を挟んで直交する２本の一般稜線を選択し、選択された２本の一般稜線に沿って前記非多様体稜線接続頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体稜線接続頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段を備えたことを特徴とする。
また、請求項１４記載の発明では、請求項１０に記載の３次元形状生成装置において、前記頂点フィッティング手段は、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから非多様体頂点を検出する手段を備えたことを特徴とする。
また、請求項１５記載の発明では、請求項１０に記載の３次元形状生成装置において、前記頂点フィッティング手段は、非多様体頂点を挟んで直交する稜線２本を１組とする稜線の組を複数組選択し、選択された複数組の稜線の各組の稜線に沿って前記非多様体頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体頂点を移動し、その移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段を備えたことを特徴とする。
また、請求項１６記載の発明では、請求項１０に記載の３次元形状生成装置において、
前記頂点フィッティング手段は、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから面構成パターンを選択する手段と、選択された面構成パターン毎に新たに頂点と稜線を生成する手段と、を備え、新たに生成した頂点を距離画像メッシュ上にのるまで移動することにより、前記一般頂点を移動することを特徴とする。
また、請求項１７記載の発明では、請求項１０乃至請求項１６のいずれか１項に記載の３次元形状生成装置において、前記頂点フィッティング手段は、頂点に隣接する基本３角形メッシュの平均法線ベクトルを計算し、求まった平均法線ベクトルから対角線ベクトルを取得し、対角線ベクトルに沿って距離画像メッシュと交差するまで頂点を移動させることにより前記頂点を距離画像メッシュ上にのるまで移動することを特徴とする。
【０００６】
【発明の実施の形態】
以下、図面により本発明の実施の形態を詳細に説明する。
図31は本発明の一実施例を示す３次元形状処理装置のハードウェアの構成ブロック図である。図示したように、この実施例の３次元形状処理装置は、プログラムに従って装置全体を制御したり本発明に係わる処理を含む３次元形状処理を行ったりするＣＰＵ１、プログラムやデータを一時的に記憶するメモリ２、プログラムや３次元形状データなど各種データを記憶しておく外部記憶装置３、マウスやキーボードなどを有して、３次元形状モデルやそれを構成している形状要素を指定したり、形状生成や形状変形のための入力を行なったりする入力装置４、グラフィックスディスプレイにより構成され、３次元形状モデルなどを表示する表示装置５などを備えている。
このようなハードウェアとプログラムを用いて、本発明の３次元形状処理システムでは、距離画像から３角形メッシュを生成する３次元形状生成方法において、輪郭・内部・外部の３つの属性値のいずれかを持つ個々のボクセルから成るボリュームモデルを距離画像から生成し、隣接する複数ボクセルの前記属性値の組み合わせを用いて基本３角形メッシュを生成し、生成された基本３角形メッシュから多様体頂点を検出してフィッティング処理を行う。なお、前記距離画像は撮影位置を視点とした透視投影または平行投影によった画像であり、距離画像を構成している各画素（背景とは区別される画像部分を構成している最小単位）は属性値として撮影位置からの距離情報を持っている。また、フィッティング処理とは、実物の形状に近づける処理である。
【０００７】
以下、図１に示す動作フローに先立って準備しておくこと、および前提条件を示す。
（１）図２に示すような３角形面生成パターンに基づいた３角形を生成する情報へのポインタおよび回転情報（後述）を３角形生成ルックアップテーブルに予め格納しておく。そのルックアップテーブルには、図３に示すような隣接する８つのボクセルの属性値の組み合わせをアドレスとしてアクセスする。図３の例で言えば、「０１０１１１１１」（図３に示したV0がビット０に相当するので前記ビット列は図３とは左右が逆になっている）という１バイトのアドレスでルックアップテーブルにアクセスするのである。なお、ボクセルとは、当該３次元形状モデルの境界箱（バウンディングボックス）をｘ，ｙ，ｚ方向に細分割して生成した個々の直方体のことであり、個々のボクセルはそれが当該３次元形状モデルの内部にあるか、輪郭位置にあるか、外部にあるかにより、内部ボクセル、輪郭ボクセル、外部ボクセルのいずれかを示す情報を属性値として持つ。また、図２および図３では８つのボクセルをそれぞれの中心点を示す白丸または黒丸で示している（図４参照）。白丸は外部ボクセル、黒丸は内部または輪郭ボクセルである。また、８つの中心点を結んでできる直方体をキューブと称する。隣接するキューブはいずれの方向も例えば４ボクセル重複して抽出した８ボクセルである。また、図２において、外部ボクセルの中心点（外部点）に結ばれる３角形面生成パターンがないのは、外部点が輪郭を形成する３角形面の外にあるからである。
（２）本発明で用いる前記ルックアップテーブルには、面を生成する場所を示す情報である図５に示すような３角形生成情報（面生成情報）を予め格納しておく（ポインタを格納しておいてもよい）。なお、図５には、３角形生成情報を６面（F0~F5）に対応付けて６ビットで示しているが、実際には例えば１バイトを用いて表現する。
（３）本発明で用いる距離画像は、各画素毎に奥行き方向（撮影位置から被写体に向かう方向）の距離情報（撮影位置からの距離を示す）、カメラ位置、カメラ撮影方向、視野角などの撮影情報を持つ。つまり、各画素毎に、透視変換を用いて容易に３次元空間上の座標値に変換できるものとする。
（４）本発明で用いるボリュームモデルでは、予め各方向のサイズ（各方向のボクセルの個数） Nx, Ny, Nz（すべて正の整数）を決めておく。しかし、必要に応じて利用者が利用前にサイズを指定することも可能とする。サイズを大きくすれば、それだけ細かな解像度の３角形メッシュを得ることができる。但し、Nx,×Ny,×Nzに比例した大きさの作業用メモリ空間が必要になる。
【０００８】
以下、図１に示す動作フローに従って、この実施例の動作の概要を説明する。
まず、３次元測定器を用いて取得した距離画像データから輪郭・内部・外部の３つの属性値のいずれかを持つボクセルから構成されるボリュームモデルを生成する（距離画像ボリューム生成ステップ）（Ｓ１）。
続いて、ボリュームモデル中のボクセルの位置を順次ずらしながら隣接する８ボクセルの属性値の組み合わせ値を取得し、その値のアドレスに記憶されている３角形生成情報を用いて基本３角形メッシュを生成する（基本メッシュ生成ステップ）（Ｓ２）。
そして、基本３角形メッシュから対応する面構成パターンを抽出し、その面構成パターンを用いて基本３角形メッシュの頂点を移動させ、その頂点移動に従って基本３角形メッシュを変形するフィッティング処理を行う（頂点フィッティングステップ）（Ｓ３）。
次に、図６に示す動作フロー図に従って、前記距離画像ボリューム生成ステップ（Ｓ１）について説明する。
まず、距離画像の画素を頂点とする距離画像メッシュを生成する（Ｓ11）。距離画像の各画素が規則的に配置されている場合には隣接情報が得られるので、隣接した３画素を頂点とする３角形を生成することにより距離画像メッシュを生成するのである。距離画像の各画素が不規則に配置されている場合には、距離画像の各画素の座標値に対してドロネ３角形分割（参考文献［５］）を用いることにより距離画像メッシュを生成する。なお、異なる方向から撮影されている複数枚の距離画像データがあれば、各距離画像データ毎に距離画像メッシュを生成する。
続いて、距離画像メッシュから、境界箱を生成し、その境界箱を細分して境界箱が複数のボクセルからなる構成とし、とりあえず、すべてのボクセルを内部ボクセルとした初期ボリュームモデルを生成する（内部ボクセル生成ステップ）（初期ボリューム生成）（Ｓ12）。
そして、前記ボリュームモデルから輪郭ボクセルを検出し（後述）、そのボクセルに輪郭ボクセルであることを示す属性情報を設定する（輪郭ボクセル生成ステップ）（Ｓ13）。
さらに、そのボリュームモデルから外部ボクセルを検出し（後述）、そのボクセルに外部ボクセルであることを示す属性情報を設定する（外部ボクセル生成ステップ）（Ｓ14）。
【０００９】
次に、図７に示す動作フロー図に従って、前記内部ボクセル生成ステップ（Ｓ12）について説明する。
まず、距離画像メッシュの頂点座標をすべて含む境界箱（バウンディングボックス）を求める（Ｓ121）。境界箱は、各頂点座標の３次元座標(X,Y,Z)の各要素X,Y,Z毎に最大値Xmin, Ymin, Zmin、最小値Xmax, Ymax, Zmaxを求め、その最大値、最小値を次のように組み合わせた８座標B1〜B8を頂点とする直方体として求める。
B1:(Xmin,Ymin,Zmin), B2:(Xmax,Ymin,Zmin), B3:(Xmin,Ymax,Zmin), B4:(Xmax,Ymax,Zmin), B5:(Xmin,Ymin,Zmax), B6:(Xmax,Ymin,Zmax), B7:(Xmin,Ymax,Zmax), B8:(Xmax,Ymax,Zmax)
続いて、境界箱の各頂点に、次に示すように定数δを加えるか減ずることにより、境界箱を拡大する（Ｓ122）。δは、各画素が境界箱の表面に分布し、微妙な境界判断の問題を起こさないようにするための、正の小さな数である。
B1:(Xmin−δ,Ymin−δ,Zmin−δ), B2:(Xmax+δ,Ymin−δ,Zmin−δ), B3:(Xmin−δ,Ymax +δ,Zmin−δ), B4:(Xmax+δ,Ymax+δ,Zmin−δ), B5:(Xmin−δ,Ymin−δ,Zmax+δ), B6:(Xmax+δ,Ymin−δ,Zmax+δ), B7:(Xmin−δ,Ymax+δ,Zmax+δ), B8:(Xmax+δ,Ymax+δ,Zmax+δ)
そして、境界箱の頂点B1をボリュームモデルの原点とし、境界箱を予め決められたサイズ（個数）Nx,Ny,Nzにより分割して生成されたボクセルにより構成されるボリュームモデルを作成する（Ｓ123）。
さらに、ボクセルの初期属性値をすべて内部ボクセルに設定する（Ｓ124）。
【００１０】
次に、図８に示す動作フロー図に従って、前記輪郭ボクセル生成ステップ（Ｓ13）について説明する。
まず、距離画像メッシュの各頂点の３次元座標(X,Y,Z)が含まれるボクセルに輪郭ボクセル属性を設定する（Ｓ131）。次に示す(1)式を用いて各頂点の座標(X,Y,Z)が含まれているボクセルを検出し、検出したボクセルに輪郭ボクセル属性を設定するのである。
(Xi,Yi,Zi)=( (X−Xmin) /Nx, (Y−Ymin)/ Ny, (Z−Zmin)/ Nz)     (1)
ここで、 (Xi,Yi,Zi)はボクセルのアドレス（番号）で各要素の小数点以下は切り捨てられ、整数に丸められる。
続いて、距離画像メッシュの３角形毎に、その頂点が含まれる最大で３つのボクセルを(1)式により探し、３つのボクセルを含む境界箱に相当する、次のように定義されるボクセルアドレス(X,Y,Z)の範囲に存在するボクセル空間を求める（Ｓ132）。
min(X1,X2,X3) ≦X≦ max(X1,X2,X3),
min(Y1,Y2,Y3) ≦Y≦ max(Y1,Y2,Y3),
min(Z1,Z2,Z3) ≦Z≦ max(Z1,Z2,Z3).
ここで、(X1,Y1,Z1),(X2,Y2,Z2),(X3,Y3,Z3)は３角形の頂点が含まれる３つのボクセルアドレスとする。
さらに、前記のような各ボクセル空間に含まれる各ボクセルについて距離画像メッシュの各３角形との交差チェックを行い、交差したボクセルを輪郭ボクセルとする（Ｓ133）。なお、計算コスト節約のため、既にステップＳ131で輪郭ボクセルと判定されているものについては、交差チェックを行わない。
【００１１】
次に、図９に示す動作フロー図に従って、前記外部ボクセル生成ステップ（Ｓ14）について説明する。
まず、距離画像の撮影位置から距離画像メッシュの各３角形面に至る空間から成る角錐状の複数の視点ボリューム空間（平行投影の場合は角柱状のボリューム空間）を作成する（Ｓ141）。
続いて、各視点ボリューム空間とボリュームモデルの交差チェックを行い、交差したボクセルに外部ボクセル属性を設定する（Ｓ142）。計算コスト節約のため、既に外部ボクセルと判定されたものや、ステップＳ131およびステップＳ133で輪郭ボクセルと判定されているものについては、交差チェックを行わずにそのままにしておく。
こうして、輪郭ボクセルでも外部ボクセルでもないボクセルが最終的な内部ボクセルとされるのであるが、そうすると、視点ボリューム空間と交わらない輪郭ボクセルの外側のボクセルがあった場合には、そのボクセルも内部ボクセルになってしまう。そのため、距離画像はあらゆる方向から撮影したものを用意して、被写体の外側はすべて視点ボリューム空間と交わるようにする。
【００１２】
次に、図10に示す動作フロー図に従って前記基本メッシュ生成ステップ（Ｓ２）について説明する。
まず、ルックアップテーブル内の、隣接する８ボクセルの属性値の組み合わせから成るアドレスから回転情報と３角形生成情報を取得する（Ｓ21）。あるいは、ルックアップテーブルに記憶されたポインタを取得し、そのポインティング先からそれらを取得してもよい。３角形生成情報は回転情報に従った回転変換分を一つにまとめることにより、前記図２に示したようにまとめられている。回転情報は、図11に示すように、X,Y,Z各軸まわりに90度の回転を１回とする回転回数を (Rx,Ry,Rz) と定義したもので、それぞれ0以上の整数である。なお、図11はX軸まわりに90度の回転を１回行なった例である。図11において、キューブの下に示した白丸および黒丸は図３と同様な意味である。
続いて、回転情報(Rx,Ry,Rz)により８ボクセル（キューブ）を回転変換させる（Ｓ22）。アドレッシング先に８ボクセルのアドレスを格納した領域を用意しておき、回転変換を行うのである。例えば、図11に示した例で言えば、ルックアップテーブルには、(b)図に示した組み合わせのアドレス情報「１１１１１１００」に対応付けて回転情報(1,0,0)および(a)図のアドレス「１１００１１１１」を格納しておき、アドレス「１１００１１１１」を得ることにより(a)図の３角形生成パターンを取得し、それをX軸まわりに90度回転させて(b)図の３角形生成パターンを得る。
さらに、回転変換させた８ボクセルと３角形生成情報を用いて基本３角形メッシュを生成する（Ｓ23）。輪郭ボクセルの中心点の座標を取得し、その中心点を３角形メッシュの頂点とする３角形を作成するのである。例えば図11の例では４個の基本３角形メッシュが作成される。なお、図２や図11に示した基本３角形メッシュの各太線は３次元形状モデルの稜線となる。
こうして、対象としているボリュームモデル全体について基本３角形メッシュが求まると、図１に示した頂点フィッティング（Ｓ３）では、例えば図12に示したような基本３角形メッシュの頂点（黒丸で図示した点）を移動させて基本３角形メッシュを変形させることにより、基本３角形メッシュの面を実際の輪郭面に近づける。以下、図13に示した動作フローに基づいて、図１に示した頂点フィッティングステップＳ３における基本３角形メッシュの頂点フィッティング方法の概要を説明する。後述するように、この実施例では、基本３角形メッシュの頂点の種類により、異なった移動方法で頂点を移動させるのが特徴である。これにより、実際の３次元形状が例えば１ボクセルの大きさにも満たない薄板のような場合でも実際に近い３次元形状を生成することができるのである。
【００１３】
図13に示したように、まず、対象としているボリュームモデル中から薄板境界頂点を検出する（Ｓ31）。そして、その薄板境界頂点を実際の３次元形状に近くなる方向へ移動する（Ｓ32）。なお、薄板とは、２つの基本３角形メッシュの組から成る４角形面が背中合わせに、すきまなく密着して存在する場合に当たり、実際の３次元形状が１ボクセルにも満たない厚さのものを言う。薄板の例を図15に示す。図15において、黒丸が薄板境界頂点である。薄板境界については後述する。
次に、非多様体稜線接続頂点を検出し（Ｓ33）、前記薄板境界頂点の場合とは違った方法でその非多様体稜線接続頂点を移動する（Ｓ34）。
続いて、非多様体頂点を検出し（Ｓ35）、非多様体頂点を移動し（Ｓ36）、さらに、一般頂点を移動する（Ｓ37）。
【００１４】
次に、図14に示した動作フローに従って、図13のステップＳ31に示した薄板境界頂点の検出方法を説明する。
まず、各頂点に隣接する２つの基本３角形メッシュの組から成る４角形面を検出し、４角形面の配置情報である４角形面配置フラグを取得する（Ｓ311）。図16に示したように、各頂点のまわりには24種類の４角形面が存在する可能性があるので、４角形面の配置情報は24bitの４角形面配置フラグで表している。４角形面配置フラグの最下位bitから最上位bitまで順にR0からR23とする。Riが１であればi番目の４角形面は存在し、Riが０であればi番目の４角形面は存在しない。このような４角形面配置フラグを図１に示したステップＳ２の基本３角形メッシュ生成時に作成しておくのである。
続いて、４角形面の有無の組み合わせから薄板の配置情報、つまり薄板の有無を求める（Ｓ312）。図17に示したように、各頂点のまわりには12種類の薄板が存在する可能性があるので、薄板の配置情報は12bitの薄板配置フラグで表す。薄板配置フラグの最下位bitから最上位bitまで順にL0からL11とする。Liが１であればi番目の薄板は存在し、Liが０であればi番目の薄板は存在しない。そのような薄板配置フラグの各bitを次のように４角形面配置フラグのbitの論理積(&)を用いて計算する。つまり、前記４角形面が両面にあれば１とするのである。
L0=R0 & R5,  L1=R1 & R4,  L2=R2 & R7,  L3=R3 & R6,
L4=R8 & R13,  L5=R9 & R12,  L6=R10 & R15, L7=R11 & R14,
L8=R17 & R20, L9=R16 & R21, L10=R19 & R22, L11=R18 & R23
【００１５】
次に、面の有無を求める（Ｓ313）。図17に示した薄板の場合と同じ配置情報を使用して、12bitの面存在フラグで表す。薄板配置フラグと同様に、最下位bitから最上位bitまで順にN0からN11とする。Niが１であればi番目の場所に面は存在し、Niが０であればi番目の場所に面は存在しない。そのような面存在フラグの各bitを次のように４角形面配置フラグのbitの論理和( | )を用いて計算する。つまり、背中合わせの両側のうち、少なくとも一方に４角形面があれば１とするのである。
N0=R0 | R5,  N1=R1 | R4,  N2=R2 | R7,  N3=R3 | R6,
N4=R8 | R13,  N5=R9 | R12,  N6=R10 | R15, N7=R11 | R14,
N8=R17 | R20, N9=R16 | R21, N10=R19 | R22, N11=R18 | R23
さらに、薄板の組み合わせにより薄板境界稜線を求める（Ｓ314）。なお、薄板境界稜線とは、薄板の境界を成す稜線、つまり、薄板を成す２つの４角形面によってのみ共有される稜線である。頂点のまわりには最大６本の稜線が存在するので、図18に示したように薄板境界稜線の配置情報を６bitの稜線配置フラグによって表す。フラグの最下位bitから最上位bitまで、順にBE0からBE5とする。BEiが１であればその場所に稜線は存在し、BEiが０であればその場所に稜線は存在しない。薄板境界稜線の稜線配置フラグの各bitは、次のように、薄板配置フラグ、面存在フラグの論理積(&)、論理和( | )、否定( ! )を用いて計算される。当該頂点のまわりに薄板境界稜線が１本でも存在すれば、その頂点は薄板境界頂点と判断する。
BE0=(L0 & (!N1 & !N4 & !N6)) | (L1 & (!N0 & !N4 & !N6))
| (L4 & (!N0 & !N1 & !N6)) | (L6 & (!N0 & !N1 & !N4)),
BE1=(L0 & (!N2 & !N8 & !N10)) | (L2 & (!N0 & !N8 & !N10))
| (L8 & (!N0 & !N2 & !N10)) | (L10 & (!N0 & !N2 & !N8)),
BE2=(L0 & (!N1 & !N4 & !N6)) | (L1 & (!N0 & !N4 & !N6))
| (L4 & (!N0 & !N1 & !N6)) | (L6 & (!N0 & !N1 & !N4)),
BE3=(L0 & (!N1 & !N4 & !N6)) | (L1 & (!N0 & !N4 & !N6))
| (L4 & (!N0 & !N1 & !N6)) | (L6 & (!N0 & !N1 & !N4)),
BE4=(L0 & (!N1 & !N4 & !N6)) | (L1 & (!N0 & !N4 & !N6))
| (L4 & (!N0 & !N1 & !N6)) | (L6 & (!N0 & !N1 & !N4)),
BE5=(L0 & (!N1 & !N4 & !N6)) | (L1 & (!N0 & !N4 & !N6))
| (L4 & (!N0 & !N1 & !N6)) | (L6 & (!N0 & !N1 & !N4))
【００１６】
次に、図19に示した動作フローに従って、図13のステップＳ32に示した薄板境界頂点の移動方法を説明する。
まず、前記薄板境界頂点まわりの基本３角形メッシュを薄板境界稜線に沿って切り離す（カットする）（Ｓ321）。図21(a),(b)に示したように、薄板境界頂点および薄板境界稜線を位相的に複製し、別の要素として分離するのである。
続いて、切り離すことにより生成された複数の頂点を図21(a)に矢印で示した方向に（この方向の詳細については後述する）距離画像メッシュ上にのるまで移動する（Ｓ322）。そして、そのような頂点の移動により生成された、基本３角形メッシュのすきまに新たに３角形面を生成する（Ｓ323）。つまり、まず、複製した薄板境界稜線を２辺とする３角形（図21(c)の太線で囲まれた４つの３角形）を生成し、図示の場合のように薄板境界稜線が３本より多い場合には、まだ多角形領域のすきまが残るので、その多角形領域を複数の３角形（図21(d)において太線で囲まれた２つの３角形）に分割することにより穴埋めを行うのである。
こうして、基本３角形メッシュの面は実際の面により近くなる。頂点移動前の頂点位置はボクセルの中心位置に近似されていたが、移動後の頂点位置は３頂点が実際の位置である距離画像メッシュ上の点であるので、実際の位置に極めて近いのである。また、面数を増やして基本３角形メッシュ間を補完したことも実際の面に近づける効果をもたらしている。
次に、図20に示した動作フローに従って、図13のステップＳ33に示した非多様体稜線接続頂点検出について説明する。
まず、２つの基本３角形メッシュの組から成る４角形面を検出し、４角形面の配置情報である４角形面配置フラグを取得する（Ｓ331）。そして、４角形面の組み合わせから非多様体稜線を検出する（Ｓ332）。なお、非多様体稜線とは、３つ以上の面により共有されている稜線であり、回転変換により同じになるものを除くと、非多様体稜線を含む４角形面の組み合わせは図22(a),(b)の２つになる。各頂点について４角形面配置フラグを格納したテーブルを用意しておき、そのようなテーブルを探索して、各頂点について図22(a),(b)に示したような非多様体稜線を含むか否かを調べ、非多様体稜線が１つでも検出されたならば、その頂点を非多様体稜線接続頂点とするのである。
【００１７】
次に、図23に示した動作フローに従って、図13のステップＳ34に示した非多様体稜線接続頂点の移動方法を説明する。
まず、非多様体稜線接続頂点を挟んで直交する２本の一般稜線（図24(a),(d)の太線）を選択する（Ｓ341）。そして、その２本の一般稜線に沿ってその頂点まわりの基本３角形メッシュを切り離す（カットする）（Ｓ342）。
続いて、この切り離しにより生成された複数の頂点を矢印方向へ（詳細は後述）距離画像メッシュ上にのるまで移動する（図24(a), (b),(d),(e)参照）（Ｓ343）。そして、その頂点の移動により生成された、基本３角形メッシュのすきまに新たに３角形面を生成する（図24(c),(f)において太線で囲まれた３角形）（Ｓ344）。
こうして、基本３角形メッシュの面は実際の面により近くなる。また、面数を増やして基本３角形メッシュ間を補完したことも実際の面に近づける効果をもたらしている。
次に、図25に示した動作フローに従って、図13のステップＳ35に示した非多様体頂点の検出方法を説明する。なお、非多様体頂点とは、複数の面により頂点のみが共有されている場合におけるその頂点のことである。
まず、２つの基本３角形メッシュの組から成る４角形面を検出し、４角形面配置フラグを取得する（Ｓ351）。そして、４角形面の組み合わせから非多様体頂点を検出する（Ｓ352）。回転変換により同じになるものを除くと、非多様体頂点を含む４角形面の組み合わせは図22(c)に示したもの１つになるので、各頂点について４角形面配置フラグを格納したテーブルを用意しておき、そのようなテーブルを探索して、各頂点について、複数の面により当該頂点のみが共有されている図22(c)のような４角形面の組み合わせの有無を調べ、そのような組み合わせがあれば、その頂点を非多様体頂点とするのである。
【００１８】
次に、図26に示した動作フローに従って、図13のステップＳ36に示した非多様体頂点の移動方法を説明する。
まず、非多様体頂点を挟んで直交する２本の稜線を１組とする稜線の組を３組（図27(a)の太線）選択する（２組でもよい）（Ｓ361）。そして、３組の稜線の各組の稜線に沿ってその非多様体頂点のまわりの複数の基本３角形メッシュを切り離す（カットする）（Ｓ362）。
続いて、この切り離しにより生成された複数の頂点を距離画像メッシュ上にのるまで移動する（図27(b)参照）（Ｓ363）。そして、そのような頂点移動により生成された、前記基本３角形メッシュのすきまに新たに３角形面（図27(c)の太線で囲まれた３角形）を生成する（Ｓ364）。
こうして、基本３角形メッシュの面は実際の面により近くなる。また、面数を増やして基本３角形メッシュ間を補完したことも実際の面に近づける効果をもたらしている。
次に、図28に示した動作フローに従って、図13のステップＳ37に示した一般頂点の移動方法を説明する。
まず、各頂点まわりについて、２つの基本３角形メッシュの組から成る４角形面を検出し、４角形面の配置情報である４角形面配置フラグを取得する（Ｓ371）。そして、これまで説明してきた各種頂点以外の一般頂点（２つの面により共有される稜線が接続する頂点など）を抽出し、その一般頂点まわりの４角形面の組み合わせから面構成パターンを選択する（Ｓ372）。回転変換により同じになるものを除くと、そのような４角形面の組み合わせは図12に示した10通りになるので、各頂点について４角形面配置フラグを格納したテーブルを用意しておき、そのようなテーブルを探索して、各頂点について、図12に示したような合致する面構成パターンを求めるのである。
続いて、頂点まわりの複数の基本３角形メッシュを切り離して（カットして）面構成パターン毎に新たに頂点と稜線を生成（複製）する（Ｓ373）。ステップＳ372において抽出した面構成パターンが、ひとつの頂点に対して複数存在する場合があるので、その場合に、頂点と接続する稜線とを複製することにより位相的に分離するのである。
さらに、もとの頂点および新たに生成した頂点を距離画像メッシュ上にのるまで移動する（Ｓ374）。
こうして、基本３角形メッシュの面は実際の面により近くなる。
【００１９】
次に、図29に示した動作フローに従って、前記した各頂点移動の際の移動方向などについて説明する。
まず、当該頂点まわりの基本３角形メッシュの平均法線ベクトルを計算する（Ｓ41）。そして、方向が平均法線ベクトルの逆方向に最も近い対角線ベクトルを求める（Ｓ42）。なお、対角線ベクトルとは、当該頂点を含む隣接８ボクセルにおいて、当該頂点と対角位置のボクセルの頂点とを結んだもの（図30(a)参照）、当該頂点に接続するいずれかの稜線の中点とその対角位置の稜線の中点とを結んだもの（図30(b)参照）、当該頂点を含むいずれかの面の中点とその対向面の中点とを結んだもの（図30(c)参照）である。
続いて、求まった対角線ベクトルが距離画像メッシュと交差する交点を求め、前記各動作フローにおいて示した各種頂点をその交点まで移動させる（Ｓ43）。
また、その際、距離画像メッシュとの交点が求まらなければ、方向が平均法線ベクトルの逆方向に次に近い対角線ベクトルを選んで前記交点を求め、いずれの対角線ベクトルも交点を持たない場合には、対角線ベクトルの始点から最も距離が近い距離画像メッシュ上の点を頂点移動先とする。なお、前記において、もとの頂点を単純に平均法線ベクトルの逆方向に移動させて距離画像メッシュにのる点を移動先としないのは、薄板などの場合には、ボクセルの中心としての頂点が実際の薄板の表面からずれてしまっていて距離画像メッシュにのらない可能性が大であるからである。
以上、本発明の３次元形状生成方法について説明してきたが、説明したような３次元形状生成方法を実施するためのプログラムを例えば着脱可能な記憶媒体に記憶させ、その記憶媒体をこれまで本発明によった３次元形状生成を行えなかったパーソナルコンピュータなど情報処理装置に装着することにより、その情報処理装置において本発明によった３次元形状生成を行うこともできる。
参考文献
［１］William E. Lorensen and Harvey E. Cline: "Marching Cubes: A High Resolution 3D Surface Construction Algorithm", SIGGRAPH'87  Proceedings, pp.163-169, Jul 1987.
［２］Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald and Werner Stuetzle: "Surface reconstruction from unorganized points", SIGGRAPH '92 Proceedings, pp.71-78, Jul 1992.
［３］Brian Curless and Marc Levoy: "A Volumetric Method for Building Complex Models from Range Images", SIGGRAPH'96 Proceedings, pp.303-312, Aug 1996.
［４］松岡、植田、早野：「格子点連結法と局所操作を用いた点群データからのソリッドモデル自動再構成」、情報処理学会論文誌、vol.40, No.5, 1999年。
［５］Jean-Daniel Boissonnat: "Geometric structures for three-dimentional shape representation", ACM Transactions on Graphics, Vol.3, No.4, Oct 1984, pp.266-286.
【００２０】
【発明の効果】
以上説明したように、請求項１、１０記載の本発明によれば、３次元測定器などで測定することにより得られる距離画像から３角形メッシュを生成する際に、角張った形状の鋭角の稜線、特に凹部分の鋭角稜線が失われるという問題、格子間隔以下の薄い形状と細い形状が失われるという問題、格子位置により形状が変化してしまうという問題などを解消できる。また基本３角形メッシュを実際の輪郭面に、より適切に近づけることができる。
また、請求項２、１１記載の発明によれば、薄板境界頂点の検出を容易に実現することができる。
【００２１】
また、請求項３、１２記載の発明によれば、非多様体稜線接続頂点の検出を容易に実現することができる。
また、請求項４、１３記載の発明によれば、非多様体稜線接続頂点を有した３次元形状であっても、基本３角形メッシュを実際の輪郭面に適切に近づけることができ、したがって、角張った形状の鋭角の稜線、特に凹部分の鋭角稜線が失われるという問題、格子間隔以下の薄い形状と細い形状が失われるという問題、格子位置により形状が変化してしまうという問題などを解消できる。
また、請求項５、１４記載の発明によれば、非多様体頂点の検出を容易に実現することができる。
また、請求項６、１５記載の発明によれば、非多様体頂点を有した３次元形状であっても、基本３角形メッシュを実際の輪郭面に適切に近づけることができ、したがって、角張った形状の鋭角の稜線、特に凹部分の鋭角稜線が失われるという問題、格子間隔以下の薄い形状と細い形状が失われるという問題、格子位置により形状が変化してしまうという問題などを解消できる。
【００２２】
また、請求項７、１６記載の発明によれば、各種頂点のなかに一般頂点が混在した３次元形状であっても、基本３角形メッシュを実際の輪郭面に適切に近づけることができ、したがって、角張った形状の鋭角の稜線、特に凹部分の鋭角稜線が失われるという問題、格子間隔以下の薄い形状と細い形状が失われるという問題、格子位置により形状が変化してしまうという問題などを解消できる。
また、請求項８、１７記載の発明によれば、例えば薄板などの場合に、頂点移動の際、ボクセルの中心としての頂点が実際の薄板の表面からずれてしまっていて距離画像メッシュにのらないという事態を避けることができる。
また、請求項９記載の発明によれば、本発明の記憶媒体をパーソナルコンピュータなど情報処理装置に装着することにより、その情報処理装置においても請求項１乃至請求項８の何れかに記載の発明の効果を実現することができる。
【図面の簡単な説明】
【図１】本発明の一実施例を示す３次元形状生成方法の動作フロー図である。
【図２】本発明の一実施例を示す３次元形状生成方法の説明図である。
【図３】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図４】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図５】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図６】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図７】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図８】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図９】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図１０】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図１１】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図１２】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図１３】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図１４】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図１５】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図１６】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図１７】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図１８】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図１９】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図２０】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図２１】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図２２】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図２３】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図２４】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図２５】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図２６】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図２７】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図２８】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図２９】本発明の一実施例を示す３次元形状生成方法の他の動作フロー図である。
【図３０】本発明の一実施例を示す３次元形状生成方法の他の説明図である。
【図３１】本発明の一実施例を示す３次元形状処理装置のハードウェアの構成ブロック図である。
【図３２】従来技術の一例を示す３次元形状生成方法の説明図である。
【符号の説明】
１  ＣＰＵ
２  メモリ
３  外部記憶装置
４  入力装置
５  表示装置
【図１】
0004061013.tif 000002
【図２】
0004061013.tif 000003
【図３】
0004061013.tif 000004
【図４】
0004061013.tif 000005
【図５】
0004061013.tif 000006
【図６】
0004061013.tif 000007
【図７】
0004061013.tif 000008
【図８】
0004061013.tif 000009
【図９】
0004061013.tif 000010
【図１０】
0004061013.tif 000011
【図１１】
0004061013.tif 000012
【図１２】
0004061013.tif 000013
【図１３】
0004061013.tif 000014
【図１４】
0004061013.tif 000015
【図１５】
0004061013.tif 000016
【図１６】
0004061013.tif 000017
【図１７】
0004061013.tif 000018
【図１８】
0004061013.tif 000019
【図１９】
0004061013.tif 000020
【図２０】
0004061013.tif 000021
【図２１】
0004061013.tif 000022
【図２２】
0004061013.tif 000023
【図２３】
0004061013.tif 000024
【図２４】
0004061013.tif 000025
【図２５】
0004061013.tif 000026
【図２６】
0004061013.tif 000027
【図２７】
0004061013.tif 000028
【図２８】
0004061013.tif 000029
【図２９】
0004061013.tif 000030
【図３０】
0004061013.tif 000031
【図３１】
0004061013.tif 000032
【図３２】
0004061013.tif 000033