Cycles: Only sort indices when finding a best dimension to split
[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
24 CCL_NAMESPACE_BEGIN
25
26 /* silly workaround for float extended precision that happens when compiling
27  * on x86, due to one float staying in 80 bit precision register and the other
28  * not, which causes the strictly weak ordering to break */
29 #if !defined(__i386__)
30 #define NO_EXTENDED_PRECISION
31 #else
32 #define NO_EXTENDED_PRECISION volatile
33 #endif
34
35 struct BVHReferenceCompare {
36 public:
37         int dim;
38
39         BVHReferenceCompare(int dim_)
40         {
41                 dim = dim_;
42         }
43
44         bool operator()(const BVHReference& ra, const BVHReference& rb)
45         {
46                 NO_EXTENDED_PRECISION float ca = ra.bounds().min[dim] + ra.bounds().max[dim];
47                 NO_EXTENDED_PRECISION float cb = rb.bounds().min[dim] + rb.bounds().max[dim];
48
49                 if(ca < cb) return true;
50                 else if(ca > cb) return false;
51                 else if(ra.prim_object() < rb.prim_object()) return true;
52                 else if(ra.prim_object() > rb.prim_object()) return false;
53                 else if(ra.prim_index() < rb.prim_index()) return true;
54                 else if(ra.prim_index() > rb.prim_index()) return false;
55                 else if(ra.prim_type() < rb.prim_type()) return true;
56                 else if(ra.prim_type() > rb.prim_type()) return false;
57
58                 return false;
59         }
60 };
61
62 void bvh_reference_sort(int start, int end, BVHReference *data, int dim)
63 {
64         BVHReferenceCompare compare(dim);
65         sort(data+start, data+end, compare);
66 }
67
68 struct BVHReferenceCompareIndexed {
69 public:
70         BVHReferenceCompareIndexed(int dim, const BVHReference *data, int start)
71         : dim_(dim),
72           start_(start),
73           data_(data)
74         {}
75
76         bool operator()(const int a, const int b)
77         {
78                 const BVHReference& ra = data_[start_ + a];
79                 const BVHReference& rb = data_[start_ + b];
80                 NO_EXTENDED_PRECISION float ca = ra.bounds().min[dim_] + ra.bounds().max[dim_];
81                 NO_EXTENDED_PRECISION float cb = rb.bounds().min[dim_] + rb.bounds().max[dim_];
82
83                 if(ca < cb) return true;
84                 else if(ca > cb) return false;
85                 else if(ra.prim_object() < rb.prim_object()) return true;
86                 else if(ra.prim_object() > rb.prim_object()) return false;
87                 else if(ra.prim_index() < rb.prim_index()) return true;
88                 else if(ra.prim_index() > rb.prim_index()) return false;
89                 else if(ra.prim_type() < rb.prim_type()) return true;
90                 else if(ra.prim_type() > rb.prim_type()) return false;
91
92                 return false;
93         }
94
95 private:
96         int dim_, start_;
97         const BVHReference *data_;
98 };
99
100 /* NOTE: indices are always from 0 to count, even in the cases when start is not
101  * zero. This is to simplify indexing in the object splitter. Index array is also
102  * always zero-based index.
103  */
104 void bvh_reference_sort_indices(int start,
105                                 int end,
106                                 const BVHReference *data,
107                                 int *indices,
108                                 int dim)
109 {
110         const int count = end - start;
111         for(int i = 0; i < count; ++i) {
112                 indices[i] = i;
113         }
114         BVHReferenceCompareIndexed compare(dim, data, start);
115         sort(indices, indices+count, compare);
116 }
117
118 CCL_NAMESPACE_END