PixelDrawing/2006-11-13-2
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
#topicpath
#contents
* 直線描画 [#z69d6d95]
直線を描画します。
#ref(PixelDrawing-20061113-4.png,nolink)
#ref(PixelDrawing-20061113-4.zip)
- 開発環境: NetBeans
** アルゴリズム [#f2e3877b]
最も有名なのはBresenhamのアルゴリズムです。
加減算だけで描画するのが特徴です。
今回はBresenhamをそのまま使わないで、
走査変換(一行ずつ描画)ベースの処理を念頭に、
任意のy座標におけるx軸のピクセルの範囲を求めて処理します。
*** 横成分が大きい右下がりの直線 [#lfdde674]
(0, 0)から(4, 2)まで直線を引くケースを考えます。(下図)
#ref(Line.png,nolink)
- ソース: &ref(Line.xls);
ピクセルの範囲の端と端を結ぶ理想曲線を想定します。
始点が左上、終点が右下に接していることに注意してください。
始点を(x1, y1)、終点を(x2, y2)と置きます。
座標は以下の関係を満たすとします。
つまり画面に対して横成分が大きい右下がりの直線ということ...
- x1 < x2
- y1 < y2
- x2 - x1 >= y2 - y1
中学数学の方程式では左辺をyに取りますが、
走査変換のためyからxを求める関係上、
左辺にxを取る形で方程式を立てます。
+ w = (x2 + 1) - x1
+ h = (y2 + 1) - y1
+ 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);
}
}
*** 縦成分が大きい右下がりの直線 [#df2a3ced]
同様に以下の条件の直線の描画を考えます。
- x1 < x2
- y1 < y2
- x2 - x1 < y2 - y1
これも四捨五入するまでの式は同じです。
+ w = (x2 + 1) - x1
+ h = (y2 + 1) - y1
+ 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);
}
*** 場合分け [#bc5409e2]
右下がりの直線はきちんと描画できるようになりました。
水平や垂直な線は考えるまでもなく描画できます。
左上がりの直線は始点と終点を入れ替えることで右下がりとし...
一般化するとh < 0のときに始点と終点を入れ替えることになり...
そのため常にh > 0が成り立ちます。
これは180度の範囲だけを場合分けすれば良いことを意味します。
整理すると以下の条件になります。
+ 水平 (h == 0)
+ 垂直 (w == 0)
+ 横成分が大きい右下がり (w >= h) ← h > 0よりw > 0
+ 横成分が大きい左下がり (-w >= h) ← h > 0よりw < 0
+ 縦成分が大きい右下がり (w > 0)
+ 縦成分が大きい左下がり (それ以外)
これでようやく全方向に直線が引けるようになりました。
** コメント [#fdd92c49]
//#comment(below)
終了行:
#topicpath
#contents
* 直線描画 [#z69d6d95]
直線を描画します。
#ref(PixelDrawing-20061113-4.png,nolink)
#ref(PixelDrawing-20061113-4.zip)
- 開発環境: NetBeans
** アルゴリズム [#f2e3877b]
最も有名なのはBresenhamのアルゴリズムです。
加減算だけで描画するのが特徴です。
今回はBresenhamをそのまま使わないで、
走査変換(一行ずつ描画)ベースの処理を念頭に、
任意のy座標におけるx軸のピクセルの範囲を求めて処理します。
*** 横成分が大きい右下がりの直線 [#lfdde674]
(0, 0)から(4, 2)まで直線を引くケースを考えます。(下図)
#ref(Line.png,nolink)
- ソース: &ref(Line.xls);
ピクセルの範囲の端と端を結ぶ理想曲線を想定します。
始点が左上、終点が右下に接していることに注意してください。
始点を(x1, y1)、終点を(x2, y2)と置きます。
座標は以下の関係を満たすとします。
つまり画面に対して横成分が大きい右下がりの直線ということ...
- x1 < x2
- y1 < y2
- x2 - x1 >= y2 - y1
中学数学の方程式では左辺をyに取りますが、
走査変換のためyからxを求める関係上、
左辺にxを取る形で方程式を立てます。
+ w = (x2 + 1) - x1
+ h = (y2 + 1) - y1
+ 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);
}
}
*** 縦成分が大きい右下がりの直線 [#df2a3ced]
同様に以下の条件の直線の描画を考えます。
- x1 < x2
- y1 < y2
- x2 - x1 < y2 - y1
これも四捨五入するまでの式は同じです。
+ w = (x2 + 1) - x1
+ h = (y2 + 1) - y1
+ 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);
}
*** 場合分け [#bc5409e2]
右下がりの直線はきちんと描画できるようになりました。
水平や垂直な線は考えるまでもなく描画できます。
左上がりの直線は始点と終点を入れ替えることで右下がりとし...
一般化するとh < 0のときに始点と終点を入れ替えることになり...
そのため常にh > 0が成り立ちます。
これは180度の範囲だけを場合分けすれば良いことを意味します。
整理すると以下の条件になります。
+ 水平 (h == 0)
+ 垂直 (w == 0)
+ 横成分が大きい右下がり (w >= h) ← h > 0よりw > 0
+ 横成分が大きい左下がり (-w >= h) ← h > 0よりw < 0
+ 縦成分が大きい右下がり (w > 0)
+ 縦成分が大きい左下がり (それ以外)
これでようやく全方向に直線が引けるようになりました。
** コメント [#fdd92c49]
//#comment(below)
ページ名: