Cycles: Store time in BVH nodes
authorSergey Sharybin <sergey.vfx@gmail.com>
Tue, 17 Jan 2017 14:34:18 +0000 (15:34 +0100)
committerSergey Sharybin <sergey.vfx@gmail.com>
Fri, 20 Jan 2017 11:46:18 +0000 (12:46 +0100)
This way we can stop traversing BVH node early on.

Gives about 2-2.5x times render time improvement with 3 BVH steps.
Hopefully this gives no measurable performance loss for scenes with
single BVH step.

Traversal is currently only implemented for QBVH, meaning old CPUs
and GPU do not benefit from this change.

intern/cycles/bvh/bvh.cpp
intern/cycles/bvh/bvh.h
intern/cycles/bvh/bvh_build.cpp
intern/cycles/bvh/bvh_node.cpp
intern/cycles/bvh/bvh_node.h
intern/cycles/bvh/bvh_params.h
intern/cycles/kernel/bvh/qbvh_shadow_all.h
intern/cycles/kernel/bvh/qbvh_traversal.h

index 4851de5..874a424 100644 (file)
@@ -845,6 +845,8 @@ void QBVH::pack_aligned_inner(const BVHStackEntry& e,
                          bounds,
                          child,
                          e.node->m_visibility,
+                         e.node->m_time_from,
+                         e.node->m_time_to,
                          num);
 }
 
@@ -852,12 +854,17 @@ void QBVH::pack_aligned_node(int idx,
                              const BoundBox *bounds,
                              const int *child,
                              const uint visibility,
+                             const float time_from,
+                             const float time_to,
                              const int num)
 {
        float4 data[BVH_QNODE_SIZE];
        memset(data, 0, sizeof(data));
 
        data[0].x = __uint_as_float(visibility & ~PATH_RAY_NODE_UNALIGNED);
+       data[0].y = time_from;
+       data[0].z = time_to;
+
        for(int i = 0; i < num; i++) {
                float3 bb_min = bounds[i].min;
                float3 bb_max = bounds[i].max;
@@ -908,6 +915,8 @@ void QBVH::pack_unaligned_inner(const BVHStackEntry& e,
                            bounds,
                            child,
                            e.node->m_visibility,
+                           e.node->m_time_from,
+                           e.node->m_time_to,
                            num);
 }
 
@@ -916,12 +925,16 @@ void QBVH::pack_unaligned_node(int idx,
                                const BoundBox *bounds,
                                const int *child,
                                const uint visibility,
+                               const float time_from,
+                               const float time_to,
                                const int num)
 {
        float4 data[BVH_UNALIGNED_QNODE_SIZE];
        memset(data, 0, sizeof(data));
 
        data[0].x = __uint_as_float(visibility | PATH_RAY_NODE_UNALIGNED);
+       data[0].y = time_from;
+       data[0].z = time_to;
 
        for(int i = 0; i < num; i++) {
                Transform space = BVHUnaligned::compute_node_transform(
@@ -1207,6 +1220,8 @@ void QBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
                                            child_bbox,
                                            &c[0],
                                            visibility,
+                                           0.0f,
+                                           1.0f,
                                            4);
                }
                else {
@@ -1214,6 +1229,8 @@ void QBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
                                          child_bbox,
                                          &c[0],
                                          visibility,
+                                         0.0f,
+                                         1.0f,
                                          4);
                }
        }
index f8fb3b5..35f4d30 100644 (file)
@@ -175,6 +175,8 @@ protected:
                               const BoundBox *bounds,
                               const int *child,
                               const uint visibility,
+                              const float time_from,
+                              const float time_to,
                               const int num);
 
        void pack_unaligned_inner(const BVHStackEntry& e,
@@ -185,6 +187,8 @@ protected:
                                 const BoundBox *bounds,
                                 const int *child,
                                 const uint visibility,
+                                const float time_from,
+                                const float time_to,
                                 const int num);
 
        /* refit */
index 21b8b98..4abd686 100644 (file)
@@ -202,11 +202,14 @@ void BVHBuild::add_reference_mesh(BoundBox& root, BoundBox& center, Mesh *mesh,
                                        BoundBox bounds = prev_bounds;
                                        bounds.grow(curr_bounds);
                                        if(bounds.valid()) {
+                                               const float prev_time = (float)(bvh_step - 1) * num_bvh_steps_inv_1;
                                                references.push_back(
                                                        BVHReference(bounds,
                                                                     j,
                                                                     i,
-                                                                    PRIMITIVE_MOTION_TRIANGLE));
+                                                                    PRIMITIVE_MOTION_TRIANGLE,
+                                                                    prev_time,
+                                                                    curr_time));
                                                root.grow(bounds);
                                                center.grow(bounds.center2());
                                        }
@@ -311,11 +314,14 @@ void BVHBuild::add_reference_mesh(BoundBox& root, BoundBox& center, Mesh *mesh,
                                                BoundBox bounds = prev_bounds;
                                                bounds.grow(curr_bounds);
                                                if(bounds.valid()) {
+                                                       const float prev_time = (float)(bvh_step - 1) * num_bvh_steps_inv_1;
                                                        int packed_type = PRIMITIVE_PACK_SEGMENT(PRIMITIVE_MOTION_CURVE, k);
                                                        references.push_back(BVHReference(bounds,
                                                                                          j,
                                                                                          i,
-                                                                                         packed_type));
+                                                                                         packed_type,
+                                                                                         prev_time,
+                                                                                         curr_time));
                                                        root.grow(bounds);
                                                        center.grow(bounds.center2());
                                                }
@@ -487,6 +493,7 @@ BVHNode* BVHBuild::run()
                else {
                        /*rotate(rootnode, 4, 5);*/
                        rootnode->update_visibility();
+                       rootnode->update_time();
                }
                if(rootnode != NULL) {
                        VLOG(1) << "BVH build statistics:\n"
@@ -836,7 +843,10 @@ BVHNode *BVHBuild::create_object_leaf_nodes(const BVHReference *ref, int start,
                prim_object[start] = ref->prim_object();
 
                uint visibility = objects[ref->prim_object()]->visibility;
-               return new LeafNode(ref->bounds(), visibility, start, start+1);
+               BVHNode *leaf_node =  new LeafNode(ref->bounds(), visibility, start, start+1);
+               leaf_node->m_time_from = ref->time_from();
+               leaf_node->m_time_to = ref->time_to();
+               return leaf_node;
        }
        else {
                int mid = num/2;
@@ -847,7 +857,10 @@ BVHNode *BVHBuild::create_object_leaf_nodes(const BVHReference *ref, int start,
                bounds.grow(leaf0->m_bounds);
                bounds.grow(leaf1->m_bounds);
 
-               return new InnerNode(bounds, leaf0, leaf1);
+               BVHNode *inner_node = new InnerNode(bounds, leaf0, leaf1);
+               inner_node->m_time_from = min(leaf0->m_time_from, leaf1->m_time_from);
+               inner_node->m_time_to = max(leaf0->m_time_to, leaf1->m_time_to);
+               return inner_node;
        }
 }
 
@@ -951,6 +964,16 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range,
                                                           visibility[i],
                                                           start_index,
                                                           start_index + num);
+                       if(true) {
+                               float time_from = 1.0f, time_to = 0.0f;
+                               for(int j = 0; j < num; ++j) {
+                                       const BVHReference &ref = p_ref[i][j];
+                                       time_from = min(time_from, ref.time_from());
+                                       time_to = max(time_to, ref.time_to());
+                               }
+                               leaf_node->m_time_from = time_from;
+                               leaf_node->m_time_to = time_to;
+                       }
                        if(alignment_found) {
                                /* Need to recalculate leaf bounds with new alignment. */
                                leaf_node->m_bounds = BoundBox::empty;
index f5cd699..67580e1 100644 (file)
@@ -176,6 +176,19 @@ uint BVHNode::update_visibility()
        return m_visibility;
 }
 
+void BVHNode::update_time()
+{
+       if(!is_leaf()) {
+               InnerNode *inner = (InnerNode*)this;
+               BVHNode *child0 = inner->children[0];
+               BVHNode *child1 = inner->children[1];
+               child0->update_time();
+               child1->update_time();
+               m_time_from = min(child0->m_time_from, child1->m_time_from);
+               m_time_to =  max(child0->m_time_to, child1->m_time_to);
+       }
+}
+
 /* Inner Node */
 
 void InnerNode::print(int depth) const
index 2faa40a..090c426 100644 (file)
@@ -47,7 +47,9 @@ class BVHNode
 {
 public:
        BVHNode() : m_is_unaligned(false),
-                   m_aligned_space(NULL)
+                   m_aligned_space(NULL),
+                   m_time_from(0.0f),
+                   m_time_to(1.0f)
        {
        }
 
@@ -91,12 +93,15 @@ public:
        void deleteSubtree();
 
        uint update_visibility();
+       void update_time();
 
        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;
+
+       float m_time_from, m_time_to;
 };
 
 class InnerNode : public BVHNode
index 233c7ad..65f9da1 100644 (file)
@@ -130,8 +130,15 @@ class BVHReference
 public:
        __forceinline BVHReference() {}
 
-       __forceinline BVHReference(const BoundBox& bounds_, int prim_index_, int prim_object_, int prim_type)
-       : rbounds(bounds_)
+       __forceinline BVHReference(const BoundBox& bounds_,
+                                  int prim_index_,
+                                  int prim_object_,
+                                  int prim_type,
+                                  float time_from = 0.0f,
+                                  float time_to = 1.0f)
+               : rbounds(bounds_),
+                 time_from_(time_from),
+                 time_to_(time_to)
        {
                rbounds.min.w = __int_as_float(prim_index_);
                rbounds.max.w = __int_as_float(prim_object_);
@@ -142,6 +149,9 @@ public:
        __forceinline int prim_index() const { return __float_as_int(rbounds.min.w); }
        __forceinline int prim_object() const { return __float_as_int(rbounds.max.w); }
        __forceinline int prim_type() const { return type; }
+       __forceinline float time_from() const { return time_from_; }
+       __forceinline float time_to() const { return time_to_; }
+
 
        BVHReference& operator=(const BVHReference &arg) {
                if(&arg != this) {
@@ -150,9 +160,11 @@ public:
                return *this;
        }
 
+
 protected:
        BoundBox rbounds;
        uint type;
+       float time_from_, time_to_;
 };
 
 /* BVH Range
index b2e9972..607295f 100644 (file)
@@ -106,14 +106,20 @@ ccl_device bool BVH_FUNCTION_FULL_NAME(QBVH)(KernelGlobals *kg,
                        while(node_addr >= 0 && node_addr != ENTRYPOINT_SENTINEL) {
                                float4 inodes = kernel_tex_fetch(__bvh_nodes, node_addr+0);
 
+                               if(false
 #ifdef __VISIBILITY_FLAG__
-                               if((__float_as_uint(inodes.x) & PATH_RAY_SHADOW) == 0) {
+                                  || ((__float_as_uint(inodes.x) & PATH_RAY_SHADOW) == 0)
+#endif
+#if BVH_FEATURE(BVH_MOTION)
+                                  || UNLIKELY(ray->time < inodes.y)
+                                  || UNLIKELY(ray->time > inodes.z)
+#endif
+                               ) {
                                        /* Pop. */
                                        node_addr = traversal_stack[stack_ptr].addr;
                                        --stack_ptr;
                                        continue;
                                }
-#endif
 
                                ssef dist;
                                int child_mask = NODE_INTERSECT(kg,
index 1d5643c..10ae7be 100644 (file)
@@ -117,6 +117,10 @@ ccl_device bool BVH_FUNCTION_FULL_NAME(QBVH)(KernelGlobals *kg,
                                float4 inodes = kernel_tex_fetch(__bvh_nodes, node_addr+0);
 
                                if(UNLIKELY(node_dist > isect->t)
+#if BVH_FEATURE(BVH_MOTION)
+                                  || UNLIKELY(ray->time < inodes.y)
+                                  || UNLIKELY(ray->time > inodes.z)
+#endif
 #ifdef __VISIBILITY_FLAG__
                                   || (__float_as_uint(inodes.x) & visibility) == 0)
 #endif