| The convex hull of a set of points is the minimal convex object that encapsulates another object, either convex or concave. As a result, the convex hull of a convex object is itself, and convex hulls of concave objects are always bigger in volume than the original shape. 2D Solution Several ways can be used to compute the convex hull of a set of points. In 2D, we would use the "rubberband method." This simple method computes the convex hull by using angular criteria. We start by searching the vertex in the mesh that has the minimal X value. Obviously, a vertex with a minimal coordinate value is always part of the convex hull. Then, we loop through the remaining vertices, looking for the vector that lies (angularly speaking) to one extreme of all the others. In other words, we must select the vertex from the set so that a segment from the original vertex to this newly added one has all other vertices located in the same hemispace. We then eliminate this new vertex and so on until we cannot add any further vertices, and we reach the starting point again. 3D Solution Several algorithms have been proposed to create 3D convex hulls. One of the best is the Quickhull algorithm, which uses a divide-and-conquer approach. The idea is simple: Start with vertices that are part of the solution and recursively add new vertices to the solution, refining it. The implementation is quite complex. Allocate a polyhedron that will hold the solution. Compute the maximal simplex from the 3D vertex list. In a 3D case, we must find four points from the set that define the maximal volume tetrahedron, which will be part of our result. To compute the tetrahedron, follow these steps: Compute the points with maximum and minimum X, Y, and Z values. Build lines that connect the minimum and maximum distance points in each direction: Xmin to Xmax, and so on. Select the longest line of the three. That's one edge of the tetrahedron. Now, select the point (of the minimax set) that has the longest distance to the line. That point and the line define a triangle that is part of the solution. Use the support plane of the triangle and detect the point of the minimax set that is farthest from the plane. The plane and the newly computed point define the tetrahedron, and thus the simplex.
Sort the points into those inside and outside of the tetrahedron. Delete those inside, because they are surely not part of the solution. Sort those outside into four groups, depending on which plane from the tetrahedron they lie outside of. If a point lies outside of more than one plane, place it randomly in one of them. Let's call these four sets the OUTSIDE set with regard to a face. While there are faces in the convex hull whose outside set is not empty: Find the point in the outside set that is farthest from the support plane. Compute the horizon of the polyhedron as seen from the selected point. This is used to refine edges from our polyhedron that are not really part of the convex hull. To construct the horizon, we perform a depth first search starting at the triangle the candidate point lies in. At each step in the process, we cross one edge and visit the neighboring triangle. If it is visible, we cross another edge, and so on. Whenever the crossing of an edge leads to a nonvisible (in terms of the dot product between the normal and the viewpoint vector, as in culling) triangle, we store the offending edge as part of the horizon and stop the search. When the algorithm is over, we have a list of edges that are all part of the horizon. Build a cone from the new vertex to the vertices on the horizon. Divide the outside set into two new sets. Those points inside the cone will be deleted (because they are not part of the convex hull), whereas those outside are the new OUTSIDE set. Iterate.
Now there are no vertices in any of the outside sets, and thus the convex hull is computed.
Quickhull is a complex algorithm. But in complexity lies efficiency. Quickhull runs in O(n2), whereas average case cost is close to N*log N, which would be the optimal solution for this kind of problem. |
