Fade2D Delaunay Triangulation

Fade2D is an easy to use Delaunay triangulation library for C++:

  • Fade2D is among the fastest Delaunay triangulation libraries
  • 2D Delaunay with Polygon support and Constraint Edges
  • 2.5D Delaunay for Surfaces and Digital Elevation Models
  • Grid Mesher, Delaunay Mesh Generator
  • Boolean Operations on Polygons
  • Cut and Fill module
  • Free for scientific research. Commercial licenses and 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. Closed objects such as, for example, a ball do not have such surfaces. Applications for Fade2.5D are surface metrology and terrain triangulation from LiDAR data.

Drag mouse to rotate, use SHIFT to
zoom and CTRL to translate
.

Fade 2.5D supports fast computation of ISO-contours and answers height queries for arbitrary (x,y)-coordinates in an extraordinary fast manner.

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

Terrain triangulation 2.5D, ISO contours of 550 000 triangles at 30 different levels computed in 0.38 seconds (Core i7 870).

Constrained and Conforming Delaunay

Constraint edges can be inserted. This works also in 2.5D.

Delaunay triangulation

Delaunay triangulation
Only points are triangulated, the empty circumcircle condition holds for each triangle

Constrained Delaunay triangulation

Constrained Delaunay triangulation
Additional segments can be inserted. Triangles may lose the empty circle property.

 

Conforming Delaunay triangulation

Conforming Delaunay triangulation
Additional segments can be inserted but these are subdivided if necessary to keep the empty circle property.

Zones in a triangulation

Zones, defined areas in a triangulation
Zones define triangles of interest, they can be combined through set operations and their triangles can be conveniently extracted.

 

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.

Zone to be refined

Constrained Delaunay triangulation: Small angles and high aspect ratios

Delaunay mesh generator

Delaunay mesh: High quality triangles have been created in the same area

 

Performance of Fade

Fade is very fast. One million points take 0.6 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).

Triangulation Performance of Fade2D

Performance of Fade2D

Feature Requests, Questions? Post here:

15 Comments

  1. Reply yangxi

    Hello, I have a question. Can Fade2D make a concave triangulation? How to do? It seems always get a convex polygon.

  2. Reply Lars

    “run-time grows only linearly with the number of input points” means that you developed a new algorithm in the asymptotic runtime complexity class O(n). Have you published any paper about it or will it be kept secret ?

    • Reply Bernhard Kornberger

      Imagine some O(n) algorithm that computes a certain result within a day and imagine that the final output must be sorted which takes just a second. Is the overall algorithm still O(n) or is it O(n log n)? As a scientist you must write O(n log n) but nobody would say that such a software product has a superlinear time consumption.

      The same is true for Fade2D: The superlinear fraction is insignificant and we observe approximately 0.6, 6.0 and 60.5 seconds for 1, 10 and 100 million points. This justifies the statement “the practical runtime grows only linearly” while the correct big-O notation would be misleading. The algorithm has not been published, I focus on software now.

  3. Reply Peng Zhen

    Hello, in my research, I need to retrieve all the segment of the graph. How can I do that?

  4. Reply Wei

    Hi,

    Thanks for your free Delaunay triangulation library, it’s very fast in my research. But I didn’t see the detailed algorithm for Delaunay triangulation(DT), is that L-S? Watson? F-P? or other algorithms?
    Thank you!

  5. Reply Dang

    Hello. I used the pre-compiled Fade2D library for Ubuntu 15.04 in my project that is compiled under Ubuntu 16.04. I added the library into usr/local/lib and I did all necessary steps to the command ldconfig. But I got an error in compilation concerning the license :

    ../share/include/include_fade2d/License.h:39: undefined reference to `GEOM_FADE2D::setLic(std::__cxx11::basic_string<char, std::char_traits, std::allocator > const&, std::__cxx11::basic_string<char, std::char_traits, std::allocator > const&, std::__cxx11::basic_string<char, std::char_traits, std::allocator > const&, std::__cxx11::basic_string<char, std::char_traits, std::allocator > const&, std::__cxx11::basic_string<char, std::char_traits, std::allocator > const&)’

    Do you have any idea to overcome this problem ?
    Thank you.

    • Reply Bernhard Kornberger

      Hello Dang,

      Ubuntu 16.04 is too new for the Fade version you use. You can already download Fade v1.41 beta (it is stable but I always wait for some feedback before I label a version as a release version). Fade v1.41 beta contains Ubuntu15.10 binaries and they should work with Ubuntu 16.04. And just for the case that they do not, I have recompiled them again on a Ubuntu 16.04 machine for you:

      http://www.geom.at/_downloads/lib_ubuntu16.04_x86_64.tar.bz2

      It would be helpful if you could leave some feedback on this new version here.

      Best regards
      Bernhard

  6. Reply Cui Lejing

    Hello,can I get a .poly file or a .ele file from Fade2.5D ? And how to do it ?

    • Reply Bernhard Kornberger

      Dear Cui Lejing,

      The .poly-Format is currently not supported. For which program do you need it as input? If useful I can put that on my todo list. Currently you can use the *.obj file format and, if not directly supported by your software, look for an obj-to-poly converter tool.

      Fade_2D::writeObj()

      Another option is to write your own output function. Have a look at FaceList for that purpose.

  7. Reply Etienne Martin

    Hello Bernhard,
    would it be possible to get a 64 bit version compiled against the current Windows platform SDK 1.4.1 (compatible with Visual Studio 2017?). Many thanks!

Leave A Reply

Your email address will not be published. Required fields are marked *

*

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close