Text archives Help

---

Author: boulos
Date: Wed Apr  2 18:34:16 2008
New Revision: 2163

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

 Removing "cached" bounding box passing around. It doesn't actually
 save any work and for a lazy build would actually be an unnecessary
 penalty. Also removes needless BBox& left_bounds, BBox& right_bounds
 from function args (which is a plus) and doesn't penalize build
 methods that don't need voxel bounds (BIH and others?).

 Restoring the parallelComputeBounds usage before
 parallelComputeBins. Also adding centroid_bounds to that computation
 for the approximate SAH.

 Updating parallelComputeBins to use scale factor instead of logic to
 place the sample elsewhere.

 Updating the sweep build to be a bit more efficient (use cached
 bboxes and centroids as well as partitionObjects instead of recomputing the
 sweep).


Modified: trunk/Model/Groups/DynBVH.cc
==============================================================================
--- trunk/Model/Groups/DynBVH.cc        (original)
+++ trunk/Model/Groups/DynBVH.cc        Wed Apr  2 18:34:16 2008
@@ -1061,13 +1061,8 @@
   int* vals = (int*)task->scratchpad_data;
   int bestAxis = vals[0];
   int split = vals[1];
-
-  BBox* boxes = (BBox*)task->scratchpad_data;
   BVHNode& node = nodes[nodeID];
 
-  BBox& left_box = boxes[1];
-  BBox& right_box = boxes[2];
-
   if (bestAxis == -1) {
     // make leaf
     node.makeLeaf(objectBegin, objectEnd-objectBegin);
@@ -1092,8 +1087,6 @@
     int left_son = node.child;
     int right_son = left_son + 1;
 
-    nodes[left_son].bounds = left_box;
-    nodes[right_son].bounds = right_box;
     // Recurse into two subtrees
     taskpool_mutex.lock();
 
@@ -1149,8 +1142,7 @@
 // We know that there is "lots of work" (objectEnd - objectBegin is
 // sort of big), so no need to check for small cases here
 void DynBVH::parallelApproximateSAH(Task* task, int nodeID, int objectBegin, 
int objectEnd, UpdateContext context) {
-  // Now kick off a parallel bin computation
-  BBox& overall_bounds = nodes[nodeID].bounds;
+  // First kick off a parallel bounds computation
   const int kBinningObjects = 1024;
   int num_objects = objectEnd - objectBegin;
   int num_tasks = num_objects / kBinningObjects;
@@ -1177,19 +1169,17 @@
     Task* child = new (TaskMemory + sizeof(Task) * (first_task + i)) Task
       (new (FourArgCallbackMemory + 
(callback_id+i)*sizeof(BVHBuildTask))BVHBuildTask
        (this,
-        &DynBVH::parallelComputeBins,
+        &DynBVH::parallelComputeBounds,
         nodeID,
         begin,
         end,
         context));
-    BBox* task_bounds = (BBox*)child->scratchpad_data;
-    *task_bounds = overall_bounds;
     children->push_back(child);
   }
 
   children->setReduction(new (FiveArgCallbackMemory + reduction_id * 
sizeof(BVHSAHReduction))BVHSAHReduction
                          (this,
-                          &DynBVH::parallelComputeBinsReduction,
+                          &DynBVH::parallelComputeBoundsReduction,
                           task,
                           nodeID,
                           objectBegin,
@@ -1203,12 +1193,16 @@
 }
 
 void DynBVH::parallelComputeBounds(Task* task, int nodeID, int objectBegin, 
int objectEnd, UpdateContext context) {
-  BBox result;
+  BBox exact_bounds;
+  BBox centroid_bounds;
   for (int i = objectBegin; i < objectEnd; i++) {
-    result.extendByBox(obj_bounds[object_ids[i]]);
+    exact_bounds.extendByBox(obj_bounds[object_ids[i]]);
+    centroid_bounds.extendByPoint(obj_centroids[object_ids[i]]);
   }
-  BBox* output = (BBox*)task->scratchpad_data;
-  *output = result;
+  BBox* boxes = (BBox*)task->scratchpad_data;
+  boxes[0] = exact_bounds;
+  boxes[1] = centroid_bounds;
+
   //cerr << MANTA_FUNC << " NodeID " << nodeID << " has bounds " << result 
<< endl;
   task->finished();
 }
@@ -1222,9 +1216,11 @@
   // Merge the bounds
   TaskList& list = *tasklist;
   BBox overall_bounds;
+  BBox centroid_bounds;
   for (size_t i = 0; i < list.tasks.size(); i++) {
     BBox* task_bounds = (BBox*)list.tasks[i]->scratchpad_data;
-    overall_bounds.extendByBox(*task_bounds);
+    overall_bounds.extendByBox(task_bounds[0]);
+    centroid_bounds.extendByBox(task_bounds[1]);
   }
   //cerr << MANTA_FUNC << " NodeID " << nodeID << " has bounds " << 
overall_bounds << endl;
 
@@ -1261,7 +1257,8 @@
         end,
         context));
     BBox* task_bounds = (BBox*)child->scratchpad_data;
-    *task_bounds = overall_bounds;
+    task_bounds[0] = overall_bounds;
+    task_bounds[1] = centroid_bounds;
     children->push_back(child);
   }
 
@@ -1279,7 +1276,11 @@
 
 void DynBVH::parallelComputeBins(Task* task, int nodeID, int objectBegin, 
int objectEnd, UpdateContext context) {
   // The overall bounds is in the scratch pad
-  BBox& overall_bounds = *((BBox*)task->scratchpad_data);
+  BBox* boxes = (BBox*)(task->scratchpad_data);
+  // NOTE(boulos): Interestingly the binning only needs the centroid
+  //bounds while the cost determination needs the overall bounds...
+  //BBox& overall_bounds = boxes[0];
+  BBox& centroid_bounds = boxes[1];
   //cerr << MANTA_FUNC << " NodeID " << nodeID << " has bounds " << 
overall_bounds << endl;
   struct SampleBin {
     SampleBin() { count = 0; }
@@ -1292,24 +1293,19 @@
   const int num_samples = BVH_num_samples;
   SampleBin bins[3][num_samples];
 
-  Vector min_point = overall_bounds.getMin();
-  Vector max_point = overall_bounds.getMax();
+  Vector min_point = centroid_bounds.getMin();
+  Vector max_point = centroid_bounds.getMax();
   Vector width = max_point - min_point;
+  Vector scale((num_samples/width[0]) * .999f,
+               (num_samples/width[1]) * .999f,
+               (num_samples/width[2]) * .999f);
 
   for (int i = objectBegin; i < objectEnd; i++) {
     BBox& obj_box = obj_bounds[object_ids[i]];
     Vector& obj_centroid = obj_centroids[object_ids[i]];
     for (int axis = 0; axis < 3; axis++) {
       // Sample bin is where this position would fall to the left
-      // int(num_samples * (centroid[axis] - min_point[axis])/width[axis])
-      int which_bin = static_cast<int>
-        (num_samples * (obj_centroid[axis] - min_point[axis])/width[axis]);
-
-      if (width[axis] == 0)
-        which_bin = 0;
-      else if (which_bin >= num_samples)
-        which_bin = num_samples - 1;
-
+      int which_bin = static_cast<int>((obj_centroid[axis] - 
min_point[axis]) * scale[axis]);
       bins[axis][which_bin].count++;
       bins[axis][which_bin].bounds.extendByBox(obj_box);
     }
@@ -1321,11 +1317,13 @@
       *output++ = bins[i][s];
     }
   }
+  BBox* centroid_output = (BBox*)output;
+  *centroid_output = centroid_bounds;
 
   task->finished();
 }
 
-inline int DynBVH::partitionObjects(int objBegin, int objEnd, int axis, 
float position, BBox& left_bounds, BBox& right_bounds) const {
+inline int DynBVH::partitionObjects(int objBegin, int objEnd, int axis, 
float position) const {
   //cerr << MANTA_FUNC << " begin = " << objBegin << ", end = " << objEnd << 
endl;
   int first = objBegin;
   int last  = objEnd;
@@ -1347,17 +1345,6 @@
       object_ids[first] = object_ids[last];
       object_ids[last]  = temp;
     } else {
-      // NOTE(boulos): The bounds can't be computed during the
-      // partitioning because the order is changing all over the
-      // place.
-      left_bounds.reset();
-      right_bounds.reset();
-      for (int i = objBegin; i < first; i++) {
-        left_bounds.extendByBox(obj_bounds[object_ids[i]]);
-      }
-      for (int i = first; i < objEnd; i++) {
-        right_bounds.extendByBox(obj_bounds[object_ids[i]]);
-      }
       return first;
     }
   }
@@ -1383,6 +1370,7 @@
   // Merge the bins
   TaskList& list = *tasklist;
   BBox overall_bounds;
+  BBox centroid_bounds;
   for (size_t i = 0; i < list.tasks.size(); i++) {
     SampleBin* task_bins = (SampleBin*)list.tasks[i]->scratchpad_data;
     for (int axis = 0; axis < 3; axis++) {
@@ -1393,15 +1381,20 @@
         overall_bounds.extendByBox(task_bin.bounds);
       }
     }
+    if (i == 0) {
+      // NOTE(boulos): Every task has the centroid bounds immediately 
following the SampleBins
+      BBox* box = (BBox*)(task_bins + 1);
+      centroid_bounds = *box;
+    }
   }
 
-  float inv_overall_area = 1.f/overall_bounds.computeArea();
-  Vector min_point = overall_bounds.getMin();
-  Vector max_point = overall_bounds.getMax();
+
+  Vector min_point = centroid_bounds.getMin();
+  Vector max_point = centroid_bounds.getMax();
   Vector width = max_point - min_point;
   // Search for best cost
   BVHCostEval best_cost;
-  best_cost.cost = BVH_C_isec * num_objects;
+  best_cost.cost = num_objects * overall_bounds.computeArea();
   best_cost.axis = -1;
   best_cost.position = FLT_MAX;
   best_cost.event = -1;
@@ -1439,10 +1432,6 @@
     for (int i = 0; i < num_samples - 1; i++) {
       float cost = (left_areas[i] * left_counts[i] +
                     right_areas[i] * right_counts[i]);
-      cost *= inv_overall_area;
-      cost *= BVH_C_isec;
-      cost += BVH_C_trav;
-
       if (cost < best_cost.cost) {
         // Found new best cost
         best_cost.cost = cost;
@@ -1471,12 +1460,9 @@
   // ids based on the axis and position
 
   // TODO(boulos): Actually do this in parallel
-  // 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)
-  BBox left_box, right_box;
-  int middle = partitionObjects(objectBegin, objectEnd, best_cost.axis, 
best_cost.position, left_box, right_box);
+  // write out object ids [objBegin,objEnd) in appropriate order
+  int middle = partitionObjects(objectBegin, objectEnd, best_cost.axis, 
best_cost.position);
   if (middle == objectBegin || middle == objectEnd) {
     // Splitting didn't find a valid split, split in the middle unless
     // we have too few
@@ -1484,23 +1470,10 @@
     if (num_objects < kMinObjects) {
       vals[0] = -1;
     } else {
-      left_box.reset();
-      right_box.reset();
       middle = objectBegin + num_objects / 2;
-      for (int i = objectBegin; i < middle; i++) {
-        left_box.extendByBox(obj_bounds[object_ids[i]]);
-      }
-      for (int i = middle; i < objectEnd; i++) {
-        right_box.extendByBox(obj_bounds[object_ids[i]]);
-      }
     }
   }
   vals[1] = middle;
-  BBox* boxes = (BBox*)task->scratchpad_data;
-  // NOTE(boulos): Intentionally waste the space between vals[1]
-  // and boxes[1] (don't want to use boxes[0] and stomp the vals)
-  boxes[1] = left_box;
-  boxes[2] = right_box;
   splitBuild(task, nodeID, objectBegin, objectEnd, context);
 }
 
@@ -1534,21 +1507,15 @@
     } else {
       int bestAxis = -1;
       int split = -1;
-      BBox left_box, right_box;
 #if USE_APPROXIMATE_BUILD
-      split = partitionApproxSAH(preprocess_context, nodeID, objectBegin, 
objectEnd, bestAxis, left_box, right_box);
+      split = partitionApproxSAH(preprocess_context, nodeID, objectBegin, 
objectEnd, bestAxis);
 #else
-      split = partitionSAH(preprocess_context, nodeID, objectBegin, 
objectEnd, bestAxis, left_box, right_box);
+      split = partitionSAH(preprocess_context, nodeID, objectBegin, 
objectEnd, bestAxis);
 #endif
 
       int* vals = (int*)task->scratchpad_data;
       vals[0] = bestAxis;
       vals[1] = split;
-      BBox* boxes = (BBox*)task->scratchpad_data;
-      // NOTE(boulos): Intentionally waste the space between vals[1]
-      // and boxes[1] (don't want to use boxes[0] and stomp the vals)
-      boxes[1] = left_box;
-      boxes[2] = right_box;
       splitBuild(task, nodeID, objectBegin, objectEnd, context);
     }
   }
@@ -1600,17 +1567,14 @@
 
   allocate();
 
-  BBox overall_bounds;
   for ( size_t i = 0; i < currGroup->size(); i++ ) {
     object_ids[i] = i;
     currGroup->get(i)->computeBounds(context, obj_bounds[i]);
     obj_centroids[i] = obj_bounds[i].center();
-    overall_bounds.extendByBox(obj_bounds[i]);
   }
 
   num_nodes.set(1);
   nextFree.set(1);
-  nodes[0].bounds = overall_bounds;
 
   double build_start = Time::currentSeconds();
 
@@ -1648,12 +1612,11 @@
 
   int bestAxis = -1;
   int split = -1;
-  BBox left_box, right_box;
   // NOTE(abe): 30% slower rendering for a single CAD dataset.
 #if USE_APPROXIMATE_BUILD
-  split = partitionApproxSAH(context,nodeID,objectBegin,objectEnd,bestAxis, 
left_box, right_box);
+  split = partitionApproxSAH(context,nodeID,objectBegin,objectEnd,bestAxis);
 #else
-  split = partitionSAH(context,nodeID,objectBegin,objectEnd,bestAxis, 
left_box, right_box);
+  split = partitionSAH(context,nodeID,objectBegin,objectEnd,bestAxis);
 #endif
 
   if (bestAxis == -1) {
@@ -1675,11 +1638,6 @@
     node.makeInternal(my_spot, bestAxis);
     num_nodes++;
 
-    BVHNode& left_son  = nodes[node.child+0];
-    BVHNode& right_son = nodes[node.child+1];
-    left_son.bounds = left_box;
-    right_son.bounds = right_box;
-
     build(context, node.child+0,objectBegin,split);
     build(context, node.child+1, split, objectEnd);
   }
@@ -1695,6 +1653,10 @@
     lazybuild_mutex.unlockMutex(mutex_id);
     return;
   }
+
+  int objectBegin = build_records[nodeID].objectBegin;
+  int objectEnd   = build_records[nodeID].objectEnd;
+
   if (nodeID == 0) {
     BBox overall_bounds;
     for ( size_t i = 0; i < currGroup->size(); i++ ) {
@@ -1709,26 +1671,18 @@
     nodes[0].bounds = overall_bounds;
   }
 
-
-  int objectBegin = build_records[nodeID].objectBegin;
-  int objectEnd   = build_records[nodeID].objectEnd;
   //cerr << MANTA_FUNC << " begin = " << objectBegin << " , end = " << 
objectEnd << endl;
   if (objectEnd <= objectBegin) {
     throw InternalError("Tried building BVH over invalid range");
   }
 
-  // TODO(boulos): Use a pool of mutexes to avoid locking the whole
-  // tree when only indivdual portions need to be locked.
-
-
   BVHNode& node = nodes[nodeID];
   int num_objects = objectEnd - objectBegin;
   num_prims_beneath[nodeID] = num_objects;
 
   int bestAxis = -1;
   int split = -1;
-  BBox left_box, right_box;
-  split = partitionApproxSAH(context,nodeID,objectBegin,objectEnd,bestAxis, 
left_box, right_box);
+  split = partitionApproxSAH(context,nodeID,objectBegin,objectEnd,bestAxis);
 
   if (bestAxis == -1) {
     // make leaf
@@ -1749,11 +1703,6 @@
     node.makeInternal(my_spot, bestAxis);
     num_nodes++;
 
-    BVHNode& left_son  = nodes[node.child+0];
-    BVHNode& right_son = nodes[node.child+1];
-    left_son.bounds = left_box;
-    right_son.bounds = right_box;
-
     build_records[node.child+0].objectBegin = objectBegin;
     build_records[node.child+0].objectEnd   = split;
 
@@ -1825,18 +1774,17 @@
                                int nodeID,
                                int objBegin,
                                int objEnd,
-                               int& output_axis,
-                               BBox& left_bounds,
-                               BBox& right_bounds) const {
+                               int& output_axis) const {
   int num_objects = objEnd - objBegin;
   if ( num_objects == 1 ) {
     output_axis = -1;
     return -1;
   }
 
-  BBox& overall_bounds = nodes[nodeID].bounds;
+  BBox overall_bounds;
   BBox centroid_bounds;
   for (int i = objBegin; i < objEnd; i++) {
+    overall_bounds.extendByBox(obj_bounds[object_ids[i]]);
     centroid_bounds.extendByPoint(obj_centroids[object_ids[i]]);
   }
 
@@ -1938,7 +1886,7 @@
   output_axis = best_cost.axis;
   if ( output_axis != -1 ) {
     // write out object ids [objBegin,objEnd) in appropriate order
-    int middle = partitionObjects(objBegin, objEnd, best_cost.axis, 
best_cost.position, left_bounds, right_bounds);
+    int middle = partitionObjects(objBegin, objEnd, best_cost.axis, 
best_cost.position);
     if (middle == objBegin || middle == objEnd) {
       // Splitting didn't find a valid split, split in the middle unless
       // we have too few
@@ -1948,14 +1896,6 @@
         return 0;
       }
       middle = objBegin + num_objects / 2;
-      left_bounds.reset();
-      right_bounds.reset();
-      for (int i = objBegin; i < middle; i++) {
-        left_bounds.extendByBox(obj_bounds[object_ids[i]]);
-      }
-      for (int i = middle; i < objEnd; i++) {
-        right_bounds.extendByBox(obj_bounds[object_ids[i]]);
-      }
     }
     return middle;
   }
@@ -1967,9 +1907,7 @@
 int DynBVH::partitionSAH(const PreprocessContext& context,
                          int nodeID,
                          int objBegin, int objEnd,
-                         int& output_axis,
-                         BBox& left_bounds,
-                         BBox& right_bounds)
+                         int& output_axis)
 {
   int num_objects = objEnd - objBegin;
   if ( num_objects == 1 ) {
@@ -1994,41 +1932,19 @@
 
   output_axis = best_cost.axis;
   if ( output_axis != -1 ) {
-    // build the events and sort them
-    std::vector<BVHSAHEvent> events;
-    for ( int i = objBegin; i < objEnd; i++ ) {
-      BVHSAHEvent new_event;
-      BBox& tri_box = obj_bounds[object_ids[i]];
-      //currGroup->get(object_ids[i])->computeBounds(context, tri_box);
-      new_event.position = tri_box.center()[output_axis];
-      new_event.obj_id   = object_ids[i];
-      events.push_back(new_event);
-    }
-
-    std::sort(events.begin(), events.end(), CompareBVHSAHEvent());
-
-    for ( int i = objBegin; i < objEnd; i++ ) {
-      object_ids[i] = events[i-objBegin].obj_id;
-      BBox& tri_box = obj_bounds[object_ids[i]];
-      if (i < best_cost.event) {
-        left_bounds.extendByBox(tri_box);
-      } else {
-        right_bounds.extendByBox(tri_box);
-      }
-    }
-
-    int result = objBegin + best_cost.event;
-
-    if ( result == objBegin || result == objEnd ) {
-      if ( num_objects < 8 ) {
+    // write out object ids [objBegin,objEnd) in appropriate order
+    int middle = partitionObjects(objBegin, objEnd, best_cost.axis, 
best_cost.position);
+    if (middle == objBegin || middle == objEnd) {
+      // 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;
       }
-      result = objBegin + num_objects/2;
-      return result;
-    } else {
-      return result;
+      middle = objBegin + num_objects / 2;
     }
+    return middle;
   }
 
   return 0; // making a leaf anyway
@@ -2044,9 +1960,8 @@
   std::vector<BVHSAHEvent> events;
   for ( int i = first; i < last; i++ ) {
     BVHSAHEvent new_event;
-    BBox tri_box;
-    currGroup->get(object_ids[i])->computeBounds(context, tri_box);
-    new_event.position = tri_box.center()[axis];
+    BBox& tri_box = obj_bounds[object_ids[i]];
+    new_event.position = obj_centroids[object_ids[i]][axis];
     new_event.obj_id   = object_ids[i];
     events.push_back(new_event);
 
@@ -2066,8 +1981,7 @@
     events[i].num_right = num_right;
     events[i].left_area = left_box.computeArea();
 
-    BBox tri_box;
-    currGroup->get(events[i].obj_id)->computeBounds(context, tri_box);
+    BBox& tri_box = obj_bounds[events[i].obj_id];
     left_box.extendByBox(tri_box);
 
     num_left++;
@@ -2080,9 +1994,7 @@
   best_eval.event = -1;
 
   for ( int i = num_events - 1; i >= 0; i-- ) {
-    BBox tri_box;
-    currGroup->get(events[i].obj_id)->computeBounds(context, tri_box);
-
+    BBox& tri_box = obj_bounds[events[i].obj_id];
     right_box.extendByBox(tri_box);
 
     if ( events[i].num_left > 0 && events[i].num_right > 0 ) {

Modified: trunk/Model/Groups/DynBVH.h
==============================================================================
--- trunk/Model/Groups/DynBVH.h (original)
+++ trunk/Model/Groups/DynBVH.h Wed Apr  2 18:34:16 2008
@@ -156,7 +156,7 @@
                                       int objectEnd,
                                       UpdateContext context);
 
-    int partitionObjects(int first, int last, int axis, float position, 
BBox& left_bounds, BBox& right_bounds) const;
+    int partitionObjects(int first, int last, int axis, float position) 
const;
     void splitBuild(Task* task, int nodeID, int objectBegin, int objectEnd, 
UpdateContext context);
 
     void preprocess(const PreprocessContext&);
@@ -202,17 +202,13 @@
                      int nodeID,
                      int objBegin,
                      int objEnd,
-                     int& output_axis,
-                     BBox& left_bounds,
-                     BBox& right_bounds);
+                     int& output_axis);
 
     int partitionApproxSAH(const PreprocessContext& context,
                            int nodeID,
                            int objBegin,
                            int objEnd,
-                           int& output_axis,
-                           BBox& left_bounds,
-                           BBox& right_bounds) const;
+                           int& output_axis) const;
 
     struct BVHCostEval
     {

---

• [Manta] r2163 - trunk/Model/Groups, Solomon Boulos, 04/02/2008

---

Archive powered by MHonArc 2.6.16.