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

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Đồ họa 2D: Các thuật toán xén hình - Bùi Tiến Lên ĐỒ HỌA 2DCÁC THUẬT TOÁN XÉN HÌNH Giảng viên : Bùi Tiến LênXé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 2Cá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 3Xén điểmCách xénInput Điểm POutput P thuộc cửa sổ W ? t Wl ≤ Px ≤ Wr l P(x, y) r  Wb ≤ Py ≤ Wt b Trang 5 Xén đoạn thẳngThuật toán Cohen-SutherlandBài toán Input Đoạn thẳng P1P2 Output P1P2 ∩ W P2 P2 Q2 Q1 P1 P1 Trang 7Phân vùngMặt phẳng được chia thành làm 5 vùng. bên trong Trang 8Phân vùng bên trái bên phải Trang 9Phân vùng bên trên bên dưới Trang 10Mã vùng – Cách tính Tính m aõ Tính maõ P vuøng C vuøng C Maõvuøng cuûa C ñieåm : P C l = Px < Wl C r = Px > Wr C b = Py < Wb C t = Py > Wt C ( l r b t) Trang 11Mã vùng – Nhận xét C( ? ? ? 1) C( 1 ? ? ?) C ( 0 0 0 0) C( ? 1 ? ?) C( ? ? 1 ?) Trang 12Thuật toánLặpbước 1 : Tính mã vùng C1 là mã vùng của P1 C2 là mã vùng của P2bướ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 13Trường hợp 1 Neáu vuøng maõ C1 0 0 0 0 C2 0 0 0 0 P2 Thì P1 Q1 = P1 Q 2 = P2 Döøng Trang 14Trường hợp 2 Neáu vuøng maõ P2 C1 1 ? ? ? C2 1 ? ? ? Thì P1P2 naèmvuøng traùi beân P1 Trang 15Trường hợp 2 : tiếp tụcNeáu vuøng maõ C1 1 ? ? ? P1P2 thuoäc vuøng traùi beân C2 1 ? ? ? C1 ? 1 ? ? P1P2 thuoäc vuøng phaûi beân C2 ? 1 ? ? C1 ? ? 1 ? P1P2 thuoäc vuøng döôùi beân C2 ? ? 1 ? C1 ? ? ? 1 P1P2 thuoäc vuøng treân beân C2 ? ? ? 1Thì Döøng Trang 16Trường hợp 3 Neáu vuøng maõ C1 0 0 0 0 P1 Thì P1 naèm trong beân P1moi = P2 P2moi = P1 P2 Trang 17Trường hợp 3 : tiếp tục Neáu vuøng maõ C1 1 ? ? ? P2 Thì P1 naèm vuøng traùi beân P1moi P1moi = P1P2 ∩ Wl P2moi = P2 P1 Trang 18Tó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 Xén đoạn thẳngThuật toán Liang-Barsky