diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2016-02-22 18:25:33 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2016-03-31 11:06:21 +0300 |
commit | d9b729e342b72bfe31e7932723a149db3b7aa77c (patch) | |
tree | cc1de21b2999dea8ad4be41752e030758f280b09 /intern/cycles/bvh | |
parent | bbbbe68473e02567a902a6405ca09de216674615 (diff) |
Cycles: Only sort indices when finding a best dimension to split
This reduces amount of data being moved back and forth, which should
have positive effect on the performance.
Diffstat (limited to 'intern/cycles/bvh')
-rw-r--r-- | intern/cycles/bvh/bvh_build.cpp | 2 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_params.h | 1 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_sort.cpp | 51 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_sort.h | 5 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_split.cpp | 18 |
5 files changed, 72 insertions, 5 deletions
diff --git a/intern/cycles/bvh/bvh_build.cpp b/intern/cycles/bvh/bvh_build.cpp index b83c1e8864b..ce15e1bbc65 100644 --- a/intern/cycles/bvh/bvh_build.cpp +++ b/intern/cycles/bvh/bvh_build.cpp @@ -245,6 +245,8 @@ BVHNode* BVHBuild::run() foreach(BVHSpatialStorage &storage, spatial_storage) { storage.spatial_right_bounds.clear(); storage.spatial_right_bounds.resize(num_bins); + storage.spatial_indices.clear(); + storage.spatial_indices.reserve(num_bins); } } diff --git a/intern/cycles/bvh/bvh_params.h b/intern/cycles/bvh/bvh_params.h index c9b4f2b39e5..2b280d66e4a 100644 --- a/intern/cycles/bvh/bvh_params.h +++ b/intern/cycles/bvh/bvh_params.h @@ -185,6 +185,7 @@ struct BVHSpatialBin struct BVHSpatialStorage { vector<BoundBox> spatial_right_bounds; BVHSpatialBin spatial_bins[3][BVHParams::NUM_SPATIAL_BINS]; + vector<int> spatial_indices; }; CCL_NAMESPACE_END diff --git a/intern/cycles/bvh/bvh_sort.cpp b/intern/cycles/bvh/bvh_sort.cpp index 3140bf23376..8088dccbc07 100644 --- a/intern/cycles/bvh/bvh_sort.cpp +++ b/intern/cycles/bvh/bvh_sort.cpp @@ -65,5 +65,54 @@ void bvh_reference_sort(int start, int end, BVHReference *data, int dim) sort(data+start, data+end, compare); } -CCL_NAMESPACE_END +struct BVHReferenceCompareIndexed { +public: + BVHReferenceCompareIndexed(int dim, const BVHReference *data, int start) + : dim_(dim), + start_(start), + data_(data) + {} + + bool operator()(const int a, const int b) + { + const BVHReference& ra = data_[start_ + a]; + const BVHReference& rb = data_[start_ + b]; + NO_EXTENDED_PRECISION float ca = ra.bounds().min[dim_] + ra.bounds().max[dim_]; + NO_EXTENDED_PRECISION float cb = rb.bounds().min[dim_] + rb.bounds().max[dim_]; + + if(ca < cb) return true; + else if(ca > cb) return false; + else if(ra.prim_object() < rb.prim_object()) return true; + else if(ra.prim_object() > rb.prim_object()) return false; + else if(ra.prim_index() < rb.prim_index()) return true; + else if(ra.prim_index() > rb.prim_index()) return false; + else if(ra.prim_type() < rb.prim_type()) return true; + else if(ra.prim_type() > rb.prim_type()) return false; + + return false; + } + +private: + int dim_, start_; + const BVHReference *data_; +}; +/* NOTE: indices are always from 0 to count, even in the cases when start is not + * zero. This is to simplify indexing in the object splitter. Index array is also + * always zero-based index. + */ +void bvh_reference_sort_indices(int start, + int end, + const BVHReference *data, + int *indices, + int dim) +{ + const int count = end - start; + for(int i = 0; i < count; ++i) { + indices[i] = i; + } + BVHReferenceCompareIndexed compare(dim, data, start); + sort(indices, indices+count, compare); +} + +CCL_NAMESPACE_END diff --git a/intern/cycles/bvh/bvh_sort.h b/intern/cycles/bvh/bvh_sort.h index 18aafb5f1ff..ec6edc42c74 100644 --- a/intern/cycles/bvh/bvh_sort.h +++ b/intern/cycles/bvh/bvh_sort.h @@ -21,6 +21,11 @@ CCL_NAMESPACE_BEGIN void bvh_reference_sort(int start, int end, BVHReference *data, int dim); +void bvh_reference_sort_indices(int start, + int end, + const BVHReference *data, + int *indices, + int dim); CCL_NAMESPACE_END diff --git a/intern/cycles/bvh/bvh_split.cpp b/intern/cycles/bvh/bvh_split.cpp index 037702c1d06..ff0142fa786 100644 --- a/intern/cycles/bvh/bvh_split.cpp +++ b/intern/cycles/bvh/bvh_split.cpp @@ -42,15 +42,25 @@ BVHObjectSplit::BVHObjectSplit(BVHBuild *builder, const BVHReference *ref_ptr = &builder->references[range.start()]; float min_sah = FLT_MAX; + storage->spatial_indices.resize(range.size()); + int *indices = &storage->spatial_indices[0]; + for(int dim = 0; dim < 3; dim++) { - /* sort references */ - bvh_reference_sort(range.start(), range.end(), &builder->references[0], dim); + /* Sort references. + * We only sort indices, to save amount of memory being sent back + * and forth. + */ + bvh_reference_sort_indices(range.start(), + range.end(), + &builder->references[0], + indices, + dim); /* sweep right to left and determine bounds. */ BoundBox right_bounds = BoundBox::empty; for(int i = range.size() - 1; i > 0; i--) { - right_bounds.grow(ref_ptr[i].bounds()); + right_bounds.grow(ref_ptr[indices[i]].bounds()); storage_->spatial_right_bounds[i - 1] = right_bounds; } @@ -58,7 +68,7 @@ BVHObjectSplit::BVHObjectSplit(BVHBuild *builder, BoundBox left_bounds = BoundBox::empty; for(int i = 1; i < range.size(); i++) { - left_bounds.grow(ref_ptr[i - 1].bounds()); + left_bounds.grow(ref_ptr[indices[i - 1]].bounds()); right_bounds = storage_->spatial_right_bounds[i - 1]; float sah = nodeSAH + |