Khoa CNTT-DDHBK Hà nội
Email: hunglt@it-hut.edu.vn
0913030731
1
1
Các giảithuậtcơsở
Le Tan Hung
hunglt@it-hut.edu.vn
0913030731
Bài 3
2
Nội dung
zCác giảithuậtxéntỉa - Clipping
zCác thuật toán tô miềnkín
zPhép xửlý Antialiasing
3
Xén tỉa - Clipping
zKhá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ị
zTiế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ị
zClipping điểm
xmin ≤x ≤xmax
ymin ≤y ≤ymax
xmin xmax
ymax
ymin
4
Clipping đoạnthẳng
zTiế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
zLý do:
zKhông kiểm tra mọi điểm trên đoạn thẳng
zHầ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ỏ
zRất ít các đợn thẳng cắt cửa sổ hiển thị
5
Giảithuật Cohen Sutherland Outcode
zGiả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ị
zMỗi điểm đầu cuối được gán mã
code phụ thuộc vào vị trí trong
mặt phẳng mã
zp.code = 0000
zIf p.x <= xmin >> P.code or 0001
zIf p.y <= ymin >> P.code or 0100
zIf p.x >= xmax >> P.code or 0010
zIf p.y >= ymax >> P.code or 1000
6
zIf P1.code OR P2.code == 0000
–Chấp nhận toàn đoạn thẳng
zIf P1.code AND P2.code != 0000
–Loại
zVớ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
zx = x1+ (x2-x
1)u = x1+ uDx
zy = y1+ (y2-y
1)u = y1+ uDy
zxmin ≤x1+ Dx.u ≤xmax ⇔x ∈[xm, xM]
zymin ≤y1+ Dy.u ≤ymax ⇔y ∈[ym, yM]
zPk 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
zNếuPk= 0 : điềuđótương đương vớiviệcđoạnthẳng
đang xét song song vớicạnh thứkcủahìnhchữnhật
clipping.
za)Nếuqk< 0 ⇒Đường thẳng nằm ngoài cửasổ(hệbất
phương trình trên vô nghiệm)
zb)Nếuqk>= 0 thì đoạnthẳng nằm trong hoặcnằmtrên
cạnh củacửasổclipping.
zHệbấtphương trình luôn thoảmãn.
9
zNếuPk≠0 : đoạnthẳng đang xét sẽcắtcạnh k tương ứng
củacửasổclipping tạivịtrí trên đoạnthẳng uk = qk/Pk.
–Pk < 0 đoạnthẳng có dạng đitừngoài vào trong
zbấtphương trình sẽcó dạng u ≥qk/Pk Ùu≥uk.
–Pk > 0
zu≥uk sẽthuộccửasổhiểnthị.
zbấtphương trình sẽcó dạng u ≤qk/Pk
zu≤uk vớiuk= qk/Pk là giao củađoạnthẳng với
cạnh k củacửasổclipping
zđoạnthẳng có dạng đitừtrong ra ngoài so vớicạnh
k.10
zPk < 0 và uk < 0
–cạnh k củacửasổclipping cắtđoạnthẳng tạiphầnmởrộng
nằm ngoài đoạnthẳng.
–uk ≤u< 0 thoảmãn bấtphương trình sẽkhông nằmtrênđoạn
thẳng cầnxét.
–=> uk sẽnhậnlà0 khi uk<0
zPk > 0 và uk > 1
–=> uk tương ứng sẽnhậngiátrị1.
zđiểmnằm trong cửasổclipping sẽcó dạng nhưsau:
–U1≤u≤U2
11
{}
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
⎭
⎬
⎫
⎩
⎨
⎧<=∪= 0,:0max
1k
k
k
kk P
P
q
uuU
{}
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
⎭
⎬
⎫
⎩
⎨
⎧>=∪= 0,:1min
2k
k
k
kk P
P
q
uuU
12
Sutherland-Hodgman Clipping
zBasic 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
zInput/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)
zNote: this is exactly what we expect from the
clipping operation against each edge
14
Sutherland-Hodgman Clipping
zSutherland-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
zEdge from sto ptakes 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
sp
i output
inside outside
s
p
i output
p output
16
Sutherland-Hodgman Clipping
zFour cases:
–sinside plane and pinside plane
zAdd pto output
zNote: shas already been added
–sinside plane and poutside plane
zFind intersection point i
zAdd ito output
–soutside plane and poutside plane
zAdd nothing
–soutside plane and pinside plane
zFind intersection point i
zAdd ito output, followed by p
17
GiảithuậtCyrus-Beck
Liang Barsky
zGiả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
zVấ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
zGiả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ị
zNicholl-Lee-Nicholl reducing redundant boundary
clipping by identifying edge and corner regions
18
3-D Clipping
zBefore actually drawing on the screen, we have
to clip (Why?)
zCan 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ảithuậtđường biên (Boundary - File
Algorithm)
zGiải_thuật_đường_biên ( x, y )
Color : biếnmầu
Begin
Color = Readpixel ( x, y );
If ( Color = mầutô) or ( Color = mầuđường biên )
Kếtthúcvìchạmbiên
hoặcchạmphầ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ựchiệnlạigiảithuậtvớicácđiểmlâncận
End.
20
Edge Walking
zBasic idea:
–Draw edges vertically
–Fill in horizontal spans for each scanline
–Interpolate colors down edges
–At each scanline, interpolate
edge colors across span
21
Edge Walking: Notes
zOrder vertices in x and y
–3 cases: break left, break right, no break
zWalk down left and right edges
–Fill each span
–Until breakpoint or bottom vertex is reached
zAdvantage: can be made very fast
zDisadvantages:
–Lots of finicky special cases
–Tough to get right
–Need to pay attention to fractional offsets
22
Edge Walking: Notes
zFractional offsets:
zBe careful when interpolating color values!
zAlso: beware gaps between adjacent edges
23
Giảithuậtđường quét
Scan-Line Algorithm
zThe scan-line algorithm uses edge-coherence and
incremental integer calculations for maximum efficiency:
–Tạobảng edge table (ET) tậpcủacáccạnh đa giác theo thứtự
giá trịymin của chúng
–Tạobảng active edge table (AET) tậpcáccạnh giao vớIđoạn
thẳng quét scan-line
zTrong tiến trình quét các cạnh sẽchuyểntừET ra AET.
zCác cạnh sẽở trong AET cho đến khi giá trịymax của
cạnh đạttới = scanline
zLúc nay cạnh sẽbịloạirakhỏiAET.
24
Edge Table (ET)
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
Khoa CNTT-DDHBK Hà nội
Email: hunglt@it-hut.edu.vn
0913030731
5
25
Giảithuật dòng quét-Scanline cho việctômầu vùng
AET =
yma
x
current x denominator current numerator
round up
round down
26
Active Edge Table (AET)
ymax current x denominator
AET =
current numerator
round up
round down
27
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
28
Rasterizing Triangles
zInteractive graphics hardware commonly uses
edge walking or edge equation techniques for
rasterizing triangles
zTwo techniques we won’t talk about much:
–Recursive subdivision of primitive into micropolygons
(REYES, Renderman)
–Recursive subdivision of screen (Warnock)
29
Recursive Triangle Subdivision
30
Edge Equations
zAn edge equation is simply the equation of the
line containing that edge
–Q: What is the equation of a 2D line?
–A: Ax + By + C = 0
–Q: Given a point (x,y), what does plugging x& yinto
this equation tell us?
–A: Whether the point is:
zOn the line: Ax + By + C = 0
z“Above” the line: Ax + By + C > 0
z“Below” the line: Ax + By + C < 0