Sign in to follow this  
uglybdavis

Ray to Ray intersection

Recommended Posts

uglybdavis    1065

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.

Share this post


Link to post
Share on other sites
Waterlimon    4398

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

Share this post


Link to post
Share on other sites
C0lumbo    4411

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

Share this post


Link to post
Share on other sites
Juliean    7077

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.

Share this post


Link to post
Share on other sites
Waterlimon    4398

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.

Share this post


Link to post
Share on other sites
uglybdavis    1065

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....

http://www.andrewaye.com/Teikitu%20Gaming%20System/code_page_template.php?codefile=/home/andreway/public_html/Teikitu%20Gaming%20System/inc/TgS%20COLLISION/TgS%20Collision%20-%20F%20-%20Ray.i_inc.html

Share this post


Link to post
Share on other sites
Waterlimon    4398

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this