Đồ họa máy tính - Các thuật toán vẽ đường

,1+
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.
· Ta có dạng tổng quát của phương trình đường thẳng :
0=++ CByAx với ( ) 21121212 ,, yxyxCxxByyA -=--=-=
· Đặt ( ) CByAxyxF ++=, , ta có nhận xét :
( )
( )
( )
( )ïỵ
ï
í
ì
>
=
<
thẳng. đường dưới phía nằm yx, nếu,0
thẳng đường vềthuộc yx, nếu,0
thẳng đường trên phía nằm yx, nếu,0
, yxF
Q(xi+1, y)
P
S
xi xi+1
yi
yi+1
MidPoint
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 12/22
· Lúc này việc chọn các điểm S, P ở trên được đưa về
việc xét dấu của ( ) ÷ø
ư
ç
è
ỉ ++==
2
1
,12MidPoint2 iii yxFFp .
¨ Nếu 0<ip , đ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à ii yy =+1 .
¨ Ngược lại, nếu 0³ip , đ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à 11 +=+ ii yy .
· Mặt khác :
÷
ø
ư
ç
è
ỉ ++-÷
ø
ư
ç
è
ỉ ++=- +++ 2
1,12
2
1,12 111 iiiiii yxFyxFpp
( ) ( ) ú
û
ù
ê
ë
é
+÷
ø
ư
ç
è
ỉ +++-ú
û
ù
ê
ë
é
+÷
ø
ư
ç
è
ỉ +++=-Û +++ CyBxACyBxApp iiiiii 2
112
2
112 111
( ) ( )iiiiii yyDxDyyyBApp --=-+=-Û +++ 111 2222
· Như vậy :
¨ Dypp ii 21 +=+ , nếu 0<ip do ta chọn ii yy =+1 .
¨ DxDypp ii 221 -+=+ , nếu 0³ip do ta chọn
11 +=+ ii yy .
· Ta tính giá trị 0p ứng với điểm ban đầu ( )00 , yx , với
nhận xét rằng ( )00 , yx là điểm thuộc về đoạn thẳng,
tức là có : 000 =++ CByAx
( ) ú
û
ù
ê
ë
é
+÷
ø
ư
ç
è
ỉ +++=÷
ø
ư
ç
è
ỉ ++= CyBxAyxFp
2
112
2
1,12 00000
( ) DxDyBABACByAxp -=+=++++=Þ 2222 000
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 13/22
Cââu hỏûi kiểåm tra
· 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ị pi vớ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ì ?
· Tại sao phải nhân F(MidPoint) với 2 khi gán cho pi
theo công thức pi=2*F(MidPoint) ?
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 14/22
· Cài đặt thuật toán cho trường hợp 0 £ m £ 1, Dx<0.
Ta sử dụng thuật toán với trường hợp 0 £ m £ 1,
Dx>0 đã cài đặt cộng thêm một số thay đổi sau :
¨ Thay biểu thức x=x+1 bằng x=x-1 và y=y+1 bằng y=y-1 vì
trong trường hợp này x và y đều giảm dần.
¨ Nhận xét rằng khi p<0 ta gán p=p+Const1, như vậy để
hướng đến sự cân bằng Const1 phải là một giá trị dương.
Tương tự như vậy, khi p³0 ta gán p=p+Const2, Const2
phải là giá trị âm.
¨ Từ nhận xét trên, trong các công thức ta sẽ thay Dx
bằng abs(Dx), Dy bằng abs(Dy).
· Mở rộng thuật toán trên để vẽ đoạn thẳng trong
trường hợp m bất kì.
¨ Trường hợp đặc biệt m=¥ : Đoạn thẳng song song trục
tung nên rất đơn giản khi vẽ.
¨ Trường hợp –1 £ m £ 1 : Sử dụng các công thức của thuật
toán vẽ trong trường hợp 0£ m £ 1, Dx>0 và thay đổi một
số điểm sau :
v Nếu Dx<0 thì bước nhảy của x sẽ thay bằng –1.
Tương tự nếu Dy<0, bước nhảy của y cũng sẽ là –1.
v Thay Dx bằng abs(Dx), Dy=abs(Dy) trong tất cả các
công thức có chứa Dx, Dy.
¨ Trường hợp m £ -1 hay m ³ 1 :
v Thay đổi vai trò của x và y, nghĩa là thay x bằng y, y
bằng x, Dx bằng Dy, Dy bằng Dx trong tất cả các
công thức.
v Thực hiện nguyên tắc về bước nhảy, thay đổi công
thức Dx, Dy như trong trường hợp –1 £ m £ 1
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 15/22
Vẽõ đườøng tròøn bằèng thuậät toáùn MidPoint
· Do tính đối xứng của đường tròn (C) nên ta chỉ cần
vẽ cung (C1/8) là cung 1/8 đường tròn, sau đó lấy đối
xứng. Cung (C1/8) được mô tả như sau (cung của phần
tô xám trong hình vẽ) :
ï
ï
ỵ
ïï
í
ì
££
££
RyR
Rx
2
2
2
20
· Như vậy nếu có (x, y) Ỵ (C1/8) thì các điểm : (y, x), (y,-
x), (x,-y), (-x,-y), (-y,-x), (-y,x), (-x,y) sẽ thuộc (C).
2
R
(x,y)(-x,y)
(y,x)(-y,x)
(x,-y)(-x,-y)
(-y,-x) (y,-x)
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 16/22
· Chọn điểm bắt đầu để vẽ là điểm (0,R).
· Dựa vào hình vẽ, nếu ( )ii yx , là điểm nguyên đã tìm
được ở bước thứ i, thì điểm ( )11 , ++ ii yx ở bước thứ
(i+1) là sự lựa chọn giữa S và P.
· Như vậy : { }ỵ
í
ì
-Ỵ
+=
+
+
1,
1
1
1
iii
ii
yyy
xx
· Đặt ( ) 222, RyxyxF -+= , ta có :
( )
( )
( )
( )ïỵ
ï
í
ì
>
=
<
tròn. đường ngoài nằm yx, nếu,0
tròn đường trên nằm yx, nếu,0
tròn đường trong nằm yx, nếu,0
, yxF
S
P
MidPoint
yi
yi-1
xi xi+1
Q(xi+1, y)
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 17/22
· Xét ( ) ÷ø
ư
ç
è
ỉ -+==
2
1,1MidPoint iii yxFFp . Ta có :
¨ Nếu 0<ip , điểm MidPoint nằm trong đường tròn. Lúc
này điểm thực Q gần S hơn nên ta chọn S, tức
là ii yy =+1 .
¨ Ngược lại, nếu 0³ip , điểm MidPoint nằm ngoài đường
tròn. Lúc này điểm thực Q gần P hơn nên ta chọn P, tức
là 11 -=+ ii yy .
· Mặt khác :
÷
ø
ư
ç
è
ỉ -+-÷
ø
ư
ç
è
ỉ -+=- +++ 2
1,1
2
1,1 111 iiiiii yxFyxFpp
( ) ( )
ú
ú
û
ù
ê
ê
ë
é
-÷
ø
ư
ç
è
ỉ -++-
ú
ú
û
ù
ê
ê
ë
é
-÷
ø
ư
ç
è
ỉ -++=-Û +++
2
2
22
2
1
2
11 2
11
2
11 RyxRyxpp iiiiii
( ) ( )iiiiiii yyyyxpp ---++=-Û +++ 122 11 32
· Vậy :
¨ 321 ++=+ iii xpp , nếu 0<ip do ta chọn ii yy =+1 .
¨ 5221 +-+=+ iiii yxpp , nếu 0³ip do ta chọn
11 -=+ ii yy .
· 0p ứng với điểm ban đầu ( ) ( )Ryx ,0, 00 = .
RRFyxFp -=÷
ø
ư
ç
è
ỉ -=÷
ø
ư
ç
è
ỉ -+=
4
5
2
1,1
2
1,1 000
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 18/22
 Lưu đồ thuật toán MidPoint vẽ đường tròn
Begin
p=5/4-R;
x=0;
y=R;
Put8Pixel(x, y, c);
x<y
Yes
No
p<0
Yes
p=p+2*x+3;
No
p=p+2(x-y)+5;
y=y-1
x=x+1;
Put8Pixel(x,y,c);
End
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 19/22
Cài đặt minh họa thuật toán MidPoint vẽ đường tròn
void CircleMidPoint (int R)
{
int x, y;
x = 0;
y = R;
Put8Pixel(x, y);
p = 1 - R; // 5/4-R
while (x < y)
{
if (p < 0)
p += 2*x + 3;
else
{
p += 2*(x -y) + 5;
y--;
}
x++;
Put8Pixel(x, y);
}
} // CircleMidPoint
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 20/22
· Ví dụ : Vẽ đường tròn tâm I(0,0), bán kính R=15.
i xi yI pi Delta1 Delta2
0 0 15 -14 1-15 3 -25
1 1 15 -11 -14+2*(0)+3 5 -23
2 2 15 -6 -11+2*(1)+3 7 -21
3 3 15 1 -6+2*(2)+3 9 -19
4 4 14 -18 1+2*(3-15)+5 11 -15
5 5 14 -7 -18+2*(4)+3 13 -13
6 6 14 6 -7+2*(5)+3 15 -11
7 7 13 -5 6+2(6-14)+5 17 -7
8 8 13 12 -5+2(7)+3 19 -5
9 9 12 7 12+2(8-13)+5 21 -1
10 10 11 6 7+2(9-12)+5 23 3
11 11 10 9 6+2(10-11)+5 25 7
Nhận xét :
· Nếu đặt Delta1 = 2*x+3, Delta2 = 2*(x-y)+5 thì
¨ Do mỗi bước đều tăng x nên sau mỗi lần lặp giá trị
Delta1 luôn tăng 2.
¨ Do y bị giảm 1 khi gặp p³0 và giữ nguyên giá trị trong
trường hợp ngược lại nên nếu lần lặp trước giá trị p³0
thì giá trị Delta2 sẽ được tăng 4 và nếu lần lặp trước giá
trị p<0 thì giá trị Delta2 sẽ được tăng 2 mà thôi.
· Hãy tối ưu hóa cài đặt thuật toán MidPoint vẽ đường
tròn từ nhận xét trên.
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 21/22
Vẽõ đườøng conics vàø mộät sốá đườøng cong kháùc
Phương trình tổng quát của các đường conics có dạng :
022 =+++++ FEyDxCyBxyAx . Giá trị của các hằng
số A, B, C, D, E, F sẽ quyết định dạng của đường conics, cụ
thể là nếu:
ï
ỵ
ï
í
ì
>
=
==<
-
hyperbol. dạng ,0
parabol dạng ,0
ellipse hay ) 0B và C A(nếu tròn đường dạng ,0
42 ACB
Ta sẽ áp dụng ý tưởng của thuật toán MidPoint để vẽ các
đường conics và một số đường cong khác, theo các bước
tuần tự sau:
· Bước 1 : Dựa vào dáng điệu và phương trình đường
cong, để xem thử có thể rút gọn phần đường cong
cần vẽ hay không.
· Bước 2 : Tính đạo hàm để từ đó phân thành các
vùng vẽ :
¨ Nếu 1)('0 ££ xf thì { }ỵ
í
ì
+Ỵ
+=
+
+
(*) 1,
1
1
1
iii
ii
yyy
xx
¨ Nếu 0)('1 ££- xf thì { }ỵ
í
ì
-Ỵ
+=
+
+
(*) 1,
1
1
1
iii
ii
yyy
xx
¨ Nếu 1)(' >xf thì { }ỵ
í
ì
+Ỵ
+=
+
+
(*) 1,
1
1
1
iii
ii
xxx
yy
¨ Nếu 1)(' -<xf thì { }ỵ
í
ì
-Ỵ
+=
+
+
(*) 1,
1
1
1
iii
ii
xxx
yy
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 22/22
· Bước 3 : Xác định công thức của ip cho từng trường
hợp để quyết định (*) dựa trên dấu của ip . ip thường
là hàm được xây dựng từ phương trình đường cong để
cho 0=ip nếu ( )ii yx , thuộc về đường cong. Việc
chọn ip cần phải chú ý sao cho thao tác tính ip sau
này hạn chế phép toán trên số thực.
· Bước 4 : Tìm mối liên quan của 1+ip và ip bằng
cách xét hiệu ii pp -+1 .
· Bước 5 : Tính 0p và hoàn chỉnh thuật toán.
Bàøi tậäp
· Giải thích tại sao chỉ chọn cung 1/8 đường tròn để vẽ
rồi lấy đối xứng mà không mở rộng cho cung 1/16
hay 1/32.
· Giải thích tại sao có thể thay công thức p0=5/4-R
bằng công thức p0=1-R khi cài đặt.
· Hãy trình bày thuật toán MidPoint vẽ cung 1/8
đường tròn sau :
ï
ï
ỵ
ïï
í
ì
££
££
2
2
0
2
2
Ry
RxR
· Aùp dụng các bước trên để vẽ đoạn thẳng trong
trường hợp tổng quát.
· Hãy trình bày khung chính của thuật toán vẽ ellipse,
parabol, hyperbol dựa vào các bước trên.