Collision detection with advanced position

A method for executing a physics engine to simulate real-time rigid body dynamics of a simulated physical system including a plurality of bodies, the method comprising:

• for a first body of the plurality of bodies, wherein the first body is located at a first position and has a movement direction indicated by a velocity vector, determining that a second position located along the velocity vector is located outside a first non-collision region for the first body and a second body of the plurality of bodies;
• determining a safe position located along the velocity vector at which the first body would lie tangent to a first separation plane that bounds the first non-collision region on a first side of the first non-collision region;
• determining an advanced position located along the velocity vector between the safe position and the second position, wherein the advanced position is located at an advancement distance along the velocity vector from the safe position;
• determining an advanced separation plane that bounds an advanced non-collision region on an advanced side of the advanced non-collision region, wherein the advanced separation plane is specified by an advanced normal vector based at least in part on the advanced position;
• and
• moving the first body to a new position based at least in part on the velocity vector and the advanced separation plane.

A computing device, comprising:

• a processor configured to execute a physics engine to simulate real-time rigid body dynamics of a simulated physical system including a plurality of bodies, the physics engine being configured to:
• for a first body of the plurality of bodies, wherein the first body is located at a first position and has a movement direction indicated by a velocity vector, determine that a second position located along the velocity vector is located outside a first non-collision region for the first body and a second body of the plurality of bodies, wherein the second position is equal to the first position plus the velocity vector multiplied by a time step length;
• determine a safe position located along the velocity vector at which the first body would lie tangent to a first separation plane that bounds the first non-collision region on a first side of the first non-collision region;
• determine an advanced position located along the velocity vector between the safe position and the second position, wherein the advanced position is located at an advancement distance along the velocity vector from the safe position;
• determine an advanced separation plane that bounds an advanced non-collision region on an advanced side of the advanced non-collision region, wherein the advanced separation plane is specified by an advanced normal vector based at least in part on the advanced position;
• and
• move the first body to the second position based at least in part on the velocity vector and the advanced separation plane, wherein the second position is within the advanced non-collision region.