Thu t toán v đ Thu t toán v đ

ng th ng Bresenham ng th ng Bresenham

ẽ ườ ẽ ườ

ậ ậ

ẳ ẳ

11

M i t M i t

ữ ữ

khi đ l n h s góc nh h n 1 khi đ l n h s góc nh h n 1

ng quan gi a X & Y ng quan gi a X & Y ỏ ơ ỏ ơ

ố ươ ố ươ ộ ớ ộ ớ

ệ ố ệ ố

Dy

Dx

nguyên hay tăng 1 nguyên hay tăng 1 ườ ườ liên t cụ liên t cụ ữ ữ ả ả

ệ ố ệ ố ộ ớ ộ ớ ủ ủ ủ ủ ổ ổ

 x tăng 1 và y gi x tăng 1 và y gi ng th ng Đi u này b o đ m cho đ ề ẳ ả ng th ng Đi u này b o đ m cho đ ề ẳ ả N u đ l n c a h s góc l n h n 1, chúng ta đ i vai trò c a x N u đ l n c a h s góc l n h n 1, chúng ta đ i vai trò c a x ơ ớ ế ế ơ ớ & y& y

 x đ x đ ượ ượ c g i là giá tr đ c l p và y là ị ộ c g i là giá tr đ c l p và y là ị ộ ậ ậ ọ ọ giá tr ph thu c ộ giá tr ph thu c ộ ụ ụ ị ị

22

ậ

ậThu t toán Bresenham Thu t toán Bresenham

ấ ấ ỉ ỉ

ng cong đ ng cong đ ể ể ộ ộ t là ầ ượ ể t là ầ ượ ể c hi n th trên ị ể ượ c hi n th trên ị ể ượ

c t a đ (x c t a đ (x

ế ế c i+1 là (x c i+1 là (x c th i, thì ) c a b ộ ii,y,yii) c a b ứ ủ c th i, thì ủ ứ ộ c xác đ nh nh th nào. c xác đ nh nh th nào. i thi u: Gi ệ ớ i thi u: Gi ệ ớ • Gi c x p x thành các đi m l n l s đ Gi ả ử ườ ượ c x p x thành các đi m l n l s đ ả ử ườ ượ (x(xii,y,yii)). Các đi m này có t a đ nguyên và đ . Các đi m này có t a đ nguyên và đ ọ ọ màn hình. màn hình. Bài toán đ t ra là n u bi ặ • Bài toán đ t ra là n u bi ặ b đi m ể ở ướ b đi m ể ở ướ ị ị ướ ướ ư ế ư ế t đ ế ượ ọ t đ ế ượ ọ ) s đ i+1i+1,y,yi+1i+1) s đ ẽ ượ ẽ ượ

ng h p h s góc 0<=m<=1, chúng ta có x ng h p h s góc 0<=m<=1, chúng ta có x ệ ố ệ ố ợ ợ +1 và i+1i+1=x=xii+1 và

Trong tr ườ • Trong tr ườ yyi+1i+1=y=yii hay y hay yi+1i+1=y=yii+1+1

yi+1

yi

yi-1

33

xi

xi+1

ậThu t toán ậ Thu t toán

ng th ng qua 2 đi m (x ng th ng qua 2 đi m (x ẳ ẳ ể ể ườ ườ ươ ươ ) là ) và (x22, y, y22) là

11, y, y11) và (x

Ph • Ph y=mx+b v i m=Dy/Dx và b=y y=mx+b v i m=Dy/Dx và b=y

ọ ọ ộ ủ i+1i+1 ph ụ ph ụ ọ ọ ộ ủ

ộ

Ng – Ng

ng trình đ ng trình đ 11-mx-mx11.. ớ ớ • Đ t dặĐ t dặ 11=y-y=y-yii và d +1)-y, do đó vi c ch n t a đ c a y và d22=(y=(yii+1)-y, do đó vi c ch n t a đ c a y ệ ệ ấ ủ 1 1 - d- d22):): ( hay d u c a d và d22 ( hay d u c a d ộthu c vào d 11 và d thu c vào d ấ ủ <0 thì ch n yọ i+1i+1=y=yii – N u dếN u dế 11-d-d22<0 thì ch n yọ ọ i+1i+1=y=yii+1+1 i, ch n y c l ượ ạ i, ch n y c l ọ ượ ạ

P

yi+1

d2

(xi+1,y=f(xi+1))

d1

S

yi

xi

xi+1=xi+1

44

ậ

ậThu t toán (cont.) Thu t toán (cont.)

• dd11 - d - d22 = (2y – 2y • Xét pXét pi i = Dx (d = (2y – 2yii – 1) là m t s th c do ch a – 1) là m t s th c do ch a ứ mm ộ ố ự ứ ộ ố ự - 1) = 2Dy xii - 2Dx y ) = Dx (2y - 2yi i - 1) = 2Dy x = Dx (d1 1 - d- d22) = Dx (2y - 2y - 2Dx yi i + C + C

ố ố thì ta ấ ủ ii thì ta ấ ủ

ặ

i+1 + C) - (2Dy x

– C = 2Dy + (2b - 1)Dx C = 2Dy + (2b - 1)Dx và (d11-d-d22) gi ng nhau nên khi xét d u c a p Do d u c a p ) gi ng nhau nên khi xét d u c a p ấ ủ ii và (d • Do d u c a p ấ ủ c y xác đ nh đ ượ i+1i+1 ị c y xác đ nh đ ượ ị i+1i+1 – p – pii = (2Dy x

= (2Dy xi+1i+1 - 2Dx y + C) - (2Dy xii - 2Dx y - 2Dx yi+1 + C) - 2Dx yi i + C)

ừ

ặM c khác, p • M c khác, p = 2Dy – 2Dx(yi+1i+1 – y – yii)) = 2Dy – 2Dx(y ừT đây, ta suy ra cách tính p • T đây, ta suy ra cách tính p – N u pếN u pế

Ng – Ng

<0 thì yi+1i+1=y=yii nên p ii<0 thì y i thì y c l ượ ạ i thì y c l ượ ạ

theo pii:: i+1i+1 theo p nên pi+1i+1 = p = pii + 2Dy + 2Dy + 2Dy – 2Dx +1 nên pi+1i+1 = p = pii + 2Dy – 2Dx i+1i+1=y=yii+1 nên p i (x c tính t i (x c tính t ị ị ầ ầ ượ ượ ạ ạ

11, y, y11) là p

) là p1 1 = 2Dy x = 2Dy x1 1 -2Dx y + C = -2Dx y1 1 + C =

Giá tr p đ u tiên đ • Giá tr p đ u tiên đ 2Dy – Dx 2Dy – Dx

55

Begin

p = 2Dy - Dx; const1=2Dy; const2=2(Dy-Dx); x = x1; y = y1; putpixel(x,y,color);

x

End

p<0

p=p+const2; y = y + 1;

p=p+const1;

x=x+1; putpixel(x,y,color);

66

ng trình (Dx>Dy>0) ng trình (Dx>Dy>0)

ươCh ươ Ch

void BresenhamLine(int x1, int y1, int x2, int y2, int color) void BresenhamLine(int x1, int y1, int x2, int y2, int color)

{{ int Dx = x2 – x1, Dy = y2 – y1; int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int x = x1, y = y1; int p = 2 * Dy – Dx; int p = 2 * Dy – Dx; int const1 = 2 * Dy, const2 = 2 * (Dy-Dx); int const1 = 2 * Dy, const2 = 2 * (Dy-Dx);

putpixel(x, y, color); putpixel(x, y, color);

while (x < x2) { while (x < x2) { if (p < 0) { if (p < 0) {

p += const1; p += const1;

} else { } else {

p += const2; p += const2; y++; y++;

}} x++; x++; putpixel(x, y, color); putpixel(x, y, color);

}}

}}

77

T ng k t ế T ng k t ế

ổ ổ

y đ n đi m hi n hành y đ n đi m hi n hành ừ ừ ệ ệ ế ế ể ể và d22 sao cho d 11 và d là đ l ch t sao cho d11 là đ l ch t ộ ệ ộ ệ

ấ ớ ấ ớ cùng d u v i (d sao cho pii cùng d u v i (d ii sao cho p ) và mang giá tr ị 11 – d – d22) và mang giá tr ị

ng ng ườ ườ ng h p p ợ ng h p p ợ ườ ườ theo 2 tr theo pii theo 2 tr > 0. Chú ý tr < 0 và pi i > 0. Chú ý tr i i < 0 và p

Xác đ nh d ị • Xác đ nh d ị yyii Xác đ nh p • Xác đ nh p ị ị nguyên nguyên Tính pi+1i+1 theo p • Tính p h p pợh p pợ = 0. ii = 0. Tính p11 • Tính p

P

yi+1

d2

(xi+1,y=f(xi+1))

d1

S

yi

xi

xi+1=xi+1

88

ở ộM r ng ở ộ M r ng

3

2

1 Dx>0,Dy>0,Dx>Dy

4 Dx<0,Dy>0,|Dx|>Dy

8 Dx>0,Dy<0,Dx>|Dy|

5 Dx<0,Dy<0,|Dx|>|Dy|

6

7

99

K t h p vùng 1 và 8 K t h p vùng 1 và 8

ế ợ ế ợ

• x tăng 1 x tăng 1 • Vùng 1 y Vùng 1 y tăng tăng còn vùng 2 y còn vùng 2 y gi mảgi mả

...... int dy = (Dy < 0) ? -1 : 1; int dy = (Dy < 0) ? -1 : 1; Dy = abs(Dy); Dy = abs(Dy); while (x < x2) { while (x < x2) { if (p < 0) { if (p < 0) {

p += const1; p += const1;

} else { } else {

p += const2; p += const2; y += dy; y += dy;

}} x++; x++; putpixel(x, y, color); putpixel(x, y, color);

}} ......

1010

K t h p vùng 1 và 4 K t h p vùng 1 và 4

ế ợ ế ợ

tăng 1, vùng 4 x 1, vùng 4 x gi mảgi mả 1 1

• Vùng 1 x Vùng 1 x tăng • tăng y y tăng

...... int dx = (Dx < 0) ? -1 : 1; int dx = (Dx < 0) ? -1 : 1; Dx = abs(Dx); Dx = abs(Dx); while (x != x2 while (

x != x2) {) { if (p < 0) { if (p < 0) {

p += const1; p += const1;

} else { } else {

p += const2; p += const2; y++; y++;

}} x += dx; x += dx; putpixel(x, y, color); putpixel(x, y, color);

}} ......

1111

K t h p vùng 1, 4, 5, 8 K t h p vùng 1, 4, 5, 8

ế ợ ế ợ

• • x x tăng y y tăng tăng 1 khi Dx > 0, tăng khi Dy > 0, 1 khi Dx > 0, gi mảgi mả 1 khi Dx < 0 1 khi Dx < 0 khi Dy < 0 khi Dy > 0, gi mảgi mả khi Dy < 0

...... int dx = (Dx < 0) ? -1 : 1; int dx = (Dx < 0) ? -1 : 1; Dx = abs(Dx); Dx = abs(Dx); int dy = (Dy < 0) ? -1 : 1; int dy = (Dy < 0) ? -1 : 1; Dy = abs(Dy); Dy = abs(Dy);

while (x != x2 while (

x != x2) {) { if (p < 0) { if (p < 0) {

p += const1; p += const1;

} else { } else {

p += const2; p += const2; y += dy; y += dy;

}} x += dx; x += dx; putpixel(x, y, color); putpixel(x, y, color);

1212

}} ......

K t h p vùng 2, 3, 6, 7: K t h p vùng 2, 3, 6, 7:

x tính theo y x tính theo y

ế ợ ế ợ

• • y y tăng x x tăng tăng 1 khi Dy > 0, tăng khi Dx > 0, 1 khi Dy > 0, gi mảgi mả 1 khi Dy < 0 1 khi Dy < 0 khi Dx < 0 khi Dx > 0, gi mảgi mả khi Dx < 0

...... int dx = (Dx < 0) ? -1 : 1; int dx = (Dx < 0) ? -1 : 1; Dx = abs(Dx); Dx = abs(Dx); int dy = (Dy < 0) ? -1 : 1; int dy = (Dy < 0) ? -1 : 1; Dy = abs(Dy); Dy = abs(Dy);

while (y != y2 while (

y != y2) {) { if (p < 0) { if (p < 0) {

p += const1; p += const1;

} else { } else {

p += const2; p += const2; x += dx; x += dx;

}} y += dy; y += dy; putpixel(x, y, color); putpixel(x, y, color);

1313

}} ......

Ch Ch

ng trình hoàn ch nh ng trình hoàn ch nh

ươ ươ

ỉ ỉ

BresenhamLine(int x1, int y1, int x2, int y2, int color) { BresenhamLine(int x1, int y1, int x2, int y2, int color) {

int Dx = x2 – x1, Dy = y2 – y1; int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int x = x1, y = y1;

int dx = (Dx < 0) ? -1 : 1; int dx = (Dx < 0) ? -1 : 1; int dy = (Dy < 0) ? -1 : 1; int dy = (Dy < 0) ? -1 : 1;

Dx = abs(Dx); Dx = abs(Dx); Dy = abs(Dy); Dy = abs(Dy);

putpixel(x, y, color); putpixel(x, y, color); if (Dx > Dy) if (Dx > Dy) {{

int p = 2 * Dy – Dx; int p = 2 * Dy – Dx; int const1 = 2 * Dy, const2 = 2 * (Dy-Dx); int const1 = 2 * Dy, const2 = 2 * (Dy-Dx);

while (x != x2 while (

x != x2) {) {

if (p < 0) { if (p < 0) {

p += const1; p += const1;

} else { } else {

p += const2; p += const2; y += dy; y += dy;

}} x += dx; x += dx; putpixel(x, y, color); putpixel(x, y, color);

}}

ữ ữ

đ i vai trò gi a x và y ổ } else {// đ i vai trò gi a x và y ổ } else {//

……

}}

}}

1414

Bài t pậ Bài t pậ

ặ ặ ườ Cài đ t thu t toán Bresenham cho: ậ Cài đ t thu t toán Bresenham cho: ậ ườĐ ng tròn tâm (x • Đ ng tròn tâm (x

ườ + (y-ycc))22 ộ ộ

= R= R22 cc,y,ycc) bán kính R: (x-x ) bán kính R: (x-xcc))2 2 + (y-y ) bán kính dài là a, r ng là b: (x-x cc,y,ycc) bán kính dài là a, r ng là b: (x-x

+ (y- cc))2 2 / a/ a22 + (y-

ườĐ ng elip tâm (x • Đ ng elip tâm (x / b/ b2 2 = 1= 1 yycc))22

1515