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