/*
 * Intersect --
 *
 *      Conventional CPU-style kdtree traversal.
 *
 * Returns:
 *      Void, but hit->tHit and hit->triNum are filled in.
 */

static void
Intersect(const Ray& ray, KDTree kdtree[], Hit *hit)
{
   float tMin, tMax, invD[3];
   uint32 node;

   // Precompute invD[0..2] = 1/ray.d[0..2]
   // Precompute rightward[0..2] = NODE_SIZE * (ray.d[0..2] < 0)
   // Intersect ray against scene bounding box and produce tMin, tMax

   hit->tHit = FLT_MAX; hit->triNum = -1;
   if (tMax < tMin) {   /* Ray missed scene bounding box */
      return;
   }

   node = 0;
   while (true) {
      while (true) {    /* Ray is traversing an interior node */
         int near, far, rightward, splitAxis;
         float tSplit, plane;

         /*
          * NOTE: 'left' is a byte offset, not an index.  This saves a shift
          * when masking off the splitAxis and when doing address
          * computations, but then nodes have to be fetched using pointer
          * arithmetic.  That's hidden behind GET_NODE() here.
          */

         near = GET_NODE(kdtree, node)->left;
         plane = GET_NODE(kdtree, node)->plane;
         splitAxis = near & 0x3;
         near = near & (~0x3);
         if (splitAxis == 3) return node;       /* At a leaf */

         tSplit = (plane - ray.o[splitAxis]) * invD[splitAxis];

         /*
          * NOTE:  This relies upon left + 1 being the index of the right child!
          *
          * NOTE2: With more registers and CMOVs, this can still be branch-free
          * and independent of packing.
          */

         far = near + NODE_SIZE - rightward;
         near += rightward;

         if (tSplit <= tMin) {        /* Only need to go far */
            node = far;
            continue;
         }
         if (tSplit >= tMax) {        /* Only need to go near */
            node = near;
            continue;
         }

         stack.Push(tMax, far);
         tMax = tSplit;
         node = near;
      }

      /* Ray is traversing a leaf */
      triIndex = (GET_NODE(kdtree, node)->left)>>2;
      numTris = *((int *) GET_NODE(kdtree, node)->plane);
      IntersectLeafTriangles(ray, triIndex, numTris, hit);

      if (hit->tHit <= tMax) {  /* Early exit, hit something */
         return;
      }

      if (stack.IsEmpty()) { /* Nothing else to do, missed everything */
         return;
      }

      tMin = tMax;
      stack.Pop(&tMax, &node);
   }
}