skipping certain number of frames on a timeline

Question

hi, i have a mathematical problem which is a bit hard to describe, but i'll give it a try anyway.

in a timeline, i have a number of frames, of which i want to skip a certain number of frames, which should be evenly distributed along the timeline.

for example i have 10 frames and i want to skip 5, then the solution is easy: we skip every second frame. 10/5 = 2

if (frame%2 == 0)
    skip();

but what if the above division does result in a floating number?

for example in 44 frames i want to skip 15 times. how can i determine the 15 frames which should be skipped?

bascially i am looking for an algorithm that distributes that 15 frames as evenly as possible along the 44 frames. it will probably look like something like skipping after 2 and then after 3 frames alternately.

thanks!

Answer 1

You can obviously not always do it really evenly in case the number of frames you want to skip is not a divisor of the total number of frames. So if it is important to always skip at least the number of frames you want, perform a floor on the division (totalFrames/framesToSkip).

Having said that, you can apply the same trick as you proposed.

if (totalFrames % floor(totalFrames/framesToSkip) == 0)
    skip();

Note that in the case of 44 and 15 you skip much more than 15. The other posibility is to ceil instead of floor, in that case you wont skip 15 frames but 14 frames.

Yet another solution is to do a round to the nearest integer, this is a better approximation, however, you sometimes skip more than wished and sometimes less than wished but on average you have better results

Answer 2

You could keep an additional floating point value, t, that corresponds to the next frame to skip, and update it every time you skip. Like this:

int frame_num = 44; 
int skips_num = 15; 
double dt =((double)(frame_num))/skips_num;
double t = 0.0;
...
// then, in your loop
if (frame == (int)t) {  
  skip();   
  t += dt; 
}

Answer 3

I set off to write a solution that improves on Igor's, but at the end the only improvement I really found was to explicitly state that round(t) should be used instead of (int)t. So here's Igor's solution again (with some variable names changed so it is more obvious and using round function).

int frame_num = 44; 
int skips_num = 15; 
double frames_between_skips =((double)(frame_num))/skips_num;
double next_skip = 0.0;
...
// then, in your loop
if (current_frame == round(next_skip)) {  
  skip();   
  next_skip += frames_between_skips; 
}

Using round(t) will make it be the most fair and try to drop the frame (int) that is closest to the ideal drop frame (double) while keeping the full precision timer (next_skip).

Couple of notes

• take care if the frame starts with 0 or with 1 and adjust accordingly,
• take care that frame_num is not > skips_num (if it is make sure you increase next_skip by more than a frame each time a frame is dropped, otherwise you'll stop increasing the next_skip and no more frames will be dropped)

Answer 4

It strikes me that the problem of mixing skips in with non-skips is a bit like the problem of mixing steps that go diagonally downwards with steps that go straight across when drawing a line with pixels. The line-drawing problem is solved in great detail at http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm