Sign in to follow this  
mike74

closed surface

Recommended Posts

mike74    100
Let's say you have a set of points. Does anyone know how to find a set of triangles that will form a closed surface around all these points (and all of the vertices of the triangles will be from the set of points)? Basically, no points would be outside the surface, but some of them might be inside. For instance, if you choose a random set of points inside a sphere, then you would be creating a closed surface somewhat similar to a sphere. The surface would be comprised of triangles whose vertices were some of the random points. Mike C. http://www.coolgroups.com/zoomer

Share this post


Link to post
Share on other sites
mike74    100
Thanks. The convex hull algorithm sounds like it will give the appropriate points that are involved, but do you know how to go about computing the faces?

Mike C.
http://www.coolgroups.com/zoomer

Share this post


Link to post
Share on other sites
Squirm    481
try these search terms:

"marching cubes"
"delauney triangulation"

also try http://gts.sourceforge.net

There are other methods :)

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
The convex hull algorithm sounds like it will give the appropriate points that are involved, but do you know how to go about computing the faces?
An appropriate convex hull algorithm will compute the faces; unfortunately, in 3d the implementation can be a little complicated.

There's a standard algorithm whose name escapes me at the moment. However, I've found that a somewhat simpler incremental algorithm works very well.

The first step is to initialize the convex hull with a more or less optimal simplex (tetrahedron in 3d):

1. Find two points some distance apart to form a segment
2. Find a point some distance from the segment to form a triangle
3. Find a point some distance from the triangle to form a tetrahedron

What 'some distance' means depends, but the idea is that the initial simplex be non-degenerate.

Then, for each point:

1. If it's inside the current hull, discard
2. Else find all faces whose support plane it is in front of
3. Discard these faces
4. Create a triangle between the new point and each exposed edge

It's been a while since I implemented this, and may not have described it correctly (I certainly left out some details). There's also the issue of robustness - there are ways to deal with this problem if you need exact results.

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