English page is here.

Bubble Mesh ... Physically-based triangulation

概要 自然界には、最密充填によってできる規則正しいパターンが数多く見られます。 石鹸の泡、ハチの巣、昆虫の複眼などがその一例です。 これらの規則パターンの中心点を結ぶことによって、歪みの小さい三角メッシュ を得ることが出来ます。 バブル・メッシュは、これらの自然現象と同様な物理モデルを用いることで、 歪みの小さいメッシュを生成します。 研究背景 数値解析の精度や、CGのための形状モデリングの精密さは、メッシュの細かさに 大きく依存します。 数値解析において、信用性の高い解を求める一手段として、上左図のように、 領域全体を一様に細かくメッシュ分割することが考えられます。 しかし、処理時間が膨大になるという問題があります。 そこで、正確に解を算出したい部位のみを細かく分割したメッシュを用いる ことで、処理時間の増加を防ぎながら正確な解を求めることが出来ます。 しかし、上右図のようなメッシュでは、メッシュの大きさが変化する部位で 要素が細長く歪んでおり、解の精度に影響を与えることがあります。 これらの背景から、数値解析やCGの分野では、 要素の大きさを適応的に制御することが可能であり、 かつ歪みの少ないメッシュを生成することが出来るメッシュ分割手法 を確立することが重要な課題となっていました。 バブル・メッシュの原理 バブル・メッシュは、質量と分子間力を仮定した球状物体(バブル)を、 領域内部で最密充填となるように動力学シミュレーションを解いて、 要素頂点の配置パターンを得ることにより、上記の課題を解決すること が出来る、新しいメッシュ分割手法です。 上図は、球状物体を配置した初期位置と、球状物体の中心点を結んで出来た 三角メッシュです。 上図は、動力学シミュレーションが収束した後の球状物体と、球状物体の 中心点を結んで出来た三角メッシュです。 メッシュの歪みが低減されているのが示されています。 動力学シミュレーションが収束する過程のアニメーション表示は、こちらを 御参照下さい。 (注：この画像ファイルはやや大きいです (109KB)。)

バブル・メッシュは、 入力形状に対して、次元の低い順 (頂点、辺、面) に、球状物体の動力学 シミュレーションを実行する。 球状物体の中心を、Delaunay Triangulation を用いて連結することにより、 三角メッシュを生成する。 の手順で、2次元三角メッシュを生成します。 同様な概念をソリッドモデルに拡張することで、3次元四面体メッシュを 生成することも可能です。 バブル・メッシュの実装 バブル・メッシュでは、要素の大きさを表す関数を参照しながら、分岐処理 (辺上では2分木、面上では4分木)によって球状物体を配置します。 球状物体が領域全体に配置されてから、運動方程式の動力学シミュレーション を解きます。 バブル・メッシュでは、隣接する球状物体間の安定距離を と定義し、球状物体間の距離が安定距離よりも大きい時には引力、小さい時 には斥力が働くように、下記のような分子間力を仮想します。 この分子間力を用いることで、球状物体の運動方程式は と記述されます。この式は常微分方程式であるので、 Runge-Kutta などの 数値解析手法を用いて解くことが出来ます。 なお、上記の式における各変数の意味は、以下の通りです。 このシミュレーションが収束したら、各隣接物体間の距離を算出し、球状物体 間に隙間が大きく生じている部位では球状物体を追加し、また球状物体が必要 以上に密集している部位では球状物体を削除して、シミュレーションを再開します。 球状物体の追加および削除が不必要になったところで、シミュレーションを 終了し、Delaunay Triangulation により三角メッシュを生成します。 メッシング・プロジェクトのトップページへ

Last modified 30 June 1998