Fade is a C++ Delaunay triangulation library and it comes in two flavors: Firstly Fade 2D is a planar Constrained Delaunay triangulation, see the above red 2D cyclist-shape. Secondly 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
- Fast 2D Delaunay triangulation and Constrained Delaunay triangulation software for points, segments 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
- Multithreaded and optimized for speed
- Free student license. Eval- and commercial licenses with support are available
Fade 2.5D Constrained Delaunay Library
The Fade 2.5D software contains all features of Fade2D. In addition it has a z-coordinate and a bunch of additional 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.
- Finally you can 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.