Here are the test results.

500K origins, one ray -> Single Ray
500K origins, 500k rays -> Multiple Rays

Moving the ray origins outside of the bounding box:

These results are benchmarked on a different laptop running on battery hence absolute values shouldn't be compared with the ones I previously posted. Having said that, the relative performance differences should still be correct. Multiple origins & single ray seems to be consistently faster than providing 2 arrays with matching length for origins and directions.

If your assumption is true, and moving ray origin points outside of the model bounding box exposes the data handling overhead, there seems to be some room for optimization here. These constitute roughly 50% of the total time.

To be clear, I measure these with a SystemDiagnostics.Stopwatch and only for one Method:

EmbreeRaytracer.IntersectOccluded(bvh, analysisPoints, new Vector3D[] { sunDirections[0] }); 

One low hanging fruit could be to create an overload for this method which takes a flat array of floats as inputs instead of arrays of Vector3D:

Currently, we have to convert twice. First from Rhino’s Vector3d/Point3d to dhart’s Vector3D and then, within the method to float[].

to clarify the multiple rays, the idea is to compare against your loop in c sharp. so something like:

make origin array of size 500_000 for each point
make direction array of the same vector with size 500_000
for each timestamp, 
- add the same 500_000 points to the origin array
- add the new directions of 500_000

The idea is, instead of c# passing 500k points 10 times, you pass 5mil points once. However to do this, we need to map every point to a direction, so you need a 5 million point origin array with a 5 million vector direction array. This should give the same result as using a 500k point origin array 10 times, with each time passing a single direction. So the timer would be across the loop of 10 calls to dhart, and the single 5milx5mil call.

but, i'm not sure this helps if its the data transfer

okay you are too fast in the responses!

I'm not sure I understand if it will get the speed we want, you are already testing just the call itself right, not the extra conversion you are doing?

I will test the 5 mil origins & 5 mil directions idea. Still found it interesting to understand which if the two methods yields better results for a single sun direction.

You understand it right - I am only benchmarking the call. But the Vector3D -> float[] conversion is part of the call itself. And since we need to convert from Rhino’s data structures anyway, we can do it directly to a flat float array. You’re right, though, this will shave off only a couple ms.

Good suggestion with me testing these on my own rather than typing it all out here :)

I updated the BUILD.MD to include some walkthrough images using Visual Studio. Please open an issue if you run into any problems or need clarity!

https://github.com/cadop/dhart/blob/main/BUILD.md

@cadop, I've done some further testing and - as mentioned earlier - there is a low hanging fruit for some minor optimization. Currently, we need to convert Rhino's Point3d and Vector3d to dhart's Vector3D which then gets converted to a float[].

This conversion is relatively slow:

Ideally, we would have an overload accepting float[] as arguments, rather than Vector3D

Then, we'd be able to convert Rhino's Point3d and Vector3d directly to a float[] like so:

// Use Reflection to get an array of Point3d from a list 
// This is much faster than calling .ToArray() on a list

            Point3d[] points = (Point3d[])typeof(List<Point3d>)
                   .GetField("_items", BindingFlags.NonPublic | BindingFlags.Instance)
                   .GetValue(_analysisPoints);

// Use Unsafe.Add to iterate over the array and cast doubles to floats

            float[] flatFloatArray = new float[points.Length * 3];

            ref var s0 = ref points[0];
            for (int i = 0, j = 0; i < points.Length; i++, j++)
            {
                flatFloatArray[j] = (float)Unsafe.Add(ref s0, i).X;
                flatFloatArray[j++] = (float)Unsafe.Add(ref s0, i).Y;
                flatFloatArray[j++] = (float)Unsafe.Add(ref s0, i).Z;
            }

For 500K origin points and 11 direction vectors, we can reduce the conversion time by 80-90%:

Independently of adding another overload to the C_CastOcclusionRays method, you could replace the current version of FlattenVectorArray(IEnumerable<Vector3D> vectors) with this one:

        public static float[] FlattenVectorArrayUnsafe(Vector3D[] vectors)
        {
            float[] out_array = new float[vectors.Length * 3];
            
            ref var s0 = ref vectors[0];
            for (int i = 0, j = 0; i < vectors.Length; i++, j++)
            {
                out_array[j] = (float)Unsafe.Add(ref s0, i).x;
                out_array[j++] = (float)Unsafe.Add(ref s0, i).y;
                out_array[j++] = (float)Unsafe.Add(ref s0, i).z;
            }

            return out_array;
        }

It should help with other methods relying on the Vector3D struct.

Hey @mariuszhermansdorfer Thanks for digging into this. Were you able to get dhart to compile from source? if not, could you let me know where it fails (maybe in a new discussion) so I can update the instructions. Likewise, if you did get it to work what was the issue? Then I can update FAQ.

As for checking rays inside of buildings vs. outside. Depending on your configuration, this is a perfect application of the graph generator! You can see a similar application in this paper https://dl.acm.org/doi/abs/10.5555/3465085.3465153 . The idea is, you generate a graph with a start point in the road/environment. It will generate all nodes in a grid given your settings, and if there is no door/open entrance to a building (e.g. in a mass model, or all doors are closed), it won't generate nodes in those locations. Then you can take the nodes from the graph and pass them to the occlusion raycast function. The graph generator is pretty fast compared to other methods of getting nodes in 3d environments, but may be a bit slower than methods that rely on 2d grids.

For your performance improvements, its possible you are doing tests on a newer CPU than me, and some architecture improvements have helped. Also I used a single plane in my test, so perhaps as the bvh grows we see much more improvement. I can change that function to always use streaming and coherent rays, since I realized it is guaranteed to be coherent when there is multiple origins with only one direction.

Please make a PR for your C# interface changes/overloads, and if possible add some unittests (i'll do it if you don't want) so I can check it won't break anything else. It's also a better workflow to give you credit, instead of me copying your code snippets and committing the changes myself :)

I have some python tutorials on this as well (unfortunately I don't think these tutorials exist for C#, perhaps in the future). This is generating a graph and calculating a visibility graph https://cadop.github.io/dhart/Python%20Docs/build/html/examples/visibility/basic.html . I think its similar, basically the empty regions are extruded volumes 'up'. If you pull the repo with gitlfs you can see the models in this file https://github.com/cadop/dhart/blob/main/src/Python/dhart/Example%20Models/VisibilityTestCases.obj It only generates the graph given a certain 'step height', so the blocks are excluded.

Thanks @cadop! I will look into the graph generator and try to wrap my head around how it works.

For now, I've made some good progress with implementing the overload mentioned above and faster casting logic. I was able to build the repo and test it from Rhino. The results are satisfying:

500k origins, 1 ray:
previously:

500k origins, 11 rays:
previously:

500k origins, 100 rays:
previously:

It seems that the data conversion step was taking about 6-8 ms per each call. Switching CastOcclusionRays to work with float[] removes this overhead.

Moving the bvh far away from vector origin points gives us this:

It seems that there is still some overhead in data piping between c# and c++.

OK, tested with 1M origin points and ran it in a loop for 100 different rays:

parallel stream:

sequential stream:

For whatever reason sequential stream execution seems to be the fastest here.

I don't think the loop will make much difference, but what was the result with the parallel non-stream (which is the latest one that doesnt use stream ... max_distance!=99999)?

The results were very similar to the parallel-stream. Almost no difference here.

Just as a reminder, this is what we started with:
500k origins, 1 direction

And this is the fastest configuration on my machine (sequential stream of rays + skip Vector3D and pass float[]

Down from approx. 60 ms for data conversion & raycasting to <40 ms. That's a 33% improvement!

Hm, I'll check tomorrow by putting all the combinations in the same dll. Can you put the rhino and gh files on your branch so I can reproduce your testing.

Its currently on the streaming branch if you had some near-term need for that extra speed, but there is no API change so it shouldn't matter for your modifications

I ported my previous optimizations to the streaming branch and created a new PR #41

Here are the results:
500K origins, 1 direction:
, previously:

500K origins, 11 directions:
, previously:

That's almost 50% improvement for only one direction (including data conversion times) and approx. 35-40% improvement for multiple directions.

Tested it on a newer laptop with 16 cores:

500K origins, 1 direction:

500K origins, 11 directions:

I think we can easily call this a success! Thanks a lot for your openness to suggestions and rapid implementation of feature requests!

awesome! Thanks for your suggestions and quick testing of them!

I will work through adding unit tests and checking that unsafe doesn't break things in Unity.

I found a bug in my unsafe looping algorithm. Will push an update later today, but it has to do with how I was indexing it. Here is the correct way: