Blender  V3.3
sort.cpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0
2  * Adapted from code copyright 2009-2010 NVIDIA Corporation
3  * Modifications Copyright 2011-2022 Blender Foundation. */
4 
5 #include "bvh/sort.h"
6 
7 #include "bvh/build.h"
8 
9 #include "util/algorithm.h"
10 #include "util/task.h"
11 
13 
14 static const int BVH_SORT_THRESHOLD = 4096;
15 
17  public:
18  int dim;
21 
24  const Transform *aligned_space)
26  {
27  }
28 
30  {
31  return (aligned_space != NULL) ?
33  prim.bounds();
34  }
35 
36  /* Compare two references.
37  *
38  * Returns value is similar to return value of strcmp().
39  */
40  __forceinline int compare(const BVHReference &ra, const BVHReference &rb) const
41  {
42  BoundBox ra_bounds = get_prim_bounds(ra), rb_bounds = get_prim_bounds(rb);
43  float ca = ra_bounds.min[dim] + ra_bounds.max[dim];
44  float cb = rb_bounds.min[dim] + rb_bounds.max[dim];
45 
46  if (ca < cb)
47  return -1;
48  else if (ca > cb)
49  return 1;
50  else if (ra.prim_object() < rb.prim_object())
51  return -1;
52  else if (ra.prim_object() > rb.prim_object())
53  return 1;
54  else if (ra.prim_index() < rb.prim_index())
55  return -1;
56  else if (ra.prim_index() > rb.prim_index())
57  return 1;
58  else if (ra.prim_type() < rb.prim_type())
59  return -1;
60  else if (ra.prim_type() > rb.prim_type())
61  return 1;
62 
63  return 0;
64  }
65 
66  bool operator()(const BVHReference &ra, const BVHReference &rb)
67  {
68  return (compare(ra, rb) < 0);
69  }
70 };
71 
74  const int job_start,
75  const int job_end,
76  const BVHReferenceCompare &compare);
77 
78 /* Multi-threaded reference sort. */
81  const int job_start,
82  const int job_end,
83  const BVHReferenceCompare &compare)
84 {
85  int start = job_start, end = job_end;
86  bool have_work = (start < end);
87  while (have_work) {
88  const int count = job_end - job_start;
89  if (count < BVH_SORT_THRESHOLD) {
90  /* Number of reference low enough, faster to finish the job
91  * in one thread rather than to spawn more threads.
92  */
93  sort(data + job_start, data + job_end + 1, compare);
94  break;
95  }
96  /* Single QSort step.
97  * Use median-of-three method for the pivot point.
98  */
99  int left = start, right = end;
100  int center = (left + right) >> 1;
101  if (compare.compare(data[left], data[center]) > 0) {
102  swap(data[left], data[center]);
103  }
104  if (compare.compare(data[left], data[right]) > 0) {
105  swap(data[left], data[right]);
106  }
107  if (compare.compare(data[center], data[right]) > 0) {
108  swap(data[center], data[right]);
109  }
110  swap(data[center], data[right - 1]);
111  BVHReference median = data[right - 1];
112  do {
113  while (compare.compare(data[left], median) < 0) {
114  ++left;
115  }
116  while (compare.compare(data[right], median) > 0) {
117  --right;
118  }
119  if (left <= right) {
120  swap(data[left], data[right]);
121  ++left;
122  --right;
123  }
124  } while (left <= right);
125  /* We only create one new task here to reduce downside effects of
126  * latency in TaskScheduler.
127  * So generally current thread keeps working on the left part of the
128  * array, and we create new task for the right side.
129  * However, if there's nothing to be done in the left side of the array
130  * we don't create any tasks and make it so current thread works on the
131  * right side.
132  */
133  have_work = false;
134  if (left < end) {
135  if (start < right) {
136  task_pool->push(
138  }
139  else {
140  start = left;
141  have_work = true;
142  }
143  }
144  if (start < right) {
145  end = right;
146  have_work = true;
147  }
148  }
149 }
150 
151 void bvh_reference_sort(int start,
152  int end,
154  int dim,
155  const BVHUnaligned *unaligned_heuristic,
156  const Transform *aligned_space)
157 {
158  const int count = end - start;
159  BVHReferenceCompare compare(dim, unaligned_heuristic, aligned_space);
160  if (count < BVH_SORT_THRESHOLD) {
161  /* It is important to not use any mutex if array is small enough,
162  * otherwise we end up in situation when we're going to sleep far
163  * too often.
164  */
165  sort(data + start, data + end, compare);
166  }
167  else {
169  bvh_reference_sort_threaded(&task_pool, data, start, end - 1, compare);
171  }
172 }
173 
void swap(T &a, T &b)
Definition: Common.h:19
NSNotificationCenter * center
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble right
void sort(btMatrix3x3 &U, btVector3 &sigma, btMatrix3x3 &V, int t)
Helper function of 3X3 SVD for sorting singular values.
__forceinline int prim_type() const
Definition: params.h:215
__forceinline int prim_object() const
Definition: params.h:211
__forceinline const BoundBox & bounds() const
Definition: params.h:203
__forceinline int prim_index() const
Definition: params.h:207
BoundBox compute_aligned_prim_boundbox(const BVHReference &prim, const Transform &aligned_space) const
Definition: unaligned.cpp:77
#define CCL_NAMESPACE_END
Definition: cuda/compat.h:9
#define function_bind
TaskPool * task_pool
int count
static int left
#define __forceinline
void bvh_reference_sort(int start, int end, BVHReference *data, int dim, const BVHUnaligned *unaligned_heuristic, const Transform *aligned_space)
Definition: sort.cpp:151
static CCL_NAMESPACE_BEGIN const int BVH_SORT_THRESHOLD
Definition: sort.cpp:14
static void bvh_reference_sort_threaded(TaskPool *task_pool, BVHReference *data, const int job_start, const int job_end, const BVHReferenceCompare &compare)
Definition: sort.cpp:79
const Transform * aligned_space
Definition: sort.cpp:20
const BVHUnaligned * unaligned_heuristic
Definition: sort.cpp:19
__forceinline BoundBox get_prim_bounds(const BVHReference &prim) const
Definition: sort.cpp:29
__forceinline int compare(const BVHReference &ra, const BVHReference &rb) const
Definition: sort.cpp:40
bool operator()(const BVHReference &ra, const BVHReference &rb)
Definition: sort.cpp:66
BVHReferenceCompare(int dim, const BVHUnaligned *unaligned_heuristic, const Transform *aligned_space)
Definition: sort.cpp:22
float3 max
Definition: boundbox.h:21
float3 min
Definition: boundbox.h:21
void push(TaskRunFunction &&task)
Definition: task.cpp:23
void wait_work(Summary *stats=NULL)
Definition: task.cpp:29