title: Octree raycasting/raytracing - best ray/leaf intersection without recursion
body: <p>Could anyone provide a short &amp; sweet explanation (or suggest a <em>good</em> tutorial) on how to cast a ray against a voxel octree without recursion? </p>
  
  <p>I have a complex model baked into an octree, and I need to find the best/closest leaf that intersects a ray. A standard drill-down iterative tree walk:</p>
  
  <ol>
  <li>Grab the root node</li>
  <li>Check for intersection</li>
  <li>No? Exit</li>
  <li>Yes? Find child that intersects the ray that is closest to the ray's origin</li>
  <li>Loop until I reach a leaf or exit the tree</li>
  </ol>
  
  <p>Always returns a leaf, but in instances where the tree stores, say, terrain, the closest node to the ray's origin doesn't necessarily contain the leaf that's the best match. This isn't suprising - taller objects in farther nodes won't get tested using this approach.</p>
  
  <p>I can do this recursively by finding all of the intersecting leaves in the tree, sorting by distance and picking the closest one to the ray's position. However, this is slow and requires recursion.</p>
  
  <p>I've read a little about using the Bresenham line algorithm to walk the tree, which seems to require that each node contain pointers to adjacent neighbors, but I'm unclear on how to implement this in a useful way.</p>
  
  <p>Any suggestions? I can fake a stack in HLSL using a fixed-length array or a struct with an element for each potential stack entry, but the memory requirements for that can become crippling with a sufficiently large tree.</p>
  
  <p>Help.</p>