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

Question

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 1

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.

Answer 2

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.

Answer 3

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 :)

Answer 4

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).

Answer 5

Late reply but I was looking for something similar and found an algorithm that works pretty well :

Take a bunch of samples around your test point (in my case I get all points that are below a given radius). Calculate the average position of all points that are inside collider (black) in this case and the average position of all points that are outside collider (white).

At the end, you got two points. From there you can calculate a vector, normalize it and your get your surface normal.

Some pseudo-code:

vec collisionpoint, pa(0, 0), pb(0, 0)
counta = 0, countb = 0

for y = 0 to r:
for x = 0 to r:
    vec offset(x, y)
    if offset.sqrMagnitude < (r * r):
        if (collisionpoint + offset).collides():
            pa += offset
            counta++     
        else:
            pb += offset
            countb++               

if counta > 0: pa /= counta
if countb > 0: pb /= countb
normal = (pb - pa).normalized