Contents  Case study  Hyperion SDK  Optimizations  Printable version  Discuss this article  in the forums The Series  Part 1  Part 2  Part 3 (coming soon)

Optimizations of the method

The study of solid deformations mixes several engineering fields, each offering efficient optimizations. In this part, we will explore different ways to improve the Hyperion method.

Related to the CPU

Frequencies do not uniquely define performance of the CPU. For the past few years, new processor instructions have been implemented. Their names are SSE or 3DNow!. One of the goals of these extended instructions is to speed up matrix computations. Hyperion method uses matrix computation intensively and sometimes handles big matrices. That is why using these special instructions could decreases computation time especially during multiplications between force vectors and the matrix K'-1r.

Related to the GPU

In the previous examples, a lot of triangular sides have been created decreasing general performance. For instance, after loading a cube which is pre-computed to be deformed, more than 6 sides (depending on the density of elements) will be displayed even if the cube is not deformed. Furthermore if the solid is locally deformed, that is, if a few sides are displaced, a big number of sides will not be moved. Reducing dynamically the number of sides is one of the possible optimizations.

On the other hand, when too few sides have been defined, quality of the result is reduced. The solution is to add new sides with the help of interpolation functions such as splines. As an aside, interpolation functions are deeply connected to the FEM. For instance, the finite element "cube" is related to one-degree interpolation functions. Whereas interpolation positions are computed regarding position of local nodes of the element, computation of interpolated nodes could be carried out with nodes related to several elements. Moreover, it turns out that finding the position of interpolated nodes is faster than finding FEM nodes.

Of course, this method has to be used with carefulness because interpolation nodes could smooth local deformations.

Related to the memory

During loading of the level, a matrix for each deformable element is fetched into the RAM. A large amount of memory will be consumed very quickly if there are n matrices for n deformable objects. However some objects have almost the same topology.

In the previous figure, two identical objects have the same topology, the same sort and the same density of finite elements, but have different proportions. For example, these two objects could be walls, items often used to build video games levels. Using homothety coefficients allows reducing the footprint of the application.

It is also worth saying that compressing files related to the definition of matrices is very efficient. Data related to the Hyperion files have been compiled in the following table.

Related to the algorithm

Great improvements can be done if algorithms which handle matrix operations are modified, such as:

• checking to know whether global matrices are invertible or not;
• matrix storage;
• dynamic simplification when forces are applied. This simplification might be very close from the render mask simplification presented in the previous part.

What next?

In the two articles, we have studied an adaptation of the Finite Element Method. This adaptation brings about more interactivity in video games. However, you have perhaps guessed that this method is trickier than springs systems usually used.

If you are interested in the FEM and its possible uses in real-time solutions, this article and the Hyperion project are good starting points. However, they do not provide any mathematical formulation because I wanted to focus on the adaptation of the FEM and not on the FEM itself. This method is a broad subject offering a lot of optimizations. Consequently, learning theory is the compulsory step to master the method.

In the third and last article, I am going to summarize drawbacks and advantages of this method and also to present how is it possible to implement the method at (relatively) low cost.

Don't hesitate to give me some feedback about this article by email at pierre_rebours@yahoo.com.