Few real world objects retain their shape and structure when subjected to real world forces. Simulating these changes in shape will inevitably lead to more realistic games and more interesting gameplay mechanics. This field of physics simulation isrefered to as soft body dynamics. This is the field of physics simulation that focuses on objects that change in shape or size (are deformable). In normal rigid body dynamics this does not occur, and any two points on the body will always be the same distance from one another. This is not true in soft body dynamics, though bodies are expected to keep their shape to some degree.

Deformable objects are defined by their undeformed shape (the equilibrium shape) and by a collection of parameters it owns that define how it deforms when forces are applied to it. If we think of a shape as being made up of a collection of points in space, we can devise a set of rules to act on each of these smaller points that will provide the deformation of the whole shape. There are various ways to generate this set of rules; I will describe two techniques in this article.

First we will look at the finite element method (FEM). This method was first described in 1943 to describe the dispersion of vibrations through objects, it was then expanded to allow more general applications in engineering and stress testing in 1956. Due to a lack of computing power FEM was limited to the expensive mainframe computers of the aeronautic, civil engineering and defence industries. Because of the increase in computing power and optimisations to the technique, FEM is now at a point where it is cheap enough to begin to put them into real-time applications [4]. But how do these methods work? FEM will divide an object into a complex system of points, creating a grid called a mesh. Each node in this mesh contains the structural properties of the shape which define how the object will react when forces are applied [1]. These properties can include:

- Mass, volume
- Strain energy, stress strain
- Force, displacement, velocity, acceleration
- Any problem specific user defined attribute

When creating the mesh, the nodes can be assigned in different ways to help with performance and define how an object will be deformed. Areas with lots of nodes will be subject to more complex deformations than areas with few. How these nodes are generated is totally dependent on the material being simulated, cloth for instance would require an even spreading of nodes across the whole object to ensure that the deformations look as natural as possible. When this technique is being used to test the structural integrity of an object for engineering purposes, node density is usually high around places that are prone to fracture, fillets, areas of complex details and high stress areas. Once we have a complete set of nodes and edges between adjacent nodes we perform the mathematics on each node that will translate it. Because each node is connected to the 3D representation of the object beneath it, pulling and pushing the nodes will pull and push the object with it, creating a visual representation of the deformation that can be seen by a user [2].

In an attempt to briefly describe the mathematics that is performed on each node in the grid we can look at a simple problem that can be solved by FEM, a three-member truss in two dimensions [5]. Each corner of the triangle formed can be treated as a node. To find the displacement of each node we must find how it is being pushed by each node it is connected to. This gives us a bar with a node at either end, each of which have displacements in the X and Y dimensions, giving four different displacements over all. Each of these displacements will then have a corresponding force, the relationship between force and displacement is:

Force = Displacement * “Stiffness”

For one bar, this gives the following equations:

F_{1} = k_{11}u_{1} + k_{12}u_{2} + k_{13}u_{3} + k_{14}u_{4}

F_{2} = k_{21}u_{2} + k_{22}u_{2} + k_{23}u_{3} + k_{24}u_{4}

F_{3} = k_{31}u_{1} + k_{32}u_{2} + k_{33}u_{3} + k_{34}u_{4}

F_{4} = k_{41}u_{1} + k_{42}u_{2} + k_{43}u_{3} + k_{44}u_{4}

Or the matrix:

This matrix is known as the “stiffness matrix”, it defines the properties of the bar between the two nodes and how it will act when subjected to outside forces. The stiffness matrices of the whole mesh made by the nodes is calculated in the same way for every connection and depends upon the properties given to the nodes. The stiffness matrix for a bar at an angle “theta” to the x-axis can be found using:

Where *A* = Area of the rod (volume in three dimensions)

*E* = Young’s Modulus of the rod

*L* = Length of the rod

*c* = cos ”theta”

*s* = sin “theta”

Now we can derive a set of equations that describe the forces acting on a node when it is at rest. The nodal forces must be equal and opposite to any outside forces. How many nodal forces act on each node depend on the amount of other nodes the node is connected to. For equlilibrium at any node we have one externally applied force in each direction, we know that subtracting each nodal force acting in the same direction (given by the stiffness matrix) will give zero. Therefore each external force (number of dimensions * number of nodes) at equillibrium is the equal to the sum of the nodal forces acting upon it.

Where *R* = Total external force

*n* = Number of dimensions * number of nodes

*x* = Coefficient of displacement direction

When a load is applied we need to know how the external forces change. This is where the constraints of the system are key, if a node is fixed then it can be disregarded, we also need to decide if a load can act on an external force. The more external forces effected by loads, the more deformable the object. A resultant force will be zero if it is not effected by a load or positive or negative depending upon the direction of the load. We can then solve the above matrix to find the total displacement in every direction.

Another common method for soft-body physics is the mass-spring system [3]. These systems are widely regarded to be the simplest and most intuitive of all the various soft-body physics systems. This method models an object as a collection of point masses connected together by a grid of massless springs. To find the shape of an object at any given time we only need the position and velocity of every one of these masses, then the forces acting on each mass is computed using the force of all the spring connections with its neighbours, as well as other external forces such as gravity. The motion of each particle can then be simply expressed using Newton’s second law. These methods were first used for the modelling of faces in 1987; soon, the methods were expanded to be used in the modelling of skin, fat and muscle. They were also used to simulate the movement of snakes worms and fish, creatures that bend as they move. In these systems, the rest-length of the springs varied over time to simulate muscle actuation.

Springs are commonly modeled as being linearly elastic; the force acting on mass *I, *created by the connection between particle *I *and particle *j *is given by:

Where Xij = The difference between the two masses positions ( - )

Ks = The spring’s stiffness

Lij= The springs rest length

However, physical bodies are not perfectly elastic and dissipate energy during deformation. To account for this, viscoelastic springs are used to damp out relative motion. Thus, in addition to the equation above, each spring exerts a viscous force. This is given by:

Where Kd = The spring’s damping constant

These equations are derived from Hooke’s law, a useful approximation of how real-life springs act when compressed or expanded by external forces. Always attempting to return to its original length, with a greater force the further from this restitution length the spring becomes.

Mass-spring systems are known to be much less accurate than finite element methods [1], mass-spring models only seek to approximate deformations whereas TEM has the advantage of being built from the ground up on elasticity theory. Mass-spring systems are crucially not convergent; as the mesh is refined the simulation does not approach the correct solution. Spring constant are commonly chosen arbitrarily, and it is impossible to draw any conclusions about what material is supposed to be being modelled. For games this may not be an issue as the lack of accuracy may be perfectly acceptable and indeed many convincing simulations have been produced using this method. However, because the behaviour of a simulation is totally dependent upon the mesh of masses, the lack of generalisation may make people wary upon putting much effort into getting this system working. So we know that FEM creates much more realistic results, but this of course comes at the expense of computing power. Many small meshes can be easily simulated in real-time and this may be more than is needed for most situations, however, with bigger meshes comes better results but by the time an acceptable result is reached the cost may have become prohibitively high.

As for their current use in real-time applications, most video game developers shy away from implementing too many deformable objects because of their high cost. Deformable objects are mostly used when they play a central role in the mechanics of a game and it is worth the developer getting them right. One dimensional mass-spring systems have seen a lot of use in real-time cloth simulation. The relative simplicity of cloth compare to objects with more dimensions means that models have been created that are convergent and create very realistic looking and behaving cloth [1]. Finite element methods have been used to simulate stresses and small deformations on rigid objects just before they break. This method means that because the objects usually break very quickly, the results do not have to be incredibly convincing and they do not mean a sustained load on computation time. Using FEM in this way also means that the shapes never have to return to their initial rest shape so this does not have to be accounted for in the model [6].

Implementing both of these methods into a rigid-body simulator requires the implementation of a way of representing objects separate to the graphical representation of the objects themselves. For FEM this would be the placing of nodes and the creation of the grid from them or placing the network of masses-and springs. The placing of nodes and masses should stick to the network of vertices that already make up the representation of the shape, the connections between these points could then be described in ways suitable for the object which is being modelled. For FEM these connections should be contained to the surface of the object, however for mass-spring networks, springs could go through an object to create a more rigid shape. Once these networks are set up, it must be possible to have forces act on separate parts of it and allow the mathematics to handle the deformation of the shape. Once the points are moving the vertices of the shape beneath them must then be moved with them to give the deformation of the shape.

References:

[1]Nealen, A., Müller, M., Keiser, R., Boxerman, E. & Carlson, M. (2005) ‘Physically Based Deformable Models in Computer Graphics’ .CiteSeerX: 10.1.1.124.4664.

[2] Muller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. (2002) ‘Stable real-time deformations’. *In SCA02: Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation*, ACM, NewYork, NY, USA, 49–54.

[3] Liu, T., Bargteil, A., O’Brien, J., Kavan, L. (2013) ‘Fast Simulation of Mass-Spring Systems.’ *ACMTrans. Graph.* 3(6), 7 pages.

[4] Widas, P (1997) *Introduction to Finite Element Analysis *Available at: http://www.sv.vt.edu/classes/MSE2094_NoteBook/97ClassProj/num/widas/history.html (Accessed: 19 May 2014)

[5] Widas, P. (1997) *Theory of Finite Element Analysis *Available at: http://www.sv.vt.edu/classes/MSE2094_NoteBook/97ClassProj/num/widas/history.html (Accessed: 19 May 2014)

[6] Baudet, V., Beuve, M., Jaillet, F., Shariat, B. and Zara, F. (2007) ‘Integrating Tensile Parameters in 3D Mass-Spring System’ *LIRIS *

In this paper we seek to investigate the effects of different breeding strategies on the performance of an evolutionary algorithm. The strategies we explore can be split into two different categories, those that effect when an agent reproduces and those that decide which two agents are selected to reproduce. The different strategies that define when an agent reproduces are well explored and defined in evolutionary biology whereas the strategies we use for partner selection are less based on natural systems. This means that our areas of investigation will be see what partner selection strategy is most beneficial for each “when” strategy. To measure the performance of the system, each agent has a “fitness” which increases whenever they collect a piece of food, of which a fixed number are placed in the environment. We define the performance of a system as the average fitness of all agents in

the world.

Read the whole report here: Third Report