類似した点群に対するDelaunay三角形分割の差分的構成法

概要

論文の詳細を見る
Delaunay三角形分割は、与えられた点群を頂点とする三角形の集合に平面を分割する手法であり、幾何的に優れた性質を持つため、よく利用されている。一方、有限要素法やCGなどの目的でCADモデルの面領域をメッシュ分割する手法の一つに、Advancing Front法やMapped Mesh法と並んで、物理シミュレーションを応用した方法がある。これは、面上に存在する点群の配置を、物理的なモデルに基づき微分方程式で記述し、それを解くことで、決定するものである。Bubble Mesh法[1]はそうした手法の一つであり、水泡どうしが離れ過ぎず近過ぎず密に詰まる現象をシミュレートする。その過程で、各バブル(水泡)を表す粒子は、互いに及ぼす力によって少しずつ安定な位置に移動する。この計算は各粒子の運動方程式を繰り返し(数百回程度)解くことで行なわれるが、その間粒子どうしの隣接関係を保持するためDelaunay三角形分割を使って、粒子を頂点とするグラフ構造が計算されている。本稿では、少しずつ移動してゆく点群に対するDelaunay三角形分割を効率よく構成する方法、およびそれをパラメータ表現された曲面上での疑似Delaunay三角形分割に応用することの利点について報告する。
1997-09-24