Jump to content
  • Advertisement
Sign in to follow this  
joseMalo

Voronoi/Delaunai in 3D Questions,...

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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
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
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!