Bresenhamと小数加算
最近ほんとアニメの話すら書いて無いな…。まあ、元々そんなに書いて無いけど。
直線描画アルゴリズムのブレゼンハムを復習がてら、ブレゼンハムが普通の浮動小数加算に対してどの程度のアドバンテージを持つのか知りたく、ちょっとベンチマークを取ってみた。(ていうか俺ここ読むまでブレゼンハム正しく理解してなかったは…orz)。
浮動小数加算方式とブレゼンハム方式、両方とも全部書くのはダルすぎなので(というかどちらを採用すべきかのテストなので)、各アルゴリズムの要点となる要素、即ち、
A.浮動小数加算→整数へのキャスト
B.整数加算+整数条件分岐
を抜き出して千万ループする時間を比べてみることにした。環境はPenM1.4GHz,Java1.5
A方式(浮動小数加算)
int a=0;
double b=5.33543,c=353344; //適当な数で
for(int i=0;i<10000000;i++){
c+=b;
a=(int)c;
}
B方式(ブレゼンハム)
int e=45,hh=83,ww=35; //適当な数で
for(i=0;i<10000000;i++){
e += hh;
if (e>=ww){
e -= ww;
}
}
で、結果は
A方式:約440ms
B方式:約90ms
ウハッ、ブレゼンハム速!しかし、いくら浮動小数とはいえ、こんなにも差が出るものかと思い、A方式のキャスト文を取り払い、以下のループでテストしてみた。
A方式'(浮動小数加算(キャスト抜き))
double a=0;
double b=5.33543,c=353344; //適当な数で
for(int i=0;i<10000000;i++){
c+=b;
a=c;
}
結果は
A'方式:約71ms
ちょっと驚いた。A方式のオーバーヘッドって100%キャストだったんだ。(因みに空ループ時の所要時間は70ms)。今日のマトメ。キャストは重い。…てな感じのしょうもない再発見をブログに載せるってのはどうなんだろうな。あんまり価値はなさそうだ。
で、ちょっと調べたら、この問題を回避するため、ゲーム機やグラフィックカードなんかではビットシフトで整数と入れ替えが出来る固定小数点が必須らしい。今回みたいに、幾何情報から画面にラスタイズする際のキャストのためにね。やべえ。固定小数点アツいかもしんね。