Bài giảng Đồ họa hiện thực ảo - Bài 3: Các giải thuật cơ sở - Lê Tấn Hùng

(c) SE/FIT/HUT 2002 1
Bài 3:
Các giải thuật cơ sở
Le Tan Hung
hunglt@it-hut.edu.vn
0913030731
(c) SE/FIT/HUT 2002 2
Nội dung 
„ Các giải thuật xén tỉa - Clipping
„ Các thuật toán tô miền kín
„ Phép tô mầu
„ Phép xử lý Antialiasing
(c) SE/FIT/HUT 2002 3
Xén tỉa - Clipping
„ Nhiệm vụ cơ bản trong đồ họa là giữ các 
phần của đối tượng lựa chọn nằm bên 
ngoài đồ hoạ. 
„ Xén tỉa là việc di chuyển tất cả các đối 
tượng hoặc các phần của đối tượng thuộc 
mô hình ngữ cảnh ra bên ngoài của sổ thế
giới thực
„ Việc loại từng điểm ảnh của đối tượng
thường chậm nhất là khi đối tượng mà
phần lớn nằm ngoài cửa sổ hiển thị.
„ Kỹ thuật thực hành là cần thiết để nâng 
cao tốc độ trong thực hiện nhiệm vụ
„ Định nghĩa
Clipping điểm
„ xmin ≤ x ≤ xmax
ymin ≤ y ≤ ymax
(c) SE/FIT/HUT 2002 4
Clipping đoạn thẳ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ải thuậ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
(c) SE/FIT/HUT 2002 7
Giải thuậ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



=
−=
=
−=
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ế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.
„ a) Nếu qk < 0 ⇒ vô nghiệm)
„ b)Nếu qk >= 0 thì bất phương trình luôn
thoả mãn.
(c) SE/FIT/HUT 2002 10
„ Nếu Pk ≠ 0 : 
„ uk = qk/Pk. 
„ Pk < 0 
• u ≥ qk/Pk Ù u ≥ uk. 
„ Pk > 0 
• u ≥ uk u ≤ qk/Pk
• u ≤ uk với uk = qk/Pk
• đoạn thẳng có dạng đi từ trong ra ngoài so với
cạnh k.
(c) SE/FIT/HUT 2002 11
„ Pk < 0 và uk < 0 
„ 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 
„ Pk > 0 và uk > 1
„ => uk tương ứng sẽ nhận giá trị 1. 
„ điểm nằm trong cửa sổ clipping sẽ có dạng như
sau:
„ U1 ≤ u ≤ U2
(c) SE/FIT/HUT 2002 12
{ } 






 <=∪= 0,:0max1 k
k
k
kk PP
quuU
{ } 






 >=∪= 0,:1min2 k
k
k
kk PP
quuU
(c) SE/FIT/HUT 2002 13
Nicholl-Lee-Nicholl clipping
„ Some edges are irrelevant to 
clipping, particularly if one vertex 
lies inside region.
„ Cases: 
„ x1 in
„ x1 in corner region
„ x1 in edge region
„ For each case, we generate 
specialized test regions for x2, 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 1 2
3
4
Reject
Top
Top, Right
Top, Bottom
Left
Left, bottom
(c) SE/FIT/HUT 2002 15
Giải thuật đường biên (Boundary - File 
Algorithm)
„ 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 
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. 
(c) SE/FIT/HUT 2002 16
Giải thuật dòng quét-Scanline cho việc tô
mầu vùng
AET =
yma
x
current x denominator current numerator
round up
round down
(c) SE/FIT/HUT 2002 17
Giải thuật tô vùng kín theo mẫ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
(c) SE/FIT/HUT 2002 19
Antialiasing
„ Méo thông tin trong quá trình lấy mẫu tần số 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 20
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 21
Phương pháp khử hiệu ứng răng cưa
Antialiasing Methods
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.
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.
(c) SE/FIT/HUT 2002 22
Antialiasing by 
supersampling
(c) SE/FIT/HUT 2002 23
(c) SE/FIT/HUT 2002 24
anti aliasing (1)
(c) SE/FIT/HUT 2002 25
Antialiasing (2)
(c) SE/FIT/HUT 2002 26
Hệ tọa độ thực
(WCS-World Coordinate System)
„Đơn vị trong hệ
thống tọa độ phụ
thuộc vào không
gian và kích thước
của đối tượng được
mô tả, có thể từ A0, 
nm, mm ... đến m, 
km ... 
(c) SE/FIT/HUT 2002 27
Hệ tọa độ thiết bị
(DCS-Device Coordinate System)
ThiÕt bÞ hiÓn thÞ
subselect.me
Vïng täa ®é thiÕt bÞ
VGA=640x480
(c) SE/FIT/HUT 2002 28
Hệ tọa độ chuẩn
(NCS - Normalized Coordinate System)
„ Giải quyết vấn đề khi ứng dụng chạy trên các thiết bị
khác nhau
„ Có kích thước 1x1
Wcs
chuyÓn ®æi 1
NCS Dcs
chuyÓn ®æi 2
(c) SE/FIT/HUT 2002 29
Screen
Windows and Viewports
The World (what you can see, the real 
world)
Screen Window
The World Window (the bit 
we want to capture)
Viewport
(c) SE/FIT/HUT 2002 30
Đặc điểm 
World Window
Example Viewports
•The world window is a rectangle.
•The viewport is a rectangle.
•Both are not necessarily the 
same size or have the same 
aspect ratio.
•Coordinates need to be 
stretched, shrunk and moved to 
make them fit.
(c) SE/FIT/HUT 2002 31
Windows and Viewports
World Window Viewport
(0,0) (0,0)(100,0) (100,0)
This is called 
Mapping
(wxmin,wymin)
(wxmax,wymax)
(vxmin,vymin)
(vxmax,vymax)
(wx,wy) (vx,vy)
(c) SE/FIT/HUT 2002 32
Windows and Viewports
Example
„ Recall from the last lecture:
„ x’ = Ax + B
„ y’ = Cy + D
„ This is exactly how mapping is achieved!!
What are A, B, C & D ??
World Window Viewport
(10,6)
(-10,-6)
400
0
0 600
(c) SE/FIT/HUT 2002 33
Phép chuyển đổi
(c) SE/FIT/HUT 2002 34
Example
World Window Viewport
(10,6)
(-10,-6)
400
0
0 600
A = 600/20 = 30
B = 400/12 = 33.3333
C = 0 – 30 * -10 = 300
D = 0 – 33.3333 * -6 = 200
If this is correct, (-10,-6) 
should map to (0,0) and 
(10,6) -> (600,400)
sx = A * -10 + C = 0
sy = B * -6 + D = 0
sx = A * 10 + C = 600
xy = B * 6 + D = 400
☺
☺
☺
☺
(c) SE/FIT/HUT 2002 35
OpenGL ?
„ Do you need to perform these 
calculations each time you draw 
something with OpenGL??
„ No
„ OpenGL does all the hard work for 
you.
„ But it important that you 
understand what is going on..
(c) SE/FIT/HUT 2002 36
Windows and Viewports
„ Each time you call for a vertex to be drawn (e.g. 
glVertex2f() etc..) the coordinates of the point are 
passed through a set of transformations that map world 
coordinates into viewport coordinates.
„ First set the world window coordinates 
with:
„ Then set the viewport with:
(c) SE/FIT/HUT 2002 37
Windows and Viewports
void myInit(void)
{
glClearColor(1.0,1.0,1.0,0.0); 
glColor3f(0,0,0);
glClear(GL_COLOR_BUFFER_BIT); 
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
//set the viewing coordinates
gluOrtho2D(-10.0, 10.0, -6.0, 6.0);
glViewport(0,0,600,400);
}
glPointSize(10.0);
glBegin(GL_POINTS);
glVertex2i(-10,-6);
glVertex2i(0,0);
glVertex2i(10,6);
glEnd();
*NOTE: Vertex are given in 
World Coordinates and OpenGL 
maps them to the Viewport 
Coordinates.
(c) SE/FIT/HUT 2002 38
„ Say we want to map 
this to a 640x480 
viewport
-0.4 -0.2
0.3
0.4
480
640
(c) SE/FIT/HUT 2002 39
Wx=-.2
Wy=.3
Wxmax=0
Wxmin=-0.4
Wymax=0.4
Wymin=0
Vx= (-.2-(-0.4))*(640-0) + 0 = 320
0-(-0.4)
Vy= (.3-0)*(0-480) + 480 = 120
0-(-0.4)
Vxmax=640
Vxmin=-0.4
Vymax=0
Vymin=480
320
120