Sign in to follow this  
kiwillama

3D Convex hull from point cloud

Recommended Posts

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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by kiwillama
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.
Is this convex hull generation intended to be used as a pre-process? And is there a reason why the AABB generation couldn't be done as a pre-process?

The reason I ask is that the optimal-case for convex hull generation is amortised O(n), and may be much worse in practice - while the cost of AABB generation is always O(n). Thus there is no advantage to generating a convex hull before generating the AABB, unless the convex hull can be generated in a pre-process, and the AABB can not.

Share this post


Link to post
Share on other sites
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 =)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this