[Math] Intersection of Polyhedra

computational geometrymg.metric-geometrypolyhedra

I'm writing a collision detection algorithm, and so far I've been using Joseph O'Rourke's book "Computational Geometry in C" as reference. It outlines an algorithm to determine whether a point is inside a polyhedron by counting the number of faces that a ray crosses which starts at the point.

I've been using this algorithm to check if any vertex of one polyhedron is inside another polyhedron, but this doesn't necessarily detect collisions between the two.

This post is two-fold:

  1. I'd like to extend this algorithm to account for a margin around the polyhedra. (i.e. determine whether a point is at least a margin length away from a polyhedron.)
  2. Is there a relatively fast algorithm used to determine the intersection of two polyhedra?

Question 1 Attempts

Given that a plane can be described by $A x + B y + C z = D$, could I just add the margin to D and continue with the algorithm in O'Rourke's book?

Question 2 Attempts

I think this could be done by computing the intersection of every segment of one polyhedron with the 3D triangle faces of the other, and then vice versa. This seems very computationally expensive though.

Personal Motivation

I'm trying to write a collision detection algorithm to help with a robot arm path planner.

Best Answer

Adding a "margin" around a polyhedron is computing the offset polyhedron, which is already a difficult problem in 2D; e.g., the CGAL manual, Chapter 23. Here is a paper on offsets in 3D:

Charlie Wang, Dinesh Manocha "GPU-based Offset Surface Computation Using Point Samples," ACM Solid and Physical Modeling, 2012. (Author web page.)
Fig7
Offsets of filigree model (3rd): positive (1st, 2nd), negative (4th).

But there has been considerable work on collision detection between polyhedra, as this is a key computation for the graphics community. For example, here is a snapshot from a video showing a computation of two colliding knots, each composed of 37,000 triangles:
   Colliding Knots Video: Interactive Continuous Collision Detection for Non-Convex Polyhedra
Their paper is here:

Zhang, Xinyu, Minkyoung Lee, and Young J. Kim. "Interactive continuous collision detection for non-convex polyhedra." The Visual Computer 22.9-11 (2006): 749-760. (Springer link).

Here is an analogous 2008 paper by Jiménez and Segura:

"Collision detection between complex polyhedra." Computers & Graphics. Volume 32, Issue 4, August 2008, Pages 402–411. (Elsevier link).

If you want to concentrate specifically on polyhedron-polyhedron intersection detection, this problem has been studied since the classic 1980's paper by Dobkin and Kirpatrick (which is mentioned in Chapter 7 of my book):

"Fast detection of polyhedral intersection." 1983. (Elsevier link)

For example, this paper shows that the quadratic feature-vs-feature naive algorithm (which you mention) can actually be made linear in practice:

Ming C. Lin , Dinesh Manocha , Madhav K. Ponamgi. "Fast Algorithms for Penetration and Contact Determination Between Non-Convex Polyhedral Models." IEEE Int. Conf. on Robotics and Automation. 1994. (CiteSeer link).

In summary, I wouldn't plunge in and write collision-detection code without first exploring some of this literature, and investigating some of the existing software libraries, such as SWIFT at UNC.

Related Question