Hello
I’m newbie in collision detection and I want to get deep understanding of this issue
I’m dealing with cloth simulation and trying to develop collision detection engine based on the work of SAI-KEUNG WONG “High Performance Virtual Clothing Dynamics”.
In this thesis Wong constructs CCD system. In order to calculate time of impact between vertex and triangle he calculates the moment when 4 points will became coplanar. (The same is done in Bullet and may other publications) . Vertex positions are updated according with formula Xi = Xi + Vi * dt. .These calculations are standard in collision detection literature. My question is following:
Why nobody accounts for force term F/m * dt *dt /2 ? In some cases external forces may have significant impact on positions of vertices.
Updating vertex positions
-
bone
- Posts: 231
- Joined: Tue Feb 20, 2007 4:56 pm
Re: Updating vertex positions
It depends on the type of integration used for the motion.
What you are describing is part of what I've seen called the "parabolic" integrator. It's accurate when the forces are constant for the entire timestep. The problem is that it is fairly unstable when simulating springs and dampers (which is a pretty common issue) because the forces change constantly based on the position and velocity of the bodies.
The games community typically uses the symplectic Euler (a.k.a. semi-implicit Euler) integration technique for motion:
v = v + ( t * f / m )
x = x + ( t * v )
This is much more stable, fairly accurate in terms of global error I understand, and very cheap to compute (exactly as cheap as the relatively horrible explicit Euler method where you do the position integration *before* the velocity integration).
There are many other integrators, and it depends on your application which one you use, but you have to understand the issues behind the choice if you're going to go with something other than symplectic Euler.
What you are describing is part of what I've seen called the "parabolic" integrator. It's accurate when the forces are constant for the entire timestep. The problem is that it is fairly unstable when simulating springs and dampers (which is a pretty common issue) because the forces change constantly based on the position and velocity of the bodies.
The games community typically uses the symplectic Euler (a.k.a. semi-implicit Euler) integration technique for motion:
v = v + ( t * f / m )
x = x + ( t * v )
This is much more stable, fairly accurate in terms of global error I understand, and very cheap to compute (exactly as cheap as the relatively horrible explicit Euler method where you do the position integration *before* the velocity integration).
There are many other integrators, and it depends on your application which one you use, but you have to understand the issues behind the choice if you're going to go with something other than symplectic Euler.
-
Ilyas
- Posts: 3
- Joined: Thu Oct 18, 2007 8:36 am
Re: Updating vertex positions
First of all, thank You for Your answer.
May be I do not properly formulate my question, or I do not understand Your answer
1) I’m using implicit Euler scheme, which is unconditionally stable.
2) In CCD I need to determine time of impact(TOI) in order to set proper collision response afterwards.
3) I estimate time TOI for vertex triangle according to standard procedure which is described in great number of articles and thesis on cloth simulation.
They calculate the moment when four points – vertex and 3 vertices of triangle will became coplanar and this time is determined as TOI
In this procedure the next coordinate of vertex is always extrapolated with formula
x1 = x0 + v0*dt
None of references uses more accurate formula
x1 = x0 + v * dt + f/m * dt * dt/2
In my calculations I see that external force f is essential
My question is: Why external force term f/m * dt *dt /2 is ignored in calculations ?
This is leading to serious inaccuracies in TOI
How accurate is CCD in comparison to approximate (and much more simple) schemes in calculation of TOI .
May be I do not properly formulate my question, or I do not understand Your answer
1) I’m using implicit Euler scheme, which is unconditionally stable.
2) In CCD I need to determine time of impact(TOI) in order to set proper collision response afterwards.
3) I estimate time TOI for vertex triangle according to standard procedure which is described in great number of articles and thesis on cloth simulation.
They calculate the moment when four points – vertex and 3 vertices of triangle will became coplanar and this time is determined as TOI
In this procedure the next coordinate of vertex is always extrapolated with formula
x1 = x0 + v0*dt
None of references uses more accurate formula
x1 = x0 + v * dt + f/m * dt * dt/2
In my calculations I see that external force f is essential
My question is: Why external force term f/m * dt *dt /2 is ignored in calculations ?
This is leading to serious inaccuracies in TOI
How accurate is CCD in comparison to approximate (and much more simple) schemes in calculation of TOI .
-
bone
- Posts: 231
- Joined: Tue Feb 20, 2007 4:56 pm
Re: Updating vertex positions
OK, I'm not a good person to answer questions about TOI and CCD, however I'll make a comment or two nonetheless:
Correct me if I'm wrong, but Implicit Euler typically uses an estimate of the force at the next timestep to calculate the next velocity, and then that updated velocity is used to update the position.
In other words, the velocity used to integrate the position is constant. The position change seems linear to me, not quadratic like it would be if one used a parabolic integrator. Perhaps your TOI calculation is using the current velocity rather than the next velocity as your integrator will be doing? In other words, x1 = x0 + v1*dt.
Have you tried this? Or have you tried your equation including the forces? Are they any more accurate?
Correct me if I'm wrong, but Implicit Euler typically uses an estimate of the force at the next timestep to calculate the next velocity, and then that updated velocity is used to update the position.
In other words, the velocity used to integrate the position is constant. The position change seems linear to me, not quadratic like it would be if one used a parabolic integrator. Perhaps your TOI calculation is using the current velocity rather than the next velocity as your integrator will be doing? In other words, x1 = x0 + v1*dt.
Have you tried this? Or have you tried your equation including the forces? Are they any more accurate?
-
Ilyas
- Posts: 3
- Joined: Thu Oct 18, 2007 8:36 am
Re: Updating vertex positions
You are right. In order to be consistent with numerical accuracy of Euler scheme
one need to use piecewise constant velocity.
That means that ignoring force we simply try to be consistent with numerical accuracy O(dt) of Euler integrator .
For now I’m using approximate collision detection scheme without CCD. In this case my results are simply bad without force term. I intend to utilize CCD and hope to get better results for simulator.
Thank You for helpful discussion
one need to use piecewise constant velocity.
That means that ignoring force we simply try to be consistent with numerical accuracy O(dt) of Euler integrator .
For now I’m using approximate collision detection scheme without CCD. In this case my results are simply bad without force term. I intend to utilize CCD and hope to get better results for simulator.
Thank You for helpful discussion