Good acceleration structure for ray sphere tests with spheres that move

Question

I'm looking for the proper acceleration structure to do ray-sphere intersection tests (in a game). the following conditions apply:

-there are arround 100 spheres and 100 rays to test against each other per frame

-the spheres move in each frame, so do the rays

-there can be rays/spheres added/removed in each frame (but most of them will be the same in between two frames, just moved slightly)

-whole thing is in 3D

a KD-Tree is very good for Ray intersection tests, but since the spheres move, i'd have to rebuild the KD-Tree in every frame, which is costly

an Oct-tree is easier to maintain, but very ineffective for ray intersection tests.

100 rays against 100 spheres doesn't seem to be much, but i'm coding on very low resources, so i'm looking for some acceleration for that

Anyone can give me some hints on that?

Answer 1

100x100=10k, an optimized brute force does not seem incoherent, especially that ray/sphere intersection test involve only add/multiply. You can always precompute all normalized ray vector before the main loop.

If you make the assumption that you live in a bounded universe and the spatial density of spheres and rays is relatively uniform, you could use a fixed spatial grid (fixed oct-tree) --something like a 16x16x16 cells grid, or more--, and:

• precompute for each sphere intersecting cells (easy to compute, only involve few adds and comparisons), store in each cell the list of intersecting spheres,
• for each ray, in a loop:
  • compute the list of cells the ray crosses (a method based on a Bresenham's algorithm could do the trick)
  • do the intersection test for all spheres in this cell list.

That way you don't have to store any ray in any tree, only spheres. Efficiency of this method depends on the ratio cell size / sphere size, if you don't have too much dispersion on sphere size it can be a good hint.

If spheres don't cross each other and sphere size have a minimum, you can even bound the sphere list in the cell list (appropriate number is left as an exercice to the reader...)

HTH