Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731
Nội dung
Các giải thuật cơ sở
(cid:122) Các giải thuật xén tỉa - Clipping (cid:122) Các thuật toán tô miền kín (cid:122) Phép xử lý Antialiasing
Le Tan Hung hunglt@it-hut.edu.vn 0913030731
Bài 3
2 1
Xén tỉa - Clipping
Clipping đoạn thẳng
(cid:122) Khái niệm
(cid:122) 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
xmin
xmax
(cid:122) 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ị
ymax
(cid:122) Clipping điểm
(cid:122) Lý do: (cid:122) Không kiểm tra mọi điểm trên đoạn thẳng (cid:122) Hầu hết các đoạn thẳng với 1 màn hình hiển thị
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ị
đều được chấp nhận hoặc loại bỏ
(cid:122) Rất ít các đợn thẳng cắt cửa sổ hiển thị
ymin
xmin ≤ x ≤ xmax ymin ≤ y ≤ ymax
3 4
Giải thuật Cohen Sutherland Outcode
(cid:122) Giải thuật Cohen-Sutherland
(cid:122) If P1.code OR P2.code == 0000 – Chấp nhận toàn đoạn thẳng (cid:122) If P1.code AND P2.code != 0000
– Loại
(cid:122) 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ị
(cid:122) 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ã
(cid:122) p.code = 0000 (cid:122) If p.x <= xmin >> P.code or 0001 (cid:122) If p.y <= ymin >> P.code or 0100 (cid:122) If p.x >= xmax >> P.code or 0010 (cid:122) If p.y >= ymax >> P.code or 1000
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ị
1
5 6
Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731
Liabarsky
(cid:122) 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.
(cid:122) x = x1 + (x2 - x1)u = x1 + uDx (cid:122) y = y1 + (y2 - y1)u = y1 + uDy (cid:122) xmin ≤ x1 + Dx.u ≤ xmax ⇔ x ∈ [xm, xM] (cid:122) ymin ≤ y1 + Dy.u ≤ ymax ⇔ y ∈ [ym, yM]
(cid:122) 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)
(cid:122) Pk u ≤ qk
k = 1, 2, 3, 4
(cid:122) 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.
P
Dx
−=
x
=
−
1
(cid:122) Hệ bất phương trình luôn thoả mãn.
P
Dx
=
x 1 x
=
−
2
m x 1
P
Dy
−=
y
=
M −
3
P
Dy
=
y 1 y
=
−
4
q 1 q 2 q 3 q 4
M
m y 1
⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩
⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩
(cid:122) 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
7 8
(cid:122) 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
– uk ≤ u< 0 thoả mãn bất phương trình sẽ không nằm trên đoạn
nằm ngoài đoạn thẳng.
(cid:122) bất phương trình sẽ có dạng u ≥ qk/Pk (cid:217) u ≥ uk.
– => uk sẽ nhận là 0 khi uk<0
– Pk > 0
(cid:122) Pk > 0 và uk > 1
– => uk tương ứng sẽ nhận giá trị 1.
(cid:122) điểm nằm trong cửa sổ clipping sẽ có dạng như sau:
(cid:122) u ≥ uk sẽ thuộc cửa sổ hiển thị. (cid:122) bất phương trình sẽ có dạng u ≤ qk/Pk (cid:122) u ≤ uk với uk = qk/Pk là giao của đoạn thẳng với
– U1 ≤ u ≤ U2
cạnh k của cửa sổ clipping
(cid:122) đoạn thẳng có dạng đi từ trong ra ngoài so với cạnh
k.
thẳng cần xét.
10 9
Sutherland-Hodgman Clipping
(cid:122) 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
:
,
0
U
u
u
=
∪
=
>
k
k
2
P k
q k P k
max
:
,
0
U
u
=
∪
=
<
{ } 0
1
k
k
P k
q k P k
⎧ ⎨ ⎩ ⎧ u ⎨ ⎩
⎛ { } ⎜ 1min ⎜ ⎝ ⎛ ⎜ ⎜ ⎝
⎞ ⎫ ⎟ ⎬ ⎟ ⎭ ⎠ ⎞ ⎫ ⎟ ⎬ ⎟ ⎭ ⎠
2
12 11
Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731
Sutherland-Hodgman Clipping
Sutherland-Hodgman Clipping
(cid:122) Input/output for algorithm:
– Input: list of polygon vertices in order – Output: list of clipped poygon vertices consisting of
(cid:122) 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
old vertices (maybe) and new vertices (maybe) (cid:122) Note: this is exactly what we expect from the
clipping operation against each edge
13 14
Sutherland-Hodgman Clipping
Sutherland-Hodgman Clipping
(cid:122) Four cases:
(cid:122) Edge from s to p takes one of four cases:
– s inside plane and p inside plane
p
(cid:122) Add p to output (cid:122) Note: s has already been added – s inside plane and p outside plane
s
(cid:122) Find intersection point i (cid:122) Add i to output
– s outside plane and p outside plane
(cid:122) Add nothing
s
p
p
s
– s outside plane and p inside plane
p output
i output
no output
(cid:122) Find intersection point i (cid:122) Add i to output, followed by p
i output p output
(Purple line can be a line or a plane) inside outside inside outside inside inside outside p outside s
15 16
3-D Clipping
Giải thuật Cyrus-Beck Liang Barsky
(cid:122) Giải Cohen-Sutherland yêu cầu cửa sổ là hình chữ
(cid:122) Before actually drawing on the screen, we have
nhật, các cạnh là cạnh của màn hình
to clip (Why?)
(cid:122) 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
(cid:122) Can we transform to screen coordinates first,
(cid:122) 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ị
then clip in 2D? – Correctness: shouldn’t draw objects behind viewer
(cid:122) Nicholl-Lee-Nicholl reducing redundant boundary clipping by identifying edge and corner regions
(what will an object with negative z coordinates do in our perspective matrix?) (draw it…)
3
17 18
Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731
Edge Walking
Giải thuật đường biên (Boundary - File Algorithm)
(cid:122) Basic idea:
– Draw edges vertically – Fill in horizontal spans for each scanline – Interpolate colors down edges – At each scanline, interpolate
edge colors across span
(cid:122) 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.
19 20
Edge Walking: Notes
Edge Walking: Notes
(cid:122) Order vertices in x and y
(cid:122) Fractional offsets:
– 3 cases: break left, break right, no break
(cid:122) Walk down left and right edges
– Fill each span – Until breakpoint or bottom vertex is reached
(cid:122) Advantage: can be made very fast (cid:122) Disadvantages:
– Lots of finicky special cases – Tough to get right – Need to pay attention to fractional offsets
(cid:122) Be careful when interpolating color values! (cid:122) Also: beware gaps between adjacent edges
21 22
Giải thuật đường quét Scan-Line Algorithm
Edge Table (ET)
(0,0)
(cid:122) The scan-line algorithm uses edge-coherence and
incremental integer calculations for maximum efficiency: – Tạo bảng edge table (ET) tập của các cạnh đa giác theo thứ tự
– Tạo bảng active edge table (AET) tập các cạnh giao vớI đoạn
giá trị ymin của chúng
numerator
1 =⇒ m
3 − 5
denominator
ymax
xmin
(cid:122) Trong tiến trình quét các cạnh sẽ chuyển từ ET ra AET. (cid:122) Các cạnh sẽ ở trong AET cho đến khi giá trị ymax của
cạnh đạt tới = scanline
(cid:122) Lúc nay cạnh sẽ bị loại ra khỏi AET.
(15,15)
scan-line Note: line (8,6) → (13,6) has been deleted according to the scan rules
thẳng quét scan-line
4
23 24
Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731
Active Edge Table (AET)
Giải thuật dòng quét-Scanline cho việc tô mầu vùng
round down
round down
round up
round up
AET =
AET =
current numerator
ymax
current x denominator
current x denominator current numerator
yma x
25 26
Scan-Line Algorithm
Rasterizing Triangles
y = y of first non empty entry in ET AET = null repeat
(cid:122) Interactive graphics hardware commonly uses edge walking or edge equation techniques for rasterizing triangles
(cid:122) Two techniques we won’t talk about much:
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
– Recursive subdivision of primitive into micropolygons
if ymax = y then remove from AET
(REYES, Renderman)
y = y+1 for all AET members
– Recursive subdivision of screen (Warnock)
update numerator if numerator>denominator
numerator=numerator-denominator x = x+1
until AET and ET empty
28 27
Recursive Triangle Subdivision
Edge Equations
(cid:122) An 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 & y into
this equation tell us? – A: Whether the point is:
(cid:122) On the line: Ax + By + C = 0 (cid:122) “Above” the line: Ax + By + C > 0 (cid:122) “Below” the line: Ax + By + C < 0
5
30 29
Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731
Edge Equations
Edge Equations
(cid:122) So…simply turn on those pixels for which all
(cid:122) Edge equations thus define two half-spaces: (cid:122) And a triangle can be defined as the intersection of
edge equations evaluate to > 0:
three positive half-spaces:
A
2x + B
A
2y + C
2x + B
2< 0
2y + C
-
2> 0
< 0 > 0 y + C3 y + C3 x + B3 x + B3
A3
A3
- + ++ -
A 1x + B 1y + C 1 > 0 A 1x + B 1y + C 1 < 0
31 32
Using Edge Equations
Using Edge Equations
(cid:122) An aside: How do you suppose edge equations
(cid:122) Which pixels: compute min,max bounding box
are implemented in hardware?
(cid:122) How would you implement an edge-equation
rasterizer in software? – Which pixels do you consider? – How do you compute the edge equations? – How do you orient them correctly?
(cid:122) Edge equations: compute from vertices (cid:122) Orientation: ensure area is positive (why?)
33 34
Signal Processing
Hiệu ứng răng cưa Aliasing - Antialiasing
(cid:122) Aliasing: signal processing term
(cid:122) Raster display: regular sampling of a continuous
with very specific meaning
function (Really?)
(cid:122) Think about sampling a 1-D function:
(cid:122) Aliasing: computer graphics term for any unwanted visual artifact (cid:122) Antialiasing: computer graphics term for avoiding unwanted artifacts
6
35 36
Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731
Signal Processing
Signal Processing
(cid:122) Sampling a 1-D function:
(cid:122) Sampling a 1-D function:
37 38
Signal Processing
Signal Processing
(cid:122) Sampling a 1-D function: what do you notice?
(cid:122) Sampling a 1-D function: – What do you notice?
– Jagged, not smooth
39 40
Signal Processing
Antialiasing
(cid:122) Méo thông tin trong quá trình lấy mẫu tần số
(cid:122) Sampling a 1-D function: what do you notice?
thấp
– Jagged, not smooth – Loses information!
sampling frequency
(cid:122) In raster images – leads to jagged edges with
hiệu ứng bậc thang – staircase effect
(cid:122) Việc làm giảm hiệu ứng méo thông tin bằng
phương pháp bù trừ
7
41 42
Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731
Prefiltering – Lọc
Phương pháp khử hiệu ứng răng cưa Antialiasing Methods
(cid:122) Eliminate high frequencies before sampling
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ấphơn trước khi
lấy mẫu.
(Foley & van Dam p. 630) – Convert I(x) to F(u) – Apply a low-pass filter (e.g., multiply F(u) by a box
function)
– Then sample. Result: no aliasing!
(cid:122) Problem: most rendering algorithms generate
sampled function directly – e.g., Z-buffer, ray tracing
Highest quality method, but often impractical. 2. Cố định mẫu bằng siêu mẫu supersampling: Use more samples to raise the Nyquist frequency. Simple and widely used. 3. Cố định mẫu bằng phương pháp mẫu bất kỳ - stochastic sampling: Sample randomly, not uniformly. Relatively simple, usually used in combination with
supersampling.
43 44
Antialiasing in the Continuous Domain
Phương pháp siêu mẫu
(cid:122) Problem with prefiltering:
(cid:122) Supersampling cons
– Sampling and image generation inextricably linked in
– Doesn’t eliminate aliasing, just shifts the Nyquist limit
most renderers
higher
(cid:122) Can’t fix some scenes (e.g., checkerboard)
(cid:122) Z-buffer algorithm (cid:122) Ray tracing
– Tăng bộ nhớ cho việc lưu trữ
– Why?
(cid:122) Sự cuốn méo với các miền liên tục do hiệu ứng
xấp xỉ của phương pháp tiền lọc
(cid:122) Supersampling pros – Relatively easy – Often works all right in practice – Can be added to a standard renderer
Antialiasing by supersampling
45 46
8
47 48
Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731
anti aliasing (1)
Antialiasing (2)
49 50
The A-Buffer
The A-Buffer
(cid:122) Advantages:
(cid:122) Idea: approximate continuous filtering by
– Incorporating into scanline renderer reduces storage costs
subpixel sampling
– Processing per pixel depends only on number of visible
dramatically
(cid:122) Summing areas now becomes simple
– Can be implemented efficiently using bitwise logical ops on
fragments
– Still basically a supersampling algorithm – Not a hardware-friendly algorithm
(cid:122) Lists of potentially visible polygons can
grow without limit
(cid:122) Work per-pixel non-deterministic
subpixel masks (cid:122) Disadvantages
51 52
Recap: Antialiasing Strategies
Antialiasing Strategies
(cid:122) Supersampling: sample at higher resolution, then
(cid:122) A-Buffer: approximate prefiltering of continuous
filter down – Pros:
signal by sampling – Pros:
(cid:122) Integrating with scan-line renderer keeps storage costs low (cid:122) Can be efficiently implemented with clever bitwise operations
(cid:122) Conceptually simple (cid:122) Easy to retrofit existing renderers (cid:122) Works well most of the time
– Cons:
– Cons:
(cid:122) Still basically a supersampling approach (cid:122) Doesn’t integrate with ray-tracing
(cid:122) High storage costs (cid:122) Doesn’t eliminate aliasing, just shifts Nyquist limit upwards
9
53 54
Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731
Stochastic Sampling
Stochastic Sampling
(cid:122) An intuitive argument:
(cid:122) Idea: randomizing distribution of samples
– In stochastic sampling, every region of the image has a finite
scatters aliases into noise
(cid:122) Problem: what type of random distribution
– Thus small features that fall between uniform sample points tend
to adopt?
probability of being sampled
(cid:122) Reason: type of randomness used affects
– Ray tracing:
(cid:122) It is just as easy to fire a ray one direction as another
spectral characteristics of noise into which high frequencies are converted
– Z-buffer: hard, but possible
(cid:122) Problem: given a pixel, how to distribute points
(cid:122) Notable example: REYES system (?) (cid:122) Using image jittering is easier (more later)
(samples) within it?
– A-buffer: nope
(cid:122) Totally built around square pixel filter and primitive-to-sample
coherence
to be detected by non-uniform samples (cid:122) Integrating with different renderers:
10
55 56
