# Bounding surface of a triangle mesh

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

## 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 on other sites
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 on other sites
Quote:
 Original post by oliiiyou 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 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 on other sites
Quote:
 Original post by oliiiall 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.

1. 1
Rutin
26
2. 2
3. 3
4. 4
5. 5

• 11
• 10
• 13
• 20
• 14
• ### Forum Statistics

• Total Topics
632950
• Total Posts
3009383
• ### Who's Online (See full list)

There are no registered users currently online

×