Neo Geo Dev: Fixed Point Numbers

When I was a freshman (or so) in high-school, our computer lab had just graduated from a time-share terminal to the next-door university to the Apple II. A kid (Ray Tobey) in the next grade up started to code a project to submit to a Byte Magazine game contest. The due date came and went, but he carried on in every moment of his free time. Long story short, this game became SkyFox of which Woz said "consider this flight simulator as the finest Apple game ever done." From Ray, I learned the value of using continued fraction approximations to trig functions using only integer math. Later, this became useful when I had to implement image rotation in a scan generator for a scanning electron microscope.

Multiplying without having a larger intermediate is much more complex than the article states. You have to use the commutative property of multiplication and split the whole and decimal parts of each number out, otherwise you're stuck with single digit whole numbers or only multiplying fractions.

So you'd take

  A.a * B.b and split it into A*B + A*b + a*B + a*b

Or

    out = ((A >> fixedbits) * (B >> fixedbits) << fixedbits)
        + ((A >> fixedbits) * b)
        + ((B >> fixedbits) * a)
        + ((a * b) >> fixedbits);

If you can get away with a little less precision and smaller whole numbers, you can avoid some of the multiplications by just doing this, which is quite common:

    (A.a >> (fixedbits / 2)) * (B.b >> (fixedbits / 2))

I always felt when learning about this stuff that people - pedagogically - make fixed point seem more complicated than it is.

Since this article is talking about more precisely positioning sprites in a 2D world, it could practically be a one-liner: "instead of tracking positions/velocities in pixels, track them in half pixels". Everything falls out of that intuition.

It's worth saying the original Playstation was entirely fixed point. You can go surprisingly far with it.

https://en.wikipedia.org/wiki/Fixed-point_arithmetic#Softwar...

I spent so much of the early stage of my career doing early mobile stuff I practically still think in fixed point, and always have to adjust to floats, for example, fixed point results can be compared exactly while with floats that is not a great idea. TeX uses fixed point entirely because it was reproducible across machines in an era where floating point was not.

Hedgewars uses fixed point due to inconsistencies in floating point implementations breaking deterministic lockstep. 0AD and Spring: RTS has similar issues although I think both use streflop now.

This sort of thing is ordinary for consoles without floating point numbers. It's easy to do in software with integers, but sometimes hardware acceleration will use it too.

The SNES and GBA both supported affine transformations, where the elements of the multiplication matrix are fixed point numbers. The Playstation's geometry coprocessor (GTE) used fixed point matrices with quite low 16 bit precision. An emulator feature called PGXP is able to perform these calculations at higher precision.

On the PC side, most developers stopped predominantly using fixed point for high performance code somewhere in the Pentium 1-3 era. For 486 class systems it was still pretty useful.

Other than on retro systems, fixed point is still useful in smaller microcontrollers.

On the Amiga and Atari, based on the Motorial 68000 like the NeoGeo, all 3D games used fixed point arithmetic.

At that time, such games were written in assembler, and you had to be very careful to place the instructions for scaling and descaling in the right places, not only to get the final result in the right units (i.e., screen coordinates), but also in intermediate calculations to preserve precision.

Is it possible to get rid of all the macros TO_FIXED, FROM_FIXED, mult, etc and replace them with a class with the correct constructors / operator overloads?

Then your code doesn't ever need to be aware of the special fixed point math and horrible syntax everywhere and everything just works?

FYI, the multiply assert isn't guaranteed to work and can be compiled out by a sufficiently smart compiler. Overflow of signed values is UB, the compiler can assume that UB is impossible, therefore the expression in the if resolves to false.

When I see a snippet like this

  int temp = a * b;
  ngassert(
        abs(temp) >= abs(a),
        "overflow!"
  );

I wonder what stops the compiler from optimizing away the assert, as it's clearly based on an undefined behavior.

Fixed point should really be used way more often than it is. It's much safer, for one thing, and less mysterious. But because C lacks first-class support for fixed point, the whole world has become flopsy.

Besides all the given examples, this was also quite common in J2ME games, given the limitations of the environment, and hardware differences across phones.

Nit to the author. Decimal point. Decimal digits. Actually binary point and binary digits.

"If you wan't"