A similar question is “How do I mesh a volume from a set of triangulated surface points?
This is an instance of the constrained Delaunay Triangulation problem. Qhull does not handle constraints. The boundary of the Delaunay triangulation is always convex. But if the input set contains enough points, the triangulation will include the boundary. The number of points needed depends on the input. Shewchuk has developed a theory of constrained Delaunay triangulations. See his paper at the 1998 Computational Geometry Conference. Using these ideas, constraints could be added to Qhull. They would have many applications. There is a large literature on mesh generation and many commercial offerings. For pointers see Owen’s Meshing Research Corner and Schneiders’ Finite Element Mesh Generation page.
