マンデルブロ集合をJavaScriptで高速に描く。

はじめに

このサンプルのマンデルブロ集合の画像は複素平面上の実部-2から1,虚部-1から1くらいのエリアを描いたものです。

マンデルブロ集合のさまざまな部分をズームしていけるようなサイトを作ったので、よかったら参照してください。

WebGL編を作りました。リアルタイムでいけるようになりました。

マンデルブロ集合そのものについては他所でたくさん説明があるので詳細はWikipediaなどを参照していただくとして、ここでは実装に必要な基本的な理論とどう高速に描画できるように実装するかについて述べたいと思います。

基本的な理論

座標系

まずcanvasを描画する複素平面のエリアをにマップします。横方向を実部、縦方向を虚部とするとサンプル画像の向きになります。

rMin: 実部の最小値
rMax: 実部の最大値
iMin: 虚部の最小値
iMax: 虚部の最大値
x -> 実部の値: rMin + x * ( rMax - rMin ) / CANVAS.width
y -> 虚部の値: iMin + y * ( iMax - iMin ) / CANVAS.height

漸化式

canvas上の全てのピクセルについて以下の判定漸化式をN回実行して、この漸化式が発散するかどうかを調べます。

${\displaystyle {\begin{cases}z_{n+1}=z_{n}^{2}+c\\z_{0}=0\end{cases}}}$

$z$は複素数です
$c$も複素数で、ピクセルの位置から求めます。

発散したかどうかはN回の実行中のどこかで漸化式中の$z$が複素平面上で原点を中心とする半径2の円から出るかどうかで判定する方法がよく使われます。

プログラムで示すと次のようになります。繰り返し回数Nはパラメータとして与え、これによって生成される画像の表情が変わります。

const cR = rMin + x * ( rMax - rMin ) / w
const cI = iMin + y * ( iMax - iMin ) / h

let zR = 0
let zI = 0 
let i = 0 
while ( i < N ) { 
    if ( zR * zR + zI * zI > 2 * 2 ) { 
        // 発散したので描画する
        break
    }   
    [ zR, zI ] = [ 
        cR + zR * zR - zI * zI
    ,   cI + 2 * zR * zI
    ]   
    ++i 
}   

彩色

このアルゴリズムの計算結果の状態をなんらかの色に変換して視覚化します。以下の例では漸化式が発散したか収束したか、とか発散するまで何回繰り返したかをパラメータに視覚化します。

バイナリ

単純な例として漸化式が発散したときと収束した時で例えば白と黒のようにピクセルの塗り分けをするとそれらしい画像が現れます。

輝度変換

漸化式の何回目の繰り返しで発散したか、輝度に変換すると、段々それらしくなってきます。canvas に描画するので、0-255 のデジタル値に変換します。

モノトーン

単純な例

発散した時の繰り返し数を i, 最大の繰り返し数を N とすると( i < N )輝度は簡単に次の式で求められます。この値を RGB のどれかとか幾つかとか全部とかにセットすればモノトーンな画像となります。

floor( 256 * i / N )

ちょっとした工夫

単純な例だと、視覚的に黒なのか白なのかはっきりしないエリアが出て、インパクトが弱いのでそれを解消するための例をいくつか紹介します。

• 上ずれ

const _ = floor( 512 * i / N )
_ < 255 ? _ : 255

• ゲタ

128 + floor( 128 * i / N )

• 二次関数

floor( 256 * sqrt( i / N ) )

色相環

色をつけたい時はHSV(HSB), HSL(HLS) などの色空間に変換するのが一般的です。H(Hue, 色相環)以外の成分は考えない方がビビッドになるので、Hueだけを変換する例を示します。
色相環についてはここがわかりやすかったので紹介しておきます。

HueからRGBのプログラムは以下のような感じです。

const
RGB_HUE = _ => {                            // 0 <= _ < 1
    _ *= 6                                  // 0 <= _ < 6
    const i = Math.floor( _ )               // 0, 1, 2, 3, 4, 5
    const p = Math.floor( ( _ - i ) * 256 ) // 0 <= p <= 255
    const q = 255 - p                       // 255 >= q >= 0
    switch ( i ) {
    case 0: return [ 255, p, 0 ]
    case 1: return [ q, 255, 0 ]
    case 2: return [ 0, 255, p ]
    case 3: return [ 0, q, 255 ]
    case 4: return [ p, 0, 255 ]
    case 5: return [ 255, 0, q ]
    }
}

色相環にゲタを履かせると様々な色合いに変えることができます。

実装

fillStyle, fillRect

最も単純な方法です。

( ctx, w, h ) => {
    for ( let y = 0; y < h; y++ ) {
        for ( let x = 0; x < w; x++ ) {
            //  iを計算
            c2d.fillStyle = `hsl( ${360 * i / N}, 100%, 50% )`
            c2d.fillRect( x, y, 1, 1 )
        }
    }
    ctx.putImage( d, 0, 0 )
}

createImage, putImage

fillStyleとfillrectを使うのは一番単純ですが速度が遅いのでcrrateimageとputimageを使って高速化を図ります。

Create image はwidth height を与えてimage data を作ります。imagedata.dataは画素数×rgbaの4バイト分のint8crampedarray になっていてこのアレイのそれぞれのバイトに0-255の値を書き込んでputimageしてやるとcanvasに表示されます。初期値はオール0、すなわち透明な黒なので色を表示したい時はrgb以外にaの部分に255のような値を書き込んでやる必要があります。全ピクセル分のデータを作って一気にputImageで描画します。これにより高速化することができます。

( ctx, w, h ) => {
    const d = ctx.createImageData( w, h )
    for ( let y = 0; y < h; y++ ) {
        for ( let x = 0; x < w; x++ ) {
            //  iを計算
            const [ r, g, b, a ] = 何らかの色を得るアルゴリズム( x, y, i )
            const _ = 4 * y * w + x
            id.data[ _ + 0 ] = r
            id.data[ _ + 1 ] = g
            id.data[ _ + 2 ] = b
            id.data[ _ + 3 ] = a
        }
    }
    ctx.putImage( d, 0, 0 )
}

最後に

このサイトのソースはペラ１で以下にあります。よかったら参考にしてみて下さい。
https://github.com/Satachito/SliP/blob/0151b7324c3d90d39e25dcba9fe4544fe187a693/Mandelbrot.html

WebGL編を作りました。リアルタイムでいけるようになりました。