Sign in to follow this  
Desperado

Conditions for the applicability of Delaunay tetrahedralization

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 this post


Link to post
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)
by Shewchuk, which are amazingly readable and can be found in pdf on this page:
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Desperado
Basically.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 dragongame
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


Which one?

Share this post


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

That's tetrahedralizing a region, not a point cloud. The input to the tetrahedralization is a closed surface representing the boundary of the object. With a point cloud you don't have that information.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this