Bài giảng Đồ họa Raster - Các thuật toán tô màu

ĐỒ HỌA RASTER CÁC THUẬT TOÁN TÔ MÀU Giảng viên : Bùi Tiến Lên Trang * Bài toán tô màu Tô 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 * Các hướng tiếp cận Có hai phương pháp - Tô màu theo lân cận - Tô màu theo dòng quét Tô màu theo lân cận Trang * Lâ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ải trái dưới trên x y (x,y) x y trái Trang * Thuật toán đệ qui bướ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ận x y Trang * Cài đặt đệ qui // To loang void 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 * Nhậ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 * Thuật toán cải tiến bướ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 * Thuật toán cải tiến hạt giống : điểm sáng kho : chứa các điểm hạt giống Trang * Thuật toán cải tiến Minh họa tô loang Trang * Thuật toán cải tiến Tiê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 * Thuật toán cải tiến Minh họa bổ sung những điểm hạt giống mới biên biên biên hạt giống Trang * Tô theo lân cận - Một số vấn đề Sử dụng lân cận nào ? Trang * Tô theo lân cận - Một số vấn đề Đường biên màu gì ? Trang * Tô theo lân cận - Một số vấn đề Tô màu theo dòng quét Trang * Khái niệm dòng quét Dòng quét là dòng điểm sáng trên màn hình y Trang * Tô hình chữ nhật l r b t Trang * Tô hình tam giác Input (X1, Y1), (X2, Y2), (X3, Y3) Cách tô bước 1 : Sắp xếp các đỉnh Y1  Y2  Y3 bước 2 : Phân trường hợp Theo tung độ Trang * Tô hình tam giác Trang * Tô hình tam giác Tô tam giác (Y1 = Y2 = Y3) Tìm Xmin, Xmax Tô dòng Y1 bắt đầu tại cột Xmin, kết thúc tại cột Xmax 1 3 2 Y1 Xmin Xmax Trang * Tô hình tam giác Tô tam giác (Y1 0 S<0 (X1,Y1) (X2,Y2) (X3,Y3) (X1,Y1) (X2,Y2) (X3,Y3) Trang * Thuật toán 1. Tìm xmin, xmax, ymin, ymax 2. Lặp y : ymin … ymax, x : xmin … xmax Nếu (x, y) nằm bên trong tam giác thì Tô (x, y) xmin xmax ymin ymax