Collision detection between two general hexahedrons

Question

I have 2 six faced solids. The only guarantee is that they each have 8 vertex3f's (verticies with x,y and z components). Given this, how can I find out if these are colliding?

Answer 1

Suppose one of your hexahedrons H1 has vertices (x_1, y_1, z_1), (x_2, y_2, z_2), .... Find the maximum and minimum in each coordinate: x_min = min(x_1, x_2, ...), x_max = max(x_1, x_2,...), and so on. Do the same for the other hexahedron H2.

If the interval [x_min(H1), x_max(H1)] and the interval [x_min(H2), x_max(H2)] do not intersect (that is, either x_max(H1) < x_min(H2) or x_max(H2) < x_min(H1)), then the hexahedrons cannot possibly collide. Repeat this for the y and z coordinates. Qualitatively, this is like looking at the shadow of each hexahedron on the x-axis. If they don't overlap, the polyhedrons can't collide.

If any of the intervals do overlap, you'll have to move on to more precise collision detection. This will be a lot trickier. The obvious brute force method is to check if any of the edges of one intersects any of the faces of the other, but I imagine you can do a lot better than that.

The brute force way to check if an edge intersects a face... First you'd find the intersection of the line defined by the edge with the plane defined by the face (see wikipedia, for example). Then you have to check if that point is actually on the edge and the face. The edge is easy - just see if the coordinates are between the coordinates of the two vertices defining the edge. The face is trickier, especially with no guarantees about it being convex. In the general case, you'll have to just see which side of the half-planes defined by each edge it's on. If it's on the inside half-plane for all of them, it's inside the face. I unfortunately don't have time to type that all up now, but I bet googling could aid you some there. But of course, this is all brute force, and there may be a better way. (And dmckee points out a special case that this doesn't handle)

Answer 2

I'm hesitant to answer after you deleted your last question while I was trying to answer it and made me lose my post. Please don't do that again. Anyway:

Not necessarily optimal, but obviously correct, based on constructive solid geometry:

1. Represent the two solids each as an intersection of 6 half-spaces. Note that this depends on convexity but nothing else, and extends to solids with more sides. My preferred representation for halfspaces is to choose a point on each surface (for example, a vertex) and the outward-pointing unit normal vector to that surface.
2. Intersect the two solids by treating all 12 half-spaces as the defining half-spaces for a new solid. (This step is purely conceptual and might not involve any actual code.)
3. Compute the surface/edge representation of the new solid and check that it's non-empty. One approach to doing this is to initially populate your surface/edge representation with one surface for each of the 12 half-spaces with edges outside the bounds of the 2 solids, then intersect its edges with each of the remaining 11 half-spaces.

It sounds like a bit of work, but there's nothing complicated. Only dot products, cross products (to get the initial representation), and projections.

Answer 3

It seems I'm too dumb to quit.

Consider this. If any edge of solid 1 intersects any face of solid 2, you have a collision. That's not quite comprehensive because there are case when one is is fully contained in the other, which you can test by determining if the center of either is contained in the other.

---

Checking edge face intersection works like this.

1. Define the edge as vector starting from one vertex running to the other. Take note of the length, L, of the edge.
2. Define the plane segments by a vertex, a normal, an in-plane basis, and the positions of the remaining vertices in that basis.
3. Find the intersection of the line and the plane. In the usual formulation you will be able to get both the length along the line, and the in-plane coordinates of the intersection in the basis that you have chosen.
4. The intersection must line as length [0,L], and must lie inside the figure in the plane. That last part is a little harder, but has a well known general solution.

This will work. For eloquence, I rather prefer R..'s solution. If you need speed...well, you'll just have to try them and see.