diff options
Diffstat (limited to 'intern/cycles/bvh')
-rw-r--r-- | intern/cycles/bvh/CMakeLists.txt | 4 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh.cpp | 4 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_binning.cpp | 223 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_binning.h | 86 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_build.cpp | 636 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_build.h | 110 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_node.cpp | 22 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_node.h | 18 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_params.h | 91 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_sort.cpp | 16 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_sort.h | 2 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_split.cpp | 293 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_split.h | 110 |
13 files changed, 1168 insertions, 447 deletions
diff --git a/intern/cycles/bvh/CMakeLists.txt b/intern/cycles/bvh/CMakeLists.txt index decc576fe51..131a7a1f750 100644 --- a/intern/cycles/bvh/CMakeLists.txt +++ b/intern/cycles/bvh/CMakeLists.txt @@ -10,17 +10,21 @@ set(INC set(SRC bvh.cpp + bvh_binning.cpp bvh_build.cpp bvh_node.cpp bvh_sort.cpp + bvh_split.cpp ) set(SRC_HEADERS bvh.h + bvh_binning.h bvh_build.h bvh_node.h bvh_params.h bvh_sort.h + bvh_split.h ) include_directories(${INC}) diff --git a/intern/cycles/bvh/bvh.cpp b/intern/cycles/bvh/bvh.cpp index c9bfa964332..15695dddf45 100644 --- a/intern/cycles/bvh/bvh.cpp +++ b/intern/cycles/bvh/bvh.cpp @@ -530,7 +530,7 @@ void RegularBVH::refit_nodes() { assert(!params.top_level); - BoundBox bbox; + BoundBox bbox = BoundBox::empty; uint visibility = 0; refit_node(0, (pack.is_leaf[0])? true: false, bbox, visibility); } @@ -572,7 +572,7 @@ void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility } else { /* refit inner node, set bbox from children */ - BoundBox bbox0, bbox1; + BoundBox bbox0 = BoundBox::empty, bbox1 = BoundBox::empty; uint visibility0 = 0, visibility1 = 0; refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0); diff --git a/intern/cycles/bvh/bvh_binning.cpp b/intern/cycles/bvh/bvh_binning.cpp new file mode 100644 index 00000000000..661541a8d23 --- /dev/null +++ b/intern/cycles/bvh/bvh_binning.cpp @@ -0,0 +1,223 @@ +/* + * Adapted from code copyright 2009-2011 Intel Corporation + * Modifications Copyright 2012, Blender Foundation. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +//#define __KERNEL_SSE__ + +#include <stdlib.h> + +#include "bvh_binning.h" + +#include "util_algorithm.h" +#include "util_boundbox.h" +#include "util_types.h" + +CCL_NAMESPACE_BEGIN + +/* SSE replacements */ + +__forceinline void prefetch_L1 (const void* ptr) { } +__forceinline void prefetch_L2 (const void* ptr) { } +__forceinline void prefetch_L3 (const void* ptr) { } +__forceinline void prefetch_NTA(const void* ptr) { } + +template<size_t src> __forceinline float extract(const int4& b) +{ return b[src]; } +template<size_t dst> __forceinline const float4 insert(const float4& a, const float b) +{ float4 r = a; r[dst] = b; return r; } + +__forceinline int get_best_dimension(const float4& bestSAH) +{ + // return (int)__bsf(movemask(reduce_min(bestSAH) == bestSAH)); + + float minSAH = min(bestSAH.x, min(bestSAH.y, bestSAH.z)); + + if(bestSAH.x == minSAH) return 0; + else if(bestSAH.y == minSAH) return 1; + else return 2; +} + +/* BVH Object Binning */ + +BVHObjectBinning::BVHObjectBinning(const BVHRange& job, BVHReference *prims) +: BVHRange(job), splitSAH(FLT_MAX), dim(0), pos(0) +{ + /* compute number of bins to use and precompute scaling factor for binning */ + num_bins = min(size_t(MAX_BINS), size_t(4.0f + 0.05f*size())); + scale = rcp(cent_bounds().size()) * make_float3((float)num_bins); + + /* initialize binning counter and bounds */ + BoundBox bin_bounds[MAX_BINS][4]; /* bounds for every bin in every dimension */ + int4 bin_count[MAX_BINS]; /* number of primitives mapped to bin */ + + for(size_t i = 0; i < num_bins; i++) { + bin_count[i] = make_int4(0); + bin_bounds[i][0] = bin_bounds[i][1] = bin_bounds[i][2] = BoundBox::empty; + } + + /* map geometry to bins, unrolled once */ + { + ssize_t i; + + for(i = 0; i < ssize_t(size()) - 1; i += 2) { + prefetch_L2(&prims[start() + i + 8]); + + /* map even and odd primitive to bin */ + BVHReference prim0 = prims[start() + i + 0]; + BVHReference prim1 = prims[start() + i + 1]; + + int4 bin0 = get_bin(prim0.bounds()); + int4 bin1 = get_bin(prim1.bounds()); + + /* increase bounds for bins for even primitive */ + int b00 = extract<0>(bin0); bin_count[b00][0]++; bin_bounds[b00][0].grow(prim0.bounds()); + int b01 = extract<1>(bin0); bin_count[b01][1]++; bin_bounds[b01][1].grow(prim0.bounds()); + int b02 = extract<2>(bin0); bin_count[b02][2]++; bin_bounds[b02][2].grow(prim0.bounds()); + + /* increase bounds of bins for odd primitive */ + int b10 = extract<0>(bin1); bin_count[b10][0]++; bin_bounds[b10][0].grow(prim1.bounds()); + int b11 = extract<1>(bin1); bin_count[b11][1]++; bin_bounds[b11][1].grow(prim1.bounds()); + int b12 = extract<2>(bin1); bin_count[b12][2]++; bin_bounds[b12][2].grow(prim1.bounds()); + } + + /* for uneven number of primitives */ + if(i < ssize_t(size())) { + /* map primitive to bin */ + BVHReference prim0 = prims[start() + i]; + int4 bin0 = get_bin(prim0.bounds()); + + /* increase bounds of bins */ + int b00 = extract<0>(bin0); bin_count[b00][0]++; bin_bounds[b00][0].grow(prim0.bounds()); + int b01 = extract<1>(bin0); bin_count[b01][1]++; bin_bounds[b01][1].grow(prim0.bounds()); + int b02 = extract<2>(bin0); bin_count[b02][2]++; bin_bounds[b02][2].grow(prim0.bounds()); + } + } + + /* sweep from right to left and compute parallel prefix of merged bounds */ + float4 r_area[MAX_BINS]; /* area of bounds of primitives on the right */ + float4 r_count[MAX_BINS]; /* number of primitives on the right */ + int4 count = make_int4(0); + + BoundBox bx = BoundBox::empty; + BoundBox by = BoundBox::empty; + BoundBox bz = BoundBox::empty; + + for(size_t i = num_bins - 1; i > 0; i--) { + count = count + bin_count[i]; + r_count[i] = blocks(count); + + bx = merge(bx,bin_bounds[i][0]); r_area[i][0] = bx.half_area(); + by = merge(by,bin_bounds[i][1]); r_area[i][1] = by.half_area(); + bz = merge(bz,bin_bounds[i][2]); r_area[i][2] = bz.half_area(); + } + + /* sweep from left to right and compute SAH */ + int4 ii = make_int4(1); + float4 bestSAH = make_float4(FLT_MAX); + int4 bestSplit = make_int4(-1); + + count = make_int4(0); + + bx = BoundBox::empty; + by = BoundBox::empty; + bz = BoundBox::empty; + + for(size_t i = 1; i < num_bins; i++, ii += make_int4(1)) { + count = count + bin_count[i-1]; + + bx = merge(bx,bin_bounds[i-1][0]); float Ax = bx.half_area(); + by = merge(by,bin_bounds[i-1][1]); float Ay = by.half_area(); + bz = merge(bz,bin_bounds[i-1][2]); float Az = bz.half_area(); + + float4 lCount = blocks(count); + float4 lArea = make_float4(Ax,Ay,Az,Az); + float4 sah = lArea*lCount + r_area[i]*r_count[i]; + + bestSplit = select(sah < bestSAH,ii,bestSplit); + bestSAH = min(sah,bestSAH); + } + + int4 mask = float3_to_float4(cent_bounds().size()) <= make_float4(0.0f); + bestSAH = insert<3>(select(mask, make_float4(FLT_MAX), bestSAH), FLT_MAX); + + /* find best dimension */ + dim = get_best_dimension(bestSAH); + splitSAH = bestSAH[dim]; + pos = bestSplit[dim]; + leafSAH = bounds().half_area() * blocks(size()); +} + +void BVHObjectBinning::split(BVHReference* prims, BVHObjectBinning& left_o, BVHObjectBinning& right_o) const +{ + size_t N = size(); + + BoundBox lgeom_bounds = BoundBox::empty; + BoundBox rgeom_bounds = BoundBox::empty; + BoundBox lcent_bounds = BoundBox::empty; + BoundBox rcent_bounds = BoundBox::empty; + + ssize_t l = 0, r = N-1; + + while(l <= r) { + prefetch_L2(&prims[start() + l + 8]); + prefetch_L2(&prims[start() + r - 8]); + + BVHReference prim = prims[start() + l]; + float3 center = prim.bounds().center2(); + + if(get_bin(center)[dim] < pos) { + lgeom_bounds.grow(prim.bounds()); + lcent_bounds.grow(center); + l++; + } + else { + rgeom_bounds.grow(prim.bounds()); + rcent_bounds.grow(center); + swap(prims[start()+l],prims[start()+r]); + r--; + } + } + + /* finish */ + if(l != 0 && N-1-r != 0) { + right_o = BVHObjectBinning(BVHRange(rgeom_bounds, rcent_bounds, start() + l, N-1-r), prims); + left_o = BVHObjectBinning(BVHRange(lgeom_bounds, lcent_bounds, start(), l), prims); + return; + } + + /* object medium split if we did not make progress, can happen when all + primitives have same centroid */ + lgeom_bounds = BoundBox::empty; + rgeom_bounds = BoundBox::empty; + lcent_bounds = BoundBox::empty; + rcent_bounds = BoundBox::empty; + + for(size_t i = 0; i < N/2; i++) { + lgeom_bounds.grow(prims[start()+i].bounds()); + lcent_bounds.grow(prims[start()+i].bounds().center2()); + } + + for(size_t i = N/2; i < N; i++) { + rgeom_bounds.grow(prims[start()+i].bounds()); + rcent_bounds.grow(prims[start()+i].bounds().center2()); + } + + right_o = BVHObjectBinning(BVHRange(rgeom_bounds, rcent_bounds, start() + N/2, N/2 + N%2), prims); + left_o = BVHObjectBinning(BVHRange(lgeom_bounds, lcent_bounds, start(), N/2), prims); +} + +CCL_NAMESPACE_END + diff --git a/intern/cycles/bvh/bvh_binning.h b/intern/cycles/bvh/bvh_binning.h new file mode 100644 index 00000000000..60742157055 --- /dev/null +++ b/intern/cycles/bvh/bvh_binning.h @@ -0,0 +1,86 @@ +/* + * Adapted from code copyright 2009-2011 Intel Corporation + * Modifications Copyright 2012, Blender Foundation. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __BVH_BINNING_H__ +#define __BVH_BINNING_H__ + +#include "bvh_params.h" + +#include "util_types.h" + +CCL_NAMESPACE_BEGIN + +/* Single threaded object binner. Finds the split with the best SAH heuristic + * by testing for each dimension multiple partitionings for regular spaced + * partition locations. A partitioning for a partition location is computed, + * by putting primitives whose centroid is on the left and right of the split + * location to different sets. The SAH is evaluated by computing the number of + * blocks occupied by the primitives in the partitions. */ + +class BVHObjectBinning : public BVHRange +{ +public: + __forceinline BVHObjectBinning() {} + BVHObjectBinning(const BVHRange& job, BVHReference *prims); + + void split(BVHReference *prims, BVHObjectBinning& left_o, BVHObjectBinning& right_o) const; + + float splitSAH; /* SAH cost of the best split */ + float leafSAH; /* SAH cost of creating a leaf */ + +protected: + int dim; /* best split dimension */ + int pos; /* best split position */ + size_t num_bins; /* actual number of bins to use */ + float3 scale; /* scaling factor to compute bin */ + + enum { MAX_BINS = 32 }; + enum { LOG_BLOCK_SIZE = 2 }; + + /* computes the bin numbers for each dimension for a box. */ + __forceinline int4 get_bin(const BoundBox& box) const + { + int4 a = make_int4((box.center2() - cent_bounds().min)*scale - make_float3(0.5f)); + int4 mn = make_int4(0); + int4 mx = make_int4((int)num_bins-1); + + return clamp(a, mn, mx); + } + + /* computes the bin numbers for each dimension for a point. */ + __forceinline int4 get_bin(const float3& c) const + { + return make_int4((c - cent_bounds().min)*scale - make_float3(0.5f)); + } + + /* compute the number of blocks occupied for each dimension. */ + __forceinline float4 blocks(const int4& a) const + { + return make_float4((a + make_int4((1 << LOG_BLOCK_SIZE)-1)) >> LOG_BLOCK_SIZE); + } + + /* compute the number of blocks occupied in one dimension. */ + __forceinline int blocks(size_t a) const + { + return (int)((a+((1LL << LOG_BLOCK_SIZE)-1)) >> LOG_BLOCK_SIZE); + } +}; + +CCL_NAMESPACE_END + +#endif + diff --git a/intern/cycles/bvh/bvh_build.cpp b/intern/cycles/bvh/bvh_build.cpp index 38674c2c561..c5b4f1d01ae 100644 --- a/intern/cycles/bvh/bvh_build.cpp +++ b/intern/cycles/bvh/bvh_build.cpp @@ -15,22 +15,36 @@ * limitations under the License. */ +#include "bvh_binning.h" #include "bvh_build.h" #include "bvh_node.h" #include "bvh_params.h" -#include "bvh_sort.h" +#include "bvh_split.h" #include "mesh.h" #include "object.h" #include "scene.h" -#include "util_algorithm.h" +#include "util_debug.h" #include "util_foreach.h" #include "util_progress.h" #include "util_time.h" CCL_NAMESPACE_BEGIN +/* BVH Build Task */ + +class BVHBuildTask : public Task { +public: + BVHBuildTask(InnerNode *node_, int child_, BVHObjectBinning& range_, int level_) + : node(node_), child(child_), level(level_), range(range_) {} + + InnerNode *node; + int child; + int level; + BVHObjectBinning range; +}; + /* Constructor / Destructor */ BVHBuild::BVHBuild(const vector<Object*>& objects_, @@ -41,10 +55,10 @@ BVHBuild::BVHBuild(const vector<Object*>& objects_, prim_object(prim_object_), params(params_), progress(progress_), - progress_start_time(0.0) + progress_start_time(0.0), + task_pool(function_bind(&BVHBuild::thread_build_node, this, _1, _2)) { spatial_min_overlap = 0.0f; - progress_num_duplicates = 0; } BVHBuild::~BVHBuild() @@ -53,57 +67,63 @@ BVHBuild::~BVHBuild() /* Adding References */ -void BVHBuild::add_reference_mesh(NodeSpec& root, Mesh *mesh, int i) +void BVHBuild::add_reference_mesh(BoundBox& root, BoundBox& center, Mesh *mesh, int i) { for(uint j = 0; j < mesh->triangles.size(); j++) { Mesh::Triangle t = mesh->triangles[j]; - Reference ref; + BoundBox bounds = BoundBox::empty; for(int k = 0; k < 3; k++) { float3 pt = mesh->verts[t.v[k]]; - ref.bounds.grow(pt); + bounds.grow(pt); } - if(ref.bounds.valid()) { - ref.prim_index = j; - ref.prim_object = i; - - references.push_back(ref); - root.bounds.grow(ref.bounds); + if(bounds.valid()) { + references.push_back(BVHReference(bounds, j, i)); + root.grow(bounds); + center.grow(bounds.center2()); } } } -void BVHBuild::add_reference_object(NodeSpec& root, Object *ob, int i) +void BVHBuild::add_reference_object(BoundBox& root, BoundBox& center, Object *ob, int i) { - Reference ref; - - ref.prim_index = -1; - ref.prim_object = i; - ref.bounds = ob->bounds; - - references.push_back(ref); - root.bounds.grow(ref.bounds); + references.push_back(BVHReference(ob->bounds, -1, i)); + root.grow(ob->bounds); + center.grow(ob->bounds.center2()); } -void BVHBuild::add_references(NodeSpec& root) +void BVHBuild::add_references(BVHRange& root) { - /* init root spec */ - root.num = 0; - root.bounds = BoundBox(); + /* reserve space for references */ + size_t num_alloc_references = 0; + + foreach(Object *ob, objects) { + if(params.top_level) { + if(ob->mesh->transform_applied) + num_alloc_references += ob->mesh->triangles.size(); + else + num_alloc_references++; + } + else + num_alloc_references += ob->mesh->triangles.size(); + } + + references.reserve(num_alloc_references); - /* add objects */ + /* add references from objects */ + BoundBox bounds = BoundBox::empty, center = BoundBox::empty; int i = 0; foreach(Object *ob, objects) { if(params.top_level) { if(ob->mesh->transform_applied) - add_reference_mesh(root, ob->mesh, i); + add_reference_mesh(bounds, center, ob->mesh, i); else - add_reference_object(root, ob, i); + add_reference_object(bounds, center, ob, i); } else - add_reference_mesh(root, ob->mesh, i); + add_reference_mesh(bounds, center, ob->mesh, i); i++; @@ -111,129 +131,213 @@ void BVHBuild::add_references(NodeSpec& root) } /* happens mostly on empty meshes */ - if(!root.bounds.valid()) - root.bounds.grow(make_float3(0.0f, 0.0f, 0.0f)); + if(!bounds.valid()) + bounds.grow(make_float3(0.0f, 0.0f, 0.0f)); - root.num = references.size(); + root = BVHRange(bounds, center, 0, references.size()); } /* Build */ BVHNode* BVHBuild::run() { - NodeSpec root; + BVHRange root; /* add references */ add_references(root); - if(progress.get_cancel()) return NULL; + if(progress.get_cancel()) + return NULL; /* init spatial splits */ if(params.top_level) /* todo: get rid of this */ params.use_spatial_split = false; - spatial_min_overlap = root.bounds.area() * params.spatial_split_alpha; + spatial_min_overlap = root.bounds().safe_area() * params.spatial_split_alpha; spatial_right_bounds.clear(); - spatial_right_bounds.resize(max(root.num, (int)BVHParams::NUM_SPATIAL_BINS) - 1); + spatial_right_bounds.resize(max(root.size(), (int)BVHParams::NUM_SPATIAL_BINS) - 1); /* init progress updates */ - progress_num_duplicates = 0; progress_start_time = time_dt(); + progress_count = 0; + progress_total = references.size(); + progress_original_total = progress_total; + + prim_index.resize(references.size()); + prim_object.resize(references.size()); /* build recursively */ - return build_node(root, 0, 0.0f, 1.0f); + BVHNode *rootnode; + + if(params.use_spatial_split) { + /* singlethreaded spatial split build */ + rootnode = build_node(root, 0); + } + else { + /* multithreaded binning build */ + BVHObjectBinning rootbin(root, &references[0]); + rootnode = build_node(rootbin, 0); + task_pool.wait(); + } + + /* delete if we cancelled */ + if(rootnode) { + if(progress.get_cancel()) { + rootnode->deleteSubtree(); + rootnode = NULL; + } + else if(!params.use_spatial_split) { + /*rotate(rootnode, 4, 5);*/ + rootnode->update_visibility(); + } + } + + return rootnode; } -void BVHBuild::progress_update(float progress_start, float progress_end) +void BVHBuild::progress_update() { if(time_dt() - progress_start_time < 0.25f) return; + + double progress_start = (double)progress_count/(double)progress_total; + double duplicates = (double)(progress_total - progress_original_total)/(double)progress_total; - float duplicates = (float)progress_num_duplicates/(float)references.size(); string msg = string_printf("Building BVH %.0f%%, duplicates %.0f%%", progress_start*100.0f, duplicates*100.0f); progress.set_substatus(msg); - progress_start_time = time_dt(); + progress_start_time = time_dt(); } -BVHNode* BVHBuild::build_node(const NodeSpec& spec, int level, float progress_start, float progress_end) +void BVHBuild::thread_build_node(Task *task_, int thread_id) { - /* progress update */ - progress_update(progress_start, progress_end); - if(progress.get_cancel()) return NULL; + if(progress.get_cancel()) + return; - /* small enough or too deep => create leaf. */ - if(spec.num <= params.min_leaf_size || level >= BVHParams::MAX_DEPTH) - return create_leaf_node(spec); - - /* find split candidates. */ - float area = spec.bounds.area(); - float leafSAH = area * params.triangle_cost(spec.num); - float nodeSAH = area * params.node_cost(2); - ObjectSplit object = find_object_split(spec, nodeSAH); - SpatialSplit spatial; - - if(params.use_spatial_split && level < BVHParams::MAX_SPATIAL_DEPTH) { - BoundBox overlap = object.left_bounds; - overlap.intersect(object.right_bounds); - - if(overlap.area() >= spatial_min_overlap) - spatial = find_spatial_split(spec, nodeSAH); - } + /* build nodes */ + BVHBuildTask *task = (BVHBuildTask*)task_; + BVHNode *node = build_node(task->range, task->level); + + /* set child in inner node */ + task->node->children[task->child] = node; - /* leaf SAH is the lowest => create leaf. */ - float minSAH = min(min(leafSAH, object.sah), spatial.sah); + /* update progress */ + if(task->range.size() < THREAD_TASK_SIZE) { + /*rotate(node, INT_MAX, 5);*/ - if(minSAH == leafSAH && spec.num <= params.max_leaf_size) - return create_leaf_node(spec); + thread_scoped_lock lock(build_mutex); - /* perform split. */ - NodeSpec left, right; + progress_count += task->range.size(); + progress_update(); + } +} + +/* multithreaded binning builder */ +BVHNode* BVHBuild::build_node(const BVHObjectBinning& range, int level) +{ + size_t size = range.size(); + float leafSAH = params.sah_triangle_cost * range.leafSAH; + float splitSAH = params.sah_node_cost * range.bounds().half_area() + params.sah_triangle_cost * range.splitSAH; - if(params.use_spatial_split && minSAH == spatial.sah) - do_spatial_split(left, right, spec, spatial); - if(!left.num || !right.num) - do_object_split(left, right, spec, object); + /* make leaf node when threshold reached or SAH tells us */ + if(params.small_enough_for_leaf(size, level) || (size <= params.max_leaf_size && leafSAH < splitSAH)) + return create_leaf_node(range); + + /* perform split */ + BVHObjectBinning left, right; + range.split(&references[0], left, right); /* create inner node. */ - progress_num_duplicates += left.num + right.num - spec.num; + InnerNode *inner; - float progress_mid = lerp(progress_start, progress_end, (float)right.num / (float)(left.num + right.num)); + if(range.size() < THREAD_TASK_SIZE) { + /* local build */ + BVHNode *leftnode = build_node(left, level + 1); + BVHNode *rightnode = build_node(right, level + 1); - BVHNode* rightNode = build_node(right, level + 1, progress_start, progress_mid); - if(progress.get_cancel()) { - if(rightNode) rightNode->deleteSubtree(); - return NULL; + inner = new InnerNode(range.bounds(), leftnode, rightnode); } + else { + /* threaded build */ + inner = new InnerNode(range.bounds()); + + task_pool.push(new BVHBuildTask(inner, 0, left, level + 1), true); + task_pool.push(new BVHBuildTask(inner, 1, right, level + 1), true); + } + + return inner; +} - BVHNode* leftNode = build_node(left, level + 1, progress_mid, progress_end); - if(progress.get_cancel()) { - if(leftNode) leftNode->deleteSubtree(); +/* single threaded spatial split builder */ +BVHNode* BVHBuild::build_node(const BVHRange& range, int level) +{ + /* progress update */ + progress_update(); + if(progress.get_cancel()) return NULL; + + /* small enough or too deep => create leaf. */ + if(params.small_enough_for_leaf(range.size(), level)) { + progress_count += range.size(); + return create_leaf_node(range); + } + + /* splitting test */ + BVHMixedSplit split(this, range, level); + + if(split.no_split) { + progress_count += range.size(); + return create_leaf_node(range); } + + /* do split */ + BVHRange left, right; + split.split(this, left, right, range); + + progress_total += left.size() + right.size() - range.size(); + size_t total = progress_total; + + /* leaft node */ + BVHNode *leftnode = build_node(left, level + 1); + + /* right node (modify start for splits) */ + right.set_start(right.start() + progress_total - total); + BVHNode *rightnode = build_node(right, level + 1); - return new InnerNode(spec.bounds, leftNode, rightNode); + /* inner node */ + return new InnerNode(range.bounds(), leftnode, rightnode); } -BVHNode *BVHBuild::create_object_leaf_nodes(const Reference *ref, int num) +/* Create Nodes */ + +BVHNode *BVHBuild::create_object_leaf_nodes(const BVHReference *ref, int start, int num) { if(num == 0) { - BoundBox bounds; + BoundBox bounds = BoundBox::empty; return new LeafNode(bounds, 0, 0, 0); } else if(num == 1) { - prim_index.push_back(ref[0].prim_index); - prim_object.push_back(ref[0].prim_object); - uint visibility = objects[ref[0].prim_object]->visibility; - return new LeafNode(ref[0].bounds, visibility, prim_index.size()-1, prim_index.size()); + if(start == prim_index.size()) { + assert(params.use_spatial_split); + + prim_index.push_back(ref->prim_index()); + prim_object.push_back(ref->prim_object()); + } + else { + prim_index[start] = ref->prim_index(); + prim_object[start] = ref->prim_object(); + } + + uint visibility = objects[ref->prim_object()]->visibility; + return new LeafNode(ref->bounds(), visibility, start, start+1); } else { int mid = num/2; - BVHNode *leaf0 = create_object_leaf_nodes(ref, mid); - BVHNode *leaf1 = create_object_leaf_nodes(ref+mid, num-mid); + BVHNode *leaf0 = create_object_leaf_nodes(ref, start, mid); + BVHNode *leaf1 = create_object_leaf_nodes(ref+mid, start+mid, num-mid); - BoundBox bounds; + BoundBox bounds = BoundBox::empty; bounds.grow(leaf0->m_bounds); bounds.grow(leaf1->m_bounds); @@ -241,310 +345,136 @@ BVHNode *BVHBuild::create_object_leaf_nodes(const Reference *ref, int num) } } -BVHNode* BVHBuild::create_leaf_node(const NodeSpec& spec) +BVHNode* BVHBuild::create_leaf_node(const BVHRange& range) { vector<int>& p_index = prim_index; vector<int>& p_object = prim_object; - BoundBox bounds; - int num = 0; + BoundBox bounds = BoundBox::empty; + int num = 0, ob_num = 0; uint visibility = 0; - for(int i = 0; i < spec.num; i++) { - if(references.back().prim_index != -1) { - p_index.push_back(references.back().prim_index); - p_object.push_back(references.back().prim_object); - bounds.grow(references.back().bounds); - visibility |= objects[references.back().prim_object]->visibility; - references.pop_back(); + for(int i = 0; i < range.size(); i++) { + BVHReference& ref = references[range.start() + i]; + + if(ref.prim_index() != -1) { + if(range.start() + num == prim_index.size()) { + assert(params.use_spatial_split); + + p_index.push_back(ref.prim_index()); + p_object.push_back(ref.prim_object()); + } + else { + p_index[range.start() + num] = ref.prim_index(); + p_object[range.start() + num] = ref.prim_object(); + } + + bounds.grow(ref.bounds()); + visibility |= objects[ref.prim_object()]->visibility; num++; } + else { + if(ob_num < i) + references[range.start() + ob_num] = ref; + ob_num++; + } } BVHNode *leaf = NULL; if(num > 0) { - leaf = new LeafNode(bounds, visibility, p_index.size() - num, p_index.size()); + leaf = new LeafNode(bounds, visibility, range.start(), range.start() + num); - if(num == spec.num) + if(num == range.size()) return leaf; } /* while there may be multiple triangles in a leaf, for object primitives - * we want them to be the only one, so we */ - int ob_num = spec.num - num; - const Reference *ref = (ob_num)? &references.back() - (ob_num - 1): NULL; - BVHNode *oleaf = create_object_leaf_nodes(ref, ob_num); - for(int i = 0; i < ob_num; i++) - references.pop_back(); + * we want there to be the only one, so we keep splitting */ + const BVHReference *ref = (ob_num)? &references[range.start()]: NULL; + BVHNode *oleaf = create_object_leaf_nodes(ref, range.start() + num, ob_num); if(leaf) - return new InnerNode(spec.bounds, leaf, oleaf); + return new InnerNode(range.bounds(), leaf, oleaf); else return oleaf; } -/* Object Split */ +/* Tree Rotations */ -BVHBuild::ObjectSplit BVHBuild::find_object_split(const NodeSpec& spec, float nodeSAH) +void BVHBuild::rotate(BVHNode *node, int max_depth, int iterations) { - ObjectSplit split; - const Reference *ref_ptr = &references[references.size() - spec.num]; - - for(int dim = 0; dim < 3; dim++) { - /* sort references */ - bvh_reference_sort(references.size() - spec.num, references.size(), &references[0], dim); - - /* sweep right to left and determine bounds. */ - BoundBox right_bounds; - - for(int i = spec.num - 1; i > 0; i--) { - right_bounds.grow(ref_ptr[i].bounds); - spatial_right_bounds[i - 1] = right_bounds; - } - - /* sweep left to right and select lowest SAH. */ - BoundBox left_bounds; - - for(int i = 1; i < spec.num; i++) { - left_bounds.grow(ref_ptr[i - 1].bounds); - right_bounds = spatial_right_bounds[i - 1]; - - float sah = nodeSAH + - left_bounds.area() * params.triangle_cost(i) + - right_bounds.area() * params.triangle_cost(spec.num - i); - - if(sah < split.sah) { - split.sah = sah; - split.dim = dim; - split.num_left = i; - split.left_bounds = left_bounds; - split.right_bounds = right_bounds; - } - } - } - - return split; + /* in tested scenes, this resulted in slightly slower raytracing, so disabled + * it for now. could be implementation bug, or depend on the scene */ + if(node) + for(int i = 0; i < iterations; i++) + rotate(node, max_depth); } -void BVHBuild::do_object_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const ObjectSplit& split) +void BVHBuild::rotate(BVHNode *node, int max_depth) { - /* sort references according to split */ - int start = references.size() - spec.num; - int end = references.size(); /* todo: is this right? */ - - bvh_reference_sort(start, end, &references[0], split.dim); - - /* split node specs */ - left.num = split.num_left; - left.bounds = split.left_bounds; - right.num = spec.num - split.num_left; - right.bounds = split.right_bounds; -} - -/* Spatial Split */ - -BVHBuild::SpatialSplit BVHBuild::find_spatial_split(const NodeSpec& spec, float nodeSAH) -{ - /* initialize bins. */ - float3 origin = spec.bounds.min; - float3 binSize = (spec.bounds.max - origin) * (1.0f / (float)BVHParams::NUM_SPATIAL_BINS); - float3 invBinSize = 1.0f / binSize; - - for(int dim = 0; dim < 3; dim++) { - for(int i = 0; i < BVHParams::NUM_SPATIAL_BINS; i++) { - SpatialBin& bin = spatial_bins[dim][i]; - - bin.bounds = BoundBox(); - bin.enter = 0; - bin.exit = 0; - } - } - - /* chop references into bins. */ - for(unsigned int refIdx = references.size() - spec.num; refIdx < references.size(); refIdx++) { - const Reference& ref = references[refIdx]; - float3 firstBinf = (ref.bounds.min - origin) * invBinSize; - float3 lastBinf = (ref.bounds.max - origin) * invBinSize; - int3 firstBin = make_int3((int)firstBinf.x, (int)firstBinf.y, (int)firstBinf.z); - int3 lastBin = make_int3((int)lastBinf.x, (int)lastBinf.y, (int)lastBinf.z); + /* nothing to rotate if we reached a leaf node. */ + if(node->is_leaf() || max_depth < 0) + return; + + InnerNode *parent = (InnerNode*)node; - firstBin = clamp(firstBin, 0, BVHParams::NUM_SPATIAL_BINS - 1); - lastBin = clamp(lastBin, firstBin, BVHParams::NUM_SPATIAL_BINS - 1); + /* rotate all children first */ + for(size_t c = 0; c < 2; c++) + rotate(parent->children[c], max_depth-1); - for(int dim = 0; dim < 3; dim++) { - Reference currRef = ref; + /* compute current area of all children */ + BoundBox bounds0 = parent->children[0]->m_bounds; + BoundBox bounds1 = parent->children[1]->m_bounds; - for(int i = firstBin[dim]; i < lastBin[dim]; i++) { - Reference leftRef, rightRef; + float area0 = bounds0.half_area(); + float area1 = bounds1.half_area(); + float4 child_area = make_float4(area0, area1, 0.0f, 0.0f); - split_reference(leftRef, rightRef, currRef, dim, origin[dim] + binSize[dim] * (float)(i + 1)); - spatial_bins[dim][i].bounds.grow(leftRef.bounds); - currRef = rightRef; - } + /* find best rotation. we pick a target child of a first child, and swap + * this with an other child. we perform the best such swap. */ + float best_cost = FLT_MAX; + int best_child = -1, bets_target = -1, best_other = -1; - spatial_bins[dim][lastBin[dim]].bounds.grow(currRef.bounds); - spatial_bins[dim][firstBin[dim]].enter++; - spatial_bins[dim][lastBin[dim]].exit++; - } - } + for(size_t c = 0; c < 2; c++) { + /* ignore leaf nodes as we cannot descent into */ + if(parent->children[c]->is_leaf()) + continue; - /* select best split plane. */ - SpatialSplit split; + InnerNode *child = (InnerNode*)parent->children[c]; + BoundBox& other = (c == 0)? bounds1: bounds0; - for(int dim = 0; dim < 3; dim++) { - /* sweep right to left and determine bounds. */ - BoundBox right_bounds; + /* transpose child bounds */ + BoundBox target0 = child->children[0]->m_bounds; + BoundBox target1 = child->children[1]->m_bounds; - for(int i = BVHParams::NUM_SPATIAL_BINS - 1; i > 0; i--) { - right_bounds.grow(spatial_bins[dim][i].bounds); - spatial_right_bounds[i - 1] = right_bounds; - } + /* compute cost for both possible swaps */ + float cost0 = merge(other, target1).half_area() - child_area[c]; + float cost1 = merge(target0, other).half_area() - child_area[c]; - /* sweep left to right and select lowest SAH. */ - BoundBox left_bounds; - int leftNum = 0; - int rightNum = spec.num; + if(min(cost0,cost1) < best_cost) { + best_child = (int)c; + best_other = (int)(1-c); - for(int i = 1; i < BVHParams::NUM_SPATIAL_BINS; i++) { - left_bounds.grow(spatial_bins[dim][i - 1].bounds); - leftNum += spatial_bins[dim][i - 1].enter; - rightNum -= spatial_bins[dim][i - 1].exit; - - float sah = nodeSAH + - left_bounds.area() * params.triangle_cost(leftNum) + - spatial_right_bounds[i - 1].area() * params.triangle_cost(rightNum); - - if(sah < split.sah) { - split.sah = sah; - split.dim = dim; - split.pos = origin[dim] + binSize[dim] * (float)i; + if(cost0 < cost1) { + best_cost = cost0; + bets_target = 0; + } + else { + best_cost = cost0; + bets_target = 1; } } } - return split; -} - -void BVHBuild::do_spatial_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const SpatialSplit& split) -{ - /* Categorize references and compute bounds. - * - * Left-hand side: [left_start, left_end[ - * Uncategorized/split: [left_end, right_start[ - * Right-hand side: [right_start, refs.size()[ */ - - vector<Reference>& refs = references; - int left_start = refs.size() - spec.num; - int left_end = left_start; - int right_start = refs.size(); - - left.bounds = right.bounds = BoundBox(); - - for(int i = left_end; i < right_start; i++) { - if(refs[i].bounds.max[split.dim] <= split.pos) { - /* entirely on the left-hand side */ - left.bounds.grow(refs[i].bounds); - swap(refs[i], refs[left_end++]); - } - else if(refs[i].bounds.min[split.dim] >= split.pos) { - /* entirely on the right-hand side */ - right.bounds.grow(refs[i].bounds); - swap(refs[i--], refs[--right_start]); - } - } - - /* duplicate or unsplit references intersecting both sides. */ - while(left_end < right_start) { - /* split reference. */ - Reference lref, rref; - - split_reference(lref, rref, refs[left_end], split.dim, split.pos); - - /* compute SAH for duplicate/unsplit candidates. */ - BoundBox lub = left.bounds; // Unsplit to left: new left-hand bounds. - BoundBox rub = right.bounds; // Unsplit to right: new right-hand bounds. - BoundBox ldb = left.bounds; // Duplicate: new left-hand bounds. - BoundBox rdb = right.bounds; // Duplicate: new right-hand bounds. - - lub.grow(refs[left_end].bounds); - rub.grow(refs[left_end].bounds); - ldb.grow(lref.bounds); - rdb.grow(rref.bounds); - - float lac = params.triangle_cost(left_end - left_start); - float rac = params.triangle_cost(refs.size() - right_start); - float lbc = params.triangle_cost(left_end - left_start + 1); - float rbc = params.triangle_cost(refs.size() - right_start + 1); - - float unsplitLeftSAH = lub.area() * lbc + right.bounds.area() * rac; - float unsplitRightSAH = left.bounds.area() * lac + rub.area() * rbc; - float duplicateSAH = ldb.area() * lbc + rdb.area() * rbc; - float minSAH = min(min(unsplitLeftSAH, unsplitRightSAH), duplicateSAH); - - if(minSAH == unsplitLeftSAH) { - /* unsplit to left */ - left.bounds = lub; - left_end++; - } - else if(minSAH == unsplitRightSAH) { - /* unsplit to right */ - right.bounds = rub; - swap(refs[left_end], refs[--right_start]); - } - else { - /* duplicate */ - left.bounds = ldb; - right.bounds = rdb; - refs[left_end++] = lref; - refs.push_back(rref); - } - } - - left.num = left_end - left_start; - right.num = refs.size() - right_start; -} + /* if we did not find a swap that improves the SAH then do nothing */ + if(best_cost >= 0) + return; -void BVHBuild::split_reference(Reference& left, Reference& right, const Reference& ref, int dim, float pos) -{ - /* initialize references. */ - left.prim_index = right.prim_index = ref.prim_index; - left.prim_object = right.prim_object = ref.prim_object; - left.bounds = right.bounds = BoundBox(); - - /* loop over vertices/edges. */ - Object *ob = objects[ref.prim_object]; - const Mesh *mesh = ob->mesh; - const int *inds = mesh->triangles[ref.prim_index].v; - const float3 *verts = &mesh->verts[0]; - const float3* v1 = &verts[inds[2]]; - - for(int i = 0; i < 3; i++) { - const float3* v0 = v1; - int vindex = inds[i]; - v1 = &verts[vindex]; - float v0p = (*v0)[dim]; - float v1p = (*v1)[dim]; - - /* insert vertex to the boxes it belongs to. */ - if(v0p <= pos) - left.bounds.grow(*v0); - - if(v0p >= pos) - right.bounds.grow(*v0); - - /* edge intersects the plane => insert intersection to both boxes. */ - if((v0p < pos && v1p > pos) || (v0p > pos && v1p < pos)) { - float3 t = lerp(*v0, *v1, clamp((pos - v0p) / (v1p - v0p), 0.0f, 1.0f)); - left.bounds.grow(t); - right.bounds.grow(t); - } - } + /* perform the best found tree rotation */ + InnerNode *child = (InnerNode*)parent->children[best_child]; - /* intersect with original bounds. */ - left.bounds.max[dim] = pos; - right.bounds.min[dim] = pos; - left.bounds.intersect(ref.bounds); - right.bounds.intersect(ref.bounds); + swap(parent->children[best_other], child->children[bets_target]); + child->m_bounds = merge(child->children[0]->m_bounds, child->children[1]->m_bounds); } CCL_NAMESPACE_END diff --git a/intern/cycles/bvh/bvh_build.h b/intern/cycles/bvh/bvh_build.h index 1fa1951d7f2..84e14632b4b 100644 --- a/intern/cycles/bvh/bvh_build.h +++ b/intern/cycles/bvh/bvh_build.h @@ -21,8 +21,10 @@ #include <float.h> #include "bvh.h" +#include "bvh_binning.h" #include "util_boundbox.h" +#include "util_task.h" #include "util_vector.h" CCL_NAMESPACE_BEGIN @@ -37,28 +39,7 @@ class Progress; class BVHBuild { public: - struct Reference - { - int prim_index; - int prim_object; - BoundBox bounds; - - Reference() - { - } - }; - - struct NodeSpec - { - int num; - BoundBox bounds; - - NodeSpec() - { - num = 0; - } - }; - + /* Constructor/Destructor */ BVHBuild( const vector<Object*>& objects, vector<int>& prim_index, @@ -70,63 +51,37 @@ public: BVHNode *run(); protected: + friend class BVHMixedSplit; + friend class BVHObjectSplit; + friend class BVHSpatialSplit; + /* adding references */ - void add_reference_mesh(NodeSpec& root, Mesh *mesh, int i); - void add_reference_object(NodeSpec& root, Object *ob, int i); - void add_references(NodeSpec& root); + void add_reference_mesh(BoundBox& root, BoundBox& center, Mesh *mesh, int i); + void add_reference_object(BoundBox& root, BoundBox& center, Object *ob, int i); + void add_references(BVHRange& root); /* building */ - BVHNode *build_node(const NodeSpec& spec, int level, float progress_start, float progress_end); - BVHNode *create_leaf_node(const NodeSpec& spec); - BVHNode *create_object_leaf_nodes(const Reference *ref, int num); - - void progress_update(float progress_start, float progress_end); - - /* object splits */ - struct ObjectSplit - { - float sah; - int dim; - int num_left; - BoundBox left_bounds; - BoundBox right_bounds; - - ObjectSplit() - : sah(FLT_MAX), dim(0), num_left(0) - { - } - }; - - ObjectSplit find_object_split(const NodeSpec& spec, float nodeSAH); - void do_object_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const ObjectSplit& split); - - /* spatial splits */ - struct SpatialSplit - { - float sah; - int dim; - float pos; - - SpatialSplit() - : sah(FLT_MAX), dim(0), pos(0.0f) - { - } - }; - - struct SpatialBin - { - BoundBox bounds; - int enter; - int exit; - }; - - SpatialSplit find_spatial_split(const NodeSpec& spec, float nodeSAH); - void do_spatial_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const SpatialSplit& split); - void split_reference(Reference& left, Reference& right, const Reference& ref, int dim, float pos); + BVHNode *build_node(const BVHRange& range, int level); + BVHNode *build_node(const BVHObjectBinning& range, int level); + BVHNode *create_leaf_node(const BVHRange& range); + BVHNode *create_object_leaf_nodes(const BVHReference *ref, int start, int num); + + /* threads */ + enum { THREAD_TASK_SIZE = 4096 }; + void thread_build_node(Task *task_, int thread_id); + thread_mutex build_mutex; + + /* progress */ + void progress_update(); + + /* tree rotations */ + void rotate(BVHNode *node, int max_depth); + void rotate(BVHNode *node, int max_depth, int iterations); /* objects and primitive references */ vector<Object*> objects; - vector<Reference> references; + vector<BVHReference> references; + int num_original_references; /* output primitive indexes and objects */ vector<int>& prim_index; @@ -138,12 +93,17 @@ protected: /* progress reporting */ Progress& progress; double progress_start_time; - int progress_num_duplicates; + size_t progress_count; + size_t progress_total; + size_t progress_original_total; /* spatial splitting */ float spatial_min_overlap; vector<BoundBox> spatial_right_bounds; - SpatialBin spatial_bins[3][BVHParams::NUM_SPATIAL_BINS]; + BVHSpatialBin spatial_bins[3][BVHParams::NUM_SPATIAL_BINS]; + + /* threads */ + TaskPool task_pool; }; CCL_NAMESPACE_END diff --git a/intern/cycles/bvh/bvh_node.cpp b/intern/cycles/bvh/bvh_node.cpp index 63683bae4a3..4edfb4b70a4 100644 --- a/intern/cycles/bvh/bvh_node.cpp +++ b/intern/cycles/bvh/bvh_node.cpp @@ -24,6 +24,8 @@ CCL_NAMESPACE_BEGIN +/* BVH Node */ + int BVHNode::getSubtreeSize(BVH_STAT stat) const { int cnt = 0; @@ -59,7 +61,8 @@ int BVHNode::getSubtreeSize(BVH_STAT stat) const void BVHNode::deleteSubtree() { for(int i=0;i<num_children();i++) - get_child(i)->deleteSubtree(); + if(get_child(i)) + get_child(i)->deleteSubtree(); delete this; } @@ -70,12 +73,27 @@ float BVHNode::computeSubtreeSAHCost(const BVHParams& p, float probability) cons for(int i=0;i<num_children();i++) { BVHNode *child = get_child(i); - SAH += child->computeSubtreeSAHCost(p, probability * child->m_bounds.area()/m_bounds.area()); + SAH += child->computeSubtreeSAHCost(p, probability * child->m_bounds.safe_area()/m_bounds.safe_area()); } return SAH; } +uint BVHNode::update_visibility() +{ + if(!is_leaf() && m_visibility == 0) { + InnerNode *inner = (InnerNode*)this; + BVHNode *child0 = inner->children[0]; + BVHNode *child1 = inner->children[1]; + + m_visibility = child0->update_visibility()|child1->update_visibility(); + } + + return m_visibility; +} + +/* Inner Node */ + void InnerNode::print(int depth) const { for(int i = 0; i < depth; i++) diff --git a/intern/cycles/bvh/bvh_node.h b/intern/cycles/bvh/bvh_node.h index 5e0a17a1193..5c00f7b7a38 100644 --- a/intern/cycles/bvh/bvh_node.h +++ b/intern/cycles/bvh/bvh_node.h @@ -49,8 +49,6 @@ public: virtual int num_triangles() const { return 0; } virtual void print(int depth = 0) const = 0; - float getArea() const { return m_bounds.area(); } - BoundBox m_bounds; uint m_visibility; @@ -58,6 +56,8 @@ public: int getSubtreeSize(BVH_STAT stat=BVH_STAT_NODE_COUNT) const; float computeSubtreeSAHCost(const BVHParams& p, float probability = 1.0f) const; void deleteSubtree(); + + uint update_visibility(); }; class InnerNode : public BVHNode @@ -66,9 +66,21 @@ public: InnerNode(const BoundBox& bounds, BVHNode* child0, BVHNode* child1) { m_bounds = bounds; - m_visibility = child0->m_visibility|child1->m_visibility; children[0] = child0; children[1] = child1; + + if(child0 && child1) + m_visibility = child0->m_visibility|child1->m_visibility; + else + m_visibility = 0; /* happens on build cancel */ + } + + InnerNode(const BoundBox& bounds) + { + m_bounds = bounds; + m_visibility = 0; + children[0] = NULL; + children[1] = NULL; } bool is_leaf() const { return false; } diff --git a/intern/cycles/bvh/bvh_params.h b/intern/cycles/bvh/bvh_params.h index 38093438500..0cf5e905fea 100644 --- a/intern/cycles/bvh/bvh_params.h +++ b/intern/cycles/bvh/bvh_params.h @@ -18,6 +18,8 @@ #ifndef __BVH_PARAMS_H__ #define __BVH_PARAMS_H__ +#include "util_boundbox.h" + CCL_NAMESPACE_BEGIN /* BVH Parameters */ @@ -73,14 +75,97 @@ public: } /* SAH costs */ - float cost(int num_nodes, int num_tris) const + __forceinline float cost(int num_nodes, int num_tris) const { return node_cost(num_nodes) + triangle_cost(num_tris); } - float triangle_cost(int n) const + __forceinline float triangle_cost(int n) const { return n*sah_triangle_cost; } - float node_cost(int n) const + __forceinline float node_cost(int n) const { return n*sah_node_cost; } + + __forceinline bool small_enough_for_leaf(int size, int level) + { return (size <= min_leaf_size || level >= MAX_DEPTH); } +}; + +/* BVH Reference + * + * Reference to a primitive. Primitive index and object are sneakily packed + * into BoundBox to reduce memory usage and align nicely */ + +class BVHReference +{ +public: + __forceinline BVHReference() {} + + __forceinline BVHReference(const BoundBox& bounds_, int prim_index, int prim_object) + : rbounds(bounds_) + { + rbounds.min.w = __int_as_float(prim_index); + rbounds.max.w = __int_as_float(prim_object); + } + + __forceinline const BoundBox& bounds() const { return rbounds; } + __forceinline int prim_index() const { return __float_as_int(rbounds.min.w); } + __forceinline int prim_object() const { return __float_as_int(rbounds.max.w); } + +protected: + BoundBox rbounds; +}; + +/* BVH Range + * + * Build range used during construction, to indicate the bounds and place in + * the reference array of a subset of pirmitives Again uses trickery to pack + * integers into BoundBox for alignment purposes. */ + +class BVHRange +{ +public: + __forceinline BVHRange() + { + rbounds.min.w = __int_as_float(0); + rbounds.max.w = __int_as_float(0); + } + + __forceinline BVHRange(const BoundBox& bounds_, int start_, int size_) + : rbounds(bounds_) + { + rbounds.min.w = __int_as_float(start_); + rbounds.max.w = __int_as_float(size_); + } + + __forceinline BVHRange(const BoundBox& bounds_, const BoundBox& cbounds_, int start_, int size_) + : rbounds(bounds_), cbounds(cbounds_) + { + rbounds.min.w = __int_as_float(start_); + rbounds.max.w = __int_as_float(size_); + } + + __forceinline void set_start(int start_) { rbounds.min.w = __int_as_float(start_); } + + __forceinline const BoundBox& bounds() const { return rbounds; } + __forceinline const BoundBox& cent_bounds() const { return cbounds; } + __forceinline int start() const { return __float_as_int(rbounds.min.w); } + __forceinline int size() const { return __float_as_int(rbounds.max.w); } + __forceinline int end() const { return start() + size(); } + +protected: + BoundBox rbounds; + BoundBox cbounds; +}; + +/* BVH Spatial Bin */ + +struct BVHSpatialBin +{ + BoundBox bounds; + int enter; + int exit; + + __forceinline BVHSpatialBin() + { + } }; CCL_NAMESPACE_END diff --git a/intern/cycles/bvh/bvh_sort.cpp b/intern/cycles/bvh/bvh_sort.cpp index ee4531a4843..bef384be592 100644 --- a/intern/cycles/bvh/bvh_sort.cpp +++ b/intern/cycles/bvh/bvh_sort.cpp @@ -32,23 +32,23 @@ public: dim = dim_; } - bool operator()(const BVHBuild::Reference& ra, const BVHBuild::Reference& rb) + bool operator()(const BVHReference& ra, const BVHReference& rb) { - float ca = ra.bounds.min[dim] + ra.bounds.max[dim]; - float cb = rb.bounds.min[dim] + rb.bounds.max[dim]; + float ca = ra.bounds().min[dim] + ra.bounds().max[dim]; + 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_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; return false; } }; -void bvh_reference_sort(int start, int end, BVHBuild::Reference *data, int dim) +void bvh_reference_sort(int start, int end, BVHReference *data, int dim) { sort(data+start, data+end, BVHReferenceCompare(dim)); } diff --git a/intern/cycles/bvh/bvh_sort.h b/intern/cycles/bvh/bvh_sort.h index f0676948146..ba35ba3fae7 100644 --- a/intern/cycles/bvh/bvh_sort.h +++ b/intern/cycles/bvh/bvh_sort.h @@ -20,7 +20,7 @@ CCL_NAMESPACE_BEGIN -void bvh_reference_sort(int start, int end, BVHBuild::Reference *data, int dim); +void bvh_reference_sort(int start, int end, BVHReference *data, int dim); CCL_NAMESPACE_END diff --git a/intern/cycles/bvh/bvh_split.cpp b/intern/cycles/bvh/bvh_split.cpp new file mode 100644 index 00000000000..263c5834428 --- /dev/null +++ b/intern/cycles/bvh/bvh_split.cpp @@ -0,0 +1,293 @@ +/* + * Adapted from code copyright 2009-2010 NVIDIA Corporation + * Modifications Copyright 2011, Blender Foundation. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "bvh_build.h" +#include "bvh_split.h" +#include "bvh_sort.h" + +#include "mesh.h" +#include "object.h" + +#include "util_algorithm.h" + +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) +{ + const BVHReference *ref_ptr = &builder->references[range.start()]; + float min_sah = FLT_MAX; + + for(int dim = 0; dim < 3; dim++) { + /* sort references */ + bvh_reference_sort(range.start(), range.end(), &builder->references[0], 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()); + builder->spatial_right_bounds[i - 1] = right_bounds; + } + + /* sweep left to right and select lowest SAH. */ + BoundBox left_bounds = BoundBox::empty; + + for(int i = 1; i < range.size(); i++) { + left_bounds.grow(ref_ptr[i - 1].bounds()); + right_bounds = builder->spatial_right_bounds[i - 1]; + + float sah = nodeSAH + + left_bounds.safe_area() * builder->params.triangle_cost(i) + + right_bounds.safe_area() * builder->params.triangle_cost(range.size() - i); + + if(sah < min_sah) { + min_sah = sah; + + this->sah = sah; + this->dim = dim; + this->num_left = i; + this->left_bounds = left_bounds; + this->right_bounds = right_bounds; + } + } + } +} + +void BVHObjectSplit::split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range) +{ + /* sort references according to split */ + bvh_reference_sort(range.start(), range.end(), &builder->references[0], this->dim); + + /* split node ranges */ + left = BVHRange(this->left_bounds, range.start(), this->num_left); + right = BVHRange(this->right_bounds, left.end(), range.size() - this->num_left); + +} + +/* Spatial Split */ + +BVHSpatialSplit::BVHSpatialSplit(BVHBuild *builder, const BVHRange& range, float nodeSAH) +: sah(FLT_MAX), dim(0), pos(0.0f) +{ + /* initialize bins. */ + float3 origin = range.bounds().min; + float3 binSize = (range.bounds().max - origin) * (1.0f / (float)BVHParams::NUM_SPATIAL_BINS); + float3 invBinSize = 1.0f / binSize; + + for(int dim = 0; dim < 3; dim++) { + for(int i = 0; i < BVHParams::NUM_SPATIAL_BINS; i++) { + BVHSpatialBin& bin = builder->spatial_bins[dim][i]; + + bin.bounds = BoundBox::empty; + bin.enter = 0; + bin.exit = 0; + } + } + + /* chop references into bins. */ + for(unsigned int refIdx = range.start(); refIdx < range.end(); refIdx++) { + const BVHReference& ref = builder->references[refIdx]; + float3 firstBinf = (ref.bounds().min - origin) * invBinSize; + float3 lastBinf = (ref.bounds().max - origin) * invBinSize; + int3 firstBin = make_int3((int)firstBinf.x, (int)firstBinf.y, (int)firstBinf.z); + int3 lastBin = make_int3((int)lastBinf.x, (int)lastBinf.y, (int)lastBinf.z); + + firstBin = clamp(firstBin, 0, BVHParams::NUM_SPATIAL_BINS - 1); + lastBin = clamp(lastBin, firstBin, BVHParams::NUM_SPATIAL_BINS - 1); + + for(int dim = 0; dim < 3; dim++) { + BVHReference currRef = ref; + + for(int i = firstBin[dim]; i < lastBin[dim]; i++) { + 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()); + 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++; + } + } + + /* select best split plane. */ + for(int dim = 0; dim < 3; dim++) { + /* sweep right to left and determine bounds. */ + 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; + } + + /* sweep left to right and select lowest SAH. */ + BoundBox left_bounds = BoundBox::empty; + int leftNum = 0; + 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; + + float sah = nodeSAH + + left_bounds.safe_area() * builder->params.triangle_cost(leftNum) + + builder->spatial_right_bounds[i - 1].safe_area() * builder->params.triangle_cost(rightNum); + + if(sah < this->sah) { + this->sah = sah; + this->dim = dim; + this->pos = origin[dim] + binSize[dim] * (float)i; + } + } + } +} + +void BVHSpatialSplit::split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range) +{ + /* Categorize references and compute bounds. + * + * Left-hand side: [left_start, left_end[ + * Uncategorized/split: [left_end, right_start[ + * Right-hand side: [right_start, refs.size()[ */ + + vector<BVHReference>& refs = builder->references; + int left_start = range.start(); + int left_end = left_start; + int right_start = range.end(); + int right_end = range.end(); + BoundBox left_bounds = BoundBox::empty; + BoundBox right_bounds = BoundBox::empty; + + for(int i = left_end; i < right_start; i++) { + if(refs[i].bounds().max[this->dim] <= this->pos) { + /* entirely on the left-hand side */ + left_bounds.grow(refs[i].bounds()); + swap(refs[i], refs[left_end++]); + } + else if(refs[i].bounds().min[this->dim] >= this->pos) { + /* entirely on the right-hand side */ + right_bounds.grow(refs[i].bounds()); + swap(refs[i--], refs[--right_start]); + } + } + + /* duplicate or unsplit references intersecting both sides. */ + while(left_end < right_start) { + /* split reference. */ + BVHReference lref, rref; + + split_reference(builder, lref, rref, refs[left_end], this->dim, this->pos); + + /* compute SAH for duplicate/unsplit candidates. */ + BoundBox lub = left_bounds; // Unsplit to left: new left-hand bounds. + BoundBox rub = right_bounds; // Unsplit to right: new right-hand bounds. + BoundBox ldb = left_bounds; // Duplicate: new left-hand bounds. + BoundBox rdb = right_bounds; // Duplicate: new right-hand bounds. + + lub.grow(refs[left_end].bounds()); + rub.grow(refs[left_end].bounds()); + ldb.grow(lref.bounds()); + rdb.grow(rref.bounds()); + + float lac = builder->params.triangle_cost(left_end - left_start); + float rac = builder->params.triangle_cost(right_end - right_start); + float lbc = builder->params.triangle_cost(left_end - left_start + 1); + float rbc = builder->params.triangle_cost(right_end - right_start + 1); + + float unsplitLeftSAH = lub.safe_area() * lbc + right_bounds.safe_area() * rac; + float unsplitRightSAH = left_bounds.safe_area() * lac + rub.safe_area() * rbc; + float duplicateSAH = ldb.safe_area() * lbc + rdb.safe_area() * rbc; + float minSAH = min(min(unsplitLeftSAH, unsplitRightSAH), duplicateSAH); + + if(minSAH == unsplitLeftSAH) { + /* unsplit to left */ + left_bounds = lub; + left_end++; + } + else if(minSAH == unsplitRightSAH) { + /* unsplit to right */ + right_bounds = rub; + swap(refs[left_end], refs[--right_start]); + } + else { + /* duplicate */ + left_bounds = ldb; + right_bounds = rdb; + refs[left_end++] = lref; + refs.insert(refs.begin() + right_end, rref); + right_end++; + } + } + + left = BVHRange(left_bounds, left_start, left_end - left_start); + right = BVHRange(right_bounds, right_start, right_end - right_start); +} + +void BVHSpatialSplit::split_reference(BVHBuild *builder, BVHReference& left, BVHReference& right, const BVHReference& ref, int dim, float pos) +{ + /* initialize boundboxes */ + BoundBox left_bounds = BoundBox::empty; + BoundBox right_bounds = BoundBox::empty; + + /* loop over vertices/edges. */ + Object *ob = builder->objects[ref.prim_object()]; + const Mesh *mesh = ob->mesh; + const int *inds = mesh->triangles[ref.prim_index()].v; + const float3 *verts = &mesh->verts[0]; + const float3* v1 = &verts[inds[2]]; + + for(int i = 0; i < 3; i++) { + const float3* v0 = v1; + int vindex = inds[i]; + v1 = &verts[vindex]; + float v0p = (*v0)[dim]; + float v1p = (*v1)[dim]; + + /* insert vertex to the boxes it belongs to. */ + if(v0p <= pos) + left_bounds.grow(*v0); + + if(v0p >= pos) + right_bounds.grow(*v0); + + /* edge intersects the plane => insert intersection to both boxes. */ + if((v0p < pos && v1p > pos) || (v0p > pos && v1p < pos)) { + float3 t = lerp(*v0, *v1, clamp((pos - v0p) / (v1p - v0p), 0.0f, 1.0f)); + left_bounds.grow(t); + right_bounds.grow(t); + } + } + + /* intersect with original bounds. */ + left_bounds.max[dim] = pos; + right_bounds.min[dim] = pos; + left_bounds.intersect(ref.bounds()); + right_bounds.intersect(ref.bounds()); + + /* set referecnes */ + left = BVHReference(left_bounds, ref.prim_index(), ref.prim_object()); + right = BVHReference(right_bounds, ref.prim_index(), ref.prim_object()); +} + +CCL_NAMESPACE_END + diff --git a/intern/cycles/bvh/bvh_split.h b/intern/cycles/bvh/bvh_split.h new file mode 100644 index 00000000000..1f4befbe8e2 --- /dev/null +++ b/intern/cycles/bvh/bvh_split.h @@ -0,0 +1,110 @@ +/* + * Adapted from code copyright 2009-2010 NVIDIA Corporation + * Modifications Copyright 2011, Blender Foundation. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __BVH_SPLIT_H__ +#define __BVH_SPLIT_H__ + +#include "bvh_build.h" +#include "bvh_params.h" + +CCL_NAMESPACE_BEGIN + +class BVHBuild; + +/* Object Split */ + +class BVHObjectSplit +{ +public: + float sah; + int dim; + int num_left; + BoundBox left_bounds; + BoundBox right_bounds; + + BVHObjectSplit() {} + BVHObjectSplit(BVHBuild *builder, const BVHRange& range, float nodeSAH); + + void split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range); +}; + +/* Spatial Split */ + +class BVHSpatialSplit +{ +public: + float sah; + int dim; + float pos; + + BVHSpatialSplit() : sah(FLT_MAX), dim(0), pos(0.0f) {} + BVHSpatialSplit(BVHBuild *builder, const BVHRange& range, float nodeSAH); + + void split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range); + void split_reference(BVHBuild *builder, BVHReference& left, BVHReference& right, const BVHReference& ref, int dim, float pos); +}; + +/* Mixed Object-Spatial Split */ + +class BVHMixedSplit +{ +public: + BVHObjectSplit object; + BVHSpatialSplit spatial; + + float leafSAH; + float nodeSAH; + float minSAH; + + bool no_split; + + __forceinline BVHMixedSplit(BVHBuild *builder, const BVHRange& range, int level) + { + /* find split candidates. */ + float area = range.bounds().safe_area(); + + leafSAH = area * builder->params.triangle_cost(range.size()); + nodeSAH = area * builder->params.node_cost(2); + + object = BVHObjectSplit(builder, 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); + } + + /* leaf SAH is the lowest => create leaf. */ + minSAH = min(min(leafSAH, object.sah), spatial.sah); + no_split = (minSAH == leafSAH && range.size() <= builder->params.max_leaf_size); + } + + __forceinline void split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range) + { + if(builder->params.use_spatial_split && minSAH == spatial.sah) + spatial.split(builder, left, right, range); + if(!left.size() || !right.size()) + object.split(builder, left, right, range); + } +}; + +CCL_NAMESPACE_END + +#endif /* __BVH_SPLIT_H__ */ + |