A ray being a point in space and a direction, how would one go about finding if two rays intersect?

I've searched the internet high and low to no avail.

Any help is greatly appreciated.

Started by Apr 08 2013 01:22 AM

,
7 replies to this topic

Posted 08 April 2013 - 01:22 AM

A ray being a point in space and a direction, how would one go about finding if two rays intersect?

I've searched the internet high and low to no avail.

Any help is greatly appreciated.

Posted 08 April 2013 - 02:48 AM

You can project P1 (point on ray R1) to the plane defined by R0, giving you P1' and P0' (where the rays intersect that plane)

This gets you the distance between P1 and R0.

Multiply the direction of R1 by that of R0.

Multiply result by the previously mentioned distance.

The resulting point should be the intersection of R0 and R1. So simply check if it lies on R0.

EDIT:

I bet this doesnt work at all.

**Edited by Waterlimon, 08 April 2013 - 06:39 AM.**

o3o

Posted 08 April 2013 - 06:05 AM

Rays, being infinitely thin are pretty much never going to intersect one another (at least not reliably what with floating point inaccuracies except in the most trivial cases) unless you have some sort of epsilon/error term.

An epsilon is effectively going to give your two rays some thickness, I think it is equivalent if you give all the 'thickness' to just one ray rather than share it equally between them. A ray with a bit of thickness is effectively a capsule (assuming you can cope with at least one of your rays being bounded - technically a line segment), if you google "ray capsule intersection" there are plenty of useful looking results, e.g. this first one has source code: http://blog.makingartstudios.com/?p=286

PS. This post assumes you're working in 3D, if you're in 2D then please ignore.

**Edited by C0lumbo, 08 April 2013 - 06:08 AM.**

Posted 08 April 2013 - 06:27 AM

PS. This post assumes you're working in 3D, if you're in 2D then please ignore.

I was wondering about this too, since in 2D, this would make even less sense, since every two rays that are not parallel will definately intersect. Maybe he was talking about 2D intersection with length-restricted rays? That would yet make the most sense.

Posted 08 April 2013 - 06:39 AM

Yeah, when you get the intersection of R0 and R1, you can get the dot product of the intersection and the ray to get the distance, and multiply the direction of the ray by that. So you get the point on the ray that is same distance away from the ray as the what-we-think-is-intersection.

Thats where you would do the comparison, possibly allowing a small error.

I assume the procedure i described is completely flawed like usual, so let me rewrite it...

R1 (D1=dir, P1=origin)

R0 (D0,P0)

1.Make R0 start from origin (subtract P0 from P1, make P0=0)

2.Use dot product to project P1 to R0 (get distance from origin)

3.Get distance between P1 and D0 * (thepreviousdistance^)

4.Get direction from the D0*prevdist to P1, multiply D1 by that

5.Divide result of 3 by magnitude of result of 4 (gets you the distance along R1 you need to travel to get to the intersection)

6.Go to that point (P1 + D1 * resultOf5)

7.Dot product D0 with the result of 6

8.Multiply result of 7 by D0

9.Compare result of 8 and 6. In an ideal world they should be equal (intersection) but add some thereshold to account for float inaccuracy.

But that seems to have way too many steps. Try googling for distance between 2 rays/lines, because if thats near 0, you have an intersection.

o3o

Posted 09 April 2013 - 02:06 AM

I mean 3D ray to ray (Maybe it's no possible?)

A ray being a point in space, that extends only in one direction (it's normal)....

This seems to have something of a sample of what i'm looking for, but i can't decipher it....

Posted 09 April 2013 - 02:21 AM

You basically need to find the shortest distance between the 2 rays. If that distance is near 0, the points which form the shortest distance are the intersection.

o3o

Posted 11 April 2013 - 01:27 PM

You need to find the shortest distance between the 2 rays.

look at "Distance between lines, rays, and segments (3D)." on http://www.geometrictools.com/LibMathematics/Distance/Distance.html

There is everything you need there.

Hope that help!

Cheers!