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
加载中,请稍侯......
精彩评论