File Exchange

image thumbnail

Ray/Triangle Intersection

version 1.0 (13.4 KB) by

Ray/triangle intersection using the algorithm proposed by Möller and Trumbore (1997)

4.45455
12 Ratings

15 Downloads

Updated

View License

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

Comments and Ratings (15)

Tibor Ádám

Thank you!

Jamie Heather

Nice vectorised implementation with handy options for choosing between ray/line/segments and handling numerical precision issues - thanks!

mirshad

the code is ok...
i have a mistake.thank u

mirshad

magnitude==andaze
i changed it formerly.

mirshad

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

Thank you very much. Really very useful piece of code.

dberm22

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

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

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

zf (view profile)

HARI KRISHNAN

Alec

Alec (view profile)

Sunghun Jung

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

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

MATLAB Release
MATLAB 7.6 (R2008a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

rayTriangleIntersection/