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

ng th ng ng th ng

ậ v đ ẽ ườ v đ ẽ ườ

ẳ ẳ

11

Xét k<1 Xét k<1

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 & ơ ớ ơ ớ yy

 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 th ng đ ẳ ng th ng đ ẳ ể ể ấ ấ ộ ộ 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 i thi u: Gi ệ ớ i thi u: Gi ệ ớ • Gi s đ Gi c x p x thành các đi m l n l ả ử ườ ượ s đ c x p x thành các đi m l n l ả ử ườ ượ (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

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

yi+1

yi

yi-1

33

xi

xi+1

Thu t toán Bresenham (ti p) Thu t toán Bresenham (ti p)

ế ế

ậ ậ

11, y, y11) và (x

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

11-kx-kx11..

Ph • Ph y=kx+m v i m=Dy/Dx và m=y y=kx+m v i m=Dy/Dx và m=y ng trình đ ng trình đ ớ ớ

i+1i+1 ph ụ ph ụ

ọ ọ ọ ọ ộ ủ ộ ủ

ộ ủ ủ

Ng – Ng

• Đ t dặĐ t dặ 11=y-y=y-yii và d ộthu c vào d thu c vào d – N u dếN u dế

i+1i+1=y=yii+1+1

và d22=(y=(yii+1)-y, do đó vi c ch n t a đ c a y +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 ấ 11 và d ấ 11-d-d22<0 thì ch n yọ i+1i+1=y=yii <0 thì ch n yọ 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 Bresenham (ti p) Thu t toán Bresenham (ti p)

ế ế

ậ ậ

• dd11 - d - d22 = (2y – 2y ứ kk = (2y – 2yii – 1) là m t s th c do ch a – 1) là m t s th c do ch a ộ ố ự ộ ố ự ứ

– C = 2Dy + (2b - 1)Dx C = 2Dy + (2b - 1)Dx

• Xét pXét pi i = Dx (d = Dx (d1 1 - d- d22) = Dx (2y - 2y ) = Dx (2y - 2yi i - 1) = 2Dy x - 1) = 2Dy xii - 2Dx y - 2Dx yi i + C + C

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

i+1i+1

) gi ng nhau nên khi xét d u c a p và (d11-d-d22) gi ng nhau nên khi xét d u c a p ii và (d c y c y Do d u c a p ủ ấ • Do d u c a p ủ ấ xác đ nh đ ượ ị xác đ nh đ ượ ị

i+1 + C) - (2Dy x

i+1i+1 – p – pii = (2Dy x

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

ặM c khác, p • M c khác, p C) = 2Dy – 2Dx(yi+1i+1 – y – yii)) C) = 2Dy – 2Dx(y

ừ

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 ượ ạ

i+1i+1=y=yii+1 nên p

ừ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ế

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

55

11, y, y11) là p

c tính t c tính t i (x i (x ượ ượ ạ ạ ) là p1 1 = 2Dy x = 2Dy x1 1 -2Dx y -2Dx y1 1 + C + C

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

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

Cài đ t thu t toán (v i Dx>Dy>0) Cài đ t thu t toán (v i Dx>Dy>0)

ớ ớ

ậ ậ

ặ ặ

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

ươ ươ

ỉ ỉ

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 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 v hình sau Cài đ t thu t toán Bresenham v hình sau

ẽ ẽ

ậ ậ

ặ ặ

1515