POV-Ray : Newsgroups : povray.general : Intersection of two vectors Server Time: 19 Dec 2018 13:24:34 GMT
  Intersection of two vectors (Message 1 to 5 of 5)  
From: Mike Horvath
Subject: Intersection of two vectors
Date: 21 Jul 2018 10:14:30
Message: <5b530786$1@news.povray.org>
Is there already a function/macro for determining the intersection of 
two coplanar lines or vectors? (So I don't have to program it again.)


Thanks.


Post a reply to this message

From: Mike Horvath
Subject: Re: Intersection of two vectors
Date: 21 Jul 2018 10:15:50
Message: <5b5307d6$1@news.povray.org>
On 7/21/2018 6:15 AM, Mike Horvath wrote:
> Is there already a function/macro for determining the intersection of 
> two coplanar lines or vectors? (So I don't have to program it again.)
> 
> 
> Thanks.


I forgot to say that the lines are not in y = mx + b form. Rather, I 
just have two pairs of points.


Mike


Post a reply to this message

From: clipka
Subject: Re: Intersection of two vectors
Date: 21 Jul 2018 10:45:22
Message: <5b530ec2$1@news.povray.org>
Am 21.07.2018 um 12:15 schrieb Mike Horvath:
> Is there already a function/macro for determining the intersection of
> two coplanar lines or vectors? (So I don't have to program it again.)

Not out of the box, as far as I know.

One approach to solve this problem would be to compute a transformation
from their common plane to the XY plane, then compute the intersection
point there, and finally apply the inverse transformation to the result
point. Finding a suitable transformation may not be trivial for general
cases though.

Another approach would be to determine the pair of points where the two
lines come closest to each other (there must be a general formula for
this somewhere), and either just pick one or compute the average of the
two. You can also use the distance between those two points as an
inexpensive coplanarity test if necessary.


Post a reply to this message

From: Bald Eagle
Subject: Re: Intersection of two vectors
Date: 21 Jul 2018 12:45:01
Message: <web.5b5329ffd39af362458c7afe0@news.povray.org>
Mike Horvath <mik### [at] gmailcom> wrote:
> On 7/21/2018 6:15 AM, Mike Horvath wrote:
> > Is there already a function/macro for determining the intersection of
> > two coplanar lines or vectors? (So I don't have to program it again.)
> >
> >
> > Thanks.
>
>
> I forgot to say that the lines are not in y = mx + b form. Rather, I
> just have two pairs of points.
>
>
> Mike

Oh. God.
Some people just want EVERYTHING.   :P

I think I coded this from Graphics Gems.




#version 3.7;
global_settings {assumed_gamma 1.0}
#include "Math.inc"
#include "Determinant.mcr"

#macro IntersectionOfLines (pa, pb, PA, PB)
 /*
 INTERSECTION OF
 TWO LINES IN
 THREE-SPACE
 Ronald Goldman
 University of Waterloo
 Waterloo, Ontario, Canada
 [From Graphics Gems (1)]
 Let each line be defined by a point Pk and a unit direction vector Vk,
 k = 1,2.
 */
 #declare P1 = pa;
 #declare V1 = vnormalize (pb-pa);
 //#debug concat ( " V1 ", vstr (3, V1, ",", 3, 1),  "\n")
 #declare P2 = PA;
 #declare V2 = vnormalize (PB-PA);
 //#debug concat ( " V2 ", vstr (3, V2, ",", 3, 1),  "\n")

 // Then we can express each line parametrically by writing
 // L1(_t) = P1 + V1 * _t
 // and
 // L2(_s) = P2 + V2 * _s.

 // The intersection occurs when L1(t) = L2(s) or equivalently when P1 + V1t =
P2 + V2s
 // Subtracting Pl from both sides and crossing with V2 yields
 // vcross(V1, V2) * _t = vcross ((P2 &#65533; P1), V2)
 // Now dotting with vcross(V1, V2) and dividing by pow(Det(vcross(V1, V2)), 2)
gives us
 // _t = vdot ( vcross((P2 &#65533; P1), V2), vcross(V1, V2) ) / pow (vdot (V1,
V2), 2);
 // Symmetrically, solving for s, we obtain
 // _s = vdot ( vcross((P2 &#65533; P1), V1), vcross(V1, V2) ) / pow (vdot (V1,
V2), 2);

 /*
 Two important observations follow:
 &#65533; If the lines are parallel, the denominator |Vl x V2|2 = 0.
 &#65533; If the lines are skew, s and t represent the parameters of the points
of
 closest approach.
 */

 //#if (pow (vdot (V1, V2), 2) = 0) // check for parallel

 #local Denom = pow (Det (V1, V2), 2);
 #if (Denom = 0) // check for parallel
  #debug concat ( " Det (V1, V2) ", str (vdot (V1, V2), 3, 1),  "\n")
  #debug concat ( " pow (Det (V1, V2), 2) ", str (Denom, 3, 1),  "\n")
  #debug "No intersection - parallel lines. \n"
  #local Intersection = (x+y+z)*666;
 #else
  //#local _t = Det ( vcross((P2 - P1), V2), vcross(V1, V2) ) / pow (Det (V1,
V2), 2);
  //#local _s = Det ( vcross((P2 - P1), V1), vcross(V1, V2) ) / pow (Det (V1,
V2), 2);
  #local _t = Det3 ( (P2 - P1), V2, vcross(V1, V2) ) / Denom;
  #local _s = Det3 ( (P2 - P1), V1, vcross(V1, V2) ) / Denom;
  //#debug concat ( " _t =", str (_t, 3, 1),  "\n")
  //#debug concat ( " _s =", str (_s, 3, 1),  "\n")

  #local I1 = P1 + V1 * _t;
  #local I2 = P2 + V2 * _s;
  //#debug concat ( "I1 = ", vstr(3, I1, ", ", 3, 2), " \n")
  //#debug concat ( "I2 = ", vstr(3, I2, ", ", 3, 2), " \n")
  #if (VEq (I1, I2)) // check for intersection, else skew
   #local Intersection = P1 + V1 * _t;
  #else
   #debug "No intersection - skew lines. \n"
   #local Intersection = (x+y+z)*666;
  #end
 #end // end if parallel

 #debug concat ( " Intersection of Line 1 [from <", vstr (3, pa, ", ", 3, 1), ">
to <", vstr (3, pb, ", ", 3, 1), ">] and Line 2 [from <", vstr (3, PA, ", ", 3,
1), "> to <", vstr (3, PB, ", ", 3, 1), ">] is the point <", vstr (3,
Intersection, ", ", 3, 1),  "> \n")

 Intersection

#end // end macro IntersectionOfLines

#include "colors.inc"

camera {
 location  <0, 0, -20>
 right    x*image_width/image_height
 look_at   <0, 0, 0>
}

light_source { <0, 10, -20>  color rgb <1, 1, 1>}

background {color rgb <1, 1, 1>*0.1}


#declare Point1 = <-5,  1,  0>;
#declare Point2 = < 5,  1,  0>;
#declare Point3 = < 0, -5,  0>;
#declare Point4 = < 0,  5,  0>;

#declare I = IntersectionOfLines (Point1, Point2, Point3, Point4);

cylinder {Point1, Point2, 0.1 pigment {Green}}
cylinder {Point3, Point4, 0.1 pigment {Blue}}
sphere {I, 0.2 pigment {Red}}


Post a reply to this message

From: Mike Horvath
Subject: Re: Intersection of two vectors
Date: 22 Jul 2018 01:58:57
Message: <5b53e4e1$1@news.povray.org>
I forgot to *also* say that both lines lie on the z plane, which would 
make things much simpler.

I went with this routine instead:

https://stackoverflow.com/questions/20677795/how-do-i-compute-the-intersection-point-of-two-lines-in-python

It works okay, but there is one small issue that I raised in the "Macro 
return value on failure" thread.


Mike



On 7/21/2018 8:41 AM, Bald Eagle wrote:
> Mike Horvath <mik### [at] gmailcom> wrote:
>> On 7/21/2018 6:15 AM, Mike Horvath wrote:
>>> Is there already a function/macro for determining the intersection of
>>> two coplanar lines or vectors? (So I don't have to program it again.)
>>>
>>>
>>> Thanks.
>>
>>
>> I forgot to say that the lines are not in y = mx + b form. Rather, I
>> just have two pairs of points.
>>
>>
>> Mike
> 
> Oh. God.
> Some people just want EVERYTHING.   :P
> 
> I think I coded this from Graphics Gems.


Post a reply to this message

Copyright 2003-2008 Persistence of Vision Raytracer Pty. Ltd.