How do I find a reduced set of faces required to check for intersection, to determine if two convex polyhedra intersect? I have an algorithm that checks if two polyhedra intersect, by checking for intersections between all faces of one polyhedron against the faces of the other polyhedron.
To make the algorithm more efficient, I'm hoping to find a sub-algorithm that can efficiently identify faces that can't possibly intersect with the other polyhedron. Intuitively, if all vertices of the other polyhedron are in the same half-space defined by the current face, then this face can't intersect the other polyhedron. I could check this by doing the dot product of the normal vector of the face, with vectors pointing to the vertices of the other polyhedron, but this would require a lot of dot product calculations and would probably not reduce the complexity.
To reduce the size of the problem, I could find the smallest spheres that envelop either polyhedra. If the plane defined by the face doesn't intersect this sphere, then the face doesn't intersect the polyhedron that defines the sphere either, and the face can be disregarded. To check the sphere-plane intersection, I could find the points defined by going from the centre of the sphere in the direction of the plane normal vector, negative and positive direction, and with a distance equal to the sphere radius. If these two opposite points on the surface of the sphere are in the same half-space defined by the plane, then the plane doesn't intersect the sphere.
Note that the latter method would fail to identify some faces that can't intersect, but that's acceptable: Later intersection tests would determine if there are intersection on this face.
My goal is simply to reduce the set of faces required to check, it doesn't have to be the minimum set.
Are there other, more direct ways to accomplish this?
 A: Axis-aligned bounding boxes can help.
If $(x_i , y_i , z_i)$ are the vertices in the polyhedron, or the vertices of a specific face, its axis-aligned bounding box is
$$\bigr( \min(x_i), \min(y_i), \min(z_i) \bigr) - \bigr( \max(x_i), \max(y_i), \max(z_i) \bigr)$$
Two polyhedra can intersect only if their axis-aligned bounding boxes intersect.
This means you only need to consider faces that intersect with the axis-aligned intersection of the two polyhedra.

If your polyhedra have both an circumsphere (that includes all its vertices) and an insphere (that is completely contained within the polyhedron), two polyhedra must intersect if their inspheres intersect.  If their circumspheres do not intersect, the two polyhedra cannot intersect.

If you have the set of faces of one convex polyhedron that intersect the axis-aligned bounding box (intersection of the two polyhedra axis-aligned bounding boxes), and the set of edges in the other (that intersect that same axis-aligned bounding box), it suffices if you find the intersection of each edge (line segment) and each face, and test if that point is within the face.
If a face is defined using its normal vector $(x_n , y_n , z_n)$ and signed distance from origin $d$ ($x x_n + y y_n + z z_n = d$), and the edge is between $(x_0 , y_0 , z_0)$ and $(x_1, y_1, z_1)$, then calculate
$$\Delta = x_n (x_1 - x_0) + y_n (y_1 - y_0) + z_n (z_1 - z_0)$$
If $\Delta = 0$, the edge is parallel to the face (and you can ignore this edge-face pair).  Otherwise, calculate
$$t = \frac{d - x_n x_0 - y_n y_0 - z_n z_0}{\Delta}$$
If $0 \le t \le 1$, the edge intersects the face at
$$\begin{cases}
x = (1 - t) x_0 + t x_1 \\
y = (1 - t) y_0 + t y_1 \\
z = (1 - t) z_0 + t z_1 \\
\end{cases}$$
and if that point is within the face polygon, or within the convex polyhedron the face belongs to (either test alone suffices), then the two polyhedra intersect.
Of course, if there are $N$ edges (from one polyhedron) and $M$ faces (from the other polyhedron), this is an $O(NM)$ worst case test (not including the complexity of point-on-face/point-in-polyhedron tests).

Faster convex polytope tests can be constructed based on separating axis theorem: Two convex objects do not overlap, if there exists a line (axis), such that the objects projected to the axis do not overlap.
