Flood filling in iPad too slow

I am using flood Filling for one of my coloring apps on iPad.

The app basically fills color within the black line of the image and I am able to do this with no problem, but it's too slow.

I first used recursive flood fill and its performance is the worst (due to Stack Overflow), then I was able to convert it to iterative using Stack with the following code but this is too slow

-(void)floodFillAtPoint:(CGPoint)atPoint
 {
Stack *stack = [[Stack alloc] init];

[stack push:[StackPoint pointWithPoint:atPoint]];
StackPoint *currentPoint = nil;
int counter = 0;
while ((currentPoint = [stack pop])) 
{
    CGPoint aPoint = currentPoint.point;//CGPointMake(pointPixel.x, pointPixel.y);
    [self setColorAtPoint:aPoint];
    CGPoint bPoint = aPoint;
    bPoint.x+=1;
    if([self checkForValidRegionAtPoint:bPoint])
        [stack push:[StackPoint pointWithPoint:bPoint]];
    bPoint = aPoint;
    bPoint.x-=1;
    if([self checkForValidRegionAtPoint:bPoint])
        [stack push:[StackPoint pointWithPoint:bPoin开发者_运维知识库t]];
    bPoint = aPoint;
    bPoint.y+=1;
    if([self checkForValidRegionAtPoint:bPoint])
        [stack push:[StackPoint pointWithPoint:bPoint]];
    bPoint = aPoint;
    bPoint.y-=1;
    if([self checkForValidRegionAtPoint:bPoint])
        [stack push:[StackPoint pointWithPoint:bPoint]];        
    counter++;
}
[stack release];

}

Would anyone suggest an alternative method which works best on iPad device?

---

Using an Objective-C object to represent each and every pixel is going to be extremely slow and add little benefit.

Use a different data structure to represent your bitmap, like one of the various CG* bitmap encapsulation mechanisms. Then twiddle the bits in the bitmap directly. It'll be tons and tons faster.

---

(Posted solution on behalf of the question author)_.

I finally managed to make an acceptable floodfill for iPhone/iPad with following class. Please excuse if any zombie code :). Suggestions for improvement always welcome.

How to use

Create the CanvasView Object and set the originalImage (this should be the uncolored/colored image with black lines and the area outside the black lines must be clear color) and you can access the coloredImage for the image after paint.

The .h file

#import <UIKit/UIKit.h>
#import "SoundEngine.h"

struct  COLOR {
    unsigned char red;
    unsigned char green;
    unsigned char blue;
    unsigned char alpha;
};

typedef struct COLOR COLOR;

@interface CanvasView : UIView {
    UIImage *originalImage;
    UIImage *coloredImage;
    int selectedColor;
    BOOL shouldShowOriginalImage;

    UIImageView *imageView;
    BOOL isImageDataFreed;

    unsigned char red;
    unsigned char green;
    unsigned char blue;
    unsigned char alpha1;
    int loopCounter;
    NSMutableArray *pixelDataArray;
    BOOL isFilling;
    BOOL hasColored;
    id delegate;
    CGPoint restartPoint;

    BOOL fillAtPoint;
    CGPoint currentTouchPoint;
    int regionCount;
    NSTimer *floadFillTimer;
}

@property (nonatomic, retain) UIImage *coloredImage;
@property (nonatomic, retain) UIImage *originalImage;
@property (nonatomic, retain) NSMutableArray *pixelDataArray;
@property (nonatomic, assign) id delegate;
@property (nonatomic, assign) BOOL shouldShowOriginalImage;
@property (nonatomic, assign) BOOL hasColored;
@property (assign) int regionCount;

-(void)toggleImage;
-(void)setColor:(int)colorIndex;
-(void)freeImageData;
-(CGColorRef)getColorForIndex:(int)index;
-(void)initializeCanvas;
-(void)prepareImageData;
-(void)setColorForColoring;
@end

And the .m file

#import "CanvasView.h"
#import "PaintGame.h"
#import "Color.h"
#import "FarvespilletAppDelegate.h"
#import "Stack.h"
#import "Point.h"


@implementation CanvasView
@synthesize coloredImage,originalImage,pixelDataArray,delegate,shouldShowOriginalImage,hasColored;
@synthesize regionCount;

unsigned char *imageRawData;

-(COLOR)getPixelColorAtIndex:(CGPoint)atPoint
{
    COLOR aColor;

    aColor.red = 0;
    aColor.green = 0;
    aColor.blue = 0;
    aColor.alpha = 0;
    NSUInteger width = self.frame.size.width;
    NSUInteger height = self.frame.size.height;
    NSUInteger bytesPerRow = 4 * width;
    long int byteIndex = (bytesPerRow * ((NSUInteger)atPoint.y-1)) + (NSUInteger)atPoint.x*4;
    if((height * width * 4)<=byteIndex)
        return aColor;
    @try {
        aColor.red = imageRawData[byteIndex];
        aColor.green = imageRawData[byteIndex+1];
        aColor.blue = imageRawData[byteIndex+2];
        aColor.alpha = imageRawData[byteIndex+3];
    }
    @catch (NSException * e) {
        NSLog(@"%@",e);
    }
    @finally {

    }


    return aColor;
}

-(void)setPixelColorAtPoint:(CGPoint)atPoint color:(COLOR)acolor
{
    NSUInteger width = self.frame.size.width;
    NSUInteger height = self.frame.size.height;
    NSUInteger bytesPerRow = 4 * width;
    long int byteIndex = (bytesPerRow * ((NSUInteger)atPoint.y-1)) + (NSUInteger)atPoint.x*4;
    if((height * width * 4)<=byteIndex)
        return;
    @try {
        imageRawData[byteIndex] = acolor.red;
        imageRawData[byteIndex+1] = acolor.green;
        imageRawData[byteIndex+2] = acolor.blue;
        imageRawData[byteIndex+3] = acolor.alpha;
    }
    @catch (NSException * e) {
        NSLog(@"%@",e);
    }
    @finally {

    }

}

-(void)initializeCanvas
{
    imageView = [[UIImageView alloc] initWithFrame:self.bounds];
    [self addSubview:imageView];
    self.backgroundColor = [UIColor clearColor];
    [imageView release];
    isImageDataFreed = YES; 
    isFilling = NO;
}

- (id)initWithFrame:(CGRect)frame {

    self = [super initWithFrame:frame];
    if (self) {
        // Initialization code.
        [self initializeCanvas];
    }
    return self;
}


// Only override drawRect: if you perform custom drawing.
// An empty implementation adversely affects performance during animation.
- (void)drawRect:(CGRect)rect {
    // Drawing code.
    if(!imageRawData)
        [self prepareImageData];
    if(shouldShowOriginalImage)
        imageView.image = originalImage;
    else
        imageView.image = coloredImage;
}


- (void)dealloc {
    [super dealloc];
    [originalImage release];
    [coloredImage release];
    [pixelDataArray release];
}


-(BOOL)isColorStandardForRed:(unsigned char)__red green:(unsigned char)__green blue:(unsigned char)__blue
{
    if(0 == __red && 0 == __green && 0 == __blue)
        return NO;
    else
        return YES;
}

-(BOOL)checkForValidRegionAtPoint:(CGPoint)touchPoint
{
    COLOR colorAtPoint = [self getPixelColorAtIndex:touchPoint];
    loopCounter++;
    unsigned char _red   = colorAtPoint.red;
    unsigned char _green = colorAtPoint.green;
    unsigned char _blue  = colorAtPoint.blue;
    unsigned char _alpha1 = colorAtPoint.alpha;

    if(touchPoint.x <= 0 || touchPoint.y <= 0 || touchPoint.x >= self.frame.size.width ||touchPoint.y >= self.frame.size.height)
        return NO;
    if(red == _red && green == _green && blue == _blue && alpha1 == _alpha1)
        return NO;
    if(_alpha1 <= 225)
        return NO;
    if(_red <= 50 && _green <= 50 && _blue <= 50 && _alpha1 == 255)
        return NO;
    if(!([self isColorStandardForRed:_red green:_green blue:_blue]))
        return NO;
    return YES;
}

-(void)setColorAtPoint:(CGPoint)atPoint
{
    //loopCounter++;
    COLOR aColor;
    aColor.red = red;
    aColor.green = green;
    aColor.blue = blue;
    aColor.alpha = alpha1;

    [self setPixelColorAtPoint:atPoint color:aColor];
}

-(void)prepareImageData
{
    if(!imageRawData)
    {
        CGImageRef imageRef = [coloredImage CGImage];
        NSUInteger bytesPerPixel = 4;
        NSUInteger width = self.frame.size.width;
        NSUInteger height = self.frame.size.height;//CGImageGetHeight(imageRef);
        CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB();

        NSUInteger bytesPerRow = bytesPerPixel * width;
        NSUInteger bitsPerComponent = 8;
        imageRawData = malloc(height * width * 4);
        CGContextRef context = CGBitmapContextCreate(imageRawData, width, height,
                                                     bitsPerComponent, bytesPerRow, colorSpace,
                                                     kCGImageAlphaPremultipliedLast);
        CGColorSpaceRelease(colorSpace);
        CGContextDrawImage(context, CGRectMake(0, 0, width, height), imageRef);
        CGContextRelease(context);
    }
}

-(void)cleanUpImageData
{
    NSUInteger bytesPerPixel = 4;
    NSUInteger width = self.frame.size.width;
    CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB();
    NSUInteger bytesPerRow = bytesPerPixel * width;
    CGContextRef ctx = CGBitmapContextCreate(imageRawData,  
                                             self.frame.size.width,  
                                             self.frame.size.height,  
                                             8,  
                                             bytesPerRow,  
                                             colorSpace,  
                                             kCGImageAlphaPremultipliedLast);  
    CGImageRef newImageRef = CGBitmapContextCreateImage(ctx);  
    CGContextRelease(ctx);
    self.coloredImage = [UIImage imageWithCGImage:newImageRef];  
    CGImageRelease(newImageRef);
}

-(void)refreshImage
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    [self cleanUpImageData];
    imageView.image = coloredImage;
    [pool release];
}


typedef struct queue_ { struct queue_ *next; } queue_t;
typedef struct ffnode_ { queue_t node; int x, y; } ffnode_t;

/* returns the new head of the queue after adding node to the queue */
queue_t* enqueue(queue_t *queue, queue_t *node) {
    if (node) {
        if(!queue)
            return node;
        queue_t *temp = queue; 
        while(temp->next)
            temp = temp->next;
        temp->next = node;

       // node->next = queue;
        return queue;
    }
    return NULL;
}

/* returns the head of the queue and modifies queue to be the new head */
queue_t* dequeue(queue_t **queue) {
    if (queue) {
        queue_t *node = (*queue);
        if(node)
        {
            (*queue) = node->next;
            node->next = NULL;
            return node;   
        }
    }
    return NULL;
}

ffnode_t* new_ffnode(int x, int y) {
    ffnode_t *node = (ffnode_t*)malloc(sizeof(ffnode_t));
    node->x = x; node->y = y;
    node->node.next = NULL;
    return node;
}

-(void)floodFillAtPoint:(CGPoint)atPoint shouldRefresh:(BOOL)refresh
{

    queue_t *head = NULL;
    ffnode_t *node = NULL;

    node = new_ffnode(atPoint.x, atPoint.y);
    head = enqueue(head, &node->node);
    long int counter = 0;
    [self setColorAtPoint:atPoint];

    while((node = (ffnode_t*)dequeue(&head))) 
    {
        counter++;
        CGPoint aPoint = CGPointMake(node->x, node->y);
        free(node);
        CGPoint bPoint = aPoint;
        bPoint.x+=1;
        if([self checkForValidRegionAtPoint:bPoint])
        {
            ffnode_t *node1 = new_ffnode(bPoint.x, bPoint.y); 
            head = enqueue(head, &node1->node);
            [self setColorAtPoint:bPoint];
        }
        bPoint = aPoint;
        bPoint.x-=1;
        if([self checkForValidRegionAtPoint:bPoint])
        {
            ffnode_t *node1 = new_ffnode(bPoint.x, bPoint.y); 
            head = enqueue(head, &node1->node);
            [self setColorAtPoint:bPoint];
        }       
        bPoint = aPoint;
        bPoint.y+=1;
        if([self checkForValidRegionAtPoint:bPoint])
        {
            ffnode_t *node1 = new_ffnode(bPoint.x, bPoint.y); 
            head = enqueue(head, &node1->node);
            [self setColorAtPoint:bPoint];
        }
        bPoint = aPoint;
        bPoint.y-=1;
        if([self checkForValidRegionAtPoint:bPoint])
        {
            ffnode_t *node1 = new_ffnode(bPoint.x, bPoint.y); 
            head = enqueue(head, &node1->node);
            [self setColorAtPoint:bPoint];
        }
    }
    if(refresh)
        [self performSelectorOnMainThread:@selector(shouldRefresh) withObject:nil waitUntilDone:YES];    
}


-(void)shouldRefresh
{
    self.regionCount += 1;
    //To detect if all the region/thread are completed; if YES then notify the delegate
    if(regionCount==9)
    {
        [floadFillTimer invalidate];
        isFilling = NO;
        [delegate fillingStateChanged:isFilling];
    }
    [self cleanUpImageData];
    imageView.image = coloredImage;
}

-(void)floodFillInBackGroundAtPoint:(StackPoint*)point
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    [self floodFillAtPoint:point.point shouldRefresh:YES];
    [pool release];
}

-(void)floodFillInBackGroundAtPointWithRefresh:(StackPoint*)point
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    [self floodFillAtPoint:point.point shouldRefresh:YES];
    [pool release];
}

-(void)initiateFloodFillAtPoint:(CGPoint)touchPoint
{
    loopCounter = 0;
    isFilling = YES;
    [delegate fillingStateChanged:isFilling];
    hasColored = YES;
    regionCount = 0;

    floadFillTimer = [NSTimer timerWithTimeInterval:0.1 target:self selector:@selector(refreshImage) userInfo:nil repeats:YES];
    [[NSRunLoop mainRunLoop] addTimer:floadFillTimer forMode:NSDefaultRunLoopMode];
    StackPoint *stackPoint = [StackPoint pointWithPoint:touchPoint];

    CGPoint floodPoint = touchPoint;

    while ([self checkForValidRegionAtPoint:floodPoint])
    {
        floodPoint.x++;
    }
    floodPoint.x--;
    StackPoint *stackPoint1 = [StackPoint pointWithPoint:floodPoint];

    floodPoint = touchPoint;
    while ([self checkForValidRegionAtPoint:floodPoint])
    {
        floodPoint.x--;
    }
    floodPoint.x++;
    StackPoint * stackPoint2 = [StackPoint pointWithPoint:floodPoint];
    floodPoint = touchPoint;
    while ([self checkForValidRegionAtPoint:floodPoint])
    {
        floodPoint.y++;
    }
    floodPoint.y--;
    StackPoint *stackPoint3 = [StackPoint pointWithPoint:floodPoint];
    floodPoint = touchPoint;
    while ([self checkForValidRegionAtPoint:floodPoint])
    {
        floodPoint.y++;
    }
    floodPoint.y--;
    StackPoint *stackPoint4 = [StackPoint pointWithPoint:floodPoint];


    floodPoint = touchPoint;

    while ([self checkForValidRegionAtPoint:floodPoint])
    {
        floodPoint.x++;
        floodPoint.y++;
    }
    floodPoint.x--;
    floodPoint.y--;
    StackPoint *stackPoint5 = [StackPoint pointWithPoint:floodPoint];

    floodPoint = touchPoint;
    while ([self checkForValidRegionAtPoint:floodPoint])
    {
        floodPoint.x--;
        floodPoint.y--;
    }
    floodPoint.x++;
    floodPoint.y++;
    StackPoint * stackPoint6 = [StackPoint pointWithPoint:floodPoint];
    floodPoint = touchPoint;
    while ([self checkForValidRegionAtPoint:floodPoint])
    {
        floodPoint.x++;
        floodPoint.y--;
    }
    floodPoint.x--;
    floodPoint.y++;
    StackPoint *stackPoint7 = [StackPoint pointWithPoint:floodPoint];
    floodPoint = touchPoint;
    while ([self checkForValidRegionAtPoint:floodPoint])
    {
        floodPoint.x--;
        floodPoint.y++;
    }
    floodPoint.x++;
    floodPoint.y--;
    StackPoint *stackPoint8 = [StackPoint pointWithPoint:floodPoint];


    [self performSelectorInBackground:@selector(floodFillInBackGroundAtPoint:) withObject:stackPoint];
    [self performSelectorInBackground:@selector(floodFillInBackGroundAtPoint:) withObject:stackPoint];    
    [self performSelectorInBackground:@selector(floodFillInBackGroundAtPoint:) withObject:stackPoint1];
    [self performSelectorInBackground:@selector(floodFillInBackGroundAtPoint:) withObject:stackPoint2];
    [self performSelectorInBackground:@selector(floodFillInBackGroundAtPoint:) withObject:stackPoint3];
    [self performSelectorInBackground:@selector(floodFillInBackGroundAtPoint:) withObject:stackPoint4];
    [self performSelectorInBackground:@selector(floodFillInBackGroundAtPoint:) withObject:stackPoint5];
    [self performSelectorInBackground:@selector(floodFillInBackGroundAtPoint:) withObject:stackPoint6];
    [self performSelectorInBackground:@selector(floodFillInBackGroundAtPoint:) withObject:stackPoint7];
    [self performSelectorInBackground:@selector(floodFillInBackGroundAtPoint:) withObject:stackPoint8];
}

-(void)touchesMoved:(NSSet *)touches withEvent:(UIEvent *)event
{
    UITouch *aTouch = [touches anyObject];
    CGPoint aPoint = [aTouch locationInView:imageView];
    [self setColorForColoring];
    //This will toggle from uncolored state to colored state, also resets the colored image
    if(shouldShowOriginalImage)
    {
        self.coloredImage = originalImage;
        shouldShowOriginalImage = !shouldShowOriginalImage;
        [self freeImageData];
        [self prepareImageData];
        [delegate coloringStarted];
    }
    if([self checkForValidRegionAtPoint:aPoint] && !isFilling)
    {
        [self setColorForColoring];
        self.userInteractionEnabled = NO;
        [self initiateFloodFillAtPoint:aPoint];
        self.userInteractionEnabled = YES;
        NSString *fileName = [NSString stringWithFormat:@"splat%d",(rand()%10)+1];
        [[SoundEngine sharedSoundEngine] playSoundWithFileName:fileName delegate:nil];
    }
}

-(void)touchesEnded:(NSSet *)touches withEvent:(UIEvent *)event
{
    UITouch *aTouch = [touches anyObject];
    CGPoint aPoint = [aTouch locationInView:self];
    [self setColorForColoring];
    //This will toggle from uncolored state to colored state, also resets the colored image
    if(shouldShowOriginalImage)
    {
        self.coloredImage = originalImage;
        shouldShowOriginalImage = !shouldShowOriginalImage;
        [self freeImageData];
        [self prepareImageData];
        [delegate coloringStarted];
    }
    if([self checkForValidRegionAtPoint:aPoint] && !isFilling)
    {
        [self setColorForColoring];
        self.userInteractionEnabled = NO;
        [self initiateFloodFillAtPoint:aPoint];
        self.userInteractionEnabled = YES;
        NSString *fileName = [NSString stringWithFormat:@"splat%d",(rand()%10)+1];
        [[SoundEngine sharedSoundEngine] playSoundWithFileName:fileName delegate:nil];
//        [self cleanUpImageData];
//        [self setNeedsDisplay];
    }

}

-(void)toggleImage
{
    shouldShowOriginalImage = !shouldShowOriginalImage;
    [self setNeedsDisplay];
}

-(void)setColorForColoring
{
    const CGFloat *colorComponents = CGColorGetComponents([self getColorForIndex:selectedColor]);
    red   =  (unsigned char)(colorComponents[0]*255);
    green =  (unsigned char)(colorComponents[1]*255);
    blue  = (unsigned char)(colorComponents[2]*255);
    alpha1 = (unsigned char)(CGColorGetAlpha([self getColorForIndex:selectedColor])*255);
}


-(void)setColor:(int)colorIndex
{
    selectedColor = colorIndex;
    //const CGFloat *colorComponents = CGColorGetComponents([self getColorForIndex:selectedColor]);
//  red   =  (unsigned char)(colorComponents[0]*255);
//  green =  (unsigned char)(colorComponents[1]*255);
//  blue  = (unsigned char)(colorComponents[2]*255);
//  alpha1 = (unsigned char)(CGColorGetAlpha([self getColorForIndex:selectedColor])*255);
}

-(void)cleanBuffer
{
    if(imageRawData)
    {
        int width = self.frame.size.width;
        int height = self.frame.size.height;
        int byteIndex = 0;
        for (int ii = 0 ; ii < (width*height*4) ; ++ii)
        {
            imageRawData[byteIndex] = 0;
            imageRawData[byteIndex + 1] = 0;
            imageRawData[byteIndex + 2] = 0;
            imageRawData[byteIndex + 3] = 255;
        }           
    }
}

-(void)freeImageData
{
    self.pixelDataArray = nil;
    free(imageRawData);
    imageRawData = NULL;
}

-(CGColorRef)getColorForIndex:(int)index
{
    switch (index) 
    {
        case 1:
            return [[UIColor colorWithRed:1.0f green:1.0f blue:1.0f alpha:1.0f] CGColor];
        case 2:
            return [[UIColor colorWithRed:0.200f green:0.200f blue:0.200f alpha:1.0f] CGColor];
        case 3:
            return [[UIColor redColor] CGColor];
        case 4:
            return [[UIColor colorWithRed:0.062f green:0.658f blue:0.062f alpha:1.0f] CGColor];
        case 5:
            return [[UIColor blueColor] CGColor];
        case 6:
            return [[UIColor yellowColor] CGColor];
        case 7:
            return [[UIColor orangeColor] CGColor];
        case 8:
            return [[UIColor brownColor] CGColor];
        case 9:
            return [[UIColor colorWithRed:0.7f green:0.7f blue:0.7f alpha:1.0f] CGColor];
        case 10:
            return [[UIColor purpleColor] CGColor];
        default:
            break;
    }


    return [[UIColor colorWithRed:1.0f green:1.0f blue:1.0f alpha:1.0f] CGColor];
}

@end

Additional Info:

StackPoint.h

    @interface StackPoint : NSObject {
        CGPoint point;
    }

    @property (nonatomic , assign) CGPoint point;
    +(StackPoint*)pointWithPoint:(CGPoint)_point;
    @end

StackPoint.m

    @implementation StackPoint
    @synthesize point;

    +(StackPoint*)pointWithPoint:(CGPoint)_point
    {
        StackPoint *__point = [[StackPoint alloc] init];
        __point.point = _point;
        return [__point autorelease];
    }

    -(id)init
    {
        self = [super init];
        if(self)
        {
            point = CGPointZero;
        }
        return self;
    }

    @end