›
›

Bài giảng Đồ họa hiện thực ảo - Bài 2: Các giải thuật sinh các thực thể cơ sở - Lê Tấn Hùng

Download
Bài 2:  
Các giải thuật sinh  
các thực thể cơ sở  
Le Tan Hung  
hunglt@it-hut.edu.vn  
(c) SE/FIT/HUT 2002  
Giải thuật xây dựng các  
thực thể cơ sở  
„ Giải thuật sinh đường thẳng – Line  
„ Giải thuật sinh đường tròn - Circle  
„ Giải thuật VanAken sinh Ellipse  
„ Giải thuật sinh đa giác  
„ Giải thuật sinh ký tự  
2
(c) SE/FIT/HUT 2002  
Rời rạc hoá điểm ảnh  
(Scan Conversion rasterization)  
„ Scan Conversion rasterization  
„ Tính chất các đối tượng cần đảm bảo :  
„ smooth  
„ continuous  
„ pass through specified points  
„ uniform brightness  
„ efficient  
3
(c) SE/FIT/HUT 2002  
Biểu diễn đoạn thẳng  
„ Biểu diễn tường minh  
(y-y1)/( x-x1) = ( y2-y1)/( x2-x1)1  
y = kx + m  
P(x2 , y2)  
„ Biểu diễn không tng minh  
(y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0  
hay rx + sy + t = 0  
u
P(x1, y1)  
„ Biểu diễn tham biến  
P(u) = P1 + u(P2 - P1)  
u [0,1]  
m
4
(c) SE/FIT/HUT 2002  
Thuật toán DDA  
(Digital Differential Analizer)  
Giải thuật thông thường  
Giải thuật DDA  
DrawLine(int x1,int y1, int x2,int y2,  
„ Với 0 < k < 1  
int color)  
xi+1 = xi + 1  
{
y= y+ k  
float y;  
int x;  
với i=1,2,3....  
for (x=x1; x<=x2; x++)  
{
y = y1 + (x-x1)*(y2-y1)/(x2-x1)  
WritePixel(x, Round(y), color );  
}}  
5
(c) SE/FIT/HUT 2002  
Giải thuật Bresenham  
„ 1960 Bresenham thuộc IBM  
„ điểm gần với đường thẳng dựa  
2
trên độ phân giai hưu hạn  
d1  
d2  
„ loại bỏ được các phép toán  
1
chia và phép toán làm tròn  
như ta đã thấy trong giải thuật  
DDA  
0
„ Xét đoạn thẳng với 0 < k < 1  
0
1
2
6
(c) SE/FIT/HUT 2002  
Giải thuật Bresenham  
d2 = y - yi = k(xi +1) + b - yi  
d1 = yi+1 - y = yi + 1 - k(xi + 1) - b  
A
yi+1  
yi  
d1  
d2  
B
xi  
xi+1  
7
(c) SE/FIT/HUT 2002  
Giải thuật Bresenham  
8
(c) SE/FIT/HUT 2002  
Giải thuật trung điểm-Midpoint  
„ 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
yi+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.  
( xi , yi )  
xi  
xi+1  
„ Nếu d > 0 điểm B được chọn, yi+1 = yi  
„ nếu d < 0 điểm A được chọn. y= y+ 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.  
9
(c) SE/FIT/HUT 2002  
Bresenham’s Algorithm:  
Midpoint Algorithm  
„ If di > 0 then chọn điểm A⇒ trung điểm tiếp theo sẽ có dạng:  
3
2
3
2
x +2, y + ⇒ d = a  
(
xi +2  
)
+b y + +c  
i
i
i+1  
i
= di +a+b  
10  
(c) SE/FIT/HUT 2002  
Midpoint Line Algorithm  
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  
initialisation  
choose B  
else  
d = d+2*(dy-dx)  
x = x+1  
y = y+1  
choose A  
endif  
SetPixel(x,y)  
endwhile  
11  
(c) SE/FIT/HUT 2002  
B¾t ®Çu  
Giải thuật  
Bresenham's Midpoint  
x = x1 ;  
y = y1;  
dx = x2 - x1;  
dy = y2 - y1;  
d = dy - dx/2;  
Putpixel (x ,y);  
<= 0  
No  
d = d + dy - dx  
y = y + 1  
x = x + 1  
yes  
d = d + dy  
yes  
x < x2  
no  
KÕt thóc  
12  
(c) SE/FIT/HUT 2002  
Sinh đường tròn  
Scan Converting Circles  
„ Explicit: y = f(x)  
y = ± R2 − x2  
Usually, we draw a quarter circle by  
incrementing x from 0 to R in unit steps  
and solving for +y for each step.  
„ Parametric:  
x = Rcosθ  
- by stepping the angle from 0 to 90  
- avoids large gaps but still insufficient.  
y = Rsinθ  
„ Implicit: f(x) = x2+y2-R2  
If f(x,y) = 0 then it is on the circle.  
f(x,y) > 0 then it is outside the circle.  
f(x,y) < 0 then it is inside the circle.  
13  
(c) SE/FIT/HUT 2002  
Midpoint Circle Algorithm  
„ 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ó  
14  
(c) SE/FIT/HUT 2002  
Midpoint Circle Algorithm  
„ As with the line, we determine the value of the decision variable by  
substituting the mid-point of the next pixel into the implicit form of the  
circle:  
2
1
2
2
2
(
)
d = x +1 + y − −r  
i
i
i
„ If di < 0 we choel B  
„ Note: we currently assume the circle is centered at the origin  
15  
(c) SE/FIT/HUT 2002  
Midpoint Circle Algorithm  
d = 1-r  
x = 0  
y = r  
initialisation  
stop at diagonal ⇒ end of octant  
while y < x  
if d < 0 then  
d = d+2*x+3  
x = x+1  
choose A  
else  
d = d+2*(x-y)+5  
x = x+1  
y = y-1  
choose B  
endif  
xy
endwhile  
Translate to the circle center  
16  
(c) SE/FIT/HUT 2002  
Scan Converting Ellipses  
F(x, y) = b2 x2 + a2 y2 − a2b2 = 0  
„ 2a is the length of the major axis along the x axis.  
„ 2b is the length of the minor axis along the y axis.  
„ The midpoint can also be applied to ellipses.  
„ For simplicity, we draw only the arc of the ellipse that lies  
in the first quadrant, the other three quadrants can be drawn  
by symmetry  
17  
(c) SE/FIT/HUT 2002  
Scan Converting Ellipses: Algorithm  
A
M
B
tiep tuyen = -1  
gradient  
B
C
M
i
„ Firstly we divide the quadrant into two regions  
„ Boundary between the two regions is  
„ the point at which the curve has a slope of -1  
„ the point at whiconents of equal  
magnitude  
grad F(x,
y
) =∂F/∂xi+∂F/∂
y
j
=2b2xi+2a2
y
j  
18  
(c) SE/FIT/HUT 2002  
Ellipses: Algorithm (cont.)  
„ At the next midpoint, if a2(yp-0.5)<=b2(xp+1), we switch region 1=>2  
„ In region 1, choices are E and SE  
„ Initial condition: dinit = b2+a2(-b+0.25)  
„ For a move to E, d= d+Deltawith Delta= b2(2xp+3)  
„ For a move to SE, dnew = dold+DeltaSE with  
DeltaSE = b2(2xp+3)+a2(-2yp+2)  
„ In region 2, choices are S and SE  
„ Initial condition: dinit = b2(xp+0.5)2+a2((y-1)2-b2)  
„ For a move to S, dnew = dold+Deltas with Deltas = a2(-2yp+3)  
„ For a move to SE, d= d+Deltawith  
DeltaSE = b2(2xp+2)+a2(-2yp+3)  
„ Stop in region 2 when the y value is zero.  
19  
(c) SE/FIT/HUT 2002  
Ký tự Bitmap  
„ 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  
„ fontcache  
„ các ký tự theo chuỗi liên tiếp nhau trong  
bộ nhớ  
„ Dạng cơ bản  
ab  
„ (thường N, nghiêng I, đậm B, nghiêng  
đậm B+I)  
„ Thuộc tính  
„ Also colour, size, spacing and  
orientation  
20  
(c) SE/FIT/HUT 2002  
Tải về để xem bản đầy đủ
pdf 28 trang yennguyen 13/04/2022 3720
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Đồ họa hiện thực ảo - Bài 2: Các giải thuật sinh các thực thể cơ sở - Lê Tấn Hùng", để 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:

  • pdfbai_giang_do_hoa_hien_thuc_ao_bai_2_cac_giai_thuat_sinh_cac.pdf