« 「嫌われ松子の一生」感想 | トップページ | 「黄金の日々」を観終わって »

ありがと!

 以前に紹介した、ベジエ曲線を高速に描画するアルゴリズムを Javascript で実装してくれた人がいるみたいで、その結果がこのページらしい。ぼくが口からデマカセを書いているわけではないことを、少なくとも地球上で一人は信じてくれたわけで、ちょっと嬉しいです。なにせ最近は人と違うことを書くとすぐトンデモ扱いされかねないご時世なので、こんな出来事でもないと、こういう自分で真剣に考えた記事を書く意欲が衰える一方なんですよね。

 もっとも、このアルゴリズム自体は 20 年も前に考案したものなので、今ではもっと優秀なアルゴリズムが存在するはずで、この記事がお目に止まったのは、ウェブ上で無料で読める日本語の文献が他に見当たらなかっただけでしょうけどね。

 この記事の末尾にもちらっと書いたけど、割り算の代わりのビットシフトもやらなくて済む方法があるので、考え方だけ簡単に書いておきましょうか。これも実はブレゼンハムのアルゴリズムの応用ですけど。意外と知られていないようだけど、ブレゼンハムのアルゴリズムの本質は分数計算でして、それを理解すればいろんなところに応用できるんですよ。

 たとえば、(0, 0) から (8, 3) に直線を描画する方法を考えてみましょう。この直線の傾きは 3/8 = 0.375 だから、x 座標を 1 ずつ増やしながら対応する y 座標を計算するには、y 座標に 0.375 を足しこんでいけばいいわけですよね。つまり、

x 座標ザヒョウ 0 1 2 3 4 5 6 7 8
y 座標ザヒョウ 0 0.375 0.75 1.125 1.5 1.875 2.25 2.625 3


 だけど、このやり方だと当然ながら浮動小数点数の計算が必要ですよね。だからまず、小数の代わりに分数で計算することを考えてみます。すると、

x 座標ザヒョウ 0 1 2 3 4 5 6 7 8
y 座標ザヒョウ 0 3/8 3/4 1+1/8 1+1/2 1+7/8 2+1/4 2+5/8 3


 これだとまだ割り算がたくさん必要なので、試しに約分をやめてみましょう。

x 座標ザヒョウ 0 1 2 3 4 5 6 7 8
y 座標ザヒョウ 0/8 3/8 6/8 9/8 12/8 15/8 18/8 21/8 24/8


 すると、y 座標の分母はすべて同じであることがわかります。まあ、足しこんでるのが同じ数(3/8)なんだから、考えてみりゃ当たり前なんだけど。だから実際には、分母を無視して分子の 3 だけ足しこんでいけば、すべての y 座標が計算できるわけですね。

 でも、9/8 を 1 + 1/8 にするには割り算が必要では、と思うかもしれませんが、実はこの割り算も回避する方法があります。この場合、傾き 3/8 は 1 より小さいわけだから、1 回足しこんだだけでは、どう転んでも 2 以上にはなりません。ということは、分子に 3 を足しこんだ結果を分母と比較して、分母より小さい場合にはそのまま、大きい場合には、分子から分母を引いて 1 繰り上げればいいわけ。つまり、

x 座標ザヒョウ   0 1 2 3 4 5 6 7 8
y 座標ザヒョウ 分子ブンシ 0 3 6 1 4 7 2 5 0
y 座標ザヒョウ 分母ブンボ 8 8 8 8 8 8 8 8 8
y 座標ザヒョウ 整数セイスウ 0 0 0 1 1 1 2 2 3


 これで、整数の加減算と比較だけで y 座標が計算できるわけです。ブレゼンハムのアルゴリズムって、コードを見るとややこしく見えるけど、本質的にはこれだけのことで、浮動小数点数の代わりに固定分母の分数を使って計算しているに過ぎません。

 まあ、実際には y 座標が 1 を越えた瞬間に繰り上げるのではなくて、0.5~1.5 の範囲に入った時点で繰り上げた方がきれいな線が描画できるので、その辺を微修正することが多いですけどね。これも要は座標を 1/2 ずらせばいいだけの話です。

 それを理解した上で、先のベジエ曲線のアルゴリズムを見ると、ここでも、足しこんでいる数の分母はすべて N の二乗で固定ですよね。だから同じ考え方でやれば、割り算を使わなくてできるはずなんです。

 ただ一つだけ考えなくちゃいけないことがあります。それは、足しこむ分数が 1 より大きくて、分母より分子の方が大きい場合にはどうするかということ。オリジナルのブレゼンハムのアルゴリズムでは、足しこむ数は直線の傾きなので、傾きが 1 より大きかったら x 座標と y 座標を入れ替えて計算すればいいわけです。でもベジエ曲線はパラメトリック曲線なので、この手は使えません。まあ、回避方法はいろいろあるので考えてみてください。

 だから、ブレゼンハムのアルゴリズムの考え方って、実はかなり応用範囲が広いってことです。まあ、ぼくみたいに多方面に応用した人は、世間広しと言えど、そんなにはいないと思いますが。

 実はこれ、ビットマップ画像の回転なんかにも応用できるんですよ。これを利用すれば、24 ビットフルカラーの画像をほとんど整数演算だけで回転させられます。精度もバイリニア法とほぼ同等でね。三角関数といえど、浮動小数点数で計算している限り、しょせんは実数ではなく有理数近似に過ぎない、ということを理解すれば、答えはすぐそこです。奇特な人は考えてみてください。

追記: 4 年も前にほとんど同じような内容の記事を書いていたことに気づいた。年だね。

|

« 「嫌われ松子の一生」感想 | トップページ | 「黄金の日々」を観終わって »

パソコン・インターネット」カテゴリの記事

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/67762/49549612

この記事へのトラックバック一覧です: ありがと!:

« 「嫌われ松子の一生」感想 | トップページ | 「黄金の日々」を観終わって »