OPTIMIZATION - Eliminating SQRTs

I have recently been through the code looking at where it can be optimized. The first thing i looked for was square roots in the code.

Square roots are required to find the length of a vector, and crop up a number of times in my code:-

• one per spring, per frame (to calculate spring forces)
  
• one per spring, per constraint pass, per frame (in order to constrain spring)
  
• one per particle, per sphere on screen, per frame (to check if the particle collides with a sphere)

I successfully managed to eliminate all these square roots and work with squared lengths instead of actual lengths. I believe the methods i have used are approximations (i use a ratio of the squared_length to the "supposed" length squared). As of yet these methods appear stable and do not seem to have changed the behaviour of the cloth noticably, which is great.

I only have only square root left in the program, which is a D3DX Normalise call on each of the triangle normals, which is actually just used for the lighting in rendering the cloth.

So what's the benefit?

I was quite limited in cloth resolution before - beyond 40 x 40 was enough to bring the best of machines to a crawl.

I am still limited of course, but i can manage approaximatley 3 times the resolution with a similar frame-rate now.

I did a test running a simulation of cloth with resolution 85 x 100, with no collision handling, with my new optimized code and the old un-optimized code. The non-optimized version ran at an average of about 4.8 FPS. The new optimized version ran at about 14.2 FPS. Again thats an increase factor of about 3!

From a realism standpoint, higher FPS means smoother animation and higher resolution allows for smaller wrinkles and folds to occur. Additionally, the optimized version allows more constrain passes to be ran each frame, which gives rise to stiffer cloth - and generally the stiffer the better when it comes to cloth realism.

So by optimizing i potentially have more realistic and better looking cloth.

Adding Verlet Integration & Tuning Deformation Constraints

Adding Verlet Integration

Using the Verlet Integration scheme, the cloth appears alot bouncier for some reason. If i increase the global damping constant i can achieve more realistic results. This means having a damping factor for Euler and damping factor for Verlet, which is not ideal.

I spotted a mistake in the constraint code. I was actually over-shooting the displacement of the spring-ends. It was this that was causing the instability. Now euler actually works ok with constraints.

However, the best looking results i am getting with Verlet.

The act of constraining appears to dampen the system. meaning damping factors have to be lowered if constraining is on. This makes sense since we are basically taking energy out of the springs when we stop them deforming too much.


Tuning Deformation Constraints

While constraining is now fixed and more stable, it causes the cloth to wibble when the constraints are fully satisfied. Constraints are continually being invalidated by other constraints. It will not sit still! At 10% satisfaction the wibbling is hardly there but the cloth is still too rubbery and bouncey.

So the more realistic i make the cloth (i.e the more i up the stiffness), the more it wibbles!

After further inspection, it seems i can increase the stiffness by increasing the number of constrain passes, only satisfying by 10% per pass, WITHOUT increasing the wibbling. However, the simulation becomes pretty slow in debug with 3 or more passes. Release will do around 20 passes without looking too slow, and the cloth looks very nice and stiff.

Increasing the Stiffness

I have added spring length constraints to get less rubbery, elastic properties and more stiff, cloth-like properties.

I implemented X.Provot's constraint method of picking up particles and moving them to a place where the springs they are attached to are of satisfactory length. (basically, stop the cloth stretching or shearing too much). The idea is that bend springs are not constrained since cloth is quite forgiving of bending motion but not of stretching or shearing motion.

----------------- RESULTS -----------------

• Can get it running "stabily" using Euler and one constraint iteration.
• Cloth does definitley behave more "stiffly"!
• Constraints must be constrianed very "loosely" or it blows up. Thus there is a low limit to how stiff i can make the cloth.
• As said above, Cloth becomes unstable and blows up if you move the ends of a spring too much in satisfying a constraint. Because of this the constraints are not solved fully.
• You CAN counter this instability by reducing the time-step of the simulation down to a crawl.
  This way i was able to almost fully satisfy the constraints and observe stiffer, potentially more realistic (although it was hard to tell because it moved so slowly) cloth.

As showed by the results, the process of instanteously picking up and moving particles raises some issues.

One is stability. Simple Euler integration, which i am currently using, is not well equipped to handle the instaneous movement of particles. If the particles are moved too much in a single frame, the cloth begins to shudder as springs fight each other to stay constrained and eventually, the cloth blows up.

A solution might be to implement the more robust verlet integration scheme that defines it's velocity implicitly from the change in position. (Thus supporting instantaneous movment much more stabily).


Another issue is that moving a particle can validate one spring but also can quite possibly invalidate other associated springs.

Iteratation of the whole constraint procedure can be used to converge to a result where most springs are constrained.

I have not as yet observed any difference in constraining multiple times though.

Another relevant factor mentioned in the literature i have read is the order in which you constrain the springs. Currently my implementation just iterates through the springs in the order they were added to the particle system.

1. Horizontal Structural Springs (from left to right).
   Verticle Structural Springs (from bottom to top).
2. Shear Springs (2 for each cell in ROW MAJOR ORDER.)
3. Bend Springs (2 for each cell in ROW MAJOR ORDER).

Experimentation with this order could provide a better, more accurate way of constraining all springs - thus obtaining stiffer and more stable cloth.

Implementation : Next Steps

With the first basic implementation completed i'm now thinking of what directions to take to improve the simulation. My thoughts are as follows:

1. Add a user-controlled wind force that allows interactivity and better demonstrates the cloths behaviour.
2. Add in collisions with spheres and cubes.
3. Add Deformation contraints. Reduce the rubbery and bounceyness of the cloth.
4. Improve stability. Allow for higher resolution cloth.
5. Get the cloth behaving more realistically by experimenting with the spring and damping coefficients of the stretch, shear and bend springs. Also tinker with the global damping constant.
   
6. Improve efficiency. Shoot for the highest frame rate you can get. Maybe profile code to find what parts are most expensive.

X.Provot - "Deformation Constraints in a Mass-spring Model to Describe Rigid Cloth Behaviour" (1995)

This paper looks at modelling cloth from a system of point masses connected by "springs".

The system is made of three types of springs:

• Structural
• Shear
• Flexion (bending)

The diagram above shows how these springs are arranged. Structural springs hold the cloth together, shear springs resist shearing deformations (movement in the plane of the cloth), and flexion (bend) springs resist bending (movement outside the plane of the cloth).

Each point-mass and its connected springs contribute to the overall behaviour but each point-mass and spring can be treated completely independently.

The movement of each point mass is determined through numerical integration of newtons second law (F=ma).

The force acting on each point-mass is broken down into internal and external forces. The internal force is evaluated as the sum of the tensions coming from each spring associated with the mass. External forces can be added to interact with the cloth, those noted are a gravitational force, a damping force (to simulate the natural loss of energy in the system) and a viscous interaction from a fluid (used to inflict wind).

With the force on each point-mass calculated, the acceleration is computed simply using a=F/m.

Then the simple Euler numerical integration scheme is noted as their method to solving velocity and position.

The original results showed a square sheet of cloth hanging from two corners, where the deformation of the springs close to the corners was very high and the deformation elsewhere was relatively low.

This behaviour is suited to a sheet of elastic but such local deformations would not occur in woven fabrics. According to the paper, cloth under high loads is inclined to rip before any large deformations occur.

Fabrics are far from ideally elastic materials. You would clearly notice the difference in behaviour between a sheet of fabric and a sheet of rubber -- rubber behaving predominantly elastically and the fabric behaving somewhat more stiffly, depending on the type of fabric. The differences between the behaviour of these two materials are most obvious in intense deformation. However, since many scenarios do not cause intense deformation (such as a table cloth), cloth is often modelled ellastically.

It is also noted that the initial results showed unrealistically high amplitude oscillation because of the elastic modelling. This was countered by a large damping force, but lead to other shortcomings where the cloth looked like it was immersed in thick fluid.

The obvious way to increase the stiffness and reduce the elasticity of the model is increase the stiffness of the springs. This can be done but reducing the time-step is required to ensure the simulation remains stable. Decreasing the time-step means more computation, resulting in a more costly algorithm.

To avoid this loss in inefficiency, Provot increases the stiffness of the cloth by constraining the amount cloth can deform. He limits the amount each spring can stretch from it's rest length. The
stretch of each spring is compared with a threshold value; if it is larger, the ends of the spring are brought closer together so that the threshold is met. This gave more realistic cloth deformations, where it would propagate through the structure as the constraints were enforced -- as apposed to staying in a concentrated area. This gave much more realistic and less elastic looking cloth, whilst maintaining the efficiency of the algorithm. However there is the overhead of constraining. Provot estimates it to be 15% greater computation than the classic elastic model.

Note that the deformation constraints could be applied to the different types of springs. Provot constrained the structural and shear springs because this is where cloth resists deformation most. He did not constrain the flexion (bend) springs, because cloth is generally accepting of bending motion. It was found in the results that cloth would bend to find it's "rest state" as apposed to stretch or sheer -- this is what real cloth will do.

Provot also notices taking a two-pass approach, where each spring is constrained twice, yields even better results -- as if the procedure is converging to a more accurate result. So the algorithm could be adaptive in terms of accuracy and efficiency, where multiple passes give accurate results and less passes give fast efficient results.


The results Provot showed were a hanging sheet of cloth, a flag blowing in a strong wind,and boat sail with wind blowing through it. Simulation times are said to be in the order of minutes.

First Implementation

Features for first implementation:-

• Particle-System based
• Mass-Spring model (X.Provot style)
• Euler Integrator
• Basic Gravity Force
• Fixable Points

Essentially this boils down to being the most simple cloth simulation you can build.

I am already somewhat familiar with particle systems from second year so thats why i chose this approach. To me, they are easier to understand than some of the more complex models out there.

Additionally the mass-spring model is well documented. I have found articles regarding the model on the internet in addition to X.Provot's paper, which describes it in-depth.

The Euler integration is the easiest to implement and the easiest to understand. This will be abstracted from the particle system so that other more advanced integration methods can be plugged in later.

The gravity force and fixable points are there to give a good indication of whether the cloth is behaving as it "should" be. They will alow me to see the "draping" behaviour.

------------ RESULTS --------------

• Experiencing the issue described in Provot's paper, refered to as "Super-elasticity".
  As a result cloth looks rubbery and is "bouncey".
  Could apply Provot's spring deformation constraints in to improve.
  

• Higher resolution appears to decrease stability -- more springs, thus more energy in the cloth , thus a more stiff system and more prone to "blowing up".

• Decreasing the time-step improves stability.

• Played around with the spring coefficients a bit, unsure of which springs should be strongest and which should be weakest (bend stretch or shear?).

A comman interface for all types of force is proving difficult to create.

• Spring forces depend on two particle positions.
• Gravity force is constant and acts on every particle.
• Damping force is applicable to all particles but depends on the particle it is being applied to(inversely proportional to velocity).

Currently Particle system contains a number of spring forces and gravity and drag forces are hardcoded in.

D.Breen - "A Particle-Based Model for Simulating the Draping Behaviour of Woven Cloth" (1993)

This paper set out to produce simulations of the various "draping" behaviours in a range of woven fabric types.

This paper very much acknowledges the underlying structure of what we refer to when we talk about cloth - we are refering to a complex woven material that contains thousands of fibres of "warp" and "weft" threads.

It poses questions such as "what would this shirt look like if made from polyester instead of cotton?"

This paper claims it is the first of its kind to attempt to simulate a specific type of fabric.

-------------------------

The model is based on interacting particles.

Emperical data from the well-known Kawabata fabric analysis system is used to tweak the model to exhibit realistic draping bahviour of particular fabrics.

It is noted that different fabric behaviours depend on lots of factors including the type of fibre (silk, cotton, polyester ect), the weight of the yarn and the tighness of the weave.

The approach taken attempts to model the low-level microscopic interactions of the fabric in belief that the correct macroscopic higher-level features will manifest themselves.

As mentioned earlier the complex composition of fabric and how this effects its "draping behaviour" is considered in this model, meaning cloth is not simply considered a continuous sheet.

However, it says that to completely model all the interactions of thousands of fibres is simply too computationally expensive and thus an undesirable approach.
So a happy medium is obtained where complexity is aknowledged such that the most important interactions of cloth can be modelled.

Energy of the cloth is modelled and broken down into repulsion energy, stretch energy, bend energy, trellising energy and gravitational energy. The methods by which these are evaluated are discussed in the paper.

It reports that the "bend" and "trellising" energies are the most significant contributors to the draping behaviour of the cloth and that using their inital configuration, they were not able to convincingly simulate different types of cloth.

So thats why Breen moved to the Kawabata system to "tweak" his model from empirical data.

Simulation times are reported as being on the scale of days! One particular simulation is quoted as having taken 1 CPU-week on an IBM RS/6000 workstation!

While this hardware is nothing compared with what we have available to us now, the method clearly has efficiency issues (which are acknowleged in the paper), especially when considering simulating cloth for real-time applications at 30 frames-per-second.