Delaunay triangulation

I have created multiple parallel splines and would like to create a surface delaunay triangulation inbetween points of neighbouring splines. Now the issue is the delaunay also creates triangles between points on the same Spline due to the curvature of the spline. Is it possible to control the maximum size of the triangles or the plane in which the triangulation occurs?

Thanks in advance

Consider two splines at a time.

Try to add constraint line segments that connect two points (p1 from one spline and p2 from another nearby spline). Even better if the constraints are exactly perpendicular to your splines. Then use contained delaunay algorithm.

Here’s a quick illustration. Try to join two nearby points with the green line segments and now triangulate this geometry with a CDT algorithm… If your points are nicely distributed along the length of the splines, you’d get a neat triangulation! That’s the first part of the trick.

Now, since Delaunay algorithm tries to generate a convex hull in the end, you’ll observe triangles beneath the blue line and possibly in the concave parts of the black spline.

To remove those, I’d suggest looping over each triangle, figuring out a closed polygon with blue, black spline as boundary and clipping away those exterior triangles.

Feel free to ask any questions :slight_smile:

1 Like

You might also want to check out the stream surface filter. It’s original purpose was to stitch streamlines together into a surface. You might be able to adapt it for your needs.

2 Likes

Thanks for the help. It worked well. The triangulation sometimes misses out individual triangles, for no obvious reason (on first sight). Have you ever dealt with these issues?

Sorry for the late reply but vtkDelaunay filter is not exactly the best implementation of that algorithm. So you could wait until we get a robust one into VTK or use external ones from CGAL or mapbox.

FYI, a bridge between VTK and CGAL is in progress and should come in the forecoming days. As it is still in development, no delaunay filter will be available at start but:

  1. It will be quite easy to add
  2. We may eventually need to add one anyway.

I will keep you in touch

Great stuff, thank you.