Better FPS Collisions

This topic is 3311 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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 on other sites
Moving to Math and Physics.

Share on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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.

1. 1
2. 2
Rutin
24
3. 3
JoeJ
19
4. 4
5. 5
gaxio
13

• 17
• 40
• 23
• 13
• 13
• Forum Statistics

• Total Topics
631729
• Total Posts
3001918
×