One of my current endeavors is creating a 2D destructible terrain engine for iOS Cocos2D (See https://github.com/crebstar/PWNDestructibleTerrain ). It is in an infant stages no doubt, but I have made significant progress since starting a couple weeks ago. However, I have run into a bit of a performance road block with calculating surface normals.

Note: For my destructible terrain engine, an alpha of 0 is considered to not be solid ground.

The method posted below works just great given small rectangles, such as n < 30. Anything above 30 causes a dip in the frame rate. If you approach 100x100 then you might as well read a book while the sprite attempts to traverse the terrain. At the moment this is the best I can come up with for altering the angle on a sprite as it roams across terrain (to get the angle for a sprite's orientation just take dot product of 100 * normal * (1,0) vector).

-(CGPoint)getAverageSurfaceNormalAt:(CGPoint)pt withRect:(CGRect)area {

float avgX = 0;
float avgY = 0;
ccColor4B color = ccc4(0, 0, 0, 0);
CGPoint normal;
float len;

for (int w = area.size.width; w >= -area.size.width; w--) {
    for (int h = area.size.height; h >= -area.size.height; h--) {
        CGPoint pixPt = ccp(w + pt.x, h + pt.y);
        if ([self pixelAt:pixPt colorCache:&color]) {
            if (color.a != 0) {
                avgX -= w;
                avgY -= h;
            } // end inner if
        } // end outer if
    } // end inner for
} // end outer for

len = sqrtf(avgX * avgX + avgY * avgY);
if (len == 0) {
    normal = ccp(avgX, avgY);
} else {
    normal = ccp(avgX/len, avgY/len);
} // end if

return normal;
} // end get

My problem is I have sprites that require larger rectangles in order for their movement to look realistic. I considered doing a cache of all surface normals, but this lead to issues of knowing when to recalculate the surface normals and these calculations also being quite expensive (also how large should the blocks be?). Another smaller issue is I don't know how to properly treat the case when length is = 0.

So I am stuck... Any advice from the community would be greatly appreciated! Is my method the best possible one? Or should I rethink the algorithm? I am new to game development and always looking to learn new tips and tricks.