Sign in to follow this  
staticVoid2

sphere collision and stairs

Recommended Posts

staticVoid2    381
hi there, I'm trying to modify my sphere-to-poly collision routine so that I can get objects to move up stairs. I'm currently just finding the point on the sphere that will intersect with the surface using: sphere.center + (surface.normal * -sphere.radius) then constructing a line segment between this and the place it will be after velocity is added, if this intersects with the polygon's plane I then do a check to see how far the intersection point is from the closest point on the polygons edges, if this value is less that the radius of the sphere then there was an intersection. I then return the surface plane so the caller can do what they wan't such as sliding along the surface. I've tried modifying this returned surface so that when the sphere hits an edge of a polygon the surface normal is rotated in the direction of that edge but this was giving a lot of other bugs I couldn't find. Is there any simple way to do this?

Share this post


Link to post
Share on other sites
polypterus    100
The standard sphere collision detection routine moves up stairs if implemented correctly. You need to check the triangle face first. If it misses the face you check each edge. If it misses the edges you check each node. For the collision normal you use a vector from point of contact on the sphere to the center of the sphere no matter what kind object you collided with. If you slide perpendicular to that normal in a direction directed by your initial force vector (there a few different ways of calculating this) then you will slide up stairs no problem.

However there are other issues that you may encounter later. First off rounding errors can get tricky with this. Also there is the case of multi-plane collision which makes things a bit more complicated. Here is my post on that but there may be better ways to do it.

Share this post


Link to post
Share on other sites
oliii    2196
you also have to consider moving down stairs. If you just do unconstrained rigid bodies, it will feel very floaty and not very useful for character control.

A sphere (or any bounding volume) is a poor representation of a character walking around. The bottom line is that characters usually have special cases with their environment, and it can get quite complicated. That usually involves 'bolting' the character to the floor, using a short raycast under his feet, and for stepping above small obstacles, checking for collisions above his target position.

I'm not an expert but to keep it simple, I've seen algorithms that decompose the movement into horizontal and vertical components, and do two collision checks, to detect obstructions and moving up slopes.

http://jnrdev.72dpiarmy.com/en/jnrdev2/

http://www.peroxide.dk/download/tutorials/tut10/pxdtut10.html

Share this post


Link to post
Share on other sites
polypterus    100
Quote:
Original post by oliii
you also have to consider moving down stairs. If you just do unconstrained rigid bodies, it will feel very floaty and not very useful for character control.


IMHO this is one of those things that's unrealistic in many games. For instance you can't run down steep hills or stairs at the speeds that you do in some games and expect to stay on the floor (or even expect to come away without injury). Gravity isn't strong enough to keep you bolted down at these angles. You kind of do float, and in a sense it's more realistic. I think the old Everquest was like this. I remember bouncing down hills. In any case you can always get rid of it if you don't like it, but on the other hand you might want your game to be more realistic.

Share this post


Link to post
Share on other sites
oliii    2196
That's why you need custom physics for characters to make them behave more appropriately. It's all a pain tbh. I'm surprised a game as big as Everquest didn't even bother doing that.

Also, another technique used is not to replace stairs with slopes (you may be rendering stairs, but the collision surface is actually one large inclined polygon).

Share this post


Link to post
Share on other sites
polypterus    100
I guess what I'm saying is I find the bouncing more realistic because it's more inline of what would happen if you could run that fast down a hill or stairs. This is all a matter of taste though.

Share this post


Link to post
Share on other sites
staticVoid2    381
thanks for all your replies, I've got it working so that when the sphere intersection point with the plane is just outside of the polygon then the plane returned slopes towards that edge, the way I do this is that I take the intersection point, subtract it from the closest point on the polygon edge, normalize this then I interpolate this vector with the polygon normal to get the normal of the plane, the way I interpolate is by taking the distance the intersection point was from the closest point on the polygon edge and puting that over the radius i.e. distance/radius, this then gives me a value between 0-1 of how much I should interpolate between the two. I know this probaly is inaccurate compared to using sphereical interpolation but it seems to work ok.

But... this still doesn't work when I use more than one triangle, any ideas? or is this approach just not going to work period.

p.s. does anyone know what quake 1 uses for collision? bounding boxes or spheres? (and how they move up stairs?) it seems awful jumpy when you go to slide along a wall.

Share this post


Link to post
Share on other sites
polypterus    100
Quote:
Original post by staticVoid2
But... this still doesn't work when I use more than one triangle, any ideas? or is this approach just not going to work period.



It's hard to say if this will work in all cases. However the method I described above works if you can manage the rounding errors. You will probably run into rounding problems no matter what method you use as your geometry gets more complex. When you think about it as you go up stairs the sphere is really contacted the polygon edges (assuming you don't put an invisible plane over the stairs). I find that writing code that more mimics what's you are actually trying to simulate usually gives me less problems. I would tend to go for the face, then edge, then point, collision detector since it's somewhat tried and true. However you do need to write both a sphere/point collision routine (easy) and a sphere/edge collision routine (a bit harder) to do this.

The reason I am able to comment this is I'm currently testing my own collision detector. I'm using it on unusual fractally generated geometry so there is huge number of cases that come up that I have to handle.

In short I would say make your collision detection as robust as possible since it's a very important part of most games. You can always look into PhysX or something if you don't want to write your own.

Share this post


Link to post
Share on other sites
polypterus    100

That's the paper I started with and it's not bad. However there are a lot of little details that you might have to work out. There are also several optimizations for instance if you check an edge or point by processing one face you don't have to check the same edge or point again when processing adjacent faces. There are also a lot of rounding hiccups that come up. Basically never check for exact values like 0.0 or PI/2 and stuff like that. Always allow for some error. Here is another post I made on the topic. That might (or might not) give you some ideas.

http://www.gamedev.net/community/forums/topic.asp?topic_id=532258&whichpage=2�

Also if you hit any stupid rounding problems that seem hard solve, feel free to ask me because there is a good chance I already ran into the same stupid thing.

Share this post


Link to post
Share on other sites
staticVoid2    381
hey, I got it working, the rounding errors weren't that bad, although I did get caught out at the end - I was adding an exact 1.0f offset from the plane to calculate the new sphere position after sliding when it should have been 1.0f + epsilon. And once again... thanks a lot.

Share this post


Link to post
Share on other sites
Fingers_    410
Quote:
Original post by staticVoid2
p.s. does anyone know what quake 1 uses for collision? bounding boxes or spheres? (and how they move up stairs?) it seems awful jumpy when you go to slide along a wall.


Quake1 uses a point and a pre-calculated world collision hull. As part of the level compiling process, the tool creates a version of the level with all the brushes "inflated" by geometrically adding the player bounding box to them. This way the game can handle the player as a point entity which was important when processor speeds were in double digits (and limited the game to two sizes of characters plus point-sized entities because each bounding box size required its own world collision hull...).

You could look up how it does stairs since the source code is out under GPL but it's probably largely irrelevant. It boils down to testing if the player will clear a collision against a vertical surface when moved up by some amount (max step height); if so, it does another ray cast from the raised location downward to find the actual new position (in case the step was lover than maximum allowed).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this