TerrainGen coverage

terraingen/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
114 / 114
100.0%
Branches:
69 / 76
90.8%
Functions:
23 / 23
100.0%
pipeline/tiles.cpp
Line Branch Exec Source
1 #include "terraingen/pipeline/tiles.h"
2
3 #include "terraingen/noise/hash.h"
4 #include "terraingen/util/checks.h"
5 #include "terraingen/util/parallel.h"
6
7 #include <algorithm>
8 #include <cmath>
9 #include <stdexcept>
10 #include <utility>
11
12 namespace terraingen {
13
14 namespace {
15
16 constexpr int kMaxLevel = 60;
17 /// The deepest whole-body level whose 2^(2L+1) tiles can be counted in 64 bits.
18 constexpr int kMaxBodyTileLevel = 30;
19
20 26 std::int64_t FloorDivide(std::int64_t value, std::int64_t divisor) {
21 26 const std::int64_t quotient = value / divisor;
22
4/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 8 times.
 26 return (value % divisor != 0 && ((value < 0) != (divisor < 0))) ? quotient - 1 : quotient;
23 }
24
25 890 void CheckLevel(int level) {
26
4/4
✓ Branch 0 taken 886 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 885 times.
 890 if (level < 0 || level > kMaxLevel) {
27
1/1
✓ Branch 1 taken 5 times.
 10 throw std::invalid_argument("Tile level must be between 0 and " +
28
1/1
✓ Branch 3 taken 5 times.
 15 std::to_string(kMaxLevel));
29 }
30 885 }
31
32 639 std::size_t TileBytes(const Raster<float>& tile) {
33 639 return tile.Size() * sizeof(float);
34 }
35
36 } // namespace
37
38 2972 std::size_t TileKeyHash::operator()(const TileKey& key) const {
39 const UVec3 hash =
40 2972 Pcg3dHash({static_cast<std::uint32_t>(key.level),
41 2972 static_cast<std::uint32_t>(key.x) ^ static_cast<std::uint32_t>(key.x >> 32),
42 2972 static_cast<std::uint32_t>(key.y) ^ static_cast<std::uint32_t>(key.y >> 32)});
43 2972 return (static_cast<std::size_t>(hash.x) << 32) ^ hash.y;
44 }
45
46 13 TileScheme TileScheme::Covering(const RasterGrid& grid, std::size_t cells) {
47 13 const GeoTransform& t = grid.transform;
48
4/6
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 12 times.
 13 if (grid.width == 0 || grid.height == 0 || cells == 0) {
49
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("A tile scheme needs a non-empty grid and cells");
50 }
51
4/6
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 11 times.
✗ Branch 5 not taken.
 12 if (t.rowRotation != 0.0 || t.colRotation != 0.0 || !(t.pixelWidth > 0.0) ||
52
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
 11 t.pixelHeight != -t.pixelWidth) {
53
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("A tile scheme covers north-up grids with square cells");
54 }
55 11 const double tileSize = static_cast<double>(cells) * t.pixelWidth;
56 11 const double extent =
57 11 std::fmax(static_cast<double>(grid.width), static_cast<double>(grid.height)) * t.pixelWidth;
58 11 double rootSize = tileSize;
59
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 11 times.
 35 while (rootSize < extent) {
60 24 rootSize *= 2.0;
61 }
62 11 return {{t.originX, t.originY}, rootSize, cells};
63 }
64
65 734 void TileScheme::Validate() const {
66
1/1
✓ Branch 2 taken 730 times.
 734 RequirePositive(rootSize, "Tile root size");
67
5/6
✓ Branch 1 taken 729 times.
✓ Branch 2 taken 1 time.
✗ Branch 4 not taken.
✓ Branch 5 taken 729 times.
✓ Branch 6 taken 1 time.
✓ Branch 7 taken 729 times.
 730 if (!(std::isfinite(origin.x) && std::isfinite(origin.y))) {
68
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("Tile origin must be finite");
69 }
70
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 728 times.
 729 if (cells == 0) {
71
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("Tiles need at least one cell");
72 }
73 728 }
74
75 854 double TileScheme::TileSize(int level) const {
76 854 CheckLevel(level);
77 853 return std::ldexp(rootSize, -level);
78 }
79
80 57 double TileScheme::Spacing(int level) const {
81 57 return TileSize(level) / static_cast<double>(cells);
82 }
83
84 15 int TileScheme::LevelFor(double spacing) const {
85
1/1
✓ Branch 2 taken 14 times.
 15 RequirePositive(spacing, "Spacing");
86 14 int level = 0;
87
5/6
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 24 times.
✓ Branch 4 taken 14 times.
✓ Branch 5 taken 24 times.
✓ Branch 6 taken 14 times.
 38 while (level < kMaxLevel && Spacing(level) > spacing) {
88 24 ++level;
89 }
90 14 return level;
91 }
92
93 8 TileKey TileScheme::TileAt(double x, double y, int level) const {
94 8 const double size = TileSize(level);
95 8 return {level, static_cast<std::int64_t>(std::floor((x - origin.x) / size)),
96 8 static_cast<std::int64_t>(std::floor((origin.y - y) / size))};
97 }
98
99 11 std::vector<TileKey> TileScheme::TilesCovering(const Bounds2d& bounds, int level) const {
100 11 const double size = TileSize(level);
101 11 const auto x0 = static_cast<std::int64_t>(std::floor((bounds.minX - origin.x) / size));
102 11 const auto x1 = static_cast<std::int64_t>(std::ceil((bounds.maxX - origin.x) / size));
103 11 const auto y0 = static_cast<std::int64_t>(std::floor((origin.y - bounds.maxY) / size));
104 11 const auto y1 = static_cast<std::int64_t>(std::ceil((origin.y - bounds.minY) / size));
105 11 std::vector<TileKey> keys;
106
2/2
✓ Branch 0 taken 69 times.
✓ Branch 1 taken 11 times.
 80 for (std::int64_t y = y0; y < y1; ++y) {
107
2/2
✓ Branch 0 taken 834 times.
✓ Branch 1 taken 69 times.
 903 for (std::int64_t x = x0; x < x1; ++x) {
108
1/1
✓ Branch 1 taken 834 times.
 834 keys.push_back({level, x, y});
109 }
110 }
111 11 return keys;
112 }
113
114 770 RasterGrid TileScheme::Grid(const TileKey& key) const {
115 770 const double size = TileSize(key.level);
116 770 return {cells, cells,
117 770 GeoTransform::NorthUp(origin.x + static_cast<double>(key.x) * size,
118 770 origin.y - static_cast<double>(key.y) * size,
119 770 size / static_cast<double>(cells))};
120 }
121
122 14 TileKey TileScheme::Parent(const TileKey& key) {
123 14 CheckLevel(key.level);
124
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 13 times.
 14 if (key.level == 0) {
125
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("Level 0 tiles have no parent");
126 }
127 13 return {key.level - 1, FloorDivide(key.x, 2), FloorDivide(key.y, 2)};
128 }
129
130 4 std::array<TileKey, 4> TileScheme::Children(const TileKey& key) {
131 4 CheckLevel(key.level + 1);
132 4 const int level = key.level + 1;
133 4 return {TileKey{level, 2 * key.x, 2 * key.y}, TileKey{level, 2 * key.x + 1, 2 * key.y},
134 4 TileKey{level, 2 * key.x, 2 * key.y + 1}, TileKey{level, 2 * key.x + 1, 2 * key.y + 1}};
135 }
136
137 4 TileScheme TileScheme::WholeBody(std::size_t cells) {
138 4 TileScheme scheme{{-180.0, 90.0}, 180.0, cells};
139 4 scheme.Validate();
140 4 return scheme;
141 }
142
143 12 std::vector<TileKey> TileScheme::BodyTiles(int level) {
144 12 CheckLevel(level);
145
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 9 times.
 10 if (level > kMaxBodyTileLevel) {
146
1/1
✓ Branch 1 taken 1 time.
 2 throw std::invalid_argument("Whole-body tile levels must be at most " +
147
1/1
✓ Branch 3 taken 1 time.
 3 std::to_string(kMaxBodyTileLevel));
148 }
149 9 const std::int64_t rows = std::int64_t{1} << level;
150 9 std::vector<TileKey> keys;
151
1/1
✓ Branch 1 taken 9 times.
 9 keys.reserve(static_cast<std::size_t>(2 * rows * rows));
152
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 9 times.
 31 for (std::int64_t y = 0; y < rows; ++y) {
153
2/2
✓ Branch 0 taken 132 times.
✓ Branch 1 taken 22 times.
 154 for (std::int64_t x = 0; x < 2 * rows; ++x) {
154
1/1
✓ Branch 1 taken 132 times.
 132 keys.push_back({level, x, y});
155 }
156 }
157 9 return keys;
158 }
159
160 6 TileKey TileScheme::WrapBodyTile(const TileKey& key) {
161 6 CheckLevel(key.level);
162 4 const std::int64_t columns = std::int64_t{2} << key.level;
163 4 return {key.level, ((key.x % columns) + columns) % columns, key.y};
164 }
165
166 716 Raster<float> EvaluateTile(const Terrain& terrain, const TileScheme& scheme, const TileKey& key,
167 unsigned threads) {
168
1/1
✓ Branch 1 taken 715 times.
 716 scheme.Validate();
169
1/1
✓ Branch 1 taken 715 times.
 715 const RasterGrid tile = scheme.Grid(key);
170
2/2
✓ Branch 1 taken 715 times.
✓ Branch 6 taken 715 times.
 715 return Evaluate(terrain, tile, EvaluationOptions{tile.Spacing(terrain.surface), threads});
171 }
172
173 5 std::vector<Raster<float>> EvaluateTiles(const Terrain& terrain, const TileScheme& scheme,
174 const std::vector<TileKey>& keys, unsigned threads) {
175
1/1
✓ Branch 2 taken 5 times.
 5 std::vector<Raster<float>> tiles(keys.size());
176
1/1
✓ Branch 2 taken 5 times.
 5 ParallelFor(keys.size(), threads,
177
2/2
✓ Branch 1 taken 5 times.
✓ Branch 5 taken 46 times.
 51 [&](std::size_t n) { tiles[n] = EvaluateTile(terrain, scheme, keys[n], 1); });
178 5 return tiles;
179 }
180
181 9 TileCache::TileCache(Terrain terrain, TileScheme scheme, std::size_t maxBytes)
182
1/1
✓ Branch 5 taken 8 times.
 11 : terrain_(std::move(terrain)), scheme_(scheme), cache_(maxBytes, TileBytes) {
183
1/1
✓ Branch 1 taken 7 times.
 8 scheme_.Validate();
184
1/1
✓ Branch 1 taken 6 times.
 7 ValidateTerrain(terrain_);
185 11 }
186
187 673 std::shared_ptr<const Raster<float>> TileCache::Get(const TileKey& key) {
188
1/1
✓ Branch 2 taken 673 times.
 1312 return cache_.Get(key, [&] { return EvaluateTile(terrain_, scheme_, key, 1); });
189 }
190
191 } // namespace terraingen
192