Size does matter - and precision too.
ooh matron double precision single precision float double precision size data types
With Pigment, I hope to (for the computers that can handle it) offer an entire galaxy to explore. Most of the area will go unexplored, as the vast distance between stars alone is enough to make the heart jump, but I want 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 rough width of our galaxy is approximately 9.5x10^20 meters. This is quite 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 approximately 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 300x200 meter ship will have some considerable problems moving about.
So what can we do? There are a couple of options:
Use a Quad
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 position value will take up 48 bytes with a quad. So a galaxy full of stars will be approximately 14.4GB of positions alone. On top of that, I would have to write my own implementation, as to my knowledge C# does not include its own native version, nor does HLSL - so I would have to add additional functions to my shaders for working with the larger data type, and I'm not even sure if it'll even accept a world coordinate that large. Additionally all of my code currently uses the SlimDX Vector3 class for position, as it's a handy tool for vector maths. I'm not adverse to writing my own implementation of those functions, but I'd rather not waste the time when there's a better solution.
Use a combination of Single and Double precision.
This is very similar to the Quad method, except instead of using a combination of 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.
An odd decision for a system which wants decimal accuracy, but if I've decided the minimum acceptable positional change is 1cm then that can be represented as my minimum integral unit. I'd need an 80-bit integer (represented by a combination of a 64 bit integer and a 16-bit integer), which is still an ugly datatype, 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 passed the days of invisible barriers. I would need to pad data sent to the GPU to 128bits, but with this datatype the math will be slightly faster, and the overall size of a universe of stars would be 9GB.
Shorten the maximum galaxy size
A double precision floating point will support a 1cm resolution up to a distance of 9x10^13, or approximately 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.8x10^16 meters. This gives us 1/10,000th of a galaxy, and roughly 30,000 stars. This is much better for space exploration, and we can be fairly sure 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 very feasible that the player might hit 1.8x10^16 meters, which is only 1.9 lightyears, particularly since they'll start in the center.
Offset from the player's location
If the precision of a floating point number 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 position looks negligeable.
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 maximum size of a single-precision float is 3.4x10^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.25x10^20) from the origin is 42,500,000,000,000m. This is a huge number, but remember we won't be rendering objects that far from the player, that's the maximum distance an item can be (roughly) from the player. Realistically, the most stars we would probably want to be rendering near the player would be ~2 (I intend to turn distant but bright celestial objects into a dynamically textured skybox). The 2nd closest star to the sun is Sirius, which is 8x10^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 much larger than one or two pixels).
The biggest downside from this system comes from the fact that you would periodically need to recalculate every celestial body's position 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 positions were recalculated, but that would only really need doing once a minute or so, depending on player speed. That's not too bad really, compared to 15GB galaxies or invisible walls or low-precision close to the player.
I haven't yet implemented it though, so it's still all pending. I want to re-evaluate how I use octrees so that instead of a spatial measure, they use the visibility of the celestial object to organise the objects (so using various "tiers" depending on visibility, allowing only a certain number of items in certain tiers), and this would be the perfect time to implement that.