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

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;
}
``````
-
Have you looked at the Sobel-operator and edge detection and finding the gradients? (never done this myself, no idea how applicable it is) – Sean Middleditch Jun 27 '13 at 5:40

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.

-
The only problem with this approach is that it can miss narrow spikes, if they exist. When I've done this sort of thing in the past (in 3D on top of polygons, admittedly), I've tested spheres against the ground, instead of lines. That way (assuming you pick a good size for your spheres), your tests can be guaranteed to hit those spikes which can be missed by linear tests. (Granted, sphere tests are likely to be more expensive than linear tests). If the terrain is guaranteed not to have very narrow spikes in it, though, this answer's approach is ideal. – Trevor Powell Jun 27 '13 at 5:46
@TrevorPowell Since these normals need to be recalculated when the terrain morphs, he could simply detect pixels that are "way out of range" and have them break off and fall down. This would both produce more realistic morphing and also solve this problem. – DampeS8N Jun 27 '13 at 16:50
@Nathan Thanks for the response. I am intrigued by your suggestions and will try implementing them tonight. I will try both the sparse sampling by stepping in larger increments and the series of 1D searches. I'll make a follow up post on the results. – Paul Renton Jun 27 '13 at 19:01
@Nathan I implemented the suggested methods and both perform much better than my posted algorithm and appear to yield the same result. As far as which one worked better, I believe the sparse sampling prevailed. It better handled the case when there was a narrow spike, as Trevor mentioned, but I do believe with some edge case tweaking it might operate just fine. Thanks so much for the help! – Paul Renton Jun 28 '13 at 6:54