Ray/triangle intersection using the algorithm proposed by Möller and Trumbore (1997)
Ray/triangle intersection using the algorithm proposed by Möller and Trumbore (1997). The zip file includes one example of intersection.
References:
[1] "Real Time Rendering". Third Edition.
Tomas Akenine-Möller, Eric Haines and Naty Hoffman.
A. K. Peters, Ltd. 2008 (Section 16.8)
[2] "Fast, minimum storage ray-triangle intersection".
Tomas Möller and Ben Trumbore.
Journal of Graphics Tools, 2(1):21--28, 1997.
[3] Other algorithms:
http://www.realtimerendering.com/intersections.html
Inspired: Ray/box Intersection, A fast voxel traversal algorithm for ray tracing, Hardware accelerated ray-triangle intersection, Triangle/Ray Intersection
Tibor Ádám (view profile)
Thank you!
Jamie Heather (view profile)
Nice vectorised implementation with handy options for choosing between ray/line/segments and handling numerical precision issues - thanks!
mirshad (view profile)
the code is ok...
i have a mistake.thank u
mirshad (view profile)
magnitude==andaze
i changed it formerly.
mirshad (view profile)
tnx.this code, give me a incorrect response for this inputs;
LINE = [0 0 1 1 1 2 ];
tri = [0 0 5;5 0 0;0 5 0;0 0 5];
magnitude=sqrt((LINE(4)-LINE(1))^2+(LINE(5)-LINE(2))^2+(LINE(6)-LINE(3))^2);
direction=[LINE(4)-LINE(1)/andaze LINE(5)-LINE(2)/andaze LINE(6)-LINE(3)/andaze];
direction=[LINE(4)-LINE(1)/andaze LINE(5)-LINE(2)/andaze LINE(6)-LINE(3)/andaze];
rayTriangleIntersection(LINE(1:3),direction,tri(1,:),tri(2,:),tri(3,:))
Kapil Dev (view profile)
Thank you very much. Really very useful piece of code.
dberm22 (view profile)
Works great, but too slow for what I needed. Mostly not your fault, but I needed to call this function more than a million times, and the built-in matlab routines you called were weighing it down.
I took your code and sped it up. for my test with 90,000 calls, it takes your function 16s, and mine only takes 1.5. That's a speedup of 10x! Here's what I have:
function [flag, u, v, t] = fastRayTriangleIntersection (o, d, p0, p1, p2)
% Ray/triangle intersection using the algorithm proposed by Möller and Trumbore (1997).
%
% Input:
% o : origin.
% d : direction.
% p0, p1, p2: vertices of the triangle.
% Output:
% flag: (0) Reject, (1) Intersect.
% u,v: barycentric coordinates.
% t: distance from the ray origin.
% Author:
% Originally written by Jesus Mena, edited by David Berman (dberm22@gmail.com)
epsilon = 0.00001;
e1 = p1-p0;
e2 = p2-p0;
q = [d(2)*e2(3)-d(3)*e2(2), d(3)*e2(1)-d(1)*e2(3), d(1)*e2(2)-d(2)*e2(1)]; %cross product
a = e1(1)*q(1)+e1(2)*q(2)+e1(3)*q(3); % determinant of the matrix M
if (a>-epsilon && a<epsilon)
% the vector is parallel to the plane (the intersection is at infinity)
flag=0;
u=0;
v=0;
t=0;
return;
end;
f = 1/a;
s = o-p0;
u = f*(s(1)*q(1)+s(2)*q(2)+s(3)*q(3));
if (u<0.0)
% the intersection is outside of the triangle
flag=0;
u=0;
v=0;
t=0;
return;
end;
r = [s(2)*e1(3)-s(3)*e1(2), s(3)*e1(1)-s(1)*e1(3), s(1)*e1(2)-s(2)*e1(1)];
v = f*(d(1)*r(1)+d(2)*r(2)+d(3)*r(3));
if (v<0.0 || u+v>1.0)
% the intersection is outside of the triangle
flag=0;
u=0;
v=0;
t=0;
return;
end;
t = f*(e2(1)*r(1)+e2(2)*r(2)+e2(3)*r(3)); % verified!
flag = 1;
return;
end
Thanks for the basis!
dberm22 (view profile)
Works great, but too slow for what I needed. Mostly not your fault, but I needed to call this function more than a million times, and the built-in matlab routines you called were weighing it down.
I took your code and sped it up. for my test with 90,000 calls, it takes your function 16s, and mine only takes 2. That's a speedup of 8x! Here's what I have:
function [flag, u, v, t] = fastRayTriangleIntersection (o, d, p0, p1, p2)
% Ray/triangle intersection using the algorithm proposed by Möller and Trumbore (1997).
%
% Input:
% IMPORTANT: ALL INPUTS NEED TO BE 3 ELEMENT ROW VECTORS
% o : origin.
% d : direction.
% p0, p1, p2: vertices of the triangle.
% Output:
% flag: (0) Reject, (1) Intersect.
% u,v: barycentric coordinates.
% t: distance from the ray origin.
% Author:
% Originally written by Jesus Mena, edited by David Berman (dberm22@gmail.com)
epsilon = 0.00001;
e1 = p1-p0;
e2 = p2-p0;
q = [d(2)*e2(3)-d(3)*e2(2), d(3)*e2(1)-d(1)*e2(3), d(1)*e2(2)-d(2)*e2(1)]; %cross product
a = e1*q'; % determinant of the matrix M
if (a>-epsilon && a<epsilon)
% the vector is parallel to the plane (the intersection is at infinity)
flag=0;
u=0;
v=0;
t=0;
return;
end;
f = 1/a;
s = o-p0;
u = f*s*q';
if (u<0.0)
% the intersection is outside of the triangle
flag=0;
u=0;
v=0;
t=0;
return;
end;
r = [s(2)*e1(3)-s(3)*e1(2), s(3)*e1(1)-s(1)*e1(3), s(1)*e1(2)-s(2)*e1(1)];
v = f*d*r';
if (v<0.0 || u+v>1.0)
% the intersection is outside of the triangle
flag=0;
u=0;
v=0;
t=0;
return;
end;
t = f*e2*r'; % verified!
flag = 1;
return;
end
Only caveat is that all inputs need to be 3 element ROW vectors, and there is absolutely no error checking. If you can live with that, then this will do it!
Thanks for the basis!
Alexander (view profile)
Thank you! I found this to be very useful! Thanks also to Wouter for the suggestion of using "sum" and an own "cross" function. I can't confirm factor 10, but factor 3 isn't so bad as well!
zf (view profile)
HARI KRISHNAN (view profile)
Alec (view profile)
Sunghun Jung (view profile)
Thank you vey much for this useful file.
Btw, could anyone give me a tip how to calculate the direction vector if I have two 3 dimensional nodes?
Wouter (view profile)
Excellent, it helped me a lot.
You can speed this function up considerably by not using the Matlab functions cross and dot, these are unnecessarily slow. Make your own cross product function, and use "sum(a.*b)" instead of "dot(a,b), and it'll will be at least a factor 10 faster.
Christian (view profile)