From bbbbe68473e02567a902a6405ca09de216674615 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Sun, 21 Feb 2016 15:39:02 +0100 Subject: Cycles: Wrap spatial split storage into own structure 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 | 21 +++++++++++++++--- intern/cycles/bvh/bvh_build.h | 3 +-- intern/cycles/bvh/bvh_params.h | 12 +++++++++++ intern/cycles/bvh/bvh_split.cpp | 48 ++++++++++++++++++++++++++--------------- intern/cycles/bvh/bvh_split.h | 29 +++++++++++++++++++------ 5 files changed, 85 insertions(+), 28 deletions(-) diff --git a/intern/cycles/bvh/bvh_build.cpp b/intern/cycles/bvh/bvh_build.cpp index ef58bb2357b..b83c1e8864b 100644 --- a/intern/cycles/bvh/bvh_build.cpp +++ b/intern/cycles/bvh/bvh_build.cpp @@ -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) { diff --git a/intern/cycles/bvh/bvh_build.h b/intern/cycles/bvh/bvh_build.h index eefb7b60f7c..5857ae7f038 100644 --- a/intern/cycles/bvh/bvh_build.h +++ b/intern/cycles/bvh/bvh_build.h @@ -114,8 +114,7 @@ protected: /* spatial splitting */ float spatial_min_overlap; - vector spatial_right_bounds; - BVHSpatialBin spatial_bins[3][BVHParams::NUM_SPATIAL_BINS]; + vector spatial_storage; /* threads */ TaskPool task_pool; diff --git a/intern/cycles/bvh/bvh_params.h b/intern/cycles/bvh/bvh_params.h index faa995c3f29..c9b4f2b39e5 100644 --- a/intern/cycles/bvh/bvh_params.h +++ b/intern/cycles/bvh/bvh_params.h @@ -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 spatial_right_bounds; + BVHSpatialBin spatial_bins[3][BVHParams::NUM_SPATIAL_BINS]; +}; + CCL_NAMESPACE_END #endif /* __BVH_PARAMS_H__ */ diff --git a/intern/cycles/bvh/bvh_split.cpp b/intern/cycles/bvh/bvh_split.cpp index 0cd2bef2eee..037702c1d06 100644 --- a/intern/cycles/bvh/bvh_split.cpp +++ b/intern/cycles/bvh/bvh_split.cpp @@ -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; diff --git a/intern/cycles/bvh/bvh_split.h b/intern/cycles/bvh/bvh_split.h index 1e46bb66203..cc61899c9b5 100644 --- a/intern/cycles/bvh/bvh_split.h +++ b/intern/cycles/bvh/bvh_split.h @@ -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. */ -- cgit v1.2.3