Voronoi/Delaunai in 3D Questions,...
Author
Hi all,
Some theory questions on computational geometry:
How one could define a Voronoi Diagram in 3D?
How to derive a Delaunay triangulation(thetraedra) in 3D from
a Voronoi diagram in 3D???
Do you know where to find some algorithm for constructing a Voronoi Diagram in 3d from a Delaunai triangulation in 3D?
Thanks in advance!!,.. if you don't have the answer,.. any advice of where to find them?
/JoseMalo
Given a set of points S={P_1,P_2,...P_n} we can define the Voronoi region of P_i as the set of points that are closer to P_i than to any other point in S. This definition can be used in any number of dimensions.
If you draw a segment between P_i and P_j when their Voronoi regions touch each other, you get the sides of a decomposition of the convex hull of S into tetrahedrons. Those are the 3-D equivalent of the Delaunay triangulation.
Really the situation is very similar to 2-D. It will be true that the sphere that contains four vertices of one of the tetrahedrons will not contain any other points in S. It will be true that you can obtain the Delaunay graph by projecting the set onto a 4-D paraboloid, computing the convex hull and projecting back to 3-D.
If you draw a segment between P_i and P_j when their Voronoi regions touch each other, you get the sides of a decomposition of the convex hull of S into tetrahedrons. Those are the 3-D equivalent of the Delaunay triangulation.
Really the situation is very similar to 2-D. It will be true that the sphere that contains four vertices of one of the tetrahedrons will not contain any other points in S. It will be true that you can obtain the Delaunay graph by projecting the set onto a 4-D paraboloid, computing the convex hull and projecting back to 3-D.
Author
Thanks Alvaro!!!
Any advice regarding short source for related algorihms?
Regards,
/JoseMalo
Any advice regarding short source for related algorihms?
Regards,
/JoseMalo
joseMalo,
In my opinion, Jonathan Richard Shewchuk of Carnegie Mellon University provides some of the definitive work in 3D tetrahedralization, including 3D Delaunay and Voronoi diagrams. You can find his myriad of papers and references here:
Jonathan Richard Shewchuk's Home Page @ CMU
As for for a definition of a 3D Voronoi Diagram, as in 2D it is the dual of the Delaunay Tetrahedralization.
In my opinion, Jonathan Richard Shewchuk of Carnegie Mellon University provides some of the definitive work in 3D tetrahedralization, including 3D Delaunay and Voronoi diagrams. You can find his myriad of papers and references here:
Jonathan Richard Shewchuk's Home Page @ CMU
As for for a definition of a 3D Voronoi Diagram, as in 2D it is the dual of the Delaunay Tetrahedralization.
Author
Thanks for your reply Graham.
Actually I already read his paper on "Triangle: Engineering a
2D Quality Mesh Generator and Delaunay Triangulator",... but
I was looking for something simpler and particularly short
available code.
Exactly what I look for is to find some short source code for improving mesh quality of objects defined with VRML.
Thanks for your reply!!
Regards,
/JoseMalo
Actually I already read his paper on "Triangle: Engineering a
2D Quality Mesh Generator and Delaunay Triangulator",... but
I was looking for something simpler and particularly short
available code.
Exactly what I look for is to find some short source code for improving mesh quality of objects defined with VRML.
Thanks for your reply!!
Regards,
/JoseMalo
I've been looking for some nice code to do a 2d Delaunay triangulation for a few months now, but it still seems to be in the realms of research & dev.
Do you really REALLY want delauney triangulation?
Or do you just want to triangulate a surface round some voxels or something?
http://gts.sourceforge.net
Or do you just want to triangulate a surface round some voxels or something?
http://gts.sourceforge.net
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
