1

To take a simple example, say there is 2 bounding boxes (not necessarily axis aligned), each defined by 6 planes.

Is there a good way to determine if the volumes defined by each set of planes overlap? (Only true/false, no need for the intersecting volume).

A solution to this problem, if its general should be able to scale up to many sets of planes too.

So far the solutions I've come up with basically rely on converting each set of planes into geometry - (vertices & polygons), then performing the intersection as you would if you have to intersect any 2 regular meshes. However I was wondering if there was a more elegant method that doesn't rely on this.

ideasman42
  • 42,413
  • 44
  • 197
  • 320

3 Answers3

1

The intersection volume (if any) is the set of all points on the right side of all planes (combined, from both volumes). So, if you can select 3 planes whose intersection is on the right side of all the remaining planes, then the two volumes have an intersection.

This is a linear programming problem. In your case, you only need to find if there is a feasible solution or not; there are standard techniques for doing this.

Community
  • 1
  • 1
comingstorm
  • 25,557
  • 3
  • 43
  • 67
0

You can determine the vertices of one of your bodies by mutually intersecting all possible triples that its planes form, and then check whether each of the resulting vertices lies on the good side of the planes defining the second body. When each of the second body's planes is given as base vertex p and normal v, this involves checking whether (x-p).v>=0 .

Assume that your planes are each given as base vertices (p,q,r) and normals (u,v,w) respectively, where the normals form the columns of a matrix M, the intersection is x = inv(M).(p.u, q.v, r.w).

Depending on how regular your two bodies are (e.g. parallelepipeds), many of the dot products and matrix inverses can be precomputed and reused. Perhaps you can share some of your prerequisites.

d01phi
  • 1
  • 2
  • This is close but wont work in the cases where there are intersecting edges (where the vertices on each end don't necessarily intersect the other volume). A similar operation as with vertices could be performed on edges (collect pairs of vertices from the same 2 planes - logical edges), and intersect all of these with the other volumes planes). At this point however - its nearly the same as calculating entire geometry for both volumes. An alternative would be to keep clipping one volume - by the other - check if all verts are clipped from that volume. – ideasman42 Jan 21 '16 at 20:10
0

Posting this answer since this is one possible solution (just from thinking about the problem).

  • first calculate a point on each plane set (using 3 planes), and simply check if either of these points is inside the other plane-set.
    This covers cases where one volume is completely inside another, but won't work for partially overlapping volumes of course.

The following method can check for partial intersections.

  • for one of the sets, calculate the ray defined by each plane-plane pair.
  • clip the each of these rays by the other planes in the set, (storing a minimum and maximum value per ray).
  • discard any rays that have a minimum value greater then their maximum.
    The resulting rays represent all 'edges' for the volume.

So far all these calculations have been done on a single set of planes, so this information can be calculated once and stored for re-use.

Now continue clipping the rays but this time use the other set of planes, (again, discarding rays with a min greater then the maximum).

If there are one or more rays remaining, then there is an intersection.

Note 0): This isn't going to be efficient for any number of planes, (too many On^2 checks going on). In that case converting to polygons and then using more typical geometry tree structures makes more sense.

Note 1): Discarding rays can be done as the plane-pairs are iterated over to avoid first having to store all possible edges, only to discard many.

Note 2): Before clipping all rays with the second set of planes, a quick check could be made by doing a point-inside test between the plane-sets (the point can be calculated using a ray and its min/max). This will work if one shape is inside another, however clipping the rays is still needed for a final result.

Community
  • 1
  • 1
ideasman42
  • 42,413
  • 44
  • 197
  • 320