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

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

1. ĐỒ HỌA 2D CÁC THUẬT TỐN XÉN HÌNH Giảng viên : Bùi Tiến Lên
2. Xén hình là gì (Clipping) ? Là thao tác loại bỏ phần hình ảnh của thế giới thực nằm bên ngồi một cửa sổ quan sát. Trang 2
3. Các loại xén hình - Xén điểm - Xén đoạn thẳng - Xén đa giác - Xén đối tượng Trang 3
4. Xén điểm
5. Cách xén Input Điểm P Output P thuộc cửa sổ W ? t Wl Px Wr l P(x, y) r Wb Py Wt b Trang 5
6. Xén đoạn thẳng Thuật tốn Cohen-Sutherland
7. Bài tốn Input Đoạn thẳng P1P2 Output P1P2  W P 2 P2 Q2 Q1 P1 P1 Trang 7
8. Phân vùng Mặt phẳng được chia thành làm 5 vùng. bên trong Trang 8
9. Phân vùng bên trái bên phải Trang 9
10. Phân vùng bên trên bên dưới Trang 10
11. Mã vùng – Cách tính Tính mã P vùng C Mã vùng C của điểm P : Cl = Px Wl Cr = Px Wr Cb = Py Wb Ct = Py Wt C(l r b t) Trang 11
12. Mã vùng – Nhận xét C(? ? ? 1) C(1 ? ? ?) C(0 0 0 0) C(? 1 ? ?) C(? ? 1 ?) Trang 12
13. Thuật tố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 ngồi th3 : Cịn lại Trang 13
14. Trường hợp 1 Nếu mã vùng C1 0 0 0 0 C2 0 0 0 0 P2 Thì Q = P P1 1 1 Q2 = P2 Dừng Trang 14
15. Trường hợp 2 Nếu mã vùng P2 C1 1 ? ? ? C2 1 ? ? ? Thì P1P2 nằm vùng bên trái P1 Trang 15
16. Trường hợp 2 : tiếp tục Nếu mã vùng C1 1 ? ? ? P1P2 thuộc vùng bên trái C2 1 ? ? ? C1 ? 1 ? ? P1P2 thuộc vùng bên phải C2 ? 1 ? ? C1 ? ? 1 ? P1P2 thuộc vùng bên dưới C2 ? ? 1 ? C1 ? ? ? 1 P1P2 thuộc vùng bên trên C2 ? ? ? 1 Thì Dừng Trang 16
17. Trường hợp 3 Nếu mã vùng C1 0 0 0 0 P1 Thì P1 nằm bên trong P1moi = P2 P2moi = P1 P2 Trang 17
18. Trường hợp 3 : tiếp tục Nếu mã vùng C1 1 ? ? ? P2 Thì P1 nằm vùng bên trái P1moi P1moi = P1P2  Wl P2moi = P2 P1 Trang 18
19. 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
20. Xén đoạn thẳng Thuật tốn Liang-Barsky
21. Phương trình tham số Cho hai điểm P1, P2. Phương trình tham số đường thẳng : x = P1x + (P2x − P1x )t với t (- , ) y = P1y + (P2y − P1y )t Phương trình tham số đoạn thẳng : x = P1x + (P2x − P1x )t với t 0,1 y = P1y + (P2y − P1y )t Trang 21
22. Ví dụ Cho 2 điểm A(4,3), B(6,4). Phương trình tham số đường thẳ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
23. Thuật tốn Liang-Barsky Thuật tố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
24. Bước 1 Wl P1x + (P2x − P1x )t Wr Wb P1y + (P2y − P1y )t Wt t 0,1 Trang 24
25. Bước 2 Đặ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 Hệ phương trình p1t q1 p2t q2 p3t q3 p4t q4 t 0,1 Trang 25
26. Bước 2 : tiếp th1 p = 0 Nếu q 0 thì vô nghiệm Nếu q 0 thì Bấ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
27. Bước 2 : tiếp th1 p = 0 Nếu q 0 thì vô nghiệm Nếu q 0 thì Hệ bấ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
28. Bước 3 Nếu hệ vô nghiệm P2 Đoạn thẳng P1P2 ở ngoài P1 Nếu hệ có nghiệ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
29. Tĩm tắt Trang 29
30. Xén đa giác Thuật tốn Sutherland-Hodegman
31. Bài tốn Input Đa giác P Output PW P P Trang 31
32. Nửa mặt phẳng trong/ngồ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 ngồi. ngồi trong Trang 32
33. 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
34. Thuật tố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
35. Thuật tốn Trang 35
36. 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
37. Thuật tố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 ngồi, s bên trong th3 : p bên ngồi, s bên ngồi th4 : p bên trong, s bên ngồi Trang 37
38. Trường hợp 1 s p OUT = { } Trang 38
39. Trường hợp 2 s p i OUT = { } Trang 39
40. Trường hợp 3 p s OUT = { } Trang 40
41. Trường hợp 4 s i p OUT = { } Trang 41
42. Vấn đề với đa giác lõm Trang 42
43. Vấn đề với đa giác lõm cạnh thừa Trang 43
44. Đặt bài tốn Input Đa giác IN Output Tập hợp các đa giác {OUTi} IN OUT2 OUT1 Trang 44
45. Phân loại giao điểm Giao điểm được chia làm 2 loại - Loại (ngồi – trong) - Loại  (trong – ngồi) p s p  s Trang 45
46. Thuật tốn xén bằng cạnh cải tiến - Bắt đầu từ bên ngồ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
47. Minh họa   Trang 47
48. Minh họa   Trang 48