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