Jump to content
  • Advertisement
Sign in to follow this  
Kitasia

General 3D Collision Detection and Response Process?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

For years I've been lumping the two together and it's become very clear that they're two very separate topics. Even so, I've yet to find a clear paper that really lays out the process in general.

I was hoping someone here may be able to tell me if this sounds about right or point me to a paper that does sum it up. I think a lot of this comes from the Kasper Fauerby Peroxide paper.

I believe th process is as follows....

1) Velocity

Update the velocites of all moving objects. Apply gravites and make special changes based on information from the previous loop.

2) Pushing Objects (??)

Apply impulses to your objects based on collisions with one another. I'm not sure it always works well to push collide moving objects so it may be best at times to treat objects to be tested against as stationary (Moving Platforms?).

3) World

For each Object, recursively update the object against every object it isn't able to push. The recursion is used to slide the object along the world.

4) Finalize

Apply Velocity to each object and then update its position in the world.


That's my take in it anyway. There are problably variations to this but I think this gives the general idea. Any thoughts?

Share this post


Link to post
Share on other sites
Advertisement
First, you're correct that it's somewhat simpler in the long run to separate collision detection from collision response.

The paper you referenced appears to apply a non-Newtonian type of physics in the collision response. When an object "bumps" into a second object, it's velocity is changed to be tangent to a plane related to the second object.

The overall algorithm you use depends on what kind of "physics" you want to implement.

I'm most familiar with ODE (Open Dynamics Engine) which takes an entirely different approach, using approximations to Newtonian physics and material properties.

I may be corrected, but the general approach for ODE is:

USER INPUT
1. set object positions, velocities, angular velocities and material properties (soft-hard, bouncy, surface friction, etc.) - this is where you apply non-gravity forces to translate/rotate your object.

COLLISION DETECTION
2. determine all collisions between all objects (applies gravity for you) - a broad phase AABB culling, then, if 2 objects intersect, fill a collision data structure with pointers to the two objects, intersection point, normal to collision point, depth of penetration, etc. Push that structure into a std::vector.

COLLISION RESPONSE
3. for each object, calculate the total force (including torques) on the object resulting from all collisions. The material properties of the 2 objects in each collision determine the resulting forces. Apply the total force and torque to determine the new object position, linear velocity, angular velocity, etc.

Note: the collision response takes into account joints attached to each object (hinges, springs, motors, etc. attached to another object)

Objects can be spheres, cylinders, cones, capsules (cylinder with half-sphere at each end), trianglular meshes, etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by AntiGuy
For years I've been lumping the two together and it's become very clear that they're two very separate topics. Even so, I've yet to find a clear paper that really lays out the process in general.


What about a book ?

I found "Game Physics Engine Development" from Ian Millington very good to start with.

Share this post


Link to post
Share on other sites
So even the general steps are a bit different than I realized when actually looking into what is done in each step (e.g. materials, no recursion,etc.. ).

Quote:
What about a book ?

I found "Game Physics Engine Development" from Ian Millington very good to start with.


I starting to think I will have to pick up an actual physics book. A lot of information is availble but none really to piece it all together. I've bought books that included physics/collision chapters but those turned out to be really skimmed.

The differences in implementation tell me a book would probably be best. Thanks!

Share this post


Link to post
Share on other sites
If you want to code a collision/physics engine strictly for the learning opportunity, have at it. A lot of developers give that a shot at one time or another, I think. Coming up with a physics system for a game will stretch your imagination.

However, if your intention is a serious engine and you're not a physics and math genious (actually, even if you're Mensa material), you're on a long and difficult road. Consider: an engine like ODE is the result of years of work by many people, many of them professors and professionals. I'm not saying you can't do better - but it won't be next year or the year after.

In either case, you may want to consider trying one or more of the available engines like Havok, ODE, Bullet, etc. (free for the most part), to see what features and limitations each one has, and the general approach used by each.

Several (all?) of those engines include the source code and I've learned an awful lot by seeing how smarter people than myself (yes, there are a few) have done things.

Good luck!

Share this post


Link to post
Share on other sites
Hi, AntiGuy!
For my final school game project, we're supposed to build an engine from scratch, and I'm in charge of the collisions for it.

I must say, the collision detection is far easier than the collision reaction. For the detection, the only thing you need to do is follow a set of formulas that are always the same. Sure, you may do some little tweaks to account for exceptions that may only happen in your project, but it's usually just a straight road.

The reaction is a far more time consuming process. Even if on paper you think you know what reaction you want, in the end, some things will end up being a trial and error kind of thing.

I've used two different ways of doing the collisions pipeline (in different projects).
The first one was to update all the objects, saving their previous positions, and calculate the collisions checking if they collided during that transition.
The second one was to calculate, based on their velocities if they would collide in the future and THEN update.

In the end, it's the same thing. You just need to use whichever one you feel is more natural and easier to understand.

I'm currently doing some simple tutorials on collisions detection, with different types of collision volumes. If you wanna check them out, you can go here:
http://miguelcasillas.com/?page_id=3.

Hope I helped out!

[Edited by - mcasillas on July 21, 2010 11:08:06 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!