Unstructured point cloud to mesh?

[Stevesy68]

I apologize in advance if this is addressed in a tutorial or forum or this shouldn't be asked here but I've been searching for hours and haven't found it. Is it possible to reconstruct a surface from X,Y,Z points (unstructured point cloud) to triangle mesh with G3Sharp?

Here's the scenario. I have a CNC that I can capture position data with. I'll be scanning from a specific axis and taking measurements at specific intervals. So for instance, I move across the X axis and get a probe measurement every 0.5 mm. I'll have the X, Y and Z point every 0.5 mm. After I complete my X axis scan, I'll move Y by 0.05 mm and then scan across the X axis again. It seems turning this into a mesh should be pretty straight forward.

It would be better if I didn't have to take a measurement at consistent X axis intervals. The laser displacement sensor and associated equipment will allow me to capture point data at 50hz. I would rather take as many measurements as possible in that time period as I scan across X but its highly likely the X at the previous Y position will not align.

I can code anything in C#, but I know little about 3D terminology. So I apologize in advance if I'm using the wrong wording to describe what I'm trying to accomplish.

[rms80]

What level of precision are you hoping for here? I can describe some ways you could do this with voxelization techniques but unless your objects are tiny, you are going to need enormous voxel resolution to reconstruct a surface in the ballpark of 0.05mm resolution.

It sounds like you probably want to do geometric stitching similar to the uniform grid you would get from the regular grid spacing. Then you exactly preserve the points. Since you are getting rows, you can do this incrementally, and since it is a height-field you can basically do it in 2D. You could use a Delaunay triangulation, but g3Sharp does not have an implementation of this yet. The MeshInsertUVPolyCurve class could be modified to do something similar, if you ripped out the insert-curve part and just did the face-pokes...would require some experimentation though.

[Stevesy68]

Most shapes would be 6" - 12" X 6" - 12" I guess about 345,744 points in a 12X12? Couldn't I just construct indices since its a grid?

Assuming my indexes are 1,2,3,4 5,6,7,8 Each index would correspond to a point X,Y,Z

My indices (triangles) would be 1,2,5 2,6,5 2,3,6 3,7,6 3,4,7 4,8,7 etc...

Not sure how I would put that in G3Sharp but an obj file would be easy.

[BenCSIRO]

I'm also looking for a point cloud -> mesh solution. There's surprisingly little out there for C#. I'd be perfectly fine with a voxel-based solution but the main requirement for me is that the result is more or less solid and can be rendered as a mesh without any significant loss in surface detail. I'd ultimately be converting it into an implicit surface so that I can perform boolean operations on it.

EDIT: I should mention my requirements are 3D, not 2.5D.

[rms80]

@Stevesy68 yes you could just write in an obj and then load it back in. Alternately you could use DMesh3Builder, see this tutorial: http://www.gradientspace.com/tutorials/2017/7/20/basic-mesh-creation-with-g3sharp

@BenCSIRO one way to do this currently, that will work but is quite slow, is to generate a triangle-fan (a small disc) around each point and then use the Mesh Winding Number to isosurface it. This tutorial describes how to get a coarse voxel surface: http://www.gradientspace.com/tutorials/2017/12/14/3d-bitmaps-and-minecraft-meshes

Once you have the voxel surface you could re-project the vertices onto the input mesh.

My software tool Cotangent has a more sophisticated way of doing this but it is not open source: https://www.youtube.com/watch?v=pItGYN22AE4

There is a variant of the algorithm I use for this that works directly on points. But it requires some other geometric operations I don't have implemented yet. I will get to it eventually.

[rms80]

I added an implementation of the point-set winding number, which can be used to surface point clouds: http://www.gradientspace.com/tutorials/2018/9/14/point-set-fast-winding

However you do need (approximate) normals at each point

[Stevesy68]

I added an implementation of the point-set winding number, which can be used to surface point clouds: http://www.gradientspace.com/tutorials/2018/9/14/point-set-fast-winding

However you do need (approximate) normals at each point

That looks like exactly what I was looking for...thanks! I'll give it a try in a couple days.

[BenCSIRO]

This looks great, @rms80, thanks for putting time into this. For approximation of normals with just a point set, would you be able to provide any basic advice?

[rms80]

The standard approach is to find neighbours (N-nearest, in-ball, etc), fit a plane to those points, and then use that planes normal as the point normal. One complication is that the plane fitting can't know inside vs outside so then you usually need to postprocess the normals to improve alignment (eg you fix one and propagate to neighbours)

PointHashGrid3d and PointAABBTree3 both have find-nearest-point queries, neither has find-N-neighbours queries but it would not be hard to add. OrthogonalPlaneFit3 can be used to fit the plane.

[petrasvestartas]

Dear @rms80 would it be possible to get a full example for dummies how to create a mesh from a small pointcloud that has no normals?

[speed-wagon]

I added an implementation of the point-set winding number, which can be used to surface point clouds: http://www.gradientspace.com/tutorials/2018/9/14/point-set-fast-winding

However you do need (approximate) normals at each point

@rms80 I have successfully been able to recreate the sphere mesh in this tutorial. But I cant figure out how to get my own list of points into this procedure.

I.e. Mesh3 pointSet = (load XYZ file here...) [from the tutorial] how do i just pass my list of points to this? rather than importing a file.