TerrainGen coverage

terraingen/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
10 / 10
100.0%
Branches:
12 / 12
100.0%
Functions:
5 / 5, 1 excl
100.0%
util/cells.h
Line Branch Exec Source
1 /// @file
2 /// @brief Surface cells for per-cell feature generation: planar squares and cube-sphere cells.
3 #pragma once
4
5 #include "terraingen/util/geometry.h"
6 #include "terraingen/util/surface.h"
7
8 #include <array>
9 #include <compare>
10 #include <cstdint>
11 #include <vector>
12
13 namespace terraingen {
14
15 /// Integer coordinates of one cell in a grid of square cells.
16 struct CellIndex {
17 7895632 std::int32_t i = 0; ///< Column, or face * n + column on a cube sphere.
18 3926561 std::int32_t j = 0; ///< Row.
19
20 /// Orders cells by `i`, then `j`.
21
12/12
✓ Branch 0 taken 3969071 times.
✓ Branch 1 taken 3926561 times.
✓ Branch 2 taken 2768837 times.
✓ Branch 3 taken 1200234 times.
✓ Branch 5 taken 3969071 times.
✓ Branch 6 taken 3926561 times.
✓ Branch 7 taken 2841143 times.
✓ Branch 8 taken 1085418 times.
✓ Branch 9 taken 1867461 times.
✓ Branch 10 taken 973682 times.
✓ Branch 12 taken 2841143 times.
✓ Branch 13 taken 1085418 times.
 12907611 auto operator<=>(const CellIndex&) const = default;
22 };
23
24 /// Partitions a surface into cells so features can be generated per cell, each from its
25 /// own random substream, identically however a region is tiled.
26 class SurfaceCells {
27 public:
28 1417 virtual ~SurfaceCells() = default;
29
30 /// The cells that intersect `region` (surface coordinates), in a fixed order.
31 /// @param cellSize The cell side in metres.
32 /// @throws std::invalid_argument if `cellSize` is not positive and finite or `region` is empty
33 /// or not finite.
34 virtual std::vector<CellIndex> CellsCovering(const Bounds2d& region, double cellSize) const = 0;
35
36 /// The area of a cell in m^2.
37 /// @param cellSize The cell side in metres.
38 virtual double CellArea(const CellIndex& cell, double cellSize) const = 0;
39
40 /// Maps uniform `u` and `v` in [0, 1) to a point uniform over a cell, in surface coordinates;
41 /// uniform over `Sampling`'s measure where that thins.
42 /// @param cellSize The cell side in metres.
43 virtual Vec2d SamplePoint(double u, double v, const CellIndex& cell, double cellSize) const = 0;
44
45 /// How to place features in a cell uniformly by area: draw a Poisson count over `area`
46 /// m^2, place each at `SamplePoint`, and keep it with chance `Weight(point) / bound` when
47 /// `bound` is positive. Without thinning (`bound` 0) `area` is `CellArea` and every point is
48 /// kept, as on a plane or a sphere.
49 struct Sampling {
50 double area = 0.0; ///< Area in m^2 the Poisson count is drawn over, >= `CellArea`.
51 double bound = 0.0; ///< Upper bound of `Weight` over the cell; 0 when nothing is thinned.
52 };
53
54 /// The sampling of a cell, as `Sampling` describes.
55 /// @param cellSize The cell side in metres.
56 196260 virtual Sampling CellSampling(const CellIndex& cell, double cellSize) const {
57 196260 return {CellArea(cell, cellSize), 0.0};
58 }
59
60 /// The weight of a sampled point, kept with chance `Weight(point) / Sampling::bound`.
61 1 virtual double Weight(const Vec2d& /*point*/) const {
62 1 return 1.0;
63 }
64 };
65
66 /// Square cells on a plane: cell (i, j) of side L covers [i L, (i + 1) L) x
67 /// [j L, (j + 1) L).
68 class PlanarCells final : public SurfaceCells {
69 public:
70 /// The cells intersecting `region` (metres), in row-major order: increasing j, then i.
71 /// @param cellSize The cell side in metres.
72 /// @throws std::invalid_argument if `cellSize` is not positive and finite, `region` is empty or
73 /// not finite, or a cell index would overflow 32 bits.
74 std::vector<CellIndex> CellsCovering(const Bounds2d& region, double cellSize) const override;
75
76 /// `cellSize` squared, in m^2.
77 double CellArea(const CellIndex& cell, double cellSize) const override;
78
79 /// The point at fractions `u` and `v` in [0, 1) across a cell in x and y, in metres.
80 Vec2d SamplePoint(double u, double v, const CellIndex& cell, double cellSize) const override;
81 };
82
83 /// Near-square cells on a body, in longitude and latitude degrees: each face of a cube split into
84 /// n x n cells along equiangular coordinates of the direction from the centre.
85 ///
86 /// For a cell side L, n = ceil(R pi / (2 L)), with R the sphere's radius or an ellipsoid's
87 /// shortest semi-axis, so no cell is narrower than L. Cell (i, j) is column i mod n and row j of
88 /// face i / n (+x, -x, +y, -y, +z, -z). On a sphere cells are near-equal-area; on an ellipsoid
89 /// `CellArea` is each cell's true area and `CellSampling` thins points to be uniform by area.
90 class CubeSphereCells final : public SurfaceCells {
91 public:
92 /// Cells on a sphere of `radius` metres.
93 /// @throws std::invalid_argument unless `radius` is positive and finite.
94 explicit CubeSphereCells(double radius);
95
96 /// Cells on a body, a sphere or an ellipsoid.
97 /// @throws std::invalid_argument for a plane.
98 explicit CubeSphereCells(const Surface& surface);
99
100 /// Every cell reaching into a region, plus some next to them, sorted by i, then j.
101 /// @param region The region in longitude and latitude degrees; longitudes may run past
102 /// [-180, 180].
103 /// @param cellSize The cell side in metres.
104 /// @throws std::invalid_argument if `cellSize` is not positive and finite, the cells would be
105 /// too small for the sphere, or `region` is not finite or inverted.
106 std::vector<CellIndex> CellsCovering(const Bounds2d& region, double cellSize) const override;
107
108 /// The area of a cell in m^2: exact from its solid angle on a sphere, by quadrature of the area
109 /// element on an ellipsoid.
110 /// @throws std::invalid_argument as `CellsPerEdge`.
111 double CellArea(const CellIndex& cell, double cellSize) const override;
112
113 /// `CellArea` without thinning on a sphere; on an ellipsoid, the cell's solid angle times a
114 /// guaranteed bound of the area per steradian over it (from interval bounds of its directions,
115 /// capped by the bound over the whole body), thinned by `Weight`.
116 /// @throws std::invalid_argument as `CellsPerEdge`.
117 Sampling CellSampling(const CellIndex& cell, double cellSize) const override;
118
119 /// The area per steradian at a point (`Surface::AreaPerSteradian`).
120 double Weight(const Vec2d& point) const override;
121
122 /// Maps uniform `u` and `v` in [0, 1) to a point uniform in solid angle over a cell, as
123 /// longitude in (-180, 180] and latitude, in degrees.
124 /// @throws std::invalid_argument as `CellsPerEdge`.
125 Vec2d SamplePoint(double u, double v, const CellIndex& cell, double cellSize) const override;
126
127 /// The cell holding a point given in degrees.
128 /// @param cellSize The cell side in metres.
129 /// @throws std::invalid_argument as `CellsPerEdge`.
130 CellIndex CellOf(double lonDeg, double latDeg, double cellSize) const;
131
132 /// A cell and the cells up to `rings` steps from it along its face's rows and columns,
133 /// continuing onto neighbouring faces past an edge, without repeats, sorted by i, then j.
134 /// @param cellSize The cell side in metres.
135 /// @throws std::invalid_argument as `CellsPerEdge`.
136 std::vector<CellIndex> Neighbours(const CellIndex& cell, double cellSize, int rings) const;
137
138 /// The unit direction of a face at equiangular coordinates.
139 /// @param face The face, 0 to 5: +x, -x, +y, -y, +z, -z.
140 /// @param alpha Angle from the face's centre along its first axis, radians in [-pi/4, pi/4].
141 /// @param beta Angle from the face's centre along its second axis, radians in [-pi/4, pi/4].
142 static Vec3d Direction(int face, double alpha, double beta);
143
144 /// The number of cells along each edge of a face, n = ceil(R pi / (2 `cellSize`)).
145 /// @param cellSize The cell side in metres.
146 /// @throws std::invalid_argument if `cellSize` is not positive and finite or the cells would be
147 /// too small for the sphere.
148 std::int32_t CellsPerEdge(double cellSize) const;
149
150 /// The radius in metres the cells are sized by: the sphere's, or an ellipsoid's shortest.
151 10 double Radius() const {
152 10 return radius_;
153 }
154
155 private:
156 /// The gnomonic bounds a1, a2, b1, b2 of a cell on its face.
157 std::array<double, 4> Bounds(const CellIndex& cell, double cellSize) const;
158
159 /// An upper bound of `Weight` over the gnomonic rectangle [a1, a2] x [b1, b2] of `face`,
160 /// from interval bounds of the direction's squared components.
161 double WeightBound(std::size_t face, double a1, double a2, double b1, double b2) const;
162
163 double radius_;
164 Surface surface_;
165 double weightCap_ = 0.0; ///< Bound of `Weight` over the whole ellipsoid; 0 on a sphere.
166 };
167
168 } // namespace terraingen
169