TerrainGen coverage

terraingen/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
177 / 177
100.0%
Branches:
62 / 62
100.0%
Functions:
9 / 9, 1 excl
100.0%
noise/fractal.h
Line Branch Exec Source
1 /// @file
2 /// @brief Fractals (fBm, ridged, billow, hybrid) built from octaves of a basis noise.
3 #pragma once
4
5 #include "terraingen/noise/hash.h"
6 #include "terraingen/noise/perlin.h"
7 #include "terraingen/noise/simplex.h"
8 #include "terraingen/noise/value.h"
9 #include "terraingen/noise/worley.h"
10
11 namespace terraingen {
12
13 /// Single-octave noise function a fractal is built from.
14 enum class NoiseBasis : uint32_t {
15 Perlin = 0, ///< Improved gradient noise (`PerlinNoise2`).
16 Simplex = 1, ///< Simplex noise (`SimplexNoise2`).
17 Value = 2, ///< Value noise (`ValueNoise2`).
18 WorleyF1 = 3, ///< Distance to the nearest feature point; cones and basins.
19 WorleyF2 = 4, ///< Distance to the second-nearest feature point.
20 WorleyF2MinusF1 = 5, ///< F2 - F1; ridges along cell borders, like cracked ground.
21 Voronoi = 6, ///< Value of the nearest feature point's cell; flat polygonal plateaus.
22 };
23
24 /// Number of `NoiseBasis` values.
25 static const uint32_t kNoiseBasisCount = 7;
26
27 /// How octaves of the basis noise are combined.
28 enum class FractalType : uint32_t {
29 Fbm = 0, ///< Weighted sum of octaves (fractional Brownian motion).
30 Ridged = 1, ///< Ridged multifractal: sharp crests from inverted |noise|.
31 Billow = 2, ///< Sum of |noise| octaves: rounded, puffy forms.
32 HybridMultifractal = 3, ///< Smooth lowlands and rough highlands.
33 };
34
35 /// Number of `FractalType` values.
36 static const uint32_t kFractalTypeCount = 4;
37
38 /// Parameters of a fractal built from octaves of a basis noise.
39 ///
40 /// Octave i has wavelength `wavelength / lacunarity^i` and weight `gain^i`;
41 /// `gain = lacunarity^(-H)` gives Hurst exponent H (`GainFromHurst`). Checked on the host by
42 /// `ValidateFractalParams`.
43 struct FractalParams {
44 31 uint32_t seed = 0; ///< Seed; each octave derives its own seed and lattice offset.
45 28 float wavelength = 1000.0f; ///< Wavelength of the first octave, in world units (metres).
46 27 float amplitude = 100.0f; ///< Maximum absolute height, in world units (metres).
47 26 int octaves = 8; ///< Number of octaves; at least 1.
48 25 float lacunarity = 2.0f; ///< Frequency ratio between successive octaves; greater than 1.
49 24 float gain = 0.5f; ///< Weight ratio between successive octaves; greater than 0.
50 23 NoiseBasis basis = NoiseBasis::Perlin; ///< Single-octave noise.
51 22 FractalType type = FractalType::Fbm; ///< How octaves combine.
52 21 float offset = 1.0f; ///< Ridge offset for `Ridged` and `HybridMultifractal`; > 0.
53
54 #ifndef __SLANG__
55
18/18
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 1 time.
✓ Branch 5 taken 26 times.
✓ Branch 6 taken 1 time.
✓ Branch 7 taken 25 times.
✓ Branch 8 taken 1 time.
✓ Branch 9 taken 24 times.
✓ Branch 10 taken 1 time.
✓ Branch 11 taken 23 times.
✓ Branch 12 taken 1 time.
✓ Branch 13 taken 22 times.
✓ Branch 14 taken 1 time.
✓ Branch 15 taken 21 times.
✓ Branch 16 taken 1 time.
✓ Branch 17 taken 20 times.
 31 bool operator==(const FractalParams&) const = default;
56 #endif
57 };
58
59 /// Octave gain `lacunarity^(-hurst)` for a Hurst exponent; evaluated on the host, kernels only
60 /// get the gain.
61 /// @param hurst Hurst exponent H, usually in (0, 1].
62 /// @param lacunarity Frequency ratio between octaves, > 1.
63 21 inline float GainFromHurst(float hurst, float lacunarity) {
64 21 return pow(lacunarity, -hurst);
65 }
66
67 /// One octave of 2D `basis` noise; Worley distances are mapped linearly from [0, bound] to
68 /// [-1, 1], and Voronoi gives the cell value.
69 /// @param basis The basis; unknown values fall back to Perlin.
70 /// @return Noise in [-1, 1].
71 548243500 inline float BasisNoise2(NoiseBasis basis, float x, float y, uint32_t seed) {
72 548243500 constexpr float kInvSqrt2 = 0.707106781186547524f;
73 548243500 constexpr float kInvSqrt5 = 0.447213595499957939f;
74
7/7
✓ Branch 0 taken 560650 times.
✓ Branch 1 taken 1771176 times.
✓ Branch 2 taken 452497 times.
✓ Branch 3 taken 175777 times.
✓ Branch 4 taken 957108 times.
✓ Branch 5 taken 414379 times.
✓ Branch 6 taken 543911913 times.
 548243500 switch (basis) {
75 560650 case NoiseBasis::Simplex:
76 560650 return SimplexNoise2(x, y, seed);
77 1771176 case NoiseBasis::Value:
78 1771176 return ValueNoise2(x, y, seed);
79 452497 case NoiseBasis::WorleyF1:
80 452497 return 2.0f * min(Worley2(x, y, seed).f1 * kInvSqrt2, 1.0f) - 1.0f;
81 175777 case NoiseBasis::WorleyF2:
82 175777 return 2.0f * min(Worley2(x, y, seed).f2 * kInvSqrt5, 1.0f) - 1.0f;
83 957108 case NoiseBasis::WorleyF2MinusF1: {
84 957108 const WorleyDistances d = Worley2(x, y, seed);
85 957108 return 2.0f * min((d.f2 - d.f1) * kInvSqrt5, 1.0f) - 1.0f;
86 }
87 414379 case NoiseBasis::Voronoi:
88 414379 return Worley2(x, y, seed).value;
89 543911913 default:
90 543911913 return PerlinNoise2(x, y, seed);
91 }
92 }
93
94 /// One octave of 3D `basis` noise, mapped like `BasisNoise2` with the 3D Worley bounds sqrt(3)
95 /// for F1 and sqrt(6) for F2; unknown values fall back to Perlin.
96 /// @return Noise in [-1, 1].
97 47235716 inline float BasisNoise3(NoiseBasis basis, LatticePoint3 point, uint32_t seed) {
98 47235716 constexpr float kInvSqrt3 = 0.577350269189625765f;
99 47235716 constexpr float kInvSqrt6 = 0.408248290463863016f;
100
7/7
✓ Branch 0 taken 257582 times.
✓ Branch 1 taken 6113 times.
✓ Branch 2 taken 4065 times.
✓ Branch 3 taken 2017 times.
✓ Branch 4 taken 2025 times.
✓ Branch 5 taken 2027 times.
✓ Branch 6 taken 46961887 times.
 47235716 switch (basis) {
101 257582 case NoiseBasis::Simplex:
102 257582 return SimplexNoise3(point, seed);
103 6113 case NoiseBasis::Value:
104 6113 return ValueNoise3(point, seed);
105 4065 case NoiseBasis::WorleyF1:
106 4065 return 2.0f * min(Worley3(point, seed).f1 * kInvSqrt3, 1.0f) - 1.0f;
107 2017 case NoiseBasis::WorleyF2:
108 2017 return 2.0f * min(Worley3(point, seed).f2 * kInvSqrt6, 1.0f) - 1.0f;
109 2025 case NoiseBasis::WorleyF2MinusF1: {
110 2025 const WorleyDistances d = Worley3(point, seed);
111 2025 return 2.0f * min((d.f2 - d.f1) * kInvSqrt6, 1.0f) - 1.0f;
112 }
113 2027 case NoiseBasis::Voronoi:
114 2027 return Worley3(point, seed).value;
115 46961887 default:
116 46961887 return PerlinNoise3(point, seed);
117 }
118 }
119
120 namespace detail {
121
122 /// Cosine of the golden-angle turn between successive 2D octave lattices, accumulated by
123 /// multiplication for bit-identical results.
124 static const float kOctaveTurnCos = -0.7373688780783197f;
125 /// Sine of the golden-angle turn; see `kOctaveTurnCos`.
126 static const float kOctaveTurnSin = 0.6754902942615238f;
127
128 /// The running sums of a fractal over its octaves.
129 struct FractalSums {
130 float weight = 1.0f; ///< Weight of the next octave, `gain^i`.
131 float sum = 0.0f; ///< Weighted sum of octave signals so far.
132 float totalWeight = 0.0f; ///< Sum of the weights so far, for normalization.
133 float feedback = 1.0f; ///< Previous signal weighting the next (ridged and hybrid).
134 };
135
136 /// Adds one octave to a fractal's running sums.
137 /// @param octave The octave, from 0.
138 /// @param n The octave's basis noise, in [-1, 1].
139 595433100 inline FractalSums AddFractalOctave(FractalSums sums, FractalParams params, int octave, float n) {
140
4/4
✓ Branch 0 taken 3129397 times.
✓ Branch 1 taken 8162231 times.
✓ Branch 2 taken 1040428 times.
✓ Branch 3 taken 583101044 times.
 595433100 switch (params.type) {
141 3129397 case FractalType::Billow:
142 3129397 sums.sum += sums.weight * (2.0f * abs(n) - 1.0f);
143 3129397 break;
144 8162231 case FractalType::Ridged: {
145 8162231 float signal = params.offset - abs(n);
146 8162231 signal *= signal * sums.feedback;
147
1/1
✓ Branch 1 taken 8162231 times.
 8162231 sums.feedback = clamp(2.0f * signal, 0.0f, 1.0f);
148 8162231 sums.sum += sums.weight * signal;
149 8162231 break;
150 }
151 1040428 case FractalType::HybridMultifractal: {
152 1040428 const float signal = (n + params.offset) * sums.weight;
153
2/2
✓ Branch 0 taken 153337 times.
✓ Branch 1 taken 887091 times.
 1040428 if (octave == 0) {
154 153337 sums.sum = signal;
155 153337 sums.feedback = signal;
156 } else {
157
1/1
✓ Branch 1 taken 887091 times.
 887091 sums.feedback = clamp(sums.feedback, 0.0f, 1.0f);
158 887091 sums.sum += sums.feedback * signal;
159 887091 sums.feedback *= signal;
160 }
161 1040428 break;
162 }
163 583101044 default:
164 583101044 sums.sum += sums.weight * n;
165 583101044 break;
166 }
167 595433100 sums.totalWeight += sums.weight;
168 595433100 sums.weight *= params.gain;
169 595433100 return sums;
170 }
171
172 /// The fractal height in [-amplitude, amplitude] world units from its sums over every octave,
173 /// normalized by its largest value.
174 104154478 inline float FinishFractal(FractalSums sums, FractalParams params) {
175
3/3
✓ Branch 0 taken 1242988 times.
✓ Branch 1 taken 153337 times.
✓ Branch 2 taken 102758153 times.
 104154478 switch (params.type) {
176 1242988 case FractalType::Ridged: {
177 1242988 const float ridgeScale = max(params.offset, 1.0f - params.offset);
178 1242988 return params.amplitude *
179 1242988 (2.0f * sums.sum / (ridgeScale * ridgeScale * sums.totalWeight) - 1.0f);
180 }
181 153337 case FractalType::HybridMultifractal:
182 153337 return params.amplitude * sums.sum / ((1.0f + params.offset) * sums.totalWeight);
183 102758153 default:
184 102758153 return params.amplitude * sums.sum / sums.totalWeight;
185 }
186 }
187
188 } // namespace detail
189
190 /// 2D fractal height; each octave has its own seed, lattice offset and golden-angle turn.
191 /// @param x, y World coordinates in metres.
192 /// @param params The fractal, assumed valid (`ValidateFractalParams` checks it on the host).
193 /// @return Height in [-amplitude, amplitude] world units, for any parameters.
194 91028899 inline float Fractal2(float x, float y, FractalParams params) {
195 91028899 float frequency = 1.0f / params.wavelength;
196 91028899 float turnCos = 1.0f;
197 91028899 float turnSin = 0.0f;
198 91028899 detail::FractalSums sums = {};
199
2/2
✓ Branch 0 taken 548215490 times.
✓ Branch 1 taken 91028899 times.
 639244389 for (int octave = 0; octave < params.octaves; ++octave) {
200 548215490 const UVec3 h = Pcg3dHash(detail::OctaveKey(params.seed, uint32_t(octave), 0u));
201 548215490 const float offsetX = HashToUnitFloat(h.y);
202 548215490 const float offsetY = HashToUnitFloat(h.z);
203 548215490 const float rx = x * turnCos - y * turnSin;
204 548215490 const float ry = x * turnSin + y * turnCos;
205 const float n =
206
1/1
✓ Branch 1 taken 548215490 times.
 548215490 BasisNoise2(params.basis, rx * frequency + offsetX, ry * frequency + offsetY, h.x);
207
1/1
✓ Branch 1 taken 548215490 times.
 548215490 sums = detail::AddFractalOctave(sums, params, octave, n);
208 548215490 frequency *= params.lacunarity;
209 548215490 const float nextCos = turnCos * detail::kOctaveTurnCos - turnSin * detail::kOctaveTurnSin;
210 548215490 turnSin = turnSin * detail::kOctaveTurnCos + turnCos * detail::kOctaveTurnSin;
211 548215490 turnCos = nextCos;
212 }
213
1/1
✓ Branch 1 taken 91028899 times.
 182057798 return detail::FinishFractal(sums, params);
214 }
215
216 /// `Fractal3` in single precision, for kernels: the same octaves, turns and offsets, to within
217 /// float rounding for coordinates of moderate size, such as a crater's local frame.
218 /// @return Height in [-amplitude, amplitude] world units.
219 4428181 inline float Fractal3Float(float x, float y, float z, FractalParams params) {
220 4428181 const float k00 = -0.6132711010727254f;
221 4428181 const float k01 = -0.293401570821183f;
222 4428181 const float k02 = 0.7333580809050306f;
223 4428181 const float k10 = 0.7897926788435601f;
224 4428181 const float k11 = -0.24097777005594262f;
225 4428181 const float k12 = 0.5640542870894418f;
226 4428181 const float k20 = 0.011228581128535142f;
227 4428181 const float k21 = 0.9251190369776896f;
228 4428181 const float k22 = 0.37951111497202883f;
229 4428181 float t00 = 1.0f;
230 4428181 float t01 = 0.0f;
231 4428181 float t02 = 0.0f;
232 4428181 float t10 = 0.0f;
233 4428181 float t11 = 1.0f;
234 4428181 float t12 = 0.0f;
235 4428181 float t20 = 0.0f;
236 4428181 float t21 = 0.0f;
237 4428181 float t22 = 1.0f;
238 4428181 float frequency = 1.0f / params.wavelength;
239 4428181 detail::FractalSums sums = {};
240
2/2
✓ Branch 0 taken 12811126 times.
✓ Branch 1 taken 4428181 times.
 17239307 for (int octave = 0; octave < params.octaves; ++octave) {
241 12811126 const UVec3 h = Pcg3dHash(detail::OctaveKey(params.seed, uint32_t(octave), 0u));
242 12811126 const UVec3 g = Pcg3dHash(detail::OctaveKey(params.seed, uint32_t(octave), 1u));
243 12811126 const float px = (t00 * x + t01 * y + t02 * z) * frequency + HashToUnitFloat(h.y);
244 12811126 const float py = (t10 * x + t11 * y + t12 * z) * frequency + HashToUnitFloat(h.z);
245 12811126 const float pz = (t20 * x + t21 * y + t22 * z) * frequency + HashToUnitFloat(g.x);
246
1/1
✓ Branch 2 taken 12811126 times.
 12811126 const float n = BasisNoise3(params.basis, SplitLattice3(px, py, pz), h.x);
247
1/1
✓ Branch 1 taken 12811126 times.
 12811126 sums = detail::AddFractalOctave(sums, params, octave, n);
248 12811126 frequency *= params.lacunarity;
249 12811126 const float n00 = k00 * t00 + k01 * t10 + k02 * t20;
250 12811126 const float n01 = k00 * t01 + k01 * t11 + k02 * t21;
251 12811126 const float n02 = k00 * t02 + k01 * t12 + k02 * t22;
252 12811126 const float n10 = k10 * t00 + k11 * t10 + k12 * t20;
253 12811126 const float n11 = k10 * t01 + k11 * t11 + k12 * t21;
254 12811126 const float n12 = k10 * t02 + k11 * t12 + k12 * t22;
255 12811126 const float n20 = k20 * t00 + k21 * t10 + k22 * t20;
256 12811126 const float n21 = k20 * t01 + k21 * t11 + k22 * t21;
257 12811126 const float n22 = k20 * t02 + k21 * t12 + k22 * t22;
258 12811126 t00 = n00;
259 12811126 t01 = n01;
260 12811126 t02 = n02;
261 12811126 t10 = n10;
262 12811126 t11 = n11;
263 12811126 t12 = n12;
264 12811126 t20 = n20;
265 12811126 t21 = n21;
266 12811126 t22 = n22;
267 }
268
1/1
✓ Branch 1 taken 4428181 times.
 8856362 return detail::FinishFractal(sums, params);
269 }
270
271 #ifndef __SLANG__
272 /// `Fractal2` in 3D, for noise on a sphere; lattice coordinates are split in double
273 /// precision so noise stays exact at a planet's radius.
274 /// @param x, y, z World coordinates in metres.
275 /// @param params The fractal, assumed valid.
276 /// @return Height in [-amplitude, amplitude] world units.
277 8697398 inline float Fractal3(double x, double y, double z, FractalParams params) {
278 /// The golden angle about the axis (1, 2, 3) / sqrt(14), which lies along no lattice axis.
279 static constexpr double kTurn[3][3] = {
280 {-0.6132711010727254, -0.293401570821183, 0.7333580809050306},
281 {0.7897926788435601, -0.24097777005594262, 0.5640542870894418},
282 {0.011228581128535142, 0.9251190369776896, 0.37951111497202883}};
283 8697398 double frequency = 1.0 / static_cast<double>(params.wavelength);
284 8697398 double turn[3][3] = {{1.0, 0.0, 0.0}, {0.0, 1.0, 0.0}, {0.0, 0.0, 1.0}};
285 8697398 detail::FractalSums sums = {};
286
2/2
✓ Branch 0 taken 34406484 times.
✓ Branch 1 taken 8697398 times.
 43103882 for (int octave = 0; octave < params.octaves; ++octave) {
287 34406484 const UVec3 h = Pcg3dHash(detail::OctaveKey(params.seed, uint32_t(octave), 0u));
288 34406484 const UVec3 g = Pcg3dHash(detail::OctaveKey(params.seed, uint32_t(octave), 1u));
289 34406484 const double rx = turn[0][0] * x + turn[0][1] * y + turn[0][2] * z;
290 34406484 const double ry = turn[1][0] * x + turn[1][1] * y + turn[1][2] * z;
291 34406484 const double rz = turn[2][0] * x + turn[2][1] * y + turn[2][2] * z;
292 34406484 const double px = rx * frequency + static_cast<double>(HashToUnitFloat(h.y));
293 34406484 const double py = ry * frequency + static_cast<double>(HashToUnitFloat(h.z));
294 34406484 const double pz = rz * frequency + static_cast<double>(HashToUnitFloat(g.x));
295
1/1
✓ Branch 2 taken 34406484 times.
 34406484 const float n = BasisNoise3(params.basis, SplitLatticePrecise3(px, py, pz), h.x);
296
1/1
✓ Branch 1 taken 34406484 times.
 34406484 sums = detail::AddFractalOctave(sums, params, octave, n);
297 34406484 frequency *= static_cast<double>(params.lacunarity);
298 34406484 double next[3][3] = {};
299
2/2
✓ Branch 0 taken 103219452 times.
✓ Branch 1 taken 34406484 times.
 137625936 for (int row = 0; row < 3; ++row) {
300
2/2
✓ Branch 0 taken 309658356 times.
✓ Branch 1 taken 103219452 times.
 412877808 for (int column = 0; column < 3; ++column) {
301 309658356 next[row][column] = kTurn[row][0] * turn[0][column] +
302 309658356 kTurn[row][1] * turn[1][column] +
303 309658356 kTurn[row][2] * turn[2][column];
304 }
305 }
306 34406484 std::memcpy(turn, next, sizeof(turn));
307 }
308
1/1
✓ Branch 1 taken 8697398 times.
 17394796 return detail::FinishFractal(sums, params);
309 }
310 #endif
311
312 } // namespace terraingen
313