I'm on the lookout to finding an algorithm that calculates the volume of the intersection between two cuboids. Most answers so far assume all the axes of the two cuboids in question are nicely aligned. Not the case in my problem. See figure below
Finding out what corners of the two cuboid are in each others space is not that difficult. Also determining some boundary points on the cuboids faces shouldn't be problematic. The hard part where I get lost is to determine what kind of shape the intersection actually is and how to calculate it's volume. I think it's safe to assume the intersection will be convex. Any suggestions?
Here is an alternative approach:
Define each of your cuboids or parallelepipeds as six opposing faces.
For each face of the target convex polyhedron, define both the face plane (unit normal vector $\hat{n}$ and signed distance from origin $d$, so that point $\vec{p}$ is inside the halfspace if and only if $\hat{n}\cdot\vec{p} - d \ge 0$), and the vertices of the face polygon $\vec{v}_i$, $i = 1 \dots N$, in counterclockwise order so that $$\hat{n}\cdot\bigl((\vec{v}_{i-1} - \vec{v}_i) \times (\vec{v}_{i+1} - \vec{v}_i)\bigr) \gt 0 \quad \forall i$$ where the index wraps around, i.e. $\vec{v}_0 = \vec{v}_N$ and $\vec{v}_{N+1} = \vec{v}_1$.
Then, apply each halfspace $\hat{n}$, $d$ of the other convex polyhedron, cutting out the vertices $\vec{v}$ in the target polyhedron that are outside the cutting halfspace, $\hat{n}\cdot\vec{v} - d \lt 0$, one at a time.
Because you "cut" the convex polyhedron left with halfspaces, the result is either a convex polyhedron, or nothing. Note that the centroid is always within the convex polyhedron, so the total volume can be calculated as the sum of the volumes of pyramids with the apex at the centroid, and the base the face polygon.
If the halfspace includes all existing vertices, it includes the entire polyhedron, and the halfspace has no effect.
Otherwise, the halfspace removes at least one vertex, and adds a new face.
If the halfspace removes all vertices of a face, that face is completely removed.
On each face where at least one vertex, but not all vertices, are removed by the halfspace, a section of the face polygon is replaced by a single edge, corresponding to the intersection with the face plane and the new halfspace (plane), so that all removed vertices are in the replaced segment; and the removed vertices are continuous in the face polygon.
So, by identifying first the vertices excluded by the halfspace, then finding the face edges between an excluded vertex and not-excluded vertex (line-plane intersection – very fast to compute), we can quickly update each partially cut face. The added new edges across all existing faces form the new face, too.
If you describe each convex polyhedron with a data structure that contains
All $N$ vertices $\vec{v}_i$, $i = 1 \dots N$, on the convex polyhedron
All $F$ face unit normal vectors $\hat{n}_f$ and signed distances $d_f$ from origin, $f = 1 \dots F$
For each face $f$, the vertices (vertex indexes) in counterclockwise order, defining the face polygon
you can quickly construct the set of edges that will be modified (for example, as triplets from vertex, to vertex, face), and their replacements.
Let $\vec{v}_k$ are the $K$ vertices of a convex polyhedron, $k = 1 \dots K$. The centroid $\vec{C}$ is then $$\vec{C} = \frac{1}{K} \sum_{k=1}^{K} \vec{v}_k$$
Let $\vec{p}_i$ are the $N$ vertices of one planar face of the convex polyhedron, $i = 1 \dots N$, with cyclic indexing so $\vec{p}_0 = \vec{p}_N$ and $\vec{p}_{N+1} = \vec{p}_1$. Let $\hat{n}$ be the face plane unit normal vector, pointing inwards. Because the polyhedron is convex, each face polygon is convex also, and therefore the face centroid $\vec{c}$ is $$\vec{c} = \frac{1}{N} \sum_{i=1}^{N} \vec{p}_i$$ and the area of this face is $$A = \frac{1}{2} \left\lVert \sum_{i=1}^{N} (\vec{p}_i - \vec{c}) \times (\vec{p}_{i+1} - \vec{c}) \right\rVert = \frac{1}{2} \sum_{i=1}^{N} \left\lvert \hat{n} \cdot (\vec{p}_{i} - \vec{c}) \times (\vec{p}_{i+1} - \vec{c}) \right\rvert$$ (because each cross product summand is always $\lambda \hat{n}$, $\lambda \in \mathbb{R}$, by definition – otherwise the face is not planar! – and $\lambda \ge 0$ or $\lambda \le 0$ depending on whether the vertices are in counterclockwise or clockwise order in the convex planar polygon) and the volume contribution of this face is $$V_f = \frac{A}{3} \hat{n} \cdot \left(\vec{C} - \vec{c}\right) = \frac{\hat{n} \cdot (\vec{C} - \vec{c})}{6} \sum_{i=1}^{N} \left\lvert \hat{n} \cdot (\vec{p}_{i} - \vec{c}) \times (\vec{p}_{i+1} - \vec{c}) \right\rvert$$ Summing the volume contributions of all faces yields the total volume, $$V = \sum_{f=1}^{F} V_f$$