【手続補正書】
【提出日】平成16年11月5日(2004.11.5)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】３次元形状生成方法、その方法を実施するためのプログラムを記憶した記憶媒体および３次元形状生成装置
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
距離画像から３角形メッシュを生成して３次元形状を生成する３次元形状生成方法において、輪郭・内部・外部の３つの属性値のいずれかを持つ個々のボクセルから成るボリュームモデルを距離画像から生成する工程と、前記ボリュームモデル中のボクセルの位置を順次ずらしながら取得した隣接する複数ボクセルの前記属性値の組み合わせに基づいて基本３角形メッシュを生成する工程と、その基本３角形メッシュの頂点を移動させて３角形メッシュを生成するする工程と、を備えたことを特徴とする３次元形状生成方法。
【請求項２】
請求項１記載の３次元形状生成方法において、基本３角形メッシュの頂点として、薄板境界頂点、非多様体稜線接続頂点、非多様体頂点、および一般頂点のうち、少なくとも２種類以上の頂点を検出し、検出された頂点の種類に応じて異なった頂点移動方法を選択可能にしたことを特徴とする３次元形状生成方法。
【請求項３】
請求項２記載の３次元形状生成方法において、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから薄板境界稜線を検出する工程と、検出された薄板境界稜線から前記薄板境界頂点を検出する工程と、を備えたことを特徴とする３次元形状生成方法。
【請求項４】
請求項２または請求項３記載の３次元形状生成方法において、薄板境界頂点まわりの複数の基本３角形メッシュを薄板境界稜線に沿って切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより薄板境界頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する工程を備えたことを特徴とする３次元形状生成方法。
【請求項５】
請求項２乃至請求項４のいずれか１つの請求項に記載の３次元形状生成方法において、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから非多様体稜線を検出する工程と、前記非多様体稜線接続頂点を検出する工程と、を備えたことを特徴とする３次元形状生成方法。
【請求項６】
請求項２乃至請求項５のいずれか１つの請求項に記載の３次元形状生成方法において、非多様体稜線接続頂点を挟んで直交する２本の一般稜線を選択し、選択された２本の一般稜線に沿って前記非多様体稜線接続頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体稜線接続頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する工程を備えたことを特徴とする３次元形状生成方法。
【請求項７】
請求項２乃至請求項６のいずれか１つの請求項に記載の３次元形状生成方法において、２つの基本３角形メッシュの組から成る４角形面を検出し、検出された４角形面の組み合わせから非多様体頂点を検出する工程を備えたことを特徴とする３次元形状生成方法。
【請求項８】
請求項２乃至請求項７のいずれか１つの請求項に記載の３次元形状生成方法において、非多様体頂点を挟んで直交する稜線２本を１組とする稜線の組を複数組選択し、選択された複数組の稜線の各組の稜線に沿って前記非多様体頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体頂点を移動し、その移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する工程を備えたことを特徴とする３次元形状生成方法。
【請求項９】
請求項２乃至請求項８のいずれか１つの請求項に記載の３次元形状生成方法において、２つの基本３角形メッシュの組から成る４角形面を検出する工程と、検出された４角形面の組み合わせから面構成パターンを選択する工程と、選択された面構成パターン毎に新たに頂点と稜線を生成する工程と、を備え、新たに生成した頂点を距離画像メッシュ上にのるまで移動することにより、前記一般頂点を移動することを特徴とする３次元形状生成方法。
【請求項１０】
請求項２乃至請求項９のいずれか１つの請求項に記載の３次元形状生成方法において、頂点に隣接する基本３角形メッシュの平均法線ベクトルを計算し、求まった平均法線ベクトルから対角線ベクトルを取得し、対角線ベクトルに沿って距離画像メッシュと交差するまで頂点を移動させることにより前記頂点を距離画像メッシュ上にのるまで移動することを特徴とする３次元形状生成方法。
【請求項１１】
プログラムを記憶した記憶媒体において、請求項１乃至請求項１０のいずれか１つの請求項に記載の３次元形状生成方法を実施するためのプログラムを記憶したことを特徴とする記憶媒体。
【請求項１２】
距離画像から３角形メッシュを生成して３次元形状を生成する３次元形状生成装置において、輪郭・内部・外部の３つの属性値のいずれかを持つ個々のボクセルから成るボリュームモデルを距離画像から生成する手段と、前記ボリュームモデル中のボクセルの位置を順次ずらしながら取得した隣接する複数ボクセルの前記属性値の組み合わせに基づいて基本３角形メッシュを生成する手段と、その基本３角形メッシュの頂点を移動させて３角形メッシュを生成するする手段と、を備えたことを特徴とする３次元形状生成装置。
【請求項１３】
請求項１２記載の３次元形状生成装置において、基本３角形メッシュの頂点として、薄板境界頂点、非多様体稜線接続頂点、非多様体頂点、および一般頂点のうち、少なくとも２種類以上の頂点を検出し、検出された頂点の種類に応じて異なった頂点移動方法を選択可能にしたことを特徴とする３次元形状生成装置。
【請求項１４】
請求項１３記載の３次元形状生成装置において、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから薄板境界稜線を検出する手段と、検出された薄板境界稜線から前記薄板境界頂点を検出する手段と、を備えたことを特徴とする３次元形状生成装置。
【請求項１５】
請求項１３または請求項１４記載の３次元形状生成装置において、薄板境界頂点まわりの複数の基本３角形メッシュを薄板境界稜線に沿って切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより薄板境界頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段を備えたことを特徴とする３次元形状生成装置。
【請求項１６】
請求項１３乃至請求項１５のいずれか１つの請求項に記載の３次元形状生成装置において、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから非多様体稜線を検出する手段と、前記非多様体稜線接続頂点を検出する手段と、を備えたことを特徴とする３次元形状生成装置。
【請求項１７】
請求項１３乃至請求項１６のいずれか１つの請求項に記載の３次元形状生成装置において、非多様体稜線接続頂点を挟んで直交する２本の一般稜線を選択し、選択された２本の一般稜線に沿って前記非多様体稜線接続頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体稜線接続頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段を備えたことを特徴とする３次元形状生成装置。
【請求項１８】
請求項１３乃至請求項１７のいずれか１つの請求項に記載の３次元形状生成装置において、２つの基本３角形メッシュの組から成る４角形面を検出し、検出された４角形面の組み合わせから非多様体頂点を検出する手段を備えたことを特徴とする３次元形状生成装置。
【請求項１９】
請求項１３乃至請求項１８のいずれか１つの請求項に記載の３次元形状生成装置において、非多様体頂点を挟んで直交する稜線２本を１組とする稜線の組を複数組選択し、選択された複数組の稜線の各組の稜線に沿って前記非多様体頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体頂点を移動し、その移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段を備えたことを特徴とする３次元形状生成装置。
【請求項２０】
請求項１３乃至請求項１９のいずれか１つの請求項に記載の３次元形状生成装置において、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから面構成パターンを選択する手段と、選択された面構成パターン毎に新たに頂点と稜線を生成する手段と、を備え、新たに生成した頂点を距離画像メッシュ上にのるまで移動することにより、前記一般頂点を移動することを特徴とする３次元形状生成装置。
【請求項２１】
請求項１３乃至請求項２０のいずれか１つの請求項に記載の３次元形状生成装置において、頂点に隣接する基本３角形メッシュの平均法線ベクトルを計算し、求まった平均法線ベクトルから対角線ベクトルを取得し、対角線ベクトルに沿って距離画像メッシュと交差するまで頂点を移動させることにより前記頂点を距離画像メッシュ上にのるまで移動することを特徴とする３次元形状生成装置。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
また、請求項５記載の発明では、請求項２乃至請求項４のいずれか１つの請求項に記載の３次元形状生成方法において、２つの基本３角形メッシュの組から成る４角形面を検出し、検出された４角形面の組み合わせから非多様体稜線を検出することにより、前記非多様体稜線接続頂点を検出した。
また、請求項６記載の発明では、請求項２乃至請求項５のいずれか１つの請求項に記載の３次元形状生成方法において、非多様体稜線接続頂点を挟んで直交する２本の一般稜線を選択し、選択された２本の一般稜線に沿って前記非多様体稜線接続頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体稜線接続頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成した。
また、請求項７記載の発明では、請求項２乃至請求項６のいずれか１つの請求項に記載の３次元形状生成方法において、２つの基本３角形メッシュの組から成る４角形面を検出し、検出された４角形面の組み合わせから非多様体頂点を検出した。
また、請求項８記載の発明では、請求項２乃至請求項７のいずれか１つの請求項に記載の３次元形状生成方法において、非多様体頂点を挟んで直交する稜線２本を１組とする稜線の組を複数組選択し、選択された複数組の稜線の各組の稜線に沿って前記非多様体頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体頂点を移動し、その移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成した。
また、請求項９記載の発明では、請求項２乃至請求項８のいずれか１つの請求項に記載の３次元形状生成方法において、２つの基本３角形メッシュの組から成る４角形面を検出し、検出された４角形面の組み合わせから面構成パターンを選択し、選択された面構成パターン毎に新たに頂点と稜線を生成し、新たに生成した頂点を距離画像メッシュ上にのるまで移動することにより、前記一般頂点を移動した。
また、請求項１０記載の発明では、請求項２乃至請求項９のいずれか１つの請求項に記載の３次元形状生成方法において、頂点に隣接する基本３角形メッシュの平均法線ベクトルを計算し、求まった平均法線ベクトルから対角線ベクトルを取得し、対角線ベクトルに沿って距離画像メッシュと交差するまで頂点を移動させることにより前記頂点を距離画像メッシュ上にのるまで移動した。
また、請求項１１記載の発明では、プログラムを記憶した記憶媒体において、請求項１乃至請求項１０のいずれか１つの請求項に記載の３次元形状生成方法を実施するためのプログラムを記憶した。
また、請求項１２記載の発明では、距離画像から３角形メッシュを生成して３次元形状を生成する３次元形状生成装置において、輪郭・内部・外部の３つの属性値のいずれかを持つ個々のボクセルから成るボリュームモデルを距離画像から生成する手段と、前記ボリュームモデル中のボクセルの位置を順次ずらしながら取得した隣接する複数ボクセルの前記属性値の組み合わせに基づいて基本３角形メッシュを生成する手段と、その基本３角形メッシュの頂点を移動させて３角形メッシュを生成するする手段と、を備えたことを特徴とする。
また、請求項１３記載の発明では、請求項１２記載の３次元形状生成装置において、基本３角形メッシュの頂点として、薄板境界頂点、非多様体稜線接続頂点、非多様体頂点、および一般頂点のうち、少なくとも２種類以上の頂点を検出し、検出された頂点の種類に応じて異なった頂点移動方法を選択可能にしたことを特徴とする。
また、請求項１４記載の発明では、請求項１３記載の３次元形状生成装置において、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから薄板境界稜線を検出する手段と、検出された薄板境界稜線から前記薄板境界頂点を検出する手段と、を備えたことを特徴とする。
また、請求項１５記載の発明では、請求項１３または請求項１４記載の３次元形状生成装置において、薄板境界頂点まわりの複数の基本３角形メッシュを薄板境界稜線に沿って切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより薄板境界頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段を備えたことを特徴とする。
また、請求項１６記載の発明では、請求項１３乃至請求項１５のいずれか１つの請求項に記載の３次元形状生成装置において、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから非多様体稜線を検出する手段と、前記非多様体稜線接続頂点を検出する手段と、を備えたことを特徴とする。
また、請求項１７記載の発明では、請求項１３乃至請求項１６のいずれか１つの請求項に記載の３次元形状生成装置において、非多様体稜線接続頂点を挟んで直交する２本の一般稜線を選択し、選択された２本の一般稜線に沿って前記非多様体稜線接続頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体稜線接続頂点を移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段を備えたことを特徴とする。
また、請求項１８記載の発明では、請求項１３乃至請求項１７のいずれか１つの請求項に記載の３次元形状生成装置において、２つの基本３角形メッシュの組から成る４角形面を検出し、検出された４角形面の組み合わせから非多様体頂点を検出する手段を備えたことを特徴とする。
また、請求項１９記載の発明では、請求項１３乃至請求項１８のいずれか１つの請求項に記載の３次元形状生成装置において、非多様体頂点を挟んで直交する稜線２本を１組とする稜線の組を複数組選択し、選択された複数組の稜線の各組の稜線に沿って前記非多様体頂点まわりの複数の基本３角形メッシュを切り離し、その結果として生成された複数の頂点を距離画像メッシュ上にのるまで移動することにより前記非多様体頂点を移動し、その移動により生成された前記基本３角形メッシュのすきまに新たに３角形面を生成する手段を備えたことを特徴とする。
また、請求項２０記載の発明では、請求項１３乃至請求項１９のいずれか１つの請求項に記載の３次元形状生成装置において、２つの基本３角形メッシュの組から成る４角形面を検出する手段と、検出された４角形面の組み合わせから面構成パターンを選択する手段と、選択された面構成パターン毎に新たに頂点と稜線を生成する手段と、を備え、新たに生成した頂点を距離画像メッシュ上にのるまで移動することにより、前記一般頂点を移動することを特徴とする。
また、請求項２１記載の発明では、請求項１３乃至請求項２０のいずれか１つの請求項に記載の３次元形状生成装置において、頂点に隣接する基本３角形メッシュの平均法線ベクトルを計算し、求まった平均法線ベクトルから対角線ベクトルを取得し、対角線ベクトルに沿って距離画像メッシュと交差するまで頂点を移動させることにより前記頂点を距離画像メッシュ上にのるまで移動することを特徴とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
【発明の効果】
以上説明したように、本発明によれば、請求項１、１２記載の発明では、輪郭・内部・外部の３つの属性値のいずれかを持つ個々のボクセルから成るボリュームモデルが距離画像から生成され、前記ボリュームモデル中のボクセルの位置を順次ずらしながら取得した隣接する複数ボクセルの前記属性値の組み合わせに基づいて基本３角形メッシュが生成され、さらに、その基本３角形メッシュの頂点が実際の輪郭面に近づく方向に移動した３角形メッシュが生成されるので、３次元測定器などで測定することにより得られる距離画像から３角形メッシュを生成する際に、角張った形状の鋭角の稜線、特に凹部分の鋭角稜線が失われるという問題、格子間隔以下の薄い形状と細い形状が失われるという問題、格子位置により形状が変化してしまうという問題などを解消できる。
また、請求項２、１３記載の発明では、基本３角形メッシュの頂点として、薄板境界頂点、非多様体稜線接続頂点、非多様体頂点、および一般頂点のうち、少なくとも２種類以上の頂点を検出し、検出された頂点の種類に応じて異なった頂点移動方法で頂点を移動させることができるので、基本３角形メッシュを実際の輪郭面に、より適切に近づけることができる。
また、請求項３、１４記載の発明では、２つの基本３角形メッシュの組から成る４角形面が検出され、検出された４角形面の組み合わせから薄板境界稜線が検出され、検出された薄板境界稜線から前記薄板境界頂点が検出されるので、請求項２及び請求項１３記載の発明における薄板境界頂点の検出を容易に実現することができる。
また、請求項４、１５記載の発明では、薄板境界頂点まわりの複数の基本３角形メッシュが薄板境界稜線に沿って切り離され、その結果として生成された複数の頂点が距離画像メッシュ上にのるまで移動されることにより薄板境界頂点が移動され、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面が生成されるので、特に、格子間隔以下の薄い形状と細い形状が失われるという問題、格子位置により形状が変化してしまうという問題などを効果的に解消できる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
また、請求項５、１６記載の発明では、２つの基本３角形メッシュの組から成る４角形面が検出され、検出された４角形面の組み合わせから非多様体稜線が検出され、それにより、前記非多様体稜線接続頂点が検出されるので、請求項２、請求項３、請求項４、請求項１３、請求項１４及び請求項１５に記載の発明における非多様体稜線接続頂点の検出を容易に実現することができる。
また、請求項６、１７記載の発明では、非多様体稜線接続頂点を挟んで直交する２本の一般稜線が選択され、選択された２本の一般稜線に沿って前記非多様体稜線接続頂点まわりの複数の基本３角形メッシュが切り離され、その結果として生成された複数の頂点が距離画像メッシュ上にのるまで移動することにより前記非多様体稜線接続頂点が移動し、この移動により生成された前記基本３角形メッシュのすきまに新たに３角形面が生成されるので、非多様体稜線接続頂点を有した３次元形状であっても、基本３角形メッシュを実際の輪郭面に適切に近づけることができ、したがって、角張った形状の鋭角の稜線、特に凹部分の鋭角稜線が失われるという問題、格子間隔以下の薄い形状と細い形状が失われるという問題、格子位置により形状が変化してしまうという問題などを解消できる。
また、請求項７、１８記載の発明では、２つの基本３角形メッシュの組から成る４角形面が検出され、検出された４角形面の組み合わせから非多様体頂点が検出されるので、請求項２乃至請求項６記載の発明における非多様体頂点の検出を容易に実現することができる。
また、請求項８、１９記載の発明では、非多様体頂点を挟んで直交する稜線２本を１組とする稜線の組が複数組選択され、選択された複数組の稜線の各組の稜線に沿って前記非多様体頂点まわりの複数の基本３角形メッシュが切り離され、その結果として生成された複数の頂点が距離画像メッシュ上にのるまで移動することにより前記非多様体頂点が移動し、その移動により生成された前記基本３角形メッシュのすきまに新たに３角形面が生成されるので、非多様体頂点を有した３次元形状であっても、基本３角形メッシュを実際の輪郭面に適切に近づけることができ、したがって、角張った形状の鋭角の稜線、特に凹部分の鋭角稜線が失われるという問題、格子間隔以下の薄い形状と細い形状が失われるという問題、格子位置により形状が変化してしまうという問題などを解消できる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
また、請求項９、２０記載の発明では、２つの基本３角形メッシュの組から成る４角形面が検出され、検出された４角形面の組み合わせから面構成パターンが選択され、選択された面構成パターン毎に新たに頂点と稜線が生成され、新たに生成された頂点が距離画像メッシュ上にのるまで移動することにより、前記一般頂点が移動するので、各種頂点のなかに一般頂点が混在した３次元形状であっても、基本３角形メッシュを実際の輪郭面に適切に近づけることができ、したがって、角張った形状の鋭角の稜線、特に凹部分の鋭角稜線が失われるという問題、格子間隔以下の薄い形状と細い形状が失われるという問題、格子位置により形状が変化してしまうという問題などを解消できる。
また、請求項１０、２１記載の発明では、頂点に隣接する基本３角形メッシュの平均法線ベクトルが計算され、求まった平均法線ベクトルから対角線ベクトルが取得され、その対角線ベクトルに沿って距離画像メッシュと交差するまで頂点が移動することにより前記頂点が距離画像メッシュ上にのるまで移動するので、例えば薄板などの場合に、頂点移動の際、ボクセルの中心としての頂点が実際の薄板の表面からずれてしまっていて距離画像メッシュにのらないという事態を避けることができる。
また、請求項１１記載の発明では、請求項１乃至請求項１０のいずれか１つの請求項に記載の３次元形状生成方法を実施するためのプログラムが例えば着脱可能な記憶媒体に記憶されるので、その記憶媒体をこれまで請求項１乃至請求項１０記載の発明によった３次元形状生成を行えなかったパーソナルコンピュータなど情報処理装置に装着することにより、その情報処理装置においても請求項１乃至請求項１０記載の発明の効果を実現することができる。