Giáo trình Đồ họa - Bài 4: Các giải thuật cơ sở

45 trang huongle 3330

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Đồ họa - Bài 4: Các giải thuật cơ sở", để 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:

giao_trinh_do_hoa_bai_4_cac_giai_thuat_co_so.pdf

Nội dung text: Giáo trình Đồ họa - Bài 4: Các giải thuật cơ sở

NỘI DUNG 1. Các giải thuật xén tỉa 2. Thuật toán tô miền kín 3. Phép xử lý Antialiasing © Copyright Copyright © Showeet.com - 2
Xén tỉa - clipping • Khái niệm 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 hay ngoài cửa sổ hiển thị • 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 thị xmin xmax • Clipping điểm ymax – xmin x xmax Copyright © Showeet.com – ymin y ymax ymin 4
Clipping đoạn thẳng • Tiến trình, giải thuật kiểm tra chấp nhận các đoạn thẳng nằm trong và loại bỏ các đoạn thẳng nằm ngoài dựa trên 2 điểm đầu cuối • Lý do: – Không kiểm tra mọi điểm trên đoạn thẳng – Hầu hết các đoạn thẳng với 1 màn hình hiển thị đều được chấp nhận hoặc loại bỏ © Copyright Copyright © Showeet.com – Rất ít các đoạn thẳng cắt cửa sổ hiển thị 5
GIẢI THUẬT COHEN SUTHERLAND OUTCODE • Giải thuật Cohen-Sutherland thực hiện nhanh với các trương hợp đoạn thẳng nằm trong hay ngoài cửa sổ hiện thị • Mỗi điểm đầu cuối được gán mã code phụ thuộc vào vị trí trong mặt phẳng mã © Copyright Copyright © Showeet.com - 6
Giải thuật Cohen Sutherland outcode p.code = 0000 . If p.x > P.code or 0001 . If p.y > P.code or 0100 . If p.x >= xmax >> P.code or 0010 . If p.y >= ymax >> P.code or 1000 © Copyright Copyright © Showeet.com 7
Giải thuật Cohen Sutherland outcode • If P1.code OR P2.code == 0000 – Chấp nhận toàn đoạn thẳng • If P1.code AND P2.code != 0000 – Loại • Với truờng hợp cắt, giải thuật xác định lại điểm đầu cuối là giao của đoạn thẳng và khung bao của cửa sổ Copyright © Showeet.com hiển thị 8
Giải thuật Cyrus-beck Liang Barsky • Giải Cohen-Sutherland yêu cầu cửa sổ là hình chữ nhật, các cạnh là cạnh của màn hình • 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 • Giải thuật Liang-Barsky tối ưu khi tìm giao điểm của đoạn thẳng với cử sổ hiển thị • Nicholl-Lee-Nicholl reducing redundant boundary clipping by identifying edge and corner regions Copyright © Showeet.com 9
Liabarsky • 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 q x x Copyright © Showeet.com 1 1 m P1 Dx q x x 2 M 1 P2 Dx q y y 3 1 m P3 Dy q y y 4 M 1 P4 Dy 10
Liabarsky • 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 thì đoạn thẳng nằm trong hoặc nằm trên cạnh của cửa sổ clipping. Copyright © Showeet.com • Hệ bất phương trình luôn thoả mãn. 11
Liabarsky • 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 • 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 Copyright © Showeet.com • đoạn thẳng có dạng đi từ trong ra ngoài so với cạnh k. 12
Liabarsky • Pk uk sẽ nhận là 0 khi uk 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: Copyright © Showeet.com – U1 u U2 13
q  U min 1  u : u k , P 0 2  k k k  Pk  q  k U max 0  u : u , P 0 1  k k k  Pk  © Copyright Copyright © Showeet.com 14
Sutherland-Hodgman Clipping • Basic idea: – Consider each edge of the viewport individually – Clip the polygon against the edge equation – After doing all planes, the polygon is fully clipped © Copyright Copyright © Showeet.com 15
Sutherland-Hodgman Clipping • Input/output for algorithm: – Input: list of polygon vertices in order – Output: list of clipped poygon vertices consisting of old vertices (maybe) and new vertices (maybe) • Note: this is exactly what we expect from the clipping operation against each edge © Copyright Copyright © Showeet.com 16
Sutherland-Hodgman Clipping • Sutherland-Hodgman basic routine: – Go around polygon one vertex at a time – Current vertex has position p – Previous vertex had position s, and it has been added to the output if appropriate © Copyright Copyright © Showeet.com 17
Sutherland-Hodgman Clipping • Edge from s to p takes one of four cases: (Purple line can be a line or a plane) inside outside inside outside inside outside inside outside p p s s p s p s Copyright © Showeet.com p output i output no output i output p output 18
Sutherland-Hodgman Clipping • Four cases: – s inside plane and p inside plane • Add p to output • Note: s has already been added – s inside plane and p outside plane • Find intersection point i • Add i to output – s outside plane and p outside plane • Add nothing – s outside plane and p inside plane © Copyright Copyright © Showeet.com • Find intersection point i • Add i to output, followed by p 19
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 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 Copyright © Showeet.com End. 21
Edge Walking • Ý tưởng – Vẽ các cạnh theo chiều dọc – Tô các đường nằm bên trong miền theo mỗi đường ngang – Nội suy xuống các cạnh ở dưới – Tại mỗi đường ngang, nội suy màu sắc của cạnh theo các đường bên trong miền © Copyright Copyright © Showeet.com 22
Giải thuật đường quét scan-line algorithm • Giải thuật đường quét sử dụng gắn kết cạnh và các tính toán số nguyên tăng dần cho hiệu quả cao nhất • 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 • Trong tiến trình quét các cạnh sẽ chuyển từ ET ra AET. • Các cạnh sẽ ở trong AET cho đến khi giá trị ymax của Copyright © Showeet.com cạnh đạt tới = scanline • Lúc nay cạnh sẽ bị loại ra khỏi AET. 23
Edge Table (ET) (0,0) numerator 1 3 Copyright © Showeet.com m 5 ymax xmin denominator (15,15) scan-line Note: line (8,6) (13,6) has been deleted according to the scan rules 24
Active Edge Table (AET) round down round up © Copyright Copyright © Showeet.com AET = ymax current x denominator current numerator 25
Active Edge Table (AET) round down round up © Copyright Copyright © Showeet.com AET = y max current x denominator current numerator 26
SCAN-LINE ALGORITHM y = y of first non empty entry in ET AET = null repeat move all ET entries in slot y to AET sort AET entries according to xmin fill spans using pairs of AET entries for all AET members if ymax = y then remove from AET y = y+1 for all AET members update numerator if numerator>denominator numerator=numerator- denominator x = x+1 Copyright © Showeet.com until AET and ET empty - 27
Hiệu ứng răng cưa • Aliasing: signal processing term with very specific meaning • Aliasing: computer graphics term for any unwanted visual artifact • Antialiasing: computer graphics term for avoiding unwanted artifacts © Copyright Copyright © Showeet.com 29
Xử lý tín hiệu • Rời rạc hóa: Bằng cách lấy mẫu theo chu kỳ nhất định • Ví dụ với đường sau đây © Copyright Copyright © Showeet.com 30
Antialiasing sampling frequency • Méo thông tin trong quá trình lấy mẫu tần số thấp • Một số trường hợp bị méo thông tin với hiệu ứng bậc thang – staircase effect • Việc làm giảm hiệu ứng méo thông tin bằng Copyright © Showeet.com phương pháp bù trừ 36
PHƯƠNG PHÁP KHỬ HIỆU ỨNG RĂNG CƯA 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ấp hơn trước khi lấy mẫu. – Chất lượng cao nhất nhưng không thực tiễn 2. Cố định mẫu bằng siêu mẫu supersampling: – Dùng nhiều mẫu hơn để tăng tần số – Đơn giản và được sử dụng rộng rãi 3. Cố định mẫu bằng phương pháp mẫu bất kỳ – Mẫu ngẫu nhiên nhưng không đồng nhất © Copyright Copyright © Showeet.com – Tương đối đơn giản, thường được kết hợp với phương pháp siêu mẫu 37
Supersampling patterns • Grid : The simplest algorithm. The pixel is split in several sub- pixels, and a sample is taken from the center of each. It is fast and easy to implement, although due to the regular nature of sampling, aliasing can still occur if a low number of sub-pixels is used. • Random: Also known as stochastic sampling, it avoids the regularity of grid supersampling. However, due to the irregularity of the pattern, samples end up being unnecessary in some areas of the pixel and lacking in others. • Poisson disc: Again an algorithm that places the samples randomly, but then checks that any two are not too close. The end result is even but random distribution of samples. Copyright © Showeet.com Unfortunately, the computational time required for this algorithm is too great to justify its use in real-time rendering, unless the sampling itself is computationally expensive compared to the positioning the sample points or the sample points are not repositioned for every single pixel. 41
Supersampling patterns • Jittered: A modification of the grid algorithm to approximate the Poisson disc. A pixel is split into several sub-pixels, but a sample is not taken from the center of each, but from a random point within the sub-pixel. Congregation can still occur, but to a lesser degree. • Rotated grid: A 2×2 grid layout is used but the sample pattern is rotated to avoid samples aligning on the horizontal or vertical axis greatly improving antialiasing quality for the most commonly encountered cases. For an optimal pattern, the rotation angle is arctan(1/2) (about 26.6 degrees) and the square is stretched by a factor of √5/2 Copyright © Showeet.com 42