Jump to content
  • Advertisement
Sign in to follow this  
dinaharchery

Mesh generation

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

I have hit a wall and I hope someone out there has an idea and please help me. Say I have a point cloud(set of points in x,y,z space) and another set of points that form a cut-off line - i.e., a curve beyond which the points in the point cloud should be removed. I would like to take the remaining points from the point cloud and retriangulate them such that a surface can be rendered. I think that it would be easiest to render the point cloud as a mesh and trim off the values beyond the cut but am unsure. I have no idea where to start and if anyone could even point me to a algorithm page so that I can understand mesh construction that would be great. Thanks for any help

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!