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

C++ Constrained Delaunay Triangulation Fade2D

Delaunay triangulation library for Windows
Delaunay triangulation library for MacOS
Delaunay triangulation Library for Raspberry PI
Delaunay triangulation library for Linux

Support for Windows (Visual Studio 2008-2017), MacOS, Linux on PC and Raspberry PI

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

Delaunay triangulation: Getting started

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

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.56
Fade 2.5D HTML PDF

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.
  • lib_${DISTRO}_${ARCHITECTURE}
    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

For Windows users:

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

For Linux and Apple users:

  1. Make sure GMP is installed:
    $ sudo apt-get install libgmp10 (works on Ubuntu/Debian/Mint/Raspbian, on other systems search for libgmp or gmp)
  2. Enter an example directory, choose (!) your OS or Linux distribution in the Makefile and type make to compile the source code.

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

Troubleshooting

  • Mixing multiple Visual Studio versions is not recommended.
  • Compare your settings with the ones from the example projects.
  • In Visual Studio increase Properties->ConfigurationProperties->Linker->System->StackReserveSize
  • Make sure that the right *.dll is used in your project.

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.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

fade[2D|25D]_$(Platform)_$(PlatformToolset)_$(Configuration).dll

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.