Intersection of Polyhedra

Question

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.

Answer 1

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.)

_{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:
    _{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.

Answer 2

You cannot add any margin, apply "is a point inside polyhedra" algorithm, and detect polyhedra intersection. This won't work even in 2D: imaging a thin tall rectangle containing (0,0), and a short fat rectangle containing (0,0): they intersect, but their vertices are nowhere near each other.

There are fairly fast and robust algorithms for detecting intersections between 2D polygons. Lookup Sweep Line algorithms; they detect 2D polygon intersections in O(N log (N)) time, where N is the number of vertices.

For 3D generalization google something like "Sweep Plane algorithm". This one sounds like something related to what you are working on:

http://www.sciencedirect.com/science/article/pii/S0010448507001649

Answer 3

I began writing a Fortran function for computing the intersection, union or difference of two polyhedra in 1973. This was after I spent nine months writing the same function for 2d polygons. Often when creating a 3D geometric function it helps to start with the odd version.

Our polygon and polyhedron data structures allow for a set of concave or convex polygons (polyhedra in 3D case) as the geometry. We called them Polygon-sets and Polyhedron-sets. The pieces can represent disjoint pieces or subjoint (holes). Our State map in polygon-set form has the following 2d piecesL Lower peninsula, upper peninsula, Drummond Island, Belle Isle, and more - depending on the problem at hand. We also have counties with hundreds of lakes that need to be treated as holes in many cases.

I finished the first version of polygon-set set operations in 1973 and debugged it for the next few years. In 1late 1973 I began the very difficult task of producing the polyhedron-set version. The objectives I imposed on the functions was 1) allow any range of coordinates are allowed; that is it must allow a small rectangle (say 1"x1") must be able to intersect or unioned with 1"x1" rectangle that is far out in the plane say miles away. ALso the result of calling the set operation functions is a polygon-set (or polyhedra=set). This allows the functions to be called repeatedly:

• PG2SET a, b, c, d, e;
  b = rectangle(0,0, 0,1, 1,1, 1,0,)…
  a = union(b,c);
  d = intersect(a, e);

  PH3SET a, b, c, d, e;
  b = cubeoid(10000000, 10000000, 10000000, …)
  a = union(b, c);
  d = intersect(a, e);

It took me three years to finish the first version of the polyhedron set-operations. I debugged for another 10 years and they became quite stable.

These were and still are not easy problems to solve. I had no exemplars to aim for or any libraries to lean on for the fundamental point, line, polygon functions. There was no C++ so I wrote in Fortran. I STILL HAVE THEM AND AM STILL TWEAKING THEM 40 YEARS LATER. (I get excited when I talk about my old Fortran code so I kick it to all caps) I have C++ versions and hundreds of utility functions and objects definitions that I use in my retirement.

I have much documentation and code that I am willing to share. I have collected several hundred polygon and polyhedron functions wand much more. But wait! You can have these absolutely free of charge.

turner@umich.edu