Text archives Help

---

Author: boulos
Date: Wed Feb 20 19:41:22 2008
New Revision: 2102

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

 Avoid re-computing the bounds when possible by filling it in from the parent.

 Also add the ability to use the longest dominant axis only (not yet
 in parallel sections, but works for the subtrees)


Modified: trunk/Model/Groups/DynBVH.cc
==============================================================================
--- trunk/Model/Groups/DynBVH.cc        (original)
+++ trunk/Model/Groups/DynBVH.cc        Wed Feb 20 19:41:22 2008
@@ -28,6 +28,8 @@
 // leads to lower rendering performance...
 const int BVH_num_samples = 8;
 
+#define LONGEST_AXIS 0
+
 #include <Model/Groups/Mesh.h>
 void WriteMeshSorted(Group* group, std::vector<int> ids, const char* 
filename) {
   FILE* output = fopen(filename, "w");
@@ -834,14 +836,23 @@
   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);
 
     std::sort(object_ids.begin()+objectBegin,object_ids.begin()+objectEnd);
 
+    node.bounds.reset();
+    for (int i = objectBegin; i < objectEnd; i++) {
+      node.bounds.extendByBox(obj_bounds[object_ids[i]]);
+    }
+
     num_nodes++;
     task->finished();
   } else {
@@ -854,6 +865,9 @@
     // Make two subtasks to build the children
     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();
 
@@ -909,6 +923,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) {
+#if 0
   // First compute overall bounds in parallel
   int num_objects = objectEnd - objectBegin;
   const int kNumObjectsPerBound = 1024;
@@ -953,7 +968,56 @@
                           objectEnd,
                           context));
   context.insertWork(children);
+#else
+  // Now kick off a parallel bin computation
+  BBox& overall_bounds = nodes[nodeID].bounds;
+  const int kBinningObjects = 1024;
+  int num_objects = objectEnd - objectBegin;
+  int num_tasks = num_objects / kBinningObjects;
+
+  taskpool_mutex.lock();
+  size_t tasklist_id = CurTaskList;
+  size_t first_task = CurTask;
+  size_t callback_id = CurFourArgCallback;
+  size_t reduction_id = CurFiveArgCallback;
+
+  CurTaskList++;
+  CurTask += num_tasks;
+  CurFourArgCallback += num_tasks;
+  CurFiveArgCallback++;
+  taskpool_mutex.unlock();
 
+  TaskList* children = new (TaskListMemory + sizeof(TaskList) * tasklist_id) 
TaskList();
+  for (int i = 0; i < num_tasks; i++) {
+    int begin = objectBegin + i * kBinningObjects;
+    int end   = begin + kBinningObjects;
+    if (i == num_tasks - 1) {
+      end = objectEnd;
+    }
+    Task* child = new (TaskMemory + sizeof(Task) * (first_task + i)) Task
+      (new (FourArgCallbackMemory + 
(callback_id+i)*sizeof(BVHBuildTask))BVHBuildTask
+       (this,
+        &DynBVH::parallelComputeBins,
+        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,
+                          task,
+                          nodeID,
+                          objectBegin,
+                          objectEnd,
+                          context));
+
+  context.insertWork(children);
+#endif
   // Then compute bin entries in parallel (sweep during reduction?)
 
   // If a split has been deemed necessary (very likely), segment the object 
ids in parallel
@@ -1082,7 +1146,7 @@
   task->finished();
 }
 
-int DynBVH::partitionObjects(int objBegin, int objEnd, int axis, float 
position) {
+int DynBVH::partitionObjects(int objBegin, int objEnd, int axis, float 
position, BBox& left_bounds, BBox& right_bounds) {
   //cerr << MANTA_FUNC << " begin = " << objBegin << ", end = " << objEnd << 
endl;
   int first = objBegin;
   int last  = objEnd;
@@ -1104,6 +1168,15 @@
       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.
+      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;
     }
   }
@@ -1220,7 +1293,8 @@
 
   // First collect all the left_objs and right_objs into local
   // vectors (because we need to copy them out)
-  int middle = partitionObjects(objectBegin, objectEnd, best_cost.axis, 
best_cost.position);
+  BBox left_box, right_box;
+  int middle = partitionObjects(objectBegin, objectEnd, best_cost.axis, 
best_cost.position, left_box, right_box);
   if (middle == objectBegin || middle == objectEnd) {
     // Splitting didn't find a valid split, split in the middle unless
     // we have too few
@@ -1228,10 +1302,23 @@
     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);
 }
 
@@ -1265,17 +1352,21 @@
     } else {
       int bestAxis = -1;
       int split = -1;
-
-      // NOTE(abe): 30% slower rendering for a single CAD dataset.
+      BBox left_box, right_box;
 #if USE_APPROXIMATE_BUILD
-      split = partitionApproxSAH(preprocess_context, objectBegin, objectEnd, 
bestAxis);
+      split = partitionApproxSAH(preprocess_context, nodeID, objectBegin, 
objectEnd, bestAxis, left_box, right_box);
 #else
-      split = partitionSAH(preprocess_context, objectBegin, objectEnd, 
bestAxis);
+      split = partitionSAH(preprocess_context, nodeID, objectBegin, 
objectEnd, bestAxis, left_box, right_box);
 #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);
     }
   }
@@ -1320,15 +1411,19 @@
     obj_centroids.resize(currGroup->size());
   }
 
+  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);
   double build_start = Time::currentSeconds();
+  nodes[0].bounds = overall_bounds;
+
   build(context, 0, 0, currGroup->size());
   double updateBound_start = Time::currentSeconds();
   updateBounds(context, 0);
@@ -1360,12 +1455,12 @@
 
   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,objectBegin,objectEnd,bestAxis);
+  split = partitionApproxSAH(context,nodeID,objectBegin,objectEnd,bestAxis, 
left_box, right_box);
 #else
-  split = partitionSAH(context, objectBegin,objectEnd,bestAxis);
+  split = partitionSAH(context,nodeID,objectBegin,objectEnd,bestAxis, 
left_box, right_box);
 #endif
 
   if (bestAxis == -1) {
@@ -1374,6 +1469,11 @@
 
     std::sort(object_ids.begin()+objectBegin,object_ids.begin()+objectEnd);
 
+    node.bounds.reset();
+    for (int i = objectBegin; i < objectEnd; i++) {
+      node.bounds.extendByBox(obj_bounds[object_ids[i]]);
+    }
+
     num_nodes++;
   } else {
     // make internal node
@@ -1382,6 +1482,10 @@
     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);
@@ -1444,9 +1548,12 @@
 }
 
 int DynBVH::partitionApproxSAH(const PreprocessContext& context,
+                               int nodeID,
                                int objBegin,
                                int objEnd,
-                               int& output_axis) {
+                               int& output_axis,
+                               BBox& left_bounds,
+                               BBox& right_bounds) {
   int num_objects = objEnd - objBegin;
   if ( num_objects == 1 ) {
     output_axis = -1;
@@ -1461,10 +1568,14 @@
 
   // TODO(boulos): Avoid recomputing overall bounds for sample
   // positions by passing in from parent.
+#if 0
   BBox overall_bounds;
   for (int i = objBegin; i < objEnd; i++) {
     overall_bounds.extendByBox(obj_bounds[object_ids[i]]);
   }
+#else
+  BBox& overall_bounds = nodes[nodeID].bounds;
+#endif
 
   float inv_overall_area = 1.f/overall_bounds.computeArea();
 
@@ -1484,11 +1595,18 @@
   //Vector scale((num_samples/width[0]) * .999f,
   //           (num_samples/width[1]) * .999f,
   //           (num_samples/width[2]) * .999f);
+#ifdef LONGEST_AXIS
+  int longest_axis = overall_bounds.longestAxis();
+#endif
 
   for (int i = objBegin; i < objEnd; i++) {
     BBox& obj_box = obj_bounds[object_ids[i]];
     Vector& obj_centroid = obj_centroids[object_ids[i]];
+#ifdef LONGEST_AXIS
+    for (int axis = longest_axis; axis == longest_axis; axis++) {
+#else
     for (int axis = 0; axis < 3; axis++) {
+#endif
       // Sample bin is where this position would fall to the left
       int which_bin = int(num_samples * (obj_centroid[axis] - 
min_point[axis])/width[axis]);
       //int which_bin = int((obj_centroid[axis] - min_point[axis]) * 
scale[axis]);
@@ -1505,7 +1623,11 @@
 
   // Now that we have all the sample points binned, we can just sweep over
   // them to search for the best cost
+#ifdef LONGEST_AXIS
+  for (int axis = longest_axis; axis == longest_axis; axis++) {
+#else
   for (int axis = 0; axis < 3; axis++) {
+#endif
     float left_areas[num_samples];
     float right_areas[num_samples];
     int left_counts[num_samples];
@@ -1560,9 +1682,7 @@
   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)
-    int middle = partitionObjects(objBegin, objEnd, best_cost.axis, 
best_cost.position);
+    int middle = partitionObjects(objBegin, objEnd, best_cost.axis, 
best_cost.position, left_bounds, right_bounds);
     if (middle == objBegin || middle == objEnd) {
       // Splitting didn't find a valid split, split in the middle unless
       // we have too few
@@ -1571,7 +1691,15 @@
         output_axis = -1;
         return 0;
       }
-      return objBegin + num_objects / 2;
+      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;
   }
@@ -1581,7 +1709,11 @@
 }
 
 int DynBVH::partitionSAH(const PreprocessContext& context,
-                         int objBegin, int objEnd, int& output_axis)
+                         int nodeID,
+                         int objBegin, int objEnd,
+                         int& output_axis,
+                         BBox& left_bounds,
+                         BBox& right_bounds)
 {
   int num_objects = objEnd - objBegin;
   if ( num_objects == 1 ) {
@@ -1610,8 +1742,8 @@
     std::vector<BVHSAHEvent> events;
     for ( int i = objBegin; i < objEnd; i++ ) {
       BVHSAHEvent new_event;
-      BBox tri_box;
-      currGroup->get(object_ids[i])->computeBounds(context, tri_box);
+      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);
@@ -1621,6 +1753,12 @@
 
     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;

Modified: trunk/Model/Groups/DynBVH.h
==============================================================================
--- trunk/Model/Groups/DynBVH.h (original)
+++ trunk/Model/Groups/DynBVH.h Wed Feb 20 19:41:22 2008
@@ -134,7 +134,7 @@
                                       int objectEnd,
                                       UpdateContext context);
 
-    int partitionObjects(int first, int last, int axis, float position);
+    int partitionObjects(int first, int last, int axis, float position, 
BBox& left_bounds, BBox& right_bounds);
     void splitBuild(Task* task, int nodeID, int objectBegin, int objectEnd, 
UpdateContext context);
 
     void preprocess(const PreprocessContext&);
@@ -175,11 +175,20 @@
 
   protected:
     int partitionSAH(const PreprocessContext& context,
-                     int objBegin, int objEnd, int& output_axis);
+                     int nodeID,
+                     int objBegin,
+                     int objEnd,
+                     int& output_axis,
+                     BBox& left_bounds,
+                     BBox& right_bounds);
+
     int partitionApproxSAH(const PreprocessContext& context,
+                           int nodeID,
                            int objBegin,
                            int objEnd,
-                           int& output_axis);
+                           int& output_axis,
+                           BBox& left_bounds,
+                           BBox& right_bounds);
 
     struct BVHCostEval
     {

---

• [Manta] r2102 - trunk/Model/Groups, Solomon Boulos, 02/20/2008

---

Archive powered by MHonArc 2.6.16.