POV-Ray : Newsgroups : povray.advanced-users : Runge-Kutta Server Time
31 Oct 2024 19:29:00 EDT (-0400)
  Runge-Kutta (Message 1 to 8 of 8)  
From: Orchid XP v2
Subject: Runge-Kutta
Date: 20 Aug 2005 16:53:12
Message: <43079838$1@news.povray.org>
There comes a time in every POVer's lifetime when they have to know...

I've Googled, I've visited Mathworld and I've checked out Wikipedia. 
(That last one actually made sense, impressively.) So I now know what 
RK4 *is*... and roughly how it works... but... Integral calculus isn't 
my strong point. (I'm much better at differential calculus.) The 
notation confuses me. Plus, the equations of motion usually aren't 
first-order.

So, I'm *sure* this is in a VFAQ _somewhere_... anybody have an 
explanation for how you do physics simulations with this thing?


Post a reply to this message

From: Thies Heidecke
Subject: Re: Runge-Kutta
Date: 21 Aug 2005 10:17:19
Message: <43088cef$1@news.povray.org>
"Orchid XP v2" <voi### [at] devnull> schrieb im Newsbeitrag 
news:43079838$1@news.povray.org...
> There comes a time in every POVer's lifetime when they have to know...
>
> I've Googled, I've visited Mathworld and I've checked out Wikipedia. (That 
> last one actually made sense, impressively.) So I now know what RK4 
> *is*... and roughly how it works... but... Integral calculus isn't my 
> strong point. (I'm much better at differential calculus.) The notation 
> confuses me. Plus, the equations of motion usually aren't first-order.
>
> So, I'm *sure* this is in a VFAQ _somewhere_... anybody have an 
> explanation for how you do physics simulations with this thing?

i'll try to explain it:
i'll take a simple harmonic oscillator as an example.
you start with your differential equations in a vectorised form
so that the timederivative is on the left side and the right side
is a function of all your variables. In our example you start with
F = m*a = -k*x  =>  a = -k/m*x
Acceleration is the second derivative of the distance with respect to

but we need the differential equation in a form that contains only
first order time derivatives. Therefore we just introduce a helper
variable, namely the velocity. Then we can formulate our second order
diff. eq. with two first order diff. eqs.:
instead of

we write
 dx/dt = v
 dv/dt = -k/m*x
written more generally as matrix:
    d /x\   / 0    1\ /x\
   -- | | = |       |.| |
   dt \v/   \-k/m  0/ \v/

now to the runge-kutta part:
The right side of the last equation can be thought of as a function
of the coordinates in phasespace (in our case x,v) which tells us
the first timederivative. In general the time itself 't' could also
influence the rightside (for example if the springconstant of our
oscillator changes with time). Now we have all what we need to
simulate our differential equation since our function gives us the
timederivative of all systemcoordinates for every possible state
of the mechanical (or whatever) system.
We call this function f(x,t) (where x is an n-dimensional vector)
and it returns an n-dimensional vector with the timederivatives.

Now we can formulate the various integration algorithms in an easy
way with our function f(x,t):
Let the stepsize in time be 'h'.
Then an ordinary Euler integration step can be seen as:

 x(t+h)=x(t) + h*f(x,t)

we just take the old coordinates and add our stepsize times the
timederivative which we get from our function f
In this way the Runge-Kutta 4th order step looks like this:

k1=h*f(x(t)     ,t    )
k2=h*f(x(t)+k1/2,t+h/2)
k3=h*f(x(t)+k2/2,t+h/2)
k4=h*f(x(t)+k3  ,t+h  )
x(t+h)=x(t) + 1/6 * (k1+2*k2+2*k3+k4)

the k1,...,k4 are multiple guesses for the time-derivative
which build upon each other. Then they are combined in
a weighted average to give the final estimate for the slope.

so the essential idea is to formulate your physical problem
as function f(x,t), then it's very easy to implement.
If the programming language doesn't support vector-valued
returnvalues you have to make a function f for every vector-
component, so in the example we would have fx and fv and then

kx1=h*fx(x(t)      ,v(t)      ,t    )
kv1=h*fv(x(t)      ,v(t)      ,t    )
kx2=h*fx(x(t)+kx1/2,v(t)+kv1/2,t+h/2)
kv2=h*fv(x(t)+kx1/2,v(t)+kv1/2,t+h/2)
kx3=h*fx(x(t)+kx2/2,v(t)+kv2/2,t+h/2)
kv3=h*fv(x(t)+kx2/2,v(t)+kv2/2,t+h/2)
kx4=h*fx(x(t)+kx3  ,v(t)+kv3  ,t+h  )
kv4=h*fv(x(t)+kx3  ,v(t)+kv3  ,t+h  )

x(t+h)=x(t) + 1/6 * (kx1+2*kx2+2*kx3+kx4)
v(t+h)=v(t) + 1/6 * (vx1+2*vx2+2*vx3+vx4)

if you have a 3d-problem, you'll have
6 formulas like that for px,py,pz,vx,vy,vz
it's just more complicated to write, but not really anything new,
you get the idea...

hope that get's you started :)

Thies


Post a reply to this message

From: scott
Subject: Re: Runge-Kutta
Date: 22 Aug 2005 05:54:52
Message: <4309a0ec@news.povray.org>
Orchid XP v2 wrote:
> There comes a time in every POVer's lifetime when they have to know...
>
> I've Googled, I've visited Mathworld and I've checked out Wikipedia.
> (That last one actually made sense, impressively.) So I now know what
> RK4 *is*... and roughly how it works... but... Integral calculus isn't
> my strong point. (I'm much better at differential calculus.) The
> notation confuses me. Plus, the equations of motion usually aren't
> first-order.
>
> So, I'm *sure* this is in a VFAQ _somewhere_... anybody have an
> explanation for how you do physics simulations with this thing?

Download this:

http://www.gaffer.org/downloads/GamePhysics.zip

and read "integration.rtf".

He uses C++ in the example code, but you should be able to work out.


Post a reply to this message

From: Orchid XP v2
Subject: Re: Runge-Kutta
Date: 22 Aug 2005 14:59:25
Message: <430a208d$1@news.povray.org>
> hope that get's you started :)

I guess the main problem is that physics equations typically involve the 
*second* derrivative of position - whereas RK seems set up for the first 
order only. From what I can see in your workings, the trick is to write 
the two terms as a matrix...?


Post a reply to this message

From: Slime
Subject: Re: Runge-Kutta
Date: 22 Aug 2005 15:38:40
Message: <430a29c0$1@news.povray.org>
> http://www.gaffer.org/downloads/GamePhysics.zip

Thanks for this link!

 - Slime
 [ http://www.slimeland.com/ ]


Post a reply to this message

From: Thies Heidecke
Subject: Re: Runge-Kutta
Date: 22 Aug 2005 16:02:41
Message: <430a2f61$1@news.povray.org>
"Orchid XP v2" <voi### [at] devnull> schrieb im Newsbeitrag 
news:430a208d$1@news.povray.org...
>> hope that get's you started :)
>
> I guess the main problem is that physics equations typically involve the 
> *second* derrivative of position - whereas RK seems set up for the first 
> order only. From what I can see in your workings, the trick is to write 
> the two terms as a matrix...?

the trick is that you can write an n-th order linear differential equation
as n first order equations by introducing 'helper-variables'.
In the simple example of the harmonic oscillator you replace this 2nd order
diff. eq. of position by two first order diff. eqs. of position and 
velocity.
Thereby you can avoid the second derivative of position with respect to time
because you can replace it with the timederivative of velocity:
 x''(t) = -k/m*x(t)               [1]
 x'(t)  = v(t)                    [2]
 x''(t) = v'(t)                   [3]
with [3] you can replace the x''(t) in [1] with v'(t), so [1] becomes
 v'(t) = -k/m*x(t)
Together with [2] you get the first order system:
 x'(t) = v(t)
 v'(t) = -k/m*x(t)

The matrixform is just to get another perspective on this
(if you're into linear algebra) and it's also a convenient way to write
linear relations. But it's not necessary to be solvable by RK4-methods.
You can use the same idea to turn a nonlinear differential equation
into a system of equations. For example:
 x'''(t)+2*x''(t)^2-x'(t)+Sin(x(t))+Exp(t)=0
can be broken down by some new helper variables y(t) and z(t):
 x'(t)  =y(t)
 x''(t) =y'(t) =z(t)
 x'''(t)=y''(t)=z'(t)
then we can write:
 x'(t)=y(t)
 y'(t)=z(t)
 z'(t)=-2*z(t)^2+y(t)-Sin(x(t))-Exp(t)

As long as the differential equation is in explicit form it's easy to get
it into RK4-compatible form.


Post a reply to this message

From: scott
Subject: Re: Runge-Kutta
Date: 25 Aug 2005 04:25:18
Message: <430d806e$1@news.povray.org>
Slime wrote:
>> http://www.gaffer.org/downloads/GamePhysics.zip
>
> Thanks for this link!

No problems, it's been in my bookmarks for a while, but I never got round to
reading it properly.  I noticed that document is actually linked from his
main page anyway.

http://www.gaffer.org/articles/

One day I will get round to having time to play with these ideas seriously!


Post a reply to this message

From: d jarbee
Subject: Re: Runge-Kutta
Date: 12 Oct 2005 18:45:00
Message: <web.434d90f891f85fb03c83beb30@news.povray.org>
"scott" <sco### [at] spamcom> wrote:
> Slime wrote:
> >> http://www.gaffer.org/downloads/GamePhysics.zip

That file doesn't seem to exist any more.
However, a short explanation can be found at:

http://astronomy.swin.edu.au/~pbourke/modelling/solver/

with a particle system example at:

http://astronomy.swin.edu.au/~pbourke/modelling/particle/


Post a reply to this message

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.