ボロノイとは
プロシージャルな石畳や細胞のパターンの生成、破壊シミュレーション時のオブジェクトの分割に良く使われるノイズのことです。詳しくはThe Book of Shaders セルラーノイズを参照ください
通常のボロノイ
ユークリッド(p=2)
d = length(r);
d = dot2(r);
通常のボロノイはこんな感じですが、距離関数を変えることで色々なボロノイを作ることができます。尚、使用するのは、符号なしのディスタンスフィールドの方です。SDFは使えません。
数学的な距離関数を使う
私たちが、普段2点間の距離を測る時に使用しているのは、三平方の定理で導かれる『ユークリッド距離』というものですが、『マンハッタン距離』、『チェビシェフ距離』、『ミンコフスキー距離』など2点間の距離の測り方にも様々な種類があります。
通常のボロノイは『ユークリッド距離』を使用していますが、この距離の測り方を『マンハッタン距離』、『チェビシェフ距離』に変えることで回路ぽいボロノイを作成できます。これはかなり使われていますね。
マンハッタン(p=1)
float sumabs(vec2 p){return abs(p.x)+abs(p.y);}
d = sumabs(r);
チェビシェフ(p=∞)
float maxabs(vec2 p){return max(abs(p.x), abs(p.y));}
d = maxabs(r);
ミンコフスキー
さて、他にも数学的距離関数がないのかと言うと、ミンコフスキー距離というものがありまして、これは、『ユークリッド距離』、『マンハッタン距離』、『チェビシェフ距離』をLPノルムという一つの式(一般式)で表すことができます。
以下、2次元(2D)の場合
- ミンコフスキー距離(p)
\sqrt[p]{|x^p|+|y^p|}
- マンハッタン距離(p=1)
\sqrt[1]{|x^1|+|y^1|}=|x|+|y|
- ユークリッド距離(p=2)
\sqrt[2]{|x^2|+|y^2|}=\sqrt{x^2+y^2}
- チェビシェフ距離(p=∞)
\sqrt[1]{|x^1|+|y^1|}=|x|+|y|=\sqrt[∞]{|x^∞|+|y^∞|}
各距離は、次元数pで表すことができ、p=1がマンハッタン、p=2がユークリッド、p=∞がチェビシェフ距離になります。なので、マンハッタン=L1距離、ユークリッド=L2距離と呼ばれていたりします。
| ノルム(p) | 数学的距離名 |
|---|---|
| 1 | マンハッタン距離(L1距離) |
| 2 | ユークリッド距離(L2距離) |
| ∞ | チェビシェフ距離 |
| p | ミンコフスキー距離 |
もちろん、このpには-∞や0.5なども任意に指定できるので今度は任意の次元pを指定したミンコフスキー距離を使ってみましょう。以下は面白い図形ができるp=-∞やp=0.5の場合を紹介しています。
float lpnorm(vec2 p, float n){vec2 t=pow(abs(p),vec2(n));return pow(t.x+t.y,1./n);}
ところで、『チェビシェフ距離』はp=∞ですが
d=lpnorm(r,∞);
とかになっていないのにお気づきでしょうか。
無限に近い数値を入れたり
d=lpnorm(r,1e10);
することで近似値を得ることが出来るのですが計算負荷的にもお勧めできません。shaderでは実はもっと簡単に実現できます。max関数を利用すればいいのです。∞がmax関数なら-∞はmin関数ですね。
ディープラーニングの発展に多大な貢献をもたらした、数学的には正しくないReLU関数(=単なるmax関数ですね)のようにプログラミング言語の関数は、新しい数学の世界を開く、shaderは新しい数学的発見を見つけることができる楽しい世界です。前振り
セル(p=3)
pが2以上は植物の細胞のような感じになる。pが大きくなればなるほど角ばって行きチェビシェフに近づく
十字(n=-∞)
d = minabs(r);
d=lpnorm(r,-1e10);
でも良いですがmin使えばいいので
アステロイド(n=0.5)
d = lpnorm(r,.5);
数学的距離関数以外
さて、本題のshaderで図形を描く時に使われる元の関数も距離関数です。
もちろん、数学的な距離関数も使われていて、以下の図形を描くのに使われています。
| ノルム(n) | 図形 | 数学的距離名 |
|---|---|---|
| -∞ | 十字 | - |
| .5 | アステロイド | - |
| 1 | 正方形(45度) | マンハッタン距離(L1距離) |
| 2 | 円 | ユークリッド距離(L2距離) |
| ∞ | 正方形 | チェビシェフ距離 |
| p | - | ミンコフスキー距離 |
しかし、これだけでは図形を描くには足りないので、角丸長方形や、三角形、六角形、星型、などの距離関数が編み出されました。
当然のことながら、これら符号なし距離関数であれば、なんでも使えるので、オリジナルのボロノイを作ってみましょう。以下はその中で面白かったボロノイを紹介しています。
ただ、ここら辺の距離関数を数式で表すのはかなり困難ですね。
三角形
d = lPoly(r,3.);
星型
d = lStar(r,5.);
サンプルプログラム
precision mediump float;
uniform vec2 m; // mouse
uniform float t; // time
uniform vec2 r; // resolution
uniform sampler2D smp; // prev scene
const float PI = acos(-1.);
const float TAU = PI * 2.;
mat2 rot(float a){float c=cos(a),s=sin(a);return mat2(c,-s,s,c);}
// signed distance
float sd(float d,float r){return r-d;}
float sd(float d){return 1.-d;}
vec2 hash2( vec2 p ){
return fract(sin(vec2(dot(p,vec2(127.1,311.7)),dot(p,vec2(269.5,183.3))))*43758.5453);
}
float lPoly(vec2 p,float n){
float a = atan(p.x,p.y)+PI;
float r = TAU/n;
return cos(floor(.5+a/r)*r-a)*length(p)/cos(r*.5);
}
float lStar(vec2 p,float n){
return min(lPoly(p,n*.5),lPoly(mod(n,2.)!=0.?vec2(-p.x,p.y):p*rot(TAU/n),n*.5));
}
float dot2(vec2 p){return dot(p,p);}
float sumabs(vec2 p){return abs(p.x)+abs(p.y);}
float maxabs(vec2 p){return max(abs(p.x), abs(p.y));}
float minabs(vec2 p){return min(abs(p.x), abs(p.y));}
float lpnorm(vec2 p, float n){vec2 t=pow(abs(p),vec2(n));return pow(t.x+t.y,1./n);}
float voronoi(vec2 x){
vec2 n = floor(x);
vec2 f = fract(x);
vec2 res = vec2(8.0);
for(int j = -1; j <= 1; j++)
for(int i = -1; i <= 1; i++){
vec2 g = vec2(i, j);
vec2 r = g - f + hash2(n + g);
float d = 0.;
//d = length(r);
//d = dot2(r);
//d = sumabs(r);
//d = sumabs(r);
//d = maxabs(r);
//d = minabs(r);
//d = lpnorm(r,.5);
//d = lpnorm(r,sin(t*.5)*4.);
//d = lPoly(r,3.);
d = lStar(r,5.);
if(d < res.x){
res.y = res.x;
res.x = d;
}else if(d < res.y){
res.y = d;
}
}
vec2 c = sqrt(res);
return c.y - c.x;
}
void main(void){
vec2 p = (gl_FragCoord.xy * 2.0 - r) / min(r.x, r.y);
float v = voronoi(4.*p);
float l = 1.-smoothstep(.02,.04,v);
//l=v;
gl_FragColor = vec4(vec3(l), 1.0);
}
参考
- 2次元ディスタンスフィールドの一覧はこちら
- iq先生のボロノイ解説 ※ iq先生のボロノイは完璧なボロノイを実現しますが、距離関数の変更には対応していないので注意
- ボロノイ！シェーダーでボロノイをあそぼう！！～理論とかはいいからとにかく使い方を知りたい～
- さやちゃんぐbotスクラップス Voronoi
関連
- ボロノイズ iq先生がボロノイとノイズの一般式を開発しています。