Physics simulation apparatus and method

• US 20060149516A1
• Filed: 12/02/2005
• Published: 07/06/2006
• Est. Priority Date: 12/03/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Telekinesys Research Limited (Microsoft Corporation)
• Inventors: Gasinski, Adrian, Strunk, Oliver, Bond, Andrew
• Granted Patent: US 7,788,071 B2
• Time in Patent Office: Days
• US Class Current: 703/6
• CPC Class Codes: A63F 13/10 Control of the course of the game, e.g. start, progess, end
• CPC Class Codes: A63F 13/45 Controlling the progress of the video game
• CPC Class Codes: A63F 13/577 using determination of contact between game characters or objects, e.g. to avoid collision between virtual racing cars
• CPC Class Codes: A63F 13/80 Special adaptations for executing a specific game genre or game mode
• CPC Class Codes: A63F 2300/64 for computing dynamical parameters of game objects, e.g. motion determination or computation of frictional forces for a virtual car
• CPC Class Codes: A63F 2300/643 by determining the impact between objects, e.g. collision detection
• CPC Class Codes: G06F 2111/10 Numerical modelling
• CPC Class Codes: G06F 30/15 Vehicle, aircraft or watercraft design
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2210/21 Collision detection, intersection

Abstract

A method and apparatus wherein complex physical interactions and collisions are modeled at a high level of detail while reducing the computational demands placed on the processing system. In one embodiment the method comprising the steps of defining a first object and a second object, each object adapted for colliding with the other object; assigning an interaction type for at least one of the first and second object in response to an object parameter; and selecting between a continuous simulation of a collision and a discrete simulation of the collision in response to the interaction type.

Claims

1. A method of simulating a plurality of objects, the method comprising the steps of:

detecting a collision between a pair of objects;

selecting between a continuous simulation mode and a discrete simulation mode for each pair in response to a physics engine parameter; and

simulating an interaction between the pair of objects using the selected simulation mode.

2. The method of claim 1 wherein the physics engine parameter is an object type and the simulation mode is selected by

associating an object type with each object in the pair,

assigning an interaction type in response to one of the object types;

and

selecting between a continuous simulation mode and a discrete simulation mode in response to the interaction type.

3. The method of claim 2 wherein the object type is selected from the group consisting of fixed, keyframed, debris, moving, critical, and bullet.

4. The method of claim 2 wherein the interaction type is selected from the group consisting of continuous, discrete, TOI interaction, and PSI interaction.

5. The method of claim 1 wherein an allowed penetration distance between objects is set based upon an object parameter.

6. The method of claim 1 wherein the physics engine parameter is selected from the group consisting of object type, separation distance, penetration distance, object relevance, physical parameters, and geometric parameters.

7. A method of simulating object interactions, the method comprising the steps of:

defining a first object having a first object type and a second object having a second object type;

assigning an interaction type in response to at least one object type; and

selecting between a continuous simulation mode and a discrete simulation mode in response to the interaction type.

8. The method of claim 7 wherein the object type is selected from the group consisting of fixed, keyframed, debris, moving, critical, and bullet.

9. The method of claim 7 wherein the interaction type is selected from the group consisting of continuous, discrete, TOI interaction, and PSI interaction.

10. A method of simulating object interactions, the method comprising the steps of:

relating a physics simulation process and a graphic display process using a reference timeframe;

calculating a first set of motion states for a plurality of objects at a first time;

calculating a second set of motion states for the plurality of objects at a second time; and

displaying a set of the plurality of objects at a third time by interpolating object positions using the first and second motion states.

11. The method of claim 10 further comprising the step of decoupling physics simulation events from graphic display events such that interpolating between time steps adjusts for lag between physics simulation events and graphic display events.

12. The method of claim 10 wherein the second motion state for an object is calculated from the first motion state and a velocity of the object.

13. A method of claim 10 wherein graphic display events and physics simulation events are calculated using separate processes.

14. A method of simulating object interactions in a physics engine, the method comprising the steps of:

calculating a motion state for a plurality of objects at a first time;

calculating a potential motion state for the plurality of objects at a second time;

arranging a plurality of times of impact (TOIs) in chronological order, each TOI associated with a pair of objects and a TOI event;

processing TOI events sequentially to determine if a collision is valid;

generating TOIs in response to valid collisions; and

simulating object collisions using a set of valid TOI events.

15. The method of claim 14 wherein the first time corresponds to a first frame and the second time corresponds to a second frame.

16. The method of claim 14 wherein a TOI is calculated between two bodies using a distance interval between the bodies, the interval representing a maximum penetration depth and a maximum separation distance.

17. The method of claim 14 wherein a plurality of TOI events generated from a plurality of colliding objects are solved simultaneously.

18. The method of claim 14 wherein maximum penetration distance is increased between a pair of colliding bodies over a number of simulation steps in order to reduce the number of TOIs generated.

19. The method of claim 14 wherein distance interval used to calculate a TOI is chosen from a dispatch table based on an assigned parameter.

20. A method of reducing collision detection processing time, the method comprising the steps of:

detecting a collision of a first object and a second object;

calculating an impulse, the impulse adapted for changing a velocity associated with the first object or the second object; and

determining if application of the impulse to the first object results in the first and second objects moving apart at a point of collision.

21. The method of claim 20 further comprising the step of

moving the first object away from the second object by applying the calculated impulse to the first object during the collision.

22. The method of claim 21 further comprising the step of applying the calculated impulse to the second object during the next PSI time step.

23. A method of identifying a potential collision event for two simulated bodies, the method comprising the steps of

calculating an initial separation distance and an initial separation direction between the two bodies;

updating a distance value associated with each body as each body moves; and

determining if a potential collision event may occur between the two bodies using the distance value, the initial separating distance and the initial separation direction.

24. The method of claim 23 wherein the distance value is based on linear movement in a direction of the separation distance and an angular movement multiplied by a worst case angular movement multiple.

25. The method of claim 23 further comprising the step of engaging a collision detection system in response to a potential collision event.

26. The method of claim 23 further comprising the step of terminating a collision detection system in response to a determination that a potential collision event will not occur for a specified time period.

27. A method of simulating two convex objects, the method comprising the steps of

calculating an initial separation distance and an initial separation direction between a corner of the first object and a planar surface of the second object;

updating a distance value measured between the corner and the planar surface as one object moves relative to the other object; and

determining a potential collision state between the two objects using the distance value, the initial separating distance and the initial separating direction.

28. The method of claim 27 further comprising the step of tracking a plurality of distance values measured between each corner of the first object and the planar surface of the second object.

29. A method of calculating contact points between two bodies, each body having one or more convex pieces, the method comprising the steps of

generating a convex hull for each of the two bodies;

calculating a contact point between each of the convex hulls;

determining whether the contact point lies on an inner convex portion of both bodies;

if it does, using the contact point for collision detection; and

if it does not, generating additional contact points.

30. The method of claim 29 wherein the determination of whether a contact point lies on the inner convex pieces of both bodies comprises the following steps:

determining if the point lies on a child convex piece for each of the two bodies; and

if the contact point lies on a child convex piece of both bodies, characterizing the contact point as suitable for collision detection.

31. A method of determining a separation vector for resolving interpenetration events involving a plurality of objects in a physics engine, the method comprising the steps of:

identifying a first set of interpenetrating objects;

identifying a second set of interpenetrating object pairs from the first set;

transforming each interpenetrating object pair in the second set into a Minkowski space representation;

generating a vector set of candidate separation vectors for each Minkowski space representation, each candidate separation vector having a magnitude and a direction; and

selecting the separation vector from all sets of candidate separation vectors, wherein the separation vector selected indicates the direction and magnitude necessary to resolve the interpenetration of the plurality of objects.

32. The method of claim 31 wherein the separation vector chosen is the vector of smallest magnitude from all sets of candidate separation vectors that can resolve the interpenetration of the plurality of objects.

33. The method of claim 31 wherein the step of selecting the separation vector is performed by generating subspaces within each Minkowski space representation and overlapping the subspaces to identify a separation vector direction.

34. The method of claim 33 wherein the subspaces are generated using a Gilbert-Johnson-Keerthi collision detection based method.

35. A method of determining a separation vector for a plurality of interpenetrating objects in a physics engine, the method comprising the steps of:

associating a range of possible expansion directions with one of the objects;

reducing the cardinality of a vector set of candidate separation vectors in response to the range of possible expansion directions; and

resolving an interpenetration state for the plurality of objects using one separation vector.

36. The method of claim 35 further comprising the step of

limiting polytope expansion in the range of possible expansion directions associated with an object to improve physics engine processing.

37. The method of claim 35 wherein the range of possible expansion directions includes a single direction such that when a first object collides with a second object a separation vector for resolving a penetration state is calculated using a depth of penetration in the single direction.