PDA

View Full Version : HELP!! 3D Math - How can i calc intersection of two line/ray?

hunsoul
03-29-2001, 07:06 AM
I have two line/ray
(A line/ray means 1point+1vector OR 2point)
I would like to calculate the intersection between the two line/ray.

Has anybody got a function what do this?

Thanx.
HunSoul

Rob
03-29-2001, 07:26 AM
In 2D or 3D? In 3D two lines don't usually intersect, so the best you can do is find the closest distance between them.

hunsoul
03-29-2001, 08:14 AM
Originally posted by Rob:
In 2D or 3D? In 3D two lines don't usually intersect, so the best you can do is find the closest distance between them.

Yes, i know...so i need a function what calc the closest distance between them - in 3D (sorry for my lack of precision)

Plese HELP me! - this is very urgent for me http://www.opengl.org/discussion_boards/ubb/frown.gif

Zeno
03-29-2001, 09:55 AM
There is a really good source for algorithms like this at:
http://www.magic-software.com/MgcDistance3D.html

They have algorithms for what you want there. Incidentally, the book is pretty good too.

-- Zeno

ScottManDeath
03-29-2001, 11:11 PM
Originally posted by hunsoul:
I have two line/ray
(A line/ray means 1point+1vector OR 2point)
I would like to calculate the intersection between the two line/ray.

Has anybody got a function what do this?

Thanx.
HunSoul

Well this is a problem of simple(?) vector mathmatics.

First you need both lines in the form

line one:

a=p1 + t * d1

a,p1,d1 ... vectors
t ... scalar

a... set point of point on the ray
p1... initital point
d1... direction of the line
t... scalare which moves fromm negative infinity to positive infinity

in componemt writing it would be
(p11) (d11)
a=(p12) + t * (d12)
(p13) (d13)

line 2 (same as line one)

b=p2 + u * d2

(p21) (d21)
b=(p22) + u * (d22)
(p23) (d23)

Two lines interescting yields in following possibilities
1) the two lines lie in the same plane but arent identical (they are parallel)
condition:
d1 &#0124; &#0124; d2
p1 not on b or p2 not on a

2) the two lines are identical
condition:
d1 &#0124; &#0124; d2
p1 lies on b or p2 lies on a

3)they intersect on one point
condition :
a=b woth one solution of this equotaion

4)they dont fullfill the other possibities
they have a point of minimal distance

then you have to set both lines equal

a=b
p1+ t * d1 = p2 + u * d2

then you get a linear equotaion system with 3 equotations and 2 unkonw variables

I p11 + t* d11 = p21 + u * d21
II p12 + t* d12 = p22 + u * d22
III p13 + t* d13 = p23 + u * d23

t and u are the variables
try to eliminate t and you will get u(or vice versa)

if possibility 3) you will get one solution
(u or t) uses this to calculate the points coordinates by setting t in a ot u in b

if possibility 1 or 4) you dont get a solution
to determine 1) or 4)
check if d1 &#0124; &#0124; d2 , if so you have 1) otherwise 4)
if possibility 2) you get a solution of true for all t, u for all numbers

now you have an idea how you can do it
hope it isnt to mathematical for you
the problem might be to solve the linear equotation system but with some if/else and some + / * - it would be possible

Bye

hunsoul
03-30-2001, 04:07 AM
THANK YOU Zeno!
THANK YOU VERY MUCH ScottManDeath!

Now, i can solve the problem!

http://www.opengl.org/discussion_boards/ubb/smile.gif

[This message has been edited by hunsoul (edited 03-30-2001).]

ScottManDeath
03-30-2001, 01:54 PM
That got me satisfied but to get the ultimate kick http://www.opengl.org/discussion_boards/ubb/biggrin.gif i looked in my 2 years old mathmatics execise book from school and i found following...

to get the distance of two non intersecting non parallel lines you can do the following

just remind

a = p1 + t * d1

b= p2 + u * d2

you can create two planes being parallel, each containing one line by doing this:

e1 = p1 + f * d1 +g * d2

e2 = p2 + h * d1 +i* d2

e1,e2 two planes
p1,p2 points of the two lines
d1,d2 directions of the two lines
f,g,h,i scalarsc from -INF to + INF to determine all points on each plane.

but what did we there ?:
(pick one plane , I took e1)
we created a plane (e1)that contains line a
then we can calculate the distance of point p2(on b) to this plane. this is equal to the distance of the two lines because a element of e1 and b elemnt of e2.

we have to translate e1 in the "Hessesche Normalform" (in german mathmatic lesson,I don't know if you use this expression but you should see it)

you need:
n ...the normal vector of e1 (by crossproducting d1 and d2)
x0 ...one point on e1 p1

you have to normalize the normal (game of words http://www.opengl.org/discussion_boards/ubb/smile.gif by dividing it by its length
n = n * 1/|n|

each point x on this plane can be calculated in this way(hessesche normalform)

(x-x0)* (n * 1/|n|) = 0 [dot product]

to get the distance d of p2 to e1 you use

d = (p2 -p1)*( n* 1/|n|)

perhaps you should take |d| otherwise you get the orientated distance

if line a | | line b the problem is calculating the distance from
point to line as done in this way:

distance line point:

l = p0 + t * d

p ... point

create a plane e orthogonal to line l and containing p:
(hessesche normalform)

(x-p)*d*(1/|d1|)=0

then you intersect line l with this plane getting point s

just "dot" the plane(hessesche normalform) out and you get
A*x +B*y +C*z +D =0

then set line l in this equotation
A(p01 + t *d1)+B(p02 + t*d2)+C(p03+ t*d3)+D=0
then you get t, use this to calc point s by placing t in l.

then you calc the size of vector (ps)
and you got it

to calc distance line line just calc distance point p2 to line a ...

I hope it's correct. ( if you hav a working version of your code please post it or mail it

[This message has been edited by ScottManDeath (edited 03-31-2001).]

ffish
04-04-2001, 12:10 AM
Found a good explanation of the problem along with source on Paul Bourke's great site:
http://astronomy.swin.edu.au/pbourke/geometry/lineline3d/

Cheers,
Toby