Reading whitepapers, especially on cloth simulation, I come across the trend that they offer an explicit solution over the implicit (or vice versa). What is the fundamental different between the two? Furthermore, what are some of the reasons for choosing one over the other?
0
Implicit/Explicit Integration
Started by daktaris, Apr 08 2005 03:43 AM
39 replies to this topic
Sponsor:
#2 Moderators - Reputation: 1345
Posted 08 April 2005 - 05:37 AM
The basic idea of explicit integration is that that these integrators are written in a way that you can update all unknown values (e.g., all particle positions) independently, in a loop such as this:
The particle positions, in this case, are treated as being decoupled, and aren't considered to affect each other.
As you can imagine, in the case of cloth, soft bodies, etc., this treatment of particle positions as being decoupled is not physically consistent. The particles in a particle representation of cloth, for example, are connected together by the cloth. They are coupled. For a given time step, explicit integrators actually move the particles out-of-sync with each other. At the end of the integration step above, for cloth, the particles are slightly in the wrong place.
Now, although for a given physics_step the particles are treated as being decoupled when you use explicit integration, they do become coupled again when you set up the forces and constraints prior to the next physics_step. Since the particles are slightly out of place, the forces and constraints actually are also slightly wrong. They will cause a small correction during the next physics_step, to try to put the particles in the right place. But, its a viscious cycle. The next physics_step overcorrects and the particles again are in the wrong place. The cycle repeats.
For some problems, this viscious cycle actually runs well. The simulation works. The results are always wrong, maybe slightly, maybe by a lot. But, the simulation runs and doesn't crash. For other problems, the cycle doesn't work, and the corrective forces work against the overshot positions to cause an unstable simulation, once in which particle positions and velocities grow without limit, resulting in overflow in just a few physics_steps.
The classic case that illustrates the instability of explicit methods is the simple spring mass problem. One mass tied to the ceiling with a spring. If you use the so-called "explicit Euler" integration method (far too popular in hobby game development), the simulation will crash because it happens that explicit Euler integration leads to unlimited growth of the error in position and velocity of the mass.
Now, on other hand, implicit integration treats the particle positions as coupled. They are solved together at each time step, as a system. The equation of motion for the system can be represented by a matrix equation:
MA + CV + KX = external forces
External forces things like an explosion blast force due to pressure, the weight of object being applied on the object by the floor, the force applied by a person smacking the other person, etc.
M is the so-called mass matrix, C is a damping matrix (ignore the term unless viscous damping is applied), K is the stiffness matrix (which represents the connection of a bunch of springs----this will feature prominently in spring-mass cloth systems).
A is the acceleration vector for the particles
V is the velocity vector for the particles
X is the position vector for the particles
The coupling/connections of the particles will be represented either in the matrices M, C, and K (preferred since these can often be precomputed) or in the unknowns A, V, X (not preferred).
The implicit solver works by computing M, C, K, then using a matrix solver or iterative (Jacobi, Gauss-Siedel, SOR) solver to compute new values of A, V, and X at the same time for all of the particles.
It turns out that by solving the particles as a coupled system, the potential for instability usually goes away and the simulator almost always works without instabilities and blow-ups.
The implicit result still has error (Taylor-series truncation error), and so the result still is imperfect. But, the implicit result is far, far more likely to actually be robust and work all the time.
The problem is...implicit integration is much more difficult (MUCH more difficult) to code correctly. Which is why people very often just go with an explicit integrator.
If you want to read a bit more (and with some hard math), you can read my article titled "Stable Rigid-Body Physics" from the Game Developer Conference 2001, available online here:
GDC 2001 Archives
I also recommend the references in the paper, especially the Tannehill book, which, despite its connection to fluid dynamics, is one of the best books I've ever seen for an introduction to the finer details of numerical integration and simulation. HIGHLY, HIGHLY recommended. (But, sadly, "pricey.")
void explicit_physics_step(time_step)
{
for (i = 0; i < num_particles; i++)
{
// this particular example happens to be explicit Euler, a particularly
// problematic explicit integrator
particle[i].position += particle[i].velocity * time_step;
particle[i].velocity += particle[i].acceleration * time_step;
}
}
The particle positions, in this case, are treated as being decoupled, and aren't considered to affect each other.
As you can imagine, in the case of cloth, soft bodies, etc., this treatment of particle positions as being decoupled is not physically consistent. The particles in a particle representation of cloth, for example, are connected together by the cloth. They are coupled. For a given time step, explicit integrators actually move the particles out-of-sync with each other. At the end of the integration step above, for cloth, the particles are slightly in the wrong place.
Now, although for a given physics_step the particles are treated as being decoupled when you use explicit integration, they do become coupled again when you set up the forces and constraints prior to the next physics_step. Since the particles are slightly out of place, the forces and constraints actually are also slightly wrong. They will cause a small correction during the next physics_step, to try to put the particles in the right place. But, its a viscious cycle. The next physics_step overcorrects and the particles again are in the wrong place. The cycle repeats.
For some problems, this viscious cycle actually runs well. The simulation works. The results are always wrong, maybe slightly, maybe by a lot. But, the simulation runs and doesn't crash. For other problems, the cycle doesn't work, and the corrective forces work against the overshot positions to cause an unstable simulation, once in which particle positions and velocities grow without limit, resulting in overflow in just a few physics_steps.
The classic case that illustrates the instability of explicit methods is the simple spring mass problem. One mass tied to the ceiling with a spring. If you use the so-called "explicit Euler" integration method (far too popular in hobby game development), the simulation will crash because it happens that explicit Euler integration leads to unlimited growth of the error in position and velocity of the mass.
Now, on other hand, implicit integration treats the particle positions as coupled. They are solved together at each time step, as a system. The equation of motion for the system can be represented by a matrix equation:
MA + CV + KX = external forces
External forces things like an explosion blast force due to pressure, the weight of object being applied on the object by the floor, the force applied by a person smacking the other person, etc.
M is the so-called mass matrix, C is a damping matrix (ignore the term unless viscous damping is applied), K is the stiffness matrix (which represents the connection of a bunch of springs----this will feature prominently in spring-mass cloth systems).
A is the acceleration vector for the particles
V is the velocity vector for the particles
X is the position vector for the particles
The coupling/connections of the particles will be represented either in the matrices M, C, and K (preferred since these can often be precomputed) or in the unknowns A, V, X (not preferred).
The implicit solver works by computing M, C, K, then using a matrix solver or iterative (Jacobi, Gauss-Siedel, SOR) solver to compute new values of A, V, and X at the same time for all of the particles.
It turns out that by solving the particles as a coupled system, the potential for instability usually goes away and the simulator almost always works without instabilities and blow-ups.
The implicit result still has error (Taylor-series truncation error), and so the result still is imperfect. But, the implicit result is far, far more likely to actually be robust and work all the time.
The problem is...implicit integration is much more difficult (MUCH more difficult) to code correctly. Which is why people very often just go with an explicit integrator.
If you want to read a bit more (and with some hard math), you can read my article titled "Stable Rigid-Body Physics" from the Game Developer Conference 2001, available online here:
GDC 2001 Archives
I also recommend the references in the paper, especially the Tannehill book, which, despite its connection to fluid dynamics, is one of the best books I've ever seen for an introduction to the finer details of numerical integration and simulation. HIGHLY, HIGHLY recommended. (But, sadly, "pricey.")
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net
#5 Members - Reputation: 208
Posted 03 May 2005 - 06:23 AM
Something that grhodes_at_work didn't mention is that explicit integration is a lot faster than implicit integration. The time to perform 1 explicit integration step is several orders of magnitude faster than 1 implicit integration. However you will need to perform a large number of explicit integrations to get obtain the same level of accuracy of implicit integration. For games accuracy is not so important as long as it looks believable as opposed to engineering applications. So you can get away with using relatively few interations.
You will need to perform at least 30 integrations per second for it too look smooth. This can be a problem for implicit integration if you have a large system of equations.
You will need to perform at least 30 integrations per second for it too look smooth. This can be a problem for implicit integration if you have a large system of equations.
#6 Anonymous Poster_Anonymous Poster_* Guests - Reputation:
Posted 03 May 2005 - 09:16 AM
Quote:
Original post by SpaceDude
Something that grhodes_at_work didn't mention is that explicit integration is a lot faster than implicit integration. The time to perform 1 explicit integration step is several orders of magnitude faster than 1 implicit integration. However you will need to perform a large number of explicit integrations to get obtain the same level of accuracy of implicit integration. For games accuracy is not so important as long as it looks believable as opposed to engineering applications. So you can get away with using relatively few interations.
You will need to perform at least 30 integrations per second for it too look smooth. This can be a problem for implicit integration if you have a large system of equations.
To be nitpicky, :)...
An implicit integration step does not necessarily take several orders of magnitude longer to update than an explicit integration step. If the problem is ill-conditioned, or if the integration scheme is poorly matched with the iterative system solver (e.g., Gauss-Siedel, SOR) for a particular problem, then yes implicit integration might take a long time to converge for each step. And, if you try to converge to an error of 1.e-32, then yes the implicit integrator might churn for a rather large number of expensive iterations and might never converge at all to that level of error. But, that is not in general true. For the banded systems that are common for most physics simulations of interest, I'd expect an appropriately chosen implicit integrator and matched iterative solver to cost a few multiples of an explicit step. Maybe one order of magnitude or so. But not "several orders of magnitude" more.
The comment about needing at least 30 integrations per second for smooth animation too is misleading. While it is sort of true that you want to update position and orientation at around 30 times/frames per second or more, it is hard to specialize and say that this means you have to do 30 physics integrations or second. Consider an object that is moving very slowly. You might only have to update it once a second because it covers only a few pixels onscreen in that amount of time. Now consider an object moving very fast, and interacting in complex ways. You might actually have to perform more than 30 integrations in order to achieve a stable simulation (at least with explicit integration, or to ensure high frequency interactions are captured). Doesn't mean you need to update the screen more or less. It just means physics might need to run at a rate that is very different from what you need to display.
I'll also just say that implicit integration is not necessarily more accurate than explicit. It can be less accurate! The major benefit you gain from implicit integration is stability. You can throw nearly anything at it and it'll run with any arbitrarily large time step (unless your inputs are kind of at the limits of floating point math). But if you throw a large time step at it, guess what? You are throwing away accuracy. Comparing implicit Euler to explicit Euler, as long as you stay within the latter's stability bounds, with the same time step you will have exactly the same accuracy.
#9 Members - Reputation: 208
Posted 03 May 2005 - 10:13 PM
Quote:
Original post by Anonymous Poster
To be nitpicky, :)...
An implicit integration step does not necessarily take several orders of magnitude longer to update than an explicit integration step. If the problem is ill-conditioned, or if the integration scheme is poorly matched with the iterative system solver (e.g., Gauss-Siedel, SOR) for a particular problem, then yes implicit integration might take a long time to converge for each step. And, if you try to converge to an error of 1.e-32, then yes the implicit integrator might churn for a rather large number of expensive iterations and might never converge at all to that level of error. But, that is not in general true. For the banded systems that are common for most physics simulations of interest, I'd expect an appropriately chosen implicit integrator and matched iterative solver to cost a few multiples of an explicit step. Maybe one order of magnitude or so. But not "several orders of magnitude" more.
The comment about needing at least 30 integrations per second for smooth animation too is misleading. While it is sort of true that you want to update position and orientation at around 30 times/frames per second or more, it is hard to specialize and say that this means you have to do 30 physics integrations or second. Consider an object that is moving very slowly. You might only have to update it once a second because it covers only a few pixels onscreen in that amount of time. Now consider an object moving very fast, and interacting in complex ways. You might actually have to perform more than 30 integrations in order to achieve a stable simulation (at least with explicit integration, or to ensure high frequency interactions are captured). Doesn't mean you need to update the screen more or less. It just means physics might need to run at a rate that is very different from what you need to display.
I'll also just say that implicit integration is not necessarily more accurate than explicit. It can be less accurate! The major benefit you gain from implicit integration is stability. You can throw nearly anything at it and it'll run with any arbitrarily large time step (unless your inputs are kind of at the limits of floating point math). But if you throw a large time step at it, guess what? You are throwing away accuracy. Comparing implicit Euler to explicit Euler, as long as you stay within the latter's stability bounds, with the same time step you will have exactly the same accuracy.
Well the speed depends on the size of your system of course. For large problems with tens of thousands of degrees of freedom the implicit integrator will be several orders of magnitude slower. For smaller systems with only say only 10 or 100 degrees of freedom that may not be the case. The explicit integration time will scale up linearly with the number of degrees of freedom whereas implicit will scale up n^2 or something (that may be wrong but its not linear anyway). I'm used to dealing with large systems as i'm doing a PhD in engineering using Finite Element code, so i can see that it will be somewhat different for games.
Isn't it true that its much harder to handle contact when using implicit integration as opposed to explicit for complicated contact cases? This seems like a big advantage to the explicit integration scheme.
#10 Members - Reputation: 179
Posted 04 May 2005 - 05:44 AM
Quote:
Original post by SpaceDude Quote:
Original post by Anonymous Poster
To be nitpicky, :)...
An implicit integration step does not necessarily take several orders of magnitude longer to update than an explicit integration step. If the problem is ill-conditioned, or if the integration scheme is poorly matched with the iterative system solver (e.g., Gauss-Siedel, SOR) for a particular problem, then yes implicit integration might take a long time to converge for each step. And, if you try to converge to an error of 1.e-32, then yes the implicit integrator might churn for a rather large number of expensive iterations and might never converge at all to that level of error. But, that is not in general true. For the banded systems that are common for most physics simulations of interest, I'd expect an appropriately chosen implicit integrator and matched iterative solver to cost a few multiples of an explicit step. Maybe one order of magnitude or so. But not "several orders of magnitude" more.
The comment about needing at least 30 integrations per second for smooth animation too is misleading. While it is sort of true that you want to update position and orientation at around 30 times/frames per second or more, it is hard to specialize and say that this means you have to do 30 physics integrations or second. Consider an object that is moving very slowly. You might only have to update it once a second because it covers only a few pixels onscreen in that amount of time. Now consider an object moving very fast, and interacting in complex ways. You might actually have to perform more than 30 integrations in order to achieve a stable simulation (at least with explicit integration, or to ensure high frequency interactions are captured). Doesn't mean you need to update the screen more or less. It just means physics might need to run at a rate that is very different from what you need to display.
I'll also just say that implicit integration is not necessarily more accurate than explicit. It can be less accurate! The major benefit you gain from implicit integration is stability. You can throw nearly anything at it and it'll run with any arbitrarily large time step (unless your inputs are kind of at the limits of floating point math). But if you throw a large time step at it, guess what? You are throwing away accuracy. Comparing implicit Euler to explicit Euler, as long as you stay within the latter's stability bounds, with the same time step you will have exactly the same accuracy.
Well the speed depends on the size of your system of course. For large problems with tens of thousands of degrees of freedom the implicit integrator will be several orders of magnitude slower. For smaller systems with only say only 10 or 100 degrees of freedom that may not be the case. The explicit integration time will scale up linearly with the number of degrees of freedom whereas implicit will scale up n^2 or something (that may be wrong but its not linear anyway). I'm used to dealing with large systems as i'm doing a PhD in engineering using Finite Element code, so i can see that it will be somewhat different for games.
Isn't it true that its much harder to handle contact when using implicit integration as opposed to explicit for complicated contact cases? This seems like a big advantage to the explicit integration scheme.
well for a CG solver its not O(n^2). indeed one iteration scales linearly with the DOF's, but the amount of iterations to take is quite sublinear. stiffness of the system is much more of a factor there.
as for it being slow: ive implemented a CG solved implicit mass spring system, and its close to an order of magnitude faster for a ~200 mass ~500 spring system, not considering the fact that the nature of the CG solver leaves open excellent possibilities for cache optimizations, which could theoreticly increase performance another order of magnitude, since 90% of all time is spent waiting for memory requests in my current implementation. thats not considering the fact SIMD operations could improve that further once memory isnt the bottleneck anymore.
as for contact: thats an interesting subject, one im trying to tackle right now. to get sucky collisions working is equally easy in both. good collision handling has always seemed impossible to me in an explicit sceme, since you simply never get close enough to the desired stiffness of the contacts (or the structure itself for that matter). i have some thoughts on how to handle collisions with stiff springs in my implicit solver, and i think its going to rock. time will tell though :).
#12 Members - Reputation: 179
Posted 04 May 2005 - 07:17 AM
Quote:
Original post by Sneftel
Both implicit and explicit Euler kind of suck for systems with lots of contact forces. If that describes your system, I'd suggest Verlet integration, which lends itself easily to contact forces and contact constraints.
verlet is explicit.
what do you think makes it special with regard to collision handling btw?
#13 Anonymous Poster_Anonymous Poster_* Guests - Reputation:
Posted 04 May 2005 - 07:24 AM
Though my practical experience with implicit vs. explicit solvers is somewhat limited, my comment was based on a personal experience. Several years ago I coded a CFD simulation based on the Euler model of fluid flow (nonlinear, compressible, rotational, but inviscid). The formulation was based on a finite difference discretization with upwind differencing (mixture of forward and backward steps depending on local flow conditions at a point). I ran the simulation for a range of between roughly 2500 and over 100000 degrees of freedom. The matrix solver was based on the multigrid technique, using Successive Over-Relaxation (SOR) at each level in the multigrid. The multigrid technique in theory can scale linearly with the number of unknowns, for elliptic problems, and in my case did scale just about linearly. The speed was many orders of magnitude faster than naive iterative methods. Explicit methods are not appropriate for solving Euler fluid flow, and so I didn't have one for comparison. (This discussion is getting me curious. That was 1996 or 1997. I'm going to dig that code out and see how fast it runs on my 3Ghz machine here now!)
Based on a little refresher, I've changed my position in general, and agree more with SpaceDude's comment.
Conjugate Gradient is a fast method for solving some systems. I'm less familiar with CG than with multigrid, though I believe some variations of CG can scale nearly linearly, for some types of problems. O(N2) I believe is worst case for CG. In the worse case, then, CG is far slower than explicit methods. In general, if CG scales as O(N1 + something) then it is true that CG will require several orders of magnitude more time, if N is large enough.
[Edited by - grhodes_at_work on May 4, 2005 4:24:39 PM]
Based on a little refresher, I've changed my position in general, and agree more with SpaceDude's comment.
Conjugate Gradient is a fast method for solving some systems. I'm less familiar with CG than with multigrid, though I believe some variations of CG can scale nearly linearly, for some types of problems. O(N2) I believe is worst case for CG. In the worse case, then, CG is far slower than explicit methods. In general, if CG scales as O(N1 + something) then it is true that CG will require several orders of magnitude more time, if N is large enough.
[Edited by - grhodes_at_work on May 4, 2005 4:24:39 PM]
#15 Members - Reputation: 807
Posted 04 May 2005 - 09:31 AM
Quote:
Original post by Eelco
good collision handling has always seemed impossible to me in an explicit sceme, since you simply never get close enough to the desired stiffness of the contacts (or the structure itself for that matter).
When using an explicit integrator, you can get perfectly rigid objects using impulses instead of forces for contacts (the only difference between impulse and force being timescale). Multiple contacts are easily handled by sequentially processing the contacts, and after each contact impulse, updating the momentum and velocity of the rigid body. A more accurate method requires contact point analysis and weighting, but isn't required for games.
Rigid constraints can also be handled with impulses, provided a small amount of relaxation is allowed. This results in slightly inexact solutions, matching the behavior of an implicit integrator.
Extremely stiff springs can also be handled with an explicit integrator if force/acceleration clamping is implemented. Again, this results in slight error in some cases, but probably similar to an implicit method. It's possible to model the springs for cars with extreme stiffness (matching an impulse), and it's completely stable.
In summary, an explicit integrator can be made very stable for the extreme conditions, and can also be symplectic (preserves geometric structure of motion, "area under curve", etc.), as well as energy accurate (does not significantly gain or loss energy). It's also relatively easy to tweak an explicit integrator, adding stability (and error) only where it's needed.
Implicit integrators tend to not be symplectic, lose energy, may have trouble modeling angular rotation for rigid bodies (precession is not correctly modeled), may require special approximations for acceleration (motion looks plausible, but not natural), can use a large amount of memory, and can be more difficult to tune. I have read recent papers on methods to try to improve on these issues, but have not yet seen a running implicit integrator that solves all of them. If an implicit integrator could be created that solves all of these problems, it would be the ultimate integrator.
For game applications, Symplectic Euler, or "Euler-Verlet" integration is the easiest, most accurate way to model motion.
#16 Anonymous Poster_Anonymous Poster_* Guests - Reputation:
Posted 04 May 2005 - 10:57 AM
Just for the record CG is not O(n2)
CG main driver is O(N), N passes each one 3 or 4 long scalar products, that made it O(N) however there is a Vector time matrix in the Main loop, so only in cases where the Matrix time vector is very sparse that can be implemented in linear time CG has O(N2) complexity.
It is my experience that Implicit method only leads to PDS Matrix when only lattices of springs are involve, for anything more complex that a spring system when the partial derivative can not be derive explicitly or have to be calculated by using the Chain Rule, the is not Guarantee that CG can by used to solve the problem.
Also for Dense problems CG in General is much slower that plain Gaussian.
This is only practical if only few passes are used in wich case the complexity is Quadratic Best case.
CG main driver is O(N), N passes each one 3 or 4 long scalar products, that made it O(N) however there is a Vector time matrix in the Main loop, so only in cases where the Matrix time vector is very sparse that can be implemented in linear time CG has O(N2) complexity.
It is my experience that Implicit method only leads to PDS Matrix when only lattices of springs are involve, for anything more complex that a spring system when the partial derivative can not be derive explicitly or have to be calculated by using the Chain Rule, the is not Guarantee that CG can by used to solve the problem.
Also for Dense problems CG in General is much slower that plain Gaussian.
This is only practical if only few passes are used in wich case the complexity is Quadratic Best case.
#17 Senior Moderators - Reputation: 1744
Posted 04 May 2005 - 09:22 PM
Quote:
Original post by Eelco Quote:
Original post by Sneftel
Both implicit and explicit Euler kind of suck for systems with lots of contact forces. If that describes your system, I'd suggest Verlet integration, which lends itself easily to contact forces and contact constraints.
verlet is explicit.
It's an explicit method. But it isn't explicit Euler (though, of course, it's closely related).
Quote:
what do you think makes it special with regard to collision handling btw?
Not collision handling (although it works fine for this); contact forces. Verlet is great for enforcing positional constraints without any oscillations, even damped ones, since it doesn't require you to manually propagate penalty forces into derivatives.
#18 Members - Reputation: 206
Posted 04 May 2005 - 10:11 PM
I might be wrong, but Verlet integration can be both explicit or implicit depending on how you define it:
X_n+1 = 2*X_n - X_n-1 + dt*dt*a_n'
if n' == n then its an explicit method
if n' == n+1 then its an implicit method
The simple difference between an explicit method and implicit method is:
To calculate some quantity at time step, n+1, explicitly ONLY quantities from time steps n, and less are needed. However, a (semi) implicit method uses quantities from time steps n+1 (and above) in the calculation.
In the implicit case you can only solve through either an iterative approach or as a set of simulatenous equations (i.e. Jacobi, Gauss-Siedel, SOR; as grhodes mentioned)
http://www.cs.umu.se/kurser/TDBD12/VT04/lectures/claude_lecture.pdf
X_n+1 = 2*X_n - X_n-1 + dt*dt*a_n'
if n' == n then its an explicit method
if n' == n+1 then its an implicit method
The simple difference between an explicit method and implicit method is:
To calculate some quantity at time step, n+1, explicitly ONLY quantities from time steps n, and less are needed. However, a (semi) implicit method uses quantities from time steps n+1 (and above) in the calculation.
In the implicit case you can only solve through either an iterative approach or as a set of simulatenous equations (i.e. Jacobi, Gauss-Siedel, SOR; as grhodes mentioned)
http://www.cs.umu.se/kurser/TDBD12/VT04/lectures/claude_lecture.pdf
#19 Anonymous Poster_Anonymous Poster_* Guests - Reputation:
Posted 05 May 2005 - 03:51 AM
You can not just extrapolate the value at the step t + 1 and say that verlet can be implicit, that does not make any sense.
It is true implicit methods used the value of the time t +1 but the quantity is predicted by evaluating the function derivative at time t + 1 and using it at time t to extrapolate the value at time t + 1, that is a very big difference with the explicit method in which you advance the function and then do some averaging of the values and some point in the integration interval to get the average derivative at time t (verlet, euler, midpoint, RH, predictor correction, etc)
Calculating the derivative is what makes implicit methods complex, because it is absolutely necessary and mandatory to have a continue and derivable implicit function that relates the dependent variable to the independent variables, and this is not always possible. (hence the name implicit integration)
Implicit integrators are only good for implementing lattices of particles connected by springs and maybe dampers (even thought damper made the jacobian matrices intractable) this is because the function between any two particles is
F = -ks *(x1 – x2) + kc * (v1 – v2)
which is easy to get the derivatives an partial derivatives for the formulationg of the jacobian matrix.
When things like contacts and friction are introduced, then there is not way to plug that in to the engine. This is because contacts and in general unilateral forces belong to a familly of constraints called Non-Holonimic constraints which is a way to say they can not be espressed as a continue function like C = f(x0, x1, x2, … t)
Also many people have the ideas that some how implicit methods are the correct or exact methods and explicit are the wrong methods. And this is wrong, implicit methods are as equally bad as explicit ones. They are good for simulating spring systems because the have the ability to extract so much energy from the system that system converge to a equilibrium position, but when the same techniques if used on different context, this feature lead to incredible dampening annoying effects. These method produce simulations that are visually pleasant but by not mean correct.
Currentely the only things implicit methods are good for is writing turn papers, research, and some sort of cloth and soft body simulations. But they can not be extended beyond that area or at least no body had come up with a method beyond springs suitable for the generalized dynamics formulation.
In that regard I agree with John Schulth, however I do not think that or is so easy to stabilized naïve explicit integration methods.
On the contrary is quite hard and expensive when the problem at hand is something more than and effect for a video game.
Finally I hear the turn semi-implicit integration, which I have no idea what it means, as far as I know there are only two ways for numerical integration of differential equation, explicit and implicit which are clearly defined by the way the derivative of the equation is used, at time t, or at time t + 1, but I hear new turn been establish with not theoretical foundation whosoever. I could be wrong, and maybe some body can enlighten me, but as far as I know there is not such thing as semi-implicit numerical integration.
It is true implicit methods used the value of the time t +1 but the quantity is predicted by evaluating the function derivative at time t + 1 and using it at time t to extrapolate the value at time t + 1, that is a very big difference with the explicit method in which you advance the function and then do some averaging of the values and some point in the integration interval to get the average derivative at time t (verlet, euler, midpoint, RH, predictor correction, etc)
Calculating the derivative is what makes implicit methods complex, because it is absolutely necessary and mandatory to have a continue and derivable implicit function that relates the dependent variable to the independent variables, and this is not always possible. (hence the name implicit integration)
Implicit integrators are only good for implementing lattices of particles connected by springs and maybe dampers (even thought damper made the jacobian matrices intractable) this is because the function between any two particles is
F = -ks *(x1 – x2) + kc * (v1 – v2)
which is easy to get the derivatives an partial derivatives for the formulationg of the jacobian matrix.
When things like contacts and friction are introduced, then there is not way to plug that in to the engine. This is because contacts and in general unilateral forces belong to a familly of constraints called Non-Holonimic constraints which is a way to say they can not be espressed as a continue function like C = f(x0, x1, x2, … t)
Also many people have the ideas that some how implicit methods are the correct or exact methods and explicit are the wrong methods. And this is wrong, implicit methods are as equally bad as explicit ones. They are good for simulating spring systems because the have the ability to extract so much energy from the system that system converge to a equilibrium position, but when the same techniques if used on different context, this feature lead to incredible dampening annoying effects. These method produce simulations that are visually pleasant but by not mean correct.
Currentely the only things implicit methods are good for is writing turn papers, research, and some sort of cloth and soft body simulations. But they can not be extended beyond that area or at least no body had come up with a method beyond springs suitable for the generalized dynamics formulation.
In that regard I agree with John Schulth, however I do not think that or is so easy to stabilized naïve explicit integration methods.
On the contrary is quite hard and expensive when the problem at hand is something more than and effect for a video game.
Finally I hear the turn semi-implicit integration, which I have no idea what it means, as far as I know there are only two ways for numerical integration of differential equation, explicit and implicit which are clearly defined by the way the derivative of the equation is used, at time t, or at time t + 1, but I hear new turn been establish with not theoretical foundation whosoever. I could be wrong, and maybe some body can enlighten me, but as far as I know there is not such thing as semi-implicit numerical integration.
#20 Members - Reputation: 206
Posted 05 May 2005 - 04:59 AM
Quote:
Finally I hear the turn semi-implicit integration, which I have no idea what it means, as far as I know there are only two ways for numerical integration of differential equation, explicit and implicit
An example of a true semi-implicit method is the "hop hotch" method for diffusion. Basically, you use an explicit method to calculate the effect of diffusion at every ODD position for time step n+1. Then at all the EVEN positions (at time step n+1) you use the neighbouring elements and the ODD elements at time step n.
I know that explanantion might not make immediate sense, but basically every ODD element has been calculated explicitly and every EVEN element has been calculated implicitly. As you advance in time you swap between ODD and EVEN, giving you a semi-implicit method which is highly stable
