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.
Best Answer
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.