Text archives Help

---

Author: boulos
Date: Wed Jul 11 19:07:33 2007
New Revision: 1466

Modified:
   trunk/Model/Groups/DynBVH.cc
   trunk/Model/Groups/DynBVH.h
Log:
Precompute all the object bounding boxes and
centroids for the tree.


Modified: trunk/Model/Groups/DynBVH.cc
==============================================================================
--- trunk/Model/Groups/DynBVH.cc        (original)
+++ trunk/Model/Groups/DynBVH.cc        Wed Jul 11 19:07:33 2007
@@ -450,12 +450,20 @@
     if(group->getSize() > object_ids.size()) {
       nodes.resize(2*group->getSize());
       object_ids.resize(group->getSize());
+      // TODO(boulos): Free these after construction? or keep around
+      // for rebuild?
+      obj_bounds.resize(group->getSize());
+      obj_centroids.resize(group->getSize());
     }
 
+
     currGroup = group;
 
-    for ( int i = 0; i < currGroup->getSize(); i++ )
+    for ( int i = 0; i < currGroup->getSize(); i++ ) {
       object_ids[i] = i;
+      currGroup->get(i)->computeBounds(context, obj_bounds[i]);
+      obj_centroids[i] = obj_bounds[i].center();
+    }
 
     num_nodes = 1; // root node
     int nextFree = 1;
@@ -524,7 +532,7 @@
 
 }
 
-void DynBVH::parallelUpdateBounds(const PreprocessContext& context, 
+void DynBVH::parallelUpdateBounds(const PreprocessContext& context,
                                   int proc, int numProcs)
 {
   //XXXX this is super naive hackish code! FIXME!
@@ -536,13 +544,13 @@
     int right_son = left_son + 1;
     if (proc == 0) {
       updateBounds(context, left_son);
-      const BVHNode& left_node = nodes[left_son];    
+      const BVHNode& left_node = nodes[left_son];
       node.bounds = left_node.bounds;
     }
     else if (proc == 1)
       updateBounds(context, right_son);
     else return;
-    
+
     barrier.wait(2);
 
     const BVHNode& right_node = nodes[right_son];
@@ -597,59 +605,93 @@
   best_cost.cost = BVH_C_isec * num_objects;
   best_cost.axis = -1;
 
-  // TODO(boulos): Avoid recomputing overall bounds
+  // TODO(boulos): Avoid recomputing overall bounds for sample
+  // positions by passing in from parent.
   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);
+    overall_bounds.extendByBox(obj_bounds[object_ids[i]]);
   }
 
-  float inv_overall_area = overall_bounds.computeArea();
+  float inv_overall_area = 1.f/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++;
-        }
-      }
+  struct SampleBin {
+    SampleBin() { count = 0; }
+    BBox bounds;
+    int count;
+  };
+
+
+  const int num_samples = 8;
+  SampleBin bins[3][num_samples];
+
+  Vector min_point = overall_bounds.getMin();
+  Vector max_point = overall_bounds.getMax();
+  Vector width = max_point - min_point;
+
+  for (int i = objBegin; i < objEnd; 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 (which_bin >= num_samples)
+        which_bin = num_samples - 1;
+      bins[axis][which_bin].count++;
+      bins[axis][which_bin].bounds.extendByBox(obj_box);
+    }
+  }
+
+  // Now that we have all the sample points binned, we can just sweep over
+  // them to search for the best cost
+  for (int axis = 0; axis < 3; axis++) {
+    float left_areas[num_samples];
+    float right_areas[num_samples];
+    int left_counts[num_samples];
+    int right_counts[num_samples];
+    BBox left_box, right_box;
+    int num_left = 0;
+    int num_right = num_objects;
+
+    // Sweep from left to right, aggregating area and counts
+    for (int i = 0; i < num_samples; i++) {
+      num_left += bins[axis][i].count;
+      num_right -= bins[axis][i].count;
+      left_box.extendByBox(bins[axis][i].bounds);
+      left_counts[i] = num_left;
+      right_counts[i] = num_right;
+      left_areas[i]  = left_box.computeArea();
+    }
+
+    // Sweep from right to left, aggregating areas
+    for (int i = num_samples - 1; i >= 0; i--) {
+      if (i == num_samples - 1)
+        right_areas[i] = FLT_MAX;
+      else
+        right_areas[i] = right_box.computeArea();
+
+      right_box.extendByBox(bins[axis][i].bounds);
+    }
 
-      // 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();
+    // NOTE(boulos): The last bin is pointless (since it indicates leaf)
+    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) {
-        //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;
+        float sample_position =
+          (min_point[axis] + 
width[axis]*(static_cast<float>(i)/num_samples));
         best_cost.position = sample_position;
-        best_cost.num_left = num_left;
-        best_cost.num_right = num_right;
+        best_cost.num_left = left_counts[i];
+        best_cost.num_right = right_counts[i];
         best_cost.event = -1; // Unused
       }
     }
@@ -664,9 +706,7 @@
     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) {
+      if (obj_centroids[object_ids[i]][output_axis] < best_cost.position) {
         left_objs.push_back(object_ids[i]);
       } else {
         right_objs.push_back(object_ids[i]);

Modified: trunk/Model/Groups/DynBVH.h
==============================================================================
--- trunk/Model/Groups/DynBVH.h (original)
+++ trunk/Model/Groups/DynBVH.h Wed Jul 11 19:07:33 2007
@@ -62,6 +62,9 @@
         Group* currGroup;
         SCIRun::Barrier barrier;
 
+      vector<BBox> obj_bounds;
+      vector<Vector> obj_centroids;
+
 
     public:
       DynBVH() : currGroup(NULL), barrier("DynBVH barrier")
@@ -97,7 +100,7 @@
                    int nodeID, int objectBegin, int objectEnd,
                    int &nextFree, int depth = 0);
 
-        void parallelUpdateBounds(const PreprocessContext& context, 
+        void parallelUpdateBounds(const PreprocessContext& context,
                                   int proc, int numProcs);
         void updateBounds(const PreprocessContext& context, int ID = 0);
 

---

• [MANTA] r1466 - trunk/Model/Groups, boulos, 07/11/2007

---

Archive powered by MHonArc 2.6.16.