Hi all,
I have a set of closed curves formed by an array of vertices.
I need to create a surface joining the vertices of neighbors curves. Anyone have any suggestions?
Thanks!
There are infinitely many ways, but it depends on the organization and character of your data and on what you want. Is there one “correct” answer, or do you just want any surface that passes through the vertices?
If your array of vertices is rectangular, then you could just form a triangle strip between each pair of neighboring rows of vertices. For example, send the first vertex each of the first and second row with the second vertex of the first row for your first triangle, then send the second vertex of the second row for your second triangle, then the third vertex of the first row for your third triangle, and so on, to the end of the two rows. Then repeat for the second and third rows of vertices. Repeat all the way to the last two rows of vertices. You would define one less triangle strip than you have rows of vertices.
If you don’t know what you need yet, I’d start with something especially easy to implement to get started and go from there.
hi david_f_knight, thank you for your help.
I will try to be more precise.
Think of a 3D object that is cut into several slices. Now, imagine that the outline of each slice is formed by a closed curve. Each curve may contain a different form and, perhaps, a different number of vertices. Now, I want to do the opposite path. I have the outlines of the slices that are closed curves, and I want to reconstruct the 3D object. I wonder if there is any algorithm that can generate a surface from a set of curves that representing cross sections of the 3D object.
Thanks!
In the general sense, it is impossible to create any algorithm that will be guaranteed to always work for any 3D object, unless the vertices are sampled close enough to prevent ambiguity in determining which are neighbors to each other.
This approach is somewhat similar to my previous suggestion, but generalized somewhat. Process your vertices slice by slice (I assume you already know which slice any given vertex belongs in; if not that’s your first task). You need to find best-fit triangles that span neighboring slices. This is how I’ll define best-fit triangle: given two consequtive vertices (call the line between them the base edge) in one slice (call this the base slice), find the nearest vertex to them in the neighboring slice on one side. Those three vertices define the best-fit triangle between those two slices for that base edge.
Every slice needs to take its turn as a base slice.
For a given base slice, proceed around it for each base edge. There will be as many base edges as there are vertices in that base slice. For each base edge, find the one nearest vertex in the neighboring slice (do this for the slice on either side of the base slice, resulting in two best-fit triangles for each base edge). This will define twice as many best-fit triangles as there are vertices in the base slice, unless the base slice is on either end of the 3D object in which case it will only define as many best-fit triangles as there are vertices in the base slice. Deal with the cap covering each of the two end slices as special cases later; essentially, each is a planar polygon.
This algorithm does not require that the number of vertices in one slice match the number in the next slice, nor does it require the spacing of those vertices be uniform on any slice. I believe the result is guaranteed to be both watertight and to have no intersecting triangles as long as the vertices have been sampled close enough/dense enough that the nearest neighbor vertex is the nearest neighbor on the actual 3D object. If your vertices haven’t been sampled close enough, then there is no solution that can guarantee correctness, because in that case your data is ambiguous.
UPDATE:
The algorithm above will not guarantee either watertightness or non-overlapping triangles as is. Some additional intelligence will need to be added to ensure that any best-fit triangle on one slice does not cross the best-fit triangle of a neighboring slice. I’d have to think some more about that. In any case, that will make determining best-fit triangles with this algorithm more complicated.
Okay, I’ve given more thought to the problem of determining best-fit triangles so that watertightness and non-overlapping triangles is guaranteed. The corrected algorithm is not much harder than the faulty one I originally presented.
Same definition of base slice, base edge, and best-fit triangle. Also define the apex vertex as the vertex on the neighboring slice used to define a best-fit triangle.
Every slice except the last one needs to take its turn as a base slice.
For a given base slice, proceed around it for each base edge. There will be as many base edges as there are vertices in that base slice. For each base edge, find the one nearest vertex in the neighboring slice (do this for the slice on just one side of the base slice and the neighboring slice must always be taken from that same side). This will define as many best-fit triangles as there are vertices in the base slice.
Deal with the cap covering each of the two end slices as special cases later; essentially, each is a planar polygon.
Once the second best-fit triangle has been determined for the base slice, zero or more triangles need to be defined going from the neighboring slice back to the base slice, and all of them will share the same vertex on the base slice: the vertex that is shared by the two base edges.
If both best-fit triangles share the same apex vertex, then there will be no triangles going from the neighboring slice back to the base slice. Otherwise, there will be one more triangle going from the neighboring slice back to the base slice as there are vertices on the neighboring slice between the two apex vertices.
When the third best-fit triangle on the base slice is found, repeat the process of defining triangles from the neighboring slice back to the base slice, but this time between the second and third best-fit triangles.
Repeat for each subsequent best-fit triangle on the base slice. After the last best-fit triangle has been defined, the triangles from the neighboring slice back to the base slice between the last and first best-fit triangles will need to be defined as all the others have been.
Thanks David_f_knight for your attention.
I will try to implement your suggested algorithm and come back to post results.
Thank you!