13
\$\begingroup\$

Just like it was demonstrated with games like dungeon siege and KSP, a large enough level will start to have glitches because of how floating point works. You can't add 1e-20 to 1e20 without losing accuracy.

If I choose to limit the size of my level, how do I calculate the minimum speed my object can move at until it begins to be choppy ?

\$\endgroup\$
26
\$\begingroup\$

A 32-bit float has a 23 bit mantissa.

That means each number is represented as 1.xxx xxx xxx xxx xxx xxx xxx xx times some power of 2, where each x is a binary digit, either 0 or 1. (With the exception of extremely small denormalized numbers less than \$2^{-126}\$ - they start with 0. instead of 1., but I'll ignore them for what follows)

So in the range from \$2^i\$ and \$2^{(i+1)}\$, you can represent any number within an accuracy of \$\pm 2^{(i - 24)}\$

As an example, for i = 0, the smallest number in this range is (2^0) * 1 = 1. The next smallest number is (2^0) * (1 + 2^-23). If you wanted to represent 1 + 2^-24, you'll have to round up or down, for an error of 2^-24 either way.

In this range:                You get accuracy within:
-----------------------------------------------
         0.25   -     0.5    2^-26 = 1.490 116 119 384 77 E-08
         0.5    -     1      2^-25 = 2.980 232 238 769 53 E-08
         1     -      2      2^-24 = 5.960 464 477 539 06 E-08
         2     -      4      2^-23 = 1.192 092 895 507 81 E-07
         4     -      8      2^-22 = 2.384 185 791 015 62 E-07
         8     -     16      2^-21 = 4.768 371 582 031 25 E-07
        16     -     32      2^-20 = 9.536 743 164 062 5  E-07
        32     -     64      2^-19 = 1.907 348 632 812 5  E-06
        64     -    128      2^-18 = 0.000 003 814 697 265 625
       128    -     256      2^-17 = 0.000 007 629 394 531 25
       256    -     512      2^-16 = 0.000 015 258 789 062 5
       512    -   1 024      2^-15 = 0.000 030 517 578 125
     1 024    -   2 048      2^-14 = 0.000 061 035 156 25
     2 048    -   4 096      2^-13 = 0.000 122 070 312 5
     4 096    -   8 192      2^-12 = 0.000 244 140 625
     8 192   -   16 384      2^-11 = 0.000 488 281 25
    16 384   -   32 768      2^-10 = 0.000 976 562 5
    32 768   -   65 536      2^-9  = 0.001 953 125
    65 536   -  131 072      2^-8  = 0.003 906 25
   131 072   -  262 144      2^-7  = 0.007 812 5
   262 144   -  524 288      2^-6  = 0.015 625
   524 288 -  1 048 576      2^-5  = 0.031 25
 1 048 576 -  2 097 152      2^-4  = 0.062 5
 2 097 152 -  4 194 304      2^-3  = 0.125
 4 194 304 -  8 388 608      2^-2  = 0.25
 8 388 608 - 16 777 216      2^-1  = 0.5
16 777 216 - 33 554 432      2^0   = 1

So if your units are metres, you'll lose millimetre precision around the 16 484 - 32 768 band (about 16-33 km from the origin).

It's commonly believed you can work around this by using a different base unit, but that's not really true, since it's relative precision that matters.

  • If we use centimetres as our unit, we lose millimetre precision at the 1 048 576-2 097 152 band (10-21 km from the origin)

  • If we use hectametres as our unit, we lose millimetre precision at the 128-256 band (13-26 km from the origin)

...so changing the unit over four orders of magnitude still ends up with a loss of millimetre precision somewhere in the range of tens of kilometers. All we're shifting is where exactly in that band it hits (due to the mismatch between base-10 and base-2 numbering) not drastically extending our playable area.

Exactly how much inaccuracy your game can tolerate will depend on details of your gameplay, physics simulation, entity size/draw distances, rendering resolution, etc. so it's tricky to set an exact cutoff. It may be your rendering looks fine 50 km from the origin, but your bullets are teleporting through walls, or a sensitive gameplay script goes haywire. Or you may find the game plays fine, but everything has a barely-perceptible vibration from inaccuracies in the camera transform.

If you know the level of accuracy you need (say, a span of 0.01 units maps to about 1 px at your typical viewing/interaction distance, and any smaller offset is invisible), you can use the table above to find where you lose that accuracy, and step back a few orders of magnitude for safety in case of lossy operations.

But if you're thinking about huge distances at all, it may be better to sidestep all of this by recentering your world as the player moves around. You choose a conservatively small square or cube-shaped region around the origin. Whenever the player moves outside this region, translate them, and everything in the world, back by half the width of this region, keeping the player inside. Since everything moves together, your player won't see a change. Inaccuracies can still happen in distant parts of the world, but they're generally much less noticeable there than happening right under your feet, and you're guaranteed to always have high precision available near the player.

\$\endgroup\$
  • \$\begingroup\$ Recentering is definitely the way to go! \$\endgroup\$ – Floris May 24 '14 at 4:47
  • 1
    \$\begingroup\$ What about using fixed point coordinates? Maybe with 64 bit integers if necessary? \$\endgroup\$ – API-Beast May 24 '14 at 6:35
  • \$\begingroup\$ the question is, how big that re-centered region can be ? if for example in my game I want to shoot at a high distance with a strong zoom, do I absolutely need to use double or is float enough? isn't it better to recenter according to a quad tree or some tile algorithm ? \$\endgroup\$ – jokoon May 24 '14 at 7:30
  • \$\begingroup\$ It will depend on the numerical stability of the algorithms employed by your rendering and physics systems - so for a given codebase/engine, the only way to know for sure is try a test scene. We can use the table to estimate maximum accuracy (eg. A camera 16 km away from an object will tend to see at least millimetre-sized errors, so your zoom should be wide enough to keep those smaller than a pixel - if the zoom needs to be tighter for your game then doubles or some clever math may be required), but a chain of lossy operations can run into problems well before this hypothetical limit. \$\endgroup\$ – DMGregory May 24 '14 at 11:45
  • \$\begingroup\$ I still am wondering what does it mean to recenter the world for a graphical API. If I have a big chunk of instanced (or not instanced) geometry, is it still safe to do it? I guess it means translating ALL transforms, but if I do this several times, isn't there a risk of floating point precision loss? \$\endgroup\$ – jokoon Apr 6 '18 at 9:46
3
\$\begingroup\$

It's hard to answer as it depends on the scale of your physics: What is the acceptable minimum movement speed that needs to NOT be rounded off to zero?

If you need a large world and consistent physics it's better to use a fixed points class.

For example, shooting a cannon ball from anywhere in the world will give you the same result and a 64bit fixed point (32.32) gives you a huge amount of precision and more than anything perceivable in most games. If your unit is 1 meter you're still at 232 picometers precision 2147483km away from the origin.

You can still do the local physics in floating points within the local cell to save on programming work and use an off-the-shelf physics engine. It will still be reasonably consistent for all practical purposes.

As a bonus broad phase and AABB tend to be faster in fixed point due to FPU latency. It's also faster to convert a fixed point to an octree (or quadtree) index as you can do simple bit masking.

Those operations do not benefit as much from SIMD instructions and pipelining which would normally hide FPU latency.

You can convert the positions to floating point AFTER subtracting the camera's position in fixed point to render everything, avoiding floating point issues in a large world and still using a regular renderer using floating points.

\$\endgroup\$
-2
\$\begingroup\$

You can avoid it altogether by multiplication.
Instead of working with floats, just multiply them by 10^(x), store them, and when needed multiply again by 10^(-x).
From that it depends on what type of int you want to use.

\$\endgroup\$
  • 1
    \$\begingroup\$ This doesn't avoid the problem. A fixed-point format still has finite precision and range - the greater the range, the lower the precision (based on where you put that fixed decimal point) - so the decision of "how big can I make a level without visible rounding errors" still applies. \$\endgroup\$ – DMGregory May 24 '14 at 3:44
  • 3
    \$\begingroup\$ Moreover, base-10 is not very practical. Fixed-point numbers work a lot better when you split the integer in terms of bits (consider unsigned 26.6 -- the fractional component is the lower 6-bits (1.0/64.0 * x&63) and the integral part is simply x>>6). That is much simpler to implement than raising something to a power of ten. \$\endgroup\$ – Andon M. Coleman May 24 '14 at 4:35

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.