intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Sinh Nhân | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST
Báo xấu
100
lượt xem 6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Bài 3: Các giải thuật cơ sở" cung cấp cho sinh viên các kiến thức: Các giải thuật xén tỉa - Clipping, các thuật toán tô miền kín, phép xử lý Antialiasing. Đây là một tài liệu tham khảo hữu ích dành cho các bạn sinh viên Công nghệ thông tin và thiết kế đồ họa dùng làm tài liệu học tập và nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng 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ải thuật cơ sở z Các giải thuật xén tỉa - Clipping z Các thuật toán tô miền kín z Phép xử lý Antialiasing Le Tan Hung Bài 3 hunglt@it-hut.edu.vn 0913030731 1 2 Xén tỉa - Clipping Clipping đoạn thẳ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 bỏ qua phần nằm ngoài cửa sổ hiển xmin xmax z Lý do: thị ymax z 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ải thuậ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 ngoài cửa sổ hiện thị z If P1.code AND P2.code != 0000 – Loại z Mỗi điểm đầu cuối được gán mã z Với truờng hợp cắt, giải thuật xác định lại 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ếu Pk = 0 : điều đó tương đương với việc đoạn thẳng z y = y1 + (y2 - y1)u = y1 + uDy đang xét song song với cạnh thứ k của hình chữ nhật z xmin ≤ x1 + Dx.u ≤ xmax ⇔ x ∈ [xm, xM] clipping. z ymin ≤ y1 + Dy.u ≤ ymax ⇔ y ∈ [ym, yM] z 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) z Pk u ≤ qk k = 1, 2, 3, 4 z 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. ⎧q1 = x1 − xm ⎧ P1 = − Dx z Hệ bất phương trình luôn thoả mãn. ⎪q = x − x ⎪ P 2 = Dx ⎪ 2 M 1 ⎪ ⎨ ⎨ ⎪q3 = y1 − ym ⎪ P 3 = − Dy ⎪⎩q4 = y M − y1 ⎪⎩ P 4 = Dy 7 8 z Pk < 0 và uk < 0 z Nếu Pk ≠ 0 : đoạn thẳng đang xét sẽ cắt cạnh k tương ứng – cạnh k của cửa sổ clipping cắt đoạn thẳng tại phần mở rộng của cửa sổ clipping tại vị trí trên đoạn thẳng uk = qk/Pk. nằm ngoài đoạn thẳng. – Pk < 0 đoạn thẳng có dạng đi từ ngoài vào trong – uk ≤ u< 0 thoả mãn bất phương trình sẽ không nằm trên đoạn z bất phương trình sẽ có dạng u ≥ qk/Pk Ù u ≥ uk. thẳng cần xét. – Pk > 0 – => uk sẽ nhận là 0 khi uk 0 và uk > 1 – => uk tương ứng sẽ nhận giá trị 1. z bất phương trình sẽ có dạng u ≤ qk/Pk z điểm nằm trong cửa sổ clipping sẽ có dạng như sau: z u ≤ uk với uk = qk/Pk là giao của đoạn thẳng với – U 1 ≤ u ≤ U2 cạnh k của cửa sổ clipping z đoạn thẳng có dạng đi từ trong ra ngoài so với cạnh k. 9 10 Sutherland-Hodgman Clipping z Basic idea: – Consider each edge of the viewport individually ⎛ ⎧ ⎫⎞ Clip the polygon against the edge equation U 2 = min⎜ {1}∪ ⎨u k : u k = k , Pk > 0 ⎬ ⎟ q – After doing all planes, the polygon is fully clipped ⎜ ⎟ – ⎝ ⎩ Pk ⎭⎠ ⎛ ⎧ ⎫⎞ U 1 = max ⎜ {0}∪ ⎨u k : u k = k , Pk < 0 ⎬ ⎟ q ⎜ ⎟ ⎝ ⎩ 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ải thuật Cyrus-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ị z Nicholl-Lee-Nicholl reducing redundant boundary – Correctness: shouldn’t draw objects behind viewer 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ải thuật đường biên (Boundary - File Algorithm) Edge Walking z Basic idea: z Giải_thuật_đường_biên ( x, y ) Color : biến mầu – Draw edges vertically Begin Color = Readpixel ( x, y ); – Fill in horizontal spans for each scanline If ( Color = mầu tô ) or ( Color = mầu đường biên ) – Interpolate colors down edges Kết thúc vì chạm biên hoặc chạm phầ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ực hiện lại giải thuật với các điểm lân cậ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ải thuậ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ạo bảng edge table (ET) tập của các cạnh đa giác theo thứ tự giá trị ymin của chúng – Tạo bảng active edge table (AET) tập các cạ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ển từ ET ra AET. ⇒ = ymax xmin denominator m 5 z Các cạnh sẽ ở trong AET cho đến khi giá trị ymax của cạnh đạt tới = scanline z Lúc nay cạnh sẽ bị loại ra khỏi AET. (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ải thuật dòng quét-Scanline cho việc tô mầu vùng Active Edge Table (AET) round down round down round up round up AET = AET = current numerator ymax yma current x denominator current numerator current x denominator 25 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 if ymax = y then remove from AET – Recursive subdivision of primitive into micropolygons 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: - + +- Ax 2 + 3 0 2 + 2 + By C 2 0 3 + By By 3 + C >0 3 + Ax B y+ 1 A 1x + 1 Ax C
  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ấy mẫu tần số – 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 Antialiasing Methods Prefiltering – Lọc 1. Cố định tín hiệu bằng phương pháp lọc-prefiltering: z Eliminate high frequencies before sampling Giảm độ rộng dải tần tín hiệu bỏi bộ lọc thấphơn trước khi (Foley & van Dam p. 630) lấy mẫu. – Convert I(x) to F(u) Highest quality method, but often impractical. 2. Cố định mẫu bằ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ẫu bằng phương pháp mẫu bất kỳ 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: z It is just as easy to fire a ray one direction as another spectral characteristics of noise into which high – 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) – A-buffer: nope (samples) within it? z Totally built around square pixel filter and primitive-to-sample 55 coherence 56 10
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2