How does Kangaroo solver work?

What algorithm does kangaroo use to within its solver to create the converged shapes?

Is there a manual with the workings and proof behind the script?

Only Daniel can answer that … but K is a particle physics engine meaning that you can Google and enjoy.

Kangaroo works by minimising total energy.

The various Goals define different energies which are zero under certain geometric conditions.

The Kangaroo solver iteratively moves the points so that the sum of the energies acting on all the points in the system is as low as possible.

For example, the Length goal acts as a spring, following Hooke’s law, so the energy is zero when it is at its rest length, but increases if it is stretched or compressed (in fact the energy increases as the square of the distance by which it is deformed).
The other goals define energies based on the geometric relations between the set of points they act on. Some of them (such as Length, Angle, Pressure) are based on physical elastic behaviour in a way that their strength can be related precisely to standard material properties and units.
Other goals are purely geometric in nature - they become zero when some condition such as circle tangency or quad planarity is satisfied, and can be used for finding geometry which satisfies some fabrication constraints.
Other goals are physically based, but not yet in a calibrated way, such as the Hinge goal for shell bending, so they can model physical behaviour qualitatively, but not in a way where numerical material properties can be so directly applied (though hopefully in a future version this will change).

When the goals do not conflict (for example starting from an arbitrary quadrilateral and making the angles all 90° and the lengths equal), this can work as a geometric constraint solver by making all the energies zero.
However, for something like finding the deflection of a hanging cable, the length and load goals will not all be satisfied - since one resists the other, so here the solver finds the configuration with the least total potential energy, and if the strengths are set correctly this can be a numerically accurate model of elastic deformation.
Sometimes you might not even want to reach a single energy minimum, but to make something dynamic like a flag flapping in the wind.

Typically these have been seen as separate things (constraint solving, modelling structural deformation, dynamic animation), needing their own specific approaches, but in Kangaroo they are all tackled with one energy minimisation approach.
Hence why I called them ‘goals’ as a more general term encompassing constraints, applied loads and elastic resistance.

The actual algorithm the Kangaroo solver uses to perform this minimisation can be seen as a form of dynamic relaxation (DR). This is a name coined by the engineer Alistair Day, to describe a technique where equilibrium is found by combining all the forces acting on each point, and repeatedly moving all the points by small steps until the forces balance and the movement stops. This happens in a dynamic fashion, using momentum, so the movement will oscillate about the equilibrium, and damping is used to remove energy and ensure convergence.
The writings of the late Mike Barnes are a good place to read more about DR, as he was a pioneer in developing its applications to form-finding, particularly for tensile structures.

In the typical engineering applications of dynamic relaxation, the desired output is just the static equilibrium configuration, so the damping and mass values are chosen just for stability and convergence rather than based on real physical values (note that this does not affect the accuracy of the equilibrium solution, only the route and number of steps taken to get there). Hence it is sometimes referred to as pseudo-dynamics.
However, (and this is sometimes a cause of confusion), the typical form of DR is essentially identical to a common approach to time integration used in physics engines for games and animation (a popular reference for which is the set of Siggraph course notes from Baraff and Witkin). If you adjust the mode and values for damping and mass appropriately, the same solver can be used for both DR form-finding, and animations of dynamics.

Since version 2, Kangaroo doesn’t actually use the classical form of DR, but a new form where instead of summing accelerations, it combines projections onto the zero energy state of each goal. This draws on conversations I had with the LGG group at EPFL, during the development of their ‘Projective Dynamics’ paper (though the method used in Kangaroo is not exactly the same as the one described in that paper, and incorporates a different approach to the damping to accelerate convergence). I later also learned that this method of combining projections actually dates back much further than the LGG work, and can be seen as a form of the alternating direction method of multipliers (ADMM).

I’ve had a mostly written paper on the solver method developed for Kangaroo sitting on my desktop for years, one day I’ll actually finish and publish it.

I hope the above helps clarify things a little more in the meantime.

52 Likes

Hi Daniel,

Thanks for the clarification. I’ll have a look into Mark Barnes to read up on Dynamic Relaxation.

Best of luck with the paper, I look forward to reading it.

Kind regards,
Will

Michael Barnes.
This one might be a good place to start:
https://researchportal.bath.ac.uk/en/publications/form-finding-and-analysis-of-tension-structures-by-dynamic-relaxa
edit- realised that link isn’t an open access one. Here’s an alternative:
http://openaccess.city.ac.uk/id/eprint/11887/

3 Likes

Hi,

Recently I had the same question. Therefore I implemented Dynamic-Relaxation in Python. It only contains a small subset of the Kangaroo goals (only springs and anchors) but it helps to understand the principles of DR. Other goals can be implemented straightforward. The results are perfectly matching with Kangaroo.

Check the comments within kangaroo.py for the mechanical background.

Best
Thomas

4 Likes

Thats nive but usually the problem with kangaroo is that there is no easy way to debug custom kangaroo goals visually to tack whats happening.

Do you have any ideas how that can be implemented?

Hi @ankere

Have you tried with this? (to do individual steps with custom goals and see the contributions for each point)



@ankere For step-by-step debugging in VS: maybe create a small plugin containing the solver which includes the KangarooSolver.dll.

@DanielPiker Very cool! I am playing around with custom goals. The force is computed by the derivative of energy functionals. The lumped mass is also straightforward. Is there a recommended way to convert them to Move + Weighting?

Another helpful thing for developing goals can be to make a little script to directly output the Move vectors per point, without even making a simulation and stepping it. I’ll try and post an example of this.

@oberbichler Thanks for the Python DR example - nice work!
As for converting things written in the classic force-based or energy-gradient approach to goals with Move & Weighting -
In general, Move should be the vectors which take the set of particles to their closest zero energy state, and when the Move multiplied by the Weighting per particle gives the same vector as the force used in the classic acceleration based DR form, it should converge to the same thing.

In the force-based approach, high stiffness means increasing the length of the acceleration vectors, and if the timestep isn’t scaled down accordingly things can get unstable because these can overshoot, as would happen in Kangaroo1, particularly when mixing elements of very different stiffness. You can always overcome this if you make the timestep small enough, but sometimes this means making it so tiny things slow to a crawl.

The big advantage of splitting it into a vector Move and a scalar Weighting is that instead of a single vector with importance controlled just by its length, it separates where the point wants to go from how much it wants to go there. So even as the weighting of one goal goes towards infinity, it doesn’t make the system unstable, it just means that goal will completely override any competing ones.

1 Like

Thanks! And thanks for the additional explanation!

Move should be the vectors which take the set of particles to their closest zero energy state, and when the Move multiplied by the Weighting per particle gives the same vector as the force

I usually implement the energy functional and compute the gradient which corresponds to the residual force. The direction of the negative gradient points to the closest energy state.

If force = move * weight then I assume that move = force / weight. I am just not sure why I divide the force by the weight when it is multiplied by the weight afterwards(?)

it separates where the point wants to go from *how much it wants to go there

Usually, I use a Newton algorithm for the solution which requires the second derivative (= stiffness) to determine a step-size (btw: there is a nice paper about the relation Newton/DR). As far as I understand the weights have a similar role with the difference that there is only one value per node and therefore no matrices are required(?)

I am still not sure how to compute a reliable weight without modifying the mechanical behavior of the system. When I find some time, I will post an example.