Top / PixelDrawing / 2006-11-13-2

直線描画 †

直線を描画します。

↑

アルゴリズム †

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

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

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

Line.png

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

始点を(x1, y1)、終点を(x2, y2)と置きます。 座標は以下の関係を満たすとします。 つまり画面を3時～4時半（45度）の方向に走る直線ということです。

中学数学の方程式では左辺を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);
  }
}

直角を特別扱いして、残りを45度ずつ条件分けします。 180度回転すると同じ直線になるため、 3時～9時の方向だけを考えています。

  1. 3時
  2. 3時～4時半
  3. 4時半～6時
  4. 6時
  5. 6時～7時半
  6. 7時半～9時
↑

コメント †


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