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

©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Trịnh Thành Trung 
trungtt@soict.hust.edu.vn 
Bài 4 
CÁC GIẢI THUẬT CƠ SỞ 
1 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
NỘI DUNG 
1. Các giải thuật xén tỉa 
2. Thuật toán tô miền kín 
3. Phép xử lý Antialiasing 
2 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
CÁC GIẢI THUẬT XÉN TỈA 
1 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
4 
• Khái niệm 
Xén tỉa là tiến trình tự động 
xác định các điểm của 1 
đối tượng nằm trong hay 
ngoài cửa sổ hiển thị 
• Tiết kiệm thời gian tiến 
trình rasterize bỏ qua phần 
nằm ngoài cửa sổ hiển thị 
• Clipping điểm 
– xmin x xmax 
– ymin y ymax 
Xén tỉa - clipping 
xmin xmax 
ymax 
ymin 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
5 
• Tiến trình, giải thuật kiểm tra chấp nhận các 
đoạn thẳng nằm trong và loại bỏ các đoạn thẳng 
nằm ngoài dựa trên 2 điểm đầu cuối 
• Lý do: 
– Không kiểm tra mọi điểm trên đoạn thẳng 
– Hầu hết các đoạn thẳng với 1 màn hình hiển 
thị đều được chấp nhận hoặc loại bỏ 
– Rất ít các đoạn thẳng cắt cửa sổ hiển thị 
Clipping đoạn thẳng 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
GIẢI THUẬT COHEN 
SUTHERLAND OUTCODE 
6 
• Giải thuật Cohen-Sutherland thực 
hiện nhanh với các trương hợp 
đoạn thẳng nằm trong hay ngoài 
cửa sổ hiện thị 
• Mỗi điểm đầu cuối được gán mã 
code phụ thuộc vào vị trí trong 
mặt phẳng mã 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
7 
p.code = 0000 
 If p.x > P.code or 0001 
 If p.y > P.code or 0100 
 If p.x >= xmax >> P.code or 0010 
 If p.y >= ymax >> P.code or 1000 
Giải thuật Cohen Sutherland 
outcode 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
8 
• If P1.code OR P2.code == 
0000 
– Chấp nhận toàn đoạn 
thẳng 
• If P1.code AND P2.code != 
0000 
– Loại 
• Với truờng hợp cắt, giải 
thuật xác định lại điểm đầu 
cuối là giao của đoạn thẳng 
và khung bao của cửa sổ 
hiển thị 
Giải thuật Cohen Sutherland 
outcode 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
9 
• Giải Cohen-Sutherland yêu cầu cửa sổ là hình 
chữ nhật, các cạnh là cạnh của màn hình 
• Vấn đề nảy sinh khi cửa sổ clip là 1 đa giác bất 
kỳ hoặc hình chữ nhật quay đi 1 góc 
• Giải thuật Liang-Barsky tối ưu khi tìm giao điểm 
của đoạn thẳng với cử sổ hiển thị 
• Nicholl-Lee-Nicholl reducing redundant 
boundary clipping by identifying edge and 
corner regions 
Giải thuật Cyrus-beck Liang Barsky 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
10 
• x = x1 + (x2 - x1)u = x1 + uDx 
• y = y1 + (y2 - y1)u = y1 + uDy 
• xmin x1 + Dx.u xmax x [xm, xM] 
• ymin y1 + Dy.u ymax y [ym, yM] 
• Pk u qk k = 1, 2, 3, 4 
Liabarsky 
DyP
DyP
DxP
DxP
4
3
2
1
14
13
12
11
yyq
yyq
xxq
xxq
M
m
M
m
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
11 
• Nếu Pk = 0 : điều đó tương đương với việc đoạn 
thẳng đang xét song song với cạnh thứ k của 
hình chữ nhật clipping. 
• a) Nếu qk < 0 Đường thẳng nằm ngoài 
cửa sổ (hệ bất phương trình trên vô 
nghiệm) 
• b)Nếu qk >= 0 thì đoạn thẳng nằm trong 
hoặc nằm trên cạnh của cửa sổ clipping. 
• Hệ bất phương trình luôn thoả mãn. 
Liabarsky 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
12 
• Nếu Pk 0 : đoạn thẳng đang xét sẽ cắt cạnh k 
tương ứng của cửa sổ clipping tại vị trí trên đoạn 
thẳng uk = qk/Pk. 
– Pk < 0 đoạn thẳng có dạng đi từ ngoài vào trong 
• bất phương trình sẽ có dạng u qk/Pk  u uk. 
– Pk > 0 
• u uk sẽ thuộc cửa sổ hiển thị. 
• bất phương trình sẽ có dạng u qk/Pk 
• u uk với uk = qk/Pk là giao của đoạn thẳng với cạnh 
k của cửa sổ clipping 
• đoạn thẳng có dạng đi từ trong ra ngoài so với cạnh 
k. 
Liabarsky 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
13 
• Pk < 0 và uk < 0 
– cạnh k của cửa sổ clipping cắt đoạn thẳng tại 
phần mở rộng nằm ngoài đoạn thẳng. 
– uk u< 0 thoả mãn bất phương trình sẽ không 
nằm trên đoạn thẳng cần xét. 
– => uk sẽ nhận là 0 khi uk<0 
• Pk > 0 và uk > 1 
– => uk tương ứng sẽ nhận giá trị 1. 
• điểm nằm trong cửa sổ clipping sẽ có dạng như 
sau: 
– U1 u U2 
Liabarsky 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
14 
 



  0,:0max1 k
k
k
kk P
P
q
uuU
 



  0,:1min2 k
k
k
kk P
P
q
uuU
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
15 
• Basic idea: 
– Consider each edge of the viewport individually 
– Clip the polygon against the edge equation 
– After doing all planes, the polygon is fully clipped 
Sutherland-Hodgman Clipping 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
16 
• Input/output for algorithm: 
– Input: list of polygon vertices in order 
– Output: list of clipped poygon vertices 
consisting of old vertices (maybe) and new 
vertices (maybe) 
• Note: this is exactly what we expect from the 
clipping operation against each edge 
Sutherland-Hodgman Clipping 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
17 
• Sutherland-Hodgman basic routine: 
– Go around polygon one vertex at a time 
– Current vertex has position p 
– Previous vertex had position s, and it has 
been added to the output if appropriate 
Sutherland-Hodgman Clipping 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
18 
• Edge from s to p takes one of four cases: 
(Purple line can be a line or a plane) 
Sutherland-Hodgman Clipping 
inside outside 
s 
p 
p output 
inside outside 
s 
p 
no output 
inside outside 
s 
p 
i output 
inside outside 
s p 
i output 
p output 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
19 
• Four cases: 
– s inside plane and p inside plane 
• Add p to output 
• Note: s has already been added 
– s inside plane and p outside plane 
• Find intersection point i 
• Add i to output 
– s outside plane and p outside plane 
• Add nothing 
– s outside plane and p inside plane 
• Find intersection point i 
• Add i to output, followed by p 
Sutherland-Hodgman Clipping 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
GIẢI THUẬT ĐƯỜNG BIÊN 
2 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
21 
• Giải_thuật_đường_biên ( x, y ) 
Color : biến mầu 
Begin 
Color = Readpixel ( x, y ); 
If ( Color = mầu tô ) or ( Color = mầu đường biên ) 
Kết thúc vì chạm biên 
hoặc chạm phần đã tô 
Else 
Putcolor(x,y, mauto) 
Giải_thuật_đường_biên ( x+1, y ); 
Giải_thuật_đường_biên ( x-1, y ); 
Giải_thuật_đường_biên ( x, y+1 ); 
Giải_thuật_đường_biên ( x, y-1 ); 
// Thực hiện lại giải thuật với các điểm lân cận 
End. 
Giải thuật đường biên (Boundary – File algorithm) 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
22 
• Ý tưởng 
– Vẽ các cạnh theo chiều dọc 
– Tô các đường nằm bên trong 
miền theo mỗi đường ngang 
– Nội suy xuống các cạnh ở dưới 
– Tại mỗi đường ngang, nội suy 
màu sắc của cạnh theo các 
đường bên trong miền 
Edge Walking 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
23 
• Giải thuật đường quét sử dụng gắn kết cạnh và các 
tính toán số nguyên tăng dần cho hiệu quả cao nhất 
• Tạo bảng edge table (ET) tập của các cạnh đa giác 
theo thứ tự giá trị ymin của chúng 
• Tạo bảng active edge table (AET) tập các cạnh giao 
vớI đoạn thẳng quét scan-line 
• Trong tiến trình quét các cạnh sẽ chuyển từ ET ra 
AET. 
• Các cạnh sẽ ở trong AET cho đến khi giá trị ymax của 
cạnh đạt tới = scanline 
• Lúc nay cạnh sẽ bị loại ra khỏi AET. 
Giải thuật đường quét 
scan-line algorithm 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Edge Table (ET) 
24 
Note: line (8,6) (13,6) has been deleted according to the scan rules 
ymax xmin 
numerator 
denominator 
scan-line 
(0,0) 
(15,15) 
5
31 
m
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Active Edge Table (AET) 
25 
AET = 
ymax current x denominator current numerator 
round up 
round down 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Active Edge Table (AET) 
26 
ymax current x denominator 
AET = 
current numerator 
round up 
round down 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
SCAN-LINE ALGORITHM 
y = y of first non empty entry in ET 
AET = null 
repeat 
 move all ET entries in slot y to AET 
 sort AET entries according to xmin 
 fill spans using pairs of AET entries 
 for all AET members 
 if ymax = y then remove from AET 
 y = y+1 
 for all AET members 
 update numerator 
 if numerator>denominator 
 numerator=numerator-
denominator 
 x = x+1 
until AET and ET empty 
27 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
GIẢI THUẬT KHỬ RĂNG CƯA 
3 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
29 
• Aliasing: signal processing term 
with very specific meaning 
• Aliasing: computer graphics term 
for any unwanted visual artifact 
• Antialiasing: computer graphics 
term for avoiding unwanted 
artifacts 
Hiệu ứng răng cưa 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
30 
• Rời rạc hóa: Bằng cách lấy mẫu theo chu kỳ 
nhất định 
• Ví dụ với đường sau đây 
Xử lý tín hiệu 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
31 
• Lấy mẫu 
Xử lý tín hiệu 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
32 
• Kết quả thu được 
Xử lý tín hiệu 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
33 
• Kết nối các giá trị thu được 
Xử lý tín hiệu 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
34 
• Một số đoạn bị gãy khúc 
Xử lý tín hiệu 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
35 
• Một số đoạn bị thất thoát dữ liệu 
Xử lý tín hiệu 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
36 
• Méo thông tin trong quá trình lấy mẫu tần số 
thấp 
• Một số trường hợp bị méo thông tin với hiệu ứng 
bậc thang – staircase effect 
• Việc làm giảm hiệu ứng méo thông tin bằng 
phương pháp bù trừ 
Antialiasing 
sampling frequency 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
37 
1. Cố định tín hiệu bằng phương pháp lọc-prefiltering: 
– Giảm độ rộng dải tần tín hiệu bỏi bộ lọc thấp hơn 
trước khi lấy mẫu. 
– Chất lượng cao nhất nhưng không thực tiễn 
2. Cố định mẫu bằng siêu mẫu supersampling: 
– Dùng nhiều mẫu hơn để tăng tần số 
– Đơn giản và được sử dụng rộng rãi 
3. Cố định mẫu bằng phương pháp mẫu bất kỳ 
– Mẫu ngẫu nhiên nhưng không đồng nhất 
– Tương đối đơn giản, thường được kết hợp với phương 
pháp siêu mẫu 
PHƯƠNG PHÁP KHỬ HIỆU ỨNG 
RĂNG CƯA 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
38 
PHƯƠNG PHÁP SIÊU MẪU 
Antialiasing by 
supersampling 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
39 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
VÍ DỤ 
40 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
41 
• Grid : The simplest algorithm. The pixel is split in several sub-
pixels, and a sample is taken from the center of each. It is fast 
and easy to implement, although due to the regular nature of 
sampling, aliasing can still occur if a low number of sub-pixels is 
used. 
• Random: Also known as stochastic sampling, it avoids the 
regularity of grid supersampling. However, due to the irregularity 
of the pattern, samples end up being unnecessary in some areas 
of the pixel and lacking in others. 
• Poisson disc: Again an algorithm that places the samples 
randomly, but then checks that any two are not too close. The 
end result is even but random distribution of samples. 
Unfortunately, the computational time required for this 
algorithm is too great to justify its use in real-time rendering, 
unless the sampling itself is computationally expensive 
compared to the positioning the sample points or the sample 
points are not repositioned for every single pixel. 
Supersampling patterns 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
42 
• Jittered: A modification of the grid algorithm to 
approximate the Poisson disc. A pixel is split into 
several sub-pixels, but a sample is not taken from 
the center of each, but from a random point within 
the sub-pixel. Congregation can still occur, but to a 
lesser degree. 
• Rotated grid: A 2×2 grid layout is used but the 
sample pattern is rotated to avoid samples aligning 
on the horizontal or vertical axis greatly improving 
antialiasing quality for the most commonly 
encountered cases. For an optimal pattern, the 
rotation angle is arctan(1/2) (about 26.6 degrees) 
and the square is stretched by a factor of √5/2 
Supersampling patterns 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
VÍ DỤ 
43 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
VÍ DỤ 
44 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
VÍ DỤ 
45