ブレゼンハムアルゴリズムで円弧を描画

僕が見ていない間に質問掲示板で「半円や四分の一の円を描くには?」という質問が投稿されていました。そんなときには U D の拡張線描画命令集「LINE++.nako」をどうぞー。と言いたいところなのですが、いかんせんもう古くって宣伝したくない(汗;今自分で見てみると結構変な書き方をしているものなんですよね。それで作り直したかったので、任意角の円弧を描画する命令ブレゼンハムアルゴリズムで実装してみました:円弧描画関数@なでしこ置き場

ブレゼンハムアルゴリズムというのを大雑把に説明します。ディスプレイ上の全ての1ドット(点)は数学で言う所の格子点であり、整数の座標で表されます(デジタルである)。従ってその上に何かを描画するのに、実数計算をするのは非常にロスが大きいので、X,Yを全て整数のまま計算させるのが都合がよく、誤差判定をしながらX,Yを漸次移動していこう、という考え方がブレゼンハムアルゴリズムです。

で今回そのブレゼンハムアルゴリズムを適用しようとしている図形は、「整数?何それ、おいしいの?」と言いたくなるような円弧。ところがうまい具合に誤差判定を整数だけで済ますことができて、完全な円の場合は意外と簡単なコードで正確・高速を実現できます。(参考:伝説のお茶の間…円描画にブレゼンハムを適用する解説を参考にさせて頂きました)

では円弧はどうか?これには大きな問題があります。描画するために必要な円弧の重要な要素である自体がどうしても実数計算を避けられないのです。具体的には、円弧のどの範囲まで描画すればいいのか判定するのにARCTAN命令が不可欠になってきます。

知っている人は知っていると思うのですが、COSSINと言った三角関数などは大抵、内部では級数展開の近似で実装されています。この級数展開がもうバリバリの実数計算なんです。で、云わばこれを使いたくないがためにブレゼンハムを持ち出したのに、やっぱり円弧の場合は級数展開から逃れられない、というわけですorz。

そんなわけで、以前僕が書いた円弧描画命令がCOS,SIN多用で描画精度低い目であったのと比較すると、今回のブレゼンハム版は少し遅い代わりに描画精度が上がっています。以前の円弧描画命令では描画区間を分割して(分割数はオプション変数で変更可)、COS,SINで座標計算して区間の間を「線」命令で結ぶということをしています。つまり、区間の間を全て直線近似していたと。一方ブレゼンハムでは、1ドット毎にもっとも近い点を選択していく近似なので、いわば折れ線のギザギザ状態は発生しない。

でもねぇ。本末転倒なんですよね。整数演算オンリーにすることで高速化を図るブレゼンハムを使ったのに実数計算から逃げられず、しかも結局COS,SIN多用で大雑把に近似した方が早いわけですから。もちろん、極力ARCTANを使用しないように工夫・改良はしてあるんですが、それでも比較的に遅い目。しかも仕様上線色は反映できても線太さ線スタイルまでは反映できない(前者のバージョンでは全て反映される)。

ブレゼンハムの勉強にはなりましたが、まだまだです。精進します。