Fade is a fast C++ Delaunay triangulation library and it comes in two flavors: First, Fade 2D is a planar Constrained Delaunay triangulation, see the above red 2D cyclist-shape. Second, Fade 2.5D creates elevated Delaunay triangulations from 2.5D point clouds like the above terrain, for instance. Both software versions are equipped with additional robust algorithms from the meshing field. Moreover, ready-made C++ examples demonstrate the application of these algorithms:
Fade 2D: Constrained Delaunay Triangulation
- Delaunay triangulation for 2D points, multithreaded
- Constrained Delaunay triangulation for segments and polygons
- Polygon clipping, boolean operations on polygons
- Voronoi diagram with fast nearest-neighbor search
- Fast segment intersection tester
- Delaunay Mesh Generator and Grid Mesher
- Free student/research license included. Commercial licenses with dedicated programming support are available
Fade 2.5D: Delaunay Triangulation for Elevated Point Clouds
The Fade 2.5D software contains all features of Fade2D. In addition points have a z-coordinate and the software provides additional high-end algorithms for point clouds:
- You can reduce a 2.5D point cloud with Fade’s
- Then create a lifted Delaunay triangulation (a TIN) from it
- Afterwards you can align its edges to valleys and ridges
- Then eliminate noise with weighted Laplacian smoothing
- Or use the
Cookie Cuttertool to cut out polygonal pieces.
- Use Cut-and-Fill for earthwork volume computations.
- If required make height queries for arbitrary (x,y) coordinates.
- Or compute ISO-contours from the terrain.
“To clarify, 2.5D allows exactly one z-value per (x,y)-coordinate pair and as a result it is suitable for surfaces which have an intersection-free projection to the (x,y)-plane like terrains. “
Constrained Delaunay Triangulation
The Fade software can insert constraint edges into a Delaunay triangulation and thus make it a Constrained Delaunay triangulation. Moreover, the constraint edges can be subdivided into sub-segments to achieve well-shaped adjacent triangles.
Fade 2.5D can insert breaklines at their elevation or it can adapt them to surface-level before insertion. It can subdivide the segments automatically to better fit the surface.
Delaunay Mesh Generator and Grid Mesher
The Mesh Generator software creates quality triangles inside a given shape. You can claim a quality feature like the minimum interior triangle angle. But you can also precisely control the mesh generation procedure according to parameters like the maximum edge length or a bound on the size-difference of adjacent triangles, for example.
Performance of Fade
The C++ library can run multiple threads on different cores and is very fast: It triangulates one million points (2 million triangles) in 0.17 seconds on a Core i7 6800K, for instance. Have a look at this comparison of single- and multithreaded runs with large point-sets.