three.jsでマーチングキューブによるメタボール表現を実装してみた (モバイルでも動くよ)

Takumi HASEGAWA (unshift Inc.)

2019年12月16日 07:00

※これはWebGL Advent Calendar 2019の16日目の記事です。
もともとはThree.js Advent Calendar 2019に書こうと思っていたんですが、すでに埋まっていたので。

前々からWebGLをレイマーチングではなく、ポリゴンによるメタボール表現をやってみたかったんですが、調べていたらどうやらマーチングキューブというものを使えばできるというところまでたどり着いたので、やってみました。

どうやら以下のアルゴリズムが有名らしいです。

しかしすでにQiitaに @aa_debdebさんの素晴らしい記事が上がっていたので、主に以下の記事を参考にさせていただきました。

あと、以下の記事も非常にわかりやすい説明でした。

マーチングキューブはめちゃくちゃざっくりいうと、3次元ボクセルデータをポリゴンデータに変換するものです。8つの隣接したボクセルがつくる立方体を1つの単位 (セルと呼ぶ) として考えます。

各ボクセルは値を持っており、そのボクセル値によってセルの辺上にどのように頂点を配置するかが決まり、その頂点によってポリゴンの面が作られます。

頂点の配置方法は、セルを構成する8つのボクセル値がある閾値 (等面閾値と呼ぶらしい) を超えるか超えないかによって決まります。なので1つのセルに対して2の8乗 = 256通りあります。

これはセル内のポリゴンの張り方を示した図です。15種類ですが、表裏を考えると256通りになります。

セル内に貼るポリゴンの数は最大5枚 (三角形ポリゴンなので頂点数は3)なので、たとえばセルの数が縦50 x 横50 x 奥行き50 の空間でマーチングキューブをする場合、

50 x 50 x 50 x 5 x 3 = 1875000

上記の数の頂点を予めシェーダに送り、ボクセル値によって描画する / しないを出し分けます。なのでセルの分割数を増やすと、結構すぐ重たくなります。。

その頂点の配置の仕方256通りを予めルックアップテーブルとしてデータ化し、参照できるようにしておくアルゴリズムらしいです。

また、ポリゴンの頂点が存在する場合、セルの辺を構成する2つのボクセル値によって辺上のどの位置に頂点が配置されるかも決まります。

実装してみたのがこちら↓です。
(と言っても @aa_debdebさんの実装をちょっと焼き直した程度ですが、、)

デモではDat.GUIを使用して、

・effectValue: エフェクトの適用度
・smoothUnionValue: メタボールの合成の滑らかさ
・numMarchingSegments: マーチングキューブ空間のセル分割数
・numSpheres: メタボールの個数
・isWireframe: ワイヤーフレーム表示
・sphereColor: 色

をいじれるようになっています。

※注意※
numMarchingSegmentsとnumSpheresを
増やしすぎると激重になります！

たまに上下左右が切れているように見えるのは、マーチングキューブの空間からはみ出しているからです。描画したい球が、セルのないエリアに飛び出しているため、ポリゴンがないため描画できません。

ソースコードはこちら↓。

この実装では、各ボクセル値を決定するのに、レイマーチングで使用するような距離関数を使用して、メタボールを実現しています。

セルの頂点を始点としたときの、描画したいオブジェクトの距離関数の値がそのままボクセル値になっており、等面閾値は0になります。(要はセルの頂点が描画したいオブジェクトの内側に入るか、外側に出るかを判断したいため。)

@aa_debdebさんの記事では素のWebGLで、かつGLSL ES 3.0で実装されていますが、今回はthree.jsを使用し、モバイルでも動くようにES 1.0で記述しています。

ではソースコードの抜粋を見てみます。まずは頂点の配置方法のルックアップテーブルのデータをテクスチャで生成する部分です。three.jsではDataTextureクラスという便利なものがあるので、それを使います。ルックアップテーブルのデータは4096個要素がある配列なので、4096 x 1のテクスチャに書き込みます。

ちなみに、「Polygonising a scalar field」では頂点のルックアップテーブル (triTable) は256 x 16の配列となっており、かつedgeTableというルックアップテーブルも使用して最終的な頂点の配置方法を参照していますが、@aa_debdebさんの実装ではtriTableを1次元の配列にし、edgeTableも廃して計算をシンプルにしています。なるほどな〜ってなりました。

// Javascript MarchingCubesクラスの中での処理
// DataTexture生成 
this.triTableTexture = new THREE.DataTexture(new Uint8Array(TRI_TABLE), 4096, 1, THREE.AlphaFormat);
this.triTableTexture.minFilter = THREE.NearestFilter;
this.triTableTexture.magFilter = THREE.NearestFilter;
this.triTableTexture.mipmap = false;

WebGL 1.0ではテクスチャはformatはUNSIGNED_BYTEくらいしか使えないのでDataTextureのformatは指定なし (省略するとTHREE.UnsignedByteTypeとなる)、typeはTHREE.AlphaFormatにしておけば、データ書き込みの際にテクセルごとに1要素だけで済みます(THREE.RGBFormatだと、RGBの3要素分のデータが必要)。

シェーダ側で値を参照するときはtexture2D関数の戻り値のa要素を参照すれば、値が取り出せます。ただし、値は0 ~ 1の範囲で格納されているので、255をかければ、もとの値が取り出せます。

// 頂点シェーダ内
// ルックアップテーブルの参照
texture2D(triTableTexture, vec2((cubeIndex * 16.0 + vertexIdInCell) / 4096.0, 0.0)).a * 255.0;

言い忘れていましたが、ルックアップテーブルで-1となっている値は、255としています(符号なしのため)。

続いてセルのボクセル値から、256通りのどのパターンになるかを算出するための計算ですが、ES 1.0だとビット演算子が使用できないので、定義しています。

// 論理和
int or(int a, int b) {
 int result = 0;
 int n = 1;
 for(int i = 0; i < 8; i++) {
   if ((modi(a, 2) == 1) || (modi(b, 2) == 1)) result += n;
   a = a / 2;
   b = b / 2;
   n = n * 2;
   if(!(a > 0 || b > 0)) break;
 }
 return result;
}

これによって、ES 3.0で

// GLSL ES 3.0
cubeIndex |= 1;

となっているところを

// GLSL ES 1.0
// こちらのコードではcubeIndexをfloatで定義しているので、intにキャストしています。
or(int(cubeIndex), 1);

と書き換えられます。

また、このアルゴリズムだとif文が多用されるんですが、あまり良くないとのことなので、step関数を使った記述に変えてみました。(体感的にはあまり変わりませんが、、どちらが良いのか教えて偉い人、、)

// ルックアップテーブルの参照

// まずはポリゴンの張り方の256通りのうちどのパターンになるか調べる
float cubeIndex = 0.0;
cubeIndex = mix(cubeIndex, float(or(int(cubeIndex),   1)), 1.0 - step(0.0, v0));
cubeIndex = mix(cubeIndex, float(or(int(cubeIndex),   2)), 1.0 - step(0.0, v1));
cubeIndex = mix(cubeIndex, float(or(int(cubeIndex),   4)), 1.0 - step(0.0, v2));
cubeIndex = mix(cubeIndex, float(or(int(cubeIndex),   8)), 1.0 - step(0.0, v3));
cubeIndex = mix(cubeIndex, float(or(int(cubeIndex),  16)), 1.0 - step(0.0, v4));
cubeIndex = mix(cubeIndex, float(or(int(cubeIndex),  32)), 1.0 - step(0.0, v5));
cubeIndex = mix(cubeIndex, float(or(int(cubeIndex),  64)), 1.0 - step(0.0, v6));
cubeIndex = mix(cubeIndex, float(or(int(cubeIndex), 128)), 1.0 - step(0.0, v7));

// 続いて現在の頂点がどの辺上に配置されるかを調べる
// つまり、ルックアップテーブルのどの値を参照するかのインデックスを求める
float edgeIndex = texture2D(triTableTexture, vec2((cubeIndex * 16.0 + vertexIdInCell) / 4096.0, 0.0)).a * 255.0;

また、ちょっとボクセル風になるエフェクトも (Dat.GUIの一番上の値を動かしてみてください)追加してますが、今回の本質とは関係ないので説明を割愛します。エフェクトは↓のような感じ。

Marching Cubes Metaball with https://t.co/xdBPn2qoiv key visual-ish effect.
ホムンクルスさんのキービジュアルで使用しているようなボクセル風エフェクト。#webgl #threejs #glsl #shader #creativecoding #generativeart #generativedesign #marchingcubes pic.twitter.com/rFU3sIhT0s
— Takumi Hasegawa (@_unshift) December 11, 2019

また、距離関数の詳細も詳しくは説明しませんが、numSpheresで渡ってきた数の分、ランダムに動く球を合成しています。ランダムな動き方は、randomValuesというuniform変数に、球の個数分のvec4にJavascript側で生成したランダムな値が入っているので、それを使用して適当に動かしています。

フラグメントシェーダでは、頂点シェーダから法線と頂点を破棄するかどうかの値を渡して、破棄する場合はdiscardし、描画する場合はフォンシェーディングで色を付けてます。

// フラグメントシェーダ
void main(void) {
 if (vDiscard == 1.0) {
   discard;
 } else {
   vec3 n = normalize(vNormal);

   vec3 light = normalize(LIGHT_DIR);
   vec3 eye = normalize(cameraPosition - vPos);
   vec3 halfLE = normalize(light + eye);
   float diffuse = clamp(dot(n, light), 0.3, 1.0);
   float specular = pow(clamp(dot(n, halfLE), 0.0, 1.0), 50.0);
   vec3 color = sphereColor * vec3(diffuse) + vec3(specular);
   gl_FragColor = vec4(color, 1.0);
 }
}

あとはそこまで大きく変わらないです。全貌はGitHubのソースコードを見ていただければと思います。

・・・

↓こちらの記事でもマーチングキューブでメタボールを実装しているようなのですが、まだちゃんと読み込んでないとはいえ、どういう実装かよくわかってないです。本質的には同じなのかな？？

・・・

WebGLでマーチングキューブの需要があるかどうかは怪しいですが、自分なりに解釈して説明してみました。記事に書くことによって理解が深まったので、個人的には満足しています。

そして実はQiitaのアドベントカレンダーに初参戦でした。(noteに書いてますが。。)

長くなってしまいましたが、以上です。
最後まで読んでいただきありがとうございます。

サポートいただければ、レッドブルを飲んでより頑張れると思います。翼を授けてください。