TerrainGen coverage

terraingen/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
114 / 115
99.1%
Branches:
69 / 70
98.6%
Functions:
9 / 9
100.0%
mesh/shape_model.cpp
Line Branch Exec Source
1 #include "terraingen/mesh/shape_model.h"
2
3 #include "terraingen/util/cube_faces.h"
4 #include "terraingen/util/log.h"
5
6 #include <algorithm>
7 #include <array>
8 #include <cmath>
9 #include <cstdint>
10 #include <numbers>
11 #include <optional>
12 #include <stdexcept>
13 #include <vector>
14
15 namespace terraingen {
16
17 namespace {
18
19 constexpr double kQuarter = std::numbers::pi / 4.0;
20
21 /// The patch coordinate, in [0, n], of gnomonic coordinate `g` on a face of `n` patches per edge.
22 1751460 double PatchCoordinate(double g, std::size_t n) {
23 1751460 return (std::atan(g) + kQuarter) / (2.0 * kQuarter) * static_cast<double>(n);
24 }
25
26 /// The triangles near each patch of a cube grid of directions, by the gnomonic projections of
27 /// their corners, so each ray tests only the triangles around it.
28 class TriangleBins {
29 public:
30
1/1
✓ Branch 1 taken 8 times.
 16 TriangleBins(const TriangleMesh& mesh, std::size_t n) : n_(n), bins_(6 * n * n) {
31
2/2
✓ Branch 1 taken 97616 times.
✓ Branch 2 taken 8 times.
 97624 for (std::size_t t = 0; t < mesh.triangles.size(); ++t) {
32 97616 std::array<Vec3d, 3> corner{};
33
2/2
✓ Branch 0 taken 292848 times.
✓ Branch 1 taken 97616 times.
 390464 for (std::size_t k = 0; k < 3; ++k) {
34 292848 corner[k] = mesh.positions[mesh.triangles[t][k]];
35 }
36
2/2
✓ Branch 0 taken 585696 times.
✓ Branch 1 taken 97616 times.
 683312 for (std::size_t face = 0; face < 6; ++face) {
37
1/1
✓ Branch 1 taken 585696 times.
 585696 Insert(static_cast<std::uint32_t>(t), face, corner);
38 }
39 }
40 8 }
41
42 /// The triangles in the patches around patch coordinates (`s`, `t`) of `face`.
43 6902 void Near(std::size_t face, double s, double t, std::vector<std::uint32_t>& out) const {
44 6902 out.clear();
45 13804 const auto range = [&](double x) {
46 13804 const auto k = static_cast<long long>(std::floor(x));
47 13804 return std::array<std::size_t, 2>{Clamp(k - 1), Clamp(k)};
48 6902 };
49
1/1
✓ Branch 1 taken 6902 times.
 6902 const auto [i0, i1] = range(s);
50
1/1
✓ Branch 1 taken 6902 times.
 6902 const auto [j0, j1] = range(t);
51
2/2
✓ Branch 0 taken 12630 times.
✓ Branch 1 taken 6902 times.
 19532 for (std::size_t j = j0; j <= j1; ++j) {
52
2/2
✓ Branch 0 taken 24024 times.
✓ Branch 1 taken 12630 times.
 36654 for (std::size_t i = i0; i <= i1; ++i) {
53 24024 const auto& bin = bins_[(face * n_ + j) * n_ + i];
54
1/1
✓ Branch 5 taken 24024 times.
 24024 out.insert(out.end(), bin.begin(), bin.end());
55 }
56 }
57
1/1
✓ Branch 3 taken 6902 times.
 6902 std::sort(out.begin(), out.end());
58
2/2
✓ Branch 5 taken 6902 times.
✓ Branch 9 taken 6902 times.
 6902 out.erase(std::unique(out.begin(), out.end()), out.end());
59 6902 }
60
61 private:
62 1204568 std::size_t Clamp(long long k) const {
63 return static_cast<std::size_t>(
64
1/1
✓ Branch 1 taken 1204568 times.
 1204568 std::clamp<long long>(k, 0, static_cast<long long>(n_) - 1));
65 }
66
67 585696 void Insert(std::uint32_t triangle, std::size_t face, const std::array<Vec3d, 3>& corner) {
68 585696 const detail::CubeFace& f = detail::kCubeFaces[face];
69 585696 double sLo = static_cast<double>(n_);
70 585696 double sHi = 0.0;
71 585696 double tLo = static_cast<double>(n_);
72 585696 double tHi = 0.0;
73 585696 bool behind = false;
74 585696 bool front = false;
75
2/2
✓ Branch 2 taken 1757088 times.
✓ Branch 3 taken 585696 times.
 2342784 for (const Vec3d& p : corner) {
76 1757088 const double along = Dot(p, f.normal);
77
2/2
✓ Branch 0 taken 888260 times.
✓ Branch 1 taken 868828 times.
 1757088 if (along <= 0.0) {
78 888260 behind = true;
79 888260 continue;
80 }
81 868828 front = true;
82 868828 const double s = PatchCoordinate(Dot(p, f.u) / along, n_);
83 868828 const double t = PatchCoordinate(Dot(p, f.v) / along, n_);
84 868828 sLo = std::min(sLo, s);
85 868828 sHi = std::max(sHi, s);
86 868828 tLo = std::min(tLo, t);
87 868828 tHi = std::max(tHi, t);
88 }
89
2/2
✓ Branch 0 taken 291456 times.
✓ Branch 1 taken 294240 times.
 585696 if (!front) {
90 291456 return;
91 }
92
2/2
✓ Branch 0 taken 9236 times.
✓ Branch 1 taken 285004 times.
 294240 if (behind) {
93 9236 sLo = 0.0;
94 9236 tLo = 0.0;
95 9236 sHi = static_cast<double>(n_);
96 9236 tHi = static_cast<double>(n_);
97 }
98
1/1
✓ Branch 1 taken 294240 times.
 294240 const std::size_t i0 = Clamp(static_cast<long long>(std::floor(sLo)) - 1);
99
1/1
✓ Branch 1 taken 294240 times.
 294240 const std::size_t i1 = Clamp(static_cast<long long>(std::floor(sHi)) + 1);
100
1/1
✓ Branch 1 taken 294240 times.
 294240 const std::size_t j0 = Clamp(static_cast<long long>(std::floor(tLo)) - 1);
101
1/1
✓ Branch 1 taken 294240 times.
 294240 const std::size_t j1 = Clamp(static_cast<long long>(std::floor(tHi)) + 1);
102
2/2
✓ Branch 0 taken 861566 times.
✓ Branch 1 taken 294240 times.
 1155806 for (std::size_t j = j0; j <= j1; ++j) {
103
2/2
✓ Branch 0 taken 4819654 times.
✓ Branch 1 taken 861566 times.
 5681220 for (std::size_t i = i0; i <= i1; ++i) {
104
1/1
✓ Branch 2 taken 4819654 times.
 4819654 bins_[(face * n_ + j) * n_ + i].push_back(triangle);
105 }
106 }
107 }
108
109 std::size_t n_;
110 std::vector<std::vector<std::uint32_t>> bins_;
111 };
112
113 /// The distance along unit `direction` from the origin at which the ray crosses triangle
114 /// (`a`, `b`, `c`), with a small tolerance at its edges; empty if it misses.
115 6427176 std::optional<double> Crossing(const Vec3d& direction, const Vec3d& a, const Vec3d& b,
116 const Vec3d& c) {
117 6427176 constexpr double kEdge = 1e-9;
118 6427176 const Vec3d e1 = b - a;
119 6427176 const Vec3d e2 = c - a;
120 6427176 const Vec3d p = Cross(direction, e2);
121 6427176 const double det = Dot(e1, p);
122
2/2
✓ Branch 0 taken 2688 times.
✓ Branch 1 taken 6424488 times.
 6427176 if (det == 0.0) {
123 2688 return std::nullopt;
124 }
125 6424488 const double inverse = 1.0 / det;
126 6424488 const Vec3d s{-a.x, -a.y, -a.z};
127 6424488 const double u = Dot(s, p) * inverse;
128
4/4
✓ Branch 0 taken 3333572 times.
✓ Branch 1 taken 3090916 times.
✓ Branch 2 taken 3148810 times.
✓ Branch 3 taken 184762 times.
 6424488 if (u < -kEdge || u > 1.0 + kEdge) {
129 6239726 return std::nullopt;
130 }
131 184762 const Vec3d q = Cross(s, e1);
132 184762 const double v = Dot(direction, q) * inverse;
133
4/4
✓ Branch 0 taken 96443 times.
✓ Branch 1 taken 88319 times.
✓ Branch 2 taken 87951 times.
✓ Branch 3 taken 8492 times.
 184762 if (v < -kEdge || u + v > 1.0 + kEdge) {
134 176270 return std::nullopt;
135 }
136 8492 const double t = Dot(e2, q) * inverse;
137
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8492 times.
 8492 if (!(t > 0.0)) {
138 ✗ return std::nullopt;
139 }
140 8492 return t;
141 }
142
143 } // namespace
144
145 11 RadialShape ShapeModelFromMesh(const TriangleMesh& mesh, std::size_t q) {
146
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 9 times.
 11 if (q == 0) {
147
1/1
✓ Branch 2 taken 2 times.
 2 throw std::invalid_argument("A radial shape needs Q > 0");
148 }
149
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 8 times.
 9 if (mesh.triangles.empty()) {
150
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("A shape model mesh needs triangles");
151 }
152
1/1
✓ Branch 1 taken 8 times.
 8 const TriangleBins bins(mesh, q);
153 8 std::vector<std::uint32_t> near;
154 8 std::size_t folded = 0;
155 2 const RadialShape shape = RadialShape::Sample(q, [&](const Vec3d& direction) {
156 6902 const std::size_t face = detail::CubeFaceOf(detail::kCubeFaces, direction);
157 6902 const detail::CubeFace& f = detail::kCubeFaces[face];
158 6902 const double along = Dot(direction, f.normal);
159
1/1
✓ Branch 4 taken 6902 times.
 6902 bins.Near(face, PatchCoordinate(Dot(direction, f.u) / along, q),
160 6902 PatchCoordinate(Dot(direction, f.v) / along, q), near);
161 6902 double outer = 0.0;
162 6902 double inner = INFINITY;
163
2/2
✓ Branch 5 taken 6427176 times.
✓ Branch 6 taken 6902 times.
 6434078 for (const std::uint32_t t : near) {
164 6427176 const auto& tri = mesh.triangles[t];
165 6427176 const std::optional<double> hit = Crossing(
166 6427176 direction, mesh.positions[tri[0]], mesh.positions[tri[1]], mesh.positions[tri[2]]);
167
2/2
✓ Branch 1 taken 8492 times.
✓ Branch 2 taken 6418684 times.
 6427176 if (hit) {
168 8492 outer = std::max(outer, *hit);
169 8492 inner = std::min(inner, *hit);
170 }
171 }
172
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 6900 times.
 6902 if (outer == 0.0) {
173 throw std::runtime_error(
174
1/1
✓ Branch 2 taken 2 times.
 2 "A ray from the shape model's origin misses it: the mesh must enclose its origin");
175 }
176
2/2
✓ Branch 0 taken 150 times.
✓ Branch 1 taken 6750 times.
 6900 if (outer - inner > 1e-6 * outer) {
177 150 ++folded;
178 }
179 6900 return outer;
180
2/2
✓ Branch 1 taken 8 times.
✓ Branch 4 taken 6 times.
 10 });
181
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 5 times.
 6 if (folded > 0) {
182
1/1
✓ Branch 4 taken 1 time.
 1 LogWarning("mesh", folded, " of ", shape.Radii().size(),
183 " rays from the origin cross the shape model more than once; it is not "
184 "star-shaped from its origin, so its outermost surface is kept");
185 }
186 12 return shape;
187 10 }
188
189 } // namespace terraingen
190