Archived

This topic is now archived and is closed to further replies.

CGameProgrammer

Point on a line nearest to another line

Recommended Posts

Yet another math-related question from me. I''m making great progress with my collision, the only thing remaining is edges. For this I need to find the point on a line nearest to another line. I already have the formula for the distance between them, if the website was correct then it is this: CrossProduct = LineA.Direction cross LineB.Direction; if( CrossProduct != vector(0,0,0) ) return (LineA.Endpoint - LineB.Endpoint) dot CrossProduct; else // They are parallel return LineA.Distance( LineB.Endpoint ); That last bit calls the function that finds the distance from a line to a point. Anyway now I need to find the point on LineA that is nearest to LineB. If I have this point then I will be set because I can use my line-point equations with it. ~CGameProgrammer( );

Share this post


Link to post
Share on other sites
Well, I have an idea. You know how if you want to project a 3D point into 2D you simply "eliminate" one of the axis? Let''s apply that concept to our lines. In effect, by removing the Z, you are also saying that there exists a point (0,0,Z) (Z being any non-zero number) where the observer is, and he is facing towards (0,0,0), and we are projecting the points/lines to his view. If we apply this same concept to our lines, then we could project them to 2D based on an imaginary observer, find the intersection there, and then translate that point back into 3D for both lines, and that would correspond to the closest points for both lines (at least, if my theory is correct ).

So for our lines, let''s say that they produce cross-product (X,Y,Z). Now let''s say that there''s an observer at that point, and he''s looking towards the origin. We can project the lines into his view, but instead of just hacking the Z, we have to use some projection math. I''m not an expert on that, so you''d have to go looking around.

Tell me if you get anywhere with this I really just thought of it...

Share this post


Link to post
Share on other sites
Well, in the parallel case it is any point. What the first part does is find the distance between two planes. If it is non-zero then the lines are skew, i.e. the lines are in differant planes. As near as I can tell you have to project one line into the plane of the other line and then find the point of intersection. The CrossProduct is a vector normal to both planes so you simply use it to translate one of the end points.

Share this post


Link to post
Share on other sites
A Google search would surely return good results for this.

I think that I have a reasonably good method. Given two lines A and B,

1. The shortest distance between line A and line B is along the vector perpendicular to both of these lines.

N = VectorA X VectorB

2. Make a plane that contains any point on the line B, and whose normal is N X VectorB

3. Intersect this plane with line A. This point should be the closest point to line B

It should work...

Cédric

[edited by - cedricl on November 3, 2002 3:03:32 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by LilBudyWizer
A vector perpendicular to two non-parallel lines in the same plane is orthogonal to the plane they are in.

Yes... If the two lines are in the same plane, then their distance is 0, so they are separated by the vector 0 * N.

To find the distance between two lines, the usual technique is to use the vector perpendicular to both lines

N = Va X Vb

And to project the vector between any point on A, and any point on B onto it.

r = Pb - Pa

d = r . N / |N|

At least, that''s what I remember. So the vector N, perpendicular to both lines, is the direction one should take to get to line B if he was on the point closest to it, on line A. Does that make sense?

Cédric

Share this post


Link to post
Share on other sites
Thanks for the replies... I haven''t tested those suggestions yet but someone told me this should work:

CrossProduct = LineA.Direction cross LineB.Direction;
Length = (((LineB.Position - LineA.Position) cross LineB.Direction) dot CrossProduct) / (CrossProduct dot CrossProduct);
NearestPoint = LineA.Position + (LineA.Direction * Length);

Is that right? I''m working on implementing it, haven''t tested it yet, so I''m just asking here.

~CGameProgrammer( );

Share this post


Link to post
Share on other sites
I haven''t read anything except the title, but what I am to understand is that you want the point on a line closest to another point. So that means you have to measure the distance between 2 points twice.
deltax = x2-x1
deltay = y2-y1
deltax= deltax*deltax;
deltay= deltay*deltay;
dist = sqrt(deltax+deltay);

do this twice, one for the point on one side and another for a point on the other side. Whichever has the least distance wins.

Hope that helps and I haven''t restated something sum1 else said.

Share this post


Link to post
Share on other sites
I can't see why the method you gave would work. Of course, that doesn't necessarily mean it doesn't work.

What I can see working is the following:

Parameterize the two lines A and B as usual x = ta + A and x = tb + B (anything in bold is a vector) where a,b are normalized.

The closest points will be joined by a vector perpendicular to both lines, call this n = a x b .

Define a plane with normal perpendicular to both n and b and passing through the point B . The closest point on line A to line B will then be the intersection between this plane and the line A. Lets call this point r .

r is in the plane defined above so

(r - B ) . (n x b ) = 0

and r is also on the line A so

r = t a + A

for some t.

Substituting the second equation in the first gives

t = ( (B - A ) . (n x b ) ) / (a . (n x b ) )

and then substitute this back to find r . It's then pretty simple to find the corresponding point on line B.

This is probably the same to the method you just put up. But hope it helps anyway.

[edited by - sQuid on November 3, 2002 10:43:42 PM]

Share this post


Link to post
Share on other sites
The projection method finds the shortest distant constrained to be in the plane that is projected into... i.e. it''s not guaranteed to be *the* shortest path, just a path that might be short

"3D Game Engine Design" by David Eberly
The minimum distance occurs when grad(Q) = (0,0)
Q(s, t) = | L0(s) - L1(t) |
where L0 & L1 are the parameteric equations for the lines


struct Line
{
float M[3];
float B[3];
};

float DistanceSquare(Line line1, Line line2, float& s, float& t)
{
diff = line0.B - line1.B;

a = dot( line0.M, line0.M );
b = -dot( line0.M, line1.N );
d = dot( line1.M, line1.M );
d = dot( line0.M, diff );
f = dot( diff, diff );

det = |a*b - b*b|;

//note this is a fuzzy-floating float compare (use an epsilon etc...)
if(det > 0)
{
e = -dot( line1.M, diff );
invdet = 1/det;
//Q(s,t) is the closest pair of points
s = (b*e - c*d) * invdet;
t = (b*d - a*e) * invdet;
//this is the distance squared
return s*(a*s + b*t 2*d) + t*( b*s + c*t + 2*e) + f;
}
else
{//lines are parallel
s = -d/a;
t = 0;
return d*s + f;
}
}

Share this post


Link to post
Share on other sites
The results from the method I posted are either correct or just close, I can''t tell. There''s something strange going on with some part of the collision so I''ll try your method, sQuid.

But is it really necessary to say (a x b) x b? That''s what n x b is. Is there a simpler way to put that?

~CGameProgrammer( );

Share this post


Link to post
Share on other sites
Well sQuid, your method produces identical results as the method I posted. And because both methods involve two cross-products and two dot-products (if you use a variable for n x b and a x b) there appears to be no advantage to using either over the other.

~CGameProgrammer( );

Share this post


Link to post
Share on other sites