Algorithm to find the intersection of non-convex polyhedra
I propose the following approach.


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$.
Convert each convex polyhedron from V-representation (its list of vertices) to H-representation (intersection of half-spaces, given by linear inequalities).
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.