TerrainGen coverage

terraingen/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
91 / 91
100.0%
Branches:
92 / 93
98.9%
Functions:
14 / 14
100.0%
layers/craters/generation/spacing.cpp
Line Branch Exec Source
1 #include "terraingen/layers/craters/generation/spacing.h"
2
3 #include "terraingen/util/checks.h"
4
5 #include <array>
6 #include <cmath>
7 #include <cstdint>
8 #include <map>
9 #include <stdexcept>
10 #include <unordered_map>
11
12 namespace terraingen {
13
14 namespace {
15
16 using CellKey = std::array<long long, 3>;
17
18 struct CellKeyHash {
19 500715 std::size_t operator()(const CellKey& key) const {
20 500715 std::uint64_t hash = 1469598103934665603ull;
21
2/2
✓ Branch 2 taken 1502145 times.
✓ Branch 3 taken 500715 times.
 2002860 for (const long long part : key) {
22 1502145 hash = (hash ^ static_cast<std::uint64_t>(part)) * 1099511628211ull;
23 }
24 500715 return static_cast<std::size_t>(hash);
25 }
26 };
27
28 /// Craters of one diameter band [2^k, 2^(k+1)) hashed into cubic cells (`Surface::Bucket`) at least
29 /// as wide as any distance at which a crater can conflict with them.
30 struct BandGrid {
31 double cellSize = 0.0;
32 std::unordered_map<CellKey, std::vector<std::size_t>, CellKeyHash> cells;
33 };
34
35 86911 CellKey KeyOf(const Crater& crater, double size, const Surface& surface) {
36
1/1
✓ Branch 1 taken 86911 times.
 86911 const BucketIndex bucket = surface.Bucket({crater.x, crater.y}, size);
37 86911 return {bucket.i, bucket.j, bucket.k};
38 }
39
40 /// The craters of `craters` bucketed by band.
41 44 std::map<int, BandGrid> BandGrids(const CraterList& craters, const CraterSpacing& spacing,
42 const Surface& surface) {
43 44 std::map<int, BandGrid> bands;
44
2/2
✓ Branch 1 taken 30521 times.
✓ Branch 2 taken 44 times.
 30565 for (std::size_t n = 0; n < craters.Size(); ++n) {
45
1/1
✓ Branch 1 taken 30521 times.
 30521 const Crater crater = craters.At(n);
46 30521 const int band = std::ilogb(crater.diameter);
47
1/1
✓ Branch 1 taken 30521 times.
 30521 BandGrid& grid = bands[band];
48
2/2
✓ Branch 0 taken 181 times.
✓ Branch 1 taken 30340 times.
 30521 if (grid.cellSize == 0.0) {
49 181 grid.cellSize = spacing.separation * spacing.diameterRatio * std::ldexp(1.0, band + 1);
50 }
51
3/3
✓ Branch 1 taken 30521 times.
✓ Branch 4 taken 30521 times.
✓ Branch 7 taken 30521 times.
 30521 grid.cells[KeyOf(crater, grid.cellSize, surface)].push_back(n);
52 }
53 44 return bands;
54 }
55
56 /// Finds whether crater `n` conflicts with a crater that takes precedence over it.
57 class ConflictSearch {
58 public:
59 44 ConflictSearch(const CraterList& craters, const CraterSpacing& spacing, const Surface& surface)
60 44 : craters_(craters), spacing_(spacing), surface_(surface),
61 44 bands_(BandGrids(craters, spacing, surface)) {}
62
63 30499 bool Outranked(std::size_t n) const {
64
1/1
✓ Branch 1 taken 30499 times.
 30499 const Crater crater = craters_.At(n);
65 30499 const int lowest = std::ilogb(crater.diameter / spacing_.diameterRatio);
66 30499 const int highest = std::ilogb(crater.diameter * spacing_.diameterRatio);
67
2/2
✓ Branch 0 taken 75024 times.
✓ Branch 1 taken 19930 times.
 94954 for (int band = lowest; band <= highest; ++band) {
68
1/1
✓ Branch 1 taken 75024 times.
 75024 const auto found = bands_.find(band);
69
7/7
✓ Branch 2 taken 56390 times.
✓ Branch 3 taken 18634 times.
✓ Branch 6 taken 56390 times.
✓ Branch 8 taken 10569 times.
✓ Branch 9 taken 45821 times.
✓ Branch 10 taken 10569 times.
✓ Branch 11 taken 64455 times.
 75024 if (found != bands_.end() && OutrankedIn(found->second, n, crater)) {
70 10569 return true;
71 }
72 }
73 19930 return false;
74 }
75
76 private:
77 /// Whether a crater in the cells of `grid` around `crater` outranks it.
78 56390 bool OutrankedIn(const BandGrid& grid, std::size_t n, const Crater& crater) const {
79
1/1
✓ Branch 1 taken 56390 times.
 56390 const CellKey centre = KeyOf(crater, grid.cellSize, surface_);
80
2/2
✓ Branch 1 taken 379 times.
✓ Branch 2 taken 56011 times.
 56390 const long long depth = surface_.IsBody() ? 1 : 0;
81
2/2
✓ Branch 0 taken 158153 times.
✓ Branch 1 taken 45821 times.
 203974 for (long long di = -1; di <= 1; ++di) {
82
2/2
✓ Branch 0 taken 463628 times.
✓ Branch 1 taken 147584 times.
 611212 for (long long dj = -1; dj <= 1; ++dj) {
83
2/2
✓ Branch 0 taken 470194 times.
✓ Branch 1 taken 453059 times.
 923253 for (long long dk = -depth; dk <= depth; ++dk) {
84 const auto cell =
85
1/1
✓ Branch 4 taken 470194 times.
 470194 grid.cells.find({centre[0] + di, centre[1] + dj, centre[2] + dk});
86
7/7
✓ Branch 2 taken 287562 times.
✓ Branch 3 taken 182632 times.
✓ Branch 6 taken 287562 times.
✓ Branch 8 taken 10569 times.
✓ Branch 9 taken 276993 times.
✓ Branch 10 taken 10569 times.
✓ Branch 11 taken 459625 times.
 470194 if (cell != grid.cells.end() && OutrankedBy(cell->second, n, crater)) {
87 10569 return true;
88 }
89 }
90 }
91 }
92 45821 return false;
93 }
94
95 /// Whether one of `others` conflicts with `crater` and takes precedence over it.
96 287562 bool OutrankedBy(const std::vector<std::size_t>& others, std::size_t n,
97 const Crater& crater) const {
98
2/2
✓ Branch 5 taken 635802 times.
✓ Branch 6 taken 276993 times.
 912795 for (const std::size_t other : others) {
99
2/2
✓ Branch 0 taken 24487 times.
✓ Branch 1 taken 611315 times.
 635802 if (other == n) {
100 24487 continue;
101 }
102
1/1
✓ Branch 1 taken 611315 times.
 611315 const Crater neighbour = craters_.At(other);
103
7/7
✓ Branch 1 taken 611315 times.
✓ Branch 3 taken 23976 times.
✓ Branch 4 taken 587339 times.
✓ Branch 5 taken 10569 times.
✓ Branch 6 taken 13407 times.
✓ Branch 7 taken 10569 times.
✓ Branch 8 taken 600746 times.
 635291 if (CratersConflict(crater, neighbour, spacing_, surface_) &&
104 23976 CraterTakesPrecedence(neighbour, crater, spacing_.outrankFrom)) {
105 10569 return true;
106 }
107 }
108 276993 return false;
109 }
110
111 const CraterList& craters_;
112 const CraterSpacing& spacing_;
113 const Surface& surface_;
114 std::map<int, BandGrid> bands_;
115 };
116
117 } // namespace
118
119 365673 void ValidateCraterSpacing(const CraterSpacing& spacing) {
120
6/6
✓ Branch 1 taken 365672 times.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 5 times.
✓ Branch 4 taken 365667 times.
✓ Branch 5 taken 6 times.
✓ Branch 6 taken 365667 times.
 365673 if (!(std::isfinite(spacing.diameterRatio) && spacing.diameterRatio >= 1.0)) {
121
1/1
✓ Branch 2 taken 6 times.
 6 throw std::invalid_argument("Crater spacing diameter ratio must be at least 1");
122 }
123
1/1
✓ Branch 2 taken 365666 times.
 365667 RequireNonNegative(spacing.separation, "Crater spacing separation");
124 365666 }
125
126 1160146 bool CratersConflict(const Crater& a, const Crater& b, const CraterSpacing& spacing,
127 const Surface& surface) {
128 1160146 const double larger = std::fmax(a.diameter, b.diameter);
129 1160146 const double smaller = std::fmin(a.diameter, b.diameter);
130
2/2
✓ Branch 0 taken 472729 times.
✓ Branch 1 taken 687417 times.
 1160146 if (larger > spacing.diameterRatio * smaller) {
131 472729 return false;
132 }
133 687417 const double limit = spacing.separation * larger;
134
2/2
✓ Branch 1 taken 540 times.
✓ Branch 2 taken 686877 times.
 687417 if (surface.IsBody()) {
135
1/1
✓ Branch 1 taken 540 times.
 540 return surface.Distance({a.x, a.y}, {b.x, b.y}) < limit;
136 }
137 686877 const double dx = a.x - b.x;
138 686877 const double dy = a.y - b.y;
139 686877 return dx * dx + dy * dy < limit * limit;
140 }
141
142 24409 bool CraterTakesPrecedence(const Crater& a, const Crater& b, double outrankFrom) {
143
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 24402 times.
 24409 if (a.manual != b.manual) {
144 7 return a.manual;
145 }
146
2/2
✓ Branch 0 taken 450 times.
✓ Branch 1 taken 23952 times.
 24402 if ((a.diameter >= outrankFrom) != (b.diameter >= outrankFrom)) {
147 450 return a.diameter >= outrankFrom;
148 }
149
2/2
✓ Branch 0 taken 23755 times.
✓ Branch 1 taken 197 times.
 23952 if (a.ageGyr != b.ageGyr) {
150 23755 return a.ageGyr < b.ageGyr;
151 }
152
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 5 times.
 197 if (a.diameter != b.diameter) {
153 192 return a.diameter > b.diameter;
154 }
155 5 return a.id < b.id;
156 }
157
158 4842 double SpacingReach(double diameter, double maxDiameter, const CraterSpacing& spacing) {
159 4842 return spacing.separation * std::fmin(spacing.diameterRatio * diameter, maxDiameter);
160 }
161
162 49 std::vector<bool> SpacingConflicts(const CraterList& craters, const CraterSpacing& spacing,
163 const Surface& surface) {
164
1/1
✓ Branch 1 taken 46 times.
 49 ValidateCraterSpacing(spacing);
165
1/1
✓ Branch 2 taken 46 times.
 46 std::vector<bool> conflicts(craters.Size(), false);
166
5/6
✓ Branch 1 taken 44 times.
✓ Branch 2 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 44 times.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 44 times.
 46 if (!spacing.Enabled() || craters.Size() < 2) {
167 2 return conflicts;
168 }
169
1/1
✓ Branch 1 taken 44 times.
 44 const ConflictSearch search(craters, spacing, surface);
170
2/2
✓ Branch 1 taken 30521 times.
✓ Branch 2 taken 44 times.
 30565 for (std::size_t n = 0; n < craters.Size(); ++n) {
171
7/7
✓ Branch 1 taken 30521 times.
✓ Branch 3 taken 30499 times.
✓ Branch 4 taken 22 times.
✓ Branch 6 taken 30499 times.
✓ Branch 8 taken 10569 times.
✓ Branch 9 taken 19930 times.
✓ Branch 11 taken 30521 times.
 30521 conflicts[n] = !craters.At(n).manual && search.Outranked(n);
172 }
173 44 return conflicts;
174 44 }
175
176 4 CraterList ThinBySpacing(const CraterList& craters, const CraterSpacing& spacing,
177 const Surface& surface) {
178
1/1
✓ Branch 1 taken 4 times.
 4 const std::vector<bool> conflicts = SpacingConflicts(craters, spacing, surface);
179
1/1
✓ Branch 1 taken 4 times.
 19 return FilterCraters(craters, [&](std::size_t n, const Crater&) { return !conflicts[n]; });
180 4 }
181
182 } // namespace terraingen
183