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.

-

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.
-
If you're worried about speed, you can precalculate the positions relative to the impact point for the (e.g. 16) samples, avoiding sin/cos and float->integer conversion. This technique can be combined with the collision detection: if you do collision detection on points in a circle around the edge of the grenade, then the vector from the point which collides with the terrain first to the centre of the grenade is a normal to the surface. – Chris Johnson Aug 17 '10 at 11:08
I felt the "sin/cos" stuff needed to go in there to describe the values. I don't recommend using sin/cos ever. There is never* a good reason to use trigonometry. *if you happen to find one, then kudos and let me know. ;) – Richard Fabian Aug 17 '10 at 11:26
so should I store offsets for each pixel to check? e.g. [x:0, y:-10], [x:2, y:-7], etc? – Iain Aug 17 '10 at 11:44
You could, and i probably would, but your performance is going to be bound on the collision check per iteration, not on your implementation of the vector array. – Richard Fabian Aug 17 '10 at 12:35
I would recommend you read up on texture swizzling, to increase cache coherency if it's just an image lookup as your collision check. – Richard Fabian Aug 17 '10 at 12:36

You need two points to calculate it. The slope is then the coefficient of the line passing for the two points, i.e.:

m = ( y2 - y1 ) / ( x2 - x1 )

To get it in form of an angle use the arctan(m) function.

-
yep - how do I find the second point in an efficient manner? – Iain Aug 17 '10 at 10:13
You should find two points which are near enough to give a good approximation. This can be done by sampling points around your collision point. – tunnuz Aug 17 '10 at 10:19
The distance around your point at which you sample will be important: if you sample just at the 8 pixels immediately surrounding the current one, you will only get angles in multiples of 45 degrees. A sensible radius at which to sample is something close to the radius of the object you wish to bounce. – Chris Johnson Aug 17 '10 at 10:40

If you want to go crazy, you could take a grid of samples around your test-point, do an edge-detection algorithm to identify the surface (i.e. any point part of the terrain with a neighbour which isn't, or vice-versa, is a surface point), and then find the best-fit line through those points to use as an approximation to the surface.

Might be overkill though :)

-

The original Worms probably didn't do anything more complex than bitmap/bitmap intersections - i.e. does the bitmap of the grenade intersect with the collision map of the world. Moving the grenade (or whatever) would follow these steps:

1. Can the object move down one pixel without a collision? If so, move object down one pixel and end test.
2. Can the object move left and down without a collision? If so, move object down and left one pixel and end test.
3. Can the object move right and down without a collision? If so, move object down and right one pixel and end test.
4. If object moved left and down (2) last time, can object move left one pixel? If so, move object left one pixel and end test.
5. If object moved right and down (3) last time, can object move left one pixel? If so, move object right one pixel and end test.

You probably only want to do (4) and (5) for a few frame to simulate friction, e.g. repeat (4) for each preceding (2).

-
A down vote? Don't forget that the original Worms ran on the Amiga which had a Motorola 68000 CPU - an integer only unit with no FPU whatsoever. – Skizz Aug 23 '10 at 23:28