線分計算のBresenhamアルゴリズムって本当には早いのかな

アルゴリズム
2008.06.01
スポンサーリンク

はじめに

「線を描画する」というのはグラフィックプログラミングの基本です。一見単純に思える直線描写にも、さまざまなアプローチや工夫があります。

この記事では、自作した素直な直線描写法から、有名なブレゼンハムのアルゴリズム、さらには整数演算だけで高速に線を引くJava実装例まで、いろいろと紹介してみます。

アルゴリズム比較と考察

素直な実装

以下はHSP3言語で書いた特に工夫点もない、素直な方法な直線描写関数です。

#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

C言語の場合は以下のようになります。

void line2(Renderer* renderer, int line_x1, int line_y1, int line_x2, int line_y2) {
    int line_xabs = abs(line_x1 - line_x2);
    int line_yabs = abs(line_y1 - line_y2);

    int line_max = (line_xabs > line_yabs) ? line_xabs : line_yabs;
    if (line_max == 0) return;

    int line_xdiff = line_x2 - line_x1;
    int line_ydiff = line_y2 - line_y1;

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

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

    for (int i = 0; i < line_max; i++) {
        line_x += line_xdelta;
        line_y += line_ydelta;
        DrawPoint(renderer, (int)line_x, (int)line_y);
    }
}

実数変数で現在位置を管理し、1ステップごとに差分だけ加算しながら線を描画していく方法で1ステップごとに差分だけ加算しながら線を描画していくというものです。

  • 実数変数に実数変数を加減算
  • 実数変数を整数に変換して座標とする

ステップ数的なコードの概要としては以下のようなことをしています。

  • 実数変数に実数変数を加減算する //line_x += line_xdelta
  • 実数変数に実数変数を加減算する //line_y += line_ydelta
  • 実数変数を整数に変換する（位置用） //int(line_x)
  • 実数変数を整数に変換する（位置用） //int(line_y)

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

素直な実装はおいておいて、今度はプレゼンハムのアルゴリズムの説明に行きます。これは直線の描写で高速なアルゴリズムとして有名であり、詳しくは伝説のお茶の間で分かりやすく説明しています。

仕組みとしては以下のような形です。

  • 基本的に「整数変数」だけで座標を扱う
  • 誤差（実数の代わりに整数で近似）を累積して、座標を移動する

草案２に記載されているサンプルコードの一部（ww >= hh のとき）を転記します。

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

このコードは、if文で誤差を調整しつつ、xとyを1ずつ増やして直線に近づける、計算の多くが整数で済むことで高速化するという説明になっています。

ステップ数的なコードの概要としては以下のようなことをしています。

  • 整数変数に整数定数を加減算する（位置用）// x++;
  • 実数変数に実数変数を加減算する//e += hh;
  • 実数変数と実数変数を比べる//if (e>=ww)
  • 実数変数に実数変数を加減算する//e -= ww;
  • 整数変数に整数定数を加減算する（位置用）//y++;

本当に速いのか考えてみる

ここで、「ブレゼンハムのアルゴリズムは本当に速いのか？」という点について、少し考えてみます。

ブレゼンハムのアルゴリズムは、if文で誤差を調整しつつ座標を進めていくため、実際に描画に使われるxy座標の更新は「1の加減算」だけで済みます。このあたりが、「ブレゼンハムは整数だけで高速に動作する」とされる理由です。

では、最初に紹介した素直な（実数を使う）方法と比較するとどうなのでしょうか。重い処理、たとえば積算や除算はどちらもあまり使っていませんが、実数演算が入るのが大きな違いです。実際、現代のCPUでは実数演算もかなり高速ですが、整数演算に比べればややコストがかかります。

ただし、たとえば直線の位置を0〜32767のような範囲に限定する場合、あらかじめ16ビットシフトして「固定小数点」として扱えば、実数を使わずにかなり精度よく整数演算だけで描画することも可能です。シンプルなアルゴリズムであっても、固定小数点で工夫すれば、整数変数同士の加減算、座標値のためのビットシフトといった処理だけで済ませられるため、かなり高速化が見込めるはずなのです。

実際にそのように工夫すると、シンプルなアルゴリズムでは以下の処理だけで済ませられるため、高速化が見込めます。

  • 整数変数同士の加減算
  • 座標値のためのビットシフト

一方でブレゼンハムのアルゴリズムを処理の流れで分解すると、以下の処理となります。

  • 整数変数への定数加減算（座標更新）
  • 整数変数同士の加減算・比較
  • if文による分岐（誤差調整）

こう考えてみると、「if文の条件分岐」が発生しない場合はブレゼンハムのほうが有利、逆にif文の分岐処理が頻繁に起きるパターンでは、場合によっては素直な実装のほうが速いのでは、というのが私の主張です。

整数だけで線を引くプログラムを考える

ここからは、Javaで整数演算のみで高速に線を引く方法に焦点をあててコード紹介に移ります。

ピクセルデータへのアクセス

Javaでは32ビットのTYPE_INT_ARGBのBufferdImageのメモリ内部を参照することで、ピクセルデータへアクセス可能です。次のコードで中のピクセルの中のデータへの参照を取得できます。（Windowsでいう32bitDIB（但し上から下へというメモリの格納順番は違いますが）のような形になります。）

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と色が入っている）とします。プレゼンハムのアルゴリズムと違ってIF文が登場しません。これはプレゼンハムのアルゴリズムより高速なのでは？

/**
* 指定した位置から、指定した位置まで線を引きます。
* @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;
	}
}

クリッピング（作成中）

作成中のものですがクリッピングするプログラムもついでに紹介します。はみ出した部分を消すという画像処理ではよく使うコードなのでセットで利用すると思います。

こちらは、Javaｱﾌﾟﾚｯﾄのゲームの限界は！スレの433さんのParticle10000のサンプルコードを参考にして作りました。直線の制限として(0～32767)までに対応しているはずです。ただ不安定でたまにエラー出ます。

/**
 * 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);
}

おわりに

線描画の世界は奥が深いです。

計算機の進化や言語の違いによって「どのやり方が一番速いか」も変化していますが、考え方やアルゴリズムの原理を知っておくことで、画像処理やゲーム制作、グラフィックスなど、幅広い応用が可能です。

スポンサーリンク

コメント

  1. ちとし より:
    2009年7月2日 23:11

    参考になりました。ありがとうございまっす。

    返信
  2. 匿名 より:
    2015年1月10日 00:14

    >実数の演算はあるみたい
    いや、普通ブレセンハムは整数で実装するでしょう
    eヘの加減算を逆にしてif文を0との比較にすれば、環境次第ではさらに早くなりますね

    返信
タイトルとURLをコピーしました