661541a8d231966d3302786e30cdf273e06d71e3
[blender.git] / intern / cycles / bvh / bvh_binning.cpp
1 /*
2  * Adapted from code copyright 2009-2011 Intel Corporation
3  * Modifications Copyright 2012, 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 //#define __KERNEL_SSE__
19
20 #include <stdlib.h>
21
22 #include "bvh_binning.h"
23
24 #include "util_algorithm.h"
25 #include "util_boundbox.h"
26 #include "util_types.h"
27
28 CCL_NAMESPACE_BEGIN
29
30 /* SSE replacements */
31
32 __forceinline void prefetch_L1 (const void* ptr) { }
33 __forceinline void prefetch_L2 (const void* ptr) { }
34 __forceinline void prefetch_L3 (const void* ptr) { }
35 __forceinline void prefetch_NTA(const void* ptr) { }
36
37 template<size_t src> __forceinline float extract(const int4& b)
38 { return b[src]; }
39 template<size_t dst> __forceinline const float4 insert(const float4& a, const float b)
40 { float4 r = a; r[dst] = b; return r; }
41
42 __forceinline int get_best_dimension(const float4& bestSAH)
43 {
44         // return (int)__bsf(movemask(reduce_min(bestSAH) == bestSAH));
45
46         float minSAH = min(bestSAH.x, min(bestSAH.y, bestSAH.z));
47
48         if(bestSAH.x == minSAH) return 0;
49         else if(bestSAH.y == minSAH) return 1;
50         else return 2;
51 }
52
53 /* BVH Object Binning */
54
55 BVHObjectBinning::BVHObjectBinning(const BVHRange& job, BVHReference *prims)
56 : BVHRange(job), splitSAH(FLT_MAX), dim(0), pos(0)
57 {
58         /* compute number of bins to use and precompute scaling factor for binning */
59         num_bins = min(size_t(MAX_BINS), size_t(4.0f + 0.05f*size()));
60         scale = rcp(cent_bounds().size()) * make_float3((float)num_bins);
61
62         /* initialize binning counter and bounds */
63         BoundBox bin_bounds[MAX_BINS][4];       /* bounds for every bin in every dimension */
64         int4 bin_count[MAX_BINS];                       /* number of primitives mapped to bin */
65
66         for(size_t i = 0; i < num_bins; i++) {
67                 bin_count[i] = make_int4(0);
68                 bin_bounds[i][0] = bin_bounds[i][1] = bin_bounds[i][2] = BoundBox::empty;
69         }
70
71         /* map geometry to bins, unrolled once */
72         {
73                 ssize_t i;
74
75                 for(i = 0; i < ssize_t(size()) - 1; i += 2) {
76                         prefetch_L2(&prims[start() + i + 8]);
77
78                         /* map even and odd primitive to bin */
79                         BVHReference prim0 = prims[start() + i + 0];
80                         BVHReference prim1 = prims[start() + i + 1];
81
82                         int4 bin0 = get_bin(prim0.bounds());
83                         int4 bin1 = get_bin(prim1.bounds());
84
85                         /* increase bounds for bins for even primitive */
86                         int b00 = extract<0>(bin0); bin_count[b00][0]++; bin_bounds[b00][0].grow(prim0.bounds());
87                         int b01 = extract<1>(bin0); bin_count[b01][1]++; bin_bounds[b01][1].grow(prim0.bounds());
88                         int b02 = extract<2>(bin0); bin_count[b02][2]++; bin_bounds[b02][2].grow(prim0.bounds());
89
90                         /* increase bounds of bins for odd primitive */
91                         int b10 = extract<0>(bin1); bin_count[b10][0]++; bin_bounds[b10][0].grow(prim1.bounds());
92                         int b11 = extract<1>(bin1); bin_count[b11][1]++; bin_bounds[b11][1].grow(prim1.bounds());
93                         int b12 = extract<2>(bin1); bin_count[b12][2]++; bin_bounds[b12][2].grow(prim1.bounds());
94                 }
95
96                 /* for uneven number of primitives */
97                 if(i < ssize_t(size())) {
98                         /* map primitive to bin */
99                         BVHReference prim0 = prims[start() + i];
100                         int4 bin0 = get_bin(prim0.bounds());
101
102                         /* increase bounds of bins */
103                         int b00 = extract<0>(bin0); bin_count[b00][0]++; bin_bounds[b00][0].grow(prim0.bounds());
104                         int b01 = extract<1>(bin0); bin_count[b01][1]++; bin_bounds[b01][1].grow(prim0.bounds());
105                         int b02 = extract<2>(bin0); bin_count[b02][2]++; bin_bounds[b02][2].grow(prim0.bounds());
106                 }
107         }
108
109         /* sweep from right to left and compute parallel prefix of merged bounds */
110         float4 r_area[MAX_BINS];        /* area of bounds of primitives on the right */
111         float4 r_count[MAX_BINS];       /* number of primitives on the right */
112         int4 count = make_int4(0);
113
114         BoundBox bx = BoundBox::empty;
115         BoundBox by = BoundBox::empty;
116         BoundBox bz = BoundBox::empty;
117
118         for(size_t i = num_bins - 1; i > 0; i--) {
119                 count = count + bin_count[i];
120                 r_count[i] = blocks(count);
121
122                 bx = merge(bx,bin_bounds[i][0]); r_area[i][0] = bx.half_area();
123                 by = merge(by,bin_bounds[i][1]); r_area[i][1] = by.half_area();
124                 bz = merge(bz,bin_bounds[i][2]); r_area[i][2] = bz.half_area();
125         }
126
127         /* sweep from left to right and compute SAH */
128         int4 ii = make_int4(1);
129         float4 bestSAH = make_float4(FLT_MAX);
130         int4 bestSplit = make_int4(-1);
131
132         count = make_int4(0);
133
134         bx = BoundBox::empty;
135         by = BoundBox::empty;
136         bz = BoundBox::empty;
137
138         for(size_t i = 1; i < num_bins; i++, ii += make_int4(1)) {
139                 count = count + bin_count[i-1];
140
141                 bx = merge(bx,bin_bounds[i-1][0]); float Ax = bx.half_area();
142                 by = merge(by,bin_bounds[i-1][1]); float Ay = by.half_area();
143                 bz = merge(bz,bin_bounds[i-1][2]); float Az = bz.half_area();
144
145                 float4 lCount = blocks(count);
146                 float4 lArea = make_float4(Ax,Ay,Az,Az);
147                 float4 sah = lArea*lCount + r_area[i]*r_count[i];
148
149                 bestSplit = select(sah < bestSAH,ii,bestSplit);
150                 bestSAH = min(sah,bestSAH);
151         }
152
153         int4 mask = float3_to_float4(cent_bounds().size()) <= make_float4(0.0f);
154         bestSAH = insert<3>(select(mask, make_float4(FLT_MAX), bestSAH), FLT_MAX);
155
156         /* find best dimension */
157         dim = get_best_dimension(bestSAH);
158         splitSAH = bestSAH[dim];
159         pos = bestSplit[dim];
160         leafSAH = bounds().half_area() * blocks(size());
161 }
162
163 void BVHObjectBinning::split(BVHReference* prims, BVHObjectBinning& left_o, BVHObjectBinning& right_o) const
164 {
165         size_t N = size();
166
167         BoundBox lgeom_bounds = BoundBox::empty;
168         BoundBox rgeom_bounds = BoundBox::empty;
169         BoundBox lcent_bounds = BoundBox::empty;
170         BoundBox rcent_bounds = BoundBox::empty;
171
172         ssize_t l = 0, r = N-1;
173
174         while(l <= r) {
175                 prefetch_L2(&prims[start() + l + 8]);
176                 prefetch_L2(&prims[start() + r - 8]);
177
178                 BVHReference prim = prims[start() + l];
179                 float3 center = prim.bounds().center2();
180
181                 if(get_bin(center)[dim] < pos) {
182                         lgeom_bounds.grow(prim.bounds());
183                         lcent_bounds.grow(center);
184                         l++;
185                 }
186                 else {
187                         rgeom_bounds.grow(prim.bounds());
188                         rcent_bounds.grow(center);
189                         swap(prims[start()+l],prims[start()+r]);
190                         r--;
191                 }
192         }
193
194         /* finish */
195         if(l != 0 && N-1-r != 0) {
196                 right_o = BVHObjectBinning(BVHRange(rgeom_bounds, rcent_bounds, start() + l, N-1-r), prims);
197                 left_o  = BVHObjectBinning(BVHRange(lgeom_bounds, lcent_bounds, start(), l), prims);
198                 return;
199         }
200
201         /* object medium split if we did not make progress, can happen when all
202            primitives have same centroid */
203         lgeom_bounds = BoundBox::empty;
204         rgeom_bounds = BoundBox::empty;
205         lcent_bounds = BoundBox::empty;
206         rcent_bounds = BoundBox::empty;
207
208         for(size_t i = 0; i < N/2; i++) {
209                 lgeom_bounds.grow(prims[start()+i].bounds());
210                 lcent_bounds.grow(prims[start()+i].bounds().center2());
211         }
212
213         for(size_t i = N/2; i < N; i++) {
214                 rgeom_bounds.grow(prims[start()+i].bounds());
215                 rcent_bounds.grow(prims[start()+i].bounds().center2());
216         }
217
218         right_o = BVHObjectBinning(BVHRange(rgeom_bounds, rcent_bounds, start() + N/2, N/2 + N%2), prims);
219         left_o  = BVHObjectBinning(BVHRange(lgeom_bounds, lcent_bounds, start(), N/2), prims);
220 }
221
222 CCL_NAMESPACE_END
223