Bài giảng Đồ họa Raster - Chương 2, Phần 1: Các thuật toán tô màu - Bùi Tiến Lên

ĐỒ HỌA RASTER CÁC THUẬT TOÁN TÔ MÀUGiảng viên : Bùi Tiến LênTrang 2Bài toán tô màuTô màu là thao tác tìm các điểm sáng “nằm bên trong” một vùng khép kín.Input : Vùng S Output : {(x1, y1), (x2, y2) (xn, yn)}Trang 3Các hướng tiếp cậnCó hai phương pháp - Tô màu theo lân cận- Tô màu theo dòng quétTô màu theo lân cậnTrang 5Lân cận là gì ?Có hai loại lân cận : lân cận 4 và lân cận 8.Lân cận 4 N4(x, y) = {(x-1, y), (x, y+1), (x+1, y), (x, y-1)}Lân cận 8 N8(x, y) = {(x-1, y), (x-1, y+1), (x, y+1), (x+1, y+1), (x+1, y), (x+1, y-1), (x, y-1), (x-1, y-1)}(x,y)phảitráidướitrênxy(x,y)xytráiTrang 6Thuật toán đệ quibước 1 Kẻ biên vùng cần tôbước 2 Xác định một điểm (x, y) nằm bên trong vùng cần tôbươc 3 Tô điểm (x, y), sau đó tô loang sang những điểm lân cậnxyTrang 7Cài đặt đệ qui// To loangvoid BoundaryFill(CDC *pDC, int x, int y, int fill_color, int boundary_color){ int color; color = pDC->GetPixel(x, y); if((color != fill_color) && (color != boundary_color)) { pDC->SetPixel(x, y, fill_color); BoundaryFill(pDC, x-1, y, fill_color, boundary_color); BoundaryFill(pDC, x, y+1, fill_color, boundary_color); BoundaryFill(pDC, x+1, y, fill_color, boundary_color); BoundaryFill(pDC, x, y-1, fill_color, boundary_color); }}Trang 8Nhận xét thuật toán đệ quiƯu điểm Có thể tô vùng có hình dạng bất kỳ.Khuyết điểm Không thể dùng để tô các vùng có kích thước lớn.kích thöôùc !Trang 9Thuật toán cải tiếnbước 1 Cất điểm hạt giống đầu tiên vào kho.bước 2 Lặp nếu kho không rỗng - c1 Lấy điểm hạt giống. - c2 Tô điểm hạt giống sau đó tô loang sang trái và sang phải. - c3 Bổ sung những điểm hạt giống mới vào kho từ dòng trên và dòng dưới. Trang 10Thuật toán cải tiếnhạt giống : điểm sángkho : chứa các điểm hạt giốngTrang 11Thuật toán cải tiếnbiênbiênMinh họa tô loangTrang 12Thuật toán cải tiếnTiêu chuẩn để là điểm hạt giốngĐiểm này chưa được tô và không phải điểm biên.Điểm này thoả :Điểm trái đầu tiên.hoặc bên trái của nó là điểm biên (nếu nó không phải là điểm trái đầu tiên).Trang 13Thuật toán cải tiếnbiênbiênMinh họa bổ sung những điểm hạt giống mớibiênbiênbiênhạt giốngTrang 14Tô theo lân cận - Một số vấn đềSử dụng lân cận nào ?Trang 15Tô theo lân cận - Một số vấn đềĐường biênmàu gì ?Trang 16Tô theo lân cận - Một số vấn đềTô màu theo dòng quétTrang 18Khái niệm dòng quétDòng quét là dòng điểm sáng trên màn hìnhyTrang 19Tô hình chữ nhậtlrbtyyTrang 20Tô hình tam giácInput (X1, Y1), (X2, Y2), (X3, Y3)Cách tôbước 1 : Sắp xếp các đỉnh Y1  Y2  Y3bước 2 : Phân trường hợp Theo tung độTrang 21Tô hình tam giácY1 = Y2 = Y3132Y1 0S<0(X1,Y1)(X2,Y2)(X3,Y3)(X1,Y1)(X2,Y2)(X3,Y3)Trang 44Thuật toán1. Tìm xmin, xmax, ymin, ymax2. Lặp y : ymin ymax, x : xmin xmax Nếu (x, y) nằm bên trong tam giác thì Tô (x, y)xminxmaxyminymax