Methods, systems and media for simulating contact scenarios
Embodiments of the invention provide methods enabling reliable simulation of objects in contact scenarios. Embodiments of the invention utilize methods providing three parameter-independent guarantees. According to embodiments of the invention, simulations of well-posed problems: have no interpenetrations; obey causality, momentum and energy conservation laws; and complete in finite time.
1. An apparatus for simulating contact between objects comprising:
one or more processors; and
a program storage device having a program of instructions executable by the one or more processors, the program of instructions comprising:
computer readable program code configured to simulate a plurality of objects in one or more contact scenarios with:
a collision detection method guaranteeing geometric safety such that simulated object collision events are not missed and object interpenetration is prohibited, wherein the collision detection method comprises use of kinetic data structures; and
a collision response model and a time integration method that guarantee physical correctness such that simulated object collision events obey causality and physical conservation laws, wherein the time integration method comprises asynchronous variational integrators, wherein the collision response model is based on a barrier potential defined as a monotonically increasing divergent function, and wherein computational progress is guaranteed via culling inactive forces such that simulation of the simulated object collision events completes in finite time.
2. The apparatus according to claim 1 , wherein the collision detection method guarantees that, prior to concluding the simulation, no simulated object collision events go undetected.
3. The apparatus according to claim 1 , wherein the time integration method belongs to a class of geometric integrators comprising at least one of symplectic and time reversible.
4. The apparatus according to claim 1 , wherein the collision response model preserves correctness of a correct physical model, and wherein the collision response model is safe in that the collision response model prevents any detectable interpenetrations.
5. The apparatus according to claim 1 , wherein the barrier potential comprises a piecewise function with c1 continuity at each transition point;
wherein each piece of the function is polynomial; and
wherein each polynomial is quadratic.
6. The apparatus according to claim 1 , wherein:
the computer readable program code is further configured to guarantee safety using kinetic data structures.
7. A method comprising:
utilizing one or more processors to execute a program of instructions for simulating a plurality of objects in one or more contact scenarios, the program of instructions comprising:
computer readable program code configured to simulate a plurality of objects in one or more contact scenarios with:
a collision detection method guaranteeing geometric safety such that simulated object collision events are not missed and object interpenetration is prohibited, wherein the collision detection method comprises use of kinetic data structures; and
a collision response model and a time integration method that guarantee physical correctness such that simulated object collision events obey causality and physical conservation laws, wherein the time integration method comprises asynchronous variational integrators, wherein the collision response model is based on a barrier potential defined as a monotonically increasing divergent function, and wherein computational progress is guaranteed via culling inactive forces such that simulation of the simulated object collision events completes in finite time.
8. The method according to claim 7 , wherein the collision detection method guarantees that, prior to concluding the simulation, no simulated object collision events go undetected.
9. The method according to claim 7 , wherein the time integration method belongs to a class of geometric integrators comprising at least one of symplectic and time reversible.
10. The method according to claim 7 , wherein the collision response model preserves correctness of a correct physical model, and wherein the collision response model is safe in that the collision response model prevents any detectable interpenetrations.
11. The method according to claim 7 , wherein barrier potential comprises a piecewise function with c1 continuity at each transition point;
wherein each piece of the function is polynomial; and
wherein each polynomial is quadratic.
12. The method according to claim 7 , wherein:
the computer readable program code is further configured to guarantee safety using the kinetic data structures.
13. A computer program product comprising:
a non-transitory computer readable storage device having computer readable program code embodied therewith, the computer readable program code comprising:
computer readable program code configured to simulate a plurality of objects in one or more contact scenarios with:
a collision detection method guaranteeing geometric safety such that simulated object collision events are not missed and object interpenetration is prohibited, wherein the collision detection method comprises use of kinetic data structures; and
a collision response model and a time integration method that guarantee physical correctness such that simulated object collision events obey causality and physical conservation laws, wherein the time integration method comprises asynchronous variational integrators, wherein the collision response model is based on a barrier potential defined as a monotonically increasing divergent function, and wherein computational progress is guaranteed via culling inactive forces such that simulation of the simulated object collision events completes in finite time.
14. An apparatus for simulating contact between objects comprising:
one or more processors; and
a program storage device having a program of instructions executable by the one or more processors, the program of instructions comprising:
computer readable program code configured to simulate a plurality of objects in one or more contact scenarios with:
a collision detection method guaranteeing geometric safety such that simulated object collision events are not missed and object interpenetration is prohibited by using certificates in progressing simulated motion for the plurality of objects asynchronously in discrete time steps, wherein the collision detection method comprises use of kinetic data structures; and
a collision response model and a time integration method that guarantee physical correctness such that simulated object collision events obey causality and physical conservation laws via simulating contact between simulated objects employing a barrier potential comprised of penalty layers which simulate application of force to a simulated object as it approaches another simulated object in a contact scenario, wherein computational overhead is reduced by accounting for only a subset of penalty layers which are active at a given discrete time step in the simulation;
wherein the time integration method comprises asynchronous variational integrators, wherein the collision response model is based on a barrier potential defined as a monotonically increasing divergent function.