Algorithm to find the intersection of non-convex polyhedra

Question

Context:

I have two polyhedra, $A = V_1\times F_1$ and $B=V_2\times F_2$ where $V_i$ is set of vertices (which are just coordonate in $\mathbb R^3$) and $F_i$ is a set of faces (tuples of length $\geq 3$ such as $(i_1,...,i_k) \in F_i$ iff there is a face formed by the $i_1$-th,...,$t_k$-th vertices of $A_i$). Then, if I want to draw a cube, I will have 8 vertices in $V$ and 6 tuples of length $4$ that define the vertices of each square that makes the 6 faces of my cube.

These are not necessarily convex (but at least they are connected).

The problem:

Find an algorithm that takes $A,B$ and return $C$ the intersection of the two polyhedra.

---

My research:

I found this on the stack network: https://mathoverflow.net/questions/141703/intersection-of-polyhedra

But the answers focuses on collision detection rather than returning the intersection of the two bodies.

The other articles I found online seem also to be all about collision detection rather than intersection.

My attempts:

I first imagine to approximate polyhedra with voxels, since it is pretty easy to find intersections of 0-1 arrays. But In my case, I would need too many voxels, then it would lead to too much memory use.

I do not have any other idea to solve efficiently my problem.

Answer 1

I propose the following approach.

1. Decompose each polyhedron into a union of convex polyhedra, say $A = A_1 \cup \cdots \cup A_m$ and $B = B_1 \cup \cdots \cup B_n$.

2. Convert each convex polyhedron from V-representation (its list of vertices) to H-representation (intersection of half-spaces, given by linear inequalities).

3. Compute the intersection as $A \cap B = \bigcup_{i,j} A_i \cap B_j$, where you can compute $A_i \cap B_j$ trivially once they are in H-representation: you just concatenate the list of linear inequalities. (If you want, you can convert $A_i \cap B_j$ back to V-representation.)

There are standard algorithms for doing step 2. In fact, given a face, it is easy to construct the corresponding linear inequality (form the plane that goes through all of the vertices on the face, then create the corresponding linear equality, then change the equality to an inequality).

I'm not sure how to do step 1; perhaps that is worth asking as a separate question, if you can't figure it out after some research.