100% guarantee non-interpenetration physics ?

[Erwin Coumans]

Yes, plus using continuous collision detection typically reduces the number of contact points greatly, because you maintain the objects slightly separated, and because at most 6 contacts points can be independent between any two objects (since there are six degrees of relative freedom)

I discussed this with Jan Paul van Waveren, idSoftware and Doom3 physics programmer. He mentions that he prevents objects from penetration all the time:

- use ccd to calculate contact points
- build & solve contact constraints, apply impulses
- safely update transform of objects using ccd, one at a time

This description is not complete, perhaps Jan Paul will publish some paper about his approach.

Stephane, do you 100% guarantee non-interpenetration physics using your approach with ccd, given your external tolerances ?

[Stephane Redon]

Stephane, do you 100% guarantee non-interpenetration physics using your approach with ccd, given your external tolerances ?

Yes. Provided interval arithmetic is implemented correctly, the complete algorithm guarantees 100% non-interpenetration physics. The reason is that each motion (i.e. free motion, constrained motion, or displacements to attempt to reposition the objects and slightly separate them from each other) is only considered as 'intentional' and is subject to CCD. At worst, the CCD will prevent the objects to move completely, but will never allow them to penetrate.

[MrElusive]

The CCD in Doom3 guarantees non-penetration. The CCD both minimizes rounding errors in the calculations and guarantees non-penetration in the context of (floating point) rounding errors. The same core CCD algorithm is used to both sweep arbitrary (not necessarily convex) polyhedra through space and to find contact points between polyhedra.

Doom3 implements several different physics solvers among which an impulse based approach where an object at most applies a single impulse per frame (60Hz). The ragdolls and vehicles use a lagrange multiplier approach with a partial linear time solver.

[Dirk Gregorius]

The ragdolls and vehicles use a lagrange multiplier approach with a partial linear time solver.

Do you really model rolling for the tyres in Doom 3? That would be a non-holonomic constraint and as far as understood analytical mechanic needs special treatment, since the constraint force is no more workless. Is this the reason why you use different approaches? E.g. if you model cloth using point masses and a simple spring-damper system the system is normally quite stiff. Verlet integretion seems well suited for these kind of siff systems (there is a paper of Jakobsen regarding this topic IIRC). Some people recommend handling everthing in a unified scheme. What were your considerations when you splitted the system?

Regards,

-Dirk

[Erin Catto]

Even for ray cast wheels, a nonholonomic constraint is usually used, except that the lateral constraint force (friction) has a limited magnitude to allow for sliding. These constraints don't need special treatment if the engine can handle lo-hi limits on the Lagrange multipliers.

I'm guessing Doom3 uses Lagrange multipliers for bilateral constraints where penetration is not a conscern and impulses for contact to prevent penetration.