Blender V5.3
rand.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2001-2002 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <cmath>
10#include <cstdlib>
11#include <cstring>
12#include <ctime>
13#include <random>
14
15#include "MEM_guardedalloc.h"
16
17#include "BLI_bitmap.hh"
19#include "BLI_math_vector_c.hh"
20#include "BLI_noise_c.hh"
21#include "BLI_rand.hh"
22#include "BLI_rand_c.hh"
23#include "BLI_sys_types.hh"
24#include "BLI_threads.hh"
25
26#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
27
28namespace blender {
29
30#define hash BLI_noise_hash_uchar_512
31
35struct RNG {
37
38 MEM_CXX_CLASS_ALLOC_FUNCS("RNG")
39};
40
42{
43 RNG *rng = new RNG();
44 rng->rng.seed(seed);
45 return rng;
46}
47
49{
50 RNG *rng = new RNG();
51 rng->rng.seed_random(seed);
52 return rng;
53}
54
55void BLI_rng_free(RNG *rng)
56{
57 delete rng;
58}
59
60void BLI_rng_seed(RNG *rng, uint seed)
61{
62 rng->rng.seed(seed);
63}
64
65void BLI_rng_srandom(RNG *rng, uint seed)
66{
67 rng->rng.seed_random(seed);
68}
69
70void BLI_rng_get_char_n(RNG *rng, char *bytes, size_t bytes_len)
71{
72 rng->rng.get_bytes(MutableSpan(bytes, int64_t(bytes_len)));
73}
74
76{
77 return rng->rng.get_int32();
78}
79
81{
82 return rng->rng.get_uint32();
83}
84
86{
87 return rng->rng.get_double();
88}
89
91{
92 return rng->rng.get_float();
93}
94
96 RNG *rng, const float v1[2], const float v2[2], const float v3[2], float r_pt[2])
97{
98 copy_v2_v2(r_pt, rng->rng.get_triangle_sample(v1, v2, v3));
99}
100
101void BLI_rng_shuffle_array(RNG *rng, void *data, uint elem_size_i, uint elem_num)
102{
103 if (elem_num <= 1) {
104 return;
105 }
106
107 const uint elem_size = elem_size_i;
108 uint i = elem_num;
109 void *temp = malloc(elem_size);
110
111 while (i--) {
112 const uint j = BLI_rng_get_uint(rng) % elem_num;
113 if (i != j) {
114 void *iElem = static_cast<uchar *>(data) + i * elem_size_i;
115 void *jElem = static_cast<uchar *>(data) + j * elem_size_i;
116 memcpy(temp, iElem, elem_size);
117 memcpy(iElem, jElem, elem_size);
118 memcpy(jElem, temp, elem_size);
119 }
120 }
121
122 free(temp);
123}
124
125void BLI_rng_shuffle_bitmap(RNG *rng, BLI_bitmap *bitmap, uint bits_num)
126{
127 if (bits_num <= 1) {
128 return;
129 }
130
131 uint i = bits_num;
132 while (i--) {
133 const uint j = BLI_rng_get_uint(rng) % bits_num;
134 if (i != j) {
135 const bool i_bit = BLI_BITMAP_TEST(bitmap, i);
136 const bool j_bit = BLI_BITMAP_TEST(bitmap, j);
137 BLI_BITMAP_SET(bitmap, i, j_bit);
138 BLI_BITMAP_SET(bitmap, j, i_bit);
139 }
140 }
141}
142
143void BLI_rng_skip(RNG *rng, int n)
144{
145 rng->rng.skip(uint(n));
146}
147
148/***/
149
151{
152 RNG rng;
153
154 BLI_rng_srandom(&rng, seed);
155 return BLI_rng_get_float(&rng);
156}
157
158void BLI_array_randomize(void *data, uint elem_size, uint elem_num, uint seed)
159{
160 RNG rng;
161
162 BLI_rng_seed(&rng, seed);
163 BLI_rng_shuffle_array(&rng, data, elem_size, elem_num);
164}
165
166void BLI_bitmap_randomize(BLI_bitmap *bitmap, uint bits_num, uint seed)
167{
168 RNG rng;
169
170 BLI_rng_seed(&rng, seed);
171 BLI_rng_shuffle_bitmap(&rng, bitmap, bits_num);
172}
173
174/* ********* for threaded random ************** */
175
177 std::array<RNG, BLENDER_MAX_THREADS> rng_tab;
178};
179
181{
182 uint i;
183 RNG_THREAD_ARRAY *rngarr = MEM_new<RNG_THREAD_ARRAY>("random_array");
184
185 for (i = 0; i < BLENDER_MAX_THREADS; i++) {
186 BLI_rng_srandom(&rngarr->rng_tab[i], uint(clock()));
187 }
188
189 return rngarr;
190}
191
193{
194 MEM_delete(rngarr);
195}
196
198{
199 return BLI_rng_get_int(&rngarr->rng_tab[size_t(thread)]);
200}
201
202/* ********* Low-discrepancy sequences ************** */
203
204/* incremental halton sequence generator, from:
205 * "Instant Radiosity", Keller A. */
206BLI_INLINE double halton_ex(double invprimes, double *offset)
207{
208 double e = fabs((1.0 - *offset) - 1e-10);
209
210 if (invprimes >= e) {
211 double lasth;
212 double h = invprimes;
213
214 do {
215 lasth = h;
216 h *= invprimes;
217 } while (h >= e);
218
219 *offset += ((lasth + h) - 1.0);
220 }
221 else {
222 *offset += invprimes;
223 }
224
225 return *offset;
226}
227
228void BLI_halton_1d(uint prime, double offset, int n, double *r)
229{
230 const double invprime = 1.0 / double(prime);
231
232 *r = 0.0;
233
234 for (int s = 0; s < n; s++) {
235 *r = halton_ex(invprime, &offset);
236 }
237}
238
239void BLI_halton_2d(const uint prime[2], double offset[2], int n, double *r)
240{
241 const double invprimes[2] = {1.0 / double(prime[0]), 1.0 / double(prime[1])};
242
243 r[0] = r[1] = 0.0;
244
245 for (int s = 0; s < n; s++) {
246 for (int i = 0; i < 2; i++) {
247 r[i] = halton_ex(invprimes[i], &offset[i]);
248 }
249 }
250}
251
252void BLI_halton_3d(const uint prime[3], double offset[3], int n, double *r)
253{
254 const double invprimes[3] = {
255 1.0 / double(prime[0]), 1.0 / double(prime[1]), 1.0 / double(prime[2])};
256
257 r[0] = r[1] = r[2] = 0.0;
258
259 for (int s = 0; s < n; s++) {
260 for (int i = 0; i < 3; i++) {
261 r[i] = halton_ex(invprimes[i], &offset[i]);
262 }
263 }
264}
265
266/* From "Sampling with Hammersley and Halton Points" TT Wong
267 * Appendix: Source Code 1 */
269{
270 double u = 0;
271
272 /* This reverse the bit-wise representation
273 * around the decimal point. */
274 for (double p = 0.5; n; p *= 0.5, n >>= 1) {
275 if (n & 1) {
276 u += p;
277 }
278 }
279
280 return u;
281}
282
283void BLI_hammersley_1d(uint n, double *r)
284{
285 *r = radical_inverse(n);
286}
287
289{
290 std::random_device rd;
291 std::mt19937 e{rd()};
292 std::uniform_int_distribution<uint32_t> dist;
293 const uint32_t seed = dist(e);
295}
296
298{
299 this->seed(seed + hash[seed & 255]);
300 seed = this->get_uint32();
301 this->seed(seed + hash[seed & 255]);
302 seed = this->get_uint32();
303 this->seed(seed + hash[seed & 255]);
304}
305
307{
308 /* Support for negative values can be added when necessary. */
309 BLI_assert(x >= 0.0f);
310 const float round_up_probability = fractf(x);
311 const bool round_up = round_up_probability > this->get_float();
312 return int(x) + int(round_up);
313}
314
316{
317 float a = float(M_PI * 2.0) * this->get_float();
318 return {cosf(a), sinf(a)};
319}
320
322{
323 float z = (2.0f * this->get_float()) - 1.0f;
324 float r = 1.0f - z * z;
325 if (r > 0.0f) {
326 float a = float(M_PI * 2.0) * this->get_float();
327 r = sqrtf(r);
328 float x = r * cosf(a);
329 float y = r * sinf(a);
330 return {x, y, z};
331 }
332 return {0.0f, 0.0f, 1.0f};
333}
334
336{
337 float u = this->get_float();
338 float v = this->get_float();
339
340 if (u + v > 1.0f) {
341 u = 1.0f - u;
342 v = 1.0f - v;
343 }
344
345 float2 side_u = v2 - v1;
346 float2 side_v = v3 - v1;
347
348 float2 sample = v1;
349 sample += side_u * u;
350 sample += side_v * v;
351 return sample;
352}
353
355{
356 float u = this->get_float();
357 float v = this->get_float();
358
359 if (u + v > 1.0f) {
360 u = 1.0f - u;
361 v = 1.0f - v;
362 }
363
364 float3 side_u = v2 - v1;
365 float3 side_v = v3 - v1;
366
367 float3 sample = v1;
368 sample += side_u * u;
369 sample += side_v * v;
370 return sample;
371}
372
374{
375 constexpr int64_t mask_bytes = 2;
376 constexpr int64_t rand_stride = int64_t(sizeof(x_)) - mask_bytes;
377
378 int64_t last_len = 0;
379 int64_t trim_len = r_bytes.size();
380
381 if (trim_len > rand_stride) {
382 last_len = trim_len % rand_stride;
383 trim_len = trim_len - last_len;
384 }
385 else {
386 trim_len = 0;
387 last_len = r_bytes.size();
388 }
389
390 const char *data_src = reinterpret_cast<const char *>(&x_);
391 int64_t i = 0;
392 while (i != trim_len) {
393 BLI_assert(i < trim_len);
394 /* NOTE: this is endianness-sensitive.
395 * Big Endian needs to iterate in reverse, with a `mask_bytes - 1` offset. */
396 for (int64_t j = 0; j != rand_stride; j++) {
397 r_bytes[i++] = data_src[j];
398 }
399 this->step();
400 }
401 if (last_len) {
402 for (int64_t j = 0; j != last_len; j++) {
403 r_bytes[i++] = data_src[j];
404 }
405 }
406}
407
408} // namespace blender
#define BLI_BITMAP_TEST(_bitmap, _index)
Definition BLI_bitmap.hh:63
#define BLI_BITMAP_SET(_bitmap, _index, _set)
#define M_PI
Random number functions.
#define BLENDER_MAX_THREADS
Read Blender memory allocation and freeing.
#define BLI_INLINE
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
Definition btQuadWord.h:117
constexpr MutableSpan()=default
constexpr int64_t size() const
Definition BLI_span.hh:499
void get_bytes(MutableSpan< char > r_bytes)
Definition rand.cc:373
int round_probabilistic(float x)
Definition rand.cc:306
RandomNumberGenerator(uint32_t seed=0)
Definition BLI_rand.hh:21
void seed_random(uint32_t seed)
Definition rand.cc:297
float3 get_triangle_sample_3d(float3 v1, float3 v2, float3 v3)
Definition rand.cc:354
float2 get_triangle_sample(float2 v1, float2 v2, float2 v3)
Definition rand.cc:335
void seed(uint32_t seed)
Definition BLI_rand.hh:35
static RandomNumberGenerator from_random_seed()
Definition rand.cc:288
ccl_device_inline dual3 fabs(const ccl_private dual3 &a)
Definition math_dual.h:241
void free(Subdiv *subdiv)
Definition subdiv.cc:192
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
void BLI_halton_2d(const unsigned int prime[2], double offset[2], int n, double *r)
Definition rand.cc:239
unsigned int uint
Definition BKE_text.h:55
void void BLI_rng_shuffle_bitmap(struct RNG *rng, unsigned int *bitmap, unsigned int bits_num) ATTR_NONNULL(1
Definition rand.cc:125
double BLI_rng_get_double(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition rand.cc:85
MINLINE void copy_v2_v2(float r[2], const float a[2])
float BLI_hash_frand(unsigned int seed) ATTR_WARN_UNUSED_RESULT
Definition rand.cc:150
struct RNG * BLI_rng_new_srandom(unsigned int seed)
Definition rand.cc:48
BLI_INLINE double halton_ex(double invprimes, double *offset)
Definition rand.cc:206
MINLINE float fractf(float a)
void BLI_bitmap_randomize(unsigned int *bitmap, unsigned int bits_num, unsigned int seed) ATTR_NONNULL(1)
Definition rand.cc:166
ATTR_WARN_UNUSED_RESULT const BMVert * v
int BLI_rng_thread_rand(RNG_THREAD_ARRAY *rngarr, int thread) ATTR_WARN_UNUSED_RESULT
Definition rand.cc:197
struct RNG * BLI_rng_new(unsigned int seed)
Definition rand.cc:41
void BLI_rng_get_tri_sample_float_v2(struct RNG *rng, const float v1[2], const float v2[2], const float v3[2], float r_pt[2]) ATTR_NONNULL()
Definition rand.cc:95
void BLI_array_randomize(void *data, unsigned int elem_size, unsigned int elem_num, unsigned int seed)
Definition rand.cc:158
unsigned int uint32_t
Definition BKE_text.h:81
void BLI_rng_get_char_n(RNG *rng, char *bytes, size_t bytes_len) ATTR_NONNULL(1
Definition rand.cc:70
void BLI_halton_1d(unsigned int prime, double offset, int n, double *r)
Definition rand.cc:228
VecBase< float, 2 > float2
unsigned char uchar
Definition BKE_text.h:58
BLI_INLINE double radical_inverse(uint n)
Definition rand.cc:268
void BLI_rng_seed(struct RNG *rng, unsigned int seed) ATTR_NONNULL(1)
Definition rand.cc:60
void BLI_halton_3d(const unsigned int prime[3], double offset[3], int n, double *r)
Definition rand.cc:252
BMesh const char void * data
unsigned int BLI_rng_get_uint(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition rand.cc:80
void BLI_rng_srandom(struct RNG *rng, unsigned int seed) ATTR_NONNULL(1)
Definition rand.cc:65
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition rand.cc:55
void BLI_rng_shuffle_array(struct RNG *rng, void *data, unsigned int elem_size_i, unsigned int elem_num) ATTR_NONNULL(1
Definition rand.cc:101
float BLI_rng_get_float(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition rand.cc:90
void int BLI_rng_get_int(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition rand.cc:75
RNG_THREAD_ARRAY * BLI_rng_threaded_new()
Definition rand.cc:180
unsigned int BLI_bitmap
Definition BLI_bitmap.hh:15
ATTR_WARN_UNUSED_RESULT const BMVert * v2
void void void BLI_rng_skip(struct RNG *rng, int n) ATTR_NONNULL(1)
Definition rand.cc:143
void BLI_rng_threaded_free(struct RNG_THREAD_ARRAY *rngarr) ATTR_NONNULL(1)
Definition rand.cc:192
void BLI_hammersley_1d(unsigned int n, double *r)
Definition rand.cc:283
VecBase< float, 3 > float3
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
#define hash
Definition noise_c.cc:156
#define sqrtf
#define sinf
#define cosf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
std::array< RNG, BLENDER_MAX_THREADS > rng_tab
Definition rand.cc:177
RandomNumberGenerator rng
Definition rand.cc:36
ccl_device_inline size_t round_up(const size_t x, const size_t multiple)
Definition types_base.h:66