hello everybody, this new algorithm can fix quite a few problems, some that you knew about and some that you never thought were possible... this is so unbelievably important, because, this is one function that you will be calling the most in your entire real-time animation application / game ..quite literary - on every single STEP on the way ..and sometimes even more than once //--------------------------------------------------------- nVidia PhysX Tips: # Trade off fixed timesteps: * A lot of substeps: physics can be the bottleneck * Few substeps: moon gravity effects //--------------------------------------------------------- it practically solves both problems related to subSteps/maxSubSteps, simply because it does not introduce any max number of anything ..there is no need to guess such thing at the design time, we can always measure the time and act accordingly in a real-time ready? lets go.. lets define UNDERSAMPLING, whatever that word really means, in this story we will (re)define it like this: # simFixedStep (fixed simulation time step) # deltaTime (time used to render last frame) eg. A) slow computer + max. game settings + complex scene geometry + many moving objects = UNDERSAMPLING, practically it means this: --------------------------------- deltaTime > simFixedStep --------------------------------- ..say, real-time measurement shows less than 60FPS and our constant, built-in simFixedStep= 1/60 seconds ..where expected result is to keep AVERAGE simulation frequency at steady, fixed rate regardless of 'deltaTime' ..but really, we have situation like this: # anmDT (time used to render the whole scene once) # simDT, N (time used to complete one simulation step, number of iterations) # deltaTime= (simDT * N) + anmDT (time used to simulate and render last frame) although obvious, this may pass unnoticed - "undersampling" is theoretically and practically only possible if the time to execute one simulation step is smaller than the fixed time step being simulated ..in a real-time that is +++ "Half-solution A" ..here's 2nd scenario and one of the ways to avoid spiraling singularity by treating it as a 'special case' ..it is actually your old algorithm until simDT >= STEP at which point we have no choice but to slow down the simulation speed if we insist to stay with the same fixed time step - the difference is that this implementation will not spiral "down to death" and no capping will occur which should result in smoother animation and still preserve accuracy and determinism... furthermore, this little addition will try to compromise between keeping high FPS and high as possible simulation frequency depending on fpsTensor variable.. //-------------------------------------------------------------------------------- float accum= 0.0f float simDT, anmDT; float STEP= 1.0f / 100; int cnt, fpsTensor= 30; while( theBeatGoesOn ) { nowTime= getCurrentTime(RTN_SECONDS); accum+= deltaTime= nowTime - lastTime; anmDT= deltaTime - simDT; if(cnt>0) simDT/= cnt; lastTime= nowTime; cnt= 0; while( accum >= STEP ) { cnt++; stepSimulation( STEP ); accum-= (simDT >= STEP)? simDT+(STEP*anmDT*fpsTensor) : STEP; } simDT= getCurrentTime(RTN_SECONDS) - lastTime; renderScene(); } //-------------------------------------------------------------------------------- (R)All rights reserved, dont you dare use this code unless you can prove to me you're human being. Use of this algorithm in commercial products without my permission will be cheerfully taken to court. //-------------------------------------------------------------------------------- *** [BULLET IMPLEMENTATION] in "btDiscreteDynamicsWorld.cpp" replace "btDiscreteDynamicsWorld::stepSimulation" with this: //------------------------------------------------------------------------------ #include <stdio.h> static btClock realTime; double simDT, anmDT, STEP; double secCnt, deltaTime = 0.0; int cnt, FPS, SPS, fpsTensor= 60; int btDiscreteDynamicsWorld::stepSimulation( btScalar timeStep,int maxSubSteps, btScalar fixedTimeStep) { deltaTime= double(realTime.getTimeMicroseconds())*0.000001f; if(deltaTime > 0.75) deltaTime= 0; STEP= fixedTimeStep; m_localTime+= deltaTime; realTime.reset(); FPS++; saveKinematicState(fixedTimeStep); applyGravity(); anmDT= deltaTime - simDT; if(cnt > 0) simDT/= cnt; cnt= 0; while( m_localTime >= fixedTimeStep ) { cnt++; SPS++; internalSingleStepSimulation(fixedTimeStep); m_localTime-= (simDT >= STEP)? simDT+(STEP*anmDT*fpsTensor) : STEP; } synchronizeMotionStates(); clearForces(); simDT= double(realTime.getTimeMicroseconds())*0.000001f; return cnt; } //------------------------------------------------------------------------------ ...re-compile and voila ...no more moon-walking! there is no need to change anything anywhere else, it completely disregards the timeStep and maxSubsteps that your games, demos and Bullet demos pass as arguments, they not really required to be supplied if this function is supposed to deal with time allocation anyway ..in case you have fast CPU im not sure if you will notice anything because everything will work as before.. or maybe even better? ..but if you try benchmark demos or have slow CPU you will definitively notice the difference, if you used maxSubSteps > 1 this is still only half-solution and it goes ON when (simDT >= STEP), that is when one simulation step need same or more time to execute than what is 'fixedTimeStep', it seem to be quite nice and visually smooth effect... but until then, its just like the old algorithm - bit choppy as simDT gets close to STEP - its a *VISUAL BELL* that tells you to lower down your simulation frequency or optimize the physics... former can be included in algorithm so it handles it automatically if that is acceptable for the end application, so that fpsTensor work left and right in regards to fixedTimeStep and pivot simulation speed and animation around desired FPS keeping it smooth on both sides around that critical fixedStep value # anmDT (time used to render the whole scene once) # simDT, N (time used to complete one simulation step, number of iterations) # deltaTime= (simDT * N) + anmDT (time used to simulate and render last frame) # FPS, SPS (animation Frames.Per.Sec, simulation Steps.Per.Sec) [ simulation SPS & animation FPS only exist as a real-time measurements, its a bit misleading to talk about Hz/FPS in design-time, that's only what you HOPE FOR, but on the program level you are really dealing in "deltaTime" and "simFixedStep" values only ..and what we are trying to do here is to average those STEPS and FRAMES per real-time second, which then maybe can be called "temporal interpolation", but im not quite sure what is the point of "geometrical interpolation" these physics libraries use today, it seem to be just unnecessary and artificial way to "smooth" the visual artifact produced by capping the number of subSteps ] cheers, http://www.geocities.com/ze_aks/ http://www.geocities.com/ze_aks/myos [Edited by - abaraba1 on September 14, 2008 8:04:23 PM]

thats it.. how wonderful!

- so where were you hiding all this time?
- why didnt you tell us about it before?
- why all the 3 mayor Physics engines have implementation with *maxSubsteps*?
- and why is such a confusion around such a simple thing?


>>"What advantage does that have over the simplistic accumulator approach?"

im not sure, i just got around realizing all "this" a few days ago.. and it took a month of confusion trying to figure out what in the world is going on?!!

i basically constructed algorithm around so i can prove to people why is old algorithm with maxSubSteps bad and why we must not have any MAX number of anything ..and no one actually believed me!?


but you got it to the point really.. beautiful!


anyway, i feel you know more about all this then i do,
so what do you think how these two compare?


cheers


[Edited by - abaraba1 on September 8, 2008 5:42:45 AM]

all right,
i'll do my inner dialog thing again,
but everyone is of course welcome to join any time ..whether to improve algorithm or to explain why PhysX, Havok and Bullet use maxSubSteps?


"simplistic accumulator"
lets turn few things around, make it bit more general and we get something like this, that can too effectively substitute Bullet's stepSimulation() function:

//------------------------------------------------------
int btDiscreteDynamicsWorld::stepSimulation( btScalar timeStep,int maxSubSteps, btScalar fixedTimeStep)
{
m_localTime+= (timeStep < fixedTimeStep*2)? timeStep : fixedTimeStep*2;
saveKinematicState(fixedTimeStep); applyGravity(); maxSubSteps= 0;
while( m_localTime >= fixedTimeStep )
{
internalSingleStepSimulation(fixedTimeStep);
m_localTime-= fixedTimeStep; maxSubSteps++;
}
synchronizeMotionStates(); clearForces();
return maxSubSteps;
}
//------------------------------------------------------

again,
there is no need to change anything anywhere else

- maxSubSteps is completely disregarded and used as a counter
- this time you need to supply deltaTime, here called timeStep

main loop:
dt = timeSinceLastFrame();
stepSimulation(dt);
//stepSimulation(dt, 0, 1.0/60);

renderScene();


..solution B is simply about switching simulation frequency which might suit some cases better,
but the one above is probably more general and give desired visual effect considering the circumstances
//-------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------



- it basically replaces all this,
and i suppose there is similar equivalent of "maxSubSteps" implementation in Havok, PhysX, ODE, Newton.. ?

****** ORIGINAL STEPPING FUNCTION with "maxSubSteps" ******
//---------------------------------------------------------------------------
int btDiscreteDynamicsWorld::stepSimulation( btScalar timeStep,int maxSubSteps, btScalar fixedTimeStep)
{
startProfiling(timeStep);
BT_PROFILE("stepSimulation");
int numSimulationSubSteps = 0;
if (maxSubSteps)
{
//fixed timestep with interpolation
m_localTime += timeStep;
if (m_localTime >= fixedTimeStep)
{
numSimulationSubSteps = int( m_localTime / fixedTimeStep);
m_localTime -= numSimulationSubSteps * fixedTimeStep;
}
} else
{
//variable timestep
fixedTimeStep = timeStep;
m_localTime = timeStep;
if (btFuzzyZero(timeStep))
{
numSimulationSubSteps = 0;
maxSubSteps = 0;
} else
{
numSimulationSubSteps = 1;
maxSubSteps = 1;
}
}

//process some debugging flags
if (getDebugDrawer())
{
gDisableDeactivation = (getDebugDrawer()->getDebugMode() & btIDebugDraw::DBG_NoDeactivation) != 0;
}
if (numSimulationSubSteps)
{
saveKinematicState(fixedTimeStep);
applyGravity();

//clamp the number of substeps, to prevent simulation grinding spiralling down to a halt
int clampedSimulationSteps = (numSimulationSubSteps > maxSubSteps)? maxSubSteps : numSimulationSubSteps;

for (int i=0;i<clampedSimulationSteps;i++)
{
internalSingleStepSimulation(fixedTimeStep);
synchronizeMotionStates();
}

}
synchronizeMotionStates();
clearForces();

#ifndef BT_NO_PROFILE
CProfileManager::Increment_Frame_Counter();
#endif //BT_NO_PROFILE
return numSimulationSubSteps;
}
//---------------------------------------------------------------------------

[Edited by - abaraba1 on September 12, 2008 7:12:14 PM]

hi agi_shi,

could you tell us what Physics library do you use and could you point some reference that talk about this "simplistic accumulator"? ..i find that term did not really exist and does not return any search results, so id appreciate if you can point where did you find about it and if there is something i failed to notice about the whole thing?

anyway, as it seem you have been using this much longer than i managed to test it in the last couple of days - could you share some of your experience with stepping the simulation in fixedTimeSteps?



thank you


//---------------------------------
all kinds of feedback/comments appreciated.. anyone?

hi grhodes_at_work,

- could you please give some comments on the whole subject?
- can you confirm that algorithms indeed work in practice as i described?
- would you agree that this is nicer design solution with much better visual results?


thank you

..surely this is in everyones interest and someone could at least confirm am i right or wrong?

i can only test it as much, and i ask everyone for help,
hope thats not too much to ask.. after all, if it works then we all benefit, right?


thank you

Quote:Original post by agi_shi
Definitely interesting post. What advantage does that have over the simplistic accumulator approach?

real accum = 0;game loop{    const real FREQ = 1.0 / 60.0, MIN_DT = 1.0 / 10.0; // 60 FPS integration, min. 10 FPS    for (accum += min(dt, MIN_DT); accum => FREQ; accum -= FREQ)        integratePhysics(FREQ);    render();}

If dt is based on real time there's the possibility that the time taken to simulate it causes an increase of dt to the next loop. On a bad system that may cause dt to keep increasing over several loops, and there'll be a long time lapse between visual updates, so it looks choppy.

It seems abaraba1's algorithm is intended to cause shorter/smoother time lapses, but slow motion instead (though I must say I'm not clear on all details in the code). So if I understood it'll look smoother and still be stable, is that right? (Question to abaraba1)

Quote:Original post by abaraba1
- and why is such a confusion around such a simple thing?

Because time steps are used in both graphics and physics, and games require both, while their respective implementations are different. Some people wants graphical speed, other wants physical stability and realistic time, so discussions about time steps don't end with one answer, but several answers, and those cause the confusion over which to choose, I believe.

Lastly I want to recommend a good "A discussion about fixed time steps"-thread that's worth reading.

thank you my friend,
you are my 1st normal human contact with the "world community" and i've been trying to discuss this for over a month during which i've been met with strong resistance and disapproval, i've been told nothing but how i "do not understand" and "not getting the point"... i've been banned from public forums merely for asking a questions and trying to figure this thing out ..then, after that - complete silence?!

thanks again!



>>"So if I understood it'll look smoother and still be stable, is that right? (Question to abaraba1)"

yes,
in essence - instead of to cap number of iterations you "cap" or "scale"(with the 1st algo) the accumulator/deltaTime which is in practice very similar thing only the later appear smoother because of the way how the FRAMES get *distributed* in the real time - but indeed it is a difficult thing to imagine..

Unfortunately, no one can be told what the 'temporal interpolation' is. You have to see it for yourself.


ahm.. so, regardless of everything,
i would like to recommend and suggest Bullet physics library if for nothing else but just to test this and practically SEE what is the difference. Bullet library will compile quickly and easily on Windows, Linux or Mac, it comes with lots of demos that compile and build automatically when you build the library. In a matter of minutes you could try to copy/paste algorithm from above, recompile and you will definitively notice the difference and see what is this all about by running the Bullet demos again.

http://www.bulletphysics.com/Bullet/wordpress/



>>"Lastly I want to recommend a good "A discussion about fixed time steps"-thread that's worth reading."

thanks, i wish i knew about it sooner.. that is exactly what im talking about, so in case some people having trouble to read my 'funny english' i too recommend that thread as a good read..



cheers

[Edited by - abaraba1 on September 14, 2008 10:31:54 PM]