7 Jun 2011 02:52
Creating enclosing convex meshes for AABB calculation
BRIAN LIVINGSTON <noizhead <at> msn.com>
2011-06-07 00:52:29 GMT
2011-06-07 00:52:29 GMT
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