Geom Softwareentwicklung
Bernhard Kornberger
Fade2D - An easy to use Delaunay Triangulation Library for C++
Author
Bernhard Kornberger, bkorn.nosp@m.@geo.nosp@m.m.at, Geom e.U. Software Development, http://www.geom.at

Introduction to Fade2D

  • Fade2D is among the fastest Delaunay triangulation libraries
  • Free for scientific research. Commercial licenses and support are available
  • Numerically robust
  • Conforming and Constrained Delaunay triangulation
  • Delaunay mesh generator
  • Zones (polygonal areas, possibly containing holes)
  • 2D and 2.5D triangulations


The two flavors of Fade2D

Fade2D consists of two separate libraries, one for 2D and one for 2.5D triangulations.

Delaunay triangulation with dual Voronoi diagram Terrain triangulation, height map

One can think of a 2.5D Delaunay triangulation as a 2D Delaunay triangulation where each vertex (x,y) has a certain height z. 2.5D Delaunay allows only one height value per (x,y) coordinate pair and that distinguishes it from a 3D Tetrahedralization. Fade 2.5D is used for height fields. Applications are surface metrology and terrain triangulation. Fade 2.5D supports computation of ISO-contours and it answers height queries for arbitrary (x,y)-coordinates in an extraordinary fast manner.

terrain_triangulation_2.5d_delaunay_triangles.gif
2.5D Delaunay triangulation, 550 000 triangles computed in 0.31 seconds

terrain_triangulation_2.5d_iso_contours.gif
Iso-contours of 550 000 triangles at 30 different levels computed in 0.38 seconds


The time consumption above has been measured with a desktop computer (Core i7 870, 3 GHz)

Zones in a triangulation

Zones are certain areas in a triangulation. A zone can be defined through a closed, simple polygon. Zones can be automatically refined and their triangles can be extracted. Zones can also be combined through set operations.

constrained-delaunay-zones-transparent.gif
Constrained Delaunay triangulation with zones: The red triangles belong to a single zone.

Delaunay mesh generator

High quality triangular meshes (with a certain minimum angle) can be generated in 2D and 2.5D.

remesh.gif
Delaunay Meshing: A Constrained Delaunay triangulation and a quality Delaunay mesh

Performance of Fade2D

Fade2D is numerically robust and very fast. It triangulates one million points in less than 0.7 seconds. The diagram below shows that the practical run-time grows only linearly with the number of input points (uniformly distributed in a rectangular area for this benchmark).

performance.png
Performance of Fade2D on a Core i7 870 CPU, 3 GHz



Licenses:

Free license

Fade2D is free of charge for personal non-commercial scientific research. You can download and use it without registration. But we ask you to put a link to Fade2D on your web site and to cite Fade2D in scientific publications using it.

Commercial license

All other applications (including commercial in-house usage) require a commercial license which guarantees maintenance, error corrections and personal support.

In no case can we be made responsible for damages of any kind that arise in connection with the use or non-usability of our software or the information provided on our internet pages. If you don't accept these terms, you are not allowed to use our software. The 2D download is a full version. The 2.5D download is limited to 50,000 points. Using Fade2D for military research and applications is not accepted.


Getting started

Download

Download Fade2D_v1.19.zip, unzip and start to play with the included examples. It works without installation for Windows and Linux developers.

For Windows users:

  1. Open one of the example projects (Visual Studio solution files in the vs2008, vs2010, vs2012 or vs2013 folder)
  2. Compile the demo source code. Find the *.exe in the Win32 or x64 folder.

For Linux users:

  1. You need GMP:
    $ sudo apt-get install libgmp3c2 // ...works for Debian and derivates like Ubuntu, Linux Mint, ...
  2. Enter the example[0-7] directory and type make to compile the source code.

Learn fast, work through the provided examples. They are small and well documented and they draw the computed triangles and polygons. Modify the source code and see what happens to get familiar with the library.


Troubleshooting

Does your program crash? Mixing multiple Visual Studio versions is not recommended. Make sure that the right *.dll is used in your project. Compare your settings with the ones from the example projects in the VS2008, VS2010, VS2012 or VS2013 folder. If the problem persists, don't hesitate to send a minimal example that reproduces the problem.


Documentation:

The 2D online / pdf documentation and the 2.5D *.pdf documentation describe the two flavors of Fade2D. The classes have identical names but different namespaces: GEOM_FADE2D or GEOM_FADE25D. For many interfaces the difference between the two libraries is just the z-coordinate, thus there is a consistent look and feel which allows to switch between the two versions quickly.

Directories

  • include_fade2d and include_fade25d
    Header files of the two libraries.
  • Win32 and x64
    This directory contains the *.dll and *.lib files for Windows 32-bit (64-bit) and it will contain the executables when you compile the example source code with Visual Studio.
  • linux_i686 and linux_x86_64
    The 32-bit (64-bit) shared library (*.so) for Linux developers.
  • example[0-7]
    Source code of the examples.
  • vs20xx_exampleProjects
    Contains the example *.sln files for Visual Studio 2008, 2010, 2012 and 2013.
  • doc
    Documentation

Release notes

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

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

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

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

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

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

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

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

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

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

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

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