c# Point Cloud to Mesh

Question

Is it possible to reconstruct a 2.5D surface from X,Y,Z points (unstructured point cloud) to triangle mesh? Is there a library available that can do this for me that I can use with C#? I can't find anything open source out of the box that has this built in function.

First option: 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 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. A single point will always intersect with 8 triangles, except on edges which would be 4 and the connected points will be known. All X/Y's would align each 0.5 mm.

Preferred option: Would require a density estimation algorithm probably and as far as I can tell not possible without something like MatLab which I don't want to have to use.

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.

In the above option I could still align the X and Y coordinates by creating a normalization algorithm.

I can code just about 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.

I know something like this would be extremely useful to hobby CNC users. Once I create the mesh I can save the result to an STL, I have that part figured out.

Answer 1

Assuming you've captured the following points with X,Y,Z:

 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15

where you you have a vertex array, and each of the numbers above are an index into that array, generate an index array (each value is an index into the vertex array, identifying the vertex - point captured from your CNC probe - in your mesh)

// first row of quads - values are indices into the vertex array
0,1,4
1,5,4
1,2,5
2,6,5
2,3,6
3,7,6

// second row...    
4,5,8
5,9,8
5,6,9
6,10,9
6,7,10
7,11,10

// etc. ..

Identifiying the pattern here, we could say: (Apologies for the formatting, and note that is is pseudocode. I wrote this on my phone, probably tons of errors.)

int cols = 4; // number of points in X
int rows = 4; // number of points in Y

std::vector<int> ti // triangle indices;
// speed things up a bit...
ti.reserve((cols + 1) * (rows + 1));

for(int j = 0; j < rows-1; ++j)
{
for(int i = 0; i < cols-1; ++i)
{
/*

i0--i1
| / |
|/  |
i2--i3

*/
int o = j * cols + i;
int i0 = o;   // nw corner of local quad
int i1 = i0 + 1; // ne corner of local quad
int i2 = i0 + cols; // sw corner of local quad
int i3 = i2 + 1; // se corner of local quad

// upper-left triangle in this quad
ti.push_back(i0);
ti.push_back(i1);
ti.push_back(i2);

// lower-right triangle in this quad
ti.push_back(i1);
ti.push_back(i3);
ti.push_back(i2);
}
}

Now, each triplet in ti indicates the indices of of a single triangle. For instance, the first part of ti will be

[0,1,4, 1,5,4, 1,2,5, 2,6,5...] etc.

Alternatively, google "height map mesh generate from grid".

This assumes that your probe data is arranged in the pattern indicated by the "matrix" at the start of this post - ie, after probing along x, you rapid back to the other side, move to the next X, then probe again, so you get a raster pattern.

I did something similar for my DIY CNC router a few years ago. It's pretty straightforward. There may be software that does this already - I'd be surprised if not - but the algorithm is pretty basic. I'm a graphics coder so I just built my own. (Which I can't share. )

This approach does not require that the samples are at precisely regular intervals, but you'll get a better result (better approximation of the sampled object) if they are close to regular.