Different output of ray_mesh_intersect after change to embree

[oqilipo]

Is it intended that ray_mesh_intersect only outputs the first intersected triangle?

Before the change to embree, in 2018 ray_mesh_intersect outputs multiple intersections

The following code was used:

clearvars; close all

[x,y,z] = sphere(16);
fv = surf2patch(x,y,z,'triangles');

ray = [-2 0 0 0.5 0 0];

tic
[flag, t, lambda] = ray_mesh_intersect(ray(:,1:3), ray(:,4:6), fv.vertices, fv.faces);
toc

% flag = t == min(t(flag));

patchProps.EdgeColor = 'k';
patchProps.FaceColor = [0.8, 0.8, 0.7];
patchProps.FaceAlpha = 0.5;
patchProps.EdgeLighting = 'none';
patchProps.FaceLighting = 'gouraud';

figure
axis equal tight
patch(fv, patchProps)
hold on
quiver3(ray(1),ray(2),ray(3),ray(4),ray(5), ray(6))
patchProps.FaceColor = 'r';
patch('vertice', fv.vertices, 'faces', fv.faces(flag,:), patchProps)
view(3)
xlabel 'X'; ylabel 'Y'; zlabel 'Z'

[alecjacobson]

It does look this change happened. the libigl wrapper of embree is not that complicated and has an overload to return all hits, so this would be an easy feature to have (and enable with some kind of flag). Not sure what the right return type should be. Maybe sparse matrix with a column per ray and row per triangle.

[oqilipo]

Besides of the incomplete output of the new embree version, I compared the speed of the new embree version to the old Möller–Trumbore version and the old one is ten times faster on my computer. So it may be better to revert to the Möller–Trumbore version Commit: 87616c77f142ef30fe9262aba27cd805cd2a820d ?

[alecjacobson]

Can you post your example for the performance comparison?

[oqilipo]

Of course. Here is the test test_RayMeshIntersect.zip .

[alecjacobson]

Ah, I see the problem. The embree version builds a BVH . This costs O(n log n) for a mesh with n faces. Then it will get hits of a input list of m rays in O( m log n) time. Resulting in a total time of O(n log n + m log n).

However, you're calling ray_intersect_mesh once for each ray, rather than passing all rays and calling it a single time. This means the BVH is rebuilt for every ray, so the total time of your code is O( m n log n )

In your test you can just replace the for loop with:

[flag, t, lambda] = ray_mesh_intersect(line(:,1:3), line(:,4:6), Sphere.vertices, Sphere.faces);

On my computer I see:

Elapsed time is 0.069826 seconds.
Elapsed time is 0.022156 seconds.
Elapsed time is 0.002322 seconds.

If you change your example to use sphere(160) then you'll see an even bigger improvement:

Elapsed time is 4.433620 seconds.
Elapsed time is 1.378942 seconds.
Elapsed time is 0.008799 seconds.

This is because the other methods are not using a BVH so their runtime is O(m n). Embree will be significantly faster when the mesh is big and you shoot many rays.

[oqilipo]

Thanks, works fine. However, output of multiple hits would be an improvement.

[alecjacobson]

See above. This is a straightforward change to the mex (just got to create time to do it :-) happy to take a PR)

On Sat, Oct 24, 2020, 8:56 AM oqilipo notifications@github.com wrote:

Thanks, works fine. However, output of multiple hits would be an improvement.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/alecjacobson/gptoolbox/issues/92#issuecomment-715911158, or unsubscribe https://github.com/notifications/unsubscribe-auth/AARDJGIHTUDEZPZRJJR7ACTSMLFIDANCNFSM4LR2NYDQ .

[ThSGM]

Dear @alecjacobson

Hi! Sorry just checking in in 2021. Was this issue ever resolved in the current version of gptoolbox? (that ray_mesh_intersect does not return anything past the first intersection).

[alecjacobson]

No, I haven't written that wrapper, yet. No challenges, just little time :-)