Pure Python convex hull implementation

I created a simple pure Python implementation of Joseph O’Rourkes classic incremental convex hull algorithm (see http://maven.smith.edu/~orourke/books/compgeom.html )

The details (including the download) can be found on my blog: http://michelanders.blogspot.com/2012/02/3d-convex-hull-in-python-blender.html

Of course there is a convex hull algorithm hidden in Blender’s game engine but that one isn’t accessible from Python as far as I know, so I wrote this Python version. It is an add mesh addon so you have install the script in the addons directory and enable it in your user preferences. After that it will be available in the Add->Mesh menu. If you invoke this menu a new object will be added which will be a convex hull of your active object. This will only work for meshes.

It is of course debatable whether such a script should be in the add mesh menu or whether this should be an operator. I personally think that the best choice would be a modifier but that isn’t possible from Python. But that is not a relevant discussion.

5 mar 2012: I tweaked it and removed a couple of bugs. The weird shapes reported by Brenel are now fixed. I also added a quick and dirty fix for shapes that give rise to many degenerate triangles while triangulating. This happens for example when trying to compute the hull of Blenders default uv-sphere. Due to the inexact nature of the computation of the volume of these triangles when using floating point values such a situation will cause an exception. We now catch this exception, reorder the vertices randomly and try again. Not elegant but it works. (but it is not guaranteed to work in every situation). I tried to use Pythons decimal module but that was both slow and didn’t solve the problem so I’ll have to rethink that.

share & enjoy,

This will be very useful thank you !

Ok tried it for the first time on 2.61 and it does not work :frowning: .On torus it gives error and on Monkey head it makes weird faces.I tried on simple concave meshes and it just gives weird faces and crashes blender if i go in edit mode with that mesh.

A modifier is essentially a script that runs every time the frame changes. So you could implement your idea that way.