Top / PixelDrawing / 2006-11-13-2

直線描画 †

直線を描画します。

↑

アルゴリズム †

最も有名なのはBresenhamのアルゴリズムです。 加減算だけで描画するのが特徴です。

今回はBresenhamをそのまま使わないで、 走査変換（一行ずつ描画）ベースの処理を念頭に、 任意のy座標におけるx軸のピクセルの範囲を求めて処理します。

↑

横成分が大きい右下がりの直線 †

(0, 0)から(4, 2)まで直線を引くケースを考えます。（下図）

Line.png

ピクセルの範囲の端と端を結ぶ理想曲線を想定します。 始点が左上、終点が右下に接していることに注意してください。

始点を(x1, y1)、終点を(x2, y2)と置きます。 座標は以下の関係を満たすとします。 つまり画面に対して横成分が大きい右下がりの直線ということです。

中学数学の方程式では左辺をyに取りますが、 走査変換のためyからxを求める関係上、 左辺にxを取る形で方程式を立てます。

  1. w = (x2 + 1) - x1
  2. h = (y2 + 1) - y1
  3. x = x1 + w * (y - y1) / h

上の図を見ると、座標のマトリックスは整数で、 交点を四捨五入して処理していることが分かります。 そのため3.の式を四捨五入して整数化します。

ここで四捨五入について考えます。 0.5を足して小数を切り捨てれば四捨五入になります。

int round(double d) { return (int)(d + 0.5); }

すべて整数型で処理しようとすると小数は使えません。 両辺を2倍して考えると、 1を足して2で割れば同じになることが分かります。 割り算が行われた時点で小数が切り捨てられてしまうため、 割り算より先に2倍にする必要があります。 そのため次のような式になります。

これをまとめると以下のようなコードになります。

int w = (x2 + 1) - x1, h = (y2 + 1) - y1;
int x1_2 = x1 + x1, w_2 = w + w;
for (int i = 0, x = x1, y = y1; i < h; i++, y++) {
  int xx = (x1_2 + w_2 * (i + 1) / h + 1) / 2;
  for (; x < xx; x++) {
    buffer.setPixel(x, y, c);
  }
}
↑

縦成分が大きい右下がりの直線 †

同様に以下の条件の直線の描画を考えます。

これも四捨五入するまでの式は同じです。

  1. w = (x2 + 1) - x1
  2. h = (y2 + 1) - y1
  3. x = x1 + w * (y - y1) / h

問題は丸め方です。 単純に四捨五入すると誤差が出てしまいます。 左辺をyにして考えると簡単なのですが、 走査変換との相性が悪くなってしまいます。

特徴を眺めると、一行のx成分は必ず1ピクセルだということが分かります。 同じx座標で縦に何行続くかということになります。 これは前のものの縦横を逆にしただけの処理です。

上から順番に追っていけば問題ないのですが、 任意のyから一発の式でxを求めるにはどうするんでしょう。。。

↑

コメント †


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS