5
- Trong hệ tọa độ chuẩn, các tọa độ x, y sẽ đƣợc gán các giá trị trong đoạn từ [0,1]. Nhƣ vậy, vùng
không gian của hệ tọa độ chuẩn chính là hình vuông đơn vị có góc trái dƣới (0, 0) và góc phải trên là (1, 1).
- Quá trình mô tả các đối tƣợng thực nhƣ sau:
Câu 4. Trình bày nguyên lý chung vẽ đoạn thẳng ?
Nguyên lý chung
Đầu vào: cho 2 điểm đầu mút (x1,y1) (x2,y2), màu vẽ C.
Phương trình đƣờng thẳng đi qua 2 điểm đầu mút:
(x-x1)/(y-y1) = (x2-x1)/(y2-y1) => Y=(y2-y1)*(x-x1)/(x2-x1)+y1
Đặt m= (y2-y1)/(x2-x1)
b= y1-mx1
ta có phƣơng trình y=mx+b
m đƣợc gọi là độ dốc hay hệ số góc của đƣờng thẳng, b đƣợc gọi là đoạn chắn trên trục y.
- Từ phƣơng trình này chúng ta có thể xây dựng quá trình vẽ các đƣờng thẳng khi cho x biến thiên các
khoảng x và kết quả ta có thể thu đƣợc giá trị của y thay đổi với các khoảng y tƣơng ứng y=mx.
- Hoặc có thể làm ngƣợc lại cho y biến thiên từng khoảng y và kết quả ta có thể thu đƣợc giá trị của x
thay đổi các khoảng x tƣơng ứng x=y/m
- Đơn vị nhỏ nhất của màn hình là một điểm ảnh nên thông thƣờng chọn x= 1 (x= -1) hoặc y= 1
(y= -1).
- Nguyên lý chung là cho một thành phần tọa độ x hay nguyên biến đổi theo từng đơn vị và tính tọa độ
nguyên còn lại sao cho gần với tọa độ thực nhất.
Câu 5. Trình bày thuật toán DDA vẽ đoạn thẳng ?
- Để đơn giản hóa giải thuật, chúng ta chỉ xét các đƣờng thẳng có hệ số góc m trong khoảng [0,1] và
Dx>0. Mỗi bƣớc nhẩy của x trong mỗi lần tính tƣơng đƣơng một điểm ảnh.
6
Như vậy tại bước i+1:
=
+ 1
Và tọa độ y tƣơng ứng
1=
+m
Vì m là số thực nên để thu đƣợc
nguyên buộc ta phải làm tròn y trƣớc khi đƣa tọa độ truy xuất lên
màn hình.
- Với đƣờng thẳng có hệ số góc m>1, ta có thể cho x biến đổi theo y nghĩa là ở đây y đóng vai trò
tăng và x đƣợc tính theo tƣơng ứng:
=
+1,
=
+1/m. Và chúng ta có thể tính tƣơng tự
cho các trƣờng hợp còn lại.
- Nhận xét:
Độ chính xác của thuật toán cao, đoạn thẳng vẽ đƣợc thể hiện rất gần với đoạn thẳng thực tế. Tuy nhiên
tốc độ tính toán chậm do phải thƣờng xuyên làm việc với các phép toán cộng số thực và làm tròn.
Câu 6. Trình bày thuật toán Breshenham vẽ đoạn thẳng?
- Đây là một phƣơng pháp có hiệu quả chỉ sử dụng cộng trừ các số nguyên và phép nhân. Thực tế cho
thấy rằng, máy tính có thể biểu diễn phép cộng trừ các số nguyên một cách nhanh chóng, giải
quyết đƣợc về mặt thời gian khi biểu diễn các phép nhân, chia cho lũy thừa của 2 vì chỉ phải sử dụng
các phép dịch bit.
- Xét đoạn thẳng có hệ số góc m[0,1] Dx>0
Lúc này bằng cách cho x tăng một đơn vị tại mỗi bƣớc, ta sẽ tìm cách tính y để vẽ các pixel tƣơng ứng.
Giả sử ở bƣớc thứ k ta đã xác định các tọa độ nguyên (xk, yk) nhƣ vậy chúng ta cần xác định tọa độ
(
,
) cho bƣớc kế tiếp
Theo công thức ta có:
=
+1
7
Giá trị của
có thể đƣợc chọn bởi một trong 2 giá trị yk hoặc yk+1. Điểm đƣợc chọn là
điểm gần với y thực nhất.
Xét khoảng cách d
1
, d
2
từ y thực đến y
k
và đến y
k+1
Gọi (x
k+1
,y) là điểm thuộc đoạn thẳng, ta có y=m(x
k
+1)+b
d
1
= y - y
k
= m(x
k
+1) + b - y
k
. d
2
= y
k
+1 - y = y
k
+ 1 - m(x
k
+ 1) -
b - Nếu d
1
< d
2
=> y
k+1
= y
k
- Ngƣợc lại d
1
>= d
2
=> y
k+1
= y
k
+1 d
1
- d
2
= 2m(x
k
+ 1) - 2y
k
+ 2b - 1
m=(y
2
-y
1
)/(x
2
-x
1
)
Nếu xác định đƣợc dấu của d
1
-d
2
thì sẽ biết đƣợc điểm ảnh nào gần với đoạn thẳng hơn. Xác
định tham số quyết định P
k
cùng dấu với d
1
-d
2
.
Đặt P
k
= (x
2
-x
1
) (d
1
- d
2
)
Do Dx>0 nên P
k
cùng dấu với d
1
-d
2
P
k
= (x
2
-x
1
)[(2(y
2
-y
1
)(x
k
+1)+(x
2
-x
1
)(- 2y
k
+2b-1)]/(x
2
-x
1
) =2(y
2
-y
1
)x
k
-2(x
2
-x
1
)y
k
+c
Trong đó c là hằng số đối với đoạn thẳng và c=2(y
2
-y
1
)+(x
2
-x
1
)(2b-1)
Pk+1 =2(y2-y1)xk+1-2(x2-x1)yk+1+c
P
k+1
tại bƣớc thứ k+1 đƣợc tính tăng dần bằng cách sử dụng giá trị P
k
tại bƣớc thứ k nhƣ sau :
+) P
k
<0 d
1
<d
2
chọn y
k+1
=y
k
P
k+1
=2(y
2
-y
1
)(x
k
+1)-2(x
2
-x
1
)y
k
+c = P
k
+2(y
2
-y
1
)
+) P
k
>=0 d
1
>=d
2
chọn y
k+1
=y
k
+1
8
P
k+1
=2(y
2
-y
1
)(x
k
+1)-2(x
2
-x
1
)(y
k
+1)+c = P
k
+2(y
2
-y
1
)-2(x
2
-x
1
)
Tính giá trị P
1
khởi tạo :
P
1
=2(y
2
-y
1
)x
1
-2(x
2
-x
1
)y
1
+2(y
2
-y
1
)+(2b-1)(x
2
-x
1
)
Do (x
1
, y
1
) là điểm nguyên thuộc đoạn thẳng nên ta có y
1
=mx
1
+b = (Dy/Dx)*x
1
+ b.
Thế vào phƣơng trình trên ta suy ra :
P
1
=2(y
2
-y
1
)- (x
2
-x
1
)
Câu 7. Thuật toán trung điểm vẽ đoạn thẳng (MidPoint)
Xét đoạn thẳng có hệ số góc thuộc [0,1]. Dx>0
Tại mỗi bƣớc x tăng lên một đơn vị, y giữ nguyên hoặc tăng lên một đơn vị, chọn giá trị y gần với
đƣờng thẳng nhất.
Thuật toán MidPoint đƣa ra cách chọn y
i+1
là y
i
hay y
i
+1 bằng cách so sánh điểm thực Q(x
i
+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.
+ Ngƣợc lại 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: F(x,y)=Ax+By+C=0
A=y
2
-y
1
, B= -(x
2
-x
1
), C=x
2
y
1
-x
1
y
2
F(x,y)=0 với mọi điểm (x,y) thuộc đƣờng thẳng
F(x,y)>0 với các điểm (x,y) nằm phía dƣới đƣờng thẳng
F(x,y)<0 với các điểm (x,y) nằm phía trên đƣờng thẳng
9
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 p
i
=2F(M)=2F(x
i
+1, y
i
+0.5)=
2A(x
i
+1)+2B(y
i
+0.5)+C
M là trung điểm của PS
+ Nếu p
i
< 0 điểm M 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 M nên ta chọn S
tức là y
i+1
=y
i
P
i+1
=2F(x
i+1
+1, y
i+1
+0.5)=2F(x
i
+2, y
i
+0.5)= 2A(x
i
+2)+2B(y
i
+0.5)+C = p
i
+2A = p
i
+2D
y
+ Nếu p
i
>=0, điểm M nằm phía dƣới đoạn thẳng. Lúc này điểm thực Q nằm phía trên điểm M nên ta
chọn P tức là y
i+1
=y
i
+1
P
i+1
=2F(x
i+1
+1, y
i+1
+0.5)=2F(x
i
+2, y
i
+1.5)= 2A(x
i
+2)+2B(y
i
+1.5)+C = p
i
+2A+2B=p
i
+ 2D
y
-2D
x
Ta tính giá trị p
1
ứng với điểm ban đầu (x
1
, y
1
), với nhận xét rằng (x
1
, y
1
) là điểm thuộc về đoạn thẳng,
tức là ta có Ax
1
+By
1
+C=0.
P
1
=2F(x
1
+1, y
1
+0.5)= 2A(x
1
+1)+2B(y
1
+0.5)+C = 2(Ax
1
+By
1
+C)+ 2A+B =2A+B= 2D
y
-D
x
Câu 8. Trình bày nguyên lý chung vẽ đường tròn?
Trong hệ tọa độ Descartes, phƣơng trình đƣờng tròn bán kính R có dạng:
Với tâm O(0,0) :
+
=
Với tâm C(x
c
, y
c
): (x-x
c
)
2
+ (y-y
c
)
2
=R
2
Trong hệ tọa độ cực :
x = x
c
+ R.cosθ, y=y
c
+ R.sinθ với θ [0, 2π].
Do tính đối xứng của đƣờng tròn C nên ta chỉ cần vẽ 1/8 cung tròn, sau đó lấy đối xứng qua 2 trục tọa
độ và 2 đƣờng phân giác thì ta vẽ đƣợc cả đƣờng tròn.
Với đƣờng tròn tâm (x
c
, y
c
) ta có thể vẽ đƣờng tròn tâm (0,0) sau đó tịnh tiến theo vecto (x
c,
y
c
).
Cho x = 0, 1, 2, , int(R x sqrt(2)/2) với R>1.
- Tại mỗi giá trị x, tính int(y = sqrt(R
2
-x
2
)).
10
- Vẽ điểm (x,y) cùng 7 điểm đối xứng của nó.
Một cách tiếp cận khác là vẽ các điểm (R cos (θ), R sin (θ)), với θ chạy từ 0
0
đến 90
0
. Cách này sẽ
khắc phục hạn chế đƣờng không liền nét của thuật toán trên, tuy nhiên điểm hạn chế chính của thuật
toán này đó là chọn bƣớc nhảy cho θ nhƣ thế nào cho phù hợp khi bán kính thay đổi.
Câu 9. Thuật toán trung điểm (MidPoint) vẽ đƣờng tròn
Xét đƣờng tròn tâm tại gốc tọa độ, bán kính R. Xét cung 1/8 đƣờng tròn C(
1/8
), sau đó lấy đối
xứng.
Nhƣ vậy nếu có (x, y) thuộc (C
1/8
) thì các điểm : (y, x), (y,-x), (x,-y), (-x,-y), (y,-x), (-y,x), (-x,y) sẽ
thuộc (C).
Chọn điểm bắt đầu để vẽ là điểm (0,R). Dựa vào hình vẽ, nếu (x
i
, y
i
) là điểm nguyên đã tìm đƣợc ở
bƣớc thứ i, thì (x
i+1
, y
i+1
) ở bƣớc thứ (i+1) là sự lựa chọn giữa S và P. Nhƣ vậy:
x
i+1
=xi+1 y
i+1
ϵ {y
i
, y
i
-1}
Tƣơng tự nhƣ thuật toán MidPoint vẽ đoạn thẳng, việc quyết định chọn một trong hai điểm S và P
sẽ đƣợc thực hiện thông qua việc xét dấu của một hàm nào đó tại điểm MidPoint là điểm nằm giữa
chúng.
Đặt F(x,y)=x
2
+y
2
-R
2
, ta có
F(x,y) <0 nếu (x,y) nằm trong đƣờng tròn
F(x,y) =0 nếu (x,y) thuộc đƣờng tròn
F(x,y) > 0 nếu (x,y) nằm ngoài đƣờng tròn
Gọi M là trung điểm PS
Xét p
i
=F(M)=F(x
i
+1, y
i
-0.5)= (x
i
+1)
2
+ (y
i
-0.5)
2
-R
2
11
p
i+1
=F(x
i+1
+1, y
i+1
-0.5)= (x
i+1
+1)
2
+ (y
i+1
-0.5)
2
- R
2
Ta có :
+ Nếu p
i
<0, điểm M 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à y
i+1
=y
i
p
i+1
=F(x
i
+2, y
i
-0.5)= (x
i
+2)
2
+ (y
i
-0.5)
2
-R
2
= p
i
+ 2x
i
+3
+ Nếu p
i
>=0, điểm M 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à y
i+1
=y
i
-1
p
i+1
=F(x
i
+2, y
i
- 1.5)= (x
i
+2)
2
+ (y
i
-1.5)
2
-R
2
= p
i
+ 2x
i
-2y
i
+5
Tính giá trị p
1
ứng với điểm ban đầu (x
1
, y
1
) = (0, R)
P
1
=F(1, R-0.5)= 5/4 –R
Câu 10. Trình bày nguyên lý thuật toán trung điểm vẽ đường elip?
Nguyên lý chung
Cho elip tâm (h, k), độ dài trục chính là a, độ dài trục phụ là b
Phƣơng trình đƣờng elip đƣợc xác định nhƣ sau : (x-h)
2
/a
2
+(y-k)
2
/b
2
=1.
Phƣơng trình elip với tâm tại gốc tọa độ x
2
/b
2
+y
2
/b
2
=1
Elip đƣợc chia thành 4 phần đối xứng qua 2 trục tọa độ, do vậy ta chỉ cần vẽ cung ¼ elip sau đó thực
hiện lấy đối xứng để thu đƣợc các phần còn lại.
Để vẽ elip tâm (h,k) ta có thể thực hiện vẽ elip tâm tại gốc tọa độ sau đó tịnh tiến theo véc tơ (h,k).
Tại mỗi bƣớc ta cho x tăng từ 0 đến a sau đó tính giá trị y tƣơng ứng qua biểu thức trên, sau đó lấy giá
trị nguyên gần với giá trị y thực nhất.
Thuật toán trung điểm (MidPoint) vẽ elip
Xét elip tâm tại gốc tọa độ. Phƣơng trình đƣờng elip:
F(x,y)=b
2
x
2
+a
2
y
2
−a
2
b
2
=0
Xét vẽ cung ¼ elip, sau đó lấy đối xứng để thu đƣợc các phần còn lại
0<=x<=a
0<=y<=b
12
Chia cung ¼ elip này thành 2 vùng với điểm chia P là tiếp điểm của tiếp tuyến có hệ số góc là -1.
Véc tơ gradient vuông góc với tiếp tuyến tại tiếp điểm đƣợc xác định nhƣ sau:
GradF(x,y) = (∂F/∂x)i+(∂F/∂y)j=2b
2
x.i+2a
2
y.j
Ta có tiếp tuyến với cung tròn (độ dốc) = -1
Vector gradient có độ dốc là 1, do đó tại P các thành phần i và j của vecto gradient có cùng độ lớn.
Trong vùng 1 thành phần j lớn hơn thành phần i của gradient. a
2
(y
p
-0.5)>b
2
(x
p
+1).
Trong vùng 2 thì ngƣợc lại.
+ Xét trên phần 1:
Bắt đầu từ (0,b),
Tại mỗi bƣớc x tăng lên một đơn vị, y biến đổi theo x bƣớc thứ i (x
i
,y
i
), Ở bƣớc i+1 chọn tiếp
A(x
i
+1, y
i
) hoặc B(x
i
+1,y
i
-1). Chọn điểm gần với đƣờng elip nhất dựa trên việc xét dấu của hàm F tại
trung điểm M của AB.
Tham số quyết định:
p
i
=F(M)= F(x
i
+1,y
i
-1/2) = b
2
(x
i
+1)
2
+ a
2
(y
i
-1/2)
2
-a
2
b
2
pi+1 = F(xi+1+1,yi+1-1/2) = b
2
(x
i+1
+1)
2
+ a
2
(y
i+1
-1/2)
2
- a
2
b
2
- Nếu p
i
<0 chọn A: xi+1=xi+1 yi+1=yi
Pi+1 = b
2
(x
i+1
+1)
2
+ a
2
(y
i+1
-1/2)
2
- a
2
b
2
= b
2
(x
i
+2)
2
+ a
2
(y
i
-1/2)
2
-a
2
b
2
= p
i
+ b
2
(2x
i
+3)
- Nếu p
i
>=0 chọn B: xi+1=xi+1 yi+1=yi -1
p
i+1
= b
2
(x
i
+2)
2
+ a
2
(y
i
-1.5)
2
-a
2
b
2
= p
i
+ b
2
(2x
i
+3) + a
2
(-2y
i
+2)
- Tính P1 khởi tạo tại (0,b): p
1
= F(1,b-1/2) = b
2
+ a
2
(b-1/2)
2
-a
2
b
2
= b
2
- a
2
b +a
2
/4
+ Xét trên phần 2:
Ta lấy toạ độ của Pixel sau cùng trong phần 1 của đƣờng cong để tính giá trị ban đầu cho phần 2.
Tại mỗi bƣớc y giảm từng đơn vị, x biến đổi theo y.
Tại bƣớc j ta có điểm (x
j
,y
j
).
Pixel ở bƣớc kế tiếp j+1 có thể là: C(x
j
,y
j
-1) hoặc D(x
j
+1, y
j
-1
13
Tham số quyết định:
q
j
=F(M)= F(x
j
+1/2,y
j
-1) = b
2
(x
j
+1/2)
2
+ a
2
(y
j
-1)
2
-a
2
b
2
qj+1 = F(x
j+1
+1+1/2, y
j+1
-1) = b
2
(x
j+1
+1/2)
2
+ a
2
(y
j+1
-1)
2
-a
2
b
2
- Nếu q
j
<0 chọn D: y
j+1
=yj-1, x
j+1
= x
j
+1
qj+1 b
2
(x
j+1
+1/2)
2
+ a
2
(y
j+1
-1)
2
-a
2
b
2
= b
2
(x
j
+1.5)
2
+ a
2
(y
j
-2)
2
-a
2
b
2
= q
j
+ b
2
(2x
j
+2) +a
2
(-2y
j
+3)
- Nếu q
j
>=0 chọn C: y
j+1
=yj-1, x
j+1
= x
j
qj+1 = b
2
(x
j+1
+1/2)
2
+ a
2
(y
j+1
-1)
2
-a
2
b
2
= b
2
(x
j
+1/2)
2
+ a
2
(y
j
-2)
2
-a
2
b
2
= q
j
+ a
2
(- 2y
j
+3)
- Tính q
1
khởi tạo q
1
= f(x
p
+1/2,y
p
-1) = b
2
(x
p
+1/2)
2
+ a
2
(y
p
-1)
2
-a
2
b
2
Câu 11. Định nghĩa đa giác, cho biết cách vẽ một đa giác?
Khái niệm đa giác
Đa giác là thành phần cơ bản nhất của bề mặt. Việc biểu diễn đa giác có thể thông qua tập các đƣờng
thẳng hay tập các điểm thuộc đa giác. Một đa giác là một đƣờng gấp khúc có điểm đầu và điểm cuối trùng
nhau.
Xây dựng cấu trúc dữ liệu để vẽ đa giác Type
d_dinh = record x,y: longint; end;
dinh = array[0 10] of d_dinh; var d: dinh;
Với cách xây dựng cấu trúc dữ liệu nhƣ thế này thì chúng ta chỉ cần nhập vào tọa độ các đỉnh và
sau đó gọi thủ tục vẽ đƣờng thẳng lần lƣợt qua 2 đỉnh nhƣ (0, 1), (1,2), , (n-1, n), trong đó đỉnh n
trùng với đỉnh 0 thì ta sẽ vẽ đƣợc toàn bộ đa giác.
Câu 12. Trình bày thuật toán tô màu dựa theo dòng quét?
Giả sử vùng tô đƣợc cho bởi một đa giác N đỉnh : P
i
(x
i
, y
i
),i=0,…,N-1. Đa giác này có thể là đa giác
lồi, đa giác lõm, và cả đa giác tự cắt, …
Ta có thể tóm bắt các bƣớc chính của thuật toán :
- Tìm y
top
, y
bottom
lần lƣợt là giá trị lớn nhất, nhỏ nhất của tập các tung độ của các đỉnh của đa giác đã
cho:
14
y
top
= max{y
i
,(x
i
,y
i
) ϵ P}, ybottom= min{y
i
, (x
i
,
y
i
)ϵP}
- Ứng với mỗi dòng quét y=k, với k thay đổi từ y
bottom
đến y
top
lặp :
+ Tìm tất cả các hoành độ giao điểm của dòng quét y=k với các cạnh của đa giác.
+ Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần : x
0
, x
1
, …
+ Tô màu các đoạn thẳng trên đƣờng thẳng y=k lần lƣợt đƣợc giới hạn bởi các cặp
(x
0
,x
1
), (x
2
, x
3
), ….
Nếu chỉ dừng ở mức này và chuyển sang cài đặt, chúng ta sẽ gặp một số vấn đề sau :
+ Nhận xét rằng, ứng với mỗi dòng quét, không phải lúc nào tất cả các cạnh của đa giác cũng tham
gia cắt dòng quét.
+ Việc tìm giao điểm của cạnh đa giác với mỗi dòng quét sẽ gặp các phép toán phức tạp nhƣ nhân,
chia, … trên số thực nếu ta dùng cách giải hệ phƣơng trình tìm giao điểm.
+ Nếu số giao điểm tìm đƣợc giữa các cạnh đa giác và dòng quét là lẻ thì việc nhóm từng cặp giao
điểm kế tiếp nhau để hình thành các đoạn tô có thể sẽ không chính xác Nếu tính số giao điểm tại
đỉnh dòng quét đi ngang qua là hai thì có thể sẽ cho kết quả tô không chính xác. Ngoài ra, việc tìm
giao điểm của dòng quét với các cạnh nằm ngang là một trƣờng hợp đặc biệt cần phải có cách xử lí
thích hợp.
Câu 13. Trình bày thuật toán tô màu theo đường biên?
Đường biên của vùng tô đƣợc xác định bởi tập các đỉnh của một đa giác, đƣờng biên trong thuật
toán đƣợc mô tả bằng một giá trị duy nhất đó là màu của tất cả các điểm thuộc về đƣờng biên.
Bắt đầu từ điểm nằm bên trong vùng tô, ta sẽ kiểm tra các điểm lân cận của nó đã đƣợc tô màu hay
có phải là điểm biên hay không, nếu không phải là điểm đã tô và không phải là điểm biên ta sẽ tô màu
nó. Quá trình này đƣợc lặp lại cho tới khi nào không còn tô đƣợc điểm nào nữa thì dừng.
Có hai quan điểm về cách tô này, đó là dùng bốn điểm lân cận hay tám điểm lân cận đối với điểm đang
xét đƣợc tô bằng màu trắng
Hình 2.25: 4 điểm lân cận (a) và 8 điểm lân cận (b)
Không có nhận xét nào:
Đăng nhận xét