Sign in to follow this  
joseMalo

Voronoi/Delaunai in 3D Questions,...

Recommended Posts

joseMalo    122
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

Share this post


Link to post
Share on other sites
alvaro    21263
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.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
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.

Share this post


Link to post
Share on other sites
joseMalo    122
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

Share this post


Link to post
Share on other sites
Aph3x    288
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.

Share this post


Link to post
Share on other sites
Squirm    481
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

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