gdalgorithms-list

[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

Re: [Algorithms] Huge world, little precision

[Jim S. <jsc...@sl...>]

Could try seperating the planet into regions of which have a large 
translation, and then surrounding land is relative to that region so that 
vertices stay within precision range.

A method could be that vertices are always relative to the center point of 
their latitude/longitude. Your position is always stored as long/lat plus a 
relative offset from there.


----- Original Message ----- 
From: "George van Venrooij" <ge...@or...>
To: <gda...@li...>
Sent: Wednesday, February 28, 2007 3:02 AM
Subject: [Algorithms] Huge world, little precision


> 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
>
>
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share 
> your
> opinions on IT & business topics through brief surveys-and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
> 

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

Re: [Algorithms] Huge world, little precision

[Jon W. <hp...@mi...>]

George van Venrooij wrote:
> 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).
>   

Yup. That's just an artifact of the quantization in the floating point 
representation. We've done on-the-ground foot-scale earth-size terrain 
since 2001, and we use doubles for the "general" coordinates. However, 
geometry is generated in a localized coordinate system as floating point 
(because hardware can do nothing else), and the difference relative to 
camera is made up in the transform matrix. This turns out to compensate 
nicely for jitter, and we can zoom from space to your face.

Thus, the trick is:
- generate geometry in a local (float) coordinate space per geometry 
"thing" (ground block, cultural, what have you)
- keep camera and "thing" coordinates in double precision
- Subtract double precision quantities to yield a single-precision 
transform matrix

Cheers,

          / h+