Bresenhamの線描画アルゴリズム

bresenham.png

草案1

// ww >= hh のとき
double e=0;
while(1){
       x++;
       e += hh/ww;
       if (e>=1){
              e -= 1;
              y++;
        }
}

となるはず。
でも e += hh/ww; は小数演算だから誤差でまくり。

xが1増えたら
e がhh/ww分増える またxが1増えたら
e がhh/ww分増える

eが満タン(=1)
になったら y を1個増やす

ここでBresenhamは考えた。
「割り算無くしゃあ誤差でねえじゃん」・・・・・
そうだ、e += hh/ww;の両辺にww 掛けてやればいいんだ!!。

草案2

// ww >= hh のとき
double e=0;
while(1){
       x++;
       e += hh;
       if (e>=ww){
              e -= ww;
              y++;
        }
}

これで整数演算のみとなり、誤差なし、演算も高速になりました。

xが1増えたら
e がhh分増える eが満タン(==ww)に
なったら y を1個
増やす

…要は0.1 ずつ足して1になったかどうか調べるんじゃなくて、1ずつ足していって10になったかどうか調べるやりかたと同じ。


outline

サポートサイト Wikidot.com outline