読者です 読者をやめる 読者になる 読者になる

人工知能に関する断創録

人工知能、認知科学、心理学、ロボティクス、生物学などに興味を持っています。このブログでは人工知能のさまざまな分野について調査したことをまとめています。最近は、機械学習、Deep Learning、Kerasに関する記事が多いです。



ブレゼンハムアルゴリズム

Javagame

ブレゼンハム(bresenham)というアルゴリズムを使ってタイル環境で直線を描画するサンプルです。ブレゼンハムはペイントソフトの直線描画にも使われているそうです。ペイントの直線描画と同じようにドラッグすれば直線が引けます。

bresenham.jar

ブレゼンハムアルゴリズム

ブレゼンハムアルゴリズムのコードは下のようになります。引数のstartは直線の始点、endは終点です。インスタンス変数のlineに直線を構成するピクセルの座標が入ります。lineは戻り値にしてもいいと思います。

    /**
     * ブレゼンハムアルゴリズムで直線を引く
     * 
     * @param start 直線の始点
     * @param end 直線の終点
     */
    private void buildLine(Point start, Point end) {
        int nextX = start.x;
        int nextY = start.y;
        int deltaX = end.x - start.x;
        int deltaY = end.y - start.y;
        int stepX, stepY;
        int step;
        int fraction;

        for (step = 0; step < MAX_LINE_LENGTH; step++) {
            line[step] = null;
        }

        step = 0;

        if (deltaX < 0)
            stepX = -1;
        else
            stepX = 1;
        if (deltaY < 0)
            stepY = -1;
        else
            stepY = 1;

        deltaX = Math.abs(deltaX * 2);
        deltaY = Math.abs(deltaY * 2);

        line[step] = new Point(nextX, nextY);
        step++;

        if (deltaX > deltaY) {
            fraction = deltaY - deltaX / 2;
            while (nextX != end.x) {
                if (fraction >= 0) {
                    nextY += stepY;
                    fraction -= deltaX;
                }
                nextX += stepX;
                fraction += deltaY;
                line[step] = new Point(nextX, nextY);
                step++;
            }
        } else {
            fraction = deltaX - deltaY / 2;
            while (nextY != end.y) {
                if (fraction >= 0) {
                    nextX += stepX;
                    fraction -= deltaY;
                }
                nextY += stepY;
                fraction += deltaX;
                line[step] = new Point(nextX, nextY);
                step++;
            }
        }
    }

実を言うとなぜこの処理で直線が引けるのか直感的には納得できてません・・・おっ本当に引けたって感じです。

デバッガを使って(または紙の上で)変数の内容を追ってみるとわかりますが、fractionがキーポイントになっています。fractionの値によってx方向に線をのばすかy方向に線をのばすかが調整されてます。

よくわからないのはdeltaXやdeltaYが参考文献では2倍されている点です。この2倍はなくてもきちんと動作したので何を意味してるのかわかりませんでした・・・わかった方はぜひ教えてください(ウシオダさんが教えてくれました。ありがとうございます。下の追記参照)。

まあとりあえず便利なのでそのまま使えればいいかな。

ブレゼンハムアルゴリズムの導出法(2005/5/14)

ウシオダさんからブレゼンハムアルゴリズムの導出法を教えていただきました。

始点を (a,b) 、終点を (a+Δx, b+Δy) とし、この間に直線を引くことを考えます。ここでは、Δx>Δy>0 とします。ある場所、◎ (a+i, b+j) において次に塗りつぶすマスは Δx>Δy という条件では P(a+i+1, b+j) か Q(a+i+1, b+j+1) のどちらかです。◎の次に塗りつぶすマスとしてPとQのどちらがよいかを判定するのがプログラム中の変数fractionです。

f:id:aidiary:20090829115112g:plain

(a,b) と (a+Δx, b+Δy) をつなぐ理想的な直線の方程式は、

   y = (Δy/Δx)(x - a) + b

となります。つまり、x=a+i+1 における理想的なy座標は上の方程式に x=a+i+1 を代入して

   y = (Δy/Δx)(a+i+1-a) + b
     = (Δy/Δx)(i+1) + b

です。また、PとQの中点のy座標は {(b+j)+(b+j+1)} / 2 より

   b+j+0.5

となります。ここで、x=a+i+1 における理想曲線のy座標とPとQの中点のy座標の差を考えます。

   fraction' = (Δy/Δx)(i+1) + b - (b+j+0.5)

このfraction'を使って、

   fraction' >= 0 ならば Q を選ぶ
   fraction' <  0 ならば P を選ぶ

と判定できます。なぜならfraction'が正ってことは理想曲線のy座標はPよりはQにより近い、fraction'が負ってことは理想曲線のy座標はQよりはPに近いことになるからです。なるべく理想曲線に近くなるようにPかQを選ぶのがコツです。

fraction'は式の中に0.5という小数があります。そのため、fraction'を2Δx倍してfractionとします。

   fraction = 2Δx * fraction'
            = 2Δy(i + 1) - Δx(2j + 1)

fraction'は大小判定に使うだけですので符号が変わらなければ何倍してもかまいません。2Δx > 0 で正数なので符号は変わりません。fractionはかなりすっきりした式になりました。

ここで、

   i(x方向)を1増やすとfractionは2Δy増える
   j(y方向)を1増やすとfractionは2Δx減る

ことに注意してください。また、fractionの初期値は i=0, j=0 なので

   2Δy-Δx

となります。ここでさらにトリックを使って2ΔxをdeltaX、2ΔyをdeltaYに置き換えてみます。すると、

   i(x方向)を1増やすとfractionはdeltaY増える
   j(y方向)を1増やすとfractionはdeltaX減る
   fractionの初期値はdeltaY-deltaX/2

となります。ここでコードを見てみます。

    // ΔxとΔyを2倍してdeltaX、deltaYとする
    deltaX = Math.abs(deltaX * 2);
    deltaY = Math.abs(deltaY * 2);  
        
    if (deltaX > deltaY) {
        fraction = deltaY - deltaX / 2;  // fractionの初期値
        while (nextX != end.x) {
            // fraction>=0のときはQ(a+i+1,b+j+1)を選ぶ
            // つまり、nextX,nextYともに+1
            if (fraction >= 0) {
                nextY += stepY;      // yが1増えると
                fraction -= deltaX;  // fractionはdeltaX減る
            }
            // fraction<0のときはP(a+i+1,b+j)を選ぶ
            // つまり、nextXだけ+1
            nextX += stepX;      // xが1増えると
            fraction += deltaY;  // fractionはdeltaY増える
            line[step] = new Point(nextX, nextY);
            step++;
        }
    }

まさにそのままですね!

『ゲーム開発者のためのAI入門』ではfractionの初期値が

   fraction = deltaY * 2 - deltaX

のままです。これは間違いではないかとウシオダさんから指摘されました。正しくは、

   fraction = deltaY - deltaX / 2

のようです。引かれた直線を見比べてみると後者の方がきれいです。

ちちかかさんから例2-6と例2-7は直接的なつながりはないのではないかという指摘をいただきました。確かにそうかも・・・そうだとしたら間違いではないですね。すごくややこしいけど。