TerrainGen coverage

terraingen/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
148 / 148
100.0%
Branches:
95 / 96
99.0%
Functions:
17 / 17
100.0%
mesh/mesh.cpp
Line Branch Exec Source
1 #include "terraingen/mesh/mesh.h"
2
3 #include "terraingen/util/checks.h"
4
5 #include <cmath>
6 #include <cstddef>
7 #include <map>
8 #include <stdexcept>
9 #include <tuple>
10 #include <utility>
11
12 namespace terraingen {
13
14 11765 Box3d Bounds(const TriangleMesh& mesh) {
15
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 11764 times.
 11765 if (mesh.positions.empty()) {
16
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("An empty mesh has no bounds");
17 }
18 11764 Box3d box{mesh.positions.front(), mesh.positions.front()};
19
2/2
✓ Branch 4 taken 4672265 times.
✓ Branch 5 taken 11764 times.
 4684029 for (const Vec3d& p : mesh.positions) {
20 4672265 box.min = {std::fmin(box.min.x, p.x), std::fmin(box.min.y, p.y), std::fmin(box.min.z, p.z)};
21 4672265 box.max = {std::fmax(box.max.x, p.x), std::fmax(box.max.y, p.y), std::fmax(box.max.z, p.z)};
22 }
23 11764 return box;
24 }
25
26 namespace {
27
28 /// Twice the area-weighted normal of triangle `t`.
29 680417 Vec3d AreaNormal(const TriangleMesh& mesh, const std::array<std::uint32_t, 3>& t) {
30 680417 const Vec3d& a = mesh.positions[t[0]];
31 680417 return Cross(mesh.positions[t[1]] - a, mesh.positions[t[2]] - a);
32 }
33
34 } // namespace
35
36 1348 void ValidateMesh(const TriangleMesh& mesh) {
37
2/2
✓ Branch 5 taken 1729193 times.
✓ Branch 6 taken 1343 times.
 1730536 for (const auto& t : mesh.triangles) {
38
2/2
✓ Branch 2 taken 5187579 times.
✓ Branch 3 taken 1729188 times.
 6916767 for (const std::uint32_t v : t) {
39
2/2
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 5187574 times.
 5187579 if (v >= mesh.positions.size()) {
40
1/1
✓ Branch 2 taken 5 times.
 5 throw std::invalid_argument("A triangle indexes past the mesh's vertices");
41 }
42 }
43 }
44 1343 }
45
46 184 double Volume(const TriangleMesh& mesh) {
47 184 ValidateMesh(mesh);
48 183 double sum = 0.0;
49
2/2
✓ Branch 4 taken 179888 times.
✓ Branch 5 taken 183 times.
 180071 for (const auto& t : mesh.triangles) {
50 179888 sum += Dot(mesh.positions[t[0]], Cross(mesh.positions[t[1]], mesh.positions[t[2]]));
51 }
52 183 return sum / 6.0;
53 }
54
55 4 double SurfaceArea(const TriangleMesh& mesh) {
56 4 ValidateMesh(mesh);
57 3 double sum = 0.0;
58
2/2
✓ Branch 4 taken 20504 times.
✓ Branch 5 taken 3 times.
 20507 for (const auto& t : mesh.triangles) {
59 20504 sum += Length(AreaNormal(mesh, t));
60 }
61 3 return 0.5 * sum;
62 }
63
64 10 std::vector<Vec3d> VertexNormals(const TriangleMesh& mesh) {
65 10 ValidateMesh(mesh);
66
1/1
✓ Branch 2 taken 9 times.
 9 std::vector<Vec3d> normals(mesh.positions.size());
67
2/2
✓ Branch 5 taken 186131 times.
✓ Branch 6 taken 9 times.
 186140 for (const auto& t : mesh.triangles) {
68 186131 const Vec3d n = AreaNormal(mesh, t);
69
2/2
✓ Branch 2 taken 558393 times.
✓ Branch 3 taken 186131 times.
 744524 for (const std::uint32_t v : t) {
70 558393 normals[v] = normals[v] + n;
71 }
72 }
73
2/2
✓ Branch 5 taken 94100 times.
✓ Branch 6 taken 9 times.
 94109 for (Vec3d& n : normals) {
74 94100 n = Normalized(n);
75 }
76 9 return normals;
77 }
78
79 417 ShadedMesh WithCreases(const TriangleMesh& mesh, double creaseAngle) {
80
1/1
✓ Branch 2 taken 416 times.
 417 RequireNonNegative(creaseAngle, "Crease angle");
81
1/1
✓ Branch 1 taken 415 times.
 416 ValidateMesh(mesh);
82 415 const double cosine = std::cos(creaseAngle);
83 415 std::vector<Vec3d> areaNormals;
84 415 std::vector<Vec3d> unitNormals;
85
1/1
✓ Branch 2 taken 415 times.
 415 std::vector<std::vector<std::size_t>> around(mesh.positions.size());
86
2/2
✓ Branch 1 taken 473782 times.
✓ Branch 2 taken 415 times.
 474197 for (std::size_t f = 0; f < mesh.triangles.size(); ++f) {
87
1/1
✓ Branch 3 taken 473782 times.
 473782 areaNormals.push_back(AreaNormal(mesh, mesh.triangles[f]));
88
1/1
✓ Branch 3 taken 473782 times.
 473782 unitNormals.push_back(Normalized(areaNormals.back()));
89
2/2
✓ Branch 3 taken 1421346 times.
✓ Branch 4 taken 473782 times.
 1895128 for (const std::uint32_t v : mesh.triangles[f]) {
90
1/1
✓ Branch 2 taken 1421346 times.
 1421346 around[v].push_back(f);
91 }
92 }
93 415 ShadedMesh shaded;
94 415 std::map<std::tuple<std::uint32_t, double, double, double>, std::uint32_t> made;
95
2/2
✓ Branch 1 taken 473782 times.
✓ Branch 2 taken 415 times.
 474197 for (std::size_t f = 0; f < mesh.triangles.size(); ++f) {
96 473782 std::array<std::uint32_t, 3> triangle{};
97
2/2
✓ Branch 0 taken 1421346 times.
✓ Branch 1 taken 473782 times.
 1895128 for (std::size_t k = 0; k < 3; ++k) {
98 1421346 const std::uint32_t v = mesh.triangles[f][k];
99 1421346 Vec3d sum{};
100
2/2
✓ Branch 6 taken 8448762 times.
✓ Branch 7 taken 1421346 times.
 9870108 for (const std::size_t g : around[v]) {
101
2/2
✓ Branch 3 taken 8342414 times.
✓ Branch 4 taken 106348 times.
 8448762 if (Dot(unitNormals[f], unitNormals[g]) >= cosine) {
102 8342414 sum = sum + areaNormals[g];
103 }
104 }
105 1421346 const Vec3d normal = Normalized(sum);
106
1/1
✓ Branch 1 taken 1421346 times.
 1421346 const auto key = std::make_tuple(v, normal.x, normal.y, normal.z);
107
1/1
✓ Branch 1 taken 1421346 times.
 1421346 const auto found = made.find(key);
108
2/2
✓ Branch 2 taken 1162439 times.
✓ Branch 3 taken 258907 times.
 1421346 if (found != made.end()) {
109 1162439 triangle[k] = found->second;
110 1162439 continue;
111 }
112 258907 const auto index = static_cast<std::uint32_t>(shaded.mesh.positions.size());
113
1/1
✓ Branch 2 taken 258907 times.
 258907 shaded.mesh.positions.push_back(mesh.positions[v]);
114
1/1
✓ Branch 1 taken 258907 times.
 258907 shaded.normals.push_back(normal);
115
1/1
✓ Branch 1 taken 258907 times.
 258907 made.emplace(key, index);
116 258907 triangle[k] = index;
117 }
118
1/1
✓ Branch 1 taken 473782 times.
 473782 shaded.mesh.triangles.push_back(triangle);
119 }
120 830 return shaded;
121 415 }
122
123 21911773 Vec3d RigidTransform::Apply(const Vec3d& p) const {
124 21911773 const auto& r = rotation;
125 21911773 return {r[0] * p.x + r[1] * p.y + r[2] * p.z + translation.x,
126 21911773 r[3] * p.x + r[4] * p.y + r[5] * p.z + translation.y,
127 43823546 r[6] * p.x + r[7] * p.y + r[8] * p.z + translation.z};
128 }
129
130 33345 RigidTransform RigidTransform::After(const RigidTransform& first) const {
131 33345 RigidTransform combined;
132
2/2
✓ Branch 0 taken 100035 times.
✓ Branch 1 taken 33345 times.
 133380 for (std::size_t i = 0; i < 3; ++i) {
133
2/2
✓ Branch 0 taken 300105 times.
✓ Branch 1 taken 100035 times.
 400140 for (std::size_t j = 0; j < 3; ++j) {
134 300105 double sum = 0.0;
135
2/2
✓ Branch 0 taken 900315 times.
✓ Branch 1 taken 300105 times.
 1200420 for (std::size_t k = 0; k < 3; ++k) {
136 900315 sum += rotation[3 * i + k] * first.rotation[3 * k + j];
137 }
138 300105 combined.rotation[3 * i + j] = sum;
139 }
140 }
141 33345 combined.translation = Apply(first.translation);
142 33345 return combined;
143 }
144
145 11154 RigidTransform RigidTransform::RotationX(double angle) {
146 11154 const double c = std::cos(angle);
147 11154 const double s = std::sin(angle);
148 11154 return {{1.0, 0.0, 0.0, 0.0, c, -s, 0.0, s, c}, {}};
149 }
150
151 45 RigidTransform RigidTransform::RotationY(double angle) {
152 45 const double c = std::cos(angle);
153 45 const double s = std::sin(angle);
154 45 return {{c, 0.0, s, 0.0, 1.0, 0.0, -s, 0.0, c}, {}};
155 }
156
157 11092 RigidTransform RigidTransform::RotationZ(double angle) {
158 11092 const double c = std::cos(angle);
159 11092 const double s = std::sin(angle);
160 11092 return {{c, -s, 0.0, s, c, 0.0, 0.0, 0.0, 1.0}, {}};
161 }
162
163 6 RigidTransform RigidTransform::Translation(const Vec3d& offset) {
164 6 RigidTransform transform;
165 6 transform.translation = offset;
166 6 return transform;
167 }
168
169 500 void RequireRotation(const std::array<double, 9>& r) {
170
2/2
✓ Branch 0 taken 1498 times.
✓ Branch 1 taken 499 times.
 1997 for (std::size_t i = 0; i < 3; ++i) {
171
2/2
✓ Branch 0 taken 4492 times.
✓ Branch 1 taken 1497 times.
 5989 for (std::size_t j = 0; j < 3; ++j) {
172 4492 double dot = 0.0;
173
2/2
✓ Branch 0 taken 13476 times.
✓ Branch 1 taken 4492 times.
 17968 for (std::size_t k = 0; k < 3; ++k) {
174 13476 dot += r[3 * i + k] * r[3 * j + k];
175 }
176
4/4
✓ Branch 0 taken 1498 times.
✓ Branch 1 taken 2994 times.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 4491 times.
 4492 if (std::fabs(dot - (i == j ? 1.0 : 0.0)) > 1e-9) {
177
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("A pose must be a rotation");
178 }
179 }
180 }
181 499 const double det = r[0] * (r[4] * r[8] - r[5] * r[7]) - r[1] * (r[3] * r[8] - r[5] * r[6]) +
182 499 r[2] * (r[3] * r[7] - r[4] * r[6]);
183
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 497 times.
 499 if (det < 0.0) {
184
1/1
✓ Branch 2 taken 2 times.
 2 throw std::invalid_argument("A pose must be a rotation, not a reflection");
185 }
186 497 }
187
188 365 std::array<double, 4> RotationQuaternion(const std::array<double, 9>& r) {
189 365 const double trace = r[0] + r[4] + r[8];
190
2/2
✓ Branch 0 taken 273 times.
✓ Branch 1 taken 92 times.
 365 if (trace > 0.0) {
191 273 const double s = 2.0 * std::sqrt(1.0 + trace);
192 273 return {(r[7] - r[5]) / s, (r[2] - r[6]) / s, (r[3] - r[1]) / s, 0.25 * s};
193 }
194
6/6
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 89 times.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 1 time.
✓ Branch 8 taken 2 times.
✓ Branch 9 taken 90 times.
 92 if (r[0] > r[4] && r[0] > r[8]) {
195 2 const double s = 2.0 * std::sqrt(1.0 + r[0] - r[4] - r[8]);
196 2 return {0.25 * s, (r[1] + r[3]) / s, (r[2] + r[6]) / s, (r[7] - r[5]) / s};
197 }
198
2/2
✓ Branch 2 taken 87 times.
✓ Branch 3 taken 3 times.
 90 if (r[4] > r[8]) {
199 87 const double s = 2.0 * std::sqrt(1.0 + r[4] - r[0] - r[8]);
200 87 return {(r[1] + r[3]) / s, 0.25 * s, (r[5] + r[7]) / s, (r[2] - r[6]) / s};
201 }
202 3 const double s = 2.0 * std::sqrt(1.0 + r[8] - r[0] - r[4]);
203 3 return {(r[2] + r[6]) / s, (r[5] + r[7]) / s, 0.25 * s, (r[3] - r[1]) / s};
204 }
205
206 2 TriangleMesh Transformed(const TriangleMesh& mesh, const RigidTransform& transform) {
207 2 TriangleMesh moved = mesh;
208
2/2
✓ Branch 5 taken 16 times.
✓ Branch 6 taken 2 times.
 18 for (Vec3d& p : moved.positions) {
209 16 p = transform.Apply(p);
210 }
211 2 return moved;
212 }
213
214 3334 TriangleMesh Scaled(const TriangleMesh& mesh, const Vec3d& scale) {
215
2/2
✓ Branch 2 taken 10000 times.
✓ Branch 3 taken 3333 times.
 13333 for (const double s : {scale.x, scale.y, scale.z}) {
216
5/6
✓ Branch 1 taken 10000 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 time.
✓ Branch 4 taken 9999 times.
✓ Branch 5 taken 1 time.
✓ Branch 6 taken 9999 times.
 10000 if (!(std::isfinite(s) && s != 0.0)) {
217
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("Scale factors must be finite and not zero");
218 }
219 }
220 3333 TriangleMesh scaled = mesh;
221
2/2
✓ Branch 4 taken 769398 times.
✓ Branch 5 taken 3333 times.
 772731 for (Vec3d& p : scaled.positions) {
222 769398 p = {p.x * scale.x, p.y * scale.y, p.z * scale.z};
223 }
224
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 3332 times.
 3333 if (scale.x * scale.y * scale.z < 0.0) {
225
2/2
✓ Branch 5 taken 12 times.
✓ Branch 6 taken 1 time.
 13 for (auto& t : scaled.triangles) {
226 12 std::swap(t[1], t[2]);
227 }
228 }
229 3333 return scaled;
230 }
231
232 } // namespace terraingen
233