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 4851de5b4816db57fe984543d3c264d0d1e396b6..874a4246d1d60887969c9eee7a5391ede022bb64 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 f8fb3b568caf3373dbc0ffef128d7bf4f0392c41..35f4d305883bdcccc485c12fab4f18a36ac02310 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 21b8b980405d4b626e1d9f5709380303c2297212..4abd686cc6eb470904820591a630542738b13fd0 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 f5cd699bdf4520da6aa1e53fe8e909a112837ba8..67580e1bc7b47d75c5d02adb02546c26b8637998 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 2faa40ab657b112f649f3204ac4d712a2645dd37..090c426de56e1fa23b3151ac5a556f455f80f0b2 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 233c7adacba8b0e164e1c59269d5030e0fd3b6b4..65f9da1c194e834e06b5fc6de5176d0a253d1c4a 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 b2e99725626a31415596648a7a140a77bcf13f1b..607295f9ed5b9de95ef03308b946ace7c19dec24 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 1d5643ca540a29342456818d19eee802f1100844..10ae7bee8524701adbc7f0b3ee096145550a8c3b 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