Advertisement Jump to content
Sign in to follow this  

closest points on two line segments (3D)

This topic is 4990 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I need to find the point on a line segment that is closest to another line segment. Need this for collision detection. Anyone want to share some code? =)

Share this post

Link to post
Share on other sites
I just used this the other week:

// 4.1.2 Distance between 2 lines

// Find closest point on both lines
// from S1 to S2 going in directions V1 and V2
CVector S1 ,S2, V1, V2;

Initilize the variables above...
and make sure V1 and V2 are normalized

CVector P1, P2;
float t1 = 0.0f, t2 = 0.0f;

float V1dotV2 = V1.dotProduct(V2);

float denom = V1dotV2 * V1dotV2 - 1.0f;

if( fabs(denom) < .0001f ){
//Lines are parallel
float c = 1.0f / denom;
float dot1 = (S2-S1).dotProduct(V1);
float dot2 = (S2-S1).dotProduct(V2);
t1 = c * (-1.0f * dot1 + V1dotV2 * dot2);
t2 = c * (-V1dotV2 * dot1 + 1.0f * dot2);


P1 = S1 + t1 * V1;
P2 = S2 + t2 * V2;

Share this post

Link to post
Share on other sites
One way to solve the problem of finding the closest pair of points on two linear components is by minimizing the quadratic squared distance function. If the linear components are L0(s) = O0+sD0 and L1(t) = O1+tD1, then the squared distance function is f(s, t) = (L0(s)-L1(t)).(L0(s)-L1(t)).

Multiply through and re-arrange and you get a quadratic in s and t. If the linear components are not parallel, the graph is a parabaloid. It is always 'concave up', and the minimum is always >= 0. At the minimum point, the partial derivatives in s and t are both 0. You can set this up as two equations in two unknowns and solve for s and t.

If the linear components are parallel, there is an infinite number of st pairs that satisfy the minimization; they form a line on the st plane running beneath the graph, which is now a parabolic cylinder. In this case you can pick any value for one of the parametric values and solve for the other.

Working with rays or segments adds the complication that the minimization is constrained to a domain. The mathematical details require some thought, although in the end it still comes out to just a few lines of code per case.

I know of two references on this subject. One can be found here at Dave Eberly's site. The other is Graham's article in GPG2. IIRC Graham deals with the constraint aspect as a geometric rather than a calculus problem, so if the calculus of the edge cases is daunting that's an option to consider.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!