Fix incorrect FLT_MIN use
[blender.git] / intern / cycles / bvh / bvh_sort.cpp
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 #include "bvh_build.h"
19 #include "bvh_sort.h"
20
21 #include "util_algorithm.h"
22 #include "util_debug.h"
23 #include "util_task.h"
24
25 CCL_NAMESPACE_BEGIN
26
27 static const int BVH_SORT_THRESHOLD = 4096;
28
29 /* Silly workaround for float extended precision that happens when compiling
30  * on x86, due to one float staying in 80 bit precision register and the other
31  * not, which causes the strictly weak ordering to break.
32  */
33 #if !defined(__i386__)
34 #  define NO_EXTENDED_PRECISION
35 #else
36 #  define NO_EXTENDED_PRECISION volatile
37 #endif
38
39 struct BVHReferenceCompare {
40 public:
41         int dim;
42
43         BVHReferenceCompare(int dim_)
44         {
45                 dim = dim_;
46         }
47
48         /* Compare two references.
49          *
50          * Returns value is similar to return value of strcmp().
51          */
52         __forceinline int compare(const BVHReference& ra,
53                                   const BVHReference& rb) const
54         {
55                 NO_EXTENDED_PRECISION float ca = ra.bounds().min[dim] + ra.bounds().max[dim];
56                 NO_EXTENDED_PRECISION float cb = rb.bounds().min[dim] + rb.bounds().max[dim];
57
58                 if(ca < cb) return -1;
59                 else if(ca > cb) return 1;
60                 else if(ra.prim_object() < rb.prim_object()) return -1;
61                 else if(ra.prim_object() > rb.prim_object()) return 1;
62                 else if(ra.prim_index() < rb.prim_index()) return -1;
63                 else if(ra.prim_index() > rb.prim_index()) return 1;
64                 else if(ra.prim_type() < rb.prim_type()) return -1;
65                 else if(ra.prim_type() > rb.prim_type()) return 1;
66
67                 return 0;
68         }
69
70         bool operator()(const BVHReference& ra, const BVHReference& rb)
71         {
72                 return (compare(ra, rb) < 0);
73         }
74 };
75
76 static void bvh_reference_sort_threaded(TaskPool *task_pool,
77                                         BVHReference *data,
78                                         const int job_start,
79                                         const int job_end,
80                                         const BVHReferenceCompare& compare);
81
82 class BVHSortTask : public Task {
83 public:
84         BVHSortTask(TaskPool *task_pool,
85                     BVHReference *data,
86                     const int job_start,
87                     const int job_end,
88                     const BVHReferenceCompare& compare)
89         {
90                 run = function_bind(bvh_reference_sort_threaded,
91                                     task_pool,
92                                     data,
93                                     job_start,
94                                     job_end,
95                                     compare);
96         }
97 };
98
99 /* Multi-threaded reference sort. */
100 static void bvh_reference_sort_threaded(TaskPool *task_pool,
101                                         BVHReference *data,
102                                         const int job_start,
103                                         const int job_end,
104                                         const BVHReferenceCompare& compare)
105 {
106         int start = job_start, end = job_end;
107         bool have_work = (start < end);
108         while(have_work) {
109                 const int count = job_end - job_start;
110                 if(count < BVH_SORT_THRESHOLD) {
111                         /* Number of reference low enough, faster to finish the job
112                          * in one thread rather than to spawn more threads.
113                          */
114                         sort(data+job_start, data+job_end+1, compare);
115                         break;
116                 }
117                 /* Single QSort step.
118                  * Use median-of-three method for the pivot point.
119                  */
120                 int left = start, right = end;
121                 int center = (left + right) >> 1;
122                 if(compare.compare(data[left], data[center]) > 0) {
123                         swap(data[left], data[center]);
124                 }
125                 if(compare.compare(data[left], data[right]) > 0) {
126                         swap(data[left], data[right]);
127                 }
128                 if (compare.compare(data[center], data[right]) > 0) {
129                         swap(data[center], data[right]);
130                 }
131                 swap(data[center], data[right - 1]);
132                 BVHReference median = data[right - 1];
133                 do {
134                         while(compare.compare(data[left], median) < 0) {
135                                 ++left;
136                         }
137                         while(compare.compare(data[right], median) > 0) {
138                                 --right;
139                         }
140                         if(left <= right) {
141                                 swap(data[left], data[right]);
142                                 ++left;
143                                 --right;
144                         }
145                 } while(left <= right);
146                 /* We only create one new task here to reduce downside effects of
147                  * latency in TaskScheduler.
148                  * So generally current thread keeps working on the left part of the
149                  * array, and we create new task for the right side.
150                  * However, if there's nothing to be done in the left side of the array
151                  * we don't create any tasks and make it so current thread works on the
152                  * right side.
153                  */
154                 have_work = false;
155                 if(left < end) {
156                         if(start < right) {
157                                 task_pool->push(new BVHSortTask(task_pool,
158                                                                 data,
159                                                                 left, end,
160                                                                 compare), true);
161                         }
162                         else {
163                                 start = left;
164                                 have_work = true;
165                         }
166                 }
167                 if(start < right) {
168                         end = right;
169                         have_work = true;
170                 }
171         }
172 }
173
174 void bvh_reference_sort(int start, int end, BVHReference *data, int dim)
175 {
176         const int count = end - start;
177         BVHReferenceCompare compare(dim);
178         if(count < BVH_SORT_THRESHOLD) {
179                 /* It is important to not use any mutex if array is small enough,
180                  * otherwise we end up in situation when we're going to sleep far
181                  * too often.
182                  */
183                 sort(data+start, data+end, compare);
184         }
185         else {
186                 TaskPool task_pool;
187                 bvh_reference_sort_threaded(&task_pool, data, start, end - 1, dim);
188                 task_pool.wait_work();
189         }
190 }
191
192 CCL_NAMESPACE_END
193