POV-Ray : Newsgroups : povray.advanced-users : 3D mathematics question Server Time
31 Oct 2024 19:29:06 EDT (-0400)
  3D mathematics question (Message 1 to 10 of 18)  
Goto Latest 10 Messages Next 8 Messages >>>
From: Andrew the Orchid
Subject: 3D mathematics question
Date: 8 Nov 2004 16:05:40
Message: <418fdfa4@news.povray.org>
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

From: Tim Nikias
Subject: Re: 3D mathematics question
Date: 8 Nov 2004 16:11:52
Message: <418fe118$1@news.povray.org>
> 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

From: Slime
Subject: Re: 3D mathematics question
Date: 8 Nov 2004 16:15:09
Message: <418fe1dd@news.povray.org>
> 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

From: Andrew the Orchid
Subject: Re: 3D mathematics question
Date: 8 Nov 2004 16:23:53
Message: <418fe3e9$1@news.povray.org>
> 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

From: Andrew the Orchid
Subject: Re: 3D mathematics question
Date: 8 Nov 2004 16:27:12
Message: <418fe4b0@news.povray.org>
> 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

From: Tor Olav Kristensen
Subject: Re: 3D mathematics question
Date: 8 Nov 2004 16:38:15
Message: <418fe747$1@news.povray.org>
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

From: ABX
Subject: Re: 3D mathematics question
Date: 8 Nov 2004 16:42:49
Message: <vppvo0ljvc5nobs4q75c4fhb63ueaj3l3t@4ax.com>
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

From: Andrew the Orchid
Subject: Re: 3D mathematics question
Date: 8 Nov 2004 17:06:20
Message: <418feddc@news.povray.org>
> 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

From: Andrew the Orchid
Subject: Re: 3D mathematics question
Date: 8 Nov 2004 17:22:58
Message: <418ff1c2$1@news.povray.org>
#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

From: Tor Olav Kristensen
Subject: Re: 3D mathematics question
Date: 8 Nov 2004 17:38:29
Message: <418ff565$1@news.povray.org>
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

Goto Latest 10 Messages Next 8 Messages >>>

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