Ray intersection with INFINITE number of spheres

Question

I'm currently trying to do an intersection test between a ray and other types of objects in a ray tracer. The ray's collisions are solved mathematically by solving equations, rather than iterating with constant or dynamic sized steps like with distancefields. This is working well, but there is a problem that I am trying to solve.

// So if we put these two together (changing x,y,z in
// equation 1 with the values from equation 2, we get:

cx,cy,cz = sphere center
r        = sphere radius
ox,oy,oz = ray origin
dx,dy,dz = ray direction
t        = if the ray will hit, then that point is origin + direction * t

(Eq1) SphereEquation = (x - cx)^2 + (y - cy)^2 + (z - cz)^2 == r^2;
(Eq2) RayEquation    = {x,y,z} == {ox,oy,oz} + t*{dx,dy,dz};

CollisionEquation    = ((ox + t*dx) - cx)^2 + 
                       ((oy + t*dy) - cy)^2 + 
                       ((oz + t*dz) - cz)^2 
                       == r^2

The variable t represents when the ray will collide. So, if we solve for the variable t using the pq-formula, we can see if the ray will collide or not. My problem is that I have an infinite number of spheres that lie on a grid, with constant sized steps between them. I want to create an equation where the ray could intersect with any of them. I have tried to find anything like this, but I can't find anything. So, how can this equation be created? If it's not possible, why not?

P.S. I'm using Mathematica when it's needed, and the raytracer is done in GLSL if someone wants to know ;)

Thanks in advance for all kinds of help.

Why are the number of spheres infinite? Seems like that could lead to all kinds of headaches. — bigbenbt
One thing for example is grass, where it is a LOT of grassblades. The grid with spheres is just an example. The sphere-equation can later be changed to a equation that is more like blades of grass. (But it's a good question) — Boll

Conninho Conninho · Accepted Answer · 2012-08-16T13:48:10

It depends a little on the exact setup:

Are the objects necessarily on a 2-dimensional grid (like in the grass example)? If so,

1) compute the intersection point s between your ray and the plane that contains the grid (this is roughly where any object has to be that is a candidate for being hit by your ray),

2) compute a suitable maximum distance that any candidate object can have from s (this may not be trivial, it depends on object size an viewing angle)

3) compute t as above for all candidates (i.e. all objects that are closer than the computed maximum distance to s). Smallest t wins.

Ray intersection with INFINITE number of spheres

1 Answers