## Re: [Algorithms] Huge world, little precision

 Re: [Algorithms] Huge world, little precision From: Jim Schuler - 2007-02-28 11:14:35 ```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" To: 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 > george@... > http://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 > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ```

 [Algorithms] Huge world, little precision From: George van Venrooij - 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 george@... http://www.organicvectory.com ```
 Re: [Algorithms] Huge world, little precision From: Jim Schuler - 2007-02-28 11:14:35 ```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" To: 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 > george@... > http://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 > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ```
 Re: [Algorithms] Huge world, little precision From: - 2007-02-28 11:23:33 ```Selon George van Venrooij : > 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 > george@... > http://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 From: Jon Watte - 2007-02-28 19:22:47 ``` 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+ ```