TerrainGen coverage

terraingen/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
106 / 108
98.1%
Branches:
83 / 85
97.6%
Functions:
11 / 11
100.0%
mesh/polyhedra.cpp
Line Branch Exec Source
1 #include "terraingen/mesh/polyhedra.h"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <initializer_list>
6 #include <limits>
7 #include <map>
8 #include <stdexcept>
9 #include <utility>
10
11 namespace terraingen {
12
13 namespace {
14
15 /// Each triangle turned to face away from the origin, which lies inside every base solid.
16 3372 TriangleMesh Outward(TriangleMesh mesh) {
17
2/2
✓ Branch 5 taken 49494 times.
✓ Branch 6 taken 3372 times.
 52866 for (auto& t : mesh.triangles) {
18 49494 const Vec3d& a = mesh.positions[t[0]];
19 49494 const Vec3d normal = Cross(mesh.positions[t[1]] - a, mesh.positions[t[2]] - a);
20
2/2
✓ Branch 7 taken 10541 times.
✓ Branch 8 taken 38953 times.
 49494 if (Dot(normal, a + mesh.positions[t[1]] + mesh.positions[t[2]]) < 0.0) {
21 10541 std::swap(t[1], t[2]);
22 }
23 }
24 3372 return mesh;
25 }
26
27 /// Two triangles for the quadrilateral a, b, c, d, in order around it.
28 10532 void AddQuad(TriangleMesh& mesh, std::uint32_t a, std::uint32_t b, std::uint32_t c,
29 std::uint32_t d) {
30
1/1
✓ Branch 1 taken 10532 times.
 10532 mesh.triangles.push_back({a, b, c});
31
1/1
✓ Branch 1 taken 10532 times.
 10532 mesh.triangles.push_back({a, c, d});
32 10532 }
33
34 1367 TriangleMesh IcosahedronMesh() {
35 1367 const double t = (1.0 + std::sqrt(5.0)) / 2.0;
36 1367 TriangleMesh mesh;
37 1367 for (const Vec3d& v : std::initializer_list<Vec3d>{{-1, t, 0},
38 {1, t, 0},
39 {-1, -t, 0},
40 {1, -t, 0},
41 {0, -1, t},
42 {0, 1, t},
43 {0, -1, -t},
44 {0, 1, -t},
45 {t, 0, -1},
46 {t, 0, 1},
47 {-t, 0, -1},
48
2/2
✓ Branch 2 taken 16404 times.
✓ Branch 3 taken 1367 times.
 19138 {-t, 0, 1}}) {
49
1/1
✓ Branch 2 taken 16404 times.
 16404 mesh.positions.push_back(Normalized(v));
50 }
51 ✗ mesh.triangles = {{0, 11, 5}, {0, 5, 1}, {0, 1, 7}, {0, 7, 10}, {0, 10, 11},
52 {1, 5, 9}, {5, 11, 4}, {11, 10, 2}, {10, 7, 6}, {7, 1, 8},
53 {3, 9, 4}, {3, 4, 2}, {3, 2, 6}, {3, 6, 8}, {3, 8, 9},
54
1/1
✓ Branch 1 taken 1367 times.
 1367 {4, 9, 5}, {2, 4, 11}, {6, 2, 10}, {8, 6, 7}, {9, 8, 1}};
55 1367 return mesh;
56 }
57
58 1666 TriangleMesh CubeMesh() {
59 1666 TriangleMesh mesh;
60
2/2
✓ Branch 0 taken 13328 times.
✓ Branch 1 taken 1666 times.
 14994 for (int i = 0; i < 8; ++i) {
61
1/1
✓ Branch 1 taken 13328 times.
 13328 mesh.positions.push_back(
62
6/6
✓ Branch 0 taken 6664 times.
✓ Branch 1 taken 6664 times.
✓ Branch 2 taken 6664 times.
✓ Branch 3 taken 6664 times.
✓ Branch 4 taken 6664 times.
✓ Branch 5 taken 6664 times.
 13328 {(i & 1) != 0 ? 1.0 : -1.0, (i & 2) != 0 ? 1.0 : -1.0, (i & 4) != 0 ? 1.0 : -1.0});
63 }
64
1/1
✓ Branch 1 taken 1666 times.
 1666 AddQuad(mesh, 0, 1, 3, 2);
65
1/1
✓ Branch 1 taken 1666 times.
 1666 AddQuad(mesh, 4, 5, 7, 6);
66
1/1
✓ Branch 1 taken 1666 times.
 1666 AddQuad(mesh, 0, 1, 5, 4);
67
1/1
✓ Branch 1 taken 1666 times.
 1666 AddQuad(mesh, 2, 3, 7, 6);
68
1/1
✓ Branch 1 taken 1666 times.
 1666 AddQuad(mesh, 0, 2, 6, 4);
69
1/1
✓ Branch 1 taken 1666 times.
 1666 AddQuad(mesh, 1, 3, 7, 5);
70 1666 return mesh;
71 }
72
73 137 TriangleMesh PyramidMesh() {
74 137 TriangleMesh mesh;
75
1/1
✓ Branch 1 taken 137 times.
 137 mesh.positions = {{-1, -1, -1}, {1, -1, -1}, {1, 1, -1}, {-1, 1, -1}, {0, 0, 1}};
76
1/1
✓ Branch 1 taken 137 times.
 137 AddQuad(mesh, 0, 1, 2, 3);
77
2/2
✓ Branch 0 taken 548 times.
✓ Branch 1 taken 137 times.
 685 for (std::uint32_t i = 0; i < 4; ++i) {
78
1/1
✓ Branch 1 taken 548 times.
 548 mesh.triangles.push_back({i, (i + 1) % 4, 4});
79 }
80 137 return mesh;
81 }
82
83 133 TriangleMesh PrismMesh() {
84 133 TriangleMesh mesh;
85
2/2
✓ Branch 2 taken 266 times.
✓ Branch 3 taken 133 times.
 399 for (const double x : {-1.0, 1.0}) {
86
1/1
✓ Branch 1 taken 266 times.
 266 mesh.positions.push_back({x, -1, -1});
87
1/1
✓ Branch 1 taken 266 times.
 266 mesh.positions.push_back({x, 1, -1});
88
1/1
✓ Branch 1 taken 266 times.
 266 mesh.positions.push_back({x, 0, 1});
89 }
90
1/1
✓ Branch 1 taken 133 times.
 133 mesh.triangles = {{0, 1, 2}, {3, 4, 5}};
91
2/2
✓ Branch 0 taken 399 times.
✓ Branch 1 taken 133 times.
 532 for (std::uint32_t i = 0; i < 3; ++i) {
92 399 const std::uint32_t j = (i + 1) % 3;
93
1/1
✓ Branch 1 taken 399 times.
 399 AddQuad(mesh, i, j, j + 3, i + 3);
94 }
95 133 return mesh;
96 }
97
98 69 TriangleMesh TetrahedronMesh() {
99 69 TriangleMesh mesh;
100
1/1
✓ Branch 1 taken 69 times.
 69 mesh.positions = {{1, 1, 1}, {1, -1, -1}, {-1, 1, -1}, {-1, -1, 1}};
101
1/1
✓ Branch 1 taken 69 times.
 69 mesh.triangles = {{0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}};
102 69 return mesh;
103 }
104
105 } // namespace
106
107 3373 TriangleMesh BaseSolidMesh(BaseSolid solid) {
108
6/6
✓ Branch 0 taken 1367 times.
✓ Branch 1 taken 1666 times.
✓ Branch 2 taken 137 times.
✓ Branch 3 taken 133 times.
✓ Branch 4 taken 69 times.
✓ Branch 5 taken 1 time.
 3373 switch (solid) {
109 1367 case BaseSolid::Icosahedron:
110
1/1
✓ Branch 1 taken 1367 times.
 1367 return Outward(IcosahedronMesh());
111 1666 case BaseSolid::Cube:
112
1/1
✓ Branch 1 taken 1666 times.
 1666 return Outward(CubeMesh());
113 137 case BaseSolid::Pyramid:
114
1/1
✓ Branch 1 taken 137 times.
 137 return Outward(PyramidMesh());
115 133 case BaseSolid::Prism:
116
1/1
✓ Branch 1 taken 133 times.
 133 return Outward(PrismMesh());
117 69 case BaseSolid::Tetrahedron:
118
1/1
✓ Branch 1 taken 69 times.
 69 return Outward(TetrahedronMesh());
119 }
120
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("Unknown base solid");
121 }
122
123 3348 TriangleMesh Subdivide(const TriangleMesh& mesh, int levels, bool onUnitSphere) {
124
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 3347 times.
 3348 if (levels < 0) {
125
1/1
✓ Branch 2 taken 1 time.
 1 throw std::invalid_argument("Subdivision levels must not be negative");
126 }
127 3347 TriangleMesh result = mesh;
128
2/2
✓ Branch 0 taken 5835 times.
✓ Branch 1 taken 3347 times.
 9182 for (int level = 0; level < levels; ++level) {
129 5835 const double vertices = static_cast<double>(result.positions.size()) +
130 5835 1.5 * static_cast<double>(result.triangles.size());
131
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5835 times.
 5835 if (vertices > static_cast<double>(std::numeric_limits<std::uint32_t>::max())) {
132
0/1
✗ Branch 2 not taken.
 ✗ throw std::invalid_argument("Subdivision would exceed 2^32 vertices");
133 }
134 5835 std::map<std::pair<std::uint32_t, std::uint32_t>, std::uint32_t> midpoints;
135 1524936 const auto midpoint = [&](std::uint32_t a, std::uint32_t b) {
136 1524936 const auto key = std::minmax(a, b);
137
1/1
✓ Branch 2 taken 1524936 times.
 1524936 const auto found = midpoints.find(key);
138
2/2
✓ Branch 2 taken 762468 times.
✓ Branch 3 taken 762468 times.
 1524936 if (found != midpoints.end()) {
139 762468 return found->second;
140 }
141 762468 Vec3d middle = (result.positions[a] + result.positions[b]) * 0.5;
142
2/2
✓ Branch 0 taken 624420 times.
✓ Branch 1 taken 138048 times.
 762468 if (onUnitSphere) {
143 624420 middle = Normalized(middle);
144 }
145 762468 const auto index = static_cast<std::uint32_t>(result.positions.size());
146
1/1
✓ Branch 1 taken 762468 times.
 762468 result.positions.push_back(middle);
147
1/1
✓ Branch 1 taken 762468 times.
 762468 midpoints.emplace(key, index);
148 762468 return index;
149 5835 };
150 5835 std::vector<std::array<std::uint32_t, 3>> triangles;
151
1/1
✓ Branch 2 taken 5835 times.
 5835 triangles.reserve(4 * result.triangles.size());
152
2/2
✓ Branch 4 taken 508312 times.
✓ Branch 5 taken 5835 times.
 514147 for (const auto& t : result.triangles) {
153
1/1
✓ Branch 3 taken 508312 times.
 508312 const std::uint32_t ab = midpoint(t[0], t[1]);
154
1/1
✓ Branch 3 taken 508312 times.
 508312 const std::uint32_t bc = midpoint(t[1], t[2]);
155
1/1
✓ Branch 3 taken 508312 times.
 508312 const std::uint32_t ca = midpoint(t[2], t[0]);
156
1/1
✓ Branch 2 taken 508312 times.
 508312 triangles.push_back({t[0], ab, ca});
157
1/1
✓ Branch 2 taken 508312 times.
 508312 triangles.push_back({ab, t[1], bc});
158
1/1
✓ Branch 2 taken 508312 times.
 508312 triangles.push_back({ca, bc, t[2]});
159
1/1
✓ Branch 1 taken 508312 times.
 508312 triangles.push_back({ab, bc, ca});
160 }
161 5835 result.triangles = std::move(triangles);
162 5835 }
163 3347 return result;
164 }
165
166 21 TriangleMesh Icosphere(int levels) {
167
4/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 19 times.
 21 if (levels < 0 || levels > 12) {
168
1/1
✓ Branch 2 taken 2 times.
 2 throw std::invalid_argument("Icosphere levels must be between 0 and 12");
169 }
170
2/2
✓ Branch 1 taken 19 times.
✓ Branch 4 taken 19 times.
 19 return Subdivide(BaseSolidMesh(BaseSolid::Icosahedron), levels, true);
171 }
172
173 } // namespace terraingen
174