GLSLで描くHyperbolic Tessellation

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

前回の記事で紹介したアルゴリズムを用いて双曲円盤上での敷き詰め模様を描いてみます．前回の例では，ユークリッド平面，つまり私達が普段考える平面での敷き詰めを行いました．敷き詰め模様は無限に続き，果てが見えません．
幾何学を研究する数学者たちは，私達の世界の法則を崩した世界を考えました．双曲幾何学(Hyperbolic Geometry)はそんな世界を考える幾何学の分野の一つです．そして，双曲幾何学の世界を一枚の円盤だとみなしたモデルが存在します．このモデルはポアンカレの円板モデルと呼ばれ，円盤の端がユークリッド平面における無限遠点，世界の端となり，円弧がこの世界における直線だと考えられます．また，三角形の内角の和が180度以下になります．この世界におけるタイルの敷き詰めがHyperbolic Tessellationです．
f:id:soma_arc:20161220204320p:plain
半球の内側にある円板がポアンカレの円板です．ユークリッド平面に対する双曲平面です．直線を半径が無限の円板の円周だとみなすと，あらゆるタイルが曲線で構成されていると考えることができます．円板の内側と外側は円板に関する反転という操作で移り合います．見た目は異なりますが，幾何学的，本質的な意味は変わりません．
画家のエッシャーはこのような敷き詰め模様に着想を得て，Circle Limitや天使と悪魔といった有名な作品を生み出しました．双曲幾何学や，Hyperbolic Tessellationに関して，厳密な話はここでは触れません．教科書等を参照してみてください．

基本タイルと変換を見つける

早速前回同様基本タイルを見つけていきましょう．
f:id:soma_arc:20161220163855p:plain
円板は原点中心，半径１の円とします．中央付近の一番大きなタイルがx軸，y軸と２つの円弧に囲まれているのがわかるでしょうか．Hyperbolic Tessellationでは円に関する反転という操作を使って敷き詰めを行います．今回はx軸対称，y軸対称，２つの円に関する反転をとり続けることで，この敷き詰めを描くことができます．

円の位置を特定する

Hyperbolic Tessellationは，タイルの辺の角度が重要になります．どんな図形でも敷き詰めることができるわけではなく，Hyperbolic Tessellationが成立する条件が存在します．これはポアンカレの貼り合わせ定理として知られています．例えば，双曲平面上での三角形である双曲三角形を考える場合は以下の条件を満たす必要があります．
${ \displaystyle ３内角を\frac{\pi}{p},\frac{\pi}{q},\frac{\pi}{r}とした時，\frac{1}{p} + \frac{1}{q} + \frac{1}{r} < 1 }$
以下の画像は一見正しそうに見えますが，正しい敷き詰めではありません．どこかでタイル同士が重なりあったりしています．
f:id:soma_arc:20161222170252p:plain
双曲四角形は２つの双曲三角形を貼り合わせることで得ることができます．今回のタイルは３つの角がPI/2，残りの角がPI/3の４辺形です．よって軸と垂直に交わり，円同士の角度がPI/3となる２円を求める必要があります．円の位置と角度の関係と双曲直線の条件から連立方程式を解きます．双曲直線の条件は以下の通りです．
円の中心を(x, y)半径をrとします．その円弧が双曲直線であるとき以下の条件を満たします．
${ \displaystyle x^2 + y^2 = r^2 + 1 }$
今回の２円はだいたい中心(1.7317, 0),(0, 1.7317)半径はともに1.413となります．円の座標と半径を求める作業が一番面倒なのですが，時間ができたら他のタイルに関しても計算したいところです．

円に関する反転

円に関する反転は，円の中心を無限遠点に，無限遠点を円の中心にもってくる操作です．この変換には等角性や円円対応といった面白い性質があります．ある点Pを中心C，半径Rの円で反転する式は以下のようになります．
${ \displaystyle \frac{(P - C) * R^2}{distance(P, C)^2} + C }$
f:id:soma_arc:20161222151738p:plain
円の外側に描いた図形を黒の円に関する反転によって変換するとこのような図になります．直線は円に，円は円に移ります．変換の前後で図形の角度は変わりませんが(例えば緑の四角形の内角は変換後も直角を保つ)，面積などは大きく変化します．また，同様にして三次元空間で球の反転を定義することもできます．

Hyperbolic Tessellationを描く

中央の一番大きな４つのタイルのうち，右上のタイルを基本タイルとした敷き詰めのコードが以下のようになります．

for(int i = 0 ; i < ITERATIONS ; i++){
    fund = true;
    if (pos.x < 0.){
        pos *= vec2(-1, 1);
        invCount++;
        fund = false;
    }
    if(pos.y < 0.){
        pos *= vec2(1, -1);
        invCount++;
        fund = false;
    }
    if(distance(pos, c1Pos) < r1 ){
        pos = circleInvert(pos, c1Pos, r1);
        invCount++;
        fund = false;
    }
    if(distance(pos, c2Pos) < r2 ){
        pos = circleInvert(pos, cPos2, r2);
        invCount++;
        fund = false;
    }
    if(fund)
        break;
}

f:id:soma_arc:20161220201855p:plain
驚くことに，円板の内側の点は，内側の基本タイル(中央，右上の水色のタイル)に，外側の点は外側の基本タイル(右上の最も大きな紫色のタイル)に移されます．円板の内側のピクセルに対して計算を行うことで円板内の敷き詰めのみを描画することができますが，最終的な点の位置によって色付けを変えることで内側と外側を区別することもできます．
Hyperbolic TessellationはCPUベースで実装すると，計算量が多くなるため，端まで描画するのは大変なのですが，この方法を用いると端まできっちりとリアルタイムで描画することができ，GLSLの計算精度の限界まで拡大することができます．
f:id:soma_arc:20161220201953p:plain
f:id:soma_arc:20161223144704g:plain
敷き詰めの過程はこのような感じです．コードはこちら
Process of the Tessellation

おわりに

今回のGLSLで双曲タイリングを行うWebアプリケーションを作ったので試してみてください．対応しているパターンは２種類しかありませんが，タイリングの変形とWebカメラからの入力を敷き詰める機能を実装してあります．
Hyperbolic Tessellator
Shadertoyにもいくつかコードを上げています．

数学の専門分野に入ってしまったうえ，説明もうまくできなかったのでわかりにくかったかもしれません．しかし，少し専門領域に踏み込むことで面白い題材が見つかるのではないでしょうか．明日の記事では今回触れた円に関する反転を用いたフラクタルについて紹介します．

心鏡曼荼羅