PixelDrawing/2006-11-13-2

直線描画 †

直線を描画します。

PixelDrawing-20061113-4.zip

• 開発環境: NetBeans

アルゴリズム †

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

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

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

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

• ソース: Line.xls

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

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

• x1 < x2
• y1 < y2
• x2 - x1 >= y2 - y1

中学数学の方程式では左辺を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倍にする必要があります。 そのため次のような式になります。

• x = x1 + (w * 2 * (y - y1) / h + 1) / 2

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

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

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

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

• x1 < x2
• y1 < y2
• x2 - x1 < y2 - y1

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

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

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

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

走査変換に関しては、xの範囲は常に1です。 xの動きはそのままか、1足すかのどちらかです。 ピクセルの右端(x + 1)のy座標が四捨五入してxのy座標と等しければ、 xに1を足す条件となります。

つまりy軸を基準にした方程式を計算して四捨五入すればOKです。

• y = y1 + (h * 2 * (x - x1) / w + 1) / 2

式変形ではなく意味から作っているので数式に実感が持てます。 これをコードにすると以下の様になりました。

int ww = (x2 + 1) - x1, hh = (y2 + 1) - y1;
int hh_2 = hh + hh;
for (int i = 0, x = x1, y = y1; i < hh; i++, y++) {
  int yy = y1 + (hh_2 * ((x + 1) - x1) / ww + 1) / 2;
  if (y == yy) x++;
  buffer.setPixel(x, y, c);
}

場合分け †

右下がりの直線はきちんと描画できるようになりました。 水平や垂直な線は考えるまでもなく描画できます。

左上がりの直線は始点と終点を入れ替えることで右下がりとして扱えます。 一般化するとh < 0のときに始点と終点を入れ替えることになります。 そのため常にh > 0が成り立ちます。 これは180度の範囲だけを場合分けすれば良いことを意味します。

整理すると以下の条件になります。

1. 水平 (h == 0)
2. 垂直 (w == 0)
3. 横成分が大きい右下がり (w >= h) ← h > 0よりw > 0
4. 横成分が大きい左下がり (-w >= h) ← h > 0よりw < 0
5. 縦成分が大きい右下がり (w > 0)
6. 縦成分が大きい左下がり (それ以外)

これでようやく全方向に直線が引けるようになりました。

コメント †