I''m trying to find the most optimal way to find the points on a 3D line that are within "radius" units of another point. Here''s the thing: I already know the minimum distance from the point to the line. Thus I know that if that distance is greater than radius then there are zero points on the line; if the distance is equal to the radius then there is one point on the line; otherwise there are two. I need to find the point/points. I don''t know how. I also don''t know the best way to find the nearest point on a line. If I did then I could use the Pyathagorean Theorem to find out the distance away from that point that the final points are, and I''d be done. I''m not sure if that''s the fastest way to do it, however. If the above method is the one I have to use, then whats the most optimal way to get the nearest point on a line, if I already have the mindistance? ~CGameProgrammer( );

So your vector equation for the line is
(x,y,z) = (a,b,c)*t + (x₀,y₀,z₀)

and the point is given by (X,Y,Z). The vector from (X,Y,Z) to the nearest point on the line will be perpendicular to the vector (a,b,c).

I think you can just write the dot product

(X - a*t - x₀, Y - b*t - y₀, Z - c*t - z₀) . (a, b, c) = 0

and then solve for t?

Interesting suggestion. I solved the equation and got:

T = Line.Direction * (Point - Line.Endpoint) / (Line.Direction dot Line.Direction)

Because Line.Direction is normalized in my case, that simplifies to:

T = Line.Direction * (Point - Line.Endpoint)

And that is incorrect. A simple illustration makes it obvious.

However when I drew the picture I realized what an idiot I am. (I tend to forget my degree of idiocy sometimes.) It really is a simple right triangle problem. The length of the hypotenuse is the distance from Point to Line.Endpoint. The length of one of the other sides is the minimum distance that I already have. Therefore I solve for the remaining side:

C^2 = A^2 + B^2
C^2 - A^2 = B^2
B = sqrt(C^2 - A^2)

C is Length(Point - Line.Endpoint), A is MinDistance, B is "T". I can't believe this didn't occur to me before. Well hopefully this will work.

~CGameProgrammer( );

EDIT: In case you're curious, here is the steps I took in solving the equation:

(P.X - L.A*L.T - L.X, P.Y - L.B*L.T - L.Y, P.Z - L.C*L.T - L.Z) dot (L.A, L.B, L.C) = 0

(L.A * (P.X - L.A*L.T - L.X)) + (L.B * (P.Y - L.B*L.T - L.Y)) + (L.C * (P.Z - L.C*L.T - L.Z)) = 0

(L.A * P.X) - (L.A * L.A * L.T) - (L.A * L.X) +
(L.B * P.Y) - (L.B * L.B * L.T) - (L.B * L.Y) +
(L.C * P.Z) - (L.C * L.C * L.T) - (L.C * L.Z) = 0

(L.A * P.X) - (L.A * L.X) +
(L.B * P.Y) - (L.B * L.Y) +
(L.C * P.Z) - (L.C * L.Z) = (L.A * L.A * L.T) +
(L.B * L.B * L.T) +
(L.C * L.C * L.T)

(L.A * P.X) - (L.A * L.X) +
(L.B * P.Y) - (L.B * L.Y) +
(L.C * P.Z) - (L.C * L.Z) = L.T * ((L.A * L.A) + (L.B * L.B) + (L.C * L.C))

L.A * (P.X - L.X) +
L.B * (P.Y - L.Y) +
L.C * (P.Z - L.Z) = L.T * ((L.A * L.A) + (L.B * L.B) + (L.C * L.C))


[edited by - CGameProgrammer on October 31, 2002 11:36:33 PM]

I''m pretty sure t=((x,y,z)-(x0,y0,z0)).(a,b,c) since (a,b,c) is a unit vector. The magnitude of the cross product of those two vectors would be the distance of the point from the line.

quote:

---

Original post by LilBudyWizer
I'm pretty sure t=((x,y,z)-(x0,y0,z0)).(a,b,c) since (a,b,c) is a unit vector. The magnitude of the cross product of those two vectors would be the distance of the point from the line.

---

(Line.Position - Point) dot Line.Direction is the equation for the distance from a point to a line. If you had read my post you would see that I already knew that! That's not what I'm trying to find.

~CGameProgrammer( );

EDIT: I shouldn't say "trying" since the equations I derived do seem to work. Unfortunately the collision algorithm itself is not working perfectly correctly yet. It's amazing how tricky it is writing sphere-triangle collision detection/handling that works correctly in all cases.

[edited by - CGameProgrammer on November 1, 2002 10:50:39 PM]

quote:

---

I also don''t know the best way to find the nearest point on a line. If I did then I could use the Pyathagorean Theorem to find out the distance away from that point that the final points are, and I''d be done.

---

That was my suggestion To find that point, you can still use the Pythagorean Theorum. You know the distance between the point and the 3D line, and you can calculate the distance between the point and a point you know to be on the 3D line somewhere else. You use the PT to find the distance from that point on the 3D line to the nearest point. Use the direction of the line to scale the distance and add to point.

Read my second post, Zipster. I did that already. It worked. So problem solved, in other words

~CGameProgrammer( );

Ah. I usually jump to the last post in a topic to see if something has been solved, and since the last line of your third post - the one after the second - was in the present tense ("That's not what I'm trying to find."), I assumed that a solution hadn't been found

It's a bit more complicated than looking for present tence and stuff, but the system works... usually

[edited by - Zipster on November 1, 2002 11:50:30 PM]

Oh, and I was wrong about the distance equation. It''s (Point - Line.Endpoint) cross Line.Direction. Cross product, not dot product.

It seems to work! Yay! The problem with the collision was apparently due to the incorrect distance formula, and also to this limitation of the Pythagorean formula used for getting the points - you can''t tell which direction to place them. In other words, because the algorithm deals with magnitudes of sides, you don''t know whether you want to place the nearest point to the left or right of Line.Endpoint, and you don''t know if you want to place the intersection point to the left or right of the nearest point.

I''ve hacked a solution by moving Line.Endpoint 1000 units away in the negative Line.Direction direction, to ensure everything is on the positive side.

~CGameProgrammer( );

The dot product gives you one side of the right triangle and the magnitude of the cross product gives you the other, i.e. cosine and sine. You know distance and you know direction. So the nearest point is np=((p-p0).d)*d+p0. A vector from the point to the nearest point on the line is np-p. The points of intersection are np+/-sqrt(r^2-|np-p|^2))*d. If that square root is complex there is no interesection, if it is zero there is one point of intersection and otherwise there are two.

Hehe, I just can't resist. If you had of read my post...

[edited by - LilBudyWizer on November 2, 2002 11:52:05 AM]