0
$\begingroup$

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?

  • 0
    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?2012-07-21
  • 0
    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 http://wiki.cgsociety.org/index.php/Ray_Sphere_Intersection). The problem is doing it (effectively) at each grid node.2012-07-21

1 Answers 1