style cleanup: block comments
[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                 r_area[i][3] = r_area[i][2];
126         }
127
128         /* sweep from left to right and compute SAH */
129         int4 ii = make_int4(1);
130         float4 bestSAH = make_float4(FLT_MAX);
131         int4 bestSplit = make_int4(-1);
132
133         count = make_int4(0);
134
135         bx = BoundBox::empty;
136         by = BoundBox::empty;
137         bz = BoundBox::empty;
138
139         for(size_t i = 1; i < num_bins; i++, ii += make_int4(1)) {
140                 count = count + bin_count[i-1];
141
142                 bx = merge(bx,bin_bounds[i-1][0]); float Ax = bx.half_area();
143                 by = merge(by,bin_bounds[i-1][1]); float Ay = by.half_area();
144                 bz = merge(bz,bin_bounds[i-1][2]); float Az = bz.half_area();
145
146                 float4 lCount = blocks(count);
147                 float4 lArea = make_float4(Ax,Ay,Az,Az);
148                 float4 sah = lArea*lCount + r_area[i]*r_count[i];
149
150                 bestSplit = select(sah < bestSAH,ii,bestSplit);
151                 bestSAH = min(sah,bestSAH);
152         }
153
154         int4 mask = float3_to_float4(cent_bounds().size()) <= make_float4(0.0f);
155         bestSAH = insert<3>(select(mask, make_float4(FLT_MAX), bestSAH), FLT_MAX);
156
157         /* find best dimension */
158         dim = get_best_dimension(bestSAH);
159         splitSAH = bestSAH[dim];
160         pos = bestSplit[dim];
161         leafSAH = bounds().half_area() * blocks(size());
162 }
163
164 void BVHObjectBinning::split(BVHReference* prims, BVHObjectBinning& left_o, BVHObjectBinning& right_o) const
165 {
166         size_t N = size();
167
168         BoundBox lgeom_bounds = BoundBox::empty;
169         BoundBox rgeom_bounds = BoundBox::empty;
170         BoundBox lcent_bounds = BoundBox::empty;
171         BoundBox rcent_bounds = BoundBox::empty;
172
173         ssize_t l = 0, r = N-1;
174
175         while(l <= r) {
176                 prefetch_L2(&prims[start() + l + 8]);
177                 prefetch_L2(&prims[start() + r - 8]);
178
179                 BVHReference prim = prims[start() + l];
180                 float3 center = prim.bounds().center2();
181
182                 if(get_bin(center)[dim] < pos) {
183                         lgeom_bounds.grow(prim.bounds());
184                         lcent_bounds.grow(center);
185                         l++;
186                 }
187                 else {
188                         rgeom_bounds.grow(prim.bounds());
189                         rcent_bounds.grow(center);
190                         swap(prims[start()+l],prims[start()+r]);
191                         r--;
192                 }
193         }
194
195         /* finish */
196         if(l != 0 && N-1-r != 0) {
197                 right_o = BVHObjectBinning(BVHRange(rgeom_bounds, rcent_bounds, start() + l, N-1-r), prims);
198                 left_o  = BVHObjectBinning(BVHRange(lgeom_bounds, lcent_bounds, start(), l), prims);
199                 return;
200         }
201
202         /* object medium split if we did not make progress, can happen when all
203          * primitives have same centroid */
204         lgeom_bounds = BoundBox::empty;
205         rgeom_bounds = BoundBox::empty;
206         lcent_bounds = BoundBox::empty;
207         rcent_bounds = BoundBox::empty;
208
209         for(size_t i = 0; i < N/2; i++) {
210                 lgeom_bounds.grow(prims[start()+i].bounds());
211                 lcent_bounds.grow(prims[start()+i].bounds().center2());
212         }
213
214         for(size_t i = N/2; i < N; i++) {
215                 rgeom_bounds.grow(prims[start()+i].bounds());
216                 rcent_bounds.grow(prims[start()+i].bounds().center2());
217         }
218
219         right_o = BVHObjectBinning(BVHRange(rgeom_bounds, rcent_bounds, start() + N/2, N/2 + N%2), prims);
220         left_o  = BVHObjectBinning(BVHRange(lgeom_bounds, lcent_bounds, start(), N/2), prims);
221 }
222
223 CCL_NAMESPACE_END
224