Blender  V3.3
jitter.cpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0
2  * Copyright 2019-2022 Blender Foundation */
3 
4 /* This file is based on "Progressive Multi-Jittered Sample Sequences"
5  * by Per Christensen, Andrew Kensler and Charlie Kilpatrick.
6  * http://graphics.pixar.com/library/ProgressiveMultiJitteredSampling/paper.pdf
7  *
8  * Performance can be improved in the future by implementing the new
9  * algorithm from Matt Pharr in http://jcgt.org/published/0008/01/04/
10  * "Efficient Generation of Points that Satisfy Two-Dimensional Elementary Intervals"
11  */
12 
13 #include "scene/jitter.h"
14 
15 #include <math.h>
16 #include <vector>
17 
19 
20 static uint cmj_hash(uint i, uint p)
21 {
22  i ^= p;
23  i ^= i >> 17;
24  i ^= i >> 10;
25  i *= 0xb36534e5;
26  i ^= i >> 12;
27  i ^= i >> 21;
28  i *= 0x93fc4795;
29  i ^= 0xdf6e307f;
30  i ^= i >> 17;
31  i *= 1 | p >> 18;
32 
33  return i;
34 }
35 
36 static float cmj_randfloat(uint i, uint p)
37 {
38  return cmj_hash(i, p) * (1.0f / 4294967808.0f);
39 }
40 
42  public:
43  static void generate_2D(float2 points[], int size, int rng_seed_in)
44  {
45  PMJ_Generator g(rng_seed_in);
46  points[0].x = g.rnd();
47  points[0].y = g.rnd();
48  int N = 1;
49  while (N < size) {
50  g.extend_sequence_even(points, N);
51  g.extend_sequence_odd(points, 2 * N);
52  N = 4 * N;
53  }
54  }
55 
56  protected:
57  PMJ_Generator(int rnd_seed_in) : num_samples(1), rnd_index(2), rnd_seed(rnd_seed_in)
58  {
59  }
60 
61  float rnd()
62  {
63  return cmj_randfloat(++rnd_index, rnd_seed);
64  }
65 
66  virtual void mark_occupied_strata(float2 points[], int N)
67  {
68  int NN = 2 * N;
69  for (int s = 0; s < NN; ++s) {
70  occupied1Dx[s] = occupied1Dy[s] = false;
71  }
72  for (int s = 0; s < N; ++s) {
73  int xstratum = (int)(NN * points[s].x);
74  int ystratum = (int)(NN * points[s].y);
75  occupied1Dx[xstratum] = true;
76  occupied1Dy[ystratum] = true;
77  }
78  }
79 
80  virtual void generate_sample_point(
81  float2 points[], float i, float j, float xhalf, float yhalf, int n, int N)
82  {
83  int NN = 2 * N;
84  float2 pt;
85  int xstratum, ystratum;
86  do {
87  pt.x = (i + 0.5f * (xhalf + rnd())) / n;
88  xstratum = (int)(NN * pt.x);
89  } while (occupied1Dx[xstratum]);
90  do {
91  pt.y = (j + 0.5f * (yhalf + rnd())) / n;
92  ystratum = (int)(NN * pt.y);
93  } while (occupied1Dy[ystratum]);
94  occupied1Dx[xstratum] = true;
95  occupied1Dy[ystratum] = true;
96  points[num_samples] = pt;
97  ++num_samples;
98  }
99 
100  void extend_sequence_even(float2 points[], int N)
101  {
102  int n = (int)sqrtf(N);
103  occupied1Dx.resize(2 * N);
104  occupied1Dy.resize(2 * N);
105  mark_occupied_strata(points, N);
106  for (int s = 0; s < N; ++s) {
107  float2 oldpt = points[s];
108  float i = floorf(n * oldpt.x);
109  float j = floorf(n * oldpt.y);
110  float xhalf = floorf(2.0f * (n * oldpt.x - i));
111  float yhalf = floorf(2.0f * (n * oldpt.y - j));
112  xhalf = 1.0f - xhalf;
113  yhalf = 1.0f - yhalf;
114  generate_sample_point(points, i, j, xhalf, yhalf, n, N);
115  }
116  }
117 
118  void extend_sequence_odd(float2 points[], int N)
119  {
120  int n = (int)sqrtf(N / 2);
121  occupied1Dx.resize(2 * N);
122  occupied1Dy.resize(2 * N);
123  mark_occupied_strata(points, N);
124  std::vector<float> xhalves(N / 2);
125  std::vector<float> yhalves(N / 2);
126  for (int s = 0; s < N / 2; ++s) {
127  float2 oldpt = points[s];
128  float i = floorf(n * oldpt.x);
129  float j = floorf(n * oldpt.y);
130  float xhalf = floorf(2.0f * (n * oldpt.x - i));
131  float yhalf = floorf(2.0f * (n * oldpt.y - j));
132  if (rnd() > 0.5f) {
133  xhalf = 1.0f - xhalf;
134  }
135  else {
136  yhalf = 1.0f - yhalf;
137  }
138  xhalves[s] = xhalf;
139  yhalves[s] = yhalf;
140  generate_sample_point(points, i, j, xhalf, yhalf, n, N);
141  }
142  for (int s = 0; s < N / 2; ++s) {
143  float2 oldpt = points[s];
144  float i = floorf(n * oldpt.x);
145  float j = floorf(n * oldpt.y);
146  float xhalf = 1.0f - xhalves[s];
147  float yhalf = 1.0f - yhalves[s];
148  generate_sample_point(points, i, j, xhalf, yhalf, n, N);
149  }
150  }
151 
152  std::vector<bool> occupied1Dx, occupied1Dy;
155 };
156 
158  protected:
160  float2 points[], float i, float j, float xhalf, float yhalf, int n, int N) override
161  {
162  int NN = 2 * N;
163  float2 pt;
164  do {
165  pt.x = (i + 0.5f * (xhalf + rnd())) / n;
166  pt.y = (j + 0.5f * (yhalf + rnd())) / n;
167  } while (is_occupied(pt, NN));
168  mark_occupied_strata1(pt, NN);
169  points[num_samples] = pt;
170  ++num_samples;
171  }
172 
173  void mark_occupied_strata(float2 points[], int N) override
174  {
175  int NN = 2 * N;
176  int num_shapes = (int)log2f(NN) + 1;
177  occupiedStrata.resize(num_shapes);
178  for (int shape = 0; shape < num_shapes; ++shape) {
179  occupiedStrata[shape].resize(NN);
180  for (int n = 0; n < NN; ++n) {
181  occupiedStrata[shape][n] = false;
182  }
183  }
184  for (int s = 0; s < N; ++s) {
185  mark_occupied_strata1(points[s], NN);
186  }
187  }
188 
189  void mark_occupied_strata1(float2 pt, int NN)
190  {
191  int shape = 0;
192  int xdivs = NN;
193  int ydivs = 1;
194  do {
195  int xstratum = (int)(xdivs * pt.x);
196  int ystratum = (int)(ydivs * pt.y);
197  size_t index = ystratum * xdivs + xstratum;
198  assert(index < NN);
199  occupiedStrata[shape][index] = true;
200  shape = shape + 1;
201  xdivs = xdivs / 2;
202  ydivs = ydivs * 2;
203  } while (xdivs > 0);
204  }
205 
206  bool is_occupied(float2 pt, int NN)
207  {
208  int shape = 0;
209  int xdivs = NN;
210  int ydivs = 1;
211  do {
212  int xstratum = (int)(xdivs * pt.x);
213  int ystratum = (int)(ydivs * pt.y);
214  size_t index = ystratum * xdivs + xstratum;
215  assert(index < NN);
216  if (occupiedStrata[shape][index]) {
217  return true;
218  }
219  shape = shape + 1;
220  xdivs = xdivs / 2;
221  ydivs = ydivs * 2;
222  } while (xdivs > 0);
223  return false;
224  }
225 
226  private:
227  std::vector<std::vector<bool>> occupiedStrata;
228 };
229 
230 static void shuffle(float2 points[], int size, int rng_seed)
231 {
232  if (rng_seed == 0) {
233  return;
234  }
235 
236  constexpr int odd[8] = {0, 1, 4, 5, 10, 11, 14, 15};
237  constexpr int even[8] = {2, 3, 6, 7, 8, 9, 12, 13};
238 
239  int rng_index = 0;
240  for (int yy = 0; yy < size / 16; ++yy) {
241  for (int xx = 0; xx < 8; ++xx) {
242  int other = (int)(cmj_randfloat(++rng_index, rng_seed) * (8.0f - xx) + xx);
243  float2 tmp = points[odd[other] + yy * 16];
244  points[odd[other] + yy * 16] = points[odd[xx] + yy * 16];
245  points[odd[xx] + yy * 16] = tmp;
246  }
247  for (int xx = 0; xx < 8; ++xx) {
248  int other = (int)(cmj_randfloat(++rng_index, rng_seed) * (8.0f - xx) + xx);
249  float2 tmp = points[even[other] + yy * 16];
250  points[even[other] + yy * 16] = points[even[xx] + yy * 16];
251  points[even[xx] + yy * 16] = tmp;
252  }
253  }
254 }
255 
256 void progressive_multi_jitter_generate_2D(float2 points[], int size, int rng_seed)
257 {
258  PMJ_Generator::generate_2D(points, size, rng_seed);
259  shuffle(points, size, rng_seed);
260 }
261 
262 void progressive_multi_jitter_02_generate_2D(float2 points[], int size, int rng_seed)
263 {
264  PMJ02_Generator::generate_2D(points, size, rng_seed);
265  shuffle(points, size, rng_seed);
266 }
267 
unsigned int uint
Definition: BLI_sys_types.h:67
_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 y
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
void mark_occupied_strata(float2 points[], int N) override
Definition: jitter.cpp:173
bool is_occupied(float2 pt, int NN)
Definition: jitter.cpp:206
void mark_occupied_strata1(float2 pt, int NN)
Definition: jitter.cpp:189
void generate_sample_point(float2 points[], float i, float j, float xhalf, float yhalf, int n, int N) override
Definition: jitter.cpp:159
float rnd()
Definition: jitter.cpp:61
int num_samples
Definition: jitter.cpp:153
std::vector< bool > occupied1Dx
Definition: jitter.cpp:152
static void generate_2D(float2 points[], int size, int rng_seed_in)
Definition: jitter.cpp:43
virtual void generate_sample_point(float2 points[], float i, float j, float xhalf, float yhalf, int n, int N)
Definition: jitter.cpp:80
PMJ_Generator(int rnd_seed_in)
Definition: jitter.cpp:57
void extend_sequence_even(float2 points[], int N)
Definition: jitter.cpp:100
void extend_sequence_odd(float2 points[], int N)
Definition: jitter.cpp:118
std::vector< bool > occupied1Dy
Definition: jitter.cpp:152
virtual void mark_occupied_strata(float2 points[], int N)
Definition: jitter.cpp:66
#define CCL_NAMESPACE_END
Definition: cuda/compat.h:9
static float cmj_randfloat(uint i, uint p)
Definition: jitter.cpp:36
void progressive_multi_jitter_02_generate_2D(float2 points[], int size, int rng_seed)
Definition: jitter.cpp:262
static void shuffle(float2 points[], int size, int rng_seed)
Definition: jitter.cpp:230
static CCL_NAMESPACE_BEGIN uint cmj_hash(uint i, uint p)
Definition: jitter.cpp:20
void progressive_multi_jitter_generate_2D(float2 points[], int size, int rng_seed)
Definition: jitter.cpp:256
#define N
#define floorf(x)
Definition: metal/compat.h:224
#define sqrtf(x)
Definition: metal/compat.h:243
static const pxr::TfToken g("g", pxr::TfToken::Immortal)
float x
Definition: types_float2.h:15
float y
Definition: types_float2.h:15