和二维情形类似，给定三维空间的一些点，包含它们的最小凸多面体称为这些点的凸包。三维凸包的求法有很多，常用的有暴力法，卷包裹法和增量法。
暴力法。枚举每三个点组成的有向三角形（实际对应一个半空间），判断是否所有点都在这个三角形的同侧（即半空间的内部）。如果是，则这个三角形是凸包中的一个面。否则就不是。判断一个点在三角形的那一侧需要一次叉积和一次点积（也可以理解为一次混合积），因此一共需要O(n^4)次叉积和点积。
卷包裹法。该算法的思想是先找到一条肯定在凸包上的边PiPj（比如，投影在平面上的凸包的边），然后想象一张纸紧贴这条边向左（这里是指向量PiPj的左边）旋转，直到碰到一个点Pk，然后以PkPj和PiPk为轴继续旋转。
尽管看上去简单，卷包裹法在实现上仍有一些需要注意的地方。首先是初始边的选择。一般先把点投影到z=0平面，求出二维凸包，然后把二维凸包上的一条边作为三维凸包卷包裹的初始边。根据二维凸包的性质，不必真的左投影和找凸包，而只需找一个y坐标最小的点作为起点，到它极角最小的点作为第二点。看上去很简单，请注意，当y最小和极角最小的选择不止一个时很容易出问题，读者不妨仔细思考(可能选择的边穿过了多面体)。另外，在卷包裹的过程中，多点共面也是比较麻烦的问题（可能会出现找不到下一个顶点的情况，因为可能多次访问）。卷包裹的实现需要十分小心。
增量法。该算法的基本思想是把点依次加到凸包中。初始时随机选两个点p1和p2，然后找一个不和这两个点共线的点p3，再找一个不和它们共面的蒂娜p4，组成初始凸包，然后依次考虑其他点pr，如果这个点在当前凸包内，直接忽略。否则找到这个点能看到的所有面，删除它们，然后把阴影边界的所有点和pr连接起来，其中每条边和pr一起构成一个三角形。
这个算法的简单实现方法是遍历所有面，判断是否可见；然后遍历所有边，判断是否在阴影边界上（即该边的两侧恰好有一个面可见）。
首先是面的定义：
struct Face { int v[3]; //顶点下标。 Vector3 normal(Point3 *P) const //求面的法线 { return Cross(P[v[1]] - P[v[0]], P[v[2]] - P[v[0]]); } int cansee(Point3 *P, int i) const //从p[i]是否可以看到此面 { return Dot(P[i]-P[v[0]], normal(P)) > 0 ? 1:0; } };增量法取三维凸包。
没有考虑各种特殊情况（如4点共面）。实践中，请在调用前对输入点进行微小扰动。
vector<Face> CH3D(Point3 *P, int n) { vector<Face> cur; int a, b, res, i, j, k, vis[maxn][maxn]; cur.push_back((Face){0, 1, 2}); cur.push_back((Face){2, 1, 0}); //两个面，取得可以看到的面，另一个边被删除 for(i = 3; i < n; i++) { vector<Face> next; //计算每条边左面的可见性 for(j = 0; j < cur.size(); j++) { Face &f = cur[j]; res = f.cansee(P, i); if(!res) next.push_back(f); for(k = 0; k < 3; k++) vis[f.v[k]][f.v[(k+1)%3]] = res; } for(j = 0; j < cur.size(); j++) for(k = 0; k < 3; k++) { a = cur[j].v[k]; b = cur[j].v[(k+1)%3]; if(vis[a][b] != vis[b][a] && vis[a][b]) //(a,b)是分界线，左边对P[i]可见 next.push_back((Face){a, b, i}); } cur = next; } return cur; }由于没有考虑特殊情况（比如凸包上多点共面）。简单起见，实践中常常把输入点进行微小扰动后再调用上述过程。
0-1的随机数
double rand01() //0-1的随机数 { return rand() / (double)RAND_MAX; }-eps/2到eps/2的随机数
double randeps() //-eps/2到eps/2的随机数 { return (rand01() - 0.5) * eps; }对点进行干扰
Point3 add_noise(const Point3 &p) //对点进行干扰 { return Point3(p.x+randeps(), p.y+randeps(), p.z+randeps()); }注意扰动之前的点要备份。上述代码中的Face结构体是顶点下标。所以可以用扰动后的点求三维凸包，然后用这些下标引用原来（未扰动）的点。此外，还有一个很容易忽略的问题，即输入点应先判重，否则在扰动后很容易出现极小的面，这样的面很容易造成麻烦。
