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!
Conditions for the applicability of Delaunay tetrahedralization
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]
"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]
Author
Thanks for your extensive answer.
One more question:
Is it absolutely necessary to construct a delaunay triangulation before a tetrahedralization?
One more question:
Is it absolutely necessary to construct a delaunay triangulation before a tetrahedralization?
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?
Constrained Delauny methods in 3D will also triangulate the forced boundary which is 2D, is this what you mean?
Author
Basically.
My main problem is to find out if you can compute a delaunay tetrahedalization from every point set without loss.
My main problem is to find out if you can compute a delaunay tetrahedalization from every point set without loss.
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.
Author
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.
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.
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.
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
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
Author
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?
Which one?
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
