Bài giảng Đồ họa và hiện thực ảo - Lesson 3: Các giải thuật cơ sở

Khoa CNTT-DDHBK Hà nội
Email: hunglt@it-hut.edu.vn
0913030731
1
1
Các giải thuật cơ sở
Le Tan Hung
hunglt@it-hut.edu.vn
0913030731Bài 3
2
Nội dung 
z Các giải thuật xén tỉa - Clipping
z Các thuật toán tô miền kín
z Phép xử lý Antialiasing
3
Xén tỉa - Clipping
z 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ị
z 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ị
z Clipping điểm
xmin ≤ x ≤ xmax 
ymin ≤ y ≤ ymax
xmin xmax
ymax
ymin
4
Clipping đoạn thẳng
z 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
z Lý do:
z Không kiểm tra mọi điểm trên đoạn thẳng
z 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ỏ
z Rất ít các đợn thẳng cắt cửa sổ hiển thị
5
Giải thuật Cohen Sutherland Outcode
z 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ị
z 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ã
z p.code = 0000
z If p.x > P.code or 0001
z If p.y > P.code or 0100
z If p.x >= xmax >> P.code or 0010
z If p.y >= ymax >> P.code or 1000
6
z If P1.code OR P2.code == 0000 
– Chấp nhận toàn đoạn thẳng
z If P1.code AND P2.code != 0000 
– Loại 
z 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ị
Khoa CNTT-DDHBK Hà nội
Email: hunglt@it-hut.edu.vn
0913030731
2
7
Liabarsky
z x = x1 + (x2 - x1)u = x1 + uDx
z y = y1 + (y2 - y1)u = y1 + uDy
z xmin ≤ x1 + Dx.u ≤ xmax ⇔ x ∈ [xm, xM]
z ymin ≤ y1 + Dy.u ≤ ymax ⇔ y ∈ [ym, yM]
z Pk u ≤ qk k = 1, 2, 3, 4
⎪⎪⎩
⎪⎪⎨
⎧
=
−=
=
−=
DyP
DyP
DxP
DxP
4
3
2
1
⎪⎪⎩
⎪⎪⎨
⎧
−=
−=
−=
−=
14
13
12
11
yyq
yyq
xxq
xxq
M
m
M
m
8
z 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.
z 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)
z 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.
z Hệ bất phương trình luôn thoả mãn.
9
z 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
z bất phương trình sẽ có dạng u ≥ qk/Pk Ù u ≥ uk. 
– Pk > 0 
z u ≥ uk sẽ thuộc cửa sổ hiển thị.
z bất phương trình sẽ có dạng u ≤ qk/Pk
z 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
z đoạn thẳng có dạng đi từ trong ra ngoài so với cạnh
k.
10
z 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 
z Pk > 0 và uk > 1
– => uk tương ứng sẽ nhận giá trị 1. 
z điểm nằm trong cửa sổ clipping sẽ có dạng như sau:
– U1 ≤ u ≤ U2
11
{ } ⎟⎟⎠
⎞
⎜⎜⎝
⎛
⎭⎬
⎫
⎩⎨
⎧ <=∪= 0,:0max1 k
k
k
kk PP
quuU
{ } ⎟⎟⎠
⎞
⎜⎜⎝
⎛
⎭⎬
⎫
⎩⎨
⎧ >=∪= 0,:1min2 k
k
k
kk PP
quuU
12
Sutherland-Hodgman Clipping
z 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
Khoa CNTT-DDHBK Hà nội
Email: hunglt@it-hut.edu.vn
0913030731
3
13
Sutherland-Hodgman Clipping
z 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)
z Note: this is exactly what we expect from the 
clipping operation against each edge
14
Sutherland-Hodgman Clipping
z 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
15
Sutherland-Hodgman Clipping
z Edge from s to p takes one of four cases:
(Purple line can be a line or a plane)
inside outside
s
p
p output
inside outside
s
p
no output
inside outside
s
p
i output
inside outside
sp
i output
p output
16
Sutherland-Hodgman Clipping
z Four cases:
– s inside plane and p inside plane
z Add p to output
z Note: s has already been added
– s inside plane and p outside plane
z Find intersection point i
z Add i to output
– s outside plane and p outside plane
z Add nothing
– s outside plane and p inside plane
z Find intersection point i
z Add i to output, followed by p
17
Giải thuật Cyrus-Beck
Liang Barsky
z 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
z 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
z 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ị
z Nicholl-Lee-Nicholl reducing redundant boundary 
clipping by identifying edge and corner regions
18
3-D Clipping
z Before actually drawing on the screen, we have 
to clip (Why?)
z Can we transform to screen coordinates first, 
then clip in 2D?
– Correctness: shouldn’t draw objects behind viewer 
(what will an object with negative z coordinates do in 
our perspective matrix?) (draw it)
Khoa CNTT-DDHBK Hà nội
Email: hunglt@it-hut.edu.vn
0913030731
4
19
Giải thuật đường biên (Boundary - File 
Algorithm)
z 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. 
20
Edge Walking
z Basic idea: 
– Draw edges vertically
– Fill