# 3D Convex hull from point cloud

This topic is 3287 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 on other sites
CGAL has functions to compute the convex hull of a set of 3D points. Perhaps you can use them.

##### Share on other sites
Quote:
 Original post by kiwillamaI 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 on other sites
Quote:
 Original post by swiftcoderIs 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 swiftcoderAnd 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 on other sites
Can't you use an OBB instead of the convex hull and use the OBB to generate the AABB?

##### Share on other sites
Quote:
 Original post by AiroCan't you use an OBB instead of the convex hull and use the OBB to generate the AABB?
That is unlikely to provide as tight a fit as generating the AABB from the convex hull.

1. 1
2. 2
3. 3
frob
15
4. 4
5. 5

• 9
• 20
• 12
• 13
• 14
• ### Forum Statistics

• Total Topics
632143
• Total Posts
3004419

×