 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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] dev null> 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
|
|
| |
| |
|
|
|
|
| |
