ボロノイ！シェーダーでボロノイをあそぼう！！～理論とかはいいからとにかく使い方を知りたい～

https://gyazo.com/e0adb7da5100969534b28bbd46e47779

https://gyazo.com/a87d0790c64f02a933e8dd49c2cfe9be

2019/08/02 (金) 19:00 - 22:00@pixiv Inc.

LT資料

TODO: ここにunitypackageのリンクを貼ります

LTあんちょこ資料

発表者

さやちゃんぐbot

全手動botです

ノイズについて良く知らないので今日は勉強させてもらうつもりでやって参りましたが、今はなぜか壇上におります

誰？

無職

ノイズ？

ボロノイはガンに効く

ノイズ？

今日はボロノイをシェーダーで使う話を雑にします

このLTの想定視聴者

ステンドグラスを作りたい人

災害対策に利用できるアルゴリズムを知りたい人

シェーダーでお絵描きをしたい人

ガンの対策方法を知りたい人

ノイズ？

さやちゃんぐbotスクラップスというページにいろいろなノイズの名前が載ってるらしい

ボロノイ？

さやちゃんぐbotスクラップスってところでボロノイについて書かれてるらしい

歴史

ホワイトノイズ、バリューノイズ、パーリンノイズ、ワーリーノイズ、ボロノイといった流れで発展してきました

ボロノイ？

セルラーボロノイ(細胞っぽいボロノイ図)

https://gyazo.com/d844842c22d8079f8f3ce42f493a8eed

ボロノイ？

作り方

近くの点をつないで三角形を作ります

垂直二等分線を書きます

おしまい

https://gyazo.com/d0c12a7dee3800c5497652e30886f458

この操作を何回か繰り返すと、形が整ったきれいなトポロジーになっていきます

みなさんもボロノイのアルゴリズムを使っていいかんじのリトポツールを作ってみてください

円錐をたくさん平面にプロジェクションする描き方とかもあります

https://www.alanzucconi.com/wp-content/uploads/2015/10/cones.gif.gif

Fortune's algorithm

https://upload.wikimedia.org/wikipedia/commons/0/0c/Fortunes-algorithm-slowed.gif

ドロネー分割

ボロノイ？

立体錯視(明大博物館@神保町)の杉原先生の本とかを読むと良いです

わたしはまだ買えていない

ほしいものリストに入れたまま手をつけられずにいるっ

ボロノイ？

ボロノイはある地点からある地点までの最短距離を可視化するので、地理とか交通とか都市計画のジャンルで活用されているっぽいですね

ハザードマップ上の避難場所をもとに地図をボロノイ分割すると、自分が住んでいるところからどこに避難すればいいかがわかります

ゲームの分野だと、砕けた大きな岩を分割するのに利用できます

Unityシェーダーの記事でおなじみ、アラン・ズッコーニのボロノイの記事が役に立ちます

ボロノイ？

Houdiniには標準でボロノイを使えるノードが用意されていて、3Dモデルを簡単に爆発四散させることができます

https://gyazo.com/bc0096078d91a5b45465c6ddc75bd76e

https://gyazo.com/1ecd62126cfec06d7341713572b470b7

やり方

Houdiniを起動します

Tabキーを押してテストジオメトリを表示します

テストジオメトリを選択してModelメニューのShatterを選ぶとボロノイのノードが出てきます

explodedviewノードを出してボロノイのノードからつなげます

Grasshopperにもボロノイのノードがありますね

ボロノイ？

そんなことよりシェーダーでお絵描きしたい

https://gyazo.com/c6f05280b29a301af135bbb955819bff

与えられたuv座標をバリューノイズ的に整数部と小数部に分解してハッシュを適用したランダムな点を決めて、3x3のマス目で勾配を求めていいかんじに補間して最短距離を求める処理を行うイメージ

この関数はチェビシェフ距離で行われたボロノイ実装

距離の出し方のアルゴリズムの違いでボロノイにはいくつかバリエーションがあるっぽいです

ユークリッド距離とかマンハッタン距離とか。距離ということばが出てきたあたりで馴染みがあると感じた方は、おそらく機械学習でクラスタリングをやったことがあるのではないでしょうか

ボロノイ？

カールスルーエ距離でのボロノイを実装してみた

https://gyazo.com/afba9daa298875e1e0d339f4bf222f4e

距離？

ユークリッド距離→目的地までまっすぐ進む

マンハッタン距離→京都とか札幌みたいな碁盤目状の道を縦横に進む

チェビシェフ距離→縦か横のより遠い方を採用する

カールスルーエ距離→中心に進む直線ルートと、同心円上の弧を進む距離を組み合わせた最短距離を採用する

※θ==2.0の時に弧を進むのと、直線を2本進距離が等しくなる

https://gyazo.com/2a0c467e0a2066353d3f8812fedce0bb

https://gyazo.com/960c74efe2cb3e1465c0c507ab2ee373

https://gyazo.com/a582946c19f1ebf29ea6d52252a4f8d2

https://gyazo.com/ae97cb64dac74d9bd3fe833715c37d3c

シェーダーのお絵描き？

関数ひとつで細かいディテールを描ければ、なんかかっちょいいシェーダーを作るのが楽になります

三次元だとメンガー、マンデルボックスなど、マンデルブロ集合を使うのが良いかもしれません

制御の難易度はともかく

二次元だとボロノイがオススメです ※三次元のボロノイもあります

境界までの距離に応じて色をつけたり、領域ごとに色を変えると独特なルックになります

世の中には何も見ないでボロノイをシェーダーライブコーディングで書いてしまう人もいます

ボロノイ？

シェーダーでボロノイを扱うことについては、iq神が素晴らしいドキュメントと実装を公開しています

The Book of Shadersを読むことも役に立ちます

ボロノイ？

ボロノイの計算は、バリューノイズ、パーリンノイズの兄弟みたいなかんじです

code:zero2one.GLSL

float a = random(i);

float b = random(i + vec2(1.0, 0.0));

float c = random(i + vec2(0.0, 1.0));

float d = random(i + vec2(1.0, 1.0));

ボロノイ？

ボロノイのはじめの実装では欠点がありました。境界がうまく判断できないケースがあるのです。

先に示したボロノイ関数が戻すものは、2番目に近い距離と1番近い距離の差です。

3x3のマス目をループで処理し終わった後、もし最小距離の点がふたつ見つかったら？

return res.y - res.x;

ここでわれわれは驚くべき事実に気が付きます。

同じ値から同じ値を引き算すると、なんとゼロになってしまうのです。

結果として境界がわからなくなってしまいます。

ボロノイ？

ボロノイで境界がわからなくなるというのは問題です。もしボロノイでお絵描きした時にこれが発生すると、あやふやな領域が発生してルックが悪くなります。

改良するやり方はあるのでしょうか？

iq神はすかさず勾配を使うやり方を紹介しつつも(レイマーチングでおなじみの法線を求めるやり方です)、ボロノイの計算をあと余分に3回行う必要があるので重い処理になることを指摘しています。

vec2( f(x+h.xy) - f(x-h.xy), f(x+h.yx) - f(x-h.yx) )

ボロノイ？

最終的な改良版では、3x3のマス目でのループで一番距離が近いセルを特定した後、そのセルに対して追加で同様のループを処理するというやり方で実現されています。

※2回目のループでは5x5のセルを対象に行う

ループが増えたのでもちろん重くはなりますが、計算時間は一定だし十分な速度で動作します。

ボロノイ？

HLSLのボロノイで色を塗る

code:VoronoiColorize.HLSL

// Unityのunlitシェーダーでボロノイを描くコード例

float o = 0.25;

float3 r = float3(o, 0, 0);

float3 g = float3(0, o, 0);

float3 b = float3(0, 0, o);

float v = Voronoi(10 * i.uv);

float3 col = (0, 0, 0);

// ボロノイの値によって(距離に応じて)色を塗り重ねる

col = col + step(v, 0.01) * b + step(v, 0.1) * g + step(v, 0.3) * r;

col = col + step(v, 0.01) * b + step(v, 0.1) * g + step(v, 0.3) * r;

col = col + step(v, 0.4) * b + step(v, 0.5) * g + step(v, 0.6) * r;

col = col + step(v, 0.7) * b + step(v, 0.8) * g + step(v, 0.9) * r;

return fixed4(col, 1);

ボロノイ？

こんな絵を描いた

https://gyazo.com/69e2422ffafed6d3504a745029e5afe8

ボロノイ？

ぼくのすきなかっこいいボロノイ

みどりはめにやさしい。

https://gyazo.com/5eecf4147d2afdfb40adb6231e368e30

ボロノイ？

ぼくのだいすきなFlopineさんのかわいいステンドグラス的なボロノイ

https://gyazo.com/133443fdf75da92ee9842c1749449b00

Flopineさんはドイツで行われた2019年のデモパーティRevisionのシェーダーライブコーディングバトル決勝戦でボロノイを描きました

ボロノイ？

コードを見てみる

code:FlopineVoronoi.GLSL

vec3 voro (vec2 uv)

{

vec2 uv_id = floor (uv);

vec2 uv_st = fract(uv);

vec2 m_diff;

vec2 m_point;

vec2 m_neighbor;

float m_dist = 10.;

for (int j = -1; j<=1; j++)

{

for (int i = -1; i<=1; i++)

{

vec2 neighbor = vec2(float(i), float(j));

vec2 point = rand(uv_id + neighbor);

point = 0.5+0.5*sin(2.*PI*point+time);

vec2 diff = neighbor + point - uv_st;

float dist = length(diff);

if (dist < m_dist)

{

m_dist = dist;

m_point = point;

m_diff = diff;

m_neighbor = neighbor;

}

}

}

m_dist = 10.;

for (int j = -2; j<=2; j++)

{

for (int i = -2; i<=2; i++)

{

if (i==0 && j==0) continue;

vec2 neighbor = m_neighbor + vec2(float(i), float(j));

vec2 point = rand(uv_id + neighbor);

point = 0.5+0.5*sin(point*2.*PI+time);

vec2 diff = neighbor + point - uv_st;

float dist = dot(0.5*(m_diff+diff), normalize(diff-m_diff));

m_point = point;

m_dist = min(m_dist, dist);

}

}

return vec3(m_point, m_dist);

}

中間点と最小距離を戻す関数にしている

ボロノイのループを2回行っている(3x3のマス目で処理した後に5x5に範囲を拡大してボロノイの最短距離を求めている)

iq神の記事の素直な実装

Flopineさんのボロノイでは各範囲のマスクを作り、それぞれでボロノイ関数を呼び出して塗り分けています。

ボロノイ？

過去に描いたボロノイ

https://gyazo.com/54fa99087a6c2aa05d7b876d22218197

code:SayachangVoronoi.HLSL

float v = Voronoi(sin(time) * 10. * p.xy * p.z);

float v2 = Voronoi(.8 * sin(time) * p.xy * p.z);

パラメータを変えてボロノイ関数を呼び出して重ねている

ボロノイ？

コツ

ボロノイは複数回使ってかさねるといいかんじのルックを生みやすい(ような気がする)(未検証)

ボロノイ？

3次元のボロノイというものもあります

https://gyazo.com/11eb2e50a77543033fef80ef45bcbeaa

なんか水のコースティクスっぽいかんじになった

2次元のボロノイ(ループ回数が3^2回)に比べると、3次元では重いです(ループ回数が3^3回)

ボロノイ？

ぐるたかさんによるUnity向けのわかりやすい記事

Unity使いの人はぜひ試してみよう！

Conclusion

ボロノイをシェーダーで描くのは楽しい

ガンに効いた

ご清聴ありがとうございました

Skyline - Raven Kwok

https://vimeo.com/139977231