BRIAN LIVINGSTON | 7 Jun 02:52 2011
Picon

Creating enclosing convex meshes for AABB calculation

Hello,
  I am aspiring game developer. I am using AABB trees for all sorts of stuff in a scene graph. The problem is that we need to quickly calculate a new AABB when an object moves. 
  Therefore I am working on an algorithm for generating vastly simplified convex meshes for fast(ish) AABB calculation for objects that can have an arbitrary orientation. The basic idea is to sort of fit a geodesic sphere over an object to produce a low-poly convex blob that contains the significant maximum extent information from any arbitrary orientation. The geodesic sphere is just a tool for discovering the maximum extent within a solid angle that radiates outward from an origin from within a mesh model. A geodesic sphere has the property that it is constructed from tetrahedrons. Therefore discovery of the maximum extent within each solid angle can occur with a barycentric coordinate evaluation. I am abusing the term solid angle here to mean the volume within a sphere which is a tetrahedron that has one vertex on the sphere origin and three vertices on the surface of the sphere.
  Once we have the maximum extent point field the question is: how do we approach building a new triangle mesh? We have the adjacency knowledge because each triangle face of the sphere is a bucket that either contains the vertices (1-N) that share the maximum distance from the origin. So if we split the sphere into 2 hemispheres we can use a hybrid 2D algorithm for constructing a plane from a point cloud. We should also have a step that further reduces the set of vertices in the point cloud by removing the entries for faces on the sphere that are now essentially concave.
  Note that we start with a sphere that totally encloses the object and now we have a sphere that has random faces pushed in to meet with the maximum extent for that solid angle.
  Note that the final result will not be spherical because we are not introducing new points and there may be a singular feature of the original mesh that juts out at an extreme angle.
  It seems like we can use a path finding algorithm on the graph where each face that contains maximal points is a node on the graph multiplied by the number of maximal points and now we need to walk the graph in a clockwise (winding order) direction until we form a loop and then subdivide if need be and then start again keeping track of edges so that we don't create the same edge twice (vertex 0 to vertex 5 is not the same edge as vertex 5 to vertex 0 for our purposes so that we can use the same two points for two adjacent polygons.
  Hopefully this question will be seen as an interesting puzzle and not as a why don't you post this elsewhere kind of submission.
  I am also curious how the pro's calculate AABB's on the fly in the cheapest (in processing) and tightest (in fit) manner. Do the pro's use low poly versions of meshes for bounding box calculations?

- Thanks in advance
- Brian Livingston
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Fabian Giesen | 7 Jun 07:28 2011
Picon
Picon

Re: Creating enclosing convex meshes for AABB calculation

On 06.06.2011 17:52, BRIAN LIVINGSTON wrote:
> Hello,
> I am aspiring game developer. I am using AABB trees for all sorts of
> stuff in a scene graph. The problem is that we need to quickly calculate
> a new AABB when an object moves.

If you're using AABBs, you already get a relatively loose fit (depending 
on the shape of the object). If you really care about getting a tight 
fit around the object, use the convex hull which you can then transform 
directly. Conversely, if you don't care about tightness that much, 
there's no point getting fancy about it; you can either build a new AABB 
from the transformed original AABB, or use something with a tighter fit 
like a general OBB, transform it, and then use the AABB of that. This is 
very easy, fast, and totally fine for e.g. culling purposes.

> Therefore I am working on an algorithm for generating vastly simplified
> convex meshes for fast(ish) AABB calculation for objects that can have
> an arbitrary orientation. The basic idea is to sort of fit a geodesic
> sphere over an object to produce a low-poly convex blob that contains
> the significant maximum extent information from any arbitrary
> orientation. The geodesic sphere is just a tool for discovering the
> maximum extent within a solid angle that radiates outward from an origin
> from within a mesh model. A geodesic sphere has the property that it is
> constructed from tetrahedrons. Therefore discovery of the maximum extent
> within each solid angle can occur with a barycentric coordinate
> evaluation. I am abusing the term solid angle here to mean the volume
> within a sphere which is a tetrahedron that has one vertex on the sphere
> origin and three vertices on the surface of the sphere.
 > Once we have the maximum extent point field the question is: how do we
 > approach building a new triangle mesh? We have the adjacency knowledge
 > because each triangle face of the sphere is a bucket that either
 > contains the vertices (1-N) that share the maximum distance from the
 > origin. So if we split the sphere into 2 hemispheres we can use a hybrid
 > 2D algorithm for constructing a plane from a point cloud. We should also
 > have a step that further reduces the set of vertices in the point cloud
 > by removing the entries for faces on the sphere that are now essentially
 > concave.
 > [..]

Why not use a convex hull algorithm to construct the exact convex hull 
and use that if you want a tight fit?

What you describe seems like an incredibly roundabout way of attacking 
the problem. And the fact that your multi-step algorithm may later 
produce concavities shows that it's an inherently flawed way of 
organizing the computation.

The sane variant of this approach is to build what's commonly called a 
k-DOP (Discrete Oriented Polytope); effectively a volume described by 
the intersection of the negative half-spaces of k planes.

Sounds fancy but is incredibly easy. Pick any direction vector d. Now 
compute the dot product of all vertex positions with d, and keep track 
of the minimum (min_d) and maximum (max_d). Clearly, the mesh is within 
the half-spaces

   dot(P, d) <= max_d
   dot(P, d) >= min_d

which immediately gives you two planes that enclose the object from 
opposing sides (that's why in practice you always pick k=even, since you 
get the second plane for any direction almost for free).

If you want to generate a mesh from that, the easiest way to do it is 
probably to take the AABB for the object and then clip it against all of 
the planes. But again, storing a mesh (even if it's a small one) just to 
generate updated bounding volumes from is probably overkill! And again, 
if you want a good approximation of the object, use its convex hull; 
there's no point in using an approximation that ends up being hairier 
than the original thing!

> I am also curious how the pro's calculate AABB's on the fly in the
> cheapest (in processing) and tightest (in fit) manner. Do the pro's use
> low poly versions of meshes for bounding box calculations?

Don't know what others do, but for stuff where tight fit doesn't matter 
much, I normally just store a model-space AABB for everything and use 
the worldspace AABB around that if I need one. This is really easy (note 
you don't expand the AABB into 8 vertices, you can solve this directly!).

If you do care about tightness of fit, use an OBB or the convex hull 
(the latter is useful for physics and collision queries, but its 
variable size and test cost make it fairly unsuitable for anything but 
the leaves of some tree). Both of these transform easily and don't lose 
any tightness of fit.

-Fabian
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

BRIAN LIVINGSTON | 7 Jun 23:46 2011
Picon

Re: Sweng-Gamedev Digest, Vol 65, Issue 1

Fabian,
  Thanks for the reply. A convex hull technique is definitely overkill for most situations. My idea may be a bit convoluted in light of other techniques but the idea was exactly that, to create a simple convex hull offline that can be transformed in game and then used to create the AABB. I am currently using a simple pre-created convex spline around the base of a model that fits the mesh projected onto the ground plane plus the height for objects that only rotate around the Y axis. The spline can be rotated and the AABB re-calculated and that was fast but then I got to thinking about objects with arbitrary orientations. I will investigate the K-dop, it sounds like what I was envisioning in my mind and it appears to resolve many of the problems that I was having with my approach. I agree that for culling purposes it makes no sense to offset the gains from culling with excessive work. Thanks again for the insight.

Brian



> From: sweng-gamedev-request <at> lists.midnightryder.com
> Subject: Sweng-Gamedev Digest, Vol 65, Issue 1
> To: sweng-gamedev <at> lists.midnightryder.com
> Date: Tue, 7 Jun 2011 13:43:11 -0700
>
> Send Sweng-Gamedev mailing list submissions to
> sweng-gamedev <at> lists.midnightryder.com
>
> To subscribe or unsubscribe via the World Wide Web, visit
> http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
>
> or, via email, send a message with subject or body 'help' to
> sweng-gamedev-request <at> lists.midnightryder.com
>
> You can reach the person managing the list at
> sweng-gamedev-owner <at> lists.midnightryder.com
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Sweng-Gamedev digest..."
>
>
> Today's Topics:
>
> 1. Creating enclosing convex meshes for AABB calculation
> (BRIAN LIVINGSTON)
> 2. Re: Creating enclosing convex meshes for AABB calculation
> (Fabian Giesen)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Tue, 7 Jun 2011 00:52:29 +0000
> From: BRIAN LIVINGSTON <noizhead <at> msn.com>
> To: <sweng-gamedev <at> lists.midnightryder.com>
> Subject: [Sweng-Gamedev] Creating enclosing convex meshes for AABB
> calculation
> Message-ID: <SNT123-w46304D5ACF4C478A953A2ADF630 <at> phx.gbl>
> Content-Type: text/plain; charset="iso-8859-1"
>
>
> Hello, I am aspiring game developer. I am using AABB trees for all sorts of stuff in a scene graph. The problem is that we need to quickly calculate a new AABB when an object moves. Therefore I am working on an algorithm for generating vastly simplified convex meshes for fast(ish) AABB calculation for objects that can have an arbitrary orientation. The basic idea is to sort of fit a geodesic sphere over an object to produce a low-poly convex blob that contains the significant maximum extent information from any arbitrary orientation. The geodesic sphere is just a tool for discovering the maximum extent within a solid angle that radiates outward from an origin from within a mesh model. A geodesic sphere has the property that it is constructed from tetrahedrons. Therefore discovery of the maximum extent within each solid angle can occur with a barycentric coordinate evaluation. I am abusing the term solid angle here to mean the volume within a sphere which is a tetrahedron t
> hat has one vertex on the sphere origin and three vertices on the surface of the sphere. Once we have the maximum extent point field the question is: how do we approach building a new triangle mesh? We have the adjacency knowledge because each triangle face of the sphere is a bucket that either contains the vertices (1-N) that share the maximum distance from the origin. So if we split the sphere into 2 hemispheres we can use a hybrid 2D algorithm for constructing a plane from a point cloud. We should also have a step that further reduces the set of vertices in the point cloud by removing the entries for faces on the sphere that are now essentially concave. Note that we start with a sphere that totally encloses the object and now we have a sphere that has random faces pushed in to meet with the maximum extent for that solid angle. Note that the final result will not be spherical because we are not introducing new points and there may be a singular feature of the original m
> esh that juts out at an extreme angle. It seems like we can use a path finding algorithm on the graph where each face that contains maximal points is a node on the graph multiplied by the number of maximal points and now we need to walk the graph in a clockwise (winding order) direction until we form a loop and then subdivide if need be and then start again keeping track of edges so that we don't create the same edge twice (vertex 0 to vertex 5 is not the same edge as vertex 5 to vertex 0 for our purposes so that we can use the same two points for two adjacent polygons. Hopefully this question will be seen as an interesting puzzle and not as a why don't you post this elsewhere kind of submission. I am also curious how the pro's calculate AABB's on the fly in the cheapest (in processing) and tightest (in fit) manner. Do the pro's use low poly versions of meshes for bounding box calculations?
> - Thanks in advance- Brian Livingston
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: <http://lists.midnightryder.com/private.cgi/sweng-gamedev-midnightryder.com/attachments/20110607/c39ca256/attachment.html>
>
> ------------------------------
>
> Message: 2
> Date: Mon, 06 Jun 2011 22:28:30 -0700
> From: Fabian Giesen <ryg <at> gmx.net>
> To: sweng-gamedev <at> midnightryder.com
> Subject: Re: [Sweng-Gamedev] Creating enclosing convex meshes for AABB
> calculation
> Message-ID: <4DEDB6FE.8010607 <at> gmx.net>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> On 06.06.2011 17:52, BRIAN LIVINGSTON wrote:
> > Hello,
> > I am aspiring game developer. I am using AABB trees for all sorts of
> > stuff in a scene graph. The problem is that we need to quickly calculate
> > a new AABB when an object moves.
>
> If you're using AABBs, you already get a relatively loose fit (depending
> on the shape of the object). If you really care about getting a tight
> fit around the object, use the convex hull which you can then transform
> directly. Conversely, if you don't care about tightness that much,
> there's no point getting fancy about it; you can either build a new AABB
> from the transformed original AABB, or use something with a tighter fit
> like a general OBB, transform it, and then use the AABB of that. This is
> very easy, fast, and totally fine for e.g. culling purposes.
>
> > Therefore I am working on an algorithm for generating vastly simplified
> > convex meshes for fast(ish) AABB calculation for objects that can have
> > an arbitrary orientation. The basic idea is to sort of fit a geodesic
> > sphere over an object to produce a low-poly convex blob that contains
> > the significant maximum extent information from any arbitrary
> > orientation. The geodesic sphere is just a tool for discovering the
> > maximum extent within a solid angle that radiates outward from an origin
> > from within a mesh model. A geodesic sphere has the property that it is
> > constructed from tetrahedrons. Therefore discovery of the maximum extent
> > within each solid angle can occur with a barycentric coordinate
> > evaluation. I am abusing the term solid angle here to mean the volume
> > within a sphere which is a tetrahedron that has one vertex on the sphere
> > origin and three vertices on the surface of the sphere.
> > Once we have the maximum extent point field the question is: how do we
> > approach building a new triangle mesh? We have the adjacency knowledge
> > because each triangle face of the sphere is a bucket that either
> > contains the vertices (1-N) that share the maximum distance from the
> > origin. So if we split the sphere into 2 hemispheres we can use a hybrid
> > 2D algorithm for constructing a plane from a point cloud. We should also
> > have a step that further reduces the set of vertices in the point cloud
> > by removing the entries for faces on the sphere that are now essentially
> > concave.
> > [..]
>
> Why not use a convex hull algorithm to construct the exact convex hull
> and use that if you want a tight fit?
>
> What you describe seems like an incredibly roundabout way of attacking
> the problem. And the fact that your multi-step algorithm may later
> produce concavities shows that it's an inherently flawed way of
> organizing the computation.
>
> The sane variant of this approach is to build what's commonly called a
> k-DOP (Discrete Oriented Polytope); effectively a volume described by
> the intersection of the negative half-spaces of k planes.
>
> Sounds fancy but is incredibly easy. Pick any direction vector d. Now
> compute the dot product of all vertex positions with d, and keep track
> of the minimum (min_d) and maximum (max_d). Clearly, the mesh is within
> the half-spaces
>
> dot(P, d) <= max_d
> dot(P, d) >= min_d
>
> which immediately gives you two planes that enclose the object from
> opposing sides (that's why in practice you always pick k=even, since you
> get the second plane for any direction almost for free).
>
> If you want to generate a mesh from that, the easiest way to do it is
> probably to take the AABB for the object and then clip it against all of
> the planes. But again, storing a mesh (even if it's a small one) just to
> generate updated bounding volumes from is probably overkill! And again,
> if you want a good approximation of the object, use its convex hull;
> there's no point in using an approximation that ends up being hairier
> than the original thing!
>
> > I am also curious how the pro's calculate AABB's on the fly in the
> > cheapest (in processing) and tightest (in fit) manner. Do the pro's use
> > low poly versions of meshes for bounding box calculations?
>
> Don't know what others do, but for stuff where tight fit doesn't matter
> much, I normally just store a model-space AABB for everything and use
> the worldspace AABB around that if I need one. This is really easy (note
> you don't expand the AABB into 8 vertices, you can solve this directly!).
>
> If you do care about tightness of fit, use an OBB or the convex hull
> (the latter is useful for physics and collision queries, but its
> variable size and test cost make it fairly unsuitable for anything but
> the leaves of some tree). Both of these transform easily and don't lose
> any tightness of fit.
>
> -Fabian
>
>
> ------------------------------
>
> _______________________________________________
> Sweng-Gamedev mailing list
> Sweng-Gamedev <at> lists.midnightryder.com
> http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
>
>
> End of Sweng-Gamedev Digest, Vol 65, Issue 1
> ********************************************
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
metanet software | 8 Jun 13:48 2011
Picon

Re: Creating enclosing convex meshes for AABB calculation

> Do the pro's use low poly versions of meshes 
> for bounding box calculations?

AFAIK both Bullet and Box2d have open-source implementations of AABB-trees in them; browsing through the
source and/or docs might give you some ideas about how they handle this.

raigan

--- On Tue, 6/7/11, Fabian Giesen <ryg <at> gmx.net> wrote:

> From: Fabian Giesen <ryg <at> gmx.net>
> Subject: Re: [Sweng-Gamedev] Creating enclosing convex meshes for AABB calculation
> To: sweng-gamedev <at> midnightryder.com
> Received: Tuesday, June 7, 2011, 1:28 AM
> On 06.06.2011 17:52, BRIAN LIVINGSTON
> wrote:
> > Hello,
> > I am aspiring game developer. I am using AABB trees
> for all sorts of
> > stuff in a scene graph. The problem is that we need to
> quickly calculate
> > a new AABB when an object moves.
> 
> If you're using AABBs, you already get a relatively loose
> fit (depending on the shape of the object). If you really
> care about getting a tight fit around the object, use the
> convex hull which you can then transform directly.
> Conversely, if you don't care about tightness that much,
> there's no point getting fancy about it; you can either
> build a new AABB from the transformed original AABB, or use
> something with a tighter fit like a general OBB, transform
> it, and then use the AABB of that. This is very easy, fast,
> and totally fine for e.g. culling purposes.
> 
> > Therefore I am working on an algorithm for generating
> vastly simplified
> > convex meshes for fast(ish) AABB calculation for
> objects that can have
> > an arbitrary orientation. The basic idea is to sort of
> fit a geodesic
> > sphere over an object to produce a low-poly convex
> blob that contains
> > the significant maximum extent information from any
> arbitrary
> > orientation. The geodesic sphere is just a tool for
> discovering the
> > maximum extent within a solid angle that radiates
> outward from an origin
> > from within a mesh model. A geodesic sphere has the
> property that it is
> > constructed from tetrahedrons. Therefore discovery of
> the maximum extent
> > within each solid angle can occur with a barycentric
> coordinate
> > evaluation. I am abusing the term solid angle here to
> mean the volume
> > within a sphere which is a tetrahedron that has one
> vertex on the sphere
> > origin and three vertices on the surface of the
> sphere.
> > Once we have the maximum extent point field the
> question is: how do we
> > approach building a new triangle mesh? We have the
> adjacency knowledge
> > because each triangle face of the sphere is a bucket
> that either
> > contains the vertices (1-N) that share the maximum
> distance from the
> > origin. So if we split the sphere into 2 hemispheres
> we can use a hybrid
> > 2D algorithm for constructing a plane from a point
> cloud. We should also
> > have a step that further reduces the set of vertices
> in the point cloud
> > by removing the entries for faces on the sphere that
> are now essentially
> > concave.
> > [..]
> 
> Why not use a convex hull algorithm to construct the exact
> convex hull and use that if you want a tight fit?
> 
> What you describe seems like an incredibly roundabout way
> of attacking the problem. And the fact that your multi-step
> algorithm may later produce concavities shows that it's an
> inherently flawed way of organizing the computation.
> 
> The sane variant of this approach is to build what's
> commonly called a k-DOP (Discrete Oriented Polytope);
> effectively a volume described by the intersection of the
> negative half-spaces of k planes.
> 
> Sounds fancy but is incredibly easy. Pick any direction
> vector d. Now compute the dot product of all vertex
> positions with d, and keep track of the minimum (min_d) and
> maximum (max_d). Clearly, the mesh is within the
> half-spaces
> 
>   dot(P, d) <= max_d
>   dot(P, d) >= min_d
> 
> which immediately gives you two planes that enclose the
> object from opposing sides (that's why in practice you
> always pick k=even, since you get the second plane for any
> direction almost for free).
> 
> If you want to generate a mesh from that, the easiest way
> to do it is probably to take the AABB for the object and
> then clip it against all of the planes. But again, storing a
> mesh (even if it's a small one) just to generate updated
> bounding volumes from is probably overkill! And again, if
> you want a good approximation of the object, use its convex
> hull; there's no point in using an approximation that ends
> up being hairier than the original thing!
> 
> > I am also curious how the pro's calculate AABB's on
> the fly in the
> > cheapest (in processing) and tightest (in fit) manner.
> Do the pro's use
> > low poly versions of meshes for bounding box
> calculations?
> 
> Don't know what others do, but for stuff where tight fit
> doesn't matter much, I normally just store a model-space
> AABB for everything and use the worldspace AABB around that
> if I need one. This is really easy (note you don't expand
> the AABB into 8 vertices, you can solve this directly!).
> 
> If you do care about tightness of fit, use an OBB or the
> convex hull (the latter is useful for physics and collision
> queries, but its variable size and test cost make it fairly
> unsuitable for anything but the leaves of some tree). Both
> of these transform easily and don't lose any tightness of
> fit.
> 
> -Fabian
> _______________________________________________
> Sweng-Gamedev mailing list
> Sweng-Gamedev <at> lists.midnightryder.com
> http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
> 
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Juan Linietsky | 22 Jun 05:12 2011
Picon

Question about large worlds and foating point precision.

Here's a doubt i've been having for a while. When developing games based on large worlds (like Elder Scrolls, GTA, etc), i can imagine that physics and rendering become more jittery the further away the camera moves from the origin (due to floating point precision loss). Is this really a problem? If so, how is this solved? I can imagine that increasing floating point precision to doubles helps a enormously, but i'm not sure if that's enough and if it's worth the extra processing/bandwidth cost.
  Transforming the world to local coordinates (so the camera is always at the origin) also seems to me like a solution, but sounds like a lot more work and messy code.
So, how is this solved in most cases?

cheers!

Juan

_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Gregory Junker | 22 Jun 05:41 2011

Re: Question about large worlds and foating point precision.

It’s most often solved by transforming the origin. Increasing precision is *not* the answer; it simply delays the inevitable a little longer (while at the same time halving your VPU throughput). Of course, at the last second, you might be able to do intermediate host computations in increased precision, but at the end of the day, your graphics hardware is rendering with 32-bit floats (at most).

 

This is a well-known problem with well-understood solutions in practice. That said, you can’t just use (for example) the GPG4 solution in one system, without your entire game engine using it. So “messy” is a relative term; if you are developing a large-world game, chances are you are using a large-world game engine. If not, you’ve probably licensed the wrong engine for your game.  

 

Floating-point precision issues are also well-defined (from a computer science perspective), but often not really fully understood by most programmers (myself included). The most commonly cited work is David Goldberg’s paper for ACM (1991). An edited version is here:

 

http://www.cse.msu.edu/~cse320/Documents/FloatingPoint.pdf

 

The original is here:

 

http://portal.acm.org/citation.cfm?id=103163


Greg

 

From: sweng-gamedev-bounces <at> lists.midnightryder.com [mailto:sweng-gamedev-bounces <at> lists.midnightryder.com] On Behalf Of Juan Linietsky
Sent: Tuesday, June 21, 2011 8:12 PM
To: sweng-gamedev <at> midnightryder.com
Subject: [Sweng-Gamedev] Question about large worlds and foating point precision.

 

Here's a doubt i've been having for a while. When developing games based on large worlds (like Elder Scrolls, GTA, etc), i can imagine that physics and rendering become more jittery the further away the camera moves from the origin (due to floating point precision loss). Is this really a problem? If so, how is this solved? I can imagine that increasing floating point precision to doubles helps a enormously, but i'm not sure if that's enough and if it's worth the extra processing/bandwidth cost.
  Transforming the world to local coordinates (so the camera is always at the origin) also seems to me like a solution, but sounds like a lot more work and messy code.
So, how is this solved in most cases?

cheers!

Juan

_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Adrian Bentley | 22 Jun 06:31 2011
Picon

Re: Question about large worlds and foating point precision.

For Infamous (medium-small world 200k cm off origin?) we only had a few minor graphical problems far out. We
ended up subtracting camera translation from our object matrices before submitting them to the gpu.
There were only a few dozen places to edit and it took one guy a few days (including research). 

There was one other feedback scenario where we manually split out the translation part M2 in M1 * Inv(M2) for
precision, but that's it.

It was actually all pretty clean in the end.

Cheers,
Adrian

On Jun 21, 2011, at 8:12 PM, Juan Linietsky <reduzio <at> gmail.com> wrote:

> Here's a doubt i've been having for a while. When developing games based on large worlds (like Elder
Scrolls, GTA, etc), i can imagine that physics and rendering become more jittery the further away the
camera moves from the origin (due to floating point precision loss). Is this really a problem? If so, how is
this solved? I can imagine that increasing floating point precision to doubles helps a enormously, but
i'm not sure if that's enough and if it's worth the extra processing/bandwidth cost. 
>   Transforming the world to local coordinates (so the camera is always at the origin) also seems to me like a
solution, but sounds like a lot more work and messy code.
> So, how is this solved in most cases?
> 
> cheers!
> 
> Juan
> 
> _______________________________________________
> Sweng-Gamedev mailing list
> Sweng-Gamedev <at> lists.midnightryder.com
> http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Gregory Junker | 22 Jun 06:37 2011

Re: Question about large worlds and foating point precision.


> -----Original Message-----
> From: sweng-gamedev-bounces <at> lists.midnightryder.com [mailto:sweng-
> gamedev-bounces <at> lists.midnightryder.com] On Behalf Of Adrian Bentley
> Sent: Tuesday, June 21, 2011 9:32 PM
> To: sweng-gamedev <at> midnightryder.com
> Subject: Re: [Sweng-Gamedev] Question about large worlds and foating
> point precision.
> 
> For Infamous (medium-small world 200k cm off origin?) we only had a few
> minor graphical problems far out. We ended up subtracting camera
> translation from our object matrices before submitting them to the gpu.
> There were only a few dozen places to edit and it took one guy a few
> days (including research).

Were there physics/collisions involved at those distances?

Greg

_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Kieran_DArchambaud | 22 Jun 11:01 2011
Picon

AUTO: Kieran D'Archambaud is out of the office. (returning 27/06/2011)


I am out of the office until 27/06/2011.

I will respond to your message when I return.

For anything that needs urgent attention, please email Karl Chandler or
Wayne Hackney.

Note: This is an automated response to your message  "[Sweng-Gamedev]
Question about large worlds and foating point	precision." sent on
22/06/2011 04:12:16.

This is the only notification you will receive while this person is away.

**********************************************************************
This email and any files transmitted with it are confidential and intended solely for the use of the
individual or entity to whom they are addressed. If you have received this email in error please notify postmaster <at> scee.net
This footnote also confirms that this email message has been checked for all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom
Registered in England: 3277793
**********************************************************************

_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

James_Levick | 22 Jun 11:50 2011
Picon

Re: Question about large worlds and foating point precision.

Tom Forsyth wrote a post about this some years ago which might be worth looking at:

http://home.comcast.net/~tom_forsyth/blog.wiki.html#[[A%20matter%20of%20precision]]

James Levick
Sony Computer Entertainment Europe Limited
http://eu.playstation.com

sweng-gamedev-bounces <at> lists.midnightryder.com wrote on 22/06/2011 04:12:16:

> Juan Linietsky <reduzio <at> gmail.com>
> Sent by: sweng-gamedev-bounces <at> lists.midnightryder.com
>
> 22/06/2011 04:12
>
> Please respond to
> sweng-gamedev <at> midnightryder.com
>
> To
>
> sweng-gamedev <at> midnightryder.com
>
> cc
>
> Subject
>
> [Sweng-Gamedev] Question about large worlds and foating point precision.
>
> Here's a doubt i've been having for a while. When developing games
> based on large worlds (like Elder Scrolls, GTA, etc), i can imagine
> that physics and rendering become more jittery the further away the
> camera moves from the origin (due to floating point precision loss).
> Is this really a problem? If so, how is this solved? I can imagine
> that increasing floating point precision to doubles helps a
> enormously, but i'm not sure if that's enough and if it's worth the
> extra processing/bandwidth cost.
>   Transforming the world to local coordinates (so the camera is
> always at the origin) also seems to me like a solution, but sounds
> like a lot more work and messy code.
> So, how is this solved in most cases?
>
> cheers!
>
> Juan
> _______________________________________________
> Sweng-Gamedev mailing list
> Sweng-Gamedev <at> lists.midnightryder.com
> http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com


**********************************************************************
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster <at> scee.net
This footnote also confirms that this email message has been checked for all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom
Registered in England: 3277793
**********************************************************************

P Please consider the environment before printing this e-mail
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Gmane