RAYTRACING ALGORITHM





    StartRaytrace(DataSet data, Window W, double D,int m,int n)
      {
         Compute x0,...,xm and y0,...,yn from W dimensions;
         for (i = 0;i<= m;i++)
            for (j=0;j<=n;j++) 
               {
                 Compute ray r from origin to (xi,yj,D);           
                 Color c = Raytrace(data,r,0,1);
                 setPixel(i,j,c);
               }
      } 







    Color Raytrace(DataSet data, ray r, int depth, double energy)
      {
          if (depth > MAXDEPTH) or (energy < MINENERGY) return (0,0,0);
          else {
            (point p, object number k) = ClosestPoint(r,data); 
            if (p == NULL) return (0,0,0);
            else {
              Color c = ambient light model;
              for each light source L 
                 {
                    lr = ray from p toward light L;
                    (lp,j) = ClosestPoint(lr,data - object[k]);
                    if (lp == NULL) c += diffuse + specular components for object[k] and light L
                 }
              F = ReflectedRay(r,p,object[k]);
              T = TransmittedRay(r,p,object[k]);
              ks = specular component for object[k];
              kt = transmissive component for object[k];
              return(energy*c + Raytrace(data,F,n+1,energy*ks) + Raytrace(data,T,n+1,energy*kt);
             }
           }
       }









A WAY TO SPEEDUP RAY/OBJECT INTERSECTIONS


   OctBoxTree Creation

   class Box {
      double x1,x2,y1,y2,z2,z2;
      DataType *data;
      Box *subBox[i];
      boolean isTerminal;
     }

   INITIALIZE
   rootBox dimensions =   XYZ-Minimax box around Data;
   rootBox.data = entire data set

   Box *CreateHierarchy(Box *rootBox,int level) 
        {
           rootBox->isTerminal = true;
           if (level < MAXLEVEL)
              {
                 for (i=0;i<8;i++) {
                     clippeddata = Clip(data,subBox[i])
                     if (clippeddata != NULL) {
                       rootBox->subBox[i] = new Box(subBox dimensions, clippeddata);
                       rootBox->subBox[i] = 
                            CreateHierarchy(rootBox->subBox[i],level+1);
                       rootBox->isTerminal = false;
                     }
                   }
              }
            return (RootBox);
        } 





   AddToBoxStack(ray r, Box *b,boxStack S)
     {
       if (b != NULL && ray r intersects Box b) 
         {
            if (b->isTerminal) push b onto S;
            else 
              for (i=0;i<8;i++) AddToBoxStack(r,b->subBox[i],S);    
         }
     }




   ClosestPoint(ray r, boxTree root)
     {
        boxStack S = empty;
        addToBoxStack(r,root,S)
        while (! S.isEmpty())
         {
           b = S.pop();
           find all points of intersection with data in box b;
         }
        return closest point;
     }