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?