Bài giảng Đồ họa và xử lí ảnh - Phần 2: Kỹ thuật đồ họa - Chương 3: Các thuật toán tô màu và xén hình - Nguyễn Đình Cường

Chương 3Các Thuật Toán Tô Màu và Xén HìnhCác thuật toán tô màuBài toánCho đa giác S xác định bởi n đỉnh: P1, P2,..Pn. Hãy tô màu miền SPhương pháp tổng quát:Tìm hình chữ nhật W nhỏ nhất chứa SDuyệt qua tất cả các điểm P(x, y) Є S thì tô màu điểm PCác thuật toán tô màuThuật toán tô màuThuật toán xác định P Є SS là đa giác lồiLấy P Є W, nối P với các đỉnh của S thì ta được n tam giác: Si = PPiPi+1 , với Pn+1=P1Nếu ∑dt(Si) = dt(S) thì P Є SThuật toán tô màuTrường hợp tổng quátLấy P(x, y) Є W, kẻ nửa đường thẳng ΔP xuất phát từ P và không đi qua các đỉnh của đa giác SGọi S(P) là số giao điểm của ΔP với các biên của SNếu S(P) lẻ thì P Є S=> Vấn đề là tìm S(P) Thuật toán tô màuTô màu theo dòng quét (Scanline)Đặt x0=Min (xi) , i Є [1, n]Bước 1: Kẻ Dy // Oy đi qua xoBước 2: Xác định giao điểm Mi(x, y) của Dy với cạnh CiNếu có cạnh Ci=PiPp+1 song song và trùng với Dy thì xem như Dy cắt Ci tại 2 điểm Pi và Pi+1Bước 3: Sắp xếp Mi theo thứ tự tăng với yi (điểm đầu tiên có thứ tự là 1)Bước 4: Những điểm nằm trên Dy ở giữa giao điểm lẻ và giao điểm chẵn liên tiếp là những điểm nằm trong đa giác và tô những điểm nàyBước 5: Tăng x0 lên một Pixel. Nếu x0 ≤ Max(xi) thì quay lại bước 1Thuật toán tô màuThuật toán tô màu▪ Thuật toán vết dầu loang▪ Lấy P(x, y) Є S, tô màu PXét các điểm lân cận của PNếu các điểm lân cận đó vẫn còn thuộc S và chưaĐược tô màu thì tô màu các điểm lân cận đóXén ĐiểmGiả sử cửa sổ xén hình chữ nhật(xmin, ymin) và (xmax, ymax)Một điểm P(x, y) nằm bên trong cửa sổ nếu thỏa mãn hệ bất phương trìnhXén đoạn thẳngXén đoạn thẳngLoại bỏ phép toán tìm giao điểm đoạn thẳng với biên cửa sổ một cách nhanh nhất Đưa ra cách tìm giao điểm thật nhanhThuật toán Cohen-Sutherland▪ Gán mã cho các điểm đầu , cuối P1P2 là c1c2▪ Các đoạn thẳng nằm bên trong cửa sổ, c1=c2=0000▪ Nếu tồn tại k, sao cho bit thứ k của c1, c2 =1, lúc này đoạn thẳng sẽ nằm về cùng phía ứng với bit k so vơi cửa sổ => Nằm hoàn toàn ngoài cửa sổ. Đoạn này loại bỏ sau khi xénThuật toán Cohen-SutherlandThuật toán xén đa giácThuật toán xén đa giácThuật toán xén đa giác