TOP > 国内特許検索 > 最大角度法を用いた三角形メッシュ生成方法及びプログラム

最大角度法を用いた三角形メッシュ生成方法及びプログラム

国内特許コード P110003336
整理番号 V236P001
掲載日 2011年6月20日
出願番号 特願2004-104732
公開番号 特開2005-293021
登録番号 特許第3928016号
出願日 平成16年3月31日(2004.3.31)
公開日 平成17年10月20日(2005.10.20)
登録日 平成19年3月16日(2007.3.16)
発明者
  • 萩原 一郎
  • 程 文杰
  • 篠田 淳一
出願人
  • 国立研究開発法人科学技術振興機構
  • 萩原 一郎
  • 篠田 淳一
発明の名称 最大角度法を用いた三角形メッシュ生成方法及びプログラム
発明の概要 【課題】
コンピュータシステムを利用し、二次元空間内若しくは三次元空間内に与えられた散乱点群から、高品質な三角形メッシュを簡単且つ高速に生成できるようにした三角形メッシュ生成方法及びプログラムを提供する。
【解決手段】
a1.コンピュータに入力された二次元散乱点群データは、四分木アルゴリズムによって木構造が生成され、ポイントリストによって整列されるステップと、a2.整列された二次元散乱点群データから初期点を選択し、選択した初期点に対する最短線分を生成するステップと、a3.前記最短線分に対して前記木構造の中の関係する点から最大角度点を探し、新しい三角形要素と線分を生成すると共に、新しく生成した三角形要素と線分をそれぞれ要素リスト、線分リストへ格納するステップと、a4.前記二次元散乱点群データに属する全ての点が三角形メッシュに含まれるまで、前記線分リストの順序に従って選択した線分を前記最短線分とし、ステップa3を繰り返すステップとを有する。
【選択図】 図5
従来技術、競合技術の概要


近年、工学、医療、地理学などの多くの分野において、三次元スキャナー等の計測機器で得られた計測データ(つまり、散乱点群)からCADモデルまたはメッシュモデルを構成し、それに解析に利用するといったことがよく行われている。その際、よく用いられるのが三角メッシュである。そこでは形状の正確な再構成が要求され、また精度のよい解析を行うためには高品質なメッシュ、即ち、正三角形に近くなるようなアスペクト比を有する三角形メッシュが必要とされる。



散乱点群からの三角形メッシュ生成に関しては、過去に多くの研究がなされてきた。二次元の場合には、Voronoi多角形(以下、ボロノイ多角形と称する)を用いたDelaunayの三角形分割法(以下、ドロネー三角形分割法と称する)が良く知られている。また、ローソンは“四角形を作った場合にその内部に点を持たない任意の四点に対して、この四角形の分割が、分割によってできる二つの三角形において、最小の角が大きくなる”という基準を提案した(非特許文献1を参照)。そして後に、“任意の三点で生成した円の中に、他の点がない場合、この三点によって三角形が構成する”という円を用いた基準も提案した(非特許文献2を参照)。ドロネー三角形分割法がローソンらの手法と同値になることは、シブソンによって証明された(非特許文献3を参照)。



さらに、これらの高速化アルゴリズムとしては、現在、次の二つの手法がその効率の良さから幅広く使われている。1つ目として、クラインとレンカは、散乱点群を整列化し、そこにローソンによって提出された手法(非特許文献1を参照)を適用する手法を提案した(非特許文献4を参照)。2つ目として、リー、シャハターとブラウンは、平面を三角形に分割して、各三角形内の点群に対してローソンによって提出された手法(非特許文献2を参照)を利用する手法を提案した(非特許文献5と非特許文献6を参照)。



一方、三次元空間内の散乱点群から曲面三角形メッシュを生成する手法としては、チョウイらがある(非特許文献7を参照)。そこでは分割した各部を射影して二次元化し、そこにドロネー三角形分割法を適用している。この意味でチョウイらの手法は、ドロネー三角形分割法を一般化にした方法である。また、ホープは散乱点群を分割し、各部分に付随する小面分とその法線ベクトルを決定し、それらを調整してメッシュを生成する手法を提案した(非特許文献8を参照)。
【非特許文献1】
シー.エル.ローソン(C.L.Lawson)著、「ジェネレーション オブ ア トライアンギュラー グリッド ウィズ アプリケーション トゥー コンター プロッティング,ジェット プロパルション ラボラトリー インターナル テクニカル メモランダム(Generation of a triangular grid with application to contour plotting, Jet Propulsion Laboratory Internal Technical Memorandum)」、1972年,第299号
【非特許文献2】
シー.エル.ローソン(C.L.Lawson)著、「ソフトウェア フォア シーワン サーフィス インターポーレーション, イン マセマティカル ソフトウェア スリー, イー.デー.ジェイ.アール,ライス, アカデミック プレス(Software for C1 surface interpolation, in Mathematical Software III,ed.J.R.Rice,Academic Press)」、米国,1977年,p.161
【非特許文献3】
アール.シブソン(R.Sibson)著、「ローカリー イークウィアンギュラー トライアンギュレーション, コンピューター ジャーナル(Locally equiangular triangulations, The Computer Journal)」、1978年,第121巻,第3号,p.243
【非特許文献4】
エー.ケー.クライン(A.K.Cline)、アール.エール.レンカ(R.L.Renka)共著、「ストーリッジ エフィシャント メソッド フォア コンストラクション オブ サイエッセン トライアンギュレーション, ロッキー マウンテン ジャーナル オブ マセマティックス(A storage-efficient method for construction of a thiessen triangulation, Rocky Mountain Journal of Mathematics)」、1984年,第14巻,第1号,p.119
【非特許文献5】
デー.テー.リー(D.T.Lee)、ビー.ジェイ.シャハター(B.J.Schachter)共著、「ツー アルゴリズム フォア コンストラクティング ドローネ トライアンギュレーション, インターナショナル ジャーナル オブ コンピュータ アンド インフォーメーション サイエンス(Two algorithms for constructing a Delaunay Triangulation, International Journal of Computer and Information Sciences)」、1980年,第9巻,第3号,p1691
【非特許文献6】
ジェイ.エル.ブラウン(J.L.Brown)著、「ヴェクテックス ベースド データ ディペンデント トライアンギュレーション, コンピュータ エイディド ジオメトリック デザイン(Vertex based data dependent triangulation, Computer Aided Geometric Design)」、1991年,第8巻,第3号,p.239
【非特許文献7】
ビー.ケー.チョウイ(B.K.Choi)、エイチ.ワイ.シン(H.Y.Shin)、ワイ.アイ.ヨーン(Y.I.Yoon)、ジェイ.ダブリュー.リー(J.W.Lee)共著、「トライアンギュレーション オブ スキャタード データ イン スリーデー スペース, コンピューター エイディド デザイン(Triangulation of scattered data in 3D space, Computer-Aided Design)」、1988年,第20巻,第5号,p.239
【非特許文献8】
エイチ.ホープ(H.Hoppe)著、「サーフィス リコンストラクション フロム アンオーガナイズド ポイント, ドクトラル シーシス, ユニバーシティ オブ ワシントン(Surface reconstruction from unorganized points, Doctoral thesis, University of Washington)」、1994年

産業上の利用分野


本発明は、工学、医療、地理学などの多くの分野で広く使用される三角形メッシュを生成する三角形メッシュ生成技術に関し、特に、コンピュータシステムを利用し、二次元空間内若しくは三次元空間内に与えられた散乱点群から、高品質な三角形メッシュを簡単且つ高速に生成できるようにした、三角形メッシュ生成方法及びプログラムに関するものである。

特許請求の範囲 【請求項1】
コンピュータの演算処理によって、三次元散乱点群データから初期三角形メッシュを自動生成する方法であって、
c1.前記コンピュータに入力された前記三次元散乱点群データは、八分木アルゴリズムによって木構造が生成され、ポイントリストによって整列されるステップと、
c2.前記木構造を用いて、各点から最短距離にある点を結び、これを長さの短い順に並べ、第1の線分リストを生成し、空の第2の線分リスト及び空の要素リストを用意するステップと、
c3.前記第1の線分リストの先頭にある線分を選択し、選択した線分の最大角度点を求め、選択した線分及びその両端点と前記最大角度点を結んでできた2線分から構成される3線分のうち、前記第2の線分リストに無いものがあれば、これを前記第2の線分リストへ格納し、また、生成した三角形が前記要素リストになければ、これを前記要素リストへ格納するステップと、
c4.生成した三角形を基準面として、その周囲の散乱点の分布状況をトポロジー判断関数によって交差の生成を判断し、交差生成の可能性が大と判断された場合に、生成した三角形を前記要素リストから削除すると共に、選択した線分を前記第1の線分リストから削除し、ステップc3に戻り、また、交差生成の可能性がないと判断された場合に、ステップc5に進むようにするステップと、
c5.生成した三角形と共有部分をもつ三角形を求め、求めた三角形と生成した三角形との共有関係によって、交差の生成を判断し、交差生成の可能性が大と判断された場合に、生成した三角形を前記要素リストから削除すると共に、選択した線分を前記第1の線分リストから削除し、ステップc3に戻り、また、交差生成の可能性がないと判断された場合に、既にステップc3で前記要素リストに格納されている生成した三角形は確定し、ステップc6に進むようにするステップと、
c6.選択した線分からのトポロジー判断を利用することによって分断面を生成し、確定した三角形と逆の方向にある散乱点群に対して、ステップc3からステップc5までの処理を実行し、もう一つの三角形を生成するステップと、
c7.選択した線分を前記第1の線分リストから削除し、前記第1の線分リストが空であれば、前記初期三角形メッシュが生成され、処理が終了し、また、前記第1の線分リストが空でなければ、ステップc3に戻るようにするステップと、
を有することを特徴とする最大角度法を用いた三角形メッシュ生成方法。

【請求項2】
コンピュータの演算処理によって、請求項1の方法によって生成された初期三角形メッシュに存在する折線ループ内に三角形メッシュを自動生成する方法であって、
d1.前記コンピュータに入力された初期三角形メッシュにおいて、未処理の折線ループを選択するステップと、
d2.選択された折線ループ内に三角形メッシュが存在するかどうかを判断し、選択された折線ループ内に三角形メッシュが存在した場合に、内側の折線ループの最短線分を選択すると共に、外側の折線ループの節点から最大角度点を選択し、ステップd3に進み、一方、選択された折線ループ内に三角形メッシュが存在しないと判断された場合に、折線ループ内の最短線分を選択し、折線ループの節点から最大角度点を選択し、ステップd3に進むようにするステップと、
d3.三角形を生成し、三角形の生成によって新しい折線ループが生成されたかどうかを判断し、新しい折線ループが生成された場合に、ステップd2に戻り、一方、新しい折線ループが生成されない場合に、折線ループの処理が終了したかどうかを判断し、折線ループの処理が終了していない場合に、ステップd2に戻るようにするステップと、
d4.ステップd3で折線ループの処理が終了したと判断された場合に、前記初期三角形メッシュに未処理の折線ループが存在するかどうかを判断し、前記初期三角形メッシュに未処理の折線ループが存在した場合に、ステップd1に戻り、一方、前記初期三角形メッシュに未処理の折線ループが存在しない場合に、前記初期三角形メッシュ内の全ての折線ループに三角形メッシュが生成され、三角形メッシュが完成するステップと、
を有することを特徴とする最大角度法を用いた三角形メッシュ生成方法。

【請求項3】
三次元散乱点群データから初期三角形メッシュを自動生成するためのコンピュータプログラムであって、
c1.前記三次元散乱点群データを取得し、取得された前記三次元散乱点群データは、八分木アルゴリズムによって木構造が生成され、ポイントリストによって整列される手順と、
c2.前記木構造を用いて、各点から最短距離にある点を結び、これを長さの短い順に並べ、第1の線分リストを生成し、空の第2の線分リスト及び空の要素リストを用意する手順と、
c3.前記第1の線分リストの先頭にある線分を選択し、選択した線分の最大角度点を求め、選択した線分及びその両端点と前記最大角度点を結んでできた2線分から構成される3線分のうち、前記第2の線分リストに無いものがあれば、これを前記第2の線分リストへ格納し、また、生成した三角形が前記要素リストになければ、これを前記要素リストへ格納する手順と、
c4.生成した三角形を基準面として、その周囲の散乱点の分布状況をトポロジー判断関数によって交差の生成を判断し、交差生成の可能性が大と判断された場合に、生成した三角形を前記要素リストから削除すると共に、選択した線分を前記第1の線分リストから削除し、手順c3に戻り、また、交差生成の可能性がないと判断された場合に、手順c5に進むようにする手順と、
c5.生成した三角形と共有部分をもつ三角形を求め、求めた三角形と生成した三角形との共有関係によって、交差の生成を判断し、交差生成の可能性が大と判断された場合に、生成した三角形を前記要素リストから削除すると共に、選択した線分を前記第1の線分リストから削除し、手順c3に戻り、また、交差生成の可能性がないと判断された場合に、既に手順c3で前記要素リストに格納されている生成した三角形は確定し、手順c6に進むようにする手順と、
c6.選択した線分からのトポロジー判断を利用することによって分断面を生成し、確定した三角形と逆の方向にある散乱点群に対して、手順c3から手順c5までの処理を実行し、もう一つの三角形を生成する手順と、
c7.選択した線分を前記第1の線分リストから削除し、前記第1の線分リストが空であれば、前記初期三角形メッシュが生成され、処理が終了し、また、前記第1の線分リストが空でなければ、手順c3に戻るようにする手順と、
をコンピュータに実行させるためのプログラム。

【請求項4】
請求項3のプログラムによって生成された初期三角形メッシュに存在する折線ループ内に三角形メッシュを自動生成するためのコンピュータプログラムであって、
d1.前記初期三角形メッシュを取得し、取得された前記初期三角形メッシュにおいて、未処理の折線ループを選択する手順と、
d2.選択された折線ループ内に三角形メッシュが存在するかどうかを判断し、選択された折線ループ内に三角形メッシュが存在した場合に、内側の折線ループの最短線分を選択すると共に、外側の折線ループの節点から最大角度点を選択し、手順d3に進み、一方、選択された折線ループ内に三角形メッシュが存在しないと判断された場合に、折線ループ内の最短線分を選択し、折線ループの節点から最大角度点を選択し、手順d3に進むようにする手順と、
d3.三角形を生成し、三角形の生成によって新しい折線ループが生成されたかどうかを判断し、新しい折線ループが生成された場合に、手順d2に戻り、一方、新しい折線ループが生成されない場合に、折線ループの処理が終了したかどうかを判断し、折線ループの処理が終了していない場合に、手順d2に戻るようにする手順と、
d4.手順d3で折線ループの処理が終了したと判断された場合に、前記初期三角形メッシュに未処理の折線ループが存在するかどうかを判断し、前記初期三角形メッシュに未処理の折線ループが存在した場合に、手順d1に戻り、一方、前記初期三角形メッシュに未処理の折線ループが存在しない場合に、前記初期三角形メッシュ内の全ての折線ループに三角形メッシュが生成され、三角形メッシュが完成する手順と、
をコンピュータに実行させるためのプログラム。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2004104732thum.jpg
出願権利状態 登録
ライセンスをご希望の方、特許の内容に興味を持たれた方は、問合せボタンを押してください。


PAGE TOP

close
close
close
close
close
close
close