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;
}