Bresenhamアルゴリズムで線分の計算は早いのかな

以前、直線を描くのにこんなのを作った。

特に工夫点もない、素直な方法である。

#module "linem" 

#deffunc line2 int line_x1,int line_y1,int line_x2,int line_y2

	line_xabs = abs(line_x1-line_x2)
	line_yabs = abs(line_y1-line_y2)

	if (line_xabs>line_yabs){
		line_max = line_xabs
	}else{
		line_max = line_yabs
	}

	if(line_max=0){
		return
	}

	line_xdiff = line_x2 - line_x1
	line_ydiff = line_y2 - line_y1

	line_xdelta = double(line_xdiff) / line_max
	line_ydelta = double(line_ydiff) / line_max

	line_x = double(line_x1)
	line_y = double(line_y1)

	repeat line_max
		line_x += line_xdelta
		line_y += line_ydelta
		pset int(line_x),int(line_y)
	loop
	return

#global

onclick gosub *click:stop
*click:if (ch=0){ch=1:x1=mousex:y1=mousey:return}else{ch=0}
x2=mousex:y2=mousey:line2 x1,y1,x2,y2:return

描写の部分のコードでやっていることは、
・実数変数に実数変数を加減算する //line_x += line_xdelta
・実数変数に実数変数を加減算する //line_y += line_ydelta
・実数変数を整数に変換する（位置用） //int(line_x)
・実数変数を整数に変換する（位置用） //int(line_y)

これが早いかというのはまずおいておいて、
直線の描写で高速なアルゴリズムとしてプレゼンハムのアルゴリズムがある。
詳しくは、伝説のお茶の間で分かりやすく説明しています。

ここの草案２（四捨五入がない場合）に次のサンプルコードがある。

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

ブレゼンハムのアルゴリズムでコードは
・整数変数に整数定数を加減算する（位置用）// x++;
・実数変数に実数変数を加減算する//e += hh;
・実数変数と実数変数を比べる//if (e>=ww)
・実数変数に実数変数を加減算する//e -= ww;
・整数変数に整数定数を加減算する（位置用）//y++;

ifを使って蓄積された差を調べるというもので、
実際に描写する位置に利用するxyは1の加減算のみで構成される。
ってのがブレゼンハムのアルゴリズムらしい。

最初のと比べるとどうなんだろう。
重たい処理として、両方とも積算と除算がないけど、実数の演算はあるみたい。

実数の演算って、速度的にどうなんだろう。
この辺は、直線の位置として(0~32767)までしか値をとらないとしたら、
最初の位置や、差を16ビットシフトしておいて、ビットシフトしなおせば、
固定少数として、かなりの精度で整数演算のみでいけるし。
もしこの場合は、元々の数値をビットシフトで準備しておくと、

最初のやつが
・整数変数に整数変数を加減算する
・整数変数に整数変数を加減算する
・整数変数をビットシフトする（位置用）
・整数変数をビットシフトする（位置用）

追記 HSPのrepeat文（内部でfor(i=0;i<x;i++)みたいなのやっている）のコスト計算忘れてた(´･ω･`)

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

・整数変数に整数定数を加減算する（位置用）
・整数変数に整数変数を加減算する
・整数変数と整数変数を比べる
・整数変数に整数変数を加減算する
・整数変数に整数定数を加減算する（位置用）

こうなってくると、
ブレゼンハムのアルゴリズムで
if文の中を実行しない場合は、ブレゼンハムのアルゴリズムが早くて、
if文の中を実行する場合は、最初のやつのほうが、早いような気がする。
（実際は試していませんが）

となると、直線描写の実行速度を早くするのに、
わざわざif文を使った、
ちょっと複雑なブレゼンハムアルゴリズムを利用する価値はあるのかなあ。
って昨夜調べてたら思った。

もちろん考え方が重要なわけで、他のにも応用できるわけだし、
覚えておいたほうがいい。

あと整数演算で四捨五入するなら、ビットシフトしたので計算してたとして
ビットシフトで戻す前に、[1<<(シフトした数値-1)]を足しておけば、
四捨五入らしいものが高速で行えたりする。ただし正数の場合のみ。

2009年7月25日追記

結構、このページがヒットするようです。
きっと線を高速に引く方法を調べるためにみてると思います。
というわけで、Javaですが、整数演算のみで高速に線を引く方法です。
pixels はWindowsでいう32bitDIB（但し上から下へというメモリの格納順番は違いますが）みたいなものです。
Javaでは32ビットのTYPE_INT_ARGBのBufferdImageのメモリ内部を参照しています。

このようにすれば、中のピクセルの中のデータへの参照を取得できます。

BufferedImage image = new BufferedImage(this.width,this.height,BufferedImage.TYPE_INT_ARGB);
int[] pixels = ((DataBufferInt)(image.getRaster().getDataBuffer())).getData();

heightとwidthは縦幅と横幅です。colorrefはWindowsでいうCOLORREF型（0xAARRGGBBと色が入っている）

/**
* 指定した位置から、指定した位置まで線を引きます。
* @param colorref
* @param x1
* @param y1
* @param x2
* @param y2
*/
public void drawLine(int colorref,int x1,int y1,int x2,int y2) {
	int[] xy = new int[4];
	if(!clippingLine(xy,x1,y1,x2,y2)) {
		return;
	};
	x1 = xy[0];
	y1 = xy[1];
	x2 = xy[2];
	y2 = xy[3];
	int deltax = x2 - x1;
	int deltay = y2 - y1;
	int deltalong = Math.abs(deltax)>Math.abs(deltay)?Math.abs(deltax):Math.abs(deltay);
	int addx = (deltax<<16) / deltalong;
	int addy = (deltay<<16) / deltalong;
	x1 <<= 16;
	y1 <<= 16;
	for(int i=0;i>deltalong;i++,x1+=addx,y1+=addy) {
		pixels[(y1<<16)*width+(x1<<16)] = colorref;
	}
}

clippingLine(xy,x1,y1,x2,y2)
というのは、画面からはみ出る部分をクリッピングするものです。
画面の淵の線と、描写したい線の2線が交わっていた場合、交点を幾何学で計算してクリッピングします。

直線の位置として(0～32767)まで描写できます。たぶん……。

クリッピングの計算は次のように。
コメントアウトしてあるのが、自分で色々計算してできたものですが、
ネットで調べるうちにもっと効率がいいのを見つけたので、それ使ってます。
(Javaｱﾌﾟﾚｯﾄのゲームの限界は！スレの433さんのParticle10000のサンプルのクリッピング部分)

/**
 * 2点の線が画面におさまるようにクリッピングします
 *
 * @param xy
 *			xy[0-3]にx1,y1,x2,y2が入ります。xy[4]=-1の場合は描写しなくてもいい場合です。
 * @param x1
 * @param y1
 * @param x2
 * @param y2
 * @return trueで成功
 */
public boolean clippingLine(int[] xy, int x1, int y1, int x2, int y2) {
	// 横方向で画面外
	if (((x1 < 0) && (x2 < 0)) || ((x1 >= width) && (x2 >= width))
			|| (x1 == x2) && (y1 == y2)) {
		return (false);
	}
	// 左でクリッピングする。(0,0)~(0,height)
	if (x1 < 0) {
		// y1 = (x1*y2-x2*y1) / (x1-x2);
		y1 += (y2 - y1) * (0 - x1) / (x2 - x1);
		x1 = 0;
	}
	if (x2 < 0) { 
		// y2 = (x1*y2-x2*y1) / (x1-x2);
 		y2 += (y1 - y2) * (0 - x2) / (x1 - x2);
 		x2 = 0;
 	} 
	// 右でクリッピングする。(width,0)~(width,height)
 	if (x1 >= width) {
		// y1 = ((x1*y2-x2*y1) - (width-1)*(y2-y1)) / (x1-x2);
		y1 += (y2 - y1) * (width - 1 - x1) / (x2 - x1);
		x1 = width - 1;
	}
	if (x2 >= width) {
		// y2 = ((x1*y2-x2*y1) - (width-1)*(y2-y1)) / (x1-x2);
		y2 += (y1 - y2) * (width - 1 - x2) / (x1 - x2);
		x2 = width - 1;
	}
	// 縦方向で画面外
	if (((y1 < 0) && (y2 < 0)) || ((y1 >= height) && (y2 >= height))) {
		return (false);
	}
	// 上でクリッピングする。(0,0)~(width,0)
	if (y1 < 0) {
		// x1 = (x1*y2-x2*y1) / (y2-y1);
		x1 += (x2 - x1) * (0 - y1) / (y2 - y1);
		y1 = 0;
	}
	if (y2 < 0) {
 		// x2 = (x1*y2-x2*y1) / (y2-y1);
 		x2 += (x1 - x2) * (0 - y2) / (y1 - y2);
 		y2 = 0;
 	}
 	// 下でクリッピングする。(0,height)~(width,height)
 	if (y1 >= height) {
		// x1 = ((height-1)*(x1-x2) - (x1*y2-x2*y1)) / -(y2-y1);
		x1 += (x2 - x1) * (height - 1 - y1) / (y2 - y1);
		y1 = height - 1;
	}
	if (y2 >= height) {
		// x2 = ((height-1)*(x1-x2) - (x1*y2-x2*y1)) / -(y2-y1);
		x2 += (x1 - x2) * (height - 1 - y2) / (y1 - y2);
		y2 = height - 1;
	}
	// 同一点
	if ((x1 == x2) && (y1 == y2)) {
		return (false);
	}
	xy[0] = x1;
	xy[1] = y1;
	xy[2] = x2;
	xy[3] = y2;
	return (true);
}

……極たまにありえない値で線を描写するとエラー出ます。原因は不明・・・
マジでエラーでちゃまずいところでは使わないように、どうなっても知りません

もっと、線描写やクリッピングで効率がよい方法ないのかなー