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
> ********************************************