TerrainGen coverage

terraingen/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
12 / 12
100.0%
Branches:
3 / 6
50.0%
Functions:
5 / 5, 1 excl
100.0%
pipeline/tiles.h
Line Branch Exec Source
1 /// @file
2 /// @brief Quadtree tile schemes, terrain tiles evaluated on them, and a cache of those tiles.
3 #pragma once
4
5 #include "terraingen/pipeline/terrain.h"
6 #include "terraingen/raster/grid.h"
7 #include "terraingen/util/geometry.h"
8 #include "terraingen/util/lru_cache.h"
9
10 #include <array>
11 #include <cstddef>
12 #include <cstdint>
13 #include <functional>
14 #include <memory>
15 #include <vector>
16
17 namespace terraingen {
18
19 /// A tile of a `TileScheme`: column `x` (east) and row `y` (south) of the tiles at `level`.
20 struct TileKey {
21 551 int level = 0;
22 551 std::int64_t x = 0;
23 551 std::int64_t y = 0;
24
25
3/6
✗ Branch 0 not taken.
✓ Branch 1 taken 551 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 551 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 551 times.
 551 bool operator==(const TileKey&) const = default;
26 };
27
28 /// Hashes a `TileKey`, for maps and caches.
29 struct TileKeyHash {
30 /// A hash of the key's level, column and row.
31 std::size_t operator()(const TileKey& key) const;
32 };
33
34 /// A quadtree of north-up tiles, as in a renderer's level-of-detail quadtree.
35 ///
36 /// Level 0 has square tiles `rootSize` world units on a side, tile (0, 0) with its top-left corner
37 /// at `origin`; each level halves the side, so tile (x, y) at level L has the children
38 /// (2x + i, 2y + j) at level L + 1. Every tile has `cells` x `cells` samples, so the spacing halves
39 /// with each level. Tiles extend in every direction, negative indices west and north of the origin.
40 /// Levels run from 0 to 60.
41 struct TileScheme {
42 Vec2d origin{}; ///< Top-left corner of tile (0, 0), in world units.
43 double rootSize = 1.0; ///< Side of a level-0 tile, in world units.
44 std::size_t cells = 256; ///< Samples along each side of a tile.
45
46 /// A scheme covering a north-up grid with square cells, one of whose levels has the grid's
47 /// cell size: the origin at the grid's top-left corner, and the root the smallest
48 /// power-of-two multiple of `cells` grid cells covering the whole grid, so tiles at that level
49 /// lie on the grid's lattice.
50 /// @throws std::invalid_argument for an empty, rotated or not north-up grid, cells that are not
51 /// square, or zero `cells`.
52 static TileScheme Covering(const RasterGrid& grid, std::size_t cells = 256);
53
54 /// A longitude-latitude pyramid over a whole body, for terrains on a sphere: the origin
55 /// at (-180, 90) and root tiles 180 degrees across, so level L has 2^(L+1) x 2^L tiles covering
56 /// every longitude and latitude once (`BodyTiles`). Spacings are in degrees; a tile's spacing
57 /// in metres is `RasterGrid::Spacing` on the sphere.
58 /// @throws std::invalid_argument for zero `cells`.
59 static TileScheme WholeBody(std::size_t cells = 256);
60
61 /// Every tile of `level` of a `WholeBody` scheme, row by row from the north-west.
62 /// @throws std::invalid_argument for a level outside [0, 30].
63 static std::vector<TileKey> BodyTiles(int level);
64
65 /// `key`, a tile of a `WholeBody` scheme, with its column wrapped across the antimeridian into
66 /// [0, 2^(level+1)).
67 /// @throws std::invalid_argument for a level outside [0, 60].
68 static TileKey WrapBodyTile(const TileKey& key);
69
70 /// Checks the scheme.
71 /// @throws std::invalid_argument for a non-positive or non-finite `rootSize`, a non-finite
72 /// origin, or zero `cells`.
73 void Validate() const;
74
75 /// The side of a tile at `level`, in world units.
76 /// @throws std::invalid_argument for a level outside [0, 60].
77 double TileSize(int level) const;
78
79 /// The sample spacing of `level` in world units: the tile side over `cells`.
80 /// @throws std::invalid_argument for a level outside [0, 60].
81 double Spacing(int level) const;
82
83 /// The coarsest level, from 0 to 60, whose spacing is at most `spacing` world units.
84 /// @throws std::invalid_argument if `spacing` is not positive and finite.
85 int LevelFor(double spacing) const;
86
87 /// The tile at `level` containing world point (`x`, `y`); points on a shared edge belong to the
88 /// tile east or south of it.
89 /// @throws std::invalid_argument for a level outside [0, 60].
90 TileKey TileAt(double x, double y, int level) const;
91
92 /// The tiles at `level` that intersect `bounds` (world units), row by row from the north-west.
93 /// @throws std::invalid_argument for a level outside [0, 60].
94 std::vector<TileKey> TilesCovering(const Bounds2d& bounds, int level) const;
95
96 /// A tile's grid of `cells` x `cells` samples.
97 /// @throws std::invalid_argument for a level outside [0, 60].
98 RasterGrid Grid(const TileKey& key) const;
99
100 /// The tile one level coarser containing `key`.
101 /// @throws std::invalid_argument for level 0 or a level above 60.
102 static TileKey Parent(const TileKey& key);
103
104 /// The four tiles one level finer covering `key`: north-west, north-east, south-west,
105 /// south-east.
106 /// @throws std::invalid_argument for a level outside [0, 59].
107 static std::array<TileKey, 4> Children(const TileKey& key);
108 };
109
110 /// The heights of one tile of a scheme at its level's spacing, as a piece of the unbounded terrain.
111 ///
112 /// The tile equals the same cells of any larger grid on the same lattice (to the bit where cell
113 /// centres coincide exactly, such as with power-of-two spacings).
114 /// @param threads Threads to use; 0 for every hardware thread.
115 /// @throws std::invalid_argument for an invalid scheme, level or terrain; and whatever the parts
116 /// throw.
117 Raster<float> EvaluateTile(const Terrain& terrain, const TileScheme& scheme, const TileKey& key,
118 unsigned threads = 1);
119
120 /// `EvaluateTile` for several tiles, split over threads, in the order of `keys`.
121 /// @param threads Threads to use; 0 for every hardware thread.
122 /// @throws std::invalid_argument as `EvaluateTile`.
123 std::vector<Raster<float>> EvaluateTiles(const Terrain& terrain, const TileScheme& scheme,
124 const std::vector<TileKey>& keys, unsigned threads = 0);
125
126 /// Tiles of one terrain and scheme, evaluated on demand with `EvaluateTile` and kept up to
127 /// a byte budget, least recently used first out. Safe to use from several threads at once; tiles
128 /// are re-evaluated identically, so eviction never changes results.
129 class TileCache {
130 public:
131 /// A cache of the tiles of `terrain` on `scheme`, holding up to `maxBytes` bytes.
132 /// @throws std::invalid_argument for an invalid scheme or terrain, or a zero `maxBytes`.
133 TileCache(Terrain terrain, TileScheme scheme, std::size_t maxBytes = std::size_t{1} << 30);
134
135 /// A tile, evaluated on one thread when it is not held.
136 /// @throws std::invalid_argument for a level outside the scheme's; and whatever the terrain's
137 /// parts throw.
138 std::shared_ptr<const Raster<float>> Get(const TileKey& key);
139
140 /// Bytes held: four per height.
141 2 std::size_t Size() const {
142 2 return cache_.Size();
143 }
144
145 /// The byte budget given at construction.
146 2 std::size_t MaxBytes() const {
147 2 return cache_.Capacity();
148 }
149
150 /// Tiles evicted since construction.
151 2 std::size_t Evictions() const {
152 2 return cache_.Evictions();
153 }
154
155 /// The tile scheme given at construction.
156 1 const TileScheme& Scheme() const {
157 1 return scheme_;
158 }
159
160 private:
161 Terrain terrain_;
162 TileScheme scheme_;
163 LruCache<TileKey, Raster<float>, TileKeyHash> cache_;
164 };
165
166 } // namespace terraingen
167