Usually you should only need the L{qhull3d} function, although the module contains some potentially useful helper functions as well.

Examples

Tetrahedron

>>> import random
>>> tetrahedron = [(0,0,0),(1,0,0),(0,1,0),(0,0,1)]
>>> for i in range(200):
...     alpha = random.random()
...     beta = random.random()
...     gamma = 1 - alpha - beta
...     if gamma >= 0:
...         tetrahedron.append((alpha, beta, gamma))
>>> verts, triangles = qhull3d(tetrahedron)
>>> (0,0,0) in verts
True
>>> (1,0,0) in verts
True
>>> (0,1,0) in verts
True
>>> (0,0,1) in verts
True
>>> len(verts)
4
>>> len(triangles)
4

A double pyramid polyhedron

>>> poly = [(2,0,0),(0,2,0),(-2,0,0),(0,-2,0),(0,0,2),(0,0,-2)]
>>> vertices, triangles = qhull3d(poly)
>>> len(vertices)
6
>>> len(triangles)
8
>>> for triangle in triangles: # check orientation relative to origin
...     verts = [ vertices[i] for i in triangle ]
...     assert(vecDotProduct(vecCrossProduct(*verts[:2]), verts[2]) == 8)

A pyramid

>>> verts, triangles = qhull3d([(0,0,0),(1,0,0),(0,1,0),(1,1,0),(0.5,0.5,1)])
>>> (0,0,0) in verts
True
>>> (1,0,0) in verts
True
>>> (0,1,0) in verts
True
>>> (1,1,0) in verts
True
>>> len(verts)
5
>>> len(triangles)
6

The unit cube

>>> import random
>>> cube = [(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)]
>>> for i in range(200):
...     cube.append((random.random(), random.random(), random.random()))
>>> verts, triangles = qhull3d(cube)
>>> len(triangles) # 6 faces, written as 12 triangles
12
>>> len(verts)
8

A degenerate shape: the unit square

>>> import random
>>> plane = [(0,0,0),(1,0,0),(0,1,0),(1,1,0)]
>>> for i in range(200):
...     plane.append((random.random(), random.random(), 0))
>>> verts, triangles = qhull3d(plane)
>>> len(verts)
4
>>> len(triangles)
2

A random shape

>>> import random
>>> shape = []
>>> for i in range(2000):
...     vert = (random.random(), random.random(), random.random())
...     shape.append(vert)
>>> verts, triangles = qhull3d(shape)

Precision

>>> plane = [(0,0,0),(1,0,0),(0,1,0),(1,1,0),(1.001, 0.001, 0)]
>>> verts, triangles = qhull3d(plane, precision=0.1)
>>> len(verts)
4
>>> len(triangles)
2

qdome2d(vertices, base, normal, precision=0.0001)

source code

Build a convex dome from C{vertices} on top of the two C{base} vertices, in the plane with normal C{normal}. This is a helper function for L{qhull2d}, and should usually not be called directly.

Parameters:

vertices - The vertices to construct the dome from.
base - Two vertices that serve as a base for the dome.
normal - Orientation of the projection plane used for calculating distances.
precision - Distance used to decide whether points lie outside of the hull or not.

Returns:

A list of vertices that make up a fan of the dome.

qhull2d(vertices, normal, precision=0.0001)

source code

Simple implementation of the 2d quickhull algorithm in 3 dimensions for vertices viewed from the direction of C{normal}. Returns a fan of vertices that make up the surface. Called by L{qhull3d} to convexify coplanar vertices.

>>> import random
>>> import math
>>> plane = [(0,0,0),(1,0,0),(0,1,0),(1,1,0)]
>>> for i in range(200):
...     plane.append((random.random(), random.random(), 0))
>>> verts = qhull2d(plane, (0,0,1))
>>> len(verts)
4
>>> disc = []
>>> for i in range(50):
...     theta = (2 * math.pi * i) / 50
...     disc.append((0, math.sin(theta), math.cos(theta)))
>>> verts = qhull2d(disc, (1,0,0))
>>> len(verts)
50
>>> for i in range(400):
...     disc.append((0, 1.4 * random.random() - 0.7, 1.4 * random.random() - 0.7))
>>> verts = qhull2d(disc, (1,0,0))
>>> len(verts)
50
>>> dist = 2 * math.pi / 50
>>> for i in range(len(verts) - 1):
...      assert(abs(vecDistance(verts[i], verts[i+1]) - dist) < 0.001)

Parameters:

vertices - The vertices to construct the hull from.
normal - Orientation of the projection plane used for calculating distances.
precision - Distance used to decide whether points lie outside of the hull or not.

Returns:

A list of vertices that make up a fan of extreme points.

basesimplex3d(vertices, precision=0.0001)

source code

Find four extreme points, to be used as a starting base for the quick hull algorithm L{qhull3d}.

The algorithm tries to find four points that are as far apart as possible, because that speeds up the quick hull algorithm. The vertices are ordered so their signed volume is positive.

If the volume zero up to C{precision} then only three vertices are returned. If the vertices are colinear up to C{precision} then only two vertices are returned. Finally, if the vertices are equal up to C{precision} then just one vertex is returned.

>>> import random
>>> cube = [(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)]
>>> for i in range(200):
...     cube.append((random.random(), random.random(), random.random()))
>>> base = basesimplex3d(cube)
>>> len(base)
4
>>> (0,0,0) in base
True
>>> (1,1,1) in base
True

Parameters:

vertices - The vertices to construct extreme points from.
precision - Distance used to decide whether points coincide, are colinear, or coplanar.

Returns:

A list of one, two, three, or four vertices, depending on the the configuration of the vertices.

qhull3d(vertices, precision=0.0001, verbose=False)

source code

Return the triangles making up the convex hull of C{vertices}. Considers distances less than C{precision} to be zero (useful to simplify the hull of a complex mesh, at the expense of exactness of the hull).

Parameters:

vertices - The vertices to find the hull of.
precision - Distance used to decide whether points lie outside of the hull or not. Larger numbers mean fewer triangles, but some vertices may then end up outside the hull, at a distance of no more than C{precision}.
verbose - Print information about what the algorithm is doing. Only useful for debugging.

Returns:

A list cointaining the extreme points of C{vertices}, and a list of triangle indices containing the triangles that connect all extreme points.

Module quickhull

Examples

Tetrahedron

A double pyramid polyhedron

A pyramid

The unit cube

A degenerate shape: the unit square

A random shape

Precision

qdome2d(vertices, base, normal, precision=0.0001)

qhull2d(vertices, normal, precision=0.0001)

basesimplex3d(vertices, precision=0.0001)

qhull3d(vertices, precision=0.0001, verbose=False)