[Algorithms] Huge world, little precision
Brought to you by:
vexxed72
|
From: George v. V. <ge...@or...> - 2007-02-28 11:02:30
|
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
|