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

Chia sẻ: Ti Vu | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

42
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài 3 trình bày về các phép giải thuật cơ sở. Nội dung chính trong chương này gồm 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. Mời các bạn cùng tham khảo.

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 Đồ họa và hiện thực ảo - Bài 3: Các giải thuật cơ sở

Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Nội dung Các giải thuật cơ sở Bài 3 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 z Le Tan Hung hunglt@it-hut.edu.vn 0913030731 2 1 Xén tỉa - Clipping Clipping đoạn thẳng 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ị ymax Clipping điểm xmin ≤ x ≤ xmax ymin ≤ y ≤ ymax z 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ỏ Rất ít các đợn thẳng cắt cửa sổ hiển thị 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ị z If P1.code OR P2.code == 0000 z If P1.code AND P2.code != 0000 z 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ã z z 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 z z z z xmin z xmax z z ymin 3 4 Giải thuật Cohen Sutherland Outcode z z z z z 5 – Chấp nhận toàn đoạn thẳng – 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ổ hiển thị 6 1 Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Liabarsky z 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] z Pk u ≤ qk z z z z k = 1, 2, 3, 4 ⎧q1 = x1 − xm ⎪q = x − x ⎪ 2 M 1 ⎨ ⎪q3 = y1 − ym ⎪⎩q4 = y M − y1 z ⎧ ⎪ ⎪ ⎨ ⎪ ⎪⎩ P1 = − Dx z P 2 = Dx 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. P 3 = − Dy P 4 = Dy 7 8 z 9 z 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 z bất phương trình sẽ có dạng u ≥ qk/Pk Ù u ≥ uk. – Pk > 0 z u ≥ uk sẽ thuộc cửa sổ hiển thị. z bất phương trình sẽ có dạng u ≤ qk/Pk z 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 z đoạn thẳng có dạng đi từ trong ra ngoài so với cạnh k. z 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 và uk > 1 z điểm nằm trong cửa sổ clipping sẽ có dạng như sau: – – => uk tương ứng sẽ nhận giá trị 1. U 1 ≤ u ≤ U2 10 Sutherland-Hodgman Clipping z – ⎛ ⎧ ⎫⎞ q U 2 = min⎜ {1}∪ ⎨u k : u k = k , Pk > 0 ⎬ ⎟ ⎜ ⎟ Pk ⎩ ⎭⎠ ⎝ ⎛ ⎧ ⎫⎞ q U 1 = max ⎜ {0}∪ ⎨u k : u k = k , Pk < 0 ⎬ ⎟ ⎜ ⎟ Pk ⎩ ⎭⎠ ⎝ 11 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 12 2 Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Sutherland-Hodgman Clipping z Input/output for algorithm: – – z Sutherland-Hodgman Clipping z Input: list of polygon vertices in order Output: list of clipped poygon vertices consisting of old vertices (maybe) and new vertices (maybe) Sutherland-Hodgman basic routine: – – – Note: this is exactly what we expect from the clipping operation against each edge 13 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 14 Sutherland-Hodgman Clipping z Sutherland-Hodgman Clipping Edge from s to p takes one of four cases: z (Purple line can be a line or a plane) inside outside inside outside inside Four cases: – outside p s inside p s inside plane and p inside plane z outside z s – s inside plane and p outside plane z z p s p output i output no output – s outside plane and p inside plane z i output p output z Add nothing Find intersection point i Add i to output, followed by p 16 Giải thuật Cyrus-Beck Liang Barsky z z z z 17 s outside plane and p outside plane z 15 Find intersection point i Add i to output – s p Add p to output Note: s has already been added 3-D Clipping 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 z z Before actually drawing on the screen, we have to clip (Why?) Can we transform to screen coordinates first, then clip in 2D? – Correctness: shouldn’t draw objects behind viewer (what will an object with negative z coordinates do in our perspective matrix?) (draw it…) 18 3 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 z 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 End. 19 – – – – Draw edges vertically Fill in horizontal spans for each scanline Interpolate colors down edges At each scanline, interpolate edge colors across span 20 Edge Walking: Notes z z – z z Fractional offsets: z Be careful when interpolating color values! Also: beware gaps between adjacent edges 3 cases: break left, break right, no break Walk down left and right edges – z Edge Walking: Notes Order vertices in x and y – Fill each span Until breakpoint or bottom vertex is reached Advantage: can be made very fast Disadvantages: – – – Lots of finicky special cases Tough to get right Need to pay attention to fractional offsets z 21 22 Giải thuật đường quét Scan-Line Algorithm z The scan-line algorithm uses edge-coherence and incremental integer calculations for maximum efficiency: – – z z z 23 Basic idea: Edge Table (ET) (0,0) 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 cạnh đạt tới = scanline Lúc nay cạnh sẽ bị loại ra khỏi AET. ymax xmin numerator 1 −3 ⇒ = denominator m 5 (15,15) scan-line Note: line (8,6) → (13,6) has been deleted according to the scan rules 24 4 Khoa CNTT-DDHBK Hà nội Email: hunglt@it-hut.edu.vn 0913030731 Active Edge Table (AET) Giải thuật dòng quét-Scanline cho việc tô mầu vùng round down round down round up round up AET = AET = 25 yma current x denominator current numerator ymax 26 current numerator current x denominator x Scan-Line Algorithm Rasterizing Triangles z 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 until AET and ET empty 27 z Interactive graphics hardware commonly uses edge walking or edge equation techniques for rasterizing triangles Two techniques we won’t talk about much: – – Recursive subdivision of primitive into micropolygons (REYES, Renderman) Recursive subdivision of screen (Warnock) 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 z z 29 On the line: Ax + By + C = 0 “Above” the line: Ax + By + C > 0 “Below” the line: Ax + By + C < 0 30 5