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

Bài 3:
Các giảithuậtcơ sở
 Le Tan Hung
 hunglt@it-hut.edu.vn
 0913030731
 (c) SE/FIT/HUT 2002 1
Nội dung 
„ Các giảithuậtxéntỉa - Clipping
„ Các thuật toán tô miềnkín
„ Phép tô mầu
„ Phép xử lý Antialiasing
 (c) SE/FIT/HUT 2002 2
 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ỉalà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 „ Định nghĩa
„ Việcloạitừng điểm ảnh của đốitượng Clipping điểm
 thường chậmnhấtlàkhiđốitượng mà
 „ xmin ≤ x ≤ xmax
 phầnlớnnằm ngoài cửasổ hiểnthị.
 ymin ≤ y ≤ ymax
„ 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ụ
 (c) SE/FIT/HUT 2002 3
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 4
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 5
(c) SE/FIT/HUT 2002 6
 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 7
 P = − Dx
 q = x − x  1
 1 1 m 
  P 2 = Dx
q2 = xM − x1 
 P = − Dy
 q = y − y  3
 3 1 m 
  P 4 = Dy
q4 = yM − y1
 (c) SE/FIT/HUT 2002 8
„ 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 ⇒ vô nghiệm)
„ b)Nếuqk>= 0 thì bấtphương trình luôn
 thoả mãn.
 (c) SE/FIT/HUT 2002 9
„ NếuPk≠ 0 : 
„ uk = qk/Pk. 
 „ Pk < 0 
 • u ≥ qk/Pk Ù u ≥ uk. 
 „ Pk > 0 
 • u ≥ uk u ≤ qk/Pk
 • u ≤ uk vớiuk= qk/Pk
 • đoạnthẳng có dạng đitừ trong ra ngoài so với
 cạnh k.
 (c) SE/FIT/HUT 2002 10
„ Pk < 0 và uk < 0 
 „ uk ≤ u< 0 thoả mãn bấtphương trình sẽ không nằm
 trên đoạnthẳng cầnxét. 
 „ => uk sẽ nhậnlà0 khi uk<0 
„ Pk > 0 và uk > 1
 „ => uk tương ứng sẽ nhậngiátrị 1. 
„ điểmnằm trong cửasổ clipping sẽ có dạng như
 sau:
 „ U1 ≤ u ≤ U2
 (c) SE/FIT/HUT 2002 11
   q 
U = min 1 ∪ u : u = k , P > 0 
 2 {}  k k k 
   Pk 
   q 
U = max 0 ∪ u : u = k , P < 0 
 1 {}  k k k 
   Pk 
 (c) SE/FIT/HUT 2002 12
 Nicholl-Lee-Nicholl clipping
„ Some edges are irrelevant to 
 clipping, particularly if one vertex a
 lies inside region.
„ Cases: 
 „ x1 in
 „
 x1 in corner region a
 „ x1 in edge region
„ For each case, we generate 
 a
 specialized test regions for x2, which 
 use simple tests (slope, >, <), and 
 tell which edges to clip against. 
 (c) SE/FIT/HUT 2002 13
Nicholl-Lee-Nicholl (2)
 „ Special cases for each endpoint location and slope
 „ Number of cases explodes in 3D, making it 
 12
 unsuitable Reject
 3
 Top
 Left Top, Right
 4
 Left, bottom
 Top, Bottom
 (c) SE/FIT/HUT 2002 14
 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ầu tô ) or ( Color = mầu đường biên ) 
Kếtthúcvì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ớicácđiểmlâncận
End. 
 (c) SE/FIT/HUT 2002 15
 Giảithuật dòng quét-Scanline cho việctô
 mầu vùng
 round down
round up
 AET =
 yma current x denominator current numerator
 (c) SE/FIT/HUT 2002 16
 x
Giảithuậ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 17
 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 18
Antialiasing
 „ Méo thông tin trong quá trình lấymẫutầnsố thấp
 sampling frequency
 „ 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
 (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 (c)and SE/FIT/HUT jaggies 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ần tín hiệubỏibộ lọcthấphơntrước khi lấ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 by 
supersampling
 (c) SE/FIT/HUT 2002 22
(c) SE/FIT/HUT 2002 23
anti aliasing (1)
 (c) SE/FIT/HUT 2002 24
Antialiasing (2)
 (c) SE/FIT/HUT 2002 25
 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 đốitượng được
 mô tả, có thể từ A0, 
 nm, mm ... đếnm, 
 km ... 
 (c) SE/FIT/HUT 2002 26
Hệ tọa độ thiếtbị
(DCS-Device Coordinate System)
 subselect.me
 Vïng täa ®é thiÕt bÞ
 VGA=640x480
 ThiÕt bÞ hiÓn thÞ
 (c) SE/FIT/HUT 2002 27
Hệ tọa độ chuẩn
(NCS - Normalized Coordinate System)
 „ Giảiquyếtvấn đề khi ứng dụng chạy trên các thiếtbị
 khác nhau
 „ Có kích thước1x1
 NCS Dcs
 Wcs chuyÓn ®æi 2
 chuyÓn ®æi 1
 (c) SE/FIT/HUT 2002 28
Windows and Viewports
 The World (what you can see, the real 
 world) The World Window (the bit 
 we want to capture)
 Screen
 Screen Window
 Viewport
 (c) SE/FIT/HUT 2002 29
 Đặc điểm 
•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.
 World Window
 Example Viewports
 (c) SE/FIT/HUT 2002 30
Windows and Viewports
 World Window Viewport
 This is called 
 Mapping
(0,0) (100,0) (0,0) (100,0)
 (wxmax,wymax)
 (vxmax,vymax)
 (wx,wy) (vx,vy)
 (vxmin,vymin)
 (c) SE/FIT/HUT 2002 31
 (wxmin,wymin)
Windows and Viewports
Example
 World Window400 Viewport
 (10,6)
 (-10,-6) 0
 0 600
„ Recall from the last lecture:
 „ x’ = Ax + B
 „ y’ = Cy + D
„ This is exactly how mapping is achieved!!
What are A, B, C & D ??
 (c) SE/FIT/HUT 2002 32
Phép chuyển đổi
 (c) SE/FIT/HUT 2002 33
Example
 World Window400 Viewport
 (10,6)
 (-10,-6) 0
 0 600
A = 600/20 = 30
B = 400/12 = 33.3333 If this is correct, (-10,-6) 
 should map to (0,0) and 
C = 0 – 30 * -10 = 300 (10,6) -> (600,400) ☺
 ☺
D = 0 – 33.3333 * -6 = 200 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 34
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 35
 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 36
 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); glPointSize(10.0);
 glViewport(0,0,600,400);
 } glBegin(GL_POINTS);
 glVertex2i(-10,-6);
 glVertex2i(0,0);
*NOTE: Vertex are given in 
 glVertex2i(10,6);
World Coordinates and OpenGL 
 glEnd();
maps them to the Viewport 
Coordinates.
 (c) SE/FIT/HUT 2002 37
 0.4
 0.3
 -0.4 -0.2
„ Say we want to map 
 this to a 640x480 
 viewport
 480
 640
 (c) SE/FIT/HUT 2002 38
Wx=-.2 Vxmax=640
Wy=.3
Wxmax=0 Vxmin=-0.4
Wxmin=-0.4 Vymax=0
Wymax=0.4 Vymin=480
Wymin=0
Vx= (-.2-(-0.4))*(640-0) + 0 = 320
 0-(-0.4)
Vy= (.3-0)*(0-480) + 480 = 120
 0-(-0.4)
 320
 120
 (c) SE/FIT/HUT 2002 39