Cycles: Implement unaligned nodes BVH builder
authorSergey Sharybin <sergey.vfx@gmail.com>
Thu, 7 Jul 2016 10:18:57 +0000 (12:18 +0200)
committerSergey Sharybin <sergey.vfx@gmail.com>
Thu, 7 Jul 2016 15:25:48 +0000 (17:25 +0200)
This is a special builder type which is allowed to orient nodes to
strands direction, hence minimizing their surface area in comparison
with axis-aligned nodes. Such nodes are much more efficient for hair
rendering.

Implementation of BVH builder is based on Embree, and generally idea
there is to calculate axis-aligned SAH and oriented SAH and if SAH
of oriented node is smaller than axis-aligned SAH we create unaligned
node.

We store both aligned and unaligned nodes in the same tree (which
seems to be different from what Embree is doing) so we don't have
any any extra calculations needed to set up hair ray for BVH
traversal, hence avoiding any possible negative effect of this new
BVH nodes type.

This new builder is currently not in use, still need to make BVH
traversal code aware of unaligned nodes.

21 files changed:
intern/cycles/bvh/CMakeLists.txt
intern/cycles/bvh/bvh.cpp
intern/cycles/bvh/bvh.h
intern/cycles/bvh/bvh_binning.cpp
intern/cycles/bvh/bvh_binning.h
intern/cycles/bvh/bvh_build.cpp
intern/cycles/bvh/bvh_build.h
intern/cycles/bvh/bvh_node.cpp
intern/cycles/bvh/bvh_node.h
intern/cycles/bvh/bvh_params.h
intern/cycles/bvh/bvh_sort.cpp
intern/cycles/bvh/bvh_sort.h
intern/cycles/bvh/bvh_split.cpp
intern/cycles/bvh/bvh_split.h
intern/cycles/bvh/bvh_unaligned.cpp [new file with mode: 0644]
intern/cycles/bvh/bvh_unaligned.h [new file with mode: 0644]
intern/cycles/kernel/kernel_types.h
intern/cycles/render/mesh.cpp
intern/cycles/render/mesh.h
intern/cycles/util/util_boundbox.h
intern/cycles/util/util_transform.h

index 5729fa6..92e48f0 100644 (file)
@@ -19,6 +19,7 @@ set(SRC
        bvh_node.cpp
        bvh_sort.cpp
        bvh_split.cpp
+       bvh_unaligned.cpp
 )
 
 set(SRC_HEADERS
@@ -29,6 +30,7 @@ set(SRC_HEADERS
        bvh_params.h
        bvh_sort.h
        bvh_split.h
+       bvh_unaligned.h
 )
 
 include_directories(${INC})
index ab4dbe8..e92526a 100644 (file)
@@ -24,6 +24,7 @@
 #include "bvh_build.h"
 #include "bvh_node.h"
 #include "bvh_params.h"
+#include "bvh_unaligned.h"
 
 #include "util_debug.h"
 #include "util_foreach.h"
@@ -192,13 +193,13 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size)
 {
        /* The BVH's for instances are built separately, but for traversal all
         * BVH's are stored in global arrays. This function merges them into the
-        * top level BVH, adjusting indexes and offsets where appropriate. */
-       bool use_qbvh = params.use_qbvh;
-       size_t nsize = (use_qbvh)? BVH_QNODE_SIZE: BVH_NODE_SIZE;
-       size_t nsize_leaf = (use_qbvh)? BVH_QNODE_LEAF_SIZE: BVH_NODE_LEAF_SIZE;
+        * top level BVH, adjusting indexes and offsets where appropriate.
+        */
+       const bool use_qbvh = params.use_qbvh;
 
-       /* adjust primitive index to point to the triangle in the global array, for
-        * meshes with transform applied and already in the top level BVH */
+       /* Adjust primitive index to point to the triangle in the global array, for
+        * meshes with transform applied and already in the top level BVH.
+        */
        for(size_t i = 0; i < pack.prim_index.size(); i++)
                if(pack.prim_index[i] != -1) {
                        if(pack.prim_type[i] & PRIMITIVE_ALL_CURVE)
@@ -340,40 +341,51 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size)
                if(bvh->pack.leaf_nodes.size()) {
                        int4 *leaf_nodes_offset = &bvh->pack.leaf_nodes[0];
                        size_t leaf_nodes_offset_size = bvh->pack.leaf_nodes.size();
-                       for(size_t i = 0, j = 0; i < leaf_nodes_offset_size; i+=nsize_leaf, j++) {
+                       for(size_t i = 0, j = 0;
+                           i < leaf_nodes_offset_size;
+                           i+= BVH_NODE_LEAF_SIZE, j++)
+                       {
                                int4 data = leaf_nodes_offset[i];
                                data.x += prim_offset;
                                data.y += prim_offset;
                                pack_leaf_nodes[pack_leaf_nodes_offset] = data;
-                               for(int j = 1; j < nsize_leaf; ++j) {
+                               for(int j = 1; j < BVH_NODE_LEAF_SIZE; ++j) {
                                        pack_leaf_nodes[pack_leaf_nodes_offset + j] = leaf_nodes_offset[i + j];
                                }
-                               pack_leaf_nodes_offset += nsize_leaf;
+                               pack_leaf_nodes_offset += BVH_NODE_LEAF_SIZE;
                        }
                }
 
                if(bvh->pack.nodes.size()) {
-                       /* For QBVH we're packing a child bbox into 6 float4,
-                        * and for regular BVH they're packed into 3 float4.
-                        */
-                       const size_t nsize_bbox = (use_qbvh)? 7: 3;
                        int4 *bvh_nodes = &bvh->pack.nodes[0];
                        size_t bvh_nodes_size = bvh->pack.nodes.size();
 
-                       for(size_t i = 0, j = 0; i < bvh_nodes_size; i+=nsize, j++) {
+                       for(size_t i = 0, j = 0; i < bvh_nodes_size; j++) {
+                               size_t nsize, nsize_bbox;
+                               if(bvh_nodes[i].x & PATH_RAY_NODE_UNALIGNED) {
+                                       nsize = use_qbvh
+                                                   ? BVH_UNALIGNED_QNODE_SIZE
+                                                   : BVH_UNALIGNED_NODE_SIZE;
+                                       nsize_bbox = (use_qbvh)? 13: 0;
+                               }
+                               else {
+                                       nsize = (use_qbvh)? BVH_QNODE_SIZE: BVH_NODE_SIZE;
+                                       nsize_bbox = (use_qbvh)? 7: 0;
+                               }
+
                                memcpy(pack_nodes + pack_nodes_offset,
                                       bvh_nodes + i,
                                       nsize_bbox*sizeof(int4));
 
-                               /* modify offsets into arrays */
+                               /* Modify offsets into arrays */
                                int4 data = bvh_nodes[i + nsize_bbox];
 
-                               data.x += (data.x < 0)? -noffset_leaf: noffset;
-                               data.y += (data.y < 0)? -noffset_leaf: noffset;
+                               data.z += (data.z < 0)? -noffset_leaf: noffset;
+                               data.w += (data.w < 0)? -noffset_leaf: noffset;
 
                                if(use_qbvh) {
-                                       data.z += (data.z < 0)? -noffset_leaf: noffset;
-                                       data.w += (data.w < 0)? -noffset_leaf: noffset;
+                                       data.x += (data.x < 0)? -noffset_leaf: noffset;
+                                       data.y += (data.y < 0)? -noffset_leaf: noffset;
                                }
 
                                pack_nodes[pack_nodes_offset + nsize_bbox] = data;
@@ -386,6 +398,7 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size)
                                       sizeof(int4) * (nsize - (nsize_bbox+1)));
 
                                pack_nodes_offset += nsize;
+                               i += nsize;
                        }
                }
 
@@ -397,12 +410,20 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size)
 
 /* Regular BVH */
 
+static bool node_bvh_is_unaligned(const BVHNode *node)
+{
+       const BVHNode *node0 = node->get_child(0),
+                     *node1 = node->get_child(1);
+       return node0->is_unaligned() || node1->is_unaligned();
+}
+
 RegularBVH::RegularBVH(const BVHParams& params_, const vector<Object*>& objects_)
 : BVH(params_, objects_)
 {
 }
 
-void RegularBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
+void RegularBVH::pack_leaf(const BVHStackEntry& e,
+                           const LeafNode *leaf)
 {
        float4 data[BVH_NODE_LEAF_SIZE];
        memset(data, 0, sizeof(data));
@@ -424,41 +445,112 @@ void RegularBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
        memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_NODE_LEAF_SIZE);
 }
 
-void RegularBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry& e0, const BVHStackEntry& e1)
+void RegularBVH::pack_inner(const BVHStackEntry& e,
+                            const BVHStackEntry& e0,
+                            const BVHStackEntry& e1)
+{
+       if (e0.node->is_unaligned() || e1.node->is_unaligned()) {
+               pack_unaligned_inner(e, e0, e1);
+       } else {
+               pack_aligned_inner(e, e0, e1);
+       }
+}
+
+void RegularBVH::pack_aligned_inner(const BVHStackEntry& e,
+                                    const BVHStackEntry& e0,
+                                    const BVHStackEntry& e1)
 {
-       pack_node(e.idx, e0.node->m_bounds, e1.node->m_bounds, e0.encodeIdx(), e1.encodeIdx(), e0.node->m_visibility, e1.node->m_visibility);
+       pack_aligned_node(e.idx,
+                         e0.node->m_bounds, e1.node->m_bounds,
+                         e0.encodeIdx(), e1.encodeIdx(),
+                         e0.node->m_visibility & ~PATH_RAY_NODE_UNALIGNED,
+                         e1.node->m_visibility & ~PATH_RAY_NODE_UNALIGNED);
 }
 
-void RegularBVH::pack_node(int idx, const BoundBox& b0, const BoundBox& b1, int c0, int c1, uint visibility0, uint visibility1)
+void RegularBVH::pack_aligned_node(int idx,
+                                   const BoundBox& b0,
+                                   const BoundBox& b1,
+                                   int c0, int c1,
+                                   uint visibility0, uint visibility1)
 {
        int4 data[BVH_NODE_SIZE] =
        {
+               make_int4(visibility0, visibility1, 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)),
-               make_int4(c0, c1, visibility0, visibility1)
        };
 
        memcpy(&pack.nodes[idx], data, sizeof(int4)*BVH_NODE_SIZE);
 }
 
-void RegularBVH::pack_nodes(const BVHNode *root)
+void RegularBVH::pack_unaligned_inner(const BVHStackEntry& e,
+                                      const BVHStackEntry& e0,
+                                      const BVHStackEntry& e1)
 {
-       size_t tot_node_size = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
-       size_t leaf_node_size = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
-       size_t node_size = tot_node_size - leaf_node_size;
+       pack_unaligned_node(e.idx,
+                           e0.node->get_aligned_space(),
+                           e1.node->get_aligned_space(),
+                           e0.node->m_bounds,
+                           e1.node->m_bounds,
+                           e0.encodeIdx(), e1.encodeIdx(),
+                           e0.node->m_visibility, e1.node->m_visibility);
+}
 
-       /* resize arrays */
-       pack.nodes.clear();
+void RegularBVH::pack_unaligned_node(int idx,
+                                     const Transform& aligned_space0,
+                                     const Transform& aligned_space1,
+                                     const BoundBox& bounds0,
+                                     const BoundBox& bounds1,
+                                     int c0, int c1,
+                                     uint visibility0, uint visibility1)
+{
+       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);
+}
 
-       /* for top level BVH, first merge existing BVH's so we know the offsets */
+void RegularBVH::pack_nodes(const BVHNode *root)
+{
+       const size_t num_nodes = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
+       const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
+       assert(num_leaf_nodes <= num_nodes);
+       const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
+       size_t node_size;
+       if(params.use_unaligned_nodes) {
+               const size_t num_unaligned_nodes =
+                       root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT);
+               node_size = (num_unaligned_nodes * BVH_UNALIGNED_NODE_SIZE) +
+                           (num_inner_nodes - num_unaligned_nodes) * BVH_NODE_SIZE;
+       }
+       else {
+               node_size = num_inner_nodes * BVH_NODE_SIZE;
+       }
+       /* Resize arrays */
+       pack.nodes.clear();
+       pack.leaf_nodes.clear();
+       /* For top level BVH, first merge existing BVH's so we know the offsets. */
        if(params.top_level) {
-               pack_instances(node_size*BVH_NODE_SIZE,
-                              leaf_node_size*BVH_NODE_LEAF_SIZE);
+               pack_instances(node_size, num_leaf_nodes*BVH_NODE_LEAF_SIZE);
        }
        else {
-               pack.nodes.resize(node_size*BVH_NODE_SIZE);
-               pack.leaf_nodes.resize(leaf_node_size*BVH_NODE_LEAF_SIZE);
+               pack.nodes.resize(node_size);
+               pack.leaf_nodes.resize(num_leaf_nodes*BVH_NODE_LEAF_SIZE);
        }
 
        int nextNodeIdx = 0, nextLeafNodeIdx = 0;
@@ -470,7 +562,9 @@ void RegularBVH::pack_nodes(const BVHNode *root)
        }
        else {
                stack.push_back(BVHStackEntry(root, nextNodeIdx));
-               nextNodeIdx += BVH_NODE_SIZE;
+               nextNodeIdx += node_bvh_is_unaligned(root)
+                                      ? BVH_UNALIGNED_NODE_SIZE
+                                      : BVH_NODE_SIZE;
        }
 
        while(stack.size()) {
@@ -479,7 +573,7 @@ void RegularBVH::pack_nodes(const BVHNode *root)
 
                if(e.node->is_leaf()) {
                        /* leaf node */
-                       const LeafNodeleaf = reinterpret_cast<const LeafNode*>(e.node);
+                       const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
                        pack_leaf(e, leaf);
                }
                else {
@@ -491,7 +585,9 @@ void RegularBVH::pack_nodes(const BVHNode *root)
                                }
                                else {
                                        idx[i] = nextNodeIdx;
-                                       nextNodeIdx += BVH_NODE_SIZE;
+                                       nextNodeIdx += node_bvh_is_unaligned(e.node->get_child(i))
+                                                              ? BVH_UNALIGNED_NODE_SIZE
+                                                              : BVH_NODE_SIZE;
                                }
                        }
 
@@ -501,7 +597,7 @@ void RegularBVH::pack_nodes(const BVHNode *root)
                        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;
 }
@@ -592,14 +688,14 @@ void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility
                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],
+               memcpy(&pack.leaf_nodes[idx * BVH_NODE_LEAF_SIZE],
                       leaf_data,
                       sizeof(float4)*BVH_NODE_LEAF_SIZE);
        }
        else {
                int4 *data = &pack.nodes[idx];
-               int c0 = data[3].x;
-               int c1 = data[3].y;
+               int c0 = data[0].z;
+               int c1 = data[0].w;
                /* refit inner node, set bbox from children */
                BoundBox bbox0 = BoundBox::empty, bbox1 = BoundBox::empty;
                uint visibility0 = 0, visibility1 = 0;
@@ -607,7 +703,7 @@ void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility
                refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0);
                refit_node((c1 < 0)? -c1-1: c1, (c1 < 0), bbox1, visibility1);
 
-               pack_node(idx, bbox0, bbox1, c0, c1, visibility0, visibility1);
+               pack_aligned_node(idx, bbox0, bbox1, c0, c1, visibility0, visibility1);
 
                bbox.grow(bbox0);
                bbox.grow(bbox1);
@@ -617,6 +713,33 @@ void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility
 
 /* QBVH */
 
+/* Can we avoid this somehow or make more generic?
+ *
+ * Perhaps we can merge nodes in actual tree and make our
+ * life easier all over the place.
+ */
+static bool node_qbvh_is_unaligned(const BVHNode *node)
+{
+       const BVHNode *node0 = node->get_child(0),
+                     *node1 = node->get_child(1);
+       bool has_unaligned = false;
+       if(node0->is_leaf()) {
+               has_unaligned |= node0->is_unaligned();
+       }
+       else {
+               has_unaligned |= node0->get_child(0)->is_unaligned();
+               has_unaligned |= node0->get_child(1)->is_unaligned();
+       }
+       if(node1->is_leaf()) {
+               has_unaligned |= node1->is_unaligned();
+       }
+       else {
+               has_unaligned |= node1->get_child(0)->is_unaligned();
+               has_unaligned |= node1->get_child(1)->is_unaligned();
+       }
+       return has_unaligned;
+}
+
 QBVH::QBVH(const BVHParams& params_, const vector<Object*>& objects_)
 : BVH(params_, objects_)
 {
@@ -645,11 +768,42 @@ void QBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
        memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_QNODE_LEAF_SIZE);
 }
 
-void QBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry *en, int num)
+void QBVH::pack_inner(const BVHStackEntry& e,
+                      const BVHStackEntry *en,
+                      int num)
+{
+       bool has_unaligned = false;
+       /* Check whether we have to create unaligned node or all nodes are aligned
+        * and we can cut some corner here.
+        */
+       if(params.use_unaligned_nodes) {
+               for(int i = 0; i < num; i++) {
+                       if(en[i].node->is_unaligned()) {
+                               has_unaligned = true;
+                               break;
+                       }
+               }
+       }
+       if(has_unaligned) {
+               /* There's no unaligned children, pack into AABB node. */
+               pack_unaligned_inner(e, en, num);
+       }
+       else {
+               /* Create unaligned node with orientation transform for each of the
+                * children.
+                */
+               pack_aligned_inner(e, en, num);
+       }
+}
+
+void QBVH::pack_aligned_inner(const BVHStackEntry& e,
+                              const BVHStackEntry *en,
+                              int num)
 {
        float4 data[BVH_QNODE_SIZE];
+       memset(data, 0, sizeof(data));
 
-       data[0].x = __uint_as_float(e.node->m_visibility);
+       data[0].x = __uint_as_float(e.node->m_visibility & ~PATH_RAY_NODE_UNALIGNED);
        for(int i = 0; i < num; i++) {
                float3 bb_min = en[i].node->m_bounds.min;
                float3 bb_max = en[i].node->m_bounds.max;
@@ -683,26 +837,81 @@ void QBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry *en, int num)
        memcpy(&pack.nodes[e.idx], data, sizeof(float4)*BVH_QNODE_SIZE);
 }
 
+void QBVH::pack_unaligned_inner(const BVHStackEntry& e,
+                                const BVHStackEntry *en,
+                                int num)
+{
+       float4 data[BVH_UNALIGNED_QNODE_SIZE];
+       memset(data, 0, sizeof(data));
+
+       data[0].x = __uint_as_float(e.node->m_visibility | PATH_RAY_NODE_UNALIGNED);
+
+       for(int i = 0; i < num; i++) {
+               Transform space = BVHUnaligned::compute_node_transform(
+                       en[i].node->m_bounds,
+                       en[i].node->get_aligned_space());
+
+               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(en[i].encodeIdx());
+       }
+
+       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.
+                */
+               for(int j = 1; j < 13; ++j) {
+                       data[j][i] = 0.0f;
+               }
+               data[13][i] = __int_as_float(0);
+       }
+
+       memcpy(&pack.nodes[e.idx], data, sizeof(float4)*BVH_UNALIGNED_QNODE_SIZE);
+}
+
 /* Quad SIMD Nodes */
 
 void QBVH::pack_nodes(const BVHNode *root)
 {
-       size_t tot_node_size = root->getSubtreeSize(BVH_STAT_QNODE_COUNT);
-       size_t leaf_node_size = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
-       size_t node_size = tot_node_size - leaf_node_size;
-
-       /* resize arrays */
+       /* 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 */
+       /* For top level BVH, first merge existing BVH's so we know the offsets. */
        if(params.top_level) {
-               pack_instances(node_size*BVH_QNODE_SIZE,
-                              leaf_node_size*BVH_QNODE_LEAF_SIZE);
+               pack_instances(node_size, num_leaf_nodes*BVH_QNODE_LEAF_SIZE);
        }
        else {
-               pack.nodes.resize(node_size*BVH_QNODE_SIZE);
-               pack.leaf_nodes.resize(leaf_node_size*BVH_QNODE_LEAF_SIZE);
+               pack.nodes.resize(node_size);
+               pack.leaf_nodes.resize(num_leaf_nodes*BVH_QNODE_LEAF_SIZE);
        }
 
        int nextNodeIdx = 0, nextLeafNodeIdx = 0;
@@ -714,7 +923,9 @@ void QBVH::pack_nodes(const BVHNode *root)
        }
        else {
                stack.push_back(BVHStackEntry(root, nextNodeIdx));
-               nextNodeIdx += BVH_QNODE_SIZE;
+               nextNodeIdx += node_qbvh_is_unaligned(root)
+                                      ? BVH_UNALIGNED_QNODE_SIZE
+                                      : BVH_QNODE_SIZE;
        }
 
        while(stack.size()) {
@@ -723,19 +934,17 @@ void QBVH::pack_nodes(const BVHNode *root)
 
                if(e.node->is_leaf()) {
                        /* leaf node */
-                       const LeafNodeleaf = reinterpret_cast<const LeafNode*>(e.node);
+                       const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
                        pack_leaf(e, leaf);
                }
                else {
-                       /* inner node */
+                       /* Inner node. */
                        const BVHNode *node = e.node;
                        const BVHNode *node0 = node->get_child(0);
                        const BVHNode *node1 = node->get_child(1);
-
-                       /* collect nodes */
+                       /* Collect nodes. */
                        const BVHNode *nodes[4];
                        int numnodes = 0;
-
                        if(node0->is_leaf()) {
                                nodes[numnodes++] = node0;
                        }
@@ -743,7 +952,6 @@ void QBVH::pack_nodes(const BVHNode *root)
                                nodes[numnodes++] = node0->get_child(0);
                                nodes[numnodes++] = node0->get_child(1);
                        }
-
                        if(node1->is_leaf()) {
                                nodes[numnodes++] = node1;
                        }
@@ -751,26 +959,26 @@ void QBVH::pack_nodes(const BVHNode *root)
                                nodes[numnodes++] = node1->get_child(0);
                                nodes[numnodes++] = node1->get_child(1);
                        }
-
-                       /* push entries on the stack */
-                       for(int i = 0; i < numnodes; i++) {
+                       /* 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 += BVH_QNODE_SIZE;
+                                       nextNodeIdx += node_qbvh_is_unaligned(nodes[i])
+                                                              ? BVH_UNALIGNED_QNODE_SIZE
+                                                              : BVH_QNODE_SIZE;
                                }
                                stack.push_back(BVHStackEntry(nodes[i], idx));
                        }
-
-                       /* set node */
+                       /* Set node. */
                        pack_inner(e, &stack[stack.size()-numnodes], numnodes);
                }
        }
-
-       /* root index to start traversal at, to handle case of single leaf node */
+       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;
 }
 
@@ -868,13 +1076,18 @@ void QBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
                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);
+               memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_QNODE_LEAF_SIZE);
        }
        else {
                int4 *data = &pack.nodes[idx];
-               int4 c = data[7];
+               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,
@@ -893,25 +1106,62 @@ void QBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
                        }
                }
 
-               float4 inner_data[BVH_QNODE_SIZE];
-               inner_data[0] = make_float4(__int_as_float(data[0].x),
-                                           __int_as_float(data[1].y),
-                                           __int_as_float(data[2].z),
-                                           __int_as_float(data[3].w));
-               for(int i = 0; i < 4; ++i) {
-                       float3 bb_min = child_bbox[i].min;
-                       float3 bb_max = child_bbox[i].max;
-                       inner_data[1][i] = bb_min.x;
-                       inner_data[2][i] = bb_max.x;
-                       inner_data[3][i] = bb_min.y;
-                       inner_data[4][i] = bb_max.y;
-                       inner_data[5][i] = bb_min.z;
-                       inner_data[6][i] = bb_max.z;
-                       inner_data[7][i] = __int_as_float(c[i]);
+               /* TODO(sergey): To be de-duplicated with pack_inner(),
+                * but for that need some sort of pack_node(). which operates with
+                * direct data, not stack element.
+                */
+               if(is_unaligned) {
+                       Transform aligned_space = transform_identity();
+                       float4 inner_data[BVH_UNALIGNED_QNODE_SIZE];
+                       inner_data[0] = make_float4(
+                               __int_as_float(visibility | PATH_RAY_NODE_UNALIGNED),
+                               0.0f,
+                               0.0f,
+                               0.0f);
+                       for(int i = 0; i < 4; ++i) {
+                               Transform space = BVHUnaligned::compute_node_transform(
+                                       child_bbox[i],
+                                       aligned_space);
+                               inner_data[1][i] = space.x.x;
+                               inner_data[2][i] = space.x.y;
+                               inner_data[3][i] = space.x.z;
+
+                               inner_data[4][i] = space.y.x;
+                               inner_data[5][i] = space.y.y;
+                               inner_data[6][i] = space.y.z;
+
+                               inner_data[7][i] = space.z.x;
+                               inner_data[8][i] = space.z.y;
+                               inner_data[9][i] = space.z.z;
+
+                               inner_data[10][i] = space.x.w;
+                               inner_data[11][i] = space.y.w;
+                               inner_data[12][i] = space.z.w;
+
+                               inner_data[13][i] = __int_as_float(c[i]);
+                       }
+                       memcpy(&pack.nodes[idx], inner_data, sizeof(float4)*BVH_UNALIGNED_QNODE_SIZE);
+               }
+               else {
+                       float4 inner_data[BVH_QNODE_SIZE];
+                       inner_data[0] = make_float4(
+                               __int_as_float(visibility & ~PATH_RAY_NODE_UNALIGNED),
+                               0.0f,
+                               0.0f,
+                               0.0f);
+                       for(int i = 0; i < 4; ++i) {
+                               float3 bb_min = child_bbox[i].min;
+                               float3 bb_max = child_bbox[i].max;
+                               inner_data[1][i] = bb_min.x;
+                               inner_data[2][i] = bb_max.x;
+                               inner_data[3][i] = bb_min.y;
+                               inner_data[4][i] = bb_max.y;
+                               inner_data[5][i] = bb_min.z;
+                               inner_data[6][i] = bb_max.z;
+                               inner_data[7][i] = __int_as_float(c[i]);
+                       }
+                       memcpy(&pack.nodes[idx], inner_data, sizeof(float4)*BVH_QNODE_SIZE);
                }
-               memcpy(&pack.nodes[idx],
-                      inner_data,
-                      sizeof(float4)*BVH_QNODE_SIZE);
        }
 }
 
index da7c9f3..1675207 100644 (file)
@@ -40,6 +40,9 @@ class Progress;
 #define BVH_ALIGN              4096
 #define TRI_NODE_SIZE  3
 
+#define BVH_UNALIGNED_NODE_SIZE 7
+#define BVH_UNALIGNED_QNODE_SIZE 14
+
 /* Packed BVH
  *
  * BVH stored as it will be used for traversal on the rendering device. */
@@ -117,9 +120,32 @@ protected:
 
        /* 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_node(int idx, const BoundBox& b0, const BoundBox& b1, int c0, int c1, uint visibility0, uint visibility1);
+
+       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();
@@ -138,9 +164,17 @@ protected:
 
        /* 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_unaligned_inner(const BVHStackEntry& e,
+                                 const BVHStackEntry *en,
+                                 int num);
+
        /* refit */
        void refit_nodes();
        void refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility);
index b07e870..5ddd734 100644 (file)
@@ -52,12 +52,35 @@ __forceinline int get_best_dimension(const float4& bestSAH)
 
 /* BVH Object Binning */
 
-BVHObjectBinning::BVHObjectBinning(const BVHRange& job, BVHReference *prims)
-: BVHRange(job), splitSAH(FLT_MAX), dim(0), pos(0)
+BVHObjectBinning::BVHObjectBinning(const BVHRange& job,
+                                   BVHReference *prims,
+                                   const BVHUnaligned *unaligned_heuristic,
+                                   const Transform *aligned_space)
+: BVHRange(job),
+  splitSAH(FLT_MAX),
+  dim(0),
+  pos(0),
+  unaligned_heuristic_(unaligned_heuristic),
+  aligned_space_(aligned_space)
 {
+       if(aligned_space_ == NULL) {
+               bounds_ = bounds();
+               cent_bounds_ = cent_bounds();
+       }
+       else {
+               /* TODO(sergey): With some additional storage we can avoid
+                * need in re-calculating this.
+                */
+               bounds_ = unaligned_heuristic->compute_aligned_boundbox(
+                       *this,
+                       prims,
+                       *aligned_space,
+                       &cent_bounds_);
+       }
+
        /* compute number of bins to use and precompute scaling factor for binning */
        num_bins = min(size_t(MAX_BINS), size_t(4.0f + 0.05f*size()));
-       scale = rcp(cent_bounds().size()) * make_float3((float)num_bins);
+       scale = rcp(cent_bounds_.size()) * make_float3((float)num_bins);
 
        /* initialize binning counter and bounds */
        BoundBox bin_bounds[MAX_BINS][4];       /* bounds for every bin in every dimension */
@@ -79,30 +102,34 @@ BVHObjectBinning::BVHObjectBinning(const BVHRange& job, BVHReference *prims)
                        const BVHReference& prim0 = prims[start() + i + 0];
                        const BVHReference& prim1 = prims[start() + i + 1];
 
-                       int4 bin0 = get_bin(prim0.bounds());
-                       int4 bin1 = get_bin(prim1.bounds());
+                       BoundBox bounds0 = get_prim_bounds(prim0);
+                       BoundBox bounds1 = get_prim_bounds(prim1);
+
+                       int4 bin0 = get_bin(bounds0);
+                       int4 bin1 = get_bin(bounds1);
 
                        /* increase bounds for bins for even primitive */
-                       int b00 = (int)extract<0>(bin0); bin_count[b00][0]++; bin_bounds[b00][0].grow(prim0.bounds());
-                       int b01 = (int)extract<1>(bin0); bin_count[b01][1]++; bin_bounds[b01][1].grow(prim0.bounds());
-                       int b02 = (int)extract<2>(bin0); bin_count[b02][2]++; bin_bounds[b02][2].grow(prim0.bounds());
+                       int b00 = (int)extract<0>(bin0); bin_count[b00][0]++; bin_bounds[b00][0].grow(bounds0);
+                       int b01 = (int)extract<1>(bin0); bin_count[b01][1]++; bin_bounds[b01][1].grow(bounds0);
+                       int b02 = (int)extract<2>(bin0); bin_count[b02][2]++; bin_bounds[b02][2].grow(bounds0);
 
                        /* increase bounds of bins for odd primitive */
-                       int b10 = (int)extract<0>(bin1); bin_count[b10][0]++; bin_bounds[b10][0].grow(prim1.bounds());
-                       int b11 = (int)extract<1>(bin1); bin_count[b11][1]++; bin_bounds[b11][1].grow(prim1.bounds());
-                       int b12 = (int)extract<2>(bin1); bin_count[b12][2]++; bin_bounds[b12][2].grow(prim1.bounds());
+                       int b10 = (int)extract<0>(bin1); bin_count[b10][0]++; bin_bounds[b10][0].grow(bounds1);
+                       int b11 = (int)extract<1>(bin1); bin_count[b11][1]++; bin_bounds[b11][1].grow(bounds1);
+                       int b12 = (int)extract<2>(bin1); bin_count[b12][2]++; bin_bounds[b12][2].grow(bounds1);
                }
 
                /* for uneven number of primitives */
                if(i < ssize_t(size())) {
                        /* map primitive to bin */
                        const BVHReference& prim0 = prims[start() + i];
-                       int4 bin0 = get_bin(prim0.bounds());
+                       BoundBox bounds0 = get_prim_bounds(prim0);
+                       int4 bin0 = get_bin(bounds0);
 
                        /* increase bounds of bins */
-                       int b00 = (int)extract<0>(bin0); bin_count[b00][0]++; bin_bounds[b00][0].grow(prim0.bounds());
-                       int b01 = (int)extract<1>(bin0); bin_count[b01][1]++; bin_bounds[b01][1].grow(prim0.bounds());
-                       int b02 = (int)extract<2>(bin0); bin_count[b02][2]++; bin_bounds[b02][2].grow(prim0.bounds());
+                       int b00 = (int)extract<0>(bin0); bin_count[b00][0]++; bin_bounds[b00][0].grow(bounds0);
+                       int b01 = (int)extract<1>(bin0); bin_count[b01][1]++; bin_bounds[b01][1].grow(bounds0);
+                       int b02 = (int)extract<2>(bin0); bin_count[b02][2]++; bin_bounds[b02][2].grow(bounds0);
                }
        }
 
@@ -151,17 +178,19 @@ BVHObjectBinning::BVHObjectBinning(const BVHRange& job, BVHReference *prims)
                bestSAH = min(sah,bestSAH);
        }
 
-       int4 mask = float3_to_float4(cent_bounds().size()) <= make_float4(0.0f);
+       int4 mask = float3_to_float4(cent_bounds_.size()) <= make_float4(0.0f);
        bestSAH = insert<3>(select(mask, make_float4(FLT_MAX), bestSAH), FLT_MAX);
 
        /* find best dimension */
        dim = get_best_dimension(bestSAH);
        splitSAH = bestSAH[dim];
        pos = bestSplit[dim];
-       leafSAH = bounds().half_area() * blocks(size());
+       leafSAH = bounds_.half_area() * blocks(size());
 }
 
-void BVHObjectBinning::split(BVHReference* prims, BVHObjectBinning& left_o, BVHObjectBinning& right_o) const
+void BVHObjectBinning::split(BVHReference* prims,
+                             BVHObjectBinning& left_o,
+                             BVHObjectBinning& right_o) const
 {
        size_t N = size();
 
@@ -176,10 +205,12 @@ void BVHObjectBinning::split(BVHReference* prims, BVHObjectBinning& left_o, BVHO
                prefetch_L2(&prims[start() + l + 8]);
                prefetch_L2(&prims[start() + r - 8]);
 
-               const BVHReference& prim = prims[start() + l];
+               BVHReference prim = prims[start() + l];
+               BoundBox unaligned_bounds = get_prim_bounds(prim);
+               float3 unaligned_center = unaligned_bounds.center2();
                float3 center = prim.bounds().center2();
 
-               if(get_bin(center)[dim] < pos) {
+               if(get_bin(unaligned_center)[dim] < pos) {
                        lgeom_bounds.grow(prim.bounds());
                        lcent_bounds.grow(center);
                        l++;
@@ -191,7 +222,6 @@ void BVHObjectBinning::split(BVHReference* prims, BVHObjectBinning& left_o, BVHO
                        r--;
                }
        }
-
        /* finish */
        if(l != 0 && N-1-r != 0) {
                right_o = BVHObjectBinning(BVHRange(rgeom_bounds, rcent_bounds, start() + l, N-1-r), prims);
index 6074215..52955f7 100644 (file)
 #define __BVH_BINNING_H__
 
 #include "bvh_params.h"
+#include "bvh_unaligned.h"
 
 #include "util_types.h"
 
 CCL_NAMESPACE_BEGIN
 
+class BVHBuild;
+
 /* Single threaded object binner. Finds the split with the best SAH heuristic
  * by testing for each dimension multiple partitionings for regular spaced
  * partition locations. A partitioning for a partition location is computed,
@@ -34,10 +37,18 @@ CCL_NAMESPACE_BEGIN
 class BVHObjectBinning : public BVHRange
 {
 public:
-       __forceinline BVHObjectBinning() {}
-       BVHObjectBinning(const BVHRange& job, BVHReference *prims);
+       __forceinline BVHObjectBinning() : leafSAH(FLT_MAX) {}
+
+       BVHObjectBinning(const BVHRange& job,
+                        BVHReference *prims,
+                        const BVHUnaligned *unaligned_heuristic = NULL,
+                        const Transform *aligned_space = NULL);
 
-       void split(BVHReference *prims, BVHObjectBinning& left_o, BVHObjectBinning& right_o) const;
+       void split(BVHReference *prims,
+                  BVHObjectBinning& left_o,
+                  BVHObjectBinning& right_o) const;
+
+       __forceinline const BoundBox& unaligned_bounds() { return bounds_; }
 
        float splitSAH; /* SAH cost of the best split */
        float leafSAH;  /* SAH cost of creating a leaf */
@@ -48,13 +59,20 @@ protected:
        size_t num_bins;        /* actual number of bins to use */
        float3 scale;           /* scaling factor to compute bin */
 
+       /* Effective bounds and centroid bounds. */
+       BoundBox bounds_;
+       BoundBox cent_bounds_;
+
+       const BVHUnaligned *unaligned_heuristic_;
+       const Transform *aligned_space_;
+
        enum { MAX_BINS = 32 };
        enum { LOG_BLOCK_SIZE = 2 };
 
        /* computes the bin numbers for each dimension for a box. */
        __forceinline int4 get_bin(const BoundBox& box) const
        {
-               int4 a = make_int4((box.center2() - cent_bounds().min)*scale - make_float3(0.5f));
+               int4 a = make_int4((box.center2() - cent_bounds_.min)*scale - make_float3(0.5f));
                int4 mn = make_int4(0);
                int4 mx = make_int4((int)num_bins-1);
 
@@ -64,7 +82,7 @@ protected:
        /* computes the bin numbers for each dimension for a point. */
        __forceinline int4 get_bin(const float3& c) const
        {
-               return make_int4((c - cent_bounds().min)*scale - make_float3(0.5f));
+               return make_int4((c - cent_bounds_.min)*scale - make_float3(0.5f));
        }
 
        /* compute the number of blocks occupied for each dimension. */
@@ -78,6 +96,17 @@ protected:
        {
                return (int)((a+((1LL << LOG_BLOCK_SIZE)-1)) >> LOG_BLOCK_SIZE);
        }
+
+       __forceinline BoundBox get_prim_bounds(const BVHReference& prim) const
+       {
+               if(aligned_space_ == NULL) {
+                       return prim.bounds();
+               }
+               else {
+                       return unaligned_heuristic_->compute_aligned_prim_boundbox(
+                               prim, *aligned_space_);
+               }
+       }
 };
 
 CCL_NAMESPACE_END
index 3f68722..67ffb68 100644 (file)
@@ -33,6 +33,7 @@
 #include "util_stack_allocator.h"
 #include "util_simd.h"
 #include "util_time.h"
+#include "util_queue.h"
 
 CCL_NAMESPACE_BEGIN
 
@@ -99,7 +100,8 @@ BVHBuild::BVHBuild(const vector<Object*>& objects_,
    prim_object(prim_object_),
    params(params_),
    progress(progress_),
-   progress_start_time(0.0)
+   progress_start_time(0.0),
+   unaligned_heuristic(objects_)
 {
        spatial_min_overlap = 0.0f;
 }
@@ -112,70 +114,74 @@ BVHBuild::~BVHBuild()
 
 void BVHBuild::add_reference_mesh(BoundBox& root, BoundBox& center, Mesh *mesh, int i)
 {
-       Attribute *attr_mP = NULL;
-       
-       if(mesh->has_motion_blur())
-               attr_mP = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
+       if(params.primitive_mask & PRIMITIVE_ALL_TRIANGLE) {
+               Attribute *attr_mP = NULL;
 
-       size_t num_triangles = mesh->num_triangles();
-       for(uint j = 0; j < num_triangles; j++) {
-               Mesh::Triangle t = mesh->get_triangle(j);
-               BoundBox bounds = BoundBox::empty;
-               PrimitiveType type = PRIMITIVE_TRIANGLE;
+               if(mesh->has_motion_blur())
+                       attr_mP = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
+
+               size_t num_triangles = mesh->num_triangles();
+               for(uint j = 0; j < num_triangles; j++) {
+                       Mesh::Triangle t = mesh->get_triangle(j);
+                       BoundBox bounds = BoundBox::empty;
+                       PrimitiveType type = PRIMITIVE_TRIANGLE;
 
-               t.bounds_grow(&mesh->verts[0], bounds);
+                       t.bounds_grow(&mesh->verts[0], bounds);
 
-               /* motion triangles */
-               if(attr_mP) {
-                       size_t mesh_size = mesh->verts.size();
-                       size_t steps = mesh->motion_steps - 1;
-                       float3 *vert_steps = attr_mP->data_float3();
+                       /* motion triangles */
+                       if(attr_mP) {
+                               size_t mesh_size = mesh->verts.size();
+                               size_t steps = mesh->motion_steps - 1;
+                               float3 *vert_steps = attr_mP->data_float3();
 
-                       for(size_t i = 0; i < steps; i++)
-                               t.bounds_grow(vert_steps + i*mesh_size, bounds);
+                               for(size_t i = 0; i < steps; i++)
+                                       t.bounds_grow(vert_steps + i*mesh_size, bounds);
 
-                       type = PRIMITIVE_MOTION_TRIANGLE;
-               }
+                               type = PRIMITIVE_MOTION_TRIANGLE;
+                       }
 
-               if(bounds.valid()) {
-                       references.push_back(BVHReference(bounds, j, i, type));
-                       root.grow(bounds);
-                       center.grow(bounds.center2());
+                       if(bounds.valid()) {
+                               references.push_back(BVHReference(bounds, j, i, type));
+                               root.grow(bounds);
+                               center.grow(bounds.center2());
+                       }
                }
        }
 
-       Attribute *curve_attr_mP = NULL;
+       if(params.primitive_mask & PRIMITIVE_ALL_CURVE) {
+               Attribute *curve_attr_mP = NULL;
 
-       if(mesh->has_motion_blur())
-               curve_attr_mP = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
+               if(mesh->has_motion_blur())
+                       curve_attr_mP = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
 
-       size_t num_curves = mesh->num_curves();
-       for(uint j = 0; j < num_curves; j++) {
-               Mesh::Curve curve = mesh->get_curve(j);
-               PrimitiveType type = PRIMITIVE_CURVE;
+               size_t num_curves = mesh->num_curves();
+               for(uint j = 0; j < num_curves; j++) {
+                       Mesh::Curve curve = mesh->get_curve(j);
+                       PrimitiveType type = PRIMITIVE_CURVE;
 
-               for(int k = 0; k < curve.num_keys - 1; k++) {
-                       BoundBox bounds = BoundBox::empty;
-                       curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bounds);
+                       for(int k = 0; k < curve.num_keys - 1; k++) {
+                               BoundBox bounds = BoundBox::empty;
+                               curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bounds);
 
-                       /* motion curve */
-                       if(curve_attr_mP) {
-                               size_t mesh_size = mesh->curve_keys.size();
-                               size_t steps = mesh->motion_steps - 1;
-                               float3 *key_steps = curve_attr_mP->data_float3();
+                               /* motion curve */
+                               if(curve_attr_mP) {
+                                       size_t mesh_size = mesh->curve_keys.size();
+                                       size_t steps = mesh->motion_steps - 1;
+                                       float3 *key_steps = curve_attr_mP->data_float3();
 
-                               for(size_t i = 0; i < steps; i++)
-                                       curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bounds);
+                                       for(size_t i = 0; i < steps; i++)
+                                               curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bounds);
 
-                               type = PRIMITIVE_MOTION_CURVE;
-                       }
+                                       type = PRIMITIVE_MOTION_CURVE;
+                               }
 
-                       if(bounds.valid()) {
-                               int packed_type = PRIMITIVE_PACK_SEGMENT(type, k);
-                               
-                               references.push_back(BVHReference(bounds, j, i, packed_type));
-                               root.grow(bounds);
-                               center.grow(bounds.center2());
+                               if(bounds.valid()) {
+                                       int packed_type = PRIMITIVE_PACK_SEGMENT(type, k);
+
+                                       references.push_back(BVHReference(bounds, j, i, packed_type));
+                                       root.grow(bounds);
+                                       center.grow(bounds.center2());
+                               }
                        }
                }
        }
@@ -209,15 +215,23 @@ void BVHBuild::add_references(BVHRange& root)
                                continue;
                        }
                        if(!ob->mesh->is_instanced()) {
-                               num_alloc_references += ob->mesh->num_triangles();
-                               num_alloc_references += count_curve_segments(ob->mesh);
+                               if(params.primitive_mask & PRIMITIVE_ALL_TRIANGLE) {
+                                       num_alloc_references += ob->mesh->num_triangles();
+                               }
+                               if(params.primitive_mask & PRIMITIVE_ALL_CURVE) {
+                                       num_alloc_references += count_curve_segments(ob->mesh);
+                               }
                        }
                        else
                                num_alloc_references++;
                }
                else {
-                       num_alloc_references += ob->mesh->num_triangles();
-                       num_alloc_references += count_curve_segments(ob->mesh);
+                       if(params.primitive_mask & PRIMITIVE_ALL_TRIANGLE) {
+                               num_alloc_references += ob->mesh->num_triangles();
+                       }
+                       if(params.primitive_mask & PRIMITIVE_ALL_CURVE) {
+                               num_alloc_references += count_curve_segments(ob->mesh);
+                       }
                }
        }
 
@@ -340,6 +354,8 @@ BVHNode* BVHBuild::run()
                                << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_INNER_COUNT)) << "\n"
                                << "  Number of leaf nodes: "
                                << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_LEAF_COUNT)) << "\n"
+                               << "  Number of unaligned nodes: "
+                               << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_UNALIGNED_COUNT))  << "\n"
                                << "  Allocation slop factor: "
                                       << ((prim_type.capacity() != 0)
                                               ? (float)prim_type.size() / prim_type.capacity()
@@ -445,10 +461,11 @@ BVHNode* BVHBuild::build_node(const BVHObjectBinning& range, int level)
        float leafSAH = params.sah_primitive_cost * range.leafSAH;
        float splitSAH = params.sah_node_cost * range.bounds().half_area() + params.sah_primitive_cost * range.splitSAH;
 
-       /* have at least one inner node on top level, for performance and correct
-        * visibility tests, since object instances do not check visibility flag */
+       /* Have at least one inner node on top level, for performance and correct
+        * visibility tests, since object instances do not check visibility flag.
+        */
        if(!(range.size() > 0 && params.top_level && level == 0)) {
-               /* make leaf node when threshold reached or SAH tells us */
+               /* Make leaf node when threshold reached or SAH tells us. */
                if((params.small_enough_for_leaf(size, level)) ||
                   (range_within_max_leaf_size(range, references) && leafSAH < splitSAH))
                {
@@ -456,28 +473,70 @@ BVHNode* BVHBuild::build_node(const BVHObjectBinning& range, int level)
                }
        }
 
-       /* perform split */
+       BVHObjectBinning unaligned_range;
+       float unalignedSplitSAH = FLT_MAX;
+       float unalignedLeafSAH = FLT_MAX;
+       Transform aligned_space;
+       if(params.use_unaligned_nodes &&
+          splitSAH > params.unaligned_split_threshold*leafSAH)
+       {
+               aligned_space = unaligned_heuristic.compute_aligned_space(
+                       range, &references[0]);
+               unaligned_range = BVHObjectBinning(range,
+                                                  &references[0],
+                                                  &unaligned_heuristic,
+                                                  &aligned_space);
+               unalignedSplitSAH = params.sah_node_cost * unaligned_range.unaligned_bounds().half_area() +
+                                   params.sah_primitive_cost * unaligned_range.splitSAH;
+               unalignedLeafSAH = params.sah_primitive_cost * unaligned_range.leafSAH;
+               if(!(range.size() > 0 && params.top_level && level == 0)) {
+                       if(unalignedLeafSAH < unalignedSplitSAH && unalignedSplitSAH < splitSAH &&
+                          range_within_max_leaf_size(range, references))
+                       {
+                               return create_leaf_node(range, references);
+                       }
+               }
+       }
+
+       /* Perform split. */
        BVHObjectBinning left, right;
-       range.split(&references[0], left, right);
+       if(unalignedSplitSAH < splitSAH) {
+               unaligned_range.split(&references[0], left, right);
+       }
+       else {
+               range.split(&references[0], left, right);
+       }
 
-       /* create inner node. */
-       InnerNode *inner;
+       BoundBox bounds;
+       if(unalignedSplitSAH < splitSAH) {
+               bounds = unaligned_heuristic.compute_aligned_boundbox(
+                       range, &references[0], aligned_space);
+       }
+       else {
+               bounds = range.bounds();
+       }
 
+       /* Create inner node. */
+       InnerNode *inner;
        if(range.size() < THREAD_TASK_SIZE) {
                /* local build */
                BVHNode *leftnode = build_node(left, level + 1);
                BVHNode *rightnode = build_node(right, level + 1);
 
-               inner = new InnerNode(range.bounds(), leftnode, rightnode);
+               inner = new InnerNode(bounds, leftnode, rightnode);
        }
        else {
-               /* threaded build */
-               inner = new InnerNode(range.bounds());
+               /* Threaded build */
+               inner = new InnerNode(bounds);
 
                task_pool.push(new BVHBuildTask(this, inner, 0, left, level + 1), true);
                task_pool.push(new BVHBuildTask(this, inner, 1, right, level + 1), true);
        }
 
+       if(unalignedSplitSAH < splitSAH) {
+               inner->set_aligned_space(aligned_space);
+       }
+
        return inner;
 }
 
@@ -516,16 +575,54 @@ BVHNode* BVHBuild::build_node(const BVHRange& range,
                        return create_leaf_node(range, *references);
                }
        }
+       float leafSAH = params.sah_primitive_cost * split.leafSAH;
+       float splitSAH = params.sah_node_cost * range.bounds().half_area() +
+                        params.sah_primitive_cost * split.nodeSAH;
+
+       BVHMixedSplit unaligned_split;
+       float unalignedSplitSAH = FLT_MAX;
+       /* float unalignedLeafSAH = FLT_MAX; */
+       Transform aligned_space;
+       if(params.use_unaligned_nodes &&
+          splitSAH > params.unaligned_split_threshold*leafSAH)
+       {
+               aligned_space =
+                       unaligned_heuristic.compute_aligned_space(range, &references->at(0));
+               unaligned_split = BVHMixedSplit(this,
+                                               storage,
+                                               range,
+                                               references,
+                                               level,
+                                               &unaligned_heuristic,
+                                               &aligned_space);
+               /* unalignedLeafSAH = params.sah_primitive_cost * split.leafSAH; */
+               unalignedSplitSAH = params.sah_node_cost * unaligned_split.bounds.half_area() +
+                                   params.sah_primitive_cost * unaligned_split.nodeSAH;
+               /* TOOD(sergey): Check we can create leaf already. */
+       }
 
        /* Do split. */
        BVHRange left, right;
-       split.split(this, left, right, range);
+       if(unalignedSplitSAH < splitSAH) {
+               unaligned_split.split(this, left, right, range);
+       }
+       else {
+               split.split(this, left, right, range);
+       }
 
        progress_total += left.size() + right.size() - range.size();
 
+       BoundBox bounds;
+       if(unalignedSplitSAH < splitSAH) {
+               bounds = unaligned_heuristic.compute_aligned_boundbox(
+                       range, &references->at(0), aligned_space);
+       }
+       else {
+               bounds = range.bounds();
+       }
+
        /* Create inner node. */
        InnerNode *inner;
-
        if(range.size() < THREAD_TASK_SIZE) {
                /* Local build. */
 
@@ -539,11 +636,11 @@ BVHNode* BVHBuild::build_node(const BVHRange& range,
                /* Build right node. */
                BVHNode *rightnode = build_node(right, &copy, level + 1, thread_id);
 
-               inner = new InnerNode(range.bounds(), leftnode, rightnode);
+               inner = new InnerNode(bounds, leftnode, rightnode);
        }
        else {
                /* Threaded build. */
-               inner = new InnerNode(range.bounds());
+               inner = new InnerNode(bounds);
                task_pool.push(new BVHSpatialSplitBuildTask(this,
                                                            inner,
                                                            0,
@@ -560,6 +657,10 @@ BVHNode* BVHBuild::build_node(const BVHRange& range,
                               true);
        }
 
+       if(unalignedSplitSAH < splitSAH) {
+               inner->set_aligned_space(aligned_space);
+       }
+
        return inner;
 }
 
@@ -616,6 +717,7 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range,
        vector<int, LeafStackAllocator> p_type[PRIMITIVE_NUM_TOTAL];
        vector<int, LeafStackAllocator> p_index[PRIMITIVE_NUM_TOTAL];
        vector<int, LeafStackAllocator> p_object[PRIMITIVE_NUM_TOTAL];
+       vector<BVHReference, LeafStackAllocator> p_ref[PRIMITIVE_NUM_TOTAL];
 
        /* TODO(sergey): In theory we should be able to store references. */
        typedef StackAllocator<256, BVHReference> LeafReferenceStackAllocator;
@@ -634,6 +736,7 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range,
                const BVHReference& ref = references[range.start() + i];
                if(ref.prim_index() != -1) {
                        int type_index = bitscan(ref.prim_type() & PRIMITIVE_ALL);
+                       p_ref[type_index].push_back(ref);
                        p_type[type_index].push_back(ref.prim_type());
                        p_index[type_index].push_back(ref.prim_index());
                        p_object[type_index].push_back(ref.prim_object());
@@ -674,16 +777,38 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range,
                if(num != 0) {
                        assert(p_type[i].size() == p_index[i].size());
                        assert(p_type[i].size() == p_object[i].size());
+                       Transform aligned_space;
+                       bool alignment_found = false;
                        for(int j = 0; j < num; ++j) {
                                const int index = start_index + j;
                                local_prim_type[index] = p_type[i][j];
                                local_prim_index[index] = p_index[i][j];
                                local_prim_object[index] = p_object[i][j];
+                               if(params.use_unaligned_nodes && !alignment_found) {
+                                       alignment_found =
+                                               unaligned_heuristic.compute_aligned_space(p_ref[i][j],
+                                                                                          &aligned_space);
+                               }
+                       }
+                       LeafNode *leaf_node = new LeafNode(bounds[i],
+                                                          visibility[i],
+                                                          start_index,
+                                                          start_index + num);
+                       if(alignment_found) {
+                               /* Need to recalculate leaf bounds with new alignment. */
+                               leaf_node->m_bounds = BoundBox::empty;
+                               for(int j = 0; j < num; ++j) {
+                                       const BVHReference &ref = p_ref[i][j];
+                                       BoundBox ref_bounds =
+                                               unaligned_heuristic.compute_aligned_prim_boundbox(
+                                                       ref,
+                                                       aligned_space);
+                                       leaf_node->m_bounds.grow(ref_bounds);
+                               }
+                               /* Set alignment space. */
+                               leaf_node->set_aligned_space(aligned_space);
                        }
-                       leaves[num_leaves++] = new LeafNode(bounds[i],
-                                                           visibility[i],
-                                                           start_index,
-                                                           start_index + num);
+                       leaves[num_leaves++] = leaf_node;
                        start_index += num;
                }
        }
@@ -765,6 +890,9 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range,
                ++num_leaves;
        }
 
+       /* TODO(sergey): Need to take care of alignment when number of leaves
+        * is more than 1.
+        */
        if(num_leaves == 1) {
                /* Simplest case: single leaf, just return it.
                 * In all the rest cases we'll be creating intermediate inner node with
index a015b89..6418034 100644 (file)
@@ -22,6 +22,7 @@
 
 #include "bvh.h"
 #include "bvh_binning.h"
+#include "bvh_unaligned.h"
 
 #include "util_boundbox.h"
 #include "util_task.h"
@@ -59,13 +60,14 @@ protected:
        friend class BVHSpatialSplit;
        friend class BVHBuildTask;
        friend class BVHSpatialSplitBuildTask;
+       friend class BVHObjectBinning;
 
-       /* adding references */
+       /* Adding references. */
        void add_reference_mesh(BoundBox& root, BoundBox& center, Mesh *mesh, int i);
        void add_reference_object(BoundBox& root, BoundBox& center, Object *ob, int i);
        void add_references(BVHRange& root);
 
-       /* building */
+       /* Building. */
        BVHNode *build_node(const BVHRange& range,
                            vector<BVHReference> *references,
                            int level,
@@ -78,7 +80,7 @@ protected:
        bool range_within_max_leaf_size(const BVHRange& range,
                                        const vector<BVHReference>& references) const;
 
-       /* threads */
+       /* Threads. */
        enum { THREAD_TASK_SIZE = 4096 };
        void thread_build_node(InnerNode *node,
                               int child,
@@ -92,41 +94,44 @@ protected:
                                             int thread_id);
        thread_mutex build_mutex;
 
-       /* progress */
+       /* Progress. */
        void progress_update();
 
-       /* tree rotations */
+       /* Tree rotations. */
        void rotate(BVHNode *node, int max_depth);
        void rotate(BVHNode *node, int max_depth, int iterations);
 
-       /* objects and primitive references */
+       /* Objects and primitive references. */
        vector<Object*> objects;
        vector<BVHReference> references;
        int num_original_references;
 
-       /* output primitive indexes and objects */
+       /* Output primitive indexes and objects. */
        array<int>& prim_type;
        array<int>& prim_index;
        array<int>& prim_object;
 
-       /* build parameters */
+       /* Build parameters. */
        BVHParams params;
 
-       /* progress reporting */
+       /* Progress reporting. */
        Progress& progress;
        double progress_start_time;
        size_t progress_count;
        size_t progress_total;
        size_t progress_original_total;
 
-       /* spatial splitting */
+       /* Spatial splitting. */
        float spatial_min_overlap;
        vector<BVHSpatialStorage> spatial_storage;
        size_t spatial_free_index;
        thread_spin_lock spatial_spin_lock;
 
-       /* threads */
+       /* Threads. */
        TaskPool task_pool;
+
+       /* Unaligned building. */
+       BVHUnaligned unaligned_heuristic;
 };
 
 CCL_NAMESPACE_END
index 8294690..f5cd699 100644 (file)
@@ -61,6 +61,76 @@ int BVHNode::getSubtreeSize(BVH_STAT stat) const
                                }
                        }
                        return cnt;
+               case BVH_STAT_ALIGNED_COUNT:
+                       if(!is_unaligned()) {
+                               cnt = 1;
+                       }
+                       break;
+               case BVH_STAT_UNALIGNED_COUNT:
+                       if(is_unaligned()) {
+                               cnt = 1;
+                       }
+                       break;
+               case BVH_STAT_ALIGNED_INNER_COUNT:
+                       if(!is_leaf()) {
+                               bool has_unaligned = false;
+                               for(int j = 0; j < num_children(); j++) {
+                                       has_unaligned |= get_child(j)->is_unaligned();
+                               }
+                               cnt += has_unaligned? 0: 1;
+                       }
+                       break;
+               case BVH_STAT_UNALIGNED_INNER_COUNT:
+                       if(!is_leaf()) {
+                               bool has_unaligned = false;
+                               for(int j = 0; j < num_children(); j++) {
+                                       has_unaligned |= get_child(j)->is_unaligned();
+                               }
+                               cnt += has_unaligned? 1: 0;
+                       }
+                       break;
+               case BVH_STAT_ALIGNED_INNER_QNODE_COUNT:
+                       {
+                               bool has_unaligned = false;
+                               for(int i = 0; i < num_children(); i++) {
+                                       BVHNode *node = get_child(i);
+                                       if(node->is_leaf()) {
+                                               has_unaligned |= node->is_unaligned();
+                                       }
+                                       else {
+                                               for(int j = 0; j < node->num_children(); j++) {
+                                                       cnt += node->get_child(j)->getSubtreeSize(stat);
+                                                       has_unaligned |= node->get_child(j)->is_unaligned();
+                                               }
+                                       }
+                               }
+                               cnt += has_unaligned? 0: 1;
+                       }
+                       return cnt;
+               case BVH_STAT_UNALIGNED_INNER_QNODE_COUNT:
+                       {
+                               bool has_unaligned = false;
+                               for(int i = 0; i < num_children(); i++) {
+                                       BVHNode *node = get_child(i);
+                                       if(node->is_leaf()) {
+                                               has_unaligned |= node->is_unaligned();
+                                       }
+                                       else {
+                                               for(int j = 0; j < node->num_children(); j++) {
+                                                       cnt += node->get_child(j)->getSubtreeSize(stat);
+                                                       has_unaligned |= node->get_child(j)->is_unaligned();
+                                               }
+                                       }
+                               }
+                               cnt += has_unaligned? 1: 0;
+                       }
+                       return cnt;
+               case BVH_STAT_ALIGNED_LEAF_COUNT:
+                       cnt = (is_leaf() && !is_unaligned()) ? 1 : 0;
+                       break;
+               case BVH_STAT_UNALIGNED_LEAF_COUNT:
+                       cnt = (is_leaf() && is_unaligned()) ? 1 : 0;
+                       break;
                default:
                        assert(0); /* unknown mode */
        }
index d476fb9..f2965a7 100644 (file)
@@ -31,6 +31,14 @@ enum BVH_STAT {
        BVH_STAT_TRIANGLE_COUNT,
        BVH_STAT_CHILDNODE_COUNT,
        BVH_STAT_QNODE_COUNT,
+       BVH_STAT_ALIGNED_COUNT,
+       BVH_STAT_UNALIGNED_COUNT,
+       BVH_STAT_ALIGNED_INNER_COUNT,
+       BVH_STAT_UNALIGNED_INNER_COUNT,
+       BVH_STAT_ALIGNED_INNER_QNODE_COUNT,
+       BVH_STAT_UNALIGNED_INNER_QNODE_COUNT,
+       BVH_STAT_ALIGNED_LEAF_COUNT,
+       BVH_STAT_UNALIGNED_LEAF_COUNT,
 };
 
 class BVHParams;
@@ -38,16 +46,41 @@ class BVHParams;
 class BVHNode
 {
 public:
-       BVHNode()
+       BVHNode() : m_is_unaligned(false),
+                   m_aligned_space(NULL)
        {
        }
 
-       virtual ~BVHNode() {}
+       virtual ~BVHNode()
+       {
+               delete m_aligned_space;
+       }
+
        virtual bool is_leaf() const = 0;
        virtual int num_children() const = 0;
        virtual BVHNode *get_child(int i) const = 0;
        virtual int num_triangles() const { return 0; }
        virtual void print(int depth = 0) const = 0;
+       bool is_unaligned() const { return m_is_unaligned; }
+
+       inline void set_aligned_space(const Transform& aligned_space)
+       {
+               m_is_unaligned = true;
+               if (m_aligned_space == NULL) {
+                       m_aligned_space = new Transform(aligned_space);
+               }
+               else {
+                       *m_aligned_space = aligned_space;
+               }
+       }
+
+       inline Transform get_aligned_space() const
+       {
+               if(m_aligned_space == NULL) {
+                       return transform_identity();
+               }
+               return *m_aligned_space;
+       }
 
        BoundBox m_bounds;
        uint m_visibility;
@@ -58,12 +91,20 @@ public:
        void deleteSubtree();
 
        uint update_visibility();
+
+       bool m_is_unaligned;
+
+       // TODO(sergey): Can be stored as 3x3 matrix, but better to have some
+       // utilities and type defines in util_transform first.
+       Transform *m_aligned_space;
 };
 
 class InnerNode : public BVHNode
 {
 public:
-       InnerNode(const BoundBox& bounds, BVHNode* child0, BVHNode* child1)
+       InnerNode(const BoundBox& bounds,
+                 BVHNode* child0,
+                 BVHNode* child1)
        {
                m_bounds = bounds;
                children[0] = child0;
index cf683df..2e698a8 100644 (file)
@@ -20,6 +20,8 @@
 
 #include "util_boundbox.h"
 
+#include "kernel_types.h"
+
 CCL_NAMESPACE_BEGIN
 
 /* BVH Parameters */
@@ -31,6 +33,9 @@ public:
        bool use_spatial_split;
        float spatial_split_alpha;
 
+       /* Unaligned nodes creation threshold */
+       float unaligned_split_threshold;
+
        /* SAH costs */
        float sah_node_cost;
        float sah_primitive_cost;
@@ -46,6 +51,14 @@ public:
        /* QBVH */
        bool use_qbvh;
 
+       /* Mask of primitives to be included into the BVH. */
+       int primitive_mask;
+
+       /* Use unaligned bounding boxes.
+        * Only used for curves BVH.
+        */
+       bool use_unaligned_nodes;
+
        /* fixed parameters */
        enum {
                MAX_DEPTH = 64,
@@ -58,6 +71,8 @@ public:
                use_spatial_split = true;
                spatial_split_alpha = 1e-5f;
 
+               unaligned_split_threshold = 0.7f;
+
                /* todo: see if splitting up primitive cost to be separate for triangles
                 * and curves can help. so far in tests it doesn't help, but why? */
                sah_node_cost = 1.0f;
@@ -69,6 +84,9 @@ public:
 
                top_level = false;
                use_qbvh = false;
+               use_unaligned_nodes = false;
+
+               primitive_mask = PRIMITIVE_ALL;
        }
 
        /* SAH costs */
index d50178b..e5bcf99 100644 (file)
@@ -29,10 +29,24 @@ static const int BVH_SORT_THRESHOLD = 4096;
 struct BVHReferenceCompare {
 public:
        int dim;
+       const BVHUnaligned *unaligned_heuristic;
+       const Transform *aligned_space;
+
+       BVHReferenceCompare(int dim,
+                           const BVHUnaligned *unaligned_heuristic,
+                           const Transform *aligned_space)
+               : dim(dim),
+                 unaligned_heuristic(unaligned_heuristic),
+                 aligned_space(aligned_space)
+       {
+       }
 
-       explicit BVHReferenceCompare(int dim_)
+       __forceinline BoundBox get_prim_bounds(const BVHReference& prim) const
        {
-               dim = dim_;
+               return (aligned_space != NULL)
+                       ? unaligned_heuristic->compute_aligned_prim_boundbox(
+                                 prim, *aligned_space)
+                       : prim.bounds();
        }
 
        /* Compare two references.
@@ -42,8 +56,10 @@ public:
        __forceinline int compare(const BVHReference& ra,
                                  const BVHReference& rb) const
        {
-               float ca = ra.bounds().min[dim] + ra.bounds().max[dim];
-               float cb = rb.bounds().min[dim] + rb.bounds().max[dim];
+               BoundBox ra_bounds = get_prim_bounds(ra),
+                        rb_bounds = get_prim_bounds(rb);
+               float ca = ra_bounds.min[dim] + ra_bounds.max[dim];
+               float cb = rb_bounds.min[dim] + rb_bounds.max[dim];
 
                if(ca < cb) return -1;
                else if(ca > cb) return 1;
@@ -161,10 +177,15 @@ static void bvh_reference_sort_threaded(TaskPool *task_pool,
        }
 }
 
-void bvh_reference_sort(int start, int end, BVHReference *data, int dim)
+void bvh_reference_sort(int start,
+                        int end,
+                        BVHReference *data,
+                        int dim,
+                        const BVHUnaligned *unaligned_heuristic,
+                        const Transform *aligned_space)
 {
        const int count = end - start;
-       BVHReferenceCompare compare(dim);
+       BVHReferenceCompare compare(dim, unaligned_heuristic, aligned_space);
        if(count < BVH_SORT_THRESHOLD) {
                /* It is important to not use any mutex if array is small enough,
                 * otherwise we end up in situation when we're going to sleep far
index 18aafb5..b49ca02 100644 (file)
 
 CCL_NAMESPACE_BEGIN
 
-void bvh_reference_sort(int start, int end, BVHReference *data, int dim);
+class BVHUnaligned;
+struct Transform;
+
+void bvh_reference_sort(int start,
+                        int end,
+                        BVHReference *data,
+                        int dim,
+                        const BVHUnaligned *unaligned_heuristic = NULL,
+                        const Transform *aligned_space = NULL);
 
 CCL_NAMESPACE_END
 
index bf68b41..d0d5fbe 100644 (file)
@@ -32,14 +32,18 @@ BVHObjectSplit::BVHObjectSplit(BVHBuild *builder,
                                BVHSpatialStorage *storage,
                                const BVHRange& range,
                                vector<BVHReference> *references,
-                               float nodeSAH)
+                               float nodeSAH,
+                               const BVHUnaligned *unaligned_heuristic,
+                               const Transform *aligned_space)
 : sah(FLT_MAX),
   dim(0),
   num_left(0),
   left_bounds(BoundBox::empty),
   right_bounds(BoundBox::empty),
   storage_(storage),
-  references_(references)
+  references_(references),
+  unaligned_heuristic_(unaligned_heuristic),
+  aligned_space_(aligned_space)
 {
        const BVHReference *ref_ptr = &references_->at(range.start());
        float min_sah = FLT_MAX;
@@ -51,12 +55,15 @@ BVHObjectSplit::BVHObjectSplit(BVHBuild *builder,
                bvh_reference_sort(range.start(),
                                   range.end(),
                                   &references_->at(0),
-                                  dim);
+                                  dim,
+                                  unaligned_heuristic_,
+                                  aligned_space_);
 
                /* sweep right to left and determine bounds. */
                BoundBox right_bounds = BoundBox::empty;
                for(int i = range.size() - 1; i > 0; i--) {
-                       right_bounds.grow(ref_ptr[i].bounds());
+                       BoundBox prim_bounds = get_prim_bounds(ref_ptr[i]);
+                       right_bounds.grow(prim_bounds);
                        storage_->right_bounds[i - 1] = right_bounds;
                }
 
@@ -64,7 +71,8 @@ BVHObjectSplit::BVHObjectSplit(BVHBuild *builder,
                BoundBox left_bounds = BoundBox::empty;
 
                for(int i = 1; i < range.size(); i++) {
-                       left_bounds.grow(ref_ptr[i - 1].bounds());
+                       BoundBox prim_bounds = get_prim_bounds(ref_ptr[i - 1]);
+                       left_bounds.grow(prim_bounds);
                        right_bounds = storage_->right_bounds[i - 1];
 
                        float sah = nodeSAH +
@@ -88,16 +96,37 @@ void BVHObjectSplit::split(BVHRange& left,
                            BVHRange& right,
                            const BVHRange& range)
 {
+       assert(references_->size() > 0);
        /* sort references according to split */
        bvh_reference_sort(range.start(),
                           range.end(),
                           &references_->at(0),
-                          this->dim);
+                          this->dim,
+                          unaligned_heuristic_,
+                          aligned_space_);
+
+       BoundBox effective_left_bounds, effective_right_bounds;
+       const int num_right = range.size() - this->num_left;
+       if(aligned_space_ == NULL) {
+               effective_left_bounds = left_bounds;
+               effective_right_bounds = right_bounds;
+       }
+       else {
+               effective_left_bounds = BoundBox::empty;
+               effective_right_bounds = BoundBox::empty;
+               for(int i = 0; i < this->num_left; ++i) {
+                       BoundBox prim_boundbox = references_->at(range.start() + i).bounds();
+                       effective_left_bounds.grow(prim_boundbox);
+               }
+               for(int i = 0; i < num_right; ++i) {
+                       BoundBox prim_boundbox = references_->at(range.start() + this->num_left + i).bounds();
+                       effective_right_bounds.grow(prim_boundbox);
+               }
+       }
 
        /* split node ranges */
-       left = BVHRange(this->left_bounds, range.start(), this->num_left);
-       right = BVHRange(this->right_bounds, left.end(), range.size() - this->num_left);
-
+       left = BVHRange(effective_left_bounds, range.start(), this->num_left);
+       right = BVHRange(effective_right_bounds, left.end(), num_right);
 }
 
 /* Spatial Split */
@@ -106,16 +135,31 @@ BVHSpatialSplit::BVHSpatialSplit(const BVHBuild& builder,
                                  BVHSpatialStorage *storage,
                                  const BVHRange& range,
                                  vector<BVHReference> *references,
-                                 float nodeSAH)
+                                 float nodeSAH,
+                                 const BVHUnaligned *unaligned_heuristic,
+                                 const Transform *aligned_space)
 : sah(FLT_MAX),
   dim(0),
   pos(0.0f),
   storage_(storage),
-  references_(references)
+  references_(references),
+  unaligned_heuristic_(unaligned_heuristic),
+  aligned_space_(aligned_space)
 {
        /* initialize bins. */
-       float3 origin = range.bounds().min;
-       float3 binSize = (range.bounds().max - origin) * (1.0f / (float)BVHParams::NUM_SPATIAL_BINS);
+       BoundBox range_bounds;
+       if(aligned_space == NULL) {
+               range_bounds = range.bounds();
+       }
+       else {
+               range_bounds = unaligned_heuristic->compute_aligned_boundbox(
+                       range,
+                       &references->at(0),
+                       *aligned_space);
+       }
+
+       float3 origin = range_bounds.min;
+       float3 binSize = (range_bounds.max - origin) * (1.0f / (float)BVHParams::NUM_SPATIAL_BINS);
        float3 invBinSize = 1.0f / binSize;
 
        for(int dim = 0; dim < 3; dim++) {
@@ -131,8 +175,9 @@ BVHSpatialSplit::BVHSpatialSplit(const BVHBuild& builder,
        /* chop references into bins. */
        for(unsigned int refIdx = range.start(); refIdx < range.end(); refIdx++) {
                const BVHReference& ref = references_->at(refIdx);
-               float3 firstBinf = (ref.bounds().min - origin) * invBinSize;
-               float3 lastBinf = (ref.bounds().max - origin) * invBinSize;
+               BoundBox prim_bounds = get_prim_bounds(ref);
+               float3 firstBinf = (prim_bounds.min - origin) * invBinSize;
+               float3 lastBinf = (prim_bounds.max - origin) * invBinSize;
                int3 firstBin = make_int3((int)firstBinf.x, (int)firstBinf.y, (int)firstBinf.z);
                int3 lastBin = make_int3((int)lastBinf.x, (int)lastBinf.y, (int)lastBinf.z);
 
@@ -140,7 +185,10 @@ BVHSpatialSplit::BVHSpatialSplit(const BVHBuild& builder,
                lastBin = clamp(lastBin, firstBin, BVHParams::NUM_SPATIAL_BINS - 1);
 
                for(int dim = 0; dim < 3; dim++) {
-                       BVHReference currRef = ref;
+                       BVHReference currRef(get_prim_bounds(ref),
+                                            ref.prim_index(),
+                                            ref.prim_object(),
+                                            ref.prim_type());
 
                        for(int i = firstBin[dim]; i < lastBin[dim]; i++) {
                                BVHReference leftRef, rightRef;
@@ -209,14 +257,15 @@ void BVHSpatialSplit::split(BVHBuild *builder,
        BoundBox right_bounds = BoundBox::empty;
 
        for(int i = left_end; i < right_start; i++) {
-               if(refs[i].bounds().max[this->dim] <= this->pos) {
+               BoundBox prim_bounds = get_prim_bounds(refs[i]);
+               if(prim_bounds.max[this->dim] <= this->pos) {
                        /* entirely on the left-hand side */
-                       left_bounds.grow(refs[i].bounds());
+                       left_bounds.grow(prim_bounds);
                        swap(refs[i], refs[left_end++]);
                }
-               else if(refs[i].bounds().min[this->dim] >= this->pos) {
+               else if(prim_bounds.min[this->dim] >= this->pos) {
                        /* entirely on the right-hand side */
-                       right_bounds.grow(refs[i].bounds());
+                       right_bounds.grow(prim_bounds);
                        swap(refs[i--], refs[--right_start]);
                }
        }
@@ -231,8 +280,12 @@ void BVHSpatialSplit::split(BVHBuild *builder,
        new_refs.reserve(right_start - left_end);
        while(left_end < right_start) {
                /* split reference. */
+               BVHReference curr_ref(get_prim_bounds(refs[left_end]),
+                                     refs[left_end].prim_index(),
+                                     refs[left_end].prim_object(),
+                                     refs[left_end].prim_type());
                BVHReference lref, rref;
-               split_reference(*builder, lref, rref, refs[left_end], this->dim, this->pos);
+               split_reference(*builder, lref, rref, curr_ref, this->dim, this->pos);
 
                /* compute SAH for duplicate/unsplit candidates. */
                BoundBox lub = left_bounds;             // Unsplit to left:             new left-hand bounds.
@@ -240,8 +293,8 @@ void BVHSpatialSplit::split(BVHBuild *builder,
                BoundBox ldb = left_bounds;             // Duplicate:                   new left-hand bounds.
                BoundBox rdb = right_bounds;    // Duplicate:                   new right-hand bounds.
 
-               lub.grow(refs[left_end].bounds());
-               rub.grow(refs[left_end].bounds());
+               lub.grow(curr_ref.bounds());
+               rub.grow(curr_ref.bounds());
                ldb.grow(lref.bounds());
                rdb.grow(rref.bounds());
 
@@ -280,6 +333,17 @@ void BVHSpatialSplit::split(BVHBuild *builder,
                            new_refs.begin(),
                            new_refs.end());
        }
+       if(aligned_space_ != NULL) {
+               left_bounds = right_bounds = BoundBox::empty;
+               for(int i = left_start; i < left_end - left_start; ++i) {
+                       BoundBox prim_boundbox = references_->at(i).bounds();
+                       left_bounds.grow(prim_boundbox);
+               }
+               for(int i = right_start; i < right_end - right_start; ++i) {
+                       BoundBox prim_boundbox = references_->at(i).bounds();
+                       right_bounds.grow(prim_boundbox);
+               }
+       }
        left = BVHRange(left_bounds, left_start, left_end - left_start);
        right = BVHRange(right_bounds, right_start, right_end - right_start);
 }
@@ -295,11 +359,13 @@ void BVHSpatialSplit::split_triangle_primitive(const Mesh *mesh,
        Mesh::Triangle t = mesh->get_triangle(prim_index);
        const float3 *verts = &mesh->verts[0];
        float3 v1 = tfm ? transform_point(tfm, verts[t.v[2]]) : verts[t.v[2]];
+       v1 = get_unaligned_point(v1);
 
        for(int i = 0; i < 3; i++) {
                float3 v0 = v1;
                int vindex = t.v[i];
                v1 = tfm ? transform_point(tfm, verts[vindex]) : verts[vindex];
+               v1 = get_unaligned_point(v1);
                float v0p = v0[dim];
                float v1p = v1[dim];
 
@@ -339,6 +405,8 @@ void BVHSpatialSplit::split_curve_primitive(const Mesh *mesh,
                v0 = transform_point(tfm, v0);
                v1 = transform_point(tfm, v1);
        }
+       v0 = get_unaligned_point(v0);
+       v1 = get_unaligned_point(v1);
 
        float v0p = v0[dim];
        float v1p = v1[dim];
@@ -473,6 +541,7 @@ void BVHSpatialSplit::split_reference(const BVHBuild& builder,
        /* intersect with original bounds. */
        left_bounds.max[dim] = pos;
        right_bounds.min[dim] = pos;
+
        left_bounds.intersect(ref.bounds());
        right_bounds.intersect(ref.bounds());
 
index aea8b25..dbdb51f 100644 (file)
@@ -24,6 +24,7 @@
 CCL_NAMESPACE_BEGIN
 
 class BVHBuild;
+struct Transform;
 
 /* Object Split */
 
@@ -41,7 +42,9 @@ public:
                       BVHSpatialStorage *storage,
                       const BVHRange& range,
                       vector<BVHReference> *references,
-                      float nodeSAH);
+                      float nodeSAH,
+                      const BVHUnaligned *unaligned_heuristic = NULL,
+                      const Transform *aligned_space = NULL);
 
        void split(BVHRange& left,
                   BVHRange& right,
@@ -50,6 +53,19 @@ public:
 protected:
        BVHSpatialStorage *storage_;
        vector<BVHReference> *references_;
+       const BVHUnaligned *unaligned_heuristic_;
+       const Transform *aligned_space_;
+
+       __forceinline BoundBox get_prim_bounds(const BVHReference& prim) const
+       {
+               if(aligned_space_ == NULL) {
+                       return prim.bounds();
+               }
+               else {
+                       return unaligned_heuristic_->compute_aligned_prim_boundbox(
+                               prim, *aligned_space_);
+               }
+       }
 };
 
 /* Spatial Split */
@@ -70,7 +86,9 @@ public:
                        BVHSpatialStorage *storage,
                        const BVHRange& range,
                        vector<BVHReference> *references,
-                       float nodeSAH);
+                       float nodeSAH,
+                       const BVHUnaligned *unaligned_heuristic = NULL,
+                       const Transform *aligned_space = NULL);
 
        void split(BVHBuild *builder,
                   BVHRange& left,
@@ -87,6 +105,8 @@ public:
 protected:
        BVHSpatialStorage *storage_;
        vector<BVHReference> *references_;
+       const BVHUnaligned *unaligned_heuristic_;
+       const Transform *aligned_space_;
 
        /* Lower-level functions which calculates boundaries of left and right nodes
         * needed for spatial split.
@@ -132,6 +152,27 @@ protected:
                                    float pos,
                                    BoundBox& left_bounds,
                                    BoundBox& right_bounds);
+
+       __forceinline BoundBox get_prim_bounds(const BVHReference& prim) const
+       {
+               if(aligned_space_ == NULL) {
+                       return prim.bounds();
+               }
+               else {
+                       return unaligned_heuristic_->compute_aligned_prim_boundbox(
+                               prim, *aligned_space_);
+               }
+       }
+
+       __forceinline float3 get_unaligned_point(const float3& point) const
+       {
+               if(aligned_space_ == NULL) {
+                       return point;
+               }
+               else {
+                       return transform_point(aligned_space_, point);
+               }
+       }
 };
 
 /* Mixed Object-Spatial Split */
@@ -148,19 +189,40 @@ public:
 
        bool no_split;
 
+       BoundBox bounds;
+
+       BVHMixedSplit() {}
+
        __forceinline BVHMixedSplit(BVHBuild *builder,
                                    BVHSpatialStorage *storage,
                                    const BVHRange& range,
                                    vector<BVHReference> *references,
-                                   int level)
+                                   int level,
+                                   const BVHUnaligned *unaligned_heuristic = NULL,
+                                   const Transform *aligned_space = NULL)
        {
+               if(aligned_space == NULL) {
+                       bounds = range.bounds();
+               }
+               else {
+                       bounds = unaligned_heuristic->compute_aligned_boundbox(
+                               range,
+                               &references->at(0),
+                               *aligned_space);
+               }
                /* find split candidates. */
-               float area = range.bounds().safe_area();
+               float area = bounds.safe_area();
 
                leafSAH = area * builder->params.primitive_cost(range.size());
                nodeSAH = area * builder->params.node_cost(2);
 
-               object = BVHObjectSplit(builder, storage, range, references, nodeSAH);
+               object = BVHObjectSplit(builder,
+                                       storage,
+                                       range,
+                                       references,
+                                       nodeSAH,
+                                       unaligned_heuristic,
+                                       aligned_space);
 
                if(builder->params.use_spatial_split && level < BVHParams::MAX_SPATIAL_DEPTH) {
                        BoundBox overlap = object.left_bounds;
@@ -171,7 +233,9 @@ public:
                                                          storage,
                                                          range,
                                                          references,
-                                                         nodeSAH);
+                                                         nodeSAH,
+                                                         unaligned_heuristic,
+                                                         aligned_space);
                        }
                }
 
@@ -181,7 +245,10 @@ public:
                            builder->range_within_max_leaf_size(range, *references));
        }
 
-       __forceinline void split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range)
+       __forceinline void split(BVHBuild *builder,
+                                BVHRange& left,
+                                BVHRange& right,
+                                const BVHRange& range)
        {
                if(builder->params.use_spatial_split && minSAH == spatial.sah)
                        spatial.split(builder, left, right, range);
@@ -193,4 +260,3 @@ public:
 CCL_NAMESPACE_END
 
 #endif /* __BVH_SPLIT_H__ */
-
diff --git a/intern/cycles/bvh/bvh_unaligned.cpp b/intern/cycles/bvh/bvh_unaligned.cpp
new file mode 100644 (file)
index 0000000..a876c67
--- /dev/null
@@ -0,0 +1,178 @@
+/*
+ * Copyright 2011-2016 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_unaligned.h"
+
+#include "mesh.h"
+#include "object.h"
+
+#include "bvh_binning.h"
+#include "bvh_params.h"
+
+#include "util_boundbox.h"
+#include "util_debug.h"
+#include "util_transform.h"
+
+CCL_NAMESPACE_BEGIN
+
+
+BVHUnaligned::BVHUnaligned(const vector<Object*>& objects)
+        : objects_(objects)
+{
+}
+
+Transform BVHUnaligned::compute_aligned_space(
+        const BVHObjectBinning& range,
+        const BVHReference *references) const
+{
+       for(int i = range.start(); i < range.end(); ++i) {
+               const BVHReference& ref = references[i];
+               Transform aligned_space;
+               /* Use first primitive which defines correct direction to define
+                * the orientation space.
+                */
+               if(compute_aligned_space(ref, &aligned_space)) {
+                       return aligned_space;
+               }
+       }
+       return transform_identity();
+}
+
+Transform BVHUnaligned::compute_aligned_space(
+        const BVHRange& range,
+        const BVHReference *references) const
+{
+       for(int i = range.start(); i < range.end(); ++i) {
+               const BVHReference& ref = references[i];
+               Transform aligned_space;
+               /* Use first primitive which defines correct direction to define
+                * the orientation space.
+                */
+               if(compute_aligned_space(ref, &aligned_space)) {
+                       return aligned_space;
+               }
+       }
+       return transform_identity();
+}
+
+bool BVHUnaligned::compute_aligned_space(const BVHReference& ref,
+                                         Transform *aligned_space) const
+{
+       const Object *object = objects_[ref.prim_object()];
+       const int packed_type = ref.prim_type();
+       const int type = (packed_type & PRIMITIVE_ALL);
+       if(type & PRIMITIVE_CURVE) {
+               const int curve_index = ref.prim_index();
+               const int segment = PRIMITIVE_UNPACK_SEGMENT(packed_type);
+               const Mesh *mesh = object->mesh;
+               const Mesh::Curve& curve = mesh->get_curve(curve_index);
+               const int key = curve.first_key + segment;
+               const float3 v1 = mesh->curve_keys[key],
+                            v2 = mesh->curve_keys[key + 1];
+               float length;
+               const float3 axis = normalize_len(v2 - v1, &length);
+               if(length > 1e-6f) {
+                       *aligned_space = make_transform_frame(axis);
+                       return true;
+               }
+       }
+       *aligned_space = transform_identity();
+       return false;
+}
+
+BoundBox BVHUnaligned::compute_aligned_prim_boundbox(
+        const BVHReference& prim,
+        const Transform& aligned_space) const
+{
+       BoundBox bounds = BoundBox::empty;
+       const Object *object = objects_[prim.prim_object()];
+       const int packed_type = prim.prim_type();
+       const int type = (packed_type & PRIMITIVE_ALL);
+       if(type & PRIMITIVE_CURVE) {
+               const int curve_index = prim.prim_index();
+               const int segment = PRIMITIVE_UNPACK_SEGMENT(packed_type);
+               const Mesh *mesh = object->mesh;
+               const Mesh::Curve& curve = mesh->get_curve(curve_index);
+               curve.bounds_grow(segment,
+                                 &mesh->curve_keys[0],
+                                 &mesh->curve_radius[0],
+                                 aligned_space,
+                                 bounds);
+       }
+       else {
+               bounds = prim.bounds().transformed(&aligned_space);
+       }
+       return bounds;
+}
+
+BoundBox BVHUnaligned::compute_aligned_boundbox(
+        const BVHObjectBinning& range,
+        const BVHReference *references,
+        const Transform& aligned_space,
+        BoundBox *cent_bounds) const
+{
+       BoundBox bounds = BoundBox::empty;
+       if(cent_bounds != NULL) {
+               *cent_bounds = BoundBox::empty;
+       }
+       for(int i = range.start(); i < range.end(); ++i) {
+               const BVHReference& ref = references[i];
+               BoundBox ref_bounds = compute_aligned_prim_boundbox(ref, aligned_space);
+               bounds.grow(ref_bounds);
+               if(cent_bounds != NULL) {
+                       cent_bounds->grow(ref_bounds.center2());
+               }
+       }
+       return bounds;
+}
+
+BoundBox BVHUnaligned::compute_aligned_boundbox(
+        const BVHRange& range,
+        const BVHReference *references,
+        const Transform& aligned_space,
+        BoundBox *cent_bounds) const
+{
+       BoundBox bounds = BoundBox::empty;
+       if(cent_bounds != NULL) {
+               *cent_bounds = BoundBox::empty;
+       }
+       for(int i = range.start(); i < range.end(); ++i) {
+               const BVHReference& ref = references[i];
+               BoundBox ref_bounds = compute_aligned_prim_boundbox(ref, aligned_space);
+               bounds.grow(ref_bounds);
+               if(cent_bounds != NULL) {
+                       cent_bounds->grow(ref_bounds.center2());
+               }
+       }
+       return bounds;
+}
+
+Transform BVHUnaligned::compute_node_transform(
+        const BoundBox& bounds,
+        const Transform& aligned_space)
+{
+       Transform space = aligned_space;
+       space.x.w -= bounds.min.x;
+       space.y.w -= bounds.min.y;
+       space.z.w -= bounds.min.z;
+       float3 dim = bounds.max - bounds.min;
+       return transform_scale(1.0f / max(1e-18f, dim.x),
+                              1.0f / max(1e-18f, dim.y),
+                              1.0f / max(1e-18f, dim.z)) * space;
+}
+
+CCL_NAMESPACE_END
diff --git a/intern/cycles/bvh/bvh_unaligned.h b/intern/cycles/bvh/bvh_unaligned.h
new file mode 100644 (file)
index 0000000..4d0872f
--- /dev/null
@@ -0,0 +1,81 @@
+/*
+ * Copyright 2011-2016 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 __BVH_UNALIGNED_H__
+#define __BVH_UNALIGNED_H__
+
+#include "util_vector.h"
+
+CCL_NAMESPACE_BEGIN
+
+class BoundBox;
+class BVHObjectBinning;
+class BVHRange;
+class BVHReference;
+struct Transform;
+class Object;
+
+/* Helper class to perform calculations needed for unaligned nodes. */
+class BVHUnaligned {
+public:
+       BVHUnaligned(const vector<Object*>& objects);
+
+       /* Calculate alignment for the oriented node for a given range. */
+       Transform compute_aligned_space(
+               const BVHObjectBinning& range,
+               const BVHReference *references) const;
+       Transform compute_aligned_space(
+               const BVHRange& range,
+               const BVHReference *references) const;
+
+       /* Calculate alignment for the oriented node for a given reference.
+        *
+        * Return true when space was calculated successfully.
+        */
+       bool compute_aligned_space(const BVHReference& ref,
+                                  Transform *aligned_space) const;
+
+       /* Calculate primitive's bounding box in given space. */
+       BoundBox compute_aligned_prim_boundbox(
+               const BVHReference& prim,
+               const Transform& aligned_space) const;
+
+       /* Calculate bounding box in given space. */
+       BoundBox compute_aligned_boundbox(
+               const BVHObjectBinning& range,
+               const BVHReference *references,
+               const Transform& aligned_space,
+               BoundBox *cent_bounds = NULL) const;
+       BoundBox compute_aligned_boundbox(
+               const BVHRange& range,
+               const BVHReference *references,
+               const Transform& aligned_space,
+               BoundBox *cent_bounds = NULL) const;
+
+       /* Calculate affine transform for node packing.
+        * Bounds will be in the range of 0..1.
+        */
+       static Transform compute_node_transform(const BoundBox& bounds,
+                                               const Transform& aligned_space);
+protected:
+       /* List of objects BVH is being created for. */
+       const vector<Object*>& objects_;
+};
+
+CCL_NAMESPACE_END
+
+#endif /* __BVH_UNALIGNED_H__ */
+
index 2187e3c..5de58ba 100644 (file)
@@ -292,11 +292,14 @@ enum PathRayFlag {
        PATH_RAY_CURVE = 512, /* visibility flag to define curve segments */
        PATH_RAY_VOLUME_SCATTER = 1024, /* volume scattering */
 
-       PATH_RAY_ALL_VISIBILITY = (1|2|4|8|16|32|64|128|256|512|1024),
+       /* Special flag to tag unaligned BVH nodes. */
+       PATH_RAY_NODE_UNALIGNED = 2048,
 
-       PATH_RAY_MIS_SKIP = 2048,
-       PATH_RAY_DIFFUSE_ANCESTOR = 4096,
-       PATH_RAY_SINGLE_PASS_DONE = 8192,
+       PATH_RAY_ALL_VISIBILITY = (1|2|4|8|16|32|64|128|256|512|1024|2048),
+
+       PATH_RAY_MIS_SKIP = 4096,
+       PATH_RAY_DIFFUSE_ANCESTOR = 8192,
+       PATH_RAY_SINGLE_PASS_DONE = 16384,
 };
 
 /* Closure Label */
index 4e1e36d..24cfb47 100644 (file)
@@ -73,6 +73,37 @@ void Mesh::Curve::bounds_grow(const int k, const float3 *curve_keys, const float
        bounds.grow(upper, mr);
 }
 
+void Mesh::Curve::bounds_grow(const int k,
+                              const float3 *curve_keys,
+                              const float *curve_radius,
+                              const Transform& aligned_space,
+                              BoundBox& bounds) const
+{
+       float3 P[4];
+
+       P[0] = curve_keys[max(first_key + k - 1,first_key)];
+       P[1] = curve_keys[first_key + k];
+       P[2] = curve_keys[first_key + k + 1];
+       P[3] = curve_keys[min(first_key + k + 2, first_key + num_keys - 1)];
+
+       P[0] = transform_point(&aligned_space, P[0]);
+       P[1] = transform_point(&aligned_space, P[1]);
+       P[2] = transform_point(&aligned_space, P[2]);
+       P[3] = transform_point(&aligned_space, P[3]);
+
+       float3 lower;
+       float3 upper;
+
+       curvebounds(&lower.x, &upper.x, P, 0);
+       curvebounds(&lower.y, &upper.y, P, 1);
+       curvebounds(&lower.z, &upper.z, P, 2);
+
+       float mr = max(curve_radius[first_key + k], curve_radius[first_key + k + 1]);
+
+       bounds.grow(lower, mr);
+       bounds.grow(upper, mr);
+}
+
 /* Mesh */
 
 NODE_DEFINE(Mesh)
@@ -522,7 +553,11 @@ void Mesh::pack_curves(Scene *scene, float4 *curve_key_co, float4 *curve_data, s
        }
 }
 
-void Mesh::compute_bvh(SceneParams *params, Progress *progress, int n, int total)
+void Mesh::compute_bvh(DeviceScene * /*dscene*/,
+                       SceneParams *params,
+                       Progress *progress,
+                       int n,
+                       int total)
 {
        if(progress->get_cancel())
                return;
@@ -553,6 +588,7 @@ void Mesh::compute_bvh(SceneParams *params, Progress *progress, int n, int total
                        BVHParams bparams;
                        bparams.use_spatial_split = params->use_bvh_spatial_split;
                        bparams.use_qbvh = params->use_qbvh;
+                       bparams.use_unaligned_nodes = false;
 
                        delete bvh;
                        bvh = BVH::create(bparams, objects);
@@ -1186,6 +1222,7 @@ void MeshManager::device_update_bvh(Device *device, DeviceScene *dscene, Scene *
        bparams.top_level = true;
        bparams.use_qbvh = scene->params.use_qbvh;
        bparams.use_spatial_split = scene->params.use_bvh_spatial_split;
+       bparams.use_unaligned_nodes = false;
 
        delete bvh;
        bvh = BVH::create(bparams, scene->objects);
@@ -1399,6 +1436,7 @@ void MeshManager::device_update(Device *device, DeviceScene *dscene, Scene *scen
                if(mesh->need_update) {
                        pool.push(function_bind(&Mesh::compute_bvh,
                                                mesh,
+                                               dscene,
                                                &scene->params,
                                                &progress,
                                                i,
index bc3d30a..0aea555 100644 (file)
@@ -72,7 +72,15 @@ public:
 
                int num_segments() { return num_keys - 1; }
 
-               void bounds_grow(const int k, const float3 *curve_keys, const float *curve_radius, BoundBox& bounds) const;
+               void bounds_grow(const int k,
+                                const float3 *curve_keys,
+                                const float *curve_radius,
+                                BoundBox& bounds) const;
+               void bounds_grow(const int k,
+                                const float3 *curve_keys,
+                                const float *curve_radius,
+                                const Transform& aligned_space,
+                                BoundBox& bounds) const;
        };
 
        Curve get_curve(size_t i) const
@@ -172,7 +180,11 @@ public:
                        size_t vert_offset,
                        size_t tri_offset);
        void pack_curves(Scene *scene, float4 *curve_key_co, float4 *curve_data, size_t curvekey_offset);
-       void compute_bvh(SceneParams *params, Progress *progress, int n, int total);
+       void compute_bvh(DeviceScene *dscene,
+                        SceneParams *params,
+                        Progress *progress,
+                        int n,
+                        int total);
 
        bool need_attribute(Scene *scene, AttributeStandard std);
        bool need_attribute(Scene *scene, ustring name);
index cef5adc..599222d 100644 (file)
@@ -151,7 +151,7 @@ public:
                       (isfinite(max.x) && isfinite(max.y) && isfinite(max.z));
        }
 
-       BoundBox transformed(const Transform *tfm)
+       BoundBox transformed(const Transform *tfm) const
        {
                BoundBox result = BoundBox::empty;
 
index f01db64..7aee7e5 100644 (file)
@@ -127,6 +127,19 @@ ccl_device_inline Transform make_transform(float a, float b, float c, float d,
        return t;
 }
 
+/* Constructs a coordinate frame from a normalized normal. */
+ccl_device_inline Transform make_transform_frame(const float3& N)
+{
+       const float3 dx0 = cross(make_float3(1.0f, 0.0f, 0.0f), N);
+       const float3 dx1 = cross(make_float3(0.0f, 1.0f, 0.0f), N);
+       const float3 dx = normalize((dot(dx0,dx0) > dot(dx1,dx1))?  dx0: dx1);
+       const float3 dy = normalize(cross(N, dx));
+       return make_transform(dx.x, dx.y, dx.z, 0.0f,
+                             dy.x, dy.y, dy.z, 0.0f,
+                             N.x , N.y,  N.z,  0.0f,
+                             0.0f, 0.0f, 0.0f, 1.0f);
+}
+
 #ifndef __KERNEL_GPU__
 
 ccl_device_inline Transform operator*(const Transform a, const Transform b)