util/random.h
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // SPDX-License-Identifier: BSD-3-Clause | ||
| 2 | /// @file random.h | ||
| 3 | /// @brief Deterministic random streams shared by every render | ||
| 4 | /// backend. | ||
| 5 | #pragma once | ||
| 6 | |||
| 7 | #include <glm/glm.hpp> | ||
| 8 | |||
| 9 | #include <cstdint> | ||
| 10 | #include <string_view> | ||
| 11 | |||
| 12 | /// Deterministic random streams shared by every render backend. | ||
| 13 | /// | ||
| 14 | /// Every random decision a renderer makes (sensor noise, and the | ||
| 15 | /// samples of ray and path tracers) derives from three numbers: a | ||
| 16 | /// seed the scene authors, a stream naming what is rendered (a render | ||
| 17 | /// product, `HashStream` its path) and the frame number. The same | ||
| 18 | /// scene, settings and frame then render the same image on any | ||
| 19 | /// machine, in any order, whatever else renders alongside. | ||
| 20 | /// | ||
| 21 | /// Reference: M. Jarzynski and M. Olano, "Hash Functions for GPU | ||
| 22 | /// Rendering", Journal of Computer Graphics Techniques 9(3):21-38, | ||
| 23 | /// 2020 (pcg3d, pcg4d). | ||
| 24 | namespace ernie { | ||
| 25 | |||
| 26 | /// The pcg3d hash: three well-mixed 32-bit words from three. Shaders | ||
| 27 | /// implement the same function. | ||
| 28 | 921605 | inline constexpr glm::uvec3 Pcg3d(glm::uvec3 v) { | |
| 29 | 921605 | v = v * 1664525u + 1013904223u; | |
| 30 | 921605 | v.x += v.y * v.z; | |
| 31 | 921605 | v.y += v.z * v.x; | |
| 32 | 921605 | v.z += v.x * v.y; | |
| 33 | 921605 | v = v ^ (v >> 16u); | |
| 34 | 921605 | v.x += v.y * v.z; | |
| 35 | 921605 | v.y += v.z * v.x; | |
| 36 | 921605 | v.z += v.x * v.y; | |
| 37 | 921605 | return v; | |
| 38 | } | ||
| 39 | |||
| 40 | /// The pcg4d hash: four well-mixed 32-bit words from four. Shaders implement the same function. | ||
| 41 | 917506 | inline constexpr glm::uvec4 Pcg4d(glm::uvec4 v) { | |
| 42 | 917506 | v = v * 1664525u + 1013904223u; | |
| 43 | 917506 | v.x += v.y * v.w; | |
| 44 | 917506 | v.y += v.z * v.x; | |
| 45 | 917506 | v.z += v.x * v.y; | |
| 46 | 917506 | v.w += v.y * v.z; | |
| 47 | 917506 | v = v ^ (v >> 16u); | |
| 48 | 917506 | v.x += v.y * v.w; | |
| 49 | 917506 | v.y += v.z * v.x; | |
| 50 | 917506 | v.z += v.x * v.y; | |
| 51 | 917506 | v.w += v.y * v.z; | |
| 52 | 917506 | return v; | |
| 53 | } | ||
| 54 | |||
| 55 | /// A stable 32-bit stream id for `name`, such as a render product's | ||
| 56 | /// path: its 32-bit FNV-1a hash. | ||
| 57 | inline constexpr std::uint32_t HashStream(std::string_view name) { | ||
| 58 | std::uint32_t hash = 2166136261u; | ||
| 59 | for (const char c : name) { | ||
| 60 | hash = (hash ^ static_cast<std::uint8_t>(c)) * 16777619u; | ||
| 61 | } | ||
| 62 | return hash; | ||
| 63 | } | ||
| 64 | |||
| 65 | /// The seed of frame `frame` of stream `stream` under the authored | ||
| 66 | /// `seed`, from which a frame's temporal noise and samples derive. | ||
| 67 | /// Distinct frames, streams or seeds give unrelated seeds. | ||
| 68 | 4096 | inline constexpr std::uint32_t FrameSeed(std::uint32_t seed, std::uint32_t stream, | |
| 69 | std::uint64_t frame) { | ||
| 70 | 4096 | const glm::uvec3 h = Pcg3d(glm::uvec3(seed, stream ^ static_cast<std::uint32_t>(frame >> 32u), | |
| 71 | static_cast<std::uint32_t>(frame))); | ||
| 72 | 4096 | return h.x ^ h.y ^ h.z; | |
| 73 | } | ||
| 74 | |||
| 75 | /// Identifies one sample: which frame (`FrameSeed`), view, pixel and sample index it is. | ||
| 76 | struct SampleKey { | ||
| 77 | std::uint32_t frameSeed = 0; | ||
| 78 | std::uint32_t view = 0; | ||
| 79 | std::uint32_t pixel = 0; | ||
| 80 | std::uint32_t sample = 0; | ||
| 81 | }; | ||
| 82 | |||
| 83 | /// 32 random bits for dimension `dimension` of a sample. A counter-based stream: any sample's | ||
| 84 | /// numbers can be regenerated without the ones before it, in any order, on the host or the GPU. | ||
| 85 | 917506 | inline constexpr std::uint32_t SampleBits(const SampleKey& key, std::uint32_t dimension) { | |
| 86 | 917506 | const glm::uvec4 h = | |
| 87 | 917506 | Pcg4d(glm::uvec4(key.pixel, key.sample, dimension, key.view ^ key.frameSeed)); | |
| 88 | 917506 | return h.x ^ Pcg3d(glm::uvec3(h.y, h.z, key.frameSeed)).x; | |
| 89 | } | ||
| 90 | |||
| 91 | /// A uniform number in [0, 1) for dimension `dimension` of a sample, with 24 random bits. | ||
| 92 | 917504 | inline constexpr float SampleUniform(const SampleKey& key, std::uint32_t dimension) { | |
| 93 | 917504 | return static_cast<float>(SampleBits(key, dimension) >> 8u) * (1.0f / 16777216.0f); | |
| 94 | } | ||
| 95 | |||
| 96 | /// @brief SplitMix64's finaliser: every input bit affects every output bit. | ||
| 97 | /// @param z The bits. | ||
| 98 | /// @return Them mixed. | ||
| 99 | 235123478 | inline constexpr std::uint64_t Mix64(std::uint64_t z) { | |
| 100 | 235123478 | z = (z ^ (z >> 30u)) * 0xbf58476d1ce4e5b9ull; | |
| 101 | 235123478 | z = (z ^ (z >> 27u)) * 0x94d049bb133111ebull; | |
| 102 | 235123226 | return z ^ (z >> 31u); | |
| 103 | } | ||
| 104 | |||
| 105 | /// @brief Folds a value into a hash, as for keys of several fields. | ||
| 106 | /// @param seed The hash so far. | ||
| 107 | /// @param value The next field. | ||
| 108 | /// @return The combined hash. | ||
| 109 | 324 | inline constexpr std::uint64_t HashCombine(std::uint64_t seed, std::uint64_t value) { | |
| 110 | 324 | return Mix64(seed + 0x9e3779b97f4a7c15ull + value); | |
| 111 | } | ||
| 112 | |||
| 113 | /// A sequential generator for host-side Monte Carlo work such as baking tables: SplitMix64, with | ||
| 114 | /// full double precision. Use `SampleBits` instead for anything the GPU must reproduce. | ||
| 115 | /// | ||
| 116 | /// Reference: G. L. Steele, D. Lea and C. H. Flood, "Fast Splittable Pseudorandom Number | ||
| 117 | /// Generators", OOPSLA 2014. | ||
| 118 | class SplitMix64 { | ||
| 119 | public: | ||
| 120 | /// @brief Starts a stream. | ||
| 121 | /// @param seed The seed; different seeds give unrelated streams. | ||
| 122 | 72 | explicit constexpr SplitMix64(std::uint64_t seed) : state_(seed) {} | |
| 123 | |||
| 124 | /// @brief Draws the next 64 random bits. | ||
| 125 | /// @return The bits. | ||
| 126 | 235109656 | constexpr std::uint64_t NextBits() { | |
| 127 | 235109656 | return Mix64(state_ += 0x9e3779b97f4a7c15ull); | |
| 128 | } | ||
| 129 | |||
| 130 | /// @brief Draws a uniform number. | ||
| 131 | /// @return A double in [0, 1) with 53 random bits. | ||
| 132 | 67950525 | constexpr double NextUniform() { | |
| 133 | 167258330 | return static_cast<double>(NextBits() >> 11u) * 0x1.0p-53; | |
| 134 | } | ||
| 135 | |||
| 136 | private: | ||
| 137 | std::uint64_t state_; | ||
| 138 | }; | ||
| 139 | |||
| 140 | } // namespace ernie | ||
| 141 |