Talk:Verlet integration

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

Start Class

Mid Priority

Field: Applied mathematics

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
Close to B class, in terms of amount of information, but it needs vigorous editing, esp. the constraints and collisions section. Geared too much towards specific applications. Needs more analysis, especially on why it's stable (and when it isn't). Jitse Niesen (talk) 07:26, 10 May 2007 (UTC)

I suggest everything below and including "Constraints" should be deleted, or moved to its own article about the use of the Verlet algorithm in game programming. —Preceding unsigned comment added by 145.116.227.10 (talk) 22:20, 2 February 2008 (UTC)

Isn't this more physics than maths?

A little harsh, but I agree it needs to be expanded. Velocity-Verlet and leapfrog should be explored, or at least linked to. The derivation of verlet itself is easy enough to show (it comes from an algebraic manipulation of the third order taylor expansions, one forward and one backward in time). Also, some accuracy details would be nice (ie: 4th order accurate, 2nd order, etc.) --Numsgil 16:48, 12 February 2006 (UTC)

The section titled "the algorithm" starts on the wrong foot "At first it may seem simpler". This section IMHO should contain only a cold, clear, crisp statement of the Verlet formulas. No "may" "if" or "but". The comparison to the simpler Euler method is valuable but belongs later on in a derivation or discussion section. (As for the third order Taylor expansion derivation, it seems to me that the 14 year old has already provided it :-) ). We might also want to mention that Verlet is an example of "symplectic integration" methods that are designed to respect the properties of mechanical systems (such as conservation of energy and reversibility in time). Encyclops 17:32, 12 February 2006 (UTC)

1 Basic Verlet
2 Velocity error term
3 Velocity Verlet
4 Constraints
5 Inverting a Matrix
6 acceleration, another methods, constraints
7 There is an error in the formula
8 Is the "Constraints" section related to Verlet integration at all?
9 Estimating velocity using the mean value theorem

[edit] Basic Verlet

It might seem misleading when one uses t_0 for the current time. Normally one mentions t_0 as the initial time and uses t further on. Also all positions, velocities and accelerations should be in vector notation. It should be mentioned for the Basic Verlet algorithm that for the first time step one should use another formula, while x(t - \Delta t) is not known at t = 0.

[edit] Velocity error term

As far as I can tell from [1] the velocity error term is delta t^2. If I'm reading it wrong, feel free to correct me. --Numsgil 12:44, 15 February 2006 (UTC)

So what? This agrees with the article, which says

$v(t_0) = \frac{x(t_0 + \Delta t) - x(t_0 - \Delta t) + O(\Delta t^3)}{2\Delta t} = \frac{x(t_0 + \Delta t) - x(t_0 - \Delta t)}{2\Delta t} + O(\Delta t^2).$

Or do you mean something else? -- Jitse Niesen (talk) 13:16, 15 February 2006 (UTC)

oh, does the delta t at the bottom of the fraction cancel out an order of magnitude for the error function? That seems unclear to me, perhaps the second error form should be used instead of the first, to heighten clarity? --Numsgil 19:09, 15 February 2006 (UTC)

I agree the second form is clearer, so I used that one instead. Regarding the cancellation:

O (Δ t 3)

means roughly

C (Δ t) 3

for some constant C, and

$\frac{C(\Delta t)^3}{\Delta t} = C(\Delta t)^2.$

To my surprise, this is not mentioned on Big-O notation; perhaps it should be? -- Jitse Niesen (talk) 19:56, 15 February 2006 (UTC)

What's the problem with these error terms? It's clear that this is an expansion in \Delta t linear in \Delta t, which means O(\Delta t^2). If you like I'll give a proof for this, based on the Basic Verlet algorithm later this week. The whole discussion on this page about the error term is a bit knotty. -- anon

The problem that Numsgil was having is resolved, as far as I know.

You're right that the article is not very clear, and I would welcome any improvements. In particular, I feel that it should start by writing down the equation solved by the algorithm. What determines the acceleration and how is it computed? -- Jitse Niesen (talk) 14:38, 16 December 2007 (UTC)

[edit] Velocity Verlet

There should also be mentioned what the difficulty's are while using this algorithm, for example when simulating many body problems with long ineraction potentials, how to take \Delta t, conservation laws, ...

[edit] Constraints

This should be a slightly more efficient way of doing what is currently demonstrated in the Constraints section.

$\Delta x = x_1 - x_2\,$

$d=0.5\left(1.0 - \frac{r}{\sqrt{\Delta x^2}}\right)\,$

$x_1 = x_1 - \Delta x d\,$

$x_2 = x_2 + \Delta x d\,$

And some pseudo-code:

/* Pre-defined variables */
vector x1, x2  // Positions of the particles
double r       // The length at which the constraint is at rest

vector delta = x1 - x2
double d = 0.5 * (1.0 - r / sqrt(delta * delta))

x1 -= delta * d
x2 += delta * d

N.B. The described constraint method (e.g. Jacobsen's Verlet projection method, which it is popularly referred to in the game physics litterature) isn't faithful to the scientific literature. It would be more apropriate to describe the RATTLE and SHAKE methods, and show that in velocity form, with the right hand side terms neglected, we end up having a simple, but often broken (very heavily damped) method, which indeed is this projection method by Verlet integration that is described here. —Preceding unsigned comment added by 89.160.50.2 (talk) 18:51, 17 September 2007 (UTC)

sorry for nitpicking, isn't is cleaner with |x| rather than with sqrt(sqr(x)) ;)? --- ca1 147.229.179.174 (talk) 16:06, 7 April 2008 (UTC)

[edit] Inverting a Matrix

In regards to Arnero's edit, while my gut tells me that this is right, that satisfying constraints is similar to matrix inversion, I don't have the mathematical background to see it, let alone put it to practical use. I'm sure others are in the same boat.

I would appreciate a simple explanation of what the matrix would even be or look like (if you would construct such a matrix), where to start, how to compare my "home grown" constraint satisfier with gaussian elimination or other methods, etc.

The two primary concerns in a constraint satisfier in any real time application are the order of convergence (how many time steps it takes to reach an acceptable answer) and overall stability over time (more difficult to quantify). If techniques from linear algebra can provide better solutions, I'd personally like to explore them.

--Numsgil 23:13, 2 November 2006 (UTC)

I wanted to integrate wisdom from the open dynamics engine: The author says verlet is unstable. Personally i like kiss systems and I looked into simulation of maxwell equations and of fluid dynamics and there global algorithms are pure nonsense. But if mechanics is simlated in so large time steps, that sound waves cannot be simulated, I understand that constraints need to be simulated with abstract code (violating KISS). My theoretical mechanics professor liked to use lagrangian mechanics and solve the equations analytically. But I understand that this is only possible for the samll systems he researched (up to 10 joints). So for real world applications I would calculate the violation of constraints every frame. By approximating the constraints (containing cos, sqrt etc) by a linear equation around its current value it is possible to correct the deviations by linar algebra methods (matrix inversion) and to limit the movement to the tangent space. As we use small steps anyway the approximation is in harmony with the rest of the simulation. Because the matrix inversion connects every joint, the constraint are met better globally. Stiffness is avoided. Stiffness is very evil so we go large distance to avoid it.

But the open dynamics engine is moving away from precise matrix inversion. I glanced over conjugate gradient method, but I have the impression that they are not better than pure verlet integration, but only formulated in a way, which is above my comprehension.Arnero 14:34, 4 November 2006 (UTC)

The above comment, comparing CG with Verlet projection is pretty confused. Anderson's RATTLE method is the correct starting point, and this method can be solved either by direct methods, or by iterative methods such as a linear relaxation method e.g. Gauss-Seidel, Jacobi, or Krylov type of methods like Conjugate Gradient. The advantage of e.g. GS over CG is that it conserves momentum and energy locally and thus works well with damping, while CG can cause local jittery behaviour. On the other hand CG has much better convergence if you need to go to higher precision. —Preceding unsigned comment added by 89.160.50.2 (talk) 18:56, 17 September 2007 (UTC)

[edit] acceleration, another methods, constraints

[edit] acceleration

x (t 0 + Δ t) = 2 x (t 0) - x (t 0 - Δ t) + a Δ t 2

Is the acceleration a in time t0? So is it a(t0)? Or is it something different?

But what if in my problem the a(t) depends on v(t)? (For example air drag, where air drag force depends on the speed and the acceleration depend on this force.) It seems that I can't use this integration method for such problem. Or can anybody explain better the part of this article with the "very simple damping effect"?

\vec{a}(t + \Delta t) is calculated using values of \vec{x} and \vec{v} dependent on the potential of the interaction.

You can probably use the old v(t - dt). But the damping effect can be also implemented directly into the Verlet equations, as shown in the article. Note that it is better to scale the constant f with the current dt (i.e. use coefficients (2-f*dt) and (1-f*dt), where f is a constant, and 0 < f*dt < 1).

[edit] another methods

Could anybody please compare Verlet integration with another integration methods? (I don't call Euler integration a "method".)

Range-Kutta? Predictor-Corrector.

[edit] constraints

Could anybody please compare kind of solving constraints mentioned in this article with Lagrange multipliers?

--147.230.151.146 12:20, 30 November 2006 (UTC)

[edit] There is an error in the formula

The accelleration term is written as a(delta_t)^2.

It should have been a(t0)*delta_2^2. This is consistent with the derivation section where the correct value is shown.

Please read the comments I added in the beginning of this discussion under "Basic Verlet" about the t0.

—Preceding unsigned comment added by 85.82.232.123 (talk) 19:26, 10 December 2007 (UTC)

[edit] Is the "Constraints" section related to Verlet integration at all?

The formulas in the current Constraints sections does not use any information at all from the previous timestep, so how is it an application of Verlet integration? --Dolda2000 (talk) 02:42, 1 April 2008 (UTC)

They're both mentioned in the Jakobsen article mainly, which has a lot of notoriety amongst indie game programmers (maybe some professional ones too. Couldn't say.) You're right, it doesn't necessarily belong in this article. I'd vote to remove it. --Numsgil (talk) 07:30, 1 April 2008 (UTC)

Fixed the equations in that section -- the constraint resolution is time-dependent and only works in a Verlet-like scheme. The attached source code, however, is just wrong... Is this in the Jakobsen article? Why do we have code in a theoretical article anyway? Anyway, the main article on this subject is Constraint algorithm -- I will add a link at the top to that effect. Cheers, pedro gonnet - talk - 01.04.2008 07:39

[edit] Estimating velocity using the mean value theorem

The recommendation of this article is to take the position at time t + h and time t - h, and use the mean value theorem to approximate the slope (velocity). However, I've been doing some experimenting, and it seems to me that taking the position at time t and t + h gives a better approximation to the velocity. This makes intuitive sense, as well, since the velocity term will respond better to local changes in force. My test cases are all damped spring equations where the force (acceleration) is related to position and velocity. So, I guess my point is that either I'm not understanding something, or the bit about approximating the velocity should be changed. --Numsgil (talk) 05:58, 2 June 2008 (UTC)