gdalgorithms-list

[Algorithms] 3d Lines Intersection

[Albert_J <Alb...@te...>]

Hi,

Is there a good algo for finding a point of intersection between two *3D lines*?
The lines is specified by their point (x,y,z) and their direction (dx,dy,dz)

I've searched the web, but all of them seems to explain about 2D lines intersection only.

Thanks in advance.
Albert J

RE: [Algorithms] 3d Lines Intersection

[Norman V. <nh...@ca...>]

Albert_J writes:
>
>Is there a good algo for finding a point of intersection 
>between two *3D lines*?
>The lines is specified by their point (x,y,z) and their 
>direction (dx,dy,dz)

You can find source for this and other common 
Intersection routines in PLib.sg.sgIsect.cxx

http://plib.sourceforge.net

Norman VIne

Re: [Algorithms] 3d Lines Intersection

[<ro...@do...>]

Albert_J  wrote:

>Hi,
>
>Is there a good algo for finding a point of intersection between two *3D lines*?
>The lines is specified by their point (x,y,z) and their direction (dx,dy,dz)
>
>I've searched the web, but all of them seems to explain about 2D lines intersection only.

The problem is that in 3D almost all pairs of lines do not intersect
(as opposed to 2D where every pair of non parallel lines intersects).

Even if the logic of the construction of the two lines is such that
you know they must intersect, any computational intersection test will
be subject to rounding errors which, in all probability, will yield a
negative result.

The best you can do computationally  is to find the two points, one on
each line, which are nearest.  You may or may not want to call the
lines "intersecting" depending on the distance between these two
points and your error tolerance.

So if your two lines are specified by  vectors X1, DX1, X2, DX2,
namely
          X1= (x1, y1, z1), 
          DX1 = (dx1, dy1, dz1) 
         X2 = (x2, y2, z2), 
        DX2 = (dx2, dy2, dz2)

write down the vector parametric representations of the general point
one each of the two lines

       X1 + s DX1
       X2  + t DX2.

where s and t are INDEPENDENT real parameters.

You want to find the values of s and t that make the distance between
these two points as small as possible.  Write down the expression for
the distance between the two points, or rather the square of the
distance ( more convenient to avoid square roots), in terms of these
two parameters.   Using elementary vector geometry this squared
distance is 

  distance squared = 
 | (X1 + sDX1) - (X2 +  tDX2) |^2
 = |(X1 - X2) + s DX1 - t DX2)|^2
 = ((X1 - X2) + s DX1 - t DX2) . ( (X1 - X2) + s DX1 - t DX2))
where . means dot product.

Apply the elementary algebraic properties of dot product and collect
terms that are like in s and t and you get
 s^2 DX1.DX1 + t^2 DX2.DX2 - 2st DX1.DX2 + 
 s DX1. (X1 - X2) -  t DX2. (X1 - X2) + (X1 - X2).(X1 - X2)

This distance-squared function is of the form
as^2 + bt^2 + c st + ds + et + f
where a, b, c, d, e, f are known scalars computed from your line data
and s and t are independent variables.

This is a general quadratic function of two independent variables s
and t.  We seek to find the values of s and t that make it as small as
possible.  The best tool for this minization problem is the elementary
differential calculus of two variables, which tells us that the
minimum value occurs where the first partial derivatives with respect
to each of the variables is zero.  So differentiating first with
respect to s and then with respect to t gives two equations
 
	2as + ct + d = 0
                2bt  + cs + e = 0

This is a system of two linear equations in two unknowns s and t,
which you know how to solve from high school algebra.  It will have a
unique solution if the lines are not parallel.

Plug the resulting values of s and t back into the distance-squared
formula and see if that is close enough to zero so that you want to
call it an intersection.  In any case, if you plug the values of s and
t back into the parametric expressions for the two lines you get the
two closest points, one on each line.

P.S. You can avoid calculus and still find the two nearest points by
using the fact from Euclidean solid geometry that the closest two
points are the two feet of the mutual perpendicular between the two
lines, the mutual perpendicular being unique if the lines are not
parallel.  Write down the expression for the vector joining a general
point of each line, as a function of s and t, and write down the
equations that say that the dot product of this vector with each of
DX1 and DX2 is zero (this is the mutual perpendicularity condition). 
 
i.e. 	DX1. ((X1 - X2) + s DX1 + t DX2) = 0
                DX2. ((X1 - X2) + s DX1 + t DX2)) = 0

 The resulting two equations is a 2x2 linear system equivalent to the
one above.  The reason I chose the calculus approach is because I
didn't just want to find the two closest points, but also to test for
(near) intersection, which means I would have had to know the distance
function anyway, so I chose to start with the distance function, and
followed my nose from there.

Re: [Algorithms] 3d Lines Intersection

[Jim O. <j.o...@in...>]

> Is there a good algo for finding a point of intersection between two *3D
lines*?
> The lines is specified by their point (x,y,z) and their direction
(dx,dy,dz)

When I wrote my first renderer, I used a simple 3D intersection algorithm in
my (very alternative) projection system:

- calculate (x, y) intersection (result <x1, y>)
- calculate (x, z) intersection (result <x2, z>)
- if (x1 == x2) the lines intersect at <x1, y, z>

Of the top of my head I can't say whether this algorithm is 100% correct (I
am not a math guy...), but, if properly implemented, it will certainly be
fast and provide at least a reasonable estimation.

Jim Offerman

Innovade
- designing the designer

Re: [Algorithms] 3d Lines Intersection

[<ro...@do...>]

Jim Offerman  wrote:

>> Is there a good algo for finding a point of intersection between two *3D
>lines*?
>> The lines is specified by their point (x,y,z) and their direction
>(dx,dy,dz)
>
>When I wrote my first renderer, I used a simple 3D intersection algorithm in
>my (very alternative) projection system:
>
>- calculate (x, y) intersection (result <x1, y>)
>- calculate (x, z) intersection (result <x2, z>)
>- if (x1 == x2) the lines intersect at <x1, y, z>
>
>Of the top of my head I can't say whether this algorithm is 100% correct

It is my sad duty to have to inform you (and I dearly hope that the
news causes no undue emotional stress), that this putative algorithm
is wrong.  

Here is the clearest, simplest to understand counterexample that I
could construct (and there are clearly a bazillion others).

Let line 1 be the x axis, so the line with parametric representation
(s, 0, 0)   

Let line 2 be the line with parametric representation (0, t, t+1).
Thus line 2 lies in the yz plane where it has the implicit equation 
z = y+1.

The projection of line 1 on the xy plane is just the x axis.
The projection of line 2 on the xy plane is the y axis,
The intersection of these projections is (0,0,0).

The projection of line1 on the xz plane is the x axis
The projection of line 2 on the xz plane is the z axis
The intersection of these projections is (0,0,0)

So in your notation  x1 = 0 = x2,  and by your algorithm you claim
that the lines intersect at (0,0,0).  In fact they do not.  Line 2
does not even pass through the point (0,0,0),  In fact these two lines
do not intersect at all, ever, nowhere, no way.  In fact, it is a
problem in freshman analytic geometry to show that the distance of
closest approach of these two lines is sqrt(1/2), but I could as
easily have made it a billion units. 

> (I
>am not a math guy...),

Which is no license to post wrong stuff..

> but, if properly implemented, it will certainly be
>fast and provide at least a reasonable estimation.
>

Bah.

I'm growing weary of playing math cop.  Soon gonna turn in my badge.

Posting Wrong Stuff (was Re: [Algorithms] 3d Lines Intersection)

[Jim O. <j.o...@in...>]

Ron,

> > (I am not a math guy...),
>
> Which is no license to post wrong stuff..

Nope.

BUT one of my reasons for posting my algorithm is that there is bound to be
a math guy like you who will open my eyes and tell me I am wrong - hence
turning this into a learning experience for myself. And, of course, there is
always a slight chance that what I post is *nearly* right and some other
clever guy on the list (of which there are quite a few) comes up with a fix
which makes the algorithm right in all cases...

In any case, I *never* post something if I know before hand that what I will
be posting is wrong. In this particular case, the faulty algorithm produced
quite convincing results when I used it (quite a while ago) - however,
looking back, the situation you used to sketch the flaws in the algorithm
never occured while I was using the algorithm. Sadly, if a flawed algorithm
works for you, it can lead you to believe that it might be correct after
all.

I contribute to this list in order to help people (and whether believe it or
not, if my post is the first in a chain of posts which will uncover a fault
in some algorithm, this also helps people to avoid my mistakes) and not to
be flamed. In the end, Ron, you have received the seemingly unwanted supreme
authority when math are concerned, and have a considerable respect for your
extensive knowledge of the area.

However, I will challenge thy knowledge when I see fit, for I learn from my
mistakes.

Having said that, can we kiss 'n make up and get on with the regular
discussion of this list?

Thanks,

Jim Offerman

Innovade
- designing the designer

Re: Posting Wrong Stuff (was Re: [Algorithms] 3d Lines Intersection)

[Peter D. <pd...@mm...>]

> > Which is no license to post wrong stuff..
>
> Nope.
>
> BUT one of my reasons for posting my algorithm is that there is bound to
be

[...]

You know, I didn't realize that your algorithm is wrong immediately when I
read it. It took me about a day of "background thinking" to see that it
doesn't work.

Deliberately posting wrong stuff is one thing, posting things that you
believe (and are pretty certain) are correct is another. After all, I do
this all the time. So does Ron, for that matter.

--
Peter Dimov
Multi Media Ltd.

[Algorithms] Re: Posting Wrong Stuff

[Jim O. <j.o...@in...>]

> Deliberately posting wrong stuff is one thing, posting things that you
> believe (and are pretty certain) are correct is another. After all, I do
> this all the time. So does Ron, for that matter.

Don't we all. And I don't think that there is anyone on this list who will
deliberately post something that is wrong.

Coming from a world of designers, I am taught to believe that every idea is
a good one, as bad ideas often lead to great ideas (I think that the most
famous example is the yellow 'Post-It' note, which is actually the result of
a failed experiment). We don't need some cop (and I mean this in general, I
don't want to start a personal attack on Ron or anyone else) to track down
and hunt posters of wrong ideas, we really don't. I'd rather see a wrong
idea feul the discussion that leads to a right idea.

Jim Offerman

Innovade
- designing the designer

"The road to success is learned from one's failures."

Re: [Algorithms] Re: Posting Wrong Stuff

[Peter D. <pd...@mm...>]

> > Deliberately posting wrong stuff is one thing, posting things that you
> > believe (and are pretty certain) are correct is another. After all, I do
> > this all the time. So does Ron, for that matter.

I realize that I was a bit unclear. What I meant was that your post falls in
the second category, not the first.

> Coming from a world of designers, I am taught to believe that every idea
is
> a good one, as bad ideas often lead to great ideas (I think that the most
> famous example is the yellow 'Post-It' note, which is actually the result
of
> a failed experiment).

And, in fact, it was your post that made me think about the solution I
posted.

--
Peter Dimov
Multi Media Ltd.

Re: [Algorithms] 3d Lines Intersection

[Stephen J B. <sj...@li...>]

On Sun, 30 Jul 2000, Ron Levine wrote:

> Jim Offerman  wrote:
> 
> >> Is there a good algo for finding a point of intersection between two *3D
> >lines*?
> >> The lines is specified by their point (x,y,z) and their direction
> >(dx,dy,dz)
> >
> >When I wrote my first renderer, I used a simple 3D intersection algorithm in
> >my (very alternative) projection system:
> >
> >- calculate (x, y) intersection (result <x1, y>)
> >- calculate (x, z) intersection (result <x2, z>)
> >- if (x1 == x2) the lines intersect at <x1, y, z>
> >
> >Of the top of my head I can't say whether this algorithm is 100% correct
> 
> It is my sad duty to have to inform you (and I dearly hope that the
> news causes no undue emotional stress), that this putative algorithm
> is wrong.  
> 
> Here is the clearest, simplest to understand counterexample that I
> could construct (and there are clearly a bazillion others).
> 
> Let line 1 be the x axis, so the line with parametric representation
> (s, 0, 0)   
> 
> Let line 2 be the line with parametric representation (0, t, t+1).
> Thus line 2 lies in the yz plane where it has the implicit equation 
> z = y+1.
> 
> The projection of line 1 on the xy plane is just the x axis.
> The projection of line 2 on the xy plane is the y axis,
> The intersection of these projections is (0,0,0).
> 
> The projection of line1 on the xz plane is the x axis
> The projection of line 2 on the xz plane is the z axis
> The intersection of these projections is (0,0,0)
> 
> So in your notation  x1 = 0 = x2,  and by your algorithm you claim
> that the lines intersect at (0,0,0).  In fact they do not.  Line 2
> does not even pass through the point (0,0,0),  In fact these two lines
> do not intersect at all, ever, nowhere, no way.  In fact, it is a
> problem in freshman analytic geometry to show that the distance of
> closest approach of these two lines is sqrt(1/2), but I could as
> easily have made it a billion units. 
> 
> > (I
> >am not a math guy...),
> 
> Which is no license to post wrong stuff..
> 
> > but, if properly implemented, it will certainly be
> >fast and provide at least a reasonable estimation.
> >
> 
> Bah.
> 
> I'm growing weary of playing math cop.  Soon gonna turn in my badge.
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 
> 

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

Re: [Algorithms] 3d Lines Intersection

[Eric H. <er...@ac...>]

Albert_J wrote:

> Is there a good algo for finding a point of intersection between two *3D lines*?
> The lines is specified by their point (x,y,z) and their direction (dx,dy,dz)
>
> I've searched the web, but all of them seems to explain about 2D lines intersection only.

An answer (but not online, unfortunately): Goldman, Intersection of Two Lines in Three-Space,
Graphics Gems, p. 304.

I looked it up on my 3D objects intersection page: http://www.realtimerendering.com/int/. I
really need to find time to put down actual algorithms and code on this page (anyone want to
give me a grant? ;^> ).

Anyway, for two lines P1 _ V1*t and P2 + V2*s, where V1 and V2 are the direction vectors and
P1 & P2 some points on the lines, the answer is:

    s = Determinant{(P2-P1),V1,V1 X V2} / | V1 X V2 |^2

If the lines are parallel, the denominator is 0. If the lines are skew (don't intersect), s
and t represent the parameters of the points of closest approach - measure the distance
between these two points and you'll know how far apart they are.

Eric

RE: [Algorithms] 3d Lines Intersection

[Graham S. R. <gr...@se...>]

There is a nice closed form solution for this determinant (since the matrix
is small). I worked it out a few years ago, and I *might* still have it
lying around somewhere. (It was sent to some newsgroup.)

I'll see if I can dig it up or redo it if anyone is interested and doesn't
want to take the time to do it themselves.

Graham

Eric Haines wrote,

> -----Original Message-----
> I looked it up on my 3D objects intersection page:
> http://www.realtimerendering.com/int/. I really need
> to find time to put down actual algorithms and code
> on this page (anyone want to give me a grant? ;^> ).
>
> Anyway, for two lines P1 _ V1*t and P2 + V2*s, where V1 and V2 are
> the direction vectors and P1 & P2 some points on the lines, the answer is:
>
>    s = Determinant{(P2-P1),V1,V1 X V2} / | V1 X V2 |^2
>
> If the lines are parallel, the denominator is 0. If the lines are skew
> (don't intersect), s and t represent the parameters of the points of
> closest approach - measure the distance between these two points and
> you'll know how far apart they are.

Eric

[Algorithms] texture space

[Vladimir K. <vka...@si...>]

Hi All,

I know similar question was discussed here some time ago.
But I need a bit more info.

I want to put dot3 bumpmapping onto animated character.
To transform light vector into texture space I need to calculate
orthonormal basis for the tangent space for vertex.

How can I calculate tangent vector of this basis ?
How it depends on texture coordinates of face ?

I found not bad example for this at nvidia site - md2shader.
But I don't understand how it's done here.
In md2shader used only one tex coordinate for calculations.
I think it's wrong.

I know you say that it's school level question.
But may be somebody can point me good code example 
or explanation.

Thanks
vlad