Subject: Collision prediction

From: [email-masked] (Lance Norskog)
Date: Sat, 7 Mar 92 17:26:21 PST

>From comp.graphics, on finding the closest points on two lines:
} 
} You might take a look at the code in the X flight simulation, ACM.  Code in
} fsim/m61a1.c addresses a generalized case of this problem:  It looks for
} the minimum distance between two points moving along two line segments with
} constant velocities.  In your case, one point would be stationary.
} 
} Basically, the algorithm works like this:
} 
} * Pick one of the points as the reference location.
} 
} * Build a parameterized system of equations that expresses the relative
}   location of the second point relative to the first:
} 
} 	s0.x = initial_loc2.x - initial_loc1.x;
} 	s0.y = initial_loc2.y - initial_loc1.y;
} 	s0.z = initial_loc2.z - initial_loc1.z;
} 	v.x = vel2.x - vel1.x;
} 	v.y = vel2.y - vel1.y;
} 	v.z = vel2.z - vel1.z;
} 
}   In your case, the velocities would correspond to the slope of the line.
}   Assuming that location2 is the stationary point, the v vector would be
}   equal to the negative slope of the line.
} 
}   At that point, the position of point2 relative to point1 can be expressed
}   as:
} 
} 	x = v.x * t + s0.x;
} 	y = v.y * t + s0.y;
} 	z = v.z * t + s0.z;
} 
}   The parameter t is time, in my usage.
} 
} * You can then determine the time, t (which is relative to the time at initial
}   locations), corresponding to the point in time where the two points are
}   closest.
} 
} 	t = - (v.x * s0.x + v.y * s0.y + v.z * s0.z) /
} 		(v.x * v.x + v.y * v.y + v.z * v.z);
} 
}   Assuming that location2 was the stationary point, you could then
}   plug t into the line equation to yield the exact closest point.
} 
} The sources to ACM can be ftp'ed from expo.lcs.mit.edu; the filename is
} contrib/acm.2.4.tar.Z.
} 
} Good luck.
} 
} -- 
} Riley Rainey			Internet: [email-masked]
} MIPS Computer Systems		Phone:    +1 214 770-7979
} Dallas, Texas
} 

Here's another take on collision detection: for all possible
object bounding thangs, use the above algorithm to predict whether
and when they will collide.  This is done in preprocessing.  When an object
is deleted from the scene, its collisions are removed from
the list.  When an object is added, its collisions are
calculated and added to the list.  When an object's bounding thang changes,
its existing list of collisions and "near points" are recalculated.
If an object collides, its future collisions are recalculated.
The list still has them for efficiency reasons.

The above only works for constant velocity object motion.  You can add higher
derivative behavior to the motion of objects easily enough, and
it should be in the simulator anyway for efficiency.  I.e. if
something is accelerating you don't speed it up by program control
on each cycle, you just set an acceleration parameter.  The collision
predictor can integrate the higher derivatives into its calculations.
(This last sentence goes far beyond my knowledge of differential equations).

This "collision prediction" technique, though limited, uses temporal 
coherence and pushes the N-body O(NN) stuff into a once-only 
preprocessing phase.  These two are important goals for a collision
detection system.  The technique is also most useful for identifying 
candidates for more in-depth checking.  

I will conclude by pointing out that if you have to sort 5 items, it
doesn't matter how you sort them.  The same is true for collision
detection.

Lance Norskog
[email-masked]