Image Texture Tracing Algorithm - Cocos2D Box2D

Context: I am working on a 2D Destructible Terrain engine for Cocos2D with Box2D. All images, when a level loads, have their border's traced and cached for the purposes of forming Box2D b2EdgeShape boundaries. Image boundaries are traversed in a clockwise direction with each boundary point stored in an object called a TerPixel.

A border pixel is defined as follows where if any of a pixel's 8 bordering pixels have an alpha of 0, it is a border pixel.

``````-(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;
} // end if
} // end inner for
} // end outer for
return isBoundary;
} // end isBoundaryPoint
``````

TerPixel stores a pointer to its next neighbor pixel which forms a circular singly linked list and stores a pointer to a TerrainBlob object which holds the physics body it belongs too. Every found border pixel is stored in a NSMutableDictionary called borderPixels.

``````@interface TerPixel : NSObject {

} // end ivars

-(TerPixel*)clockwise:(TerPixel*)sp;
``````

Whenever the terrain becomes altered, let's say through a circular explosion, a part of the image texture needs to be retraced in order to form the next physics border. My two current algorithms for this are posted below.

The retraceEffectedTerrainBodies loops through a rectangle which fully encompasses the explosion radius. It removes from the cache all previous border pixels which have an alpha of 0 after the explosion. When it finds a border pixel that was not previously in the cache, it retraces the border twice. First it finds an existing border pixel going clockwise then reconnects the linked list. Next, it does another trace going counter clockwise until it finds another previously existing border pixel. I denoted the problem areas with the comment: // ** PROBLEM IS HERE ** //

``````-(void)retraceEffectedTerrainBodies:(CGPoint)loc radius:(int)radius {
CCLOG(@"DEBUG:: START OF RETRACE -> ExplosionOrigin is %f, %f", loc.x, loc.y);

for (int y = loc.y - radius; y <= (loc.y + radius); y++) {
for (int x = loc.x - radius; x <= (loc.x + radius); x++) {
// Starting bottom left
CGPoint pixPt = ccp(x,y);
NSValue * valPt = [NSValue valueWithCGPoint:pixPt];
if ([self pixelAt:pixPt].a == 0) {
TerPixel * tper = [self->borderPixels objectForKey:valPt];
if (tper) {
// Since it is alpha'ed out
CCLOG(@"DEBUG :: Found and REMOVING dirty terPixel at %d, %d", x,y);
[self->borderPixels removeObjectForKey:valPt];
if (tper.blob.body) {
//CCLOG(@"DEBUG :: Destroying physics body for previous border");
self->world->DestroyBody(tper.blob.body);
} // end if
tper.blob.body = NULL;
tper.blob = nil;
}

} else {
// Pixel is solid
TerPixel * tper = [self->borderPixels objectForKey:valPt];
if (!tper && [self isBoundaryPoint:valPt.CGPointValue]) {
tper = [[TerPixel alloc] initWithCoords:x ypt:y prevx:-1 prevy:0];
TerrainBlob * blob = [[TerrainBlob alloc] init];
tper.blob = blob;
blob.tracePixel = tper;
CCLOG(@"DEBUG :: Found a new boundary pixel at %d, %d", x, y);
[self traceUntil:tper];
if (tper.dirty) continue;

} // end inner if
} // end outer if

} // end inner for
} // end outer for
} // end function

-(TerPixel *)traceUntil:(TerPixel *)tper {

int traceCount = 0;
TerPixel * start = tper;
TerPixel * next = start;
TerPixel * old;
NSMutableDictionary * pixSet = [[NSMutableDictionary alloc] init];
//while (next.y > (start.y - circ) && next.y < (start.y + circ) ) {
while (true) {
// Trace until a familiar boundary is found
// CLOCKWISE Trace
traceCount++;
old = next;
next = [self findNextBoundaryPixel:next];
[next setNSP:[old subTerPixel:next]];
[pixSet setObject:next forKey:[next getAsValueWithPoint]];
old.nextBorderPixel = next;
if (TerPixel * fb = [borderPixels objectForKey:[next getAsValueWithPoint]]) {
CCLOG(@"DEBUG :: SUCCESS Found first common boundary at %d, %d", next.x, next.y);
// ** PROBLEM IS HERE ** //
old.nextBorderPixel = fb;
fb.blob = old.blob;
ccColor4B colTest = ccc4(10, 50, 200, 250);

//CCLOG(@"DEBUG :: OLD IS POINTING TO THIS POINT %d, %d", old.nextBorderPixel.x, old.nextBorderPixel.y);
break;
} else {
//CCLOG(@"DEBUG :: Adding %d, %d found while tracing new border", next.x, next.y);
[borderPixels setObject:next forKey:[next getAsValueWithPoint]];
}
} // end while

next = start;
//CCLOG(@"START BORDER PIXEL IS %d, %d", start.x, start.y);
//while (next.y > (start.y - circ) && next.y < (start.y + circ) ) {
while (true) {
// Trace until a familiar boundary is found
// COUNTER-CLOCKWISE trace
traceCount++;
old = next;

// Force the other direction
for (int i = 0; i <9; i++) {
TerPixel * p = [next clockwise];
if ([self isBoundaryPoint:[p getPixelAsPoint]] && ![pixSet objectForKey:[p getAsValueWithPoint]]) {
//CCLOG(@"DEBUG::  2nd while-> Found boundary pixel at %d, %d", next.x, next.y);
next = p;
break;
} // end if
} // end for

[next setNSP:[old subTerPixel:next]];
CCLOG(@"DEBUG :: 2nd WHILE -> next x,y %d, %d", next.x, next.y);
//old.nextBorderPixel = next;
next.nextBorderPixel = old;
//next.blob = old.blob;
/*
TerPixel * temp = next;
while (temp != start) {

temp = temp.nextBorderPixel;
CCLOG(@"TESTWHILE :: %d, %d", temp.x, temp.y);
}
*/

if (TerPixel * fb = [borderPixels objectForKey:[next getAsValueWithPoint]]) {
// ** PROBLEM IS HERE ** //
CCLOG(@"traceCount is %d", traceCount);
fb.nextBorderPixel = old;
return start;
} else {
//CCLOG(@"DEBUG :: Adding %d, %d found while tracing new border", next.x, next.y);
[borderPixels setObject:next forKey:[next getAsValueWithPoint]];
} // end if
} // end while

CCLOG(@"DEBUG ERROR:: traceUntil :: ERROR IN LOGIC -> No common boundary found");
return nil;
} // end function
``````

The clockwise trace works as follows in the following order:

``````2 3 4
1 P 5
8 7 6
``````

So here is my problem. For the first explosion these algorithms work just fine. The clockwise and counterclockwise traces work just great and the linked list is reestablished with the new borders. However, let's say a second explosion occurs within the first explosion. All of the sudden, a clockwise trace has the potential to become a counterclockwise trace if the terrain is sloping down. Because of how my logic is currently set up, the linked list will become inaccurate as which pointer gets assigned to which depends on the trace being clockwise or counter clockwise.

For clockwise traces, I assign

``````    old.nextBorderPixel = fb;
fb.blob = old.blob;
``````

For counterclockwise traces, I assign

``````    fb.nextBorderPixel = old;
``````

So what ends up happening is the pointers form a half moon shaped border because they point to the old border pointers. I need the 'relinking' to be opposite when this situation occurs. My question is how can I develop an algorithm, with my current tracing method, to accurately recreate the linked list regardless of a clockwise or counter clockwise direction or how can I correctly take into account the direction? I realize this post is long and still may need more information. Let me know and I will provide it.

EDIT Here is a short video illustrating the problem. Sorry about the quality.. The emulator isn't the best http://www.youtube.com/watch?v=gZEUxuJ3UYg&feature=youtu.be

-