I have an algorithm that checks if two polyhedra intersect, by checking for intersections between all faces of one polyhedron against the faces of the other polyhedron.

To make the algorithm more efficient, I'm hoping to find a sub-algorithm that can efficiently identify faces that can't possibly intersect with the other polyhedron. Intuitively, if all vertices of the other polyhedron are in the same half-space defined by the current face, then this face can't intersect the other polyhedron. I could check this by doing the dot product of the normal vector of the face, with vectors pointing to the vertices of the other polyhedron, but this would require a lot of dot product calculations and would probably not reduce the complexity.

To reduce the size of the problem, I could find the smallest spheres that envelop either polyhedra. If the plane defined by the face doesn't intersect this sphere, then the face doesn't intersect the polyhedron that defines the sphere either, and the face can be disregarded. To check the sphere-plane intersection, I could find the points defined by going from the centre of the sphere in the direction of the plane normal vector, negative and positive direction, and with a distance equal to the sphere radius. If these two opposite points on the surface of the sphere are in the same half-space defined by the plane, then the plane doesn't intersect the sphere.

Note that the latter method would fail to identify some faces that can't intersect, but that's acceptable: Later intersection tests would determine if there are intersection on this face.

My goal is simply to reduce the set of faces required to check, it doesn't have to be the minimum set.

Are there other, more direct ways to accomplish this?

  • $\begingroup$ There is a standard algorithm for this. $\endgroup$ – Don Thousand Jun 23 '20 at 13:57
  • $\begingroup$ @DonThousand Please explain how that 2D polygon collision algorithm solves my 3D polyhedron collision problem. $\endgroup$ – K0ICHI Jun 23 '20 at 14:13
  • $\begingroup$ @KOICHI The separating hyperplane theorem... instead of looking at lines generating by sides of a polygon, look at planes generated by sides of a polyhedron. $\endgroup$ – Don Thousand Jun 23 '20 at 16:08
  • $\begingroup$ There are many online publications, such as this. Optimized implementations seem all to be not very simple. $\endgroup$ – WimC Jun 23 '20 at 18:10
  • $\begingroup$ @DonThousand OK, I see what you mean. I hadn't heard of this terminology before, but I realise how that this is actually what my current algorithm is doing. The thing is, these calculations are computationally heavy (despite using the most efficient algorithm that I know of) and there's many of them for most polyhedra. Your suggestion doesn't answer my question, which was to identify trivial faces that I don't need to use the SAT on. $\endgroup$ – K0ICHI Jun 24 '20 at 4:47

Axis-aligned bounding boxes can help.

If $(x_i , y_i , z_i)$ are the vertices in the polyhedron, or the vertices of a specific face, its axis-aligned bounding box is $$\bigr( \min(x_i), \min(y_i), \min(z_i) \bigr) - \bigr( \max(x_i), \max(y_i), \max(z_i) \bigr)$$

Two polyhedra can intersect only if their axis-aligned bounding boxes intersect. This means you only need to consider faces that intersect with the axis-aligned intersection of the two polyhedra.

If your polyhedra have both an circumsphere (that includes all its vertices) and an insphere (that is completely contained within the polyhedron), two polyhedra must intersect if their inspheres intersect. If their circumspheres do not intersect, the two polyhedra cannot intersect.

If you have the set of faces of one convex polyhedron that intersect the axis-aligned bounding box (intersection of the two polyhedra axis-aligned bounding boxes), and the set of edges in the other (that intersect that same axis-aligned bounding box), it suffices if you find the intersection of each edge (line segment) and each face, and test if that point is within the face.

If a face is defined using its normal vector $(x_n , y_n , z_n)$ and signed distance from origin $d$ ($x x_n + y y_n + z z_n = d$), and the edge is between $(x_0 , y_0 , z_0)$ and $(x_1, y_1, z_1)$, then calculate $$\Delta = x_n (x_1 - x_0) + y_n (y_1 - y_0) + z_n (z_1 - z_0)$$ If $\Delta = 0$, the edge is parallel to the face (and you can ignore this edge-face pair). Otherwise, calculate $$t = \frac{d - x_n x_0 - y_n y_0 - z_n z_0}{\Delta}$$ If $0 \le t \le 1$, the edge intersects the face at $$\begin{cases} x = (1 - t) x_0 + t x_1 \\ y = (1 - t) y_0 + t y_1 \\ z = (1 - t) z_0 + t z_1 \\ \end{cases}$$ and if that point is within the face polygon, or within the convex polyhedron the face belongs to (either test alone suffices), then the two polyhedra intersect.

Of course, if there are $N$ edges (from one polyhedron) and $M$ faces (from the other polyhedron), this is an $O(NM)$ worst case test (not including the complexity of point-on-face/point-in-polyhedron tests).

Faster convex polytope tests can be constructed based on separating axis theorem: Two convex objects do not overlap, if there exists a line (axis), such that the objects projected to the axis do not overlap.

  • $\begingroup$ Good suggestions. I'm already using circumspheres and inspheres to detect non-collision and collision respectively. AABB's are not tight enough when rotating 45 degrees off axis. And I'm already using a fast algorithm similar to SAT. But both SAT and my algorithm are still computationally heavy and could both benefit from discarding some trivial cases. $\endgroup$ – K0ICHI Jun 24 '20 at 7:02
  • $\begingroup$ @K0ICHI: If you can subdivide your polyhedron into simplices (tetrahedra), you might be able to speed up collision testing even further. Similarly, instead of a single circum/insphere pair, you can use several. The edge-plane testing can be speeded up by calculating the signed distance for each vertex for the current face plane, and then testing only the edges that intersect the face plane – obviously limiting to the set of edges and faces within the axis-aligned bounding box (AABB). It all depends on your polyhedra... $\endgroup$ – Guest Jun 24 '20 at 7:15
  • $\begingroup$ Thanks again. Yes, I'm using several circum/inspheres, where that makes sense. Haven't tested for the best common number of them yet, but probably beyond 8 per polyhedron, the cost outweighs the benefit. My algorithm already checks of all vertices currently being checked are in the same half space, and disregards if they are. Not sure if separating into tetrahedra would help, since I then introduce many more faces, but I do separate the faces into triangles, obviously only checking the triangles that have vertices in both half spaces. $\endgroup$ – K0ICHI Jun 24 '20 at 7:26
  • $\begingroup$ Currently working on the sphere-plane intersection test. Though simple in theory, the number of required operations makes me think this also might not be worth the extra work. $\endgroup$ – K0ICHI Jun 24 '20 at 7:29
  • $\begingroup$ @K0ICHI: If you have the plane normal as an unit vector $\hat{n}$ (and signed distance $d$), and the sphere is centered at $\vec{c}$ with radius $r$, then it suffices to test if $(\vec{c} + r \hat{n}) \cdot \hat{n} - d$ and $(\vec{c} - r \hat{n}) \cdot \hat{n} + d$ have different signs. In fact, the first one is $\vec{c}\cdot\hat{n} - r - d$, and the latter is $\vec{c}\cdot\hat{n}+r-d$! If they have the same sign, the sphere is on that side of the plane. If you need the exact intersection, use the line segment - plane intersection test in my answer with $\vec{c}\pm r\hat{n}$. $\endgroup$ – Guest Jun 24 '20 at 9:52

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.