制約つきDelaunay三角メッシュ生成法の効率的な実装方法

概要

論文の詳細を見る
CADなどで生成された形状を細かい要素の集合に分割するメッシュ生成技術は、計算力学、形状表現、画像生成などの各分野に広く用いられている。もっとも有名なメッシュ生成手法の一つに、Delaunay三角メッシュ生成法がある。この方法は、平面中に与えられた多数の節点(ノード)を連結して三角形要素の集合を生成する方法であり、三角形要素の最小角度が最大になるようにメッシュを生成する。特に、形状の外周(Outside loop)、穴(Inside hole)、内部線分(Inside wire)などを制約条件にして(図1(a)参照)、制約条件を破損しないように三角メッシュを生成する、制約つきDelaunay三角メッシュ生成法が広く実用されている。ここでいう「制約条件を破損しない」とは、制約条件を構成するすベての線分(制約線分)が1個または2個の要素の辺となるように三角メッシュを生成することを意味する。制約つきDelaunay三角メッシュ生成法の典型的なアルゴリズム[1]では、制約線分がない状態で三角メッシュを生成し、そのメッシュに制約線分を追加し、制約線分と交差する要素を除去し、その領域におけるメッシュを再生成する(図1(b)参照)。しかしこの手法では、非常に多数のノードや制約線分をもつ場合に、要素と制約線分の交差判定処理、および再メッシュ生成処理の処理時間が大きくなる。本報告では、要素と制約線分との交差判定などの処理時間を低減する、制約つきDelaunay三角メッシュ生成法の効率的な実装方法(図1(c)参照)を提案する。本手法では、まず制約線分に接するノードを処理し、2辺が同一制約線分と文差する三角形がある場合には、メッシュをそのノードの処理前の状態に戻し、別のノードを先に処理する。この処理を終えた時点で、すべての制約線分は1個または2個の三角形要素に共有された状態となる。その後に、制約線分に接しないノードを処理して三角メッシュを完成する。この時、制約線分に接しないノードの処理において、新しい三角形要素と制約線分の交差判定をすることなく、制約線分の破損を防ぐことができる。よって、従来の手法よりも、制約線分との交差判定を少なくすることができる。
一般社団法人情報処理学会の論文
1997-09-24

制約つきDelaunay三角メッシュ生成法の効率的な実装方法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク