Mesh generation

Google marching cubes

For clarity, are you talking about trimming a portion off a mesh that is already triangulated, or removing points from a disconnected point cloud? If the former, google for constructive solid geometry. CSG involves performing set-like operations (union, intersection, defference) on geometric entities.

The way you describe it though sounds like you need some method for producing a surface from the point cloud. That's not simple to be honest - there are various special cases (ridge-and-span if the points are arranged in cross sections, or numerous methods for creating convex hulls of point clouds) but these may not be suitable for your needs, and it's often fairly trivial to come up with a pathological case that any given method will not handle well. For instance, any method that uses cross-sections will have to address changes in slice topology, for instance, what happens when the slice through your palm (a circle-ish shape) changes to the slice through your fingers? (four circles, and sorry for the painful sounding description!)

The marching cubes method relies on being able to define a signed scalar field f(x,y,z) at every point in space such that the zero-crossings, f=0, correspond to the desired surface. The mesh is then created by evaluating points on a cubic lattice and creating triangles determined by pairs of neighbouring points with opposite sign. The quality of the reproduced surface depends largely on the resolution of the lattice, so it's a tradeoff of time and memory versus results. It's unlikely to be feasible if this needs to be done in realtime for high resolution meshes. Google will have plenty on this algorithm.

The most critical part of the MC process is choosing a good signed-distance function. One method involves performing principal components analysis on a group of nearby points to determine a local tangent space. The two strongest axes of variation, along with the centroid of the local points, will define a plane. Measuring a signed-distance to the plane (positive 'inside' the mesh, negative 'outside') provides a scalar field with zero crossings at (or near) the surface. As above though, there may be simpler functions, particularly if they can take advantage of specific aspects of your point clouds.

Thank you for the response.

Wow, it sounds like I have a large amount of work in front of me. It seems like there would be an open source library available, oh well. I will give the marching cubes algorithm a try.

Once again, thank you.

I don't know about any libraries for doing this, sorry. I've never used it on a personal project, and at work we use a surface builder (that I didn't write, thankfully!) that uses a sort of hybrid method - marching cubes, but with a set of 2D cross-sectional functions that are interpolated, rather than a true 3D function.

You might want to look at the recent (last month I think) article on this site about a marching squares implementation. Marching squares, as you'd expect, is the 2D case of marching cubes, but works in basically the same way. That may give you some ideas for surface building, though I forget exactly what content was in the article.

(For interest only...)
The signed distances in this hybrid method are calculated in planes that contain polygonal cross sections - so the function is Fz(x,y) for a given slice with fixed z, Fz(x,y) being the distance to the nearest point on the polygon at slice z, signed such that 'inside' is positive. Then the surface between each pair of slices z,z+1 is built by plugging the linearly interpolated values of Fz(x,y) and Fz+1(x,y) into the standard marching cubes algorithm.

This handles topology changes reasonably well, but does produce potentially unacceptable distortions in cases where the aspect ratio is very different between neighbouring slices, i.e. if a round cross section in one slice suddenly changes to a thin ellipse in the next, the zero-crossings of the interpolated function don't form a smooth step between the two (because the signed-distance in the region internal to the thin shape is effectively clamped to the size of the shape in the 'narrow' direction, which could be arbitrarily small compared to the size in the 'long' direction and therefore arbitrarily inaccurate compared to a circle of any size.)

Anyway, This isn't a huge problem for us as we only work with real-world data from medical images (typically of bones) and don't come across this kind of unusual structure in the body, but it highlights what I meant by all of these surface-builder algorithms being susceptible to failure when faced with specific pathological cases.