diff options
Diffstat (limited to 'intern/cycles/bvh/bvh_build.cpp')
-rw-r--r-- | intern/cycles/bvh/bvh_build.cpp | 270 |
1 files changed, 199 insertions, 71 deletions
diff --git a/intern/cycles/bvh/bvh_build.cpp b/intern/cycles/bvh/bvh_build.cpp index 3f687224eee..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,70 +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; - 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; + 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); - 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; + 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], &mesh->curve_radius[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; - float3 *key_steps = curve_attr_mP->data_float3(); + /* 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, &mesh->curve_radius[0], 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()); + } } } } @@ -209,15 +215,23 @@ void BVHBuild::add_references(BVHRange& root) continue; } if(!ob->mesh->is_instanced()) { - num_alloc_references += ob->mesh->num_triangles(); - 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->num_triangles(); - 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); + } } } @@ -340,6 +354,8 @@ BVHNode* BVHBuild::run() << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_INNER_COUNT)) << "\n" << " Number of leaf nodes: " << 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() @@ -445,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)) { @@ -456,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; } @@ -516,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. */ @@ -539,11 +636,11 @@ BVHNode* BVHBuild::build_node(const BVHRange& range, /* Build right node. */ BVHNode *rightnode = build_node(right, ©, 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, @@ -560,6 +657,10 @@ BVHNode* BVHBuild::build_node(const BVHRange& range, true); } + if(unalignedSplitSAH < splitSAH) { + inner->set_aligned_space(aligned_space); + } + return inner; } @@ -616,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; @@ -634,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()); @@ -674,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; } } @@ -765,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 |