Re: [Algorithms] Huge world, little precision

[<lo...@fr...>]

Selon George van Venrooij <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
>

64 bit integers?

Anyway, I believe you should read TomF's blog, as it dealt with this subject:

http://home.comcast.net/~tom_forsyth/blog.wiki.html#%5B%5BA%20matter%20of%20precision%5D%5D

Regards,

-- Emmanuel Deloget