Khoa CNTT-DDHBK Hà nội
Email: [email protected]
0913030731
1
(c) SE/FIT/HUT 2002
1
B
ài 3:
Các giảithuậtcơ sở
Le Tan Hung
[email protected]
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

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

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

−=
=
−=
DyP
DyP
DxP
DxP
4
3
2
1
⎪
⎪
⎩
⎪
⎪
⎨
⎧
−=
−=
−=
−=
14
13
12
11
yyq
yyq
xxq
xxq

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,:1min
2 k
k
k
kk
P
P
q
uuU
Khoa CNTT-DDHBK Hà nội
Email: [email protected]
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

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ô


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: [email protected]
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.


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: [email protected]
0913030731
5
(c) SE/FIT/HUT 2002
25
Antialiasing (2)