›
›

Bài giảng Đồ họa máy tính - Hiển thị đối tượng hai chiều - Ngô Quốc Việt

pdf 32 trang Gia Huy 16/05/2022 3420
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Đồ họa máy tính - Hiển thị đối tượng hai chiều - Ngô Quốc Việt", để 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:

  • pdfbai_giang_do_hoa_may_tinh_hien_thi_doi_tuong_hai_chieu_ngo_q.pdf

Nội dung text: Bài giảng Đồ họa máy tính - Hiển thị đối tượng hai chiều - Ngô Quốc Việt

  1. BÀI GIẢNG ĐỒ HỌA MÁY TÍNH HIỂN THỊ ĐỐI TƯỢNG HAI CHIỀU NGÔ QUỐC VIỆT 2009
  2. Nội dung • Giới thiệu. • Một số hệ tọa độ • Các thuật giải cắt xén • Bài tập • Giải đáp thắc mắc 2
  3. Giới thiệu • Hiển thị đối tượng ở thế giới thực (hệ tọa độ thực trên thiết bị. • Tăng tốc độ hiển thị bằng cách loại bớt phần đang không nhìn thấy trên thiết bị hiển thị (có vẽ cũng không thấy). 3
  4. Cắt xén khi hiển thị • Tại sao cần cắt xén trước khi hiển thị. • Tránh các tác vụ không cần thiết. • Vì đối tượng vector có thể xấp xỉ đa giác thuật giải đưa về là cắt xén từng đoạn thẳng. 4
  5. Cắt xén khi hiển thị 5
  6. Cắt xén khi hiển thị Clipping window (xwmin, ywmax) (xwmax, ywmax) (xwmin, ywmin) (xwmax, ywmin) 6
  7. Thuật giải Cohen-Sutherland 1. Xác định xem cần xén đoạn thẳng đang xét Xét điều kiện bỏ hết hay giữ nguyên không bỏ phần nào 2. Tìm giao điểm của đoạn thẳng với vùng nhìn Có thể dùng y = mx + b để thực hiện • Cần xác định cạnh nào của vùng nhìn có giao nhằm loại bớt các tính toán không cần thiết. • Thuật giải bắt đầu bằng cách phân loại các khu vực liên quan đến vùng nhìn. 7
  8. Thuật giải Cohen-Sutherland Top-Left Top Top-Right Left Inside Right Bottom-Left Bottom Bottom-Right TBRL 8
  9. Thuật giải Cohen-Sutherland T B R L Bit 1 2 3 4 1001 1000 1010 0001 0000 0010 0101 0100 0110 9
  10. Thuật giải Cohen-Sutherland • Kiểm tra quan hệ giữa điểm đầu mút và vùng. point.region = ((point.x viewport.maxX) ? 0x02 : 0) | ((point.y viewport.maxY) ? 0x08 : 0); • Xét các trường hợp hiển nhiên (nằm trong hoặc nằm ngoài vùng nhìn) accept = !(p1.region | p2.region); reject = p1.region & p2.region; 10
  11. Thuật giải Cohen-Sutherland 1001 1000 1010 0001 0000 0010 0101 0100 0110 11
  12. Thuật giải Cohen-Sutherland 1. Assign a region code for each endpoints. 2. If both endpoints have a region code 0000 trivially accept these line. 3. Else, perform the logical AND operation for both region codes. 3.1 if the result is not 0000 trivially reject the line. 3.2 else – (result = 0000, need clipping) 3.2.1. Choose an endpoint of the line that is outside the window. 3.2.2. Find the intersection point at the window boundary (base on region code). 3.2.3. Replace endpoint with the intersection point and update the region code. 3.2.4. Repeat step 2 until we find a clipped line either trivially accepted or trivially rejected. 4. Repeat step 1 for other lines. 12
  13. Thuật giải Cohen-Sutherland How to check for intersection? if bit 1 = 1 there is intersection on TOP boundary. if bit 2 = 1 BOTTOM if bit 3 = 1 RIGHT If bit 4 = 1 LEFT How to find intersection point? use line equation intersection with LEFT or RIGHT boundary. x = xwmin (LEFT) x = xwmax (RIGHT) y = y1 + m(x –x1) intersection with BOTTOM or TOP boundary. y = ywmin (BOTTOM) y = ywmax (TOP) x = x1 + (y –y1)/m 13
  14. Thuật giải Cohen-Sutherland B1 1001 1000 1010 D1 B2 C1 A2 0001 A1 0000 0010 C2 0101 0100 0110 D2 14
  15. Thuật giải Cohen-Sutherland 1001 1000 1010 1. A1=0000,A2=0000 2. (both 0000) – A2 Yes -> accept & draw 0001 A1 0000 0010 3. 3.1 3.2 3.2.1 3.2.2 3.2.3 3.2.4 0101 0100 0110 15
  16. Thuật giải Cohen-Sutherland B1 1001 1000 1010 1. B1=1001,B2=1010 B2 2. (both 0000) – No 3. AND Operation B1 1001 A2 B2 1010 Result 1000 0001 A1 0000 0010 3.1 (not 0000) – Yes reject 3.2 3.2.1 3.2.2 3.2.3 3.2.4 0101 0100 0110 16
  17. Thuật giải Cohen-Sutherland algorithm 1001 1000 1010 1.1. C1=0001,C2=0000 C1=0001,C2=0000 2.2. (both (both 0000) 0000) – –NoYes 3.-> AND accept Operation & C1 draw 0001 A2 3. 0000 3.1result 0000 3.1(not3.2 0000) - No A1 0000 0010 0001 3.2.3.2.1 (0000)-Yes C1’ 3.2.1.3.2.2 choose C1 3.2.2.3.2.3 Intersection C2 point,3.2.4 C1’ at LEFT 3.2.3 C1 <- C1’ 0101 0100 0110 C1 = 0000 3.2.4 repeat 2 17
  18. Thuật giải Cohen-Sutherland D1 algorithm 1001 1000 1010 D1’ D1’’ A2 0001 A1 0000 0010 C1’ C2 D2’’ 0101 0100 0110 D2’ D2 18
  19. Thuật giải Cohen-Sutherland (150, 100) (10, 10) Thực hiện thuật giải Cohen-Sutherland với P1 (0, 120) ; P2(130, 5) , và vùng nhìn như trên hình 19
  20. Thuật giải Cohen-Sutherland 1. P1=1001, P2=0100 2. (both 0000) – Noyes ACCEPT & DRAW 3. AND Operation EndpointsB1 100110000000 after clipping P1’’ B2= (22, 100)0100 P2’ = 124, 10) Result 0000 3.1 (not 0000) – no 3.2 (0000) yes 3.2.1choose P1P1’P2 3.2.2 intersection with LEFTTOPBOTTOM boundary boundary boundary m = (5-120)/(130-0) = -0.8846 • yx == x1y1 + + (y m(x –y1)/m –x1) where where y =x 100;10;= 10; • yx = 12010130 + + (100 (10-0.8846(10-111)/5)/ -0.8846 -0.8846-0) = = 111.15 124.35= 22.44 = = 111 =124 22 • P1’P1’’P2’ == (10,(124,(22, 111)100) 10) 3.2.3 update region code P1’P1’’P2’ == 100000000000 (TOP) 3.2.4 repeat step 2 20
  21. Nhận xét thuật giải Cohen-Sutherland • Số lần cắt tối đa là bao nhiêu cho mỗi đoạn được chấp nhận? • Số lần cắt tối đa là bao nhiêu cho mỗi đoạn bị từ chối? Ưu điểm: Dễ cài đặt Dễ kiểm tra trường hợp hiển nhiên. Nhược điểm: Tốc độ không cao nếu có quá nhiêu đoạn cắt. 21
  22. Thuật giải Liang-Biarsky • Dựa trên phương trình tham số: x = x + u. x 1 0 u 1 y = y1 + u. y • Cửa sổ xén được biểu diễn bởi: xwmin x1 + u. x xwmax ywmin y1 + u. y ywmax hoặc, u. pk qkk = 1, 2, 3, 4 • Với: p1 = - x , q1 = x1 – xwmin p2 = x , q2 = xwmax- x1 p3 = - y , q3 = y1 – ywmin p4 = y , q4 = ywmax - y1 22
  23. Thuật giải Liang-Biarsky • Clipped line will be: x1’ = x1 + u1. x; u1 0 y1’ = y1 + u1. y; x2’ = x1 + u2. x; u2 1 y2’ = y1 + u2. y; • Reject line with pk = 0 and qk < 0. • Calculate uk uk = qk/pk 23
  24. Thuật giải Liang-Biarsky • u1 : maximum value between 0 and u (for pk 0), where starting value for u2 is 1 (u2 = 1) • Consider our previous example where: xwmin = 0, xwmax = 100 ywmin = 0, ywmax = 50 And the line we want to clip connects P1(10, 10) and P2(110, 40) 24
  25. Thuật giải Liang-Biarsky k pk qk uk - x x1 – xwmin 1 = -(110-10) = 10-0 = 10 = -100 x xwmax- x1 2 =110-10=100 = 100 – 10 = 90 - y y1 – ywmin 3 = -(40-10) = 10–0 = 10 =-30 y ywmax - y1 4 = 40-10=30 = 50 – 10 = 40 25
  26. Thuật giải Liang-Biarsky k pk qk uk - x x1 – xwmin = 10-0 = 10 u1 1 = -(110-10) = -100 Since x xwmax- x1 2 pk < 0 =110-10=100 = 100 – 10 = 90 - y y1 – ywmin u1 3 = -(40-10) = 10–0 = 10 =-30 y ywmax - y1 4 = 40-10=30 = 50 – 10 = 40 26
  27. Thuật giải Liang-Biarsky • u1 : maximum value between 0 and u (for pk < 0)! k pk qk uk - x x1 – xwmin u=10/(-100) = 10-0 = 10 =-1/10 We opt u1 1 = -(110-10) = -100 u1 =0, x xwmax- x1 2 =110-10=100 = 100 – 10 = 90 - y y1 – ywmin u=10/(-30) =-1/3 u1 3 = -(40-10) = 10–0 = 10 =-30 y ywmax - y1 4 = 40-10=30 = 50 – 10 = 40 27
  28. Thuật giải Liang-Biarsky • u2 : minimum value between u (for pk > 0) and 1 k pk qk uk - x x1 – xwmin u=10/(-100) 1 = -(110-10) = 10-0 = 10 =-1/10 We opt = -100 u1 =0, x xwmax- x1 2 u2 =110-10=100 = 100 – 10 = 90 - y y1 – ywmin u=10/(-30) 3 = -(40-10) = 10–0 = 10 =-1/3 Since p > 0 =-30 k y ywmax - y1 u 4 2 = 40-10=30 = 50 – 10 = 40 28
  29. Thuật giải Liang-Biarsky • u2 : minimum value between u (for pk > 0) and 1 k pk qk uk - x x1 – xwmin u=10/(-100) We opt 1 = -(110-10) = 10-0 = 10 =-1/10 u =0, = -100 1 x xwmax- x1 u=90/100 2 We opt u2 = 100 – 10 = 90 =9/10 =110-10=100 u2 = 0.9 - y y1 – ywmin u=10/(-30) 3 = -(40-10) = 10–0 = 10 =-1/3 =-30 y ywmax - y1 u=40/30) u 4 2 = 40-10=30 = 50 – 10 = 40 =4/3 29
  30. Thuật giải Liang-Biarsky • If u1 > u2 then reject line (completely outside clipping window!) • Clipped line will be: x1’ = x1 + u1. x (u1 = 0) = 10 + 0.(100) = 10 y1’ = y1 + u1. y = 10 + 0.(30) = 10 x2’ = x1 + u2. x (u2 = 9/10) = 10 + 0.9(100) = 100 y2’ = y1 + u2. y = 10 + 0.9(30) = 37 30
  31. Bài tập • Làm thêm: thực hiện bằng tay với các tham số cho vùng nhìn và các đoạn khác nhau. • Thực hành: cài đặt hai thuật giải Cohen- Sutherland và Liang-Biarsky. 31
  32. Hỏi đáp 32