[Bf-blender-cvs] [8044e5f2d77] blender2.7: Cycles: Make BVH wider prior to packing
Sergey Sharybin
noreply at git.blender.org
Wed Jan 9 12:56:34 CET 2019
Commit: 8044e5f2d771a1c3ee1a116132ddc09ce3452cbb
Author: Sergey Sharybin
Date: Tue Jan 8 18:10:32 2019 +0100
Branches: blender2.7
https://developer.blender.org/rB8044e5f2d771a1c3ee1a116132ddc09ce3452cbb
Cycles: Make BVH wider prior to packing
This allows to do more non-trivial tree modifications to make
it more dense and more friendly for vectorization.
===================================================================
M intern/cycles/bvh/bvh.cpp
M intern/cycles/bvh/bvh.h
M intern/cycles/bvh/bvh2.cpp
M intern/cycles/bvh/bvh2.h
M intern/cycles/bvh/bvh4.cpp
M intern/cycles/bvh/bvh4.h
M intern/cycles/bvh/bvh8.cpp
M intern/cycles/bvh/bvh8.h
M intern/cycles/bvh/bvh_embree.cpp
M intern/cycles/bvh/bvh_embree.h
M intern/cycles/bvh/bvh_node.cpp
M intern/cycles/bvh/bvh_node.h
===================================================================
diff --git a/intern/cycles/bvh/bvh.cpp b/intern/cycles/bvh/bvh.cpp
index ac0614e3659..af012bbf3ac 100644
--- a/intern/cycles/bvh/bvh.cpp
+++ b/intern/cycles/bvh/bvh.cpp
@@ -127,10 +127,26 @@ void BVH::build(Progress& progress, Stats*)
pack.prim_time,
params,
progress);
- BVHNode *root = bvh_build.run();
+ BVHNode *bvh2_root = bvh_build.run();
if(progress.get_cancel()) {
- if(root) root->deleteSubtree();
+ if(bvh2_root != NULL) {
+ bvh2_root->deleteSubtree();
+ }
+ return;
+ }
+
+ /* BVH builder returns tree in a binary mode (with two children per inner
+ * node. Need to adopt that for a wider BVH implementations. */
+ BVHNode *root = widen_children_nodes(bvh2_root);
+ if(root != bvh2_root) {
+ bvh2_root->deleteSubtree();
+ }
+
+ if(progress.get_cancel()) {
+ if(root != NULL) {
+ root->deleteSubtree();
+ }
return;
}
@@ -232,37 +248,6 @@ void BVH::refit_primitives(int start, int end, BoundBox& bbox, uint& visibility)
}
}
-bool BVH::leaf_check(const BVHNode *node, BVH_TYPE bvh)
-{
- if(node->is_leaf()) {
- return node->is_unaligned;
- }
- else {
- return node_is_unaligned(node, bvh);
- }
-}
-
-bool BVH::node_is_unaligned(const BVHNode *node, BVH_TYPE bvh)
-{
- const BVHNode *node0 = node->get_child(0);
- const BVHNode *node1 = node->get_child(1);
-
- switch(bvh) {
- case bvh2:
- return node0->is_unaligned || node1->is_unaligned;
- break;
- case bvh4:
- return leaf_check(node0, bvh2) || leaf_check(node1, bvh2);
- break;
- case bvh8:
- return leaf_check(node0, bvh4) || leaf_check(node1, bvh4);
- break;
- default:
- assert(0);
- return false;
- }
-}
-
/* Triangles */
void BVH::pack_triangle(int idx, float4 tri_verts[3])
diff --git a/intern/cycles/bvh/bvh.h b/intern/cycles/bvh/bvh.h
index c8ad29004d7..33a069eeaf5 100644
--- a/intern/cycles/bvh/bvh.h
+++ b/intern/cycles/bvh/bvh.h
@@ -99,8 +99,6 @@ protected:
/* Refit range of primitives. */
void refit_primitives(int start, int end, BoundBox& bbox, uint& visibility);
- static __forceinline bool leaf_check(const BVHNode *node, BVH_TYPE bvh);
- static bool node_is_unaligned(const BVHNode *node, BVH_TYPE bvh);
/* triangles and strands */
void pack_primitives();
@@ -112,6 +110,8 @@ protected:
/* for subclasses to implement */
virtual void pack_nodes(const BVHNode *root) = 0;
virtual void refit_nodes() = 0;
+
+ virtual BVHNode *widen_children_nodes(const BVHNode *root) = 0;
};
/* Pack Utility */
diff --git a/intern/cycles/bvh/bvh2.cpp b/intern/cycles/bvh/bvh2.cpp
index 4a423c16559..e5dc4e6b1a8 100644
--- a/intern/cycles/bvh/bvh2.cpp
+++ b/intern/cycles/bvh/bvh2.cpp
@@ -30,6 +30,11 @@ BVH2::BVH2(const BVHParams& params_, const vector<Object*>& objects_)
{
}
+BVHNode *BVH2::widen_children_nodes(const BVHNode *root)
+{
+ return const_cast<BVHNode *>(root);
+}
+
void BVH2::pack_leaf(const BVHStackEntry& e,
const LeafNode *leaf)
{
@@ -188,9 +193,8 @@ void BVH2::pack_nodes(const BVHNode *root)
}
else {
stack.push_back(BVHStackEntry(root, nextNodeIdx));
- nextNodeIdx += node_is_unaligned(root, bvh2)
- ? BVH_UNALIGNED_NODE_SIZE
- : BVH_NODE_SIZE;
+ nextNodeIdx += root->has_unaligned() ? BVH_UNALIGNED_NODE_SIZE
+ : BVH_NODE_SIZE;
}
while(stack.size()) {
@@ -203,7 +207,7 @@ void BVH2::pack_nodes(const BVHNode *root)
pack_leaf(e, leaf);
}
else {
- /* innner node */
+ /* inner node */
int idx[2];
for(int i = 0; i < 2; ++i) {
if(e.node->get_child(i)->is_leaf()) {
@@ -211,7 +215,7 @@ void BVH2::pack_nodes(const BVHNode *root)
}
else {
idx[i] = nextNodeIdx;
- nextNodeIdx += node_is_unaligned(e.node->get_child(i), bvh2)
+ nextNodeIdx += e.node->get_child(i)->has_unaligned()
? BVH_UNALIGNED_NODE_SIZE
: BVH_NODE_SIZE;
}
diff --git a/intern/cycles/bvh/bvh2.h b/intern/cycles/bvh/bvh2.h
index ecc697567bb..f38cdf5aca9 100644
--- a/intern/cycles/bvh/bvh2.h
+++ b/intern/cycles/bvh/bvh2.h
@@ -48,6 +48,9 @@ protected:
friend class BVH;
BVH2(const BVHParams& params, const vector<Object*>& objects);
+ /* Building process. */
+ virtual BVHNode *widen_children_nodes(const BVHNode *root) override;
+
/* pack */
void pack_nodes(const BVHNode *root);
diff --git a/intern/cycles/bvh/bvh4.cpp b/intern/cycles/bvh/bvh4.cpp
index a449587e607..a7c4cea85ce 100644
--- a/intern/cycles/bvh/bvh4.cpp
+++ b/intern/cycles/bvh/bvh4.cpp
@@ -37,6 +37,68 @@ BVH4::BVH4(const BVHParams& params_, const vector<Object*>& objects_)
params.bvh_layout = BVH_LAYOUT_BVH4;
}
+namespace {
+
+BVHNode *bvh_node_merge_children_recursively(const BVHNode *node)
+{
+ if(node->is_leaf()) {
+ return new LeafNode(*reinterpret_cast<const LeafNode *>(node));
+ }
+ /* Collect nodes of one layer deeper, allowing us to have more childrem in
+ * an inner layer. */
+ assert(node->num_children() <= 2);
+ const BVHNode *children[4];
+ const BVHNode *child0 = node->get_child(0);
+ const BVHNode *child1 = node->get_child(1);
+ int num_children = 0;
+ if(child0->is_leaf()) {
+ children[num_children++] = child0;
+ }
+ else {
+ children[num_children++] = child0->get_child(0);
+ children[num_children++] = child0->get_child(1);
+ }
+ if(child1->is_leaf()) {
+ children[num_children++] = child1;
+ }
+ else {
+ children[num_children++] = child1->get_child(0);
+ children[num_children++] = child1->get_child(1);
+ }
+ /* Merge children in subtrees. */
+ BVHNode *children4[4];
+ for(int i = 0; i < num_children; ++i) {
+ children4[i] = bvh_node_merge_children_recursively(children[i]);
+ }
+ /* Allocate new node. */
+ BVHNode *node4 = new InnerNode(node->bounds, children4, num_children);
+ /* TODO(sergey): Consider doing this from the InnerNode() constructor.
+ * But in order to do this nicely need to think of how to pass all the
+ * parameters there. */
+ if(node->is_unaligned) {
+ node4->is_unaligned = true;
+ node4->aligned_space = new Transform();
+ *node4->aligned_space = *node->aligned_space;
+ }
+ return node4;
+}
+
+} // namespace
+
+BVHNode *BVH4::widen_children_nodes(const BVHNode *root)
+{
+ if(root == NULL) {
+ return NULL;
+ }
+ if(root->is_leaf()) {
+ return const_cast<BVHNode *>(root);
+ }
+ BVHNode *root4 = bvh_node_merge_children_recursively(root);
+ /* TODO(sergey): Pack children nodes to parents which has less that 4
+ * children. */
+ return root4;
+}
+
void BVH4::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
{
float4 data[BVH_QNODE_LEAF_SIZE];
@@ -248,14 +310,14 @@ void BVH4::pack_unaligned_node(int idx,
void BVH4::pack_nodes(const BVHNode *root)
{
/* Calculate size of the arrays required. */
- const size_t num_nodes = root->getSubtreeSize(BVH_STAT_QNODE_COUNT);
+ const size_t num_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_QNODE_COUNT);
+ root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT);
node_size = (num_unaligned_nodes * BVH_UNALIGNED_QNODE_SIZE) +
(num_inner_nodes - num_unaligned_nodes) * BVH_QNODE_SIZE;
}
@@ -283,9 +345,8 @@ void BVH4::pack_nodes(const BVHNode *root)
}
else {
stack.push_back(BVHStackEntry(root, nextNodeIdx));
- nextNodeIdx += node_is_unaligned(root, bvh4)
- ? BVH_UNALIGNED_QNODE_SIZE
- : BVH_QNODE_SIZE;
+ nextNodeIdx += root->has_unaligned() ? BVH_UNALIGNED_QNODE_SIZE
+ : BVH_QNODE_SIZE;
}
while(stack.size()) {
@@ -299,44 +360,30 @@ void BVH4::pack_nodes(const BVHNode *root)
}
else {
/* Inner node. */
- const BVHNode *node = e.node;
- const BVHNode *node0 = node->get_child(0);
- const BVHNode *node1 = node->get_child(1);
/* Collect nodes. */
- const BVHNode *nodes[4];
- int numnodes = 0;
- if(node0->is_leaf()) {
- nodes[numnodes++] = node0;
- }
- else {
- nodes[numnodes++] = node0->get_child(0);
- nodes[numnodes++] = node0->get_child(1);
- }
- if(node1->is_leaf()) {
- nodes[numnodes++] = node1;
- }
- else {
- nodes[numnodes++] = node1->get_child(0);
- nodes[numnodes++] = node1->get_child(1);
- }
+ const BVHNode *children[4];
+ const int num_children = e.node->num_children();
/* Push entries on the stack. */
- for(int i = 0; i < numnodes; ++i) {
+ for(int i = 0; i < num_children; ++i) {
int idx;
- if(nodes[i]->is_leaf()) {
+ children[i] = e.node->get_child(i);
+ assert(children[i] != NULL);
+ if(children[i]->is_leaf()) {
idx = nextLeafNodeIdx++;
}
else {
idx = nextNodeIdx;
- nextNodeIdx += node_is_unaligned(nodes[i], bvh4)
+ nextNodeIdx += children[i]->has_unaligned()
? BVH_UNALIGNED_QNODE_SIZE
: BVH_QNODE_SIZE;
}
- stack.push_back(BVHStackEntry(nodes[i], idx));
+ stack.push_back(BVHStackEntry(children[i], idx));
}
/* Set node. */
- pack_inner(e, &stack[stack.size()-numnodes], numnodes);
+ pack_inner(e, &stack[stack.size() - num_children], num_children);
}
}
+
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;
diff --git a/intern/cycles/bvh/bvh4.h b/intern/cycles/bvh/bvh4.h
index 28bab2fe327..2a2a466c767 100644
--- a/intern/cycles/bvh/bvh4.h
+++ b/intern/cycles/bvh/bvh4.h
@@ -48,6 +48,9 @@ protected:
friend class BVH;
BVH4(const BVHParams& params, const vector<Object*>& objects);
+ /* Building process. */
+ virtual BVHNode *widen_children_nodes(const BVHNode *root) override;
+
/* pack */
void pack_nodes(const BVHNode *root);
diff --git a/intern/cycles/bvh/bvh8.cpp b/intern/cycles/bvh/bvh8.cpp
index b95fe572e27..af930b2f2df 100644
--- a/intern/cycles/bvh/bvh8.cpp
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list