Bug fix in extent calculations (25% regression) & Bounding Box checks in Booleans+Placed Volume(50% better)

[ndinsmore]

Overall from master, this brings the xray benchmark from 2.2s -> 1.4 on my computer.

1. First in the process of doing this, I found a bug in the extant calculations for booleans & and aggregates fixing it caused a 25% regression on my machine 2s->2.5s because there were more intersections in the BVH for the booleans. Numerically the calculation is just as efficient. It stole the code for extent of a placed volume and made it into a function. This refresion was worth 25%
2. I added an AABB and intersection check to PlacedVolume this makes the multiple dispatch(even though I don't think this is the problem) not happen most time. This saves around 25%.
3. Add AABB for both the left and right objects in booleans. Then we use those bounding boxes to shortcut the calculation of distanceToIn distanceToOut and inside . This simplifies the evaluation of most booleans because most of the time the evaluation is for only one of the shapes. This also saves 25%.
4. Moved AABB and the bounding box stuff to its own file to be used earlier.

The boolean multiple dispatch is not a problem anymore. When you profile the code it doesn't even show up anymore.
I think what is still an issue and I will make an issue on Monday is that the ray tracing is O(~n^2) where n is the number of shapes intersected. The worst pixels on the benchmark goes through 800 shapes(381 mean), but distanceToIn is called 69,000 times

[peremato]

Very nice work. Thanks for the fix in the extent of booleans. I'll check the PR in the next days.

One thing I want to mention is that in this exercise I wanted to compare the C++ and Julia implementation without changing too much the algorithms and optimizations in order to make a fair comparison. This is why I was comparing using the TrivialNavigator because the implemented algorithm is more comparable. Adding a aabb for each PlacedVolume is probably a very good optimization (although for simple shapes like a Box is a penalty) but is different than what is currently in the C++ code.

[ndinsmore]

When I run the benchmark with the TrivialNavigator timing on my machine goes from 6.17s->2.2s (2.8x speed up) so this should help that, but does change the algorithms some what. I think that this would make it beat the VecGeom code

I started down this path to understand if multiple dispatch could be improved some how for this type of problem, when I made these improvements it seems like it might not have been the issue at all.

As for adding aabb to each placed volume, I had the same thought as you about the impact to shapes like box. So I had created a branch where aabb::Union{Nothing,AABB{T}} , but it was a bit more complex and didn't yield many benefits. Therefore I though for a first step leaving it out was better.

[peremato]

Yes, this is really great. Thanks very much. I also measured a factor 3 speedup with the TrivialNavigator. I discussed with the C++ developer and told me that they discarded to use an aabb at the level of the PlacedVolume to avoid interrogating the shape in most of the cases. The argument was that there is early shacks in the specific algorithms for complicated shapes. But this is certainly not true for Booleans. I am ready to merge the PR. Anything else to add?

[ndinsmore]

It was an interesting distraction, thank you.

[peremato]

With the following change I get a 15% better for TrivialNavigator.

--- a/src/Volume.jl
+++ b/src/Volume.jl
@@ -71,9 +71,9 @@ end
 function contains(vol::Volume{T}, p::Point3{T})::Bool where T<:AbstractFloat
     inside(vol.shape, p) == kInside
 end
-@inline function distanceToIn(pvol::PlacedVolume{T}, p::Point3{T}, d::Vector3{T})::T where T<:AbstractFloat
+@inline function distanceToIn(pvol::PlacedVolume{T}, p::Point3{T}, d::Vector3{T}, rcp_d::Vector3{T}=inv.(d))::T where T<:AbstractFloat

-    !intersect(pvol.aabb,p,d) && return T(Inf);
+    !intersect(pvol.aabb,p,d,rcp_d) && return T(Inf);

     distanceToIn(pvol.volume.shape, pvol.transformation * p, pvol.transformation * d)
 end

This improvement I think is because the reciprocal direction is calculated once for all interrogated daughters in a Volume