Sunday 26 February 2012

3D Convex hull in Python, a Blender implementation.

A slight adaption of the code in my previous post to make it directly usable as a add mesh extension in Blender.

A Blender add mesh extension

As of Blender 2.64 there is a native Convex Hull operator availablein Blender.

I won't elaborate too much on my adaption as it has nothing to do with web development. The script can be downloaded from my site and should be installed in Blenders addons directory and enabled in the user preferences. It is tested with Blender 2.61.

I still think it is a nice implementation and although it is pure Python, it performs quite well. Of course there is a native convex hull implementation in Blender game engine but that one isn't accessible from Python. Previous implemenations relied on external programs like qhull, which might be faster for large point sets but having a pure Python implementation that is tightly integrated with Blender feels cleaner. It certainly can handle points sets of up to a couple of thousand points.

I have adapted it to randomize the order of the vertices if the hull algorithm bombs. This will happen if adding a point involves calculating the volume of many degenerate tetrahedrons which is the case when trying to compute the hull of Blenders default uv-sphere. I tried to use Python's decimal module but the results did not improve so now if an error is encountered the vertices are reordered and a second attempt is made. Not clean, but simple.

4 comments: