›
›

Bài giảng Các giải thuật sinh các thực thể cơ sở - Bài 3: Các giải thuật cơ sở - Lê Tấn Hùng

pdf 39 trang cucquyet12 7720
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Các giải thuật sinh các thực thể cơ sở - Bài 3: Các giải thuật cơ sở - Lê Tấn Hùng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cac_giai_thuat_sinh_cac_thuc_the_co_so_bai_3_cac_g.pdf

Nội dung text: Bài giảng Các giải thuật sinh các thực thể cơ sở - Bài 3: Các giải thuật cơ sở - Lê Tấn Hùng

  1. Bài 3: Cỏc giảithuậtcơ sở Le Tan Hung hunglt@it-hut.edu.vn 0913030731 (c) SE/FIT/HUT 2002 1
  2. 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
  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ỉ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
  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 4
  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 5
  6. (c) SE/FIT/HUT 2002 6
  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 7
  8. 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
  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 thỡ bấtphương trỡnh luụn thoả món. (c) SE/FIT/HUT 2002 9
  10. „ NếuPk≠ 0 : „ uk = qk/Pk. „ 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
  11. „ Pk uk sẽ nhậnlà0 khi uk 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
  12.   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
  13. 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
  14. 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
  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ầ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
  16. 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
  17. 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
  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 18
  19. 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
  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 (c)and SE/FIT/HUT jaggies 2002 20
  21. 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
  22. Antialiasing by supersampling (c) SE/FIT/HUT 2002 22
  23. (c) SE/FIT/HUT 2002 23
  24. anti aliasing (1) (c) SE/FIT/HUT 2002 24
  25. Antialiasing (2) (c) SE/FIT/HUT 2002 25
  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 đốitượng được mụ tả, cú thể từ A0, nm, mm đếnm, km (c) SE/FIT/HUT 2002 26
  27. 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
  28. 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
  29. 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
  30. Đặ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
  31. 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)
  32. 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
  33. Phộp chuyển đổi (c) SE/FIT/HUT 2002 33
  34. 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
  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 35
  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 36
  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); 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
  38. 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
  39. 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