Cycles: Split BVH implementations into separate files
authorSergey Sharybin <sergey.vfx@gmail.com>
Thu, 13 Apr 2017 08:55:46 +0000 (10:55 +0200)
committerSergey Sharybin <sergey.vfx@gmail.com>
Thu, 13 Apr 2017 08:55:46 +0000 (10:55 +0200)
intern/cycles/bvh/CMakeLists.txt
intern/cycles/bvh/bvh.cpp
intern/cycles/bvh/bvh.h
intern/cycles/bvh/bvh2.cpp [new file with mode: 0644]
intern/cycles/bvh/bvh2.h [new file with mode: 0644]
intern/cycles/bvh/bvh4.cpp [new file with mode: 0644]
intern/cycles/bvh/bvh4.h [new file with mode: 0644]

index 4701d75350acb724f2c782c1df9dc3a643c8733b..6078db5a8caa7d04c324e800963d23afe4ebeafc 100644 (file)
@@ -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
index 6a9aa2aafdb56ef196af3b78378a3f2761a59c14..33143e2d8aaa3bbba47067369e906b506ec8d2e6 100644 (file)
  * 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
index 8e664e67dc5ed60a6baf80e7a43f5c65f0bf26de..7bac6112fd9911bf6fe6e6f9b802d26585355672 100644 (file)
@@ -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 (file)
index 0000000..340ba7d
--- /dev/null
@@ -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 (file)
index 0000000..df65ddc
--- /dev/null
@@ -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 (file)
index 0000000..5034ab8
--- /dev/null
@@ -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 (file)
index 0000000..1e1e856
--- /dev/null
@@ -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__ */
+