Image display apparatus, method and program based on rigid body dynamics

• US 7,610,182 B2
• Filed: 03/09/2001
• Issued: 10/27/2009
• Est. Priority Date: 03/10/2000
• Status: Active Grant

• Current Assignee: Criterion Software Ltd. (Electronic Arts Incorporated)
• Original Assignee: Electronic Arts Incorporated
• Inventors: Claude, Lacoursiere, Smith, Russell Leigh
• Primary Examiner(s): JONES, HUGH M
• Application Number:
  US10/221,051
• Publication Number:
  US 20030179205A1
• Time in Patent Office: 3,154 Days
• Field of Search: 703/2, 703/7
• US Class Current: 703/2
• 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/04 Constraint-based CAD
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30

Abstract

An image display system and method that use physical models to produce a realistic display of a scene are disclosed. The image display method involves operating a computer having a display screen, a memory and a processing unit for simulating the motion of objects and displaying the results on the display screen. The method includes the steps of storing in the memory position and velocity parameters which define an initial state of a model system having a plurality of bodies, storing in the memory parameters which define at least one constraint function constraining the motion of the bodies in the model system, and calculating in the processor the position and velocity parameters which define the state of the system after a predetermined time step based on rigid body dynamics, including carrying out a semi-implicit integration step subject to the constraints, to determine the velocity after the step, including determining the constraint forces that act to keep the system in compliance with the constraints by ensuring that the first derivative of the constraint function is zero.

Claims

1. A computer-implemented method, using a computer having at least a processing unit and a memory, for determining motion of simulated objects each of which is represented by a data structure indicating characteristics of the simulated object, wherein each of at least some of the simulated objects have visual characteristics and simulated physical characteristics and wherein the motion of the simulated objects is to be in compliance with a physics model and is to be represented on a display device such that a viewer perceives the motion of the simulated objects in compliance with the physics model, the method comprising:

storing, in the memory, position parameters and velocity parameters, the position and velocity parameters defining an initial state of the physics model and the simulated objects;

storing, in the memory, constraint parameters defining at least one constraint function constraining the motion of the simulated objects according to the physics model, wherein the constraint parameters include at least one position constraint constraining the motion of the plurality of rigid bodies;

calculating, using the processor, the position and velocity parameters defining the state of the simulated objects after a predetermined time step based on rigid body dynamics, including;

a) carrying out a semi-implicit integration step subject to the constraints constraining the motion of the simulated objects, to determine the velocity after the step; and

b) determining constraint forces that act to keep the simulated objects in compliance with the constraints by ensuring that the first derivative of the constraint function is zero;

generating, using the processor, at the end of the predetermined time step, a screen image of a series of screen images for display on the display device, the screen image displaying a view of the simulated objects such that the viewer can perceive the motion of the simulated objects in compliance with the physics model, the screen image being based on the calculated position and velocity parameters defining the state of the simulated objects at the end of the predetermined time step; and

displaying the screen image on the display device;

wherein the physics model includes a model of friction in which the frictional force between a pair of objects is independent of a normal force between the objects for both elastic and inelastic collisions.

2. The method of claim 1, further comprising before the step of calculating in the processor the position and velocity parameters, a step of:

storing in the memory parameters defining a bounded constraint force to simulate the effects of friction in which the constraint force acts in the plane of contact between a pair of objects to prevent sliding of one of the pair of objects over the other of the pair, wherein the constraint force is bounded to be not greater than a predetermined constant value to allow sliding of the objects over one another and thus include dynamic friction in the simulation.

3. A method according to claim 1 wherein the calculating step includes carrying out the implicit integration by:

calculating the velocity parameters after the time step from the external forces, the constraint forces and the position and velocity parameters before the time step, and

calculating the position parameters after the time step from the external forces and constraint forces, the calculated velocity parameters after the time step and the position parameters before the time step.

4. A method according to claim 1 wherein the frictional force between a pair of objects is modelled as a bounded constraint force in which the constraint force acts in the plane of contact between the pair of objects to prevent sliding of one of the pair of objects over the other of the pair, wherein the constraint force is bounded to be not greater than a predetermined constant value to allow sliding of the objects over one another and thus include dynamic friction in the simulation.

5. A method according to claim 1 wherein the bounds on the constraint forces are included by a step of testing whether the constraint forces have a magnitude greater than a predetermined value and if so setting them to be that predetermined value.

6. A method of generating a display in a computer game according to claim 1.

7. A method according to claim 1, wherein the constraint forces are determined by solving the mixed linear complementarity problem using a Murty algorithm.

8. A method according to claim 5 wherein the linear complementarity problem is solved by solving the boxed LCP problem by the boxed Murty'"'"'s method.

9. A method according to claim 7 wherein the constraints are required to be held to within a predetermined tolerance ε

.

10. A method according to claim 9 where ε

has a value between 10<sup>−

4</sup> and 10<sup>−

2</sup>.

11. A method according to claim 1, in which the constraints are modelled using the first order expansion of the constraint function Φ

, such that Φ

=φ

_o+J_p(p′

−

p)=(1−

γ

)φ

_o, where γ

is a relaxation parameter, φ

_o is a constraint, J_p is the Jacobian of the constraint forces based on position, p′

is a position parameter after the predetermined timestep, and p is a position parameter before the predetermined timestep.

12. A method according to claim 11 wherein γ

and a predetermined tolerance ε

on the constraints are chosen to model a compliant coupling between two of the rigid bodies.

13. A computer readable medium storing a plurality of program code for controlling a data processor of a computer system, that when executed, cause the data processor to perform one or more tasks for simulating the motion of objects and displaying the results on a display screen, the computer system including a memory having memory locations for position parameters and for velocity parameters, the position and velocity parameters defining an initial state of a model system having a plurality of bodies, the plurality program code comprising:

program code for storing, in the memory, constraint parameters defining at least one constraint function constraining the motion of the bodies in the model system, wherein the constraint parameters include at least one position constraint constraining the motion of the plurality of rigid bodies;

program code for calculating the position and velocity parameters defining the state of the system after a predetermined time step based on rigid body dynamics, including;

a) program code for performing a semi-implicit integration step subject to the constraints constraining the motion of the simulated objects to determine the velocity after the step; and

b) program code for determining constraint forces that act to keep the system in compliance with the constraints by ensuring that the first derivative of the constraint function is zero; and

program code for generating, at the end of the predetermined time step, a screen image of a series of screen images for display on the display screen, the screen image displaying a view of the simulated objects such that the viewer can perceive the motion of the simulated objects in compliance with the physics model, the screen image being based on the calculated position and velocity parameters defining the state of the simulated objects at the end of the predetermined time step; and

program code for displaying the screen image on the display screen,

wherein the model system includes a model of friction in which the frictional force between a pair of objects is independent of a normal force between the objects for both elastic and inelastic collisions.

14. The computer readable medium of claim 13, wherein the data carrier is a cartridge for a computer game machine.

15. The computer readable medium of claim 13, wherein the semi-implicit integration step comprises:

program code for calculating the velocity parameters after the time step from external forces, the constraint forces and the position and velocity parameters before the time step, and

program code for calculating the position parameters after the time step from the external forces and constraint forces, the calculated velocity parameters after the time step and the position parameters before the time step each according to the constraints.

16. Apparatus for simulating the motion of objects and displaying the results on a display screen comprising:

a display screen,

a memory,

a processing unit,

and a computer program stored in the memory for causing the apparatus to carry out the steps of;

a) storing in the memory position and velocity parameters defining an initial state of a model system having a plurality of bodies,

b) storing in the memory parameters defining at least one constraint function constraining the motion of the bodies in the model system, wherein the at least one constraint function defines at least one position constraint constraining the motion of the plurality of rigid bodies,

c) storing in the memory parameters defining a bounded constraint force to simulate the effects of friction in which the constraint force acts in the plane of contact between a pair of objects to prevent sliding of one of the pair of objects over the other of the pair, wherein the constraint force is bounded to be not greater than a predetermined constant value to allow sliding of the objects over one another and thus include dynamic friction in the simulation, and wherein the bounded constraint force is independent of a normal force between the objects for both elastic and inelastic collisions;

d) calculating in the processor the position and velocity parameters defining the state of the system after a predetermined time step based on rigid body dynamics, including

i) carrying out a semi-implicit integration step subject to the constraints, to determine the velocity after the step; and

ii) determining the constraint forces that act to keep the system in compliance with the constraints by ensuring that the first derivative of the constraint function is zero; and

e) generating, at the end of the predetermined time step, a screen image of a series of screen images for display on the display screen, the screen image displaying a view of the simulated objects such that the viewer can perceive the motion of the simulated objects in compliance with the physics model, the screen image being based on the calculated position and velocity parameters defining the state of the simulated objects at the end of the predetermined time step, and

f) displaying, on the display screen, the screen image.

17. A computer-implemented method, using a computer, for simulating movement of a plurality of rigid bodies according to a physics model by calculating motion of the plurality of the rigid bodies the method comprising:

storing, into storage accessible to the computer, position parameters defining initial positions of a plurality of rigid bodies;

defining at least one position constraint constraining the motion of the plurality of rigid bodies, the at least one position constraint defining constraints on positions of the plurality of rigid bodies represented by the position parameters read from the storage;

providing the at least one position constraint to the computer;

determining a bounded constraint force, using the computer, wherein the bounded constraint force represents a frictional force between a pair of objects of the plurality of rigid bodies, the frictional force acting in a plane of contact between the pair of objects and wherein at least one reaction force is bounded to be not greater than a predetermined value relative to the frictional force, and wherein the bounded constraint force is independent of a normal force between the objects for both elastic and inelastic collisions;

calculating, using the computer, new position parameters for the plurality of rigid bodies using the computer, the new position parameters defining new positions of the plurality of rigid bodies after a predetermined time step, wherein the new position parameters depend on at least one reaction force that acts to keep the plurality of rigid bodies in compliance with the at least one position constraint, such that the new position parameters satisfy the at least one position constraint directly without an iterative error process; and

generating, using the processor, at the end of the predetermined time step, a screen image of a series of screen images for display on a display device, the screen image displaying a view of the simulated objects such that the viewer can perceive the motion of the simulated objects in compliance with the physics model, the screen image being based on the calculated position and velocity parameters defining the state of the simulated objects at the end of the predetermined time step; and

displaying the screen image on the display device.

18. The method according to claim 17, further comprising constraining at least one reaction force to not exceed a predetermined value by setting the at least one reaction force equal to the predetermined value if it would exceed the predetermined value.

19. The method according to claim 17, further comprising displaying an image of the plurality of rigid bodies at their calculated positions on a display.

20. The method according to claim 17, further comprising:

storing, into the storage, velocity parameters defining initial velocities of the plurality of rigid bodies;

defining at least one combined constraint constraining the motion of the plurality of rigid bodies, the at least one combined constraint defining constraints on velocities and positions of the plurality of rigid bodies represented by the velocity parameters and position parameters read from the storage;

providing the at least one combined constraint to the computer, and

wherein calculating the new position parameters depends on at least one reaction force that acts to keep the plurality of rigid bodies in compliance with the at least one position constraint and the at least one combined constraint.

21. The method according to claim 20, further comprising storing, into the storage, force parameters defining at least one initial force acting on the plurality of rigid bodies, and wherein the at least one constraint further includes constraints on the positions of the plurality of rigid bodies that depend upon the stored position parameters, the velocity parameters and the force parameters read from the storage.

22. The method according to claim 20, further comprising calculating new velocity parameters for the plurality of rigid bodies defining new velocities of the plurality of rigid bodies after the predetermined time step.

23. A computer system comprising a processor and instruction memory, the instruction memory comprising instructions that, when executed, calculate simulated movement of a plurality of rigid bodies according to a physics model from stored representations of the plurality of rigid bodies, the computer system comprising:

a data memory configured to store position parameters defining initial positions of the plurality of rigid bodies;

a constraint definer that, when executed, defines at least one position constraint constraining motion of the plurality of rigid bodies, the at least one position constraint defining constraints on positions of the plurality of rigid bodies represented by the stored position parameters read from the storage;

a friction modeler operable to determine a bounded constraint force, wherein the bounded constraint force represents a frictional force between a pair of objects of the plurality of rigid bodies, the frictional force acting in a plane of contact between the pair of objects, wherein at least one reaction force is bounded to be not greater than a predetermined value relative to the frictional force, and wherein the bounded constraint force is independent of a normal force between the objects for both elastic and inelastic collisions; and

a position parameter calculator that, when executed, calculates new position parameters for the plurality of rigid bodies defining new positions of the plurality of rigid bodies after a predetermined time step, wherein the new position parameters depend on at least one reaction force that acts to keep the plurality of rigid bodies in compliance with the at least one position constraint, such that the new position parameters satisfy the at least one position constraint directly without an iterative error process;

a image generator that when executed at the end of the predetermined time step, generates a screen image of a series of screen images for display on a display device, the screen image displaying a view of the simulated objects such that the viewer can perceive the motion of the simulated objects in compliance with the physics model, the screen image being based at least in part on the position parameters for the plurality of rigid bodies at the end of the predetermined time step;

wherein the processor is configured, when executed, to perform processing operations that implement the constraint definer and the position parameter calculator in accordance with computer executable instructions stored in the instruction memory.

24. Computer system according to claim 23, the computer executable instructions stored in the instruction memory further comprising instructions for determining a bounded constraint force, wherein the bounded constraint force represents a frictional force between a pair of objects of the plurality of rigid bodies, the frictional force acting in a plane of contact between the pair of objects and wherein at least one reaction force is bounded to be not greater than a predetermined value relative to the frictional force.

25. Computer system according to claim 23, the computer executable instructions stored in the instruction memory further comprising instructions for constraining at least one reaction force to not exceed a predetermined value by setting the at least one reaction force equal to the predetermined value if it would exceed the predetermined value.

26. Computer system according to claim 23, the computer executable instructions stored in the instruction memory further comprising instructions to generate a display of an image of the plurality of rigid bodies at their calculated positions on a display.

27. Computer system according to claim 23, wherein the data memory is further configured to store velocity parameters defining initial velocities of the plurality of rigid bodies, and wherein the constraint definer configured with the at least one constraint including at least one combined constraint constraining velocities and positions of the plurality of rigid bodies represented by the velocity parameters and position parameters stored in the data memory.

28. Computer system according to claim 27, wherein the data memory is further configured to store force parameters defining at least one initial force acting on the plurality of rigid bodies, and wherein the at least one constraint further includes constraints on the positions of the plurality of rigid bodies that depend upon the stored position parameters, the velocity parameters and the force parameters read from the data memory.

29. Computer system according to claim 27, further comprising a velocity parameter calculator configured to calculate new velocity parameters for the plurality of rigid bodies after the predetermined time step.

30. Computer system according to claim 23, further comprising a reaction force calculator configured to calculate at least one reaction force.

31. Computer system according to claim 30, wherein the reaction force calculator is configured, when executed, to calculate the at least one reaction force to not exceed a predetermined value by setting the at least one reaction force equal to the predetermined value if it would exceed the predetermined value.

32. Computer system according to claim 23, the computer executable instructions stored in the instruction memory further comprising instructions for defining at least one combined constraint constraining the motion of the plurality of rigid bodies, the at least one combined constraint defining constraints on velocities and positions of the plurality of rigid bodies represented by the velocity parameters and position parameters read from the storage, and for calculating new position parameters for the plurality of rigid bodies defining new positions of the plurality of rigid bodies after a predetermined time step, wherein the new position parameters depend on at least one reaction force that acts to keep the plurality of rigid bodies in compliance with the at least one position constraint and the at least one combined constraint.

33. Computer system according to claim 32, the computer executable instructions stored in the instruction memory further comprising instructions for storing force parameters defining at least one initial force acting on the plurality of rigid bodies and for implementing constraints on the positions of the plurality of rigid bodies that depend upon the stored position parameters, the velocity parameters and the force parameters read from the data memory.

34. Computer system according to claim 32, the computer executable instructions stored in the instruction memory further comprising instructions for calculating new velocity parameters for the plurality of rigid bodies defining new velocities of the plurality of rigid bodies after the predetermined time step.

35. Processing apparatus for calculating simulated movement of a plurality of rigid bodies according to a physics model, the processing apparatus comprising:

means for storing position parameters defining initial positions of a plurality of rigid bodies;

means for defining at least one position constraint constraining the motion of the plurality of rigid bodies, the at least one position constraint defining constraints on positions of the plurality of rigid bodies represented by the position parameters read from the means for storing;

means for determining a bounded constraint force, wherein the bounded constraint force represents a frictional force between a pair of objects of the plurality of rigid bodies, the frictional force acting in a plane of contact between the pair of objects, wherein at least one reaction force is bounded to be not greater than a predetermined value relative to the frictional force, and wherein the bounded constraint force is independent of a normal force between the objects for both elastic and inelastic collisions;

means for calculating new position parameters for the plurality of rigid bodies defining new positions of the plurality of rigid bodies after a predetermined time step, wherein the new position parameters depend on at least one reaction force that acts to keep the plurality of rigid bodies in compliance with the at least one position constraint, such that the new position parameters satisfy the at least one position constraint directly without an iterative error process; and

means for generating, at the end of the predetermined time step, a screen image of a series of screen images for display on a display device, the screen image displaying a view of the simulated objects such that the viewer can perceive the motion of the simulated objects in compliance with the physics model, the screen image being based on the calculated position and velocity parameters defining the state of the simulated objects at the end of the predetermined time step; and

means for displaying the screen image on the display device.

36. A data carrier tangibly embodying a program of machine readable instructions executable by a digital processing apparatus having stored thereon instructions that, when executed, calculate simulated movement of a plurality of rigid bodies according to a physics model, the program comprising:

program code for storing, into storage accessible to the computer, position parameters defining initial positions of a plurality of rigid bodies;

program code for defining at least one position constraint constraining the motion of the plurality of rigid bodies, the at least one position constraint defining constraints on positions of the plurality of rigid bodies represented by the position parameters read from the storage;

program code for determining a bounded constraint force, wherein the bounded constraint force represents a frictional force between a pair of objects of the plurality of rigid bodies, the frictional force acting in a plane of contact between the pair of objects, wherein at least one reaction force is bounded to be not greater than a predetermined value relative to the frictional force, and wherein the bounded constraint force between the pair of objects is independent of a normal force between the objects for both elastic and inelastic collisions;

program code for calculating new position parameters for the plurality of rigid bodies defining new positions of the plurality of rigid bodies after a predetermined time step, wherein the new position parameters depend on at least one reaction force that acts to keep the plurality of rigid bodies in compliance with the at least one position constraint, such that the new position parameters satisfy the at least one position constraint directly without an iterative error process; and

program code for generating, at the end of the predetermined time step, a screen image of a series of screen images for display on a display device, the screen image displaying a view of the simulated objects such that the viewer can perceive the motion of the simulated objects in compliance with the physics model, the screen image being based on the calculated position and velocity parameters defining the state of the simulated objects at the end of the predetermined time step; and

program code for displaying the screen image on the display device.

37. The data carrier tangibly embodying a program of machine readable instructions according to claim 36, further comprising program code for constraining at least one reaction force to not exceed a predetermined value by setting the at least one reaction force equal to the predetermined value if it would exceed the predetermined value.

38. The data carrier tangibly embodying a program of machine readable instructions according to claim 36, further comprising program code for displaying an image of the plurality of rigid bodies at their calculated positions on a display.

39. The data carrier tangibly embodying a program of machine readable instructions according to claim 36, further comprising:

program code for storing, into the storage, velocity parameters defining initial velocities of the plurality of rigid bodies;

program code for defining at least one combined constraint constraining the motion of the plurality of rigid bodies, the at least one combined constraint defining constraints on velocities and positions of the plurality of rigid bodies represented by the velocity parameters and position parameters read from the storage; and

program code for calculating new position parameters for the plurality of rigid bodies defining new positions of the plurality of rigid bodies after a predetermined time step, wherein the new position parameters depend on at least one reaction force that acts to keep the plurality of rigid bodies in compliance with the at least one position constraint and the at least one combined constraint.

40. The data carrier tangibly embodying a program of machine readable instructions according to claim 39, further comprising program code for storing, into the storage, force parameters defining at least one initial force acting on the plurality of rigid bodies, and the at least one constraint further includes constraints on the positions of the plurality of rigid bodies that depend upon the stored position parameters, the velocity parameters and the force parameters read from the storage.

41. The data carrier tangibly embodying a program of machine readable instructions according to claim 39, further comprising program code for calculating new velocity parameters for the plurality of rigid bodies defining new velocities of the plurality of rigid bodies after the predetermined time step.