Cycles: Store time in BVH nodes

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.
This commit is contained in:
Sergey Sharybin 2017-01-17 15:34:18 +01:00
parent c4890cd354
commit 1ad04c7d65
8 changed files with 93 additions and 9 deletions

View 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);
}
}

View 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 */

View 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;

View 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

View 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

View 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

View 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,

View 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