Collision Detection and Physics FAQ

Contents

• This FAQ is preliminary, so make sure to browse the Physics Forum

How can I avoid missing collisions for fast moving objects

When using collision detection at discrete time steps, tunneling can happen:

The objects moves faster then its own radius, and at the new position no collision is detected.
A method to approximate or calculate the time of impact is needed:
- smaller timesteps
- extruding the object along the motion
- ray cast to the new position
- swept collision test (convex cast, linear cast)
- continuous collision detection, including rotational motion
Interval Arithmethic, Algebraic methods, iterative methods are available and have been succesfully used in realtime game applications, like Doom 3, Half Life 2.

See forum topic(s)

Continuous Collision Detection and Interpenetration
100% guarantee non-interpenetration physics ?
POLL: what time of impact estimation method are you using ?
Kinetic Sweep and Prune

How do most physics engines solve constraints?

It depends what kind of constraints.

For contact constraints, either a sequential impulse based method, or mathematically equivalent iterative LCP constraint solving method called 'Projected Gauss Seidel' (PGS) is used in almost every realtime physics engine.
The same solution can be used for other constraints / joints, like point to point constraint (ball socket joint), hinge (revolute joint) and other. Alternatively a direct solution, like Featherstone or pivoting LCP methods, like Dantzig LCP, can be used, they can provide a better quality solution (more stiffness).

See forum topic(s):

Which LCP's solver have been used by popular physics engine?
Equivalence sequential impulses & Projected Gauss Seidel

What are most popular collision detection algorithms

Collision detection typically happens in several phases:

- broadphase : most coarse grain culling, based on bounding boxes per object
very popular is the 3D Sweep and Prune, based on axis aligned bounding boxes (AABB)
- midphase : for complex objects with a lot of triangles, an acceleration structure based on Bounding Volume Hierarchy is very popular. OPCODE, Bullet and SOLID use an AABB tree, with an AABB for each triangle.
- narrowphase : The actual contact information for a pair of objects is calculated here, including penetration depth, contact normal and contact position.
Special case solutions and general solutions are available. GJK is a generic solution that handles all combinations between two convex object (sphere,box,cylinder,cone,convex hull, triangle leaf from midphase). SAT is another popular but less generic convex-convex collision detection algorithm that only works on polyhedra (with vertices, edges and faces). It doesn't handle implicit/analytical objects, so Special case solutions for convex versus sphere, cylinder etc. are needed.

One closest point is not enough, How can we generate the contact manifold?

See forum topic(s)

Contact Manifold Generation: A question about GJK

My simulation becomes instable when heavy objects rest on light objects

For iterative solvers, this is a difficult problem, and most developers avoid the problem by not creating large mass ratios.

See forum topic(s)

How to handle large mass ratios ?