Fade is a C++ Delaunay library and it comes in two flavors: Firstly Fade 2D is a planar Constrained Delaunay triangulation, see the above red 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 Delaunay Triangulation
- Fast 2D Delaunay triangulation and Constrained Delaunay triangulation software for points, segments and shapes
- 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 Delaunay Library
The Fade 2.5D software contains all features of Fade2D plus a z-coordinate and a bunch of additional algorithms for point clouds:
- You can use Fade’s
CloudPreparetool to reduce a 2.5D point cloud
- Then create a lifted Delaunay triangulation (a TIN) from it
- Afterwards you can align its edges to valleys and ridges
- Next 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. When Fade 2.5D is used, then it 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 just 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
Fade2D is multithreaded and very fast: Triangulating one million points (2 million triangles) takes 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.