Best way to determine surface normal for a group of pixels?

Question

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.

EDIT: This is a re-work of the getSurfaceNormal function to implement the 2nd algorithm as specified by Nathan. I am putting it here for purposes of feedback and to hopefully show in code what Nathan is talking about.

-(CGPoint)getSurfaceNormalAt:(CGPoint)pt withSquareWidth:(int)area {
// This method only looks at surface pixels

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

for (int w = area; w >= -area; w--) {
    int h = area;
    do {
        if ([self pixelAt:ccp(w + pt.x, h + pt.y) colorCache:&color]) {
            if (color.a != 0) {
                if (w < 0) {
                    avgX -= w;
                    avgY -= h;
                } else {
                    avgX += w;
                    avgY += h;
                }
                break;
            } // end inner if
        } // end outer if
        h--;
    } while (h >= -area);
} // end for
int perpX = -avgY;
int perpY = avgX;
len = sqrtf(perpX * perpX + perpY * perpY);
normal = ccp(perpX/len, perpY/len);

return normal;
}

Answer 1

I think your basic idea is sound. I'll summarize what your current code is doing. To get the average normal within an area around a point, you're gathering all the pixels in a rectangle centered on that point. For all the pixels in the rectangle that are solid ground, you're averaging the vector from the pixel to the query point. Effectively you're calculating the vector from the center of mass of the nearby solid pixels, to the query point.

I have two general suggestions to speed this up. The first is that you don't need to look at every single pixel in the search area. You can probably get a pretty good approximation by using a sparse sampling: only look at a few isolated pixels, evenly distributed over the search area. For instance, you could step by units of 2 to 5 pixels instead of 1 pixel in your loop; that would give you a sparse grid sampling and that might well be good enough to get away with. Poisson disk sampling is also a common sparse sampling method, especially in pixel shaders for soft shadows, SSAO, etc. You precompute a Poisson disk pattern (just store the points in a static array in your code) and scale the pattern to the size of the desired search area at runtime.

The second suggestion is that you could probably replace the 2D search with a series of 1D searches. You don't really care what's under the ground, you just care what the orientation of the ground surface is, if I understand correctly. So you could pick a few points along the top of the search area, then just do a 1D search down from each starting point until you find a solid pixel. In ASCII art,

X   X   X   X
|   |   |   |
|   |   | ..*
| ..*...*....
*............

The X's are the starting points, the vertical bars are the 1D searches, the dots are the ground, and the stars are the ground points found by the searches. Once you have these points, you calculate the average vector from each of them to the center point, but negate the vector for the points to the left of the center, and leave it alone for the points to the right. That should prevent the average from coming out zero, and will give you a vector that points tangent to the terrain, to the right. Calculate the vector perpendicular to this one and you'll have your normal.