Archived

This topic is now archived and is closed to further replies.

Intersecting triagles with lines?

This topic is 6552 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Slow down Chappa!
__Are we talking 2D or 3D intersections? And what do you mean by intersecting?
__Do you want to find out whether or not a line intersects a triangle, or do you want to make a line from a point intersect a triangle?
__Please write your question more clearly so we know what to answer. If you're pressed for time, just jot a note down for yourself on paper, then post when you do have time.

-thanks for your patience-
-Sonic Silicon

Share this post


Link to post
Share on other sites
Sorry for being so unclear.
Well, talking about 3d. It makes no sense to intersect a plane in 2d.
I want be able find out whether a straight line intersects with a triangle. And now I wanted to know if there is a fast algorithm for doing this.
My idea was first to create a plane from the 3 points of the triangle, then intersect it with that line. Afterwards, you could check if the point lies within the 3 edges of the triangle. But maybe there's another way of finding out if the triangle and this straight line intersect, even without calculating the intersection.

(Please do apologize me if I made spelling mistakes. Not everyone is a native english speaker.)

Share this post


Link to post
Share on other sites
__Well, I usually don't care about spelling. It's bad grammer that irks me. I don't look for perfect english, just english good enough for conversation. (This IS a message board after all.)
__As for an answer: I can't remember anyone asking for anything similar, so I can't reference anything. Your way is the obvious way, but (unfortunately) the obvious way is usually the least efficient.
__I don't remember trig to well, but I'm sure I can come up with something for you. I'll just have to get back to you later.

-good luck

Share this post


Link to post
Share on other sites
Are you trying to do ray tracing? If not, this is something that is foundational to ray tracing, so you can probably get some ideas from reading documents on it. What you've described is one of the standard methods used, the other being using Barycentric coordinates. And in fact, if you are only using triangles, and especially if you are texture-mapping, Barycentric coords are probably a win. Unfortunately, I don't know of any good tutorials to point you to, but I'm sure a search will turn something up.

Share this post


Link to post
Share on other sites
Well, I wonder if anyone knows a quick and fast way of intersecting triagles with lines.
I don't wanna use planes for some reason.
There would be 3 points defining the vertices of the triangle and 1 point and 1 vector for defining the line.
Of course I could intersect the line with a plane first and then check if the intersection point lies within the edges of the triagle. But there must be a faster way to do this.

p.h.m.o thanx

Share this post


Link to post
Share on other sites
You definatly wouldn''t want to test and see if a line interects a plane first, then see if it hits the triangle because unless they are paralell, they will interect at some point.

Share this post


Link to post
Share on other sites
From http://www.magic-software.com ...

bool LineTriangleIntersection (const Line3& line, const Triangle3& tri,
Point3& intersect)
{
const float fTolerance = 1e-06f;

// Compute plane of triangle, Dot(normal,X-tri.b) = 0 where ''normal'' is
// the plane normal. If the angle between the line direction and normal
// is small, then the line is effectively parallel to the triangle.
Point3 normal = Cross(tri.e0,tri.e1);
float fDenominator = Dot(normal,line.m);
float fLLenSqr = Dot(line.m,line.m);
float fNLenSqr = Dot(normal,normal);
if ( fDenominator*fDenominator <= fTolerance*fLLenSqr*fNLenSqr )
{
// Line and triangle are parallel. I assume that only transverse
// intersections are sought. If the line and triangle are coplanar
// and they intersect, then you will need to put code here to
// compute the intersection set.
return false;
}

// The line is X(t) = line.b + t*line.m. Compute line parameter t for
// intersection of line and plane of triangle. Substitute in the plane
// equation to get Dot(normal,line.b-tri.b) + t*Dot(normal,line.m)
Point3 kDiff0 = line.b - tri.b;
float fTime = -Dot(normal,kDiff0)/fDenominator;

// Find difference of intersection point of line with plane and vertex
// of triangle.
Point3 kDiff1 = kDiff0 + fTime*line.m;

// Compute if intersection point is inside triangle. Write
// kDiff1 = s0*E0 + s1*E1 and solve for s0 and s1.
float fE00 = Dot(tri.e0,tri.e0);
float fE01 = Dot(tri.e0,tri.e1);
float fE11 = Dot(tri.e1,tri.e1);
float fDet = Abs(fE00*fE11-fE01*fE01); // = /normal/^2 > 0
float fR0 = Dot(tri.e0,kDiff1);
float fR1 = Dot(tri.e1,kDiff1);

float fS0 = fE11*fR0 - fE01*fR1;
float fS1 = fE00*fR1 - fE01*fR0;

if ( fS0 >= 0.0 && fS1 >= 0.0 && fS0 + fS1 <= fDet )
{
// intersection is inside triangle
intersect = kDiff1 + tri.b;
return true;
}
else
{
// intersection is outside triangle
return false;
}
}

Share this post


Link to post
Share on other sites
Thanks for all the help, guys. Especially for the well commented and clear code. However, the code seems a bit time expensive (lot of dot-products).
This might be faster but I didn't have the time yet to compare the two algos.

Anyhow, thanks again

-Chappa

Edited by - chappa on 1/5/00 7:24:23 AM

Share this post


Link to post
Share on other sites