<p>Your procedure could be optimized in two directions:</p>

<ol>
<li><p>If your rays are structured you could possibly take advantage of space coherence: if a ray intersects a given triangle, then a nearby rays has high possibility of intersecting the same triangle or an neighboring one. Therefore simple parallelism over the rays may not be optimal, you could at least process them in batches based on adjacency.</p></li>
<li><p>If you have adjacency information on the triangles of your meshes, you could possibly exploit it when testing a ray against the mesh: the Möller-Trumbore algorithm can inform you if the intersection point of the ray and the triangle plane lies inside or outside each of the edges, so you may have a hint at which (neighboring) triangle to check next. That said, your meshes are quite small so the extra overhead may not be worth it.</p></li>
</ol>

CC BY-SA 3.0
2018-03-02T08:59:05.157Z
2018-03-02T08:59:05.157Z
nplatis
<p>I am looking for a way to efficiently compute ray-triangle intersections for a large number of rays (~1k) and a large set of triangle-mesh bodies (~100k) with each composed of several hundred faces. My current approach towards optimization consists of </p>

<ul>
<li>thread parallelism for each ray</li>
<li>pre-select bodies by testing for ray-bounding box intersections</li>
<li>loop over faces of pre-selected bodies to detect ray-triangle intersections using the Möller-Trumbore algorithm.</li>
</ul>

<p>Not impressed with performance so far. (Admittedly using python). Are there alternative solutions ?</p>

CC BY-SA 3.0
2018-03-01T15:30:38.810Z
did you profile and see which steps take a long time?
ratchet freak
CC BY-SA 3.0
2018-03-01T15:32:09.767Z
" (Admittedly using python). Are there alternative solutions ?" C++ is a good alternative. How fast do you need it to go? It may simply be unachievable in Python.
Dan Hulme
CC BY-SA 3.0
2018-03-01T16:31:12.697Z
@ratchet freak: Will do and post resuts.
Rakulan S.
CC BY-SA 3.0
2018-03-01T17:42:42.857Z
You can 1) try C++   2) try to convert your code to make it work on the gpu  3) using spatial data structures
gallickgunner
CC BY-SA 3.0
2018-03-02T09:49:13.113Z
Are you just firing primary rays or are you also  doing secondaries, e.g. reflections?
Simon F
<raytracing><optimisation>
Rays (~1k) intersecting triangle meshes (~100k) with ca. 100 vertices each
Rakulan S.
# Rays (~1k) intersecting triangle meshes (~100k) with ca. 100 vertices each

(Asked by: username_0 on 2018-03-01)

I am looking for a way to efficiently compute ray-triangle intersections for a large number of rays (~1k) and a large set of triangle-mesh bodies (~100k) with each composed of several hundred faces. My current approach towards optimization consists of

* thread parallelism for each ray
* pre-select bodies by testing for ray-bounding box intersections
* loop over faces of pre-selected bodies to detect ray-triangle intersections using the Möller-Trumbore algorithm.

Not impressed with performance so far. (Admittedly using python). Are there alternative solutions ?

**Tags:** raytracing, optimisation

> **Comments:**
> **username_1**: did you profile and see which steps take a long time?  
> **username_2**: " (Admittedly using python). Are there alternative solutions ?" C++ is a good alternative. How fast do you need it to go? It may simply be unachievable in Python.  
> **username_0**: @username_1: Will do and post resuts.  
> **username_3**: You can 1) try C++   2) try to convert your code to make it work on the gpu  3) using spatial data structures  
> **username_4**: Are you just firing primary rays or are you also  doing secondaries, e.g. reflections?  

---

## 1 answers

### Answer by username_5 on 2018-03-02. Score: 1 | Accepted answer

Your procedure could be optimized in two directions:

1. If your rays are structured you could possibly take advantage of space coherence: if a ray intersects a given triangle, then a nearby rays has high possibility of intersecting the same triangle or an neighboring one. Therefore simple parallelism over the rays may not be optimal, you could at least process them in batches based on adjacency.
2. If you have adjacency information on the triangles of your meshes, you could possibly exploit it when testing a ray against the mesh: the Möller-Trumbore algorithm can inform you if the intersection point of the ray and the triangle plane lies inside or outside each of the edges, so you may have a hint at which (neighboring) triangle to check next. That said, your meshes are quite small so the extra overhead may not be worth it.


---

