Blender  V3.3
bvh/node.h
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 #ifndef __BVH_NODE_H__
6 #define __BVH_NODE_H__
7 
8 #include "util/boundbox.h"
9 #include "util/types.h"
10 
12 
13 enum BVH_STAT {
26 };
27 
28 class BVHParams;
29 
30 class BVHNode {
31  public:
32  virtual ~BVHNode()
33  {
34  delete aligned_space;
35  }
36 
37  virtual bool is_leaf() const = 0;
38  virtual int num_children() const = 0;
39  virtual BVHNode *get_child(int i) const = 0;
40  virtual int num_triangles() const
41  {
42  return 0;
43  }
44  virtual void print(int depth = 0) const = 0;
45 
47  {
48  is_unaligned = true;
49  if (this->aligned_space == NULL) {
50  this->aligned_space = new Transform(aligned_space);
51  }
52  else {
53  *this->aligned_space = aligned_space;
54  }
55  }
56 
58  {
59  if (aligned_space == NULL) {
60  return transform_identity();
61  }
62  return *aligned_space;
63  }
64 
65  inline bool has_unaligned() const
66  {
67  if (is_leaf()) {
68  return false;
69  }
70  for (int i = 0; i < num_children(); ++i) {
71  if (get_child(i)->is_unaligned) {
72  return true;
73  }
74  }
75  return false;
76  }
77 
78  // Subtree functions
80  float computeSubtreeSAHCost(const BVHParams &p, float probability = 1.0f) const;
81  void deleteSubtree();
82 
84  void update_time();
85 
86  /* Dump the content of the tree as a graphviz file. */
87  void dump_graph(const char *filename);
88 
89  // Properties.
92 
94 
95  /* TODO(sergey): Can be stored as 3x3 matrix, but better to have some
96  * utilities and type defines in util_transform first.
97  */
99 
101 
102  protected:
103  explicit BVHNode(const BoundBox &bounds)
104  : bounds(bounds),
105  visibility(0),
106  is_unaligned(false),
108  time_from(0.0f),
109  time_to(1.0f)
110  {
111  }
112 
113  explicit BVHNode(const BVHNode &other)
114  : bounds(other.bounds),
115  visibility(other.visibility),
116  is_unaligned(other.is_unaligned),
118  time_from(other.time_from),
119  time_to(other.time_to)
120  {
121  if (other.aligned_space != NULL) {
122  assert(other.is_unaligned);
123  aligned_space = new Transform();
124  *aligned_space = *other.aligned_space;
125  }
126  else {
127  assert(!other.is_unaligned);
128  }
129  }
130 };
131 
132 class InnerNode : public BVHNode {
133  public:
134  static constexpr int kNumMaxChildren = 8;
135 
136  InnerNode(const BoundBox &bounds, BVHNode *child0, BVHNode *child1)
138  {
139  children[0] = child0;
140  children[1] = child1;
142 
143  if (child0 && child1) {
144  visibility = child0->visibility | child1->visibility;
145  }
146  else {
147  /* Happens on build cancel. */
148  visibility = 0;
149  }
150  }
151 
154  {
155  visibility = 0;
156  time_from = FLT_MAX;
157  time_to = -FLT_MAX;
158  for (int i = 0; i < num_children; ++i) {
159  assert(children[i] != NULL);
161  this->children[i] = children[i];
164  }
166  }
167 
168  /* NOTE: This function is only used during binary BVH builder, and it's
169  * supposed to be configured to have 2 children which will be filled-in in a
170  * bit. But this is important to have children reset to NULL. */
172  {
174  visibility = 0;
175  num_children_ = 2;
176  }
177 
178  bool is_leaf() const
179  {
180  return false;
181  }
182  int num_children() const
183  {
184  return num_children_;
185  }
186  BVHNode *get_child(int i) const
187  {
188  assert(i >= 0 && i < num_children_);
189  return children[i];
190  }
191  void print(int depth) const;
192 
195 
196  protected:
198  {
199  for (int i = num_children_; i < kNumMaxChildren; ++i) {
200  children[i] = NULL;
201  }
202  }
203 };
204 
205 class LeafNode : public BVHNode {
206  public:
208  : BVHNode(bounds), lo(lo), hi(hi)
209  {
210  this->bounds = bounds;
211  this->visibility = visibility;
212  }
213 
214  LeafNode(const LeafNode &other) : BVHNode(other), lo(other.lo), hi(other.hi)
215  {
216  }
217 
218  bool is_leaf() const
219  {
220  return true;
221  }
222  int num_children() const
223  {
224  return 0;
225  }
226  BVHNode *get_child(int) const
227  {
228  return NULL;
229  }
230  int num_triangles() const
231  {
232  return hi - lo;
233  }
234  void print(int depth) const;
235 
236  int lo;
237  int hi;
238 };
239 
241 
242 #endif /* __BVH_NODE_H__ */
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
int num_children() const
Definition: bvh/node.h:182
void reset_unused_children()
Definition: bvh/node.h:197
bool is_leaf() const
Definition: bvh/node.h:178
InnerNode(const BoundBox &bounds)
Definition: bvh/node.h:171
InnerNode(const BoundBox &bounds, BVHNode *child0, BVHNode *child1)
Definition: bvh/node.h:136
void print(int depth) const
Definition: bvh/node.cpp:190
int num_children_
Definition: bvh/node.h:193
static constexpr int kNumMaxChildren
Definition: bvh/node.h:134
BVHNode * get_child(int i) const
Definition: bvh/node.h:186
BVHNode * children[kNumMaxChildren]
Definition: bvh/node.h:194
InnerNode(const BoundBox &bounds, BVHNode **children, const int num_children)
Definition: bvh/node.h:152
LeafNode(const LeafNode &other)
Definition: bvh/node.h:214
int num_triangles() const
Definition: bvh/node.h:230
int hi
Definition: bvh/node.h:237
BVHNode * get_child(int) const
Definition: bvh/node.h:226
int lo
Definition: bvh/node.h:236
int num_children() const
Definition: bvh/node.h:222
void print(int depth) const
Definition: bvh/node.cpp:203
bool is_leaf() const
Definition: bvh/node.h:218
LeafNode(const BoundBox &bounds, uint visibility, int lo, int hi)
Definition: bvh/node.h:207
#define CCL_NAMESPACE_END
Definition: cuda/compat.h:9
ccl_device_inline Transform transform_identity()
CCL_NAMESPACE_BEGIN struct Transform Transform
#define min(a, b)
Definition: sort.c:35
Transform * aligned_space
Definition: bvh/node.h:98
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
BVHNode(const BoundBox &bounds)
Definition: bvh/node.h:103
float computeSubtreeSAHCost(const BVHParams &p, float probability=1.0f) const
Definition: bvh/node.cpp:101
bool is_unaligned
Definition: bvh/node.h:93
virtual ~BVHNode()
Definition: bvh/node.h:32
virtual bool is_leaf() const =0
void deleteSubtree()
Definition: bvh/node.cpp:92
float time_from
Definition: bvh/node.h:100
void set_aligned_space(const Transform &aligned_space)
Definition: bvh/node.h:46
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
Transform get_aligned_space() const
Definition: bvh/node.h:57
BVHNode(const BVHNode &other)
Definition: bvh/node.h:113
BoundBox bounds
Definition: bvh/node.h:90
void dump_graph(const char *filename)
Definition: bvh/node.cpp:174
float max