fd8b497769923c2d5b7de4dea6e1fa5e75c325e8
[blender.git] / intern / cycles / bvh / bvh_node.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/bvh_node.h"
19
20 #include "bvh/bvh.h"
21 #include "bvh/bvh_build.h"
22
23 #include "util/util_vector.h"
24
25 CCL_NAMESPACE_BEGIN
26
27 /* BVH Node */
28
29 int BVHNode::getSubtreeSize(BVH_STAT stat) const
30 {
31         int cnt = 0;
32
33         switch(stat)
34         {
35                 case BVH_STAT_NODE_COUNT:
36                         cnt = 1;
37                         break;
38                 case BVH_STAT_LEAF_COUNT:
39                         cnt = is_leaf() ? 1 : 0;
40                         break;
41                 case BVH_STAT_INNER_COUNT:
42                         cnt = is_leaf() ? 0 : 1;
43                         break;
44                 case BVH_STAT_TRIANGLE_COUNT:
45                         cnt = is_leaf() ? reinterpret_cast<const LeafNode*>(this)->num_triangles() : 0;
46                         break;
47                 case BVH_STAT_CHILDNODE_COUNT:
48                         cnt = num_children();
49                         break;
50                 case BVH_STAT_QNODE_COUNT:
51                         cnt = 1;
52                         for(int i = 0; i < num_children(); i++) {
53                                 BVHNode *node = get_child(i);
54                                 if(node->is_leaf()) {
55                                         cnt += 1;
56                                 }
57                                 else {
58                                         for(int j = 0; j < node->num_children(); j++) {
59                                                 cnt += node->get_child(j)->getSubtreeSize(stat);
60                                         }
61                                 }
62                         }
63                         return cnt;
64                 case BVH_STAT_ONODE_COUNT:
65                         cnt = 1;
66                         for(int i = 0; i < num_children(); i++) {
67                                 BVHNode *node = get_child(i);
68                                 if(node->is_leaf()) {
69                                         cnt += 1;
70                                 }
71                                 else {
72                                         for(int j = 0; j < node->num_children(); j++)
73                                         {
74                                                 BVHNode *node_next = node->get_child(j);
75                                                 if(node_next->is_leaf()) {
76                                                         cnt += 1;
77                                                 }
78                                                 else {
79                                                         for(int k = 0; k < node_next->num_children(); k++) {
80                                                                 cnt += node_next->get_child(k)->getSubtreeSize(stat);
81                                                         }
82                                                 }
83                                         }
84                                 }
85                         }
86                         return cnt;
87                 case BVH_STAT_UNALIGNED_INNER_ONODE_COUNT:
88                         {
89                                 bool has_unaligned = false;
90                                 for(int i = 0; i < num_children(); i++) {
91                                         BVHNode *node = get_child(i);
92                                         if(node->is_leaf()) {
93                                                 has_unaligned |= node->is_unaligned;
94                                         }
95                                         else {
96                                                 for(int j = 0; j < node->num_children(); j++) {
97                                                         BVHNode *node_next = node->get_child(j);
98                                                         if(node_next->is_leaf()) {
99                                                                 has_unaligned |= node_next->is_unaligned;
100                                                         }
101                                                         else {
102                                                                 for(int k = 0; k < node_next->num_children(); k++) {
103                                                                         cnt += node_next->get_child(k)->getSubtreeSize(stat);
104                                                                         has_unaligned |= node_next->get_child(k)->is_unaligned;
105                                                                 }
106                                                         }
107                                                 }
108                                         }
109                                 }
110                                 cnt += has_unaligned? 1: 0;
111                         }
112                         return cnt;
113                 case BVH_STAT_ALIGNED_COUNT:
114                         if(!is_unaligned) {
115                                 cnt = 1;
116                         }
117                         break;
118                 case BVH_STAT_UNALIGNED_COUNT:
119                         if(is_unaligned) {
120                                 cnt = 1;
121                         }
122                         break;
123                 case BVH_STAT_ALIGNED_INNER_COUNT:
124                         if(!is_leaf()) {
125                                 bool has_unaligned = false;
126                                 for(int j = 0; j < num_children(); j++) {
127                                         has_unaligned |= get_child(j)->is_unaligned;
128                                 }
129                                 cnt += has_unaligned? 0: 1;
130                         }
131                         break;
132                 case BVH_STAT_UNALIGNED_INNER_COUNT:
133                         if(!is_leaf()) {
134                                 bool has_unaligned = false;
135                                 for(int j = 0; j < num_children(); j++) {
136                                         has_unaligned |= get_child(j)->is_unaligned;
137                                 }
138                                 cnt += has_unaligned? 1: 0;
139                         }
140                         break;
141                 case BVH_STAT_ALIGNED_INNER_QNODE_COUNT:
142                         {
143                                 bool has_unaligned = false;
144                                 for(int i = 0; i < num_children(); i++) {
145                                         BVHNode *node = get_child(i);
146                                         if(node->is_leaf()) {
147                                                 has_unaligned |= node->is_unaligned;
148                                         }
149                                         else {
150                                                 for(int j = 0; j < node->num_children(); j++) {
151                                                         cnt += node->get_child(j)->getSubtreeSize(stat);
152                                                         has_unaligned |= node->get_child(j)->is_unaligned;
153                                                 }
154                                         }
155                                 }
156                                 cnt += has_unaligned? 0: 1;
157                         }
158                         return cnt;
159                 case BVH_STAT_UNALIGNED_INNER_QNODE_COUNT:
160                         {
161                                 bool has_unaligned = false;
162                                 for(int i = 0; i < num_children(); i++) {
163                                         BVHNode *node = get_child(i);
164                                         if(node->is_leaf()) {
165                                                 has_unaligned |= node->is_unaligned;
166                                         }
167                                         else {
168                                                 for(int j = 0; j < node->num_children(); j++) {
169                                                         cnt += node->get_child(j)->getSubtreeSize(stat);
170                                                         has_unaligned |= node->get_child(j)->is_unaligned;
171                                                 }
172                                         }
173                                 }
174                                 cnt += has_unaligned? 1: 0;
175                         }
176                         return cnt;
177                 case BVH_STAT_ALIGNED_LEAF_COUNT:
178                         cnt = (is_leaf() && !is_unaligned) ? 1 : 0;
179                         break;
180                 case BVH_STAT_UNALIGNED_LEAF_COUNT:
181                         cnt = (is_leaf() && is_unaligned) ? 1 : 0;
182                         break;
183                 case BVH_STAT_DEPTH:
184                         if(is_leaf()) {
185                                 cnt = 1;
186                         }
187                         else {
188                                 for(int i = 0; i < num_children(); i++) {
189                                         cnt = max(cnt, get_child(i)->getSubtreeSize(stat));
190                                 }
191                                 cnt += 1;
192                         }
193                         return cnt;
194                 default:
195                         assert(0); /* unknown mode */
196         }
197
198         if(!is_leaf())
199                 for(int i = 0; i < num_children(); i++)
200                         cnt += get_child(i)->getSubtreeSize(stat);
201
202         return cnt;
203 }
204
205 void BVHNode::deleteSubtree()
206 {
207         for(int i = 0; i < num_children(); i++)
208                 if(get_child(i))
209                         get_child(i)->deleteSubtree();
210
211         delete this;
212 }
213
214 float BVHNode::computeSubtreeSAHCost(const BVHParams& p, float probability) const
215 {
216         float SAH = probability * p.cost(num_children(), num_triangles());
217
218         for(int i = 0; i < num_children(); i++) {
219                 BVHNode *child = get_child(i);
220                 SAH += child->computeSubtreeSAHCost(p, probability * child->bounds.safe_area()/bounds.safe_area());
221         }
222
223         return SAH;
224 }
225
226 uint BVHNode::update_visibility()
227 {
228         if(!is_leaf() && visibility == 0) {
229                 InnerNode *inner = (InnerNode*)this;
230                 BVHNode *child0 = inner->children[0];
231                 BVHNode *child1 = inner->children[1];
232
233                 visibility = child0->update_visibility()|child1->update_visibility();
234         }
235
236         return visibility;
237 }
238
239 void BVHNode::update_time()
240 {
241         if(!is_leaf()) {
242                 InnerNode *inner = (InnerNode*)this;
243                 BVHNode *child0 = inner->children[0];
244                 BVHNode *child1 = inner->children[1];
245                 child0->update_time();
246                 child1->update_time();
247                 time_from = min(child0->time_from, child1->time_from);
248                 time_to =  max(child0->time_to, child1->time_to);
249         }
250 }
251
252 /* Inner Node */
253
254 void InnerNode::print(int depth) const
255 {
256         for(int i = 0; i < depth; i++)
257                 printf("  ");
258
259         printf("inner node %p\n", (void*)this);
260
261         if(children[0])
262                 children[0]->print(depth+1);
263         if(children[1])
264                 children[1]->print(depth+1);
265 }
266
267 void LeafNode::print(int depth) const
268 {
269         for(int i = 0; i < depth; i++)
270                 printf("  ");
271
272         printf("leaf node %d to %d\n", lo, hi);
273 }
274
275 CCL_NAMESPACE_END