In my studies of POV-Ray's source, I've discovered an alternative box 
intersection algorithm.  This one is far less branchy and far less prone 
to floating-point floatiness problems.

The only C++ compiler I have is Microsoft's (VS.NET 2003), so I'm not 
able to compare the speed with the official version (which uses Intel's 
compiler).  Theoretically, it should be faster because it's so much 
simpler.  Some casual tests on image quality (like StackerDay.pov) 
indicate that this has at least the same quality as the old code.

This is a complete replacement for the body of the Intersect_Box 
function in boxes.cpp.

Thoughts and opinions are welcome :)

-Ryan

int smin = 0, smax = 0;    /* Side hit for min/max intersection. */
   DBL t, tmin, tmax;
   VECTOR P, D;

   /* Transform the point into the boxes space */

   if (Trans != NULL)
   {
     MInvTransPoint(P, Ray->Initial, Trans);
     MInvTransDirection(D, Ray->Direction, Trans);
   }
   else
   {
     Assign_Vector(P, Ray->Initial);
     Assign_Vector(D, Ray->Direction);
   }

   DBL tYMin, tYMax, tZMin, tZMax;

           //Based on http://www.cs.utah.edu/~rmorley/pubs/box.pdf
           //Credits go to Amy L. Williams, Steve Barrus,
           //R. Keith Morley, and Peter Shirly
           //for developing this technique.
           // Adapted for use with POV-Ray by Ryan Lamansky
           smin = SIDE_X_0;
           smax = SIDE_X_1;

           DBL //Provides a free way out of the negative zero problem.
                    divx = 1/D[X],
                    divy = 1/D[Y];
           if (divx >= 0)
           {
                    tmin = (Corner1[X] - P[X]) * divx;
                    tmax = (Corner2[X] - P[X]) * divx;
           }
           else
           {
                    tmin = (Corner2[X] - P[X]) * divx;
                    tmax = (Corner1[X] - P[X]) * divx;
           }
           if (divy >= 0)
           {
                    tYMin = (Corner1[Y] - P[Y]) * divy;
                    tYMax = (Corner2[Y] - P[Y]) * divy;
           }
           else
           {
                    tYMin = (Corner2[Y] - P[Y]) * divy;
                    tYMax = (Corner1[Y] - P[Y]) * divy;
           }

           if (tmin > tYMax || tYMin > tmax)
                    return false;
           if (tYMin > tmin)
           {
                    tmin = tYMin;
                     smin = SIDE_Y_0;
           }
           if (tYMax < tmax)
           {
                    tmax = tYMax;
                    smax = SIDE_Y_1;
           }

           DBL divz = 1/D[Z];
           if (divz >= 0)
           {
                    tZMin = (Corner1[Z] - P[Z]) * divz;
                    tZMax = (Corner2[Z] - P[Z]) * divz;
           }
           else
           {
                    tZMin = (Corner2[Z] - P[Z]) * divz;
                    tZMax = (Corner1[Z] - P[Z]) * divz;
           }

           if (tmin > tZMax || tZMin > tmax)
                    return false;
           if (tZMin > tmin)
           {
                    tmin = tZMin;
                    smin = SIDE_Z_0;
           }
           if (tZMax < tmax)
           {
                    tmax = tZMax;
                    smax = SIDE_Z_1;
           }

   *Depth1 = tmin;
   *Depth2 = tmax;

   *Side1 = smin;
   *Side2 = smax;


           return tmax > EPSILON; //Prevents same-point self-shadowing.

Post a reply to this message