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 <[email protected]> wrote:

> From: Fabian Giesen <[email protected]>
> Subject: Re: [Sweng-Gamedev] Creating enclosing convex meshes for AABB calculation
> To: [email protected]
> 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
> [email protected]
> http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
> 
_______________________________________________
Sweng-Gamedev mailing list
[email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com