Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/intern/cycles/scene/jitter.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'intern/cycles/scene/jitter.cpp')
-rw-r--r--intern/cycles/scene/jitter.cpp287
1 files changed, 38 insertions, 249 deletions
diff --git a/intern/cycles/scene/jitter.cpp b/intern/cycles/scene/jitter.cpp
index 4f9c4fb9418..8287a029752 100644
--- a/intern/cycles/scene/jitter.cpp
+++ b/intern/cycles/scene/jitter.cpp
@@ -2,267 +2,56 @@
* Copyright 2019-2022 Blender Foundation */
/* This file is based on "Progressive Multi-Jittered Sample Sequences"
- * by Per Christensen, Andrew Kensler and Charlie Kilpatrick.
- * http://graphics.pixar.com/library/ProgressiveMultiJitteredSampling/paper.pdf
- *
- * Performance can be improved in the future by implementing the new
- * algorithm from Matt Pharr in http://jcgt.org/published/0008/01/04/
- * "Efficient Generation of Points that Satisfy Two-Dimensional Elementary Intervals"
+ * by Christensen, Kensler, and Kilpatrick, but with a much simpler and
+ * faster implementation based on "Stochastic Generation of (t, s)
+ * Sample Sequences" by Helmer, Christensen, and Kensler.
*/
#include "scene/jitter.h"
+#include "util/hash.h"
#include <math.h>
#include <vector>
CCL_NAMESPACE_BEGIN
-static uint cmj_hash(uint i, uint p)
-{
- i ^= p;
- i ^= i >> 17;
- i ^= i >> 10;
- i *= 0xb36534e5;
- i ^= i >> 12;
- i ^= i >> 21;
- i *= 0x93fc4795;
- i ^= 0xdf6e307f;
- i ^= i >> 17;
- i *= 1 | p >> 18;
-
- return i;
-}
-
-static float cmj_randfloat(uint i, uint p)
-{
- return cmj_hash(i, p) * (1.0f / 4294967808.0f);
-}
-
-class PMJ_Generator {
- public:
- static void generate_2D(float2 points[], int size, int rng_seed_in)
- {
- PMJ_Generator g(rng_seed_in);
- points[0].x = g.rnd();
- points[0].y = g.rnd();
- int N = 1;
- while (N < size) {
- g.extend_sequence_even(points, N);
- g.extend_sequence_odd(points, 2 * N);
- N = 4 * N;
- }
- }
-
- protected:
- PMJ_Generator(int rnd_seed_in) : num_samples(1), rnd_index(2), rnd_seed(rnd_seed_in)
- {
- }
-
- float rnd()
- {
- return cmj_randfloat(++rnd_index, rnd_seed);
- }
-
- virtual void mark_occupied_strata(float2 points[], int N)
- {
- int NN = 2 * N;
- for (int s = 0; s < NN; ++s) {
- occupied1Dx[s] = occupied1Dy[s] = false;
- }
- for (int s = 0; s < N; ++s) {
- int xstratum = (int)(NN * points[s].x);
- int ystratum = (int)(NN * points[s].y);
- occupied1Dx[xstratum] = true;
- occupied1Dy[ystratum] = true;
- }
- }
-
- virtual void generate_sample_point(
- float2 points[], float i, float j, float xhalf, float yhalf, int n, int N)
- {
- int NN = 2 * N;
- float2 pt;
- int xstratum, ystratum;
- do {
- pt.x = (i + 0.5f * (xhalf + rnd())) / n;
- xstratum = (int)(NN * pt.x);
- } while (occupied1Dx[xstratum]);
- do {
- pt.y = (j + 0.5f * (yhalf + rnd())) / n;
- ystratum = (int)(NN * pt.y);
- } while (occupied1Dy[ystratum]);
- occupied1Dx[xstratum] = true;
- occupied1Dy[ystratum] = true;
- points[num_samples] = pt;
- ++num_samples;
- }
-
- void extend_sequence_even(float2 points[], int N)
- {
- int n = (int)sqrtf(N);
- occupied1Dx.resize(2 * N);
- occupied1Dy.resize(2 * N);
- mark_occupied_strata(points, N);
- for (int s = 0; s < N; ++s) {
- float2 oldpt = points[s];
- float i = floorf(n * oldpt.x);
- float j = floorf(n * oldpt.y);
- float xhalf = floorf(2.0f * (n * oldpt.x - i));
- float yhalf = floorf(2.0f * (n * oldpt.y - j));
- xhalf = 1.0f - xhalf;
- yhalf = 1.0f - yhalf;
- generate_sample_point(points, i, j, xhalf, yhalf, n, N);
- }
- }
-
- void extend_sequence_odd(float2 points[], int N)
- {
- int n = (int)sqrtf(N / 2);
- occupied1Dx.resize(2 * N);
- occupied1Dy.resize(2 * N);
- mark_occupied_strata(points, N);
- std::vector<float> xhalves(N / 2);
- std::vector<float> yhalves(N / 2);
- for (int s = 0; s < N / 2; ++s) {
- float2 oldpt = points[s];
- float i = floorf(n * oldpt.x);
- float j = floorf(n * oldpt.y);
- float xhalf = floorf(2.0f * (n * oldpt.x - i));
- float yhalf = floorf(2.0f * (n * oldpt.y - j));
- if (rnd() > 0.5f) {
- xhalf = 1.0f - xhalf;
- }
- else {
- yhalf = 1.0f - yhalf;
- }
- xhalves[s] = xhalf;
- yhalves[s] = yhalf;
- generate_sample_point(points, i, j, xhalf, yhalf, n, N);
- }
- for (int s = 0; s < N / 2; ++s) {
- float2 oldpt = points[s];
- float i = floorf(n * oldpt.x);
- float j = floorf(n * oldpt.y);
- float xhalf = 1.0f - xhalves[s];
- float yhalf = 1.0f - yhalves[s];
- generate_sample_point(points, i, j, xhalf, yhalf, n, N);
- }
- }
-
- std::vector<bool> occupied1Dx, occupied1Dy;
- int num_samples;
- int rnd_index, rnd_seed;
-};
-
-class PMJ02_Generator : public PMJ_Generator {
- protected:
- void generate_sample_point(
- float2 points[], float i, float j, float xhalf, float yhalf, int n, int N) override
- {
- int NN = 2 * N;
- float2 pt;
- do {
- pt.x = (i + 0.5f * (xhalf + rnd())) / n;
- pt.y = (j + 0.5f * (yhalf + rnd())) / n;
- } while (is_occupied(pt, NN));
- mark_occupied_strata1(pt, NN);
- points[num_samples] = pt;
- ++num_samples;
- }
-
- void mark_occupied_strata(float2 points[], int N) override
- {
- int NN = 2 * N;
- int num_shapes = (int)log2f(NN) + 1;
- occupiedStrata.resize(num_shapes);
- for (int shape = 0; shape < num_shapes; ++shape) {
- occupiedStrata[shape].resize(NN);
- for (int n = 0; n < NN; ++n) {
- occupiedStrata[shape][n] = false;
- }
- }
- for (int s = 0; s < N; ++s) {
- mark_occupied_strata1(points[s], NN);
- }
- }
-
- void mark_occupied_strata1(float2 pt, int NN)
- {
- int shape = 0;
- int xdivs = NN;
- int ydivs = 1;
- do {
- int xstratum = (int)(xdivs * pt.x);
- int ystratum = (int)(ydivs * pt.y);
- size_t index = ystratum * xdivs + xstratum;
- assert(index < NN);
- occupiedStrata[shape][index] = true;
- shape = shape + 1;
- xdivs = xdivs / 2;
- ydivs = ydivs * 2;
- } while (xdivs > 0);
- }
-
- bool is_occupied(float2 pt, int NN)
- {
- int shape = 0;
- int xdivs = NN;
- int ydivs = 1;
- do {
- int xstratum = (int)(xdivs * pt.x);
- int ystratum = (int)(ydivs * pt.y);
- size_t index = ystratum * xdivs + xstratum;
- assert(index < NN);
- if (occupiedStrata[shape][index]) {
- return true;
- }
- shape = shape + 1;
- xdivs = xdivs / 2;
- ydivs = ydivs * 2;
- } while (xdivs > 0);
- return false;
- }
-
- private:
- std::vector<std::vector<bool>> occupiedStrata;
-};
-
-static void shuffle(float2 points[], int size, int rng_seed)
+void progressive_multi_jitter_02_generate_2D(float2 points[], int size, int rng_seed)
{
- if (rng_seed == 0) {
- return;
- }
-
- constexpr int odd[8] = {0, 1, 4, 5, 10, 11, 14, 15};
- constexpr int even[8] = {2, 3, 6, 7, 8, 9, 12, 13};
-
- int rng_index = 0;
- for (int yy = 0; yy < size / 16; ++yy) {
- for (int xx = 0; xx < 8; ++xx) {
- int other = (int)(cmj_randfloat(++rng_index, rng_seed) * (8.0f - xx) + xx);
- float2 tmp = points[odd[other] + yy * 16];
- points[odd[other] + yy * 16] = points[odd[xx] + yy * 16];
- points[odd[xx] + yy * 16] = tmp;
- }
- for (int xx = 0; xx < 8; ++xx) {
- int other = (int)(cmj_randfloat(++rng_index, rng_seed) * (8.0f - xx) + xx);
- float2 tmp = points[even[other] + yy * 16];
- points[even[other] + yy * 16] = points[even[xx] + yy * 16];
- points[even[xx] + yy * 16] = tmp;
+ /* Xor values for generating the PMJ02 sequence. These permute the
+ * order we visit the strata in, which is what makes the code below
+ * produce the PMJ02 sequence. Other choices are also possible, but
+ * result in different sequences. */
+ static uint xors[2][32] = {
+ {0x00000000, 0x00000000, 0x00000002, 0x00000006, 0x00000006, 0x0000000e, 0x00000036,
+ 0x0000004e, 0x00000016, 0x0000002e, 0x00000276, 0x000006ce, 0x00000716, 0x00000c2e,
+ 0x00003076, 0x000040ce, 0x00000116, 0x0000022e, 0x00020676, 0x00060ece, 0x00061716,
+ 0x000e2c2e, 0x00367076, 0x004ec0ce, 0x00170116, 0x002c022e, 0x02700676, 0x06c00ece,
+ 0x07001716, 0x0c002c2e, 0x30007076, 0x4000c0ce},
+ {0x00000000, 0x00000001, 0x00000003, 0x00000003, 0x00000007, 0x0000001b, 0x00000027,
+ 0x0000000b, 0x00000017, 0x0000013b, 0x00000367, 0x0000038b, 0x00000617, 0x0000183b,
+ 0x00002067, 0x0000008b, 0x00000117, 0x0001033b, 0x00030767, 0x00030b8b, 0x00071617,
+ 0x001b383b, 0x00276067, 0x000b808b, 0x00160117, 0x0138033b, 0x03600767, 0x03800b8b,
+ 0x06001617, 0x1800383b, 0x20006067, 0x0000808b}};
+
+ uint rng_i = rng_seed;
+
+ points[0].x = hash_hp_float(rng_i++);
+ points[0].y = hash_hp_float(rng_i++);
+
+ /* Subdivide the domain into smaller and smaller strata, filling in new
+ * points as we go. */
+ for (int log_N = 0, N = 1; N < size; log_N++, N *= 2) {
+ float strata_count = (float)(N * 2);
+ for (int i = 0; i < N && (N + i) < size; i++) {
+ /* Find the strata that are already occupied in this cell. */
+ uint occupied_x_stratum = (uint)(points[i ^ xors[0][log_N]].x * strata_count);
+ uint occupied_y_stratum = (uint)(points[i ^ xors[1][log_N]].y * strata_count);
+
+ /* Generate a new point in the unoccupied strata. */
+ points[N + i].x = ((float)(occupied_x_stratum ^ 1) + hash_hp_float(rng_i++)) / strata_count;
+ points[N + i].y = ((float)(occupied_y_stratum ^ 1) + hash_hp_float(rng_i++)) / strata_count;
}
}
}
-void progressive_multi_jitter_generate_2D(float2 points[], int size, int rng_seed)
-{
- PMJ_Generator::generate_2D(points, size, rng_seed);
- shuffle(points, size, rng_seed);
-}
-
-void progressive_multi_jitter_02_generate_2D(float2 points[], int size, int rng_seed)
-{
- PMJ02_Generator::generate_2D(points, size, rng_seed);
- shuffle(points, size, rng_seed);
-}
-
CCL_NAMESPACE_END
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-21 00:07:02 +0300