Text archives Help

---

Author: thiago
Date: Fri Jan 25 12:45:02 2008
New Revision: 2007

Modified:
   trunk/Model/Groups/KDTree.cc
   trunk/Model/Groups/KDTree.h
Log:
Added a single ray traversal path (no loop overheads).

Modified: trunk/Model/Groups/KDTree.cc
==============================================================================
--- trunk/Model/Groups/KDTree.cc        (original)
+++ trunk/Model/Groups/KDTree.cc        Fri Jan 25 12:45:02 2008
@@ -336,6 +336,7 @@
   const int ray_end   = rays.end();
 
   if (!rays.getFlag(RayPacket::ConstantSigns)) {
+    TrvStack trvStack[80];
     for (int first=ray_begin; first < ray_end; ++first) {
       int last = first+1;
       for (; last < ray_end; ++last) {
@@ -345,14 +346,32 @@
           break;
         }
       }
-      RayPacket sameSignSubpacket(rays, first, last);
-      sameSignSubpacket.setFlag(RayPacket::ConstantSigns);
-      sameSignSubpacket.resetFlag(RayPacket::HaveCornerRays);
-      intersect(context, sameSignSubpacket);
-      first = last-1;
+      if (first+1==last) {
+        RayPacket singleRayPacket(rays, first, last);
+        Vector origin = rays.getOrigin( first );
+        Vector direction = rays.getDirection( first );
+        Vector inverse_direction = rays.getInverseDirection(first);
+        
traverse(context,singleRayPacket,origin,direction,inverse_direction,trvStack);
+       }
+      else {
+        RayPacket sameSignSubpacket(rays, first, last);
+        sameSignSubpacket.setFlag(RayPacket::ConstantSigns);
+        sameSignSubpacket.resetFlag(RayPacket::HaveCornerRays);
+        intersect(context, sameSignSubpacket);
+        first = last-1;
+      }
     }
     return;
   }
+  else if (ray_begin+1 == ray_end) {
+    TrvStack trvStack[80];
+    const Vector origin = rays.getOrigin( rays.begin() );
+    const Vector direction = rays.getDirection( rays.begin() );
+    const Vector inverse_direction = rays.getInverseDirection(rays.begin());
+    traverse(context,rays,origin,direction,inverse_direction,trvStack);
+    return;
+  }
+    
 
   const bool COMMON_ORIGIN = rays.getFlag(RayPacket::ConstantOrigin);
 
@@ -842,6 +861,85 @@
     }
   }
 }
+
+void KDTree::traverse(const RenderContext &context, RayPacket &ray,
+                      const Vector &org, const Vector &dir,
+                      const Vector &rcp, TrvStack *const stackBase)
+  const
+{
+#ifdef COLLECT_STATS
+  nTotalRays += ray.end() - ray.begin();
+#endif
+  float t_n = T_EPSILON;
+  float t_f = ray.getMinT( ray.begin() );
+
+  const int signs[3] = {dir[0] < 0, dir[1] < 0, dir[2] < 0};
+
+  for (int k=0;k<3;k++) {
+    if (signs[k]) {
+      const float k0 = (bounds[1][k] - org[k]) * rcp[k];
+      t_n = Max(t_n,k0);
+      const float k1 = (bounds[0][k] - org[k]) * rcp[k];
+      t_f = Min(t_f,k1);
+    } else {
+      const float k0 = (bounds[0][k] - org[k]) * rcp[k];
+      t_n = Max(t_n,k0);
+      const float k1 = (bounds[1][k] - org[k]) * rcp[k];
+      t_f = Min(t_f,k1);
+    }
+    if (t_n > t_f) 
+      return;
+  };
+  TrvStack *stackPtr = stackBase;
+  int nodeID = 0;
+
+  while (1) {
+#ifdef COLLECT_STATS
+    nTraversals++;
+#endif
+    const Node &node = this->node[nodeID];
+    if (node.isLeaf) {
+#ifdef COLLECT_STATS
+      nIntersects += node.numPrimitives;
+#endif
+      int primOffset = node.childIdx;
+      for (int i=0; i<node.numPrimitives; ++i) {
+        const int triID = itemList[primOffset+i];
+        currGroup->get(triID)->intersect(context, ray);
+      }
+      if (stackPtr <= stackBase)
+        return;
+      --stackPtr;
+      const float newT = ray.getMinT( ray.begin() );
+      if (newT <= t_f)
+        return;
+      nodeID = stackPtr->nodeID;
+      t_n = t_f;
+      t_f = Min(newT,stackPtr->t);
+    } 
+    else {
+      const float t_p = (node.planePos - org[node.planeDim]) * 
rcp[node.planeDim];
+
+      const int frontChild = node.childIdx+signs[node.planeDim];
+      const int backChild  = node.childIdx+1-signs[node.planeDim];
+
+      if (t_p < t_n) {
+        nodeID = backChild;
+      }
+      else if (t_p > t_f) {
+        nodeID = frontChild;
+      }
+      else {
+        stackPtr->nodeID = backChild;
+        stackPtr->t = t_f;
+        ++stackPtr;
+
+        nodeID = frontChild;
+        t_f = t_p;
+      }
+    }
+  }
+};
 
 
 

Modified: trunk/Model/Groups/KDTree.h
==============================================================================
--- trunk/Model/Groups/KDTree.h (original)
+++ trunk/Model/Groups/KDTree.h Fri Jan 25 12:45:02 2008
@@ -135,6 +135,16 @@
 #endif
                        ) const;
 #endif
+
+    //single ray traversal
+    struct TrvStack {
+      int nodeID;
+      float t;
+    };
+    void traverse(const RenderContext &context, RayPacket &ray,
+                  const Vector &org, const Vector &dir,
+                  const Vector &rcp, TrvStack *const stackBase) const;
+
     bool intersectBounds(const RenderContext& context, RayPacket& rays) 
const;
 
     void computeBounds(const PreprocessContext&,

---

• [Manta] r2007 - trunk/Model/Groups, thiago, 01/25/2008

---

Archive powered by MHonArc 2.6.16.