Fix T49818: Crash when rendering with motion blur
[blender.git] / intern / cycles / bvh / bvh_split.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_SPLIT_H__
19 #define __BVH_SPLIT_H__
20
21 #include "bvh_build.h"
22 #include "bvh_params.h"
23
24 CCL_NAMESPACE_BEGIN
25
26 class BVHBuild;
27 struct Transform;
28
29 /* Object Split */
30
31 class BVHObjectSplit
32 {
33 public:
34         float sah;
35         int dim;
36         int num_left;
37         BoundBox left_bounds;
38         BoundBox right_bounds;
39
40         BVHObjectSplit() {}
41         BVHObjectSplit(BVHBuild *builder,
42                        BVHSpatialStorage *storage,
43                        const BVHRange& range,
44                        vector<BVHReference> *references,
45                        float nodeSAH,
46                        const BVHUnaligned *unaligned_heuristic = NULL,
47                        const Transform *aligned_space = NULL);
48
49         void split(BVHRange& left,
50                    BVHRange& right,
51                    const BVHRange& range);
52
53 protected:
54         BVHSpatialStorage *storage_;
55         vector<BVHReference> *references_;
56         const BVHUnaligned *unaligned_heuristic_;
57         const Transform *aligned_space_;
58
59         __forceinline BoundBox get_prim_bounds(const BVHReference& prim) const
60         {
61                 if(aligned_space_ == NULL) {
62                         return prim.bounds();
63                 }
64                 else {
65                         return unaligned_heuristic_->compute_aligned_prim_boundbox(
66                                 prim, *aligned_space_);
67                 }
68         }
69 };
70
71 /* Spatial Split */
72
73 class BVHSpatialSplit
74 {
75 public:
76         float sah;
77         int dim;
78         float pos;
79
80         BVHSpatialSplit() : sah(FLT_MAX),
81                             dim(0),
82                             pos(0.0f),
83                             storage_(NULL),
84                             references_(NULL) {}
85         BVHSpatialSplit(const BVHBuild& builder,
86                         BVHSpatialStorage *storage,
87                         const BVHRange& range,
88                         vector<BVHReference> *references,
89                         float nodeSAH,
90                         const BVHUnaligned *unaligned_heuristic = NULL,
91                         const Transform *aligned_space = NULL);
92
93         void split(BVHBuild *builder,
94                    BVHRange& left,
95                    BVHRange& right,
96                    const BVHRange& range);
97
98         void split_reference(const BVHBuild& builder,
99                              BVHReference& left,
100                              BVHReference& right,
101                              const BVHReference& ref,
102                              int dim,
103                              float pos);
104
105 protected:
106         BVHSpatialStorage *storage_;
107         vector<BVHReference> *references_;
108         const BVHUnaligned *unaligned_heuristic_;
109         const Transform *aligned_space_;
110
111         /* Lower-level functions which calculates boundaries of left and right nodes
112          * needed for spatial split.
113          *
114          * Operates directly with primitive specified by it's index, reused by higher
115          * level splitting functions.
116          */
117         void split_triangle_primitive(const Mesh *mesh,
118                                       const Transform *tfm,
119                                       int prim_index,
120                                       int dim,
121                                       float pos,
122                                       BoundBox& left_bounds,
123                                       BoundBox& right_bounds);
124         void split_curve_primitive(const Mesh *mesh,
125                                    const Transform *tfm,
126                                    int prim_index,
127                                    int segment_index,
128                                    int dim,
129                                    float pos,
130                                    BoundBox& left_bounds,
131                                    BoundBox& right_bounds);
132
133         /* Lower-level functions which calculates boundaries of left and right nodes
134          * needed for spatial split.
135          *
136          * Operates with BVHReference, internally uses lower level API functions.
137          */
138         void split_triangle_reference(const BVHReference& ref,
139                                       const Mesh *mesh,
140                                       int dim,
141                                       float pos,
142                                       BoundBox& left_bounds,
143                                       BoundBox& right_bounds);
144         void split_curve_reference(const BVHReference& ref,
145                                    const Mesh *mesh,
146                                    int dim,
147                                    float pos,
148                                    BoundBox& left_bounds,
149                                    BoundBox& right_bounds);
150         void split_object_reference(const Object *object,
151                                     int dim,
152                                     float pos,
153                                     BoundBox& left_bounds,
154                                     BoundBox& right_bounds);
155
156         __forceinline BoundBox get_prim_bounds(const BVHReference& prim) const
157         {
158                 if(aligned_space_ == NULL) {
159                         return prim.bounds();
160                 }
161                 else {
162                         return unaligned_heuristic_->compute_aligned_prim_boundbox(
163                                 prim, *aligned_space_);
164                 }
165         }
166
167         __forceinline float3 get_unaligned_point(const float3& point) const
168         {
169                 if(aligned_space_ == NULL) {
170                         return point;
171                 }
172                 else {
173                         return transform_point(aligned_space_, point);
174                 }
175         }
176 };
177
178 /* Mixed Object-Spatial Split */
179
180 class BVHMixedSplit
181 {
182 public:
183         BVHObjectSplit object;
184         BVHSpatialSplit spatial;
185
186         float leafSAH;
187         float nodeSAH;
188         float minSAH;
189
190         bool no_split;
191
192         BoundBox bounds;
193
194         BVHMixedSplit() {}
195
196         __forceinline BVHMixedSplit(BVHBuild *builder,
197                                     BVHSpatialStorage *storage,
198                                     const BVHRange& range,
199                                     vector<BVHReference> *references,
200                                     int level,
201                                     const BVHUnaligned *unaligned_heuristic = NULL,
202                                     const Transform *aligned_space = NULL)
203         {
204                 if(aligned_space == NULL) {
205                         bounds = range.bounds();
206                 }
207                 else {
208                         bounds = unaligned_heuristic->compute_aligned_boundbox(
209                                 range,
210                                 &references->at(0),
211                                 *aligned_space);
212                 }
213                 /* find split candidates. */
214                 float area = bounds.safe_area();
215
216                 leafSAH = area * builder->params.primitive_cost(range.size());
217                 nodeSAH = area * builder->params.node_cost(2);
218
219                 object = BVHObjectSplit(builder,
220                                         storage,
221                                         range,
222                                         references,
223                                         nodeSAH,
224                                         unaligned_heuristic,
225                                         aligned_space);
226
227                 if(builder->params.use_spatial_split && level < BVHParams::MAX_SPATIAL_DEPTH) {
228                         BoundBox overlap = object.left_bounds;
229                         overlap.intersect(object.right_bounds);
230
231                         if(overlap.safe_area() >= builder->spatial_min_overlap) {
232                                 spatial = BVHSpatialSplit(*builder,
233                                                           storage,
234                                                           range,
235                                                           references,
236                                                           nodeSAH,
237                                                           unaligned_heuristic,
238                                                           aligned_space);
239                         }
240                 }
241
242                 /* leaf SAH is the lowest => create leaf. */
243                 minSAH = min(min(leafSAH, object.sah), spatial.sah);
244                 no_split = (minSAH == leafSAH &&
245                             builder->range_within_max_leaf_size(range, *references));
246         }
247
248         __forceinline void split(BVHBuild *builder,
249                                  BVHRange& left,
250                                  BVHRange& right,
251                                  const BVHRange& range)
252         {
253                 if(builder->params.use_spatial_split && minSAH == spatial.sah)
254                         spatial.split(builder, left, right, range);
255                 if(!left.size() || !right.size())
256                         object.split(left, right, range);
257         }
258 };
259
260 CCL_NAMESPACE_END
261
262 #endif /* __BVH_SPLIT_H__ */