ヒルベルト曲線 – Hilvert Curve

幾何学模様シリーズ第3弾です。今回はヒルベルト曲線という再帰曲線の描画を紹介します。
wikipediaによると、ヒルベルト曲線はドイツの数学者ダフィット・ヒルベルトが1891年に考案したそうです。
空間を覆い尽くす空間充填曲線の一つでフラクタル図形になっています。

ヒルベルト曲線を描画するアルゴリズムはいろいろなサイトで紹介されていて、コードも短いので実装するのに
そこまで時間はかかりません。再帰関数のプログラムも紹介されているので、詳しくはこちらを参照してください。
今回は別のアプローチでこのヒルベルト曲線を見てみたいと思います。

そもそも、ヒルベルト曲線は一筆描きできる線なのですが、再帰関数が呼ばれて描画するという行為を繰り返すうえで、いったい今どこの部分を描画しているのかが気になりました。
wikipediaにあるヒルベルト曲線の例もそうですが、どのサイトも完成されたヒルベルト曲線なので、その描画の過程が分かりません。そこで、今回はヒルベルト曲線が描画されて行く様をアニメーションとして表現してみました。
まず、アニメーションさせるための設計を考えていて少し気になったことが、各段階ごとでできるヒルベルト曲線の単位当たりの線の総数です。アニメーションが常にループ再生されるコードを書くためには、描画終わりの線を
知る必要があります。なので、線の総数を計算してみました。

各段階ごとの線を調べてみると、

1段階 : 3本
2段階 : 15本
3段階 : 63本
4段階 : 255本
5段階 : 1023本
...

という具合に本数が増えていってます。
これを数列で表すと

an = 3, 15, 63, 255, 1023, ...,22(n+1)-2- 1

となります。つまり22(n+1)-2– 1本が各段階における線の総数です。
これをコードに置き換えます。stagesは現在何段階のヒルベルト曲線かを保持している変数です。

pow(2.0, ((2 * (stages + 1)) - 2)) - 1;

これで「現在描画している線が最後の線に到達したら、描画をリセットして再び最初から描画させる」というプログラムを書くことができます。

ちなみに一つの再帰関数で描画される線は3本なので、再帰関数が呼ばれる回数は

総数 / 3

となりますね。

次に苦労した点が、線が描画されていくアニメーション部分です。
単純に横に線を引くアニメーションであれば、

ofLine(0.0, 0.0, x, 0.0);

このように書いて、xの値を毎フレーム変化させていけばいいです。
しかし、ヒルベルト曲線を描画するアルゴリズムは再帰関数を使って構築されているため、最初に関数を呼んだ後は、最後の線を描画するまで繰り返し呼ばれます。
そのため現在描画中の線の次に描画する線は、途中下車のように描画を止める必要があります。毎フレーム少しずつ線を描画してアニメーションさせていって、1つの線が書き終わると、
次のフレームでは新しい線を書くといった処理が必要です。さらに、現在の線よりも古い線はアニメーションの線ではなく実線として描画する必要があります。
そうしないと、今まで描画した部分が表示されず、1本の線のアニメーションだけになってしまいます。

線の描画アニメーションはofxTweenというライブラリを使っています。
このライブラリは、ある値からある値まで、毎フレーム移動量分だけ追加していくことができるライブラリです。
つまり変数 x を10から20まで毎フレーム1ずつ増やしていきたい場合などに効力を発揮します。
このライブラリのいい点は、ある値まで到達したらコールバックで通知がくる点です。
これで線が描画し終わるとコールバックで通知され、次の線を描画させることができるようになりました。 

再帰関数の一つと描画部分の関数を抜粋します。

void ofxHilbertCurve::ldr(int n)
{
    if (n > 0) {
         dlu(n - 1);
         if (drawingCount < count) return;
         // <-
         drawLineInDirection(VectorDirectionRightToLeft);
            
         ldr(n - 1);
         if (drawingCount < count) return;
         // v|
         drawLineInDirection(VectorDirectionUpToDown);
            
         ldr(n - 1);
         if (drawingCount < count) return;
         // ->
         drawLineInDirection(VectorDirectionLeftToRight);
            
         urd(n - 1);
    }
}

void ofxHilbertCurve::drawLineInDirection(VectorDirection direction) {
    
    switch (direction) {
        case VectorDirectionRightToLeft:
            hilbertXpos -= delta;
            break;
        case VectorDirectionLeftToRight:
            hilbertXpos += delta;
            break;
        case VectorDirectionDownToUp:
            hilbertYpos -= delta;
            break;
        case VectorDirectionUpToDown:
            hilbertYpos += delta;
            break;
            
        default:
            break;
    }
    
    if (direction == VectorDirectionLeftToRight || direction == VectorDirectionRightToLeft) {
        if (drawingCount == count && enableDrawing) {
            tweenlinear.setParameters(count, easinglinear, ofxTween::easeOut, tempX, hilbertXpos, duration, delay);
            ofAddListener(tweenlinear.end_E, this, &ofxHilbertCurve::tweenCallback);
            ofLine(tempX, hilbertYpos, tweenlinear.update(), hilbertYpos);
            enableDrawing = false;
        } else if (drawingCount == count && !enableDrawing) {
            ofLine(tempX, hilbertYpos, tweenlinear.update(), hilbertYpos);
        } else {
            ofLine(tempX, hilbertYpos, hilbertXpos, hilbertYpos);
        }
        tempX = hilbertXpos;
    } else {
        if (drawingCount == count && enableDrawing) {
            tweenlinear.setParameters(count, easinglinear, ofxTween::easeOut, tempY, hilbertYpos, duration, delay);
            ofAddListener(tweenlinear.end_E, this, &ofxHilbertCurve::tweenCallback);
            ofLine(hilbertXpos, tempY, hilbertXpos, tweenlinear.update());
            enableDrawing = false;
        } else if (drawingCount == count && !enableDrawing) {
            ofLine(hilbertXpos, tempY, hilbertXpos, tweenlinear.update());
        } else {
            ofLine(hilbertXpos, tempY, hilbertXpos, hilbertYpos);
        }
        tempY = hilbertYpos;
    }
    
    count++;
}

アニメーションとしてヒルベルト曲線を見てみると、描画のアルゴリズムが見て取れるため、なかなか面白いです。
あと、曲線が完成されるまでちょっと見入ってしまいます笑。

■参考サイト
http://www.softist.com/programming/hilbert/hilbert.htm

You may also like...