I previously posted this question on stackoverflow, but it's really more of a mathematical question. I have reworked the question for presentation here.
I have a regular 3D unit cubic grid of enormous size (10^6 in each of the three axes, at least). At each grid node, there is a simple, mathematically defined object--perhaps a sphere or cube. Every object is identical.
Given a ray, I need a constant time algorithm to find which object within the grid, if any, it intersects. Algorithms that walk down the grid step by step (such as octrees or grid walking) are simply unacceptable.
First, is such an algorithm even possible? Second, if so, what is it?