--------------------------------------------------------------------------- "Ron Levine" Subject: Re: [Algorithms] Collisions of moving objects 11/14/2000 02:20 PM For convex polyhedra moving with uniform rectilinear motion (i.e. constant velocity, no spin), determining whether or not collision occurs and its exact time in case collision does occur is really no more difficult than determining whether or not two stationary convex polyhedra intersect. The idea uses the separating axis theorem. Recall that this theorem gives you a finite set of axes such that if the projections of the two bodies onto on every axis of the set intersect, then you know that the two bodies intersect in space. In other words, if the two bodies are separated in space, then their two projections onto at least one of the separating axes are separated. The algorithm goes like this. You work with the relative velocity vector of the two convex bodies. Projecting each of the two bodies and the relative velocity vector onto a particular separating axis at t0 gives two 1-D intervals and a 1-D velocity, such that it is easy to tell whether the two intervals intersect, and if not, whether they are moving apart or moving together. If they are separated and moving apart on any of the separating axes (or, in fact, on any axis whatever), then you know that there is no future collision. If on any separating axis the two projected intervals intersect at t0 or are separated and are moving together, then it is easy to compute (by two simple 1D linear expressions) the earliest future time at which the two intervals will first intersect and (assuming continuing rectilinear motion) the latest future time at which the two intervals will last intersect and begin moving apart. (If they are intersecting at t0 then the earliest future intersection time is t0). Do this for at most all the separating axes. If the maximum over all the axes of the earliest future intersection time is less than the minimum over all the axes of the latest future intersection time then that maximum earliest future intersection time is the exact time of first collision of the two 3D polyhedra, otherwise there is no collision in the future. The algorithm has the possibility of early outs as you loop over the separating axes, for if ever the maximum earliest future intersection time for the axes tested so far is greater than the minimum latest future intersection time for the axes tested so far, then you know there is no future collision and are done. --------------------------------------------------------------------------- Ron Levine Subject: Re: [Algorithms] collision detection and movement 05/04/2002 01:06 PM Continuing my previous post, here is the elegant solution for finding the exact time of collision of two axis-aligned boxes in uniform linear 3D motion. Actually the method also works for non-axis-aligned boxes (OBBs) and even for arbitrary convex polyhedra, when you combine it with the method of separatig axes. But not to assume you know the method of separating axes, and to keep the elucidation of the idea simple, I'll describe the restricted version that applies to the case of axis-aligned boxes. Suppose your two boxes are given at time t = 0 by ([x1min, x1max], [y1min, y1max], [z1min,z1max]) and ([x2min, x2max], [y2min, y2max], [z2min,z2max]) and suppose that V1 and V2 are their respective 3D velocity vectors, Let W = V2 - V1 be their relative velocity vector. The overview of the algorithm goes like this: We treat the three axes (x,y,z) in turn. At any time, the projection of each box onto an axis is an interval of constant length that is moving uniformly in time along the axis, and the relative speed of the two projection intervals is the projection of W onto that axis, thus Wx for the x-axis, etc. Note that the two projection intervals on one axis can overlap without the boxes intersecting in 3D space. In fact, the boxes intersect in 3D space only when the projection intervals overlap SIMULTANEOUSLY on all three axes. From this consideration, the validity of the following algorithm should be clear: For each axis, find the earliest future time (including possibly the present) t >= 0 such that the two moving projection intervals overlap and find the latest future time at which they overlap, assuming continued constant relative speed. (see below) If on any axis there is no future time at which the projection intervals overlap, then there is no future collision. Now consider the maximum over all three axes of the earliest future overlap time and the minimum over all three axes of the latest future overlap time. If the maximum earliest future overlap time is greater than the minimum latest future overlap time, then there is no collision in the future. If the maximum earliest future overlap time is less than or equal to the minimum latest future overlap time, then that maximum earliest future overlap time is the exact time of first collision. Now, let's look in a little more detail at the determination of earliest future overlap time and latest future overlap time on the x-axis. First suppose that Wx > 0 If x1max < x2min, then the projection of box 2 lies to the right of the projection of box2 and is moving further to the right, so there is no future overlap time and so no future collision of the 3D boxes. If x1min <= x2min <= x1max or x2min < x1min <= x2max then the boxes are overlapping at t=0 so the earliest future (or present) overlap time is 0. But box 2 is still moving to the right (with respect to box1) and the projection intervals come apart at time (x1max -- x2min)/Wx, so that is the latest future overlap time. If x2max < x1min, then the earliest future overlap time is (x1min - x2max)/Wx and the latest future overlap time is again (x1max - x2min)/Wx Now suppose that Wx < 0. Then you use exactly the same procedure, but with the roles of box1 and box2 reversed, to get the earliest and latest overlap times. If Wx = 0, then we see a divide by zero problem. In this case there is no relative motion on the x-axis so it comes down to whether the two intervals [x1min, x1max] and [x2min, x2max] overlap. If yes then both the earilest and latest future overlap times are 0. If no, then there is no future intersection of the 3D boxes. QED. For OBBs, according to the separating axis theorem, there are 15 axes to check instead of three, and the per axis computation is pretty much the same except that you have to use some dot products to get the projections. As a practical matter, you get accurate enough results for game situations by checking only six of the 15 axes that you need for an exact result. And similarly, it extends to arbitrary convex polyhedra, with the number of axes to be checked growing with the number of faces and edges of the polyhedra. Note that this algorithm has frequent early outs in the case of non-collision, so if you know something about the distribution of positions and velocities of your colliding bodies, you can speed it up by appropriately ordering the separating axes. I discovered this very elegant algorithm for exact collision time and used it with OBBs in a published game about five years ago, but my client at the time would not allow me to publiciZe it (competitive advantage, non-disclosure agreements, etc.) I did describe it tersely in a post to this list a couple of years ago. No one seemed to notice or appreciate it except Dave Eberly. You can find code implementing it on his web site, www.magic-software.com. ---------------------------------------------------------------------------