Physics Engine Questions (GJK+EPA, SI/PGS)

[glitchyme]

Hey all, I'm getting to that point in my 3d rigid body simulator where things are getting pretty hairy. I've got some weird issues, and I'm hoping that somebody can confirm my understanding for the simulation process.


Main Physics Update

1. Update velocity (add external forces, eg. gravity)
2. Predict position for all bodies (temporarily update position)
3. Collision detection
4. Collision resolution
5. Restore positions for all bodies
6. Add stored impulses to velocity, reset impulses
7. Update position for all bodies (using the new velocity)

I'm assuming that performing the position prediction is beneficial in allowing us to find collisions before they occur, and apply enough impulse in order to prevent those collisions. After the collision resolution procedure stores some impulse in each body, we apply those impulses directly to the linear/angular velocity and reset the stored impulse to 0. Dampening may or may not be applied to velocities afterwards (not sure if this is necessary?).


Collision Detection

1. Broadphase detection
2. GJK+EPA
3. Add/update contacts to the contact manifold

I believe my collision detection works, but the most important question is: is what I'm returning the same thing that SI/PGS is expecting? GJK+EPA returns a normal, a penetration depth, and 2 contact points: essentially EPA finishes with a support point and a triangle in the minkowski configuration. Those contact points can be found by first retrieving the bayesian coefficients (u, v, w) with respect to the last projected point, and multiplying those coefficients with the associated support points:

Code: Select all

contact.pointA = triangle.v1.support_a*u + triangle.v2.support_a*v + triangle.v3.support_a*w
contact.pointB = triangle.v1.support_b*u + triangle.v2.support_b*v + triangle.v3.support_b*w

The new contact is added to the bodyA/bodyB manifold. If the same contact already exists (the pair of associated vertices for each support point {support_a.vertex_index, support_b.vertex_index} is the same in an existing contact) then that contact is updated with the new information. Otherwise the new contact is updated. If our manifold exceeds 4 points then delete the weakest contact. This also means that older (weaker) contacts are not updated whatsoever, so they're assumed to be persistent until the bodyA/bodyB are no longer colliding. I'm sure this is wrong, but I couldn't find any material in how to maintain manifolds with older contacts (is it still colliding? have the contacts moved? etc.)


Collision Resolution

1. For each contact: solve penetrations, warmstart impulses, calculate b for baumgarte stabilization
2. For each contact: For each iteration: find delta lambda and add impulse

Solve Penetrations

Code: Select all

contact.rA = contact.pointA - bodyA.position
contact.tangent = contact.rA.cross(contact.normal)
bodyA.d = bodyA.invMass + contact.normal.dot( contact.tangent.cross(contact.rA) * bodyA.invInertia )
contact.d = 1.0 / (bodyA.d + bodyB.d)
dVA = contact.normal.dot( bodyA.velocity ) + contact.tangent.dot( bodyA.angularVelocity )
immediateLinearImpulse = contact.normal * body.invMass * (contact.depth - (dVA * contact.d) - (dVB * contact.d))
immediateAngularImpulse = contact.tangent * body.invInertia * (contact.depth - (dVA * contact.d) - (dVB * contact.d))

both of the immediate impulses are directly added to each body's linear/angular velocity.

Warmstart Impulses
Dampen contact's stored impulse and apply to each body

Code: Select all

contact.impulse *= warmstart
body.applyLinearImpulse( contact.normal * body.invMass * contact.impulse )
body.applyAngularImpulse( contact.tangent * body.invInertia * contact.impulse )

Note that the impulses don't affect the velocity until after the collision resolution.

Baumgarte Stabilization

Code: Select all

relativeVelocityA = contact.normal.dot(bodyA.velocity) + contact.tangent.dot(bodyA.angularVelocity)
contact.b = contact.d * (contact.depth + slop) * baumgarte / dt + contact.d * (relativeVelocityA + relativeVelocityB) * damping

Sequential Impulses

Code: Select all

delta = contact.b - contact.impulse
dVA = contact.normal.dot(bodyA.impulseV) + contact.tangent.dot(bodyA.impulseW)
delta -= dVA * contact.d + dVB * contact.d
contact.impulse = clamp(contact.impulse + delta, 0, Infinity)

body.applyLinearImpulse( contact.normal * body.invMass * delta )
body.applyAngularImpulse( contact.tangent * body.invInertia * delta )

Note that contact.impulse is stored for the next time around, and the body's impulses are reset by the end of the physics engine update.


I could really use some advice, if anybody here knows what I'm doing wrong or if I misunderstood something please let me know.


Video 1: https://www.youtube.com/watch?v=nA8X4PINldE
Notice that the first two attempts the body simply topples over. The 3rd attempt the body stabilizes but runs into the resting contact problem.

[glitchyme]

I could really use some advice, but haven't heard anything yet. I've forwarded the post to gamedev: http://www.gamedev.net/topic/666447-3d- ... ely-stuck/ with some updates. Please feel free to look there and reply either there or here. Any insight into this could really help me out, thanks

[Dirk Gregorius]

This question is way too long. You need to break into smaller parts.