As in polygons we begin with the boundary theorem: ∂(x∩y) = x∩∂y ∪ ∂x∩y which is good for any number of dimensions. Also carried over from the 2D case is the winding number at a point which may be generalized as the net number of times you leave the polyhedron starting from the point and going continuously to infinity. We propose to compute the integral of the product of the winding numbers of two polyhedra, thus generalizing our 2D code.
I restrict myself to polyhedra with triangular faces (or simplexes when n>3). The polyhedra are given as an unordered list of faces, each an oriented triangle which is given as a triple (n-tuple) of indexes into an array of shared vertices, each of which is given by its Cartesian coördinates.
An element of the boundary of the intersection (IBE) is an oriented planar area in space. In this sense the boundary is not the union of these IBEs but the sum considering signs. (Plan A: We associate a volume with each IBE as we associate an area with line segments in the polygon case. In this case the volume between the oriented triangle and some fixed plane which is held constant for the entire computation. This too is signed (oriented). The volume of the intersection is the sum of the volumes associated with the IBEs.) (Plan B: We adopt these ideas) I characterize the intersection of the boundaries here.
The ideas above generalize to n dimensions with “(n−1)-simplex” substituted for “triangle”.
The IBEs are thus to be enumerated so as to sum their associated volumes. Some of the above ideas are recursively applied in one less dimension in identifying these IBEs. Each IBE is in the plane of a face of one of the polyhedra. It is itself bounded by line segments ((n−2)-simplexes). These 2nd order boundaries arise in several disjoint manners:
For each face of the other polyhedron we test to see if the plane cuts it. If so the intersection is a line segment which may intersect the first face.
The above amounts to an algorithm to find all intersections of a face of the first polyhedron with a face of the second. These line segments each bound two IBEs, one from the 1st and one from the 2nd polyhedron. The other IBE boundaries are edges of the original polyhedra. Such a line segment face intersection quantifies an IBE portion.
Each face has a first vertex as specified in the input data. If that vertex is in the other polyhedron then include the associated volume for that face. For each face intersection ... (like this but in 3D) For each edge that begins inside the other polyhedron, it bounds two IBEs, one in the face of each polyhedron.
When an edge of one polyhedron pierces a face of the other, we have a transaction. The edge bounds two faces, each of which intersect the first face. An edge may indeed pierce several faces of the other polyhedron. If the other polyhedron does not intersect itself then these piercings will alternate orientation—in and out. The resulting contributions will be in effect only for alternate intervals between the piercings.
For each face of both polyhedra we compute the linear function which is zero on that face. We record the sign of that function for each vertex of the other polyhedron. For each edge of both polyhedra we consider each face of the other polyhedron whose plane separates the ends of the edge. For those cases we check for piercing.