Delaunay Triangulation Libraries for 2D and 2.5D

Fade is a high-performance C++ Delaunay triangulation library available in two versions: Firstly, Fade2D constructs planar Delaunay triangulations with constraints, as the 2D cyclist-shape above. Secondly, Fade2.5D generates elevated Delaunay triangulations from 2.5D point clouds, such as the terrain example shown above. Both software versions come equipped with robust algorithms from the meshing field. Furthermore, we provide ready-made C++ examples that demonstrate the practical application of these algorithms:

Fade 2D: Constrained Delaunay Triangulation

  • Delaunay triangulation for 2D points, multithreaded
  • Constrained Delaunay triangulation for segments and polygons
  • Polygon clipping, boolean operations on polygons
  • Voronoi diagram with fast nearest-neighbor search
  • Fast segment intersection tester
  • Delaunay Mesh Generator and Grid Mesher
  • Free student/research license included. Commercial licenses with dedicated programming support are available

Fade 2.5D: Delaunay Triangulation for Elevated Point Clouds

The Fade 2.5D software contains all features of Fade2D. Additionally, points have a z-coordinate, and the software offers advanced algorithms for elevated point clouds:

  • Reduce a 2.5D point cloud with Fade’s CloudPrepare tool
  • Create a lifted Delaunay triangulation (a TIN) from it
  • Align its edges to valleys and ridges
  • Eliminate noise with weighted Laplacian smoothing
  • Utilize the Cookie Cutter tool to cut out polygonal pieces.
  • Perform Cut-and-Fill for earthwork volume computations.
  • Make height queries for arbitrary (x,y) coordinates.
  • Compute ISO-contours from the terrain.

“To clarify, the 2.5D dimension allows exactly one z-value per (x,y)-coordinate pair. Therefore, it is well-suited for surfaces that can be projected without intersections onto the (x,y)-plane, such as terrains.”

Delaunay Terrain triangulation (2.5D TIN), 550 000 triangles
Terrain (2.5D TIN), 550,000 triangles computed in 0.11 seconds
ISO contours of a terrain consisting of  550 000 triangles.
Terrain triangulation 2.5D, ISO contours of 550,000 triangles at 30 different levels computed in 0.38 seconds.

Constrained Delaunay Triangulation

With Fade, you can effortlessly insert constraint edges into a Delaunay triangulation, transforming it into a Constrained Delaunay triangulation. Additionally, these constraint edges can be subdivided into sub-segments, ensuring the creation of well-shaped adjacent triangles.

C++ Delaunay triangulation of points without constraint edges
Delaunay triangulation of points without constraint edges
C++ Constrained Delaunay triangulation library
Constrained Delaunay triangulation with constraint edges
Conforming Delaunay triangulation -  subdivision for constraint segments to achieve better triangle quality.
Subdivided constraint edges for better triangle quality using the makeDelaunay() method
Zones (Shapes)
Zones define areas of interest. They support Polygon Clipping, or more general, they support the boolean set operations union, intersection, difference and symmetric difference.

Fade 2.5D can insert breaklines at their original elevation or it can adapt them to surface-level before insertion. It can subdivide the segments automatically to better fit the surface.

Breaklines (constraint edges)
Polygonal breaklines (blue polygon), projected (red polygon) and inserted into a 2.5D triangulation. The left image shows the original long segments. In contrast the right image shows automatically subdivided segments.

Delaunay Mesh Generator and Grid Mesher

The Mesh Generator module produces high-quality triangles within a specified shape. These triangles can conform to a grid mesh pattern, ensuring that all points align precisely with the grid. Alternatively, you have the flexibility to set quality criteria, such as minimum interior triangle angle, maximum edge length, or constraints on size differences between neighboring triangles. This flexibility allows you to tailor the mesh generation to your specific needs, whether you prefer grid-based meshes or triangles meeting other quality criteria.

Quality meshing inside a polygon.
A Delaunay Meshing function creates a high quality triangle mesh

Performance of Fade

The C++ library can utilize multiple threads on different cores, delivering exceptional speed: For example, it can triangulate one million points (resulting in two million triangles) in just 0.17 seconds on a Core i7 6800K processor. You can explore a detailed performance comparison between single-threaded and multithreaded runs with large point sets.

Delaunay Benchmark single- and multithreaded
Delaunay benchmark: 1 million points (2 million triangles) in 0.17 s multithreaded or in 0.42 s single-threaded

38 replies on “Delaunay Triangulation Libraries for 2D and 2.5D”

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

“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 ?

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.

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!

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.

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

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.

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!

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.

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.

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.

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

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

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

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

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

I use fade2d in ue4,when I use dt->getTrianglePointers() or pZone0->getTriangles() in beginplay ,the beginplay method will raised error when closed method.error is about free memory.

can you tell me how to loop all Triangle don’t use dt->getTrianglePointers() or pZone0->getTriangles()

Hello!

Both methods work perfectly, they have been tested countless times in industrial environments. Please make sure that the Fade_2D instance is still alive at the time you use the triangles. Because with the destructor of the Fade_2D class the memory of all vertices and triangles is also released.

If this hint does not solve your problem, please send me a *minimal* example that I can compile and test.

test project on https://github.com/gysgogo/ue4_fade2d_test

please use win64,click play button multi time(not every time error happen)

Fade_2D dt;
Point2 p0(0.0, 0.0);
Point2 p1(1.0, 0.0);
Point2 p2(0.5, 2.0);
Point2 p3(0.5, 0.5);

// Insert the points
dt.insert(p0);
dt.insert(p1);
dt.insert(p2);
dt.insert(p3);
std::vector vTriangles;
dt.getTrianglePointers(vTriangles);

I use above code in ue4 beginplay method,when I clicked play button dt.getTrianglePointers(vTriangles) crash my app some times (not every time) .the beginplay method raised error when closed method.error is about free memory.
I have post minimal ue4 project on github that only have one actor Source\ue4_fade2d_test\TestActor.cpp and beginplay is above simple code.
https://github.com/gysgogo/ue4_fade2d_test Project please use win64 ,click play button multi time ,the error will happen(not every time)

By the way: I had just a case where a user has used
header files from one Fade version and binaries from
another Fade version. This can cause trouble due to
different memory footprints of classes in the headers
and in the binaries. When this is also the case in
your project please remove all Fade binaries from
your development folder and download a fresh copy
of Fade.

Hi!

Your code looks correct. But the related functions of Fade are basic functions that are certainly correct.I don’t know UE4, but since the error doesn’t occur every time, I assume a memory problem that was caused elsewhere, but is only having an effect here. Another possibility is that you have mixed different VisualStudio versions, that also rarely goes well. The below error message is also not really related to Fade2D but to something inside UE4.

UE4Editor-Core.dll!rml::internal::freeSmallObject(void * object) Line 2522 C++
[Inline Frame] UE4Editor-Core.dll!rml::internal::internalPoolFree(rml::internal::MemoryPool * memPool, void *) Line 2621 C++
[Inline Frame] UE4Editor-Core.dll!rml::internal::internalFree(void *) Line 2644 C++
UE4Editor-Core.dll!scalable_free(void * object) Line 2933 C++
UE4Editor-Core.dll!FMemory::Free(void * Original) Line 80 C++

is not related to Fade2D.

Hi !
I’ve tried to test your library and it generates errors frequently at createZone_cookieCutter with message “Dt2_cat_cutt.cpp Line 944” Expression:vChildConstraintSegments.size() == 2)
Can you solve it ?

Hello
I did all the linking process for iOS build to my Xcode ( Version 15.2 (15C500b)). I also linked gmp library.

Process is failing at this point:
dt.printLicense();
dt.insert(vInputPoints); <——— failure point

debugger Error is :
Thread 1: EXC_BAD_ACCESS (code=1, address=0xfffffffffffffffc)

this was shown in my console :
Fade2.5D license:
—————–
* Fade: getStoredVal(4) while uninitialized
* Fade: getStoredVal(6) while uninitialized
Licensetype: Unknown
* Fade: getStoredVal(3) while uninitialized
Limit 2.5D: 16 points
* Fade: getStoredVal(8) while uninitialized
Limit CutFill: 16 triangles
* Fade: getStoredVal(11) while uninitialized
Limit Voronoi: 16 Voronoi cells
* Fade: getStoredVal(5) while uninitialized
Limit SegmentChecker: 16 segments
Limit Mesh Generation: 16 output triangles

Fade 2.5D, RELEASE, v2.10.0

* Fade: getStoredVal(3) while uninitialized

Hello!

Thank you for your report. The issue is due to an uninitialized license object, which is unexpected as it has not occurred before. Are you running one of the provided examples or have you created your own project? Please try manually including the License.h file or launching the setLic() command contained in the License.h file. Let me know if this resolves the problem. I’m here to assist you, and furthermore, a new version will be released very soon, so I appreciate knowing about any issues in order to address them now.

Hello. I did call the mentioned function and it is working now.
thanks. I tried to replicate the example code in my project. I did not know that I have to call this function. I thought calling printLicense is enough.

Hi! Thank you for your feedback. You do not need to print the license. You should also not need to call the setLic() command manually because, if you include the Fade_2D.h header, the License.h will automatically be included, except when the macro FADE2D_EXPORT is defined. So the only plausible explanations are that you didn’t include Fade_2D.h or FADE2D_EXPORT was defined by accident.

Leave a Reply

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