いきなり3次元で考えると事態が複雑化するから、まずは2次元の平面図形で考えてみる。

この絵は濃度の分布を白-黒のグラデーションで表したもので、色が濃い（黒い）方が分布関数の値が大きいことを示している。また、赤い線は濃度がとある閾値と等しくなる位置を示している。

とりあえず今は丸いメタボールを生成する事について考える。また、中心点も複数あると厄介だから、一つだけに限定する。すると、赤い線で示された、濃度が閾値に等しくなる部分の形状は正円になるはずである。

とりあえずまずは、上記のような濃度分布を元に赤い線を描画させる方法について検討する。

直線による近似

上記のような線は、数学的には分布関数C_mが「とある閾値」に等しくなる点の集合として求められる。しかし、それで満足するのは数学屋だけである。

世の中で重要なのは理論ではなく出力である。上記のような曲線をどうやってコンピュータに描かせるのか、その具体的な方法について考えなければならない。

処理系にもよるが、普通、コンピュータで曲線を描く場合には、複数の直線が連なった物として描画する。また、直線を描く場合には二点の座標を指定して「その二点間を線で結べ」という指示の仕方をする。

例えばBasicなら
line( x1, y1 ) - (x2, y2 ),7
となる。また、Xなら
XDrawLine( display, d, gc, x1, y1, x2, y2 );
で、PostScriptなら
x1 y1 moveto
x2 y2 lineto
stroke
となる。

だから、上図の赤い線を、何らかの方法で複数個の直線として求めてやらなければならない。

だからそういう場合は、こんな風にして考える。

まず、座標系全体を格子状に分割する。

この絵は、さっきの絵に等間隔に青い直線を引いただけの絵である。この青い線は、一応座標系を表しているものと思ってもらいたい。

なお、線がゆがんで見えるのは目の錯覚である。決して座標系が歪んでいる訳ではない。

ここで、分割された格子の内の1つ、描画したい赤い線が含まれている格子に着目して考えてみる。

上図では、描画したい線は赤い太線で示してある。また、右下の黒い四角は、格子の頂点における濃度が閾値を超えている事を表していて、それ以外の白い四角は頂点の濃度が閾値を下回っていることを表してる。

つまり、右下に行くほど濃度が高くなっているのだと解釈してもらいたい。

ここで、この赤い線を近似する線分として、下記のような線を引いてみることにする。

この絵を見ると、赤い線の形が結構変わってしまっているような気もする。だが、格子のサイズが十分に小さければ、この差はほとんど無視できるようになるはずである。

このように「格子の中に線分を引く」という操作をひたすら全ての格子に対して行えば、最終的には目的の曲線を描画することが可能となる。

格子の中の直線を求める

格子の中にある短い曲線を近似した線分として描画する、というのを直感的に理解するのは簡単である。しかし、プログラムにするとなると、これが意外と厄介である。

ここでは「近似した線分」の求め方について説明する。

まず、格子の1つに着目したとき、得られる情報としては、4つある頂点での濃度ぐらいしかない。

もちろん、格子内の至る所で濃度を求めれば求められないことはないが、それでは細かい格子に分割した理由がなくなるから、ここは頂点での濃度だけを考えることにする。

例えば、ここでは閾値を0.3と仮定して、頂点における濃度が下記のようになっていたものとする。

ここでは右下の頂点が閾値を超えている。

右下の頂点だけが閾値を超えているという事実から、求める線分の端点は下と右の辺上に存在するということが求められる。

つまり、上記の絵でいうところの濃い緑で示された辺を斜めに繋ぐように線分が引かれるということを意味している。

後は、適当な補間アルゴリズムか何かを使って、濃度が閾値（ここでは0.3）になる点を推定してやって、その2点を結ぶ直線を引けばいい。

補間アルゴリズムとして比較的簡単なのは線形補間である。

左上の座標を(X₁,Y₁)、右上の座標を(X₂,Y₁)、左下の座標を(X₁,Y₂)、右下の座標を(X₂,Y₂)として、また同様に、下の辺上にある直線の端を(X₃,Y₂)、右の辺上にある直線の端を(X₂,Y₃)とする。また、左上の濃度をC₁、右上の濃度をC₂、左下の濃度をC₃、右下の濃度をC₄とする。

そうすると、X₃は下記の式で求められる。

数式にすると難しそうな気がするが、何のことはない。単に濃度の値で比例配分しているだけである。とりあえず、こうやって線を引いてやれば、目的の曲線が得られるはずである。

引くべき線のパターン

上の方で、「右下の頂点だけが閾値を超えているという事実から、求める線分の端点は下と右の辺上に存在するということが求められる」と簡単に書いたが、これをプログラムにするにはどうしたらいいのだろうか。

人間が目で見て判断するのは簡単である。しかし、プログラムで求める方法が思いつかない。例えば、下記のように閾値を超えている頂点が複数個存在した場合にはどうなるのだろうか。

人間様であれば、「下と右」「上と左」を繋ぐ線分が2本存在する、ということがすぐに判るが、プログラムで判断させるとなると、かなり難しいのではないだろうか。

はっきり言ってしまおう。これをプログラムで求めるのは不可能である。

だから、事前に考えられ得る全てのパターンを求めておいて、プログラム中に定義しておくしかないらしい。

二次元の図形であれば、格子中に存在する頂点は4つであるため、組み合わせの数としては2⁴= 16 通り考えられる。回転や対称を考えれば更に少なくなるが、元々16通りしかないから、これ以上削減する意味は余りない。

ということで、16通り全ての組み合わせを絵で描くとこうなる。

特に難しいことはない。

上記のようなパターンをプログラム中に定義し、全ての格子に対してそのパターン以外に該当するのかを求め、必要に応じて直線を引くという処理を行えば、目的の曲線が得られるはずである。

3Dに拡張する

3次元になった場合も、基本的には同じである。座標空間を小さな格子に分割して、それぞれの格子ごとにポリゴンを生成してやるだけである。

例えば、とある一つの頂点での濃度が閾値を超えていたとした場合には、生成されるポリゴンは下記のようになる。

2次元の時とほぼ同じ。

しかし、ここで注意が必要なのは通常ポリゴンには裏と表があるということである。

濃度が閾値を超えている点は、生成されるオブジェクトの内側にくることになり、逆に濃度が閾値を下回っている点は、生成されるオブジェクトの外側にくることになる。また、例えばOpenGLであれば、頂点を定義した順番が左回りに見える方が、ポリゴンの表になるものと定義されている。

だから、上の図でいうと、ポリゴンは必ずa-c-bの順（あるいはc-b-aかb-a-cの順）に定義しなければならない。そうでないと、変な図形が生成されることになる。

また、立体の格子には頂点が8つあるから、考えられる組み合わせは、全部で 2⁸= 256 通り存在することになる。回転や対称を除けば全部で15通りにまで絞ることができるそうだが、まぁ、全ての組み合わせを手作業で登録するのが一番簡単である。

とりあえず、15通りの絵を全部かくのは面倒なため、URLだけここに書いておく。

http://en.wikipedia.org/wiki/Marching_cubes

http://www.exaflop.org/docs/marchcubes/

例

ここで、上記の説明を元に作成したサンプルのプログラムを公開しておく。

meta2.zip 86.9KB

gmview.zip 32.3KB

meta2exeは、実行するとカレントディレクトリにあるcube.txtと、Ball.txtという定義ファイルを読み込み、標準出力にポリゴンのモデルを出力する。

cube.txtには、格子の種類別に応じたポリゴンのモデルを記述している。Ball.txtは、メタボールとして生成したいオブジェクトの形状を定義している。

Ball2.txtは下記のように記述する。
X, Y, Z, 有効範囲球のサイズ, ボールのサイズ
1行でボール1つ分、複数行記述すれば複数個のボールが生成される。

mata2.exeにより出力されたモデルは、gmview.exeの入力になる。gmview.exeは、meta2.exeにより出力されたデータを読み込み、モデルを画面に表示する。だから、meta2.exeの出力はリダイレクトしてファイルに書き込ませなくてはならない。

とりあえず、Ball.txtに下記のようなデータを記述すると、こんな結果が得られる。
-2.1, -2.1, -2.1, 3.5, 0.5
2.1, -2.1, -2.1, 3.5, 0.5
2.1, -2.1, 2.1, 3.5, 0.5
2.1, 2.1, -2.1, 3.5, 0.5
-2.1, 2.1, -2.1, 3.5, 0.5

別の方法

実をいうと、このmarching cubes法という奴はすでに特許があるらしい。しかし、諸説あるがこの特許は2005年に時効になっているらしい。

まぁ、個人で楽しむ分には多分問題とはならないだろうが、商売でプログラムを作る場合は気を付けた方が良いようだ。

とりあえず、特許回避という事と性能の向上の為に、marching tetrahedrons法という方法を説明する。

概要

marching tetrahedrons法も、基本的にやっていることはmarching cubes法と同じである。ただ、座標空間を正六面体に分割するのではなく四面体に分割するというところだけが異なる。

ただ、どうやって座標空間（普通は直方体だと思う）を複数の四面体に分割するのかが判りにくい。

とりあえず、この辺とかこの辺のページを見てみると、どうやらmarching cubes法における格子一つを、更に4つなり5つなりに分割してやればいいらしい。

分割方法

格子一つを分割するといっても、それをどうやって分割すれば良いのか。

とりあえず、直感的に理解しやすい、下記のような方法での分割を試みてみた。

言葉で書くと、

0-1-3-4の頂点からなる四面体

1-2-3-6　〃

1-4-5-6　〃

3-4-6-7　〃

1-3-4-6　〃

の5つとなる。

また、上記の左右対称となるパターンも考えられる。

同じく、言葉で書くと、

0-1-2-5の頂点からなる四面体

0-2-3-7　〃

0-4-5-7　〃

2-5-6-7　〃

0-2-5-7　〃

の5つとなる。

座標空間の分割

分割方法が2つ考えられるが、どちらを使用するべきなのか。どっちでも良いような気もするが、実はそうではない。

片方の分割方法だけを使って、座標空間中に存在する全ての格子を分割してしまうと、ポリゴンをうまく生成することができなくなる。すなわち、変な隙間が生じる恐れが出てくる。

なぜならば、同じ種類の格子を隣接させると、隣接する四面体の辺が一致しない部分が生じるからである。

例えば、下側の分割方法（右上奥に三角形が存在する方）を使って分割した格子を2つ並べると、下記のようになる。

上図の、中央部にある太い赤線は、左側の立方体の右側面に位置している。また、太い赤線と交差している太い青い点線は右側の立方体の左側面に位置している。

つまり、太い赤線と太い青い点線は同じ平面上に存在していると言うことになる。

また、ポリゴンの頂点は必ず四面体の辺上に存在する。

そのため、ポリゴンの頂点がうまい具合に太い赤線と太い青い点線の交点に来ない限り、隣接するべきポリゴンの間に不自然な隙間が生じてしまうことになる。

だから、必ず二つある分割方法を交互に使ってやらなければならない。そうすれば、隣接する四面体の辺が一致して、不自然な隙間が生じることはなくなる。

ポリゴンを生成するパターン

四面体の頂点は全部で4つ存在する。だから、「各頂点での濃度が閾値を超えたか否か」の組み合わせは全部で16通り存在する。

その16通りの組み合わせや、それぞれのパターンで生成されるポリゴン及びポリゴンの生成方法についてはmarching cubes法と同じ考え方で求めることができるから、説明は割愛する。

例

marching tetrahedrons法に従いプログラムを実装してみた。

meta3.zip 46.2KB

使い方はさっきと同じである。

カレントディレクトリにあるBall.txtファイルを読み込んで、gmviewの入力になるベクトルデータを出力する。

さっきと同じような下記のデータを喰わせると、こんな結果が得られる。
b, -2.1, -2.1, -2.1, 3.5, 0.5
b, 2.1, -2.1, -2.1, 3.5, 0.5
b, 2.1, -2.1, 2.1, 3.5, 0.5
b, 2.1, 2.1, -2.1, 3.5, 0.5
b, -2.1, 2.1, -2.1, 3.5, 0.5
正直に言うと、marching cubes法と何が違うのかよく分からない。

とりあえず、プログラムを作るときに定義するポリゴンの生成パターンが、256通りから16通りに減少するところが利点だろうか。