2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You could investigate the intersection algorithm used by Blender. There have been at least two so far, because the first one had trouble with coplanar faces (and the other one might, too, as will inevitably have any that uses floating point numbers) $\endgroup$ – John Dvorak Jun 9 at 17:00
  • $\begingroup$ @D.W. it's the wrong word ("connexe" is the french word for "connected"). I edited my question. Thanks for your comment. $\endgroup$ – MiKiDe Jun 10 at 7:16
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jun 10 at 7:30
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer, this method suits pretty well in my case. The 1. seems to be well documented online. By standard algorithm, could you give me one reference? $\endgroup$ – MiKiDe Jun 10 at 7:39
  • $\begingroup$ @MiKiDe, I don't remember -- it's been a while since I looked at this. Sorry. $\endgroup$ – D.W. Jun 10 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.