Hit point for Moller / Trumbore Triangle Intersection

Hello,

I am currently working on my own raycasting system that not only works in other threads, but also allows me to raycast in my custom coordinates system for my open world.

As the title suggests, I am using the Moller-Trumbore triangle intersection algorithm to check if the ray hits. Now I am stuck at figuring out how to get the actual hit point and normal of the hit triangle. The code I am using is from here http://answers.unity3d.com/questions/861719/a-fast-triangle-triangle-intersection-algorithm-fo.html :

Code (CSharp):

1.         public static bool Intersect(Vector3 p1, Vector3 p2, Vector3 p3, TWRay ray)
2.         {
3.    
4.             // Vectors from p1 to p2/p3 (edges)
5.             //Find vectors for edges sharing vertex/point p1
6.             Vector3 e1 = p2 - p1;
7.             Vector3 e2 = p3 - p1;
8.        
9.             // Calculate determinant
10.             Vector3 p = Vector3.Cross(ray.direction, e2);
11.        
12.             //Calculate determinat
13.             float det = Vector3.Dot(e1, p);
14.        
15.             //if determinant is near zero, ray lies in plane of triangle otherwise not
16.             if (det > -Mathf.Epsilon && det < Mathf.Epsilon) { return false; }
17.             float invDet = 1.0f / det;
18.        
19.             //calculate distance from p1 to ray origin
20.             Vector3 t = ray.origin - p1;
21.        
22.             //Calculate u parameter
23.             float u = Vector3.Dot(t, p) * invDet;
24.        
25.             //Check for ray hit
26.             if (u < 0 || u > 1) { return false; }
27.        
28.             //Prepare to test v parameter
29.             Vector3 q = Vector3.Cross(t, e1);
30.        
31.             //Calculate v parameter
32.             float v = Vector3.Dot(ray.direction, q) * invDet;
33.        
34.             //Check for ray hit
35.             if (v < 0 || u + v > 1) { return false; }
36.        
37.             if ((Vector3.Dot(e2, q) * invDet) > Mathf.Epsilon){
38.                 //ray does intersect
39.                 return true;
40.             }
41.        
42.             // No hit at all
43.             return false;
44.         }

Can you show me how its done? Thank you very much in advance!

 

I'm pretty sure that algorithm you posted takes the three points of a triangle and a Ray your casting. So naively your sending it the 3 Vector3 positions of every triangle on your scene and it returns true or false if that ray hits that triangle. So of course you know the triangle your sending into the algorithm.

To be more clear when you get triangles[] array of a mesh
triangles[x] = index of a Vertex in the vertices array
triangles[0], triangles[1], triangles[2] are the indexes into the vertices area to get the first 3 Vector3 that form triangle 1

And you call your function above with this:

Code (CSharp):

1. bool hit = Intersect(vertices[triangles[0]], vertices[triangles[1]],vertices[triangles[2]], yourRay);

So you are guaranteed to know which triangle that ray hit, because you passed the triangle in. The hard part of this is figuring out some culling method based on your ray to exclude triangles in your scene that are impossible to be hit. Which sadly is beyond the scope of my knowledge. You certainly don't want to iterate over every triangle of every mesh in your scene.

 

Yes, you are right, it takes the three vertex of a triangle and thats how it works.

The culling method was the easy part, I've already done that. Before the ray is tested at all, my framework makes a collection of Objects that are within a certain range and within a certain angle from the rays direction and I also can filter Objects on various other criteria than just layermask. So in the end I have a narrowed list of possible Objects that the ray can hit. The geometry I pass through this algorithm is also kept simple like bounding / convex hulls meshes.

As you said, getting a triangle is not my problem, but I have trouble getting the exact intersection point. My brain is trying to understand barycentric math and fails to assamble a working piece of code out of it.

 

ah was confused.. Any particular reason you need the exact hit point of the triangle, rather than just knowing it hit a specific triangle. Though as far as getting the normal of that triangle if you know V1, V2 and V3 then:

E1 = V2-V1
E2 = V3-V1
And the Normal is N and * is the Dot Product then:
N(x) = E1(y)*E2(z)-E1(Z)*E2(y)
N(y) = E1(z)*E2(x)-E1(x)*E2(z)
N(z) = E1(x)*E2(y)-E1(y)*E2(x)

Reading up on barycentric co-ordinates, I believe your intersection point is:
P = A + u(p2-p1) +v(p3-p1)

Thus you could modify the code to look like this:

Code (CSharp):

1. public static bool Intersect(Vector3 p1, Vector3 p2, Vector3 p3, TWRay ray, ref Vector3 hit)
2.         {
3.  
4.             // Vectors from p1 to p2/p3 (edges)
5.             //Find vectors for edges sharing vertex/point p1
6.             Vector3 e1 = p2 - p1;
7.             Vector3 e2 = p3 - p1;
8.      
9.             // Calculate determinant
10.             Vector3 p = Vector3.Cross(ray.direction, e2);
11.      
12.             //Calculate determinat
13.             float det = Vector3.Dot(e1, p);
14.      
15.             //if determinant is near zero, ray lies in plane of triangle otherwise not
16.             if (det > -Mathf.Epsilon && det < Mathf.Epsilon) { return false; }
17.             float invDet = 1.0f / det;
18.      
19.             //calculate distance from p1 to ray origin
20.             Vector3 t = ray.origin - p1;
21.      
22.             //Calculate u parameter
23.             float u = Vector3.Dot(t, p) * invDet;
24.      
25.             //Check for ray hit
26.             if (u < 0 || u > 1) { return false; }
27.      
28.             //Prepare to test v parameter
29.             Vector3 q = Vector3.Cross(t, e1);
30.      
31.             //Calculate v parameter
32.             float v = Vector3.Dot(ray.direction, q) * invDet;
33.      
34.             //Check for ray hit
35.             if (v < 0 || u + v > 1) { return false; }
36.      
37.             // New code here
38.             // fill in our intersection point
39.             hit  = p1 + u*e1 + v*e2;
40.  
41.             if ((Vector3.Dot(e2, q) * invDet) > Mathf.Epsilon){
42.                 //ray does intersect
43.                 return true;
44.             }
45.      
46.             // No hit at all
47.             return false;
48.         }

Note you still need to check if Intersection is true/false if its false the hit ref will be invalid. but if its true then hit will contain your intersection point

 

Awesome! Thank you very much! For example I need the exact location to place particle effects like explosions at the point where the weapon hits the Objects collider - just the triangle center wouldnt do much good as my colliders can be quite large depending on the Objects size - and I cant do it with Unitys API since its not thread-safe. And there are other reasons for me to implement a custom raycasting system besides that.

Checking for the intersection first shouldn't be a problem, just doing the math before the method returns true.