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