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

[0001] The invention relates to an image display system and method, and in particular to an image display system that uses physical dynamic models to produce a realistic display of a scene.

[0002] It is becoming increasingly useful to display scenes on computer displays that represent the real world. Such scenes may occur in virtual reality devices, simulators and computer games.

[0003] One way of providing such scenes is to film images and to display the recorded images on the display. However, this approach requires that the content of the scene is predetermined and appropriate film sequences created and pre-stored in the computer. Thus, such an approach cannot be used where the scenes are not wholly scripted, which makes the approach unsuitable for simulations and computer games in which the user can carry out actions not predicted by the programmer.

[0004] An alternative approach uses a simulation of rigid body dynamics to allow scenes including such objects to be displayed realistically. In order to cope with simulation applications, the model has to be able to cope with a variable number of simulated objects that can be created and destroyed.

[0005] Such models should model a plurality of rigid objects that can interact with each other, subject to constraints. For example, if one object is hinged to another object that hinge acts as a constraint; the two objects cannot move independently. The existence of constraints makes the problem much more difficult to solve than a simple application of Newton's laws of motion.

[0006] A number of prior approaches have been presented but these have not proven wholly successful. The most suitable for simulation of multiple objects are so-called extended coordinate methods in which the constraints are introduced using Lagrange multipliers that correspond to forces that maintain the constraints. However, there are difficulties with these approaches.

[0007] Firstly, the known methods use a large number of variables, using nearly doubling the number of variables (because of the Lagrange multipliers) to describe the system, which results in them being eight times more computationally intensive than an equivalent system without constraints. Thus, the prior art methods tend to be highly inefficient.

[0008] Secondly, the known methods use differential algebraic equations that are numerically rather stiff. Simple methods for solving such equations are rather unstable.

[0009] Thirdly, it is not known how to efficiently incorporate friction into such systems. As will be appreciated, friction is an important property of real physical systems that has to be modelled correctly for a realistic result. This is a difficult problem but a working solution was reported in D. E. Stewart and J. C. Trinkle, An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction, International for numerical methods in engineering, volume 39 pages 2673-2691 (1996), and was improved on by Mihai Anitescu and F. A. Potra, Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementarity problems, Non-linear Dynamics, volume 14 pages 231-237 (1997). The approach described allows consistent models in which the velocities can always be computed and are always finite. The disadvantage of the approach is that the model involves solving a particular class of linear complementarity problem which has a structure such that not all algorithms are suitable. Anitescu and Trinkle used the Lemke algorithm but this is inefficient and prone to large errors.

[0010] A fourth difficulty with prior art approaches is that the constraints are generated automatically; such constraints need not be not independent of one another which results in the system being degenerate. Geometric analysis software that performs collision detection cannot check whether all the constraints are truly independent of each other, and only during simulation can it be determined that some constraints are redundant. Such degeneracy can cause real problems for the simulations, especially in the case of collision detection which checks for proximity of pairs of objects, whereas the constraint degeneracy only appears at the system level including all the rigid bodies in the system.

[0011] Fifthly, known systems do not cope well with stiffness, i.e. rigid spring-like systems and compliant elements. The only tractable solutions ignore contact and friction altogether, which makes them unsuitable for analysis of arbitrary physical systems.

[0012] Accordingly, there is a need for an image display system that ameliorates or alleviates some or all of these difficulties.

[0013] The known models require the solution of linear complementarity problems, a particular type of constrained equation. In general, a linear complementarity problem can be put in the form:

[0014] where M is an n by n matrix and z and w are real n-dimensional vectors. The problem requires finding the solution of equation (1), i.e. the values of z and w, subject to the constraints (2)-(4).

[0015] This is fundamentally a combinatorial problems, and solutions generally search through two index sets, where each index is in one of the sets. The first set is a set of active variables for which w_i0 and the second set is a set of free variables for which z_i0. The problem is then partitioned as $\begin{array}{cc}\left[\begin{array}{cc}{M}_{}& M_{}\\ M_{}& M_{}\end{array}\right]\left[\begin{array}{c}{z}_{}\\ 0\end{array}\right]+\left[\begin{array}{c}{q}_{}\\ q_{}\end{array}\right]=\left[\begin{array}{c}0\\ w_{}\end{array}\right]& \left(5\right)\end{array}$

[0016] where and specify indices in the first and second sets respectively.

[0017] This is equivalent to the linear algebra problem

[0018] which must be solved for z while w is calculated by substitution. M is known as the principal submatrix.

[0019] Various implementations are known. They differ in how the two sets are revised. They use a computed complementarity point which is a vector s such that $\begin{array}{cc}{s}_i=\{\begin{array}{cc}{z}_i& i\\ w_i& i\end{array}& \left(7\right)\end{array}$

[0020] The methods go through a sequence of sets until a solution is found, i.e. until s_i0 i1, 2 . . . n.

[0021] The Murty principal pivoting algorithm is known from Murty and Yu: Linear Complementarily, Linear and Non Linear programming available at www.personal.engin.umich.edu/-murty/book/LCPbook/index.html, and also in an earlier edition published by Helderman-Verlag, Heidelberg (1988), the content of which is incorporated into this specification by reference.

[0022] The indices are assigned to a set, and i is set to zero. Then, the principal submatrix Man is formed and solved for z using equation (6).

[0023] Then s⁽ⁱ⁾zw is calculated, where

[0024] If s0 then the algorithm has found a solution. Otherwise, the smallest index j for which the corresponding element of s is found. If this index is in the first set, the index is moved to the second, otherwise the index is in the second set in which case it is moved to the first set. The loop parameter i is incremented and the loop restarted until a solution is found.

[0025] The method is illustrated in the flow chart of FIG. 1.

[0026] The method is stateless and can be started from any initial guess for the division of the indices into first and second sets. The matrix will work on any P matrix and in particular on any positive definite matrix.

[0027] The method can fail where the matrix is positive semi-definite. Such matrices arise in real physical systems, and can be made positive definite by adding a small amount to each element along the diagonal. Kostreva in Generalisation of Murty's direct algorithm to linear and convex quadratic programming, Journal of optimisation theory and applications, Vol. 62 pp 63-76 (1989)demonstrated how to solve such positive semi-definite problems. Basically, the problem is solved for an initial value of , is then reduced until the solutions converge; if the solutions diverge the problem is unfeasible.

[0028] According to the invention, there is provided a method, a computer program recorded on a data carrier (e.g. a magnetic or optical disc, a solid-state memory device such as a PROM, an EPROM or an EEPROM, a cartridge for a gaming console or another device), for controlling a computer (e.g. a general purpose micro, mini or mainframe computer, a gaming console or another device) having a display screen, a memory and a processing unit, the computer program being operable to control the computer to carry out the method, and a computer programmed to carry out the method.

[0029] The method according to the invention may include the steps of:

[0030] storing in a memory position and velocity parameters defining an initial state of a model system having a plurality of bodies,

[0031] storing in the memory parameters defining at least one constraint function constraining the motion of the bodies in the model system, and

[0032] 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

[0033] carrying out a semi-implicit integration step subject to the constraints, to determine the velocity after the step, including

[0034] 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.

[0035] In known approaches, the second derivative was held to be zero. However, the method according to the invention provides much faster calculation.

[0036] The method may cause the computer to carry out the further step of displaying an image of the objects at their calculated positions on the computer display screen, so that the display shows the objects on the screen using physical laws to simulate their motion.

[0037] The means for determining the constraint forces may include solving the linear complementarity problem using the Murty algorithm.

[0038] The calculating step may include carrying out the implicit integration by

[0039] 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

[0040] 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; and

[0041] In prior art image display methods implementing rigid body dynamics the accelerations have been taken as parameters. In the method according to the invention, the parameters calculated are position and velocity.

[0042] The means for solving the linear complementarity problem may include solving the boxed LCP problem by the modified Murty's method.

[0043] In order to implement maximum bounds on the constraint forces the calculation may include the 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. This has not previously been done but leads to a more efficient solution.

[0044] Preferably, the model includes a model of friction. Static friction requires that the tangential force f_t of magnitude less than or equal to the static friction coefficient _s times the normal force f_n. The force f_t due to dynamic friction has a magnitude equal to the dynamic friction coefficient _s times the normal force, and a direction given by f_tv_t0.

[0045] The dependence of the frictional force on the normal force can be replaced by a novel approximation in which the friction, dynamic or static, is not dependent on the normal force. This force then corresponds to a simple bounded multiplier, i.e. a force that can have up to a predetermined value. Thus the force exactly fits the model used in any event in which the constraint forces Lagrange multipliers have maximum values; friction in the model is equivalent to another bounded constraint force. Thus making this approximation substantially simplifies the inclusion of friction in the model.

[0046] Accordingly, the method may include a model of friction in which the frictional force between a pair of objects is independent of the normal force between the objects.

[0047] The frictional force between each pair of objects may be 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.

[0048] In order to implement bounded constraint forces, the method may include the 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.

[0049] The method may include a relaxation parameter introduced to determine how exactly to satisfy the constraints.

[0050] The friction model taken leads to a symmetric positive definite linear complementarity problem, in which the only friction conditions are simple inequalities. This allows the use of the much more efficient Murty algorithm that the less useful Lemke algorithm.

[0051] From further aspects, this invention provides a computer program that is a computer game program, which game program may be recorded within a cartridge for a computer game machine; and a computer game programmed to generate a display by means of a computer program according to any preceding claim.

[0052] Specific embodiments of the invention will now be described, purely by way of example, with reference to the accompanying drawings in which

[0053] FIG. 1 shows a flow diagram of a prior art implementation of the Murty algorithm,

[0054] FIG. 2 shows a computer running the present invention,

[0055] FIG. 3 shows a flow diagram of the implementation of the present invention,

[0056] FIG. 4 shows the friction pyramid,

[0057] FIG. 5 shows the box-friction model used to approximate to the friction pyramid,

[0058] FIG. 6 is a flow chart of the method including friction, and

[0059] FIG. 7 is a flow chart of the program according to the invention.

[0060] The implementation of the invention that will be described includes a computer system 1 having a display 3, a memory 5 and a processor. The computer system has software 9 loaded into the computer memory to allow the computer system to display a simulation of the real physical world on the display 3. The display 3 may be a conventional computer display screen, for example an Liquid Crystal Display (LCD) screen or a Cathode Ray Tube (CRT) screen, or the display 3 may be a less conventional display type such as virtual reality goggles or multiple screens of a coin operated video game, of the type installed in public places.

[0061] A physical system which has n rigid bodies is modelled. The i^th body has a mass m_i, and a position vector p which has seven coordinates, three to define the position of the rigid body and four being the Euler parameters of the body defining its orientation. Each body also has velocity vector v which has six coordinates, three being the three components of linear velocity and three being the three components of angular velocity, each relative to the inertial frame. Further details about the coordinates and the matrices used to convert between coordinates in the local reference frame and those in an inertial frame are given in sections 1 to 1.4 of Appendix 1.

[0062] The key point to note is that equations 1.36 and 1.37 of Appendix 1 define Newton's laws for a dynamical system in a form similar to equation (1), i.e.

[0063] where M is the block diagonal matrix defined in equation 1.37 of appendix 1.

[0064] A rigid body dynamics problem then becomes equivalent to solving equation (7) subject to the dynamic constraints. This is carried out by numerical integration. The difficult part is calculating the constraint force.

[0065] The initial state of the system is set up in the computer memory, and includes the above parameters.

[0066] Constraints governing the rigid bodies may also be set up. The software 9 may include definitions of such constraints. An example of a constraint is a hinge between two rigid body elements so that the elements cannot move independently. The system contains constraint initialisation routines for setting up such constraints. A separate routine is provided for each type of constraint; the routine is called, defining the one, two or three constrained elements and other information required to specify the constraint. For example, if there are two constrained elements in the form of two rigid bodies are joined by a ball and socket joint, the information required is the identity of the constrained elements and the position of the ball and socket joint. The constraint information is stored in the form of the Jacobian of constraint.

[0067] A simple example of a constraint would be a rigid floor at height zero in the model. The constraint function (p_x,p_y,p_z) is then chosen to be (p)p_z, the conventional constraint (p)0 then being a definition of the constraint.

[0068] The solution method used requires a Jacobian J of the constraint function (p)this is related to the more conventional Jacobian J_p of the function (p) with respect to position by JJ_pQ where Q is defined at equation 1.40 of Appendix 1.

[0069] The method used does not require storing the second derivative of the constraint function.

[0070] After the initial conditions and constraints are set up, the routine may be called to simply step forward in time by a predetermined time period. Indeed, the use of this simple program structure in which a routine is called with a matrix and outputs a like matrix of the results one time step forward is a significant advantage over prior approaches in which the movement forward in time has not been encapsulated in this way.

[0071] The way in which the system moves one step forward is based on simple Euler integration, i.e. calculating the final positions and velocities from the initial positions and velocities and the applied forces. Of course, some of the forces are the constraint forces that ensure that the system remains in accordance with the constraints; the way these are calculated will be described below.

[0072] Euler integration can be explicit, in which the integration is based on the values at the start of the step, or implicit in which the values at the end of the step are used. In the method of the invention, a semi-implicit approach is used in which the positions after the step are calculated using the positions at the start of the step and the velocities at the end of the step and the velocities are calculated explicitly. Put mathematically, the position p and velocity v at the (i1)^th step after a time h are given by

[0073] where M is the block diagonal matrix defined in Appendix 1 and f is the sum of the forces on the system, including the constraint forces to maintain the constraint. Note that the equations for the position variables are implicit and the equation for velocity explicit. Thus, the above equations need to be solved subject to the constraint equations.

[0074] Of course, in order to carry out the above calculation it is necessary to calculate f. The force f is made up of the external force plus the effects of the external torques plus the constraint force that keeps the system in accordance with the constraints. Thus, the constraint forces on the system must be calculated. Appendix 1 at 1.51 demonstrates how to do this for an explicit Euler scheme to calculate subject to the constraint (p)0. In the conventional scheme, the constraints are calculated by setting the second derivative of to zero.

[0075] In the method according to the embodiment, however, this is not done and the first derivative $\frac{}{p}$

[0076] is set to zero.

[0077] The detail is set out in sections 1.5 to 1.6 of Appendix 1. The approach of using the velocity constraints rather than the second derivative of the constraint function has both advantages and disadvantage. The key disadvantage is that although this approach guarantees that the velocity constraints are satisfied it does not guarantee that the position constraints are.

[0078] The constraint equation may be given by

[0079] where J_p is the Jacobian of the constraint forces based on the position, i.e. $J_p=\frac{}{p}.$

[0080] This is related to the J actually calculated by JJ_pQ.

[0081] Rather than satisfy this exactly, the parameter 7 is introduced by amending the right hand side of equation (5) so that it reads

[0082] When 1 equation (6) becomes equivalent to equation (5). A value of 0.2 has been found suitable.

[0083] A solution for the forces is given at 1.5.5. of Appendix 1.

[0084] The result is: $\begin{array}{cc}\left(J.M^{-1}{J}^T\right)=\frac{-{}_0}{h^2}-\frac{\mathrm{Jv}}{h}-{\mathrm{JM}}^{-1}\left(f_c+f_r\right)& \left(14\right)\end{array}$

[0085] This is an equation in the form Axbw and it can be solved by the algorithm presented below to find the vector . The constraint force f_c is then given by

[0086] The constraint forces may then be fed into the integration step to compute the position of each object after the timestep.

[0087] It should be noted that the method uses bounded constraints. In other words, each element of the force is not allowed to become arbitrarily large as in previous methods but is bounded. This is simply implemented by testing to see if the elements of the force are larger than the bound and if so reducing the element to the bound.

[0088] The problem posed is not directly amenable to simple solution by the Murty algorithm. Rather, it has the slightly different structure of a boxed linear complementarity problem, as follows:

[0089] The w and w terms come from the integration step; they correspond to forces/accelerations from upper and lower boundaries respectively, the positions of the boundaries being given by u and l. The z term corresponds to the differential of the velocity.

[0090] The result gives the constraint force which can be plugged into the integration.

[0091] The above formalism is equivalent to a mixed complementarity problem defined as $\begin{array}{cc}\left[\begin{array}{ccc}A& -I& I\\ I& 0& 0\\ -I& 0& 0\end{array}\right]\left[\begin{array}{c}\begin{array}{c}z\\ w_{+}\end{array}\\ w_{-}\end{array}\right]+\left[\begin{array}{c}\begin{array}{c}q\\ -l\end{array}\\ u\end{array}\right]=\left[\begin{array}{c}\begin{array}{c}0\\ \end{array}\\ v\end{array}\right].& \left(17\right)\end{array}$

[0092] This can be solved by partitioning the second set defined above into two sets, and , so that z_jl_j for j and z_ju_j for j. Afterwards, the Murty algorithm is followed with a different definition of the complementarity point, namely, $\begin{array}{cc}{s}_j=\{\begin{array}{cc}\min \left(z_j-l_j,u_j-z_j\right)& j\\ \left(A_{}{z}_{}-A_{}{l}_{}-A_{}{u}_l+q_y\right)& j\\ -\left(A_{}{z}_{}-A_{}{l}_{}-A_{}{u}_{}+q_{}\right)& j\end{array}& \left(18\right)\end{array}$

[0093] The least index rule is applied to the complementarity point as follows:

[0094] If j and z_j<l_j then remove j from and put it in

[0095] If j and z_j>u_j then remove j from and put it in

[0096] If j add j to and remove it from

[0097] If j add j to and remove it from

[0098] The loop is then repeated until there is no element s_j<0.

[0099] FIG. 3 sets out a flow chart of the Murty algorithm that is used to model the constraints. It is based on that of FIG. 1, with amendments to cope with the bounded parameters which are may be used to model friction.

[0100] This solution will be referred to as the Boxed LCP solution, which has been developed independently by the inventors.

[0101] The above solution may be refined by replacing the zeroes with a tolerance parameter. This is similar to the Kostreva method, except here the parameter is not reduced but simply kept at a constant value say 10^3.

[0102] The parameters and may be chosen to model a compliant coupling between two of the rigid bodies. In this way springs and compliant bodies may be included in the model without any complexity.

[0103] Appendix 4 sets out how the parameters and already present in the model can be used to model stiff springs. Such parameters are very useful for modelling car suspensions, and the like. Thus, the use of the model provides the unexpected benefit of being usable not merely to ensure fitting of the constraints but can also be used to model stiff springs without any additional parameters or programming.

[0104] A key advantage provided by the approach selected is that it allows the inclusion of friction.

[0105] The friction constraint can thus be considered to be given by a cone which; if the contact force between two bodies is given by a force vector the values of the dynamic friction when the bodies slide is given by a cone in the three dimensional space of the force (FIG. 4). In the invention this cone is approximated by a four sided box, in other words friction is approximated by a model in which the transverse frictional force is not dependent on the normal force (FIG. 5).

[0106] The method thus works as follows:

[0107] Step 1: For each contact point, apply a non-penetration constraint and a static friction constraint.

[0108] Step 2: Estimate a normal force _i for each point

[0109] Step 3: At each point of contact, limit the Lagrange multipliers that enforce zero relative velocity to have a maximum value proportional to the normal force: i.e.

[0110] Step 4: solve with the boxed Murty algorithm

[0111] Step 5: refine estimate of normal forces and repeat if required.

[0112] A flow chart of this procedure is presented in FIG. 6.

[0113] Surprisingly, such a crude model still gives good realistic results. The real advantage is that the model does not involve a combination of the Lagrange multipliers (constraint forces)as a constraintthe constraints are of the simple form f_ta constant, whereas for more realistic model the upper bound on f_t would depend on the normal force. This allows the use of a simpler algorithm as set out above. Indeed, the bounded constraint force has exactly the same bounded force as used for all of the constraints on the objects; accordingly adding friction does not add significantly to the difficulty of solving the problem.

[0114] Thus, the described embodiment allows much faster processing of the simulation.

[0115] A list of the routines used in the program implementing the embodiment, including the many routines to set up individual types of constraint, is provided in Appendix 2.

[0116] The program implementing the above is schematically shown in FIG. 7.

[0117] Firstly, a body data array containing the information about each rigid object, i.e. its position, orientation and mass is initialised. A constraint data array is likewise initialised containing parameters defining the constraints.

[0118] In the next step, the constraint data array is interrogated to create a list of Jacobians.

[0119] Then, a matrix A is calculated given by AJM¹J^T where M is the mass matrix as defined in Appendix 1 and J is the Jacobian. This step is done so that A is an upper triangle matrix (and symmetric).

[0120] The upper triangle elements of A are then copied to the lower, and the diagonal modified. Rotational force may be added to the bodies at this stage. The A matrix is then complete.

[0121] Next, A is factorised to find A¹ by Cholesky deposition.

[0122] An intermediate result rhs is then calculated as follows: Calculation of rhs, for each body:

[0123] Then, rhs, A, A¹ and the lower and upper constraint vectors l and u are sent to a routine which calculates , the Lagrange multipliers, by solving equation (16) by these parameters by the boxed LCD method as described above.

[0124] Next, the resultant forces are calculated from and J, and the results passed to the semi-implicit integrator.

[0125] This outputs the velocity, force, position and orientation, in the form of the transformation matrix and orientation quaternion of each body.

[0126] Finally, a screen image is calculated displaying the objects in their new locations and this is displayed on the video display unit.

[0127] The method described works much faster than previously known methods. Accordingly, it becomes possible to more accurately simulate real time scenes, and provide an improved simulation that more rapidly and accurately simulates the real physical world.