Cycles: Make BVH wider prior to packing
[blender.git] / intern / cycles / bvh / bvh2.cpp
1 /*
2  * Adapted from code copyright 2009-2010 NVIDIA Corporation
3  * Modifications Copyright 2011, Blender Foundation.
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17
18 #include "bvh/bvh2.h"
19
20 #include "render/mesh.h"
21 #include "render/object.h"
22
23 #include "bvh/bvh_node.h"
24 #include "bvh/bvh_unaligned.h"
25
26 CCL_NAMESPACE_BEGIN
27
28 BVH2::BVH2(const BVHParams& params_, const vector<Object*>& objects_)
29 : BVH(params_, objects_)
30 {
31 }
32
33 BVHNode *BVH2::widen_children_nodes(const BVHNode *root)
34 {
35         return const_cast<BVHNode *>(root);
36 }
37
38 void BVH2::pack_leaf(const BVHStackEntry& e,
39                      const LeafNode *leaf)
40 {
41         assert(e.idx + BVH_NODE_LEAF_SIZE <= pack.leaf_nodes.size());
42         float4 data[BVH_NODE_LEAF_SIZE];
43         memset(data, 0, sizeof(data));
44         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->lo] == -1) {
45                 /* object */
46                 data[0].x = __int_as_float(~(leaf->lo));
47                 data[0].y = __int_as_float(0);
48         }
49         else {
50                 /* triangle */
51                 data[0].x = __int_as_float(leaf->lo);
52                 data[0].y = __int_as_float(leaf->hi);
53         }
54         data[0].z = __uint_as_float(leaf->visibility);
55         if(leaf->num_triangles() != 0) {
56                 data[0].w = __uint_as_float(pack.prim_type[leaf->lo]);
57         }
58
59         memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_NODE_LEAF_SIZE);
60 }
61
62 void BVH2::pack_inner(const BVHStackEntry& e,
63                       const BVHStackEntry& e0,
64                       const BVHStackEntry& e1)
65 {
66         if(e0.node->is_unaligned || e1.node->is_unaligned) {
67                 pack_unaligned_inner(e, e0, e1);
68         } else {
69                 pack_aligned_inner(e, e0, e1);
70         }
71 }
72
73 void BVH2::pack_aligned_inner(const BVHStackEntry& e,
74                               const BVHStackEntry& e0,
75                               const BVHStackEntry& e1)
76 {
77         pack_aligned_node(e.idx,
78                           e0.node->bounds, e1.node->bounds,
79                           e0.encodeIdx(), e1.encodeIdx(),
80                           e0.node->visibility, e1.node->visibility);
81 }
82
83 void BVH2::pack_aligned_node(int idx,
84                              const BoundBox& b0,
85                              const BoundBox& b1,
86                              int c0, int c1,
87                              uint visibility0, uint visibility1)
88 {
89         assert(idx + BVH_NODE_SIZE <= pack.nodes.size());
90         assert(c0 < 0 || c0 < pack.nodes.size());
91         assert(c1 < 0 || c1 < pack.nodes.size());
92
93         int4 data[BVH_NODE_SIZE] = {
94                 make_int4(visibility0 & ~PATH_RAY_NODE_UNALIGNED,
95                           visibility1 & ~PATH_RAY_NODE_UNALIGNED,
96                           c0, c1),
97                 make_int4(__float_as_int(b0.min.x),
98                           __float_as_int(b1.min.x),
99                           __float_as_int(b0.max.x),
100                           __float_as_int(b1.max.x)),
101                 make_int4(__float_as_int(b0.min.y),
102                           __float_as_int(b1.min.y),
103                           __float_as_int(b0.max.y),
104                           __float_as_int(b1.max.y)),
105                 make_int4(__float_as_int(b0.min.z),
106                           __float_as_int(b1.min.z),
107                           __float_as_int(b0.max.z),
108                           __float_as_int(b1.max.z)),
109         };
110
111         memcpy(&pack.nodes[idx], data, sizeof(int4)*BVH_NODE_SIZE);
112 }
113
114 void BVH2::pack_unaligned_inner(const BVHStackEntry& e,
115                                 const BVHStackEntry& e0,
116                                 const BVHStackEntry& e1)
117 {
118         pack_unaligned_node(e.idx,
119                             e0.node->get_aligned_space(),
120                             e1.node->get_aligned_space(),
121                             e0.node->bounds,
122                             e1.node->bounds,
123                             e0.encodeIdx(), e1.encodeIdx(),
124                             e0.node->visibility, e1.node->visibility);
125 }
126
127 void BVH2::pack_unaligned_node(int idx,
128                                const Transform& aligned_space0,
129                                const Transform& aligned_space1,
130                                const BoundBox& bounds0,
131                                const BoundBox& bounds1,
132                                int c0, int c1,
133                                uint visibility0, uint visibility1)
134 {
135         assert(idx + BVH_UNALIGNED_NODE_SIZE <= pack.nodes.size());
136         assert(c0 < 0 || c0 < pack.nodes.size());
137         assert(c1 < 0 || c1 < pack.nodes.size());
138
139         float4 data[BVH_UNALIGNED_NODE_SIZE];
140         Transform space0 = BVHUnaligned::compute_node_transform(bounds0,
141                                                                 aligned_space0);
142         Transform space1 = BVHUnaligned::compute_node_transform(bounds1,
143                                                                 aligned_space1);
144         data[0] = make_float4(__int_as_float(visibility0 | PATH_RAY_NODE_UNALIGNED),
145                               __int_as_float(visibility1 | PATH_RAY_NODE_UNALIGNED),
146                               __int_as_float(c0),
147                               __int_as_float(c1));
148
149         data[1] = space0.x;
150         data[2] = space0.y;
151         data[3] = space0.z;
152         data[4] = space1.x;
153         data[5] = space1.y;
154         data[6] = space1.z;
155
156         memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_UNALIGNED_NODE_SIZE);
157 }
158
159 void BVH2::pack_nodes(const BVHNode *root)
160 {
161         const size_t num_nodes = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
162         const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
163         assert(num_leaf_nodes <= num_nodes);
164         const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
165         size_t node_size;
166         if(params.use_unaligned_nodes) {
167                 const size_t num_unaligned_nodes =
168                         root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT);
169                 node_size = (num_unaligned_nodes * BVH_UNALIGNED_NODE_SIZE) +
170                             (num_inner_nodes - num_unaligned_nodes) * BVH_NODE_SIZE;
171         }
172         else {
173                 node_size = num_inner_nodes * BVH_NODE_SIZE;
174         }
175         /* Resize arrays */
176         pack.nodes.clear();
177         pack.leaf_nodes.clear();
178         /* For top level BVH, first merge existing BVH's so we know the offsets. */
179         if(params.top_level) {
180                 pack_instances(node_size, num_leaf_nodes*BVH_NODE_LEAF_SIZE);
181         }
182         else {
183                 pack.nodes.resize(node_size);
184                 pack.leaf_nodes.resize(num_leaf_nodes*BVH_NODE_LEAF_SIZE);
185         }
186
187         int nextNodeIdx = 0, nextLeafNodeIdx = 0;
188
189         vector<BVHStackEntry> stack;
190         stack.reserve(BVHParams::MAX_DEPTH*2);
191         if(root->is_leaf()) {
192                 stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++));
193         }
194         else {
195                 stack.push_back(BVHStackEntry(root, nextNodeIdx));
196                 nextNodeIdx += root->has_unaligned() ? BVH_UNALIGNED_NODE_SIZE
197                                                      : BVH_NODE_SIZE;
198         }
199
200         while(stack.size()) {
201                 BVHStackEntry e = stack.back();
202                 stack.pop_back();
203
204                 if(e.node->is_leaf()) {
205                         /* leaf node */
206                         const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
207                         pack_leaf(e, leaf);
208                 }
209                 else {
210                         /* inner node */
211                         int idx[2];
212                         for(int i = 0; i < 2; ++i) {
213                                 if(e.node->get_child(i)->is_leaf()) {
214                                         idx[i] = nextLeafNodeIdx++;
215                                 }
216                                 else {
217                                         idx[i] = nextNodeIdx;
218                                         nextNodeIdx += e.node->get_child(i)->has_unaligned()
219                                                                ? BVH_UNALIGNED_NODE_SIZE
220                                                                : BVH_NODE_SIZE;
221                                 }
222                         }
223
224                         stack.push_back(BVHStackEntry(e.node->get_child(0), idx[0]));
225                         stack.push_back(BVHStackEntry(e.node->get_child(1), idx[1]));
226
227                         pack_inner(e, stack[stack.size()-2], stack[stack.size()-1]);
228                 }
229         }
230         assert(node_size == nextNodeIdx);
231         /* root index to start traversal at, to handle case of single leaf node */
232         pack.root_index = (root->is_leaf())? -1: 0;
233 }
234
235 void BVH2::refit_nodes()
236 {
237         assert(!params.top_level);
238
239         BoundBox bbox = BoundBox::empty;
240         uint visibility = 0;
241         refit_node(0, (pack.root_index == -1)? true: false, bbox, visibility);
242 }
243
244 void BVH2::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
245 {
246         if(leaf) {
247                 /* refit leaf node */
248                 assert(idx + BVH_NODE_LEAF_SIZE <= pack.leaf_nodes.size());
249                 const int4 *data = &pack.leaf_nodes[idx];
250                 const int c0 = data[0].x;
251                 const int c1 = data[0].y;
252
253                 BVH::refit_primitives(c0, c1, bbox, visibility);
254
255                 /* TODO(sergey): De-duplicate with pack_leaf(). */
256                 float4 leaf_data[BVH_NODE_LEAF_SIZE];
257                 leaf_data[0].x = __int_as_float(c0);
258                 leaf_data[0].y = __int_as_float(c1);
259                 leaf_data[0].z = __uint_as_float(visibility);
260                 leaf_data[0].w = __uint_as_float(data[0].w);
261                 memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_NODE_LEAF_SIZE);
262         }
263         else {
264                 assert(idx + BVH_NODE_SIZE <= pack.nodes.size());
265
266                 const int4 *data = &pack.nodes[idx];
267                 const bool is_unaligned = (data[0].x & PATH_RAY_NODE_UNALIGNED) != 0;
268                 const int c0 = data[0].z;
269                 const int c1 = data[0].w;
270                 /* refit inner node, set bbox from children */
271                 BoundBox bbox0 = BoundBox::empty, bbox1 = BoundBox::empty;
272                 uint visibility0 = 0, visibility1 = 0;
273
274                 refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0);
275                 refit_node((c1 < 0)? -c1-1: c1, (c1 < 0), bbox1, visibility1);
276
277                 if(is_unaligned) {
278                         Transform aligned_space = transform_identity();
279                         pack_unaligned_node(idx,
280                                             aligned_space, aligned_space,
281                                             bbox0, bbox1,
282                                             c0, c1,
283                                             visibility0,
284                                             visibility1);
285                 }
286                 else {
287                         pack_aligned_node(idx,
288                                           bbox0, bbox1,
289                                           c0, c1,
290                                           visibility0,
291                                           visibility1);
292                 }
293
294                 bbox.grow(bbox0);
295                 bbox.grow(bbox1);
296                 visibility = visibility0|visibility1;
297         }
298 }
299
300 CCL_NAMESPACE_END