   objects jittering, timestep/interpolation problems
  I apologise for the amount of code dumped in this post, but I am really at my wits end...I'm having problems with jittering/stuttering in my game engine, that is, visible objects in the world that are moving occasionally shake as if jumping very quickly between two positions or something. This doesn't happen all the time, only every few seconds or so. I think it must be to do with my timestepping and interpolation system.I'll try to describe how my engine does timestepping. But if you don't have time to read all this then just skip to the bottom where I've tried to describe the jittering better... maybe there is a common cause for this sort of thing?...My engine contains three main types of object; Entities, Bodies (physics), and Graphics. All of these are derived from a base ITransformable which allows setting and getting of their world transformations.The "top level" game object is the Entity. An entity can optionally contain a Body (from the physics engine) and also a Graphic (such as a mesh).Crucially, these three types of objects are each managed by a separate task, and each task is run at a different frame rate. (these are not in separate threads mind)Physics bodies are managed by a PhysicsTaskEntities are managed by a LogicTaskGraphics are managed by a RenderTaskI also have a system where (in its constructor) an entity can specify rules defining how some parts take their transformation from others.For example, if an Entity has a Body and a Graphic, then there would be rules saying:- the Entity itself takes its transformation from the Body- the Graphic also takes its transformation from the BodyThis allows for other combinations, for example an entity doesn't have to have a body, and then it can be specified that the Graphic takes its transformation straight from the entity. But the situation with a body, an entity, and a graphic is the most common, and is what I am having problems with.It is assumed that Bodies, as they are controlled by the physics engine, will never take their transformation from anywhere. Transformations can thus only be propagated in these possible manners:body->entitybody->graphicentity->graphic(it is assumed that graphics will never give anything else their transformation, as they are positioned as a result of other logic or physics)Now obviously since they updated at different frame rates, there needs to be interpolation between them.A graphic may be rendered in between updates of the physics Body, so it will have its transformation interpolated between the previous Body transformation and the current Body transformation.Well I think I can better show the rest of how this works through code. I've pruned as much uneccessary stuff out as possible.Pretty much the main loop:The PotentialUpdate method of a task may or may not call its actual update function, depending on how much time has passed.while (true){for (int i = 0; i < tasks.size(); i ++){tasks->PotentialUpdate(GetTimeInSeconds());}}ITaskThis is the base class for all Tasks. PotentialUpdate is repeatedly called in the main game loop, and it should trigger the Update function (implemented in a derived task) when the defined timestep has passed.Derived classes are PhysicsTask, LogicTask and RenderTask.PhysicsTask has a fixed timestep of 1/20.LogicTask has a fixed timestep of 1/15RenderTask has a non-fixed timestep (should run as fast as possible).(but these timestep sizes are pretty arbitrary for now)class ITask{public:ITask(){// default settings, derived classes will specify different valuesfixedTimeStep = false;timeStep = 1.f/60.f;}virtual void Update(float dt, float currentTime) = 0;float GetInterpolationAmount(float currentTime){return (currentTime - lastUpdateTime) / timeStep;}protected:bool fixedTimeStep;float timeStep;private:float lastUpdateTime;void InitUpdateTime(float currentTime){lastUpdateTime = currentTime;}void PotentialUpdate(float currentTime){// Only call Update at that task's FPSfloat timeSinceLastUpdate = currentTime - lastUpdateTime;// Update if the timestep has passed, OR if is not a fixed timestep (as with// rendering) then update whenever possible.if (timeSinceLastUpdate >= timeStep || !fixedTimeStep){// if the timestep is fixed, then that is the amount passed as the delta time// (the first parameter of Update) to the Update. However delta time is// not actually used anywhere yet so it is not relevant to the problemUpdate( fixedTimeStep ? timeStep : timeSinceLastUpdate, currentTime );lastUpdateTime = currentTime;}}};Transform rules structure and interpolation functions:Each Entity has a TransformRules structure which it uses to define what interpolations take place. physicsToLogic will contain Body-Entity pairs, logicToGraphics contains Entity-Graphic pairs and physicsToGraphics contains Body-Graphic pairs.EvaluateTransformRules takes a list of pairs (physicsToGraphics for example) and:The "first" in the pair is the source for the transform (e.g. the physics Body), so its transform is interpolated between its previous (cached) value and its current value, based on the interpolation amount. The "second" in the pair (e.g. the Graphic) is then set to this resulting interpolated transformation.struct TransformRules{std::vector<std::pair<ITransformable *, ITransformable *> > physicsToLogic;std::vector<std::pair<ITransformable *, ITransformable *> > logicToGraphics;std::vector<std::pair<ITransformable *, ITransformable *> > physicsToGraphics;};void InterpolateMatrix(const matrix4 &a, const matrix4 &b, f32 alpha, matrix4 &dest){dest = b*alpha + a*(1.0-alpha);}// takes a reference to a vector of pairs, (one of the three from a TransformRules structure)// Entity, Body and Graphic all derive from ITransformablevoid EvaluateTransformRules(const std::vector<std::pair<ITransformable *, ITransformable *> > &rules,float interpolationAmount){for (int i = 0; i < rules.size(); i ++){ITransformable *a = rules.first;ITransformable *b = rules.second;matrix4 m_interpolated;// Set b transform to interpolated between a's last transform and current transform.InterpolateMatrix(a->GetCachedTransform(), a->GetTransform(),interpolationAmount, m_interpolated);b->SetTransform(m_interpolated);}}Now I'll describe the Update methods of each task. The Update method is called by PotentialUpdate at each time step.PhysicsTask update. First of all calls CacheTransform on each body, which saves the old transformation (so it can be interpolated from). Then steps physics, so on finishing all Bodies will have a new transformation. (Bodies get their transformations from the physics engine).void PhysicsTask::Update(float dt, float currentTime){// Cache last body transformationsfor (IEntity *entity = world->GetFirstEntity(); entity = world->GetNextEntity();){if (IBody *body = entity->GetBody()) // may either have a single body or a vector of bodies{body->CacheTransform();}else if (const std::vector<IBody *> *bodies = entity->GetBodies()){for (int i = 0; i < (*bodies).size(); i ++)(*bodies)->CacheTransform();}}// Step physics!physics->Step(dt);}LogicTask update, updates all Entities.Like with the physics update, all old entity transformations are cached in case a graphic takes its transform from an entity and needs to do interpolation.The GetInterpolationAmount is part of ITask, and returns a value from 0 to 1 based on the fraction of the task's timestep that has passed since the last task update (in this case it is PhysicsTask.GetInterpolationAmount that is called, so it is the interpolation amount since the last physics update).Then, some physics-to-logic "transform rules" are evaluated. These are simply a list of Body-Entity pairs present in each entity. Generally there is only one rule, which defines that the current entity takes its transformation from a specific physics Body. These use the interpolation amount to set a Entity's transformation to somewhere between the previous and current physics Body's transformation.void LogicTask::Update(float dt, float currentTime){// Cache last Entity transformationsfor (IEntity *entity = world->GetFirstEntity(); entity = world->GetNextEntity();)entity->CacheTransform();float physicsInterpolation = engine->GetPhysicsTask()->GetInterpolationAmount( currentTime );// Evaluate body->entity transform rules...for (IEntity *entity = world->GetFirstEntity(); entity = world->GetNextEntity();)EvaluateTransformRules( entity->GetTransformRules().physicsToLogic, physicsInterpolation );// Update entities, now they have their new positionsfor (IEntity *entity = world->GetFirstEntity(); entity = world->GetNextEntity();)entity->Update(dt);}RenderTask update.Don't need to cache the previous Graphic transformations as there is nothing which takes its transformation from a graphic.Interpolation is done for graphics much like it is done for physics-to-logic in LogicTask (this time as physics-to-graphics), except there is also the possibility of interpolation from entities as well as bodies (logicInterpolation and logicToGraphics).void RenderTask::Update(float dt, float currentTime){float physicsInterpolation = engine->GetPhysicsTask()->GetInterpolationAmount( currentTime );float logicInterpolation = engine->GetLogicTask()->GetInterpolationAmount( currentTime );// Evaluate body->graphic transform rulesfor (IEntity *entity = world->GetFirstEntity(); entity = world->GetNextEntity();)EvaluateTransformRules( entity->GetTransformRules().physicsToGraphics, physicsInterpolation );// Evaluate entity->graphic transform rulesfor (IEntity *entity = world->GetFirstEntity(); entity = world->GetNextEntity();)EvaluateTransformRules( entity->GetTransformRules().logicToGraphics, logicInterpolation );// Render now that all Graphic objects have been given their new, interpolated, transformationsrenderer->Render();}So there you go! I really can't see much wrong with it, it ought to work... And it does work for a some of the time, just an occasional (very visually obvious) stutter.Even if the physics was running slow or something, I don't see why it should cause a stutter. And there is only one or two objects present for testing, so it shouldn't be slow at all.Interestingly, if PhysicsTask and LogicTask are both given the same time step size, then the problem completely disappears and it seems to work perfectly, as if them being unsynchronised causes the problem. This is rather odd, I have no idea why this might be.Maybe there is sometimes a situation where two tasks need to update at the same time, so one gets delayed. But once again interpolation is supposed to deal handle this.More about the stutter: it doesn't even just look like a temporary slowdown/frame rate issue, it looks kind of like the object is jumping forwards a bit then jumping backwards really quickly. As if the interpolation was messed up somehow...!?Further thought: on a really low power machine it constantly stutters, and it is very evident that the problem is jumping back and forth between positions. Like each frame it is alternating between two positions! Or for a fraction of a second a completely out interpolation value was being used.It also seems to be worse the more faster moving an object is.   
  I don't have a great deal to offer here, but here's something you might try.Set up your simulation with a single object, and give it an axis-aligned initial velocity and no drag. Set it up so that (in theory at least) the object will move at a fixed speed along a single positive axis (e.g. x), with no rotation or other motion.Then, add some debug output that tracks its position on this axis (a single scalar), the interpolation value, and anything else that you think might be relevant. For each entry, store both the 'old' and 'new' positions (the positions you'll be interpolating between).After running the simulation for a bit, examine the debug output. The position should be strictly increasing, and (presumably) the 'old' position for each position pair should match the 'new' position from the previous pair. For the updates for which a single pair of positions applies, the interpolation value should be strictly increasing.This may all seem fairly obvious, but it sounds to me like there's a fairly straightforward logic error somewhere that you could probably isolate by setting up a very simple test case like the one described above. In the described test case, you'd be looking for unexpected values for the old or new object positions (which in the example are strictly increasing scalars and are therefore easy to track), irregularities in the interpolation value, or places where the interpolation value cycles without a corresponding update to the transforms.If the problem doesn't occur in this simple test case, you can start adding more elements to the test case (rotational motion, multiple objects, etc.) in order to determine where and when the problem is introduced.The probably isn't related, but I notice you're interpolating your transform matrices linearly. I'm guessing you already know that the results of this won't be entirely accurate, and will most likely cause your objects to deform somewhat over the timestep (if the timesteps are small enough though, this probably won't be too noticeable).   ;  Several possible issues, as mentioned your interpolating linearly on the matrix, which I don't know if you'll get the results you want for the rotational component. Interpolation schemes I've seen separate out the rotation component and interpolate it using quaternion, but I'm not that familiar with the math so you'll have to look into that. 2nd issue is aliasing of update rates, since you have 2 different update rates coupled together. The physics and logic update rates are slightly out of sync ( in the original scheme u had where it was 20/15 ), so in some cases the you could get multiple physics update on a single logic update or vice versa, that could be an issue. When your interpolating from 0->1 this is implicitly applying a velocity on the matrix transformation speed depending upon the update rate. So at 15 ups each tick represents 66 ms but at 20 ups each tick is 50ms. So fundamentally the physics systems assume a velocity of 50ms per tick, while the logic update assumes a 66ms per tick. So this means the logic systems interpolation results will always undershoot the physics system implicit velocity for the matrix ( ie a .5 interpolation on logic is 33 ms while .5 on physics is 25 ms ).3rd issue, your interpolating from 0->1 initially and taking that value for the logic matrix, which in turn is interoplated again from 0->1 in the render thread and that is the value displayed. As you can see there are many steps where interoplation error creeps in. This might be an issue.Good Luck!-ddn   ;  Hi, thanks for the suggestions. I've had a look at a really simple situation and am doing as jyk advises, but haven't found anything obviously out of order yet.Except that in some cases there is a huge variation in the amount of render updates (and interpolations) done per physics timestep (e.g. sometimes with 5 or so, some with 20 or so), and it does seem like this occurs around the time the stuttering does. But I'm really not sure if it is related.I forgot about the interpolation, you meant I should use slerp for the rotations right? It doesn't help though, not related.@ddn3for the 2nd issue, I'm afraid I don't completely understand what you mean... is this aliasing something that is fixable?for the 3rd issue, there is only actually one interpolation step in this test case, from body to graphics. it would be possible to have others but I am just testing in this simple situation. maybe I overcomplicated things by including it, logicTask is not actually used yet.There are a few things I noticed which I'm still thinking through:- In the update, timeSinceLastUpdate >= timeStep means that there will always be a small fraction of time left over (timeSinceLastUpdate-timeStep), I don't know if this might cause problems. I tried subtracting (timeSinceLastUpdate-timeStep) from the lastUpdateTime each update to account for this, and it seemed to help on the slower machine at a particular physics timestep size, but if I varied the timestep size or moved to a faster machine the problem reappeared.- I calculate the interpolation amount as a fraction of the fixed timeStep, while the actual time passed may not be exactly that. Don't know if this is a problem. The interpolation amount never seems to go out the 0-1 range though.To be honest though, unless someone can see something very obvious I should change in my code I will probably abandon this "tasks" approach, I've spent too much time on it.Although I'm just having a last look at this article which seems to be somewhat similar to what I want to do... Trying to get my head around it.. It seems there is a couple of missing operators in the code in that article (see before TICK_TIME), anyone know what they should be?   ;  Soo...I had a look at that article (the complete version without missing operators is here), and reimplemented my timestepping system using their approach.... and the problem was still there!The only real difference in my approach from others seemed to be that I had more than one fixed timestep task. So, I have combined my Physics task and Logic tasks into one, and sure enough it now works perfectly!So something to do with doing interpolations in more than one task was causing the problem. But it is an acceptable solution to keep physics and logic combined, I suppose, better than wasting any more time. I can always run multiple physics steps for every logic one.I'm still very puzzled about the cause of this though.   ;  I'm not sure what distinction you're drawing between "physics" and "logic". If you have code that updates game state in response to user input, it should be as minimal as possible - respond to the key event directly by setting e.g. m_accelerating in the player's object. Then the "physics" does everything else.   ;  Ermm... hmm. I had some weird ideas about running AI or something at a different rate to physics, so that might have needed interpolated physics positions. But I am beginning to see now it was probably pointless and unnecessary.. :)   