# Voronoi/Delaunai in 3D Questions,...

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

## 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 on other sites
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 on other sites
Thanks Alvaro!!!

Any advice regarding short source for related algorihms?

Regards,

/JoseMalo

##### 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 on other sites

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.

Regards,

/JoseMalo

##### 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 on other sites
i'm using http://www.qhull.org

##### 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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 15
• 14
• 46
• 22
• 27
• ### Forum Statistics

• Total Topics
634044
• Total Posts
3015215
×