Public Group

# closed surface

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

## Recommended Posts

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 on other sites
What you're looking for is a convex hull algorithm. Enjoy.

##### Share on other sites
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 on other sites
try these search terms:

"marching cubes"
"delauney triangulation"

also try http://gts.sourceforge.net

There are other methods :)

##### Share on other sites
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.

1. 1
Rutin
37
2. 2
3. 3
4. 4
5. 5

• 12
• 14
• 9
• 9
• ### Forum Statistics

• Total Topics
633347
• Total Posts
3011454
• ### Who's Online (See full list)

There are no registered users currently online

×