title: Intersection of a 3D Grid's Vertices
body: <p>Imagine an enormous 3D grid (procedurally defined, and potentially infinite; at the very least, 10^6 coordinates per side).  At each grid coordinate, there's a primitive (e.g., a sphere, a box, or some other simple, easily mathematically defined function).</p>
  <p>I need an algorithm to intersect a ray, with origin outside the grid and direction entering it, against the grid's elements.  I.e., the ray might travel halfway through this huge grid, and then hit a primitive.  Because of the scope of the grid, an iterative method [EDIT: (such as ray marching) ]is unacceptably slow.  What I need is some closed-form [EDIT: <em>constant time</em> ]solution for finding the primitive hit.</p>
  <p>One possible approach I've thought of is to determine the amount the ray <em>would</em> converge each time step toward the primitives on each of the eight coordinates surrounding a grid cell in some modular arithmetic space in each of x, y, and z, then divide by the ray's direction and take the smallest distance.  I have no evidence other than intuition to think this might work, and Google is unhelpful; &quot;intersecting a grid&quot; means intersecting the grid's <em>faces</em>.</p>
  <p>Notes:</p>
  <ul>
  <li>I really only care about the surface normal of the primitive (I could easily find that given a distance to intersection, but I don't care about the distance per se).</li>
  <li>The type of primitive intersected isn't important at this point.  Ideally, it would be a box.  Second choice, sphere.  However, I'm assuming that whatever algorithm is used might be generalizable to other primitives, and if worst comes to worst, it doesn't really matter for this application anyway.</li>
  </ul>