Problem with Flood Fill algorithm

Forums Programming cocos2d support (graphics engine) Problem with Flood Fill algorithm

This topic contains 13 replies, has 9 voices, and was last updated by  daylord 9 months, 2 weeks ago.

Viewing 14 posts - 1 through 14 (of 14 total)
Author Posts
Author Posts
December 9, 2011 at 1:17 pm #237561

DaProd
Participant
@daprod

Hi,

I’m programming a multiple games app and I have troubles implementing the coloring game. I’m trying to use the Flood Fill algorithm but I can’t figure out how to prepare all my variables. I tried to create a bitmap context, draw the image into, call my flood fill algorithm and update my sprite image.

Here is my code so far :

CGImageRef imageRef = [[self convertSpriteToImage:mySprite] CGImage];

// Create off screen bitmap context to draw the image into. Format ARGB is 4 bytes for each pixel: Alpa, Red, Green, Blue.

CGContextRef cgctx = [self createARGBBitmapContextFromImage:imageRef];

size_t w = CGImageGetWidth(imageRef);

size_t h = CGImageGetHeight(imageRef);

CGRect rect = {{0,0},{w,h}};

// Draw the image to the bitmap context. Once we draw, the memory

// allocated for the context for rendering will then contain the

// raw image data in the specified color space.

CGContextDrawImage(cgctx, rect, imageRef);

// Now we can get a pointer to the image data associated with the bitmap

// context.

unsigned char* data = CGBitmapContextGetData (cgctx);

CGPoint pointOnimage = [mySprite boundingBox].origin;

pointOnimage = ccp(pointOnimage.x,[mySprite boundingBox].size.height + pointOnimage.y);

pointOnimage = [[CCDirector sharedDirector] convertToUI:pointOnimage];

pointOnimage = CGPointMake(location.x – pointOnimage.x, location.y – pointOnimage.y);

NSLog(@”%f %f”, pointOnimage.x, pointOnimage.y);

color myColor = {255,255,255,255};

color myColor2 = {255,0,0,255};

//[FloodFill floodfillX:pointOnimage.x Y:pointOnimage.y image:data width:w height:h origIntColor:[FloodFill getRGBIntFromColor:myColor] replacementIntColor:[FloodFill getRGBIntFromColor:myColor2]];

CGImageRef imRef = CGBitmapContextCreateImage(cgctx);

CCTexture2D *texture = CCTexture2D alloc] initWithImage:[UIImage imageWithCGImage:imRef;

[mySprite setTexture: texture];

First of all, I wanted to check if my context was ok, I commented out the flood fill call and see if my image is still the same …. but it’s not. I have a blank sprite with pieces of my sprite in the top and bottom right corner.

What am I doing wrong ? Any idea is welcome because I’m pretty lost right now.

Thanks

December 9, 2011 at 10:03 pm #358240

Jeston
@rhapsodus

Hey DaProd,

I made about 10 coloring book apps that are on the itunes store and sorry if some of this code contains irrelevant timers and bools but the necessary parts should be here. I figured I would share how I did the flood fill as I got a lot of help with filling a texture using CCMutableTexture2D authored by Lam Hoang Pham also posted in the forums here….

First off I created a CCMutableTexture2D from a UIImage when my drawing layer is shown:

ColoringImage = [[UIImage alloc] initWithContentsOfFile:file];
[CCTexture2D setDefaultAlphaPixelFormat:kCCTexture2DPixelFormat_RGBA8888];
ColoringTexture = [[CCMutableTexture2D alloc] initWithImage:ColoringImage];

And below is the actual flood fill, which is done in a few steps, first it prepares the image by setting a 2d

array of bools to not checked. Then on the touchesEnded, adds the color and pixel to a Queue which will be

calling linear fill on the update. The linear fill scans horizontally and all the neighbors for a positive color change and sets the pixels with the newColor adding all neighbors to the Queue as well and marks it dirty.

You could do the whole image at once, but I found it better to watch the fill animate and is more responsive.

-(void)tick:(ccTime)dt
{
NoMoveTimer -= (float)dt;
NoFillTimer -= (float)dt;

if( lastUpdate <= 0 )
{
int count = 0;

while( [PixelQueue count] > 0 && count < 30)
{
ccRange range;
[[PixelQueue objectAtIndex:0] getValue:&range];
[PixelQueue removeObjectAtIndex:0];

int upY = range.Y - 1;
int downY = range.Y +1;
for( int i = range.Start; i<= range.End; i++ )
{

if( range.Y > 0 && !PixelsChecked[upY])
{
ccColor4B pixel = [ColoringTexture pixelAt:ccp(i,upY)];
if( [self CheckPixel:pixel] )
{
[self LinearFill: i : upY];
}
}

if( range.Y < [ColoringSprite contentSize].height-1 && !PixelsChecked
[downY])
{
ccColor4B pixel = [ColoringTexture pixelAt:ccp(i,downY)];
if( [self CheckPixel:pixel] )
{
[self LinearFill: i : downY];

}
}
}

count++;
}

if( count > 0 )
{
[ColoringTexture apply];
ColoringSprite.dirty = YES;
}
}

}

-(void) LinearFill: (int) startX : (int) startY
{
//**********************************************************************
// Scan left
//**********************************************************************
int lFillLoc = startX;
while (true)
{
[ColoringTexture setPixelAt:ccp(lFillLoc,startY) rgba:TargetColor];
PixelsChecked[lFillLoc][startY] = YES;
lFillLoc--;

if( lFillLoc < 0 )
{
break;
}

if( PixelsChecked[lFillLoc][startY] )
{
break;
}

ccColor4B pixel = [ColoringTexture pixelAt:ccp(lFillLoc,startY)];
if(![self CheckPixel:pixel])
{
break;
}
}
lFillLoc++;

//**********************************************************************
// Scan right
//**********************************************************************
int rFillLoc = startX;
while (true)
{
[ColoringTexture setPixelAt:ccp(rFillLoc,startY) rgba:TargetColor];
PixelsChecked[rFillLoc][startY] = YES;
rFillLoc++;

if( rFillLoc >= [ColoringSprite contentSize].width )
{
break;
}

if( PixelsChecked[rFillLoc][startY] )
{
break;
}

ccColor4B pixel = [ColoringTexture pixelAt:ccp(rFillLoc,startY)];
if(![self CheckPixel:pixel] )
{
break;
}
}
rFillLoc--;

//add range to queue
ccRange range = ccr( lFillLoc, rFillLoc, startY);
NSValue* val = [NSValue value:&range withObjCType:@encode(ccRange)];
[PixelQueue addObject:val];
}

-(Boolean) CheckPixel: (ccColor4B)pixelA
{
if( pixelA.r == StartingColor.r &&
pixelA.g == StartingColor.g &&
pixelA.b == StartingColor.b )
{
return YES;
}

return NO;
}

-(void)FloodFillTexture :(CGPoint) UvTxtCoord
{
int x = UvTxtCoord.x;
int y = UvTxtCoord.y;

StartingColor = [ColoringTexture pixelAt:ccp(x,y)];
if (StartingColor.r == 0 && StartingColor.g == 0 && StartingColor.b == 0 )
{
return;
}

[self PrepareFill];
[self LinearFill: x : y];
}

//******************************************************
// Prepare linear queue algorithm
//******************************************************
-(void)PrepareFill
{
[[SimpleAudioEngine sharedEngine] playEffect:@"ColorPlopped.wav"];
while( [PixelQueue count] > 0 )
{
[PixelQueue removeObjectAtIndex:0];
}

int mw = [ColoringSprite contentSize].width;
int mh = [ColoringSprite contentSize].height;
for( int i = 0; i<mw; i++ )
{
for( int j = 0; j<mh; j++ )
{
PixelsChecked
[j] = NO;
}
}
}

To actually being the flood fill, on touches ended I did this:

int pixelX = 0;
int pixelY = 0;

int width = [ColoringSprite contentSize].width * ColoringSprite.scaleX;
int height = [ColoringSprite contentSize].height * ColoringSprite.scaleY;

int rightX = ColoringSprite.position.x + width/2;
int leftX = ColoringSprite.position.x - width/2;
int topY = ColoringSprite.position.y + height/2;
int bottomY = ColoringSprite.position.y - height/2;

if ( (WolrdLoc.x < leftX || WolrdLoc.x > rightX) || (WolrdLoc.y < bottomY || WolrdLoc.y > topY ) )
{

}
else
{
if( WolrdLoc.x > leftX && WolrdLoc.x <= rightX)
{
int nx = WolrdLoc.x - leftX;
pixelX = (int)((float)nx/(float)ColoringSprite.scaleX);
}

if( WolrdLoc.y > bottomY && WolrdLoc.y <= topY)
{
int ny = topY - WolrdLoc.y;
pixelY = (int)((float)ny/(float)ColoringSprite.scaleY);
}

ccColor4B col = ccc4( Colors[SelectedCrayon].r,
Colors[SelectedCrayon].g,
Colors[SelectedCrayon].b,
255 );

if( [PixelQueue count] == 0 )
{
TargetColor = col;
if( TargetColor.r <= 15 && TargetColor.g <= 15 && TargetColor.b <= 15 )
{
NSLog(@"COLOR FILTER HIT");
TargetColor = ccc4(20,15,15,255);
}
if( EraserPushed )
{
TargetColor = ccc4(255, 255, 255, 255);

}
[self FloodFillTexture: ccp(pixelX, pixelY)];
[ColoringTexture apply];
ColoringSprite.dirty = YES;
}
}

And some of the helper structs like range are below:

typedef struct _ccRange
{
int Start;
int End;
int Y;
} ccRange;

static inline ccRange
ccr(const int start, const int end, const int y)
{
ccRange c = {start, end, y};
return c;
}

//******************************************************
// Layer for drawing screen
//******************************************************
@interface DrawingLayer : CCLayer {}
Boolean PixelsChecked[MaxImageDimension][MaxImageDimension];
CCMutableTexture2D* ColoringTexture;
NSMutableArray* PixelQueue;

Hopefully that helps,

~J

December 10, 2011 at 1:25 pm #358241

DaProd
Participant
@daprod

Thank you a lot for sharing this code Jeston. It’s working great !

December 11, 2011 at 12:34 am #358242

ccastro
Participant
@ccastro

Hello Jeston,

Yesterday I finished a Flood Fill for iPad, but I’m not using cocos2d (I’m learning cocos2d yet).

My problem is the time, 5s to fill 768 x 1024.

Do you know how many sec does you take to 768×1024?

thx,

Claudio

December 12, 2011 at 9:37 pm #358243

Jeston
@rhapsodus

CCastro there are several types of fill algorithms, and others are in O ( n ) time, but something like a recursive neighbor fill would be horribly ineficient and very slow.

You can find a few here: http://en.wikipedia.org/wiki/Flood_fill

There are other tricks you can do like not processing the entire flood fill within the same frame which is what I did.

January 17, 2012 at 11:00 pm #358244

Jbrownie77
@jbrownie77

ccastro,

I am also working on implementing a flood fill and am determining whether to do it with or without cocos2d.

I’m wondering if I could compare your non-cocos2d implementation with mine to see where I am getting hung up.

-JB

March 9, 2012 at 10:44 am #358245

DaProd
Participant
@daprod

Hey Jeston, I come back here because I have issues with retina display. It appears there is a scale problem in your code but I can’t find out where. Any idea ?

March 27, 2012 at 7:50 am #358246

zuil7
@zuil7

Hi All can you share some sample on flood fill? Thanks!

March 29, 2012 at 3:58 pm #358247

DaProd
Participant
@daprod

Jeston code is working perfectly, just follow his instructions. I had to make couples modifications to have it working on my game.

Here is how I call it :

int pixelX = 0;

int pixelY = 0;

//NSLog(@”%f”,decors.scaleX);

int width = [decors contentSize].width * decors.scaleX;

int height = [decors contentSize].height * decors.scaleY;

//NSLog(@”%f %f”, [decors contentSize].width, decors.scaleX);

int rightX = decors.position.x + width/2;

int leftX = decors.position.x – width/2;

int topY = decors.position.y + height/2;

int bottomY = decors.position.y – height/2;

if( location.x > leftX && location.x <= rightX)

{

int nx = location.x – leftX;

pixelX = (int)((float)nx/(float)decors.scaleX);

}

if( location.y > bottomY && location.y <= topY)

{

int ny = topY – location.y;

pixelY = (int)((float)ny/(float)decors.scaleY);

}

if( [PixelQueue count] == 0 )

{

TargetColor = tempColor;

if( TargetColor.r <= 15 && TargetColor.g <= 15 && TargetColor.b <= 15 )

{

//NSLog(@”COLOR FILTER HIT”);

TargetColor = ccc4(20,15,15,255);

}

[GameSoundManager playGlisse];

pixelX *= myScale;

pixelY *= myScale;

[self FloodFillTexture: ccp(pixelX, pixelY)];

[ColoringTexture apply];

decors.dirty = YES;

}

where myScale is :

if( [UIScreen instancesRespondToSelector:@selector(scale)] )

myScale = [[UIScreen mainScreen] scale];

else

myScale = 1.0;

You can figure out how to make it working I think with that. Come back if not, i’ll try to explain you.

DaProd.

March 30, 2012 at 7:42 pm #358248

iNinja
@ininja

Hello there.

I took Jeston’s code, applied some optimizations (replaced NSMutableArray with a C stack, for instance) and got it to run at 20% faster.

I’ve also synthesized the code into a CCSprite subclass that you can instantiate by passing a UIImage and then just passing a point and a color for it to apply the flood fill.

I’ve uploaded the code to https://github.com/iNinja/CCSpriteFloodFill in case you want to check it / fork it / make it better.

Hope this helps !

April 5, 2012 at 1:22 pm #358249

jojeex2
@jojeex2

Hello iNinja

thanks a Million for the code,

thanks a ton for all those who contributed.

thanks and appreciation:))))

May 26, 2012 at 11:45 am #358250

daylord
Participant
@daylord

Hi… It works really great. But it works on only 1024*768 images, if i use other sized images it’s not working!

May i know the reason behind this?

Thanks!

July 21, 2012 at 1:46 pm #358251

mhynson
@mhynson

daylord,

I think it has to do something with the way that pixelsChecked is defined in CCSpriteFloodFill.h. I’m not sure how to change those values dynamically, though

July 12, 2013 at 12:19 am #407678

daylord
Participant
@daylord

It’s leaving the borders without filling. Anyone got this problem?

Viewing 14 posts - 1 through 14 (of 14 total)

You must be logged in to reply to this topic.