Fade is a high-performance C++ Delaunay triangulation library available in two versions: Firstly, Fade2D constructs planar Delaunay triangulations with constraints, as the 2D cyclist-shape above. Secondly, Fade2.5D generates elevated Delaunay triangulations from 2.5D point clouds, such as the terrain example shown above. Both software versions come equipped with robust algorithms from the meshing field. Furthermore, we provide ready-made C++ examples that demonstrate the practical application of these algorithms:
- 2D Delaunay Triangulation Examples
- 2.5D (elevated) Delaunay Triangulations
- Practical Meshing Examples
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. Additionally, points have a z-coordinate, and the software offers advanced algorithms for elevated point clouds:
- Reduce a 2.5D point cloud with Fade’s
- Create a lifted Delaunay triangulation (a TIN) from it
- Align its edges to valleys and ridges
- Eliminate noise with weighted Laplacian smoothing
- Utilize the
Cookie Cuttertool to cut out polygonal pieces.
- Perform Cut-and-Fill for earthwork volume computations.
- Make height queries for arbitrary (x,y) coordinates.
- Compute ISO-contours from the terrain.
“To clarify, the 2.5D dimension allows exactly one z-value per (x,y)-coordinate pair. Therefore, it is well-suited for surfaces that can be projected without intersections onto the (x,y)-plane, such as terrains.”
Constrained Delaunay Triangulation
With Fade, you can effortlessly insert constraint edges into a Delaunay triangulation, transforming it into a Constrained Delaunay triangulation. Additionally, these constraint edges can be subdivided into sub-segments, ensuring the creation of well-shaped adjacent triangles.
Fade 2.5D can insert breaklines at their original 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 module produces high-quality triangles within a specified shape. These triangles can conform to a grid mesh pattern, ensuring that all points align precisely with the grid. Alternatively, you have the flexibility to set quality criteria, such as minimum interior triangle angle, maximum edge length, or constraints on size differences between neighboring triangles. This flexibility allows you to tailor the mesh generation to your specific needs, whether you prefer grid-based meshes or triangles meeting other quality criteria.
Performance of Fade
The C++ library can utilize multiple threads on different cores, delivering exceptional speed: For example, it can triangulate one million points (resulting in two million triangles) in just 0.17 seconds on a Core i7 6800K processor. You can explore a detailed performance comparison between single-threaded and multithreaded runs with large point sets.