2
\$\begingroup\$

I would think there should be an abundance of excellent articles answering this question, but my searches have come up completely empty.

I am developing an embedded graphics engine on a microcontroller which does not have an FPU or math co-processor.

I read somewhere before during my research that reasonably precise physics can be implemented without floating point math by using fixed point math.

How exactly does this work? What generally would be the programmatic behavior of a physics engine with some time step dt?

\$\endgroup\$
  • 1
    \$\begingroup\$ Never done it myself, but I don't see that much of a problem here. The formulas stay the same, just scale everything up to the precision you need. For example, if you have something moving with 0,2 meters per second, use 200 millimeters per second or even 200.000 micrometers per second. Just keep track of the units to avoid calculation mistakes. Also, be careful with over- and underflows and try to avoid mixing very large numbers with very small ones during multiplication and division. \$\endgroup\$ – wychmaster Jun 30 at 6:54
  • \$\begingroup\$ However, more complex operations like square roots, sine, cosine etc. might be a problem but I guess there are already a lot of approximation algorithms like this one for the sine (only read the title, but it seems to fit). \$\endgroup\$ – wychmaster Jun 30 at 7:00
  • \$\begingroup\$ Can you edit your question to clarify where you're run into trouble? A fixed point number is still just a number. So, anywhere you'd use a floating point data type, you replace it with a fixed point data type. It's unclear to me what aspect of this switch you need help with. \$\endgroup\$ – DMGregory Jun 30 at 10:16
4
\$\begingroup\$

TL;DR they work exactly the same; the difference comes from trade-offs like performance, value range and (sometimes) syntax.

It's is possible to simulate floating- or fixed-point math, you just have to write all logic yourself (or use library). The only limits are your creativity and resulting performance overhead.

Fixed-point math may be considered a subset of floating-point math, where exponent is constant. This leads to fewer instructions (no need to read exponent and do calculations on it) and smaller data types (no need to store exponent).

If your language of choice supports operator overloading, then syntax won't be too much different from floating-point universe: x * y is same thing in both worlds. Copy-pasting some premade physics engine and replacing data types it operates on might just work. In case you are less lucky with language, then I wish you patience, because turning every b*x + a into add(mul(b, x), a) is tedious task.

Next, because exponent is fixed, the possible range of fixed-point numbers is severely limited. It's not a problem for storing things like coordinates, because even in floating-point engines objects don't go too far from origin — but when they do, coordinates start to loose precision and physics becomes wonky, so game designers try to avoid that.

But for intermediate operations this loss of range matters. If numbers go out of range during fixed-point calculations, information will be lost. (Yes, you can go out of range with floating points too, but it's much harder to do so.) This issue can be mitigated by promoting values to bigger types during calculations, but it incurs further performance costs.

To avoid underflow and overflow issues, it's better to choose all units of measurements such that most variables (and constants) will be as close to 1.0 as possible. For instance, distance of x = 0.001 units may seem not too bad for int16 + int16 fixed-point data type, but calculating area x*x will blow out of range.

Using very small units of measurements stored as integers (as proposed in comments) is possible as well. Integer values may be considered special case of fixed-point without fractional part. In some calculations, using pure integers will result in even faster code.

As a side note, I presume it'll be impossible to get rid of fixed-point completely, because they have nice property of shrinking values by multiplication. You'll also would need them for all sorts of unit-less multipliers that must be compatible with any other unit type — imagine scaling object's size, weight and acceleration with same curve.

At last, it may be good idea to assign and display all values via conversion functions: meters(3) looks more readable than 3 * 0xFFFF and allows to easily change unit representation later, would the need arise. Again, some programming languages (C++) allow to introduce measurement units into type system to protect you from mistakes and even allow to define custom suffixes, so it will be possible to write previous example as 3m.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I'd quibble with your last point, about fixed point being fundamentally different from a suitable choice of unit. If I make a fixed point system in decimal (for ease of talking about it) where 1.0 = 1 m and with 9 fractional digits, I can equivalently think of it as a system with no fractional digits where 1 = 1 nm. Same digits in all my numbers, just a shift in where I place the decimal point. In binary it's a bit more complicated to talk about, since we don't get nice power-of-10 named units for each shift, but the math isn't fundamentally different. \$\endgroup\$ – DMGregory Jun 30 at 16:52
  • \$\begingroup\$ @DMGregory you are right. I meant it will be inconvenient to work with these, but on second thought, all values have to be assigned and displayed through conversion functions anyways. \$\endgroup\$ – Shadows In Rain Jun 30 at 18:36
  • \$\begingroup\$ That's right on the money! Thank you! \$\endgroup\$ – Connor Spangler Jul 1 at 2:15
1
\$\begingroup\$

I've been using FixedPoint (FxP) for last several years across multiple 8/16/32/64 bit platforms (mostly in Assembler).

The single most problematic issue with FxP is occasional overflow during multiplication. Very hard to reproduce and debug if it happens at 1 frame out of 1,000, especially in Assembler.

I would very strongly recommend doing initial prototyping in as high-level language as possible (even if you are targeting ASM). Just spend a weekend creating a reference floating-point functionality, save the ranges of all values into some global Min,Max variables and only then start refactoring it to work in FxP.

You might find you don't even need FxP - just 32-bit integer - as long as all computations are done in 32-bit integer space, then it doesn't matter.

Alternatively, a simple hack is to shift 8x (e.g. 24.8) - for most purposes it gives sufficient precision - but you must confirm your dataset will be fine with it (or adjust environment).

For things like Global Illumination (Radiosity Form Factors) - it's even possible to use 32-bit Integer approximation to form factors (double fp precision originally).

Can you double check if your target platform doesn't accidentally support intermediate results in higher precision ? Meaning while you can't access full 24-bit intermediate result (for 16-bit ops), internally the ALU will work with more bits than you have access to (via registers).

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.