Size matters, and precision too

Sorry for dredging up the space game again, but I completely forgot about my blog post until 30 minutes before this went live! To make it up to you, I have peppered this article with Douglas Adams quotes.

Double note: I am NOT working on my space game again!

Space is big. Really big. You just won’t believe how vastly, hugely, mind-bogglingly big it is. I mean, you may think it’s a long way down the road to the chemist’s, but that’s just peanuts to space. – Douglas Adams

With my space game, I hoped to (for the computers that can handle it) offer an entire galaxy to explore. Most of the area would go unexplored, as the vast distance between stars alone is enough to make the heart jump, but I wanted the far away stars and black holes to still have their effect felt in across the galaxy.

This brings a problem of precision.

According to Wolfram Alpha, the width of our galaxy is about 9.5×10^20 meters. This is a lot, as you can imagine. Luckily, a double-precision floating point is more than capable of storing that number. What it cannot do, unfortunately, is store many numbers around that number.

The double precision floating point format has an 11 bit exponent and a 53-bit significand. The significand is essentially the number of bits of precision any number can use. This is about 15 decimal places. Any number that requires more than 15 significant digits will suffer from rounding errors. At the edge of the galaxy you would need a 70 bit significand (log2(9.5*10^20) = ~69.68) to represent a position at 1 meter accuracy. Ideally I would like centimeter accuracy to better deal with movement that takes place close to the camera and for that kind of accuracy I would need a 79 bit significand. With a double, the position would be rounded to the nearest 130,000 meters. That might be ok for large celestial bodies like the sun, but a 300×200 meter ship will have noticeable problems moving about.

So what can we do? There are a couple of options:

All you really need to know for the moment is that the universe is a lot more complicated than you might think, even if you start from a position of thinking it’s pretty damn complicated in the first place. – Douglas Adams

A quadruple precision floating point value is simply a turbo-charged double. It has a significand of 113 bits, which will give us a precision of around 114 femtometres at the edge of the universe. This seems like a bit of an overkill really. Each place value will take up 48 bytes with a quad. So a galaxy full of stars will be about 14.4GB of positions alone. On top of that, I would have to write the implementation myself, as to my knowledge Unity does not support quad positions in their Transform component.

Combining single and double precision

He was wrong to think he could now forget that the big, hard, oily, dirty, rainbow-hung Earth on which he lived was a microscopic dot on a microscopic dot lost in the unimaginable infinity of the Universe. – Douglas Adams

This is very similar to the Quad method, except instead we’re combining 64bit and 32bit floating point values to give us a significand of 53 + 23 = 76 bits. An accuracy of 1.5cm at the edge of the galaxy. With this representation, a galaxy full of stars will have cut down to 10.8GB, which is not something to sneeze at, but I’ll have to handle the math related to the compound values and I’m wasting the exponent bits in my single precision item.

Use an integer

The story so far:

In the beginning the Universe was created. This has made a lot of people very angry and been widely regarded as a bad move. – Douglas Adams

An odd decision for a system which wants decimal accuracy, but if I’ve decided the least acceptable positional change is 1cm then I can represent that as my smallest integral unit. I’d need an 80-bit integer (represented by combining a 64 bit integer and a 16-bit integer), which is still an ugly data type, but it’s precise and the accuracy is guaranteed to not change. Unfortunately I’d have to physically stop the player from exiting this range, and I thought we were past the days of invisible barriers. Once again there is no Unity support, but with this data type the maths will be slightly faster, and the overall size of a universe of stars would be 9GB.

Shorten the largest galaxy size

If life is going to exist in a Universe of this size, then the one thing it cannot afford to have is a sense of proportion. – Douglas Adams

A double precision floating point will support a 1 cm resolution up to a distance of 9×10^13, or about 1/10,000,000th of our galaxy. Our galaxy has approximately 300,000,000 stars. 30 stars would fit in this restricted size, which isn’t much for a space exploration game.

So what about integers? Using the same number of bits, an integer can represent 1.8×10^16 meters. This gives us 1/10,000th of a galaxy, and roughly 30,000 stars. This is better for space exploration, and I’m confident that a galaxy any larger has a very low chance of being explored. 30,000 stars with 64-bit integer positions would take up 720kb of memory.

But then there’s still the problem of invisible barriers. It’s possible that the player might hit the 1.8×10^16 meters point, which is only 1.9 light years, particularly since they’ll start in the center.

Offset from the player’s location

“Go to it,” it said, “and good luck.”

It was cross-referenced to the entry concerning the size of the Universe and the ways of coping with that. – Douglas Adams

If a floating point number’s precision reduces as the number increases, why not make that number the distance from the player? As the object is further and further from the player, its accuracy becomes less important, leaving an area of extremely high accuracy centred around the player, with lower accuracy reserved for the larger objects still being rendered, which are so far away that a 130km jump in place looks negligible.

With this system you’d only really need the precision of a float, which would work wonderfully as I’m already using them. Fortunately the largest size of a single-precision float is 3.4×10^38, due to the size of its exponent, which gives us plenty of room to play with. The accuracy at the edge of the galaxy (4.25×10^20) from the origin is 42,500,000,000,000m. This is a huge number, but remember we won’t render objects that far from the player, that’s the greatest distance an item can be (roughly) from the player. Realistically, the most stars we would probably want to render near the player would be ~2 (I intended to turn distant but bright celestial objects into a dynamically textured skybox). The second closest star to the sun is Sirius, which is 8×10^16 metres away. At this distance, the accuracy will be ~800,000,000m, which is less than its radius (and at that distance I doubt that length would be larger than one or two pixels).

On top of that, this is easy in Unity. The floating point transforms can refer instead to their offset position from a parent, but we would have to take care not to introduce rounding errors as we move.

The biggest downside from this system comes from the fact that you would periodically need to recalculate every celestial body’s offset from the player’s by summing the difference between the player’s current position and the position the player was at the last time the offsets were recalculated, but that would only really need doing once a minute or so, depending on player speed, and you can offload that to a low-priority thread. That’s not bad, compared to 15GB galaxies or invisible walls or low-precision close to the player.

I haven’t implemented it though, so it’s still all a big what-if. I wanted to re-evaluate how I use octrees so that instead of a spatial measure, they use the celestial object’s visibility to organise themselves (so using various “tiers” depending on brightness, allowing only a certain number of items in certain tiers), and this would be the perfect time to make that.