Optimizing intersect finding code

The bottleneck of many raytracers is intersect finding code.
Usually it look like a
Object * Intersect ( Ray& ray, double& t )
{
Object * ClosestObj = NULL;
double ClosestDist = INFINITY;

for ( int i = 0; i < SolidsCount; i++ ) // check every object
    if ( Solid [i] -> Intersect ( ray, t ) ) // if intersect then check distance
       if ( t < ClosestDist )
       {
       ClosestDist = t;
       ClosestObj = Solid [i];
       }
t = ClosestDist;
return ClosestObj;
}

But this code check all objects in scene, also objects, which is too far from the ray direction.
Let's try to find better way.
Ray divide space to subspaces where ray can be and where cant be.
When ray direction is >0.0 then bounding box of object is righter from ray origin, otherwise - lefter.
I use heuristic to check it.

Code1:
Object * Intersect ( Ray& ray, double& t )
{
Object * ClosestObj = NULL;
double ClosestDist = INFINITY;
int sx, sy, sz, ok;

sx=(r.dir.x<=0.0);sy=(r.dir.y<=0.0);sz=(r.dir.z<=0.0); //signs of direction
for ( int i = 0; i < SolidsCount; i++ ) // check every object
    {
     ok=(sx)? (Solid [i] ->min.x<=r.org.x): (Solid [i] ->max.x>=r.org.x);
     if (!ok) continue;
     ok=(sy)? (Solid [i] ->min.y<=r.org.y): (Solid [i] ->max.y>=r.org.y);
     if (!ok) continue;
     ok=(sz)? (Solid [i] ->min.z<=r.org.z): (Solid [i] ->max.z>=r.org.z);
     if (!ok) continue;
     if ( Solid [i] -> Intersect ( ray, t ) ) // if intersect then check distance
       if ( t < ClosestDist )
       {
       ClosestDist = t;
       ClosestObj = Solid [i];
       }
    }
t = ClosestDist;
return ClosestObj;
}

Works faster, but not too fast - usually 25% speedup.
This code checks also objects lefter or righter from far ray intersection point with all-objects-bounding-box.
Let's optimize further.

Code2:
Object * Intersect ( Ray& ray, double& t )
{
Object * ClosestObj = NULL;
double ClosestDist = INFINITY, mx, my, mz;
int sx, sy, sz, ok;

sx=(r.dir.x<=0.0);sy=(r.dir.y<=0.0);sz=(r.dir.z<=0.0); //signs of direction
mx=r.dir.x; my=r.dir.y; mz=r.dir.z;
if (sx) mx=-mx;
if (sy) my=-my;
if (sz) mz=-mz;
if (mx>my && mx>mz) // x direction increasing faster
  {
   mx=(sx)? gbb.max.x : gbb.min.x; t=(mx-r.org.x)/r.dir.x; //gbb - global bounding box - min and max points of scene
   my=r.org.y + r.dir.y*t; mz=r.org.z + r.dir.z*t;
  }
  else if (my>mx && my>mz) // y direction increasing faster
     {
      my=(sy)? gbb.max.y : gbb.min.y; t=(my-r.org.y)/r.dir.y;
      mx=r.org.x + r.dir.x*t; mz=r.org.z + r.dir.z*t;
     }
    else // z direction increasing faster
       {
        mz=(sz)? gbb.max.z : gbb.min.z; t=(mz-r.org.z)/r.dir.z;
        my=r.org.y + r.dir.y*t; mx=r.org.x + r.dir.x*t;
       }
for ( int i = 0; i < SolidsCount; i++ ) // check every object
    {
     ok=(sx)? (Solid [i] ->min.x<=r.org.x): (Solid [i] ->max.x>=r.org.x);
     if (!ok) continue;
     ok=(sy)? (Solid [i] ->min.y<=r.org.y): (Solid [i] ->max.y>=r.org.y);
     if (!ok) continue;
     ok=(sz)? (Solid [i] ->min.z<=r.org.z): (Solid [i] ->max.z>=r.org.z);
     if (!ok) continue;
     ok=(!sx)? (Solid [i] ->min.x>=mx): (Solid [i] ->max.x<=mx);
     if (!ok) continue;
     ok=(!sy)? (Solid [i] ->min.y>=my): (Solid [i] ->max.y<=my);
     if (!ok) continue;
     ok=(!sz)? (Solid [i] ->min.z>=mz): (Solid [i] ->max.z<=mz);
     if (!ok) continue;
     if ( Solid [i] -> Intersect ( ray, t ) ) // if intersect then check distance
       if ( t < ClosestDist )
       {
       ClosestDist = t;
       ClosestObj = Solid [i];
       }
    }
t = ClosestDist;
return ClosestObj;
}

We can use these algorithms with octrees, bsp or with other scene traversal.
---------------------------------------
Be optimized!
tigra

icq 429048706