Skip to main content
gamedev.net
🔒 Locked

Simulation algorithm

Started by DanHawson 2 replies 650+ views
Original Post
DanHawson
DanHawson
I''m unsure as to the general top-level algorithm to use in simulating rigid bodies and dealing with collisions? I was thinking it would go something like this - - Clear force and torque accumulators on all objects - Apply external forces like weight, wind, thrust, etc. to all bodies. - For all objects: Update position, orientation, linear and rotational momentum, based on the accumulated forces. Ignoring collisions/interpenetration for now. - Clear force and torque accumulators again. - For all objects: Check for interpenetration with every other collideable body/object - For each object the body is penetrating: Backtrack both objects'' positions and orientations to the time when they made contact. Determine the contact points at this time and apply force and torque to both objects in response to the collision contacts. - For all objects: if this object has accumulated more force and torque, as a result of a collision, then update position, orientation and momentums again, to take them from the collision time (to which they had been backtracked) back up to the current time again. However, doing this causes problems: If, for example I''m checking object A for penetration with other objects. I first check it against B to find that it is not penetrating, then find it is penetrating object C. I’d determine the contact point, and update object A and C in response to the collision. However, the response to the collision with C might now mean that A is now penetrating object B! Unless, you would continue repeating the collision tests, backtracking, and updating until there were no more collisions. Is there a better way to approach the top-level simulation or get round the ''collision response causing a new collision'' problem? Thanks in advance. Dan.
teamonkey
teamonkey
Don''t check for collisions separately, do the check while updating the position.

[teamonkey]
[teamonkey] [blog] [tinyminions]
Geoff the Medio
Geoff the Medio
You don't need to check every object with every other object for interpenetration. You can use an quadtree or octree to subdivide space so that you only need to check nearby objects.

Once you have the octree/quadtree, you can check all mutually nearby objects for collisions/penetration and make a sorted list of possible collisions (sort by time). Then, depending how complicated you want to make things, backtrack either all the nearby particles, or all particles, to the time of the first collision and perform the necessary calculations and updates to velocities. Then remove the old collisions from the list that involved the updated particles, and check if the updated particles make any new possible collisions with nearby objects. If they do, add those collisions to your sorted list. Then advance the simulation to the next collision, and repeat, until you finish the time step.

You might be able to run this continuously as well.

[edited by - Geoff the Medio on July 13, 2003 4:10:28 PM]
DanHawson
DanHawson
Thanks. That''s helped clear things up a bit.

This has also got me thinking about resting contacts and how they''d be incorporated into the algorithm. This could complicate matters -
If an object is in contact with a surface one frame, then, after the update, is no longer in contact, would I have to back track the object to the point of leaving the surface so that I could simulate the remainder of the frame time without the contact friction?

Then, what if it was also involved with a collision and a change in resting contact between the frame step? I suppose that so long as I treated a change in resting contact the same way as I''d treat a collision in this collision algorithm, I''d be alright.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.