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:
- 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.)
- 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:
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:
Video: Interactive Continuous Collision Detection for Non-Convex Polyhedra
Their paper is here:
Here is an analogous 2008 paper by Jiménez and Segura:
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):
For example, this paper shows that the quadratic feature-vs-feature naive algorithm (which you mention) can actually be made linear in practice:
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.