Jump to content
  • Advertisement
Sign in to follow this  
Khaos Dragon

algorithm to compute a convex hull

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to figure out given a mesh and the vertex cloud you obtain from it how to build the perfect convex representation from it using only triangles. Maybe I am just conceptualizing this entirely wrong but anything I envision would end up having triangles overlapping horribly over each other. I really just want my convex hull to be one smooth two-manifold surface. Is there a commonly accepted straightforward algorithm for this? I am not sure if I have phrased my question right, if anyone's confused I can try to explain using pictures.

Share this post


Link to post
Share on other sites
Advertisement
Are you familiar with Voronai diagrams, Delauney and Constrained Delauney Triangulation? Delauney Tetrahedralisation? If I understand your description correctly, you may find it useful to study these algorithms and then apply some of the processes involved in 3D. I'm working on a related algorithm for my project.

Are you trying to create convex triangular hulls or convex tetrahedra (which are later reduced to triangles) hulls?

Paulcoz.

Share this post


Link to post
Share on other sites
I think the most common way is quickhull. Google that and you'll find lots of stuff.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Building convex hulls are _really_ hard. The algorithms themselves are pretty simple, but getting it to work for all point clouds is almost impossible... Even mature libs like qhull can't generate convex hull for some point clouds...

Share this post


Link to post
Share on other sites
couldn t you start with a bounding box
calculate the distance of each vertex to each plane of the bbox

and use the vertices with the shortest distance to begin with?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!