Cycles: Make BVH wider prior to packing
[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_ALIGNED_COUNT:
51                         if(!is_unaligned) {
52                                 cnt = 1;
53                         }
54                         break;
55                 case BVH_STAT_UNALIGNED_COUNT:
56                         if(is_unaligned) {
57                                 cnt = 1;
58                         }
59                         break;
60                 case BVH_STAT_ALIGNED_INNER_COUNT:
61                         if(!is_leaf()) {
62                                 bool has_unaligned = false;
63                                 for(int j = 0; j < num_children(); j++) {
64                                         has_unaligned |= get_child(j)->is_unaligned;
65                                 }
66                                 cnt += has_unaligned? 0: 1;
67                         }
68                         break;
69                 case BVH_STAT_UNALIGNED_INNER_COUNT:
70                         if(!is_leaf()) {
71                                 bool has_unaligned = false;
72                                 for(int j = 0; j < num_children(); j++) {
73                                         has_unaligned |= get_child(j)->is_unaligned;
74                                 }
75                                 cnt += has_unaligned? 1: 0;
76                         }
77                         break;
78                 case BVH_STAT_ALIGNED_LEAF_COUNT:
79                         cnt = (is_leaf() && !is_unaligned) ? 1 : 0;
80                         break;
81                 case BVH_STAT_UNALIGNED_LEAF_COUNT:
82                         cnt = (is_leaf() && is_unaligned) ? 1 : 0;
83                         break;
84                 case BVH_STAT_DEPTH:
85                         if(is_leaf()) {
86                                 cnt = 1;
87                         }
88                         else {
89                                 for(int i = 0; i < num_children(); i++) {
90                                         cnt = max(cnt, get_child(i)->getSubtreeSize(stat));
91                                 }
92                                 cnt += 1;
93                         }
94                         return cnt;
95                 default:
96                         assert(0); /* unknown mode */
97         }
98
99         if(!is_leaf())
100                 for(int i = 0; i < num_children(); i++)
101                         cnt += get_child(i)->getSubtreeSize(stat);
102
103         return cnt;
104 }
105
106 void BVHNode::deleteSubtree()
107 {
108         for(int i = 0; i < num_children(); i++)
109                 if(get_child(i))
110                         get_child(i)->deleteSubtree();
111
112         delete this;
113 }
114
115 float BVHNode::computeSubtreeSAHCost(const BVHParams& p, float probability) const
116 {
117         float SAH = probability * p.cost(num_children(), num_triangles());
118
119         for(int i = 0; i < num_children(); i++) {
120                 BVHNode *child = get_child(i);
121                 SAH += child->computeSubtreeSAHCost(p, probability * child->bounds.safe_area()/bounds.safe_area());
122         }
123
124         return SAH;
125 }
126
127 uint BVHNode::update_visibility()
128 {
129         if(!is_leaf() && visibility == 0) {
130                 InnerNode *inner = (InnerNode*)this;
131                 BVHNode *child0 = inner->children[0];
132                 BVHNode *child1 = inner->children[1];
133
134                 visibility = child0->update_visibility()|child1->update_visibility();
135         }
136
137         return visibility;
138 }
139
140 void BVHNode::update_time()
141 {
142         if(!is_leaf()) {
143                 InnerNode *inner = (InnerNode*)this;
144                 BVHNode *child0 = inner->children[0];
145                 BVHNode *child1 = inner->children[1];
146                 child0->update_time();
147                 child1->update_time();
148                 time_from = min(child0->time_from, child1->time_from);
149                 time_to =  max(child0->time_to, child1->time_to);
150         }
151 }
152
153 /* Inner Node */
154
155 void InnerNode::print(int depth) const
156 {
157         for(int i = 0; i < depth; i++)
158                 printf("  ");
159
160         printf("inner node %p\n", (void*)this);
161
162         if(children[0])
163                 children[0]->print(depth+1);
164         if(children[1])
165                 children[1]->print(depth+1);
166 }
167
168 void LeafNode::print(int depth) const
169 {
170         for(int i = 0; i < depth; i++)
171                 printf("  ");
172
173         printf("leaf node %d to %d\n", lo, hi);
174 }
175
176 CCL_NAMESPACE_END