[Algorithms] Huge world, little precision

[George v. V. <ge...@or...>]

Hi,

    I have been working on a spherical terrain engine capable of handling 
earth-sized planets. Recently a numerical problem showed up that seems to be 
caused by precision loss in 32-bit floating point arithmetic.

    A short description of what happens:

1) Terrain vertices are created in "planet-space", so the center of the 
sphere is considered to be the origin (0,0,0). For large planets, this means 
the vertices always have really big coordinates.
2) In a test application, the planet's position is conveniently located at 
the origin in world space as well. This means the viewer's position also has 
really large coordinates.
3) All goes perfectly well, until the viewer gets really close to the 
surface of the planet and the terrain triangulation produces detail at 
roughly meter resolution. When this happens, vertices near the viewer (or 
the viewer itself...) appear to be "jumping" when moving small steps (in the 
order of a meter per frame).

My analysis of this behavior is the following:

The Earth's radius is almost 7000 km, so coordinates (which are in meters) 
are in the million meter ranges. Since a 32-bit float has only 6 or 7 digits
of significance, it is impossible to accurately calculate in the sub-meter 
or 1-meter range. Moving around at a slow speed will also not work, because
the changes to the viewer's position will be "invisible" to the significant 
part of the floating point number.

I have tried changing the whole pipeline to use doubles, but apparently you 
can send doubles to OpenGL but the driver converts them into floats
anyway... Or at least, that's what I think, since the behavior is exactly 
the same.

Looking for literature on this problem yielded just a few results:

1) Work with a "universal" 3D-grid, where each grid "block" is small enough 
to not cause any precision problems. Transform all objects when the viewer 
crosses a block boundary.
2) Work with specific areas that use a fixed origin (something like this was 
used in Dungeon Siege I believe), transform objects and/or viewer as they 
cross a region boundary.
3) Have all items in your world relative to the viewer position during 
rendering.

Personally, I don't like options 1 and 2, since the boundary handling is 
very hard to get right. The 3rd option works fine for "normal-sized" 
objects, but if the object you want to render has a size that's bigger than 
can be accurately represented by a float (say for example... a planet?), it 
will not work.


Does anybody have any good suggestions on how to tackle this problem in an 
efficient and elegant way?

Regards,

    George van Venrooij
    ge...@or...
    www.organicvectory.com