Hey guys, I am trying to speed up some AABB code by creating convex hulls of the models. I figure checking for min and max points should be faster if i have less points to check. I was wondering if anyone had a C# implementation of a 3 dimensional convex hull algorithm lying around? Or perhaps a suggestion for a simple algorithm? thanks!

You can look at this page for some algorithms to compute convex hulls. It also provides the source for the applet in that page too, in java.

CGAL has functions to compute the convex hull of a set of 3D points. Perhaps you can use them.

Quote:Original post by swiftcoder
Is this convex hull generation intended to be used as a pre-process?

Yes, I intend to do it once during load and then store it. Therefore, it doesn't really matter too much if the convex hull algorithm runs in O(nlogn) or O(n^2). Which ever algorithm is simplest to implement will be the one I go with.

Quote:Original post by swiftcoder
And is there a reason why the AABB generation couldn't be done as a pre-process?

When the object is rotated its AABB needs to be updated. If I have a convex hull of the object computing the AABB every frame would not be so bad. Especially, if I could find an algorithm which reduces convex hull vertices by inflating the size of the convex hull by an acceptable amount. (does any one have any suggestions for such an algorithm?)

I have considered using object aligned bounding boxes but I am a little worried that it would be too much work for what I am working on. If I am not mistaken the task of collision detection on OBB requires about 18 cases...

However, I am open to opinions on this. Currently I need AABBs for frustrum culling but I guess I will use them in broad phase collision detection as well.

please let me know what you think =)

Can't you use an OBB instead of the convex hull and use the OBB to generate the AABB?