|
 Features
A
Real-Time Procedural Universe, Part Three: Matters of Scale
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.
______________________________________________________
|
|
|
|
|
One
Planet 
