Question: does contains_points actually use Rtree?

[avlonder]

Hi,

First of all, thank you for this wonderful package. I was just wondering... Is there some bounding volume hierarchy (Rtree) algorithm activated when using contains_points? It is not clear to me.

[Marviel]

Looks like it! contains_point execution seems to eventually end up in: https://github.com/mikedh/trimesh/blob/master/trimesh/ray/ray_triangle.py which references: https://github.com/mikedh/trimesh/blob/master/trimesh/triangles.py which references: https://github.com/mikedh/trimesh/blob/master/trimesh/util.py which has a function bounds_tree -- which in this case is an rtree.

[avlonder]

Well, I wasn't quite sure which intersects_location() is used: the one in ray_triangle or the one in ray_pyembree. Thanks anyway!

And also, if Rtree is used, I do not understand why it should make the code more efficient if you discard the points outside the AABB of your mesh: this AABB should be the root of your r-tree, so this reduction of ray-triangle intersection operations is already done by r-tree and shouldn't be repeated explicitly. Or am I completely wrong about this?

[mikedh]

Yup, the reason to do the AABB check on the point before the ray test is to exit higher in the pipeline. Also the rtree query implemented in ray_triangle is basically finding the AABB of the ray passing through the mesh volume and can have some pretty rough worst- case performance. If all the points are outside of the mesh's AABB we can avoid creating the rtree at all.

Intersector objects in ray_triangle and ray_pyembree have identical interfaces, but the embree one is preferred if pyembree is installed. The one in ray_triangle is intended as a fallback and is somewhat naive, it does ~12,000 rays/s on my computer while embree was written by Intel and does roughly 650,000 rays/s on the same computer.

[avlonder]

Okay, thanks a lot!