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

• 2D Delaunay with Polygon support and Constraint Edges
• 2.5D Delaunay for Surfaces and Digital Elevation Models
• Grid Mesher, Delaunay Mesh Generator
• Polygon Clipping, Boolean Operations on Polygons
• Cut and Fill for Earthwork Volume Computations
• Free student license. Eval- and Commercial licenses with 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 while closed objects such as e.g., a ball do not have such surfaces. Applications for Fade2.5D are surface metrology and terrain triangulation from LiDAR data. The Fade 2.5D extension comes with a buch of additional algorithms:

• Fast computation of ISO lines
• Height queries for arbitrary (x,y)-coordinates
• EfficientModel-class to reduce a point cloud within a user specified tolerance
• SegmentChecker to compute segment intersections. Works even in the practical case where two line segments intersect in (x,y) but at different heights (both heights are reported then)
• 2.5 Mesh optimization: Fade2.5D does not only lift a 2D triangulation but can optimize a triangulation for the local slope

Terrain triangulation 2.5D, 550 000 triangles computed in 0.31 seconds (Core i7 870).

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
Only points are triangulated, the empty circumcircle condition holds for each triangle

Constrained Delaunay triangulation
Constraint segments are inserted in order to enforce certain edges in the triangulation. Triangles can lose the empty circle property.

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

Zones define areas of interest. Their triangles can be conveniently extracted. Zones support POLYGON CLIPPING, or more general, they support the boolean set operations union, intersection, difference and symmetric difference). The area of a Zone can be meshed with the Delaunay Mesher and Grid Mesher.

## 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.

Constrained Delaunay triangulation: Small angles and high aspect ratios

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

Fade2D is multithreaded and very fast. One million points take 0.16 seconds on a Corei7 6800K. Have a look at this comparison of single- and multithreaded runs with large point-sets.

## Feature Requests, Questions? Post here:

1. yangxi

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

2. A Delaunay triangulation is always convex. You must insert the segments of your concave polygon, define a zone and retrieve the triangles of the non-convex area, see example 4.

3. 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 ?

• 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.

4. Peng Zhen

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

5. 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!

• Hi!

Fade is close to the Bowyer–Watson algorithm. Thanks for the feedback.

6. 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.

• 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

7. Cui Lejing

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

• 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.

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

8. 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!

9. Bay

How can i deal with self-intersection polygon?

• Insert the polygon segments as constraints. They will automatically be subdivided at their intersection points.

10. 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.
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.

11. Shunji Kikuchi

Hello I’m Shunji Kikuchi in Japan.

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));
segA, CIS_CONSTRAINED_DELAUNAY);
segA.clear();
}
/* or
segA, CIS_CONSTRAINED_DELAUNAY);
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:

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

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).

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