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

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

1. Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Nội dung Các giảithuậtcơ sở z Các giảithuậtxéntỉa - Clipping z Các thuật toán tô miềnkín z Phép xử lý Antialiasing Le Tan Hung hunglt@it-hut.edu.vn Bài 3 0913030731 1 2 Xén tỉa - Clipping Clipping đoạnthẳng z Khái niệm z Tiến trình, giải thuật kiểm tra chấp nhận các Xén tỉa là tiến trình tự động xác định các điểm của 1 đối tượng nằm trong đoạn thẳng nằm trong và loại bỏ các đoạn thẳng hay ngoài cửa sổ hiển thị nằm ngoài dựa trên 2 điểm đầu cuối z Tiết kiệm thời gian tiến trình rasterize x x z bỏ qua phần nằm ngoài cửa sổ hiển min max Lý do: thị z ymax Không kiểm tra mọi điểm trên đoạn thẳng z Clipping điểm xmin ≤ x ≤ xmax z Hầu hết các đoạn thẳng với 1 màn hình hiển thị ymin ≤ y ≤ ymax đều được chấp nhận hoặc loại bỏ z Rất ít các đợn thẳng cắt cửa sổ hiển thị ymin 3 4 Giảithuật Cohen Sutherland Outcode z Giải thuật Cohen-Sutherland z If P1.code OR P2.code == 0000 thực hiện nhanh với các trương – Chấp nhận toàn đoạn thẳng hợp đoạn thẳng nằm trong hay z ngoài cửa sổ hiện thị If P1.code AND P2.code != 0000 – Loại z Với truờng hợp cắt, giải thuật xác định lại z Mỗi điểm đầu cuối được gán mã code phụ thuộc vào vị trí trong điểm đầu cuối là giao của đoạn thẳng và mặt phẳng mã khung bao của cửa sổ hiển thị z p.code = 0000 z If p.x > P.code or 0001 z If p.y > P.code or 0100 z If p.x >= xmax >> P.code or 0010 z If p.y >= ymax >> P.code or 1000 5 6 1
2. Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Liabarsky z x = x1 + (x2 -x1)u = x1 + uDx z NếuPk= 0 : điều đótương đương vớiviệc đoạnthẳng z y = y1 + (y2 -y1)u = y1 + uDy đang xét song song vớicạnh thứ kcủahìnhchữ nhật z xmin ≤ x1 + Dx.u ≤ xmax ⇔ x ∈ [xm, xM] clipping. z ymin ≤ y + Dy.u ≤ ymax ⇔ y ∈ [ym, yM] 1 z a) Nếuqk = 0 thì đoạnthẳng nằm trong hoặcnằmtrên cạnh củacửasổ clipping. ⎧q1 = x1 − xm ⎧ P1 = − Dx z Hệ bấtphương trình luôn thoả mãn. ⎪ ⎪ ⎪q2 = xM − x1 ⎪ P 2 = Dx ⎨ ⎨ P = − Dy ⎪q3 = y1 − ym ⎪ 3 ⎪ ⎪ ⎩q4 = yM − y1 ⎩ P 4 = Dy 7 8 z Pk uk sẽ nhậnlà0 khi uk 0 z Pk > 0 và uk > 1 z u ≥ uk sẽ thuộccửasổ hiểnthị. – => uk tương ứng sẽ nhậngiátrị 1. z bấtphương trình sẽ có dạng u ≤ qk/Pk z điểmnằm trong cửasổ clipping sẽ có dạng như sau: z u ≤ uk vớiuk= qk/Pk là giao của đoạnthẳng với – U ≤ u ≤ U cạnh k củacửasổ clipping 1 2 z đoạnthẳng có dạng đitừ trong ra ngoài so vớicạnh k. 9 10 Sutherland-Hodgman Clipping z Basic idea: – Consider each edge of the viewport individually – Clip the polygon against the edge equation ⎛ ⎧ qk ⎫⎞ U = min⎜ 1 ∪ u : u = , P > 0 ⎟ – After doing all planes, the polygon is fully clipped 2 ⎜{} ⎨ k k k ⎬⎟ ⎝ ⎩ Pk ⎭⎠ ⎛ ⎧ q ⎫⎞ U = max⎜ 0 ∪ u : u = k , P < 0 ⎟ 1 ⎜{} ⎨ k k k ⎬⎟ ⎝ ⎩ Pk ⎭⎠ 11 12 2
3. Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Sutherland-Hodgman Clipping Sutherland-Hodgman Clipping z Input/output for algorithm: z Sutherland-Hodgman basic routine: – Input: list of polygon vertices in order – Go around polygon one vertex at a time – Output: list of clipped poygon vertices consisting of – Current vertex has position p old vertices (maybe) and new vertices (maybe) – Previous vertex had position s, and it has been added z Note: this is exactly what we expect from the to the output if appropriate clipping operation against each edge 13 14 Sutherland-Hodgman Clipping Sutherland-Hodgman Clipping z Edge from s to p takes one of four cases: z Four cases: (Purple line can be a line or a plane) – s inside plane and p inside plane z Add p to output inside outside inside outside inside outside inside outside z Note: s has already been added p p s s – s inside plane and p outside plane z Find intersection point i z Add i to output – s outside plane and p outside plane p s z Add nothing p s – s outside plane and p inside plane z Find intersection point i p output i output no output i output z Add i to output, followed by p p output 15 16 GiảithuậtCyrus-Beck Liang Barsky 3-D Clipping z Giải Cohen-Sutherland yêu cầu cửa sổ là hình chữ z Before actually drawing on the screen, we have nhật, các cạnh là cạnh của màn hình to clip (Why?) z Vấn đề nảy sinh khi cửa sổ clip là 1 đa giác bất kỳ hoặc hình chữ nhật quay đi 1 góc z Can we transform to screen coordinates first, z Giải thuật Liang-Barsky tối ưu khi tìm giao điểm của then clip in 2D? đoạn thẳng với cử sổ hiển thị – Correctness: shouldn’t draw objects behind viewer z Nicholl-Lee-Nicholl reducing redundant boundary clipping by identifying edge and corner regions (what will an object with negative z coordinates do in our perspective matrix?) (draw it ) 17 18 3
4. Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Giảithuật đường biên (Boundary - File Algorithm) Edge Walking z Basic idea: z Giải_thuật_đường_biên ( x, y ) Color : biếnmầu – Draw edges vertically Begin – Color = Readpixel ( x, y ); Fill in horizontal spans for each scanline If ( Color = mầutô) or ( Color = mầu đường biên ) – Interpolate colors down edges Kếtthúcvìchạmbiên hoặcchạmphần đãtô – At each scanline, interpolate Else edge colors across span Putcolor(x,y, mauto) 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. 19 20 Edge Walking: Notes Edge Walking: Notes z Order vertices in x and y z Fractional offsets: – 3 cases: break left, break right, no break z Walk down left and right edges – Fill each span – Until breakpoint or bottom vertex is reached z Advantage: can be made very fast z Disadvantages: – Lots of finicky special cases – Tough to get right z Be careful when interpolating color values! – Need to pay attention to fractional offsets z Also: beware gaps between adjacent edges 21 22 Giảithuật đường quét Scan-Line Algorithm Edge Table (ET) z The scan-line algorithm uses edge-coherence and (0,0) incremental integer calculations for maximum efficiency: – Tạobảng edge table (ET) tậpcủacáccạnh đa giác theo thứ tự giá trị ymin của chúng – Tạobảng active edge table (AET) tậpcáccạnh giao vớI đoạn thẳng quét scan-line numerator 1 −3 z Trong tiến trình quét các cạnh sẽ chuyểntừ ET ra AET. ⇒ = m 5 ymax xmin denominator z Các cạnh sẽở trong AET cho đến khi giá trị ymax của cạnh đạttới = scanline z Lúc nay cạnh sẽ bị loạirakhỏiAET. (15,15) scan-line Note: line (8,6) → (13,6) has been deleted according to the scan rules 23 24 4
5. Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Giảithuật dòng quét-Scanline cho việctômầu vùng Active Edge Table (AET) round down round down round up round up AET = AET = current numerator y y current x denominator current numerator max current x denominator 25 ma 26 x Scan-Line Algorithm Rasterizing Triangles y = y of first non empty entry in ET z Interactive graphics hardware commonly uses AET = null repeat edge walking or edge equation techniques for move all ET entries in slot y to AET rasterizing triangles sort AET entries according to xmin fill spans using pairs of AET entries z Two techniques we won’t talk about much: for all AET members – Recursive subdivision of primitive into micropolygons if ymax = y then remove from AET y = y+1 (REYES, Renderman) for all AET members update numerator – Recursive subdivision of screen (Warnock) if numerator>denominator numerator=numerator-denominator x = x+1 until AET and ET empty 27 28 Recursive Triangle Subdivision Edge Equations z An edge equation is simply the equation of the line containing that edge – Q: What is the equation of a 2D line? – A: Ax + By + C = 0 – Q: Given a point (x,y), what does plugging x & y into this equation tell us? – A: Whether the point is: z On the line: Ax + By + C = 0 z “Above” the line: Ax + By + C > 0 z “Below” the line: Ax + By + C < 0 29 30 5
6. Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Edge Equations Edge Equations z Edge equations thus define two half-spaces: z So simply turn on those pixels for which all z And a triangle can be defined as the intersection of edge equations evaluate to > 0: three positive half-spaces: A 2 x 0 + B + C - C B 2 3 0 y + B 3 + + B 0 x + > C1 3 y + x B A + 1 + x 3 A1 A < 0 y + C1 + B1 - A1x 31 32 Using Edge Equations Using Edge Equations z An aside: How do you suppose edge equations z Which pixels: compute min,max bounding box are implemented in hardware? z How would you implement an edge-equation rasterizer in software? – Which pixels do you consider? – How do you compute the edge equations? – How do you orient them correctly? z Edge equations: compute from vertices z Orientation: ensure area is positive (why?) 33 34 Hiệu ứng răng cưa Aliasing - Antialiasing Signal Processing z Aliasing: signal processing term z Raster display: regular sampling of a continuous with very specific meaning function (Really?) z Aliasing: computer graphics term z Think about sampling a 1-D function: for any unwanted visual artifact z Antialiasing: computer graphics term for avoiding unwanted artifacts 35 36 6
7. Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Signal Processing Signal Processing z Sampling a 1-D function: z Sampling a 1-D function: 37 38 Signal Processing Signal Processing z Sampling a 1-D function: z Sampling a 1-D function: what do you notice? – What do you notice? – Jagged, not smooth 39 40 Signal Processing Antialiasing z Sampling a 1-D function: what do you notice? z Méo thông tin trong quá trình lấymẫutầnsố – Jagged, not smooth thấp – Loses information! sampling frequency z In raster images – leads to jagged edges with hiệu ứng bậc thang – staircase effect z Việc làm giảm hiệu ứng méo thông tin bằng phương pháp bù trừ 41 42 7
8. Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Phương pháp khử hiệu ứng răng cưa Prefiltering – Lọc Antialiasing Methods 1. Cốđịnh tín hiệubằng phương pháp lọc-prefiltering: z Eliminate high frequencies before sampling Giảm độ rộng dảitần tín hiệubỏibộ lọcthấphơntrướckhi (Foley & van Dam p. 630) lấymẫu. – Convert I(x) to F(u) Highest quality method, but often impractical. 2. Cốđịnh mẫubằng siêu mẫu supersampling: – Apply a low-pass filter (e.g., multiply F(u) by a box function) Use more samples to raise the Nyquist frequency. Simple and widely used. – Then sample. Result: no aliasing! 3. Cốđịnh mẫubằng phương pháp mẫubấtkỳ z Problem: most rendering algorithms generate - stochastic sampling: sampled function directly Sample randomly, not uniformly. – e.g., Z-buffer, ray tracing Relatively simple, usually used in combination with supersampling. 43 44 Antialiasing in the Continuous Domain Phương pháp siêu mẫu z Problem with prefiltering: z Supersampling cons – Sampling and image generation inextricably linked in – Doesn’t eliminate aliasing, just shifts the Nyquist limit most renderers higher z Z-buffer algorithm z Can’t fix some scenes (e.g., checkerboard) z Ray tracing – Tăng bộ nhớ cho việc lưu trữ – Why? z Supersampling pros z Sự cuốn méo với các miền liên tục do hiệu ứng – Relatively easy xấp xỉ của phương pháp tiền lọc – Often works all right in practice – Can be added to a standard renderer 45 46 Antialiasing by supersampling 47 48 8
9. Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 anti aliasing (1) Antialiasing (2) 49 50 The A-Buffer The A-Buffer z Advantages: z Idea: approximate continuous filtering by – Incorporating into scanline renderer reduces storage costs subpixel sampling dramatically – Processing per pixel depends only on number of visible z Summing areas now becomes simple fragments – Can be implemented efficiently using bitwise logical ops on subpixel masks z Disadvantages – Still basically a supersampling algorithm – Not a hardware-friendly algorithm z Lists of potentially visible polygons can grow without limit z Work per-pixel non-deterministic 51 52 Recap: Antialiasing Strategies Antialiasing Strategies z Supersampling: sample at higher resolution, then z A-Buffer: approximate prefiltering of continuous filter down signal by sampling – Pros: – Pros: z Conceptually simple z Integrating with scan-line renderer keeps storage costs low z Easy to retrofit existing renderers z Can be efficiently implemented with clever bitwise operations z Works well most of the time – Cons: – Cons: z Still basically a supersampling approach z High storage costs z Doesn’t integrate with ray-tracing z Doesn’t eliminate aliasing, just shifts Nyquist limit upwards 53 54 9
10. Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Stochastic Sampling Stochastic Sampling z An intuitive argument: z Idea: randomizing distribution of samples – In stochastic sampling, every region of the image has a finite scatters aliases into noise probability of being sampled – Thus small features that fall between uniform sample points tend z Problem: what type of random distribution to be detected by non-uniform samples to adopt? z Integrating with different renderers: z Reason: type of randomness used affects – Ray tracing: spectral characteristics of noise into which high z It is just as easy to fire a ray one direction as another – Z-buffer: hard, but possible frequencies are converted z Notable example: REYES system (?) z Problem: given a pixel, how to distribute points z Using image jittering is easier (more later) (samples) within it? – A-buffer: nope z Totally built around square pixel filter and primitive-to-sample 55 coherence 56 10