›
›

Giáo trình Đồ họa máy tính - Chương 2, Phần 2: Các đối tượng đồ họa cơ sở

Download
CHƯƠNG 2  
CÁC ĐỐI TƯỢNG ĐỒ HỌA CƠ SỞ  
Bất kì một ảnh mô tả thế giới thực nào bao giờ cũng được cấu trúc từ tập các đối tượng  
đơn giản hơn. Ví dụ một ảnh thể hiện bài trí của một căn phòng sẽ được cấu trúc từ các  
đối tượng như cây cảnh, tủ kính, bàn ghế, tường, ánh sáng đèn, … Với các ảnh đồ họa  
phát sinh bằng máy tính, hình dạng và màu sắc của mỗi đối tượng có thể được mô tả  
riêng biệt bằng hai cách : hoặc là bằng dãy các pixel tương ứng hoặc là bằng tập các đối  
tượng hình học cơ sở như đoạn thẳng hay vùng tô đa giác, … Sau đó, các ảnh sẽ được  
hiển thị bằng cách nạp các pixel vào vùng đệm khung.  
Hình 2.1 – Ảnh cánh tay robot được cấu tạo từ các đối tượng đồ họa cơ sở  
Với các ảnh được mô tả bằng các đối tượng hình học cơ sở, cần phải có một quá trình  
chuyển các đối tượng này về dạng ma trận các pixel trước. Quá trình này còn được gọi là  
quá trình chuyển đổi bằng dòng quét (scan-converting). Bất kì công cụ lập trình đồ họa  
nào cũng phải cung cấp các hàm để mô tả một ảnh dưới dạng các đối tượng hình học cơ  
sở hay còn gọi là các đối tượng đồ họa cơ sở (output primitives) và các hàm cho phép kết  
hợp tập các đối tượng cơ sở để tạo thành đối tượng có cấu trúc phức tạp hơn.  
Mỗi đối tượng đồ họa cơ sở được mô tả thông qua dữ liệu về tọa độ và các thuộc tính của  
nó, đây chính là thông tin cho biết kiểu cách mà đối tượng được hiển thị. Đối tượng đồ  
họa cơ sở đơn giản nhất là điểm và đoạn thẳng, ngoài ra còn có đường tròn, và các đường  
conics, mặt bậc hai, các mặt và đường splines, các vùng tô đa giác, chuỗi kí tự, … cũng  
được xem là các đối tượng đồ họa cơ sở để giúp xây dựng các ảnh phức tạp. Chương này  
sẽ khảo sát các thuật toán hiển thị các đối tượng đồ họa cơ sở cho các thiết bị hiển thị  
dạng điểm.  
Xét về mặt bản chất, các thuật toán này thực hiện quá trình chuyển đổi các đối tượng đồ  
họa cơ sở được mô tả trong hệ tọa độ thực về dãy các pixel có tọa độ nguyên của thiết bị  
hiển thị. Có hai yêu cầu đặt ra cho các thuật toán này đó là :  
•
Đối tượng được mô tả trong hệ tọa độ thực là đối tượng liên tục, còn đối tượng trong hệ tọa  
độ thiết bị là đối tượng rời rạc, do đó bản chất của quá trình chuyển đổi này chính là sự rời  
rạc hóa và nguyên hóa các đối tượng sao cho có thể xác định các điểm nguyên xấp xỉ đối  
tượng một cách tốt nhất, thực nhất. Nghĩa là đối tượng hiển thị bằng lưới nguyên trên thiết  
bị hiển thị phải có hình dạng tương tự như đối tượng trong lưới tọa độ thực và “có vẻ” liên  
tục, liền nét. Sự liên tục trên lưới nguyên của thiết bị hiển thị có được do mắt người không  
thể phân biệt được hai điểm quá gần nhau.  
•
Do các đối tượng đồ họa cơ sở là thành phần chính cấu trúc các đối tượng phức tạp nên  
các thuật toán hiển thị chúng cần phải được tối ưu hóa về mặt tốc độ, đây chính là điểm  
mấu chốt cho việc ra đời các thuật toán khác nhau.  
Hình 2.2 – Quá trình chuyển đổi một đoạn thẳng về dãy các pixel tương ứng  
1. CÁC ĐỐI TƯỢNG ĐỒ HỌA CƠ SỞ  
1.1. Hệ tọa độ thế giới thực và hệ tọa độ thiết bị  
1.1.1. Hệ tọa độ thế giới thực  
Hệ tọa độ thế giới thực (hay hệ tọa độ thực) là hệ tọa độ được dùng mô tả các đối tượng  
thế giới thực. Một trong các hệ tọa độ thực thường được dùng nhất đó là hệ tọa độ  
Descartes. Với hệ tọa độ này, bất kì một điểm nào trong mặt phẳng cũng được mô tả bằng  
một cặp tọa độ (x, y) trong đó x, y R. Gốc tọa độ là điểm O có tọa độ (0, 0). Các trục  
tọa độ có chiều dương được quy ước như hình 2.3; Ox, Oy lần lượt được gọi là trục  
hoành, trục tung; x là khoảng cách từ điểm đến trục hoành hay còn được gọi là hoành độ,  
y là khoảng cách từ điểm đến trục tung hay còn được gọi là tung độ.  
Các tọa độ thế giới thực cho phép người dùng sử dụng bất kì một thứ nguyên (dimension)  
quy ước như foot, cm, mm, km, inch, ... nào và có thể lớn nhỏ tùy ý.  
1.1.2. Hệ tọa độ thiết bị  
Hệ tọa độ thiết bị là hệ tọa độ được dùng bởi một thiết bị xuất cụ thể nào đó như máy in, màn hình, ...  
Đặc điểm chung của các hệ tọa độ thiết bị đó là :  
•
Các điểm trong hệ tọa độ thiết bị cũng được mô tả bởi một cặp tọa độ (x, y), tuy nhiên  
điểm khác với hệ tọa độ thực là x, y N. Điều này cho thấy các điểm trong hệ tọa độ  
thực được định nghĩa liên tục, còn các điểm trong các hệ tọa độ thiết bị là rời rạc do tính  
chất của tập các số tự nhiên.  
•
Các tọa độ x, y của hệ tọa độ thiết bị không thể lớn tùy ý mà đều bị giới hạn trong một  
khoảng nào đó. Một số thiết bị chỉ cho x chạy trong đoạn[0,639], y chạy trong đoạn  
[0,479]. Khoảng giới hạn các tọa độ x, y là khác nhau đối với từng loại thiết bị khác  
nhau.  
Hình 2.3 – Hệ tọa độ thực (a) và hệ tọa độ thiết bị (b)  
Hệ tọa độ với các hướng của các trục tọa độ như trên còn được gọi là hệ tọa độ theo quy  
ước bàn tay phải.  
Ngoài ra do cách tổ chức bộ nhớ nên thông thường các hệ tọa độ thiết bị thường dựa trên  
hệ tọa độ theo quy ước bàn tay trái.  
Hình 2.4 - Hệ tọa độ theo quy ước bàn tay phải (a) và quy ước bàn tay trái (b)  
1.2. Điểm  
Điểm là thành phần cơ sở được định nghĩa trong một hệ tọa độ. Đối với hệ tọa độ hai  
chiều mỗi điểm được xác định bởi cặp tọa độ (x, y).  
Ngoài thông tin về tọa độ, điểm còn có thuộc tính là màu sắc.  
1.3. Đoạn thẳng, đường gấp khúc  
Một đường thẳng có thể xác định nếu biết hai điểm thuộc nó. Phương trình đường thẳng  
đi qua hai điểm (x1, y1) và (x2, y2) có dạng sau :  
x x1  
y y1  
x2 x1  
y2 y1  
hay ở dạng tương đương :  
x x1 y2 y1  
y y1 x2 x1  
   
Khai triển ta có dạng : y mx b, trong đó :  
Dy  
m   
, Dy y2 y1, Dx x2 x1  
Dx  
b y1 mx1  
Đây còn được gọi là phương trình đoạn chắn của đường thẳng.  
Nếu khai triển dưới dạng :  
y2 y1  
x   
x2 x1  
y x1 y2 x2 y1 0  
và đặt A y2 y1, B    
Ax By C 0, dạng này được gọi là phương trình tổng quát của đường thẳng.  
x2 x1 ,C x2 y1 x1 y2 thì phương trình đường thẳng sẽ có dạng  
Phương trình tham số của đường thẳng có dạng các tọa độ x, y được mô tả qua một thành  
phần thứ ba là t. Dạng này rất thuận tiện khi khảo sát các đoạn thẳng.  
x   
y   
1t  
1t  
x1 tx2  
y1 ty2  
Nếu t   
0,1  
, ta có các điểm (x,y) thuộc về đoạn thẳng giới hạn bởi hai điểm (x1, y1) và (x2, y2), nếu  
t   
,  
, ta sẽ có toàn bộ đường thẳng.  
Một đoạn thẳng là một đường thẳng bị giới hạn bởi hai điểm đầu, cuối.  
Hình 2.5 – Dạng tham số của phương trình đường thẳng  
Đường gấp khúc là tập các đoạn thẳng nối với nhau một cách tuần tự. Các đoạn thẳng này  
không nhất thiết phải tạo thành một hình khép kín và các đoạn có thể cắt lẫn nhau. Điểm  
giao của hai đoạn thẳng được gọi là đỉnh. Các đường gấp khúc được xác định qua danh  
sách các đỉnh, mỗi đỉnh được cho bởi các cặp tọa độ  
xi , yi .  
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.  
Hình 2.6 – Đường gấp khúc (a) và đa giác (b)  
Các thuộc tính của đoạn thẳng bao gồm :  
•
•
•
Màu sắc  
Độ rộng của nét vẽ.  
Kiểu nét vẽ của đoạn thẳng : có thể là một trong các dạng như hình 2.7. Hầu hết các công  
cụ đồ họa đều định nghĩa tập các kiểu nét vẽ đoạn thẳng có thể dùng và cho phép người  
dùng định nghĩa kiểu đoạn thẳng của mình thông qua một mẫu (pattern) gồm các số 0, 1.  
Đối với đường gấp khúc, các đoạn thẳng trong cùng một đường gấp khúc thì có cùng một  
thuộc tính.  
Hình 2.7 – Một số kiểu nét vẽ của đoạn thẳng  
1.4. Vùng tô  
Một vùng tô bao gồm đường biên và vùng bên trong. Đường biên là một đường khép  
kín ví dụ như đa giác.  
Các thuộc tính của vùng tô bao gồm:  
•
•
Thuộc tính của đường biên : chính là các thuộc tính như thuộc tính của đoạn thẳng.  
Thuộc tính của vùng bên trong : bao gồm màu tô và mẫu tô.  
Hình 2.8 – Vùng tô với các dạng đường biên và mẫu tô khác nhau  
1.5. Kí tự, chuỗi kí tự  
Các chuỗi kí tự giúp hiển thị nội dung các thông điệp theo một ngôn ngữ nào đó.  
Các thuộc tính của kí tự bao gồm :  
•
•
Màu sắc của các kí tự.  
Font chữ : bộ kí tự dùng hiển thị; Nó định nghĩa kiểu, kích thước của kí tự hiển thị. Hình  
dạng của mỗi kí tự có thể được xác định bởi một tập các đường gấp khúc (trường hợp  
font vector) hay là mẫu các pixel (font bitmap). Có nhiều loại font khác nhau như font  
bitmap, font truetype, font CHR, ...  
•
Kích thước : chiều cao và chiều rộng của kí tự. Các kí tự định nghĩa bằng đường gấp  
khúc có thể dễ dàng thay đổi kích thước hơn là các kí tự định nghĩa bằng mẫu các pixel.  
•
•
Khoảng cách giữa các kí tự.  
Sự canh chỉnh (gióng lề) : canh trái (left text), canh phải (right text), canh giữa (center  
text), canh đều nhau (justify text).  
•
•
Cách hiển thị tuần tự của các kí tự : có thể là phải sang trái, từ trên xuống dưới, từ trái  
sang phải, từ dưới lên trên.  
Hướng của kí tự.  
Hình 2.9 – Dạng bitmap và vector của font kí tự B  
2. CÁC THUẬT TOÁN VẼ ĐƯỜNG  
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à  
điểm nguyên sẽ được hiển thị trên màn hình.  
xi , yi ,i 0,.... Đây là các  
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  
x
i1, yi1 sẽ được xác định như thế nào.  
Nhận xét rằng để đối tượng hiển thị trên lưới nguyên được liền nét, các điểm mà  
chọn chỉ là một trong tám điểm được đánh số từ 1 đến 8 trong hình 2.10 (điểm đen chính là  
nói cách khác : i1, yi1 xi 1, yi 1  
x
i1, yi1  
có thể  
).Hay  
xi , yi  
x
.
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  
độ.  
Hình 2.10 – Các điểm  
x
i1, yi1  
có thể chọn ở bước (i+1)  
2.1. Thuật toán vẽ đoạn thẳng  
Xét đoạn thẳng có hệ số góc 0 m 1và 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ì  
ở bước thứ (i+1) sẽ là một trong hai trường hợp như hình vẽ sau :  
.
điểm cần chọn  
x
i1, yi1  
Hình 2.11 – Các điểm  
x
i1, yi1  
chọn ở bước (i+1) cho trường hợp  
đoạn thẳng có hệ số góc 0<m<1  
x
yi1  
xi 1  
i1  
Như vậy :  
yi , yi 1  
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 độ.  
2.1.1. Thuật toán DDA (Digital Differential Analyzer)  
Với thuật toán DDA, việc quyết định chọn yi1 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  
sẽ là giá trị sau khi làm tròn giá trị tung độ y.  
xi 1, y thuộc về đoạn thẳng thực. Tiếp đó, yi1  
y m  
yi1 Round  
xi 1  
b  
   
y
Như vậy :  
Hình 2.12 – Minh họa thuật toán DDA  
Nếu tính trực tiếp giá trị thực y ở mỗi bước từ phương trình y mx bthì 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 :  
ysau mxi1 b m  
xi 1 b  
ytröôùc mxi b  
ysau ytröôùc m  
Lưu đồ thuật toán DDA vẽ đoạn thẳng qua hai điểm (x1, y1) và (x2,y2)  
Begin  
m=Dy/Dx;  
x=x1;  
y=y1;  
putpixel(x, Round(y), c);  
No  
x<x2  
Yes  
x=x+1;  
y=y+m;  
putpixel(x, Round(y),c);  
End  
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<x2; i++)  
{
x++;  
y +=m;  
putpixel(x, Round(y), Color);  
}
} // LineDDA  
Nhận xét  
•
Việc sử dụng công thức ysau ytröôùc m để tính giá trị y tại mỗi bước đã giúp cho  
thuật toán DDA nhanh hơn hẳn so với cách tính y từ phương trình y mx b do khử  
được phép nhân trên số thực. Tuy nhiên, việc cộng dồn giá trị thực m vào y có thể sẽ tích  
lũy sai số làm cho hàm làm tròn có kết quả sai dẫn tới việc xác định vị trí của điểm vẽ ra  
bị chệch hướng so với đường thẳng thực. Điều này chỉ xảy ra khi vẽ đoạn thẳng khá dài.  
•
Tuy đã khử được phép nhân số thực nhưng thuật toán DDA vẫn còn bị hạn chế về mặt tốc  
độ do vẫn còn phép toán cộng số thực và làm tròn. Có thể khắc phục thao tác cộng số  
Dy  
Dx  
thực m và làm tròn trong thuật toán bằng cách nhận xét m   
với Dy, Dx là các số  
nguyên.  
2.1.2. Thuật toán Bresenham  
Thuật toán Bresenham đưa ra cách chọn yi1 là yi hay yi 1 theo một hướng khác sao cho có thể  
tối ưu hóa về mặt tốc độ so với thuật toán DDA. Vấn đề mấu chốt ở đây là làm thế nào để hạn chế tối đa  
các phép toán trên số thực trong thuật toán.  
Hình 2.13 – Minh họa thuật toán Bresenham  
Gọi  
Đặt  
xi 1, y  
d1 y yi  
d2 yi 1 y  
là điểm thuộc đoạn thẳng. Ta có: y m  
xi 1 b .  
Xét tất cả các vị trí tương đối của y so với yi và yi 1, việc chọn điểm  
thuộc vào việc so sánh d1 và d2 hay dấu của d1 d2 :  
x
i1, yi1 là S hay P phụ  
•
•
Nếu d1 d2 0 , ta sẽ chọn điểm S, tức là yi1 yi  
Ngược lại, nếu d1 d2 0 , ta sẽ chọn điểm P, tức là yi1 yi 1 .  
d1 d2 Dx 2y 2yi 1  
.
Xét pi Dx  
pi Dx  
2
m
xi 1  
b  
2yi 1  
Dy  
Dx  
Thay m   
c 2Dy 2b 1  
Nhận xét rằng do Dx 0 nên dấu của biểu thức d1 d2 cũng chính là dấu của  
cách khác, 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 ở  
vào phương trình trên ta được  
:
pi 2Dyxi 2Dxyi c  
,
với  
Dx .  
p
i . Hay nói một  
bước (i+1). Vấn đề còn lại là làm thế nào để tính được  
pi tại mỗi bước thật nhanh.  
Ta có :  
pi1 pi   
pi1 pi 2Dy  
pi1 pi 2Dy 2Dx  
2Dyxi1 2Dxyi1 c  
xi1 xi 2Dx  
yi1 yi  
2Dyxi 2Dxyi c  
yi1 yi  
, do xi1 xi 1  
Từ đây ta có thể suy ra cách tính pi1 từ pi như sau :  
•
Nếu pi 0 thì pi1 pi 2Dy do ta chọn yi1 yi  
.
•
Ngược lại, nếu pi 0, thì pi1 pi 2Dy 2Dx , do ta chọn yi1 yi 1 .  
Giá trị  
p0 được tính từ điểm vẽ đầu tiên  
2b 1 Dx  
x0 , y0  
theo công thức  
:
p0 2Dyx0 2Dxy0 c 2Dyx0 2Dxy0 2Dy   
Dy  
Dx  
Do  
x0 , y0  
là điểm nguyên thuộc về đoạn thẳng nên ta có y0 mx0 b   
x0 b . Thế vào  
phương trình trên ta suy ra : p0 2Dy Dx .  
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);  
No  
x<x2  
Yes  
No  
p<0  
Yes  
p=p+Const1;  
p=p+Const2;  
y=y+1  
x=x+1;  
putpixel(x,y,c);  
End  
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 = x2 - x1;  
Dy = 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<x2; i++)  
{
if (p<0)  
p += Const1;  
else  
{
p += Const2;  
y++;  
}
x++;  
putpixel(x, y, Color);  
}
} // LineBres  
Nhận xét  
•
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 pi1 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.  
2.1.3. Thuật toán MidPoint  
Thuật toán MidPoint đưa ra cách chọn yi1 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.  
•
Ngược lại nếu điểm Q nằm trên điểm MidPoint ta chọn P.  
Hình 2.14 – Minh hoïa thuaät toaùn MidPoint  
Ta có dạng tổng quát của phương trình đường thẳng :  
Ax By C 0  
với A y2 y1, B    
x2 x1 ,C x2 y1 x1 y2  
Đặt  
F
x, y  
Ax By C , ta có nhận xét :  
 0,neáu  
x,y  
naèm phía treân ñöôøng thaúng  
thuoäc veàñöôøng thaúng  
naèm phía döôùi ñöôøng thaúng.  
F
x, y  
0,neáu  
0,neáu  
x,y  
x,y  
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  
1
2
pi 2F  
MidPoint  
2F x 1, y   
.
i
i
•
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à yi1 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à yi1 yi 1 .  
Mặt khác :  
1
2
1
2
pi1 p 2F x 1, yi1  
2F x 1, y   
i
i1  
i
i
1
2
1
2
pi1 p 2 A  
x
i1 1  
B yi1   
C 2 A  
xi 1  
B y   
C  
i
i
pi1 pi 2A 2B  
Vậy :  
yi1 yi  
2Dy 2Dx  
yi1 yi  
•
•
pi1 pi 2Dy , nếu pi 0 do ta chọn yi1 yi  
.
pi1 pi 2Dy 2Dx , nếu pi 0 do ta chọn yi1 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ó : Ax0 By0 C 0  
1
2
1
2
p 2F x 1, y   
2 A  
x0 1  
B y   
C  
0
0
0
0
p0 2  
Ax0 By0 C 2A B 2A B 2Dy Dx  
Nhận xét rằng thuật toán MidPoint cho kết quả tương tự như thuật toán Bresenham.  
2.2. Thuật toán vẽ đường tròn  
Phương trình đường tròn có tâm là gốc tọa độ, bán kính R là : x2 y2 R2 . Từ phương  
trình này ta có thể đưa về dạng y   R2 x2 . Để vẽ các đường tròn có tâm  
kì, đơn giản chỉ cần tịnh tiến các điểm sau khi vẽ xong đường tròn có tâm là gốc tọa độ  
theo vector tịnh tiến  
xC , yC bất  
xC , yC .  
2.2.1. Một số cách tiếp cận vẽ đường tròn  
Do tính đối xứng nên để vẽ toàn bộ đường tròn, ta chỉ cần vẽ cung ¼ đường tròn sau đó  
lấy đối xứng để xác định các điểm còn lại.  
Một trong những cách đơn giản nhất là cho x chạy từ 0 đến R, sau đó tính y từ công thức trên (chỉ lấy  
giá trị dương) rồi làm tròn để xác định giá trị nguyên tương ứng. Cách làm này không hiệu quả do gặp phải  
các phép toán nhân và lấy căn làm hạn chế tốc độ, ngoài ra đường tròn vẽ ra theo cách này có thể không  
liền nét (trừ trường hợp R lớn) khi x gần R (do chỉ có một giá trị y duy nhất cho một giá trị x). Chúng ta có  
thể khắc phục điều này bằng cách điều chỉnh đối tượng thay đổi là x (rồi tính y theo x) hay y (rồi tính x  
theo y) tùy vào giá trị tuyệt đối của hệ số góc đường tròn là lớn hơn hay nhỏ hơn 1, nhưng cách làm này đòi  
hỏi thêm các phép tính toán và kiểm tra nên làm cho thuật toán phức tạp thêm. (Xem hình 2.15)  
Một cách tiếp cận khác là vẽ các điểm  
Rcos  
, Rsin  
  
, với  
chạy từ 00 đến 900. 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  
bán kính thay đổi.  
như thế nào cho phù hợp khi  
Hình 2.15 – Đường tròn vẽ ra không liền nét theo cách vẽ trên  
2.2.2. 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ẽ) :  
2
2
0 x R  
2
R
y R  
2
(-x,y)  
(x,y)  
(-y,x)  
(y,x)  
R
2
(-y,-x)  
(y,-x)  
(-x,-y)  
(x,-y)  
Hình 2.16 – Các vị trí đối xứng trên đường tròn (C) tương ứng với (x,y)  
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).  
Chọn điểm bắt đầu để vẽ là điểm (0,R). Dựa vào hình vẽ, nếu  
xi , yi là điểm nguyên đã  
tìm được ở bước thứ i, thì điểm ở bước thứ (i+1) là sự lựa chọn giữa S và P.  
x
i1, yi1  
x
yi1  
xi 1  
i1  
Như vậy :  
yi , yi 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.  
Hình 2.17 – Thuật toán MidPoint vẽ đường tròn  
Đặt  
F
x, y  
x2 y2 R2 , ta có :  
 0,neáu  
x,y  
x,y  
x,y  
naèm trong ñöôøng troøn  
naèm treân ñöôøng troøn  
naèm ngoaøi ñöôøng troøn.  
F
x, y  
0,neáu  
0,neáu  
1
2
Xét pi F  
MidPoint  
F x 1, y . Ta có :  
i
i
•
Nếu pi 0, đ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à yi1 yi  
.
•
Ngược lại, nếu pi 0, đ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à yi1 yi 1.  
Mặt khác :  
1
2
1
2
pi1 p F x 1, yi1  
F x 1, y   
i i  
i
i1  
2
2
1
2
1
2
p p   
x
1 2  
y  
R2  
x 1 2  
y   
R2  
i1  
i
i1  
i1  
i
i
2
2
1
2
1
p p   
x 2 2  
y  
R2  
x 1 2  
y   
R2  
i1  
i
i
i1  
i
i
2
pi1 p 2x 3  
Vậy :  
yi21 yi2
  
yi1 yi
  
i
i
•
•
pi1 pi 2xi 3, nếu pi 0 do ta chọn yi1 yi  
pi1 pi 2xi 2yi 5, nếu pi 0 do ta chọn yi1 yi 1.  
x0 , y0 0, R  
R  
.
Ta tính giá trị p0 ứng với điểm ban đầu  
.
1
2
1
2
5
4
p F x 1, y   
F 1, R   
0
0
0
Lưu đồ thuật toán MidPoint vẽ đường tròn  
Begin  
p=5/4-R;  
x=0;  
y=R;  
Put8Pixel(x, y, c);  
No  
x<y  
Yes  
No  
p<0  
Yes  
p=p+2*x+3;  
p=p+2(x-y)+5;  
y=y-1  
x=x+1;  
Put8Pixel(x,y,c);  
End  
Cài đặt minh họa thuật toán MidPoint vẽ đường tròn  
// Ve 8 diem doi xung  
void Put8Pixel(int x, int y)  
{
putpixel(x, y, Color);  
putpixel(y, x, Color);  
putpixel(y, -x, Color);  
putpixel(x, -y, Color);  
putpixel(-x, -y, Color);  
putpixel(-y, -x, Color);  
putpixel(-y, x, Color);  
putpixel(-x, y, Color);  
} // Put8Pixel  
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  
2.3. Thuật toán vẽ các đườ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 :  
Ax2 Bxy Cy2 Dx Ey F 0 . 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:  
 0, daïng ñöôøng troøn (neáu A C vaø B 0 ) hay ellipse  
B2 4AC 0, daïng parabol  
0, daïng hyperbol.  
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. Điều này sẽ làm tăng tốc độ vẽ so với việc phải vẽ toàn bộ  
đường cong. Một trong những cách đơn giản nhất là dựa vào tính đối xứng, tính chất của  
hàm chẵn, hàm lẻ,   
Bước 2 : Tính đạo hàm để từ đó phân thành các vùng vẽ :  
x
yi1  
xi 1  
i1  
•
•
•
•
Nếu 0 f '(x) 1 thì  
yi , yi 1  
(*)  
x
xi 1  
i1  
Nếu 1 f '(x) 0 thì  
yi1  
yi , yi 1  
(*)  
y
yi 1  
i1  
Nếu f '(x) 1 thì  
xi1  
xi, xi 1  
(*)  
y
yi 1  
i1  
Nếu f '(x)  1 thì  
xi1  
xi , xi 1  
(*)  
Đây là bước quan trọng vì với việc xác định đối tượng x hay y biến thiên theo dáng điệu  
của đường cong sẽ đảm bảo đường sau khi được vẽ ra sẽ liền nét, không bị hở.  
Bước 3 : Xác định công thức của pi cho từng trường hợp để quyết định (*) dựa trên dấu  
của pi  
.
pi thường là hàm được xây dựng từ phương trình đường cong để cho pi 0 nếu  
xi ,yi  
thuộc về đường cong. Việc chọn pi cần phải chú ý sao cho thao tác tính pi 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 pi1 và pi bằng cách xét hiệu pi1 pi  
.
Bước 5 : Tính p0 và hoàn chỉnh thuật toán.  
3. CÁC THUẬT TOÁN TÔ MÀU  
Các vùng tô là một trong những đối tượng đồ họa cơ sở được hầu hết các công cụ lập  
trình đồ họa hỗ trợ. Có hai dạng vùng tô thường gặp đó là : tô bằng một màu thuần nhất  
(solid fill) hay tô theo một mẫu tô (fill-pattern) nào đó.  
Một vùng tô thường được xác định bởi một đường khép kín nào đó gọi là đường biên.  
Một trong những dạng đường biên đơn giản nhất đó là đa giác.  
Để tô màu một vùng tô, người ta thường chia làm hai công đoạn : công đoạn thứ nhất là  
xác định các điểm nào để tô và công đoạn còn lại đơn giản hơn đó là quyết định tô các  
điểm đó bằng giá trị màu nào. Công đoạn thứ hai chỉ thực sự phức tạp nếu ta tô theo một  
mẫu tô nào đó không phải là tô thuần một màu.  
Có hai cách tiếp cận chính để tô màu một vùng tô đối với thiết bị hiển thị dạng điểm đó  
là : tô theo dòng quét (scan-line fill) và tô dựa theo đường biên (boundary fill).  
Phương pháp tô theo dòng quét sẽ xác định các phần giao của các dòng quét kế tiếp nhau  
với đường biên của vùng tô, sau đó sẽ tô màu các điểm thuộc về phần giao này. Cách tiếp  
cận này thường được dùng để tô màu các đa giác, đường tròn, ellipse, và một số đường  
cong đơn giản khác. Phương pháp tô dựa theo đường biên sẽ bắt đầu từ một điểm ở bên  
trong vùng tô và từ đó loang dần ra cho tới khi ta gặp các điểm biên. Cách tiếp cận này  
thường được dùng cho các vùng tô có dạng đường biên phức tạp hơn.  
3.1. 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 xi , yi  
,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, …  
Hình 2.18 sau minh họa ý tưởng chính của thuật toán. Với mỗi dòng quét, ta sẽ xác định phần giao  
của đa giác và dòng quét rồi tô màu các pixel thuộc đoạn giao đó. Để xác định các đoạn giao ta tiến hành  
việc tìm giao điểm của dòng quét với các cạnh của đa giác, sau đó các giao điểm này sẽ được sắp theo thứ  
tự tăng dần của hoành độ giao điểm. Các đoạn giao chính là các đoạn thẳng được giới hạn bởi từng cặp  
giao điểm một, ví dụ như (0,1), (2,3), ….  
Hình 2.18 – Thuật toán scan-line với một dòng quét nào đó  
Ta có thể tóm bắt các bước chính của thuật toán :  
•
Tìm ytop  
,
ybottom 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 ytop max  
yi , xi , yi P ybottom min yi , xi , yi P  
,
.
•
Ứng với mỗi dòng quét y k , với k thay đổi từ bottom đến top , lặp :  
y
y
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 : x0, x1, …  
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  
x0 , x1 x2 , x3 ,..., x2k , x2k1  
,
.
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. Do đó để cải thiện tốc độ cần phải có một cách nào đó để  
hạn chế được số cạnh cần tìm giao điểm ứng với mỗi 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.  
Điều này sẽ làm giảm tốc độ thuật toán khi phải lặp đi lặp lại nhiều lần thao tác này khi  
dòng quét quét qua đa giác.  
•
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. Điều này  
chỉ xảy ra khi dòng quét đi ngang qua các đỉnh của đa giá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 như trong  
trường hợp của hình 2.19. 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.  
Để giải quyết các vấn đề trên, cần phải xây dựng một cấu trúc dữ liệu và thuật toán thích  
hợp đối với chúng.  
Hình 2.19 – Dòng quét y=k2 đi ngang qua đỉnh có thể sẽ cho kết quả tô không chính xác so với dòng quét y=k1  
3.1.1. Danh sách các cạnh kích hoạt AET (Active Edge Table)  
Để hạn chế số cạnh cần tìm giao điểm ứng với mỗi dòng quét, ta xây dựng một số cấu  
trúc dữ liệu như sau :  
Cạnh đa giác (EDGE)  
Mỗi cạnh của đa giác được xây dựng từ hai đỉnh kề nhau  
P
i xi , yi  
và  
P
i1   
x
i1, yi1 gồm  
các thông tin sau :  
•
yMin : giá trị tung độ nhỏ nhất trong 2 đỉnh của cạnh.  
•
•
xIntersect : hoành độ giao điểm của cạnh với dòng quét hiện đang xét.  
DxPerScan : giá trị 1/m (m là hệ số góc của cạnh).  
•
deltaY : khoảng cách từ dòng quét hiện hành tới đỉnh yMax .  
Tải về để xem bản đầy đủ
doc 33 trang Thùy Anh 27/04/2022 7140
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Đồ họa máy tính - Chương 2, Phần 2: Các đối tượng đồ họa cơ sở", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • docgiao_trinh_do_hoa_may_tinh_chuong_2_phan_2_cac_doi_tuong_do.doc
  • htmChuong2.htm