Bài giảng Công nghệ đồ họa và hiện thực ảo - Bài 3: Giải thuật sinh các thực thể cơ sở - Trịnh Thành Trung

©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Bài 3 
GIẢI THUẬT SINH 
CÁC THỰC THỂ CƠ SỞ 
1 
Trịnh Thành Trung 
trungtt@soict.hust.edu.vn 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
NỘI DUNG 
1. Biểu diễn đoạn thẳng 
a) Thuật toán DDA 
b) Giải thuật Bresenham 
c) Giải thuật trung điểm 
2. Biểu diễn đường tròn 
3. Biểu diễn đường ê-líp 
4. Giải thuật sinh ký tự 
2 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
3 
• Là tiến trình sinh các đối tượng hình học cơ sở 
bằng phương pháp xấp xỉ dựa trên lưới phân giải 
của màn hình 
• Tính chất các đối tượng cần đảm bảo : 
– mượt - smooth 
– liên tục - continuous 
– đi qua các điểm xác định 
– độ sáng đồng nhất 
– hiệu quả - efficient 
Rời rạc hóa điểm ảnh 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
BIỂU DIỄN ĐOẠN THẲNG 
1 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
•Biểu diễn tường minh 
(y-y1)/( x-x1) = ( y2-y1)/( x2-x1) 
y = kx + m 
– k = (y2-y1)/( x2-x1) 
– m = y1- kx1 
– y = k x 
Biểu diễn đoạn thẳng 
5 
m 
P(x1, y1) 
P(x2 , y2) 
u 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
•Biểu diễn không tường 
minh 
(y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 
hay rx + sy + t = 0 
– s = -(x2-x1 ) 
– r = (y2-y1) và t = x2y1 - x1y2 
6 
m 
P(x1, y1) 
P(x2 , y2) 
u 
Biểu diễn đoạn thẳng 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
•Biểu diễn tham biến 
P(u) = P1 + u(P2 - P1) 
u [0,1] 
X = x1 + u( x2 - x1 ) 
Y = y1 + u( y2 - y1 ) 
7 
m 
P(x1, y1) 
P(x2 , y2) 
u 
Biểu diễn đoạn thẳng 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Giải thuật DDA 
Với 0 < k < 1 
xi+1 = xi + 1 
yi+1 = yi + k 
với i=1,2,3.... 
Thuậttoán ddaline (x1, y1, x2, y2) 
 x1, y1, x2, y2 : tọa độ 2 điểm đầu cuối 
 k : hệ số góc 
 x,y,m :biến 
 begin 
 m =(x2-x1)/(y2-y1); 
 x = x1; 
 y = y1; 
 k = 1/m; 
 putpixel(x,y); 
while x<x2 
 begin 
 x = x+1; 
 y = y+k; 
putpixel(x,round(y)); 
 end; end; 
Thuật toán DDA 
(Digital Differential Analyzer) 8 
Giải thuật thông thường 
DrawLine(int x1,int y1, 
int x2,int y2, int color) 
{ 
 float y; 
 int x; 
 for (x=x1; x<=x2; x++) 
 { 
 y = y1 + (x-
x1)*(y2-y1)/(x2-x1) 
 WritePixel(x, 
Round(y), color ); 
 }} 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
9 
• 1960 Bresenham thuộc IBM 
• điểm gần với đường thẳng 
dựa trên độ phân giai hưu 
hạn 
• loại bỏ được các phép toán 
chia và phép toán làm tròn 
như ta đã thấy trong gỉai 
thuật DDA 
• Xét đoạn thẳng với 0 < k < 1 
Giải thuật Bresenham 
0 1 2 
0 
1 
2 
d1 
d2 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
d2 = y - yi = k(xi +1) + b - yi 
d1 = yi+1 - y = yi + 1 - k(xi + 
1) - b 
if d1 d2 => yi+1 = yi + 1 
else d1 > d2 => yi+1 = yi 
D = d1 - d2 
 = -2k(xi + 1) + 2yi - 2b + 1 
Pi = xD = x (d1 - d2) 
Giải thuật Bresenham 
10 
0 1 2 
0 
1 
2 
d1 
d2 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Pi = -2 yxi + 2 xyi + c 
Pi+1 - Pi 
 = -2 y(xi+1 - xi) + 2 x(yi+1 - yi) 
•Nếu Pi 0 yi+1 = yi + 1 
 Pi+1 = Pi - 2 y + 2 x 
•Nếu Pi > 0 yi+1 = yi 
 Pi+1 = Pi - 2 y 
P1 = x(d1 - d2) 
P1 = -2 y + x 
11 
P > 0
B¾t ®Çu
x = x1 ;
y = y1;
dx = x2 - x1;
dy = y2 - y1;
P = dx - 2dy;
Putpixel (x ,y);
x < x2
KÕt thóc
P = P - 2dy
P = P - 2dy + 2dx
y = y + 1
yes
no
No
yes
x = x + 1
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
•Jack Bresenham 1965 / Pitteway 
1967 
•VanAken áp dụng cho việc sinh các 
đường thẳng và đường tròn 1985 
•Các công thức đơn giản hơn, tạo 
được các điểm tương tự như với 
Bresenham 
A 
M 
B 
Giải thuật trung điểm 
12 
 yi+1 
 M 
 ( xi , yi ) 
 xi xi+1 
•d = F (xi + 1, yi + 1/2) là trung điểm của đoạn AB 
•Việc so sánh, hay kiểm tra M sẽ được thay bằng việc xét giá trị d. 
– Nếu d > 0 điểm B được chọn, yi+1 = yi 
– nếu d < 0 điểm A được chọn. yi+1 = yi + 1 
– Trong trường hợp d = 0 chúng ta có thể chọn điểm bất kỳ hoặc A, 
hoặc B. 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
13 
• Sử dụng phương pháp biểu diễn không tường minh 
• Tại mỗi trung điểm của đoạn thẳng giá trị được tính 
là: 
• Chúng ta gọi di là biến quyết định của bước thứ i 
Giải thuật trung điểm 
0 cbyax
 iiii
iiii
iiii
yxcbyax
yxcbyax
yxcbyax
,0
,0
,0
 on line 
above line 
below line 
 cybxad iii 
2
1
1
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
14 
• If di > 0 then chọn điểm A trung điểm tiếp 
theo sẽ có dạng: 
Giải thuật trung điểm 
bad
cybxadyx
i
iiiii
2
3
2
2
3
,2 1
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
15 
Giải thuật trung điểm 
if di < 0 then chọn điểm B và trung điểm mới là 
Ta có: 
Ðiểm đầu 
 
2
2
1
1
2
1
,1
b
acbyax
cybxadyx
startstart
startstartstartstartstart
2
0
b
a 
ad
cybxadyx
i
iiiii
2
1
2
2
1
,2 1
Cx
x
y
y
xCc
xxxb
yyya
startend
startend



 where
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
16 
Giải thuật trung điểm 
dx = x_end-x_start 
dy = y_end-y_start 
d = 2*dy-dx 
x = x_start 
y = y_start 
while x < x_end 
 if d <= 0 then 
 d = d+(2*dy) 
 x = x+1 
 else 
 d = d+2*(dy-dx) 
 x = x+1 
 y = y+1 
 endif 
 SetPixel(x,y) 
endwhile 
initialisation 
choose B 
choose A 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
17 
• d = a(xi + 1) + b(yi + 1/2) + c 
• Nếu điểm được chọn là B thi M sẽ tang theo x một đơn vị 
– di +1 = F(xi +2, yi + 1/2) 
– = a(xi +2) + b(yi + 1/2) + c 
– di = a(xi + 1) + b(yi + 1/2) + c 
• Nếu điểm A được chọn thì M tăng theo 2 hướng x và y với 
cùng một đơn vị. 
– di + 1 = F (xi + 2, yi + 3/2) 
– = a(xi + 2) + b(yi +3/2) + c 
– di + 1 = di + a + b. 
• Với a + b = dy - dx. 
Giải thuật trung điểm 
d <= 0
B¾t ®Çu
x = x1 ;
y = y1;
dx = x2 - x1;
dy = y2 - y1;
d = dy - dx/2;
Putpixel (x ,y);
x < x2
K Õt thóc
d = d + dy
d = d + dy - dx
y = y + 1
yes
no
No
yes
x = x + 1
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
BIỂU DIỄN ĐƯỜNG TRÒN 
VÀ ĐƯỜNG Ê-LÍP 
2 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
19 
• Sử dụng phương pháp biểu diễn không tường minh trong giải 
thuật 
• Thực hiện giải thuật trên 1/8 đường tròn và lấy đối xứng xho các 
góc còn lại. 
• Với di là giá trị của đường tròn tại một điểm bất kỳ ta có 
Giải thuật trung điểm cho 
đường tròn 
 0222 ryyxx cc
circle outside is , if 0
circleon is , if 0
circle inside is , if 0
ii
ii
ii
i
yx
yx
yx
d
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
20 
Giải thuật trung điểm cho 
đường tròn 
d = 1-r 
x = 0 
y = r 
while y < x 
 if d < 0 then 
 d = d+2*x+3 
 x = x+1 
 else 
 d = d+2*(x-y)+5 
 x = x+1 
 y = y-1 
 endif 
 SetPixel(cx+x,cy+y) 
endwhile 
initialisation 
choose B 
choose A 
Translate to the circle center 
stop at diagonal end of octant 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
21 
• Tương tự hình tròn 
• Áp dụng giải thuật cho ¼ đường ê-líp, sau đó lấy 
đối xứng cho các vị trí còn lại 
• Phương trình đường ê-líp 
– 2a: đường kính ngang 
– 2b: đường kính dọc 
Giải thuật trung điểm cho 
đường ê-líp 
2 2 2 2 2 2( , ) 0F x y b x a y a b 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
BIỂU DIỄN ĐA GIÁC 
3 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
23 
• Tồn tại rất nhiều giải thuật sinh đa giác. 
• Mỗi giải thuật phục vụ cho 1 loại đa giác nhất 
định: 
• Một số giải thuật chỉ sử dụng được với các tam 
giác 
• Một số giải thuật đòi hỏi đa giác là lồi, không tự 
cắt chính nó và không có lỗ hổng bên trong 
Giải thuật đường quét sinh đa giác 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
24 
• Polygon scan conversion là giải thuật chung 
kinh điển cho các loại khác nhau 
• Cho mỗi đoạn thẳng quét, chúng ta xác định các 
cạnh của đa giác cắt đoạn thẳng 
Giải thuật đường quét sinh đa giác 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
25 
• Dùng giải thuật (trung điểm) để 
xác định các điểm biên cho mỗi 
đa giác theo thứ tự tăng của x. 
• Các điểm phải: 
– Không bị chia sẻ bởi các đa 
giác lân cận 
– Các đa giác chỉ toàn các 
điểm cạnh (điểm biên) 
• Đảm bảo các đa giác chia sẻ 
điểm biên mà không chia sẻ 
các điểm ảnh bên trong của 
mình. 
Giải thuật đường quét sinh đa giác 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
26 
• Thủ tục chung: 
– Xác định giao của đường thẳng quét với cạnh 
đa giác 
– Sắp xếp các giao điểm theo mức độ tăng dần 
của x value 
– Điền các điểm ảnh vào giữa cặp các điểm x 
Giải thuật đường quét sinh đa giác 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
27 
Giải thuật đường quét sinh đa giác 
rounded down for A 
rounded up for B 
integer x value is on 
right = exterior 
ymax not 
included 
horizontal edge 
removed 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
BIỂU DIỄN KÝ TỰ 
4 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
29 
• Trên cơ sỏ định nghĩa mỗi ký tự với một font chư 
cho trước là một bitmap chữ nhật nhỏ 
• Font/typeface: set of character shapes 
Giải thuật sinh ký tự 
ab 
• fontcache 
– các ký tự theo chuỗi liên tiếp 
nhau trong bộ nhớ 
• Dạng cơ bản 
– (thường N, nghiêng I, đậm B, 
nghiêng đậm B+I) 
• Thuộc tính 
– Also colour, size, spacing 
and orientation 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Cấu trúc font chữ 
30 
Typedef struct 
{ 
int leftx, 
int width; 
} Char location; //Vị trí 
Typedef struct 
{ 
CacheId; 
Heiglit; // Độ rộng chữ 
CharSpace; // Khoảng cách 
 // giữa các ký tự 
Charlocation Table [128]; 
} fontcache 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
31 
• Xây dựng theo phương 
pháp định nghĩa các ký 
tự bởi đường cong mềm 
bao ngoài của chúng. 
• Tốn kém nhất về mặt 
tính toán 
• Chất lượng cao 
Ký tự vector 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Đơn giản trông việc sinh ký 
tự (copypixel) 
• Lưu trữ lớn 
• Các phép biến đổi (I,B, scale) 
đòi hỏi lưu trữ thêm 
• Kích thước không đổi 
• Phức tạp (Tính toán 
phương trình) 
• Lưu trữ gọn nhẹ 
• Các phép biến đổi dựa vào 
các công thức biến đổi 
• Kích thước phụ thuôc vào 
môi trường ( không có kích 
thước cố định) 
So sánh 
32