[SOLVED] Ray - Triangle Intersection

That function doesn't do any triangle boundary check. It just gives you the point of intersection in the plane of the triangle.

There are many algorithms available for checking if a point is in the triangle boundary or not. The simplest to understand is the convex subdivision. Check the sign of the point of intersection against the edge planes. If the point is on the same side of all those planes, the point is inside the triangle.

The basic ray-plane intersection algo is the one you have.

What you need to do after that, is to check if the intersection point is inside the boundaries of the triangle.

This also depends on your polygon winding order (clockwise, counter-clockwise), and if you care about back-sided polygons intersections or not. This (untested) pseudo-code below 'should be' for double-sided polygons, any winding order.

struct Triangle { v[3] };
struct Ray { Vector start, dir; };

bool RayTriangleIntersect(Ray ray, Triangle tri, ref Vector i)
{
    // triangle normal (not a unit vector).
    Vector n = (tri.v[1] - tri.v[0]).cross(tri.v[2] - tri.v[0]);

    // line-plane intersection quantities.
    float numer = (ray.start - tri.v[0]) .dot(n);
    float denom = ray.dir.dot(n);

    // ray parallel to plane. (Ambiguous result!)
    if(fabs(denom) < 1.0E-8f) return false;

    // parametric ray-plane intersection result.
    float t = -numer / denom;

    // plane behind the ray.
    if(t < 0.0f) return false;

    // interection point on triangle plane.
    i = ray.start + ray.dir * t;

    
    // detect the winding order of the polygon.
    bool winding;

    // check if intersection point is inside the triangle boundaries. 
    for(int ip1 = 0, i = 2; ip1 < 3; i=ip1, ++ip1)
    {
        // edge of the triangle.
        Vector e = (tri.v[ip1] - tri.v[i]); 
        
        // edge normal. perpendicular to edge direction, and also triangle plane normal.
        Vector en = e.cross(n); 

        // position of  point 'i' relative to edge plane. Either above or below the edge plane.
        bool sign = ((i - tri.v[i]).dot(en) >= 0.0f); 

        // defines our initial polygon winding order. Either clockwise, or counter-clockwise.
        if(ip1 == 0) winding = sign;

        // point contradict winding order. it's outside. 
        if(sign != winding)
            return false;
    }
    return true;
}

the point 'i' is inside the polygon is it is either, outside ALL the edges of the polygon, or inside ALL the edges of the polygon. As soon as an edge test contradicts the other edges, the point is found to be outside.

Ok, thanks! Is that Möller–Trumbore algo? Isn't that the fastest?

Edit: fixed it, couldn't get MT to work so I did it like this:

	public static Vector3f intersectRayTriangle(Vector3f start, Vector3f dir, Triangle tri) {
		Vector3f u = new Vector3f(tri.points[1]);
		Vector3f.sub(u, tri.points[0], u);

		Vector3f v = new Vector3f(tri.points[2]);
		Vector3f.sub(v, tri.points[0], v);

		Vector3f n = new Vector3f();
		Vector3f.cross(u, v, n);

		if (n.length() == 0) {
			return null;
		}

		Vector3f w = new Vector3f(start);
		Vector3f.sub(w, tri.points[0], w);

		float a = -Vector3f.dot(n, w);
		float b = Vector3f.dot(n, dir);

		if ((float) Math.abs(b) < SMALL_NUM) {
			return null;
		}

		float r = a / b;

		if (r < 0.0) {
			return null;
		}

		Vector3f i = new Vector3f(start);
		i.x += r * dir.x;
		i.y += r * dir.y;
		i.z += r * dir.z;

		float uu, uv, vv, wu, wv, D;

		uu = Vector3f.dot(u,u);
		uv = Vector3f.dot(u,v);
		vv = Vector3f.dot(v,v);

		Vector3f.sub(i, tri.points[0], w);

		wu = Vector3f.dot(w,u);
		wv = Vector3f.dot(w,v);

		D = uv * uv - uu * vv;

		float s, t;

		s = (uv * wv - vv * wu) / D;
		if (s < 0.0 || s > 1.0) {
			return null;
		}

		t = (uv * wu - uu * wv) / D;
		if (t < 0.0 || (s + t) > 1.0) {
			return null;
		}

		return i;
	}

Yeah, I'd go with Möller–Trumbore. It's a pretty slick algo. If this above works (looks OK to me), then just go with that.