Khoa CNTT-DDHBK Hà nội
Email:
0913030731
1
(c) SE/FIT/HUT 2002
1
B
ài 3:
Các giảithuậtcơ sở
Le Tan Hung

0913030731
(c) SE/FIT/HUT 2002
2
Nội dung

Các giảithuậtxéntỉa - Clipping

Các thuậttoántômiềnkín

Phép tô mầu

Phép xử lý Antialiasing
(c) SE/FIT/HUT 2002
3
Xén tỉa - Clipping

A fundamental task in graphics is to
keep those parts of an object that lie
outside a selected view from being
drawn


Clipping is the removal of all objects
or part of objects in a modelled scene
that are outside the real-world
window.

Việcloạitừng điểm ảnh của đốitượng
thường chậmnhấtlàkhiđốitượng mà
phầnlớnnằm ngoài cửasổ hiểnthị.

More practical techniques are
necessary to speed up the task

Khái niệm
Xén tỉalàtiếntrìnhxác
định các điểmcủa1 đối
tượng nằm trong hay
ngoài cửasổ hiểnthị

Clipping điểm

xmin ≤ x ≤ xmax
ymin ≤ y ≤ ymax
(c) SE/FIT/HUT 2002
4
Clipping đoạnthẳng

Lines are defined by their endpoints, so it should be
possible just to examine these (in a similar way to
points) and determine whether or not to clip without

considering every pixel on the line

We often have windows that are either very large,
i.e. nearly the whole scene fits inside, or very small,
i.e. most of the scene lies inside the window

Hence, most lines may be either trivially accepted or
rejected
(c) SE/FIT/HUT 2002
5
Giảithuật
Cohen Sutherland
Outcode

The Cohen-Sutherland line-clipping algorithm is particularly
fast for “trivial” cases, i.e. lines completely inside or outside
the window.

Non-trivial lines, i.e. ones that cross a boundary of the
window, are clipped by computing the coordinates of the new
boundary endpoint of the line where it crosses the edge of the
window

Each point on all lines are first assigned an “outcode”
defining their position relative to the clipping rectangle
(c) SE/FIT/HUT 2002
6

NếumãcủaP
1

và P
2
đều = 0000 thì toàn bộđoạnthẳng thuộcphầnhiển
thị.

If P
1
.Mã OR P
2
.Mã == 0000 then “ cảđoạnthẳng thuộccửasổ hiểnthị”

NếumãcủaP
1
và P
2
có cùng mộtvị trí mà ởđó ≠ 0 thì P
1
và P
2
=> cùng
phía

If P
1
.Mã AND P
2
.Mã != 0000 then “ 2 điểmnằmvề 1 phía củacửasổ”
Khoa CNTT-DDHBK Hà nội
Email:
0913030731

2
(c) SE/FIT/HUT 2002
7
Giảithuật Cyrus-Beck
Lyang Barsky

The Cohen-Sutherland algorithm requires the
window to be a rectangle, with edges aligned with
the co-ordinate axes

It is sometimes necessary to clip to any convex
polygonal window, e.g. triangular, hexagonal, or
rotated.

The, and Liang-Barsky line clippers better
optimise the intersection calculations for clipping
to window boundary

Nicholl-Lee-Nicholl reducing redundant boundary
clipping by identifying edge and corner regions
(c) SE/FIT/HUT 2002
8

x = x
1
+ (x
2
-x
1
)u = x

1
+ uDx

y = y
1
+ (y
2
-y
1
)u = y
1
+ uDy

xmin ≤ x
1
+ Dx.u ≤ xmax ⇔ x ∈ [xm, xM]

ymin ≤ y
1
+ Dy.u ≤ ymax ⇔ y ∈ [ym, yM]

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
(c) SE/FIT/HUT 2002
9

Nế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.

a) Nếuqk< 0 ⇒ Đường thẳng nằm ngoài cửasổ (hệ bất
phươngtrìnhtrênvônghiệm)

b)Nếuqk>= 0 thì đoạnthẳng nằm trong hoặcnằmtrêncạnh
củacửasổ clipping.

Hệ bấtphương trình luôn thoả mãn.
(c) SE/FIT/HUT 2002
10

NếuPk≠ 0 : đoạnthẳng đang xét sẽ cắtcạnh k tương ứng của
cử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
• bấtphương trình sẽ có dạng u ≥ qk/Pk Ù u ≥ uk.

Pk > 0
• u ≥ uk sẽ thuộccửasổ hiểnthị.
• bấtphương trình sẽ có dạng u ≤ qk/Pk
• u ≤ uk vớiuk= qk/Pk là giao của đoạnthẳng vớicạnh

kcủacửasổ clipping
• đoạnthẳng có dạng đitừ trong ra ngoài so vớicạnh k.
(c) SE/FIT/HUT 2002
11

Pk < 0 và uk < 0

cạnhkcủ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

Pk > 0 và uk > 1

=> uk tương ứng sẽ nhận giá trị 1.

điểmnằm trong cửasổ clipping sẽ có dạng như sau:

U
1
≤ u ≤ U
2
(c) SE/FIT/HUT 2002
12
{}
⎟
⎟

⎠
⎞
⎜
⎜
⎝
⎛
⎭
⎬
⎫
⎩
⎨
⎧
<=∪= 0,:0max
1 k
k
k
kk
P
P
q
uuU
{}
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛

⎭
⎬
⎫
⎩
⎨
⎧
>=∪= 0,:1min
2 k
k
k
kk
P
P
q
uuU
Khoa CNTT-DDHBK Hà nội
Email:
0913030731
3
(c) SE/FIT/HUT 2002
13
Nicholl-Lee-Nicholl clipping

Some edges are irrelevant to
clipping, particularly if one vertex
lies inside region.

Cases:

x

1
in

x
1
in corner region

x
1
in edge region

For each case, we generate
specialized test regions for x
2
,
which use simple tests (slope, >,
<), and tell which edges to clip
against.
a
a
a
(c) SE/FIT/HUT 2002
14
Nicholl-Lee-Nicholl (2)

Special cases for each endpoint location and slope

Number of cases explodes in 3D, making it
unsuitable
12

3
4
Reject
Top
Top, Right
Top, Bottom
Left
Left, bottom
(c) SE/FIT/HUT 2002
15
Giảithuật đường biên (Boundary - File
Algorithm)

Giả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ết thúc vì chạmbiên
hoặcchạmphần đãtô
Else
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ới các điểmlâncận
End.
(c) SE/FIT/HUT 2002
16
Giảithuật dòng quét-Scanline cho việctô

mầu vùng
AET =
y
ma
x
current x denominator current numerator
round up
round down
(c) SE/FIT/HUT 2002
17
Giảithuậttôvùngkíntheomẫu
(Pattern Filling)

Phương pháp 1

Phương pháp 2
(c) SE/FIT/HUT 2002
18
Hiệu ứng răng cưa
Aliasing

SPATIAL ALIASING, IN PICTURES

moire patterns arise in

image warping & texture mapping

jaggies arise in rendering

TEMPORAL ALIASING, IN AUDIO


when resampling an audio signal at a lower sampling
frequency,

e.g. 50KHz (50,000 samples per second) to 10KHz

TEMPORAL ALIASING, IN FILM/VIDEO

strobing and the “wagon wheel effect”

jaggies in foreground.

jaggies
Khoa CNTT-DDHBK Hà nội
Email:
0913030731
4
(c) SE/FIT/HUT 2002
19
When Does Spatial Aliasing
Occur?

During image synthesis:

when sampling a continuous (geometric) model to create a raster image,

e.g. scan converting a line or polygon.

Sampling: converting a continuous signal to a discrete signal.


During image processing and image synthesis:

when resampling a picture, as in image warping or texture mapping.

Resampling: sampling a discrete signal at a different sampling rate.
Example: “zooming” a picture from nx by ny pixels to snx by sny pixels
s>1: called upsampling or interpolation
can lead to blocky appearance if point sampling is used
s<1: called downsampling or decimation
can lead to moire patterns and jaggies
(c) SE/FIT/HUT 2002
20
Phương pháp khử hiệu ứng răng cưa
Antialiasing Methods
1. Cốđịnh tín hiệubằng phương pháp lọc-prefiltering:
Giảm độ rộng dảitầntínhiệubỏibộ lọcthấphơntrướckhilấy
mẫu.
Highest quality method, but often impractical.
2. Cốđịnh mẫubằng siêu mẫu supersampling:
Use more samples to raise the Nyquist frequency.
Simple and widely used.
3. Cốđịnh mẫubằng phương pháp mẫubấtkỳ
- stochastic sampling:
Sample randomly, not uniformly.
Relatively simple, usually used in combination with
supersampling.
(c) SE/FIT/HUT 2002
21
Antialiasing


Méo thông tin trong quá trình lấymẫutầnsố thấp

In raster images – leads to jagged edges with hiệu
ứng bậc thang – staircase effect

We can reduce effects by antialiasing methods to
compensate for undersampling
sampling frequency
(c) SE/FIT/HUT 2002
22
Antialiasing by
supersampling
(c) SE/FIT/HUT 2002
23
(c) SE/FIT/HUT 2002
24
anti aliasing (1)
Khoa CNTT-DDHBK Hà nội
Email:
0913030731
5
(c) SE/FIT/HUT 2002
25
Antialiasing (2)