Numerical Integration

The term "Numerical Integration" seems to encompass quite a few different but related topics. But for the purposes of my project, we are refering to a family of algorithms for approximately solving ordinary differential equations. Many different methods exist, such as Euler, Verlet and a whole family of methods called Runge-Kutta.

Euler Integration is the most basic method. It involves multiplying a differential by a change (or delta) in the independent variable to work out the change in the dependant variable over a "step" or interval. This value is then added to the old value from the last step.

E.g. At time 0.1 seconds, a particle was moving at 10m/s and the acceleration of the particle was 5m/s^2. How fast is the particle moving at 0.2 seconds?

The step measurement here is in time so let's say the distance between each step is 0.1 seconds.

And differential here is acceleration (the change in velocity with respect to time):

A(t) = d V(t) / d t

We want to know how much the velocity has changed this step. So it's intuitive that we multiply this differential by the size of the time step (delta t):

Change in V(t) = A(t) * dt

The new V(t), then, is this change plus the old value from the last step:

V(t) = V(old_time) + A(t) * dt

Punching in the numbers from above:-

V(t) = 10 + (5 * 0.1)
V(t) = 10.5

...we get the velocity to be 10.5m/s after 0.2 seconds.

This is basic Euler Integration. It is a fast and simple method. It's major drawback is the accuracy of the results it produces. All Numerical Integration techniques are designed to give an approximate solution but the Euler method is the most inaccurate of all. It's huge downfall is that it assumes the differential to be constant over the step interval. What happens in the example above when the acceleration wildly fluctuates between 0.1 seconds and 0.2 seconds? The result at 0.2 seconds could be hugely inaccurate. What's more is the error accumulates since each result is based on the value from the last step.

-----------------------------------------------

Verlet Integration is a scheme often used in computer simulations. It evaluates the differential, not as a result of integrating, but as the difference in the dependant variable since the last step.

For example:

Si+1 = Si + (Si - Si-1) + a* dt*dt

Where Si+1 is the new position, Si is the last position, a is acceleration, dt is the size of the time step and (Si - Si-1) is velocity.

In this example, not evaluating velocity by integrating acceleration means greater accuracy and more predictable results. It breeds avantages such as being able to instantaneoulsy place objects, with their velocity implicitly defined as a result of their movement. However, as with Euler, the Verlet scheme also assumes the differential (acceleration in the example) to be constant over the time step.

-------------------------------------------------------

The family of Runge-Kutta methods evaluate the derivative at multiple points along a time step interval to converge to a more accurate solution.

One known as the Midpoint Method (or second-order Runge-Kutta) uses the initial derivative to find the derivative half-way between this step and the next. Then this "half-way derivative" is used to integrate over the whole step.

These methods are superior to Euler and Verlet in that they accept changes in the derivative over the time step.

A Higher-order method, such as the Runge-Kutta 4 method, calculates four derivatives between the current step and the next. Each successive calculation of the derivative uses the old derivative as input. An example of how the four derivatives are calculated follows.

Suppose that velocity (derivative of position wrt time) is given by a known function of time and position:

dS/dt = f (t, s)

Derivatives per time step are calculated as follows:

• a = f (t0, position from last interval)
• b = f (t0 + h/2, position half-way to next interval (calculated from derivative a))
• c = f (t0 + h/2, position half-way to next interval (calculated from derivative b))
• d = f (t0 + h, position at next interval (calculated from derivative c))

Where t0 is time at the beginning of the last interval and h is step-size.

Then the Runge-Kutta 4 method evaulates the final result as follows:

[new value] = [value from last interval] + h/6(a + 2b + 2c + d)

---------------------------------------------------------------------------------

Within the field of numerical integration is a concept of Adaptive Time-Stepping. Adaptive Time Stepping is designed to improve the accuracy of the solution whilst maintaining as much efficiency as possible. It works on the principle that with smaller time-steps, results become more accurate. This fact makes all these algorithms adaptive in terms of accuracy, simply by modifying the time-step. This is an advantage but the problem is, decreasing the time step means increasing the computation cost. So adaptive time stepping works on the idea that the ideal would be to take small time-steps when the results coming back are inaccurate and larger time steps when they are of an acceptable accuracy.

Adaptive time stepping adapts the integration scheme through a feedback loop, which per step calculates the error in the last result, makes a decision whether this is "acceptable" and then modifies the time-step accordingly.

Sources:

Numerical Recipes In C : The Art of Scientific Computing, by W.Press, B.Flannery, S.Teukolsky and W.Vetterling.
http://gafferongames.wordpress.com/game-physics/integration-basics/
http://www.gamedev.net/reference/programming/features/verlet/default.asp
http://www.gamedev.net/reference/programming/features/verlet/default.asp
http://mathworld.wolfram.com/Runge-KuttaMethod.html
http://www.myphysicslab.com/runge_kutta.html
http://numericalmethods.eng.usf.edu/mcquizzes/08ode/runge4th.pdf

Differential Equations and Integration

The derivative of a function is a measurement of how it changes when it's input changes.

Another way of looking at this is that the derivative of a function is an expression for the gradient of the curve of the function. Derivatives are concerned with dependant and independent variables. You can think of the independent variable as an input to a function. It is unaffected by other variables. And the variable that is dependant is changing with the independent variable. In a derivative, the change of the dependant variable with respect to the independent variable is being expressed.

Velocity can be expressed as a derivative - the change of position with time. Here, time is the independent variable and position is the dependant variable.

A differential equation is one that relates the derivative of a function to some other function and/or another derivative.

What is known as an ordinary differential equation is a differential equation that has only one independent variable. A partial differential equation is one that has two or more independent variables.

So a differential equation that relates acceleration (dv / dt) with velocity (ds / dt) would be ordinary, since "t" is the independent variable here in both cases.

The goal of solving differential equations is to not to solve for an unknown value but to solve for an unknown function.

For example, given an unknown function for the position of a particle, S(t) and a known function for the velocity of a particle, V(t),

V(t) = d S(t) / d t

,where V(t) is the derivative of S(t) with respect to time, we can solve for the function S such that the above equation is true. Once S is found we can plug in a value of "t" to obtain a position.

We would solve this equation using a method known as Integration.

Integration is like the reverse of differentiation. The integration of a derivative will bring us back to the function we started with. This is sometimes known as anti-differentiation. The result is a expression called an indefinite integral.

More useful is to integrate over a range of values. This results in a definite integral, which is a "real value" representing the area on a graph between the curve of the function and the x-axis beween the range of values.

It is like adding up all the results (the changes) over the given range of the independent variable (e.g. between x=a and x=h for the above example). The result of adding these changes together gives us an actual value. Thus we can see how integrating velocity (the change in position with respect to time) can give us a position value. However, to get the real value, we must know and add on the initial value. When this is unknown it is acknowledged after integration by adding a constant, C.

Going back to the above example, the equation can be solved by integrating both sides with respect to "t". As shown below:

V(t) dt = S(t)

Notice that the previous right-hand-side of the equation, the derviative (d S(t) / dt), integrates to just S(t). But what is the integral of V(t) with respect to "t"? In some situations, depending on what the function V is, an exact integral is possible via analytical integration. However, in other situations numerically solving the differential equation is either more plausible or required.

That is where we come into the realm of Numerical Integration.

Research on numerical integration coming soon.


Sources:

http://en.wikipedia.org/wiki/Numerical_ordinary_differential_equations
http://www.physics.ohio-state.edu/~physedu/mapletutorial/tutorials/diff_eqs/intro.html
http://www.myphysicslab.com/what_diff_eq.html
http://en.wikipedia.org/wiki/Integral
http://en.wikipedia.org/wiki/Differential_equation
http://en.wikipedia.org/wiki/Derivative

Survey Paper From 1996

Before the christmas break i got down to reading a few papers and managed find what looks a really relevant survery paper called:

" Computer Graphics Techniques For Modelling Cloth" by H.Ng & R.Grimsdale

This pretty much sums up most of the work done in cloth modelling and simulation up until 1996 when it was published.

The paper shows shows three main approaches to modelling cloth in the past.

• Geometrical - where the appearance of cloth is modelled - not the behaviour. The model is based on geoemetrical equations, which can represent the features of cloth like folds and creases. The mechanical properties of cloth are not concerned with.
• Physical - where the model is based on actual physical properties and behaviours of cloth. Forces are 'applied' to a piece of cloth and a simulation is ran to produce the desired shapes(s).
• Hybrid - a combination of the two, where some features are modelled geometrically and others physically.

Looking a bit at the goemetrical approaches, they generally seem simple and flexible. Where things can be altered easily in order to get the desired shape(s). Like, it is what it is; it does not have to be accurate at all. However, i think getting results that are realistic would be difficult. Furthermore, it seems plausible that basic cloth animation could be done, but not interactive simulation of cloth that can respond to its environment. This is where the need for a physical model becomes apparent. And since the aim of my project is to create a cloth simulation that is interactive, i decided to disregard geomertical methods and focus on the physical ones in the paper.

However, i found when reading about the physically based methods, a number of unfamilar concepts repeatedly leaped out and puzzled me. Additionally, there were other more familar concepts that i still felt needed some refreshment or further reading. So i made a list of these concepts which goes...

• Differential Equations and Integration.
  
• Numerical Integration.
• Energy minimization.
• Finite Difference and Finite Element method.
• Elasticity Thoery.
• Lagrange's Theroy.
• D'Alembert's Principle.
• Navier-Stokes equations.
• Multi-grid method.
• Equation 'stiffness'.
• Sparse Linear Systems.

Admittedly, theres alot to look into there but i think to really get to grips with the subject matter, a reasonable understanding of these concepts is going to help alot when reading further material.

---------------------------------------------------------------------------------------

So i'm covering these concepts now, over the christmas break. I'm currently refreshing myself on Differential Equations, having covered them at A Level Maths but none-the-less feeling rusty on the subject.

I'll post back very soon to sum-up and digest what i found.