Cycles: add Sobol-Burley sampling pattern

Based on the paper "Practical Hash-based Owen Scrambling" by Brent Burley,
2020, Journal of Computer Graphics Techniques.

It is distinct from the existing Sobol sampler in two important ways:
* It is Owen scrambled, which gives it a much better convergence rate in many
  situations.
* It uses padding for higher dimensions, rather than using higher Sobol
  dimensions directly. In practice this is advantagous because high-dimensional
  Sobol sequences have holes in their sampling patterns that don't resolve
  until an unreasonable number of samples are taken. (See Burley's paper for
  details.)

The pattern reduces noise in some benchmark scenes, however it is also slower,
particularly on the CPU. So for now Progressive Multi-Jittered sampling remains
the default.

Differential Revision: https://developer.blender.org/D15679

1 files changed, 116 insertions, 4 deletions

diff --git a/intern/cycles/util/hash.h b/intern/cycles/util/hash.h
index 081b33025d8..61705276a90 100644
--- a/intern/cycles/util/hash.h
+++ b/intern/cycles/util/hash.h
@@ -8,6 +8,23 @@
 
 CCL_NAMESPACE_BEGIN
 
+/* [0, uint_max] -> [0.0, 1.0) */
+ccl_device_forceinline float uint_to_float_excl(uint n)
+{
+  // Note: we divide by 4294967808 instead of 2^32 because the latter
+  // leads to a [0.0, 1.0] mapping instead of [0.0, 1.0) due to floating
+  // point rounding error. 4294967808 unfortunately leaves (precisely)
+  // one unused ulp between the max number this outputs and 1.0, but
+  // that's the best you can do with this construction.
+  return (float)n * (1.0f / 4294967808.0f);
+}
+
+/* [0, uint_max] -> [0.0, 1.0] */
+ccl_device_forceinline float uint_to_float_incl(uint n)
+{
+  return (float)n * (1.0f / (float)0xFFFFFFFFu);
+}
+
 /* ***** Jenkins Lookup3 Hash Functions ***** */
 
 /* Source: http://burtleburtle.net/bob/c/lookup3.c */
@@ -116,22 +133,22 @@ ccl_device_inline uint hash_uint4(uint kx, uint ky, uint kz, uint kw)
 
 ccl_device_inline float hash_uint_to_float(uint kx)
 {
-  return (float)hash_uint(kx) / (float)0xFFFFFFFFu;
+  return uint_to_float_incl(hash_uint(kx));
 }
 
 ccl_device_inline float hash_uint2_to_float(uint kx, uint ky)
 {
-  return (float)hash_uint2(kx, ky) / (float)0xFFFFFFFFu;
+  return uint_to_float_incl(hash_uint2(kx, ky));
 }
 
 ccl_device_inline float hash_uint3_to_float(uint kx, uint ky, uint kz)
 {
-  return (float)hash_uint3(kx, ky, kz) / (float)0xFFFFFFFFu;
+  return uint_to_float_incl(hash_uint3(kx, ky, kz));
 }
 
 ccl_device_inline float hash_uint4_to_float(uint kx, uint ky, uint kz, uint kw)
 {
-  return (float)hash_uint4(kx, ky, kz, kw) / (float)0xFFFFFFFFu;
+  return uint_to_float_incl(hash_uint4(kx, ky, kz, kw));
 }
 
 /* Hashing float or float[234] into a float in the range [0, 1]. */
@@ -359,6 +376,101 @@ ccl_device_inline avxi hash_avxi4(avxi kx, avxi ky, avxi kz, avxi kw)
 
 #endif
 
+/* ***** Hash Prospector Hash Functions *****
+ *
+ * These are based on the high-quality 32-bit hash/mixings functions from
+ * https://github.com/skeeto/hash-prospector
+ */
+
+ccl_device_inline uint hash_hp_uint(uint i)
+{
+  // The actual mixing function from Hash Prospector.
+  i ^= i >> 16;
+  i *= 0x21f0aaad;
+  i ^= i >> 15;
+  i *= 0xd35a2d97;
+  i ^= i >> 15;
+
+  // The xor is just to make input zero not map to output zero.
+  // The number is randomly selected and isn't special.
+  return i ^ 0xe6fe3beb;
+}
+
+/* Seedable version of hash_hp_uint() above. */
+ccl_device_inline uint hash_hp_seeded_uint(uint i, uint seed)
+{
+  // Manipulate the seed so it doesn't interact poorly with n when they
+  // are both e.g. incrementing.  This isn't fool-proof, but is good
+  // enough for practical use.
+  seed ^= seed << 19;
+
+  return hash_hp_uint(i ^ seed);
+}
+
+/* Outputs [0.0, 1.0]. */
+ccl_device_inline float hash_hp_seeded_float(uint i, uint seed)
+{
+  return uint_to_float_incl(hash_hp_seeded_uint(i, seed));
+}
+
+/* ***** CMJ Hash Functions *****
+ *
+ * These are based on one of the hash functions in the paper
+ * "Correlated Multi-Jittered Sampling" by Andrew Kensler, 2013.
+ *
+ * These are here for backwards-compatibility, and can be replaced
+ * by the Hash Prospector hashes above at some point.
+ * See https://developer.blender.org/D15679#426304
+ */
+
+ccl_device_inline uint hash_cmj_seeded_uint(uint i, uint seed)
+{
+  i ^= seed;
+  i ^= i >> 17;
+  i ^= i >> 10;
+  i *= 0xb36534e5;
+  i ^= i >> 12;
+  i ^= i >> 21;
+  i *= 0x93fc4795;
+  i ^= 0xdf6e307f;
+  i ^= i >> 17;
+  i *= 1 | seed >> 18;
+
+  return i;
+}
+
+/* Outputs [0.0, 1.0]. */
+ccl_device_inline float hash_cmj_seeded_float(uint i, uint seed)
+{
+  return uint_to_float_excl(hash_cmj_seeded_uint(i, seed));
+}
+
+/* ***** Modified Wang Hash Functions *****
+ *
+ * These are based on a bespoke modified version of the Wang hash, and
+ * can serve as a faster hash when quality isn't critical.
+ *
+ * The original Wang hash is documented here:
+ * https://www.burtleburtle.net/bob/hash/integer.html
+ */
+
+ccl_device_inline uint hash_wang_seeded_uint(uint i, uint seed)
+{
+  i = (i ^ 61) ^ seed;
+  i += i << 3;
+  i ^= i >> 4;
+  i *= 0x27d4eb2d;
+  return i;
+}
+
+/* Outputs [0.0, 1.0]. */
+ccl_device_inline float hash_wang_seeded_float(uint i, uint seed)
+{
+  return uint_to_float_incl(hash_wang_seeded_uint(i, seed));
+}
+
+/* ********** */
+
 #ifndef __KERNEL_GPU__
 static inline uint hash_string(const char *str)
 {