Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
What does it mean for the object to intersect the ray? I mean, does each object have a radius from its grid node, or what? – copper.hat Jul 21 '12 at 6:49
For a sphere at a grid node, "intersection" would mean that there exists a point on the ray that passes closer than a certain distance (radius) to the grid node. Basically, it's a simple intersection. You can find classic solutions for doing this (e.g., a sphere intersection is found by The problem is doing it (effectively) at each grid node. – imallett Jul 21 '12 at 6:56

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.

share|cite|improve this answer
If I understand what you're saying, the problem is that that's still an iterative algorithm. Suppose for example, that the objects have a very very small size. Many rays would pass through the grid without intersection. If you have 10^6 z planes, you see how stepping through becomes unacceptable. I need an O(1) algorithm. – imallett Jul 21 '12 at 21:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.