Text archives Help

---

Author: cgribble
Date: Sat Jun  3 21:45:49 2006
New Revision: 1095

Modified:
   trunk/Model/Primitives/GridSpheres.cc
   trunk/Model/Primitives/GridSpheres.h
Log:
Model/Primitives/GridSpheres.cc
Model/Primitives/GridSpheres.h
  Initial profiling on my Mac revealed some obvious optimizations
  Added sphere intersection code optimized for certain cases (CommonOrigin,
    NormalizedDirections, etc.)
  Accessed via a function pointer that's set once per ray packet
  Minor increase in performance, but shifts the bottleneck from Ray/Sphere
    intersection to traversal --> true for render threads, as well as texture
    generation threads
  Experimented with other optimizations based on RayPacket flags, but these
    didn't help and uglified the code terribly, so they're not being committed
  No obvious way to improve performance without tracing packets through the
    grid (at least not that I can see)


Modified: trunk/Model/Primitives/GridSpheres.cc
==============================================================================
--- trunk/Model/Primitives/GridSpheres.cc       (original)
+++ trunk/Model/Primitives/GridSpheres.cc       Sat Jun  3 21:45:49 2006
@@ -65,6 +65,10 @@
 
   counts=0;
   cells=0;
+
+#ifdef USE_FUNCTION_POINER
+  intersectSphere=0;
+#endif
 }
 
 GridSpheres::~GridSpheres()
@@ -361,13 +365,37 @@
   rays.computeInverseDirections();
   rays.computeSigns();
 
+#ifdef USE_OPTIMIZED_FCNS
+  // Determine appropriate sphere intersection function for this ray packet
+  SphereIntersectFcn intersectSphere;
+
+  switch (rays.getAllFlags() & (RayPacket::ConstantOrigin |
+                                RayPacket::NormalizedDirections)) {
+  case RayPacket::ConstantOrigin|RayPacket::NormalizedDirections:
+    // Rays of constant origin and normalized directions
+    intersectSphere=&GridSpheres::intersectSphereCOND;
+    break;
+  case RayPacket::ConstantOrigin:
+    // Rays of constant origin for not normalized directions
+    intersectSphere=&GridSpheres::intersectSphereCO;
+    break;
+  case RayPacket::NormalizedDirections:
+    // Rays of non-constant origin and normalized directions
+    intersectSphere=&GridSpheres::intersectSphereND;
+    break;
+  case 0:
+    // Rays of non-constant origin and non-normalized directions
+    intersectSphere=&GridSpheres::intersectSphereDefault;
+    break;
+  }
+#endif // USE_OPTIMIZED_FCNS
+
   for (int i=rays.begin(); i<rays.end(); ++i) {
     const Vector origin(rays.getOrigin(i));
     const Vector direction(rays.getDirection(i));
     const Vector inv_direction(rays.getInverseDirection(i));
 
     // Intersect ray with bounding box
-#if 1
     Real tnear, tfar;
     int di_dx;
     int ddx;
@@ -460,7 +488,7 @@
     int idx=(ix*ncells + iy)*ncells + iz;
 
     // Compute delta t in each direction
-    Real 
dt_dx=static_cast<Real>(di_dx)*diagonal.x()*inv_ncells*inv_direction.x();
+    Real dt_dx=di_dx*diagonal.x()*inv_ncells*inv_direction.x();
     Real dt_dy=di_dy*diagonal.y()*inv_ncells*inv_direction.y();
     Real dt_dz=di_dz*diagonal.z()*inv_ncells*inv_direction.z();
 
@@ -481,59 +509,11 @@
              tnext.x(), tnext.y(), tnext.z(),
              cellcorner, celldir,
              di_dx, di_dy, di_dz, didx_dx, didx_dy, didx_dz,
-             stop_x, stop_y, stop_z);
+#ifdef USE_OPTIMIZED_FCNS
+             stop_x, stop_y, stop_z, intersectSphere);
 #else
-    Vector v1=(bmin - origin)*inv_direction;
-    Vector v2=(bmax - origin)*inv_direction;
-    Vector vmin=Min(v1, v2);
-    Vector vmax=Max(v1, v2);
-    Real tnear=vmin.maxComponent();
-    Real tfar=vmax.minComponent();
-    if (tnear >= tfar)
-      continue;
-    if (tfar < static_cast<Real>(1.e-6))
-      continue;
-    if (tnear < 0)
-      tnear=0;
-
-    // Compute lattice coordinates
-    Vector p=origin + tnear*direction;
-    Vector lattice=(p - bmin)*inv_diagonal;
-    Vector integer(Clamp(static_cast<int>(lattice.x()*ncells), 0, ncells - 
1),
-                   Clamp(static_cast<int>(lattice.y()*ncells), 0, ncells - 
1),
-                   Clamp(static_cast<int>(lattice.z()*ncells), 0, ncells - 
1));
-    
-    // Compute delta i and stopping criteria in each direction
-    Vector di=Vector(1, 1, 1) - 2*rays.getSigns(i);
-    Vector stop(di.x()>0?ncells:-1, di.y()>0?ncells:-1, di.z()>0?ncells:-1);
-
-    // Compute cell index
-    int idx=(integer.x()*ncells + integer.y())*ncells + integer.z();
-
-    // Compute delta index for each direction
-    Vector didx=di*Vector(ncells*ncells, ncells, 1);
-
-    // Compute delta t for each direction
-    Vector dt=di*diagonal*inv_ncells*inv_direction;
-
-    // Compute far edges of the cell
-    Vector next=integer + Vector(1, 1, 1) - rays.getSigns(i);
-    Vector far=diagonal*next*inv_ncells + bmin;
-
-    // Compute t values at far edges of the cell
-    Vector tnext=(far - origin)*inv_direction;
-
-    // Compute cell corner and direction
-    Vector factor(ncells*inv_diagonal);
-    Vector cellcorner((origin - bmin)*factor);
-    Vector celldir(direction*factor);
-
-    // Traverse the hierarchy
-    traverse(i, rays, depth, tnear, integer.x(), integer.y(), integer.z(),
-             idx, dt.x(), dt.y(), dt.z(), tnext.x(), tnext.y(), tnext.z(),
-             cellcorner, celldir, di.x(), di.y(), di.z(),
-             didx.x(), didx.y(), didx.z(), stop.x(), stop.y(), stop.z());
-#endif
+             stop_x, stop_y, stop_z);
+#endif // USE_OPTIMIZED_FCNS
   }
 }
 
@@ -670,7 +650,12 @@
                            const Vector& cellcorner, const Vector& celldir,
                            int di_dx, int di_dy, int di_dz,
                            int didx_dx, int didx_dy, int didx_dz,
+#ifdef USE_OPTIMIZED_FCNS
+                           int stop_x, int stop_y, int stop_z,
+                           SphereIntersectFcn intersectSphere) const
+#else
                            int stop_x, int stop_y, int stop_z) const
+#endif // USE_OPTIMIZED_FCNS
 {
   if (depth>0) {
     // Traverse the macrocell layers
@@ -715,7 +700,11 @@
                  new_cellcorner, new_celldir,
                  di_dx, di_dy, di_dz,
                  didx_dx, didx_dy, didx_dz,
+#ifdef USE_OPTIMIZED_FCNS
+                 stop_x, stop_y, stop_z, intersectSphere);
+#else
                  stop_x, stop_y, stop_z);
+#endif // USE_OPTIMIZED_FCNS
       }
 
       // March to next macrocell at the current depth
@@ -764,8 +753,14 @@
           radius2=radius*radius;
         }
 
-        intersectSphere(rays, ray_idx, start + j,
-                        Vector(data[0], data[1], data[2]), radius2);
+#ifdef USE_OPTIMIZED_FCNS
+        // Intersect the sphere using the appropriately optimized function
+        (*this.*intersectSphere)(rays, ray_idx, start + j,
+                                 Vector(data[0], data[1], data[2]), radius2);
+#else
+        intersectSphereDefault(rays, ray_idx, start + j,
+                               Vector(data[0], data[1], data[2]), radius2);
+#endif
       }
 
       // March to the next cell
@@ -795,16 +790,41 @@
   }
 }
 
-void GridSpheres::intersectSphere(RayPacket& rays, int ray_idx, int idx,
-                                  const Vector& center, float radius2) const
+#ifdef USE_OPTIMIZED_FCNS
+void GridSpheres::intersectSphereCOND(RayPacket& rays, int ray_idx, int idx,
+                                      const Vector& center, float radius2) 
const
 {
-  Vector O(rays.getOrigin(ray_idx) - center);
+  // Rays of constant origin and normalized directions
+  Vector O(rays.getOrigin(0) - center);
+  Real C=Dot(O, O) - radius2;
   Vector D(rays.getDirection(ray_idx));
-  Real A=Dot(D, D);
   Real B=Dot(O, D);
+  Real disc=B*B - C;
+  if (disc >= 0) {
+    Real r=Sqrt(disc);
+    Real t0=-(r + B);
+    if (t0 > T_EPSILON) {
+      if (rays.hit(ray_idx, t0, this, this, this))
+        rays.scratchpad<int>(ray_idx)=cells[idx];
+    } else {
+      Real t1=r - B;
+      if (rays.hit(ray_idx, t1, this, this, this))
+        rays.scratchpad<int>(ray_idx)=cells[idx];
+    }
+  }
+}
+
+void GridSpheres::intersectSphereCO(RayPacket& rays, int ray_idx, int idx,
+                                    const Vector& center, float radius2) 
const
+{
+  // Rays of constant origin for not normalized directions
+  Vector O(rays.getOrigin(0) - center);
   Real C=Dot(O, O) - radius2;
+  Vector D(rays.getDirection(ray_idx));
+  Real A=Dot(D, D);
+  Real B=Dot(O, D);
   Real disc=B*B - A*C;
-  if (disc >= 0){
+  if (disc >= 0) {
     Real r=Sqrt(disc);
     Real t0=-(r + B)/A;
     if (t0 > T_EPSILON) {
@@ -814,6 +834,55 @@
       Real t1=(r - B)/A;
       if (rays.hit(ray_idx, t1, this, this, this))
         rays.scratchpad<int>(ray_idx)=cells[idx];
+    }
+  }
+}
+
+void GridSpheres::intersectSphereND(RayPacket& rays, int ray_idx, int idx,
+                                    const Vector& center, float radius2) 
const
+{
+  // Rays of non-constant origin and normalized directions
+  Vector O(rays.getOrigin(ray_idx) - center);
+  Vector D(rays.getDirection(ray_idx));
+  Real B=Dot(O, D);
+  Real C=Dot(O, O) - radius2;
+  Real disc=B*B - C;
+  if (disc >= 0) {
+    Real r=Sqrt(disc);
+    Real t0=-(r + B);
+    if (t0 > T_EPSILON) {
+      if (rays.hit(ray_idx, t0, this, this, this))
+        rays.scratchpad<int>(ray_idx)=cells[idx];
+    } else {
+      Real t1=r - B;
+      if (rays.hit(ray_idx, t1, this, this, this))
+        rays.scratchpad<int>(ray_idx)=cells[idx];
+    }
+  }
+}
+#endif // USE_OPTIMIZED_FCNS
+
+void GridSpheres::intersectSphereDefault(RayPacket& rays, int ray_idx, int 
idx,
+                                         const Vector& center,
+                                         float radius2) const
+{
+  // Rays of non-constant origin and non-normalized directions
+  Vector O(rays.getOrigin(ray_idx) - center);
+  Vector D(rays.getDirection(ray_idx));
+  Real A=Dot(D, D);
+  Real B=Dot(O, D);
+  Real C=Dot(O, O) - radius2;
+  Real disc=B*B - A*C;
+  if (disc >= 0) {
+    Real r=Sqrt(disc);
+    Real t0=-(r + B)/A;
+    if (t0 > T_EPSILON) {
+      if (rays.hit(ray_idx, t0, this, this, this))
+        rays.scratchpad<int>(ray_idx)=cells[idx];
+    } else {
+      Real t1=(r - B)/A;
+      if (rays.hit(ray_idx, t1, this, this, this));
+      rays.scratchpad<int>(ray_idx)=cells[idx];
     }
   }
 }

Modified: trunk/Model/Primitives/GridSpheres.h
==============================================================================
--- trunk/Model/Primitives/GridSpheres.h        (original)
+++ trunk/Model/Primitives/GridSpheres.h        Sat Jun  3 21:45:49 2006
@@ -9,6 +9,8 @@
 #include <Model/Primitives/PrimitiveCommon.h>
 #include <Model/Materials/LitMaterial.h>
 
+#define USE_OPTIMIZED_FCNS
+
 namespace Manta {
   class RegularColorMap;
 
@@ -35,6 +37,11 @@
                                   RayPacket& rays) const;
 
   protected:
+#ifdef USE_OPTIMIZED_FCNS
+    typedef void (GridSpheres::*SphereIntersectFcn)(RayPacket&, int, int,
+                                                    const Vector&, float) 
const;
+#endif
+
     struct MCell {
       int nspheres;
       float* max;
@@ -50,14 +57,29 @@
                   const Vector& corner, const Vector& celldir,
                   int di_dx, int di_dy, int di_dz,
                   int didx_dx, int didx_dy,
+#ifdef USE_OPTIMIZED_FCNS
+                  int didx_dz, int stop_x, int stop_y, int stop_z,
+                  SphereIntersectFcn intersectSphere) const;
+#else
                   int didx_dz, int stop_x, int stop_y, int stop_z) const;
-    void intersectSphere(RayPacket& rays, int i, int idx,
-                         const Vector& center, float radius2) const;
+#endif // USE_OPTIMIZED_FCNS
     void transformToLattice(const BBox& box, int& sx, int& sy, int& sz,
                             int& ex, int& ey, int& ez) const;
     int mapIdx(int ix, int iy, int iz, int depth);
     void fillMCell(MCell& mcell, int depth, int startidx) const;
     void mapDiffuseColors(Packet<Color>& diffuse, RayPacket& rays) const;
+
+#ifdef USE_OPTIMIZED_FCNS
+    // Sphere intersection functions
+    void intersectSphereCOND(RayPacket& rays, int ray_idx, int idx,
+                             const Vector& center, float radius2) const;
+    void intersectSphereCO(RayPacket& rays, int ray_idx, int idx,
+                           const Vector& center, float radius2) const;
+    void intersectSphereND(RayPacket& rays, int ray_idx, int idx,
+                           const Vector& center, float radius2) const;
+#endif // USE_OPTIMIZED_FCNS
+    void intersectSphereDefault(RayPacket& rays, int ray_idx, int idx,
+                                const Vector& center, float radius2) const;
 
     float* spheres;
     int nspheres;

---

• [MANTA] r1095 - trunk/Model/Primitives, cgribble, 06/03/2006

---

Archive powered by MHonArc 2.6.16.