4 0 0 0 制約つきDelaunay三角メッシュ生成法の効率的な実装方法
CADなどで生成された形状を細かい要素の集合に分割するメッシュ生成技術は、計算力学、形状表現、画像生成などの各分野に広く用いられている。もっとも有名なメッシュ生成手法の一つに、Delaunay三角メッシュ生成法がある。この方法は、平面中に与えられた多数の節点(ノード)を連結して三角形要素の集合を生成する方法であり、三角形要素の最小角度が最大になるようにメッシュを生成する。特に、形状の外周(Outside loop)、穴(Inside hole)、内部線分(Inside wire)などを制約条件にして(図1(a)参照)、制約条件を破損しないように三角メッシュを生成する、制約つきDelaunay三角メッシュ生成法が広く実用されている。ここでいう「制約条件を破損しない」とは、制約条件を構成するすベての線分(制約線分)が1個または2個の要素の辺となるように三角メッシュを生成することを意味する。制約つきDelaunay三角メッシュ生成法の典型的なアルゴリズム[1]では、制約線分がない状態で三角メッシュを生成し、そのメッシュに制約線分を追加し、制約線分と交差する要素を除去し、その領域におけるメッシュを再生成する(図1(b)参照)。しかしこの手法では、非常に多数のノードや制約線分をもつ場合に、要素と制約線分の交差判定処理、および再メッシュ生成処理の処理時間が大きくなる。本報告では、要素と制約線分との交差判定などの処理時間を低減する、制約つきDelaunay三角メッシュ生成法の効率的な実装方法(図1(c)参照)を提案する。本手法では、まず制約線分に接するノードを処理し、2辺が同一制約線分と文差する三角形がある場合には、メッシュをそのノードの処理前の状態に戻し、別のノードを先に処理する。この処理を終えた時点で、すべての制約線分は1個または2個の三角形要素に共有された状態となる。その後に、制約線分に接しないノードを処理して三角メッシュを完成する。この時、制約線分に接しないノードの処理において、新しい三角形要素と制約線分の交差判定をすることなく、制約線分の破損を防ぐことができる。よって、従来の手法よりも、制約線分との交差判定を少なくすることができる。
1 0 0 0 OA 製品設計と製造における「自由度」
- 著者
- 嶋田 憲司
- 出版者
- 公益社団法人 精密工学会
- 雑誌
- 精密工学会誌 (ISSN:09120289)
- 巻号頁・発行日
- vol.80, no.2, pp.162-166, 2014-02-05 (Released:2014-02-05)
- 参考文献数
- 4
- 著者
- 嶋田 憲司
- 出版者
- 日本シミュレーション学会
- 雑誌
- シミュレーション (ISSN:02859947)
- 巻号頁・発行日
- vol.12, no.1, pp.11-20, 1993-03-15
- 被引用文献数
- 14
Automated mesh generation is a significant problem in many computer applications such as engineering analysis, computer graphics and layered manufacturing. Although various algorithms have been proposed thus far, their functionality and coverage are limited, in most cases being application-specific. This paper provides a summary of those algorithms by classifying them and pointing out unsolved problems. In reviewing them, it is clear that none sufficiently address the major problem of node placement, that is to say the locating of nodes such that they maintain a specified distance between nodes and create a mesh with minimal distortion. This paper introduces a new, physically-based approach to this problem. The method was inspired by the pattern of soap bubbles floating in liquid which gives topology and geometry similar to ideal meshes. Each mesh node is modeled as a bubble with a point mass and viscous damping. The force field exerts repelling/attracting forces between bubbles much like intermolecular van del Waals forces. The equilibrium bubble configuration is obtained by solving numerically the governing equation of motion to yield the static force balance. After the bubble locations are decided, their center points are connected by Delaunay triangulation to give a complete mesh topology.