4a423c165591c82ae64ebaf1ea679dee68933009
[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 void BVH2::pack_leaf(const BVHStackEntry& e,
34                      const LeafNode *leaf)
35 {
36         assert(e.idx + BVH_NODE_LEAF_SIZE <= pack.leaf_nodes.size());
37         float4 data[BVH_NODE_LEAF_SIZE];
38         memset(data, 0, sizeof(data));
39         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->lo] == -1) {
40                 /* object */
41                 data[0].x = __int_as_float(~(leaf->lo));
42                 data[0].y = __int_as_float(0);
43         }
44         else {
45                 /* triangle */
46                 data[0].x = __int_as_float(leaf->lo);
47                 data[0].y = __int_as_float(leaf->hi);
48         }
49         data[0].z = __uint_as_float(leaf->visibility);
50         if(leaf->num_triangles() != 0) {
51                 data[0].w = __uint_as_float(pack.prim_type[leaf->lo]);
52         }
53
54         memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_NODE_LEAF_SIZE);
55 }
56
57 void BVH2::pack_inner(const BVHStackEntry& e,
58                       const BVHStackEntry& e0,
59                       const BVHStackEntry& e1)
60 {
61         if(e0.node->is_unaligned || e1.node->is_unaligned) {
62                 pack_unaligned_inner(e, e0, e1);
63         } else {
64                 pack_aligned_inner(e, e0, e1);
65         }
66 }
67
68 void BVH2::pack_aligned_inner(const BVHStackEntry& e,
69                               const BVHStackEntry& e0,
70                               const BVHStackEntry& e1)
71 {
72         pack_aligned_node(e.idx,
73                           e0.node->bounds, e1.node->bounds,
74                           e0.encodeIdx(), e1.encodeIdx(),
75                           e0.node->visibility, e1.node->visibility);
76 }
77
78 void BVH2::pack_aligned_node(int idx,
79                              const BoundBox& b0,
80                              const BoundBox& b1,
81                              int c0, int c1,
82                              uint visibility0, uint visibility1)
83 {
84         assert(idx + BVH_NODE_SIZE <= pack.nodes.size());
85         assert(c0 < 0 || c0 < pack.nodes.size());
86         assert(c1 < 0 || c1 < pack.nodes.size());
87
88         int4 data[BVH_NODE_SIZE] = {
89                 make_int4(visibility0 & ~PATH_RAY_NODE_UNALIGNED,
90                           visibility1 & ~PATH_RAY_NODE_UNALIGNED,
91                           c0, c1),
92                 make_int4(__float_as_int(b0.min.x),
93                           __float_as_int(b1.min.x),
94                           __float_as_int(b0.max.x),
95                           __float_as_int(b1.max.x)),
96                 make_int4(__float_as_int(b0.min.y),
97                           __float_as_int(b1.min.y),
98                           __float_as_int(b0.max.y),
99                           __float_as_int(b1.max.y)),
100                 make_int4(__float_as_int(b0.min.z),
101                           __float_as_int(b1.min.z),
102                           __float_as_int(b0.max.z),
103                           __float_as_int(b1.max.z)),
104         };
105
106         memcpy(&pack.nodes[idx], data, sizeof(int4)*BVH_NODE_SIZE);
107 }
108
109 void BVH2::pack_unaligned_inner(const BVHStackEntry& e,
110                                 const BVHStackEntry& e0,
111                                 const BVHStackEntry& e1)
112 {
113         pack_unaligned_node(e.idx,
114                             e0.node->get_aligned_space(),
115                             e1.node->get_aligned_space(),
116                             e0.node->bounds,
117                             e1.node->bounds,
118                             e0.encodeIdx(), e1.encodeIdx(),
119                             e0.node->visibility, e1.node->visibility);
120 }
121
122 void BVH2::pack_unaligned_node(int idx,
123                                const Transform& aligned_space0,
124                                const Transform& aligned_space1,
125                                const BoundBox& bounds0,
126                                const BoundBox& bounds1,
127                                int c0, int c1,
128                                uint visibility0, uint visibility1)
129 {
130         assert(idx + BVH_UNALIGNED_NODE_SIZE <= pack.nodes.size());
131         assert(c0 < 0 || c0 < pack.nodes.size());
132         assert(c1 < 0 || c1 < pack.nodes.size());
133
134         float4 data[BVH_UNALIGNED_NODE_SIZE];
135         Transform space0 = BVHUnaligned::compute_node_transform(bounds0,
136                                                                 aligned_space0);
137         Transform space1 = BVHUnaligned::compute_node_transform(bounds1,
138                                                                 aligned_space1);
139         data[0] = make_float4(__int_as_float(visibility0 | PATH_RAY_NODE_UNALIGNED),
140                               __int_as_float(visibility1 | PATH_RAY_NODE_UNALIGNED),
141                               __int_as_float(c0),
142                               __int_as_float(c1));
143
144         data[1] = space0.x;
145         data[2] = space0.y;
146         data[3] = space0.z;
147         data[4] = space1.x;
148         data[5] = space1.y;
149         data[6] = space1.z;
150
151         memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_UNALIGNED_NODE_SIZE);
152 }
153
154 void BVH2::pack_nodes(const BVHNode *root)
155 {
156         const size_t num_nodes = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
157         const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
158         assert(num_leaf_nodes <= num_nodes);
159         const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
160         size_t node_size;
161         if(params.use_unaligned_nodes) {
162                 const size_t num_unaligned_nodes =
163                         root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT);
164                 node_size = (num_unaligned_nodes * BVH_UNALIGNED_NODE_SIZE) +
165                             (num_inner_nodes - num_unaligned_nodes) * BVH_NODE_SIZE;
166         }
167         else {
168                 node_size = num_inner_nodes * BVH_NODE_SIZE;
169         }
170         /* Resize arrays */
171         pack.nodes.clear();
172         pack.leaf_nodes.clear();
173         /* For top level BVH, first merge existing BVH's so we know the offsets. */
174         if(params.top_level) {
175                 pack_instances(node_size, num_leaf_nodes*BVH_NODE_LEAF_SIZE);
176         }
177         else {
178                 pack.nodes.resize(node_size);
179                 pack.leaf_nodes.resize(num_leaf_nodes*BVH_NODE_LEAF_SIZE);
180         }
181
182         int nextNodeIdx = 0, nextLeafNodeIdx = 0;
183
184         vector<BVHStackEntry> stack;
185         stack.reserve(BVHParams::MAX_DEPTH*2);
186         if(root->is_leaf()) {
187                 stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++));
188         }
189         else {
190                 stack.push_back(BVHStackEntry(root, nextNodeIdx));
191                 nextNodeIdx += node_is_unaligned(root, bvh2)
192                                        ? BVH_UNALIGNED_NODE_SIZE
193                                        : BVH_NODE_SIZE;
194         }
195
196         while(stack.size()) {
197                 BVHStackEntry e = stack.back();
198                 stack.pop_back();
199
200                 if(e.node->is_leaf()) {
201                         /* leaf node */
202                         const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
203                         pack_leaf(e, leaf);
204                 }
205                 else {
206                         /* innner node */
207                         int idx[2];
208                         for(int i = 0; i < 2; ++i) {
209                                 if(e.node->get_child(i)->is_leaf()) {
210                                         idx[i] = nextLeafNodeIdx++;
211                                 }
212                                 else {
213                                         idx[i] = nextNodeIdx;
214                                         nextNodeIdx += node_is_unaligned(e.node->get_child(i), bvh2)
215                                                                ? BVH_UNALIGNED_NODE_SIZE
216                                                                : BVH_NODE_SIZE;
217                                 }
218                         }
219
220                         stack.push_back(BVHStackEntry(e.node->get_child(0), idx[0]));
221                         stack.push_back(BVHStackEntry(e.node->get_child(1), idx[1]));
222
223                         pack_inner(e, stack[stack.size()-2], stack[stack.size()-1]);
224                 }
225         }
226         assert(node_size == nextNodeIdx);
227         /* root index to start traversal at, to handle case of single leaf node */
228         pack.root_index = (root->is_leaf())? -1: 0;
229 }
230
231 void BVH2::refit_nodes()
232 {
233         assert(!params.top_level);
234
235         BoundBox bbox = BoundBox::empty;
236         uint visibility = 0;
237         refit_node(0, (pack.root_index == -1)? true: false, bbox, visibility);
238 }
239
240 void BVH2::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
241 {
242         if(leaf) {
243                 /* refit leaf node */
244                 assert(idx + BVH_NODE_LEAF_SIZE <= pack.leaf_nodes.size());
245                 const int4 *data = &pack.leaf_nodes[idx];
246                 const int c0 = data[0].x;
247                 const int c1 = data[0].y;
248
249                 BVH::refit_primitives(c0, c1, bbox, visibility);
250
251                 /* TODO(sergey): De-duplicate with pack_leaf(). */
252                 float4 leaf_data[BVH_NODE_LEAF_SIZE];
253                 leaf_data[0].x = __int_as_float(c0);
254                 leaf_data[0].y = __int_as_float(c1);
255                 leaf_data[0].z = __uint_as_float(visibility);
256                 leaf_data[0].w = __uint_as_float(data[0].w);
257                 memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_NODE_LEAF_SIZE);
258         }
259         else {
260                 assert(idx + BVH_NODE_SIZE <= pack.nodes.size());
261
262                 const int4 *data = &pack.nodes[idx];
263                 const bool is_unaligned = (data[0].x & PATH_RAY_NODE_UNALIGNED) != 0;
264                 const int c0 = data[0].z;
265                 const int c1 = data[0].w;
266                 /* refit inner node, set bbox from children */
267                 BoundBox bbox0 = BoundBox::empty, bbox1 = BoundBox::empty;
268                 uint visibility0 = 0, visibility1 = 0;
269
270                 refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0);
271                 refit_node((c1 < 0)? -c1-1: c1, (c1 < 0), bbox1, visibility1);
272
273                 if(is_unaligned) {
274                         Transform aligned_space = transform_identity();
275                         pack_unaligned_node(idx,
276                                             aligned_space, aligned_space,
277                                             bbox0, bbox1,
278                                             c0, c1,
279                                             visibility0,
280                                             visibility1);
281                 }
282                 else {
283                         pack_aligned_node(idx,
284                                           bbox0, bbox1,
285                                           c0, c1,
286                                           visibility0,
287                                           visibility1);
288                 }
289
290                 bbox.grow(bbox0);
291                 bbox.grow(bbox1);
292                 visibility = visibility0|visibility1;
293         }
294 }
295
296 CCL_NAMESPACE_END