diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2019-01-08 20:10:32 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2019-01-09 14:14:20 +0300 |
commit | 8044e5f2d771a1c3ee1a116132ddc09ce3452cbb (patch) | |
tree | a30b0f3f2e90b197e9ebaebae6ceab108d9548d2 /intern/cycles/bvh | |
parent | b486088218f66810b97294f38f246e4650d32f2b (diff) |
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.
Diffstat (limited to 'intern/cycles/bvh')
-rw-r--r-- | intern/cycles/bvh/bvh.cpp | 51 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh.h | 4 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh2.cpp | 14 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh2.h | 3 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh4.cpp | 105 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh4.h | 3 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh8.cpp | 164 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh8.h | 3 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_embree.cpp | 6 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_embree.h | 4 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_node.cpp | 99 | ||||
-rw-r--r-- | intern/cycles/bvh/bvh_node.h | 129 |
12 files changed, 331 insertions, 254 deletions
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 +++ b/intern/cycles/bvh/bvh8.cpp @@ -41,6 +41,96 @@ BVH8::BVH8(const BVHParams& params_, const vector<Object*>& objects_) { } +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 two layer deeper, allowing us to have more childrem in + * an inner layer. */ + assert(node->num_children() <= 2); + const BVHNode *children[8]; + 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 { + const BVHNode *child00 = child0->get_child(0), + *child01 = child0->get_child(1); + if(child00->is_leaf()) { + children[num_children++] = child00; + } + else { + children[num_children++] = child00->get_child(0); + children[num_children++] = child00->get_child(1); + } + if(child01->is_leaf()) { + children[num_children++] = child01; + } + else { + children[num_children++] = child01->get_child(0); + children[num_children++] = child01->get_child(1); + } + } + if(child1->is_leaf()) { + children[num_children++] = child1; + } + else { + const BVHNode *child10 = child1->get_child(0), + *child11 = child1->get_child(1); + if(child10->is_leaf()) { + children[num_children++] = child10; + } + else { + children[num_children++] = child10->get_child(0); + children[num_children++] = child10->get_child(1); + } + if(child11->is_leaf()) { + children[num_children++] = child11; + } + else { + children[num_children++] = child11->get_child(0); + children[num_children++] = child11->get_child(1); + } + } + /* Merge children in subtrees. */ + BVHNode *children4[8]; + for(int i = 0; i < num_children; ++i) { + children4[i] = bvh_node_merge_children_recursively(children[i]); + } + /* Allocate new node. */ + BVHNode *node8 = 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) { + node8->is_unaligned = true; + node8->aligned_space = new Transform(); + *node8->aligned_space = *node->aligned_space; + } + return node8; +} + +} // namespace + +BVHNode *BVH8::widen_children_nodes(const BVHNode *root) +{ + if(root == NULL) { + return NULL; + } + if(root->is_leaf()) { + return const_cast<BVHNode *>(root); + } + BVHNode *root8 = bvh_node_merge_children_recursively(root); + /* TODO(sergey): Pack children nodes to parents which has less that 4 + * children. */ + return root8; +} + void BVH8::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf) { float4 data[BVH_ONODE_LEAF_SIZE]; @@ -252,14 +342,14 @@ void BVH8::pack_unaligned_node(int idx, void BVH8::pack_nodes(const BVHNode *root) { /* Calculate size of the arrays required. */ - const size_t num_nodes = root->getSubtreeSize(BVH_STAT_ONODE_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_ONODE_COUNT); + root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT); node_size = (num_unaligned_nodes * BVH_UNALIGNED_ONODE_SIZE) + (num_inner_nodes - num_unaligned_nodes) * BVH_ONODE_SIZE; } @@ -287,9 +377,8 @@ void BVH8::pack_nodes(const BVHNode *root) } else { stack.push_back(BVHStackEntry(root, nextNodeIdx)); - nextNodeIdx += node_is_unaligned(root, bvh8) - ? BVH_UNALIGNED_ONODE_SIZE - : BVH_ONODE_SIZE; + nextNodeIdx += root->has_unaligned() ? BVH_UNALIGNED_ONODE_SIZE + : BVH_ONODE_SIZE; } while(stack.size()) { @@ -303,72 +392,29 @@ void BVH8::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[8]; - int numnodes = 0; - if(node0->is_leaf()) { - nodes[numnodes++] = node0; - } - else { - const BVHNode *node00 = node0->get_child(0), - *node01 = node0->get_child(1); - if(node00->is_leaf()) { - nodes[numnodes++] = node00; - } - else { - nodes[numnodes++] = node00->get_child(0); - nodes[numnodes++] = node00->get_child(1); - } - if(node01->is_leaf()) { - nodes[numnodes++] = node01; - } - else { - nodes[numnodes++] = node01->get_child(0); - nodes[numnodes++] = node01->get_child(1); - } - } - if(node1->is_leaf()) { - nodes[numnodes++] = node1; - } - else { - const BVHNode *node10 = node1->get_child(0), - *node11 = node1->get_child(1); - if(node10->is_leaf()) { - nodes[numnodes++] = node10; - } - else { - nodes[numnodes++] = node10->get_child(0); - nodes[numnodes++] = node10->get_child(1); - } - if(node11->is_leaf()) { - nodes[numnodes++] = node11; - } - else { - nodes[numnodes++] = node11->get_child(0); - nodes[numnodes++] = node11->get_child(1); - } - } + const BVHNode *children[8]; + 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); + if(children[i]->is_leaf()) { idx = nextLeafNodeIdx++; } else { idx = nextNodeIdx; - nextNodeIdx += node_is_unaligned(nodes[i], bvh8) - ? BVH_UNALIGNED_ONODE_SIZE - : BVH_ONODE_SIZE; + nextNodeIdx += children[i]->has_unaligned() + ? BVH_UNALIGNED_ONODE_SIZE + : BVH_ONODE_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/bvh8.h b/intern/cycles/bvh/bvh8.h index 834daf3abce..84f82538c0f 100644 --- a/intern/cycles/bvh/bvh8.h +++ b/intern/cycles/bvh/bvh8.h @@ -59,6 +59,9 @@ protected: friend class BVH; BVH8(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/bvh_embree.cpp b/intern/cycles/bvh/bvh_embree.cpp index 2d6efe8dad5..8415d80c4a8 100644 --- a/intern/cycles/bvh/bvh_embree.cpp +++ b/intern/cycles/bvh/bvh_embree.cpp @@ -436,6 +436,12 @@ void BVHEmbree::build(Progress& progress, Stats *stats_) stats = NULL; } +BVHNode *BVHEmbree::widen_children_nodes(const BVHNode * /*root*/) +{ + assert(!"Must not be called."); + return NULL; +} + void BVHEmbree::add_object(Object *ob, int i) { Mesh *mesh = ob->mesh; diff --git a/intern/cycles/bvh/bvh_embree.h b/intern/cycles/bvh/bvh_embree.h index 9990826ba98..983b6dc07da 100644 --- a/intern/cycles/bvh/bvh_embree.h +++ b/intern/cycles/bvh/bvh_embree.h @@ -40,6 +40,10 @@ public: virtual ~BVHEmbree(); RTCScene scene; static void destroy(RTCScene); + + /* Building process. */ + virtual BVHNode *widen_children_nodes(const BVHNode *root) override; + protected: friend class BVH; BVHEmbree(const BVHParams& params, const vector<Object*>& objects); diff --git a/intern/cycles/bvh/bvh_node.cpp b/intern/cycles/bvh/bvh_node.cpp index fd8b4977699..dc0255c4039 100644 --- a/intern/cycles/bvh/bvh_node.cpp +++ b/intern/cycles/bvh/bvh_node.cpp @@ -47,69 +47,6 @@ int BVHNode::getSubtreeSize(BVH_STAT stat) const case BVH_STAT_CHILDNODE_COUNT: cnt = num_children(); break; - case BVH_STAT_QNODE_COUNT: - cnt = 1; - for(int i = 0; i < num_children(); i++) { - BVHNode *node = get_child(i); - if(node->is_leaf()) { - cnt += 1; - } - else { - for(int j = 0; j < node->num_children(); j++) { - cnt += node->get_child(j)->getSubtreeSize(stat); - } - } - } - return cnt; - case BVH_STAT_ONODE_COUNT: - cnt = 1; - for(int i = 0; i < num_children(); i++) { - BVHNode *node = get_child(i); - if(node->is_leaf()) { - cnt += 1; - } - else { - for(int j = 0; j < node->num_children(); j++) - { - BVHNode *node_next = node->get_child(j); - if(node_next->is_leaf()) { - cnt += 1; - } - else { - for(int k = 0; k < node_next->num_children(); k++) { - cnt += node_next->get_child(k)->getSubtreeSize(stat); - } - } - } - } - } - return cnt; - case BVH_STAT_UNALIGNED_INNER_ONODE_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++) { - BVHNode *node_next = node->get_child(j); - if(node_next->is_leaf()) { - has_unaligned |= node_next->is_unaligned; - } - else { - for(int k = 0; k < node_next->num_children(); k++) { - cnt += node_next->get_child(k)->getSubtreeSize(stat); - has_unaligned |= node_next->get_child(k)->is_unaligned; - } - } - } - } - } - cnt += has_unaligned? 1: 0; - } - return cnt; case BVH_STAT_ALIGNED_COUNT: if(!is_unaligned) { cnt = 1; @@ -138,42 +75,6 @@ int BVHNode::getSubtreeSize(BVH_STAT stat) const 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; diff --git a/intern/cycles/bvh/bvh_node.h b/intern/cycles/bvh/bvh_node.h index 65d5df01158..8a2cffeb056 100644 --- a/intern/cycles/bvh/bvh_node.h +++ b/intern/cycles/bvh/bvh_node.h @@ -29,18 +29,13 @@ enum BVH_STAT { BVH_STAT_LEAF_COUNT, 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, BVH_STAT_DEPTH, - BVH_STAT_ONODE_COUNT, - BVH_STAT_UNALIGNED_INNER_ONODE_COUNT, }; class BVHParams; @@ -48,13 +43,6 @@ class BVHParams; class BVHNode { public: - BVHNode() : is_unaligned(false), - aligned_space(NULL), - time_from(0.0f), - time_to(1.0f) - { - } - virtual ~BVHNode() { delete aligned_space; @@ -85,6 +73,19 @@ public: return *aligned_space; } + inline bool has_unaligned() const + { + if(is_leaf()) { + return false; + } + for(int i = 0; i < num_children(); ++i) { + if(get_child(i)->is_unaligned) { + return true; + } + } + return false; + } + // Subtree functions int getSubtreeSize(BVH_STAT stat=BVH_STAT_NODE_COUNT) const; float computeSubtreeSAHCost(const BVHParams& p, float probability = 1.0f) const; @@ -105,56 +106,130 @@ public: Transform *aligned_space; float time_from, time_to; + +protected: + explicit BVHNode(const BoundBox& bounds) + : bounds(bounds), + visibility(0), + is_unaligned(false), + aligned_space(NULL), + time_from(0.0f), + time_to(1.0f) + { + } + + explicit BVHNode(const BVHNode& other) + : bounds(other.bounds), + visibility(other.visibility), + is_unaligned(other.is_unaligned), + aligned_space(NULL), + time_from(other.time_from), + time_to(other.time_to) + { + if(other.aligned_space != NULL) { + assert(other.is_unaligned); + aligned_space = new Transform(); + *aligned_space = *other.aligned_space; + } + else { + assert(!other.is_unaligned); + } + } }; class InnerNode : public BVHNode { public: + static constexpr int kNumMaxChildren = 8; + InnerNode(const BoundBox& bounds, BVHNode* child0, BVHNode* child1) + : BVHNode(bounds), + num_children_(2) { - this->bounds = bounds; children[0] = child0; children[1] = child1; + reset_unused_children(); - if(child0 && child1) - visibility = child0->visibility|child1->visibility; - else - visibility = 0; /* happens on build cancel */ + if(child0 && child1) { + visibility = child0->visibility | child1->visibility; + } + else { + /* Happens on build cancel. */ + visibility = 0; + } } + InnerNode(const BoundBox& bounds, + BVHNode** children, + const int num_children) + : BVHNode(bounds), + num_children_(num_children) + { + visibility = 0; + time_from = FLT_MAX; + time_to = -FLT_MAX; + for(int i = 0; i < num_children; ++i) { + assert(children[i] != NULL); + visibility |= children[i]->visibility; + this->children[i] = children[i]; + time_from = min(time_from, children[i]->time_from); + time_to = max(time_to, children[i]->time_to); + } + reset_unused_children(); + } + + /* NOTE: This function is only used during binary BVH builder, and it + * supposed to be configured to have 2 children which will be filled in in a + * bit. But this is important to have children reset to NULL. */ explicit InnerNode(const BoundBox& bounds) + : BVHNode(bounds), + num_children_(0) { - this->bounds = bounds; + reset_unused_children(); visibility = 0; - children[0] = NULL; - children[1] = NULL; + num_children_ = 2; } bool is_leaf() const { return false; } - int num_children() const { return 2; } - BVHNode *get_child(int i) const{ assert(i>=0 && i<2); return children[i]; } + int num_children() const { return num_children_; } + BVHNode *get_child(int i) const + { + assert(i >= 0 && i < num_children_); + return children[i]; + } void print(int depth) const; - BVHNode *children[2]; + int num_children_; + BVHNode *children[kNumMaxChildren]; + +protected: + void reset_unused_children() + { + for(int i = num_children_; i < kNumMaxChildren; ++i) { + children[i] = NULL; + } + } }; class LeafNode : public BVHNode { public: LeafNode(const BoundBox& bounds, uint visibility, int lo, int hi) - : lo(lo), + : BVHNode(bounds), + lo(lo), hi(hi) { this->bounds = bounds; this->visibility = visibility; } - LeafNode(const LeafNode& s) - : BVHNode() + LeafNode(const LeafNode& other) + : BVHNode(other), + lo(other.lo), + hi(other.hi) { - *this = s; } bool is_leaf() const { return true; } |