version 1.7 (309 KB) by
Jaroslaw Tuszynski

Fast vectorized triangle/ray intersection algorithm

Ray/triangle intersection using the algorithm proposed by Möller and

Trumbore (1997), implemented as highly vectorized MATLAB code.

The algorithm can work with one and two sided surfaces, as well as, with

infinite lines, rays (lines bounded on one side) and segments (lines bounded on

both sides).

Input (all arrays in in Nx3, where N is number of vertices or rays):

orig : ray's origin

dir : ray's direction

vert0, vert1, vert2: vertices of the triangle

Output:

Intersect - boolean array of length N

t - distance from the ray origin to the intersection point in |dir|

u,v - barycentric coordinates of the intersection point units

xcoor - carthesian coordinates of the intersection point

In addition PointInsideVolume is 3D equivalent to 2D inpolygon function and can test if

array of points is inside or outside any volume defined by the surface grid.

Jaroslaw Tuszynski (2021). Triangle/Ray Intersection (https://www.mathworks.com/matlabcentral/fileexchange/33073-triangle-ray-intersection), MATLAB Central File Exchange. Retrieved .

Created with
R2017b

Compatible with any release

**Inspired by:**
Ray/Triangle Intersection

**Inspired:**
in_polyhedron, RayShapeArticle_FEX.zip

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

Stefan WamplFrancesco SturlaHi! does anyone know a code that overcomes the limit discussed above (total number of triangles different than total ray number)?

Berk BuralIt doesn't work when total triangle number in mesh is different than total ray number. Therefore it has limited usage.

KonradEmile TalonHi, I am trying to use this code in order to obtain thickness information of my 3D object.

I select a triangle on my mesh, and then place the origin of the ray along the normal to the baricentrum of my selected triangle.

The ray is then going to intersect my mesh first in the defined triangle and then in a second one.

How could I get the second triangle as an output of the function? And therefore the distance between this two traingles (and so the thickness of my object).

Any help would be really appreciated.

Yasaman MoghadamniaWorks perfectly for a ray! What sort of modification would you suggest for a line segment?

Bernard BeitzThere seems to be some confusion about the many-to-many case. If you have n rays and triangles, the function will test the k-th ray against the k-th triangle, but it will not test the k-th ray against every n triangles. So there are n intersection tests, not n^2. That's why you need to have as many rays as triangles in the many-to-many case. The one-to-many case is just treated as a special case of many-to-many where all n rays/triangles happen to be the identical.

SJTULudovic BretonHi, I too have the same question about the many rays/many faces. It doesn't seem to work, or maybe am I using it the wrong way. I'm trying to find whether the rays intersect a triangle on a segment going from the origin to each of the triangles in the scene.

Here's the code :

%% cube definition

Vertices=[0,0,0;1,0,0;1,0,1;0,0,1;0,1,0;1,1,0;1,1,1;0,1,1];

Faces=[2,4,1;2,3,4;2,6,3;3,6,7;5,7,6;5,8,7;1,4,8;1,8,5;1,6,2;1,5,6;3,7,4;4,7,8];

p0=Vertices(Faces(:,1),:);

p1=Vertices(Faces(:,2),:);

p2=Vertices(Faces(:,3),:);

%% Computation

CG=(p0+p1+p2)./3;

origin=[2 3 2];

direction=1.*(CG-repmat(+origin,size(Faces,1),1));

[intersect, t,u,v,xcoord] = TriangleRayIntersection(origin, direction, p0, p1, p2, 'lineType', 'segment','planeType','two sided','fullReturn', true);

%% we draw the figure

quiver3(repmat(origin(1),12,1),repmat(origin(2),12,1),repmat(origin(3),12,1),direction(:,1),direction(:,2),direction(:,3));

patch('Faces',Faces,'Vertices', Vertices,'FaceColor','m','FaceAlpha',0.8)

N=cross(p1-p0,p2-p0)/(norm(p1-p0)*norm(p2-p0));

text(CG(:,1)+.2*N(:,1)/norm(N(:,1)), CG(:,2)+.2*N(:,2)/norm(N(:,2)), CG(:,3)+.2*N(:,3)/norm(N(:,3)), num2str((1:12)'));

By changing the scalar (e.g. 1 or 0.99) in front of "direction" I get either only ones or zeros for the value of intersect.

Jun WHi, in your first example Line 86-100 in 'TriangleRayIntersection_tutorial.m', you get 4 intersections, but 43 distances 't'. Aren't we supposed to get only 4 distances for the 4 intersections?

John HussI also agree with the previous comments. I can't get the many faces/many rays version to work. I have a complex stl surface consisting of approximately 25,000 triangles and a set of 400 rays that all start inside the model and go outwards. It says only 13 of them intersect, which is not correct. Any tips? I might try to loop through all rays one at a time instead.

Stuart ScollayHi, thanks for the code. I want to second Andre's comment. I too am having trouble getting the many rays, many faces implementation working.

Andre PaixaoHi, Jaroslaw. Thanks for this very useful tool! I'm trying to find the intersection of many (M) rays in many faces of closed triangular meshes made of N>400000 vertices (with M<N).

The tool works great if I search for one ray at a time in a for loop, though it takes quite a while to go through all my rays.

To make it faster, I've been trying to run many rays at once but the function returns empty all the time (no intersections detected), which is weird. And yes, I'm using repmat to clone the rays until M=N and all the input are in Nx3 format.

However, it works well If I consider the rays passing through the centre of each triangle, as in your example.

I see comments from other users also struggling with the many rays-many faces option.

Can you help? Thks

Philip KunzFabricio CastroJaroslaw TuszynskiReply to jack' green: I think you should be able to find much simpler codes to do 2D case. Or just write one to do line/line intersection for ray intersection with each line segment and see if the intersection point is between each segment end points.

jack' greenHi, Jaroslaw. Thanks for provding such a cool tool. It works well on my computer. Just wonder is it possible to apply it to a purely 2D (in-plane) case where the triangles all become segments?

Yanjun Hanmany faces / many rays intersection, the return value 'flag'? Should it be a matrix but actual it is not.

Yanjun HanHello, Can anyone help me! Now I have a series of path points, and I want project them on a specified mesh surface along the specified direction, for example dir=(0,0,1). For every path point, I can iterate over all the triangular meshes to get the corresponding projection points，but this is too time-consuming. Can I use a faster method？

I want to get the projection point of all the points in the fixed direction on the triangular mesh surface. How can I use the 'many faces / many rays intersection' ?

Ander BiguriDoes the many rays-many faces case only work with Nfaces==Nrays? If so, is there any specific reason for implementing that specific case?

Yumin SunActually for multiple faces and multiple rays, one should remember you need to repmat origin, if all origins are same.

Leonardo ColavittiIgorTo do your program better I suggests

1) Add description about use option FullReturn. It shold be '1' but not 'true' for example.

2) Add in initialize default output string

xcoor=zeros(size(orig));

If xcoor not initialized than if no intersections error appear with params count.

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

Jaroslaw TuszynskiReply to Murat: You might have to look into using "border" parameter. If it does not work can you construct a scenario that demonstrates the issue and email it to me

MuratHi, the code is working well but it sometimes cannot handle with large incident angles. When the incident angle is around 90, it ignores triangles. Could you correct it?

Ehsan golkJeffreyI'm having trouble with the many rays, many faces option. Lets say I have 11 faces and 5 rays. What resizing of the inputs needs to be done? Do I need to repmat all arrays to be of size 55x3?

Based on what I can tell it can handle:

- one ray, many faces

- many rays, one face

- many rays, many faces (but # of faces = # of rays)

But I think I am just missing something here.

Jaroslaw TuszynskiReply to Nick: In many rays and many triangle case you still test for intersection of prearranged pairs and the return value informs you which ray/triangle pair intersected

NickVery useful but when considering many rays and many triangles is there a way to find which ray has intersected which triangle?

NickAmilcar TorresExcellent.. Really helpful!!!

BenLooks great. Downloaded and will try it later.

Jaroslaw TuszynskiRe to Anton Semechko: This is a low level function which can be called with one ray and many faces, many faces and one ray or many faces and rays. It is quite simple to apply repmat function to the inputs.

Anton Semechkowhy does the number of rays have to equal the number of faces? that's so inconvenient