collision detection - How do I calculate the angle of the slope at a point on a 2D bitmap terrain?

I have an arbitrary destructible bitmap terrain like the one in "Worms". It's easy to work out if a character or missile intersects the terrain, but how do I work out the angle of the slope at the contact point, so I can make grenades roll down hills, bounce off at the right angle, etc. I know it can be down by somehow taking a sample of points around the impact point and seeing which ones intersect, but I'm not sure exactly how to go about it, and in an efficient way.

Answer

If you're happy sampling then run a coarse sample at a defined radius around your hit point. 16 samples in a circle will provide you with quite accurate curvature. If you add up all the vectors that "missed", you'll have a vector that can be normalised to a surface normal.

If you hit the flat floor, all the vectors will miss if they're pointing up at all, so they add up to an up vector. If you hit a 45 degree slope, the vectors that point away from the slope will miss and add up to a 45 degree vector away from the slope. Even a rough surface will provide a reasonable surface normal as you're checking for "misses" not a surface.

This works fine until you get into really tight spaces, at which point, curvature is all shot to crap anyway, and you would probably not get a sensible result in any technique other than precomputed surface normals (which can be found by blurring a "vector to closest feature" map where feature is non colliding / non matter).

so:

Vec collisionPoint # point of collision
Vec acc(0,0)

for f = 0 to 2pi:
 vec check = vec( sin( f ), cos( f ) )
 if ( check + collisionPoint ).collides():
  acc += check
normal = acc.normalise() # yes, there is a chance of a divide by zero.