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
[email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com