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 and Fade2.5D

  • Fade2D is among the fastest Delaunay triangulation libraries
  • Available for Windows and Linux
  • Free for scientific research. Commercial licenses and support are available
  • Numerically robust
  • Constrained Delaunay triangulation
  • Delaunay meshing
  • Zones - polygonal areas, possibly containing holes - can be defined
  • 2D and 2.5D triangulations


2.5D Constrained Delaunay triangulations

One can think of a 2.5D Delaunay triangulation as a 2D Delaunay triangulation where each vertex has a certain height. The difference to 3D Delaunay is that triangles are used and that each (x,y) coordinate pair has a unique z-coordinate in 2.5D. This makes 2.5D Delaunay triangulations ideal for terrain triangulation, mapping software and surface metrology. Extra features of the 2.5D version of Fade are extraordinary fast computation of iso-contours and heights of arbitrary (x,y) coordinate pairs.

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

Fade2D introduces the concept of Zones which enable extraction of certain areas of a triangulation. A zone can be defined through a closed, simple polygon. This works in 2D and 2.5D. Zones can be combined through set operations. The Delaunay meshing algorithm can refine a zone and the member triangles of zones can be retrieved.

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

Delaunay meshing

Fade2D can create a high quality triangular mesh inside an area defined by a Zone. When this feature is used in 2.5D then new vertices will automatically get height values.

remesh.gif
Remeshing: Left: A Constrained Delaunay triangulation; Right: 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. The non-commercial 2D version is a full version. 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. The commercial 2.5D version of Fade is unlimited.

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. Using Fade2D for military research and applications is not accepted.


Getting started

Download

Download Fade2D_v1.16.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 or vs2012 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.

For a steep learning curve you should work through the provided examples. The examples are small and well documented and they draw the computed triangulations. 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 you use the right *.dll in you project and compare your settings with the ones from the example projects in the VS2008, VS2010 or VS2012 folder. If the problem persists, don't hesitate to send a minimal example that reproduces the bug.


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 most 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 2008/2010.
  • 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.
  • vs2008_exampleProjects, vs2010_exampleProjects, vs2012_exampleProjects
    Contains the example *.sln files for Visual Studio 2008, 2010 and 2012.
  • doc
    Documentation

Release notes

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.