Jump to content

  • Log In with Google      Sign In   
  • Create Account


advancing animation in fixed time-steps & frame-rate independence


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • This topic is locked This topic is locked
25 replies to this topic

#1 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 18 September 2008 - 10:21 AM

hi, if you use fixed time steps in your game, whether with your own physics library or Intel Havok, nVidia PhysX, Bullet, ODE... you are most likely using this algorithm that deals with the maximum number of iterations in the following way: //-------------------------- *** ORIGINAL algo - capping the NUMBER
cnt= 0;
time= 10;

maxSteps= 5;

while(time > 0 && cnt < maxSteps)
{
  step(); cnt++;
  time--;
}

//--------------------------
Iterations, cnt= 5
"Time left", time= 5

most might recognize that the inner part of your 'stepSimulation' function resembles this algorithm, best described here: "Fix Your Timestep!" now, the problem with its practical implementation is in that you have to guess the NUMBER, and it manifests in two ways under certain circumstances: 1.) guess was too low for target CPU - "moon gravity effect" 2.) no matter how high - on some target 'slow enough CPU' it will "spiral to death" which is not a "real problem", because you can sort it out in design-time, but the peculiar thing is that it also seem to try to deal with the reminder of the time after the iterations have finished, with -interpolation- , which i think only introduces the errors and its not really necessary? //----------------------------------------------------------------------------------------- i propose two solutions, this practically solves both problems and removes any errors possibly introduced by "interpolation": //-------------------------- *** 1st algo - scaling the TIME "inside"
cnt= 0;
time= 10;

scaleFactor= 1;

while(time > 0)
{
  step(); cnt++;
  time--; time-= scaleFactor;
}

//--------------------------
Iterations, cnt= 5
"Time left", time= 0

//-------------------------- *** 2st algo - capping the TIME "outside"
cnt= 0;
time= 10;

if(time > 5) time= 5;

while(time > 0)
{
  step(); cnt++;
  time--;
}

//--------------------------
Iterations, cnt= 5
"Time left", time= 0

there is "a paper" on this and there you can find practical implementation and copy/paste source code to REPLACE your existing algorithm, so this can be easily tested in 5-10 minutes, and the difference is very obvious: "sampleTest.html" in essence, these are the solutions related to these discussions: http://www.gamedev.net/community/forums/..452753 http://www.gamedev.net/community/forums/..393475 what do you think? does this approach solves some of your problems? thank you, gameBoX Linux //----------------------------------------------------------------------------------------- ApochPiQ,
Quote:
For better or worse, people are powerfully impacted by presentation.
- absolutely, how to make TAGS in this forum? are there buttons for TAGS like in other forums on the internet?
Quote:
There are many places to submit such papers; a little bit of research can find several candidates for you, or you are free to ask where to publish it in a forum such as this one
- i cant find anything, can someone give me a name or link or organization or some address? [Edited by - abaraba1 on September 19, 2008 7:26:17 AM]

Sponsor:

#2 scgames   Members   -  Reputation: 1973

Like
0Likes
Like

Posted 18 September 2008 - 11:44 AM

Quote:
- absolutely,
how to make TAGS in this forum? are there buttons for TAGS like in other forums on the internet?
You can create source boxes using [source][/source]. To quote text, use [quote][/quote].

You can also create clickable links by using the HTML 'href' tag.

#3 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 18 September 2008 - 12:47 PM

thanks, its fixed.
(tho it took quite some time, basically whatever i write the next time i edit im confronted with something different, it breaks lines, inserts some symbols, preview is different to the final page, some stuff is automatically inserted in the final message like 'yahoo.com', which i didnt want ..but all that is not important so lets NOT talk about that, lets just talk about algorithms..)


i see you are the author of CML:
- "The CML (Configurable Math Library) is a free C++ math library for games and graphics." (http://cmldev.net/)


thats great!
you're perfect to make some comment on this algorithms because this is the very place where mathematics merge with graphics in the most literal way


- would you agree these algorithms address and solve the problem?
- whats your opinion on how it works in practice - visual appearance?


thank you



//-----------------------------------------------------------------------------------------
Quote:
There are many places to submit such papers; a little bit of research can find several candidates for you, or you are free to ask where to publish it in a forum such as this one

- i cant find anything,
can someone give me a name or link or organization or some address?


[Edited by - abaraba1 on September 19, 2008 5:47:24 AM]

#4 scgames   Members   -  Reputation: 1973

Like
0Likes
Like

Posted 18 September 2008 - 01:25 PM

Quote:
Original post by abaraba1
thanks, its fixed.

i see you are the author of CML:
Co-author, actually (I worked with one other programmer on the project). But thanks for noticing :)
Quote:
thats great!
you're perfect to make some comment on this algorithms because this is the very place where mathematics merge with graphics in the most literal way
Unfortunately, physics (at this level at least) is not my area of expertise. There are plenty of folks here who have a lot of experience in that field though, so I imagine that now that the presentation is cleaned up a bit, you're likely to get some feedback on your ideas.

#5 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 18 September 2008 - 01:53 PM

>>"Unfortunately, physics (at this level at least) is not my area of expertise"

ok, fair enough,
but let me underline that this is not about Physics at all - it is about Graphics, its about Animation, its about FPS.. it is also about Mathematics since it is about an Algorithm ...its not about Physics

* its about the Algorithm that distributes those animation FRAMES per second, in a REAL-TIME



it is a little 'while loop' and only 3-5 lines of code, BUT
- this is the very essence of computer ANIMATION and the core 'function call' of any real-time simulation / game, right?


its not about the Physics,
it may be unfortunate circumstance that it ended up implemented in the Physics libraries, while it really belongs in the main program loop.



cheers




//-----------------------------------------------------------------------------
ApochPiQ,
Quote:

Similarly, code/source tags are important as well. They make it easy and convenient to copy/paste code and test it out. Although you are correct that it is still possible to do so without proper tagging, it's a pain.

>>"you can go on live your whole life thinking the earth is flat if you like, its not "important" information if you don't care about it, but if you use it in your line of work.. there was no point in arguing if you were not interested enough to pursue the matter for your own interests"

i find its actually easier to copy/paste without tagging

[Edited by - abaraba1 on September 20, 2008 2:53:05 PM]

#6 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 20 September 2008 - 09:17 AM

Quote:
There are many places to submit such papers; a little bit of research can find several candidates for you, or you are free to ask where to publish it in a forum such as this one


ok, i got some answers to this - thank you

SIGGRAPH:
http://www.siggraph.org/publications/instructions


but it doesnt seem to be very simple procedure,
- and would anyone go on to submit this without checking it out with general public first?
- i mean, i dont even know if this is some misunderstanding, i dont know if im right or wrong?
- simply, i cant be sure, and i can not go on claiming something if i cant confirm my results and my conclusions, right?



would anyone care to discuss this and actually confirm OR prove it wrong, im happy with either.


thank you

#7 Aardvajk   Crossbones+   -  Reputation: 5746

Like
0Likes
Like

Posted 21 September 2008 - 06:38 PM

In reality, your time values will not be nice, neat integers - most usually they will be very small float values. In a system updating in sync with the vertical retrace at 60 fps, the time values will be around 0.016f but will fluctuate around that value quite significantly.

Both of your solutions above appear to me to lead to the same problem that interpolation is introduced in order to solve - once your physics updates go out of sync with the graphics update, the display will begin to stutter as you will be doing, say, three updates one frame, then one the next, then three the next etc.

I haven't tested your algorithms to be fair, but from looking at the code they seem to be pretty much equivalent to just ignoring the accumulator when rendering. Both algorithms do less physics steps within the timeframe than is actually correct.

Interpolation doesn't introduce errors if done correctly, it just displays your graphics 0 to 1 frame behind the simulation.

#8 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 21 September 2008 - 10:42 PM

>>"Both of your solutions above appear.."

sorry, you lost me right there,
we cant discuss this if all you have to offer is your guesses and assumptions..


basically,
on all that what you said, im telling you - you're wrong

#9 Aardvajk   Crossbones+   -  Reputation: 5746

Like
0Likes
Like

Posted 22 September 2008 - 01:07 AM

Quote:
Original post by abaraba1
basically,
on all that what you said, im telling you - you're wrong


First algorithm consumes one time unit per call to step(). Remaining time units are propagated to next frame and interpolation used to "smooth out" visual results.

Both your algorithms consume 2 time units per call to step(). Therefore though 10 units have passed in actual time, only 5 time-units-worth of simulation has taken place.

Therefore in your example, simulation is running at half speed.

Also, regardless of whether you tell me I am wrong or not, there is now the capacity with more realistic values (in particular, different values for time each frame and a value for time that is not evenly divisible by the physics step) for the physics and rendering to fall out of sync so that you get, say, two steps one frame and one the next. This is what causes the visual stuttering that interpolation solves.

You keep referring to errors introduced by interpolation - what errors do you think interpolation introduces? I have two current projects that use the method outlined at gaffer.org and I can assure you that interpolation is not introducing any errors.

Since you are modifying Bullet code in your paper, may I suggest you post something about your discovery on the Bullet forums? Since the lead on that project worked on the Havok engine, I assume he has a fair idea what he is talking about.

[Edited by - EasilyConfused on September 22, 2008 7:07:10 AM]

#10 WillC   Members   -  Reputation: 540

Like
0Likes
Like

Posted 22 September 2008 - 01:24 AM

Quote:
Original post by abaraba1
>>"Both of your solutions above appear.."

sorry, you lost me right there,
we cant discuss this if all you have to offer is your guesses and assumptions..


basically,
on all that what you said, im telling you - you're wrong


It's a shame you're taking this attitude, as there are many experienced people on this site that could have given you constructive feedback on this issue. It's a well trodden path that anyone who has done any game physics has 'solved' many times before. Unfortunetly from your posts there seems little point in discussing this with you.

Also I noticed this on the page you linked to...

Quote:

® 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.


A few points about this. Firstly ® is a registered trade mark sign. Do you have a registered trade mark? If so what is it? and what does that have to do with 'your' algorithm? Secondly, what ownership claims do you have for 'your' algorithm? You'd need a patent to prevent commercial use (in countries that allow software patents); do you have a patent for this?

Obviously those are retorical questions, as clearly you don't, but my point is that you are way out of your depth here, making wild claims about things you seem to know little about. I would suggest you take a different, less agressive approach if you really want to find solutions to the problems you have presented.

[Edited by - WillC on September 22, 2008 7:24:07 AM]

#11 Kylotan   Moderators   -  Reputation: 3333

Like
0Likes
Like

Posted 22 September 2008 - 02:35 AM

Quote:
Original post by abaraba1
>>"Both of your solutions above appear.."

sorry, you lost me right there,
we cant discuss this if all you have to offer is your guesses and assumptions..


basically,
on all that what you said, im telling you - you're wrong

abaraba1 - lose the attitude. You should have learned from the responses to your first thread on this.

#12 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 22 September 2008 - 01:47 PM

>"lose the attitude"

what do you mean?
i simply had enough of people putting me down without even thinking!

..and what if turns out that the whole world was wrong?
..maybe i was supposed to give up from telling this to anyone?

because, for trying to tell you this, i got nothing but shit in return


thank you


#13 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 22 September 2008 - 01:56 PM

EasilyConfused,
>>"You keep referring to errors introduced by interpolation - what errors do you think interpolation introduces? I have two current projects that use the method outlined at gaffer.org and I can assure you that interpolation is not introducing any errors."

- and i can assure you that you're just lucky because your deltaTime < fixedTimeStep


>>"...what errors do you think interpolation introduces?"

- and what do you think interpolation accomplishes?
(whatever your answers is, i can tell you it works better WITHOUT IT)






WillC,
>>"A few points about this. Firstly ® is a registered trade mark sign"

- thats right,
but understanding of that one is not a requirement for 'this' algorithm to work.


>>"Obviously those are retorical questions.."

- rHetorical, eh?
if you continue to pretend that you know - you will never learn.




//-------------------------------------------------------------------

you should all understand,
- i made it very EASY for you to test it
- all you said so far are your *ASSUMPTIONS*


stop wasting more of my time, behave like scientist should - TEST IT!

Quote:
would anyone care to discuss this and actually confirm OR prove it wrong, im happy with either.



so, if you don't like me,
you dont need to say anything, this is a HARD-TALK - facts only, please!

[Edited by - abaraba1 on September 22, 2008 8:56:13 PM]

#14 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 22 September 2008 - 02:52 PM

let me just say that, while in the loop, we doing nothing more but this:

a.) calculate new positions
b.) render straight after, as soon as we can
->REPEAT


there is no magic here, its simple as that,
you simply just have to forget about the "interpolation" ..thats it
..and theres that bit about Max/Min number of iterations, but that has to do with 'accumulator' and 'temporal-interpolation'


..maybe its worth noting that you always look at the computer animation in - the past- ..so to say - you can not really 'keep-up' with a real time, you're always lag behind as much as it was last 'deltaTime', but this is important as much as it is that your wrist watch is off from the "real-time" a few seconds



Unfortunately, no one can be told what the 'temporal-interpolation' is. You have to see it for yourself.
This is your last chance. After this, there is no turning back.

#15 Numsgil   Members   -  Reputation: 501

Like
0Likes
Like

Posted 22 September 2008 - 03:04 PM

Quote:
Original post by abaraba1
WillC,
>>"A few points about this. Firstly ® is a registered trade mark sign"

- thats right,
but understanding of that one is not a requirement for 'this' algorithm to work.


>>"Obviously those are retorical questions.."

- rHetorical, eh?
if you continue to pretend that you know - you will never learn.


I think you're missing Will's point. He's not commenting on your algorithm, but on legal issues. ® means registed trademark. You probably meant ©opyright. But all a copyright gives you is legal protection if someone copies your idea verbatim (given your rather free form grammar, I don't think you have to worry about that :)). You need a software patent to protect the idea itself. Which, in the US anyway, isn't too hard to obtain, but it is expensive. I didn't look at your algorithm enough to say if it's patentable or not, but that's the only way to protect it. Other than a "please don't copy this idea, pretty please" clause ;)
Darwinbots - Artificial life simulation

#16 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 22 September 2008 - 03:58 PM

Numsgil,

ok, let me point all of the problems again, this time with your message as practical example:



problem 1.)
>>"He's not commenting on your algorithm.."

- my question is pretty clear, and for such important and simple algorithm i find it strange indeed that no one can offer any reasonable comment



problem 2.)
>>"You probably meant ©opyright."

- you making me repeat myself



problem 3.)
>>"You need a software patent to protect the idea itself. "
>>"Which, in the US anyway,isn't too hard to obtain, but it is expensive."

- why do you think i need such information?



problem 4.)
>>"I didn't look at your algorithm enough.."

- so, how then do you find appropriate to make any comments about it?




#17 Numsgil   Members   -  Reputation: 501

Like
0Likes
Like

Posted 22 September 2008 - 04:13 PM

I'm not commenting on your algorithm. I'm commenting on your commenting to Will's commenting on your understanding of trademarks/copyrights/patents. I sense you still do not understand this, and take our comments as somehow directed at your algorithm and being critical of it. You know what a copyright is, right? You understand that it has nothing to do with physics? Specifically we're talking about your legal disclaimer in this link. Where you claim you'll sue our pants off if we copy your idea. This is what you say: "Use of this algorithm in commercial products without my permission will be cheerfully taken to court." But you can't sue us without a patent. Well you can, but the judge'll throw it out the case.

Since you got me all riled up, I spent some effort to see what your algorithm is talking about. Method 1 and 2 are essentially identical since you're calling the step() function the same number of times, so my comments relate to both methods.

You're calling a step() function with no arguments. From which I can conclude that you're using a fixed timestep irregardless of the frame rate. In essence, during times of potential infinite spiraling, you just simulate 50ms instead of the proper 150ms (or whatever) and call it a day.

Meaning that the game will simulate smoothly but in slow motion. Sort of like what the old NES games did. I did something very similar (I frame locked the graphics to N physics updates) for Darwinbots, where the simulation slowdown doesn't matter since users don't interact with it in real time anyway.

It's a reasonable hack for a game, but it still doesn't address the core concern for all cases. Imagine the case of a networked game where we're just sending deltas every frame. If I have a faster computer, I could be several seconds or even minutes ahead of you in game time if/when you experience lag. I don't even want to think how screwed up the game would get in a state like that.

Another solution I played with but didn't get very far with was a stepless physics engine. Instead of stepping at discrete time intervals, I tried solving the equations of motion analytically and solving each collision at the exact moment it occurred between two bodies. After a collision you'd get new equations of motion and continue the simulation. It worked as long as there wasn't any rotation (since it's hard to solve object to object collisions involving rotations in an analytical way) and no drag (drag made the motion equations have exponent terms, which made solving the collision equations... difficult). It's still possible to go in to an infinite spiral, though, if you have enough objects and not enough CPU power. It's just less likely.

[Edited by - Numsgil on September 22, 2008 10:13:49 PM]
Darwinbots - Artificial life simulation

#18 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 22 September 2008 - 05:38 PM

>>"I'm not commenting on your algorithm. "

- Please... please, all i ask is that you do the opposite ..or nothing


this is very, very concrete and specific algorithm,
it is about complete replacement that solves THREE somewhat different problems that might have been affecting your game in possibly unknown ways

you simply have to REPLACE the old one with any of the two new ones and report how it works, if you will



i ask nothing more then you to put some effort into it if you want to discuss it, if you are not interested enough to do that, then please do not waste my time


experimental facts only, please!



>>"I sense you still do not understand this.."

- it is not required from you to be sensing anything, on the contrary i ask you to turn your brains on



i mean, it only takes about FIVE MINUTES to test it ..i don't understand, if you're too lazy for that, then just leave me be




thanks




//----------------------------------------------------------
i believe every criticism is constructive as long as you state your reasoning or otherwise show the logic of your conclusion, i even believe you can go as far and say that im stupid as long as you can explain it or at least try to reason your opinion with some arguments. ASSUMPTION is NOT ARGUMENT. Assumption is mother of all fukups.

[Edited by - abaraba1 on September 22, 2008 11:38:06 PM]

#19 Aardvajk   Crossbones+   -  Reputation: 5746

Like
0Likes
Like

Posted 22 September 2008 - 06:33 PM

Quote:
Original post by abaraba1
- and i can assure you that you're just lucky because your deltaTime < fixedTimeStep


The following from gaffer.org:

Quote:
From Fix Your Timestep
This code handles both undersampling and oversampling correctly which very is important. Undersampling is where the render framerate is lower that the physics framerate, eg. 20fps display when physics runs at 60fps. Oversampling is where you have an insanely high framerate (or you are viewing physics in slow motion) where one physics frame accumulates over several display updates. Note that the “sampling” here applies not to the physics steps, but to the renderer sampling state and drawing it on the screen.


In other words, the algorithm handles both the under- and over-sampling cases equally well as if the update time is less that the physics timestep, one physics step is accumulated over two frames.

Quote:

- and what do you think interpolation accomplishes?
(whatever your answers is, i can tell you it works better WITHOUT IT)


Third try [smile].

When your physics and rendering rates fall out of sync, you can get a situation where you get a repeating pattern of, say, two steps one frame, one the next, two next frame, one the next etc.

This leads to a visual stuttering that can look jerky. It has no actual affect on simulation speed or stability.

Interpolation addresses just this issue. By rendering a frame that is technically in between the last frame and current frame, based on using a scaling factor based on the remainder left in the accumulator, this "smooths" the motion and helps remove the stuttering.

I'm not trying to convince you - just trying to make sure this thread has correct information in for other browsers.

[EDIT] I'd suggest this thread is closed. I'll be taking no further part in it as I have serious concerns about the OP.

[Edited by - EasilyConfused on September 23, 2008 2:33:08 AM]

#20 abaraba1   Banned   -  Reputation: 100

Like
0Likes
Like

Posted 22 September 2008 - 07:37 PM

EasilyConfused,

>>"The following from gaffer.org:"

- ok, this time you have an argument, but its not YOURS

in other words,
you simply just choose to believe that instead of your own conclusions, what im telling you is: - dont believe, of course not! You simply have to *SEE* it for *YOURSELF*

[Homer Simpson's comment on religion: -"..and all they ask for is a little bit of blind fate"]


you made me repeat myself, but i dont mind as long as there is some argument there,
and i got used to it in the last TWO MONTHS.. basically i now mostly just copy/paste what i wrote a long time ago to many, many other people before



//=====================================================================
you think im crazy and arrogant?
can you explain why they spread wrong information on the PUBLIC FORUM, then get angry when i interfere to explain misunderstanding and DELETE most of the messages that explain whats going on..


ok forget everything,
how is this possible - they simply deleted last part of this tread after i was being called "idiot" and got attacked by probably same person with multiple nick-names.. what in the world is going on?

(as S.H.)
http://www.geocities.com/ze_aks/bullet/bn1-viewtopic.php.htm
http://www.geocities.com/ze_aks/bullet/bn2-viewtopic.php.htm

and here is original if there at all:
http://www.bulletphysics.com/Bullet/phpBB3/viewtopic.php?f=9&t=2638


maybe i should have mentioned earlier, i didnt want to, but you pulled it - gaffer actually deleted the whole conversation where he goes on and on how i "do not understand", then at the end... he just deleted everything.. and what you quoted me is WRONG, but dont believe me, of course not! ..see for yourself, if you will


crazy, eh?
..you've seen nothing yet,
and actually i hope you dont pull any more of these out..


be HONEST, tell me then,
on whose side do you think i am? and what do you think i want from you?

[Edited by - abaraba1 on September 23, 2008 2:37:28 AM]




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS