Fast Mesh Ray intersection

I have large mesh, and a long list of rays (millions). I need to know if the rays hit any part of the mesh. Got this working in Python RhinoCommon with Intersect.Intersection.MeshRay.

I am looking for a way to speed this up by at least a factor of 10. Is there a relatively easy way to utilise the graphics card for this through Cycles/CUDA/OptiX? Or is it worthwhile re-writing in C#?

All I need to know is whether the rays hit anything at all. Thank you for your thoughts.

How many cores do you have available? A way to improve this would be to multithread this: with enough threads, maybe 12-16, and using the same mesh, with some bookkeeping you can probably get the wanted 10x speedup. You should not use a different thread for each ray, or this will become certainly slower. Dividing the rays in groups would work much better. Also, a single thread that goes 10x faster would do, of course.

I’d say it’s worth it, but it’s not the only factor. What the rest of the code does would also make a difference. If you simply add to a list, then it’s probably not worth it.

Real performance gains would probably come from porting the relevant, slow parts to an external, compiled C++ library (dylib on macOS, dll on Windows) and using that in IronPython with ctypes.
@Terry_Chappell does amazing stuff with this, and I had some small success with it myself, though unrelated to Rhino/Grasshopper.

If you manage to pair that with multithreading (on the C++ side), like Guilio mentioned, the gains would probably be me enormous. C++ is by nature, faster than C#, and much faster than Python.

Here’s a very neat tutorial that got me started:
https://solarianprogrammer.com/2019/07/18/python-using-c-cpp-libraries-ctypes/

You need to be proficient in C++ though.

Thank you both for these tips.

Our machines have 8 physical (16 virtual cores), so multi-threading should speed the intersection calculation up quite a bit. Since I’m not proficient in C++, I’ll start with multi-threading in Python and see where it takes me. Got an idea how to do this ray grouping.

Thank you again

Fun video where a guy (he wrote task manager) compares python vs. c# vs. c++ on a prime sieve:

Not totally applicable since you are calling rhino to do the intersection, and he did not use numpy or anything, but still, the money shot is impressive:

Interesting vid. Thanks for linking it in. In this particular example, the massive speed improvement you see with C++ seems to be due to the bit arrays that you don’t have in Python. Give that I’ll be using RhinoCommon, I wonder if the difference in execution time is really that much.

In this case I was more interested in the python to c# delta, though for your use yes it’s difficult to guess how much work is already happening in .net land, and how much in python.

One strategy I’ve been developing for a view analysis tool, which may help in this instance, is to set a camera at a point, capture the view to a bitmap, then iterate over the pixels with GH_MemoryBitmap.Sample to see if a color is present. In my testing, iterating over pixels can be significantly faster than Intersect.Intersection.MeshRay when there are hundreds of thousands of rays to cast. In a way this uses the graphics card to cast rays to see if an object (or any object) is visible from a point.

In the image below, instead of capturing just one camera, a series of them are captured to create a cubemap. Rays are cast in the direction of the specified pixel color for visualization purposes, but if not needed, the component is even faster.

2 Likes

Here is an update on my progress so far. I have implemented multithreading following Steve Baer’s tutorial (Multithreaded Python | Steve Baer's Notes)

I get a speedup of up to 6x. This is on an 8-core HT processor.

Given that this is Python, a 6x improvement is actually not too bad.

I also looked into Python multiprocessing, which should be in 2.7, but it appears that Rhino Python doesn’t ship with this module. I’ve no idea why this is.

Because Rhino uses IronPython, which is a shittier version of CPython! Why you may ask, well because modern Rhino development is allegedly mainly done in C#, and IronPython is all that’s available. CPython has roots in C and C++ (which are superior coding languages in my opinion), and thus form a much more solid base. :sunglasses: