How to find all points of penetration/contact of two boxes (rectangular parallelepipeds), knowing the coordinates of their vertices?

Question

3D

We have two boxes (rectangular boxes), we know the coordinates of their vertices. We need to determine the points of their contact/interpenetration into each other. Can anyone help me?
PS I'm writing a small physics engine. Such advice as "use a ready-made engine" please do not write.

Answer 1

I think you should take a ready-made open source engine and see how experienced people do it.
All more or less complex algorithms for finding the intersection of convex polyhedra are based on the "Separating Axis Theorem". The essence is simple: if the projections of polyhedra on some straight line do not intersect, then they do not intersect in space. If there is no such axis, then they intersect. As such, they will not have end points of intersection, there will be a whole polyhedron of these intersections. But for the physics engine, you need to select a certain number of characteristic points, and this choice will depend on the axis that you yourself choose. In most cases, such an axis is chosen as a straight line on which the intersection of the projections is minimal.
What axles should be checked? After all, there are an infinite number of them.
It depends on the topology. In the general case, it is enough to check the axes collinary to the normals of all faces of polyhedra (in this case we are looking for an intersection with a face), and the axes obtained by the vector product of each edge of one polyhedron with each edge of another (edge-edge intersection). But, since Box has a lot of parallel faces and edges, it makes no sense to check all of them. Since it will turn out a bunch of identical axes.
In total, it turns out that you need to check 3 + 3 (faces) + 3 * 3 (pairs of edges) = 15 potential separating axes. In the first case, it will then be necessary to find the intersection of the face with the vertices, and from those vertices that intersect the plane, build a polygon and intersect it already in 2D, getting from 1 to 6 intersection points. In the second case, it is even simpler - we are looking for the intersection point of two vectors.
PS: It's better to start your own engine with simpler figures - spheres and cassettes. Their intersection function is a couple of orders of magnitude simpler.

Answer 2

couples at the university did not have to skip)