Text archives Help

---

Author: abe
Date: Sat Jan 28 21:05:26 2006
New Revision: 872

Modified:
   trunk/Model/Groups/VerticalKDTree.cc
   trunk/Model/Groups/VerticalKDTree.h
Log:

Added code to prune rays from the active mask when they miss subtrees.

M    VerticalKDTree.h
M    VerticalKDTree.cc


Modified: trunk/Model/Groups/VerticalKDTree.cc
==============================================================================
--- trunk/Model/Groups/VerticalKDTree.cc        (original)
+++ trunk/Model/Groups/VerticalKDTree.cc        Sat Jan 28 21:05:26 2006
@@ -213,12 +213,6 @@
                                                       
subPacket.getRay(which+p),
                                                       
subPacket.getSigns(which+p),
                                                       
subPacket.getInverseDirection(which+p));
-#if 0
-        if (p_start && valid_mask[p]) {
-          subPacket.scratchpad<ScratchPadInfo>(which+p).payload = 
Color(RGB(1,0,0));
-          
assert(rays.hit(which+p,T_EPSILON*8,getMaterial(),this,(TexCoordMapper *)1));
-        }
-#endif        
         
         // Determine the actual minimum distance.
         minDist[p] = SCIRun::Max( minDist[p], T_EPSILON );
@@ -254,14 +248,9 @@
 
 // Traversal Stack Entry.
 struct Stack {
-#if __ECC
-  __declspec(align(16))
-#endif
-    float t_near[TraversalPacketSize];
-#if __ECC
-  __declspec(align(16)) 
-#endif
-    float t_far [TraversalPacketSize];
+  float t_near[TraversalPacketSize];
+  float t_far [TraversalPacketSize];
+  Mask  mask;
   KDTreeNode* node;
 };
 
@@ -295,7 +284,8 @@
  
   
/////////////////////////////////////////////////////////////////////////////
   // Mask to keep track of rays that still need to find closest 
intersections.
-  Mask active_mask = valid_mask;
+  Mask live_mask = valid_mask;
+  stack[1].mask  = valid_mask;
 
   // Process nodes on the stack.
   while (stack_index) {
@@ -313,6 +303,24 @@
       t_far [p] = stack[stack_index].t_far [p];
     }
 
+    // Obtain the active mask for this subtree.
+    Mask active_mask = stack[stack_index].mask;
+#if 0
+    if (rays.getFlag( RayPacket::DebugPacket )) {
+      std::cerr << "Beginning of descent\n";
+      std::cerr << "t_near: ";
+      for (int p=0;p<TraversalPacketSize;++p) {
+        std::cerr << t_near[p] << " ";
+      }
+      std::cerr << "\n";
+
+      std::cerr << "t_far: ";
+      for (int p=0;p<TraversalPacketSize;++p) {
+        std::cerr << t_far[p] << " ";
+      }
+      std::cerr << "\n";
+    }
+#endif
     // Pop stack.
     stack_index--;
 
@@ -338,7 +346,7 @@
         t_split[p] = (split - rays.getOrigin(which+p,axis)) *
           rays.getInverseDirection(which+p,axis);
       }
-      
+      //#if 0      
       
/////////////////////////////////////////////////////////////////////////
       // Classify the case.
       Mask cmp_result;
@@ -348,6 +356,8 @@
         
///////////////////////////////////////////////////////////////////////
         // Case I: "Near Only"
 
+        //        if (rays.getFlag( RayPacket::DebugPacket )) { std::cerr << 
"A\n"; }
+
         // Update the current node.
         node = node->getChild( far_index );
         
@@ -361,16 +371,19 @@
         
///////////////////////////////////////////////////////////////////////
         // Case II: "Far Only"
 
+        //        if (rays.getFlag( RayPacket::DebugPacket )) { std::cerr << 
"B\n"; }
+
         // Update the current node.
         node = node->getChild( near_index );
 
-        
         // No stack operations.
         continue;
       }
-
+      // #endif
       
/////////////////////////////////////////////////////////////////////////
       // Otherwise:
+
+      //      if (rays.getFlag( RayPacket::DebugPacket )) { std::cerr << 
"C\n"; }
       
       // Case III "Both" -- Push far node on stack.
       stack_index++;
@@ -382,6 +395,11 @@
         stack[stack_index].t_far [p] = t_far[p];
       }
 
+      // Determine the valid mask for the far subtree.
+      set_lte( cmp_result, t_split, t_far );
+      set_and( stack[stack_index].mask, cmp_result, active_mask );
+      // stack[stack_index].mask = active_mask;
+      
       // Update the current node.
       node = node->getChild( near_index );
 
@@ -389,6 +407,10 @@
       for (int p=0;p<TraversalPacketSize;++p) {
         t_far[p] = t_split[p];
       }
+
+      // Update the active mask.      
+      set_lte( cmp_result, t_near, t_far );
+      set_and( active_mask, active_mask, cmp_result );
     }
 
     
///////////////////////////////////////////////////////////////////////////
@@ -451,22 +473,25 @@
 
     /////////////////////////////////////////////////////////////////////
     /////////////////////////////////////////////////////////////////////
-    // Check to see if the hit is inside the current cell.
-
-    // Update the active_mask.
+    // After finding a leaf:
+    // Check for an early exit if all rays terminated.
     Mask cmp_result;
     set_gt( cmp_result, &rays.getMinT(which), t_far );
 
-    // And the active mask with the result of the comparsion.
-    // (only pay attention to bits which are both active and passed the 
comparsion )
-    set_and( active_mask, active_mask, cmp_result );
+    // AND with the active mask to eliminate rays that are not active
+    // in the current subtree.
+    set_or_not( cmp_result, cmp_result, active_mask );
+
+    // Turn off all rays which terminate in this cell.
+    set_and( live_mask, live_mask, cmp_result );
     
     // Check to see if any rays are active any longer.
-    if (none(active_mask)) {
+    if (none(live_mask)) {
 
       // Done with this packet.
       break;
     }
+
   }
 }
 

Modified: trunk/Model/Groups/VerticalKDTree.h
==============================================================================
--- trunk/Model/Groups/VerticalKDTree.h (original)
+++ trunk/Model/Groups/VerticalKDTree.h Sat Jan 28 21:05:26 2006
@@ -115,6 +115,24 @@
       }
     }
 
+    static inline void set_or ( Mask &result, const Mask &vec0, const Mask 
&vec1 ) {
+      for (int p=0;p<TraversalPacketSize;++p) {
+        result[p] = (vec0[p] || vec1[p]);
+      }
+    }
+
+    static inline void set_or_not ( Mask &result, const Mask &vec0, const 
Mask &vec1 ) {
+      for (int p=0;p<TraversalPacketSize;++p) {
+        result[p] = (vec0[p] || (!vec1[p]));
+      }
+    }        
+
+    static inline void set_not( Mask &result, const Mask &vec0 ) {
+      for (int p=0;p<TraversalPacketSize;++p) {
+        result[p] = !(vec0[p]);
+      }
+    }    
+
     static inline bool any( const Mask &mask ) {
       bool result = mask[0];
       for (int p=1;(!result) && (p<TraversalPacketSize);++p) {
@@ -142,18 +160,7 @@
 
       return result;
       
-#if 0
-      bool result = mask[0] || (!active[0]);
-      bool any_active  = active[0];
-
-      for (int p=1;(p<TraversalPacketSize);++p) {
-        result = result && (mask[p] || (!active[p]));
-        any_active = any_active || active[p];
-      }
 
-      // Make sure atleast one bit is active.
-      return result && any_active;
-#endif
     }
 
 
@@ -178,7 +185,7 @@
         : active_mask( active_mask_ ) { };
     };
 
-    std::ostream &operator<< (std::ostream &out, const Mask &mask) {
+    inline std::ostream &operator<< (std::ostream &out, const Mask &mask) {
 
       out << "{ ";
       for (int p=0;p<TraversalPacketSize;++p) {

---

• [MANTA] r872 - trunk/Model/Groups, abe, 01/28/2006

---

Archive powered by MHonArc 2.6.16.