Bài giảng Đồ họa máy tính - Bài 3: Các thuật toán mành hóa - Ma Thị Châu

Nội dung text: Bài giảng Đồ họa máy tính - Bài 3: Các thuật toán mành hóa - Ma Thị Châu

1. Cài đặt thuật toán tô phủ cơ bản Cài đặt thuật toán tô phủ Smith Cài đặt thuật toán tô phủ Fishkin 11 9/13/2011 Ma Thị Châu - Bộ môn KHMT
2. Định lý Jordan. Số điểm cắt chẵn: Ngoài đa giác 4 3 2 0 Số điểm cắt lẻ: Trong đa giác 1 0 4 2 1 Không đúng đối với đa giác tự cắt 3 12 9/13/2011 Ma Thị Châu - Bộ môn KHMT
3. Định lý Jordan Kiểm tra đại lượng e -Sử dụng cả hướng của đường thẳng -đặt e = 0 -Cắt từ trái qua phải e + +, phải qua trái e - - -e != 0, nằm trong 1 0 0 2 0 1 0 1 1 13 9/13/2011 Ma Thị Châu - Bộ môn KHMT
4. Trường hợp đặc biệt • Có 2 trường hợp đặc biệt trong thuật toán Jordan : • Cắt trùng lên cạnh • Cắt trùng lên đỉnh đa giác 14 9/13/2011 Ma Thị Châu - Bộ môn KHMT
5. Thuật toán đường quét  Kiểm tra Jordan tăng dần  Sắp xếp theo giá trị của y y 15 9/13/2011 Ma Thị Châu - Bộ môn KHMT
6. Thuật toán đường quét  Kiểm tra Jordan tăng dần  Sắp xếp theo giá trị của y  Sử dụng sự liên kết giữa các đường quét – giá trị cho đường quét trước gần bằng giá trị cho đường quét sau.  Lưu trữ danh sách các cạnh đang xét 16 9/13/2011 Ma Thị Châu - Bộ môn KHMT
7. Danh sách các cạnh đang xét Các đỉnh là các ‘sự kiện’ trong danh sách cạnh – các cạnh có thể được xét, không được xét hoặc được thay bằng các cạnh khác - Sắp xếp các giao điểm theo x - Kết quả chính là phần giữa cạnh bên trái và bên phải Tạo y Thay thế Xóa 17 9/13/2011 Ma Thị Châu - Bộ môn KHMT
8. Danh sách các cạnh đang xét Phần thảo luận buổi sau: 1. Các thuật toán cắt xén 03 sv – Presentation120p 18 9/13/2011 Ma Thị Châu - Bộ môn KHMT