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.

A Look @ Agile Software Development

Having been prompted by my tutor, I decided to take a look at Agile Software Development today and find out what it's all about.



Here are the some of the underlying principles i extracted from my research:-

• Changes in requirements are accepted as inevitable.
• KISS (Keep it simple, stupid!). Don't do more work than is required.
• Code should be of High-quality and clear of it's intention. Techniques such as design patterns and refactoring are embraced.
• Systems are built incrementally, each piece at a time with frequent builds encouraged.
• Focuses on the strong value of team-work rather than the use of excessive or expensive tools to improve productivity. Believes that face-to-face conversation with team members is always the best method of communication.
• It's all about the software. Documentation can be neccessary but takes a back seat to the primary goal of creating high-quality software. Unless documentation is absolutely required, it is avoided.
• Constant communication between the developer and customer is vital so that "inevitable" changes can be relayed effectively.
  

The term Agile development encompasses many recently developed methodologies such as XP, SCRUM and Test-driven Development. Work is generally done iteratively in small independant teams that make a piece of software every couple of weeks. Each iteration will contain phases similar to those in the Waterfall Method, such as Planning, Requirements Analysis, Design, Implementation, Testing and Evaluation.

It was useful last year that we touched on Design Patterns and UML diagrams in the 'Rendering' module. This helped to understand the purpose of Agile development and the issues with implementing maintainable and flexible code for large systems.

We also touched on Refactoring last year in the GS2 module, which basically encompasses the restructuring of code so that is it more usable, understandable, reliable, flexible or maintainable, WITHOUT actaully changing what the code does. Again, this helped to understand the motivation for the principles in Agile development.

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

Essentially, Agile development seems to be about simplicity. It's like a 'stripped-down' appraoch to software development. In many ways, it seems to be about finding the most effective and least painful way of arriving at the end goal - software that works. It focuses on what matters and devotes time to what is most important, whilst ignoring the laborious processes that do little to actually progress the project.

Equally it promotes focusing on the problems of 'the now' and tackling potential problems when they arrise.

Seems perfect for the stereotypically lazy student!

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

I think some of the principles of Agile development create a good mindset to approach implementing the application with. However, it's views on documentation mean i cannot wholely take on the Agile mindset, since 70% of the project marks are awarded for the report, making the documentation of higher priority than the application! Additionally, some of the principles seem only applicable to team-work, whereas i am undertaking this project alone.

I am also reluctant to take the iterative approach that is described in many Agile practices. Again this is designed for teams but the main worry is that i would not have enough time to complete more than one iteration in the allotted time for the project.

What was interesting was thinking about the way Agile development accepts changes as inevitable and the realisation that the requirements within my project could change as i begin to understand more about the subject area. Perhaps the adoption of Agile methods during my implementation could ensure the impact of these potential changes are kept to a minumum?


Sources :

• 'Agile Software Development' by Robert C.Martin.
• Wikipedia Article - http://en.wikipedia.org/wiki/Agile_software_development
• Youtube - Interview with Shane Warden and Jim Shore - "On The Art Of Agile Development" - http://uk.youtube.com/watch?v=bfmLsQq6OUU
• Youtube -"Agile Software Development" http://uk.youtube.com/watch?v=1Qg6sgS8QIE
  

Max Garber's Cloth Simulation App

Hi all,
Research is officially under-way! So first-up, i found this peice of work:-

Max Garber, Cloth Simulation

This is a really cool application; it allows the user to fire cannon balls at two pieces of cloth, and the cloth simulation and collision response seem very good. The dude who created this piece referenced an article - Advanced Character Physics by Thomas Jakobsen - as what he based it on. So i thought what better place to start than this:

'Advanced Character Physics', by Thomas Jakobsen

What I Learned From This Article
This article introduced me to a wide range of different topics concerned with real-time simulation.

The first interesting thing it mentions about simulation for real-time use is accuracy is not the major concern - it is more about believability, speed of execution and stability. Ultimately, for real-time use, if the programmer can cobble together a fast and stable solution that still looks believable to a degree, this is more valuable than an immensely accurate simulation.

Verlet Integration
Verlet integration works by storing a particles position and last position. The concept of velocity is not really taken into account, although it is implicity defined for the last frame by (position - old position). Not explicitly defining a velocity for a particle means, you can 'pick-up' particles and place them somewhere, in an instant; their velocity is implicitly defined as a result of their movement and the simulation continues smoothly - this makes it very useful for collision handling.

Constraints
Particle positions can be constrained by 'springs'. A weak spring will gradually satisfy a constraint and a stiff spring will rapidly satisfy a constraint. An infinitely stiff spring can instantly satisfy a constraint (put a particle straight back where it should be).

An Iterative Approach to Satisfying Multiple Constraints
Satisfying multiple constraints can be a problem because satisfying one constraint can invalidate another. The article mentions a method whereby each constraint is satisfied individually, and this process is repeated a number of times per frame. This winds up giving a result that converges to satisfy all constrains simultaneously (Apparently! I can foresee situations where the constraints are continually invalidating each other?). Supposedly, more times you repeat, the better the result converges so the method becomes flexible in terms of simulation accuracy, which is very useful for optimisation. Additionally, the articles states that Verlet Integration maintains the simulations stability independently of how accurate the results are.

Approximating Square-Roots
When satisfying a constraint such as the distance between two particles, a square-root calculation must be done per frame to know the current distance between them. Put simply, square-roots are slow and expensive. So a good optimization is to approximate the result. A method to do this is touched on in the article called 1st order Taylor-expansion. This needs further reading to understand its implemtation.

How can this be applied to my project?
Cloth could be a grid of vertices, each represented by point-particles with constraints between adjacent particles modelled by springs. Constraints are solved iteratively therefore giving a simulation with flexible accuracy, optimisable for real-time.


What didn't i understand in this article / what else needs to be researched?

• Numerical integration - the article mentions other types, which would be worth looking into. Also i'd like to better understand the issues related with stability (what exactly makes a method stable or unstable? and why do the stability issues arrise?).
• The article mentions optimisation through use of an array of floats instead of a Vector3 representation - how does this work?
• Approximating square-roots. 1st order Taylor-Expansion - how does this work and how can it be implemented?
  
• Relaxation / Jacobi or Gauss-Seidel iteration - learn more about this iterative constraint handling and how it converges the results to satisfy multiple constraints.
  

Thoughts on Research

Research Purpose
What is the purpose of my research?

• To get the knowledge and skills to actually create what i plan to create.
• To be able to write an informed requirements analysis for the application.
• To be able to document the learning process in the project write-up.

See What's Out There
For my initial research i am simply going to see what's already been done in the field. The goal being a good understanding of the fundamentals (if they exist!) in simulating cloth, and a good overall feel for what's possible, what's been tried, what works, what doesn't ect!

Branching
I plan to approach the research by branching off if needed. So when i'm researching and i come accross a concept i'm not familiar with, i will branch away to discover what it is, make a note of the article i was reading previously and come back to it later. I realise this could mean branching around on a wild goose-chase, particularly in the beginning, even perhaps into topics that aren't relevant. However, i think it is a good approach as long as i keep record of previous material i didn't finish reading and i ensure what i'm researching doesn't get completely off-topic. Common sense will decide when to branch and when not to.

Specific Features
After a good grounding in the concepts involved, i'm then gonna start researching about the specific features i want the Cloth to show - real-time, interaction, collision ect.

----------------
So that i can document the learning process in the write-up, i will show and organise my findings here, on this blog.

Tim.

The first of many...

Hi all,

Welcome to my Final Year Project blog. This is gonna' be a collection of ideas and thought processes associated with the Final Year Project module, and also just general updates outlining where i'm at in the project.

So, with the specification submitted i have finally decided what my project is going to be:-

Cloth simulation showing the following features:-

• It is real-time.
• It exists within a three-dimensional environment.
• The cloth moves and deforms realistically in accordance with its environment.
• The simulation is interactive through allowing the application user to move and deform the piece of cloth.
• The piece of cloth can collide with simplistic primitives, such as a sphere or cuboid, in a realistic fashion.
• The piece of cloth is fixable at points in the 3D environment.

An application showing an implementation of cloth with these features will be implemented. Along with a 10,000 word report that discusses the research process, learning outcomes, decisions made, and then documents the testing of the application and wraps up with an evaluation of the project.

With the specification i gave a rough project schedule as:-

• Nov – Research relevant subject matter and gain knowledge needed.
• Dec – Analysis of requirements upon reflection of research. Application design.
• Jan – Start application construction / implementation.
• Feb – Complete application. Testing of application. Begin write-up.
• March – Finish write-up.

By December i'd like to be in a position of thorough understanding in the cloth simulation techniques out there, be deciding what the most suitable method(s)/technique(s) for me to use are, and then start thinking about how i might actually implement the application.

First things first though : Research!

Onwards and upwards.

Tim.