Game Development - Software Engineering

BRIAN LIVINGSTON | 7 Jun 2011 02:52

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

headers

Fabian Giesen | 7 Jun 2011 07:28

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

headers

metanet software | 8 Jun 2011 13:48

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