pouët.net

Frame-independent movement, I'm stuck

category: general [glöplog]
Quote:
huh? We have intricate enginereed solutions, like, uh, pointers, to solve that...


Uhm.. except that what he's doing is copying the state of the simulation, so he can interpolate between that state and the next:

Code:previousState = currentState; integrate(currentState, t, dt);


You can take that to be pseudocode explaining the principle, but it doesn't really do justice to the amount of changes you'd have to make to an existing engine to turn it from single- to doublebuffering. And don't forget the second copy going on here:

Code:State state = currentState*alpha + previousState*(1.0f-alpha);


Which, again, you can work around, but whatever you do it's not the trivial process it looks like, the biggest difficulty lying in the "+" operator and how one state lines up with another. In a game you'll invariably have objects being created and destroyed between frames, and/or moving from one position to another in non-linear containers like quad-/octtrees.
added on the 2009-01-02 18:01:17 by doomdoom doomdoom
Quote:
Wtf is wrong with "QueryPerformanceCounter" for Windoof or "gettimeofday" for Linux?


QueryPerformanceCounter is neat, although, at least at one point, it had some bad problems on multi-core CPUs. I don't know if they've been dealt with.
added on the 2009-01-02 18:05:52 by doomdoom doomdoom
bad problems being the frequency jumping up and down if the CPU switches to energy saving mode? :)
added on the 2009-01-02 18:16:50 by Gargaj Gargaj
@doom (or whoever, i cannot follow the nicknames on pouet for some years now...):

1) it's pseudocode, not the friggin' duke nukem forever source
2) he has bigger problems than a little memory copy
3) unless he has like 10^6 particles, you won't notice the time spent on copy
4) if he has 10^6 particles, memory copy will be unmeasurable compared to the rendering time
5)
Code: state state1,state2; state *oldstate=state1,*newstate=state2; [...] swap(oldstate,newstate); [...]
added on the 2009-01-02 18:18:32 by blala blala
Quote:
it's pseudocode, not the friggin' duke nukem forever source

for all we know, the two might be identical.
added on the 2009-01-02 18:25:52 by Gargaj Gargaj
Gargaj: Oh yeah, I remember reading about that, too. :) Probably an even bigger issue. But just the fact that each core has its own performance counter is somehow bad enough, isn't it?

blala: Doom, of course. ;) But it's Christmas.

1) I know.

2) I know.

3+4) Possibly, possibly not. 10^6 "physics states" can be a shitload of data, unless the parts requiring interpolation are separated from the rest of the data (not trivial either, in practise). Rendering them isn't necessarily slow, especially since you might not need to process all of them in rendering (think quadtrees, BSP trees, portals and such).

(You might also have particles represented by a single pixel, in which case copying does take a comparable amount of time to rendering.)

5) There's still an implicit copy there. state1 and state2 both need to be complete states, so when the physics engine updates newstate, it has to update every single element, since the data it's writing over is two iterations old, not one.

And there's still the problem of producing a linear combination of two states. That requires some way of lining them up so that you can always pair an element from state1 with the corresponding element from state2. You really don't want states represented just by lists of objects in no particular order. Do you leave a blank space in the list when destroying an object, for example? Cause if not, it won't line up with the state from the previous iteration, and then how do you combine the two?

Obviously what you want is to maintain two separate states per object, not to maintain two complete states separately. That forces some design choices on you, but it's probably not too bad unless you've already done a lot of work in a different direction.

It's still not "perfectly simple", though. Suppose you have an object somewhere in a quadtree. In the previous state, it belonged to one node, in the current state it's moved to another. Depending on how far into the timestep you want the interpolated position, it may be in the wrong part of the tree compared to the position shown to the rendering engine. If the rendering engine also uses the quadtree (and that's a perfectly awesome way to cut down on superfluous rendering), objects may be discarded as off-screen even when their interpolated position would have put them on-screen.

I guess it more or less sums up as "decoupling a renderable object's visual representation from its internal representation is not as simple as Glenn Fiedler makes it out to be".

Here's some physics-enginy stuff I was doing, in case you think I haven't actually tried a whole bunch of different approaches to physics. ;) (F1 toggles normals and stuff, F2 toggles gravity, and F4 zooms).
added on the 2009-01-02 19:28:46 by doomdoom doomdoom
your program crashes here. :P

anyway, the physics are really not a real cpu hogger, it's just about updating x and y coordinates, and I don't need to do any binary sorting or something like that anyway, because I already have to arrays, one holding the currently active particles and one that contains the inactive ones (that way, I can switch the state of a certain particle fastly), and those that are active are also visible.
Thanks a lot guys, your help was really useful. The game timing seems to be a lot more reliable after using the "accumulator" as described at Gaffer on Games. I'll try to add that dithering stuff as it's described there as well next.
lol @ Gargaj :D

Also it seems the QueryPerformanceCounter is really unreliable sometimes. Some people sugest using timeGetTime() instead, but has other problems.

If you really want to know more about it, look here and here.
I wasn't smarter afterwards though...
added on the 2009-01-05 17:41:59 by raer raer
timeGetTime() is reliable. may be use timeBeginPeriod() to make it more accurate, but since Windows XP that should not make a difference.

stick to a fixed timeslice, 10ms works fine for 50 and 60 Hz displays. don't forget to interpolate (yes, KB, you are right).

forget all the fancy math, it's more complicated to get right than the people who suggest it do imagine.

something like this might do the whole trick (untested):


Code: void FRAME() { static int oldtime = 0; int newtime = timeGetTime(); if(oldtime==0) oldtime = newtime; while(oldtime<newtime) { SIMULATE(); oldtime += 10; } RENDER(); }


you should add some code, so that SIMULATE is never called more than like 100 times (that's at 1fps)

you should interpolate by (newtime-oldtime/10.0f), with the position after the simulation and the position before the simulation. this makes your image at most 10ms too old.

keep the timeslice factor as an easy to change constant. you might want to experiment. try to code all physics so that they care about that constant, but remember that you don't need to be perfect.

added on the 2009-01-05 18:49:36 by chaos chaos
oh, and it will crash when windows is running for longer than 42 days without rebooting.... (timer sign overflow..)
added on the 2009-01-05 18:51:20 by chaos chaos
Well yes, My code approximately looks like yours now (just that it counts down, not up). Just now that I thought of the interpolation stuff, I'm not really shure if I know how I should do that, since all objects are interfering with each other (ball hits platforms -> platforms fall down, particles appear, etc). so do i need to make a copy of every single object?
every object and the camera remember it's position and rotation from the last simulation step. then just linear interpolation. if they change bounce or change course, no one will notice. interpolation is only needed to get rid of a subtle jittering. but KB insists of it.
added on the 2009-01-05 20:00:30 by chaos chaos
Okay, thanks a lot for the clarification. I'll try to get this working tonight then.
Saga Musix: This illustrates the problem a bit:

BB Image

On the left is (supposed to be) the path of a particle bouncing a couple of times, then landing on the floor and rolling a bit. On the right is the result of interpolating from discrete sampling points. If you picture the sampling points being one second apart, with 60 frames displayed between each point (along each interpolated line), what you get won't look anything like a bounce at all.

Of course, if the simulation runs at a higher framerate than the rendering engine, you probably won't have to worry about it, so simply remember the current and previous positions for each object, and add a getInterpolatedPosition( float dt ) method for all of them, ignoring the path taken between timesteps.

What you might have to worry about is very fast constrained movements, like a particle rotating about a fixed point very quickly. Basically you can't trust distances with this method, so e.g. if you're using two particles to describe the position and orientation of an object, be mindful that even if the particles are rigidly constrained to a certain distance from one another, their interpolated positions won't be.
added on the 2009-01-05 21:13:31 by doomdoom doomdoom
That's why I proposed introducing a flag that turns off the interpolation on "hard cuts" such as bounces. In the above example, the physics code could set the flag when the ball hits the ground and omit the ball's first-tick collision response. Of course this would "delay" the ball's movement by the fraction of a tick but it would at least look like a proper bounce.

I won't dig out my non-existent photoshop skills now, but imagine the 5th and 10th point of the red line firmly tucked to the ground.
added on the 2009-01-05 21:24:36 by kb_ kb_
well, I'm forcing the ball to "touch" the platforms if there was a collosion anyway, so I guess that there's no need to turn interpolation off anyway.
kb: But linear interpolation can give you undesirable results if you take more than one sample from each interval (which of course you avoid by running the simulation at a "high enough" framerate, which was really the point I was trying to make). If you want to make sure that there's a full frame shown where colliding objects are actually touching, then yeah, I guess turning off the interpolation would give you that in exchange for a bit of delay (made up for by a skip, mind you), but probably nothing noticeable.

Saga Musix: There would be if you want to make sure that the collision is shown. If I understand you right then the ball will only touch the platform for one physics frame, and rendering may skip that frame altogether. It's actually more correct not to show that frame, though, so I dunno what would look best in your case.
added on the 2009-01-05 22:28:58 by doomdoom doomdoom
well, rendering is completely independent, so it will maybe not be shown visible. :)
QueryPerformanceTimer works quite well really. There are a few proplems tho but they can most of the time be avoided.

As gargaj said there is a problem when the cpu switches to energy saving mode. (solved by calling QueryPerformanceFrequency and set new frequency when that happens).

but also when calling it from multiple cores.

QueryPerformanceTimer should only be called from one core. (which is usually the case anyway, the main thread calculates delta and time).

added on the 2009-01-05 23:13:46 by pantaloon pantaloon
and this must be some kind of record. no trolling yet ?
added on the 2009-01-05 23:15:39 by pantaloon pantaloon
doom: if the bounce rate is that fast compared to the frame rate, i dont see a problem with having a jitter...
added on the 2009-01-05 23:19:04 by Gargaj Gargaj
when do you know you have to QueryPerformanceFrequency again? is there a notification mechanism?
just call it every 128 or 256 frames and you are fine :D
added on the 2009-01-05 23:42:07 by xyz xyz
BB Image
added on the 2009-01-06 01:22:55 by thec thec

login