Hi, sorry for posting what I believe is a common problem to come up (and yet my google-fu failed to return anything...). I've been reading real-time collision detection by christer ericson, and I was reading about cramers rule, and how it can be used to find the intersection of two rays, but I don't understand how it applies. In truth I don't even know how to check for the intersection of two rays. I know a few ways to tell if rays don't intersect, but no actual way of checking the collision...especially with cramers rule. Given two rays r(t) = p0 + t pd (pd = p1 - p0) u(s) = q0 + s qd (qd = q1 - q0) Each ray has a variable for time, but not a common variable. I don't see how cramers rule applies here.

Everything in the equations except 's' and 't' are constants. Those are your two variables. What you want to do now is break down the vectors into their individual components and write out those equations for X and Y. As long as the rays are 2D you will get two equations to go along with those two variables. If Z is involved, then Cramer's Rule doesn't apply, at least not directly. You would first have to try and eliminate one of the three resulting equations through linear combination (you eliminate an equation by arriving at an equivalence or "truth", like 0 = 0 or s = s). Another way of saying this, is to eliminate any linearly dependent equations. Once you've eliminated such an equation, you are left with two and can use Cramer's Rule. If you can't eliminate any equations, then there is no intersection. It's fairly unlikely that two 3D rays intersect in the general case anyway, so I wouldn't be surprised if you can't eliminate any of the equations.

The problem I have at this point is that each equation only makes reference to either s or t, neither has two unknowns. Are the equations met to be set equal to each other (since they will intersect at some point where R(t) = U(s) )?

If you re-write them like this:

r(t).X = p0.X + t(p1.X - p0.X)
r(t).Y = p0.Y + t(p1.Y - p0.Y)
u(s).X = q0.X + s(q1.X - q0.X)
u(s).Y = q0.Y + s(q1.Y - q0.Y)

Then set r(t).X = u(s).X and r(t).Y = u(s).Y:

p0.X + t(p1.X - p0.X) = q0.X + s(q1.X - q0.X)
p0.Y + t(p1.Y - p0.Y) = q0.Y + s(q1.Y - q0.Y)

You have two equations with two unknowns each. Unless perhaps I misunderstood your first post? It wouldn't be the first time :)

Thanks Zipster, I went away and looked at it, then did some stuff with Barycentric coordinates, and for some reason that helped me understand.

However, now I have another related problem. Based on this, I will need to express points in 3D space in terms of the 2D plane they exist on, yes?

How would I project the four end points in 3D onto a 2d plane in order to use Cramers Rule to check for intersection?

As Zipster said, you first rewrite the equations for the rays (actually lines) in terms of X and Y.

The ray is basically defined by the part of the line when the parameter (t or s) is greater than or equal to 0 (assuming p0 and q0 are the starting points of the rays). Unless the lines are perfectly parallel, they will intersect at some point. This is the point at which the X and Y values of both lines correspond with one another. So we rewrite them as equalities:

p0.x + t * pd.x = q0.x + s * qd.x
p0.y + t * pd.y = q0.y + s * qd.y

We can now algebraically isolate t and s:

t = (qd.x*(q0.y - p0.y) + qd.y*(p0.x - q0.x)) / (pd.y*qd.x - pd.x*qd.y)
s = (pd.x*(q0.y - p0.y) + pd.y*(p0.x - q0.x)) / (pd.y*qd.x - pd.x*qd.y)

Since both have the same divisor, we can make this a little easier on the computer by calculating it first:

div = pd.y*qd.x - pd.x*qd.y

(If div = 0, you can stop here: the lines/rays are perfectly parallel and they will never intersect.)

Now:

t = (qd.x*(q0.y - p0.y) + qd.y*(p0.x - q0.x)) / div
s = (pd.x*(q0.y - p0.y) + pd.y*(p0.x - q0.x)) / div

t is the point on the first line at which the intersection occurs, and s is the point of intersection on the second line.

We must determine if the intersection occurs in the rays. If t >= 0 and s >= 0, then the rays intersect. If one or both are < 0, the rays do not intersect, and the intersection occurs at some point before the start of the ray (on the line that the ray defines).

If t and s meet the proper conditions, you can now plug t or s into one of the original equations to find the exact point of intersection, which you also might need for your program.

Study all of that, make sure it makes sense, and you'll be good to go. :)

Quote:Original post by Winegums
Thanks Zipster, I went away and looked at it, then did some stuff with Barycentric coordinates, and for some reason that helped me understand.

However, now I have another related problem. Based on this, I will need to express points in 3D space in terms of the 2D plane they exist on, yes?

How would I project the four end points in 3D onto a 2d plane in order to use Cramers Rule to check for intersection?

As Zipster mentioned earlier, linear components in 3-d will rarely be found to intersect (especially when a limited precision floating-point representation is used). May I ask what you need 3-d ray intersections for?

The typical solution to the 'line intersection' problem in 3-d is to compute the closest pair of points between the two lines or linear components, and then see if the distance between the two points is below some threshold. The details of this algorithm can be found online - you might try Googling for 'closest points two lines' and see what you come up with.

Although you could compute (or approximate) the intersection by projecting onto a plane and then using the 2-d version of the algorithm, I wouldn't recommend doing it this way (unless you have a good reason for doing so).

^ I was under the impression that Winegums wanted this on a two dimensional plane, not in 3D space. The method I posted only works in two dimensions. If Z is involved, then you'd want to do something more like the above post...

Thanks very much for the replies guys, jyk I'll look into what you suggested.

This isn't really "for" anything other than the joy of knowing how to do things. I've been working a lot with intersection algorithms recently and wanted to know how to check if two rays intersected, even if it is a very unlikley scenario.

If you need quick examples for the 2D intersection versions:
C++
C#
free to use. circle, ray, line, line-segment combinations