Talk:Verlet integration

From Wikipedia, the free encyclopedia

Just a note - the base page was by me but I wasn't logged in :( DivisionByZero 01:25, Jul 15, 2004 (UTC)

This page sounds like it was written by a 14 year-old kid who read some webpages about game programming. Can we get a more formal definition?

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)

Contents 1 Velocity error term 2 Constraints 3 Inverting a Matrix 4 acceleration, another methods, constraints 4.1 acceleration 4.2 another methods 4.3 constraints

[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

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³) means roughly C(Δt)³ for some constant C, and

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

[edit] Constraints

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

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

[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)

[edit] acceleration, another methods, constraints

[edit] acceleration

x(t₀ + Δt) = 2x(t₀) − x(t₀ − Δt) + aΔt²

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"?

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".)

[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)