Blender  V3.3
bvh/node.cpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0
2  * Adapted from code copyright 2009-2010 NVIDIA Corporation
3  * Modifications Copyright 2011-2022 Blender Foundation. */
4 
5 #include "bvh/node.h"
6 
7 #include "bvh/build.h"
8 #include "bvh/bvh.h"
9 
10 #include "util/vector.h"
11 
13 
14 /* BVH Node */
15 
17 {
18  int cnt = 0;
19 
20  switch (stat) {
22  cnt = 1;
23  break;
25  cnt = is_leaf() ? 1 : 0;
26  break;
28  cnt = is_leaf() ? 0 : 1;
29  break;
31  cnt = is_leaf() ? reinterpret_cast<const LeafNode *>(this)->num_triangles() : 0;
32  break;
34  cnt = num_children();
35  break;
37  if (!is_unaligned) {
38  cnt = 1;
39  }
40  break;
42  if (is_unaligned) {
43  cnt = 1;
44  }
45  break;
47  if (!is_leaf()) {
48  bool has_unaligned = false;
49  for (int j = 0; j < num_children(); j++) {
51  }
52  cnt += has_unaligned ? 0 : 1;
53  }
54  break;
56  if (!is_leaf()) {
57  bool has_unaligned = false;
58  for (int j = 0; j < num_children(); j++) {
60  }
61  cnt += has_unaligned ? 1 : 0;
62  }
63  break;
65  cnt = (is_leaf() && !is_unaligned) ? 1 : 0;
66  break;
68  cnt = (is_leaf() && is_unaligned) ? 1 : 0;
69  break;
70  case BVH_STAT_DEPTH:
71  if (is_leaf()) {
72  cnt = 1;
73  }
74  else {
75  for (int i = 0; i < num_children(); i++) {
76  cnt = max(cnt, get_child(i)->getSubtreeSize(stat));
77  }
78  cnt += 1;
79  }
80  return cnt;
81  default:
82  assert(0); /* unknown mode */
83  }
84 
85  if (!is_leaf())
86  for (int i = 0; i < num_children(); i++)
87  cnt += get_child(i)->getSubtreeSize(stat);
88 
89  return cnt;
90 }
91 
93 {
94  for (int i = 0; i < num_children(); i++)
95  if (get_child(i))
97 
98  delete this;
99 }
100 
101 float BVHNode::computeSubtreeSAHCost(const BVHParams &p, float probability) const
102 {
103  float SAH = probability * p.cost(num_children(), num_triangles());
104 
105  for (int i = 0; i < num_children(); i++) {
106  BVHNode *child = get_child(i);
107  SAH += child->computeSubtreeSAHCost(
108  p, probability * child->bounds.safe_area() / bounds.safe_area());
109  }
110 
111  return SAH;
112 }
113 
115 {
116  if (!is_leaf() && visibility == 0) {
117  InnerNode *inner = (InnerNode *)this;
118  BVHNode *child0 = inner->children[0];
119  BVHNode *child1 = inner->children[1];
120 
121  visibility = child0->update_visibility() | child1->update_visibility();
122  }
123 
124  return visibility;
125 }
126 
128 {
129  if (!is_leaf()) {
130  InnerNode *inner = (InnerNode *)this;
131  BVHNode *child0 = inner->children[0];
132  BVHNode *child1 = inner->children[1];
133  child0->update_time();
134  child1->update_time();
135  time_from = min(child0->time_from, child1->time_from);
136  time_to = max(child0->time_to, child1->time_to);
137  }
138 }
139 
140 namespace {
141 
142 struct DumpTraversalContext {
143  /* Descriptor of while where writing is happening. */
144  FILE *stream;
145  /* Unique identifier of the node current. */
146  int id;
147 };
148 
149 void dump_subtree(DumpTraversalContext *context, const BVHNode *node, const BVHNode *parent = NULL)
150 {
151  if (node->is_leaf()) {
152  fprintf(context->stream,
153  " node_%p [label=\"%d\",fillcolor=\"#ccccee\",style=filled]\n",
154  node,
155  context->id);
156  }
157  else {
158  fprintf(context->stream,
159  " node_%p [label=\"%d\",fillcolor=\"#cceecc\",style=filled]\n",
160  node,
161  context->id);
162  }
163  if (parent != NULL) {
164  fprintf(context->stream, " node_%p -> node_%p;\n", parent, node);
165  }
166  context->id += 1;
167  for (int i = 0; i < node->num_children(); ++i) {
168  dump_subtree(context, node->get_child(i), node);
169  }
170 }
171 
172 } // namespace
173 
174 void BVHNode::dump_graph(const char *filename)
175 {
176  DumpTraversalContext context;
177  context.stream = fopen(filename, "w");
178  if (context.stream == NULL) {
179  return;
180  }
181  context.id = 0;
182  fprintf(context.stream, "digraph BVH {\n");
183  dump_subtree(&context, this);
184  fprintf(context.stream, "}\n");
185  fclose(context.stream);
186 }
187 
188 /* Inner Node */
189 
190 void InnerNode::print(int depth) const
191 {
192  for (int i = 0; i < depth; i++)
193  printf(" ");
194 
195  printf("inner node %p\n", (void *)this);
196 
197  if (children[0])
198  children[0]->print(depth + 1);
199  if (children[1])
200  children[1]->print(depth + 1);
201 }
202 
203 void LeafNode::print(int depth) const
204 {
205  for (int i = 0; i < depth; i++)
206  printf(" ");
207 
208  printf("leaf node %d to %d\n", lo, hi);
209 }
210 
unsigned int uint
Definition: BLI_sys_types.h:67
BVH_STAT
Definition: bvh/node.h:13
@ BVH_STAT_TRIANGLE_COUNT
Definition: bvh/node.h:17
@ BVH_STAT_NODE_COUNT
Definition: bvh/node.h:14
@ BVH_STAT_CHILDNODE_COUNT
Definition: bvh/node.h:18
@ BVH_STAT_ALIGNED_COUNT
Definition: bvh/node.h:19
@ BVH_STAT_ALIGNED_INNER_COUNT
Definition: bvh/node.h:21
@ BVH_STAT_ALIGNED_LEAF_COUNT
Definition: bvh/node.h:23
@ BVH_STAT_DEPTH
Definition: bvh/node.h:25
@ BVH_STAT_UNALIGNED_COUNT
Definition: bvh/node.h:20
@ BVH_STAT_UNALIGNED_LEAF_COUNT
Definition: bvh/node.h:24
@ BVH_STAT_UNALIGNED_INNER_COUNT
Definition: bvh/node.h:22
@ BVH_STAT_INNER_COUNT
Definition: bvh/node.h:15
@ BVH_STAT_LEAF_COUNT
Definition: bvh/node.h:16
__forceinline float cost(int num_nodes, int num_primitives) const
Definition: params.h:145
void print(int depth) const
Definition: bvh/node.cpp:190
BVHNode * children[kNumMaxChildren]
Definition: bvh/node.h:194
int hi
Definition: bvh/node.h:237
int lo
Definition: bvh/node.h:236
void print(int depth) const
Definition: bvh/node.cpp:203
#define CCL_NAMESPACE_END
Definition: cuda/compat.h:9
OperationNode * node
#define min(a, b)
Definition: sort.c:35
int getSubtreeSize(BVH_STAT stat=BVH_STAT_NODE_COUNT) const
Definition: bvh/node.cpp:16
void update_time()
Definition: bvh/node.cpp:127
uint visibility
Definition: bvh/node.h:91
uint update_visibility()
Definition: bvh/node.cpp:114
virtual int num_children() const =0
float time_to
Definition: bvh/node.h:100
float computeSubtreeSAHCost(const BVHParams &p, float probability=1.0f) const
Definition: bvh/node.cpp:101
bool is_unaligned
Definition: bvh/node.h:93
virtual bool is_leaf() const =0
void deleteSubtree()
Definition: bvh/node.cpp:92
float time_from
Definition: bvh/node.h:100
bool has_unaligned() const
Definition: bvh/node.h:65
virtual BVHNode * get_child(int i) const =0
virtual int num_triangles() const
Definition: bvh/node.h:40
virtual void print(int depth=0) const =0
BoundBox bounds
Definition: bvh/node.h:90
void dump_graph(const char *filename)
Definition: bvh/node.cpp:174
__forceinline float safe_area() const
Definition: boundbox.h:95
float max