• 12
• 14
• 13
• 10
• 11

# Integer spatial position and sub-periodic derivative epsilons

This topic is 2204 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi everyone

Okay, I don't really know if integer values and fixed point are so much used for otherwise typical "float" or "double" computing, nowadays, but I decided to use integer encoding for various reasons.
In particular, I'll use integer values to represent a spatial position (1 unit being 1/1024th of a meter, which is fine-grained enough for my purpose).

I ran into the following issue : if velocity and acceleration are to be integers too, and applied once per frame, then the velocity epsilon would be the spatial epsilon per frame period (with 1/32th of a second per frame, this gives 1/32 m/s, which is quite a lot), and the acceleration epsilon would be the velocity epsilon per frame period (1 m/s², which IS a lot).
And by 'a lot', I mean too much.
For my taste, at least.

At first, the only solutions I thought of were to use a better spatial precision (not really satisfying as I don't want to grow the size of position encoding too much), or to increase frame period (not satisfying at all).

Then, I had the idea to use the frame counter and some bit tricks to perform sub-periodic accumulations :
If velocity components were to be fixed points, of which an integer unit represents 1 pos epsilon per frame period, then the following bit means 1 pos epsilon every other frame, the 2nd bit after point means 1 pos epsilon 1 frame out of 4, and so on.

So here I am with a nice way to have sub-periodic epsilons for velocity and acceleration. With 8 bits after point on velocity and same on acceleration, I can get my velocity epsilon down to about 1 millimeter over eight seconds (much better) and my acceleration epsilon down to about 15 micrometers per second squared (much, much better).
This may not be "100% accurate", but I seek reproductibility above accuracy.
Only question left is : when... I mean... when? is 79 frames out of 256 ?
Currently, I use a front recognition on the lsb of the frame counter, mirror the bits, AND them with my fractional part of hopefully the same size, add +1 to the delta when the result is non-zero, and voilà, I get 79 frames out of 256, but I think the pattern is not "perfect".

For example, my algorithm gives the following pattern for a fractional part of 01100000b, when input increases by 1 (such as, say, a frame counter ) :
false, false, true, false, true, false, true, false ... and repeat.
that is, 3 times out of 8.
Good news is, that is correct : 1/4 + 1/8 = 3/8
Bad news is, I get 3 consecutive 'false' when a more regular pattern would show at most 2 'false' following each other.

Question : would someone out there think of a better way of accumulating the fractional part of the derivatives ?
other than storing 256x256 hand computed booleans, that is.

My (untested) code so far :
 // ************************************************************************* // Returns the 8-bit-inverted bit front of the 8 lsb of a value. // ************************************************************************* // Used to retrieve the inverted bit fronts of a frame counter, for tests needed by sub-frame accumulators with 8bit fractional parts : // integration of acceleration and velocity in particular. // Explanation : consider the first returned value in the algorithm below : 0x80, which is returned in half the total cases. // in binary, this return value is 10000000 // this will match (binary AND != 0) any fractional part of an 8-bit fixed point with a '1' right after its point, which reprensents 1/2. // for derivatives such as velocity and acceleration, such a fractional part represents half a "step" each frame. // if we interpret this as a step every two frames, we see that we just found the right trigger for the application of the delta : // it will indeed happen every other frame. // How does this scale to fractional parts with more than 1 bit set ? take a fractional part of 0x60 for example, // it represents 1/4 step per frame + 1/8 step per frame, i.e 3/8 steps per frame. // in other terms, this means we need to add one step on 3 frames out of 8. // 0x60 (01100000) will match against return values of this function of 0x40 (01000000) and 0x20 (00100000) // Returning one of those values, given an entry value incremented by 1 between each call, will happen in the following pattern : // false, false, true, false, true, false, true, false ... and repeat. // if the entry value of this function is the frame count, this will indeed happen 3 frames out of 8. // Note : This is not the "best" repartition : // we can see 3 consecutive 'false', when a more regular pattern would show at most 2 false following each other. // ... but this is not the worst repartition either. // ************************************************************************* uint8 getInvFront8(uint32 counter) { if (counter & 0x00000001) return 0x80; // happens every other value else if (counter & 0x00000002) return 0x40; // happens 1 time out of 2 when previous test was false, i.e 1 time out of 4 else if (counter & 0x00000004) return 0x20; // happens 1 time out of 2 when all previous tests were false, i.e 1 time out of 8 else if (counter & 0x00000008) return 0x10; // happens 1 time out of 16 else if (counter & 0x00000010) return 0x08; // happens 1 time out of 32 else if (counter & 0x00000020) return 0x04; // happens 1 time out of 64 else if (counter & 0x00000040) return 0x02; // happens 1 time out of 128 else if (counter & 0x00000080) return 0x01; // happens 1 time out of 256 else return 0; // happens 1 time out of 256 } // ************************************************************************* // Applies an acceleration to the inertial parameters of an entity (position and velocity) and compute the resulting position. // ************************************************************************* // This function is meant to be called once per entity for a frame with a constant period (typically 1/32th of a second) // This function was designed for use with integer position components and fixed point related derivatives : // integer part of a 8b-frac fixed point velocity component is meant to represent 1 position component epsilon per frame period. // (=> velocity epsilon is 1 pos epsilon per 8 seconds with a 1/32th second period) // integer part of a 8b-frac fixed point acceleration component is meant to represent 1 velocity component epsilon per frame period. // (=> accel epsilon is 1 vel epsilon per 8 seconds, with a 1/32th second period) // The trick for accumulating sub-periodic derivatives is to test the fractional part against the 8-bits-inverted bit front on the frame counter. // pos and vel are in-out parameters. // acc is in-only. // invFront8 is the inverted bit front from the frame counter (hopefully computed only once per frame). // ************************************************************************* void applyAccAndVelOverOneFrame(Position* pos, Velocity* vel, const Accel* acc, uint8 invFront8) { // Each Frame, adds integer part (n>>8) of each component of the acceleration vector to // the respective components of the velocity vector. // Adds 1 more if fractional part (8 lsb) of an acceleration component matches // the current 8-bits-inverted bit front on the frame counter. // int32 effAccX = acc->x >> 8; vel->x += (invFront8 & acc->x) ? effAccX+1 : effAccX; int32 effAccY = acc->y >> 8; vel->y += (invFront8 & acc->y) ? effAccY+1 : effAccY; int32 effAccZ = acc->z >> 8; vel->z += (invFront8 & acc->z) ? effAccZ+1 : effAccZ; // Each Frame, adds integer part (n>>8) of each component of the resulting velocity vector to // the respective components of the position vector. // Adds 1 more if fractional part (8 lsb) of a velocity component matches // the current 8-bits-inverted bit front on the frame counter. // int32 effVelX = vel->x >> 8; pos->x += (invFront8 & vel->x) ? effVelX+1 : effVelX; int32 effVelY = vel->y >> 8; pos->y += (invFront8 & vel->y) ? effVelY+1 : effVelY; int32 effVelZ = vel->z >> 8; pos->z += (invFront8 & vel->z) ? effVelZ+1 : effVelZ; } 

##### Share on other sites

Question : would someone out there think of a better way of accumulating the fractional part of the derivatives ?
other than storing 256x256 hand computed booleans, that is.

After a discussion with a collegue of mine, a possible alternative solution would be to indeed store those 256x256 booleans. Crazy, hmm ? Thing is, I even had trouble to find the values for filling this table (hence my "hand computed" pun in quote), so he came with the solution for pre-computing it : with the same kind of algorithm as a line rasterizer, on which fronts (increases of the line "y") are trues and non-fronts (same "y" as previous pixel) are falses.
Would this be worth it ? 65KB is not a small amount of RAM for an otherwise quite inexpensive approximation. I don't really know.
Table could also be packed in 256 x 256 bits, at the expense of a longer check each time (6 times a frame, per entity...).

Any help still appreciated

##### Share on other sites
I ran into the following issue : if velocity and acceleration are to be integers too, and applied once per frame, then the velocity epsilon would be the spatial epsilon per frame period.
Not necessarily - your velocity and acceleration can be in different units if you liked. e.g. if position was quantised to whole metres and time was quantised to milliseconds, velocity could still be quantized to something completely differnet like centimetres/second.int pos_m = 42; // start at 42 metres int delta_time_ms = 100;// 100 miliseconds elapsed, 0.1s int vel_cm_s = 1000;// 1000cm/s == 10m/s ==0.01m/milisecond int cm_per_m = 100; int ms_per_s = 1000; int pos_cm = pos_m*cm_per_m; int new_pos_m = (pos_cm + (int64)vel_cm_s * delta_time_ms / ms_per_s) / cm_per_m;// 42 + 10m/s*0.1s == 43 == (42*100 + 1000*100/1000)/100Though either way, this seems like a lot more work than just using float

##### Share on other sites

Not necessarily - your velocity and acceleration can be in different units if you liked. e.g. if position was quantised to whole metres and time was quantised to milliseconds, velocity could still be quantized to something completely differnet like centimetres/second.

Well, your solution may indeed store velocities of any precision. But they won't have any effect on the position when
|velocity*dt| < anyprecisionconversionquotientyoumightthinkof
because then, the integer division of velocity*dt by your quotient (cm_per_m in your example) will be 0 :
 int vel_cm_s = 800; // as big as 800 times the velocity epsilon is still too small to have any effect, as shown by : // [...] int new_pos_m = (pos_cm + (int64)vel_cm_s * delta_time_ms / ms_per_s) / cm_per_m; // (42*100 + 800*100/1000)/100 = 4280/100 = 42 ==> your "mobile" is idle // 1000 was in fact the "smallest" observable velocity. Moreover, dt was quite large. 
Which means you still have a minimal observable non-null velocity of PositionPrecision/dt.

Though either way, this seems like a lot more work than just using float

Not necessarily, althought I swore to myself not to go into a discussion about the merits of integers in this thread