• 検索結果がありません。

走査変換(1)

N/A
N/A
Protected

Academic year: 2021

シェア "走査変換(1)"

Copied!
31
0
0

読み込み中.... (全文を見る)

全文

(1)

コンピュータグラフィックス

(2)

デジタル画像の生成

2 ベクトルデータ デジタル画像 ラ ス タ ラ イ ズ 頂点 頂点 頂点 頂点 頂点 三角形 線分

(3)

走査変換(スキャンコンバージョン)

ベクトルデータのデジタル画像化(ラスタライズ)

線分を描く

円を描く

台形を塗りつぶす

三角形を塗りつぶす

任意の多角形を塗りつぶす

3

(4)

線分を描く

2点

(x

0

, y

0

),(x

1

, y

1

) を結ぶ線分の生成

条件

• x0 < x1 • y0 < y1 • x1 – x0 > y1 – y0 4 (x0, y0) (x1, y1) この 範囲だけ を対象にする yy0 = xx0 (x0, y0) y x

(5)

直線の方程式

y = ax + b

a = (y

1

– y

0

) / (x

1

– x

0

)

b = y

0

– ax

0 5

(x

0

, y

0

)

(x

1

, y

1

)

a

1

x

1

– x

0

> y

1

– y

0

a < 1

(6)

水平線を描く

6 x0 x1 y BEGIN x ← x0 (x, y) に 点を打つ x ←x + 1 x < x1 END Y N x←x0 x←x+1 x←x+1

(7)

傾きを累積して斜線を描く

7 x0 y0 BEGIN x ← x0 (x, y+0.5) に 点を打つ x ← x + 1 x < x1 END Y N y1 y ← y0 y ← y + a a a x1

(8)

傾きの代わりに誤差を用いる

8 0 0.5 e < 0.5 e > 0.5 e – 1 BEGIN x ← x0 y ← y0 (x, y) に 点を打つ x ← x + 1 x < x0 END Y N e ← 0 e ← e + a y ← y + 1 e ← e – 1 e>0.5 1 e = 0

(9)

誤差の初期値をずらす

9 0 e < 0 e > 0 e – 1 BEGIN x ← x0 y ← y0 (x,y) に 点を打つ x ← x + 1 x < x0 END Y N e ← –0.5 e ← e + a y ← y + 1 e ← e – 1 e > 0 0との 比較 e = −0.5 0.5 −0.5

(10)

処理の整数化

次に打つべき点の位置の候補は次の2つ

(x + 1, y + 1)

(x + 1, y)

上のいずれかを選択する

e に対する加減算の後,符号判定により判断できる

e に関する処理に正の定数をかけても結果は同じ

e に関する処理を

2(x

1

– x

0

)

倍する

10 (x + 1, y + 1) (x + 1, y)

(11)

e に関する処理を 2(x

1

– x

0

) 倍

11 BEGIN x ← x0 y ← y0 (x,y) に 点を打つ x ← x + 1 x < x0 END Y N e ← –(x1 – x0) e ← e + 2(y1 – y0) y ← y + 1 e ← e – 2(x1 – x0) e > 0

(12)

始点と終点の変位

x y dx dy (x0, y0) (x1, y1) dx = x1 - x0 dy = y1 - y0 12 x y (x0, y0) (x1, y1)

(13)

線分を生成する8分の1象限

x y dx > 0 dy > 0 dx > dy x y -dx < dy -dx < -dy dx < -dy -dx > dy -dx > -dy dx > dy dx > -dy dx < 0 dy > 0 dx < 0 dy > 0 dx < 0 dy < 0 dx > 0 dy < 0 dx < dy 13

(14)

象限ごとの処理

x y y ← y + 1 時々 x ← x + 1 x ← x + 1 時々 y ← y + 1 y ← y + 1 時々 x ← x - 1 x ← x + 1 時々 y ← y - 1 x ← x - 1 時々 y ← y + 1 x ← x - 1 時々 y ← y - 1 y ← y - 1 時々 x ← x + 1 y ← y - 1 時々 x ← x - 1 14 それ以外なら 右を |dy|+1回 繰り返し ・y の増分計算x 方向の誤差  判定に基づく  x の増分計算 x の増分計算 dx≧0 なら: それ以外なら: x ← x + 1 x ← x - 1 y の増分計算 dy≧0 なら: それ以外なら: y ← y + 1 y ← y - 1 ・x の増分計算y 方向の誤差  判定に基づく  y の増分計算 |dx|≧|dy| なら 右を |dx|+1回 繰り返し 増分方向の決定

(15)

点の位置 (x, y) に始点の位置 (x0, y0) を設定

Bresenham のアルゴリズム (1)

15 BEGIN x ← x0 y ← y0 1

(16)

ix, iy : 線の進行方向 dx, dy : 線分の幅と高さ

Bresenham のアルゴリズム (2)

16 ix ← 1 dx ← x1 – x0 1 dx< 0 ix ← –ix dx ← –dx iy ← 1 dy ← y1 – y0 2 dy< 0 iy ← –iy dy ← –dy Y N Y N 3 2

(17)

d : 点を打つ数 e : 誤差 a : 誤差の増分 b : 誤差の補正量 ax, ay : 毎回の増分 bx, by : 補正時のの増分

Bresenham のアルゴリズム (3)

17 3 dx<dy d ← dx e ← –dx a ← 2dy b ← –2dx ax ← ix ay ← 0 bx ← 0 by ← iy d ← dy e ← –dy a ← 2dx b ← –2dy ax ← 0 ay ← iy bx ← ix by ← 0 N Y 4

(18)

x, y, e の更新

Bresenham のアルゴリズム (4)

18 点を打つ (x, y) に 点を打つ 4 x ← x + a x y ← y + ay e ← e + a 5 e > 0 x ← x + bx y ← y + by e ← e + b 7 5 Y N 6

(19)

点を全部打ったら終わり

Bresenham のアルゴリズム (5)

19 d > 0 d ← d – 1 END N Y 6 7

(20)

円を描く

x

y

y

y −1

y

y −1

20 この 1/8 円に つ い て 考 え る x を 1 増すたびに (x, y – 1) と (x, y) の どちらに点を打つか 判断する

(21)

真の円との二乗誤差による判定

P

Q

R

O

r

21 しかし 絶対値を とるのが イヤ Eq

E

r

(22)

したがって di+1 < 0 ならば Q di+1 > 0 ならば R

絶対値を使わずに判別する

di+1 = Eq + Er とおく 真の線が Aを通るコース(Qを選ぶ) • Eq< 0, Er < 0 ⇒ di+1 < 0 Cを通るコース(Rを選ぶ) • Eq> 0, Er > 0 ⇒ di+1 > 0 Bを通るコース • Eq> 0, Er < 0 • Qを選ぶべきコースなら |Eq| < |Er | ⇒ di+1 < 0 • Rを選ぶべきコースなら |Eq| > |Er | ⇒ di+1 > 0

Q

R

A

B

C

P

O

22

(23)

d

i+1

を漸化式で表す

23

d

i+1

= E

q

+ E

r

= x

{

(

i

+1

)

2

+ y

i2

- r

2

}

+ x

{

(

i

+1

)

2

+ y

(

i

- 1

)

2

- r

2

}

d

i

= x

{

(

i- 1

+1

)

2

+ y

i- 12

- r

2

}

+ x

{

(

i- 1

+1

)

2

+ y

(

i-1

- 1

)

2

- r

2

}

di+1 - di = x

{

(

i +1

)

2 + yi2 - r2

}

+ x

{

(

i +1

)

2 + y

(

i - 1

)

2 - r2

}

-

{

(

xi- 1 +1

)

2 + yi- 12 - r2

}

+ x

{

(

i- 1 +1

)

2 + y

(

i- 1 - 1

)

2 - r2

}

(24)

d

i

< 0 のとき

この場合は

Q を選択

これを代入すれば

24 xi = xi- 1 +1 yi = yi- 1 ì í î di+1 - di = 4xi- 1+ 6 di+1 = di + 4xi- 1 + 6

(25)

d

i

0 のとき

この場合は

R を選択

これを代入すれば

25 xi = xi- 1 +1 yi = yi- 1 - 1 ì í î di+1 - di = 4 x

(

i- 1 - yi- 1

)

+10 di+1 = di + 4 x

(

i- 1 - yi- 1

)

+10

(26)

起点(真上)では

x

0

= 0, y

0

= r, d

0

= 0

26 d1 = x

{

(

0 +1

)

2 + y0 - r2

}

+ x

{

(

0 +1

)

2 + y

(

0 - 1

)

- r2

}

= 3- 2r

x

y

r (0, r) O

(27)

Michener のアルゴリズム (1)

27 点の位置 (x, y) に真上の位置 (0, r) を設定 d に 3 – 2r を設定 BEGIN x ← 0 y ← r d ← 3 – 2r 1

(28)

(xc+ x, yc+ y), (xc– x, yc– y) (xc+ y, yc+ x), (xc– y, yc– x) (xc+ x, yc– y), (xc– x, yc+ y) (xc– y, yc+ x), (xc+ y, yc– x) に点を打つ x y

Michener のアルゴリズム (2)

28 1 4 2 同時に8点描く (xc+ x, yc+ y) (xc– x, yc– y) (xc+ y, yc+ x) (xc– y, yc– x) (xc+ x, yc– y) (xc– x, yc+ y) (xc– y, yc+ x) (xc+ y, yc– x)

(29)

Michener のアルゴリズム (3)

29 2 d > 0 x ← x + 1 Y N d ← d + 4(x – y) + 10 y ← y – 1 d ← d + 4x + 6 2 d > 0 x ← x + 1 d ← d + 4x + 2 Y N y ← y – 1 d ← d – 4y 改良 3 3

(30)

1/8円描いたら終わり

Michener のアルゴリズム (4)

30 x < y END Y N 2 4

x

y

x < y

(31)

おわり

参照

関連したドキュメント

 私は,2 ,3 ,5 ,1 ,4 の順で手をつけたいと思った。私には立体図形を脳内で描くことが難

婚・子育て世代が将来にわたる展望を描ける 環境をつくる」、「多様化する子育て家庭の

 少子高齢化,地球温暖化,医療技術の進歩,AI

LLVM から Haskell への変換は、各 LLVM 命令をそれと 同等な処理を行う Haskell のプログラムに変換することに より、実現される。

変容過程と変化の要因を分析すべく、二つの事例を取り上げた。クリントン政 権時代 (1993年~2001年) と、W・ブッシュ政権

・患者毎のリネン交換の検討 検討済み(基準を設けて、リネンを交換している) 改善 [微生物検査]. 未実施

★分割によりその調査手法や評価が全体を対象とした 場合と変わることがないように調査計画を立案する必要 がある。..

❏重量車モード(都市内走 行モード( JE05 モ ード)と 都市間走行モード(縦断勾 配 80km/h 定速モード))を エンジン回転数・ トルクに