Question [Solved] How to best group vertices that are nodes of two curves when creating triangles for a pl...

Hello,
I'm working on a mesh generation script.
There are two curves in a 3D space, each curve has more than two nodes. I want to create a mesh of a plane where these two curves are two sides of the plane.

The nodes are used as vertices, and then I'll need to get the value for the mesh.triangles. Each curve may have different number of nodes (vertices), so how shall I group them into triangle int[], so that firstly, all vertices are used in order to best describe the shape, and secondly, no triangle is in overlap with another for better performance?

PS: These two curves will always be almost parallel, and they have no intersection when we see them in xy, xz, or yz planes. So we don't need to think about any complicated/special senario, e.g. picking vertices in different orders from two curves for different triangles.

Please see the attached picture.
Thanks very much.

 

Is it highly performance critical how long the procedure takes?
Since otherwise I'd use a trick I've used before for a similar case: Apply a Delaunay triangulation (implementations on github) on all points independently of the curve and then iterate through all triangles and remove ones that have been constructed solely with points of one curve, since those would be outside your desired curve.

As for a more focused solution: I'd imagine having a virtual train that tries to run down this track. We can say it has flexible wheels so that Its axle would be in an angle that would be the average of what angle is exactly perpendicular on either curve.
Then whenever its "wheels" hit a point, you add those to a list. From that list it should not be too hard to form a set of triangles.

 

Hi @DragonCoder, thank you so much for your reply. I've checked out the Delaunay math theory, it is beyond me and I'm not sure if I can understand the delaunay project from github. But the virtual train solution really solves the problem since the vertices indeed belong to two curves, which is a special case for the delaunay.

I applied two rules to each vertice, if it's a beginning or an end point, it can only work with one vertice from the same curve to form a triangle, for other vertices, each one shall work with two other vertices from the same curve, unless no eligible vertice from the same curve has been passed by the train. So each time a vertice is passed by the trian, it can only form 1 triangle with existing other vertices train passed, or just wait for the trian to pass more.

The process wsa not highly performance critical, but this solution is not heavy anyway.
Thank you very much for the tip!!

 

Anyone knows how to flag this Question to Solved?

 

You can just rename the thread.

 

Thanks

 

I don't either but yet used it (for a case where curves were effectively splitting up) The idea was to utilize that as a drop in algorithm (without modifying its internals etc.), since its interface is fairly simple: Points go in; a list of triangles for a coherent mesh using all those points comes out.

Glad you solved it with the more target-oriented idea

 

Delaunay is quite promising, especially when it comes to the need for modifying a vertice and more senarios, if the interfaces are already there , I'll definately check the project out for future use. Thanks a lot.

 

Here's a site that not only covers the general theory, but explains it well with examples, as well as several related things.

https://www.habrador.com/tutorials/math/

It's worth learning Delaunay if you plan on doing anything with triangulation in the future.

 

For the simple cases without implementing full Delauny triangulation you could do something like this:

For the triangle cost function there are couple of options not sure which one would work best but most of them will probably give somewhat reasonable results:
* longest edge length
* difference between smallest and largest angle
* largest angle

Code (CSharp):

1.  
2. // WARNING pseudocode, don't expect it work by copy and pasting without understanding it and filling in gaps.
3. // Might lack handling of some edge case or off by 1 errors.
4. int left = 0;
5. int right = 0;
6.  
7. while (left + 1 < leftLine.size() && right +1 < rightLine.size()) {
8.     if (triangleCost(leftLine[left], leftLine[left+1], rightLine[right]) <  
9.         triangleCost(leftLine[left], rightLine[right+1], rightLine[right])) {
10.         addTriangle(leftLine[left], leftLine[left+1], rightLine[right]);
11.         left++;
12.     } else {
13.         addTriangle(leftLine[left], rightLine[right+1], rightLine[right]);
14.         right++;
15.     }
16. }
17.  
18. // create the remaining triangles once one side is emptied
19. while (left + 1 < leftLine.size()) {
20.     addTriangle(leftLine[left], leftLine[left+1], rightLine[right]);
21.     left++;
22. }
23.  
24. while (right + 1 < rightLine.size()) {
25.     addTriangle(leftLine[left], rightLine[right+1], rightLine[right]);
26.     right++;
27. }

Might need a bit of extra special care if you want to handle sharp bends with few points. Unless taken into account the code above might produce few overlaping/going backwards triangles in such corners depending on exact point positions and triangleCost function chosen. Could be reduced by adding additional check whether points are on the sides you expect them to be when choosing between advancing left or right.

 

Here is the example of corners I was talking about. It's probably easiest to just try it out to see which of the cost functions perform better in such situations. Or maybe you have placed the points sufficiently close so this is not a probably at all. I assume that if there were additional points on the top of outer line none of the cost functions would produce bad results.