Analytic Intersection of Objects Located on a 3D Grid's Vertices

Question

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?

Answer 1

Try this approach:

1. Determine the function of the ray;

2. Say the grid is divided in different planes in z axis, the ray will intersect with each 'z plane' (the plane where the grid nodes at the same height lie in), and you can easily compute the coordinate (x, y, z) of the intersect points from the ray function;

3. Swipe z planes, you can easily determine which intersect points lie in a cubic or a sphere;

4. But the ray may intersects with the cubics/spheres between the z planes, so you need to repeat the 1-3 steps in x, y axises. This will ensure no intersection is left off.

5. Throw out the repeated cubics/spheres found from x,y,z directions searches.