Sunday, January 10, 2010

"Raytracing on a Grid" updated

Commenter SyntaxError has spotted and corrected several bugs in the code I presented in my article Raytracing on a Grid; I mention this in case anybody used the first or second pieces of example code as a basis for their own work. The code in the article has been updated and retested.

The core of the problem was that I was failing to account for the fact that zero multiplied by infinity yields an undefined result. This happened when both endpoints had identical horizontal or vertical coordinates, which you'd think I would have caught earlier.

2 comments:

Scott said...

I used your article as a reference when implementing the spatial hash traversal for the segment queries in Chipmunk. I had some code that detected the NaNs and dealt with them. I could swear those checks were in your original code...

http://code.google.com/p/chipmunk-physics/source/browse/trunk/src/cpSpaceHash.c#498

I actually had to fix the same issue, but for a different reason. I was detecting the NaNs afterwards and dealing with them, but GCC's -ffast-math flag disables software checks for infinite and NaN math. Most FPUs do fine with the infinite stuff (PPC, x86, and ARM FPUs) but don't implement NaN checks. Took a while to realize that it was an issue too because I my debugging target was compiled without -ffast-math so I never noticed in my trivial tests. Whoops.

Scott said...

Oh! I actually had one other improvement that I did to the original code come to think of it.

Instead of tracking the number of cells to traverse as an integer, I just exit when t > 1.0. In my case, I also had the ray collision routines return the t value of the intersection. That way I could short circuit the traversal when I knew that the ray was moving into a grid cell that was beyond where a collision was already found.