GK.ConvexHullCalculator Class Reference

An implementation of the quickhull algorithm for generating 3d convex hulls. More...

Public Member Functions
void	GenerateHull (List< Vector3 > points, bool splitVerts, ref List< Vector3 > verts, ref List< int > tris, ref List< Vector3 > normals)
	Generate a convex hull from points in points array, and store the mesh in Unity-friendly format in verts and tris. If splitVerts is true, the the verts will be split, if false, the same vert will be used for more than one triangle. More...
void	GenerateHull2 (List< Vector3 > points, ref List< int > tris)

Detailed Description

An implementation of the quickhull algorithm for generating 3d convex hulls.

The algorithm works like this: you start with an initial "seed" hull, that is just a simple tetrahedron made up of four points in the point cloud. This seed hull is then grown until it all the points in the point cloud is inside of it, at which point it will be the convex hull for the entire set.

All of the points in the point cloud is divided into two parts, the "open set" and the "closed set". The open set consists of all the points outside of the tetrahedron, and the closed set is all of the points inside the tetrahedron. After each iteration of the algorithm, the closed set gets bigger and the open set get smaller. When the open set is empty, the algorithm is finished.

Each point in the open set is assigned to a face that it lies outside of. To grow the hull, the point in the open set which is farthest from it's face is chosen. All faces which are facing that point (I call them "lit faces" in the code, because if you imagine the point as a point light, it's the set of points which would be lit by that point light) are removed, and a "horizon" of edges is found from where the faces were removed. From this horizon, new faces are constructed in a "cone" like fashion connecting the point to the edges.

To keep track of the faces, I use a struct for each face which contains the three vertices of the face in CCW order, as well as the three triangles which share an edge. I was considering doing a half-edge structure to store the mesh, but it's not needed. Using a struct for each face and neighbors simplify the algorithm and makes it easy to export it as a mesh.

The most subtle part of the algorithm is finding the horizon. In order to properly construct the cone so that all neighbors are kept consistent, you can do a depth-first search from the first lit face. If the depth-first search always proceeeds in a counter-clockwise fashion, it guarantees that the horizon will be found in a counter-clockwise order, which makes it easy to construct the cone of new faces.

A note: the code uses a right-handed coordinate system, where the cross-product uses the right-hand rule and the faces are in CCW order. At the end of the algorithm, the hull is exported in a Unity-friendly fashion, with a left-handed mesh.

Member Function Documentation

GenerateHull()

void GK.ConvexHullCalculator.GenerateHull	(	List< Vector3 >	points,
		bool	splitVerts,
		ref List< Vector3 >	verts,
		ref List< int >	tris,
		ref List< Vector3 >	normals
	)

Generate a convex hull from points in points array, and store the mesh in Unity-friendly format in verts and tris. If splitVerts is true, the the verts will be split, if false, the same vert will be used for more than one triangle.