Cycles: Wrap spatial split storage into own structure
authorSergey Sharybin <sergey.vfx@gmail.com>
Sun, 21 Feb 2016 14:39:02 +0000 (15:39 +0100)
committerSergey Sharybin <sergey.vfx@gmail.com>
Thu, 31 Mar 2016 08:06:21 +0000 (10:06 +0200)
This has following advantages:

- Localizes all the run-time storage into a single structure,
  which could easily be extended further.

- Storage could be created per-thread, so once builder is
  threaded we wouldn't have any conflicts between threads.

- Global nature of the storage avoids memory re-allocation
  on the runtime, keeping builder as fast as possible.

Currently it's just API changes, which don't affect user at all.

intern/cycles/bvh/bvh_build.cpp
intern/cycles/bvh/bvh_build.h
intern/cycles/bvh/bvh_params.h
intern/cycles/bvh/bvh_split.cpp
intern/cycles/bvh/bvh_split.h

index ef58bb2357bede87d35008ea973ea7b15d8b8639..b83c1e8864b6802d0990ccb22cda3b4bbb993480 100644 (file)
@@ -230,8 +230,23 @@ BVHNode* BVHBuild::run()
        }
 
        spatial_min_overlap = root.bounds().safe_area() * params.spatial_split_alpha;
-       spatial_right_bounds.clear();
-       spatial_right_bounds.resize(max(root.size(), (int)BVHParams::NUM_SPATIAL_BINS) - 1);
+
+       if(params.use_spatial_split) {
+               /* NOTE: The API here tries to be as much ready for multi-threaded build
+                * as possible, but at the same time it tries not to introduce any
+                * changes in behavior for until all refactoring needed for threading is
+                * finished.
+                *
+                * So we currently allocate single storage for now, which is only used by
+                * the only thread working on the spatial BVH build.
+                */
+               spatial_storage.resize(1);
+               size_t num_bins = max(root.size(), (int)BVHParams::NUM_SPATIAL_BINS) - 1;
+               foreach(BVHSpatialStorage &storage, spatial_storage) {
+                       storage.spatial_right_bounds.clear();
+                       storage.spatial_right_bounds.resize(num_bins);
+               }
+       }
 
        /* init progress updates */
        double build_start_time;
@@ -407,7 +422,7 @@ BVHNode* BVHBuild::build_node(const BVHRange& range, int level)
        }
 
        /* splitting test */
-       BVHMixedSplit split(this, range, level);
+       BVHMixedSplit split(this, &spatial_storage[0], range, level);
 
        if(!(range.size() > 0 && params.top_level && level == 0)) {
                if(split.no_split) {
index eefb7b60f7c0d362869afe9e85c6e48d098add10..5857ae7f0389bfc4b29e50766cf8e41827be477e 100644 (file)
@@ -114,8 +114,7 @@ protected:
 
        /* spatial splitting */
        float spatial_min_overlap;
-       vector<BoundBox> spatial_right_bounds;
-       BVHSpatialBin spatial_bins[3][BVHParams::NUM_SPATIAL_BINS];
+       vector<BVHSpatialStorage> spatial_storage;
 
        /* threads */
        TaskPool task_pool;
index faa995c3f299f2d212243278a01c5ae6ef16d746..c9b4f2b39e5ce09e180549ce23c311e6186fceb5 100644 (file)
@@ -175,6 +175,18 @@ struct BVHSpatialBin
        }
 };
 
+/* BVH Spatial Storage
+ *
+ * The idea of this storage is have thread-specific storage for the spatial
+ * splitters. We can pre-allocate this storage in advance and avoid heavy memory
+ * operations during split process.
+ */
+
+struct BVHSpatialStorage {
+       vector<BoundBox> spatial_right_bounds;
+       BVHSpatialBin spatial_bins[3][BVHParams::NUM_SPATIAL_BINS];
+};
+
 CCL_NAMESPACE_END
 
 #endif /* __BVH_PARAMS_H__ */
index 0cd2bef2eeeda2d6f6922694d25dd642cdc547b0..037702c1d069cb1490373d8a7ebc4691bc697b49 100644 (file)
@@ -28,8 +28,16 @@ CCL_NAMESPACE_BEGIN
 
 /* Object Split */
 
-BVHObjectSplit::BVHObjectSplit(BVHBuild *builder, const BVHRange& range, float nodeSAH)
-: sah(FLT_MAX), dim(0), num_left(0), left_bounds(BoundBox::empty), right_bounds(BoundBox::empty)
+BVHObjectSplit::BVHObjectSplit(BVHBuild *builder,
+                               BVHSpatialStorage *storage,
+                               const BVHRange& range,
+                               float nodeSAH)
+: sah(FLT_MAX),
+  dim(0),
+  num_left(0),
+  left_bounds(BoundBox::empty),
+  right_bounds(BoundBox::empty),
+  storage_(storage)
 {
        const BVHReference *ref_ptr = &builder->references[range.start()];
        float min_sah = FLT_MAX;
@@ -43,7 +51,7 @@ BVHObjectSplit::BVHObjectSplit(BVHBuild *builder, const BVHRange& range, float n
 
                for(int i = range.size() - 1; i > 0; i--) {
                        right_bounds.grow(ref_ptr[i].bounds());
-                       builder->spatial_right_bounds[i - 1] = right_bounds;
+                       storage_->spatial_right_bounds[i - 1] = right_bounds;
                }
 
                /* sweep left to right and select lowest SAH. */
@@ -51,7 +59,7 @@ BVHObjectSplit::BVHObjectSplit(BVHBuild *builder, const BVHRange& range, float n
 
                for(int i = 1; i < range.size(); i++) {
                        left_bounds.grow(ref_ptr[i - 1].bounds());
-                       right_bounds = builder->spatial_right_bounds[i - 1];
+                       right_bounds = storage_->spatial_right_bounds[i - 1];
 
                        float sah = nodeSAH +
                                left_bounds.safe_area() * builder->params.primitive_cost(i) +
@@ -83,8 +91,14 @@ void BVHObjectSplit::split(BVHBuild *builder, BVHRange& left, BVHRange& right, c
 
 /* Spatial Split */
 
-BVHSpatialSplit::BVHSpatialSplit(BVHBuild *builder, const BVHRange& range, float nodeSAH)
-: sah(FLT_MAX), dim(0), pos(0.0f)
+BVHSpatialSplit::BVHSpatialSplit(BVHBuild *builder,
+                                 BVHSpatialStorage *storage,
+                                 const BVHRange& range,
+                                 float nodeSAH)
+: sah(FLT_MAX),
+  dim(0),
+  pos(0.0f),
+  storage_(storage)
 {
        /* initialize bins. */
        float3 origin = range.bounds().min;
@@ -93,7 +107,7 @@ BVHSpatialSplit::BVHSpatialSplit(BVHBuild *builder, const BVHRange& range, float
 
        for(int dim = 0; dim < 3; dim++) {
                for(int i = 0; i < BVHParams::NUM_SPATIAL_BINS; i++) {
-                       BVHSpatialBin& bin = builder->spatial_bins[dim][i];
+                       BVHSpatialBin& bin = storage_->spatial_bins[dim][i];
 
                        bin.bounds = BoundBox::empty;
                        bin.enter = 0;
@@ -119,13 +133,13 @@ BVHSpatialSplit::BVHSpatialSplit(BVHBuild *builder, const BVHRange& range, float
                                BVHReference leftRef, rightRef;
 
                                split_reference(builder, leftRef, rightRef, currRef, dim, origin[dim] + binSize[dim] * (float)(i + 1));
-                               builder->spatial_bins[dim][i].bounds.grow(leftRef.bounds());
+                               storage_->spatial_bins[dim][i].bounds.grow(leftRef.bounds());
                                currRef = rightRef;
                        }
 
-                       builder->spatial_bins[dim][lastBin[dim]].bounds.grow(currRef.bounds());
-                       builder->spatial_bins[dim][firstBin[dim]].enter++;
-                       builder->spatial_bins[dim][lastBin[dim]].exit++;
+                       storage_->spatial_bins[dim][lastBin[dim]].bounds.grow(currRef.bounds());
+                       storage_->spatial_bins[dim][firstBin[dim]].enter++;
+                       storage_->spatial_bins[dim][lastBin[dim]].exit++;
                }
        }
 
@@ -135,8 +149,8 @@ BVHSpatialSplit::BVHSpatialSplit(BVHBuild *builder, const BVHRange& range, float
                BoundBox right_bounds = BoundBox::empty;
 
                for(int i = BVHParams::NUM_SPATIAL_BINS - 1; i > 0; i--) {
-                       right_bounds.grow(builder->spatial_bins[dim][i].bounds);
-                       builder->spatial_right_bounds[i - 1] = right_bounds;
+                       right_bounds.grow(storage_->spatial_bins[dim][i].bounds);
+                       storage_->spatial_right_bounds[i - 1] = right_bounds;
                }
 
                /* sweep left to right and select lowest SAH. */
@@ -145,13 +159,13 @@ BVHSpatialSplit::BVHSpatialSplit(BVHBuild *builder, const BVHRange& range, float
                int rightNum = range.size();
 
                for(int i = 1; i < BVHParams::NUM_SPATIAL_BINS; i++) {
-                       left_bounds.grow(builder->spatial_bins[dim][i - 1].bounds);
-                       leftNum += builder->spatial_bins[dim][i - 1].enter;
-                       rightNum -= builder->spatial_bins[dim][i - 1].exit;
+                       left_bounds.grow(storage_->spatial_bins[dim][i - 1].bounds);
+                       leftNum += storage_->spatial_bins[dim][i - 1].enter;
+                       rightNum -= storage_->spatial_bins[dim][i - 1].exit;
 
                        float sah = nodeSAH +
                                left_bounds.safe_area() * builder->params.primitive_cost(leftNum) +
-                               builder->spatial_right_bounds[i - 1].safe_area() * builder->params.primitive_cost(rightNum);
+                               storage_->spatial_right_bounds[i - 1].safe_area() * builder->params.primitive_cost(rightNum);
 
                        if(sah < this->sah) {
                                this->sah = sah;
index 1e46bb662031a2e6c4635dcf669185d52651d4cf..cc61899c9b5361d6597dfb2b81249eaffb6fd673 100644 (file)
@@ -37,9 +37,18 @@ public:
        BoundBox right_bounds;
 
        BVHObjectSplit() {}
-       BVHObjectSplit(BVHBuild *builder, const BVHRange& range, float nodeSAH);
+       BVHObjectSplit(BVHBuild *builder,
+                      BVHSpatialStorage *storage,
+                      const BVHRange& range,
+                      float nodeSAH);
 
-       void split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range);
+       void split(BVHBuild *builder,
+                  BVHRange& left,
+                  BVHRange& right,
+                  const BVHRange& range);
+
+protected:
+       BVHSpatialStorage *storage_;
 };
 
 /* Spatial Split */
@@ -52,7 +61,10 @@ public:
        float pos;
 
        BVHSpatialSplit() : sah(FLT_MAX), dim(0), pos(0.0f) {}
-       BVHSpatialSplit(BVHBuild *builder, const BVHRange& range, float nodeSAH);
+       BVHSpatialSplit(BVHBuild *builder,
+                       BVHSpatialStorage *storage,
+                       const BVHRange& range,
+                       float nodeSAH);
 
        void split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range);
        void split_reference(BVHBuild *builder,
@@ -63,6 +75,8 @@ public:
                             float pos);
 
 protected:
+       BVHSpatialStorage *storage_;
+
        /* Lower-level functions which calculates boundaries of left and right nodes
         * needed for spatial split.
         *
@@ -123,7 +137,10 @@ public:
 
        bool no_split;
 
-       __forceinline BVHMixedSplit(BVHBuild *builder, const BVHRange& range, int level)
+       __forceinline BVHMixedSplit(BVHBuild *builder,
+                                   BVHSpatialStorage *storage,
+                                   const BVHRange& range,
+                                   int level)
        {
                /* find split candidates. */
                float area = range.bounds().safe_area();
@@ -131,14 +148,14 @@ public:
                leafSAH = area * builder->params.primitive_cost(range.size());
                nodeSAH = area * builder->params.node_cost(2);
 
-               object = BVHObjectSplit(builder, range, nodeSAH);
+               object = BVHObjectSplit(builder, storage, range, nodeSAH);
 
                if(builder->params.use_spatial_split && level < BVHParams::MAX_SPATIAL_DEPTH) {
                        BoundBox overlap = object.left_bounds;
                        overlap.intersect(object.right_bounds);
 
                        if(overlap.safe_area() >= builder->spatial_min_overlap)
-                               spatial = BVHSpatialSplit(builder, range, nodeSAH);
+                               spatial = BVHSpatialSplit(builder, storage, range, nodeSAH);
                }
 
                /* leaf SAH is the lowest => create leaf. */