Subject: TECH: Collision Prediction, take 2

From: [email-masked] (Lance Norskog)
Date: Sun, 8 Mar 92 12:29:25 PST

More from comp.graphics:
} From: [email-masked] (Eyal Lebedinsky)
} Subject: Solution: shortest distance between two segment-paths.
} 
} [...]
} 
} The problem:
} 
} Given a line segment and a point(p) find the point(n) on the segment
} nearest the point(p). [ ... ]
} 
} By now I realized that my REAL need is to find the shortest distance
} between two line segments, not a line and a point. And moreover, as the
} lines represent the path of two points moving in a fixed rate in a
} straight line then I am only interested in the distance between two
} RELATED points on these paths. Strangely this problem was easier to
} see. Here is how I do it now:
} 
} Given a point a(x,y,z) and a segment from it va(x,y,z), a point b(x,y,z)
} and a segment from it vb(x,y,z) we observe that the parametric line
} segments are
}     (ax+d*vax,ay+d*vay,az+d*vaz) and (bx+d*vbx,by+d*vby,bz+d*vbz)
} Where d is between 0 and 1, and it is the SAME d for related points on
} the two line segments.
} 
} The distance (squared) is: 
}     (ax+d*vax-bx+d*vbx)^2 + (ay+d*vay-by+d*vby)^2 + (az+d*vaz-bz+d*vbz)^2
} 
} which expands to:
} 
}     d^2*((vax-vbx)^2 + (vay-vby)^2 + (vaz-vbz)^2) +
}     2*d*((ax-bx)*(vax-vbx) + (ay-by)*(vay-vby) + (az-bz)*(vaz-vbz)) +
}     (ax-bx)^2 + (ay-by)^2 + (az-bz)^2
} 
} The minimum is when the derivative is zero:
} 
}     2*d*((vax-vbx)^2 + (vay-vby)^2 + (vaz-vbz)^2) +
}     2*((ax-bx)*(vax-vbx) + (ay-by)*(vay-vby) + (az-bz)*(vaz-vbz)) == 0
} 
} Which is a straight forward calculation.
} 
} d = ((ax-bx)*(vax-vbx) + (ay-by)*(vay-vby) + (az-bz)*(vaz-vbz)) /
}     ((vax-vbx)^2 + (vay-vby)^2 + (vaz-vbz)^2)
} 
} However, this need not be calculated always. if the first term is
} negative then the nearest distance is between the starting points. If
} the first term is larger than the second then the end points are
} closest. Otherwise we need to calculate 'd' and subtitute into the
} parametric line squations.
} 
} In practice there are many common terms, so the math goes like this:
} 
} x  = bx-ax
} y  = by-ay
} z  = bz-az
} dx = vbx-vax
} dy = vby-vay
} dz = vbz-vaz
} 
} s = x*dx+y*dy+z*dz;
} if (s > 0) {
} 	t = dx*dx+dy*dy+dz*dz;
} 	if (s >= t) {
} 		x += dx;
} 		y += dy;
} 		z += dz;
} 	} else {
} 		x += dx*s/t;
} 		y += dy*s/t;
} 		z += dz*s/t;
} 	}
} }
} 
} neartest distance = x*x+y*y+z*z;
} 
} If all I want is to know when the two paths are closest then I can
} ignore the case (s >= t) because the end points will be the start
} points of the next time I do the test (next time interval). I may
} choose to ignore the case when (s < 0) as the objects are getting away
} from each other but for (s == 0) I have a real minimum.
} 

He didn't mention it before, but he appears to be working on 
collision detection also.

Lance Norskog
[email-masked]