GLSLで描くTessellation

qiita.com
GPUで暖を取りたい人のためのGLSL Advent Calendar 2016,23日目の記事です.

今回の記事ではGLSLで敷き詰め模様,Tessellationをレンダリングする方法を紹介します. これを読むような人ならばTessellationというと,ポリゴンの三角形分割を思い浮かべる方が多いかもしれませんがこの記事で話題にするのはより広義のTessellation,平面を平面図形で埋め合わせる平面充填のことです.タイリングとよんだりもします.GLSLでなんらかの絵を描いたことがある人ならば一度はチェッカーパターンを描いたことがあると思います.これも敷き詰め模様です.

正方形の敷き詰め

f:id:soma_arc:20161218181520p:plain
まず初めに,ごく簡単な正方形のtessellationを考えてみましょう.画像のように,正方形で平面全体を敷き詰めようとするとき,基本となる正方形を縦と横に動かすことを考えると思います.縦と横の平行移動,全4種類の変換の組み合わせで平面全体を正方形で埋め尽くすことができそうです.
f:id:soma_arc:20161222134855p:plain
GLSLで描画する場合はその逆を行います.すなわち,各ピクセルを敷き詰めを構成する4種類の変換で基本タイルに向かって動かしていきます.そうして,基本タイルに入ったあとで操作の回数によって色付けを行ったり,基本タイル上の色を参照するなどします.
f:id:soma_arc:20161222134927p:plain
以下が実装例です.Shadertoy上の実装です.

vec3 hsv2rgb(vec3 c){
    vec4 K = vec4(1.0, 2.0 / 3.0, 1.0 / 3.0, 3.0);
    vec3 p = abs(fract(c.xxx + K.xyz) * 6.0 - K.www);
    return c.z * mix(K.xxx, clamp(p - K.xxx, 0.0, 1.0), c.y);
}

const int MAX_ITERATIONS = 100;
void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
    float ratio = iResolution.x / iResolution.y / 2.0;
    
    vec2 pos = (fragCoord.xy / iResolution.yy ) - vec2(ratio, 0.5);
    pos *= 10.;
    
    bool isFund = true;
    float opCount = 0.;
    float rectSize = 1.;

    for(int i = 0 ; i < MAX_ITERATIONS ; i++){
        isFund = true;
        if(pos.x < 0.){
            pos.x += rectSize;
            opCount++;
            isFund = false;
        }
        if(pos.x > rectSize){
            pos.x -= rectSize;
            opCount++;
            isFund = false;
        }
        if(pos.y < 0.){
            pos.y += rectSize;
            opCount++;
            isFund = false;
        }
        if(pos.y > rectSize){
            pos.y -= rectSize;
            opCount++;
            isFund = false;
        }
        if(isFund) break;
    }   
    fragColor = vec4(hsv2rgb(vec3(opCount * 0.2, 1., 1.)), 1.0 );
}

上の画像は操作の回数によって色をつけています.とても簡単で計算量の少なそうなコードになりました.各ピクセルを変換し続ける処理は,MAX_ITERATIONSによって制限せざるを得ませんが,多くの場合は問題ありません.

moduloによる効率化

多くの方はお気づきだと思いますが,単純な平行移動はmoduloをつかって効率化することができます.

if(pos.x < 0. || rectSize < pos.x){
    opCount += abs(floor(pos.x / rectSize));
    pos.x = mod(pos.x, rectSize);
    isFund = false;
}
if(pos.y < 0. || rectSize < pos.y){
    opCount += abs(floor(pos.y / rectSize));
    pos.y = mod(pos.y, rectSize);
    isFund = false;
}

操作の回数は商の絶対値をとってやれば計算できます.注意が必要なのは,基本タイルの位置が軸に沿っていない時です.正しく商と余りを計算するためには,タイルの辺が軸に沿うように一度平行移動や回転を行う必要があります.

正方形の敷き詰めを行うコードはShadertoyにアップロードしてあります.
https://www.shadertoy.com/view/4t3SDs

鏡映によるTessellation

もう一つ試してみましょう.
f:id:soma_arc:20161218195601p:plain
この模様はどのような基本タイルと変換で敷き詰めているでしょうか.平面は直角二等辺三角形でうめつくされています.また,よく見ると猫が三角形の各辺に対して鏡写しになっているのがわかります.これは三角形の各辺における鏡映変換という操作で移されています.基本としているタイルは(0, 0), (1, 0), (1, 0)を頂点に持つ赤い三角形です.この敷き詰めを描くコードの一部は以下のようになります.
x軸対称,y軸対称,そして斜辺による対称をとり続けることで基本タイルへと点を持っていくことができます.

for(int i = 0 ; i < MAX_ITERATIONS ; i++){
    isFund = true;
        
    if(pos.x < 0.){
        pos.x *= -1.;
        opCount++;
        isFund = false;
    }
    if(pos.y < 0.){
        pos.y *= -1.;
        opCount++;
        isFund = false;
    }
    // the inversion of line (x + y - 1 = 0)
    pos -= vec2(0, 1);
    pos = invRotateM * pos;
    if(pos.x > 0.){
        pos.x *= -1.;
        opCount++;
        isFund = false;
    }
    pos = rotateM * pos;
    pos += vec2(0, 1);
        
    if(isFund) break;
}

今回は,変換の回数で三角形の色を決めるのに加え,基本タイルの上に置いておいた猫のテクスチャを参照しています.完全なコードはこちらです.
https://www.shadertoy.com/view/4l3SDs

まとめ

今回紹介したアルゴリズムをまとめると以下のようになります.

  1. 基本タイルを見つける.
  2. 基本タイルを敷き詰めるための変換を見つける
  3. ピクセルを基本タイルに入るまで変換し続ける
  4. 変換の回数や,基本タイルの色を使って色をつける

Further Reading

最近知った本で,まだ読めてはいないのですが,敷き詰めパターンの分類や,それらを用いたデザインの方法が詳しく書かれています.こういったデザインの創作に興味のある方は必読ではないでしょうか.

ユークリッド平面上の敷き詰めを双曲平面上での敷き詰めに変形する手法について書かれています.また,今回紹介したアルゴリズムとほぼ同じものがReverse Pixel Lookupという名前で記述されています.この論文では既存の装飾パターンを読み込んで処理するということに主眼をおいています.
また,著者が書いたmorenamentsというソフトは敷き詰めの挙動を見るのに役に立つのではないかと思います.

おわりに

GLSLで敷き詰め模様をレンダリングするアルゴリズムを紹介しました.基本がわかれば色々と応用がきくと思います.明日の記事では双曲平面上でのタイルの敷き詰め,Hyperbolic Tessellationについて紹介します.