Bài giảng Đồ họa 2D: Các thuật toán xén hình có nội dung trình bày khái niệm xén hình, xén điểm, cách xén, xén đoạn thẳng - Thuật toán Cohen-Sutherland, xén đoạn thẳng - Thuật toán Liang-Barsky, xén đa giác - Thuật toán Sutherland-Hodegman và một số nội dung khác. | ĐỒ HỌA 2D CÁC THUẬT TOÁN XÉN HÌNH Giảng viên : Bùi Tiến Lên Trang 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 ngoài một cửa sổ quan sát. Trang 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 Xén điểm Trang Cách xén Input Điểm P Output P thuộc cửa sổ W ? l r b t P(x, y) Xén đoạn thẳng Thuật toán Cohen-Sutherland Trang Bài toán Input Đoạn thẳng P1P2 Output P1P2 W P1 P2 P1 P2 Q1 Q2 Trang Phân vùng Mặt phẳng được chia thành làm 5 vùng. bên trong Trang Phân vùng bên trái bên phải Trang Phân vùng bên trên bên dưới Trang Mã vùng – Cách tính P Tính maõ vuøng C Trang Mã vùng – Nhận xét Trang 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 Trường hợp 1 P1 P2 Trang Trường hợp 2 P1 P2 Trang Trường hợp 2 : tiếp tục Trang Trường hợp 3 P2 P1 Trang Trường hợp 3 : tiếp tục P1 P2 P1moi Trang Tóm tắt Tính mã vùng Xét Hết Begin End P1, P2 Q1, Q2 P1moi, P2moi th1 th2 th3 Xén đoạn thẳng Thuật toán Liang-Barsky Trang Phương trình tham số Trang Ví dụ 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 10 (4,3) (6,4) (8,5) (2,2) t=-1 t=0 t=1 t=2 Trang 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 Bước 1 P1 P2 t 0 1 Trang Bước 2 Trang Bước 2 : tiếp Trang Bước 2 : tiếp Trang Bước 3 P1 P2 P1 P2 Q1 Q2 Trang Tóm tắt Xén đa giác Thuật toán Sutherland-Hodegman Trang Bài toán Input Đa giác P Output P W P P Trang 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. trong ngoài Trang 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 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 Thuật toán Trang 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 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 Trường hợp 1 p s OUT = { } Trang Trường hợp 2 p s i OUT = { } Trang Trường hợp 3 p s OUT = { } Trang Trường hợp 4 p s i OUT = { } Trang Vấn đề với đa giác lõm Trang Vấn đề với đa giác lõm caïnh thöøa Trang Đặt bài toán Input Đa giác IN Output Tập hợp các đa giác {OUTi} OUT1 OUT2 IN Trang 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 s p Trang 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 Minh họa Trang Minh họa
