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.

1 Like

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.

1 Like

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:

@diff-arch can I please ask you to use less rude terms when expressing your opinions? Yes, it’s an entirely different implementation, with some long history, and that does not suffer from the GIL (Global Interpreter Lock). GIL is a pretty problematic feature of CPython and multiprocessing works to circumvent it.

We are aware of the existence of CPython and making it available is our concern. Now, you can use CPython with Hops.

Sure! Sorry if my comment offended you. Where I’m from, people are less easily shook by colourful language, and it’s often part of expressing an honest opinion.

I’m aware of the GIL-related limitations. The pros and cons have been discussed ad absurdum, but I guess the Python Foundation probably knows what they are doing.

What? Where was I insinuating that you weren’t aware of CPython?
Making it available seems to be a concern now with the advent of machine learning and the immense popularity of CPython. People have been asking for a better CPython integration over and over for years though!

I am aware of Hops - have even used it -, and it’s probably a step in the right direction. I’d personally have preferred if CPython would have taken the place of IronPython in Rhino by now, but that clearly won’t happen.

1 Like

We are saying, literally, the same thing :slight_smile:
I hope there will be some news regarding this.

1 Like

wait what, is this actually faster than meshray? looks like so much overhead even though we are leveraging gpu… And I guess you can scale it easily with image resolution depending how far your target is. Gets me thinking… Would you have a script to share?

What about this version of ironpython?

In my own testing (not rigorous), I’ve found it to be much faster if you are casting the number of rays you would in a 3D isovist. View.CaptureToBitmap in C# is fast, but ideally this approach of counting pixels rather than intersecting rays with a mesh would be migrated to OpenGL to take full advantage of the graphics card. I’ve tried with GhGL without success.

The components shown in the screenshot are now available in the latest version of Heron (see definition below). The code for ImageCubeMapPlus can be found here and ImageCubeMap here.

20211002_SF View Analysis-MeshOnly.3dm (8.8 MB)
20211002_SF View Analysis.gh (22.9 KB)

2 Likes

This is really cool! Do you have the View Analysis display mode set up somewhere on github also? I guess it’s somehow with colors, without any lighting settings/shadows etc.

Edit I’m sharing it here, in case anyone is following.
View Analysis.ini (13.9 KB)

@sonderskovmathias Thanks for sharing the display mode! I like to also turn off the grid display and use flat shade:
View Analysis BW.ini (13.9 KB)

I should probably include this “View Analysis” display mode as an option for the components so they are more portable.

1 Like

Thank you!
This is exactly what I’ve wanted to do in rhino/gh for a while. MeshRayIntesect and others in Rhino have been inconsistent on large, complex meshes. Rendered raytracing, even on cpu, seems like a better plan.

I come from 3dsMax/VRay where raytracing is an integral part of the system. We have a render farm and could spit out thousands of images in minutes at this scale. But this is even faster.

For my needs, I only want to test a horizontal plane. so it could work to render images with a cylindrical projection at 1 x 360 , for example.

1 Like