Bài giảng Đồ họa máy tính: Tô màu

Bài giảng Đồ họa máy tính: Tô màu (area filling) có nội dung trình bày cho sinh viên về vùng tô, thuật toán cải tiến – dùng stack, thuật toán scanline tổng quát, demo, các trường hợp đặc biệt, hạn chế của thuật toán, cải tiến tốc độ thuật toán, thuật toán cải tiến.
Nội dung trích xuất từ tài liệu:
Bài giảng Đồ họa máy tính: Tô màuArea Filling Tô màu 1 Vùng tôVùng được xác định bởi điểm ảnh – pixel-defined regionVùng xác định bởi đa giác – polygonal region pixel-defined region polygonal region 2 Pixel-defined regionVùng được định nghĩa bởi màu của pixel, chia làm 3 phần: Vùng trong – interior Vùng ngoài – exterior Biên (liên tục) - boundary exterior interior boundary 3 Liên thông 4 và liên thông 84-connected : 2 pixel liên thông với nhau nếu chúng kề nhau theo chiều ngang hay chiều dọc8-connected : 2 pixel liên thông với nhau nếu chúng kề nhau theo chiều ngang, hay chiều dọc, hay đường chéo 4 Cách thức định nghĩa pixel-defined regionInterior defined Tất cả các pixel trong vùng có cùng một màu, gọi là inside-color Các pixel trên biên không có màu này Có thể có lỗ trong vùngBoundary defined Các pixel thuộc biên có cùng màu – boundary-color Các pixel trong vùng không có màu này Nếu một số pixel trong vùng có màu boundary-color thì vùng sẽ chứa lỗ inside color Interior-defined Boundary-defined 5 Polygonal RegionĐịnh nghĩa bằng đa giác: xác định các định các đỉnh p i = (xi,yi)Các loại đa giác: Convex Concave, simple Nonsimple polygonal convex concave nonsimple region 6 Recursive Flood-Fill Algorithm (interior-defined, 4-connected region)Đổi màu của tất cả các interior-pixel thành màu tô – fill color.Quá trình tô màu bắt đầu từ một điểm (seed pixel) thuộc phía trong vùng tô và lan truyền khắp vùng tô => Flood-Fill seed pixel inside fill color color Interior-defined Recursive Flood-Fill 7 Recursive Flood-Fill Algorithm (cont)Thuật toán Nếu pixel tại (x,y) thuộc vùng trong – màu của pixel đó là inside-color thì Đổi màu của nó thành fill-color Áp dụng quá trình trên cho 4 điểm lân cận nó (4-connected). Ngược lại, không làm gì. (4,2) (3,2) (2,2) (1,2) 6 (4,2) (3,2) 5 4 (3,3) (2,3) 3 (2,1) 2 S 1 0 0 12 3 4 56 8 Recursive Flood-Fill Programvoid FloodFill(int x, int y, int inside_color, int fill_color){ if (getpixel(x,y) == inside_color) { putpixel(x,y,fill_color); FloodFill(x-1,y, inside_color, fill_color); FloodFill(x+1,y, inside_color, fill_color); FloodFill(x,y+1, inside_color, fill_color); FloodFill(x,y-1, inside_color, fill_color); }} 9 Recursive Flood-Fill (cont) (boundary-defined, 4-connected region)Bài tập Mô tả thuật toán Cài đặt Boundary-defined 10 Cải tiếnRun - Đường chạy Dãy các pixel liên tiếp theo hàng ngang nằm trong vùng tô Mỗi run được đặt tên bằng pixel ở cực trái (hay phải) của run b a s c d e 11 Thuật toán cải tiến – Dùng stackCho vào stack run chứa seed pixel Stack:while stack not empty { a s a begin = pop(); Tô run bắt đầu từ begin Cho vào stack các run ở bên trên Stack: Cho vào stack các run ở bên dưới b b} c c d d Stack: ...