Bear with me as this will be a rather lengthy post. For the last month I have been working on an open source Cocos2D, Box2D Destructible Terrain Engine. I have some questions regarding its implementation.
TLDR-> When tracing images, how can I account for a divided image where there is a column or row of alpha separating the sprite? How can I leverage a dynamic programming (or something else) type approach to make this algorithm efficient.
Some Context: In the engine, destructible terrain sprites are created with MutableTextures which allow for direct manipulation of pixel values. An alpha value of zero is considered to be destroyed or non existent terrain.
Now in order to use these mutable texture sprites with Box2D, I need an efficient algorithm to trace the image and create a set of vertices which can be used to define the terrain border. From research, there where two ways I could go about this. I could create many, composite polygons (avoid concave angles) to fill the terrain or just trace the border with EdgeShapes. I opted for EdgeShapes.
-(void)makePhysicsObject:(b2World *)theWorld {
self.physicsObject = YES;
self->world = theWorld;
[self generatePhysicsPoints];
if (body) {
world->DestroyBody(self->body);
} // end if
b2BodyDef tDef;
tDef.position.Set(0, 0);
self->body = world->CreateBody(&tDef);
gameObjectType = kGroundTypeDynamic;
self->body->SetUserData((__bridge void *) self);
b2EdgeShape shape;
CCLOG(@"Size of simplified before adding verts is %d", imageBorderPointsSimplified.count);
for (int i =1; i < imageBorderPointsSimplified.count; i++) {
NSValue * val = [imageBorderPointsSimplified objectAtIndex:i];
CGPoint endPt = val.CGPointValue;
NSValue * val2 = [imageBorderPointsSimplified objectAtIndex:i-1];
CGPoint startPt = val2.CGPointValue;
b2Vec2 startVert = b2Vec2(startPt.x/PTM_RATIO, startPt.y/PTM_RATIO);
b2Vec2 endVert = b2Vec2(endPt.x/PTM_RATIO, endPt.y/PTM_RATIO);
shape.Set(startVert, endVert);
self->body->CreateFixture(&shape,0);
if (i == imageBorderPointsSimplified.count - 1) {
// Connect the end verts
val = [imageBorderPointsSimplified objectAtIndex:i];
endPt = val.CGPointValue;
val2 = [imageBorderPointsSimplified objectAtIndex:0];
startPt = val2.CGPointValue;
b2Vec2 startVert = b2Vec2(startPt.x/PTM_RATIO, startPt.y/PTM_RATIO);
b2Vec2 endVert = b2Vec2(endPt.x/PTM_RATIO, endPt.y/PTM_RATIO);
shape.Set(startVert, endVert);
self->body->CreateFixture(&shape,0);
} // end inner if
} // end for
} // MakePhysics
This turned out to work fairly well and didn't kill the fps. However, what is hurting from a performance and algorithmic perspective, is retracing the image.
The algorithm for tracing the image is posted below where the final array called ImageBorderPointsSimplified contains a set of vertices which can be given to box2d to trace the sprite. On average it contains 15-25 points for a medium sized 800x800 terrain sprite.
-(BOOL)isBoundaryPoint:(CGPoint)pt {
BOOL isBoundary = NO; // assumption
// Is trans... so not boundary
if ([self pixelAt:pt].a == 0) {
return isBoundary;
}
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if ([self pixelAt:ccp(pt.x + i, pt.y + j)].a == 0) {
isBoundary = YES;
return isBoundary;
}
}
}
return isBoundary;
} // end isBoundaryPoint
isBoundaryPoint traverses pixels around a given pixel to see if there is a pixel with alpha = 0. If a pixel has an alpha of 0, then it must be a boundary pixel.
-(void)traceImage {
// List of visited pixels
imageBorderPoints = [[NSMutableSet alloc] init];
// ALL Border points
imageBorderPointsOrdered = [[NSMutableArray alloc] init];
// Smoothed with averages
imageBorderPointsSmoothed = [[NSMutableArray alloc] init];
// Simplified based on curvature
imageBorderPointsSimplified = [[NSMutableArray alloc] init];
static int avgCons = 4;
float originX = self.position.x - self.contentSize.width/2;
float originY = self.position.y - self.contentSize.height/2;
float endX = originX + self.contentSize.width;
float endY = originY + self.contentSize.height;
for (int x = originX; x < endX; x++) {
for (int y = originY; y < endY; y++) {
if ([self isBoundaryPoint:ccp(x,y)]) {
CCLOG(@"First boundary point found at %d, %d", x,y);
[self traverseBoundaryPoints:ccp(x,y)];
if (imageBorderPointsOrdered.count > 19) {
// Smooth the points
for (int i = avgCons; i < imageBorderPointsOrdered.count; i = i + avgCons) {
NSMutableArray * tempStore = [[NSMutableArray alloc] init];
for (int x = i; x > i - avgCons; x--) {
[tempStore addObject:[imageBorderPointsOrdered objectAtIndex:x]];
}
NSValue * avgVal = [self averageVertices:tempStore];
//CCLOG(@"Adding %f, %f to averageArray", avgVal.CGPointValue.x, avgVal.CGPointValue.y);
[imageBorderPointsSmoothed addObject:avgVal];
} // end for to pop avg
[self simplifyVertices];
} // end if
return;
} // end if
} // end inner for
} // end outer for
CCLOG(@"MUTTEXTURE :: No boundary points found");
} // end traceImage
-(void)traverseBoundaryPoints:(CGPoint)startPt {
NSValue * startVal = [NSValue valueWithCGPoint:startPt];
[imageBorderPoints addObject:startVal];
NSValue * nextVal = [NSValue valueWithCGPoint:startVal.CGPointValue];
while (true) {
nextVal = [self findNextBoundaryPixel:nextVal.CGPointValue];
if (nextVal == nil) {
CCLOG(@"nextVal is nil... returning");
return;
}
if (CGPointEqualToPoint(startVal.CGPointValue, nextVal.CGPointValue)) {
CCLOG(@"Start Point equals end point.. Exiting traverseBoundaryPoints");
return;
} else {
[imageBorderPoints addObject:nextVal];
[imageBorderPointsOrdered addObject:nextVal];
}
}
}
traverseBoundary points (along with findNextBoundaryPixel) navigates itself around the image pixel by pixel. It stores the visited pixels in a set, and uses the set to check if it has visited there before. It will continue traversing until the start point equals the end point or there are no more pixels left to traverse. This algorithm is the issue tbh... It breaks apart when an image is split in two or there is a linear line of pixels. I could use some suggestions here.
-(NSValue *)findNextBoundaryPixel:(CGPoint)pt {
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
CGPoint ptToCheck = ccp(pt.x + i, pt.y + j);
if ([self isBoundaryPoint:ptToCheck]) {
NSValue * val = [NSValue valueWithCGPoint:ptToCheck];
if ([imageBorderPoints containsObject:val]) {
// CCLOG(@"imageBorderPoints already contains the border point");
} else {
//CCLOG(@"Next boundary found %f, %f", ptToCheck.x, ptToCheck.y);
return val;
} // end inner if
} else {
//CCLOG(@"Point is not a boundary point %f, %f", ptToCheck.x, ptToCheck.y);
}
}
}
return nil;
}
-(NSValue *)averageVertices:(NSMutableArray *)vertices {
CGPoint averagePt = ccp(0,0);
for (NSValue * val in vertices) {
CGPoint pt = val.CGPointValue;
averagePt = ccp(averagePt.x + pt.x, averagePt.y + pt.y);
}
averagePt = ccp(averagePt.x/vertices.count, averagePt.y/vertices.count);
NSValue * valToReturn = [NSValue valueWithCGPoint:averagePt];
return valToReturn;
}
findCurvature locates the midpoint between 2 points and compares that midpoint to a point in-between the two outer points. The distance between the midpoint and the middle point gives a measure of curvature. If there is high curvature, more vertices are needed to trace the image accurately. Simplify vertices reduces the amount of points needed to trace the image by looking at the curvature of a set of points. When the total curvature breaks the arbitrary threshhold, it will use the given point for the final trace.
-(float)findCurvature:(CGPoint)pt1 pt2:(CGPoint)pt2 pt3:(CGPoint)pt3 {
// If curv is high, then there is high curvature
// If it is low then there is low curvature
CGPoint mid = ccpMidpoint(pt3, pt1);
return ccpDistance(pt2, mid);
} // end findcurvature
-(void)simplifyVertices {
float lim = 0.5;
float curvature = 0;
float curvatureTotal = 0;
for (int i = 2; i < self->imageBorderPointsSmoothed.count; i++) {
NSValue * v1 = [imageBorderPointsSmoothed objectAtIndex:i];
CGPoint pt1 = v1.CGPointValue;
NSValue * v2 = [imageBorderPointsSmoothed objectAtIndex:i-1];
CGPoint pt2 = v2.CGPointValue;
NSValue * v3 = [imageBorderPointsSmoothed objectAtIndex:i-2];
CGPoint pt3 = v3.CGPointValue;
curvature = [self findCurvature:pt1 pt2:pt2 pt3:pt3];
curvatureTotal += curvature;
if (curvatureTotal > lim) {
curvatureTotal = 0;
[imageBorderPointsSimplified addObject:[imageBorderPointsSmoothed objectAtIndex:i-2]];
}
}
}
In general this is what is happening: Starting from a corner, it traverses the sprite's texture until it finds a non alpha pixel. It then will 'climb' around all the border pixels caching their location until it reaches the same point again. The array of pixels found are then smoothed (averaged) and reduced based on curvature. However, I am running into problems where if a player destroys the terrain to where it is split in half, only half of the image is traced. I can't think of a way to account for this and am asking for help here.
Also the other issue with my current algorithm, is it will become 'stuck' when there is a straight line of pixels as it won't visit already visited pixels again. When this happens the tracing is incomplete (albeit this is a rare edge case)
Lastly, performance... When a player destroys the terrain, I know exactly which columns of the texture are modified. What I would like to figure out is a way I can avoid retracing the unaffected columns and just retrace the altered columns.
Thanks for reading this long post. Any help would be very welcomed
EDIT Here is a video demonstrating the algorithms in action. At the end it of the video it incorrectly draws the edge of the terrain. This is one of the edge cases described above where there is a linear line of pixels. http://www.youtube.com/watch?v=IUsgjYLr6e0&feature=youtu.be