layers/craters/shaping/irregularity.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "terraingen/layers/craters/shaping/irregularity.h" | ||
| 2 | |||
| 3 | #include "terraingen/layers/fade.h" | ||
| 4 | #include "terraingen/random/stream.h" | ||
| 5 | #include "terraingen/util/checks.h" | ||
| 6 | #include "terraingen/util/fft.h" | ||
| 7 | |||
| 8 | #include <algorithm> | ||
| 9 | #include <cmath> | ||
| 10 | #include <complex> | ||
| 11 | #include <cstddef> | ||
| 12 | #include <numbers> | ||
| 13 | #include <stdexcept> | ||
| 14 | |||
| 15 | namespace terraingen { | ||
| 16 | |||
| 17 | namespace { | ||
| 18 | |||
| 19 | constexpr std::uint32_t kIrregularityStream = 0x49525247u; | ||
| 20 | |||
| 21 | constexpr std::uint32_t kMarksStream = 0x4D41524Bu; | ||
| 22 | |||
| 23 | constexpr int kMaxMarkKnots = 1024; | ||
| 24 | |||
| 25 | /// How far a periodic Catmull-Rom spline can overshoot its knots, as a share of their largest | ||
| 26 | /// magnitude. | ||
| 27 | constexpr double kSplineOvershoot = 1.25; | ||
| 28 | |||
| 29 | /// The steepest slope of `Smoothstep`. | ||
| 30 | constexpr double kSmoothstepSlope = 1.5; | ||
| 31 | |||
| 32 | constexpr std::size_t kTableSize = 1024; | ||
| 33 | |||
| 34 | /// A standard normal from the next two uniforms of `random`. | ||
| 35 | 27348 | double Normal(RandomStream& random) { | |
| 36 | 27348 | const double u1 = random.NextDouble(); | |
| 37 | 27348 | const double u2 = random.NextDouble(); | |
| 38 | 27348 | return StandardNormal(u1, u2); | |
| 39 | } | ||
| 40 | |||
| 41 | /// y = a D + b in a crater's diameter D (km), with one line up to 20 km and another above, as Du et | ||
| 42 | /// al. (2024, Table 2) fit their breakpoints; and its 1-sigma misfit on each side. | ||
| 43 | struct PiecewiseFit { | ||
| 44 | double a1, b1, sigma1, a2, b2, sigma2; | ||
| 45 | |||
| 46 | 270 | double At(double kilometres, double z) const { | |
| 47 | 270 | return kilometres <= 20.0 ? a1 * kilometres + b1 + z * sigma1 | |
| 48 | 270 | : a2 * kilometres + b2 + z * sigma2; | |
| 49 | } | ||
| 50 | }; | ||
| 51 | |||
| 52 | /// The rim crest radial distance fits of Du et al. (2024, Table 2). | ||
| 53 | constexpr PiecewiseFit kSlope12{-0.022, 3.3, 0.54, -0.00019, 2.9, 0.22}; | ||
| 54 | constexpr PiecewiseFit kLogWavelength2{0.010, -0.57, 0.27, -0.00035, -0.36, 0.27}; | ||
| 55 | constexpr PiecewiseFit kLogPower2{0.043, 0.59, 0.55, 0.010, 1.2, 0.75}; | ||
| 56 | constexpr PiecewiseFit kLogPower3{0.055, 2.3, 0.58, -0.0026, 3.5, 0.44}; | ||
| 57 | constexpr PiecewiseFit kLogPower4{0.066, -1.1, 1.00, 0.0062, 0.059, 0.69}; | ||
| 58 | constexpr double kSpectrumSigma = 0.55; | ||
| 59 | constexpr double kSpectrumVertices = 5000.0; | ||
| 60 | |||
| 61 | /// The breakpoints of one crater's rim spectrum, from the fits at its diameter. | ||
| 62 | struct DuSpectrum { | ||
| 63 | double slope; | ||
| 64 | double logWavelength2; | ||
| 65 | double logPower2; | ||
| 66 | double logPower3; | ||
| 67 | double logPower4; | ||
| 68 | |||
| 69 | /// log10 power of harmonic `k`. | ||
| 70 | 27594 | double LogPower(std::size_t k) const { | |
| 71 | 27594 | if (k == 1) { | |
| 72 | 54 | return logPower4; | |
| 73 | } | ||
| 74 | 27540 | if (k == 2) { | |
| 75 | 54 | return logPower3; | |
| 76 | } | ||
| 77 | 27486 | const double logPi = std::log10(std::numbers::pi); | |
| 78 | 27486 | const double logWavelength = std::log10(2.0 * std::numbers::pi / static_cast<double>(k)); | |
| 79 | 27486 | if (logWavelength >= logWavelength2) { | |
| 80 | 926 | return logPower2 + (logWavelength - logWavelength2) / (logPi - logWavelength2) * | |
| 81 | 926 | (logPower3 - logPower2); | |
| 82 | } | ||
| 83 | 26560 | return logPower2 + slope * (logWavelength - logWavelength2); | |
| 84 | } | ||
| 85 | }; | ||
| 86 | |||
| 87 | /// `table` scaled down so that no value exceeds `maxDeviation` in magnitude. | ||
| 88 | 54 | void LimitDeviation(std::vector<double>& table, double maxDeviation) { | |
| 89 | 54 | double largest = 0.0; | |
| 90 | 55350 | for (const double value : table) { | |
| 91 | 55296 | largest = std::fmax(largest, std::fabs(value)); | |
| 92 | } | ||
| 93 | 54 | if (largest > maxDeviation) { | |
| 94 | 53300 | for (double& value : table) { | |
| 95 | 53248 | value *= maxDeviation / largest; | |
| 96 | } | ||
| 97 | } | ||
| 98 | 54 | } | |
| 99 | |||
| 100 | 54 | std::vector<double> DuRimTable(double diameter, bool scatter, double maxDeviation, | |
| 101 | RandomStream& random) { | ||
| 102 | 54 | const double kilometres = std::clamp(diameter / 1000.0, 1.0, 140.0); | |
| 103 | 270 | const auto draw = [&] { return scatter ? Normal(random) : 0.0; }; | |
| 104 | 54 | DuSpectrum fit{}; | |
| 105 | 54 | fit.slope = kSlope12.At(kilometres, draw()); | |
| 106 | 54 | fit.logWavelength2 = kLogWavelength2.At(kilometres, draw()); | |
| 107 | 54 | fit.logPower2 = kLogPower2.At(kilometres, draw()); | |
| 108 | 54 | fit.logPower3 = kLogPower3.At(kilometres, draw()); | |
| 109 | 54 | fit.logPower4 = kLogPower4.At(kilometres, draw()); | |
| 110 | 54 | std::vector<std::complex<double>> spectrum(kTableSize); | |
| 111 | 27648 | for (std::size_t k = 1; k < kTableSize / 2; ++k) { | |
| 112 | 27594 | const double noise = scatter ? kSpectrumSigma * Normal(random) : 0.0; | |
| 113 | const double amplitude = | ||
| 114 | 27594 | std::sqrt(std::pow(10.0, fit.LogPower(k) + noise) * 2.0 * std::numbers::pi) / | |
| 115 | 27594 | kSpectrumVertices; | |
| 116 | 27594 | const double phase = 2.0 * std::numbers::pi * random.NextDouble(); | |
| 117 | 27594 | spectrum[k] = std::complex<double>(0.0, -1.0) * std::polar(amplitude, phase); | |
| 118 | } | ||
| 119 | 54 | Fft(spectrum, 1.0); | |
| 120 | 54 | std::vector<double> table(kTableSize); | |
| 121 | 55350 | for (std::size_t n = 0; n < kTableSize; ++n) { | |
| 122 | 55296 | table[n] = spectrum[n].real(); | |
| 123 | } | ||
| 124 | 54 | LimitDeviation(table, maxDeviation); | |
| 125 | 108 | return table; | |
| 126 | 54 | } | |
| 127 | |||
| 128 | /// sum over k of k^-slope squared, from `first` to `last`. | ||
| 129 | 31152 | double PowerSum(int first, int last, double slope) { | |
| 130 | 31152 | double sum = 0.0; | |
| 131 | 373824 | for (int k = first; k <= last; ++k) { | |
| 132 | 342672 | sum += std::pow(static_cast<double>(k), -2.0 * slope); | |
| 133 | } | ||
| 134 | 31152 | return sum; | |
| 135 | } | ||
| 136 | |||
| 137 | /// The uniforms an outline is drawn from, in the order drawn. | ||
| 138 | struct OutlineDraws { | ||
| 139 | double rough, elongated, r1, r2, s1, s2, e1, e2, h; | ||
| 140 | }; | ||
| 141 | |||
| 142 | 51208 | OutlineDraws DrawOutline(RandomStream& random) { | |
| 143 | 51208 | OutlineDraws draws{}; | |
| 144 | 51208 | for (double* draw : {&draws.rough, &draws.elongated, &draws.r1, &draws.r2, &draws.s1, &draws.s2, | |
| 145 | 563288 | &draws.e1, &draws.e2, &draws.h}) { | |
| 146 | 460872 | *draw = random.NextDouble(); | |
| 147 | } | ||
| 148 | 51208 | return draws; | |
| 149 | } | ||
| 150 | |||
| 151 | /// Adds the power-law harmonics of `irregularity` to `outline`. | ||
| 152 | 31152 | void AddHarmonics(CraterOutline& outline, const CraterIrregularity& irregularity, | |
| 153 | const OutlineDraws& draws, RandomStream& random) { | ||
| 154 | 31152 | const double roughness = irregularity.roughness.Sample(draws.r1, draws.r2); | |
| 155 | 31152 | const double slope = irregularity.spectralSlope.Sample(draws.s1, draws.s2); | |
| 156 | 62304 | const double norm = roughness * std::sqrt(2.0 / PowerSum(irregularity.minHarmonic, | |
| 157 | 31152 | irregularity.maxHarmonic, slope)); | |
| 158 | 31152 | outline.firstHarmonic = irregularity.minHarmonic; | |
| 159 | 31152 | if (roughness > 0.0) { | |
| 160 | 373452 | for (int k = irregularity.minHarmonic; k <= irregularity.maxHarmonic; ++k) { | |
| 161 | 342331 | outline.amplitudes.push_back(norm * std::pow(static_cast<double>(k), -slope)); | |
| 162 | 342331 | outline.phases.push_back(2.0 * std::numbers::pi * random.NextDouble()); | |
| 163 | } | ||
| 164 | } | ||
| 165 | 31152 | } | |
| 166 | |||
| 167 | } // namespace | ||
| 168 | |||
| 169 | 246729 | void ValidateCraterIrregularity(const CraterIrregularity& irregularity) { | |
| 170 | 246729 | ValidateValueDistribution(irregularity.roughness); | |
| 171 | 246729 | ValidateValueDistribution(irregularity.spectralSlope); | |
| 172 | 246728 | ValidateValueDistribution(irregularity.ellipticity); | |
| 173 | 740181 | for (const double share : {irregularity.roughShare, irregularity.elongatedShare}) { | |
| 174 | 493455 | RequireUnitInterval(share, "Crater irregularity shares"); | |
| 175 | } | ||
| 176 | 246726 | ValidateCraterSelection(irregularity.selection, "Crater irregularity"); | |
| 177 | 246724 | if (!(irregularity.minHarmonic >= 1 && irregularity.minHarmonic <= irregularity.maxHarmonic && | |
| 178 | 246723 | irregularity.maxHarmonic <= 64)) { | |
| 179 | 2 | throw std::invalid_argument("Crater harmonics must satisfy 1 <= min <= max <= 64"); | |
| 180 | } | ||
| 181 | 246722 | const int harmonics = irregularity.maxHarmonic - irregularity.minHarmonic + 1; | |
| 182 | 493443 | if (!(irregularity.roughness.Lowest() >= 0.0 && | |
| 183 | 246721 | irregularity.roughness.Highest() * std::sqrt(2.0 * harmonics) < 0.5)) { | |
| 184 | throw std::invalid_argument( | ||
| 185 | "Crater roughness must not be negative, and at most 0.5 / sqrt(2 n) radii for n " | ||
| 186 | 2 | "harmonics, so rims cannot fold"); | |
| 187 | } | ||
| 188 | 246720 | if (!(irregularity.ellipticity.Lowest() >= 1.0)) { | |
| 189 | 1 | throw std::invalid_argument("Crater ellipticity must be at least 1"); | |
| 190 | } | ||
| 191 | 246719 | if (!(irregularity.maxDeviation > 0.0 && irregularity.maxDeviation <= 0.5)) { | |
| 192 | 2 | throw std::invalid_argument("Crater maxDeviation must be in (0, 0.5]"); | |
| 193 | } | ||
| 194 | 493433 | if ((irregularity.heading && !std::isfinite(*irregularity.heading)) || | |
| 195 | 246716 | !IsNonNegative(irregularity.headingSpread)) { | |
| 196 | 2 | throw std::invalid_argument("Crater heading and spread must be finite, the spread >= 0"); | |
| 197 | } | ||
| 198 | 246715 | ValidateValueDistribution(irregularity.marksAmplitude); | |
| 199 | 246714 | RequireUnitInterval(irregularity.marksShare, "Crater marks share"); | |
| 200 | 246713 | if (!(irregularity.marksKnots >= 3 && irregularity.marksKnots <= kMaxMarkKnots)) { | |
| 201 | 2 | throw std::invalid_argument("Crater mark knots must be from 3 to 1024"); | |
| 202 | } | ||
| 203 | 246711 | const double fade = irregularity.marksFadeRadii; | |
| 204 | 493420 | if (!(IsPositive(fade) && irregularity.marksInnerRadii - fade >= 0.0 && | |
| 205 | 246709 | irregularity.marksInnerRadii <= irregularity.marksOuterRadii && | |
| 206 | 246708 | irregularity.marksOuterRadii + fade <= 1.0)) { | |
| 207 | throw std::invalid_argument("Crater marks need a positive fade with 0 <= inner - fade, " | ||
| 208 | 4 | "inner <= outer and outer + fade <= 1 radii"); | |
| 209 | } | ||
| 210 | 493413 | if (!(irregularity.marksAmplitude.Lowest() >= 0.0 && | |
| 211 | 246706 | 2.0 * kSplineOvershoot * kSmoothstepSlope * irregularity.marksAmplitude.Highest() < | |
| 212 | fade)) { | ||
| 213 | throw std::invalid_argument("Crater mark amplitude must not be negative, and below fade / " | ||
| 214 | 2 | "3.75 radii so walls cannot fold"); | |
| 215 | } | ||
| 216 | 246705 | } | |
| 217 | |||
| 218 | 1460260 | double CraterOutline::Scale(double dx, double dy) const { | |
| 219 | 1460260 | if (Round()) { | |
| 220 | 1 | return 1.0; | |
| 221 | } | ||
| 222 | 1460259 | const double theta = std::atan2(dy, dx); | |
| 223 | 1460259 | double scale = 1.0; | |
| 224 | 1460259 | if (ellipticity != 1.0) { | |
| 225 | 1088282 | const double along = std::sqrt(ellipticity); | |
| 226 | 1088282 | const double across = 1.0 / along; | |
| 227 | 1088282 | const double c = std::cos(theta - heading) / along; | |
| 228 | 1088282 | const double s = std::sin(theta - heading) / across; | |
| 229 | 1088282 | scale = 1.0 / std::sqrt(c * c + s * s); | |
| 230 | } | ||
| 231 | 1460259 | double wobble = 1.0; | |
| 232 | 1460259 | if (!table.empty()) { | |
| 233 | 2002 | const double turns = theta / (2.0 * std::numbers::pi); | |
| 234 | 2002 | const double position = (turns - std::floor(turns)) * static_cast<double>(table.size()); | |
| 235 | 2002 | const auto index = std::min(static_cast<std::size_t>(position), table.size() - 1); | |
| 236 | 2002 | const double t = position - static_cast<double>(index); | |
| 237 | 2002 | wobble += (1.0 - t) * table[index] + t * table[(index + 1) % table.size()]; | |
| 238 | } | ||
| 239 | 17032838 | for (std::size_t n = 0; n < amplitudes.size(); ++n) { | |
| 240 | 15572579 | const double k = static_cast<double>(firstHarmonic) + static_cast<double>(n); | |
| 241 | 15572579 | wobble += amplitudes[n] * std::cos(k * theta + phases[n]); | |
| 242 | } | ||
| 243 | 1460259 | return scale * wobble; | |
| 244 | } | ||
| 245 | |||
| 246 | 1396310 | double CraterOutline::MarkShift(double dx, double dy, double radii) const { | |
| 247 | 1461152 | if (marks.empty() || !(radii > marksInnerRadii - marksFadeRadii) || | |
| 248 | 64842 | !(radii < marksOuterRadii + marksFadeRadii)) { | |
| 249 | 1339505 | return 0.0; | |
| 250 | } | ||
| 251 | 56805 | const double window = Smoothstep((radii - marksInnerRadii + marksFadeRadii) / marksFadeRadii) * | |
| 252 | 56805 | Smoothstep((marksOuterRadii + marksFadeRadii - radii) / marksFadeRadii); | |
| 253 | const double turns = | ||
| 254 | 56805 | (dx == 0.0 && dy == 0.0) ? 0.0 : std::atan2(dy, dx) / (2.0 * std::numbers::pi); | |
| 255 | 56805 | const std::size_t size = marks.size(); | |
| 256 | 56805 | const double position = (turns - std::floor(turns)) * static_cast<double>(size); | |
| 257 | 56805 | const auto index = std::min(static_cast<std::size_t>(position), size - 1); | |
| 258 | 56805 | const double t = position - static_cast<double>(index); | |
| 259 | 56805 | const double p0 = marks[(index + size - 1) % size]; | |
| 260 | 56805 | const double p1 = marks[index]; | |
| 261 | 56805 | const double p2 = marks[(index + 1) % size]; | |
| 262 | 56805 | const double p3 = marks[(index + 2) % size]; | |
| 263 | 56805 | const double shift = | |
| 264 | 56805 | 0.5 * (2.0 * p1 + (p2 - p0) * t + (2.0 * p0 - 5.0 * p1 + 4.0 * p2 - p3) * t * t + | |
| 265 | 56805 | (3.0 * (p1 - p2) + p3 - p0) * t * t * t); | |
| 266 | 56805 | return window * shift; | |
| 267 | } | ||
| 268 | |||
| 269 | 12052752 | double CraterOutline::MaxScale() const { | |
| 270 | 12052752 | double sum = 1.0; | |
| 271 | 12103952 | for (const double deviation : table) { | |
| 272 | 51200 | sum = std::fmax(sum, 1.0 + deviation); | |
| 273 | } | ||
| 274 | 12734983 | for (const double amplitude : amplitudes) { | |
| 275 | 682231 | sum += std::fabs(amplitude); | |
| 276 | } | ||
| 277 | 12052752 | return std::sqrt(ellipticity) * sum; | |
| 278 | } | ||
| 279 | |||
| 280 | 6255629 | CraterOutline OutlineOf(const Crater& crater, const CraterIrregularity& irregularity) { | |
| 281 | 6255629 | CraterOutline outline; | |
| 282 | 6255629 | if (!irregularity.enabled || !irregularity.selection.Includes(crater)) { | |
| 283 | 6204421 | return outline; | |
| 284 | } | ||
| 285 | 51208 | const IdWords id = SplitId(crater.id); | |
| 286 | 51208 | RandomStream random(irregularity.seed, kIrregularityStream, id.low, id.high); | |
| 287 | 51208 | const OutlineDraws draws = DrawOutline(random); | |
| 288 | 51208 | if (draws.elongated < irregularity.elongatedShare) { | |
| 289 | 8096 | outline.ellipticity = irregularity.ellipticity.Sample(draws.e1, draws.e2); | |
| 290 | 8096 | outline.heading = | |
| 291 | 8096 | irregularity.heading | |
| 292 | 8096 | ? *irregularity.heading + irregularity.headingSpread * (2.0 * draws.h - 1.0) | |
| 293 | 6467 | : std::numbers::pi * draws.h; | |
| 294 | } | ||
| 295 | 51208 | if (draws.rough < irregularity.roughShare && irregularity.model == RimRoughnessModel::Du2024) { | |
| 296 | 54 | outline.table = | |
| 297 | 54 | DuRimTable(crater.diameter, irregularity.scatter, irregularity.maxDeviation, random); | |
| 298 | 51154 | } else if (draws.rough < irregularity.roughShare) { | |
| 299 | 31152 | AddHarmonics(outline, irregularity, draws, random); | |
| 300 | } | ||
| 301 | 51208 | if (irregularity.marksShare > 0.0) { | |
| 302 | 4681 | RandomStream marks(irregularity.seed, kMarksStream, id.low, id.high); | |
| 303 | 4681 | const double share = marks.NextDouble(); | |
| 304 | 4681 | const double u1 = marks.NextDouble(); | |
| 305 | 4681 | const double u2 = marks.NextDouble(); | |
| 306 | 4681 | const double amplitude = irregularity.marksAmplitude.Sample(u1, u2); | |
| 307 | 4681 | if (share < irregularity.marksShare && amplitude > 0.0) { | |
| 308 | 1647 | outline.marks.resize(static_cast<std::size_t>(irregularity.marksKnots)); | |
| 309 | 75729 | for (double& knot : outline.marks) { | |
| 310 | 74082 | knot = amplitude * (2.0 * marks.NextDouble() - 1.0); | |
| 311 | } | ||
| 312 | 1647 | outline.marksInnerRadii = irregularity.marksInnerRadii; | |
| 313 | 1647 | outline.marksOuterRadii = irregularity.marksOuterRadii; | |
| 314 | 1647 | outline.marksFadeRadii = irregularity.marksFadeRadii; | |
| 315 | } | ||
| 316 | } | ||
| 317 | 51208 | return outline; | |
| 318 | } | ||
| 319 | |||
| 320 | 6188 | double MaxOutlineScale(const CraterIrregularity& irregularity) { | |
| 321 | 6188 | if (!irregularity.enabled) { | |
| 322 | 4547 | return 1.0; | |
| 323 | } | ||
| 324 | 1641 | const int harmonics = irregularity.maxHarmonic - irregularity.minHarmonic + 1; | |
| 325 | 1641 | double rough = 1.0; | |
| 326 | 1641 | if (irregularity.roughShare > 0.0) { | |
| 327 | 1641 | rough = irregularity.model == RimRoughnessModel::Du2024 | |
| 328 | 1641 | ? 1.0 + irregularity.maxDeviation | |
| 329 | 1640 | : 1.0 + irregularity.roughness.Highest() * std::sqrt(2.0 * harmonics); | |
| 330 | } | ||
| 331 | const double elongated = | ||
| 332 | 1641 | irregularity.elongatedShare > 0.0 ? std::sqrt(irregularity.ellipticity.Highest()) : 1.0; | |
| 333 | 1641 | return rough * elongated; | |
| 334 | } | ||
| 335 | |||
| 336 | 10536092 | double CraterProfileDistance(const Crater& crater, const CraterOutline& outline, double x, double y, | |
| 337 | const Surface& surface) { | ||
| 338 | 10536092 | return CraterProfileDistance(crater, outline, surface.Offset({crater.x, crater.y}, {x, y})); | |
| 339 | } | ||
| 340 | |||
| 341 | 11590099 | double CraterProfileDistance(const Crater& crater, const CraterOutline& outline, | |
| 342 | const Vec2d& offset) { | ||
| 343 | 11590099 | const double distance = std::sqrt(offset.x * offset.x + offset.y * offset.y); | |
| 344 | 11590099 | if (outline.Round()) { | |
| 345 | 10223064 | return distance; | |
| 346 | } | ||
| 347 | 1367035 | const double scaled = distance / outline.Scale(offset.x, offset.y); | |
| 348 | 1367035 | const double radius = 0.5 * crater.diameter; | |
| 349 | 1367035 | return scaled + radius * outline.MarkShift(offset.x, offset.y, scaled / radius); | |
| 350 | } | ||
| 351 | |||
| 352 | } // namespace terraingen | ||
| 353 |