Cycles: Make spatial split BVH multi-threaded
[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
28 /* Object Split */
29
30 class BVHObjectSplit
31 {
32 public:
33         float sah;
34         int dim;
35         int num_left;
36         BoundBox left_bounds;
37         BoundBox right_bounds;
38
39         BVHObjectSplit() {}
40         BVHObjectSplit(BVHBuild *builder,
41                        BVHSpatialStorage *storage,
42                        const BVHRange& range,
43                        vector<BVHReference> *references,
44                        float nodeSAH);
45
46         void split(BVHRange& left,
47                    BVHRange& right,
48                    const BVHRange& range);
49
50 protected:
51         BVHSpatialStorage *storage_;
52         vector<BVHReference> *references_;
53 };
54
55 /* Spatial Split */
56
57 class BVHSpatialSplit
58 {
59 public:
60         float sah;
61         int dim;
62         float pos;
63
64         BVHSpatialSplit() : sah(FLT_MAX), dim(0), pos(0.0f) {}
65         BVHSpatialSplit(const BVHBuild& builder,
66                         BVHSpatialStorage *storage,
67                         const BVHRange& range,
68                         vector<BVHReference> *references,
69                         float nodeSAH);
70
71         void split(BVHBuild *builder,
72                    BVHRange& left,
73                    BVHRange& right,
74                    const BVHRange& range);
75
76         void split_reference(const BVHBuild& builder,
77                              BVHReference& left,
78                              BVHReference& right,
79                              const BVHReference& ref,
80                              int dim,
81                              float pos);
82
83 protected:
84         BVHSpatialStorage *storage_;
85         vector<BVHReference> *references_;
86
87         /* Lower-level functions which calculates boundaries of left and right nodes
88          * needed for spatial split.
89          *
90          * Operates directly with primitive specified by it's index, reused by higher
91          * level splitting functions.
92          */
93         void split_triangle_primitive(const Mesh *mesh,
94                                       const Transform *tfm,
95                                       int prim_index,
96                                       int dim,
97                                       float pos,
98                                       BoundBox& left_bounds,
99                                       BoundBox& right_bounds);
100         void split_curve_primitive(const Mesh *mesh,
101                                    const Transform *tfm,
102                                    int prim_index,
103                                    int segment_index,
104                                    int dim,
105                                    float pos,
106                                    BoundBox& left_bounds,
107                                    BoundBox& right_bounds);
108
109         /* Lower-level functions which calculates boundaries of left and right nodes
110          * needed for spatial split.
111          *
112          * Operates with BVHReference, internally uses lower level API functions.
113          */
114         void split_triangle_reference(const BVHReference& ref,
115                                       const Mesh *mesh,
116                                       int dim,
117                                       float pos,
118                                       BoundBox& left_bounds,
119                                       BoundBox& right_bounds);
120         void split_curve_reference(const BVHReference& ref,
121                                    const Mesh *mesh,
122                                    int dim,
123                                    float pos,
124                                    BoundBox& left_bounds,
125                                    BoundBox& right_bounds);
126         void split_object_reference(const Object *object,
127                                     int dim,
128                                     float pos,
129                                     BoundBox& left_bounds,
130                                     BoundBox& right_bounds);
131 };
132
133 /* Mixed Object-Spatial Split */
134
135 class BVHMixedSplit
136 {
137 public:
138         BVHObjectSplit object;
139         BVHSpatialSplit spatial;
140
141         float leafSAH;
142         float nodeSAH;
143         float minSAH;
144
145         bool no_split;
146
147         __forceinline BVHMixedSplit(BVHBuild *builder,
148                                     BVHSpatialStorage *storage,
149                                     const BVHRange& range,
150                                     vector<BVHReference> *references,
151                                     int level)
152         {
153                 /* find split candidates. */
154                 float area = range.bounds().safe_area();
155
156                 leafSAH = area * builder->params.primitive_cost(range.size());
157                 nodeSAH = area * builder->params.node_cost(2);
158
159                 object = BVHObjectSplit(builder, storage, range, references, nodeSAH);
160
161                 if(builder->params.use_spatial_split && level < BVHParams::MAX_SPATIAL_DEPTH) {
162                         BoundBox overlap = object.left_bounds;
163                         overlap.intersect(object.right_bounds);
164
165                         if(overlap.safe_area() >= builder->spatial_min_overlap) {
166                                 spatial = BVHSpatialSplit(*builder,
167                                                           storage,
168                                                           range,
169                                                           references,
170                                                           nodeSAH);
171                         }
172                 }
173
174                 /* leaf SAH is the lowest => create leaf. */
175                 minSAH = min(min(leafSAH, object.sah), spatial.sah);
176                 no_split = (minSAH == leafSAH &&
177                             builder->range_within_max_leaf_size(range, *references));
178         }
179
180         __forceinline void split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range)
181         {
182                 if(builder->params.use_spatial_split && minSAH == spatial.sah)
183                         spatial.split(builder, left, right, range);
184                 if(!left.size() || !right.size())
185                         object.split(left, right, range);
186         }
187 };
188
189 CCL_NAMESPACE_END
190
191 #endif /* __BVH_SPLIT_H__ */
192