So, playing with particles recently, I noticed a small* problem.

"Fixing" your timestep, such that it is always processed in increments of some
arbitrary value, greatly increases the quality of your simulation.  When dt
seconds have passed, and your timestep is the arbitrary value ts, then

while (dt > ts)
  step(ts)
  dt -= ts

The fun part comes up when the time required to do a simulation step is greater
than the time stepped (ts).  This situation results in a negative feedback
loop; the greater dt is, the more steps you must take, meaning dt for the next
frame will be even greater, meaning even more steps must be taken, meaning...

What this means, in practice, is that as the number of particles increase you
will see an expected decrease in framerate until you cross the line where you
enter this loop.  After that, each frame takes longer than the previous.  In
the simulation I've been playing with recently, this means that my framerate
will drop quite smoothly from 75 to 20, and then suddenly plummet down to 5,
then 2, then...

Naturally, this threw me for a loop until I figured it out :)

Fortunately, there's a simple solution for this.  While "fixing" your timestep
provides a valuable increase in the quality of your simulation, the solution is
to simply make a step using whatever dt you have.  That is,

if (dt > ts*5)
  step(dt)
else
  while (dt > ts)
    step(ts)
    dt -= ts

The 5 above was chosen at random, and can be modified to suit individual
simulations.

Anyway, since I find negative feedback loops in performance situations to be
interesting problems to solve, I thought others here might also be interested
in hearing about this.

*For some random definition of "small".

Post a reply to this message

"Chambers" <bdc### [at] yahoocom> wrote:
> So, playing with particles recently, I noticed a small* problem.
>
> "Fixing" your timestep, such that it is always processed in increments of some
> arbitrary value, greatly increases the quality of your simulation.  When dt
> seconds have passed, and your timestep is the arbitrary value ts, then
>
> while (dt > ts)
>   step(ts)
>   dt -= ts
>
> The fun part comes up when the time required to do a simulation step is greater
> than the time stepped (ts).  This situation results in a negative feedback
> loop; the greater dt is, the more steps you must take, meaning dt for the next
> frame will be even greater, meaning even more steps must be taken, meaning...

Isn't that more of a positive* feedback loop, where a perturbation reinforces
itself?

I didn't figure out the problem until the next paragraph until I figured out
we're talking real-time.  Have you thought about adaptive timestepping to
alleviate the problem of selecting an appropriate timestep?  Do an RK4 step and
an Euler step with the same initial conditions.  Compare the results, perhaps
excluding particles which have just collided.  Just (x_rk4 - x_euler) / dx.  If
the relative error is larger than some tolerance, subdivide the timestep.  If
it's too small, then double it.  Try it every ten steps, for example, and make
sure the timestep isn't much smaller than what you could be using.

- Ricky

*for some definition of positive.

Post a reply to this message

"triple_r" <nomail@nomail> wrote:
> Isn't that more of a positive* feedback loop, where a perturbation reinforces
> itself?

Possibly; in the contexts I've seen it used, a negative effect reinforcing
itself has been referred to as a negative feedback loop.  However, calling it a
positive feedback loop is, unintuitively enough, logical.

> I didn't figure out the problem until the next paragraph until I figured out
> we're talking real-time.  Have you thought about adaptive timestepping to
> alleviate the problem of selecting an appropriate timestep?

The funny thing is, using a fixed timestep is supposed to "fix" the problem of a
dynamic timestep :)  The whole thing about a dynamic timestep is that the
results of your simulation depend on your framerate; using a fixed timestep
like this means that you'll get smooth results, no matter the ts value.

....Chambers

Post a reply to this message

On Mon, 14 Apr 2008 16:35:24 EDT, "Chambers" <bdc### [at] yahoocom>
wrote:

>"triple_r" <nomail@nomail> wrote:
>> Isn't that more of a positive* feedback loop, where a perturbation reinforces
>> itself?
>
>Possibly; in the contexts I've seen it used, a negative effect reinforcing
>itself has been referred to as a negative feedback loop.  However, calling it a
>positive feedback loop is, unintuitively enough, logical.

It is easy if you think of the changes. A positive feedback adds to
the change and that is good for a detector. Negative feedback
subtracts from the change which is good for an amplifier. You have
heard socio-babble :)
-- 

Regards
     Stephen

Post a reply to this message

"Chambers" <bdc### [at] yahoocom> wrote:
> "triple_r" <nomail@nomail> wrote:
> > Isn't that more of a positive* feedback loop, where a perturbation reinforces
> > itself?
>
> Possibly; in the contexts I've seen it used, a negative effect reinforcing
> itself has been referred to as a negative feedback loop.  However, calling it a
> positive feedback loop is, unintuitively enough, logical.

Forgive me--I wasn't being facetious when I said it depends on your definition
of positive.  Sounds like it's just a matter of convention in all kinds of
fields where it's used.  My undergraduate
yeah-I-took-a-course-in-that-so-I-must-be-an-expert experience is that you call
anything destabilizing a positive feedback loop whether that makes any sense or
not...  But the whole course was really just one specific case where angles are
defined so that that's always the case...

> The funny thing is, using a fixed timestep is supposed to "fix" the problem of a
> dynamic timestep :)

As long as you're taking the largest time step possible.  If not, then dynamic
timestepping should catch that and increase the step, allowing even fewer
iterations.  I guess you're right though.  It may make more sense here to
sacrifice some accuracy rather than framerate.  Just as long as you don't leave
the stability domain.

 - Ricky

Post a reply to this message

Chambers wrote:
> So, playing with particles recently, I noticed a small* problem.
> 
> "Fixing" your timestep, such that it is always processed in increments of some
> arbitrary value, greatly increases the quality of your simulation.  When dt
> seconds have passed, and your timestep is the arbitrary value ts, then
> 
> while (dt > ts)
>   step(ts)
>   dt -= ts
> 
> The fun part comes up when the time required to do a simulation step is greater
> than the time stepped (ts).

Only if you want real-time performance.  For us animators, that's not an 
issue.

If you have access to system timekeeping, simply measure the start and 
end times at the beginning and end of each loop, and advance the time 
clock by that value at the end of each pass.

Regards,
John

Post a reply to this message

> if (dt > ts*5)
>  step(dt)
> else
>  while (dt > ts)
>    step(ts)
>    dt -= ts

Won't this have the effect of the framerate dropping steadily until frames 
get too long, at which point we drop all the extra work we've accumulated 
and the framerate snaps back to decent and starts dropping again? This might 
be annoying.

A different possibility would be to cap the number of physics timesteps we 
take in any frame:

if ( dt > ts * 5 )
  for ( i = 1 to 5 )
    step( dt / 5 )
else
  while (dt > ts)
    step(ts)
    dt -= ts

With this solution, if the framerate drops it will eventually settle 
somewhere (depending on the number you use instead of '5') and remain 
constant, because we'll be doing the same amount of work every frame.

Of course, if you see the framerate dropping for this reason, the *best* 
solution is to admit that you're doing more work than you can handle in the 
time you have, and either increase the timestep, reduce the number of 
objects being simulated, or optimize physics engine. =) (It doesn't hurt to 
have a fallback, of course.)

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

> Fortunately, there's a simple solution for this.  While "fixing" your 
> timestep
> provides a valuable increase in the quality of your simulation, the 
> solution is
> to simply make a step using whatever dt you have.  That is,
>
> if (dt > ts*5)
>  step(dt)
> else
>  while (dt > ts)
>    step(ts)
>    dt -= ts
>
> The 5 above was chosen at random, and can be modified to suit individual
> simulations.

That's a bad idea, what happens when Invisible comes along with his 10 year 
old PC and your code starts doing time-steps of 10*ts or even 20*ts?  Who 
knows?

Far better to *always* do step(ts), you can absolutely guarantee that on 
every single machine the results will be the same then.  And if it takes 
Invisible's PC 10*ts to do a ts time-step, then so be it and just let the 
simulation run at 1/10th speed, it can't be improved.  It's a much better 
way to peform on slow PCs rather than having unknown things happen with huge 
time steps.

Post a reply to this message

Slime wrote:
> Of course, if you see the framerate dropping for this reason, the *best* 
> solution is to admit that you're doing more work than you can handle in the 
> time you have, and either increase the timestep, reduce the number of 
> objects being simulated, or optimize physics engine. =) (It doesn't hurt to 
> have a fallback, of course.)

Unfortunately, we always seem to come back to a dynamic timestep.  I 
suppose the "best" solution would be to have a range of timesteps that 
are acceptable, and to keep it as low as possible, but never out of this 
range.

-- 
...Ben Chambers
www.pacificwebguy.com

Post a reply to this message

Chambers <ben### [at] pacificwebguycom> wrote:
> Unfortunately, we always seem to come back to a dynamic timestep.  I
> suppose the "best" solution would be to have a range of timesteps that
> are acceptable, and to keep it as low as possible, but never out of this
> range.

Found it! Try:

http://www.gaffer.org/game-physics/fix-your-timestep

I found this article very useful a while ago when I was messing around with toy
spring-mass simulations.

Tom

Post a reply to this message