UI: Custom Face Orientation Colors
[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     case BVH_STAT_NODE_COUNT:
35       cnt = 1;
36       break;
37     case BVH_STAT_LEAF_COUNT:
38       cnt = is_leaf() ? 1 : 0;
39       break;
40     case BVH_STAT_INNER_COUNT:
41       cnt = is_leaf() ? 0 : 1;
42       break;
43     case BVH_STAT_TRIANGLE_COUNT:
44       cnt = is_leaf() ? reinterpret_cast<const LeafNode *>(this)->num_triangles() : 0;
45       break;
46     case BVH_STAT_CHILDNODE_COUNT:
47       cnt = num_children();
48       break;
49     case BVH_STAT_ALIGNED_COUNT:
50       if (!is_unaligned) {
51         cnt = 1;
52       }
53       break;
54     case BVH_STAT_UNALIGNED_COUNT:
55       if (is_unaligned) {
56         cnt = 1;
57       }
58       break;
59     case BVH_STAT_ALIGNED_INNER_COUNT:
60       if (!is_leaf()) {
61         bool has_unaligned = false;
62         for (int j = 0; j < num_children(); j++) {
63           has_unaligned |= get_child(j)->is_unaligned;
64         }
65         cnt += has_unaligned ? 0 : 1;
66       }
67       break;
68     case BVH_STAT_UNALIGNED_INNER_COUNT:
69       if (!is_leaf()) {
70         bool has_unaligned = false;
71         for (int j = 0; j < num_children(); j++) {
72           has_unaligned |= get_child(j)->is_unaligned;
73         }
74         cnt += has_unaligned ? 1 : 0;
75       }
76       break;
77     case BVH_STAT_ALIGNED_LEAF_COUNT:
78       cnt = (is_leaf() && !is_unaligned) ? 1 : 0;
79       break;
80     case BVH_STAT_UNALIGNED_LEAF_COUNT:
81       cnt = (is_leaf() && is_unaligned) ? 1 : 0;
82       break;
83     case BVH_STAT_DEPTH:
84       if (is_leaf()) {
85         cnt = 1;
86       }
87       else {
88         for (int i = 0; i < num_children(); i++) {
89           cnt = max(cnt, get_child(i)->getSubtreeSize(stat));
90         }
91         cnt += 1;
92       }
93       return cnt;
94     default:
95       assert(0); /* unknown mode */
96   }
97
98   if (!is_leaf())
99     for (int i = 0; i < num_children(); i++)
100       cnt += get_child(i)->getSubtreeSize(stat);
101
102   return cnt;
103 }
104
105 void BVHNode::deleteSubtree()
106 {
107   for (int i = 0; i < num_children(); i++)
108     if (get_child(i))
109       get_child(i)->deleteSubtree();
110
111   delete this;
112 }
113
114 float BVHNode::computeSubtreeSAHCost(const BVHParams &p, float probability) const
115 {
116   float SAH = probability * p.cost(num_children(), num_triangles());
117
118   for (int i = 0; i < num_children(); i++) {
119     BVHNode *child = get_child(i);
120     SAH += child->computeSubtreeSAHCost(
121         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 namespace {
154
155 struct DumpTraversalContext {
156   /* Descriptor of wile where writing is happening. */
157   FILE *stream;
158   /* Unique identifier of the node current. */
159   int id;
160 };
161
162 void dump_subtree(DumpTraversalContext *context, const BVHNode *node, const BVHNode *parent = NULL)
163 {
164   if (node->is_leaf()) {
165     fprintf(context->stream,
166             "  node_%p [label=\"%d\",fillcolor=\"#ccccee\",style=filled]\n",
167             node,
168             context->id);
169   }
170   else {
171     fprintf(context->stream,
172             "  node_%p [label=\"%d\",fillcolor=\"#cceecc\",style=filled]\n",
173             node,
174             context->id);
175   }
176   if (parent != NULL) {
177     fprintf(context->stream, "  node_%p -> node_%p;\n", parent, node);
178   }
179   context->id += 1;
180   for (int i = 0; i < node->num_children(); ++i) {
181     dump_subtree(context, node->get_child(i), node);
182   }
183 }
184
185 }  // namespace
186
187 void BVHNode::dump_graph(const char *filename)
188 {
189   DumpTraversalContext context;
190   context.stream = fopen(filename, "w");
191   if (context.stream == NULL) {
192     return;
193   }
194   context.id = 0;
195   fprintf(context.stream, "digraph BVH {\n");
196   dump_subtree(&context, this);
197   fprintf(context.stream, "}\n");
198   fclose(context.stream);
199 }
200
201 /* Inner Node */
202
203 void InnerNode::print(int depth) const
204 {
205   for (int i = 0; i < depth; i++)
206     printf("  ");
207
208   printf("inner node %p\n", (void *)this);
209
210   if (children[0])
211     children[0]->print(depth + 1);
212   if (children[1])
213     children[1]->print(depth + 1);
214 }
215
216 void LeafNode::print(int depth) const
217 {
218   for (int i = 0; i < depth; i++)
219     printf("  ");
220
221   printf("leaf node %d to %d\n", lo, hi);
222 }
223
224 CCL_NAMESPACE_END