Creating enclosing convex meshes for AABB calculation

[BRIAN LIVINGSTON]

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

[Fabian Giesen]

Post by BRIAN LIVINGSTON
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.

Post by BRIAN LIVINGSTON
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!

Post by BRIAN LIVINGSTON
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

[metanet software]

Post by BRIAN LIVINGSTON
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

Post by BRIAN LIVINGSTON
Subject: Re: [Sweng-Gamedev] Creating enclosing convex meshes for AABB calculation
Received: Tuesday, June 7, 2011, 1:28 AM
On 06.06.2011 17:52, BRIAN LIVINGSTON

Post by BRIAN LIVINGSTON
Hello,
I am aspiring game developer. I am using AABB trees

for all sorts of

Post by BRIAN LIVINGSTON
stuff in a scene graph. The problem is that we need to

quickly calculate

Post by BRIAN LIVINGSTON
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.

Post by BRIAN LIVINGSTON
Therefore I am working on an algorithm for generating

vastly simplified

Post by BRIAN LIVINGSTON
convex meshes for fast(ish) AABB calculation for

objects that can have

Post by BRIAN LIVINGSTON
an arbitrary orientation. The basic idea is to sort of

fit a geodesic

Post by BRIAN LIVINGSTON
sphere over an object to produce a low-poly convex

blob that contains

Post by BRIAN LIVINGSTON
the significant maximum extent information from any

arbitrary

Post by BRIAN LIVINGSTON
orientation. The geodesic sphere is just a tool for

discovering the

Post by BRIAN LIVINGSTON
maximum extent within a solid angle that radiates

outward from an origin

Post by BRIAN LIVINGSTON
from within a mesh model. A geodesic sphere has the

property that it is

Post by BRIAN LIVINGSTON
constructed from tetrahedrons. Therefore discovery of

the maximum extent

Post by BRIAN LIVINGSTON
within each solid angle can occur with a barycentric

coordinate

Post by BRIAN LIVINGSTON
evaluation. I am abusing the term solid angle here to

mean the volume

Post by BRIAN LIVINGSTON
within a sphere which is a tetrahedron that has one

vertex on the sphere

Post by BRIAN LIVINGSTON
origin and three vertices on the surface of the

sphere.

Post by BRIAN LIVINGSTON
Once we have the maximum extent point field the

question is: how do we

Post by BRIAN LIVINGSTON
approach building a new triangle mesh? We have the

adjacency knowledge

Post by BRIAN LIVINGSTON
because each triangle face of the sphere is a bucket

that either

Post by BRIAN LIVINGSTON
contains the vertices (1-N) that share the maximum

distance from the

Post by BRIAN LIVINGSTON
origin. So if we split the sphere into 2 hemispheres

we can use a hybrid

Post by BRIAN LIVINGSTON
2D algorithm for constructing a plane from a point

cloud. We should also

Post by BRIAN LIVINGSTON
have a step that further reduces the set of vertices

in the point cloud

Post by BRIAN LIVINGSTON
by removing the entries for faces on the sphere that

are now essentially

Post by BRIAN LIVINGSTON
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!

Post by BRIAN LIVINGSTON
I am also curious how the pro's calculate AABB's on

the fly in the

Post by BRIAN LIVINGSTON
cheapest (in processing) and tightest (in fit) manner.

Do the pro's use

Post by BRIAN LIVINGSTON
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
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com