i have an origin and target, that i can use to cast a ray. Then i have 2 points which we can use to draw a line segment. With these information can you show me how i can do a ray to line intersection test that would return true/false. Thanks.

Find the intersection point of the two full lines, and then determine whether that is on the ray and the segment (i.e. that its distance on the ray is >0 and its distance on the segment is 0>x>length of line).

I asked this question a while ago...

clicky

Quote:Original post by Bob Janova
Find the intersection point of the two full lines, and then determine whether that is on the ray and the segment (i.e. that its distance on the ray is >0 and its distance on the segment is 0>x>length of line).

I was hoping for a more detailed explanation. Or perhaps I would appreciate if there's some code posted.

Quote:I asked this question a while ago...

Actually I stumbled into this one before posting this post. In fact i tried to use the code from http://pastebin.com/f22ec3cf1.

I'm not successful. Also you're using 2 rays, i have 1 ray and a line segment and the equations there are confusing.

My variables are:

1. 2 vector points that specifies a line segment
2. 1 origin and 1 direction that specifies a ray

From these variables how do i check for ray-line intersection?

Thanks.

Actually in that source code that function takes 4 points. The two points of the line segment then two points of the ray. The origin then the origin + direction. I have a new version of that source if you want it.

This code is actually just the line to line intersection test with constraints on r and s. If you look up line to line intersection you'll find the directions for deriving the equations. It's been a while since I've written the code, so I forgot the details.

Here's one using vectors if you find that easier to deal with:



I just typed that out now so it probably doesn't work (chances are I got a sign wrong way round), but hopefully it shows you the right logic. I have some Delphi code to do a 3D line-line intersection somewhere which actually does work, but it's not on this computer.

Quote:Original post by Sirisian
Actually in that source code that function takes 4 points. The two points of the line segment then two points of the ray. The origin then the origin + direction. I have a new version of that source if you want it.

My problem earlier was the function parameters wasn't meaningful enough that I would know that the parameter "x1_" would be the ray origin and that the "y1_" would be the direction, so debugging or knowing if the function works for me is a little bit hard, as I try to mix and match my variables with the parameters with no success.

Would you give the parameters are more meaningful names please?

Quote:(chances are I got a sign wrong way round)

Could it be this is the only issue?

Well I specifically said to ask if you wanted the new version.

C++ Intersection Functions
(My vector2 implementation is ad hoc so you'll need to find your own).

So for ray to line segment it expects the origin then origin+direction then the two points of the line segment.

This should be fairly easy. Consider the line segment as an infinite line. If the ray never intersects the infinite line, then the ray never hits. If it does hit, we can find the point on the infinite line that it does. This comparable to the 3D case of a plane and ray, which is a well documented problem. Once we have the point on the infinite line, we can use the equation of a line segment to determine whether it is in fact inside the line segment.

A line segment is defined in terms of 2 points and a scalar t.
L(t) = P1 + (P2-P1)*t

P1,P2 are points of the line segment. Here are the basic properties.
L(0.0) = P1
L(1.0) = P2

Thus, 0.0 <= t <= 1.0 for the point of intersection to be on the line segment. If t is not in this range, it hits the infinite line segment. If we know a point lies on the infinite line, but aren't sure if it is on the segment, we can solve for the value of t and determine if it is within [0.0,1.0]. We'll do this by setting the line segment equation to the intersection point. Let's call this point X. Remember, we want to find t. Also remember that X, P1, P2 are vectors.

1) X = L(t)2) X = P1 + (P2-P1)*t3) X - P1 = (P2-P1)*t4) (X - P1)/(P2-P1) = t

As with any division, make sure that the denominator is not zero! If it is, then the line is perpendicular to that axis. That isn't a bad thing, but you cannot compute the value of t from it -- you'll have to use the other axis.

Now, you could compute the value of t by using:
(X.x - P1.x)/(P2.x - P1.x) = t
(X.y - P1.y)/(P2.y - P1.y) = t

Which value of t do you use? Well, if you assume the point is ON the line, they have to be the same. If they weren't the same, then we'd have an equation that didn't work because we'd get the contradiction that t != t. Therefore, if the point is really ON the line, it is sufficient to calculate t using only the X or Y coordinate.

Finally, we reject the point X if the value of t is not in [0.0,1.0]. OK! So now we can tell whether a point on a line segment is valid. Now we have to find out how to get that point so we can test it.

We know a ray's equation is R(t) = O + D*t, where O is the ray's origin, and D is the ray's direction.

Let's consider a more general equation of an infinite line that doesn't involve t. It's a plane in 2D, and it uses this equation:
Ax + By + C = 0

A,B,C define the line, and x, y are the coordinates of the point on the line. How can we get this equation? Well, a plane is defined by its normal vector N = (A,B) and distance to origin C. Once we have (A,B) and a point (x,y) on the plane, we can solve for C, specifically, C = -(Ax + By)

In order to find this plane, we need a two points (because any two points are collinear). Well, we can just use P1 and P2 from the line segment!
D = P2 - P1.

Now, we have to find the normal, which perpendicular to the line D. Without proof, I'm going to tell you that is simply:
N = (-D.y, D.x)

Notice that the Y and X coordinates swapped positions. Now we've got a normal, so let's solve for C:

C = -(Ax+By)
C = -( [-D.y]*[P1.x] + [D.x]*[P1.y] )
C = D.y*P1.x - D.x*P1.y

Now you've got the plane in form of:
Ax + By + C = 0 and know the values of A,B,C.

To find out whether a ray hits the plane, we substitute the formula of a ray INTO the plane equation. This step isn't always, clear so let's be explicit here.

A ray is defined by the equation R(t) = O + D*t (Not the same D as before!)
That means the x & y coordinates are:
Rx(t) = O.x + D.x*t
Ry(t) = O.y + D.y*t

Let's substitute the x and y coordinates into the plane equation and solve for the ray's parameter t:

1) 0 = A(O.x + D.x*t) + B(O.y + D.y*t) + C2) -C = AO.x + AD.x*t + BO.y + BD.y*t3) -(AO.x + BO.y + C) = AD.x*t + BD.y*t4) -(AO.x + BO.y + C) = t(AD.x + BD.y)5) -(AO.x + BO.y + C)/(AD.x + BD.y) = t

Note: Compute the denominator (AD.x + BD.y) first! If it is zero, then the ray NEVER intersects the plane OR it is ON TOP OF the plane. Whatever you do, don't divide by zero!

Ok, we have the ray's parameter t. Let's find the point of intersection:

X = O + D*t

Now, let's compute the line segment's parameter t0 and determine if it is in [0.0,1.0].

t0 = (X - P1)/(P2-P1).

if(t0 > 1.0 || t0 < 0.0f)
return MISS;

return HIT


I hope that explains everything down to the nitty-gritty details.