• Advertisement
Sign in to follow this  

Bounding surface of a triangle mesh

This topic is 3294 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

Could someone point me out a book, article, etc. explaining an algorithm to find the minimal surface enclosing a triangle mesh? The computed surface ought not to be convex. The minimal surface would be a set of triangles that belong to the mesh... P.S: sorry for the eventual mistakes in English as it isn't my mother tongue... [Edited by - johnstanp on January 14, 2009 6:47:32 AM]

Share this post


Link to post
Share on other sites
Advertisement
you mean convex hulls? These are either made up of.

- a set of infinite planes, all pointing outwards from the mesh.
- a list of convex polygons, with normals also pointing outwards.
- a topology (list of edges, planes, vertices...). That's useually used for collision detection.

There are several ways to compute a convex hull from a mesh, it's usually pre-computed as it can take a bit of time.

from a convex hull, you can also compute.
- a axis aligned bounding box.
- a bounding sphere
- a oriented bounding box (that's more maths intensive, making use of eigen vectors and such).

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
you mean convex hulls? These are either made up of.

- a set of infinite planes, all pointing outwards from the mesh.
- a list of convex polygons, with normals also pointing outwards.
- a topology (list of edges, planes, vertices...). That's useually used for collision detection.

There are several ways to compute a convex hull from a mesh, it's usually pre-computed as it can take a bit of time.

from a convex hull, you can also compute.
- a axis aligned bounding box.
- a bounding sphere
- a oriented bounding box (that's more maths intensive, making use of eigen vectors and such).


I knew you would be the first one to answer...Well, I'm not looking for a convex hull algorithm( explanation ), for the simple reason that I don't need the bounding surface to be convex. I simply want to remove interior points in case the mesh contains some: I want to be able to compute the exact envelope of a set of points.
Thanks for the link even if, actually, I know where I can find a well presented algorithm that should make the implementation of a convex hull not ( too ) painful.

You've written about computing OBBs from a convex hull: I've already implemented the algorithm for computing an OBB( and a minimal one with the Powell's direction set method, some time ago ) and wanted to implement an OBBTree for better accuracy in collision detection...Computing the convex hull speed up the computing of a box fitting a set of points( and for OBBTrees ), but I really don't like the fact that a convex hull could not be a good fit for a shape containing concave regions. So the optimal bounding shape would be an envelope.

P.S: sorry for the eventual syntactical and grammatical errors...

[Edited by - johnstanp on January 14, 2009 9:00:34 AM]

Share this post


Link to post
Share on other sites
all right-y.

Then I would be able to only speculate.

- flood-fill algorithm. Take one triangle that you know is on the surface (example, find a vertex on the surface, i.e. the extrema along a arbitrary direction, and start with one of the triangles attached to that vertex), and using the topology information (what triangles it is connected to), add all the connected triangles.

problem is if your mesh isn't a closed surface (T-junctions, holes, ect...), or has weird topology.

simply, each edge of each triangle would always connect to just one other triangle, and no edge remains unconnected, to prevent holes. although in your case, holes would still be ok, as well as inconsistent topologies (for example, triangles with a different winding order).

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
all right-y.

Then I would be able to only speculate.

- flood-fill algorithm. Take one triangle that you know is on the surface (example, find a vertex on the surface, i.e. the extrema along a arbitrary direction, and start with one of the triangles attached to that vertex), and using the topology information (what triangles it is connected to), add all the connected triangles.

problem is if your mesh isn't a closed surface (T-junctions, holes, ect...), or has weird topology.

simply, each edge of each triangle would always connect to just one other triangle, and no edge remains unconnected, to prevent holes. although in your case, holes would still be ok, as well as inconsistent topologies (for example, triangles with a different winding order).


Thanks. That should work: I didn't come up with a problematic case.

Share this post


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

  • Advertisement