Text archives Help

---

Author: boulos
Date: Thu Mar 27 20:33:59 2008
New Revision: 2153

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

 Adding a lazy build to DynBVH. The most annoying portion of this is
 that since intersect is const, lots of other functions had to become
 const and most members are now mutable.

 A MutexPool is used to avoid contention for building the tree
 (currently set at 16) and the nodeID is used to hash into this
 set. Since neighboring nodes will hash to different mutexes this
 seems like a good way to get some parallelism from a lazy build.

 Note: I've only tested this on the bunny on my laptop ;).


Modified: trunk/Model/Groups/DynBVH.cc
==============================================================================
--- trunk/Model/Groups/DynBVH.cc        (original)
+++ trunk/Model/Groups/DynBVH.cc        Thu Mar 27 20:33:59 2008
@@ -30,6 +30,10 @@
 const int BVH_num_samples = 8;
 
 #define LONGEST_AXIS 0
+#define USE_LAZY_BUILD 0
+#if (USE_LAZY_BUILD) && !(USE_APPROXIMATE_BUILD)
+  #error "Lazy build requires approximate build to be on."
+#endif
 #define USE_PARALLEL_BUILD 1
 
 #include <Model/Groups/Mesh.h>
@@ -229,6 +233,10 @@
 
 void DynBVH::intersectNode(int nodeID, const RenderContext& context, 
RayPacket& rays, const IAData& ia_data) const
 {
+#if USE_LAZY_BUILD
+  PreprocessContext preprocess_context;
+  lazyBuild(preprocess_context, nodeID);
+#endif
   const BVHNode& node = nodes[nodeID];
   float tmin;
   int firstActive = firstIntersects(node.bounds, rays, ia_data, &tmin);
@@ -707,9 +715,11 @@
   // positions of underlying WaldTriangles are correct)
   if (currGroup) {
     currGroup->preprocess(context);
-
+    allocate();
     // Call rebuild (may call update underneath)
+#if !(USE_LAZY_BUILD)
     rebuild(context.proc, context.numProcs);
+#endif
 
     // NOTE(boulos): We allow rebuild to set the group_changed flag so
     // that you're not required to call preprocess in order to do an
@@ -1294,7 +1304,7 @@
   task->finished();
 }
 
-int DynBVH::partitionObjects(int objBegin, int objEnd, int axis, float 
position, BBox& left_bounds, BBox& right_bounds) {
+int DynBVH::partitionObjects(int objBegin, int objEnd, int axis, float 
position, BBox& left_bounds, BBox& right_bounds) const {
   //cerr << MANTA_FUNC << " begin = " << objBegin << ", end = " << objEnd << 
endl;
   int first = objBegin;
   int last  = objEnd;
@@ -1534,12 +1544,16 @@
     group_changed = false;
 }
 
-void DynBVH::allocate() {
+void DynBVH::allocate() const {
  if(currGroup->size() > object_ids.size()) {
     nodes.resize(2*currGroup->size());
     num_prims_beneath.resize(2*currGroup->size());
     object_ids.resize(currGroup->size());
-
+    built.resize(2*currGroup->size());
+    memset(&(built[0]), 0, sizeof(int) * currGroup->size());
+    build_records.resize(2*currGroup->size());
+    build_records[0].objectBegin = 0;
+    build_records[0].objectEnd   = currGroup->size();
     // TODO(boulos): Free these after construction? or keep around
     // for rebuild?
     obj_bounds.resize(currGroup->size());
@@ -1646,6 +1660,87 @@
   }
 }
 
+void DynBVH::lazyBuild(const PreprocessContext& context, int nodeID) const
+{
+  if (built[nodeID]) return;
+  unsigned int mutex_id = (nodeID & kLazyBuildMutexMask);
+  lazybuild_mutex.lockMutex(mutex_id);
+  // NOTE(boulos): We have to check again to see if someone else built for us
+  if (built[nodeID]) {
+    lazybuild_mutex.unlockMutex(mutex_id);
+    return;
+  }
+  if (nodeID == 0) {
+    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;
+  }
+
+
+  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);
+
+  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++;
+  } else {
+    // make internal node
+    // allocate two spots
+    int my_spot = (nextFree += 2);
+    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;
+
+    build_records[node.child+1].objectBegin = split;
+    build_records[node.child+1].objectEnd   = objectEnd;
+  }
+
+  built[nodeID] = true;
+  lazybuild_mutex.unlockMutex(mutex_id);
+}
+
+
 void DynBVH::parallelUpdateBounds(const PreprocessContext& context,
                                   int proc, int numProcs)
 {
@@ -1707,7 +1802,7 @@
                                int objEnd,
                                int& output_axis,
                                BBox& left_bounds,
-                               BBox& right_bounds) {
+                               BBox& right_bounds) const {
   int num_objects = objEnd - objBegin;
   if ( num_objects == 1 ) {
     output_axis = -1;

Modified: trunk/Model/Groups/DynBVH.h
==============================================================================
--- trunk/Model/Groups/DynBVH.h (original)
+++ trunk/Model/Groups/DynBVH.h Thu Mar 27 20:33:59 2008
@@ -7,6 +7,7 @@
 #include <Interface/AccelerationStructure.h>
 #include <Core/Thread/AtomicCounter.h>
 #include <Core/Thread/Barrier.h>
+#include <Core/Thread/MutexPool.h>
 #include <Core/Util/SpinLock.h>
 
 namespace Manta
@@ -62,21 +63,32 @@
       void readwrite(ArchiveElement* archive);
     };
 
+    struct BVHBuildRecord {
+      int objectBegin;
+      int objectEnd;
+    };
+
   protected:
-    vector<BVHNode> nodes;
-    vector<int> object_ids;
-    vector<unsigned int> num_prims_beneath; // the number of primitives 
beneath this node.
+    // NOTE(boulos): Because intersect is const, lazy build requires
+    // that almost everything in here become mutable and that almost
+    // all functions become const. How sad.
+    mutable vector<BVHNode> nodes;
+    mutable vector<int> object_ids;
+    mutable vector<unsigned int> num_prims_beneath; // the number of 
primitives beneath this node.
+    mutable vector<int> built;
+    mutable vector<BVHBuildRecord> build_records;
 
-    AtomicCounter num_nodes;
+    mutable AtomicCounter num_nodes;
     Group* currGroup;
     bool group_changed;
     Barrier barrier;
     SpinLock taskpool_mutex;
+    mutable MutexPool lazybuild_mutex;
 
-    AtomicCounter nextFree;
+    mutable AtomicCounter nextFree;
 
-    vector<BBox> obj_bounds;
-    vector<Vector> obj_centroids;
+    mutable vector<BBox> obj_bounds;
+    mutable vector<Vector> obj_centroids;
 
     char* TaskListMemory;
     size_t CurTaskList;
@@ -95,8 +107,9 @@
 
     bool print_info;
   public:
-
-    DynBVH(bool print = true) : num_nodes("DynBVH Num Nodes", 0), 
currGroup(NULL), group_changed(false), barrier("DynBVH barrier"), 
nextFree("DynBVH Next Free", 0), TaskListMemory(0), CurTaskList(0), 
TaskMemory(0), CurTask(0), TwoArgCallbackMemory(0), CurTwoArgCallback(0), 
FourArgCallbackMemory(0), CurFourArgCallback(0), FiveArgCallbackMemory(0), 
CurFiveArgCallback(0), print_info(print)
+    const static unsigned int kNumLazyBuildMutexes = 16;
+    const static unsigned int kLazyBuildMutexMask = kNumLazyBuildMutexes - 1;
+    DynBVH(bool print = true) : num_nodes("DynBVH Num Nodes", 0), 
currGroup(NULL), group_changed(false), barrier("DynBVH barrier"), 
lazybuild_mutex("Lazybuild Mutex", kNumLazyBuildMutexes), nextFree("DynBVH 
Next Free", 0), TaskListMemory(0), CurTaskList(0), TaskMemory(0), CurTask(0), 
TwoArgCallbackMemory(0), CurTwoArgCallback(0), FourArgCallbackMemory(0), 
CurFourArgCallback(0), FiveArgCallbackMemory(0), CurFiveArgCallback(0), 
print_info(print)
     {}
     virtual ~DynBVH();
 
@@ -107,7 +120,7 @@
     virtual void addToUpdateGraph(ObjectUpdateGraph* graph,
                                   ObjectUpdateGraphNode* parent);
 
-    void allocate();
+    void allocate() const;
 
     void performUpdate(const UpdateContext& context);
     void finishUpdate(TaskList* list, UpdateContext context);
@@ -141,7 +154,7 @@
                                       int objectEnd,
                                       UpdateContext context);
 
-    int partitionObjects(int first, int last, int axis, float position, 
BBox& left_bounds, BBox& right_bounds);
+    int partitionObjects(int first, int last, int axis, float position, 
BBox& left_bounds, BBox& right_bounds) const;
     void splitBuild(Task* task, int nodeID, int objectBegin, int objectEnd, 
UpdateContext context);
 
     void preprocess(const PreprocessContext&);
@@ -174,6 +187,8 @@
     void build(const PreprocessContext& context,
                int nodeID, int objectBegin, int objectEnd);
 
+    void lazyBuild(const PreprocessContext& context, int nodeID) const;
+
     void parallelUpdateBounds(const PreprocessContext& context,
                               int proc, int numProcs);
     void updateBounds(const PreprocessContext& context, int ID = 0);
@@ -195,7 +210,7 @@
                            int objEnd,
                            int& output_axis,
                            BBox& left_bounds,
-                           BBox& right_bounds);
+                           BBox& right_bounds) const;
 
     struct BVHCostEval
     {

---

• [Manta] r2153 - trunk/Model/Groups, Solomon Boulos, 03/27/2008

---

Archive powered by MHonArc 2.6.16.