Does anyone know where I can find a copy of the post
'Collisions of moving objects' (post by Ron Levine to gd-algorithms 11/14/2000)
Ron Levine's "collisions of moving objects"
-
Erwin Coumans
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
"From: Ron Levine <ron@do...>
Re: Collisions of moving objects
2000-11-14 13:20
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."
Also check:
http://sourceforge.net/mailarchive/foru ... viewday=14
and
http://www.gamedev.net/community/forums ... _id=298699
Re: Collisions of moving objects
2000-11-14 13:20
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."
Also check:
http://sourceforge.net/mailarchive/foru ... viewday=14
and
http://www.gamedev.net/community/forums ... _id=298699