Space is what keeps everything from happening at the same place - Ivan Karamazov

3D isn't really so hard. We're quite used to it. We move through it gracefully, as if we were born with all the reasoning we'd ever need to handle it. We can move quickly around, over and under objects without fear. Yet, turn out the lights and the party's over. If we have to think about 3D instead of just seeing it, we stand a very good chance that we'll shortly be crashing into objects.

Programming 3D manipulations is a lot like having the lights turned out on you.

The problem a few of us recently undertook was detecting 3D collisions; that's detecting when two objects are intersecting each other in 3-space, and doing that detection in a virtual world filled with many objects, as quickly as possible. The solution we came up with was good enough for our needs, and may be useful to you, too.

Let's Set the Scene

Our world consists of boxes in a room. Some of the boxes are large, some of the boxes are small, and they can potentially float all over the place. But we have constrained the situation so we know that only one box is moving at a time. We know the dimensions and locations of each box, and the dimensions of the room.

This is not as unrealistic is you might think. If you could put colored bounding boxes around every object in the world you interact with, it might look pretty much the same if you squinted. Granted, everything is moving at once, but the universe has a lot more computing power than we do. Physics is one hell of a computing engine that runs across the universe in real time.

Finding Collisions

So now that our room is full of boxes, and we know that just one is moving, our task of recognizing collisions is pretty simple: Figure out which boxes might be intersecting the moving box, from those figure out if any boxes actually are intersecting the moving box, and finally see if the moving box is intersecting the room. When any of these happen the intersecting objects need to light up and be noticed.

Note that we're assuming the second step is considerably more expensive than the first. This may not be true, but I'm going to work under that supposition.

Step 1. Intersecting Spherical Hulls

The first step needs to be quick - determine if the moving box might be intersecting the moving box. We can do this by intersecting spherical hulls.

Intersecting two spheres is insanely easy. Two balls touch if the sum of their radii is equal to the distance between their centers. if the sum is greater than the distance, we have an intersection.

The radius of a bounding sphere is easy. Since we have pure, symmetrical boxes, it's equal to the 3D distance from a corner to the center. We'll keep this around with the object so we only need to compute it once.

The next step is also pretty easy - walk the list of other boxes in the room, compute the distance between their center and the moving box, and then compare it with the sum of the radii. If the sum is greater than the distance, the boxes are too far apart to worry any further.

Step 2. Intersecting Bounding Boxes

So now the rubber meets the road. How do we tell if box A is intersecting box B?

Despite being something that's intuitively easy, it's really not. How many ways can two boxes intersect. Let's enumerate them. For the purposes of this discussion, our moving box will be A, the other box will be B.

Complete Enclosure

Suppose box A is completely enclosed by boxB. All eight corners of A are inside B. All six sides of A are inside B. Clearly the two intersect.

Wait a moment. Corners and sides. Is there a prefered choice? Lets see what develops.

Without loss of generality, if B is enclosed by A, the two also intersect.

Non Intersection

Thinking about it, it may be easier to tell if two boxes don't intersect than if they do. Let's figure out if A doesn't intersect B.

We can arrange things so that all boxes are oriented in the same way. the top, bottom, left, right, front and back sides are all oriented in the same direction.

So if the top of A is lower than the bottom of B, the boxes don't intersect. Similarly, bottom A is higher than top of B, left of A is more right than right of B, right of A is more left than left of B, front of A is more back than the back of B, and back of A is more front than the front of B. In any of these cases, we have non-intersection. It also covers our enclosure case. And it's just compares... it may be fast enough to obviate the spherical intersection step.

But is this pairwise testing enough? Let's look more closely. We'll codify the natural relations between the two blocks:

either (fb) A.front < B.back or (bf) A.back > B.front
either (rl) A.right < B.left or (lr) A.left > B.right
either (tb) A.top < B.bottom or (bt) A.bottom > B.top

In other words, in a nicely ordered array of blocks, front < back, right < left and top < bottom. This breaks down by boolean logic to eight compositer truth relations.

fb || rl || tb
fb || rl || bt
fb || lr || tb
fb || lr || bt
bf || rl || tb
bf || rl || bt
bf || lr || tb
bf || lr || bt

If all of these relations are true, there is no intersection. Conversely, in order for two blocks to intersect, one of these truth relations must fail. If all are valid, then the blocks do not intersect. Logically, that's

(!fb && !bf) || (!rl && !lr) || (!tb && !bt)

or even

((A.front > B.back) && (A.back < B.front)) ||
((A.right > B.left) && (A.left < B.right)) ||
((A.top > B.bottom) && (A.ottom < B.top))

The Holy Grail

Inspecting this relation you can see that as soon as one of the sub-expressions fail, the entire relation fails, and there is no intersection! This is wonderful! Forget about step 1! Eliminate it completely! Even in the worst case (six compares, three ANDs, two ORs) this is much faster than finding 3D distance (3 multiplies, two adds and a square root and a compare) unless you have access to serious mathematical hardware!

Step 3. Intersecting Enclosures

Here comes the kicker. To check and see if a box is intersecting an enclosure, you just slightly adjust the relationship. Because in the normal case, when a box doesn't intersect a wall of the room, then

both (fbe) A.front < enclosure.front or (bfe) A.back > enclosure.back
both (rle) A.right < enclosure.right or (lre) A.left > enclosure.left
both (tbe) A.top < enclosure.top or (bte) A.bottom > enclosure.bottom

Intesection then happens when

!(fbe && bfe && rle && lre && tbe && bte)

The walls that intersect the object are the ones where the comparison is false.

Interaction Strategy and Denoting Collisions

For our purposes, we had while only one object is moving, collisions between objects must be allowed to happen, show by specially marking colliding objects, either through color, a halo, blinking, or whatever. The important thing is that both objects in the collision need to be marked.

Why? Because to fix the arrangement we may choose to move the other object rather than the one that was moving when the collision happened. If we dissallowed the movement, then the other object would have to be moved first, and that might cascade further and back into our world. We feel in this case it's better to allow the user resolve problems rather than to prevent them from occurring by limiting motion. Other applications may have different requirements.

Take a Look

A Meteor sketch of the algorithm to determine whether or not two boxes intersect can be found at https://gist.github.com/eymiha/771b42c090965a882fe9. In the best case, one compare is enough to tell if there's no collision.

Takeaways

• It's all up in the air when you're solving problems. We got to dismiss a whole line of the solution by optimising a subsequent step.
  
• Playing with the real world, even a very abstracted model of it, can be tremendous fun.
  
• Sometimes you figure out something that surprises you, even when you think you've got it all figured out.