Fade2D is an easy to use Delaunay triangulation library for C++:
- Fastest multithreaded Delaunay algorithm.
- 2D Delaunay with Polygon support and Constraint Edges
- 2.5D Delaunay for Surfaces and Digital Elevation Models
- Grid Mesher, Delaunay Mesh Generator
- Polygon Clipping, Boolean Operations on Polygons
- Cut and Fill for Earthwork Volume Computations
- Free student license. Eval- and Commercial licenses with support are available
Fade2.5D – Extension for Delaunay triangulations in 2.5D
A 2.5D Delaunay triangulation is a 2D Delaunay triangulation where each point (x,y) has a certain height: 2.5D allows exactly one height value z per (x,y) coordinate pair and that distinguishes it from 3D. It works for surfaces which have an intersection-free projection to the x,y-plane like a terrain while closed objects such as e.g., a ball do not have such surfaces. Applications for Fade2.5D are surface metrology and terrain triangulation from LiDAR data. The Fade 2.5D extension comes with a buch of additional algorithms:
- Fast computation of ISO lines
- Height queries for arbitrary (x,y)-coordinates
- EfficientModel-class to reduce a point cloud within a user specified tolerance
- SegmentChecker to compute segment intersections. Works even in the practical case where two line segments intersect in (x,y) but at different heights (both heights are reported then)
- 2.5 Mesh optimization: Fade2.5D does not only lift a 2D triangulation but can optimize a triangulation for the local slope
Constrained and Conforming Delaunay
Constraint edges can be inserted. This works also in 2.5D.
Delaunay mesh generator
The mesh generator creates high quality triangles inside a given area. The quality of the triangular output mesh can be controlled by specification of a minimal interior angle that will be kept by all triangles (as far as existing constraint edges allow). Additionally a target value for the length of the edges can be specified which is often required for simulation purposes. The mesh generator is available in 2D and 2.5D.
Performance of Fade2D
Fade2D is multithreaded and very fast. One million points take 0.16 seconds on a Corei7 6800K. Have a look at this comparison of single- and multithreaded runs with large point-sets.