Thread: Re: [Algorithms] Fixed time step loop with varying framerate
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Manolache A. <pro...@ya...> - 2009-03-18 04:52:56
|
Sorry for the typo, Line 9 should be:
9. accumulator -= fixedDt.
in the simulation it's written like above, otherwise i would not get numUpdatesThisFrame greater than 1.
Sorry for the silly mistake :D
--- On Wed, 3/18/09, Andrew Ellem <an...@ar...> wrote:
From: Andrew Ellem <an...@ar...>
Subject: Re: [Algorithms] Fixed time step loop with varying framerate
To: pro...@ya...
Date: Wednesday, March 18, 2009, 6:43 AM
Is this the actual code you're running?
This loop here looks pretty broken to me:
7. while (accumulator >= fixedDt)
{
8. UpdateSimulation(fixedDt);
9. accumulator -= accumulator; 10. numUpdatesThisFrame ++;
}
Shouldn't it be
accumulator -= fixedDt;
I don't understand how numUpdatesThisFrame isn't always 1.
> I've stumbled on a problem these days while programming a small
simulation. I've read a few articles with a main title of: "Fix
you're time step" and concluded on the following loop:
> 0. numTotalUpdates = 0;
> 1. fixedDt = 1.0f / 400.0f; // how small is enough?
> 2. while (IsRunning())
> {
> 3. DispatchEvents();
> 4. static float accumulator = 0.0f;
> 5. numUpdatesThisFrame = 0;
> 6. accumulator += GetFrameTime() ; // time since last update
> 7. while (accumulator >= fixedDt)
> {
> 8. UpdateSimulation(fixedDt);
> 9. accumulator -= accumulator; 10. numUpdatesThisFrame
++; }
> 11. numTotalUpdates++;
> 12. renderInterpolator = accumulator / fixedDt; // safe to say it's
in 0..1
> 13. Render(renderInterpolator);
> }
> As far as i know this is physics engine friendly main loop because
physics engine deal great with small fixed time steps when approximating
integration.
> As i was saying i was running a simple simulation of a circle that was
hitting obstacles and was being reflected as expected. Actually there was more
going on, on the screen, but the main idea of the simulation is of a circle in a
2D environment colliding in a breakout game fashion.
> I repeatedly run the simulation with VSync on and observed an annoying
stuttering/choppy movement of the circle. The stuttering is almost random like.
After some profiling i found out that numUpdatesThisFrame was varying kind of
weird: it was growing from 6,7 to 15 or even 24. I changed this line to this
line
> 6'. accumulator = some_constant;
> and the ran the simulation again with VSync on. The stuttering was gone
and since the value of some_constant was tweaked for my processor speed the
motion was neither to slow and neither two fast.
> So something was happening that caused big times between frames which
implied an unnaturally big numUpdatesThisFrame value. The framerate was very
high though, without VSync on i was getting a few thousands frames per second so
i thought to myself that bothering with why does sometime the time beween frames
was unnaturally big, was not the way to solve the problem.
> I thought the way to tackle this issue is to compensate for the random
big times between is to write additional code in the main loop. I never dealt
with the problem of fixed time steps and varying framerate and i can't
really know how to start.
> One way i thought was to first detect when a big shift occurs and then
try to correct it.
> The numbers of updates per frame form a series of intger numbers. The
series is unlikely to be convergent in the pure mathematical point of view but i
think it's intuitive to observe that its values will get closer to some
fixed values. I can calculate an approximation of this value by an arithemetic
mean like so:
> approximateConvergenceValue = Sum(sequence[i]) / numTotalUpdates,
1<=i<=numTotalUpdates;
> A better approximation of this value would be to use a quadratic mean
like so:
> approximateConvergenceValue = Square_Root(Sum(sequence[i]*sequence[i]) /
numTotalUpdates), 1<=i<=numTotalUpdates;
> This is pretty close to the most frequent values of numUpdatesThisFrame
so i guess it's a good approximation. I'm puzzled when applying this
detection to correct the framerate and also keep approximateConvergenceValue to
a good approximation. The simulation would ideally self adapt to work the same
using this calculation(minimizing the effect seen on screen as a result of the
adaption)
> So how does one usually deal with fixed time step loops and varying frame
rate?
>
>
> ------------------------------------------------------------------------
>
>
------------------------------------------------------------------------------
> Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are
> powering Web 2.0 with engaging, cross-platform capabilities. Quickly and
> easily build your RIAs with Flex Builder, the Eclipse(TM)based development
> software that enables intelligent coding and step-through debugging.
> Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
|
|
From: Manolache A. <pro...@ya...> - 2009-03-18 09:22:08
|
Yes i do. I've been made aware of this problem and proposed this code to test if something's wrong with the QPC function (note that i'm using sfml for cross platform dev which uses the high performance timer on windows if available):
{
sf::Clock c;
while (1)
{
float a = 0.0f;
DWORD start = timeGetTime();
c.Reset();
for (int g=0; g<100000; g++)
{
float d = sqrtf(g);
a += d*d*d;
}
float dur = c.GetElapsedTime();
float dur2 = (float)(timeGetTime()-start)/1000.0f;
if (abs(dur-dur2)>.01)
{
char mess[256];
sprintf(mess, "detected anomalous time error greater than .01 sec");
MessageBox(NULL, mess, mess, MB_OK);
}
}
}
Ran the code for a few minutes and there was no popup warning. Guess the timer's fine.
Also this code demonstrates that indeed i have a high performance timer on windows
{
sf::Clock c;
float a = 0.0f;
c.Reset();
for (int g=0; g<10000000; g++)
{
float d = sqrtf(g);
a += d*d*d;
}
char mess[256];
sprintf(mess, "time=%f a=%f", c.GetElapsedTime(),a);
MessageBox(NULL, mess, mess, MB_OK);
}
The message box says: time=0.269663 a=1274143319414508570.000000 (hope i did copy correctly in case someone
tries the code :D )
Moreover i also tested the application on a dual core macbook with an integrated graphics card and the stuttering is still there. I noticed that if i replace this line
6. accumulator += GetFrameTime() ; // time since last
update
with this line
6''. accumulator = myProcessorSpecificConstant ;
where myProcessorSpecificConstant is chosen apropriate so that the simulation won't go too fast or too slow than the choppiness/stuttering is completely gone.
I also observed that the when numUpdatesThisFrame is almost constant(not to different from frame to frame) then there is no stuttering.
--- On Wed, 3/18/09, David Pangerl <em...@gm...> wrote:
From: David Pangerl <em...@gm...>
Subject: Re: [Algorithms] Fixed time step loop with varying framerate
To: pro...@ya..., "Game Development Algorithms" <gda...@li...>
Date: Wednesday, March 18, 2009, 7:42 AM
Hi Adrian,
Do you have a multi core processor? There was a discussion a while ago
on Algorithms about incorrect time reporting of QPC function on multi
core processors.
Cheers,
DAVID
David Pangerl, CEO
e-mail da...@Ac...
mobile +386 31 664 297
address ActaLogic
Tehnoloski
park 21
1000
Ljubljana
Slovenia
Europe
Manolache Adrian wrote:
I've stumbled on a problem these days while programming a
small simulation. I've read a few articles with a main title of: "Fix
you're time step" and concluded on the following loop:
0. numTotalUpdates = 0;
1. fixedDt = 1.0f / 400.0f; // how small is enough?
2. while (IsRunning())
{
3. DispatchEvents();
4. static float accumulator = 0.0f;
5. numUpdatesThisFrame = 0;
6. accumulator += GetFrameTime() ; // time since last
update
7. while (accumulator >= fixedDt)
{
8. UpdateSimulation(fixedDt);
9. accumulator -= accumulator;
10. numUpdatesThisFrame ++;
}
11. numTotalUpdates++;
12. renderInterpolator = accumulator / fixedDt; // safe
to say it's in 0..1
13. Render(renderInterpolator);
}
As far as i know this is physics engine friendly main loop
because physics engine deal great with small fixed time steps when
approximating integration.
As i was saying i was running a simple simulation of
a circle that was hitting obstacles and was being reflected as
expected. Actually there was more going on, on the screen, but the main
idea of the simulation is of a circle in a 2D environment colliding in
a breakout game fashion.
I repeatedly run the simulation with VSync on and observed
an annoying stuttering/choppy movement of the circle. The stuttering is
almost random like. After some profiling i found out that
numUpdatesThisFrame was varying kind of weird: it was growing from 6,7
to 15 or even 24. I changed this line to this line
6'. accumulator = some_constant;
and the ran the simulation again with VSync on. The
stuttering was gone and since the value of some_constant was tweaked
for my processor speed the motion was neither to slow and neither two
fast.
So something was happening that caused big times between
frames which implied an unnaturally big numUpdatesThisFrame value. The
framerate was very high though, without VSync on i was getting a few
thousands frames per second so i thought to myself that bothering with
why does sometime the time beween frames was unnaturally big, was not
the way to solve the problem.
I thought the way to tackle this issue is to compensate
for the random big times between is to write additional code in the
main loop. I never dealt with the problem of fixed time steps and
varying framerate and i can't really know how to start.
One way i thought was to first detect when a big shift
occurs and then try to correct it.
The numbers of updates per frame form a series of
intger numbers. The series is unlikely to be convergent in the pure
mathematical point of view but i think it's intuitive to observe that
its values will get closer to some fixed values. I can calculate an
approximation of this value by an arithemetic mean like so:
approximateConvergenceValue = Sum(sequence[i]) /
numTotalUpdates, 1<=i<=numTotalUpdates;
A better approximation of this value would be to use a
quadratic mean like so:
approximateConvergenceValue =
Square_Root(Sum(sequence[i]*sequence[i]) / numTotalUpdates),
1<=i<=numTotalUpdates;
This is pretty close to the most frequent values of
numUpdatesThisFrame so i guess it's a good approximation. I'm puzzled
when applying this detection to correct the framerate and also keep
approximateConvergenceValue to a good approximation. The simulation
would ideally self adapt to work the same using this
calculation(minimizing the effect seen on screen as a result of the
adaption)
So how does one usually deal with fixed time step loops
and varying frame rate?
------------------------------------------------------------------------------
Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are
powering Web 2.0 with engaging, cross-platform capabilities. Quickly and
easily build your RIAs with Flex Builder, the Eclipse(TM)based development
software that enables intelligent coding and step-through debugging.
Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
|
|
From: Jason H. <jas...@di...> - 2009-03-18 06:22:25
|
Varying framerates is always a problem with a fixed update loop. If you
have no way to catch up, you eventually will get into a death spiral
where one slow frame can cascade to the next, and to the next, etc. You
have to guarantee that nothing inside (or outside) your update ever
approaches the length of time it is simulating. When you run at 400hz,
you have to have pretty small amounts of work to do, and your fixed
overhead becomes a larger percentage of the time spent (loop overhead,
etc). If your main thread is waiting on vsync and performing simulation
steps, it's possible you just missed a vsync and just began waiting for
the next one, 1/60th of a second wasted. That's a lot of simulation
steps you have to make up for.
Perhaps you can try implicit integrators so your timesteps can be
larger? Or limit the number of simulation steps you allow per update,
which breaks the death spiral. Or, divide the actual time between
frames by a fixed number of steps so you get several timesteps in a row
at a fixed dt, but not necessarily the same dt every frame.
There are many other refinements. But rest assured you're not the first
person to run into this problem. :-)
JH
Manolache Adrian wrote:
> Sorry for the typo, Line 9 should be:
> 9. accumulator -= fixedDt.
> in the simulation it's written like above, otherwise i would not get
> numUpdatesThisFrame greater than 1.
> Sorry for the silly mistake :D
>
> --- On *Wed, 3/18/09, Andrew Ellem /<an...@ar...>/* wrote:
>
> From: Andrew Ellem <an...@ar...>
> Subject: Re: [Algorithms] Fixed time step loop with varying framerate
> To: pro...@ya...
> Date: Wednesday, March 18, 2009, 6:43 AM
>
> Is this the actual code you're running?
>
> This loop here looks pretty broken to me:
>
> 7. while (accumulator >= fixedDt)
> {
> 8. UpdateSimulation(fixedDt);
> 9. accumulator -= accumulator; 10. numUpdatesThisFrame ++;
> }
>
> Shouldn't it be
> accumulator -= fixedDt;
>
> I don't understand how numUpdatesThisFrame isn't always 1.
>
>
> > I've stumbled on a problem these days while programming a small
> simulation. I've read a few articles with a main title of: "Fix
> you're time step" and concluded on the following loop:
> > 0. numTotalUpdates = 0;
> > 1. fixedDt = 1.0f / 400.0f; // how small is enough?
> > 2. while (IsRunning())
> > {
> > 3. DispatchEvents();
> > 4. static float accumulator = 0.0f;
> > 5. numUpdatesThisFrame = 0;
> > 6. accumulator += GetFrameTime() ; // time since last update
> > 7. while (accumulator >= fixedDt)
> > {
> > 8. UpdateSimulation(fixedDt);
> > 9. accumulator -= accumulator; 10. numUpdatesThisFrame
> ++; }
> > 11. numTotalUpdates++;
> > 12. renderInterpolator = accumulator / fixedDt; // safe to say it's
> in 0..1
> > 13. Render(renderInterpolator);
> > }
> > As far as i know this is physics engine friendly main loop because
> physics engine deal great with small fixed time steps when approximating
> integration.
> > As i was saying i was running a simple simulation of a circle that was
> hitting obstacles and was being reflected as expected. Actually there was more
> going on, on the screen, but the main idea of the simulation is of a circle in a
> 2D environment colliding in a breakout game fashion.
> > I repeatedly run the simulation with VSync on and observed an annoying
> stuttering/choppy movement of the circle. The stuttering is almost random like.
> After some profiling i found out that numUpdatesThisFrame was varying kind of
> weird: it was growing from 6,7 to 15 or even 24. I changed this line to this
> line
> > 6'. accumulator = some_constant;
> > and the ran the simulation again with VSync on. The stuttering was gone
> and since the value of some_constant was tweaked for my processor speed the
> motion was neither to slow and neither two fast.
> > So something was happening that caused big times between frames which
> implied an unnaturally big numUpdatesThisFrame value. The framerate was very
> high though, without VSync on i was getting a few thousands frames per second so
> i thought to myself that bothering with why does sometime the time beween frames
> was unnaturally big, was not the way to solve the problem.
> > I thought the way to tackle this issue is to compensate for the random
> big times between is to write additional code in the main loop. I never dealt
> with the problem of fixed time steps and varying framerate and i can't
> really know how to start.
> > One way i thought was to first detect when a big shift occurs and then
> try to correct it.
> > The numbers of updates per frame form a series of intger numbers. The
> series is unlikely to be convergent in the pure mathematical point of view but i
> think it's intuitive to observe that its values will get closer to some
> fixed values. I can calculate an approximation of this value by an arithemetic
> mean like so:
> > approximateConvergenceValue = Sum(sequence[i]) / numTotalUpdates,
> 1<=i<=numTotalUpdates;
> > A better approximation of this value would be to use a quadratic mean
> like so:
> > approximateConvergenceValue = Square_Root(Sum(sequence[i]*sequence[i]) /
> numTotalUpdates), 1<=i<=numTotalUpdates;
> > This is pretty close to the most frequent values of numUpdatesThisFrame
> so i guess it's a good approximation. I'm puzzled when applying this
> detection to correct the framerate and also keep approximateConvergenceValue to
> a good approximation. The simulation would ideally self adapt to work the same
> using this calculation(minimizing the effect seen on screen as a result of the
> adaption)
> > So how does one usually deal with fixed time step loops and varying frame
> rate?
> >
> >
> > ------------------------------------------------------------------------
> >
> >
> ------------------------------------------------------------------------------
> > Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are
> > powering Web 2.0 with engaging, cross-platform capabilities. Quickly and
> > easily build your RIAs with Flex Builder, the Eclipse(TM)based development
> > software that enables intelligent coding and step-through debugging.
> > Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com
> > ------------------------------------------------------------------------
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
>
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------------
> Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are
> powering Web 2.0 with engaging, cross-platform capabilities. Quickly and
> easily build your RIAs with Flex Builder, the Eclipse(TM)based development
> software that enables intelligent coding and step-through debugging.
> Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
|
Thanks for helping keep SourceForge clean.
X