ソフトの砂場(直線描画)

最終更新日:1999年06月13日

 以前、組み込み機器用の描画プログラムを作ったことがあるのですが、肝心の描画アルゴリズムが分かっていなかったので、描画処理部分は他の人に作ってもらいました(そうすると、私は何を作ったのでしょう? ^^;)。最近になって、そ〜いえば、どういうアルゴリズムかな〜、と気になり、一番簡単と思われる直線描画について試してみました。ちなみに、DelphiでCanvasオブジェクトのLineToメソッドを用いて描画すると、次のような結果になります。

CanvasのLineToメソッド

 両端2点(x1, y1), (x2, y2)の座標が与えられ、その間を結ぶ直線(正確には線分ですね)を描画します。話を簡単にするため、x2 > x1≧ 0, y2 > y1≧ 0、直線の傾きはx2 - x1 > y2 - y1とします。組み込み機器なので、浮動小数点演算は使わないことにしておきます。画面には、(x, y)座標を指定して、そこに点を打てるものとします。

 直線描画アルゴリズムで、まずパッと思いついたのが、再帰的に二分割しながら点を打っていくものです。アルゴリズムとして書くと、次のようなかんじでしょうか。

  1. (x1, y1)をA、(x2, y2)をBとします。
  2. A, Bに点を打ちます。Aの座標を(xa, ya)、Bの座標を(xb, yb)と書きます。
  3. A, Bの中点C((xa+xb)/2, (ya+yb)/2)を求め、Cに点を打ちます。/は整数除算とします。
  4. xc-xa>1なら、CをBと置き直して、再帰的に3に戻ります。
  5. xb-xc>1なら、CをAと置き直して、再帰的に3に戻ります。
  6. おわり

 これでプログラムを作ってみると、次のような結果になりました。う〜ん、これはひどすぎます。

2分法(失敗)

 これ以上、素人考えを続けても仕方がないので、[1]を見てみると、Bresenhamアルゴリズムが載っていました。考え方を読んで納得です。こういうのを古典というのでしょう。これの整数版を実装してみると、次のようになりました。

Bresenhamアルゴリズムによる直線描画

 最初の画面とほぼ同じ結果です。LineToメソッドは、WindowsのGDIを呼び出しているので、GDIも同じアルゴリズムを使っているのでしょう。

 ちょっと思いついて、Bresenhamアルゴリズムの誤差を使って、アンチエイリアスのような処理ができないか試してみました。誤差の値により、点の色の濃度を変えたり、その隣にも点を打ったりしています。で、やってみると、確かにギザギザが目立たなくなったところもありますが、線が太い上に幅が一定ではないし、やっぱり素人考えではだめですね。

アンチエイリアスもどき(失敗)

雑感

 結論は、要するに、ちゃんと勉強せよ、ということです ^^;

おまけ

 ついでに、Bresenhamアルゴリズムを使った、円描画プログラムも作ってみました。すばらしい出来です。組み込み機器用のものでは、もう少しいびつな形をしていたような ^^; このアルゴリズムの考え方を応用すれば、いろいろな図形を描画できそうです。

Bresenhamアルゴリズムによる円描画

参考文献

  1. D.F.Rogers著, 山口富士夫 監修, 実践コンピュータグラフィックス, 日刊工業新聞社, 1987

ホーム