Thao tác điền hoạt động như thế nào trong các ứng dụng vẽ?

Question

Tất cả các chương trình vẽ, độc lập với cách đơn giản hoặc phức tạp của chúng, đi kèm với công cụ tô màu. Điều này về cơ bản thay thế màu sắc của một vùng kín với màu khác. Tôi biết rằng có các API khác nhau để làm điều này, nhưng tôi quan tâm đến thuật toán. Thuật toán hiệu quả để triển khai công cụ này là gì?

Một vài điều tôi có thể nghĩ ra một cách nhanh chóng là:

1. Chuyển đổi hình ảnh thành một bản đồ nhị phân, nơi pixel trong màu được thay thế là 1 và tất cả các màu khác là 0.
2. Tìm một vùng khép kín xung quanh điểm bạn muốn thay đổi sao cho tất cả các điểm ảnh bên trong là 1 và tất cả các điểm ảnh lân cận là 0.

Sample Image

Answer 1

Nhiều triển khai được thực hiện như một chinh phục đệ quy và phân chia thuật toán. Nếu bạn làm một google nhanh chóng cho "lũ điền thuật toán", bạn sẽ tìm thấy nhiều tài nguyên bao gồm cả trang wikipedia tuyệt vời trên the topic.

Answer 2

Nếu bạn muốn có một thuật toán hiệu quả thời gian đó không quan tâm rất hiệu quả về bộ nhớ, bạn có thể làm điều đó bằng cách:

1) giữ một ký ức boolean trong đó các tế bào bạn đã ghé thăm: Vis[]

2) giữ một danh sách các điểm bạn đã đến thăm nhưng chưa đánh dấu những người hàng xóm cho: Busy[]

3) bắt đầu cả hai những người như trống

4) thêm điểm bắt đầu của bạn để Busy

5)

while you have a point P in Busy: 
{ 
    for each neighbour N of the point P for which Vis[N] is still false 
    { 
     if appropriate (not crossing the boundary of the fill region) 
     { 
      set Vis[N] to true 
      update the colour of N in the bitmap 
      add N to the end of Busy[] 
     } 
     remove P from Busy[] 
    } 
} 

Answer 3

The Flood Fill thuật toán là những gì phổ biến nhất được sử dụng. Sau đây là một phiên bản ngây thơ của nó thẳng ra khỏi sách giáo khoa trường đại học cũ của tôi, "Đồ họa máy tính với OpenGL" bởi Hearn Baker, 3rd ed:

void floodFill4 (int x, int y, int fillColor, int interiorColor) 
{ 
    int color; 

    /* Set current color to fillColor, then perform the following operations */ 
    getPixel(x, y, color); 
    if (color == interiorColor) 
    { 
    setPixel(x,y); // Set color of pixel to fillColor. 
    floodFill4(x + 1, y, fillColor, interiorColor); 
    floodFill4(x - 1, y, fillColor, interiorColor); 
    floodFill4(x, y + 1, fillColor, interiorColor); 
    floodFill4(x, y - 1, fillColor, interiorColor); 
    } 
} 

Đối với hình ảnh lớn, tuy nhiên, ở trên có thể sẽ cung cấp cho bạn một chồng lỗi tràn-overflow do đệ quy cho mỗi điểm ảnh. Thông thường, thuật toán này được sửa đổi để nó sử dụng lặp lại khi điền vào một hàng pixel, sau đó đệ quy lấp đầy các hàng ở trên và bên dưới. Như @kasperjj đã nói, wikipedia có một bài viết hay về điều này.

Answer 4

Các loại thuật toán này được thảo luận chi tiết trong Computer Graphics: Principles and Practice. Tôi rất khuyên bạn nên cuốn sách này nếu bạn quan tâm đến việc hiểu cách rasterize đường, điền vào đa giác, viết mã 3d mà không có lợi ích của việc sử dụng API DirectX hoặc OpenGL. Tất nhiên, đối với các ứng dụng thế giới thực, có thể bạn sẽ muốn sử dụng các thư viện hiện có, nhưng nếu bạn tò mò về cách các thư viện này hoạt động, đây là một lần đọc tuyệt vời.

Answer 5

Cũng đọc về ghi nhãn thành phần được kết nối. Đây là một cách hiệu quả để tìm các pixel được kết nối trong khi chỉ truy cập mọi pixel hai lần.

Wikipedia article.

Lợi thế này là các giá trị pixel không phải nhất thiết phải giống nhau hoặc các chức năng mô tả pixel như kết nối có thể là một cái gì đó khác hơn là giá trị nguyên - gradient lẽ.

Answer 6

Ý tưởng chung được mô tả là Flood Fill Algorithm và có nhiều sửa đổi khác nhau cho nó. Một trong những phổ biến là scanline điền. Xem câu hỏi liên quan How Scanline based 2d rendering engines works?