Geom Software - C++ Programming and Geometry Libraries
Fade2D Documentation pages v1.81
Fade2D Documentation

C++ Constrained Delaunay Triangulation Fade2D

Delaunay triangulation with Fade2D

Delaunay triangulation 2D

Constrained Delaunay triangulation

Constrained Delaunay triangulation

Zones in a triangulation

Zones in a triangulation

2D Mesh Generator

2D Mesh generation

Fast Segment Intersection Test Algorithm

Segment Intersection Detection: 1000 Segments checked in 0.003 s

Terrain triangulation with Fade2.5D

Terrain triangulation 2.5D, 550 000 triangles computed in 0.31 seconds (Core i7 870)

Terrain triangulation 2.5D, ISO contours

ISO contours of 550 000 triangles at 30 different elevations computed in 0.38 seconds (Core i7 870).

Cut And Fill: Earthwork Volume Computations, C++ Library

Cut And Fill: Earthwork Volume Computations between two surfaces

Getting started with Delaunay triangulations:

Download. Unzip. Start to play with the included example source codes. It works without installation. The first example is described here.

Fade comes as two separate libraries, Fade2D and Fade2.5D. Fade2.5D can do everything that Fade2D can do. But Fade2.5D offers a z-coordinate and additional functionality for Digital Elevation Models (DEM) and surfaces. A collection of 2D and 2.5D example source codes is contained in the download. The examples go step by step over the concepts of Fade. New Fade2.5D users are advised to start with the 2D examples because the basics are described there and these apply also to Fade2.5D.

Documentation Download
Fade 2D HTML (this document) PDF Download Fade2D and Fade2.5D v1.81
Fade 2.5D HTML PDF

For Windows users:

  1. Open one of the Visual Studio example projects (currently supported: VS2010, VS2012, VS2013, VS2015, VS2017, VS2019)
  2. Compile the example source code. The executable is written to the Win32 or x64 folder.

When you link Fade with your own software you can use the settings from the example solutions or use the table below:

Visual Studio IDE version Platform Toolset
VS2010 version 10 toolset v100 or Windows7.1SDK
VS2012 version 11 toolset v110
VS2013 version 12 toolset v120
VS2015 version 14 toolset v140
VS2017 version 15 toolset v141
VS2019 version 16 toolset v142

For Linux and Apple users:

  1. Edit the Makefile (choose Apple, your Linux distro or Raspberry PI) and type make to compile the example source code.
  2. Make sure GMP is installed:
    $ sudo apt-get install libgmp10 (works on Ubuntu/Debian/Mint/Raspbian, on other systems search for libgmp or gmp)

Work through the provided examples. They are small, well documented and they visualize the results.

Directory Contents

  • include_fade2d and include_fade25d
    Header files of the two libraries.
  • Win32 and x64
    This directory contains the DLL's for Windows 32-bit and 64-bit and it is the target directory for the executables of example code compiled with Visual Studio.
    The shared libs (*.so) for Linux/Apple developers.
  • examples_2D
    Example source code and Visual Studio projects using Fade2D
  • examples_25D
    Example source code and Visual Studio projects using Fade2.5D
  • doc
    PDF Documentation


  • Mixing multiple Visual Studio versions won't work. Use the right dll.
  • Compare your settings with the ones from the example projects.
  • In rare cases you might need to increase Properties->ConfigurationProperties->Linker->System->StackReserveSize in your Visual Studio project settings.
  • If your problem persists, don't hesitate to send a minimal example that reproduces it and it will be fixed asap.

Release notes / History

Version 1.81, May 17th, 2020:

  • Memory Leak in EfficientModel fixed. EfficientModel improved: Pruning the point cloud is much faster now and the new method zSmoothing() has been implemented. It provides minimum-, maximum-, median- and average-smoothing.

Version 1.80, March 25th, 2020:

  • Bug in Cut&Fill solved: A foot point was computed in 3D while it should have been computed in 2D. The difference was in most cases insignificant and thus the problem did not become apparent earlier. Sorry. Fixed.
  • Improvement in Cut&Fill: The algorithm checks now if the two input zones do overlap. If not, the CutAndFill::go() method returns false and the CutAndFill object shall not further be used.
  • Example source codes adapted and -std=c++98 removed from their Makefiles
  • Documentation improved

Version 1.79, January 20th, 2020:
Internal version. Revision.

Version 1.78, November 15th, 2019:

  • Bugfix: Multithreading did not work in Windows versions due to a CMake configuration error.
  • A typo in the function name Fade_2D::measureTriangulationTime() has been corrected.

Version 1.77, October 21st, 2019

  • Support for Visual Studio 2019.
  • A bug has been fixed: In a rare case a self-intersecting constraint graph could generate an error.
  • Improvements: The constraint-insertion-strategies CIS_CONFORMING_DELAUNAY and CIS_CONFORMING_DELAUNAY_SEGMENT_LEVEL are deprecated now.
  • The fast and reliable replacement is CIS_CONSTRAINED_DELAUNAY along with the new methods ConstraintGraph::makeDelaunay() and Fade_2D::drape(). See the new example code in examples_25D/terrain.cpp.

Version 1.75 and 1.76

  • Non-public test versions.

Version 1.74, March 19th, 2019:

  • Cleanup: The (until now experimental) surface reconstruction module has been moved into the separate WOF Point Cloud Meshing library ( This makes the Fade binaries smaller and it improves the maintainability of the code.
  • Cleanup: Support for VS2008 has been dropped (if you are a commercial user and still need VS2008 then contact the author please!).
  • The build system has been migrated to CMake to reduce the manual work and to guarantee uniform flags for all builds.
  • The HoleFiller class that has been developed for the removed surface reconstruction module is retained in Fade because it has already users. Its code has been revised in order to provide repeatable results for identical inputs.
  • According to a user request the MeshGenParams class (used for advanced Delaunay Meshing) offers now a method to lock certain constraint segments such that they are not splitted while all others can be splitted if required.

Version 1.73, January 14th, 2019:
While all below mentioned versions after v1.63 were development versions the present v1.73 is again an official release version for all. The work of the below internal versions is included as well as a bugfix in the getProfile() method of the IsoContours class (this method was new and experimental in v1.63)

Version 1.71 and 1.72, October 24th, 2018:
(internal) Hole-Filling (Polygon-Triangulation) improved.

Version 1.70, October 17th, 2018:
(internal) Hole-Filling (Polygon-Triangulation) improved.

Version 1.69, October 15th, 2018:
(internal) Hole-Filling (Polygon-Triangulation) improved.

Version 1.68, September 14th, 2018:
(internal) Hole-Filling (Polygon-Triangulation) improved.

Version 1.67, September 4th, 2018:
(internal) Hole-Filling (Polygon-Triangulation) is now offered via. an API call. Intermediate beta release.

Version 1.66, August 25th, 2018:
(internal) Bugfix in Cut&Fill: An intersection point could be slightly off its expected range. Solved. Unofficial intermediate version.

Version 1.65, July 29th, 2018:
(internal) Another bugfix in Cut&Fill. Unofficial intermediate version.

Version 1.64, July 21st, 2018:
(internal) Bugfix in the Cut&Fill module: In rare cases Cut&Fill crashed due to unexpected numeric deviation (fixed). The importTriangles() function has been reimplemented and is considerably faster now. And there is a change that affects only 32-bit users: Binary files written with the writePointsBIN() and writeSegmentsBIN() functions on 32-bit machines were not readable on 64-bit machines. The format on 32-bit machines (read/write) has been adapted to match exactly the one of 64-bit machines. But note that old 32-bit files are not readable anymore. This should affect next to nobody, thus this solution has been chosen.

Version 1.63, June 10th, 2018:
Cookie-Cutter operation added. 3D Point Cloud Reconstruction added to the API (but is still under development, pls. take it as a preview). Raspberry PI support added again.

Version 1.62, June 3rd, 2018:
3D Point Cloud Reconstruction considerably improved. Unofficial demo.

Version 1.61, May 1st, 2018:
3D Point Cloud Reconstruction: Unofficial demo.

Version 1.60, February 26th, 2018:
Accurate computation of glancing segment intersections. Additional parameter for Advanced Meshing: bool bKeepExistingSteinerPoints=true in MeshGenParams makes all Steiner points from previous refinement calls static, i.e. unremovable during subsequent refinement calls. This way Advanced Meshing can be carried out for several zones of a triangulation such that it does not destroy what has been meshed so far.

Version 1.59, January 14th, 2018:
Performance upgrade: Multithreading is available now. Large point sets reach a speedup of 4.4 on a hexacore CPU (i7 6800K)

Version 1.58, October 23th, 2017:
Mesh Generator refactored. Delaunay Meshing is +10x faster now. A function to create polygons from boundary edges has been added.

Version 1.57, October 9th, 2017:
Nonpublic test version.

Version 1.56, September 24th, 2017:
Bugfix: createConstraint() crashed in a rare case. Solved. Functions for binary file I/O added.

Version 1.55, August 12th, 2017:
Access to internal Cut&Fill datastructures revised. Example source codes revised. Support for Visual Studio 2017 added.

Version 1.54beta, August 8th, 2017:
Access to internal Cut&Fill datastructures. This is a pre-released beta version, code quality is good but final tests and documentation updates required.

Version 1.53, July 15th, 2017:
Error corrections and performance upgrades in the still quite new Cut&Fill library module.

Version 1.53 beta, June 2nd, 2017:
The new Cut&Fill library module has been added. Cut&Fill computes the volume between two surfaces.

Version 1.51 beta, May 27th, 2017:
Non-public test version

Version 1.50, April 5th, 2017:
After three internal test versions (that concetrated on refactoring and rare bugs) this is again a stable public release version: The constraint insertion subsystem has been rewrittten and is faster now. Visualization improved. Exact orientation tests provided through the API. Improved progress bar support. Mesh generator improved.
Users who upgrade from earlier Fade versions: The Zone2::getArea() and Triangle2::getArea() methods have been replaced by getArea2D() in Fade2D and by getArea2D() AND getArea25D() in Fade2.5D. The reason is that the old getArea() method was easily misunderstood in Fade2.5D (it returned the same result as getArea25D() now). We have decided to remove the old method to avoid confusion and a potential source of error. If necessary, please adapt your code.

Version 1.49, March 2nd, 2017:
Constraint insertion subsystem improved. Mesh generator revised.

Version 1.48, February 15th, 2017:
Corrections of yesterday's v1.47 version.

Version 1.47, February 14th, 2017:
The focus of this (for now) non-public version is stability: Intersecting constraint segments must be subdivided although their exact intersection is not always representable with double precision coordinates. Thus tiny rounding errors are unavoidable and these caused trouble in very unlikely cases. The constraint insertion subsystem has now been re-implemented to behave robust also in such cases.

Version 1.46a, January 14th, 2017:
+++ Raspberry PI is supported now +++ // Appart from RPI support version 1.46a is equal to v1.46. Raspberry PI users: Please give feedback, do you have everything you need for RPI development now?

Version 1.46, January 8th, 2017:
+++ MacOS is supported now +++ // A new class EfficientModel takes oversampled 2.5D point clouds and returns a subset that represents the model efficiently. The automatic pruning process runs in a controlled fashion such that a user specified maximum error is kept. // The Delaunay Mesh Generator is now supported by a Grid Mesher, thus it creates more regular meshes. // The Delaunay triangulation of specific point sets is not unique, for example when grid points are triangulated (4 points on a common circumcircle). To improve the repeatability and for reasons of visual appearance the new method Zone2::unifyGrid() has been implemented. // A problem in the point location method Fade_2D::locate() when the query point was exactly on the convex hull of the triangulation has been solved.

Version 1.43, November 20th, 2016:
Better example source code for the new SegmentChecker class. And the SegmentChecker of v1.42 returned false positives, this problem is solved now.

Version 1.42, October 19th, 2016:
The new tool SegmentChecker takes a bunch of segments and fully automatically identifies intersecting segments. The underlying data structure makes the tool incredibly fast. Intersecting segments can be visualized. Intersections can be computed in 2D and 2.5D (with heights). A new module named TestDataGenerators creates random polygons, random segments, points, random numbers and polylines for automated software stress tests. Progress bar support added.

Version 1.41, July 24th, 2016:
New constraint insertion strategy. Minor bug fixes. Performance slightly improved.

Version 1.40 beta, June 14th, 2016:
Non public intermediate test version. Bounded zones introduced: Mesh generation algorithms require that zones are bounded by constraint segments. This is certainly the case for the most usual zones with zoneLocation=ZL_INSIDE. But other types of zones may be unbounded and in this case remeshing won't work well, so it was necessary to change the behavior: From now on calling refine() and refineAdvanced() is only allowed with zones whose zoneLocation is ZL_INSIDE or ZL_BOUNDED. A bounded zone can easily be gained from any other zone using Zone2::convertToBoundedZone(). Also new: Fade_2D::createConstraintGraph(..) has now a third parameter 'bool bOrientedSegments=false'. By default it is false to provide backwards compatibility. This parameter allows you to specify that the provided segments are CCW oriented. This way more complex inside- and outside-zones can be formed. Performance of Fade_2D::createConstraint(..) drastically improved.

Version 1.39, May 31st, 2016:
Non public intermediate test version.

Version 1.37, March 15th, 2016:
Small upgrade: The performance of the remove method has been improved.

Version 1.37, March 10th, 2016:
Interface change in the MeshGenParams class. The class has been introduced two weeks before, so chances are good that the change does not affect you. Previously the class had the methods getMaxTriangleArea(double x,double y) and getMaxEdgeLength(double x,double y) where x and y where the barycenter of a triangle for which the algorithm determines if it must be refined. The change is that x and y have been replaced by the triangle itself to give client code even more control (x and y can still be computed from the triangle).

Version 1.36, February 29th, 2016:
Experimental method refineExtended(..) replaced by the (now permanent) method refineAdvanced(MeshGenParams* pParams). This method allows much more control over the mesh density.

Version 1.34, February 14th, 2016:
Vertex management subsystem revised (sometimes Vertex removement did not work as expected). Performance improvement.

Version 1.33 PreRelease, January 17th, 2016:
The previous official Fade version is Fade 1.24. It was released 6 months ago. Since then major developments have been made and now a big upgrade follows with version 1.33.14: Constraint segments may intersect now and they are automatically subdivided at their intersection points. Import of existing triangles is supported and one can cut through static triangulations. This version is well tested. It also runs at two customers sites with no known problems. But due to the large amount of new code we call this version a pre-release. Please report if you find any problems and note that it is also helpful if you report that the library works well in your setting. The DLL names have been adapted to the safer and more convenient pattern


If you upgrade from an earlier version it is recommended that you remove any previous Fade DLL's to avoid unintended linking to an old version.

Version 1.31 and 1.32, December 1st, 2015:
Non public intermediate release, improves the CDT.

Version 1.30, November 18th, 2015:
Non public intermediate release, improves the refineExtended method.

Version 1.29, October 17th, 2015:
Non public intermediate release. The method importTriangles() detects invalid input data now and returns NULL to avoid an assertion or even an infinite loop when the input data is not clean. The possibly invalid input elements are written to stdout and a postscript file visualizes where the problem occurs.

Version 1.28, October 10th, 2015:
Non public intermediate release. Customer specific code revised. Stress tests with random polygons and segments have been made. Heap checking to ensure proper memory handling.

Version 1.27, October 5th, 2015:
Non public release, improvements of the recently implemented functions, especially of customer specific code Fade_2D::importTriangles() and Fade2D::cutTriangles().

Version 1.26, September 8th, 2015:
New functions of the last inofficial version 1.25 have been revised. Constraint segments may intersect now.

Version 1.25, August 18th, 2015:
Intermediate pre-release with new features: importTriangles() imports arbitrary triangles into a triangulation, cutTriangles() allows to insert a constraint segment as if it where a knife, getOrientation() provides an exact orientation test. Zone2 objects can now also be made from a set of triangles. Constraint segments can intersect now. These features correspond to a large amount of new code: Please test v1.25 carefully before deploying it in a production environment.

Version 1.24, July 22nd, 2015:
Public release of version 1.23's improvements. And I'm sorry but we had a bug in Fade_2D::getVertexPointers(..). The method may have missed to return a few pointers after a call to refine() or remove(). This bug is fixed now.

Version 1.23, July 9th, 2015:
Internal test release with the new refineExtended() method for the specific needs of a certain client software.

Version 1.22, May 25th, 2015:
Code refactored, build system refactored and as a result improved Linux support: CentOS 6.4, Ubuntu 14.04, Ubuntu 15.04 and similar systems. Removement of points has been implemented, Delaunay meshing has been reworked, sqDistance() has been replaced by sqDistance2D() and sqDistance25D() because both versions are useful in 2.5D. OpenMP has been removed, it was only used under Linux and currently I work on a better way to provide multithreading.

Version 1.21, May 17th, 2015:
Unofficial intermediate release. Testing new features.

Version 1.20, April 5th, 2015:
3D scene Visualization for (up to date) web browsers added. Misleading enumeration values CIS_KEEP_DELAUNAY and CIS_IGNORE_DELAUNAY have been replaced by CIS_CONFORMING_DELAUNAY and CIS_CONSTRAINED_DELAUNAY (the two deprecated names are kept for backward compatibility). Bug in the free function center(Point2&,Point2&) solved. Major revision of the documentation pages. The source codes of the examples have been reengineered and are included in the present documentation pages.

Version 1.19, October 26th, 2014:
Support for Visual Studio 2013 (VC12) has been added. Only minor code changes.

Version 1.18.3, June 9th, 2014:
Delaunay Mesh Generation has been improved: Better quality, better performance. API improved. Small bug fixes.

Version 1.16.1, February 10th, 2014:
Small update: In rare cases it was possible that subdivided ConstraintSegments caused problems in combination with zone growing. This is fixed now.

Version 1.16, February 3rd, 2014:
Constrained Delaunay triangulation improved, Delaunay meshing improved, aspect ratio meshing (experimental) added. Minor bug fixes. Added support for Visual Studio 2012.

Version 1.14, November 2013 and version 1.15, December 2013:
Non-public intermediate releases (test versions with experimental features).

Version 1.13, August 4th, 2013:
Mesh generation (Delaunay Meshing) has been improved and two bugfixes have been made in the new IsoContours class: A message can be suppressed now and a numeric problem has been fixed.

Version 1.12, June 30th, 2013:
Starting with version v1.12 the download consists of two separate libraries: The familiar full version of the 2D flavor as well as a 2.5D evaluation version. Two very fast new methods have been added to the 2.5D version: One computes iso-contours, the other computes the height of a point with arbitrary (x,y) coordinates. Delaunay mesh generation has been improved. Support for VS2008, 32-bit and 64-bit, has been added. The performance has been improved.

Version 1.11, June 14th, 2013:
Non-public intermediate release with VS2008 support and a first version of the iso-contour feature.

Version 1.10, March 30th, 2013:
Delaunay Refinement (already included as preview in the previous release) has been improved and is officially released now. Parts of the algorithm can use up to 8 CPUs under Linux if explicitly switched on using Fade2D::enableMultithreading(). There is a new insert method in the API which uses arrays.

Version 1.03, Nov. 4th, 2012:
A critical bug has been fixed, please switch to the current version. Performance upgrade: A first step towards multithreading has been made in the Linux version. In order to facilitate the installation for users without administrator privileges the installers have been replaced by a simple zipped directory that contains everything. Meshing through Delaunay Refinement is scheduled for the next release but it is pre-released as an experimental feature in the current version 1.03.

Version 1.02, 9/2012:
An additional debug library version for Windows has been added and the directory structure has been reorganized.

Version 1.01, 9/2012:
This is a stable public release. Since version 0.9 we have introduced insertion of constraint edges and the zone concept. Moreover the API is under a namespace now. Boost types have been removed from the API to avoid this additional dependency. New demo software has been written and the library is now also available for 64-bit Windows.