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/bvh_build.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'intern/cycles/bvh/bvh_build.cpp')
-rw-r--r--intern/cycles/bvh/bvh_build.cpp285
1 files changed, 211 insertions, 74 deletions
diff --git a/intern/cycles/bvh/bvh_build.cpp b/intern/cycles/bvh/bvh_build.cpp
index 76a1bfa2bfe..67ffb6853d6 100644
--- a/intern/cycles/bvh/bvh_build.cpp
+++ b/intern/cycles/bvh/bvh_build.cpp
@@ -33,6 +33,7 @@
#include "util_stack_allocator.h"
#include "util_simd.h"
#include "util_time.h"
+#include "util_queue.h"
CCL_NAMESPACE_BEGIN
@@ -99,7 +100,8 @@ BVHBuild::BVHBuild(const vector<Object*>& objects_,
prim_object(prim_object_),
params(params_),
progress(progress_),
- progress_start_time(0.0)
+ progress_start_time(0.0),
+ unaligned_heuristic(objects_)
{
spatial_min_overlap = 0.0f;
}
@@ -112,68 +114,74 @@ BVHBuild::~BVHBuild()
void BVHBuild::add_reference_mesh(BoundBox& root, BoundBox& center, Mesh *mesh, int i)
{
- Attribute *attr_mP = NULL;
-
- if(mesh->has_motion_blur())
- attr_mP = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
+ if(params.primitive_mask & PRIMITIVE_ALL_TRIANGLE) {
+ Attribute *attr_mP = NULL;
- for(uint j = 0; j < mesh->triangles.size(); j++) {
- Mesh::Triangle t = mesh->triangles[j];
- BoundBox bounds = BoundBox::empty;
- PrimitiveType type = PRIMITIVE_TRIANGLE;
+ if(mesh->has_motion_blur())
+ attr_mP = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
+
+ size_t num_triangles = mesh->num_triangles();
+ for(uint j = 0; j < num_triangles; j++) {
+ Mesh::Triangle t = mesh->get_triangle(j);
+ BoundBox bounds = BoundBox::empty;
+ PrimitiveType type = PRIMITIVE_TRIANGLE;
- t.bounds_grow(&mesh->verts[0], bounds);
+ t.bounds_grow(&mesh->verts[0], bounds);
- /* motion triangles */
- if(attr_mP) {
- size_t mesh_size = mesh->verts.size();
- size_t steps = mesh->motion_steps - 1;
- float3 *vert_steps = attr_mP->data_float3();
+ /* motion triangles */
+ if(attr_mP) {
+ size_t mesh_size = mesh->verts.size();
+ size_t steps = mesh->motion_steps - 1;
+ float3 *vert_steps = attr_mP->data_float3();
- for(size_t i = 0; i < steps; i++)
- t.bounds_grow(vert_steps + i*mesh_size, bounds);
+ for(size_t i = 0; i < steps; i++)
+ t.bounds_grow(vert_steps + i*mesh_size, bounds);
- type = PRIMITIVE_MOTION_TRIANGLE;
- }
+ type = PRIMITIVE_MOTION_TRIANGLE;
+ }
- if(bounds.valid()) {
- references.push_back(BVHReference(bounds, j, i, type));
- root.grow(bounds);
- center.grow(bounds.center2());
+ if(bounds.valid()) {
+ references.push_back(BVHReference(bounds, j, i, type));
+ root.grow(bounds);
+ center.grow(bounds.center2());
+ }
}
}
- Attribute *curve_attr_mP = NULL;
+ if(params.primitive_mask & PRIMITIVE_ALL_CURVE) {
+ Attribute *curve_attr_mP = NULL;
- if(mesh->has_motion_blur())
- curve_attr_mP = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
+ if(mesh->has_motion_blur())
+ curve_attr_mP = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
- for(uint j = 0; j < mesh->curves.size(); j++) {
- Mesh::Curve curve = mesh->curves[j];
- PrimitiveType type = PRIMITIVE_CURVE;
+ size_t num_curves = mesh->num_curves();
+ for(uint j = 0; j < num_curves; j++) {
+ Mesh::Curve curve = mesh->get_curve(j);
+ PrimitiveType type = PRIMITIVE_CURVE;
- for(int k = 0; k < curve.num_keys - 1; k++) {
- BoundBox bounds = BoundBox::empty;
- curve.bounds_grow(k, &mesh->curve_keys[0], bounds);
+ for(int k = 0; k < curve.num_keys - 1; k++) {
+ BoundBox bounds = BoundBox::empty;
+ curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bounds);
- /* motion curve */
- if(curve_attr_mP) {
- size_t mesh_size = mesh->curve_keys.size();
- size_t steps = mesh->motion_steps - 1;
- float4 *key_steps = curve_attr_mP->data_float4();
+ /* motion curve */
+ if(curve_attr_mP) {
+ size_t mesh_size = mesh->curve_keys.size();
+ size_t steps = mesh->motion_steps - 1;
+ float3 *key_steps = curve_attr_mP->data_float3();
- for(size_t i = 0; i < steps; i++)
- curve.bounds_grow(k, key_steps + i*mesh_size, bounds);
+ for(size_t i = 0; i < steps; i++)
+ curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bounds);
- type = PRIMITIVE_MOTION_CURVE;
- }
+ type = PRIMITIVE_MOTION_CURVE;
+ }
- if(bounds.valid()) {
- int packed_type = PRIMITIVE_PACK_SEGMENT(type, k);
-
- references.push_back(BVHReference(bounds, j, i, packed_type));
- root.grow(bounds);
- center.grow(bounds.center2());
+ if(bounds.valid()) {
+ int packed_type = PRIMITIVE_PACK_SEGMENT(type, k);
+
+ references.push_back(BVHReference(bounds, j, i, packed_type));
+ root.grow(bounds);
+ center.grow(bounds.center2());
+ }
}
}
}
@@ -188,10 +196,10 @@ void BVHBuild::add_reference_object(BoundBox& root, BoundBox& center, Object *ob
static size_t count_curve_segments(Mesh *mesh)
{
- size_t num = 0, num_curves = mesh->curves.size();
+ size_t num = 0, num_curves = mesh->num_curves();
for(size_t i = 0; i < num_curves; i++)
- num += mesh->curves[i].num_keys - 1;
+ num += mesh->get_curve(i).num_keys - 1;
return num;
}
@@ -203,16 +211,27 @@ void BVHBuild::add_references(BVHRange& root)
foreach(Object *ob, objects) {
if(params.top_level) {
+ if(!ob->is_traceable()) {
+ continue;
+ }
if(!ob->mesh->is_instanced()) {
- num_alloc_references += ob->mesh->triangles.size();
- num_alloc_references += count_curve_segments(ob->mesh);
+ if(params.primitive_mask & PRIMITIVE_ALL_TRIANGLE) {
+ num_alloc_references += ob->mesh->num_triangles();
+ }
+ if(params.primitive_mask & PRIMITIVE_ALL_CURVE) {
+ num_alloc_references += count_curve_segments(ob->mesh);
+ }
}
else
num_alloc_references++;
}
else {
- num_alloc_references += ob->mesh->triangles.size();
- num_alloc_references += count_curve_segments(ob->mesh);
+ if(params.primitive_mask & PRIMITIVE_ALL_TRIANGLE) {
+ num_alloc_references += ob->mesh->num_triangles();
+ }
+ if(params.primitive_mask & PRIMITIVE_ALL_CURVE) {
+ num_alloc_references += count_curve_segments(ob->mesh);
+ }
}
}
@@ -224,6 +243,10 @@ void BVHBuild::add_references(BVHRange& root)
foreach(Object *ob, objects) {
if(params.top_level) {
+ if(!ob->is_traceable()) {
+ ++i;
+ continue;
+ }
if(!ob->mesh->is_instanced())
add_reference_mesh(bounds, center, ob->mesh, i);
else
@@ -326,11 +349,13 @@ BVHNode* BVHBuild::run()
VLOG(1) << "BVH build statistics:\n"
<< " Build time: " << time_dt() - build_start_time << "\n"
<< " Total number of nodes: "
- << rootnode->getSubtreeSize(BVH_STAT_NODE_COUNT) << "\n"
+ << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_NODE_COUNT)) << "\n"
<< " Number of inner nodes: "
- << rootnode->getSubtreeSize(BVH_STAT_INNER_COUNT) << "\n"
+ << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_INNER_COUNT)) << "\n"
<< " Number of leaf nodes: "
- << rootnode->getSubtreeSize(BVH_STAT_LEAF_COUNT) << "\n"
+ << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_LEAF_COUNT)) << "\n"
+ << " Number of unaligned nodes: "
+ << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_UNALIGNED_COUNT)) << "\n"
<< " Allocation slop factor: "
<< ((prim_type.capacity() != 0)
? (float)prim_type.size() / prim_type.capacity()
@@ -436,10 +461,11 @@ BVHNode* BVHBuild::build_node(const BVHObjectBinning& range, int level)
float leafSAH = params.sah_primitive_cost * range.leafSAH;
float splitSAH = params.sah_node_cost * range.bounds().half_area() + params.sah_primitive_cost * range.splitSAH;
- /* have at least one inner node on top level, for performance and correct
- * visibility tests, since object instances do not check visibility flag */
+ /* Have at least one inner node on top level, for performance and correct
+ * visibility tests, since object instances do not check visibility flag.
+ */
if(!(range.size() > 0 && params.top_level && level == 0)) {
- /* make leaf node when threshold reached or SAH tells us */
+ /* Make leaf node when threshold reached or SAH tells us. */
if((params.small_enough_for_leaf(size, level)) ||
(range_within_max_leaf_size(range, references) && leafSAH < splitSAH))
{
@@ -447,28 +473,70 @@ BVHNode* BVHBuild::build_node(const BVHObjectBinning& range, int level)
}
}
- /* perform split */
+ BVHObjectBinning unaligned_range;
+ float unalignedSplitSAH = FLT_MAX;
+ float unalignedLeafSAH = FLT_MAX;
+ Transform aligned_space;
+ if(params.use_unaligned_nodes &&
+ splitSAH > params.unaligned_split_threshold*leafSAH)
+ {
+ aligned_space = unaligned_heuristic.compute_aligned_space(
+ range, &references[0]);
+ unaligned_range = BVHObjectBinning(range,
+ &references[0],
+ &unaligned_heuristic,
+ &aligned_space);
+ unalignedSplitSAH = params.sah_node_cost * unaligned_range.unaligned_bounds().half_area() +
+ params.sah_primitive_cost * unaligned_range.splitSAH;
+ unalignedLeafSAH = params.sah_primitive_cost * unaligned_range.leafSAH;
+ if(!(range.size() > 0 && params.top_level && level == 0)) {
+ if(unalignedLeafSAH < unalignedSplitSAH && unalignedSplitSAH < splitSAH &&
+ range_within_max_leaf_size(range, references))
+ {
+ return create_leaf_node(range, references);
+ }
+ }
+ }
+
+ /* Perform split. */
BVHObjectBinning left, right;
- range.split(&references[0], left, right);
+ if(unalignedSplitSAH < splitSAH) {
+ unaligned_range.split(&references[0], left, right);
+ }
+ else {
+ range.split(&references[0], left, right);
+ }
- /* create inner node. */
- InnerNode *inner;
+ BoundBox bounds;
+ if(unalignedSplitSAH < splitSAH) {
+ bounds = unaligned_heuristic.compute_aligned_boundbox(
+ range, &references[0], aligned_space);
+ }
+ else {
+ bounds = range.bounds();
+ }
+ /* Create inner node. */
+ InnerNode *inner;
if(range.size() < THREAD_TASK_SIZE) {
/* local build */
BVHNode *leftnode = build_node(left, level + 1);
BVHNode *rightnode = build_node(right, level + 1);
- inner = new InnerNode(range.bounds(), leftnode, rightnode);
+ inner = new InnerNode(bounds, leftnode, rightnode);
}
else {
- /* threaded build */
- inner = new InnerNode(range.bounds());
+ /* Threaded build */
+ inner = new InnerNode(bounds);
task_pool.push(new BVHBuildTask(this, inner, 0, left, level + 1), true);
task_pool.push(new BVHBuildTask(this, inner, 1, right, level + 1), true);
}
+ if(unalignedSplitSAH < splitSAH) {
+ inner->set_aligned_space(aligned_space);
+ }
+
return inner;
}
@@ -507,16 +575,54 @@ BVHNode* BVHBuild::build_node(const BVHRange& range,
return create_leaf_node(range, *references);
}
}
+ float leafSAH = params.sah_primitive_cost * split.leafSAH;
+ float splitSAH = params.sah_node_cost * range.bounds().half_area() +
+ params.sah_primitive_cost * split.nodeSAH;
+
+ BVHMixedSplit unaligned_split;
+ float unalignedSplitSAH = FLT_MAX;
+ /* float unalignedLeafSAH = FLT_MAX; */
+ Transform aligned_space;
+ if(params.use_unaligned_nodes &&
+ splitSAH > params.unaligned_split_threshold*leafSAH)
+ {
+ aligned_space =
+ unaligned_heuristic.compute_aligned_space(range, &references->at(0));
+ unaligned_split = BVHMixedSplit(this,
+ storage,
+ range,
+ references,
+ level,
+ &unaligned_heuristic,
+ &aligned_space);
+ /* unalignedLeafSAH = params.sah_primitive_cost * split.leafSAH; */
+ unalignedSplitSAH = params.sah_node_cost * unaligned_split.bounds.half_area() +
+ params.sah_primitive_cost * unaligned_split.nodeSAH;
+ /* TOOD(sergey): Check we can create leaf already. */
+ }
/* Do split. */
BVHRange left, right;
- split.split(this, left, right, range);
+ if(unalignedSplitSAH < splitSAH) {
+ unaligned_split.split(this, left, right, range);
+ }
+ else {
+ split.split(this, left, right, range);
+ }
progress_total += left.size() + right.size() - range.size();
+ BoundBox bounds;
+ if(unalignedSplitSAH < splitSAH) {
+ bounds = unaligned_heuristic.compute_aligned_boundbox(
+ range, &references->at(0), aligned_space);
+ }
+ else {
+ bounds = range.bounds();
+ }
+
/* Create inner node. */
InnerNode *inner;
-
if(range.size() < THREAD_TASK_SIZE) {
/* Local build. */
@@ -530,11 +636,11 @@ BVHNode* BVHBuild::build_node(const BVHRange& range,
/* Build right node. */
BVHNode *rightnode = build_node(right, &copy, level + 1, thread_id);
- inner = new InnerNode(range.bounds(), leftnode, rightnode);
+ inner = new InnerNode(bounds, leftnode, rightnode);
}
else {
/* Threaded build. */
- inner = new InnerNode(range.bounds());
+ inner = new InnerNode(bounds);
task_pool.push(new BVHSpatialSplitBuildTask(this,
inner,
0,
@@ -551,6 +657,10 @@ BVHNode* BVHBuild::build_node(const BVHRange& range,
true);
}
+ if(unalignedSplitSAH < splitSAH) {
+ inner->set_aligned_space(aligned_space);
+ }
+
return inner;
}
@@ -607,6 +717,7 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range,
vector<int, LeafStackAllocator> p_type[PRIMITIVE_NUM_TOTAL];
vector<int, LeafStackAllocator> p_index[PRIMITIVE_NUM_TOTAL];
vector<int, LeafStackAllocator> p_object[PRIMITIVE_NUM_TOTAL];
+ vector<BVHReference, LeafStackAllocator> p_ref[PRIMITIVE_NUM_TOTAL];
/* TODO(sergey): In theory we should be able to store references. */
typedef StackAllocator<256, BVHReference> LeafReferenceStackAllocator;
@@ -625,6 +736,7 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range,
const BVHReference& ref = references[range.start() + i];
if(ref.prim_index() != -1) {
int type_index = bitscan(ref.prim_type() & PRIMITIVE_ALL);
+ p_ref[type_index].push_back(ref);
p_type[type_index].push_back(ref.prim_type());
p_index[type_index].push_back(ref.prim_index());
p_object[type_index].push_back(ref.prim_object());
@@ -665,16 +777,38 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range,
if(num != 0) {
assert(p_type[i].size() == p_index[i].size());
assert(p_type[i].size() == p_object[i].size());
+ Transform aligned_space;
+ bool alignment_found = false;
for(int j = 0; j < num; ++j) {
const int index = start_index + j;
local_prim_type[index] = p_type[i][j];
local_prim_index[index] = p_index[i][j];
local_prim_object[index] = p_object[i][j];
+ if(params.use_unaligned_nodes && !alignment_found) {
+ alignment_found =
+ unaligned_heuristic.compute_aligned_space(p_ref[i][j],
+ &aligned_space);
+ }
+ }
+ LeafNode *leaf_node = new LeafNode(bounds[i],
+ visibility[i],
+ start_index,
+ start_index + num);
+ if(alignment_found) {
+ /* Need to recalculate leaf bounds with new alignment. */
+ leaf_node->m_bounds = BoundBox::empty;
+ for(int j = 0; j < num; ++j) {
+ const BVHReference &ref = p_ref[i][j];
+ BoundBox ref_bounds =
+ unaligned_heuristic.compute_aligned_prim_boundbox(
+ ref,
+ aligned_space);
+ leaf_node->m_bounds.grow(ref_bounds);
+ }
+ /* Set alignment space. */
+ leaf_node->set_aligned_space(aligned_space);
}
- leaves[num_leaves++] = new LeafNode(bounds[i],
- visibility[i],
- start_index,
- start_index + num);
+ leaves[num_leaves++] = leaf_node;
start_index += num;
}
}
@@ -756,6 +890,9 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range,
++num_leaves;
}
+ /* TODO(sergey): Need to take care of alignment when number of leaves
+ * is more than 1.
+ */
if(num_leaves == 1) {
/* Simplest case: single leaf, just return it.
* In all the rest cases we'll be creating intermediate inner node with
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-05 15:50:49 +0300