diff options
| -rw-r--r-- | intern/cycles/bvh/CMakeLists.txt | 4 | ||||
| -rw-r--r-- | intern/cycles/bvh/bvh.cpp | 863 | ||||
| -rw-r--r-- | intern/cycles/bvh/bvh.h | 106 | ||||
| -rw-r--r-- | intern/cycles/bvh/bvh2.cpp | 364 | ||||
| -rw-r--r-- | intern/cycles/bvh/bvh2.h | 87 | ||||
| -rw-r--r-- | intern/cycles/bvh/bvh4.cpp | 516 | ||||
| -rw-r--r-- | intern/cycles/bvh/bvh4.h | 88 |
7 files changed, 1080 insertions, 948 deletions
diff --git a/intern/cycles/bvh/CMakeLists.txt b/intern/cycles/bvh/CMakeLists.txt index 4701d75350a..6078db5a8ca 100644 --- a/intern/cycles/bvh/CMakeLists.txt +++ b/intern/cycles/bvh/CMakeLists.txt @@ -8,6 +8,8 @@ set(INC_SYS set(SRC bvh.cpp + bvh2.cpp + bvh4.cpp bvh_binning.cpp bvh_build.cpp bvh_node.cpp @@ -18,6 +20,8 @@ set(SRC set(SRC_HEADERS bvh.h + bvh2.h + bvh4.h bvh_binning.h bvh_build.h bvh_node.h diff --git a/intern/cycles/bvh/bvh.cpp b/intern/cycles/bvh/bvh.cpp index 6a9aa2aafdb..33143e2d8aa 100644 --- a/intern/cycles/bvh/bvh.cpp +++ b/intern/cycles/bvh/bvh.cpp @@ -15,45 +15,32 @@ * limitations under the License. */ +#include "bvh/bvh.h" + #include "render/mesh.h" #include "render/object.h" -#include "render/scene.h" -#include "render/curves.h" -#include "bvh/bvh.h" +#include "bvh/bvh2.h" +#include "bvh/bvh4.h" #include "bvh/bvh_build.h" #include "bvh/bvh_node.h" -#include "bvh/bvh_params.h" -#include "bvh/bvh_unaligned.h" -#include "util/util_debug.h" #include "util/util_foreach.h" -#include "util/util_logging.h" -#include "util/util_map.h" #include "util/util_progress.h" -#include "util/util_system.h" -#include "util/util_types.h" -#include "util/util_math.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 */ @@ -418,832 +405,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; -} - -BVH2::BVH2(const BVHParams& params_, const vector<Object*>& objects_) -: BVH(params_, objects_) -{ -} - -void BVH2::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->lo] == -1) { - /* object */ - data[0].x = __int_as_float(~(leaf->lo)); - data[0].y = __int_as_float(0); - } - else { - /* triangle */ - data[0].x = __int_as_float(leaf->lo); - data[0].y = __int_as_float(leaf->hi); - } - data[0].z = __uint_as_float(leaf->visibility); - if(leaf->num_triangles() != 0) { - data[0].w = __uint_as_float(pack.prim_type[leaf->lo]); - } - - memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_NODE_LEAF_SIZE); -} - -void BVH2::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 BVH2::pack_aligned_inner(const BVHStackEntry& e, - const BVHStackEntry& e0, - const BVHStackEntry& e1) -{ - pack_aligned_node(e.idx, - e0.node->bounds, e1.node->bounds, - e0.encodeIdx(), e1.encodeIdx(), - e0.node->visibility, e1.node->visibility); -} - -void BVH2::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 BVH2::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->bounds, - e1.node->bounds, - e0.encodeIdx(), e1.encodeIdx(), - e0.node->visibility, e1.node->visibility); -} - -void BVH2::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 BVH2::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 BVH2::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 BVH2::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; - } -} - -/* BVH4 */ - -/* 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; -} - -BVH4::BVH4(const BVHParams& params_, const vector<Object*>& objects_) -: BVH(params_, objects_) -{ - params.use_qbvh = true; -} - -void BVH4::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->lo] == -1) { - /* object */ - data[0].x = __int_as_float(~(leaf->lo)); - data[0].y = __int_as_float(0); - } - else { - /* triangle */ - data[0].x = __int_as_float(leaf->lo); - data[0].y = __int_as_float(leaf->hi); - } - data[0].z = __uint_as_float(leaf->visibility); - if(leaf->num_triangles() != 0) { - data[0].w = __uint_as_float(pack.prim_type[leaf->lo]); - } - - memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_QNODE_LEAF_SIZE); -} - -void BVH4::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 BVH4::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->bounds; - child[i] = en[i].encodeIdx(); - } - pack_aligned_node(e.idx, - bounds, - child, - e.node->visibility, - e.node->time_from, - e.node->time_to, - num); -} - -void BVH4::pack_aligned_node(int idx, - const BoundBox *bounds, - const int *child, - const uint visibility, - const float time_from, - const float time_to, - const int num) -{ - float4 data[BVH_QNODE_SIZE]; - memset(data, 0, sizeof(data)); - - data[0].x = __uint_as_float(visibility & ~PATH_RAY_NODE_UNALIGNED); - data[0].y = time_from; - data[0].z = time_to; - - 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 BVH4::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->bounds; - child[i] = en[i].encodeIdx(); - } - pack_unaligned_node(e.idx, - aligned_space, - bounds, - child, - e.node->visibility, - e.node->time_from, - e.node->time_to, - num); -} - -void BVH4::pack_unaligned_node(int idx, - const Transform *aligned_space, - const BoundBox *bounds, - const int *child, - const uint visibility, - const float time_from, - const float time_to, - 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); - data[0].y = time_from; - data[0].z = time_to; - - 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 BVH4::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 BVH4::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 BVH4::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, - 0.0f, - 1.0f, - 4); - } - else { - pack_aligned_node(idx, - child_bbox, - &c[0], - visibility, - 0.0f, - 1.0f, - 4); - } - } -} - CCL_NAMESPACE_END diff --git a/intern/cycles/bvh/bvh.h b/intern/cycles/bvh/bvh.h index 8e664e67dc5..7bac6112fd9 100644 --- a/intern/cycles/bvh/bvh.h +++ b/intern/cycles/bvh/bvh.h @@ -33,15 +33,8 @@ class LeafNode; class Object; class Progress; -#define BVH_NODE_SIZE 4 -#define BVH_NODE_LEAF_SIZE 1 -#define BVH_QNODE_SIZE 8 -#define BVH_QNODE_LEAF_SIZE 1 -#define BVH_ALIGN 4096 -#define TRI_NODE_SIZE 3 - -#define BVH_UNALIGNED_NODE_SIZE 7 -#define BVH_UNALIGNED_QNODE_SIZE 14 +#define BVH_ALIGN 4096 +#define TRI_NODE_SIZE 3 /* Packed BVH * @@ -54,7 +47,7 @@ struct PackedBVH { /* BVH leaf nodes storage. */ array<int4> leaf_nodes; /* object index to BVH node index mapping for instances */ - array<int> object_node; + array<int> object_node; /* Mapping from primitive index to index in triangle array. */ array<uint> prim_tri_index; /* Continuous storage of triangle vertices. */ @@ -110,95 +103,16 @@ protected: virtual void refit_nodes() = 0; }; -/* BVH2 - * - * Typical BVH with each node having two children. */ - -class BVH2 : public BVH { -protected: - /* constructor */ - friend class BVH; - BVH2(const BVHParams& params, const vector<Object*>& objects); - - /* pack */ - void pack_nodes(const BVHNode *root); - - void pack_leaf(const BVHStackEntry& e, - const LeafNode *leaf); - void pack_inner(const BVHStackEntry& e, - const BVHStackEntry& e0, - const BVHStackEntry& e1); - - void pack_aligned_inner(const BVHStackEntry& e, - const BVHStackEntry& e0, - const BVHStackEntry& e1); - void pack_aligned_node(int idx, - const BoundBox& b0, - const BoundBox& b1, - int c0, int c1, - uint visibility0, uint visibility1); - - void pack_unaligned_inner(const BVHStackEntry& e, - const BVHStackEntry& e0, - const BVHStackEntry& e1); - void pack_unaligned_node(int idx, - const Transform& aligned_space0, - const Transform& aligned_space1, - const BoundBox& b0, - const BoundBox& b1, - int c0, int c1, - uint visibility0, uint visibility1); - - /* refit */ - void refit_nodes(); - void refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility); -}; - -/* BVH4 - * - * Quad BVH, with each node having four children, to use with SIMD instructions. */ +/* Pack Utility */ +struct BVHStackEntry +{ + const BVHNode *node; + int idx; -class BVH4 : public BVH { -protected: - /* constructor */ - friend class BVH; - BVH4(const BVHParams& params, const vector<Object*>& objects); - - /* pack */ - void pack_nodes(const BVHNode *root); - - void pack_leaf(const BVHStackEntry& e, const LeafNode *leaf); - void pack_inner(const BVHStackEntry& e, const BVHStackEntry *en, int num); - - void pack_aligned_inner(const BVHStackEntry& e, - const BVHStackEntry *en, - int num); - void pack_aligned_node(int idx, - const BoundBox *bounds, - const int *child, - const uint visibility, - const float time_from, - const float time_to, - const int num); - - void pack_unaligned_inner(const BVHStackEntry& e, - const BVHStackEntry *en, - int num); - void pack_unaligned_node(int idx, - const Transform *aligned_space, - const BoundBox *bounds, - const int *child, - const uint visibility, - const float time_from, - const float time_to, - const int num); - - /* refit */ - void refit_nodes(); - void refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility); + BVHStackEntry(const BVHNode *n = 0, int i = 0); + int encodeIdx() const; }; CCL_NAMESPACE_END #endif /* __BVH_H__ */ - diff --git a/intern/cycles/bvh/bvh2.cpp b/intern/cycles/bvh/bvh2.cpp new file mode 100644 index 00000000000..340ba7dcf53 --- /dev/null +++ b/intern/cycles/bvh/bvh2.cpp @@ -0,0 +1,364 @@ +/* + * 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/bvh2.h" + +#include "render/mesh.h" +#include "render/object.h" + +#include "bvh/bvh_node.h" +#include "bvh/bvh_unaligned.h" + +CCL_NAMESPACE_BEGIN + +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; +} + +BVH2::BVH2(const BVHParams& params_, const vector<Object*>& objects_) +: BVH(params_, objects_) +{ +} + +void BVH2::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->lo] == -1) { + /* object */ + data[0].x = __int_as_float(~(leaf->lo)); + data[0].y = __int_as_float(0); + } + else { + /* triangle */ + data[0].x = __int_as_float(leaf->lo); + data[0].y = __int_as_float(leaf->hi); + } + data[0].z = __uint_as_float(leaf->visibility); + if(leaf->num_triangles() != 0) { + data[0].w = __uint_as_float(pack.prim_type[leaf->lo]); + } + + memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_NODE_LEAF_SIZE); +} + +void BVH2::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 BVH2::pack_aligned_inner(const BVHStackEntry& e, + const BVHStackEntry& e0, + const BVHStackEntry& e1) +{ + pack_aligned_node(e.idx, + e0.node->bounds, e1.node->bounds, + e0.encodeIdx(), e1.encodeIdx(), + e0.node->visibility, e1.node->visibility); +} + +void BVH2::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 BVH2::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->bounds, + e1.node->bounds, + e0.encodeIdx(), e1.encodeIdx(), + e0.node->visibility, e1.node->visibility); +} + +void BVH2::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 BVH2::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 BVH2::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 BVH2::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; + } +} + +CCL_NAMESPACE_END diff --git a/intern/cycles/bvh/bvh2.h b/intern/cycles/bvh/bvh2.h new file mode 100644 index 00000000000..df65ddca5b7 --- /dev/null +++ b/intern/cycles/bvh/bvh2.h @@ -0,0 +1,87 @@ +/* + * 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 __BVH2_H__ +#define __BVH2_H__ + +#include "bvh/bvh.h" +#include "bvh/bvh_params.h" + +#include "util/util_types.h" +#include "util/util_vector.h" + +CCL_NAMESPACE_BEGIN + +class BVHNode; +struct BVHStackEntry; +class BVHParams; +class BoundBox; +class LeafNode; +class Object; +class Progress; + +#define BVH_NODE_SIZE 4 +#define BVH_NODE_LEAF_SIZE 1 +#define BVH_UNALIGNED_NODE_SIZE 7 + +/* BVH2 + * + * Typical BVH with each node having two children. + */ +class BVH2 : public BVH { +protected: + /* constructor */ + friend class BVH; + BVH2(const BVHParams& params, const vector<Object*>& objects); + + /* pack */ + void pack_nodes(const BVHNode *root); + + void pack_leaf(const BVHStackEntry& e, + const LeafNode *leaf); + void pack_inner(const BVHStackEntry& e, + const BVHStackEntry& e0, + const BVHStackEntry& e1); + + void pack_aligned_inner(const BVHStackEntry& e, + const BVHStackEntry& e0, + const BVHStackEntry& e1); + void pack_aligned_node(int idx, + const BoundBox& b0, + const BoundBox& b1, + int c0, int c1, + uint visibility0, uint visibility1); + + void pack_unaligned_inner(const BVHStackEntry& e, + const BVHStackEntry& e0, + const BVHStackEntry& e1); + void pack_unaligned_node(int idx, + const Transform& aligned_space0, + const Transform& aligned_space1, + const BoundBox& b0, + const BoundBox& b1, + int c0, int c1, + uint visibility0, uint visibility1); + + /* refit */ + void refit_nodes(); + void refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility); +}; + +CCL_NAMESPACE_END + +#endif /* __BVH2_H__ */ diff --git a/intern/cycles/bvh/bvh4.cpp b/intern/cycles/bvh/bvh4.cpp new file mode 100644 index 00000000000..5034ab811d5 --- /dev/null +++ b/intern/cycles/bvh/bvh4.cpp @@ -0,0 +1,516 @@ +/* + * 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/bvh4.h" + +#include "render/mesh.h" +#include "render/object.h" + +#include "bvh/bvh_node.h" +#include "bvh/bvh_unaligned.h" + +CCL_NAMESPACE_BEGIN + +/* 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; +} + +BVH4::BVH4(const BVHParams& params_, const vector<Object*>& objects_) +: BVH(params_, objects_) +{ + params.use_qbvh = true; +} + +void BVH4::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->lo] == -1) { + /* object */ + data[0].x = __int_as_float(~(leaf->lo)); + data[0].y = __int_as_float(0); + } + else { + /* triangle */ + data[0].x = __int_as_float(leaf->lo); + data[0].y = __int_as_float(leaf->hi); + } + data[0].z = __uint_as_float(leaf->visibility); + if(leaf->num_triangles() != 0) { + data[0].w = __uint_as_float(pack.prim_type[leaf->lo]); + } + + memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_QNODE_LEAF_SIZE); +} + +void BVH4::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 BVH4::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->bounds; + child[i] = en[i].encodeIdx(); + } + pack_aligned_node(e.idx, + bounds, + child, + e.node->visibility, + e.node->time_from, + e.node->time_to, + num); +} + +void BVH4::pack_aligned_node(int idx, + const BoundBox *bounds, + const int *child, + const uint visibility, + const float time_from, + const float time_to, + const int num) +{ + float4 data[BVH_QNODE_SIZE]; + memset(data, 0, sizeof(data)); + + data[0].x = __uint_as_float(visibility & ~PATH_RAY_NODE_UNALIGNED); + data[0].y = time_from; + data[0].z = time_to; + + 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 BVH4::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->bounds; + child[i] = en[i].encodeIdx(); + } + pack_unaligned_node(e.idx, + aligned_space, + bounds, + child, + e.node->visibility, + e.node->time_from, + e.node->time_to, + num); +} + +void BVH4::pack_unaligned_node(int idx, + const Transform *aligned_space, + const BoundBox *bounds, + const int *child, + const uint visibility, + const float time_from, + const float time_to, + 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); + data[0].y = time_from; + data[0].z = time_to; + + 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 BVH4::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 BVH4::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 BVH4::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, + 0.0f, + 1.0f, + 4); + } + else { + pack_aligned_node(idx, + child_bbox, + &c[0], + visibility, + 0.0f, + 1.0f, + 4); + } + } +} + +CCL_NAMESPACE_END diff --git a/intern/cycles/bvh/bvh4.h b/intern/cycles/bvh/bvh4.h new file mode 100644 index 00000000000..1e1e8565ea1 --- /dev/null +++ b/intern/cycles/bvh/bvh4.h @@ -0,0 +1,88 @@ +/* + * 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 __BVH4_H__ +#define __BVH4_H__ + +#include "bvh/bvh.h" +#include "bvh/bvh_params.h" + +#include "util/util_types.h" +#include "util/util_vector.h" + +CCL_NAMESPACE_BEGIN + +class BVHNode; +struct BVHStackEntry; +class BVHParams; +class BoundBox; +class LeafNode; +class Object; +class Progress; + +#define BVH_QNODE_SIZE 8 +#define BVH_QNODE_LEAF_SIZE 1 +#define BVH_UNALIGNED_QNODE_SIZE 14 + +/* BVH4 + * + * Quad BVH, with each node having four children, to use with SIMD instructions. + */ +class BVH4 : public BVH { +protected: + /* constructor */ + friend class BVH; + BVH4(const BVHParams& params, const vector<Object*>& objects); + + /* pack */ + void pack_nodes(const BVHNode *root); + + void pack_leaf(const BVHStackEntry& e, const LeafNode *leaf); + void pack_inner(const BVHStackEntry& e, const BVHStackEntry *en, int num); + + void pack_aligned_inner(const BVHStackEntry& e, + const BVHStackEntry *en, + int num); + void pack_aligned_node(int idx, + const BoundBox *bounds, + const int *child, + const uint visibility, + const float time_from, + const float time_to, + const int num); + + void pack_unaligned_inner(const BVHStackEntry& e, + const BVHStackEntry *en, + int num); + void pack_unaligned_node(int idx, + const Transform *aligned_space, + const BoundBox *bounds, + const int *child, + const uint visibility, + const float time_from, + const float time_to, + const int num); + + /* refit */ + void refit_nodes(); + void refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility); +}; + +CCL_NAMESPACE_END + +#endif /* __BVH_H__ */ + |