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