# Conditions for the applicability of Delaunay tetrahedralization

This topic is 2845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello folks,

can you tell me, which conditions have to be applied to:

- A point cloud to be able to be reconstructed using Delaunay triangulation / tetrahedralization
- A triangular mesh cloud to be able to be reconstructed using Delaunay triangulation / tetrahedralization

Surface continuity? Manifolds?

Thanks a lot!

##### Share on other sites
First, let me say that the absolute best papers for Delaunay meshing are
"Delaunay Refinement Algorithms for Triangular Mesh Generation" (2D), and
"Delaunay Refinement Mesh Generation" (2D and 3D)
http://www.cs.cmu.edu/~jrs/jrspapers.html

No-frills delaunay triangulization (in 3D, tetrahedralization) takes a set of points as input, and outputs a triangulation of the convex hull of those points. Furthermore, the triangles use exactly the input points and no more.

There are many possible ways to triangulate a set of points in this manner, some better than others depending on your goals. The Delaunay is a particular one which is "optimal" in 2D, in some sense (maximizes the minimum angle). In 3D (and higher) the Delaunay triangulation is still well-defined and can be computed, but it has some serious problems that make it less ideal (due to the existence of "sliver" tetrahedra).

If you want to "spice up" the Delaunay triangulation, there are a couple directions to go in
1) adding more points to make the triangles/tetrahedra better, called "Delaunay mesh refinement" and
2) triangulating inside a region constrained by a boundary, or with certain edges/faces "forced" to be in it.

Both are easy and good in 2D (look up "Constrained Delaunay"), but have serious issues in 3D. So far as I understand there are some good strategies but this is still an area of active research.

[Edited by - Maze Master on December 9, 2010 6:16:04 AM]

##### Share on other sites

One more question:

Is it absolutely necessary to construct a delaunay triangulation before a tetrahedralization?

##### Share on other sites
The triangulation applies only in 2D, whereas the tetrahedralization applies only in 3D, so I'm not sure I understand the question.

Constrained Delauny methods in 3D will also triangulate the forced boundary which is 2D, is this what you mean?

##### Share on other sites
Basically.

My main problem is to find out if you can compute a delaunay tetrahedalization from every point set without loss.

##### Share on other sites
Quote:
 Original post by DesperadoBasically.My main problem is to find out if you can compute a delaunay tetrahedalization from every point set without loss.

Without loss of what? I still don't understand what this thread is about.

##### Share on other sites
I have a 3d point set which samples the surface of some arbitrary shaped object.
I want to construct a delaunay tetrahedralization from that point set.
From the programs I've tried until now I assume that there are surfaces that are disadvantageous for this task, meaning that they cannot be reconstructed faithfully by delaunay tetrahedralization or you have to add/remove data. I know there are mesh examples that cannot be triangulated well (like Schoenhardts Polyhedron), but I need to know if there are similar examples for point sets.

##### Share on other sites
A set of points doesn't really describe a volume in a canonical way, so your question is not very well defined. The Delaunay tetrahedralization will cover the convex hull of your points, but that's probably not what you want, if the object whose surface you sampled was not convex.

##### Share on other sites
Hi,

if you have access to research paper have a look at the one from Peer Stelldinger:
http://kogs-www.informatik.uni-hamburg.de/~stelldin/publications.html

##### Share on other sites
There are some implementations who are able to create delaunay tetrahedralizations for point sets representing concave geometry (like http://tetgen.berlios.de/).

In fact, I mean Delaunay tetrahedralization. Some people refer to this as "3D Delaunay triangulation".

However, I still need examples for ill-conditioned point sets to create a tetrahedralization for.

As far as I understand, they include:

- point sets on a regular lattice (as circumspheres of most triangles are likely to include points which is against the delaunay criterion)
- points that cause elongated triangles because you have to insert additional points (Steiner) to make them more well shaped

Right?

Quote:
 Original post by dragongameHi,if you have access to research paper have a look at the one from Peer Stelldinger:http://kogs-www.informatik.uni-hamburg.de/~stelldin/publications.html

Which one?

1. 1
2. 2
3. 3
Rutin
18
4. 4
JoeJ
14
5. 5

• 14
• 10
• 23
• 9
• 48
• ### Forum Statistics

• Total Topics
632637
• Total Posts
3007577
• ### Who's Online (See full list)

There are no registered users currently online

×