Why this paper?
This paper attempts to model deformable objects for general applications with less restrictions apparent than in previous models.
It looks at a more efficient collision detection and handling process, that is universally suitable for all kinds of collisions with a surface (and handles many consecutive collisions).
The process described handles self-collision very efficiently.
It highlights the difficulties of collision handling in generic situations; that possible optimizations based on a known predifined contex do not apply.
How is cloth represented?
The paper states the underlying representation they will use will be a particle system, where each particle represents a vertex of a triangle (where triangles share vertices and therefore particles too).
Cloth is considered to be isotropic material (meaning it's properties are independant of the direction in which they are measured) and of constant thickness.
What are the "Driving Equations" of the cloth?
Deformable surfaces are simulated through Integration of newtons motion equation, keeping time-steps as small as possible. It says that other more complex methods (energy minimization, lagrange dynamics) allow larger time-steps, but since the collision detection algorithm will require small time-steps to be effective these methods are ignored.
The numerical integration method used to solve the equations is the second order (midpoint method) of the Euler-Cromer method (also known as the semi-implicit Euler method). An adaptive time-step scheme is incorporated into this routine, giving optimal efficiency whilst maintaining accurate results.
Buckling, due to cloth compression, is considered into the Elastic properties that model the cloth (Young's modulus, Poisson coefficient, density and thickness) by allowing the Young's modulus to vary, depending on whether the cloth is stretched or compressed.
Cloths ability to move past positions from which it will no longer return (like a spring going beyond it's elastic limit) is handled by changing the inital conditions of the differential equations to the current conditions when a deformation exceeds a certain amount.
Curvature forces are evaluated by looking at the "hinges" (sharing edges) of triangles and using the angle between the normals.
Strain within the cloth is calculated from the strain at each edge of each triangle.
Contraints caused by collisions are satisfied iteratively.
How are collisions with the cloth handled (if at all)?
Collisions are handled as a seperate process. Cloth is simulated, then collision detection is ran and then the neccessary collision handling is taken care of.
To increase efficiency, an algorithm based on hierarchical octree subdivision singles-out the potentially colliding elements at any one time. It takes advantage of adjacency between elements in a heirarchy, which is built once during preprocessing. The criteria for which elements should be "collision checked" is based on a calculated property "surface curvature". The surface curvature property is also used to cut-down the self-collision tests.
Any results or conclusions of interest?
A simulation was run on pieces of cloth within a rotating cylinder to animate them the way a drying machine would. This was a good test of the robustness of the collision detection algorithm, since many collision configurations occur, and interactions of cloth-to-cloth and solid-to-cloth are frequent. It is also a good test for the collision response procedure and the overal numerical stability of the model.
Additional Sources:
http://www.thefreedictionary.com/isotropic
http://en.wikipedia.org/wiki/Young%27s_modulus
http://en.wikipedia.org/wiki/Symplectic_Euler_method
Wednesday, 7 January 2009
Friday, 2 January 2009
C.Feynman - "Modelling the Appearance of Cloth" (1986)
Why this paper?
This was the first paper pointed to by the Survey Paper that looks at physically modelling cloth. From 1986, it is also probably one of the first written on the topic.
How is cloth represented?
In this paper, Feynman represents cloth as a discrete, uniform grid of points. A "multi-grid method" is used, where multiple grids of varied densities are used to represent cloth; see below.
Cloth is modelled such that each point represents a piece of cloth sized h*h (where h is the distance between points) The behaviour of a point is governed only by its nearest neighbours, thus two points on opposite sides of the cloth have no impact on each other.
What are the "Driving Equations" behind the cloth?
Cloth is simulated by minimizing its energy state. This is also known as relaxation. The sum of the energies at each point equals the energy state of the entire cloth.
Each point is relaxed one-by-one. Each point in the grid is relaxed by evaluating a "force vector" that will move the point into a position of decreased energy. When this is done for all points, the overall energy state of the cloth is decreased.
Feynman derives and equation to evaluate the energy state of the cloth from the theory of elastic plates. This equation attempts to mimic the energy dynamics of cloth in "real-life". In his approximation, the total energy is a combination of gravitational effects, bend effects and strain effects. (Strain being distortion within the plane of the cloth, and bend being distortion outside the plane.)
The multi-grid method is an optimization based on the premise that creating large features (large folds ect) through relaxation on a fine grid is more costly than on a coarse grid. In fact there is an optimal grid size (point-spacing) for a feature of a certain size, so that it is small enough to represent to the feature but coarse enough that as few as possible points have to be relaxed.
The idea behind the multi-grid method then, is that multiple relaxation sweeps are done for grids of multiple resolutions -- finer grids for small features and coarser grids for larger features. Finally results from these relaxation sweeps are molded together, incorporating both the small and large features into one grid.
How are collisions with the cloth handled (if at all)?
Feynman included support for collisions with ellipsoids. Ellipsoids can be used to represent a wide range of solid objects, whilst can be algebraically defined easily (although Feynman admits the collision detection is still a slow process). He defines a collision as one or more points being inside the volume of the ellipsoid. A collision is handled by placing the point back at the nearest point outside of the ellipsoid.
Feynman comments that the results involving collisions are disappointing and highlights that when the cloth grid is too coarse it is possible for solid objects to completely pass through the cloth without a collision even being detected.
Any results or conclusions of interest?
Feynman simulated environments with hanging clothes and cloth draped over a sphere.
But no results regarding the time taken to run these simulations were given.
Note that this paper produced static results not animated ones. Feynman discusses the difficulty of using the energy minimization approach to a dynamic simulation. Since one of my "requirements" is that my simulation is dynamic, perhaps, as Feynman advises, the energy minimization technique would not be the best approach for me to take.
An interesting observation that Feynman highlights was the difference between stretching and compressing cloth, and the different way it responds to these actions. He explains how cloth is strong when it comes to resisting stretching but weak at resisting compression because of buckling. When you attempt to compress cloth, the fabric itself will most likely not give, but it will buckle instead (bend out of it's plane). Although mentioned, buckling is not a phenomenon taken care of in this work.
Another behavioural property of cloth highlighted is cloth's tendency to arrange itself in positions it has previously been in (particularly for long periods of time). This is due to prolonged arrangement of fibres in cloth and the friction between them. This phenomenon was also unaccounted for.
This was the first paper pointed to by the Survey Paper that looks at physically modelling cloth. From 1986, it is also probably one of the first written on the topic.
How is cloth represented?
In this paper, Feynman represents cloth as a discrete, uniform grid of points. A "multi-grid method" is used, where multiple grids of varied densities are used to represent cloth; see below.
Cloth is modelled such that each point represents a piece of cloth sized h*h (where h is the distance between points) The behaviour of a point is governed only by its nearest neighbours, thus two points on opposite sides of the cloth have no impact on each other.
What are the "Driving Equations" behind the cloth?
Cloth is simulated by minimizing its energy state. This is also known as relaxation. The sum of the energies at each point equals the energy state of the entire cloth.
Each point is relaxed one-by-one. Each point in the grid is relaxed by evaluating a "force vector" that will move the point into a position of decreased energy. When this is done for all points, the overall energy state of the cloth is decreased.
Feynman derives and equation to evaluate the energy state of the cloth from the theory of elastic plates. This equation attempts to mimic the energy dynamics of cloth in "real-life". In his approximation, the total energy is a combination of gravitational effects, bend effects and strain effects. (Strain being distortion within the plane of the cloth, and bend being distortion outside the plane.)
The multi-grid method is an optimization based on the premise that creating large features (large folds ect) through relaxation on a fine grid is more costly than on a coarse grid. In fact there is an optimal grid size (point-spacing) for a feature of a certain size, so that it is small enough to represent to the feature but coarse enough that as few as possible points have to be relaxed.
The idea behind the multi-grid method then, is that multiple relaxation sweeps are done for grids of multiple resolutions -- finer grids for small features and coarser grids for larger features. Finally results from these relaxation sweeps are molded together, incorporating both the small and large features into one grid.
How are collisions with the cloth handled (if at all)?
Feynman included support for collisions with ellipsoids. Ellipsoids can be used to represent a wide range of solid objects, whilst can be algebraically defined easily (although Feynman admits the collision detection is still a slow process). He defines a collision as one or more points being inside the volume of the ellipsoid. A collision is handled by placing the point back at the nearest point outside of the ellipsoid.
Feynman comments that the results involving collisions are disappointing and highlights that when the cloth grid is too coarse it is possible for solid objects to completely pass through the cloth without a collision even being detected.
Any results or conclusions of interest?
Feynman simulated environments with hanging clothes and cloth draped over a sphere.
But no results regarding the time taken to run these simulations were given.
Note that this paper produced static results not animated ones. Feynman discusses the difficulty of using the energy minimization approach to a dynamic simulation. Since one of my "requirements" is that my simulation is dynamic, perhaps, as Feynman advises, the energy minimization technique would not be the best approach for me to take.
An interesting observation that Feynman highlights was the difference between stretching and compressing cloth, and the different way it responds to these actions. He explains how cloth is strong when it comes to resisting stretching but weak at resisting compression because of buckling. When you attempt to compress cloth, the fabric itself will most likely not give, but it will buckle instead (bend out of it's plane). Although mentioned, buckling is not a phenomenon taken care of in this work.
Another behavioural property of cloth highlighted is cloth's tendency to arrange itself in positions it has previously been in (particularly for long periods of time). This is due to prolonged arrangement of fibres in cloth and the friction between them. This phenomenon was also unaccounted for.
Saturday, 27 December 2008
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):
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:
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
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.
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
The new V(t), then, is this change plus the old value from the last step: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
V(t) = V(old_time) + A(t) * dt
...we get the velocity to be 10.5m/s after 0.2 seconds.Punching in the numbers from above:-
V(t) = 10 + (5 * 0.1)
V(t) = 10.5
V(t) = 10.5
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.
Si+1 = Si + (Si - Si-1) + a* dt*dt
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:
Then the Runge-Kutta 4 method evaulates the final result as follows:
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.
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.
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))
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. ---------------------------------------------------------------------------------
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
Tuesday, 23 December 2008
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),
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
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.
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.
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
Friday, 19 December 2008
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:
The paper shows shows three main approaches to modelling cloth in the past.
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...
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.
I'll post back very soon to sum-up and digest what i found.
" 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.
This pretty much sums up most of the work done in cloth modelling and simulation up until 1996 when it was published.
- 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.
- 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.
Monday, 24 November 2008
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:-
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 :
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
Monday, 17 November 2008
Max Garber's Cloth Simulation App
Hi all,
Research is officially under-way! So first-up, i found this peice of work:-
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?
Research is officially under-way! So first-up, i found this peice of work:-
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.
Subscribe to:
Posts (Atom)