Hi,
Edit: This actually works just fine. Rays don’t end at their magnitude, so of course this would return true.
Enclosed is a photo of a ray and a triangle. The ray does not visibly intersect the triangle. But according to every triangle intersection algorithm I can find, it does.
This one’s stumped me for an entire weekend and now I’m pissed. Normally when someone gets an algorithm that won’t work right, simply changing the algorithm or copying and pasting in some else’s algorithm is all you have to do. Then, look for differences, and figure out where yours went wrong.
Not this time.
This is a simple triangle intersection algorithm I’ve changed over and over. I’ve googled the hell out of this, and modified several others’ algorithms (see below) with my data. I have looked over other forum threads, and others’ source code, which is where I got the original versions of some of this code.
Basically, they all seems to work right for many triangles and rays, but occasionally they all get stumped on one. This particular one (and some variations on it) are always “wrong”, and it’s driving me nuts. I put wrong in quotes because clearly it’s doing what I’m telling it to do, it’s just that the results aren’t what I want.
For the sake of convenience, I have added all necessary code here so you can copy and paste it into a project and see it fail for yourself. In every case below, it’s checking to see if the ray intersects the triangle, and in every case, it returns ‘true’. It should be false.
Please help, I’m at the end of my rope, and I’m pretty sure this rope doesn’t intersect a triangle either.
-Chilton
bool BetweenTriangleAndRay()
{
//ref Vector3 p1, ref Vector3 p2, ref Vector3 p3, ref Vector3 rayForward, ref Vector3 rayOrigin
Vector3 rayOrigin = new Vector3(1,0,0);
Vector3 rayForward = new Vector3(0,2,0);
//Ray ray = new Ray(P0,P1);
Vector3 p1 = new Vector3(3, 2.3f, -4);
Vector3 p2 = new Vector3(-7, 2.3f, 2);
Vector3 p3 = new Vector3(3, 2.3f, 2);
Debug.DrawLine(rayOrigin,rayForward, Color.red, 10);
Debug.DrawLine(p1, p2, Color.blue, 10);
Debug.DrawLine(p2, p3, Color.blue, 10);
Debug.DrawLine(p3, p1, Color.blue, 10);
//Find vectors for two edges sharing vertex/point p1
var e1 = p2 - p1;
var e2 = p3 - p1;
// calculating determinant
var p = Vector3.Cross( rayForward, e2);
//Calculate determinat
var det = Vector3.Dot( e1, p);
//if determinant is near zero, ray lies in plane of triangle otherwise not
if (det > -0.000001f && det < 0.000001f) { return false; }
var invDet = 1.0f / det;
//calculate distance from p1 to ray origin
var t = rayOrigin - p1;
//Calculate u parameter
var u = Vector3.Dot( t, p) * invDet;
//Check for ray hit
if (u < 0 || u > 1) { return false; }
//Prepare to test v parameter
var q = Vector3.Cross( t, e1);
//Calculate v parameter
var v = Vector3.Dot( rayForward, q) * invDet;
//Check for ray hit
if (v < 0 || u + v > 1) return false;
if ((Vector3.Dot(e2, q) * invDet) > 0.000001)
{
//ray does intersect
return true;
}
// No hit at all
return false;
}
Another attempt, found this algorithm in another place, adapted it for the same test…
public static bool Intersect()
{
Vector3 P0 = new Vector3(1,0,0);
Vector3 P1 = new Vector3(0,2,0);
Ray ray = new Ray(P0,P1);
Vector3 p1 = new Vector3(3, 2.3f, -4);
Vector3 p2 = new Vector3(-7, 2.3f, 2);
Vector3 p3 = new Vector3(3, 2.3f, 2);
// Vectors from p1 to p2/p3 (edges)
Vector3 e1, e2;
Vector3 p, q, t;
float det, invDet, u, v;
//Find vectors for two edges sharing vertex/point p1
e1 = p2 - p1;
e2 = p3 - p1;
// calculating determinant
p = Vector3.Cross(ray.direction, e2);
//Calculate determinat
det = Vector3.Dot(e1, p);
//if determinant is near zero, ray lies in plane of triangle otherwise not
if (det > -Mathf.Epsilon && det < Mathf.Epsilon) { return false; }
invDet = 1.0f / det;
//calculate distance from p1 to ray origin
t = ray.origin - p1;
//Calculate u parameter
u = Vector3.Dot(t, p) * invDet;
//Check for ray hit
if (u < 0 || u > 1) { return false; }
//Prepare to test v parameter
q = Vector3.Cross(t, e1);
//Calculate v parameter
v = Vector3.Dot(ray.direction, q) * invDet;
//Check for ray hit
if (v < 0 || u + v > 1) { return false; }
if ((Vector3.Dot(e2, q) * invDet) > Mathf.Epsilon)
{
//ray does intersect
return true;
}
// No hit at all
return false;
}
… and one more attempt, another algorithm adapted, slightly different input, same result…
int intersect3D_RayTriangle()
{
Vector3 P0 = new Vector3(0,0,0);
Vector3 P1 = new Vector3(0,1,0);
Vector3 V0 = new Vector3(3, 2.3f, -4);
Vector3 V1 = new Vector3(-7, 2.3f, 2);
Vector3 V2 = new Vector3(3, 2.3f, 2);
Debug.DrawLine(P0,P1, Color.red, 10);
Debug.DrawLine(V0, V1, Color.blue, 10);
Debug.DrawLine(V1, V2, Color.blue, 10);
Debug.DrawLine(V2, V0, Color.blue, 10);
Vector3 I;
Vector3 u, v, n; // triangle vectors
Vector3 dir, w0, w; // ray vectors
float r, a, b; // params to calc ray-plane intersect
// get triangle edge vectors and plane normal
u = V1 - V0;
v = V2 - V0;
n = Vector3.Cross(u, v); // cross product
if (n == Vector3.zero) // triangle is degenerate
return -1; // do not deal with this case
dir = P1 - P0; // ray direction vector
w0 = P0 - V0;
a = -Vector3.Dot(n,w0);
b = Vector3.Dot(n,dir);
if (Mathf.Abs(b) < .00001f) { // ray is parallel to triangle plane
if (a == 0) // ray lies in triangle plane
return 2;
else return 0; // ray disjoint from plane
}
// get intersect point of ray with triangle plane
r = a / b;
if (r < 0.0) // ray goes away from triangle
return 0; // => no intersect
// for a segment, also test if (r > 1.0) => no intersect
I = P0 + r * dir; // intersect point of ray and plane
// is I inside T?
float uu, uv, vv, wu, wv, D;
uu = Vector3.Dot(u,u);
uv = Vector3.Dot(u,v);
vv = Vector3.Dot(v,v);
w = I - V0;
wu = Vector3.Dot(w,u);
wv = Vector3.Dot(w,v);
D = uv * uv - uu * vv;
// get and test parametric coords
float s, t;
s = (uv * wv - vv * wu) / D;
if (s < 0.0 || s > 1.0) // I is outside T
return 0;
t = (uv * wu - uu * wv) / D;
if (t < 0.0 || (s + t) > 1.0) // I is outside T
return 0;
return 1; // I is in T
}
