›
›

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  
[email protected].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 19260 Free
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