ブレゼンハムの直線描画アルゴリズム

wonderFLにて使用されている。
bitmapにＣＰＵにあまり負荷をかけずに直線を描画するためのロジック。
まじめに直線を書こうとすると直線をxの長さと、yの長さに分解し、角度を計算するなど三角関数を使用するが、これはとても負荷がかかる。
しかもピクセル描画すればいいので、厳密に計算しても意味なない。
そこで簡便な計算方法を用い描画を高速させている。

以下その手法


◆縦移動より横移動の方が多い場合=（x1-x0)>(y1-y0)の場合
１．横移動は必ず行う
２．縦移動は移動距離がおおきかったら行う。
３．少なかったら行わない。
４．本来行うべきなのに行わないので誤差がでる。その誤差を貯めておく。
５．ためた誤差が一定の数値を超えたら縦移動する

◆横移動より縦移動の方が多い場合(x1-x0)<(y1-y0)の場合
上記縦と横を入れ替えて同じ計算を実施する
ソースはこんな感じ


package {
import flash.desktop.NotificationType;
import flash.display.Bitmap;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.geom.Point;

public class Blesenham extends Sprite {
private var _canvas:BitmapData;
private var point_0:Point;
private var point_1:Point;

function Blesenham() {
//set canvas
_canvas = new BitmapData(stage.stageWidth , stage.stageHeight , false , 0x000000);
addChild(new Bitmap(_canvas) );
//set event
stage.addEventListener(MouseEvent.MOUSE_DOWN , onMousedown);
}
private function onMousedown(event:MouseEvent):void {
var target:MouseEvent = event.currentTarget as MouseEvent;
//イベント引き継ぎ
if (point_1) {
//二つポイントがある　描画取り消し
point_0 = null;
point_1 = null;
_canvas.fillRect(_canvas.rect , 0x000000);
}else if(point_0){
//１つポイントがある　二つ目を登録し描画
point_1 = new Point(mouseX , mouseY);
_canvas.setPixel(mouseX , mouseY , 0xFF0000);
_drawLine(point_0.x , point_0.y , point_1.x , point_1.y , 0xFF0000 , 1.0);
trace(point_1);
}else {
//１つもポイントが無い
point_0 = new Point(mouseX , mouseY);
_canvas.setPixel(mouseX , mouseY , 0xFF0000);
trace(point_0);
}
}
private function _drawLine(x0:int , y0:int , x1:int , y1:int , color:int , alpha:Number):void {
var steep:Boolean = Math.abs(y1 - y0) > Math.abs(x1 - x0);//x移動より y移動の方が大きい
/*
* こんな感じだとtrueになる
* ■
* 　■
* 　　■
* 　　　■
*/
var tmp:int;
if (steep) {
//x移動より y移動の方が大きいときはxとyの値を入れ替えるそして書くときも入れ替える
//計算手順の簡略化のためかも。
tmp = x0;
x0 = y0;
y0 = tmp;
tmp = x1;
x1 = y1;
y1 = tmp;
}
if (x0 > x1) {
//①マイナス向けに移動してたらx0とx1を入れ替える→右から書こうが左から書こうが同じだよってことか
tmp = x0;
x0 = x1;
x1 = tmp;
tmp = y0;
y0 = y1;
y1 = tmp;
}
var deltax:int = x1 - x0;//横距離を計算　①で入れ替え計算しているので必ず正になる
var deltay:int = Math.abs(y1 - y0);//縦距離を計算して絶対値化
var error:int = deltax / 2;//x移動距離の半分？これを誤差とみなすのだろうか
var ystep:int = y0;
var y:int = y0;
if (y0 < y1) {
//正方向なら1
ystep = 1;
}else {
//負方向なら-1
ystep = -1;
}
for (var x:int = x0; x <= x1 ; x++) {
//xは必ず１ずつ動かす　このために①でx0とx1を入れ替えてた　あとはyのことだけ考慮すればよい
if (steep) {
//steepがtrueってことはxとyが入れ替えられている　→ 描画もyとxを入れ替える
//_canvas.setPixel32(y , x , color | ((alpha * 0xff) << 24)  );
_canvas.setPixel32(y , x ,  ((alpha * 0xff) << 24) | color   );
}else {
//_canvas.setPixel32(x , y , color | ( (alpha * 0xff << 24)  ) );
_canvas.setPixel32(x , y , ( (alpha * 0xff << 24) | color ) );
}
error = error - deltay; //x移動距離の半分（＝誤差）からy移動距離（絶対値）を引く　誤差をためておく
if (error < 0) {
//yの増分がxの増分半分を超えたらyをひとつ移動させ、マイナスになってしまったエラーにまたx増分を足す。以降繰り返し
y = y + ystep;
error = error + deltax; //誤差に横全移動距離を足し、新たな判定基準にする
}
}
}
}
}