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.)

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.

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

Found something interesting at
http://www.acm.org/jgt/papers/MollerTrumbore97/

The presented algorihm seems to be faster than barycentric coordinates. However I haven't had the time to check it out yet, but I will get to that asap.

[This message has been edited by Chappa (edited December 30, 1999).]

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.

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;
}
}

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