Functions | |
void | Compute_Convex_Hull (int pcount, const HC_POINT *points, int *fcount, int *face_list) |
Given a set of points, determines the set of faces that minimally bind all the points. More... | |
void Compute_Convex_Hull | ( | int | pcount, |
const HC_POINT * | points, | ||
int * | fcount, | ||
int * | face_list | ||
) |
Given a set of points, determines the set of faces that minimally bind all the points.
pcount | - Number of valid points in points. |
points | - Vector of x-y-z triplets for the coordinates of the vertices. (A simple N*3 can also be used.) Passed by reference always. |
fcount | - Total number of integers returned in face_list. Passed by reference always. Returned to user. |
face_list | - Encoded description of how to connect the points to build the faces of the hull. Same format as in Insert_Shell() . Passed by reference always. Returned to user. Potentially up to 8*pcount*sizeof(int) in length. |
A "hull", as used here, is a closed wrapper around a set of points. The hull is a simple polyhedron, its vertices are chosen only from the set of points, and all the points end up either on the surface or within the hull.
For all but the simplest sets of points there are many possible hulls. However, disregarding degeneracies (coplanar/colinear points), there is only one possible convex hull surrounding any given set of points. Compute_Convex_Hull() computes this shape. The input is a list of points. The output is a face connectivity list suitable for passing to Insert_Shell() .
Compute_Convex_Hull() only produces convex figures, by definition. However, there is nothing preventing you from artificially moving one of the points inward to form a concave figure after Compute_Convex_Hull() returns. Likewise, Compute_Convex_Hull() only produces closed figures, by definition. There is nothing preventing you from artificially removing one or more of the faces to form an open shell afterwards.
The variable, face_list_length, is the number of entries in face_list that the system has used up. face_list_length is returned to you. It is not the total available space you're passing in. The system assumes your face_list is "big enough" to hold any possible result. Allow for at least 8*pcount*sizeof(int) in face_list – in other words, the new face list contains up to 2*pcount triangles.
The algorithm used is O(n squared). In other words, it's going to take a while.
Not all the points will necessarily be mentioned in the face_list. Depending on the shape of your object, many points might be completely interior to the hull and thus unconnected.
Another definition of "convex hull" is "the surface of the smallest area that encloses a set of points".