File Exchange

image thumbnail

Triangle/Ray Intersection

version 1.5 (211 KB) by

Fast vectorized triangle/ray intersection algorithm

41 Downloads

Updated

View License

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.

Comments and Ratings (13)

Igor

Igor (view profile)

To 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 Heather

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

Reply 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

Murat

Murat (view profile)

Hi, 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 golk

Jeffrey

I'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.

Reply 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

Nick

Nick (view profile)

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

Nick

Nick (view profile)

Excellent.. Really helpful!!!

Ben

Ben (view profile)

Looks great. Downloaded and will try it later.

Re 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 Semechko

Anton Semechko (view profile)

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

Updates

1.5

correct description: no symbolic toolbox is needed

1.5

Major rewrite of the function with additional options and output variables. Also provided PointInsideVolume function

1.4

documentation improvements and typo correction

1.2

correct treatment of 3x3 arrays as suggested by Andreas Weber

1.1

Improvements to border handling

MATLAB Release
MATLAB 7.12 (R2011a)
Acknowledgements

Inspired by: Ray/Triangle Intersection

Inspired: RayShapeArticle_FEX.zip, in_polyhedron

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

» Watch video