Calculating normal vector on a 2d pixelated map

Question

I want to know an efficient way to get the normal of the surface of a 2d map. suppose an object hit the map, i want the object to bounce accordingly. The problem is, the "bounding box" of said object is several pixels in size and the map has many curves.

I thought about getting the pixels that collides with the object (don't ask me how) and calculating it's mean, and having the normal to be the line between said pixel and the center of the object

for those familiar with worms, I want to do the same when a grenade hits the map and bounces back

EDIT: I'm not looking for a 100% accurate formula, I want it to be efficient and believable enough

Answer 1

First, determine which pixels are boundary/surface pixels. Brute force iterate through all pixels in the map. If they have any "air"/"void" pixels bordering them (could be eg. 0 / black pixels in your implementation), they are boundary pixels.

Now for each of these surface pixels, in order to calculate the surface normals, look at it's (two) neighbours. Before we get onto evaluating neighbours, though, there are two ways we can go about running through the surface pixels: one easier, one more efficient.

1. (Easier) Simply keep an unordered list of all surface pixels. As you evaluate each pixel for it's neighbours, you will need to look at all 8 immediate neighbours, checking which already exist in the surface pixel list. This could wind up being really costly, probably O(n*s), where n is the total number of pixels in the bitmap and S is the number of surface pixels.

2. (More efficient) Find the leftmost, topmost surface pixel in the entire map. Evaluate it for surface pixel neighbours (should be just one). Calc surface normals. Now step to the next unwalked neighbour along the surface. Rinse, repeat, until you've walked every surface pixel. Dealing with floating islands is an edge case you would need to handle separately (but that is a separate question, if you wish to ask it). Because we are not re-evaluating every pixel in isolation for it's neighbours, and are instead re-using the last surface pixels calculations in order to walk to the next surface pixel, this approach should be roughly twice as fast.

So how do we actually use neighbours to find normals during this process? If the pixel in question is A, and it's neighbours are B and C, get the angle of AB and AC. Average these angles. Now get the normal (can usually be done fast by flipping/negating the X and Y components of the averaged vector. Alternatively use a vector rotation approach).

Finally, if you want smoother surfaces (since IIRC the above will give you only about 16 distinct normal angles), you can reapply the same approach to the outputted normals, averaging them further between neighbours. Since you'd likely be precalculating all this prior to the level actually starting, a multipass approach wouldn't cost you anything, really.

Notes on efficiency: As in Worms, you are likely re-evaluating surfaces during runtime (that is, CSG is taking place on the terrain). It is probably best to precalculate as much as possible, so your physics can run fast while a player shot is underway. However whenever the terrain is modified, you will have little choice but to perform recalculations (which can then be recached for physics ops). Fortunately though, this will happen between shots, so speed isn't a major concern there, since between shots, physics is usually frozen.