Flood fill algorithm

Question

Hi, im working in a simple graphical library in C with turbo C++ because im developing a very primitive version of a paint style program, everyting works well but i can´t get the flood fill algorithm to work. Im using the 4 way flood fill algorithm, first i tried with the recursive version but it only work with small areas, filling large areas make it crash; reading i found that implement an explicit stack version of it solve the problem but i don´t really see it.

I have developed a stack like this:

struct node
{
    int x, y;
    struct node *next;
};

int push(struct node **top, int x, int y)
{
    struct node *newNode;
    newNode = (struct node *)malloc(sizeof(struct node));
    if(newNode == NULL) //If there is no more memory
        return 0;
    newNode->x = x;
    newNode->y = y;
    newNode->next = *top;
    *top = newNode;
    return 1; //If we push the element correctly
}

int pop(struct node **top, int &x, int &y)
{
    if(*top == NULL) //If the stack is empty
        return 0;
    struct node *temporal;
    temporal = *top;
    x = (*top)->x;
    y = (*top)->y;
    *top = (*top)->next;
    free(temporal);
    return 1; //If we pop an element 
}

And this is the code i have make to the flood fill function:

void floodFill(int x, int y, int color_to_replace, int color_to_fill)
{
    if(color_to_replace == color_to_fill)
  return;
 struct node *stack = NULL;
 if(push(&stack, x, y) == 0) //If we can´t push the pixel
            return;
    while(pop(&stack, x, y) == 1) //While are pixels in the stack
    {
        pixel(x, y, color_to_fill);
        if(x+1 < 640 && read_pixel(x+1, y) == color_to_replace)
            if(push(&stack, x+1, y) == 0)
                return;
        if(x-1 >= 0 && read_pixel(x-1, y) == color_to_replace)
            if(push(&stack, x-1, y) == 0)
                return;
        if(y+1 < 480 && read_pixel(x, y+1) == color_to_replace)
            if(push(&stack, x, y+1) == 0)
                return;
        if(y-1 >= 0 && read_pixel(x, y-1) == color_to_replace)
            if(push(&stack, x, y-1) == 0)
                return;
    }
}

But it still don´t work, when im triying to fill large areas it just stop and because im working with resolution 640 X 480 in my program that´s really a problem; any ideas why it dont work?

Answer 1

Instead of pushing every pixel on the stack, try to fill as many pixels as possible horizontally before pushing a new position on the stack. See the Wikipedia article for a discussion.

Answer 2

I don't see any boundschecking anywhere...

Are you sure the X and Y values don't go out of the picture?

EDIT:

Extra ideas why it could not work:

• The read and write pixel functions have a bug
• The color value you get back is scaled up to 32 bit (because for instance your picture is 16 bit) and the color you are trying to write and read back again will not match exactly. (e.g. you write the color: 0xff00ff but you get back: 0xf800f8 because the color got scaled up from 16 bit) and this will result in the flood fill going on forever.