Is there a python script/plugin that can do 2-D and 3-D Delaunay triangulation from vertices? Right now I’m particularly interested in the 2D version. From my searching, it looks like I’d have to export my mesh data, import it into either Triangle or Qhull, then import back into Blender.

# Delaunay triangulation script?

**scorpius**(scorpius) #2

There’s a script (at the wiki site) that computes the convex hull in 2D and 3D. So if you have a bunch of random points on the surface of a sphere, the script will create the faces of the mesh. But I don’t think it will form a mesh around any given point cloud – this is much more complex.

**GrayTrace**(GrayTrace) #3

Hi Alitorious,

some time ago I wrote a short script which uses the external free triangulation software ‘Triangulate’, which can do delaunay triangulation perfectly.

The script can handle 2D curves created on the x/y plane. Even holes are possible.

I tried with Blender 2.44 and Python 2.5 installed. It still works (I was surprised to be honest!).

Please have a look at my tutorial first: http://home.arcor.de/kamebaukun/Data/TriangleMeshFillDoc.pdf

It will guide you through the process how to succeed.

You first have to download the triangle program together with the ‘cygwin1.dll’, which you can get from my site as a windows precompiled version (see thread http://blenderartists.org/forum/showthread.php?t=65240)

Hope this still could be useful!

**Alitorious**(Alitorious) #4

Thanks for the help.

Actually, the Delaunay triangulation I was thinking of was to compute a mesh from a cloud (2D or 3D) of vertices. I was able to do this by exporting to .off format and using this in qhull. (http://www.qhull.org/)

Your script, though, I can see is very useful. Thanks for the link!

**Kai_Kostack**(Kai Kostack) #5

the C source code is available on this site, maybe someone will try to integrate it into blender. seems like a useful tool to me.

**ideasman42**(ideasman42) #6

try this - its just my own crappy algo but works ok

http://members.optusnet.com.au/cjbarton/tri_terrain.blend