Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/intern/cycles/bvh
diff options
context:
space:
mode:
Diffstat (limited to 'intern/cycles/bvh')
-rw-r--r--intern/cycles/bvh/CMakeLists.txt4
-rw-r--r--intern/cycles/bvh/bvh.cpp4
-rw-r--r--intern/cycles/bvh/bvh_binning.cpp223
-rw-r--r--intern/cycles/bvh/bvh_binning.h86
-rw-r--r--intern/cycles/bvh/bvh_build.cpp636
-rw-r--r--intern/cycles/bvh/bvh_build.h110
-rw-r--r--intern/cycles/bvh/bvh_node.cpp22
-rw-r--r--intern/cycles/bvh/bvh_node.h18
-rw-r--r--intern/cycles/bvh/bvh_params.h91
-rw-r--r--intern/cycles/bvh/bvh_sort.cpp16
-rw-r--r--intern/cycles/bvh/bvh_sort.h2
-rw-r--r--intern/cycles/bvh/bvh_split.cpp293
-rw-r--r--intern/cycles/bvh/bvh_split.h110
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__ */
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-13 07:54:53 +0300