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
    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.2019-04-14

1 Answers 1

0

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.

  • 0
    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.2012-07-21