Các giải thuật cơ sở

Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 1 (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 „ A fundamental task in graphics is to keep those parts of an object that lie outside a selected view from being drawn „ Clipping is the removal of all objects or part of objects in a modelled scene that are outside the real-world window. „ 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ị. „ More practical techniques are necessary to speed up the task „ Khái niệm Xén tỉa là tiến trình xác định các điểm của 1 đối tượng nằm trong hay ngoài cửa sổ hiển thị „ 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 „ Nếu mã của P1 và P2 đều = 0000 thì toàn bộ đoạn thẳng thuộc phần hiển thị. „ If P1.Mã OR P2.Mã == 0000 then “ cả đoạn thẳng thuộc cửa sổ hiển thị” „ Nếu mã của P1 và P2 có cùng một vị trí mà ở đó ≠ 0 thì P1 và P2 => cùng phía „ If P1.Mã AND P2.Mã != 0000 then “ 2 điểm nằm về 1 phía của cửa sổ” Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 2 (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 „ x = x1 + (x2 - x1)u = x1 + uDx „ y = y1 + (y2 - y1)u = y1 + uDy „ xmin ≤ x1 + Dx.u ≤ xmax ⇔ x ∈ [xm, xM] „ ymin ≤ y1 + Dy.u ≤ ymax ⇔ y ∈ [ym, yM] „ Pk u ≤ qk k = 1, 2, 3, 4 ⎪⎪⎩ ⎪⎪⎨ ⎧ = −= = −= 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 ⇒ Đường thẳng nằm ngoài cửa sổ (hệ bất phương trình trên vô nghiệm) „ b)Nếu qk >= 0 thì đoạn thẳng nằm trong hoặc nằm trên cạnh của cửa sổ clipping. „ Hệ bất phương trình luôn thoả mãn. (c) SE/FIT/HUT 2002 10 „ Nếu Pk ≠ 0 : đoạn thẳng đang xét sẽ cắt cạnh k tương ứng của cửa sổ clipping tại vị trí trên đoạn thẳng uk = qk/Pk. „ Pk < 0 đoạn thẳng có dạng đi từ ngoài vào trong • bất phương trình sẽ có dạng u ≥ qk/Pk Ù u ≥ uk. „ Pk > 0 • u ≥ uk sẽ thuộc cửa sổ hiển thị. • bất phương trình sẽ có dạng u ≤ qk/Pk • u ≤ uk với uk = qk/Pk là giao của đoạn thẳng với cạnh k của cửa sổ clipping • đ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 „ cạnh k của cửa sổ clipping cắt đoạn thẳng tại phần mở rộng nằm ngoài đoạn thẳng. „ 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 Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 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: „ 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 Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 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. „ 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 20 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 21 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 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: hunglt@it-hut.edu.vn 0913030731 5 (c) SE/FIT/HUT 2002 25 Antialiasing (2)