メタボールを作る2

[1] 主筆嬢 08/03/24 23:12

以前考えたメタボールの生成方法だと、どうしても接合部分が綺麗にならなかったから、もうちょっとマシな画像を生成する方法について考えてみる。

[2] nabiki_t 08/03/24 23:13

前にも言ったが、やっぱりメタボールって、このサイトの趣旨・志向とは大幅に異なるじゃねぇか。

[3] 主筆嬢 08/03/24 23:16

細かいことは気にしない。

[4] 主筆嬢 08/03/24 23:19

今回も、前回同様二つのオブジェクトをなめらかに融合させることを考えてみる。でもって、例のごとく結果はポリゴンで出力する。

レイトレーシングとかやれば問答無用で美しい画像を生成することができるんでしょうけど、それだと計算負荷が高い。

日進月歩で技術は進歩しているとは言っても、やっぱりレイトレーシングでリアルタイムにアニメーションを描画できるほど、ハードウェアの性能は高くなっていないみたいだし。

[5] nabiki_t 08/03/24 23:23

前回も言ったが、メタボールをポリゴンで出力する場合は、分布関数による濃度の情報から、どうやってポリゴンを生成するのかが最大の問題となる。

3次元空間中の任意の点における濃度が判れば、メタボールは濃度が特定の閾値になる点の集合として求めることができる・・・・・・のではあるが、こんな答えで満足するのは一部の数学屋だけだ。

実際に動くモノを作るには、「点の集合」から面の集合による定義に変換してやらなければならない。

[6] 主筆嬢 08/03/24 23:30

だから前回は、球を表すポリゴンを求めて、それを元にポリゴンの頂点を球の中心から外に向かって、濃度が閾値と等しくなる点まで移動させていくという手法について考えてみた。

でもその手法だと、どうしても接合部分のポリゴンが荒くなって、絵が汚くなる。処理速度やメモリ使用量の観点からいけば有利な点があるのだろうけど、やっぱりハッタリをかますためにも高精度なグラフィックを表示したい。

だからやり方を替えて、marching cubes法という奴をやってみることにした。

[6] 主筆嬢 08/03/24 23:32

いきなり3次元で考えると難しいから、まずは、2次元の平面図形で考えてみる。

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

[7] nabiki_t 08/03/24 23:36

とりあえず今は丸いメタボールについて考えていることと、上記の絵では中心点が一つしかないことから、赤い線（濃度が閾値に等しくなる部分）の形状は正円になる。

でも当然だが、本来であれば上図の赤い線は不定形を描くことになるはずである。

[8] 主筆嬢 08/03/24 23:39

この辺りで広告を入れておこうか・・・・・・

[9] 主筆嬢 08/03/24 23:45

数学的には分布関数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

となる。

[10] nabiki_t 08/03/24 23:51

なんでBasicなんだよ・・・・・・

[10] 主筆嬢 08/03/24 23:55

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

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

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

[11] nabiki_t 08/03/25 00:00

線がゆがんで見えるのは目の錯覚だな。

[12] 主筆嬢 08/03/25 00:03 

でもって、分割された格子の内の一つに着目する。

ここでは、濃度が閾値に等しくなる点の集合（すなわち描画したい線）が含まれている格子について考えてみる。

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

[13] 主筆嬢 08/03/25 00:08

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

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

[14] 主筆嬢 08/03/25 00:11

あとは、>>10で作った全ての格子について>>12・>>13の操作を行い、得られた直線を描画すれば、目的の曲線を描くことができるようになる。・・・・・・はず。

[15] nabiki_t 08/03/25 00:13

をい、説明を端折りすぎだろうが。

一番肝心な「>>13で引く直線をどうやって生成するのか」ってことを言って無いじゃねぇか。

[15] 主筆嬢 08/03/25 00:18

うるさい。今から言うところだ。

[16] 主筆嬢 08/03/25 00:25

まず、格子一つに着目したとき、得られる情報としては、4つある頂点での濃度ぐらいしかない。もちろん、格子内の至る所で濃度を求めれば求められないことはないけど、それでは細かい格子に分割した理由がなくなるから、ここは頂点での濃度だけを考えることにする。

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

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

[17] 主筆嬢 08/03/25 00:26

この事から、下と右の辺上に直線の端が存在することが判る。

つまり、下図の緑色の辺上のどこかに、直線の端が存在することになるはず。

[18] 主筆嬢 08/03/25 00:27

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

補間アルゴリズムは、多分一番簡単なのは線形補間。

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

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

数式にするとエラそーな気がするけど、何のことはない。単に濃度の値で比例配分しているだけ。

とりあえず、こうやって線を引いてあげれば、目的の曲線が得られるはず。

[19] nabiki_t 08/03/25 00:35

いくら何でも、>>18の絵はいい加減すぎだろう。

どう見ても、赤い線の位置がおかしいぜ。

[20] 主筆嬢 08/03/25 00:35

いちいち細かいことを気にするな。

ケツの穴の小さい野郎だ。

[21] nabiki_t 08/03/25 00:36

またそういう下品なことを・・・・・・

それに、まだ説明を端折ってるところがあるぜ。

>>17で、頂点での濃度から「直線の端がどの辺上に存在するかが判る」と言っているけど、それはどうやって求めるんだ？　直感的にいって、簡単には求められそうにもない気がするが。

例えば、こういう風に閾値を超えている点が複数あった場合は、どうなるんだ？

[22] 主筆嬢 08/03/25 00:40

確かに、この馬鹿の言うとおり、どの辺に直線の端が存在するのか、あるいは、直線をどの辺からどの辺に向かって引けばいいのか、ということは簡単には求められない。というか、プログラムでは算出できないらしい。

だから、事前に考えられ得る全てのパターンを列挙して、どういうときにはどこからどこに線を引けばいいのかを定義しておく必要がある。

この場合、頂点は4つだから、組み合わせの数としては 2⁴ = 16 通り考えられる。回転や対称を除けばもっと少なくなるんだけど、元が16通りしかないから削減する意味は余りないと思う。

[23] 主筆嬢 08/03/25 00:45

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

特に難しいことはない。

[22] nabiki_t 08/03/25 00:52

ここまではな。

[23] 主筆嬢 08/03/25 00:55

この辺りで広告を入れておこうか・・・・・・

[24] nabiki_t 08/03/25 00:56

じゃぁ、今度は今までのことを踏まえて3Dに拡張してみようか。

できるのならな。

[25] 主筆嬢 08/03/25 01:00

やなやつ。

[26] 主筆嬢 08/03/25 01:01

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

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

2次元の時とほぼ同じ。

[27] 主筆嬢 08/03/25 01:02

ただ、一つ気を付けなければいけないのは、ポリゴンには表裏があるということ。

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

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

[28] 主筆嬢 08/03/25 01:06

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

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

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

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

[29] nabiki_t 08/03/25 01:07

横着するなよ。

[30] 主筆嬢 08/03/25 01:11

だって、面倒なんだもん。

[31] 主筆嬢 08/03/25 01:15

とりあえず、上記のことを元にサンプルのプログラムを作ってみた。

meta2.zip 86.9KB

gmview.zip 32.3KB

動かし方はまぁ、ソースを見ながら何とか推定して。

[32] nabiki_t 08/03/25 01:17

無茶なことを言うなよ・・・・・・

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

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

Ball2.txtは下記のように記述する。

X, Y, Z, 有効範囲球のサイズ, ボールのサイズ

一行でボール一つ分、複数行記述すれば複数個のボールが生成される。

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

[33] 主筆嬢 08/03/25 01:31

ところで、ここまで解説しておいて言うのは何だけど、このmarching cubes法という奴はすでに特許があるらしい。

でも、いろいろ調べると、いつ誰が特許を取ったのかというのは、いろいろな人がいろいろ言っててよく分からないけど、どうもそろそろ時効になっているらしい。（ここには2005年に失効と書いてる・・・・・・）

まぁ、個人で楽しむ分には多分、問題は無いと思うけど。

[32] 主筆嬢 08/03/25 01:32

あと、ついでだから、marching cubes法によく似たmarching tetrahedrons法とか言う方法についても、考えてみる。

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

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

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

[33] 主筆嬢 08/03/25 01:35

そうすると、格子一つをどのように分割するのか、ということが問題になる。

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

言葉で書くと、

1. 0-1-3-4の頂点からなる四面体
2. 1-2-3-6　〃
3. 1-4-5-6　〃
4. 3-4-6-7　〃
5. 1-3-4-6　〃

の5つとなる。

[34] 主筆嬢 08/03/25 01:37

それと、>>33の左右対称となるパターンも考えられる。

同じく、言葉で書くと、

1. 0-1-2-5の頂点からなる四面体
2. 0-2-3-7　〃
3. 0-4-5-7　〃
4. 2-5-6-7　〃
5. 0-2-5-7　〃

の5つとなる。

[35] 主筆嬢 08/03/25 01:40

ここで少し考えなくてはいけないことがある。それは、>>33と>>34のどちらの分割方法を使うべきかと言うこと。

なにやらどっちでも良さ様な気がするけど、実はそうではない。

>>33もしくは>>34のどっちか片方だけを使って全ての格子を分割する方にすると、ポリゴンがうまく生成できない。変な隙間が生じる恐れが出てくる。

なぜかというと、同じ種類の格子を隣接させると、隣接する四名対の辺が一致しない部分が生じるから。

[36] 主筆嬢 08/03/25 01:45

例えば、>>34の様に分割した格子を二つ並べると、下記のようになる。

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

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

[37] 主筆嬢 08/03/25 01:49

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

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

[38] 主筆嬢 08/03/25 01:53

だから、必ず>>33と>>34のパターンを交互に使ってやらなければならない。そうすれば、隣接する四面体の辺が一致して、不自然な隙間が生じることはなくなる。

[39] nabiki_t 08/03/25 01:56

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

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

[40] 主筆嬢 08/03/25 01:56

横着するな。

[41] nabiki_t 08/03/25 01:57

おまえに言われたくない。

[42] 主筆嬢 08/03/25 02:03

馬鹿は放っておいて、とりあえず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

[43] 主筆嬢 08/03/25 02:05

正直言って、marching cubes法と何が違うのかよく分からない。

とりあえず、プログラムを作るときに256通りのポリゴンの生成パターンを定義しなくても良いところが利点だろうか。

[44] 主筆嬢 08/03/25 02:10

でもまぁ、それっぽい結果がでたから、まっ、いいか。

[45] nabiki_t 08/03/25 02:13

最後はそれかよ・・・・・・。