• Advertisement

Archived

This topic is now archived and is closed to further replies.

Good ol' fashion flood-fill algorithm?

This topic is 5836 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m looking for a nice/clean yet efficient flood-fill algorithm to use in a game I plan on creating. The algorithms I''ve found so far either include insane amounts of recursion (one recursize call per pixel, recursing on all 4 adjoining pixels), or use loops qith queues almost mimicking recursion but without the stack problem, some of those also go by scan ilne instead of per pixel. Does anyone know of any other way or are those pretty much standards? I mean, is that pretty much the algo. photoshop would use?? Or any imaging software for that matter. ByteMe95::~ByteMe95() My S(h)ite

Share this post


Link to post
Share on other sites
Advertisement
I don''t know if this would be very fast, but it''s an idea.
  
// w and h are the width and height, and imageData is the imageData (note that this would be for 8bpp, but is easily modifiable for other bpps)

// (x, y) is the initial point, and color is the color that it is filling with

int old_color = imageData[x + y * w];
UCHAR *map = new UCHAR[w * h];
assert(map != NULL); // Make sure the memory was allocated

memset(map, 0, w * h);
map[x + y * w] = 1;
int changed;
do
{
changed = 0;

for(int i = 0; i < h; i++)
{
for(int j = 0; j < w; j++)
{
if((j > 0) && (imageData[i * w + j] == old_color) && (map[i * w + j - 1] == 1))
{
imageData[i * w + j] = color;
map[i * w + j] = 1;
changed = 1;
}
else if((j < w - 1) && (imageData[i * w + j] == old_color) && (map[i * w + j + 1] == 1))
{
imageData[i * w + j] = color;
map[i * w + j] = 1;
changed = 1;
}
else if((i > 0) && (imageData[i * w + j] == old_color) && (map[(i - 1) * w + j] == 1))
{
imageData[i * w + j] = color;
map[i * w + j] = 1;
changed = 1;
}
else if((i < h - 1) && (imageData[i * w + j] == old_color) && (map[(i + 1) * w + j] == 1))
{
imageData[i * w + j] = color;
map[i * w + j] = 1;
changed = 1;
}
}
}
} while(changed);

What it basically does is it uses a map to keep track of which pixels have been changed. While its still making changes, it loops through each pixel, and tests if its next to a pixel that''s already been changed and if its color is equal to the color of the original pixel. If it is, it changes that pixel and marks it on the map. I haven''t tested it yet, but it theoretically should work. I have no idea if it would be faster than a massively recursive algorithm.

Share this post


Link to post
Share on other sites
IT looks like all this would really do is make a filled square qouldnt it?
It would draw a square wxh pixels on the screen
I need a fill function that fills in a bounded region

ByteMe95::~ByteMe95()
My S(h)ite

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
one i implemented a few years ago went as follows

insert flooding_startpoint into list
WHILE points IN list
remove point from list
write floodcolor to point
if point.x, point.y+1 == opencolor add_point_to_list
if point.x+1, point.y == opencolor add_point_to_list
if point.x, point.y-1 == opencolor add_point_to_list
if point.x-1, point.y == opencolor add_point_to_list
WHILE-END

Share this post


Link to post
Share on other sites
While you can use shortcuts they all result incomplete fills.

The recursive pixel method is one general way of doing it. It''s called a depth first recursion because often it does all the way to the bottom before it starts going up.

The problem you are dealing with is that you must check to see if each pixel is part of the the ''body'' you are filling. Now the only way to do that is to see if there is a ''path'' of pixels of the same color connecting that pixel to the original position pixel. Now you could check every single pixel in the picture, however if you do a recursive search, you only have to deal with the pixels that are in or bording thus making it faster. Now since you are dealing with many function calls any optimization that reduces a call is good so you could try unrolling loops or using queues. But they are work on the same principle.

Share this post


Link to post
Share on other sites

  • Advertisement