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 and Constrained Delaunay triangulation for segments, polygons and shapes
- Voronoi diagram with fast nearest-neighbor search to find for arbitrary points the containing Voronoi cells
- Polygon clipping, boolean operations on polygons
- Fast segment intersection tester
- Delaunay Mesh Generator and Grid Mesher
- Fast multithreaded algorithms
- Free student/research license included. Commercial licenses with dedicated programming support are available
Fade 2.5D: Constrained Delaunay Library 2.5D
The Fade 2.5D software contains all features of Fade2D. In addition it has a z-coordinate and 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 breakline-elevation or it can adapt them to surface-level before insertion.
Delaunay Mesh Generator and Grid Mesher
The Mesh Generator software creates high quality triangles inside a given area. For example the user can either claim a simple quality feature like the minimum interior triangle angle. But he can also precisely control the mesh generation procedure where possible parameters are the maximum edge length, a grow factor on neighbored triangles and grid alignment.
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.