A Real-Time Procedural Universe, Part Three: Matters of Scale
by Sean O'Neil 
July 12, 2002 Page 1 of 3
In Parts One and Two of this series, I explained how to dynamically generate and render planetary bodies at real-time speeds using a function based on fractal Brownian motion (fBm) paired with a spherical ROAM algorithm. This article will concentrate on how to scale that up to a star system or even an entire galaxy. It will also discuss some of the problems you will run into with scale and frame of reference, and different ways to solve them.
Problems of Scale: One Planet
The main problem with trying to model and render a really large game world is precision. A 32-bit float has a maximum of 6 significant digits of accuracy, and a 64-bit double has a maximum of 15. To put this into the correct frame of reference, if the smallest unit you care about keeping track of is a millimeter, you start to lose accuracy around 1,000 km with floats and around 1 trillion km with doubles.
Given the fact that the Earth's radius is close to 6,378 km, a 32-bit float isn't even enough to model and render one Earth-sized planet accurately. But losing precision at the millimeter, and possibly centimeter level, with the vertices in a planet's model is not a significant concern. You will run into a number of much bigger problems trying to model and render such a large game world. One possible solution is to use 64-bit doubles everywhere, but this is a slow and rather clumsy way to solve these problems.
When I first rendered my planet centered at the origin of my 3D map, I noticed two problems right away. The first was that placing the far clipping plane out at a decent distance made my Z-buffer useless. The second problem was that at a certain distance, the planet would disappear regardless of what I set the far clipping plane to. The second problem seemed to be driver or card-specific because each video card I tested it on ran into the problem at different distances. Both problems had something to do with very large numbers being used in the transformation matrices.
I solved both of these problems by scaling down the size and the distance of planetary bodies by modifying the model matrix. Using a defined constant for the desired far clipping plane, which I'll call FCP for now, I exponentially scale down the distance so that everything past FCP/2 (out to infinity) is scaled down to fall between FCP/2 and FCP. To make the size of the planetary body appear accurate, all you have to do is scale the size by the same factor you scale the distance. Once the routine was written, I just brought the far clipping plane in until the Z-buffer precision seemed to be sufficient. Because distances are scaled exponentially, the proper Z order is maintained in the Z-buffer.
Problems of Scale: A Star System
Next I tried placing a star at the center of the 3D map and placing the planet and camera out to Earth's orbital distance in the X direction. I immediately ran into rendering problems and positioning problems, though it was hard to tell that it was multiple problems until I fixed the rendering problems. The rendering problems caused all objects in the scene to shake and occasionally disappear whenever the camera moved or turned. Again the rendering problems showed up differently on each video card I tested it on, and again they had something to do with very large numbers being used in the transformation matrices.
Perhaps the most common way to use OpenGL's model/view matrix is to push the camera's view matrix onto the stack and multiply it by each object's model matrix during rendering. The problem with the traditional model and view matrices in the test case outlined above is that both have a very large translation in the X direction. A 32-bit float starts to lose precision around 1000 km, and Earth's orbit is around 149,600,000 km. Even though the camera is close to the planet and the numbers should cancel each other out, too much precision is lost during the calculations to make the resulting matrix accurate.
Is it time to resort to doubles yet? Not yet. This problem can be fixed very easily without using doubles by changing how the model and view matrices are calculated. Start out by pretending the camera is at the origin when you calculate your view matrix. If you use an existing function like gluLookAt() to generate your view matrix, just pass it (0, 0, 0) for the eye position and adjust your center position. Then calculate each model matrix relative to the camera's actual position by subtracting the camera's position from the model's position. The result is two matrices with very small numbers when the camera is close to the model, which makes the problem go away completely. A precision problem still exists with objects at a great distance from the camera, but at that distance the precision loss isn't noticeable.
After all rendering problems have been fixed, you run into precision problems with object positions. Using floats, you can't model positions accurately once you get out past 1,000 km from the origin. The most obvious symptom appears when you try to move the camera (or any other object) when it's far away from the origin. When a position contains really large numbers, a relatively small velocity will be completely dropped as a rounding error. Sometimes it will be dropped in 1 axis, sometimes in 2, and sometimes in all 3. When the velocity gets high enough along a specific axis, the position will start to "jump" in noticeably discrete amounts along that axis. The end result is that both the direction and magnitude of your velocity vector end up being ignored to a certain extent.
Is it time to resort to doubles yet? Yes. I don't think there's any way around it with object position. There's no number magic you can work that will give you extra digits of precision without cost. TANSTAAFL. Luckily, you only need doubles for object positions. Everything else can still be represented with floats, and almost every math operation you perform will still be a single-precision operation. The only time you need double-precision operations is when you're updating an object's position or comparing the positions of two objects. And with 15 digits of precision, you get better precision way out at 1000 times Pluto's orbit than you get with floats dealing with one planet at the origin.
Problems of Scale: An Entire Galaxy
This is a tough one. A double may get you safely out to 1000 times Pluto's orbit, which is just under 2/3 of a light-year, but you really can't take it much farther. Since we don't currently have any built-in data types larger than a double, you have to resort to something custom. I've seen a number of implementations that will work here, but something fast is needed. I've seen custom 128-bit fixed-point numbers created using 2 __int64 values. I've seen 4-bit BCD (Binary Coded Decimal) routines used to achieve unlimited precision. I'm sure if you looked you could even find 128-bit floating-point emulation routines out there.
A common problem with all the schemes I've mentioned so far is performance. Generally speaking, software is much slower than hardware. This means that if you're not using a native data type, all of these custom routines will run much more slowly than double-precision operations. I prefer to solve this problem by using different frames of reference at different scales. The top level would be the galaxy level, with the galaxy centered at the origin and with 1 unit being equal to 1 light-year. The next level would be the star system level, with the star centered at the origin and 1 unit being equal to 1 kilometer.
Because the distance between stars is so vast, you really don't need to mix the two frames of reference. If you consider the fact that anything traveling between stars at sub-light speeds would never get there during the player's lifetime, then you can choose your frame of reference based on whether an object is traveling above or below the speed of light. When an object jumps to FTL (Faster Than Light) travel, you can immediately switch to the galaxy frame of reference. When an object drops back to sub-light speed, you can immediately switch to the star system frame of reference. If a star is nearby, you can choose that to be the new origin. Otherwise, you can make the object's initial position the origin. It is also possible to keep the player from stopping between star systems by forcing them to select a destination star system, then leading the camera there any way you want.
Page 1 of 3