Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given two rectangular parallelepipeds in 3D space, how would you compute the volume of their intersection? The orientations of the two rectangular parallelepipeds are not constrained in any special way. Each parallelepiped is described by a point P that is a corner of the parallelepiped as well as vectors F, G, and H which represent the three mutually orthogonal edges that meet at point P.

share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

A workable way would be to clip all 6 boundary faces of each box against the boundary planes of the other, which leaves you with a bunch of convex faces that form the boundary of the intersection object. The actual volume of this object can be calculated by

$$ V = \frac{1}{3} \sum_{F_i \in Faces} \vec p_i \cdot \vec n_i A_i $$

in which $\vec p_i$ is a point on the face, $\vec n_i$ is the unit face normal and $A_i$ is the area of face $F_i$. Take care to keep the orientation of the faces consistent, however.

share|improve this answer
add comment

I was thinking of a few different approaches. Rectangular prisms are well-behaved, so it may be possible to do a very direct calculation using some brute force multivariable integrals. This seems... painful.

I am unconvinced that there is a general and easy way of doing this, though I should say that WLOG we can assume one prism to be in the 'normal' orientation with one vertex at the origin, and lying entirely in the positive octant (are octants numbered like 2D quadrants are?).

Unless I am mistaken, the intersection will be convex (this seems true, yes?) and a polyhedron. So it can be decomposed into tetrahedra using only the original vertices. This should work. Is it hard? I don't think so, but I haven't decomposed many polyhedra before.

These are just my thoughts on the problem, and unfortunately too long to be a comment.

share|improve this answer
    
The octant you want is called the "first octant," but the rest are typically not numbered (no simple way to order them). –  Isaac Jun 28 '11 at 21:36
add comment

If you need to write code for that and already have code for tetrahedra intersection, you could replace each parallelepiped by 3 tetrahedra, and then sum volume of all intersections between them. (Intersection of 2 tetrahedra is in general union of $0\dots4$ tetrahedra).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.