Bài giảng Đồ họa 2D - Chương 4a: Các thuật toán xén hình - Bùi Tiến Lên

Nội dung text: Bài giảng Đồ họa 2D - Chương 4a: Các thuật toán xén hình - Bùi Tiến Lên

1. Mã vùng – Cách tính Tính maõ P vuøng C Maõ vuøng C cuûa ñieåm P : Cl = Px Wl Cr = Px Wr Cb = Py Wb Ct = Py Wt C(l r b t) Trang 11
2. Mã vùng – Nhận xét C(? ? ? 1) C(1 ? ? ?) C(0 0 0 0) C(? 1 ? ?) C(? ? 1 ?) Trang 12
3. Thuật toán Lặp bước 1 : Tính mã vùng C1 là mã vùng của P1 C2 là mã vùng của P2 bước 2 : Xét mã vùng th1 : Đoạn thẳng nằm vùng bên trong th2 : Đoạn thẳng thuộc các vùng bên ngoài th3 : Còn lại Trang 13
4. Trường hợp 1 Neáu maõ vuøng C1 0 0 0 0 C2 0 0 0 0 P2 Thì Q = P P1 1 1 Q2 = P2 Döøng Trang 14
5. Trường hợp 2 Neáu maõ vuøng P2 C1 1 ? ? ? C2 1 ? ? ? Thì P1P2 naèm vuøng beân traùi P1 Trang 15
6. Trường hợp 2 : tiếp tục Neáu maõ vuøng C1 1 ? ? ? P1P2 thuoäc vuøng beân traùi C2 1 ? ? ? C1 ? 1 ? ? P1P2 thuoäc vuøng beân phaûi C2 ? 1 ? ? C1 ? ? 1 ? P1P2 thuoäc vuøng beân döôùi C2 ? ? 1 ? C1 ? ? ? 1 P1P2 thuoäc vuøng beân treân C2 ? ? ? 1 Thì Döøng Trang 16
7. Trường hợp 3 Neáu maõ vuøng C1 0 0 0 0 P1 Thì P1 naèm beân trong P1moi = P2 P2moi = P1 P2 Trang 17
8. Trường hợp 3 : tiếp tục Neáu maõ vuøng C1 1 ? ? ? P2 Thì P1 naèm vuøng beân traùi P1moi P1moi = P1P2  Wl P2moi = P2 P1 Trang 18
9. Tóm tắt Begin P1, P2 Tính mã vùng Xét th3 th1 th2 P1moi, Q1, Q2 Hết P2moi End Trang 19
10. Xén đoạn thẳng Thuật toán Liang-Barsky
11. Phương trình tham số Cho hai ñieåm P1, P2. Phöông trình tham soá ñöôøng thaúng : x = P1x + (P2x − P1x )t vôùi t (- , ) y = P1y + (P2y − P1y )t Phöông trình tham soá ñoaïn thaúng : x = P1x + (P2x − P1x )t vôùi t 0,1 y = P1y + (P2y − P1y )t Trang 21
12. Ví dụ Cho 2 ñieåm A(4,3), B(6,4). Phöông trình tham soá ñöôøng thaúng : x = 4 + 2t y = 3 + t 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 Trang 22
13. Thuật toán Liang-Barsky Thuật toán bước 1 Lập hệ bất phương trình bước 2 Giải hệ bất phương trình bước 3 Nhận xét nghiệm Trang 23
14. Bước 1 Wl P1x + (P2x − P1x )t Wr Wb P1y + (P2y − P1y )t Wt t 0,1 Trang 24
15. Bước 2 Ñaët p1 = −(P2x − P1x ) q1 = P1x − Wl p2 = P2x − P1x q2 = Wr − P1x p3 = −(P2y − P1y ) q3 = P1y − Wb p4 = P2y − P1y q4 = Wt − P1y Heä phöông trình p1t q1 p2t q2 p3t q3 p4t q4 t 0,1 Trang 25
16. Bước 2 : tiếp th1 p = 0 Neáu q 0 thì voâ nghieäm Neáu q 0 thì Baát phöông trình p.t q t - ,  th2 p 0 thì q t - , p th3 p 0 thì q t , p Trang 26
17. Bước 2 : tiếp th1 p = 0 Neáu q 0 thì voâ nghieäm Neáu q 0 thì Heä baát phöông trình t1moi = t1 p.t q t2moi = t2 t t1,t2  th2 p 0 thì t1moi = t1 t2moi = min(t2,q p) th3 p 0 thì t1moi = max(t1,q p) t2moi = t2 Trang 27
18. Bước 3 Neáu heä voâ nghieäm P2 Ñoaïn thaúng P1P2 ôû ngoaøi P1 Neáu heä coù nghieäm P2 t t1,t2  Q1x = P1x + (P2x − P1x )t1 Q2 Q1y = P1y + (P2y − P1y )t1 Q1 Q2x = P1x + (P2x − P1x )t2 P 1 Q2y = P1y + (P2y − P1y )t2 Trang 28
19. Tóm tắt Trang 29
20. Xén đa giác Thuật toán Sutherland-Hodegman
21. Bài toán Input Đa giác P Output PW P P Trang 31
22. Nửa mặt phẳng trong/ngoài Mỗi cạnh chia mặt phẳng ra làm hai phần gồm : nửa mặt phẳng trong và nửa mặt phẳng ngoài. ngoài trong Trang 32
23. Nhận xét Cửa sổ quan sát là giao của các nửa mặt phẳng trong của các cạnh. cửa sổ quan sát Trang 33
24. Thuật toán Dùng từng cạnh của cửa sổ lần lượt xén đa giác. bước 1 : Xén trái bước 2 : Xén phải bước 3 : Xén dưới bước 4 : Xén trên Trang 34
25. Thuật toán Trang 35
26. Xén đa giác bằng cạnh trái Input Đa giác IN = {p0, p1, , pn-1} Output Đa giác OUT = IN  W Trang 36
27. Thuật toán xén đa giác bằng cạnh trái bước 1 OUT = {} bước 2 Lặp p : p0 pn-1 s là đỉnh kề trước của p th1 : p bên trong, s bên trong th2 : p bên ngoài, s bên trong th3 : p bên ngoài, s bên ngoài th4 : p bên trong, s bên ngoài Trang 37
28. Trường hợp 1 s p OUT = { } Trang 38
29. Trường hợp 2 s p i OUT = { } Trang 39
30. Trường hợp 3 p s OUT = { } Trang 40
31. Trường hợp 4 s i p OUT = { } Trang 41
32. Vấn đề với đa giác lõm Trang 42
33. Vấn đề với đa giác lõm caïnh thöøa Trang 43
34. Đặt bài toán Input Đa giác IN Output Tập hợp các đa giác {OUTi} IN OUT2 OUT1 Trang 44
35. Phân loại giao điểm Giao điểm được chia làm 2 loại - Loại (ngoài – trong) - Loại  (trong – ngoài) p s p  s Trang 45
36. Thuật toán xén bằng cạnh cải tiến - Bắt đầu từ bên ngoài - Gặp giao điểm thì khởi động đa giác OUT = {} - Gặp giao điểm  thì kết thúc đa giác OUT Trang 46
37. Minh họa   Trang 47
38. Minh họa   Trang 48