Jump to content
  • Advertisement
Sign in to follow this  
Lawl_Rock

Flood fill problem

This topic is 3730 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 am using a recursive flood fill algorithm in C++ with SDL, and my program crashes whenever the function is called. I have come to the conclusion that the crash is caused by the function's recursiveness, but I may be wrong. I am looking for a solution, whether it is another algorithm or just an adjustment. I searched google and gamedev furiously and found nothing.
void draw_fill(int x, int y, SDL_Surface *surface, Uint32 replacementColor, Uint32 targetColor) {
	if ((x<0)||(x>=surface->w)) {
		return;
	}
	if ((y<0)||(y>=surface->h)) {
		return;
	}
	if (get_pixel(x, y, surface)==targetColor) {
		put_pixel(x, y, surface, replacementColor);
		draw_fill(x+1, y, surface, replacementColor, targetColor);
		draw_fill(x, y+1, surface, replacementColor, targetColor);
		draw_fill(x-1, y, surface, replacementColor, targetColor);
		draw_fill(x, y-1, surface, replacementColor, targetColor);
		return;
	}
}
(get_pixel and put_pixel have already been declared)

Share this post


Link to post
Share on other sites
Advertisement
How does the program crash? Are you running it through the debugger? If not, that should be a start because it will give you a good hint of what's wrong. Maybe surface is a NULL-pointer?

Share this post


Link to post
Share on other sites
It stops responding and closes.

I know surface is not null, I tested for it, and the program doesn't crash if I comment out some of the recursive lines.

Share this post


Link to post
Share on other sites
Old and really crappy code I did for a universitity course, but it should work... just replace the bitmap usage with your own.



template <typename T> inline
void fill_interval(Bitmap<T> & bitmap, int x, int y, const T & fillColor, const T & toFill)
{
T pixel;

for(int xx = x-1; xx >= 0; --xx)
{
bitmap.getPixel(Point(xx,y),pixel);

if(pixel != toFill)
break;
}

for(int xx = x; xx < int(bitmap.getWidth());xx++)
{
bitmap.getPixel(Point(xx,y),pixel);

if(pixel != toFill)
break;

bitmap.setPixel(Point(xx,y),fillColor);
}
}

template <typename T> inline
void floodfill(Bitmap<T> & bitmap, const Point & start, const T & color)
{
T toFill, pixel;

bitmap.getPixel(start,toFill);

std::stack<Point> stack;

stack.push(start);

const int maxIterations = int(bitmap.getWidth() * bitmap.getHeight());

int iteration = 0;

do
{
Point p = stack.top();
stack.pop();

bitmap.getPixel(p,pixel);

if(pixel == toFill)
{
// Find the start of the range of fillable pixels
int minX = p[0];

while(minX > 0)
{
bitmap.getPixel(Point(minX,p[1]),pixel);

if(pixel != toFill)
break;
else --minX;
}

int lines[] = { p[1] - 1, p[1]+1 };

for(int line = 0;line < 2; ++line)
{
int y = lines[line];

if( (y>=0) && (y<int(bitmap.getHeight())) )
{
bool activeInterval = false;

for(int x=minX;x<int(bitmap.getWidth());++x)
{
bitmap.getPixel(Point(minX,p[1]),pixel);

if(pixel != toFill)
break;

bitmap.getPixel(Point(minX,p[1]),pixel);

if(pixel == toFill)
{
if(!activeInterval)
{
stack.push(Point(x,y));
activeInterval = true;
}
}
else
{
activeInterval = false;
}
}
}
}
fill_interval(bitmap,p[0],p[1],color,toFill);
++iteration;
}
}
while(!stack.empty() && (iteration < maxIterations));
}




Share this post


Link to post
Share on other sites
Here's another algorithm. I think it's actually called sweep fill. It uses a 1-bit-per-pixel temporary buffer to keep track of what it's filled so far, and does repetitive sweeps filling up and left, then up and right, down/left, down/right, until nothing changes and then it's done.

Note: "pitch" is the number of bytes per row for the buffers, "width" is the logical width of the image it stores (usually they're the same thing)

#define BIT(x) (1 << (x))

void FloodFill(u8 *dest, u32 destWidth, u32 destHeight, u32 destPitch, u8xy start, u32 color)
{
u32 targetColor = dest[start.x + start.y * destPitch];
u32 *mask;
u32 maskPitch = (destPitch + 31) & ~31;
int iteration, x, y, xStart, yStart, xEnd, yEnd, xInc, yInc;
bool changed = true;

if (targetColor == color)
{
return;
}

mask = (u32*)malloc(maskPitch * destHeight / 8);
memset(mask, 0, maskPitch * destHeight / 8);

dest[start.y * destPitch + start.x] = color;
mask[(start.y * maskPitch + start.x) >> 5] |= BIT(start.x & 31);

while(changed)
{
changed = false;

for (iteration = 0; iteration < 4; iteration++)
{
if (iteration & BIT(0))
xStart = destWidth - 1, xEnd = -1, xInc = -1;
else
xStart = 0, xEnd = destWidth, xInc = 1;

if (iteration & BIT(1))
yStart = destHeight - 1, yEnd = -1, yInc = -1;
else
yStart = 0, yEnd = destHeight, yInc = 1;

for (y = yStart; y != yEnd; y += yInc)
{
for (x = xStart; x != xEnd; x += xInc)
{
if (mask[(y * maskPitch + x) >> 5] & BIT(x & 31))
{
int i;

for (i = x + xInc; i != xEnd && dest[y * destPitch + i] == targetColor; i += xInc)
{
dest[y * destPitch + i] = color;
mask[(y * maskPitch + i) >> 5] |= BIT(i & 31);
changed = true;
}
for (i = y + yInc; i != yEnd && dest[i * destPitch + x] == targetColor; i += yInc)
{
dest[i * destPitch + x] = color;
mask[(i * maskPitch + x) >> 5] |= BIT(x & 31);
changed = true;
}
}
}
}
}
}

free(mask);
}

Share this post


Link to post
Share on other sites
Before you start trying new algorithms you should step through yours with a debugger and find out exactly what's causing it to crash.

Recursiveness by itself doesn't cause a crash. Unending recursion could but you can't prove that's the problem just by commenting out the recursive call.

Share this post


Link to post
Share on other sites
It's an interesting contained little problem, that of filling a surface with a colour. Personally whenever I see a pointer to some unstructured data I'm inclined to sin and fall back on 'Good Ole C' routines like memcpy and suchlike just because I can't write code that's faster than hand optimised assembly without using SIMD or parallel processing cheats.

I suppose it's one of those.. How fast do you need it to go? If you're doing it every frame then I'd suggest that's a little too often but never the less you want it to be as fast as can be.

Lawl_Rock, your algorithm doesn't necessarily need to be recursive, in fact the overhead of the function call is probably negating any speed up you'd assume would come with the coolness of finding a use for recursive functions :-) You're more likely to get better performance just setting up a nested loop and iterating over the whole data array.

Trace through the function in your debugger to get a better idea of how it's behaving and why it's crashing. Debugging is an art in itself.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!