Sign in to follow this  
Maddius

Better FPS Collisions

Recommended Posts

Maddius    146
Hi all, Just wanted to ask for some opinions on FPS collision methods, I developed a collision between a point and a plane (which could really be just a triangle i guess) but anyway it basically calculated the distance between the point and the plane and if they are close it would find the point of collision on the plane and then push the point (the camera position) back by a specified distance. This was okay for most situations but in alot of ways it wasn't great, for example the point is obviously only one point (the head of the player) so if you wanted to check for collisions that are lower than this point you would have to check the plane against a new point, this could yield unreliable results as you could only approximate all the points between the players head and ground. Also if the player is on an inclined plane or any slanted plane, because the method pushes the player back in the direction of the normal there would be gaps between a slanted wall and a flat wall which the player could 'walk between the walls'. So basically I am asking for some improvement ideas to this method because its not totally bad, but i'm just wondering are there any other common methods / improvements to the system. Also I want to be able to collide with 3D models loaded by the my program, all objects have indicies and verticies so the collision engine can just take that data for any worldobject and apply the collision algorithm to it. Sorry that took a while to get through, hope everything is clear.

Share this post


Link to post
Share on other sites
jyk    2094
Short answer: getting this sort of collision detection (and response) to work correctly can be somewhat difficult. These days, the task is often passed off to a physics and collision detection library such as PhysX, but if you want to do it yourself there are a few different approaches you can take.

As you've discovered, it doesn't really work to represent your objects using points. More common is to use a bounding volume of some sort, such as an axis-aligned box, an oriented box, a sphere, a cylinder, a capsule, or an ellipsoid.

There are various techniques for intersecting these shapes with polygon soups or with environments represented using a BSP. The Quake engines use AABBs for objects and a BSP for the environment; there are some articles describing the specific techniques used, and the Quake 3 source code is available as a reference also. There's also the 'dynamic plane shifting' technique, which works with BSPs and accommodates a number of different bounding shapes.

Once you get the basics working, there are a number of corner cases (no pun intended) that have to be dealt with. These usually involve intersecting with more than one surface during a time step, which often happens when running into corners (which without special handling can result in getting stuck, 'falling through' obstacles, or 'jittering' back and forth).

Have to run at the moment, but I'm sure others will chime in with suggestions and/or links to other references that might be helpful.

Share this post


Link to post
Share on other sites
Kwizatz    1392
That method is awful...

I hope you mean ray and plane and not point and plane, checking point and plane would produce tunneling in 99.99% percent of cases, and that's being optimistic, since you mention that it works for you, there must be something you are not telling, perhaps its sphere plane what you're doing.

As for better ways, you should use a proxy shape for the characters, for example an axis aligned bounding box (AABB), Oriented Bounding Box (OBB), Capsule (a cylinder with spheres for caps), etc and do your collision tests between that proxy and the level geometry, by the way, it is a good idea to keep level geometry convex, or perhaps use dual geometry for the level, the raw polygon soup for rendering and blocks of convex shapes for collision calculations, that way you can use the Separating Axis Theorem to do these kinds of stuff.

For things like character movement you shouldn't use the raw model data, in fact you probably shouldn't use it for anything other than rendering, using proxy bounding shapes to determine bullet hits and such, you can use those same proxy shapes as a way to cull which triangles are affected in order to add effects to the mesh, such as blood stains, but that's probably getting too far ahead.

Share this post


Link to post
Share on other sites
Maddius    146
So you are saying, have a bounding box that sounds the camera the size I want the player to be in the world then collide that bounding box with the geometry of the level?

What kind of collision method should I use? Intersection between triangles of the bounding box and geometry?

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
So you are saying, have a bounding box that sounds the camera the size I want the player to be in the world then collide that bounding box with the geometry of the level?
Fundamentally, yes (although it doesn't have to be a box - it could be a sphere, a capsule, or some other shape, although a box is a fairly common shape to use for this sort of thing).
Quote:
What kind of collision method should I use? Intersection between triangles of the bounding box and geometry?
No. There are a variety of algorithms that can be used, depending on bounding shape. For boxes, the SAT (separating axis test) is a good choice. For both spheres and ellipsoids, you can make use of (directly or indirectly) swept sphere tests. There are also methods that work with a BSP tree representing the collidable geometry in the environment; these methods can work with boxes, sphere, cylinders, or other shapes.

Very rarely would you actually perform this sort of collision detection on a per-triangle basis (whether it's the triangles that make up the model, or the triangles making up a bounding volume such as a box).

Share this post


Link to post
Share on other sites
Maddius    146
Okay I have done a little searching on SAT and I have a question now, would you be able to use SAT on a 3D model e.g. a car vs the bounding box of the player and produce accurate results? It seems SAT is for bounding boxes not for polygons, or am I mistaken? (I probably am).

Share this post


Link to post
Share on other sites
Maddius    146
Okay I have been reading this

http://www.metanetsoftware.com/technique/tutorialA.html

and that has explained alot, so basically to translate this into 3D you would need to take into account another axis (the z) and another pair of projections of the objects onto that axis? Is this correct? That is the only difference?

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Okay I have done a little searching on SAT and I have a question now, would you be able to use SAT on a 3D model e.g. a car vs the bounding box of the player and produce accurate results? It seems SAT is for bounding boxes not for polygons, or am I mistaken? (I probably am).
The SAT can be used to detect intersections between convex shapes (such as polytopes, and, in some cases, curved shapes such as circles and spheres).

To use the SAT with a (presumably) non-convex shape such as a car, you would first break it into multiple convex shapes. Keep in mind though that in 3-d, the SAT is not terribly practical when the shapes are complex and/or irregular, due to the many cross-product axes that must be tested. One way to reduce the cost of the test is to use simplified geometry for the purpose of collision detection.

You can also use the SAT in 'polygon soup' environments by treating each polygon as a separate convex object for the purpose of collision detection.

So in short, yes, you could use the SAT to determine intersection between a player (or other in-game object) and a non-convex object such as a car. How effective a solution this would be would depend on the circumstances.

Share this post


Link to post
Share on other sites
Maddius    146
Well the 3D models i'm using are MD2 file format so they are pretty low triangle count. So I guess it could work, if I make it so it checks triangles only when the player is near enough to the model to require further checking.

If not are there any other collision models you would suggest? I think SAT could be a good idea though.

Share this post


Link to post
Share on other sites
Kwizatz    1392
Stop thinking in terms of (character) model triangles, once you get character movement right, you can think about cars, for that you will need a physics library like ODE or PhysX and probably to get familiar with rag doll physics, for now, just focus on character and world collision.

Share this post


Link to post
Share on other sites
oliii    2196
the SAT is good, but it is a lot of work if you are not familiar with it. You can develop the SAT in 2D, and then expand to 3D relatively easily.

You first have to be familiar with basic vector maths such as the dot product and cross product (also vector addition, multiplication, scaling, ect...).

Sphere collisions are usually quite straight forward. The simplest algorithm you can use is to find the closest point on a triangle to the sphere centre, and check if that point is inside the sphere or not.

If it is, you can push the sphere along the direction of the closest point towards the sphere centre.

If you are unsure about all that stuff, your best bet would be to use a 3rd party physics / collision engine such as PhysX.



sphere collisions with mesh.

does basic collisions with a 3D mesh. There are three main files, the first does a very simple interference response (move objects away from the collisions), the others have slightly more involved collision response code.

you can also look at discussion about the SAT in 3D and OBBs, with code and executable.
Maddius    146
Quote:
Original post by Kwizatz
Stop thinking in terms of (character) model triangles, once you get character movement right, you can think about cars, for that you will need a physics library like ODE or PhysX and probably to get familiar with rag doll physics, for now, just focus on character and world collision.


Sorry I should have explained myself a bit better, I dont mean cars to drive around in, it was just an example of a static object in a scene so the player can stand on them etc. Sorry.

Thanks oliii I have downloaded the source from the one you linked on your post and it looks very good to get me moving in the right direction I will try to implement it myself, thanks very much, everyone.

Share this post


Link to post
Share on other sites
Kwizatz    1392
Quote:
Original post by Maddius
Sorry I should have explained myself a bit better, I dont mean cars to drive around in, it was just an example of a static object in a scene so the player can stand on them etc. Sorry.


Oh, ok, in that case the car should have a proxy as well, either a rough convex hull of sorts or something simpler like an oriented box, or a series of boxes, how detailed this proxy would be depends on your needs, you'll need more detail if you want the characters to be able to jump on the car and walk on top of it than you would if you only want them not to walk through it.

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