LineDrawing

ĐỒ HỌA MÁY TÍNH

Các thuật toán vẽ đường
Dẫn nhập

? Giả sử tọa độ các điểm nguyên sau khi xấp xỉ đối
tượng thực lần lượt là ?xi, yi?, i ??0,... . Đây là các điểm
nguyên sẽ được hiển thị trên màn hình.
? Bài toán đặt ra là nếu biết được ?xi, yi? là tọa độ
nguyên xác định ở bước thứ i, điểm nguyên tiếp theo
?xi?1,yi?1?sẽ được xác định như thế nào.
? Đối tượng hiển thị trên lưới nguyên được liền nét,
các điểm mà ? 1?
xi?1,yi? có thể chọn chỉ là một trong
tám điểm được đánh số từ 1 đến 8 trong hình sau
(điểm đen chính là ?xi, yi??).Hay nói cách khác :
?xi?1,yi?1???xi??1, yi??1??.





4


5


6





3






7





2


1


8



? Dáng điệu của đường sẽ cho ta gợi ý khi chọn một
trong tám điểm trên. Cách chọn các điểm như thế
nào sẽ tùy thuộc vào từng thuật toán trên cơ sở xem
xét tới vấn đề tối ưu tốc độ.




Dương Anh Đức, Lê Đình Duy




Các thuật toán vẽ đường 1/22

ĐỒ HỌA MÁY TÍNH

Thuật toán vẽ đường thẳng


? Xét đoạn thẳng có hệ số góc


0 ??m ??1 và


Dx ??0 .
? Với các đoạn thẳng dạng này, nếu ?xi, yi? là điểm
đã xác định được ở bước thứ i (điểm màu đen) thì
điểm cần chọn ?xi?1,yi?1?ở bước thứ (i+1) sẽ là một
trong hai trường hợp như hình vẽ sau :
?xi1
??xi
??1
?
?








yi
y

i
?
?1
?
?y , y
i i




2


1



xi
?
??1

(xi+1, yi+1)


(xi+1, yi)





? Vấn đề còn lại, là cách chọn một trong hai điểm trên
như thế nào để có thể tối ưu về mặt tốc độ.














Dương Anh Đức, Lê Đình Duy














Các thuật toán vẽ đường 2/22

ĐỒ HỌA MÁY TÍNH

Thuật toán DDA (Digital Differential Analyzer)

? Việc quyết định chọn

yi?1 là yi hay

yi??1 , dựa vào
phương trình của đoạn thẳng y ??mx ??b . Nghĩa là,
ta sẽ tính tọa độ của điểm ?xi??1, y? thuộc về đoạn
thẳng thực. Tiếp đó,
tròn giá trị tung độ y.
yi?1
sẽ là giá trị sau khi làm
?
1?
? Như vậy :
y ??m xi? ??b
yi?1?Round???




(xi+1, Round(y))






(xi+1, y)



(xi, yi)
? Nếu tính trực tiếp giá trị thực y ở mỗi bước từ
phương trình y ??mx ??b thì phải cần một phép toán
nhân và một phép toán cộng số thực. Để cải thiện
tốc độ, người ta tính giá trị thực của y ở mỗi bước
theo cách sau để khử phép tính nhân trên số thực :

? Nhận xét rằng :
y


sau

?
mx


i?1
?
??b ??m xi?
1????b
ytrước
??mxi??b
? ysau? ytrước?m




Dương Anh Đức, Lê Đình Duy







Các thuật toán vẽ đường 3/22

ĐỒ HỌA MÁY TÍNH

Lưu đồ thuật toán DDA


Begin






m=Dy/Dx;
x=x1;
y=y1;
putpixel(x, Round(y), c);



















x=x+1;
y=y+m;







x




Yes








No
putpixel(x, Round(y),c);















End



Dương Anh Đức, Lê Đình Duy



Các thuật toán vẽ đường 4/22

ĐỒ HỌA MÁY TÍNH

? Ví dụ : Cho A(12, 20) và B(22, 27), ta có m= 0.7
i
0
1
2
3
4
5
6
7
8
9
10
xi
12
13
14
15
16
17
18
19
20
21
22
yi
20
21
21
22










27
y
20
20.7
21.4
22.1
? Cài đặt minh họa thuật toán DDA

#define Round(a) int(a+0.5)
int Color = GREEN;


void LineDDA (int x1, int y1, int x2, int y2)
{
int x = x1;
float y = y1;
float m = float(y2-y1)/(x2-x1);


putpixel(x, Round(y), Color);
for(int i=x1; i{
x++;
y +=m;
putpixel(x, Round(y), Color);
}
} // LineDDA


Dương Anh Đức, Lê Đình Duy


Các thuật toán vẽ đường 5/22

ĐỒ HỌA MÁY TÍNH

Thuật toán Bresenham









(xi+1, y)
yi+1 P
y

yiS



xixi+1


















d2

d1
? Gọi ?xi??1, y?
? ????b
y ??m xi??1
d1? y ??yi



.
là điểm thuộc đoạn thẳng. Ta có:
? Đặt d2
????yi??1????y

? Xét tất cả các vị trí tương đối của y so với yivà
yi??1 , việc chọn điểm ? ?1?
xi?1,yi là S hay P phụ thuộc
vào việc so sánh d1 và d2hay dấu của

? Nếu d1??d2??0
d1??d2 :

y?1?y
, ta sẽ chọn điểm S, tức là
d1??d2??0
i
i .
? Ngược lại, nếu
yi?1?yi??1
, ta sẽ chọn điểm P, tức là

? Xét

p
i

?
?
Dx d
1

?

d
2
?

?
?
Dx 2 y

??2

y


i

?
1?

p
?
?
?
?
?
1?
?
?
Dx 2 m x
1
b
2
y
i
i
? ? ?
i
?






Dương Anh Đức, Lê Đình Duy






Các thuật toán vẽ đường 6/22




? Thay




m ?Dy

ĐỒ HỌA MÁY TÍNH


vào phương trình trên ta được :
Dx
p
i
??2Dyx
i
?
2Dxyi??c , với
c
?
2Dy
?
?2b
?
1?Dx .

? Nhận xét rằng nếu tại bước thứ i ta xác định được
dấu của pi
thì xem như ta xác định được điểm cần
chọn ở bước (i+1).

? Ta có :
pi?1 ??pi???2Dyxi?1 ??2Dxyi?1?c???2Dyxi??2Dxyi??c?

p

p

2
?
?

2
?
i?
?

p
i?1
?

p
i
?
Dy xi?1 ??xi
Dy ?
?
Dx yi?1 ??y
?
?
i?1
?
i
??2
??2Dx yi?1 ??yi
 , do
xi?1?xi??1

? Từ đây ta có thể suy ra cách tính

pi?1 từ pi như sau :

? Nếu

pi??0 thì

pi?1?p
i

??2Dy do ta chọn

yi?1?

yi.

? Ngược lại, nếu

pi??0 , thì pi?1?p


i

??2Dy ??2Dx , do
ta chọn
yi?1?yi
??1 .

? Giá trị p0 được tính từ điểm vẽ đầu tiên ?
theo công thức :

x0, y0?
p
0
??2Dyx
0
??2Dxy
0
c
? ?
2Dyx


0

?
2Dxy
0

?
2Dy

?
?2b

?
1?Dx
? Do ?x0, y0?

là điểm nguyên thuộc về đoạn thẳng

nên ta có
y
0
??mx

0
bDyx
? ?

0

?
b

. Thế vào phương
trình trên ta suy ra :
Dx
p0??2 Dy ??Dx
.








Dương Anh Đức, Lê Đình Duy








Các thuật toán vẽ đường 7/22

ĐỒ HỌA MÁY TÍNH

Lưu đồ thuật toán Bresenham

Begin




p=2Dy-Dx;
Const1=2Dy;
Const2=2(Dy-Dx);
x=x1;
y=y1;
putpixel(x, y, c);





x

Yes


p<0


Yes


p=p+Const1;













No





No

























Dương Anh Đức, Lê Đình Duy










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







End


p=p+Const2;
y=y+1




















Các thuật toán vẽ đường 8/22

ĐỒ HỌA MÁY TÍNH

? Ví dụ : Cho A(12, 20) và B(22, 27),

? Ta có

? Dx = 22-12 = 10, Dy=27-20=7

? Const1 = 2Dy = 14, Const2 = 2(Dy - Dx) = -6

? p0 = 2Dy - Dx = 14-10 = 4

























? Nhận xét
i
0
1
2
3
4
5
6
7
8
9
10
xi
12
13
14
15
16
17
18
19
20
21
22
yi
20
21
21
22
23
24
24
25
26
26
27
pi
4
-2
12
6
0
-6
8
2
-4
10
4

? Thuật toán Bresenham chỉ làm việc trên số nguyên và
các thao tác trên số nguyên chỉ là phép cộng và phép
dịch bit (phép nhân 2) điều này là một cải tiến làm tăng
tốc độ đáng kể so với thuật toán DDA. Ý tưởng chính của
thuật toán nằm ở chỗ xét dấu pi để quyết định điểm kế
tiếp, và sử dụng công thức truy hồi
pi?1 ??pi để tính pi
bằng các phép toán đơn giản trên số nguyên.

? Thuật toán này cho kết quả tương tự như thuật toán
DDA.





Dương Anh Đức, Lê Đình Duy





Các thuật toán vẽ đường 9/22

ĐỒ HỌA MÁY TÍNH

? Cài đặt minh họa thuật toán Bresenham

void LineBres (int x1, int y1, int x2, int y2)
{
int Dx, Dy, p, Const1, Const2;
int x, y;



Dx
Dy



= x2 - x1;
= y2 - y1;
p = 2*Dy - Dx; // Dy <<1 - Dx
Const1 = 2*Dy; // Dy <<1
Const2 = 2*(Dy-Dx); // (Dy-Dx) <<1
x = x1;
y = y1;
putpixel(x, y, Color);
for(i=x1; i{
if (p<0)
p += Const1;
else
{
p += Const2;
y++;
}
x++;
putpixel(x, y, Color);
}
} // LineBres

Dương Anh Đức, Lê Đình Duy















































Các thuật toán vẽ đường 10/22

ĐỒ HỌA MÁY TÍNH

Thuật toán MidPoint

? Thuật toán MidPoint đưa ra cách chọn







yi?1 là yi
hay yi??1
bằng cách so sánh điểm thực Q ?xi
??1, y?
với điểm MidPoint là trung điểm của S và P. Ta có :

? Nếu điểm Q nằm dưới điểm MidPoint, ta chọn S.

? Nếu điểm Q nằm trên điểm MidPoint ta chọn P.










Q(xi+1, y)
yi+1 P


MidPoint
yi





xi
S



xi+1




? Ta có dạng tổng quát của phương trình đường thẳng :
Ax ??By ??C ??0

với

A ? y
2

?

y1, B

???
?
x


2

?
?
x1, C ??x y
2 1

?

y
x12
? Đặt F ????y

? Ax ??By ??C , ta có nhận xét :

??
F ????
y ??
0, nếu ???
???
0, nếu

y nằm phía trên đường thẳng
y thuộc về đường thẳng
??
0, nếu ???
y nằm phía dưới đường thẳng.
?


Dương Anh Đức, Lê Đình Duy




Các thuật toán vẽ đường 11/22

ĐỒ HỌA MÁY TÍNH

? Lúc này việc chọn các điểm S, P ở trên được đưa về
?
?
?
1 ?
việc xét dấu của
p
i
?
F
2 MidPoint
?
?
2F x
i
?
1, y
i
?
?
.
?
2 ?

? Nếu

pi??0 , điểm MidPoint nằm phía trên đoạn thẳng.
Lúc này điểm thực Q nằm dưới điểm MidPoint nên ta
chọn S, tức là yi?1?yi.

? Ngược lại, nếu

pi??0 , điểm MidPoint nằm phía dưới
đoạn thẳng. Lúc này điểm thực Q nằm trên điểm
MidPoint nên ta chọn P, tức là yi?1?yi??1 .

? Mặt khác :


p


p

?

1 ?

?

1 ?
i?1
?
i
??2F ??x
?
i?1
??1, y
i?1
?
2
????2F ??x
? ?
i
??1, y
i
?
2
?
?


p


p

?


?


?

?

1 ?

?

?


?

? ??? ????1 ?

?
?
i?1
?i??2??A x
i?1
1
? ?
B??y
i?1
?
2
???
C???
2??A x
i
1
B
?
i
2
???
C
?
p
?
p
2 A
2
?
?
?
?
?
2
?
2
?
?
?
yi?
?
?
i?1
?
i
?
?
B yi?1 ??yi
?
Dy ?
Dx yi?1 ?

? Như vậy :

?
pi?1?p


i
??2Dy , nếu
pi??0 do ta chọn
yi?1?
yi.

?

pi?1?p


i

??2Dy ??2Dx ,

nếu

pi??0 do

ta

chọn
yi?1?yi??1 .
? Ta tính giá trị p0ứng với điểm ban đầu ?x0, y0??, với
nhận xét rằng ?x0, y0?? là điểm thuộc về đoạn thẳng,
tức là có : Ax

?

0
??By

0
C
? ?
1 ?
0

?



? ? ?y0?1 ?



?
p
2F??x
1, y
2
?
1?
0
?
0
?
0
?
???
??A x0
B?
????C?
?
2 ?
?
?
2 ?
?

??p
0
??2??Ax
0
??By0??C ?

?

2 A B
? ?

2A B
? ?

2Dy ??Dx


Dương Anh Đức, Lê Đình Duy


Các thuật toán vẽ đường 12/22



Câu hỏi kiểm tra

ĐỒ HỌA MÁY TÍNH
? Xét thuật toán Bresenham, với cách đặt d1 và d2 như
trên, có khi nào d1 hay d2 âm hay không ? Cho ví dụ
minh họa.























? Tại sao phải so sánh giá trị pivới 0 trong các thuật
toán MidPoint và Bresenham, bản chất của việc so
sánh này là gì ?