diff options
Diffstat (limited to 'intern/cycles/bvh/bvh.cpp')
| -rw-r--r-- | intern/cycles/bvh/bvh.cpp | 884 |
1 files changed, 34 insertions, 850 deletions
diff --git a/intern/cycles/bvh/bvh.cpp b/intern/cycles/bvh/bvh.cpp index 4851de5b481..0ad3c8a7429 100644 --- a/intern/cycles/bvh/bvh.cpp +++ b/intern/cycles/bvh/bvh.cpp @@ -15,45 +15,32 @@ * limitations under the License. */ -#include "mesh.h" -#include "object.h" -#include "scene.h" -#include "curves.h" - -#include "bvh.h" -#include "bvh_build.h" -#include "bvh_node.h" -#include "bvh_params.h" -#include "bvh_unaligned.h" - -#include "util_debug.h" -#include "util_foreach.h" -#include "util_logging.h" -#include "util_map.h" -#include "util_progress.h" -#include "util_system.h" -#include "util_types.h" -#include "util_math.h" +#include "bvh/bvh.h" + +#include "render/mesh.h" +#include "render/object.h" + +#include "bvh/bvh2.h" +#include "bvh/bvh4.h" +#include "bvh/bvh_build.h" +#include "bvh/bvh_node.h" + +#include "util/util_foreach.h" +#include "util/util_progress.h" CCL_NAMESPACE_BEGIN /* Pack Utility */ -struct BVHStackEntry +BVHStackEntry::BVHStackEntry(const BVHNode *n, int i) + : node(n), idx(i) { - const BVHNode *node; - int idx; - - BVHStackEntry(const BVHNode* n = 0, int i = 0) - : node(n), idx(i) - { - } +} - int encodeIdx() const - { - return (node->is_leaf())? ~idx: idx; - } -}; +int BVHStackEntry::encodeIdx() const +{ + return (node->is_leaf())? ~idx: idx; +} /* BVH */ @@ -65,9 +52,9 @@ BVH::BVH(const BVHParams& params_, const vector<Object*>& objects_) BVH *BVH::create(const BVHParams& params, const vector<Object*>& objects) { if(params.use_qbvh) - return new QBVH(params, objects); + return new BVH4(params, objects); else - return new RegularBVH(params, objects); + return new BVH2(params, objects); } /* Building */ @@ -81,6 +68,7 @@ void BVH::build(Progress& progress) pack.prim_type, pack.prim_index, pack.prim_object, + pack.prim_time, params, progress); BVHNode *root = bvh_build.run(); @@ -165,7 +153,6 @@ void BVH::pack_primitives() if(pack.prim_index[i] != -1) { int tob = pack.prim_object[i]; Object *ob = objects[tob]; - if((pack.prim_type[i] & PRIMITIVE_ALL_TRIANGLE) != 0) { pack_triangle(i, (float4*)&pack.prim_tri_verts[3 * prim_triangle_index]); pack.prim_tri_index[i] = 3 * prim_triangle_index; @@ -174,11 +161,10 @@ void BVH::pack_primitives() else { pack.prim_tri_index[i] = -1; } - - pack.prim_visibility[i] = ob->visibility; - - if(pack.prim_type[i] & PRIMITIVE_ALL_CURVE) + pack.prim_visibility[i] = ob->visibility_for_tracing(); + if(pack.prim_type[i] & PRIMITIVE_ALL_CURVE) { pack.prim_visibility[i] |= PATH_RAY_CURVE; + } } else { pack.prim_tri_index[i] = -1; @@ -256,6 +242,10 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size) pack.leaf_nodes.resize(leaf_nodes_size); pack.object_node.resize(objects.size()); + if(params.num_motion_curve_steps > 0 || params.num_motion_triangle_steps > 0) { + pack.prim_time.resize(prim_index_size); + } + int *pack_prim_index = (pack.prim_index.size())? &pack.prim_index[0]: NULL; int *pack_prim_type = (pack.prim_type.size())? &pack.prim_type[0]: NULL; int *pack_prim_object = (pack.prim_object.size())? &pack.prim_object[0]: NULL; @@ -264,6 +254,7 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size) uint *pack_prim_tri_index = (pack.prim_tri_index.size())? &pack.prim_tri_index[0]: NULL; int4 *pack_nodes = (pack.nodes.size())? &pack.nodes[0]: NULL; int4 *pack_leaf_nodes = (pack.leaf_nodes.size())? &pack.leaf_nodes[0]: NULL; + float2 *pack_prim_time = (pack.prim_time.size())? &pack.prim_time[0]: NULL; /* merge */ foreach(Object *ob, objects) { @@ -309,6 +300,7 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size) int *bvh_prim_type = &bvh->pack.prim_type[0]; uint *bvh_prim_visibility = &bvh->pack.prim_visibility[0]; uint *bvh_prim_tri_index = &bvh->pack.prim_tri_index[0]; + float2 *bvh_prim_time = bvh->pack.prim_time.size()? &bvh->pack.prim_time[0]: NULL; for(size_t i = 0; i < bvh_prim_index_size; i++) { if(bvh->pack.prim_type[i] & PRIMITIVE_ALL_CURVE) { @@ -324,6 +316,9 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size) pack_prim_type[pack_prim_index_offset] = bvh_prim_type[i]; pack_prim_visibility[pack_prim_index_offset] = bvh_prim_visibility[i]; pack_prim_object[pack_prim_index_offset] = 0; // unused for instances + if(bvh_prim_time != NULL) { + pack_prim_time[pack_prim_index_offset] = bvh_prim_time[i]; + } pack_prim_index_offset++; } } @@ -408,815 +403,4 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size) } } -/* Regular BVH */ - -static bool node_bvh_is_unaligned(const BVHNode *node) -{ - const BVHNode *node0 = node->get_child(0), - *node1 = node->get_child(1); - return node0->is_unaligned() || node1->is_unaligned(); -} - -RegularBVH::RegularBVH(const BVHParams& params_, const vector<Object*>& objects_) -: BVH(params_, objects_) -{ -} - -void RegularBVH::pack_leaf(const BVHStackEntry& e, - const LeafNode *leaf) -{ - assert(e.idx + BVH_NODE_LEAF_SIZE <= pack.leaf_nodes.size()); - float4 data[BVH_NODE_LEAF_SIZE]; - memset(data, 0, sizeof(data)); - if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) { - /* object */ - data[0].x = __int_as_float(~(leaf->m_lo)); - data[0].y = __int_as_float(0); - } - else { - /* triangle */ - data[0].x = __int_as_float(leaf->m_lo); - data[0].y = __int_as_float(leaf->m_hi); - } - data[0].z = __uint_as_float(leaf->m_visibility); - if(leaf->num_triangles() != 0) { - data[0].w = __uint_as_float(pack.prim_type[leaf->m_lo]); - } - - memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_NODE_LEAF_SIZE); -} - -void RegularBVH::pack_inner(const BVHStackEntry& e, - const BVHStackEntry& e0, - const BVHStackEntry& e1) -{ - if(e0.node->is_unaligned() || e1.node->is_unaligned()) { - pack_unaligned_inner(e, e0, e1); - } else { - pack_aligned_inner(e, e0, e1); - } -} - -void RegularBVH::pack_aligned_inner(const BVHStackEntry& e, - const BVHStackEntry& e0, - const BVHStackEntry& e1) -{ - pack_aligned_node(e.idx, - e0.node->m_bounds, e1.node->m_bounds, - e0.encodeIdx(), e1.encodeIdx(), - e0.node->m_visibility, e1.node->m_visibility); -} - -void RegularBVH::pack_aligned_node(int idx, - const BoundBox& b0, - const BoundBox& b1, - int c0, int c1, - uint visibility0, uint visibility1) -{ - assert(idx + BVH_NODE_SIZE <= pack.nodes.size()); - assert(c0 < 0 || c0 < pack.nodes.size()); - assert(c1 < 0 || c1 < pack.nodes.size()); - - int4 data[BVH_NODE_SIZE] = { - make_int4(visibility0 & ~PATH_RAY_NODE_UNALIGNED, - visibility1 & ~PATH_RAY_NODE_UNALIGNED, - c0, c1), - make_int4(__float_as_int(b0.min.x), - __float_as_int(b1.min.x), - __float_as_int(b0.max.x), - __float_as_int(b1.max.x)), - make_int4(__float_as_int(b0.min.y), - __float_as_int(b1.min.y), - __float_as_int(b0.max.y), - __float_as_int(b1.max.y)), - make_int4(__float_as_int(b0.min.z), - __float_as_int(b1.min.z), - __float_as_int(b0.max.z), - __float_as_int(b1.max.z)), - }; - - memcpy(&pack.nodes[idx], data, sizeof(int4)*BVH_NODE_SIZE); -} - -void RegularBVH::pack_unaligned_inner(const BVHStackEntry& e, - const BVHStackEntry& e0, - const BVHStackEntry& e1) -{ - pack_unaligned_node(e.idx, - e0.node->get_aligned_space(), - e1.node->get_aligned_space(), - e0.node->m_bounds, - e1.node->m_bounds, - e0.encodeIdx(), e1.encodeIdx(), - e0.node->m_visibility, e1.node->m_visibility); -} - -void RegularBVH::pack_unaligned_node(int idx, - const Transform& aligned_space0, - const Transform& aligned_space1, - const BoundBox& bounds0, - const BoundBox& bounds1, - int c0, int c1, - uint visibility0, uint visibility1) -{ - assert(idx + BVH_UNALIGNED_NODE_SIZE <= pack.nodes.size()); - assert(c0 < 0 || c0 < pack.nodes.size()); - assert(c1 < 0 || c1 < pack.nodes.size()); - - float4 data[BVH_UNALIGNED_NODE_SIZE]; - Transform space0 = BVHUnaligned::compute_node_transform(bounds0, - aligned_space0); - Transform space1 = BVHUnaligned::compute_node_transform(bounds1, - aligned_space1); - data[0] = make_float4(__int_as_float(visibility0 | PATH_RAY_NODE_UNALIGNED), - __int_as_float(visibility1 | PATH_RAY_NODE_UNALIGNED), - __int_as_float(c0), - __int_as_float(c1)); - - data[1] = space0.x; - data[2] = space0.y; - data[3] = space0.z; - data[4] = space1.x; - data[5] = space1.y; - data[6] = space1.z; - - memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_UNALIGNED_NODE_SIZE); -} - -void RegularBVH::pack_nodes(const BVHNode *root) -{ - const size_t num_nodes = root->getSubtreeSize(BVH_STAT_NODE_COUNT); - const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT); - assert(num_leaf_nodes <= num_nodes); - const size_t num_inner_nodes = num_nodes - num_leaf_nodes; - size_t node_size; - if(params.use_unaligned_nodes) { - const size_t num_unaligned_nodes = - root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT); - node_size = (num_unaligned_nodes * BVH_UNALIGNED_NODE_SIZE) + - (num_inner_nodes - num_unaligned_nodes) * BVH_NODE_SIZE; - } - else { - node_size = num_inner_nodes * BVH_NODE_SIZE; - } - /* Resize arrays */ - pack.nodes.clear(); - pack.leaf_nodes.clear(); - /* For top level BVH, first merge existing BVH's so we know the offsets. */ - if(params.top_level) { - pack_instances(node_size, num_leaf_nodes*BVH_NODE_LEAF_SIZE); - } - else { - pack.nodes.resize(node_size); - pack.leaf_nodes.resize(num_leaf_nodes*BVH_NODE_LEAF_SIZE); - } - - int nextNodeIdx = 0, nextLeafNodeIdx = 0; - - vector<BVHStackEntry> stack; - stack.reserve(BVHParams::MAX_DEPTH*2); - if(root->is_leaf()) { - stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++)); - } - else { - stack.push_back(BVHStackEntry(root, nextNodeIdx)); - nextNodeIdx += node_bvh_is_unaligned(root) - ? BVH_UNALIGNED_NODE_SIZE - : BVH_NODE_SIZE; - } - - while(stack.size()) { - BVHStackEntry e = stack.back(); - stack.pop_back(); - - if(e.node->is_leaf()) { - /* leaf node */ - const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node); - pack_leaf(e, leaf); - } - else { - /* innner node */ - int idx[2]; - for(int i = 0; i < 2; ++i) { - if(e.node->get_child(i)->is_leaf()) { - idx[i] = nextLeafNodeIdx++; - } - else { - idx[i] = nextNodeIdx; - nextNodeIdx += node_bvh_is_unaligned(e.node->get_child(i)) - ? BVH_UNALIGNED_NODE_SIZE - : BVH_NODE_SIZE; - } - } - - stack.push_back(BVHStackEntry(e.node->get_child(0), idx[0])); - stack.push_back(BVHStackEntry(e.node->get_child(1), idx[1])); - - pack_inner(e, stack[stack.size()-2], stack[stack.size()-1]); - } - } - assert(node_size == nextNodeIdx); - /* root index to start traversal at, to handle case of single leaf node */ - pack.root_index = (root->is_leaf())? -1: 0; -} - -void RegularBVH::refit_nodes() -{ - assert(!params.top_level); - - BoundBox bbox = BoundBox::empty; - uint visibility = 0; - refit_node(0, (pack.root_index == -1)? true: false, bbox, visibility); -} - -void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility) -{ - if(leaf) { - assert(idx + BVH_NODE_LEAF_SIZE <= pack.leaf_nodes.size()); - const int4 *data = &pack.leaf_nodes[idx]; - const int c0 = data[0].x; - const int c1 = data[0].y; - /* refit leaf node */ - for(int prim = c0; prim < c1; prim++) { - int pidx = pack.prim_index[prim]; - int tob = pack.prim_object[prim]; - Object *ob = objects[tob]; - - if(pidx == -1) { - /* object instance */ - bbox.grow(ob->bounds); - } - else { - /* primitives */ - const Mesh *mesh = ob->mesh; - - if(pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) { - /* curves */ - int str_offset = (params.top_level)? mesh->curve_offset: 0; - Mesh::Curve curve = mesh->get_curve(pidx - str_offset); - int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]); - - curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bbox); - - visibility |= PATH_RAY_CURVE; - - /* motion curves */ - if(mesh->use_motion_blur) { - Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION); - - if(attr) { - size_t mesh_size = mesh->curve_keys.size(); - size_t steps = mesh->motion_steps - 1; - float3 *key_steps = attr->data_float3(); - - for(size_t i = 0; i < steps; i++) - curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bbox); - } - } - } - else { - /* triangles */ - int tri_offset = (params.top_level)? mesh->tri_offset: 0; - Mesh::Triangle triangle = mesh->get_triangle(pidx - tri_offset); - const float3 *vpos = &mesh->verts[0]; - - triangle.bounds_grow(vpos, bbox); - - /* motion triangles */ - if(mesh->use_motion_blur) { - Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION); - - if(attr) { - size_t mesh_size = mesh->verts.size(); - size_t steps = mesh->motion_steps - 1; - float3 *vert_steps = attr->data_float3(); - - for(size_t i = 0; i < steps; i++) - triangle.bounds_grow(vert_steps + i*mesh_size, bbox); - } - } - } - } - - visibility |= ob->visibility; - } - - /* TODO(sergey): De-duplicate with pack_leaf(). */ - float4 leaf_data[BVH_NODE_LEAF_SIZE]; - leaf_data[0].x = __int_as_float(c0); - leaf_data[0].y = __int_as_float(c1); - leaf_data[0].z = __uint_as_float(visibility); - leaf_data[0].w = __uint_as_float(data[0].w); - memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_NODE_LEAF_SIZE); - } - else { - assert(idx + BVH_NODE_SIZE <= pack.nodes.size()); - - const int4 *data = &pack.nodes[idx]; - const bool is_unaligned = (data[0].x & PATH_RAY_NODE_UNALIGNED) != 0; - const int c0 = data[0].z; - const int c1 = data[0].w; - /* refit inner node, set bbox from children */ - BoundBox bbox0 = BoundBox::empty, bbox1 = BoundBox::empty; - uint visibility0 = 0, visibility1 = 0; - - refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0); - refit_node((c1 < 0)? -c1-1: c1, (c1 < 0), bbox1, visibility1); - - if(is_unaligned) { - Transform aligned_space = transform_identity(); - pack_unaligned_node(idx, - aligned_space, aligned_space, - bbox0, bbox1, - c0, c1, - visibility0, - visibility1); - } - else { - pack_aligned_node(idx, - bbox0, bbox1, - c0, c1, - visibility0, - visibility1); - } - - bbox.grow(bbox0); - bbox.grow(bbox1); - visibility = visibility0|visibility1; - } -} - -/* QBVH */ - -/* Can we avoid this somehow or make more generic? - * - * Perhaps we can merge nodes in actual tree and make our - * life easier all over the place. - */ -static bool node_qbvh_is_unaligned(const BVHNode *node) -{ - const BVHNode *node0 = node->get_child(0), - *node1 = node->get_child(1); - bool has_unaligned = false; - if(node0->is_leaf()) { - has_unaligned |= node0->is_unaligned(); - } - else { - has_unaligned |= node0->get_child(0)->is_unaligned(); - has_unaligned |= node0->get_child(1)->is_unaligned(); - } - if(node1->is_leaf()) { - has_unaligned |= node1->is_unaligned(); - } - else { - has_unaligned |= node1->get_child(0)->is_unaligned(); - has_unaligned |= node1->get_child(1)->is_unaligned(); - } - return has_unaligned; -} - -QBVH::QBVH(const BVHParams& params_, const vector<Object*>& objects_) -: BVH(params_, objects_) -{ - params.use_qbvh = true; -} - -void QBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf) -{ - float4 data[BVH_QNODE_LEAF_SIZE]; - memset(data, 0, sizeof(data)); - if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) { - /* object */ - data[0].x = __int_as_float(~(leaf->m_lo)); - data[0].y = __int_as_float(0); - } - else { - /* triangle */ - data[0].x = __int_as_float(leaf->m_lo); - data[0].y = __int_as_float(leaf->m_hi); - } - data[0].z = __uint_as_float(leaf->m_visibility); - if(leaf->num_triangles() != 0) { - data[0].w = __uint_as_float(pack.prim_type[leaf->m_lo]); - } - - memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_QNODE_LEAF_SIZE); -} - -void QBVH::pack_inner(const BVHStackEntry& e, - const BVHStackEntry *en, - int num) -{ - bool has_unaligned = false; - /* Check whether we have to create unaligned node or all nodes are aligned - * and we can cut some corner here. - */ - if(params.use_unaligned_nodes) { - for(int i = 0; i < num; i++) { - if(en[i].node->is_unaligned()) { - has_unaligned = true; - break; - } - } - } - if(has_unaligned) { - /* There's no unaligned children, pack into AABB node. */ - pack_unaligned_inner(e, en, num); - } - else { - /* Create unaligned node with orientation transform for each of the - * children. - */ - pack_aligned_inner(e, en, num); - } -} - -void QBVH::pack_aligned_inner(const BVHStackEntry& e, - const BVHStackEntry *en, - int num) -{ - BoundBox bounds[4]; - int child[4]; - for(int i = 0; i < num; ++i) { - bounds[i] = en[i].node->m_bounds; - child[i] = en[i].encodeIdx(); - } - pack_aligned_node(e.idx, - bounds, - child, - e.node->m_visibility, - num); -} - -void QBVH::pack_aligned_node(int idx, - const BoundBox *bounds, - const int *child, - const uint visibility, - const int num) -{ - float4 data[BVH_QNODE_SIZE]; - memset(data, 0, sizeof(data)); - - data[0].x = __uint_as_float(visibility & ~PATH_RAY_NODE_UNALIGNED); - for(int i = 0; i < num; i++) { - float3 bb_min = bounds[i].min; - float3 bb_max = bounds[i].max; - - data[1][i] = bb_min.x; - data[2][i] = bb_max.x; - data[3][i] = bb_min.y; - data[4][i] = bb_max.y; - data[5][i] = bb_min.z; - data[6][i] = bb_max.z; - - data[7][i] = __int_as_float(child[i]); - } - - for(int i = num; i < 4; i++) { - /* We store BB which would never be recorded as intersection - * so kernel might safely assume there are always 4 child nodes. - */ - data[1][i] = FLT_MAX; - data[2][i] = -FLT_MAX; - - data[3][i] = FLT_MAX; - data[4][i] = -FLT_MAX; - - data[5][i] = FLT_MAX; - data[6][i] = -FLT_MAX; - - data[7][i] = __int_as_float(0); - } - - memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_QNODE_SIZE); -} - -void QBVH::pack_unaligned_inner(const BVHStackEntry& e, - const BVHStackEntry *en, - int num) -{ - Transform aligned_space[4]; - BoundBox bounds[4]; - int child[4]; - for(int i = 0; i < num; ++i) { - aligned_space[i] = en[i].node->get_aligned_space(); - bounds[i] = en[i].node->m_bounds; - child[i] = en[i].encodeIdx(); - } - pack_unaligned_node(e.idx, - aligned_space, - bounds, - child, - e.node->m_visibility, - num); -} - -void QBVH::pack_unaligned_node(int idx, - const Transform *aligned_space, - const BoundBox *bounds, - const int *child, - const uint visibility, - const int num) -{ - float4 data[BVH_UNALIGNED_QNODE_SIZE]; - memset(data, 0, sizeof(data)); - - data[0].x = __uint_as_float(visibility | PATH_RAY_NODE_UNALIGNED); - - for(int i = 0; i < num; i++) { - Transform space = BVHUnaligned::compute_node_transform( - bounds[i], - aligned_space[i]); - - data[1][i] = space.x.x; - data[2][i] = space.x.y; - data[3][i] = space.x.z; - - data[4][i] = space.y.x; - data[5][i] = space.y.y; - data[6][i] = space.y.z; - - data[7][i] = space.z.x; - data[8][i] = space.z.y; - data[9][i] = space.z.z; - - data[10][i] = space.x.w; - data[11][i] = space.y.w; - data[12][i] = space.z.w; - - data[13][i] = __int_as_float(child[i]); - } - - for(int i = num; i < 4; i++) { - /* We store BB which would never be recorded as intersection - * so kernel might safely assume there are always 4 child nodes. - */ - - data[1][i] = 1.0f; - data[2][i] = 0.0f; - data[3][i] = 0.0f; - - data[4][i] = 0.0f; - data[5][i] = 0.0f; - data[6][i] = 0.0f; - - data[7][i] = 0.0f; - data[8][i] = 0.0f; - data[9][i] = 0.0f; - - data[10][i] = -FLT_MAX; - data[11][i] = -FLT_MAX; - data[12][i] = -FLT_MAX; - - data[13][i] = __int_as_float(0); - } - - memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_UNALIGNED_QNODE_SIZE); -} - -/* Quad SIMD Nodes */ - -void QBVH::pack_nodes(const BVHNode *root) -{ - /* Calculate size of the arrays required. */ - const size_t num_nodes = root->getSubtreeSize(BVH_STAT_QNODE_COUNT); - const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT); - assert(num_leaf_nodes <= num_nodes); - const size_t num_inner_nodes = num_nodes - num_leaf_nodes; - size_t node_size; - if(params.use_unaligned_nodes) { - const size_t num_unaligned_nodes = - root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_QNODE_COUNT); - node_size = (num_unaligned_nodes * BVH_UNALIGNED_QNODE_SIZE) + - (num_inner_nodes - num_unaligned_nodes) * BVH_QNODE_SIZE; - } - else { - node_size = num_inner_nodes * BVH_QNODE_SIZE; - } - /* Resize arrays. */ - pack.nodes.clear(); - pack.leaf_nodes.clear(); - /* For top level BVH, first merge existing BVH's so we know the offsets. */ - if(params.top_level) { - pack_instances(node_size, num_leaf_nodes*BVH_QNODE_LEAF_SIZE); - } - else { - pack.nodes.resize(node_size); - pack.leaf_nodes.resize(num_leaf_nodes*BVH_QNODE_LEAF_SIZE); - } - - int nextNodeIdx = 0, nextLeafNodeIdx = 0; - - vector<BVHStackEntry> stack; - stack.reserve(BVHParams::MAX_DEPTH*2); - if(root->is_leaf()) { - stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++)); - } - else { - stack.push_back(BVHStackEntry(root, nextNodeIdx)); - nextNodeIdx += node_qbvh_is_unaligned(root) - ? BVH_UNALIGNED_QNODE_SIZE - : BVH_QNODE_SIZE; - } - - while(stack.size()) { - BVHStackEntry e = stack.back(); - stack.pop_back(); - - if(e.node->is_leaf()) { - /* leaf node */ - const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node); - pack_leaf(e, leaf); - } - else { - /* Inner node. */ - const BVHNode *node = e.node; - const BVHNode *node0 = node->get_child(0); - const BVHNode *node1 = node->get_child(1); - /* Collect nodes. */ - const BVHNode *nodes[4]; - int numnodes = 0; - if(node0->is_leaf()) { - nodes[numnodes++] = node0; - } - else { - nodes[numnodes++] = node0->get_child(0); - nodes[numnodes++] = node0->get_child(1); - } - if(node1->is_leaf()) { - nodes[numnodes++] = node1; - } - else { - nodes[numnodes++] = node1->get_child(0); - nodes[numnodes++] = node1->get_child(1); - } - /* Push entries on the stack. */ - for(int i = 0; i < numnodes; ++i) { - int idx; - if(nodes[i]->is_leaf()) { - idx = nextLeafNodeIdx++; - } - else { - idx = nextNodeIdx; - nextNodeIdx += node_qbvh_is_unaligned(nodes[i]) - ? BVH_UNALIGNED_QNODE_SIZE - : BVH_QNODE_SIZE; - } - stack.push_back(BVHStackEntry(nodes[i], idx)); - } - /* Set node. */ - pack_inner(e, &stack[stack.size()-numnodes], numnodes); - } - } - assert(node_size == nextNodeIdx); - /* Root index to start traversal at, to handle case of single leaf node. */ - pack.root_index = (root->is_leaf())? -1: 0; -} - -void QBVH::refit_nodes() -{ - assert(!params.top_level); - - BoundBox bbox = BoundBox::empty; - uint visibility = 0; - refit_node(0, (pack.root_index == -1)? true: false, bbox, visibility); -} - -void QBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility) -{ - if(leaf) { - int4 *data = &pack.leaf_nodes[idx]; - int4 c = data[0]; - /* Refit leaf node. */ - for(int prim = c.x; prim < c.y; prim++) { - int pidx = pack.prim_index[prim]; - int tob = pack.prim_object[prim]; - Object *ob = objects[tob]; - - if(pidx == -1) { - /* Object instance. */ - bbox.grow(ob->bounds); - } - else { - /* Primitives. */ - const Mesh *mesh = ob->mesh; - - if(pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) { - /* Curves. */ - int str_offset = (params.top_level)? mesh->curve_offset: 0; - Mesh::Curve curve = mesh->get_curve(pidx - str_offset); - int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]); - - curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bbox); - - visibility |= PATH_RAY_CURVE; - - /* Motion curves. */ - if(mesh->use_motion_blur) { - Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION); - - if(attr) { - size_t mesh_size = mesh->curve_keys.size(); - size_t steps = mesh->motion_steps - 1; - float3 *key_steps = attr->data_float3(); - - for(size_t i = 0; i < steps; i++) - curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bbox); - } - } - } - else { - /* Triangles. */ - int tri_offset = (params.top_level)? mesh->tri_offset: 0; - Mesh::Triangle triangle = mesh->get_triangle(pidx - tri_offset); - const float3 *vpos = &mesh->verts[0]; - - triangle.bounds_grow(vpos, bbox); - - /* Motion triangles. */ - if(mesh->use_motion_blur) { - Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION); - - if(attr) { - size_t mesh_size = mesh->verts.size(); - size_t steps = mesh->motion_steps - 1; - float3 *vert_steps = attr->data_float3(); - - for(size_t i = 0; i < steps; i++) - triangle.bounds_grow(vert_steps + i*mesh_size, bbox); - } - } - } - } - - visibility |= ob->visibility; - } - - /* TODO(sergey): This is actually a copy of pack_leaf(), - * but this chunk of code only knows actual data and has - * no idea about BVHNode. - * - * Would be nice to de-duplicate code, but trying to make - * making code more general ends up in much nastier code - * in my opinion so far. - * - * Same applies to the inner nodes case below. - */ - float4 leaf_data[BVH_QNODE_LEAF_SIZE]; - leaf_data[0].x = __int_as_float(c.x); - leaf_data[0].y = __int_as_float(c.y); - leaf_data[0].z = __uint_as_float(visibility); - leaf_data[0].w = __uint_as_float(c.w); - memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_QNODE_LEAF_SIZE); - } - else { - int4 *data = &pack.nodes[idx]; - bool is_unaligned = (data[0].x & PATH_RAY_NODE_UNALIGNED) != 0; - int4 c; - if(is_unaligned) { - c = data[13]; - } - else { - c = data[7]; - } - /* Refit inner node, set bbox from children. */ - BoundBox child_bbox[4] = {BoundBox::empty, - BoundBox::empty, - BoundBox::empty, - BoundBox::empty}; - uint child_visibility[4] = {0}; - int num_nodes = 0; - - for(int i = 0; i < 4; ++i) { - if(c[i] != 0) { - refit_node((c[i] < 0)? -c[i]-1: c[i], (c[i] < 0), - child_bbox[i], child_visibility[i]); - ++num_nodes; - bbox.grow(child_bbox[i]); - visibility |= child_visibility[i]; - } - } - - if(is_unaligned) { - Transform aligned_space[4] = {transform_identity(), - transform_identity(), - transform_identity(), - transform_identity()}; - pack_unaligned_node(idx, - aligned_space, - child_bbox, - &c[0], - visibility, - 4); - } - else { - pack_aligned_node(idx, - child_bbox, - &c[0], - visibility, - 4); - } - } -} - CCL_NAMESPACE_END |