title: Data structure / approach for efficient raytracing
body: <p>I'm writing a 3D raytracer as a personal learning project (<a href="https://github.com/mikera/enlight" rel="noreferrer">Enlight</a>) and have run into an interesting problem related to doing intersection tests between a ray and a scene of objects.</p>
  
  <p>The situation is:</p>
  
  <ul>
  <li>I have a number of primitives that rays can intersect with (spheres, boxes, planes, etc.) and groups thereof. Collectively I'm calling these scene objects.</li>
  <li>I want to be able to scene objects primitives with arbitrary affine transformations by wrapping them in a <code>Transform</code> object (importantly, this will enable multiple instances of the same primitive(s) to be used in different positions in the scene since primitives are immutable)</li>
  <li>Scene objects may be stored in a bounding volume hierarchy (i.e. I'm doing spatial partitioning)</li>
  <li>My intersection tests work with <code>Ray</code> objects that represent a partial ray segment (start vector, normalised direction vector, start distance, end distance)</li>
  </ul>
  
  <p>The problem is that when a ray hits the bounding box of a Transform object, it looks like the only way to do an intersection test with the transformed primitives contained within is to transform the <code>Ray</code> into the transformed co-ordinate space. This is easy enough, but then if the ray doesn't hit any transformed objects I need to fall back to the original <code>Ray</code> to continue the trace. Since Transforms may be nested, this means I have to maintain a whole stack of <code>Ray</code>s for each intersection trace that is done. </p>
  
  <p>This is of course within the inner loop of the whole application and the primary performance bottleneck. It will be called millions of times a second so I'm keen to minimise complexity / avoid unnecessary memory allocation.</p>
  
  <p>Is there a clever way to avoid having to allocate new <code>Ray</code>s / keep a <code>Ray</code> stack?</p>
  
  <p>Or is there a cleverer way of doing this altogether?</p>