Volume of overlap between two convex polyhedra I have two convex polyhedra represented by triangle meshes.  I can easily determine if they are in contact or not, but when they are in contact then I would like to determine the volume of their overlap.  
I suspect it may involve doing edge/triangle intersection tests, recording points from intersections when found, then generating a convex hull from those points and determining its volume.  
If anyone knows of an existing method for this, it would be much appreciated!  I already have methods for determining things like minimum distance needed for separation.

 A: Good question! As you suspect, one common approach is to calculate the edges along which two boundary triangles intersect, cutting the triangles up along those edges so that every new triangle is contained entirely in the intersection of the two bodies, or entirely on the surface of one body, or entirely on the surface of the other, and then finding the volume of overlap is easy (you have effectively created a new polygonal mesh enclosing the common volume).
There ought to be a way of calculating it using a boundary integral as well, which would have the advantage that you could work with the geometry "as-is" without having to do any remeshing or CSG. Here are a few thoughts off of the cuff: we know that the volume of overlap is given by
$$V = \int_{M_1} \chi_{M_2}$$
where the integral is over the interior of the first body $M_1$, and the integrand is the indicator function of the body $M_2$. Now we can write the indicator function also as an integral
$$V=\int_{M_1} \int_{M_2} \delta(p-q)\,dq\,dp$$
where $\delta$ is the Dirac delta. The inner integral evaluates to 1 if $p$ is also inside $M_2$, and zero otherwise.
Finally, if $G$ is the Green's function of the Laplacian in $\mathbb{R}^3$, we have
\begin{align*}
V &= \int_{M_1} \int_{M_2} \Delta G(p,q)\,dq\,dp\\
&= \int_{M_1} \int_{\partial M_2} \nabla_q G(p,s)\cdot \hat{n}(s)\,ds\,dp\\
&= \int_{M_1} \int_{\partial M_2} -\nabla_p G(p,s) \cdot \hat{n}(s)\,ds\,dp\\
&= -\int_{M_1} \int_{\partial M_2} \nabla_p \cdot G(p,s)\hat{n}(s)\,ds\,dp\\
&= -\int_{M_1} \nabla_p \cdot \int_{\partial M_2} G(p,s)\hat{n}(s)\,ds\,dp\\
&= -\int_{\partial M_1}\int_{\partial M_2} G(t,s)\hat{n}(s)\cdot \hat{n}(t)\,ds\,dt.
\end{align*}
For two bodies with polygonal boundary the integrals can be split up as sums of integrals over pairs of faces; in each integral term the surface normals are constant so it's just a matter of integrating the Green's function
$$G(s,t) = \frac{-1}{4\pi \|s-t\|}$$
over a pair of (possibly intersecting) triangles. I'm not sure off-hand if there is a nice analytic formula for this.
A: An implementation is discussed in Powell & Abel (2014)
http://arxiv.org/abs/1412.4941
including the more general case of integrating a polynomial function over this overlap volume. It also links to a c-code which will do the calculations for you. 
A: There is software that will compute the intersection (or union) of two closed triangle meshes as another closed triangle mesh.  In fact, I wrote a program that reliably computes arbitrary triangle mesh intersections and unions.  
Once you have a closed triangle mesh of the intersection region, there is in fact a very nice formula for the volume.  The formula is obtained by using the divergence theorem:
$$
\int\int\int_V (\nabla\cdot\mathbf{F}) \operatorname{d}\!V = \int\int_S (\mathbf{F}\cdot \mathbf{n}) \operatorname{d}\!A \tag{1}
$$
where $\mathbf{F}:\mathbb{R}^3\rightarrow\mathbb{R}^3$ is any $C^1$ vector field and $\mathbf{n}$ is the exterior pointing unit surface normal.  Define $\mathbf{F}(x,y,z) = (x,y,z)$.  Then the left side of $(1)$ is just $3V$ (three times the volume of the region enclosed by the mesh).  To compute the surface integral for a single triangle $ABC$, the barycentric coordinates surface parameterization works very well. The barycentric coordinates for $A$ are $(u,v)=(1,0)$, for $B$ they are $(u,v)=(0,1)$ and for $C$ $(0,0).$  Barycentric coordinates map $(u,v)$ to $(x,y,z)$ like this:
$$
(x,y,z) = uA + vB + (1-u-v)C = u(A-C) + v(B-C) + C. \tag{2}
$$
Since $\mathbf{n}$ is orthogonal to all vectors in the plane of the triangle, $\mathbf{F}\cdot \mathbf{n}$ is very easy to compute: it's just $C\cdot\mathbf{n}$ or equivalently $A\cdot\mathbf{n}$ or $B\cdot\mathbf{n}$ since $(A-C)\cdot\mathbf{n} = (B-C)\cdot\mathbf{n} = 0.$  Using $(2)$ it is easy to compute $\mathbf{x}_u = A-C$ and $\mathbf{x}_v = B-C.$  So the surface integral is
$$
\begin{align}
\int\int_S (\mathbf{F}\cdot \mathbf{n}) \operatorname{d}\!A &= \int_0^1\int_0^{1-v} (C\cdot\mathbf{n}) |(A-C) \times (B-C)| \operatorname{d}\!u \operatorname{d}\!v \\
& = (C\cdot \mathbf{n})|(A-C) \times (B-C)| / 2 \\
& = (C\cdot ((A-C)\times (B-C))) / 2.
\end{align}
$$
The last equality above is true since $\mathbf{n} = ((A-C)\times (B-C)) / |(A-C)\times (B-C))|.$  So the formula for the volume of a closed triangle mesh is just
$$
V = \frac{1}{6}\sum_{i=1}^N (C_i\cdot ((A_i - C_i)\times (B_i - C_i))) \tag{3}
$$
where $A_i$, $B_i$, and $C_i$ are the vertices of the $i$th triangle of the mesh and $N$ is the number of triangles in the mesh.
I use the formula $(3)$ all the time. You could test it on some sphere meshes.  Just make sure that the face vertex order is consistent and produces an exterior facing normal. This means that if a triangle of your mesh is parallel to the screen and the exterior pointing normal pointing directly at you, the vertices $A$, $B$, and $C$ of the triangle must have counter-clockwise orientation. 
