For up to the size of a solar system doubles work fine, and rendeirng is usually alos no thta much a problem, since a spaceship is kinda large, your near frustrum can be really large as well.
Here is my take on this problem, it is not really different from the others but I would like to explain why.
I think it is important to consider the problem of the coordinate system as a distinct problem from the partitioning one. There are many ways to partition the space and all have their advantages and disadvantages but there are not many ways to think about the coordinates.
The coordinates:
By putting it on a computer, we are trying to discretize space but give the illusion of a continuous (gigantic) universe. So our main concern is the size of our discretization. Anything too big and the player will notice something fishy.
The problem (and blessing) with floating point arithmetic (floats and doubles) is that the accuracy is spread evenly on a relative basis. Meaning for numbers of the order of 10^-30, we have rounding errors of the same order (~10^-40, don’t quote me on these figures) while number of the order of 10^40 give us rounding errors of the order of 10^30. These rounding errors basically represent the size of the tiles in our grid we use for our discretization.
This means that with floating points our grid is concentrated at 0 and grow into huge tiles as we move towards infinity.
Now, on the other hand, if we look at integer arithmetic, we have rounding error evenly spread on a absolute basis. Each tile is exactly of size one regardless of where we are in the range.
Now, enough with the math… Here is how I think about the coordinate problem. First, determine how much accuracy you need to give the illusion of continuous space. (e.g. floating point in the range of [-100, 100] would look reasonable). Then encode anything bigger into integer arithmetic, such as int, long or the BigInteger class if you feel big! This allows you to compute the world coordinates as (integer part)*(100 or whatever range used) + (floating point part).
Encoding coordinates this way allows you to keep the accuracy you need for any object regardless of there position. If you use BigInteger, you can have coordinates as big as you have memory (please don’t do that… They slow down the bigger they get!).
Now this is completely equivalent with partitioning the space into quadrants and having local coordinates (as floats) within the quadrants since the index of your quadrants will give you the integer part. In fact, partitioning in quadrants will always take less memory if you have at least one entity in each quadrant since the integer part is reused across several entities.
The partitioning and range queries:
It important to keep JME’s coordinates smallish because of the lose of accuracy mentioned above. This is why we are interested in expressing the near entities in camera coordinates (or close to). We can, however, store our ships and stations in some other form as long as we can query near objects efficiently.
I took the time to talk about the coordinates to highlight that we are really discussing two different problems. The coordinate problem is not flexible. Though, the implementation is very flexible. As long as you can theoretically recreate the huge integer part and the floating point part then we are dealing with equivalent things.
The naive way: Have each entity carry with them an extra integer. If a int or a long is good enough then this is a valid solution. You can use the usual space partitioning data structure to be able to answer range queries efficiently. If on the other hand, you need more (e.g. BigInteger) then this is probably not the best approach.
The grid: As mentioned above, you have the index of your quadrants (I use the word quadrant very loosely, sorry) to get back the integer part and the local position as the floating point part. This would allow us to generate the integer part and the float if we wanted to.
Many adaptations: You can then start looking at the many partitioning data structures and think of ways to adapt them into this form of local coordinate. An oct-tree like adaptation would look a lot like the grid implementation except you take advantage of the fact that not all quadrants are filled.
All implementations will have their strengths and weaknesses. It is not clear what is best and will depend really on your setting (range, density, etc.) The best would be to be capable of answering range queries without ever generating the huge integer.
(Aside)
All the implementation above will likely have redundant information (cluster of objects such as solar systems will cause that). The one best way (in terms of data compression) to store the integer for each entity is by encoding all integer parts into a prefix tree (Trie) and having the entites at the leaves. This guarantees you that your coordinates will be encoded in the smallest possible way! (perfect compression!) Any implementation that saves memory is loosely equivalent to a Trie with some nodes with too many children.
This, however cool, will not make your implementation any faster. This will most likely slow everything down!
edit:
TL;DR To keep coordinates accurate, there is only one conceptual way of doing it. In practice, there many ways of implementing it.
edit2:
I am wrong about the perfect compression thing sorry 
You would need to recode the integers (hoffman coding will do that ‘perfectly’) but with out recoding, the Trie is the best compression.
3 Likes