1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 *
16 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17 * All rights reserved.
18 */
19
20 /** \file
21 * \ingroup bli
22 */
23
24 #include <math.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <time.h>
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_math.h"
32 #include "BLI_rand.h"
33 #include "BLI_rand.hh"
34 #include "BLI_threads.h"
35
36 /* defines BLI_INLINE */
37 #include "BLI_compiler_compat.h"
38
39 #include "BLI_strict_flags.h"
40 #include "BLI_sys_types.h"
41
42 extern "C" unsigned char BLI_noise_hash_uchar_512[512]; /* noise.c */
43 #define hash BLI_noise_hash_uchar_512
44
45 /**
46 * Random Number Generator.
47 */
48 struct RNG {
49 blender::RandomNumberGenerator rng;
50
51 MEM_CXX_CLASS_ALLOC_FUNCS("RNG")
52 };
53
BLI_rng_new(unsigned int seed)54 RNG *BLI_rng_new(unsigned int seed)
55 {
56 RNG *rng = new RNG();
57 rng->rng.seed(seed);
58 return rng;
59 }
60
61 /**
62 * A version of #BLI_rng_new that hashes the seed.
63 */
BLI_rng_new_srandom(unsigned int seed)64 RNG *BLI_rng_new_srandom(unsigned int seed)
65 {
66 RNG *rng = new RNG();
67 rng->rng.seed_random(seed);
68 return rng;
69 }
70
BLI_rng_copy(RNG * rng)71 RNG *BLI_rng_copy(RNG *rng)
72 {
73 return new RNG(*rng);
74 }
75
BLI_rng_free(RNG * rng)76 void BLI_rng_free(RNG *rng)
77 {
78 delete rng;
79 }
80
BLI_rng_seed(RNG * rng,unsigned int seed)81 void BLI_rng_seed(RNG *rng, unsigned int seed)
82 {
83 rng->rng.seed(seed);
84 }
85
86 /**
87 * Use a hash table to create better seed.
88 */
BLI_rng_srandom(RNG * rng,unsigned int seed)89 void BLI_rng_srandom(RNG *rng, unsigned int seed)
90 {
91 rng->rng.seed_random(seed);
92 }
93
BLI_rng_get_char_n(RNG * rng,char * bytes,size_t bytes_len)94 void BLI_rng_get_char_n(RNG *rng, char *bytes, size_t bytes_len)
95 {
96 rng->rng.get_bytes(blender::MutableSpan(bytes, static_cast<int64_t>(bytes_len)));
97 }
98
BLI_rng_get_int(RNG * rng)99 int BLI_rng_get_int(RNG *rng)
100 {
101 return rng->rng.get_int32();
102 }
103
BLI_rng_get_uint(RNG * rng)104 unsigned int BLI_rng_get_uint(RNG *rng)
105 {
106 return rng->rng.get_uint32();
107 }
108
109 /**
110 * \return Random value (0..1), but never 1.0.
111 */
BLI_rng_get_double(RNG * rng)112 double BLI_rng_get_double(RNG *rng)
113 {
114 return rng->rng.get_double();
115 }
116
117 /**
118 * \return Random value (0..1), but never 1.0.
119 */
BLI_rng_get_float(RNG * rng)120 float BLI_rng_get_float(RNG *rng)
121 {
122 return rng->rng.get_float();
123 }
124
BLI_rng_get_float_unit_v2(RNG * rng,float v[2])125 void BLI_rng_get_float_unit_v2(RNG *rng, float v[2])
126 {
127 copy_v2_v2(v, rng->rng.get_unit_float2());
128 }
129
BLI_rng_get_float_unit_v3(RNG * rng,float v[3])130 void BLI_rng_get_float_unit_v3(RNG *rng, float v[3])
131 {
132 copy_v3_v3(v, rng->rng.get_unit_float3());
133 }
134
135 /**
136 * Generate a random point inside given tri.
137 */
BLI_rng_get_tri_sample_float_v2(RNG * rng,const float v1[2],const float v2[2],const float v3[2],float r_pt[2])138 void BLI_rng_get_tri_sample_float_v2(
139 RNG *rng, const float v1[2], const float v2[2], const float v3[2], float r_pt[2])
140 {
141 copy_v2_v2(r_pt, rng->rng.get_triangle_sample(v1, v2, v3));
142 }
143
BLI_rng_shuffle_array(RNG * rng,void * data,unsigned int elem_size_i,unsigned int elem_tot)144 void BLI_rng_shuffle_array(RNG *rng, void *data, unsigned int elem_size_i, unsigned int elem_tot)
145 {
146 const uint elem_size = elem_size_i;
147 unsigned int i = elem_tot;
148 void *temp;
149
150 if (elem_tot <= 1) {
151 return;
152 }
153
154 temp = malloc(elem_size);
155
156 while (i--) {
157 unsigned int j = BLI_rng_get_uint(rng) % elem_tot;
158 if (i != j) {
159 void *iElem = (unsigned char *)data + i * elem_size_i;
160 void *jElem = (unsigned char *)data + j * elem_size_i;
161 memcpy(temp, iElem, elem_size);
162 memcpy(iElem, jElem, elem_size);
163 memcpy(jElem, temp, elem_size);
164 }
165 }
166
167 free(temp);
168 }
169
170 /**
171 * Simulate getting \a n random values.
172 *
173 * \note Useful when threaded code needs consistent values, independent of task division.
174 */
BLI_rng_skip(RNG * rng,int n)175 void BLI_rng_skip(RNG *rng, int n)
176 {
177 rng->rng.skip((uint)n);
178 }
179
180 /***/
181
182 /* fill an array with random numbers */
BLI_array_frand(float * ar,int count,unsigned int seed)183 void BLI_array_frand(float *ar, int count, unsigned int seed)
184 {
185 RNG rng;
186
187 BLI_rng_srandom(&rng, seed);
188
189 for (int i = 0; i < count; i++) {
190 ar[i] = BLI_rng_get_float(&rng);
191 }
192 }
193
BLI_hash_frand(unsigned int seed)194 float BLI_hash_frand(unsigned int seed)
195 {
196 RNG rng;
197
198 BLI_rng_srandom(&rng, seed);
199 return BLI_rng_get_float(&rng);
200 }
201
BLI_array_randomize(void * data,unsigned int elem_size,unsigned int elem_tot,unsigned int seed)202 void BLI_array_randomize(void *data,
203 unsigned int elem_size,
204 unsigned int elem_tot,
205 unsigned int seed)
206 {
207 RNG rng;
208
209 BLI_rng_seed(&rng, seed);
210 BLI_rng_shuffle_array(&rng, data, elem_size, elem_tot);
211 }
212
213 /* ********* for threaded random ************** */
214
215 static RNG rng_tab[BLENDER_MAX_THREADS];
216
BLI_thread_srandom(int thread,unsigned int seed)217 void BLI_thread_srandom(int thread, unsigned int seed)
218 {
219 if (thread >= BLENDER_MAX_THREADS) {
220 thread = 0;
221 }
222
223 BLI_rng_seed(&rng_tab[thread], seed + hash[seed & 255]);
224 seed = BLI_rng_get_uint(&rng_tab[thread]);
225 BLI_rng_seed(&rng_tab[thread], seed + hash[seed & 255]);
226 seed = BLI_rng_get_uint(&rng_tab[thread]);
227 BLI_rng_seed(&rng_tab[thread], seed + hash[seed & 255]);
228 }
229
BLI_thread_rand(int thread)230 int BLI_thread_rand(int thread)
231 {
232 return BLI_rng_get_int(&rng_tab[thread]);
233 }
234
BLI_thread_frand(int thread)235 float BLI_thread_frand(int thread)
236 {
237 return BLI_rng_get_float(&rng_tab[thread]);
238 }
239
240 struct RNG_THREAD_ARRAY {
241 RNG rng_tab[BLENDER_MAX_THREADS];
242 };
243
BLI_rng_threaded_new(void)244 RNG_THREAD_ARRAY *BLI_rng_threaded_new(void)
245 {
246 unsigned int i;
247 RNG_THREAD_ARRAY *rngarr = (RNG_THREAD_ARRAY *)MEM_mallocN(sizeof(RNG_THREAD_ARRAY),
248 "random_array");
249
250 for (i = 0; i < BLENDER_MAX_THREADS; i++) {
251 BLI_rng_srandom(&rngarr->rng_tab[i], (unsigned int)clock());
252 }
253
254 return rngarr;
255 }
256
BLI_rng_threaded_free(struct RNG_THREAD_ARRAY * rngarr)257 void BLI_rng_threaded_free(struct RNG_THREAD_ARRAY *rngarr)
258 {
259 MEM_freeN(rngarr);
260 }
261
BLI_rng_thread_rand(RNG_THREAD_ARRAY * rngarr,int thread)262 int BLI_rng_thread_rand(RNG_THREAD_ARRAY *rngarr, int thread)
263 {
264 return BLI_rng_get_int(&rngarr->rng_tab[thread]);
265 }
266
267 /* ********* Low-discrepancy sequences ************** */
268
269 /* incremental halton sequence generator, from:
270 * "Instant Radiosity", Keller A. */
halton_ex(double invprimes,double * offset)271 BLI_INLINE double halton_ex(double invprimes, double *offset)
272 {
273 double e = fabs((1.0 - *offset) - 1e-10);
274
275 if (invprimes >= e) {
276 double lasth;
277 double h = invprimes;
278
279 do {
280 lasth = h;
281 h *= invprimes;
282 } while (h >= e);
283
284 *offset += ((lasth + h) - 1.0);
285 }
286 else {
287 *offset += invprimes;
288 }
289
290 return *offset;
291 }
292
BLI_halton_1d(unsigned int prime,double offset,int n,double * r)293 void BLI_halton_1d(unsigned int prime, double offset, int n, double *r)
294 {
295 const double invprime = 1.0 / (double)prime;
296
297 *r = 0.0;
298
299 for (int s = 0; s < n; s++) {
300 *r = halton_ex(invprime, &offset);
301 }
302 }
303
BLI_halton_2d(const unsigned int prime[2],double offset[2],int n,double * r)304 void BLI_halton_2d(const unsigned int prime[2], double offset[2], int n, double *r)
305 {
306 const double invprimes[2] = {1.0 / (double)prime[0], 1.0 / (double)prime[1]};
307
308 r[0] = r[1] = 0.0;
309
310 for (int s = 0; s < n; s++) {
311 for (int i = 0; i < 2; i++) {
312 r[i] = halton_ex(invprimes[i], &offset[i]);
313 }
314 }
315 }
316
BLI_halton_3d(const unsigned int prime[3],double offset[3],int n,double * r)317 void BLI_halton_3d(const unsigned int prime[3], double offset[3], int n, double *r)
318 {
319 const double invprimes[3] = {
320 1.0 / (double)prime[0], 1.0 / (double)prime[1], 1.0 / (double)prime[2]};
321
322 r[0] = r[1] = r[2] = 0.0;
323
324 for (int s = 0; s < n; s++) {
325 for (int i = 0; i < 3; i++) {
326 r[i] = halton_ex(invprimes[i], &offset[i]);
327 }
328 }
329 }
330
BLI_halton_2d_sequence(const unsigned int prime[2],double offset[2],int n,double * r)331 void BLI_halton_2d_sequence(const unsigned int prime[2], double offset[2], int n, double *r)
332 {
333 const double invprimes[2] = {1.0 / (double)prime[0], 1.0 / (double)prime[1]};
334
335 for (int s = 0; s < n; s++) {
336 for (int i = 0; i < 2; i++) {
337 r[s * 2 + i] = halton_ex(invprimes[i], &offset[i]);
338 }
339 }
340 }
341
342 /* From "Sampling with Hammersley and Halton Points" TT Wong
343 * Appendix: Source Code 1 */
radical_inverse(unsigned int n)344 BLI_INLINE double radical_inverse(unsigned int n)
345 {
346 double u = 0;
347
348 /* This reverse the bit-wise representation
349 * around the decimal point. */
350 for (double p = 0.5; n; p *= 0.5, n >>= 1) {
351 if (n & 1) {
352 u += p;
353 }
354 }
355
356 return u;
357 }
358
BLI_hammersley_1d(unsigned int n,double * r)359 void BLI_hammersley_1d(unsigned int n, double *r)
360 {
361 *r = radical_inverse(n);
362 }
363
BLI_hammersley_2d_sequence(unsigned int n,double * r)364 void BLI_hammersley_2d_sequence(unsigned int n, double *r)
365 {
366 for (unsigned int s = 0; s < n; s++) {
367 r[s * 2 + 0] = (double)(s + 0.5) / (double)n;
368 r[s * 2 + 1] = radical_inverse(s);
369 }
370 }
371
372 namespace blender {
373
374 /**
375 * Set a randomized hash of the value as seed.
376 */
seed_random(uint32_t seed)377 void RandomNumberGenerator::seed_random(uint32_t seed)
378 {
379 this->seed(seed + hash[seed & 255]);
380 seed = this->get_uint32();
381 this->seed(seed + hash[seed & 255]);
382 seed = this->get_uint32();
383 this->seed(seed + hash[seed & 255]);
384 }
385
get_unit_float2()386 float2 RandomNumberGenerator::get_unit_float2()
387 {
388 float a = (float)(M_PI * 2.0) * this->get_float();
389 return {cosf(a), sinf(a)};
390 }
391
get_unit_float3()392 float3 RandomNumberGenerator::get_unit_float3()
393 {
394 float z = (2.0f * this->get_float()) - 1.0f;
395 float r = 1.0f - z * z;
396 if (r > 0.0f) {
397 float a = (float)(M_PI * 2.0) * this->get_float();
398 r = sqrtf(r);
399 float x = r * cosf(a);
400 float y = r * sinf(a);
401 return {x, y, z};
402 }
403 return {0.0f, 0.0f, 1.0f};
404 }
405
406 /**
407 * Generate a random point inside the given triangle.
408 */
get_triangle_sample(float2 v1,float2 v2,float2 v3)409 float2 RandomNumberGenerator::get_triangle_sample(float2 v1, float2 v2, float2 v3)
410 {
411 float u = this->get_float();
412 float v = this->get_float();
413
414 if (u + v > 1.0f) {
415 u = 1.0f - u;
416 v = 1.0f - v;
417 }
418
419 float2 side_u = v2 - v1;
420 float2 side_v = v3 - v1;
421
422 float2 sample = v1;
423 sample += side_u * u;
424 sample += side_v * v;
425 return sample;
426 }
427
get_bytes(MutableSpan<char> r_bytes)428 void RandomNumberGenerator::get_bytes(MutableSpan<char> r_bytes)
429 {
430 constexpr int64_t mask_bytes = 2;
431 constexpr int64_t rand_stride = static_cast<int64_t>(sizeof(x_)) - mask_bytes;
432
433 int64_t last_len = 0;
434 int64_t trim_len = r_bytes.size();
435
436 if (trim_len > rand_stride) {
437 last_len = trim_len % rand_stride;
438 trim_len = trim_len - last_len;
439 }
440 else {
441 trim_len = 0;
442 last_len = r_bytes.size();
443 }
444
445 const char *data_src = (const char *)&x_;
446 int64_t i = 0;
447 while (i != trim_len) {
448 BLI_assert(i < trim_len);
449 #ifdef __BIG_ENDIAN__
450 for (int64_t j = (rand_stride + mask_bytes) - 1; j != mask_bytes - 1; j--)
451 #else
452 for (int64_t j = 0; j != rand_stride; j++)
453 #endif
454 {
455 r_bytes[i++] = data_src[j];
456 }
457 this->step();
458 }
459 if (last_len) {
460 for (int64_t j = 0; j != last_len; j++) {
461 r_bytes[i++] = data_src[j];
462 }
463 }
464 }
465
466 } // namespace blender
467