Fade2D Delaunay Triangulation

Fade 2D

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

  • 2D Delaunay with Constraint Edges and Zone-Concept
  • Multithreaded, high Performance Algorithm
  • Grid Mesher, Delaunay Mesh Generator
  • Polygon Clipping, Boolean Operations on Polygons
  • Fast Segment Intersection Tester
  • Free academic use. Eval- and Commercial licenses with Support are available
.

Fade 2.5D

Fade 2.5D is a Delaunay triangulation library that computes elevated TINs from 2.5D point clouds. 2.5D allows exactly one height (z) value per (x,y)-coordinate pair and this distinguishes it from 3D: It’s there for surfaces which have an intersection free projection to the (x,y)-plane like a terrain. Fade 2.5D provides all features of Fade2D plus a z-coordinate and additional algorithms for height fields.

  • 2.5D TINs for elevated Surfaces
  • Breakline Insertion at Segment- or Surface-Level
  • Fast ISO-Contours
  • Cut and Fill for Earthwork Volume Computations
  • Height queries for arbitrary (x,y)-Coordinates
  • EfficientModel to reduce a Point Cloud within a specified Tolerance
Terrain triangulation (TIN) with Fade2.5D

Terrain triangulation (2.5D TIN), 550 000 triangles computed in 0.11 seconds.

ISO contours in a 2.5D TIN

Terrain triangulation (2.5D TIN), ISO contours of 550 000 triangles at 30 different levels computed in 0.22 seconds.

Constrained and Conforming Delaunay

You can insert Constraint edges. This holds also for 2.5D where the term ‘Breakline’ is more common.

Delaunay triangulation with Fade2D

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

Constrained Delaunay triangulation, constraint edges can be enforced

Constrained Delaunay triangulation with Constraint edges

 

Conforming Delaunay triangulation, constraint edges that can be subdivided

Conforming Delaunay triangulation
Subdivision for Constraint Segments to achieve better triangle quality.

Zones in a triangulation support polygon clipping. Their areas can be retriangulated with the Delaunay Mesh Generator or Grid Mesher

Zones define areas of interest. They support POLYGON CLIPPING, or more general, they support the boolean set operations union, intersection, difference and symmetric difference. You can use a Zone for convenient triangle extraction or you can remesh a Zone using the Delaunay Mesh Generator and Grid Mesher.

 

Delaunay Mesh Generator and Grid Mesher

The Mesh Generator creates high quality triangles inside a given area. Thereby the user can either claim just a simple quality feature like the minimum interior triangle angle. Or he can precisely control the mesh generation procedure. Possible parameters are the maximum edge length, a grow factor on neighbored triangles and grid alignment.

Zone to be refined

Constrained Delaunay triangulation: Small angles and high aspect ratios

Delaunay mesh generator

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

 

Performance of Fade2D

Fade2D is multithreaded and very fast. Triangulating one million points (2 million triangles) takes 0.17 seconds on a Corei7 6800K. Have a look at this comparison of single- and multithreaded runs with large point-sets.

Delaunay Triangulation Performance Comparison Fade2D

Performance of Fade2D

25 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:

      [file removed, you can use the current version instead]

      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!

  8. Reply Shunji Kikuchi

    Hello, my name is Shunji Kikuchi in Japan.
    (1) std::vector
    I have much interest in Constrained Delaunay Triangle methods.
    So I execute example3, but crashed.
    I find the following methods have some problem.
    – dt.insert(vInputPoints)
    – ConstraintGraph2* pCG=dt.createConstraint(vSegments,CIS_CONSTRAINED_DELAUNAY);
    I avoid this problem by using for loop without using std::vector.

    (2) Question
    By avoid the above problem, I make a my sample program.
    Fade seems to add additional points in CDT. Is it correct ?
    I want to make CDT diagram of just given xy-points.
    Are there any option/parameter to specify this.

    Thank you.

    • Reply Bernhard Kornberger

      Hello Shunji Kikuchi,

      (1)
      Example3 is simple and well tested. I doubt that it crashes due to a bug but rather due to some incompatible linking or something like that. Please contact me via email to send details:
      * Have you modified the source code of Example3?
      * Which compiler do you use?
      * Against which binary to you link?
      I will support you also if you have no license, it is very important that the library is stable in all supported environments.

      (2)
      When you use CIS_CONSTRAINED_DELAUNAY then no additional points are inserted *unless* the constraint segments cross each other. In this case they are subdivided at their intersection point. It is always a good idea to visualize the result to see what’s going on. Use Fade_2D::show(“out.ps”) to write a Postscript file.

  9. Reply Shunji Kikuchi

    Hello I’m Shunji Kikuchi in Japan.

    (1)Fade2 add additional xy-points
    Yesterday, I sent this problem to you.
    Maybe, this problem happens by my usage of “applyConstraintsAndZones”.
    As I reported, “createConstraint(segA, CIS_CONSTRAINED_DELAUNAY)”
    is crushed for multi-segments.
    In order to avoid this problem, I make the following codes.

    std::vector segA; segA.clear();
    for (int i0 = 0; i0 getCoords(pntA);
    for (int k0 = 1; k0 < (int)pntA.size(); k0++) {
    Point2 v1 = Point2(pntA[k0-1].x(), pntA[k0-1].y());
    Point2 v2 = Point2(pntA[k0].x(), pntA[k0].y());
    segA.push_back(Segment2(v1, v2));
    ConstraintGraph2* pCG = m_fade2D.createConstraint(
    segA, CIS_CONSTRAINED_DELAUNAY);
    m_fade2D.applyConstraintsAndZones();
    segA.clear();
    }
    /* or
    ConstraintGraph2* pCG = m_fade2D.createConstraint(
    segA, CIS_CONSTRAINED_DELAUNAY);
    m_fade2D.applyConstraintsAndZones();
    segA.clear();
    */
    }

    But these ways does not work well.

    Thank you.

    • Reply Bernhard Kornberger

      Dear Shunji Kikuchi,

      thank you for your email. I have tried to compile and run
      example3 with Visual Studio 2017. These were my steps:

      1. Download Fade v1.63 and unzip
      2. Change to fadeRelease\examples_2D\vs2017_exampleProject
      3. Open examples_2D.sln with Visual Studio 2017
      4. Select x64 Release and build
      5. Open a command line window, go to fadeRelease\x64
      6. Launch examples_2D.exe and select ‘3’

      That works exactly as it should. And it should also work on
      your side if you use the original VS2017 project that is
      provided with the download.

      I guess that your project settings are wrong and that you have
      a version mismatch i.e., you link with a library that has been
      made for another compiler version. My questions:

      1. Does at least the above (original project) work for you?

      2. What setting does your VS2017 project use in Configuration
      Properties -> General -> Platform Toolset ? It should be
      Visual Studio 2017 (v141).

      3. What string do you use in Linker -> Additional Dependencies?

      If that does not solve the problem, please provide a minimal
      test project that reproduces the behavior: One *.cpp file with
      a Visual Studio project so that I can compile it exactly like
      you do. Thank you.

      Best regards
      Bernhard Kornberger
      Geom Software

  10. Reply Salman

    Hello,
    I would like to use Fade2D on Debian Stretch for purely academic purposes. However, the supplied versions are not working. Could you compile it on Debian stretch?

    Thank you

    • Reply Bernhard Kornberger

      Hi, have you tried the code in the examples2D/ directory and did you edit the Makefile to find out if one of the provided versions is compatible?

      #DISTRO :=../lib_centos6.4_${ARCHITECTURE}
      #DISTRO :=../lib_ubuntu14.04_${ARCHITECTURE}
      #DISTRO :=../lib_ubuntu16.04_${ARCHITECTURE}
      #DISTRO :=../lib_ubuntu17.04_${ARCHITECTURE}
      DISTRO :=../lib_ubuntu18.04_${ARCHITECTURE}
      #DISTRO :=../lib_APPLE
      #DISTRO :=../lib_raspberry_armv6l
      #DISTRO :=../lib_raspberry_armv7l

  11. Reply Nhan

    Hello,
    I use Fade2D with Visual Studio 2017 on Windows 10 system. I linked the fade2D_Win32_v141_Debug.lib in my project (MFC project). I don’t call any API from the Fade2D module, just link the lib and launch my MFC project.
    I got a lot of memory leaks in the output (about 700 lines). Here are some of these lines:
    {2123} normal block at 0x00CA18D8, 8 bytes long.
    Data: 40 FE C8 00 00 00 00 00
    {2122} normal block at 0x00C996B8, 24 bytes long.
    Data: 20 8F C9 00 90 8E C9 00 F0 9A C9 00 01 01 CD CD
    {2121} normal block at 0x00C8FE38, 68 bytes long.
    Data: > 3E 00 00 00 E7 03 00 00 D8 18 CA 00 B8 96 C9 00
    {2120} normal block at 0x00CA25F0, 1 bytes long.
    Data: CD
    {2095} normal block at 0x00C9DE30, 32 bytes long.
    Data: 46 61 64 65 20 32 44 2C 20 44 45 42 55 47 2C 20
    {2094} normal block at 0x00CA0E58, 8 bytes long.
    Data: D0 17 42 0F 00 00 00 00
    {2091} normal block at 0x00CA0FA8, 8 bytes long.

    Any idea?
    Thank you

    • Reply Bernhard Kornberger

      Hi!

      Thank you for this report. Very recently I have got the first report about this warning but I was not able to reproduce the warnings on my machine. I have also tested the library with Valgrind and it reports

      ==31458==
      ==31458== HEAP SUMMARY:
      ==31458== in use at exit: 0 bytes in 0 blocks
      ==31458== total heap usage: 239 allocs, 239 frees, 104,002 bytes allocated
      ==31458==
      ==31458== All heap blocks were freed -- no leaks are possible
      ==31458==
      ==31458== For counts of detected and suppressed errors, rerun with: -v
      ==31458== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

      It would be very helpful if you could send me a minimal VS2017 project that I can compile on my machine to debug this issue. Thank you!

      Best regards
      Bernhard

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