LIFE LOG(MochiMochi3D)

MochiMochi3D

3D関係の記事を書きます

Grid Traversal ~Repeatでぶっ壊れないRaymarchingの仕方~ & SESSIONS 2024の話

この記事はSESSIONS Advent Calendar 2024 - Adventarの12/15の記事です。レイマーチングにおいてRepeat時にSDFがおかしくなる現象を防ぐGrid Traversalという手法& SESSIONS 2024で提出した作品の解説を行います。

RepeatとOvershooting

SDFに渡すPositionにmodを作用させることでSDFを無限に並べられるRepeatというテクニックはレイマーチングをしている方ならお馴染みかと思います。

これだけでも楽しいものですが、慣れてくるとRepeatしたSDFになんかランダム性を加えたくなってくるところです。RepeatしたBoxをそれぞれOffsetをランダムに与えて地形的なものを作ったり、1つごとにSDFを変えたりとか、空間ごとにユニークな要素を追加したら中々面白そうです。

ですが、これを実際に実装してみるとなんかめちゃくちゃバグった結果が出てくることが多いです。例えばRepeatしたBoxをそれぞれOffsetを加えてレイマーチングしてみるとこんな感じでちらほら穴が開いてとてもじゃないがきれいじゃない結果が得られます。恐らくこのような経験をした人は多いのではないでしょうか(私も昔やらかしました)

段差がきれいにでない

www.shadertoy.com

何故こんなことが起きるのかというとRepeatしたSDFはSDFとして不確かな距離を返しているためです(もはやシーンのSDFとは言えない)。基本的にRepeatしたSDFの評価は自分がいるグリッドの空間しか見ておらず、隣のグリッドはどうなっていようが無視しています。極端な状況では以下の図のように隣のグリッドのSDFと非常に近い状況であっても、現在いるグリッドのSDFしか見ないため結果としてSDFを貫通するような大きい距離を返してしまうということになります。このような本来のSDFより大きい距離を返してしまうことによってSDFを貫通してしまう現象をOvershootingと言います。

Overshootingの例

回避方法として隣のSDFを評価して正確にSDFを計算するという手もありますが、SDFの評価が重くなりがちというのもあるのであまりやりたくはありません(隣接だけでも単純に考えて4倍,6倍とかになる)。そこでシェーダー芸ではレイの進む距離に制限をかけるGrid Traversalという手法が一般的に用いられています。

Grid Traversal

結局RepeatによるOvershootingは隣のSDFがどうなってるかわからないのに隣のグリッドにガンガン進んでしまうことが原因でした。なので、レイが行き過ぎないように一旦現在のグリッドの境界線でレイを止めてしまえば、隣のSDFがどうなっていようが安全に進むことができます。Grid Traversalの考え方はまさにこれで、レイマーチングにおいてグリッドを超える際に一度グリッドの境界で止めるように距離に制限をかけるという手法です。

Grid Traversalのイメージ

Grid Traversalの流れとしては以下のようにレイのstepについてちょっとだけ処理が増える形になります。

  1. 現在の位置からGridの境界までの距離 d_{grid}を計算
  2. SDFの計算(通常通り) d_{sdf}
  3. レイの進むstep距離を d_{grid}, d_{sdf}の小さい方にする

結構シンプルでほんまか？となるかもしれませんが実際にshaderを書いてみると確かに想像通りの結果が出てきます。

www.shadertoy.com

Grid Traversalの実装

Grid Traversalの実装は0v5vr氏のshaderを元に制作いたしました。(いつもお世話になっております...)

www.shadertoy.com

では、Grid Traversalの処理を一つ一つ追っていきましょう。今回はxz平面でグリッド作る形で実装を行っています。実際にGrid Traversalで追加した&変更したコードはこんな感じです

vec2 gridCenter;
float gridTraversal( vec2 ro, vec2 rd) {
   gridCenter = floor( ( ro + rd * 1E-3 )) + 0.5;
   
   vec2 src = -( ro - gridCenter ) / rd;
   vec2 dst = abs( 0.5 / rd );
   vec2 bv = src + dst;

   return  min( bv.x, bv.y );
} 
float map(vec3 p)
{
    // Repeat
    // vec2 gridId = floor(p.xz);
    // p.xz = mod(p.xz, 1.0) - 0.5;

    p.xz -= gridCenter;

    // float offset = hash12(gridId) * 1.0;
    float offset = hash12(gridCenter) * 1.0;

    float d = sdBox(p + vec3(0,offset,0), vec3(0.5,2.0,0.5));
    return d;
}
    // Raymarching
    vec3 pos = ro;
    float d = 0.0;
    for(int i = 0; i < 100; i++){
        float limitD = gridTraversal(pos.xz, rd.xz);
        d = map(pos);
        if(d < 0.001) 
        {
            col = getNormal(pos) * 0.5 + 0.5;
            break;
        }
        d = min(limitD, d);
        pos += rd * d;
    }


まずはGrid Traversalがやっていることを見ていきましょう。Raymarchingのコードを見るとgridTraversalという関数がlimitとなる距離を返しており、レイのstep距離について制限をかけていることがわかります。これが先ほど言っていたGrid Traversalの処理であるわけですね。

d = min(limitD, d);

map関数の部分ではちょっと違いとしてはgridの中心点で相対座標を作っているというぐらいですね。これ自体はそうした方がGrid内のSDFが書きやすいので沿いうしているだけなのであまり気にしないでください(Gridのサイズが変わっても同じようにかけるので。別にmodで座標を合わせても問題はないです)。

    p.xz -= gridCenter;


これでレイマーチング側の変更は以上となります。では本筋となるGridの境界線までの距離を求める関数gridTraversalの内容に入っていきましょう。今回は2次元のGrid Traversalを考えるため、二次元の位置ro,方向rdを受け取って計算していきます。最初はまずGridの中心点について求めています。

vec2 gridCenter;
float gridTraversal( vec2 ro, vec2 rd) {
   gridCenter = floor( ( ro + rd * 1E-3 )) + 0.5;

ここからroからrdを放った時、境界までの最短距離を求めていく処理になります。これが多分一番わかりにくい部分なので一つ一つ何を表しているか見ていきましょう。

   vec2 src = -( ro - gridCenter ) / rd;
   vec2 dst = abs( 0.5 / rd );
   vec2 bv = src + dst;

この中でわかりやすいのはdstという変数です。これは中心点からrdの方向へとレイを放った場合の各軸の境界線までの距離を計算しているというものです。説明だけ聞いてもなんとなくピンとこないかもしれないので1を方向ベクトルで割った1/rdという量を考えてみます。

方向ベクトルrdというのはそもそも「レイが1の距離を進んだ時、xとy座標がどれだけ進んでいるか」ということを表す量です。その逆数である1/rdというのはその関係性が逆転することですから、1/rdは「レイのx,y座標が1進むのに必要なレイの進行距離」を表す量であるというわけです。

方向ベクトルの逆数が表すこと

中心点から各軸の境界線は各々の軸でどれも0.5だけ離れているわけですから、ここからrd方向にレイを放つと各座標が0.5だけ進んだ時のレイの進行距離がそのまま各軸の境界線までの進行距離ということになります。それが0.5/rdの結果であるわけです。

また、レイがの符号が変わろうとも結果として出てくる距離(の絶対値)自体は変わらないので、ここでは方向の符号の依存性をなくすためabsを付けて結果に符号がないようにしています。

こんな感じでdstの意味は分かりましたが、私たちが欲しいのは中心点ではなくroという点から放った時の進行距離です。中心点の結果dstからずれればそれだけ結果も変わるはずです。その差分をここではsrcとして計算しており、最終的にはdst + srcが求めたかった原点ro,方向rdのレイと各軸の境界線までの進行距離となります。

そう言うことでsrcを細かく見ていきましょう。srcはまずレイの原点からグリッドの中心点を引いたベクトル( ro - gridCenter )を作っています。これは図的にはグリッドの中心からroに引いたベクトルを作っているということですね。

そのベクトルだけレイを平行移動させた時、進むべきx,y座標が0.5から変化することになります。平行移動によって減った(または増えた)x,y座標の変化量は(ro-gridCenter).x,y)となります。なのでこの変化量に応じて、減るべき(増えるべき)レイの進行距離は先ほどの1/rdの考え方を用いれば(ro-gridCenter)/rdと表されるわけです。あとはこれを引けば丁度原点roからはなった場合の進行距離となりますのでマイナス符号をつけてあげてsrcの計算が完了します。

ということで以上で必要な計算がほぼ完了しました。roからの各軸の境界線までの進行距離はdst + srcであり、それがbvという変数で格納されています。ここまでの計算はx軸,y軸独立して計算されていてbvの各x,yにその情報が入っています。この内で最も進行距離が短いものを採用すればいいので最後の処理としてminを使って最小値を返しています。

   return  min( bv.x, bv.y );

以上でgridTraversalの処理は終わりです。ぱっと見た感じだと何やってんだ見たいな気持ちにはなりますが、一つ一つ処理を追っていくと結構やってることはシンプルというかなんだか意外と簡単と感じると思います。

Grid Traversalの作例

2次元でやるのはもちろんですが、別に3次元でも同じような処理になるのでこんな感じでGridを3次元にすることも可能です

vec3 gridCenter;
float gridTraversal( vec3 ro, vec3 rd) {
   gridCenter = floor( ( ro + rd * 1E-3 )) + 0.5;
   
   vec3 src = -( ro - gridCenter ) / rd;
   vec3 dst = abs( 0.5 / rd );
   vec3 bv = src + dst;

   return  min(min( bv.x, bv.y ),bv.z);
}

www.shadertoy.com

また、gridのサイズを変える場合はこんな感じになります。(サイズ分だけ距離が遠くなるだけ)

vec2 gridCenter;
float gridTraversal( vec2 ro, vec2 rd,vec2 size) {
   gridCenter = (floor( ( ro + rd * 1E-3 ) / size) + 0.5)*size;
   
   vec2 src = -( ro - gridCenter ) / rd;
   vec2 dst = abs( 0.5 * size / rd );
   vec2 bv = src + dst;

   return  min( bv.x, bv.y );
}

www.shadertoy.com

Grid Traversalの注意点

当たり前の話ではありますがGrid Traversalはグリッドで止められる以上レイの進みが結構遅いです。遠くに行くレイはぶつかりもしないグリッドでも一々止められてしまうため、普通のレイマーチングに比べたらあまり遠くまで行くことができません。なのでStep数には結構注意して取り扱う必要があります。

あと実装の細かい話ですが、Gridの飛び越しについてはちゃんと小さいoffsetを付けてあげないと一生同じGridにとどまり続けてしまうみたいなことがあるのでその辺は注意してください。

(あとなんかあったかな・・・)

発展的なTraversal

Grid Traversalの根幹は「ループさせる領域の境界で止めてあげる」というものでありましたが、これ自体はGridだけに限る...というわけではないはずです。ループ形状が異なっても、その領域の境界までの進行距離がわかればovershootingを防げるというのは変わらないはずです。つまりは境界までの進行距離を求められるのであれば、任意の形状でも同様のTraversalを考えることができます。

ということでそんなGridから離れたTraversalをちょっと紹介します(あんまり私もわからないので簡単な紹介程度にさせて頂きます)。

Hexagonal Grid Traversal

六角柱の領域でTraversalを行っている手法、六角柱に対するIntersectの処理はあるので多分それを使って進行距離を求めていると思います

www.shadertoy.com

おそらくこのhexagonal prismの式を使って境界の計算をしている(はず...) iquilezles.org

QuadTree, OctTree Traversal

Gridを再帰的に分割したQuadTree, OctTreeに対するTraversal手法です。 (0b5vr氏の実装はraymarchingではないので今回のとはちょっと離れると思いますが、一応原理的には近いはずなので記載)

www.shadertoy.com

www.shadertoy.com

SESSIONS 2024に出した作品の簡単な解説

ここから先はSESSIONS 2024の話になるのでGrid Traversalだけ見たい方はもう大丈夫です。

なんでGrid Traversalの話をしたのかというと、SESSIONS 2024で出した作品はめちゃめちゃGrid Traversalを使っていた背景があったためです。なので簡単に今回作った作品がどんな感じで作られていたのか&Grid Traversalをどう使っていたのかを話していこうと思います。

SESSIONSに出した作品は二つあって、code graphicsでは「Dance Floor」、realtime graphicsでは「block」(4k executable)というものを出しておりました。コードはgithubに上げましたので興味ある方はどうぞ

github.com

Dance Floor

youtu.be

(かなり重いシェーダーなので注意) t.co

テーマはもちろん名前の通り「ダンス」で、ピクトグラムがダンスフロアでダンスしまくるというものになっています。

ダンスしているピクトグラム(?)はどうやって作っているのかというと頭や関節部分に点を考えて、それをつなげるカプセルのSDFをめちゃめちゃ用意して作っています。それで関節点をいくつか用意してダンスのポーズを取らせていたという感じです。

    float headD = sdSphere(p - headPoint,head);
    d = min(d,headD);

    float upperArmRD = sdCapsule(p,upperArmR,elbowR,limb);
    float lowerArmRD = sdCapsule(p,elbowR,handR,limb);
    d = min(d,upperArmRD);
    d = min(d,lowerArmRD);

    float upperArmLD = sdCapsule(p,upperArmL,elbowL,limb);
    float lowerArmLD = sdCapsule(p,elbowL,handL,limb);
    d = min(d,upperArmLD);
    d = min(d,lowerArmLD);

    float upperLegRD = sdCapsule(p,upperLegR,kneeR,limb);
    float lowerLegRD = sdCapsule(p,kneeR,footR,limb);
    d = min(d,upperLegRD);
    d = min(d,lowerLegRD);

    float upperLegLD = sdCapsule(p,upperLegL,kneeL,limb);
    float lowerLegLD = sdCapsule(p,kneeL,footL,limb);
    d = min(d,upperLegLD);
    d = min(d,lowerLegLD);

    float upperBodyD = sdCapsule(p,upperBody,lowerBody,body);
    d = min(d,upperBodyD);

    return d;
}

どうやってダンスのポーズを作ったのかというとBlenderで同じようなモデルを作って、Blender上で作ったポーズの各ボーン点をアドオン(ChatGPTに書いてもらいました)で書き出して、それをShaderに埋め込むというような手順でやっていました。

Blenderで作ったモデル

ダンスのポーズは友達のlox9973さんに考えてもらいました。SDF作っていたら普段loxさんがダンスするときに使ってるアバターに似ていたので、唐突に夜に呼び出して「なんかかっこいいポーズ取って」とお願いしてやってもらいました(ありがとうございました&すいませんでした)。VRChat上でポーズを取ってもらい、それを見ながら私がBlenderでポーズを作りました。

ダンスポーズはもっと作って連続に動くようにしたかったところなのですが、どうも4つ以上になるとコンパイルがかなりかかるようになり、(前回コンパイルが通らないレベルまで書いて怖くなった思い出があるので)結局3つに抑えて補完することにしました。

あと、各々ダンサーが違うポーズをさせたかったのですが、それをしてみるととんでもなく遅くなりました。恐らくDivergenceってやつだと思います(Data Divergenceでしょうか?)。スレッドごとに違うことをさせるのは危険ですね。

Lightingはいつも通りパストレベース、ダンスする場所はGrid Traversalで作ってGridのIDを頑張って制御してピクトグラムを配置しています。制作時間は3~4日ぐらいでした。


当初は音ゲー的なのを考えていましたが制作期間的に断念しました(これをやれなかったのはちょっと公開しています)。あと、ダンスである以上音楽との同期がやっぱ必要だったなと思います。Demoとして出すべきだったかも...

block

block

せっかくGrid Traversalを覚えたんで、なんかVoxelっぽいの作りたいな～と思い、なんとなくレゴが頭に浮かんだのでVoxel&Legoの4k executableを書こうという感じでblockを作りました。

各GridにはVoxelかどうかのフラグを考え、Voxel用のSDFの中にGridがあるかどうかを判定してVoxelとしてBoxを配置するというような流れになっています。地形はノイズ、SESSIONSの文字は頑張って2D SDFを作ってそれをExtrudeする形で作っています(何気にExtrudeの存在を初めて知った)。Extrudeはiq先生の以下の記事にあります。

iquilezles.org

それでレゴっぽくしたいのでVoxelの上に円柱を置くような実装をしました。これは単純に下にVoxelが存在していたら付けるみたいな感じの実装です。

ライティングは例のごとくパストレーシングです。Microfacet(GGX)とLambertの複合BRDFを考えてOneSample MISをしています。ちゃんとアンバイアスに作っているのでレイトレ警察も安心！

今回はまじめなThin-Lensを実装して、しかも六角形絞りを実装しました。なのでよく見るとボケがちゃんと六角形になっています(正直よくわからんと思う)。絞りの実装はレンズ上に六角形のSDFを置き、そのSDF内に存在するレイだったらちゃんとレイを放ち、そうでなければ消すというような感じで実装しています(昔薄レンズの記事を書いた時にやった覚えがあったので)。

六角形ボケ

制作期間は3日でした。この時期は(諸々が重なって)限界を迎えており題名の適当さからかなりヤバかったことが伺えます。


SESSIONSでは4kexeの規定があまりなかったのでRevisionルールに合わせてレンダリング時間は30秒にしたのですが、なかなかノイズが多くて厳しさを感じています。ナイーブなパストレでは複雑なシーンはやはり限界があるので、もう少し高速化or簡易的なライティング手法を考えなくてはいけないなと感じます(確率的手法を抑えるようにしたい)。

Shader Jam

デモシーンイベントではリアルタイムにシェーダーを書いていく様子を見てワイワイするShader Jamという催しがあります。今回のSESSIONSでもShader Jamがあり、私はこちらに登壇者として参加させて頂きました。人生で初めてのShader Jamだったのでなかなかに緊張しましたが、なんとかやろうとしていたこと(パストレ)ができたのでとても楽しかったです。

youtu.be

参加のお誘いは開催の1週間ぐらい前に運営の方から「やってみないですか」みたいな感じで頂きました。まさか自分がShader Jamの参加者になれるとは思っていなかったのでびっくりしましたが、またとないチャンスということで参加をすることにしました。

とはいえライブコーディング自体も初めてだったのでBonzomaticもちゃんと触ったことはないし、全く作品のアイディアもないしどうしよ～となっていました。開催までの一週間はとにかくネタの仕込みとライブコーディング自体の練習を毎日繰り返して、何とか本番に臨みました。

作品について

Shader Jam(というかライブコーディング)ではBonzomaticというソフトが使用されます。現在では本家のバージョンとComputeバージョンがあり、SESSIONSのShaderJamは後者を採用していました(近年のデモシーン界隈ではComputeが使われているイメージ)。

本家 github.com

Computeバージョン github.com

Computeバージョンの特徴はシェーダー内でランダムアクセスできるComputeTextureというものがあるとこです。これのおかげでバッファリングや疑似的にパーティクルの描画といった表現が可能で3つあるので色とかも保存可能です。ただちょっと仕様が面倒くさい部分があり、Compute TextureはUintの1チャンネルしか持ちません。なのでfloatの値を入れるには255かけて整数にしたり、ビットごと突っ込むみたいなことをする必要があります。(なぜか書き込む際はチャンネル4つ入れなければいけませんが、記録されるのは結局最初の1チャンネルだけ)

私は今回パストレーシングするということでCompute TextureをAccumulation Bufferとして使用していました。ただ、Compute Textureの仕様のためパッキング処理を挟んで使っていました。

Accumulation Bufferは色の累計と累計回数を保存する必要があるため、ちゃんとやるには4チャンネル必要なのですが、Compute Textureで記録できるのは1チャンネルのTextureが3つなので合計で3チャンネルしか使えません。なのでBを保存するCompute Textureの8bitに累計回数を突っ込むようなパッキング処理を以下のように書いていました。

uvec3 pack(vec4 p){
    uvec3 s = uvec3(p.xyz * 255.0);
    s.z = (s.z << 8) | (uint(p.w) & 0xff);
    return s;
}

vec4 unpack(uvec3 s){
    vec4 p;
   p.xy = s.xy / 255.0;
  p.w = float(s.z & 0xff);
  p.z = (s.z >> 8) / 255.0;

    return p;
}

void store(vec4 col, ivec2 idx){
  uvec3 s = pack(col);
  imageStore(computeTex[0],idx,s.xxxx);
  imageStore(computeTex[1],idx,s.yxxx);
    imageStore(computeTex[2],idx,s.zxxx);
}

vec4 load(ivec2 idx){
  uvec3 s = uvec3(
    imageLoad(computeTexBack[0],idx).x,
    imageLoad(computeTexBack[1],idx).x,
    imageLoad(computeTexBack[2],idx).x
  );
  
  return unpack(s);
}

ライブコーディングということ当たり前のことですが間違えにくいコードにすることを念頭に設計を考えていました。私個人としては以下のことが大事かなと思います。

  • (1) 原理を知っている手法を使う
  • (2) 固定値を分かりやすい形にする
  • (3) いくつかテストとなる表現を入れるようにする

(1)は当たり前なんですが、原理を知らない手法だと暗記も厳しいですし間違いがあった瞬間全てが狂います。本番で間違いを見つけるのは本当に厳しいのでできる限り、書いてあることが全てわかるような手法にすべき(理解するようにする)だと感じます。SDFとかは特に式の意味を理解しておくといい気がします。

(2)については円周率とかハッシュの固定値を分かりやすい表現を考えておくという感じですね。円周率は良くライブコーディングではacosを使って書かれることが多いのでそれに従いました(これ2piですが)

const float TAU = 2.0 * acos(-1.0);

ハッシュ関数には個人的にわかりやすいiq先生のXOR Hashを使わさせて頂きました。Sin Hashは結構数値によっては周期性が出てきてしまうのでビット操作系のハッシュの方が良いかと思います。ハッシュ関数で使用される固定値は割と何でもよかったので0x20242024uみたいな値を使いました。事前にそういう覚えやすい値が使えるのかというのも確認しておくのが重要だと思いました

#define C_HASH 0x20242024u

vec3 hash33(vec3 p){
  uvec3 x = floatBitsToUint(p);
  x = C_HASH * ((x >> 8)^x.yzx);
    x = C_HASH * ((x >> 8)^x.yzx);
    x = C_HASH * ((x >> 8)^x.yzx);
  return vec3(x) / float(-1u);

www.shadertoy.com

あと地味な所ですがhash33から始めて次元を落としたhashはhash33から部分的に取るようにすると簡単な気がします

vec2 hash21(float p){
  return hash33(vec3(p,1.0,2.0)).xy;
}
float hash11(float p){
  return hash33(vec3(p,1.0,2.0)).x;
}

(3)については、何度か練習しているとやっぱり一発でコードを通すのは難しいので段階的なテストができるような演出を考えておく必要があると思います。今回の場合、私は「HashのテストとしてのTextureいじり」、「Accumulation」、「Raymarhicngのテストとして法線表示」、「パストレーシング」というような感じで確認していました。

やってみた感想

今まではShader Jamを見る側だったので気づかなかったですが、やってみるとShader Jamは

  • 割とカジュアル
  • カンペを見てもいいし、事前に書いててもいい
  • みんなで変なシェーダーを書いてワイワイするのが目的
  • あと別に完成させなくても怒られはしない

と意外とかなり自由な雰囲気で面白かったです(やっている人が大体強いせいで敷居が高そうに見えますが)。コンペというわけでもないので好き勝手にできるというのも面白いです。

参加者となると他の人の作品をずっと見ることはできないので、時たま実装がひと段落ついてはちょっと見ていたのですが、実装が早い人はそのわずかな時間でも絵がガラッと変わっており、「えっちょっと見ないうちになんかすげえことになってる」みたいな驚きがありました。これは中々に楽しかったです。

参加者にならないと味わえない楽しさがあるので、是非興味がある人はやってみてほしいです(多分運営の人にやりたいですみたいなこと言えば行けると思います)。

おわりに

ここまで読んでいただきありがとうございます。私も昔はRepeatやGrid Traversalに悩まされたものですから、この記事で理解が進んで頂ければ幸いです。

今年のSESSIONSも非常に楽しかったです！また次の開催を楽しみにしています