Code covered by the BSD License  

Highlights from
Ray/Triangle Intersection

4.25

4.2 | 9 ratings Rate this file 44 Downloads (last 30 days) File Size: 13.4 KB File ID: #25058
image thumbnail

Ray/Triangle Intersection

by

 

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

| Watch this File

File Information
Description

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

Acknowledgements

This file inspired Ray Shape Article Fex.Zip, Ray/Box Intersection, A Fast Voxel Traversal Algorithm For Ray Tracing, and Triangle/Ray Intersection.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (9)
19 Dec 2014 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!

19 Dec 2014 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!

06 Jun 2013 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!

06 Jun 2012 zf  
23 Jun 2011 HARI KRISHNAN  
07 May 2011 Alec  
16 Oct 2010 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?

30 Aug 2010 Wouter

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.

21 Oct 2009 Christian  

Contact us