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.