ray-triangle intersection

I’m sure that this has been gone over hundereds of times on this forum alone… but I’m going to ask anyway. I just want to make a function that checks if a single ray intersects a single triangle. I currently have a function that is pretty much a replica of the first MT algorithm, and it almost seems to work. To test the function I am rendering a triangle and a line, with the arrow keys controling the position of the line. When the function says there was an intersection, the line is red, if it says there wasnt the line is green. It works along one side of the triangle, and then it stops working about 1/2 of the way in to the center of the triangle on the other two sides. And if i switch the order that I feed the vertices to the function in, say from intersection(o,d,v1,v2,v3) to intersection(o,d,v2,v3,v1) wierd stuff happens. I wish I could be of more help in helping me, but I can find the dot product and cross product, but I really dont know what any of it means. This is the function that i’m using now…

  
bool intersect(Vert origin, Vert direction, Vert v1, Vert v2, Vert v3)
{
	Vert edge1, edge2,pvec;
	float det;

	edge1 = v2-v1;
	edge2 = v3-v1;

	pvec = CROSS(direction,edge2);

	det = DOT(edge1,pvec);

	if(det<EPSILON)
		return false;

	Vert tvec;
	tvec = origin - v1;

	float u,v;

	u = DOT(tvec,pvec);

	Vert qvec;
	qvec = CROSS(tvec,edge1);

	v = DOT(d,qvec);

	if(u < 0.0f&#0124;&#0124;u > det)
		return false;
	if(v < 0.0f&#0124;&#0124;u+v >det)
		return false;
	return true;
}

Hi,

Here what I do

 // Intersects the triangle with the line 
        // returns true only if the line both intersects the plane of the triangle
        //  and is inside of the triangle
        bool Intersect( const Ray<T>&  _ln,
                        VecType&       _dest) const
        {
            return IntersectTrianglePlane(_ln, _dest) && IsPointInside(_dest);
        }


        // Intersects the plane of the triangle with the line
        bool IntersectTrianglePlane( const Ray<T>& _ln, 
                                     VecType&      _dest ) const
        {
            VecType nm = Normal().unit();
            T val = nm*_ln.Dir();
            if (val == T(0.0) )
            {
                return false;
            }

            // line : a+b*t , plane = NM*(x-p0)=0
            // therefore, NM*(a+b*t-p0) = 0 or t = NM*(a-p0)/(NM*b).
            T t = (nm*(m_points[0]-_ln.Origin()))/val;
            _dest = _ln.PointOnRay(t);
            return true;
        }

 // checks if point ON THE PLANE is inside of the triangle
        bool IsPointInside(const VecType& _pt) const
        {
            return IsSameSide(_pt, m_points[2], m_points[0], m_points[1]) &&
                   IsSameSide(_pt, m_points[0], m_points[1], m_points[2]) &&
                   IsSameSide(_pt, m_points[1], m_points[2], m_points[0]);
        }

 // Returns true if p1 and p2 are on the sime side
        // relative to line a-->b
        static bool IsSameSide( const VecType& _p1, 
                                const VecType& _p2,
                                const VecType& _a, 
                                const VecType& _b   )
        {
            VecType tmp = _b-_a;
            return ((_p1-_a)^tmp).dot((_p2-_a)^tmp) >= T(0.0);
        }

The code is templated but easy to understand.
Hope it helps

Hmmm even with this approach i’m getting the same thing. Something fish though, the triangle i’m testing against has the points 1(-2.0f,0.0f,-2.0f) 2(2.0f,0.0f,-2.0f) and 3(0.0f,2.0f,-2.0f). with that it gets collisions through most of the triangle, but not along two sides. if i move the third vertex to (0.0f,1.0f,-2.0f) though, it works fine. Like i said i’m not much of a math wiz but that seemed kind of strange to me… any ideas?

Ok i’m going to post every little bit of code i’m now using… I know its pretty sloppy i’ll go tidy it up after i post, i just wanted help asap

   
bool intersect(vert origin, vert direction, vert v1, vert v2, vert v3)
{
    vert edge1, edge2, triangleNormal, collision;
    float d, det;

    edge1 = v1-v2;
    edge2 = v1-v3;

    triangleNormal = CROSS(edge1,edge2);

    d = DOT(edge1,edg2);

    det = DOT(triangleNormal,direction);

    if(det < EPSILON && det > -EPSILON)
         return false;
    
    float t = (d-DOT(triangleNormal,origin))/(DOT(triangleNormal,direction));
 
collision = origin + (t*direction);

    if(!PointInTriangle(collision,v1,v2,v3))
        return false;

    return true;
}

inline bool PointInTriangle(vert t,vert a, vert b, vert c)
{
	if(SameSide(t,a,c,b) && SameSide(t,b,c,a) && SameSide(t,c,b,a))
		return true;
	return false;
}
inline bool SameSide(vert testAgainst,vert testing,vert A,vert B)
{
	vert cp1, cp2;
	vert BMA,temp; //sorry about the ambiguity
	SU(BMA,B,A);   //and temps, i'll go make operators as soon as i post this :/
	SU(temp,testAgainst,A);
	CROSS(cp1,BMA,temp);
	SU(temp,testing,A);
	CROSS(cp2,BMA,temp);

	if(DOT(cp1,cp2) >=0)
		return true;
	return false;
}
 

And here are the SU DOT and CROSS macros

#define EPSILON 0.0001
#define CROSS(dest,v1,v2) \
          dest.x=(v1.y*v2.z)-(v1.z*v2.y); \
          dest.y=(v1.z*v2.x)-(v1.x*v2.z); \
          dest.z=(v1.x*v2.y)-(v1.y*v2.x);
#define DOT(v1,v2) (v1.x*v2.x+v1.y*v2.y+v1.z*v2.z)
#define SU(dest,v1,v2) \
          dest.x=v1.x-v2.x; \
          dest.y=v1.y-v2.y; \
          dest.z=v1.z-v2.z; 

I think i’ve been making a stupid mistake… You have the origin of the ray (O), and the direction (D), if O is lets say (5,5,5), and D is (1,0,0), does that mean the ray is going from the point (5,5,5) to the point (1,0,0), or from the point (5,5,5) to the point (6,5,5) ?

Originally posted by GbenderL:
I think i’ve been making a stupid mistake… You have the origin of the ray (O), and the direction (D), if O is lets say (5,5,5), and D is (1,0,0), does that mean the ray is going from the point (5,5,5) to the point (1,0,0), or from the point (5,5,5) to the point (6,5,5) ?
Saying it goes from one point to another is a bit misleading. A ray is infinite and has no end point.

In the case you described, the ray is going from point (5, 5, 5) in the direction of (1, 0, 0). So it will go through point (6, 5, 5) and continue infinitely.