# Arbitrary Accuracy Scalable Rope Simulation

I am trying to simulate a rope object. The formulation I understand is an array of particles, connected by springs. These springs have very large k-values, so that the line deforms, but stretches very little. I have concluded that solving this as a function of time is not possible in closed-form because a rope is a generalization of a pendulum (which is not closed-form).

Settling for approximate solutions, then. I need an algorithm that scales well. Examples I have seen use either explicit or implicit Eulerian integration to move the particles. This does not scale.

To see this, consider a rope with n nodes. Apply a large force to one end. Because the rope should not stretch very much, the acceleration at the other end must be immediate.

However, with Eulerian integration, to get any force to the other end requires n steps. I notice an exponential falloff: if the first node accelerates a certain amount, then the adjacent nodes accelerate less (if they accelerate at the same rate, then the algorithm is not stable). Consequently, the nodes adjacent to that node accelerate even slower!

So, for n nodes away, the acceleration is almost negligible. This leads to rope that stretches significantly. If you want to only double the simulation's resolution, you suddenly need to take time steps that are tens or hundreds of times smaller to get similar behavior.

I am looking for a simple method that solves this problem--i.e., higher resolution simulations converge to the solution with only polynomial time extra computation. A full library of matrix and linear algebra techniques is available. My knowledge of classical mechanics is very good, and I know some numerical analysis.

• It seems that RK-like sub-stepping algorithms will speed up the communications (measured in nodes/step) by a factor roughly equal to the number of sub-steps, but that may not be much of a win in terms to actual computational time. To be really general, you probably need to compute how far you expect the effect to propagate in a timestep (i.e. $v_s \mathrm{d}t$), and start from a heuristic application of the strain over that length then relax. – dmckee --- ex-moderator kitten Oct 24 '12 at 19:27
• @dmckee, yes, please do! In answer to your second comment, ideally the force ought to propagate effectively infinitely far in any timestep. – imallett Oct 25 '12 at 3:02
• Well, the speed of sound is probably pretty high...but if your time steps are less than 10 ms, that propagation length is still only a few meters. – dmckee --- ex-moderator kitten Oct 25 '12 at 3:42
• I am curious to know if the suggestions you've received here have been helpful. I'm assuming that the lack of acceptance means either that you are still following up or that none of the answers are exactly what you had hoped for, but have they shown you a way forward? – dmckee --- ex-moderator kitten Oct 27 '12 at 17:12
• They have been helpful, but a lot of things just came up simultaneously. I have clarified my intentions on some answers, and when I get a breather I'll be able to follow-up on them. Thanks, – imallett Oct 28 '12 at 3:15

First of all, as Jed Brown has mentioned, you should use an implicit time-stepping scheme as your problem seems quite stiff, or at least a more stable, yet equally simple scheme such as Leapfrog integration or Verlet integration.

As for the physical problem, how interested are you in the stretching? Instead of connecting the particles with stiff springs, you could use holonomic constraints, e.g. ensure that the distance between pairs of particles remains constant. The constraints need to be solved for at each time step, and there exist efficient algorithms for exactly your setup, i.e. a long linked chain of constraints. See, for instance, this paper.

Just out of curiosity, are you also using angular potentials along the length of the rope to model its flexibility?

• Even using implicit time stepping (which does help), stretching occurs. In fact, I'm interested in stretching only insofar as I'm trying to get rid of it. The math in the paper is basically over my head, but I'm studying the fortran code. Not using angular constraints of any kind yet. – imallett Oct 28 '12 at 3:09
• @IanMallett: Ok, then constraints are the way to go, i.e. there is no stretching at all with constraints. – Pedro Oct 29 '12 at 9:13

You have a stiff system with the current formulation. The dynamic stretching and vibration in the string are (presumably) uninteresting, but they control the explicit time step. This indicates using an implicit time integration method. You can use damping to prevent the oscillations which will tend to mess up adaptive error control for the implicit method.

If the fine-scale oscillations are important to model despite wanting to step over them (e.g., for fatigue modeling), then you may want to check out new multiscale methods such as the Heterogeneous Multiscale Method (Engquist, Tsai, etc) or semi-spectral in time methods. Use of such methods is a research-level topic and you have to understand your problem and the capabilities of the method well to decide whether it may be appropriate. If you want to conserve energy, for example that certain vibrational modes should not dissipate, then you should look at symplectic integrators such as Verlet.

You can also solve the zero-stretch limit if you like. With inertial terms, the model can be reformulated in terms of angles, leading to a non-stiff ODE system. As faleichik pointed out, this is the ROPE test problem considered in Hairer, Nørsett, and Wanner's book. If you discard inertia of the rope itself, but allow slack (light, low-stretch rope with discrete loading; not a common model), the problem becomes a differential variational inequality (DVI) and you cannot generally get better than first order accuracy in time.

• HMM is a projection-based model reduction method, in essence. I hesitate recommending such methods unless an application specifically demands them; one has to be willing to sacrifice accuracy for speed. Determining "good" choices of the compression and reconstruction operators (using the nomenclature of HMM) remains nontrivial for some applications (combustion is one such example). – Geoff Oxberry Oct 25 '12 at 5:42
• @GeoffOxberry Agreed, I added a warning. A classic problem is how mechanical vibrations in a clock cause drift. An example problem that I think would be appropriate is modeling creep/slip of a rope around a capstan accelerated by vibrational modes from the loaded side. Not everything is combustion. ;-) – Jed Brown Oct 25 '12 at 13:36
• The zero-stretch-limit is basically the only thing I'm really trying for at this point. Fine-scale oscillations would be nice, but an inelastic cloth that is too smooth is preferable right now. I have tried implicit time stepping (via OpenCloth's formulation), and unfortunately the problem still occurs. Can you elaborate/give links about how to execute your final paragraph? Thanks, – imallett Oct 28 '12 at 3:13

If you're interested in a fast, approximate solution, then the methods used in digital effects such as discrete differential geometry may be of interest to you. I'm aware of a quasistatic formulation in Discrete Elastic Rods, a 2008 paper from Grinspun's group at Columbia University, but there is probably more recent literature in this area.

The movement of hanging rope is a beloved test problem of Hairer and Wanner which appeared in the second (stiff) volume of "Solving Ordinary Differential Equations" and in the second edition of the first volume (1993). I recommend the last option, page 247. The equations are tricky to derive and the algorithm of numerical solution is not very straightforward. Though at the end conventional explicit time steppers like DOPRI, RK45 or ODEX are applied and behave pretty well, so the problem is not really stiff.

• The ROPE problem from the book models a rope that does not stretch, with dynamics dominated by inertial effects. The question seems to be asking about ropes that stretch. – Jed Brown Oct 25 '12 at 12:59