Unite 2010GDC ChinaAsia Game Show 2010GDC 2011
|
Where we have been, where we are goingIn the last article "Real-time deformation of solids", a solution to deform solids in real-time was set out. Deforming solids is based on a method christened the "Finite Element Method" (FEM). In order to get real-time results, the FEM has been slightly adapted to obtain the "Hyperion method". To summarize, the first step of the method, which is carried out during the construction of video game levels, consists of finding the linear relation between the stress applied on the solid and the displacements of nodes. This linear relation is represented by a matrix, which is saved in a file. During the loading of the level, the application parses the file to extract the matrix. During the execution of the level, collisions occurring, for example, when a rocket bursts near a wall, are translated in a force vector. Multiplying this force vector by the loaded matrix allows the application to find the deformation of the related solid with a high degree of accuracy. Please refer to the last article to learn more about the FEM and computation of deformations.
Whereas we have been focused on general statements so far, we are now going to have a deeper look at technical issues and possible optimizations. Case studyBecause a simple example is better than a long detailed piece of literature, we are going to study a complete case. In order to simplify our case, the shape studied in this part will be a cube. However, it is important to remember that the method can be applied on various shapes even complicated. Actually, the principle of the FEM is to divide such complicated solids into simple elements which are easily handled by software applications. Hypotheses related to the problemIt is worth saying that the most important step is the definition of hypotheses related to the problem, such as properties of material/s, geometric shape of the solid or boundary conditions. In our case, the material of the cube is steel. The following table describes steel properties necessary to solve the problem. Some other materials have been added as references.
The elastic modulus is defined as the force you need to provide to elongate your material. Poisson's ratio is the lateral contraction per unit breadth divided by the longitudinal extension per unit length.
Cubes are not special items in video games. For instance, cubes could represent boxes scattered in the level and containing medipacks or ammunition. They can also represent walls if one dimension is smaller than the two others.
To simplify the problem, the cube studied here is compact, that is, has no cavity. Moreover its dimensions, in meters, are 2 by 2 by 2. As an aside, all units in this article follow the international system. The cube is also soldered on the floor. Consequently its base is not able to move or to rotate in any direction. MeshingMeshing is a process consisting of dividing the body into finite elements. In theory, we can mix several sorts of elements (beams, plates and so on) but in practice and when it is possible, we prefer to use one sort of element in order to simplify computation. In our case, the meshing is also straightforward. It consists of dividing the big cube into several small cubes made up of eight nodes with three degrees of freedom (DOF) by nodes. Again, a node having three degrees of liberty means that it can move along the x, y and z axes.
We will also choose the handiest solution, that is, dividing the cube into elements of same size. You are perhaps wondering how dividing the big cube in a non-homogeneous way can be beneficial. Actually this is an example of optimizations which are possible with the FEM.
In this first picture, big deformations are supposed likely to occur on the top of the cube. On the other hand, probability to have deformations on one of its faces is very high in the second picture. The higher the density is, the more accurate the results are. Imagine a car simulation for example. Along the track, crash barriers have been set up for obvious security reasons. Collisions between cars and crash barriers occur several times during a game, but car crashes on the bottom of the barriers are unlikely. So there is no point in having a high density of elements on the top of the barriers. In our case, we consider that all faces of the cube may be deformed with the same probability. Moreover, in order to simplify the problem, the cube is only divided into eight elements. So we obtain the following configuration.
We can figure out the dimension of the problem. The cube has 27 nodes connecting eight cubic elements. According to the description of the elements used, each node has three degrees of freedom, one along the x-axis, one along the y-axis and the last one along the z-axis. Consequently, the unknown related to the problem is a vector of dimension 81 (27 x 3). The following relation formulates our problem:
u1, which is the first component of the vector U, corresponds to the displacement of node 1 along the x-axis. u2 corresponds to the displacement of node 1 along the y-axis. u81 corresponds to the displacement of node 9 along the z-axis. The vector F represents the forces applied on the nodes of the cube. Because F follows the same notation as U, f1 correspond to the force applied on node 1 along the x-axis. Here is an example of this matrix notation.
The matrix K related to our cube is called "matrix of rigidity" or "global matrix". Again, check out both the previous article and the links located in the appendix to have more information. Computation of the matrix relationsTypically, the level designer only provides hypotheses. The steps described in this section are computed without human decision. Firstly, the matrix of rigidity of each finite element is found [step 1]. According to our example, eight matrices, which have 24 rows and 24 columns, are consequently assembled to obtain the global matrix K [step 2]. The next step [step 3] consists of simplifying the global matrix. According to the hypotheses described above, the cube is fixed at its base. In other words, whatever the forces applied on the cube, its base will never move. This sentence could be translated in mathematical terms: the 27 matrix components which represent the nine nodes on the base of the cube could be set to zero. After simplification, we obtain a new matrix K' called "boundary matrix" which has 57 rows and 57 columns. Unknowns of the problem are represented by the vector U' having a dimension equal to 57. It is time to carry out the longest step of the method, that is, the inversion of the matrix K' [step 4]. How to inverse the matrix and obtain an accurate solution is beyond the scope of the article. It turns out that exploiting specificities related to video games brings about great improvements in the computation method. In our example, node 10, which is in the middle of the cube, will never be seen by players. So knowing its displacement after deformation is useless. This simplification step has been christened "render mask simplification" [step 5]. In fact, another matrix called RM, which has the same dimension as the unknown matrix U', is computed. The value of each matrix component is either zero or one. Zero means that some geometric sides hide the node related to the component. On the other hand, the value "one" means that the node is visible.
We finally obtain the matrix K'-1r which has 51 rows and 54 columns. As an aside, index r means reduce. Notice that the new matrix is not square. Even if we remove the central node from the unknowns, we can still find the displacements when stress is applied in the middle of the cube.
The last step is to save the matrix K'-1r in a file in order to load it before the starting of the level. Finding the displacementsFinding the displacements is really straightforward. When a player fires a rocket into a piece of furniture or when her/his car crashes into a wall, the application translates this information into a force vector F. This vector is multiplied by the matrix K'-1r previously loaded in the memory to obtain the vector U'r. To find the final position of all the nodes, the vector U'r must be added to the previous position vector X. Let us imagine a game where it is possible to put an elephant on the top of our cube. By the way, it will be an interesting example because it explains how to handle pressure forces. The weight of an adult elephant is around six tons. We consider that its weight is applied uniformly on the top of the cube. So 9x3 force components must be found to represent the weight of that elephant.
It is easily to understand that forces on each node are opposed to the z-axis. Consequently, all the components of the vector F along the x and y axes are set to zero. However, finding the values of these 9 force components is trickier than it appears. The first though might be "Divide the weight of the elephant by nine, the result will correspond to the value of all the z-components". It is wrong. Imagine that the cube is made up by a frame of springs [figure below]. Nodes are connected to each other by springs which have the same properties. The more springs are linked to the node, the more rigid the node comes. Consequently, if all the z-components are equal, deformation will be bigger for a node linked by two springs than by a node linked by three springs.
Nodes on the top of the cube could be divided in three categories:
a, b and c are the value of the z-component applied on nodes from the first, second and third category respectively. A system is obtained below:
After resolving the system, we find
So the vector F is found:
Until now, we have been talking about theories and painting the big picture of the different computation steps related to the method. In the next part, we are going to learn how to use the Hyperion SDK, which implements the method. To have a general view of the architecture of the project, please read the first article. |
in the forums
or KU=F
