Jump to content
  • Advertisement
Sign in to follow this  
glSmurf

closest points on two line segments (3D)

This topic is 4898 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
Advertisement
I just used this the other week:


//////////////////////////////////////////////////////////////////////////
// MATHEMATICS for 3D GAME PROGRAMMING & COMPUTER GRAPHICS (second edition)
// 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
}else{
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 GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!