Suppose I have a triangle with corners A, B and C. Suppose, further, 
that I have a line that passes through P and Q.

Now... how do I figure out whether these two objects intersect each 
other? (I don't care *where* they intersect, only *if*.)

Andrew.

Post a reply to this message

> Suppose I have a triangle with corners A, B and C. Suppose, further,
> that I have a line that passes through P and Q.
>
> Now... how do I figure out whether these two objects intersect each
> other? (I don't care *where* they intersect, only *if*.)

Well, you could generate the plane of the triangle, and then cut the line
through P and Q with that plane. The angle between the vectors that point
from the intersection to the three corners then needs to add up to 360
degrees to lie in the triangle.

I hope that's correct, just wrote this off the top of my head. Maybe someone
can correct me if I've missed something.

Regards,
Tim

-- 
"Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message

> Suppose I have a triangle with corners A, B and C. Suppose, further,
> that I have a line that passes through P and Q.
>
> Now... how do I figure out whether these two objects intersect each
> other? (I don't care *where* they intersect, only *if*.)


Tim's solution is most likely the best, but if you're looking for a quick
solution and you're not worried about speed, then you might just want to
#declare a triangle and trace() a ray towards it.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

> Well, you could generate the plane of the triangle, and then cut the line
> through P and Q with that plane. The angle between the vectors that point
> from the intersection to the three corners then needs to add up to 360
> degrees to lie in the triangle.
> 
> I hope that's correct, just wrote this off the top of my head. Maybe someone
> can correct me if I've missed something.

Uh... dude... how the HELL do you calculate the angle between vectors?? :-S

(I had already figured out how to test if the line passes through the 
plane of the triangle. Whether it goes through the triangle itself...?)

Actually, here's a thought... What if a take the dot product of point C 
against the vector from A to B? Then I take the dot product of the point 
where the line intersects the plane. If the answer has the same sign but 
is nearer to zero, then I can do the same check with the other pair(s) 
of points...

Maybe that could work...

Andrew.

Post a reply to this message

> Actually, here's a thought... What if a take the dot product of point C 
> against the vector from A to B? Then I take the dot product of the point 
> where the line intersects the plane. If the answer has the same sign but 
> is nearer to zero, then I can do the same check with the other pair(s) 
> of points...
> 
> Maybe that could work...

Uh... no... that's NOT going to work...

What I want is a vector *perpendicular* to AB, but still in the same 
plane as the triangle... :-S

Post a reply to this message

Tim Nikias wrote:
>>Suppose I have a triangle with corners A, B and C. Suppose, further,
>>that I have a line that passes through P and Q.
>>
>>Now... how do I figure out whether these two objects intersect each
>>other? (I don't care *where* they intersect, only *if*.)
> 
> 
> Well, you could generate the plane of the triangle, and then cut the line
> through P and Q with that plane. The angle between the vectors that point
> from the intersection to the three corners then needs to add up to 360
> degrees to lie in the triangle.
> 
> I hope that's correct, just wrote this off the top of my head. Maybe someone
> can correct me if I've missed something.

Inverse trigonometric operations are slow.

Try this search:

http://www.google.com/search?q=efficient+line+triangle+intersection

-- 
Tor Olav
http://subcube.net
http://subcube.com

Post a reply to this message

On Mon, 08 Nov 2004 21:26:38 +0000, Andrew the Orchid <voi### [at] devnull> wrote:
> What I want is a vector *perpendicular* to AB, but still in the same 
> plane as the triangle... :-S

do a cross vector between triangle edges. This makes vector S perpendicular to
triangle. Now, do a cross vector between S and edge AB and you have vector to
AB and again on the plane of trinagle. Is that readable ?

Writing it blindly and without handling special cases:

#macro DoIt(A,B,V1,V2,V3) /* point and triangle */
  #local AB = B-A;
  #local P1 = V2-V1;
  #local P2 = V3-V1;
  #local S = vcross(P1,P2);
  #local P = vcross(S,AB);
  (P)
#end

ABX

Post a reply to this message

> Inverse trigonometric operations are slow.
> 
> Try this search:
> 
> http://www.google.com/search?q=efficient+line+triangle+intersection

Was about to try something even more complex and longwinded. But the 
very first link gives me this:

Plane thru A, B, C is given by
   P(u, v) = A + u*AB + v*AC
Line thru J, K is given by
   L(t) = J + t*JK
Intersection of P and L is I=L(t) where
   t = N . (A - P) / N . (Q - P)
u,v coordinate of I is
   u = AI . (N x AC) / AB . (N x AC)
   v = AI . (N x AB) / AC . (N x AB)
(N = normal of the plane).

Finally, the point lies within the triangle iff
   u >= 0
   v >= 0
   u+v <= 1

Add to that a check in case the line and triangle are perpendicular - 
and anoter check because I want my line to be finite length (check that 
0<=t<=1) and we're done! Ha!

Andrew.

Post a reply to this message

#macro TestIsect(A, B, C, P, Q)
   #local AB = B - A;
   #local AC = C - A;
   #local N = vcross(AB, AC);

   #local PQ = Q - P;

   #local _t = vdot(N, A - P) / vdot(N, PQ);

   #local Isect = ((_t >= 0) & (_t <= 1));

   #if (Isect)
     #local I = P + PQ*_t;

     #local AI = I - A;
     #local J = vcross(N, AB);
     #local K = vcross(N, AC);
     #local _u = vdot(AI, K) / vdot(AB, K);
     #local _v = vdot(AI, J) / vdot(AC, J);

     #local Isect = ((_u >= 0) & (_v >= 0) & (_u + _v <= 1));
   #end

   Isect
#end

Andrew.

PS. Annoying that I have to put the underscores on those variable 
names... grrr!

Post a reply to this message

Andrew the Orchid wrote:
>> Inverse trigonometric operations are slow.
>>
>> Try this search:
>>
>> http://www.google.com/search?q=efficient+line+triangle+intersection
> 
> 
> Was about to try something even more complex and longwinded. But the 
> very first link gives me this:
> 
> Plane thru A, B, C is given by
>   P(u, v) = A + u*AB + v*AC
> Line thru J, K is given by
>   L(t) = J + t*JK
> Intersection of P and L is I=L(t) where
>   t = N . (A - P) / N . (Q - P)
> u,v coordinate of I is
>   u = AI . (N x AC) / AB . (N x AC)
>   v = AI . (N x AB) / AC . (N x AB)
> (N = normal of the plane).
> 
> Finally, the point lies within the triangle iff
>   u >= 0
>   v >= 0
>   u+v <= 1
> 
> Add to that a check in case the line and triangle are perpendicular - 
> and anoter check because I want my line to be finite length (check that 
> 0<=t<=1) and we're done! Ha!

Yes that looks elegant.

When I sit down and figure out such things myself,
I continue until the solution is as simple as I
can manage to make it.

If it then does not look elegant, then it's probably
not the best solution.

-- 
Tor Olav
http://subcube.net
http://subcube.com

Post a reply to this message

Andrew the Orchid nous apporta ses lumieres ainsi en ce 2004-11-08 
17:22... :

>
>
> Andrew.
>
> PS. Annoying that I have to put the underscores on those variable 
> names... grrr!

Use Upercase then you don't need those underscores.

Post a reply to this message

In article <418fe747$1@news.povray.org>,
 Tor Olav Kristensen <tor### [at] TOBEREMOVEDgmailcom> wrote:

> Inverse trigonometric operations are slow.

In POV, the difference between an inverse trig operation and any other 
operation is likely to be overwhelmed by the overhead of parsing the 
script. Code that is simpler to parse is likely to be faster.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: <chr### [at] tagpovrayorg>
http://tag.povray.org/

Post a reply to this message

Christopher James Huff wrote:
> In article <418fe747$1@news.povray.org>,
>  Tor Olav Kristensen <tor### [at] TOBEREMOVEDgmailcom> wrote:
> 
> 
>>Inverse trigonometric operations are slow.
> 
> 
> In POV, the difference between an inverse trig operation and any other 
> operation is likely to be overwhelmed by the overhead of parsing the 
> script. Code that is simpler to parse is likely to be faster.

Yes, I know.

I thought it was a general mathematic question.

-- 
Tor Olav
http://subcube.net
http://subcube.com

Post a reply to this message

>> PS. Annoying that I have to put the underscores on those variable 
>> names... grrr!
> 
> 
> Use Upercase then you don't need those underscores.

The idea is to use upercase for vectors and lowercase for scalars...

But yes, that would also work of course.

Andrew.

(I understand not being able to use "x", "y" and "z", but "t"? That's 
not even *valid* as a token by itself...)

Also vaguely irritating is the need to wrap Boolean assignments with 
brackets, but still...

Post a reply to this message

On Tue, 09 Nov 2004 20:14:17 +0000, Andrew the Orchid <voi### [at] devnull> wrote:
> (I understand not being able to use "x", "y" and "z", but "t"? That's 
> not even *valid* as a token by itself...)

http://www.povray.org/documentation/view/3.6.1/229/

  VECTOR_BUILT-IN_IDENT:
       x | y | z | t | u | v

and later

  2.2.1.4.3 Operators

and then try

#declare V=<1,2,3,4>;
#declare Vt=V.t;

ABX

Post a reply to this message

>>(I understand not being able to use "x", "y" and "z", but "t"? That's 
>>not even *valid* as a token by itself...)
> 
> 
> http://www.povray.org/documentation/view/3.6.1/229/
> 
>   VECTOR_BUILT-IN_IDENT:
>        x | y | z | t | u | v
> 
> and later
> 
>   2.2.1.4.3 Operators
> 
> and then try
> 
> #declare V=<1,2,3,4>;
> #declare Vt=V.t;

Oh, sure... V.t is a perfectly valid expression. But - unlike "x" / "y" 
/ "z", "t" by itself isn't a valid expression.

Post a reply to this message

On Tue, 09 Nov 2004 20:22:17 +0000, Andrew the Orchid <voi### [at] devnull> wrote:
> Oh, sure... V.t is a perfectly valid expression. But - unlike "x" / "y" 
> / "z", "t" by itself isn't a valid expression.

Look later into "2.2.1.4.6 Built-in Constants"

All built-in vector identifiers never change value. They are defined as though
the following lines were at the start of every scene. 

 #declare x = <1, 0, 0>;
 #declare y = <0, 1, 0>;
 #declare z = <0, 0, 1>;
 #declare t = <0, 0, 0, 1>;
 #declare u = <1, 0>;
 #declare v = <0, 1>;

ABX

Post a reply to this message

>  #declare t = <0, 0, 0, 1>;
>  #declare u = <1, 0>;
>  #declare v = <0, 1>;

Well... you learn something every day... I never knew you could do that...

Post a reply to this message