I am in the process of writing a ray tracing algorithm in Julia (not related to 3D rendering, but for physical simulations). The code is too complex and I have not been able to make a good MWE, but I will try to describe the problem as best as I can and I would love people if people could comment on alternatives or their own experience solving similar problems.
I have a binary tree where the leaf nodes contain data of different types (i.e. triangles, circles, cylinders, etc). For each ray, the algorithm traverses the tree until it finds a leaf node where the ray hits and then I need to check whether the ray intersects the geometry or not.
Since each node may have a different type of geometry, the intersection method is selected at runtime. On my machine, runtime dispatch (on Julia 0.6) takes about 100 ns, which can be 10 slower than the actual time to calculate the intersection test. So this makes my algorithm at least an order of magnitude slower.
As alternative to runtime dispatch I am considering:
Encode the type as field and do dispatch manually (if-else). This would force me to make one data structure to fit all the geometry which would waste memory. And the code would get really C-ish ugly…
Using an union type. On 0.6 this did not help, but I think on 0.7 this will get faster, but will it be as fast as the approach above? I know there was a comparison some time ago by benchmarking on an array (can’t find the post sorry) but it seems to me that is a different problem from tree traversal in ray tracing.
I have tried to make my algorithm type stable despite having nodes of different types but did not manage. Has anyone found a good way to do this? (I know about FunctionWrappers.jl, and TypedSortedCollections.jl but I don’t see how this would fit this particular data structure and algorithm)
I would love to hear about similar problems others may have solved, or whether there is a general recommendation for dealing with heterogeneous tree structures (not arrays!) in Julia
Thanks in advance!