Text archives Help

---

Author: boulos
Date: Mon Jul  9 15:35:09 2007
New Revision: 1456

Modified:
   trunk/Model/Groups/DynBVH.cc
   trunk/Model/Groups/DynBVH.h
Log:
Adding beginnings of approximate SAH build, works
fine but doesn't gain much perf yet due to recomputing
the bounds.


Modified: trunk/Model/Groups/DynBVH.cc
==============================================================================
--- trunk/Model/Groups/DynBVH.cc        (original)
+++ trunk/Model/Groups/DynBVH.cc        Mon Jul  9 15:35:09 2007
@@ -451,7 +451,7 @@
       object_ids.resize(group->getSize());
     }
 
-    currGroup = group;    
+    currGroup = group;
 
     for ( int i = 0; i < currGroup->getSize(); i++ )
       object_ids[i] = i;
@@ -468,8 +468,8 @@
          << "build ("<<updateBound_start-build_start<<")\n"
          << "updateBounds ("<<end-updateBound_start<<")\n"
          << "BBox = ("<<nodes[0].bounds.getMin()<<", 
"<<nodes[0].bounds.getMax()<<"\n\n";
-    
-    
+
+
   }
 }
 
@@ -487,7 +487,13 @@
     BVHNode& node = nodes[nodeID];
 
     int bestAxis = -1;
-    int split = partitionSAH(context, objectBegin,objectEnd,bestAxis);
+    int split = -1;
+    int num_objects = objectEnd - objectBegin;
+    if (num_objects < 32) {
+      split = partitionSAH(context, objectBegin,objectEnd,bestAxis);
+    } else {
+      split = partitionApproxSAH(context, objectBegin,objectEnd,bestAxis);
+    }
 
     if (bestAxis == -1)
     {
@@ -548,6 +554,122 @@
         node.bounds.extendByBox(left_node.bounds);
         node.bounds.extendByBox(right_node.bounds);
     }
+}
+
+int DynBVH::partitionApproxSAH(const PreprocessContext& context,
+                               int objBegin,
+                               int objEnd,
+                               int& output_axis) {
+  int num_objects = objEnd - objBegin;
+  if ( num_objects == 1 ) {
+    output_axis = -1;
+    return -1;
+  }
+
+  BVHCostEval best_cost;
+  best_cost.cost = BVH_C_isec * num_objects;
+  best_cost.axis = -1;
+
+  // TODO(boulos): Avoid recomputing overall bounds
+  BBox overall_bounds;
+  for (int i = objBegin; i < objEnd; i++) {
+    // NOTE(boulos): computeBounds extends the passed in box
+    currGroup->get(object_ids[i])->computeBounds(context, overall_bounds);
+  }
+
+  float inv_overall_area = overall_bounds.computeArea();
+
+  for ( int axis = 0; axis < 3; axis++ ) {
+    // TODO(boulos): Switch to object bounds for small number of 
primitives...
+    const int num_samples = 8;
+    // Use the 1-d hammersley samples (uniform in 1d)
+    float n_inv = 1./static_cast<float>(num_samples);
+    float axis_min = overall_bounds.getMin()[axis];
+    float axis_max = overall_bounds.getMax()[axis];
+    float axis_width = axis_max - axis_min;
+    for (int s = 0; s < num_samples; s++) {
+      float sample_position = axis_min + (s * n_inv) * axis_width;
+      // Scan over all objects and determine which side they're on
+      // TODO(boulos): Pregenerate a list of boxes?
+      BBox left_box;
+      BBox right_box;
+      int num_left = 0;
+      int num_right = 0;
+      for (int i = objBegin; i < objEnd; i++) {
+        BBox obj_box;
+        currGroup->get(object_ids[i])->computeBounds(context, obj_box);
+        if (obj_box.center()[axis] < sample_position) {
+          left_box.extendByBox(obj_box);
+          num_left++;
+        } else {
+          right_box.extendByBox(obj_box);
+          num_right++;
+        }
+      }
+
+      // Evaluate SAH: left_box.area * num_left + right_box.area * num_right
+      float cost = (left_box.computeArea() * num_left +
+                    right_box.computeArea() * num_right);
+      cost /= overall_bounds.computeArea();
+      cost *= BVH_C_isec;
+      cost += BVH_C_trav;
+
+      if (cost < best_cost.cost) {
+        //cerr << "Found new best cost on axis " << axis << " and cost " << 
cost;
+        //cerr << " (sample id = " << s << ")" << endl;
+        // Found new best cost
+        best_cost.cost = cost;
+        best_cost.axis = axis;
+        best_cost.position = sample_position;
+        best_cost.num_left = num_left;
+        best_cost.num_right = num_right;
+        best_cost.event = -1; // Unused
+      }
+    }
+  }
+
+  output_axis = best_cost.axis;
+  if ( output_axis != -1 ) {
+    // write out object ids [objBegin,objEnd) in appropriate order
+
+    // First collect all the left_objs and right_objs into local
+    // vectors (because we need to copy them out)
+    std::vector<int> left_objs;
+    std::vector<int> right_objs;
+    for (int i = objBegin; i < objEnd; i++) {
+      BBox obj_box;
+      currGroup->get(object_ids[i])->computeBounds(context, obj_box);
+      if (obj_box.center()[output_axis] < best_cost.position) {
+        left_objs.push_back(object_ids[i]);
+      } else {
+        right_objs.push_back(object_ids[i]);
+      }
+    }
+
+    // Write them back in order
+    for (size_t i = 0; i < left_objs.size(); i++) {
+      object_ids[i + objBegin] = left_objs[i];
+    }
+
+    for (size_t i = 0; i < right_objs.size(); i++) {
+      object_ids[i + objBegin + left_objs.size()] = right_objs[i];
+    }
+    if (left_objs.size() == (size_t)num_objects ||
+        left_objs.size() == 0) {
+      // Splitting didn't find a valid split, split in the middle unless
+      // we have too few
+      const int kMinObjects = 3;
+      if (num_objects < kMinObjects) {
+        output_axis = -1;
+        return 0;
+      }
+      return objBegin + num_objects / 2;
+    }
+    return objBegin + left_objs.size();
+  }
+
+  // making a leaf
+  return 0;
 }
 
 int DynBVH::partitionSAH(const PreprocessContext& context,

Modified: trunk/Model/Groups/DynBVH.h
==============================================================================
--- trunk/Model/Groups/DynBVH.h (original)
+++ trunk/Model/Groups/DynBVH.h Mon Jul  9 15:35:09 2007
@@ -97,8 +97,12 @@
 
 
     protected:
-        int partitionSAH(const PreprocessContext& context,
-                         int objBegin, int objEnd, int& output_axis);
+      int partitionSAH(const PreprocessContext& context,
+                       int objBegin, int objEnd, int& output_axis);
+      int partitionApproxSAH(const PreprocessContext& context,
+                             int objBegin,
+                             int objEnd,
+                             int& output_axis);
 
         struct BVHCostEval
         {

---

• [MANTA] r1456 - trunk/Model/Groups, boulos, 07/09/2007

---

Archive powered by MHonArc 2.6.16.