ラスターグラフィックスの基本

Bresenhamのアルゴリズムについて
ラスターグラフィックスの基本
• ディスプレイはデジタル表示が一般的
• 直線も曲線も離散的に表示（点列表示）
• 高速描画(高速アルゴリズム)が要求される
• ベクター表示する可能な全てのデバイスに
組み込まれる
• 直線はBresenham, 円弧はMichenerのアル
ゴリズムが使われている
画素中間の上下どちらを真の直線が通過するか
1
Bresenhamアルゴリズムの考え方
dx= x2ｰx1, dy= y2 ｰy1
(x2,y2)
傾き：
d=dy／dx
①演算(x<x2の間中、
①②③を繰返す）
初期誤差：
e=0
(x1,y1)
d
1
初期出力：
(x1,y1)をプロット, x=x1,y=y1
d
x=x+1, e=e+d
②判別式：
e> 12 のとき：
y=y+1, e=eｰ1 とする
③出力
(x,y)をプロット
3
Bresenhamのアルゴリズムのまとめ
(x2,y2)
2
アルゴリズムの高速演算化
式に 2dx を掛けて整数化, 判定を正負で行う
(x2,y2)
傾き：d=2dy
(x<x2の間）
d
(x1,y1)
d
ｰdx
2dx
２．判別式：
e>0のとき：y=y+1,
e=eｰ2dx
とする
2dx
初期出力：
(x1,y1)をプロット, x=x1,y=y1
３．出力
(x,y)をプロット
4
適用領域の拡張のための変数置き換え(1/5)
dx= x2ｰx1, dy= y2 ｰy1 , d2=2*dx
全ての入れ替えを重ねる
(x1,y1)
ｙ＝－ｘ
１．初期化
(x1,y1)をプロット, d=2dy, e=ｰdx , x=x1, y=y1
（終点は周辺）
ｘ1とｘ2を
入れ替え
る範囲
２．繰り返し演算（x＜x2が成り立つとき）
2.1 x=x+1, e=e+d
2.2 もし e>0 ならば、y=y+1, e=eｰd2
2.3 (x,y)をプロット
但し、0≦ y2ｰy1 ≦ x2ｰx1 のときのみ有効
１．繰り返し演算：
x=x+1, e=e+d
初期誤差：
e=ｰdx
（始点は中心）
ｙ1とｙ2を入れ
替える範囲
ｙ＝ｘ
5
ｘとｙを入れ替える範囲
6
1
適用領域の拡張のための変数置き換え(2/5)
x1＞x2 のとき x1とx2を入れ替える
適用領域の拡張のための変数置き換え(3/5)
y1＞y2 のとき y1とy2を入れ替える
（終点は周辺）
（始点は中心）
（始点は中心）
ｘ1とｘ2を
入れ替える範囲
（終点は周辺）
ｙ1とｙ2を入れ替
える範囲
ｙ＝－ｘ
ｙ＝－ｘ
ｙ＝ｘ
ｙ＝ｘ
7
8
適用領域の拡張のための変数置き換え(4/5)
適用領域の拡張のための変数置き換え(5/5)
｜y1ーy2｜＞｜x1ーx2｜のときxとyを入れ替える
x1＞x2のとき x1とx2を入れ替える、表示点は x1+x2-x
y1＞y2のとき y1とy2を入れ替える、表示点は y1+y2-y
（終点は周辺）
ｙ＝ｘの直線
入れ替え後のｘｙの範囲
（始点は中央、終点は周辺）
（始点は中心）
ｘとｙを入れ替える範囲
｜y2ーy1｜＞｜x2ーx1｜のときxとyを入れ替える
表示点では、ｘとｙを入れ替える
ｙ＝ｘ
ｙ＝－ｘ
9
10
適用領域の拡張のための変数交換(1/4)
適用領域の拡張のための変数交換(2/4)
x2 (交換)
変換前 x: x1→x2
終点
変換後
x': x2→x1
アルゴリズムの動作
(x2,y2)
(x',y) (x ,y )
x'＝a*x＋b とすると
1 2
x2＝a*x1＋b
プロット点
x1＝a*x2＋b より
(x1+x2－x', y)
x1＞x2 の場合
(x2,y1)
x1
(x1,y1)
始点
a＝－1，b＝x1＋x2
これより
x ＝x1＋x2－ x'
の場合
11
y1
y2 xとyを交換
終点 (x2,y2)
プロット点(y, x)
(y2,x2)
(x, y):アルゴリズムの出力点
(y1,x1)
直線：y=xに
線対称
y1＞y2 の場合でも同様
x1
x2
y2ー y1 > x2ー x1 > 0
x: y1→y2
y: x1→x2
始点
(x1,y1)
12
2
適用領域の拡張のための変数交換(3/4)
可換
複数の置き換え
① x1 x2 交換
② y1 y2 交換
x
y1
③ x1
y2
2
プロットする点
①
x1+x2－x
y1+y2ーy
(y,x)
適用領域の拡張のための変数交換(4/4)
③ x1とy1の交換
x2とy2の交換
x成分とy成分を
交換してプロット
ｙ＝－ｘ
始点
(x1,y1)
最終
プロット点
① x1とx2 を交換
x1+x2－x
でプロット
② y1と y2 交換
アルゴリズム ②
出力点(x, y)
③
終点
(x2,y2)
ｙ＝ｘ
13
14
Michenerの円弧アルゴリズムの考え方
x位置の画素から(x+1)の画素の描画へ
x2+y2=r2
P
y
n
n-1
y1+y2ーyでプロット
x
OP2=x2+n2>r2
r
0
y-1
R
Q
45
°
3
2
1
Q
y
OQ2=x2+(n-1)2<r2
x
x
判別式：
D=(OP2ｰr2)+(OQ2ｰr2)
正ならばQを、
負ならばPを選択
１. xからx+1への移動時の判定式：d1
x
x+1 x+2
Q
y-1
２．x+1からx+2への移動時の判定式：d2
d1≧0,
d2≧0
＜0ならばQ
16
d1<0 のとき： x+1からx+2への移動時の判定式：d2
真円
y
d1≧0の
とき
d1≧0,
d2<0
d1=eQ+eR ≧0ならばR
最適なｙ座標値の判定式(1/2)
xからx+1、x+1からx+2の２段階の移動を考える
d1<0,
d2≧0
真円
２次式であり、計算時間がかかる
判定式を高速に計算するために
d1<0,
d2<0
eQ
eR
eQ=(x+1)2+y2ｰr2
eR=(x+1)2+(yｰ1)2ｰr2
xから(x+1)に移るときの判定式 d1 は
d1=2(x+1)2+y2+(yｰ1)2ｰ2r2
15
d1<0の
とき
x+1
R
なぜなら
17
d2=(x+2)2+y2ｰr2
+(x+2)2+(yｰ1)2ｰr2
=d1+4x+6
となる
d1=2(x+1)2+y2+(yｰ1)2ｰ2r2
18
3
最適なｙ座標値の判定式(2/2)
d1≧0 のとき：x+1からx+2への移動時の判定式：d2
真円
y
x
x+1 x+2
y-1
Q
y-2
d2=(x+2)2+(yｰ1)2ｰr2
+(x+2)2+(yｰ2)2ｰr2
=d1+4(xｰy)+10
となる
R
なぜなら
d1=2(x+1)2+y2+(yｰ1)2ｰ2r2
x＝0からr/√2 まで、半径ｒの
1/8円弧をプロットする
円の方程式：x2＋y2 ＝r2
ｘ０＝０；ｙ０＝ｒ；
P0（x0,y0）
Q
R
まず最初の判別式d１を求める
d１＝ｅＱ１＋ｅＲ１
０
＝（ｘ０＋１）2＋ｙ０2－ｒ2
＋（ｘ０＋１）2＋（ｙ０－１）2－ｒ2
＝１＋ｒ2－ｒ2＋１＋（ｒ－１）2－ｒ2
（∵ ｘ０＝０，ｙ０＝ｒ）
＝３－２ｒ
19
Michenerアルゴリズムのまとめ
（中心が原点の場合に１／８円をプロット）
１．初期化 x=0, y=r, d=3ｰ2r, (x,y)をプロット
２．繰り返し計算(x<yが成り立つ間)
もし(d<0)ならば、d=d+4x+6
2.1
そうでなければ、d=d+4(xｰy)+10, y=yｰ1
2.2 x=x+1
y
2.3 (x,y)をプロット
0
x
21
Ｘ
20
適用領域の拡張のための変数追加
(-x,y)
(y,-x)
y
アルゴリズムの
出力点(x, y)
(y, x)
(x, y)が円周上の点ならば
x
0
(-y,-x)
y=x (-x,-y)
に線対称
(-y, x)
(x,-y)
(±x, ±y),(±y, ±x)も
同様に円周上の点
中心が(x0,y0)の円を描くには(x,y)の代わりに、
(x0±x，y0±y)，(x0±y,y0±x)にプロットする
複号任意 (合計8通りある)
22
4

Download Report