GCC Code Coverage Report

Directory: ./
File: lib/geogram/mesh/mesh_CSG_utils.cpp
Date: 2026-09-07 02:36:43
Exec Total Coverage
Lines: 306 486 63.0%
Functions: 28 33 84.8%
Branches: 300 949 31.6%
Line Branch Exec Source
1 /*
2 * Copyright (c) 2000-2025 Inria
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 * * Neither the name of the ALICE Project-Team nor the names of its
14 * contributors may be used to endorse or promote products derived from this
15 * software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 *
29 * Contact: Bruno Levy
30 *
31 * https://www.inria.fr/fr/bruno-levy
32 *
33 * Inria,
34 * Domaine de Voluceau,
35 * 78150 Le Chesnay - Rocquencourt
36 * FRANCE
37 *
38 */
39
40 #include <geogram/mesh/mesh_CSG_utils.h>
41 #include <geogram/mesh/mesh_io.h>
42 #include <geogram/mesh/mesh_repair.h>
43 #include <geogram/numerics/predicates.h>
44 #include <fstream>
45
46 /********* Value and ArgList *********************************************/
47
48 namespace GEOCSG {
49
50 1675 Value::Value() : type(NONE) {
51 1675 }
52
53
1/2
✓ Branch 2 taken 69 times.
✗ Branch 3 not taken.
 69 Value::Value(const std::string& x) : type(STRING), string_val(x) {
54 69 }
55
56 450 Value::Value(double x) : type(NUMBER), number_val(x) {
57 450 }
58
59 5284 Value::Value(int x) : type(NUMBER), number_val(double(x)) {
60 5284 }
61
62 160 Value::Value(bool x) : type(BOOLEAN), boolean_val(x) {
63 160 }
64
65 21 Value::Value(const std::filesystem::path& x) :
66
1/2
✓ Branch 2 taken 21 times.
✗ Branch 3 not taken.
 21 type(PATH), string_val(x.string()) {
67 21 }
68
69 105 std::string Value::to_string() const {
70
3/7
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 59 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 105 switch(type) {
71 38 case NUMBER: {
72 // We do not want trailing .000 for integers
73 38 return (ceil(number_val) == number_val)
74
1/2
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
 76 ? String::to_string(int(number_val))
75
1/4
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 38 : String::to_string(number_val);
76 }
77 8 case BOOLEAN:
78 8 return String::to_string(boolean_val);
79 ✗ case ARRAY1D: {
80 ✗ std::string result = "[";
81 ✗ if(array_val.size() != 0) {
82 ✗ for(double v: array_val[0]) {
83 ✗ result += String::to_string(v);
84 ✗ result += " ";
85 }
86 }
87 ✗ result += "]";
88 ✗ return result;
89 ✗ }
90 ✗ case ARRAY2D: {
91 ✗ std::string result = "[";
92 ✗ for(const vector<double>& row : array_val) {
93 ✗ result += "[";
94 ✗ for(double v: row) {
95 ✗ result += String::to_string(v);
96 ✗ result += " ";
97 }
98 ✗ result += "]";
99 }
100 ✗ result += "]";
101 ✗ return result;
102 ✗ }
103 59 case PATH:
104 case STRING: {
105
2/4
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 59 times.
✗ Branch 5 not taken.
 59 return "\"" + string_val + "\"";
106 }
107 ✗ case NONE: {
108 ✗ return "<none>";
109 }
110 }
111 ✗ return "<unknown>";
112 }
113
114 723 ArgList::ArgList() : nb_unnamed_(0) {
115 723 }
116
117 1881 void ArgList::add_arg(const std::string& name, const Value& value) {
118
2/2
✓ Branch 1 taken 255 times.
✓ Branch 2 taken 1626 times.
 1881 if(name == "") {
119
2/4
✓ Branch 1 taken 255 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 255 times.
✗ Branch 5 not taken.
 255 add_arg(unnamed_arg_name(nb_unnamed_), value);
120 255 ++nb_unnamed_;
121 255 return;
122 }
123
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1626 times.
 1626 if(has_arg(name)) {
124 ✗ throw(std::logic_error("Duplicated arg:" + name));
125 }
126
2/4
✓ Branch 1 taken 1626 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1626 times.
✗ Branch 5 not taken.
 1626 args_.push_back(std::make_pair(name,value));
127 }
128
129 5248 bool ArgList::has_arg(
130 const std::string& name, index_t pos_fallback, Value::Type type
131 ) const {
132
2/2
✓ Branch 2 taken 10742 times.
✓ Branch 3 taken 3659 times.
 19649 for(const Arg& arg : args_) {
133
2/2
✓ Branch 1 taken 1658 times.
✓ Branch 2 taken 9084 times.
 10742 if(arg.first == name) {
134
4/4
✓ Branch 0 taken 187 times.
✓ Branch 1 taken 1471 times.
✓ Branch 2 taken 118 times.
✓ Branch 3 taken 69 times.
 1658 if(type == Value::NONE || type == arg.second.type) {
135 1589 return true;
136 }
137 }
138 }
139
2/2
✓ Branch 0 taken 3336 times.
✓ Branch 1 taken 323 times.
 3659 if(pos_fallback == NO_INDEX) {
140 3336 return false;
141 }
142
2/4
✓ Branch 1 taken 323 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 323 times.
✗ Branch 5 not taken.
 323 return has_arg(unnamed_arg_name(pos_fallback), NO_INDEX, type);
143 }
144
145 1725 const Value& ArgList::get_arg_value(
146 const std::string& name, index_t pos_fallback
147 ) const {
148
2/2
✓ Branch 2 taken 4712 times.
✓ Branch 3 taken 254 times.
 6691 for(const Arg& arg : args_) {
149
2/2
✓ Branch 1 taken 1471 times.
✓ Branch 2 taken 3241 times.
 4712 if(arg.first == name) {
150 1471 return arg.second;
151 }
152 }
153
1/2
✓ Branch 0 taken 254 times.
✗ Branch 1 not taken.
 254 if(pos_fallback != NO_INDEX) {
154
2/4
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 254 times.
✗ Branch 5 not taken.
 254 return get_arg_value(unnamed_arg_name(pos_fallback));
155 }
156 ✗ geo_assert_not_reached;
157 }
158
159 2394 double ArgList::get_arg(
160 const std::string& name, double default_val, index_t pos_fallback
161 ) const {
162
2/2
✓ Branch 1 taken 778 times.
✓ Branch 2 taken 1616 times.
 2394 if(has_arg(name, pos_fallback)) {
163 778 const Value& value = get_arg_value(name, pos_fallback);
164
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 778 times.
 778 if(value.type != Value::NUMBER) {
165 ✗ throw(std::logic_error("Arg " + name + " has wrong type"));
166 }
167 778 return value.number_val;
168 }
169 1616 return default_val;
170 }
171
172 48 int ArgList::get_arg(
173 const std::string& name, int default_val, index_t pos_fallback
174 ) const {
175
2/2
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24 times.
 48 if(has_arg(name, pos_fallback)) {
176 24 const Value& value = get_arg_value(name, pos_fallback);
177
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if(value.type != Value::NUMBER) {
178 throw(std::logic_error(
179 ✗ "Arg " + name + " has wrong type"
180 ✗ ));
181 }
182
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
 24 if(GEO::round(value.number_val) != value.number_val) {
183 throw(std::logic_error(
184 ✗ "Arg " + name + " has wrong type"
185 ✗ ));
186 }
187 24 return int(value.number_val);
188 }
189 24 return default_val;
190 }
191
192 156 bool ArgList::get_arg(
193 const std::string& name, bool default_val, index_t pos_fallback
194 ) const {
195
1/2
✓ Branch 1 taken 156 times.
✗ Branch 2 not taken.
 156 if(has_arg(name, pos_fallback)) {
196 156 const Value& value = get_arg_value(name, pos_fallback);
197
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 156 times.
 156 if(value.type != Value::BOOLEAN) {
198 ✗ throw(std::logic_error("Arg " + name + " has wrong type"));
199 }
200 156 return value.boolean_val;
201 }
202 ✗ return default_val;
203 }
204
205 94 vec2 ArgList::get_arg(
206 const std::string& name, vec2 default_val, index_t pos_fallback
207 ) const {
208
1/2
✓ Branch 1 taken 94 times.
✗ Branch 2 not taken.
 94 if(has_arg(name, pos_fallback)) {
209 94 const Value& value = get_arg_value(name, pos_fallback);
210
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 70 times.
 94 if(value.type == Value::NUMBER) {
211 24 return vec2(
212 24 value.number_val,
213 24 value.number_val
214 24 );
215
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 70 times.
 70 } else if(value.type != Value::ARRAY1D) {
216 throw(std::logic_error(
217 ✗ "Arg " + name + " has wrong type"
218 ✗ ));
219 }
220
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 70 times.
 70 if(value.array_val.size() != 1) {
221 throw(std::logic_error(
222 ✗ "Arg " + name + " has wrong dimension"
223 ✗ ));
224 }
225 70 index_t N = value.array_val[0].size();
226 70 return vec2(
227
2/4
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 70 times.
✗ Branch 5 not taken.
 70 (N >= 1) ? value.array_val[0][0] : 0.0,
228
4/8
✓ Branch 0 taken 70 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 70 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 70 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 70 times.
✗ Branch 9 not taken.
 140 (N >= 2) ? value.array_val[0][1] : 0.0
229 70 );
230 }
231 ✗ return default_val;
232 }
233
234 47 vec3 ArgList::get_arg(
235 const std::string& name, vec3 default_val, index_t pos_fallback
236 ) const {
237
1/2
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
 47 if(has_arg(name, pos_fallback)) {
238 47 const Value& value = get_arg_value(name, pos_fallback);
239
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 47 times.
 47 if(value.type != Value::ARRAY1D) {
240 throw(std::logic_error(
241 ✗ "Arg " + name + " has wrong type"
242 ✗ ));
243 }
244
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 47 times.
 47 if(value.array_val.size() != 1) {
245 throw(std::logic_error(
246 ✗ "Arg " + name + " has wrong dimension"
247 ✗ ));
248 }
249 47 index_t N = value.array_val[0].size();
250 return vec3(
251
2/4
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 47 times.
✗ Branch 5 not taken.
 47 (N >= 1) ? value.array_val[0][0] : 0.0,
252
3/6
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 47 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 47 times.
✗ Branch 7 not taken.
 47 (N >= 2) ? value.array_val[0][1] : 0.0,
253
4/8
✓ Branch 0 taken 47 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 47 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 47 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 47 times.
✗ Branch 9 not taken.
 94 (N >= 3) ? value.array_val[0][2] : 0.0
254 47 );
255 }
256 ✗ return default_val;
257 }
258
259 1 vec4 ArgList::get_arg(
260 const std::string& name, vec4 default_val, index_t pos_fallback
261 ) const {
262
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 1 if(has_arg(name, pos_fallback)) {
263 ✗ const Value& value = get_arg_value(name, pos_fallback);
264 ✗ if(value.type != Value::ARRAY1D) {
265 throw(std::logic_error(
266 ✗ "Arg " + name + " has wrong type"
267 ✗ ));
268 }
269 ✗ if(value.array_val.size() != 1) {
270 throw(std::logic_error(
271 ✗ "Arg " + name + " has wrong dimension"
272 ✗ ));
273 }
274 ✗ index_t N = value.array_val[0].size();
275 return vec4(
276 ✗ (N >= 1) ? value.array_val[0][0] : 0.0,
277 ✗ (N >= 2) ? value.array_val[0][1] : 0.0,
278 ✗ (N >= 3) ? value.array_val[0][2] : 0.0,
279 ✗ (N >= 4) ? value.array_val[0][3] : 0.0
280 ✗ );
281 }
282 1 return default_val;
283 }
284
285 254 mat4 ArgList::get_arg(
286 const std::string& name, const mat4& default_val, index_t pos_fallback
287 ) const {
288
1/2
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
 254 if(has_arg(name, pos_fallback)) {
289
1/2
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
 254 const Value& value = get_arg_value(name, pos_fallback);
290
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 254 times.
 254 if(value.type != Value::ARRAY2D) {
291 throw(std::logic_error(
292 ✗ "Arg " + name + " has wrong type"
293 ✗ ));
294 }
295
1/2
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
 254 auto Mvv = value.array_val;
296 254 if(
297
1/2
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
 508 Mvv.size() != 4 ||
298
2/4
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 254 times.
✗ Branch 5 not taken.
 508 Mvv[0].size() != 4 ||
299
2/4
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 254 times.
✗ Branch 5 not taken.
 508 Mvv[1].size() != 4 ||
300
4/8
✓ Branch 0 taken 254 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 254 times.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 254 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 254 times.
 762 Mvv[2].size() != 4 ||
301
1/2
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
 254 Mvv[3].size() != 4
302 ) {
303 throw(std::logic_error(
304 "Matrix arg has wrong dimension"
305 ✗ ));
306 }
307
1/2
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
 254 mat4 result;
308
2/2
✓ Branch 0 taken 1016 times.
✓ Branch 1 taken 254 times.
 1270 for(index_t i=0; i<4; ++i) {
309
2/2
✓ Branch 0 taken 4064 times.
✓ Branch 1 taken 1016 times.
 5080 for(index_t j=0; j<4; ++j) {
310
3/6
✓ Branch 1 taken 4064 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4064 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4064 times.
✗ Branch 8 not taken.
 4064 result(i,j) = Mvv[i][j];
311 }
312 }
313 254 return result;
314 254 }
315 ✗ return default_val;
316 }
317
318 50 std::string ArgList::get_arg(
319 const std::string& name, const std::string& default_val,
320 index_t pos_fallback
321 ) const {
322
1/2
✓ Branch 1 taken 50 times.
✗ Branch 2 not taken.
 50 if(has_arg(name, pos_fallback)) {
323 50 const Value& value = get_arg_value(name, pos_fallback);
324
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50 times.
 50 if(value.type != Value::STRING) {
325 throw(std::logic_error(
326 ✗ "Arg " + name + " has wrong type"
327 ✗ ));
328 }
329 50 return value.string_val;
330 }
331 ✗ return default_val;
332 }
333 }
334
335
336 /********* Sweep *************************************************/
337
338 namespace GEOCSG {
339
340 122 void sweep(
341 std::shared_ptr<Mesh>& M, index_t nv,
342 std::function<vec3(index_t, index_t)> sweep_path,
343 SweepCapping capping
344 ) {
345
346
1/2
✓ Branch 2 taken 122 times.
✗ Branch 3 not taken.
 122 M->vertices.set_dimension(2);
347 122 index_t nu = M->vertices.nb();
348
349 122 index_t total_nb_vertices = 0;
350
3/4
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 122 switch(capping) {
351 118 case SWEEP_CAP: {
352 118 total_nb_vertices = nu*nv;
353 118 } break;
354 1 case SWEEP_POLE: {
355 1 total_nb_vertices = nu*(nv-1)+1;
356 1 } break;
357 3 case SWEEP_PERIODIC: {
358 3 total_nb_vertices = nu*(nv-1);
359
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 M->facets.clear();
360 3 } break;
361 }
362
363 122 index_t nt0 = M->facets.nb();
364
365
1/2
✓ Branch 2 taken 122 times.
✗ Branch 3 not taken.
 122 M->vertices.set_dimension(3);
366
1/2
✓ Branch 2 taken 122 times.
✗ Branch 3 not taken.
 122 M->vertices.create_vertices(total_nb_vertices - nu);
367
368 // Start from 1: do not touch first slice for now, because it
369 // may be used by sweep_path (as the origin of paths)
370
2/2
✓ Branch 0 taken 685 times.
✓ Branch 1 taken 122 times.
 807 for(index_t v=1; v<nv-1; ++v) {
371
2/2
✓ Branch 0 taken 20130 times.
✓ Branch 1 taken 685 times.
 20815 for(index_t u=0; u<nu; ++u) {
372
2/4
✓ Branch 1 taken 20130 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 20130 times.
✗ Branch 6 not taken.
 20130 M->vertices.point(v*nu+u) = sweep_path(u,v);
373 }
374 }
375
376 // Particular case: last slice
377
3/4
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 122 switch(capping) {
378 118 case SWEEP_CAP:
379
2/2
✓ Branch 0 taken 3293 times.
✓ Branch 1 taken 118 times.
 3411 for(index_t u=0; u<nu; ++u) {
380
2/4
✓ Branch 1 taken 3293 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 3293 times.
✗ Branch 6 not taken.
 3293 M->vertices.point((nv-1)*nu+u) = sweep_path(u,nv-1);
381 }
382 118 break;
383 1 case SWEEP_POLE:
384
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 M->vertices.point((nv-1)*nu) = sweep_path(0,nv-1);
385 1 break;
386 3 case SWEEP_PERIODIC:
387 // Nothing to do, last slice is same as first slice
388 3 break;
389 }
390
391 // Now map first slice
392
2/2
✓ Branch 0 taken 3384 times.
✓ Branch 1 taken 122 times.
 3506 for(index_t u=0; u<nu; ++u) {
393
2/4
✓ Branch 1 taken 3384 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 3384 times.
✗ Branch 6 not taken.
 3384 M->vertices.point(u) = sweep_path(u,0);
394 }
395
396 // creates one row of "brick" for the walls
397 806 auto create_brick_row = [&](index_t v, bool periodic=false) {
398 806 index_t v1 = v;
399 806 index_t v2 = v1+1;
400
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 803 times.
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 806 if(periodic && v2 == nv-1) {
401 3 v2 = 0;
402 }
403
2/2
✓ Branch 2 taken 23394 times.
✓ Branch 3 taken 806 times.
 24200 for(index_t e=0; e < M->edges.nb(); ++e) {
404 23394 index_t vx1 = v1 * nu + M->edges.vertex(e,0) ;
405 23394 index_t vx2 = v1 * nu + M->edges.vertex(e,1) ;
406 23394 index_t vx3 = v2 * nu + M->edges.vertex(e,0) ;
407 23394 index_t vx4 = v2 * nu + M->edges.vertex(e,1) ;
408 23394 const vec3& p1 = M->vertices.point(vx1);
409 23394 const vec3& p2 = M->vertices.point(vx2);
410 23394 const vec3& p3 = M->vertices.point(vx3);
411 23394 const vec3& p4 = M->vertices.point(vx4);
412
413
1/2
✓ Branch 2 taken 23394 times.
✗ Branch 3 not taken.
 23394 double l1 = length(p3-p2);
414
1/2
✓ Branch 2 taken 23394 times.
✗ Branch 3 not taken.
 23394 double l2 = length(p4-p1);
415 23394 bool not_significative = (::fabs(l1-l2) < (l1+l2)*1e-6);
416
417
4/4
✓ Branch 0 taken 4460 times.
✓ Branch 1 taken 18934 times.
✓ Branch 2 taken 1440 times.
✓ Branch 3 taken 3020 times.
 23394 if(not_significative || l1 < l2) {
418 20374 M->facets.create_triangle(vx1, vx2, vx3);
419 20374 M->facets.create_triangle(vx3, vx2, vx4);
420 } else {
421 3020 M->facets.create_triangle(vx1, vx2, vx4);
422 3020 M->facets.create_triangle(vx1, vx4, vx3);
423 }
424 }
425 806 };
426
427 // generate walls (all brick rows except last one)
428
2/2
✓ Branch 0 taken 685 times.
✓ Branch 1 taken 122 times.
 807 for(index_t v=0; v+2 < nv; ++v) {
429
1/2
✓ Branch 1 taken 685 times.
✗ Branch 2 not taken.
 685 create_brick_row(v);
430 }
431
432 // generate walls (last "brick" row, depends on capping mode)
433
3/4
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 122 switch(capping) {
434 118 case SWEEP_CAP: {
435
1/2
✓ Branch 1 taken 118 times.
✗ Branch 2 not taken.
 118 create_brick_row(nv-2);
436 118 } break;
437 1 case SWEEP_POLE: {
438 1 index_t v = nv-2;
439
2/2
✓ Branch 2 taken 30 times.
✓ Branch 3 taken 1 times.
 31 for(index_t e=0; e < M->edges.nb(); ++e) {
440
1/2
✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
 30 index_t vx1 = v * nu + M->edges.vertex(e,0) ;
441
1/2
✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
 30 index_t vx2 = v * nu + M->edges.vertex(e,1) ;
442 30 index_t vx3 = nu * (nv-1);
443
1/2
✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
 30 M->facets.create_triangle(vx1, vx2, vx3);
444 }
445 1 } break;
446 3 case SWEEP_PERIODIC: {
447
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 create_brick_row(nv-2, true); // periodic
448 3 } break;
449 }
450
451 // generate second capping
452
2/2
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 4 times.
 122 if(capping == SWEEP_CAP) {
453 118 index_t nt1 = M->facets.nb();
454 118 index_t v_ofs = nu*(nv-1);
455
1/2
✓ Branch 2 taken 118 times.
✗ Branch 3 not taken.
 118 M->facets.create_triangles(nt0);
456
2/2
✓ Branch 0 taken 3121 times.
✓ Branch 1 taken 118 times.
 3239 for(index_t t=0; t<nt0; ++t) {
457
2/4
✓ Branch 3 taken 3121 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 3121 times.
✗ Branch 7 not taken.
 3121 M->facets.set_vertex(t+nt1, 0, v_ofs + M->facets.vertex(t,0));
458
2/4
✓ Branch 3 taken 3121 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 3121 times.
✗ Branch 7 not taken.
 3121 M->facets.set_vertex(t+nt1, 1, v_ofs + M->facets.vertex(t,1));
459
2/4
✓ Branch 3 taken 3121 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 3121 times.
✗ Branch 7 not taken.
 3121 M->facets.set_vertex(t+nt1, 2, v_ofs + M->facets.vertex(t,2));
460 }
461 }
462
463 // flip initial triangles to generate first capping
464
4/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 118 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 3 times.
 122 if(capping == SWEEP_CAP || capping == SWEEP_POLE) {
465
2/2
✓ Branch 0 taken 3149 times.
✓ Branch 1 taken 119 times.
 3268 for(index_t t=0; t<nt0; ++t) {
466
1/2
✓ Branch 2 taken 3149 times.
✗ Branch 3 not taken.
 3149 M->facets.flip(t);
467 }
468 }
469
470
1/2
✓ Branch 2 taken 122 times.
✗ Branch 3 not taken.
 122 M->edges.clear();
471 122 }
472
473 ✗ void keep_z0_only(std::shared_ptr<Mesh>& M) {
474 ✗ vector<index_t> remove_triangle(M->facets.nb(),0);
475 ✗ for(index_t t=0; t<M->facets.nb(); ++t) {
476 ✗ for(index_t lv=0; lv<3; ++lv) {
477 ✗ const vec3& p = M->facets.point(t,lv);
478 ✗ if(p.z != 0.0) {
479 ✗ remove_triangle[t] = 1;
480 ✗ break;
481 }
482 }
483 }
484 ✗ M->facets.delete_elements(remove_triangle);
485 ✗ M->vertices.remove_isolated();
486 ✗ M->vertices.set_dimension(2);
487 ✗ }
488 }
489
490 /*************************************************************************/
491
492 namespace {
493 /** \brief subdirectory with all cached files converted by OpenSCAD */
494 static const char* OpenSCache = "OpenSCache";
495
496 bool OpenSCache_invalidate = false;
497 bool OpenSCache_ignore_time = false;
498 }
499
500 namespace GEOCSG {
501
502 ✗ void OpenSCAD_cache_invalidate() {
503 ✗ OpenSCache_invalidate = true;
504 ✗ }
505
506 20 void OpenSCAD_cache_ignore_time() {
507 20 OpenSCache_ignore_time = true;
508 20 }
509
510 21 std::shared_ptr<Mesh> call_OpenSCAD(
511 const std::filesystem::path& path, const std::string& command,
512 const ArgList& args, bool TWO_D
513 ) {
514
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 std::shared_ptr<Mesh> result = std::make_shared<Mesh>();
515
516
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 std::string mangled = command;
517
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 std::string command_with_args = command + "(";
518
3/4
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 63 times.
✓ Branch 4 taken 21 times.
 84 for(index_t i=0; i<args.size(); ++i) {
519
2/4
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 63 times.
✗ Branch 5 not taken.
 63 command_with_args += args.ith_arg_name(i);
520
1/2
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
 63 command_with_args += '=';
521
3/6
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 63 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 63 times.
✗ Branch 8 not taken.
 63 command_with_args += args.ith_arg_val(i).to_string();
522
3/4
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 42 times.
✓ Branch 4 taken 21 times.
 63 if(i != args.size()-1) {
523
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 command_with_args += ',';
524 }
525
1/2
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
 63 mangled += '_';
526 63 std::string mangled_arg;
527
3/4
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 21 times.
✓ Branch 4 taken 42 times.
 63 if(args.ith_arg_val(i).type == Value::PATH) {
528
2/4
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21 times.
✗ Branch 5 not taken.
 21 std::filesystem::path path_val(args.ith_arg_val(i).string_val);
529
3/6
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 21 times.
✗ Branch 8 not taken.
 21 mangled_arg += path_val.filename().string();
530 21 } else {
531
2/4
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 42 times.
✗ Branch 5 not taken.
 42 mangled_arg = args.ith_arg_val(i).to_string();
532 }
533
5/6
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 44 times.
✓ Branch 5 taken 19 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 19 times.
✓ Branch 8 taken 44 times.
 126 if(*mangled_arg.begin() == '"' && *mangled_arg.rbegin() == '"') {
534
1/2
✓ Branch 2 taken 19 times.
✗ Branch 3 not taken.
 19 mangled_arg = mangled_arg.substr(1, mangled_arg.length()-2);
535
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 16 times.
 19 if(mangled_arg.size() == 0) {
536
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 mangled_arg = "nil";
537 }
538 }
539
1/2
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
 63 mangled += mangled_arg;
540 63 }
541
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 command_with_args += ')';
542
543 21 std::replace(mangled.begin(), mangled.end(), ' ', '_');
544 21 std::replace(mangled.begin(), mangled.end(), '.', '@');
545 21 std::replace(mangled.begin(), mangled.end(), '/', '!');
546 21 std::replace(mangled.begin(), mangled.end(), '\\', '!');
547
548
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 std::filesystem::path tmp = std::filesystem::temp_directory_path();
549
2/4
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21 times.
✗ Branch 5 not taken.
 21 std::filesystem::path cache_path = path / OpenSCache;
550
2/4
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 21 times.
 21 if(!std::filesystem::is_directory(cache_path)) {
551 ✗ std::filesystem::create_directory(cache_path);
552 }
553
554
3/6
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 21 times.
✗ Branch 8 not taken.
 21 std::filesystem::path cached_STL = cache_path / (mangled + ".stl");
555
556 // Cached file exists, load it and return it
557 21 if(
558
2/4
✓ Branch 0 taken 21 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 21 times.
✗ Branch 3 not taken.
 42 !OpenSCache_invalidate &&
559
2/4
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 21 times.
✗ Branch 4 not taken.
 21 std::filesystem::is_regular_file(cached_STL)
560 ) {
561
5/10
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 21 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 21 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 21 times.
✗ Branch 14 not taken.
 21 Logger::out("CSG")<< "Using cached " << cached_STL << std::endl;
562
3/6
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 21 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 21 times.
✗ Branch 9 not taken.
 21 mesh_load(cached_STL.string(), *result);
563
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 mesh_repair(
564 21 *result, MeshRepairMode(MESH_REPAIR_DEFAULT | MESH_REPAIR_QUIET)
565 );
566
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 2 times.
 21 if(TWO_D) {
567
1/2
✓ Branch 2 taken 19 times.
✗ Branch 3 not taken.
 19 result->vertices.set_dimension(2);
568 }
569 21 return result;
570 }
571
572 // Generate file with OpenSCAD
573 ✗ std::filesystem::path osc = tmp / "tmpscad.scad";
574 ✗ std::filesystem::path osc_stl = tmp / "tmpscad.stl";
575 ✗ std::ofstream gen_osc(osc);
576 ✗ if(!gen_osc) {
577 ✗ throw(std::logic_error(osc.string() + ": could not create"));
578 }
579 // OpenSCAD cannot save 2d results, so if we are in 2D, we
580 // artificially generate a 3d result by extrusion
581 ✗ if(TWO_D) {
582 ✗ gen_osc << "linear_extrude(height=1.0) {";
583 }
584 ✗ gen_osc << command_with_args << ";" << std::endl;
585 ✗ if(TWO_D) {
586 ✗ gen_osc << "}";
587 }
588 ✗ gen_osc.close();
589
590
591 // Execute openscad
592 std::string openscad_command = "openscad "
593 ✗ + osc.string() + " -o " + osc_stl.string() ;
594 ✗ if(system(openscad_command.c_str())) {
595 ✗ Logger::warn("CSG") << "Error while running openscad "
596 ✗ << std::endl;
597 ✗ Logger::warn("CSG") << "(for command: " << command <<") "
598 ✗ << std::endl;
599 }
600
601 ✗ if(!std::filesystem::is_regular_file(osc_stl)) {
602 ✗ Logger::warn("CSG") << "Could not open " << osc_stl << std::endl;
603 ✗ return result;
604 }
605
606 ✗ mesh_load(osc_stl.string(), *result);
607 ✗ std::filesystem::remove(osc);
608 ✗ std::filesystem::remove(osc_stl);
609
610 // If we are in 2D, we have artificially added an extrusion to
611 // have a 3D result (else OpenSCAD does not output anything),
612 // so we need to remove these additional triangles
613 ✗ if(TWO_D) {
614 ✗ keep_z0_only(result);
615 }
616 ✗ mesh_save(*result,cached_STL.string());
617 ✗ mesh_repair(
618 ✗ *result, MeshRepairMode(MESH_REPAIR_DEFAULT | MESH_REPAIR_QUIET)
619 );
620 ✗ return result;
621 21 }
622
623 40 std::string load_OpenSCAD(const std::filesystem::path& input) {
624
15/30
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 20 times.
✓ Branch 8 taken 20 times.
✓ Branch 10 taken 20 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 20 times.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✓ Branch 17 taken 20 times.
✓ Branch 18 taken 20 times.
✓ Branch 19 taken 20 times.
✓ Branch 21 taken 20 times.
✓ Branch 22 taken 20 times.
✓ Branch 24 taken 40 times.
✗ Branch 25 not taken.
✓ Branch 27 taken 40 times.
✗ Branch 28 not taken.
✓ Branch 30 taken 20 times.
✓ Branch 31 taken 20 times.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
 40 if(input.extension() == ".scad" || input.extension() == ".SCAD") {
625
3/6
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 20 times.
✗ Branch 8 not taken.
 20 std::filesystem::path cache_path=input.parent_path() / OpenSCache;
626
627
2/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 20 times.
 20 if(!std::filesystem::is_directory(cache_path)) {
628 ✗ std::filesystem::create_directory(cache_path);
629 }
630
631 std::filesystem::path cached_csg =
632
4/8
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 20 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 20 times.
✗ Branch 11 not taken.
 20 cache_path / input.filename().replace_extension(".csg");
633
634
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 bool generate = !std::filesystem::is_regular_file(cached_csg);
635
636
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if(OpenSCache_invalidate) {
637 ✗ generate = true;
638 }
639
640
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if(!OpenSCache_ignore_time) {
641 ✗ generate = generate || (
642 ✗ std::filesystem::last_write_time(input) >
643 ✗ std::filesystem::last_write_time(cached_csg)
644 );
645 }
646
647
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if(generate) {
648 ✗ Logger::out("CSG") << "Converting " << input << " with OpenSCAD"
649 ✗ << std::endl;
650 std::string openscad_command = "openscad "
651 ✗ + input.string() + " -o " + cached_csg.string() ;
652 ✗ if(system(openscad_command.c_str())) {
653 ✗ Logger::warn("CSG") << "Error while running openscad "
654 ✗ << std::endl;
655 ✗ Logger::warn("CSG") << "(for converting: " << input << ") "
656 ✗ << std::endl;
657 ✗ return "";
658 }
659 ✗ if(std::filesystem::is_regular_file(cached_csg)) {
660 ✗ Logger::out("CSG") << "Created " << cached_csg << std::endl;
661 } else {
662 ✗ Logger::out("CSG") << "Could not create"
663 ✗ << cached_csg << std::endl;
664 }
665 ✗ } else {
666
5/10
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 20 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 20 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 20 times.
✗ Branch 14 not taken.
 40 Logger::out("CSG") << "Using cached " << cached_csg << std::endl;
667 }
668
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 return load_OpenSCAD(cached_csg);
669 20 }
670
671
8/30
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 20 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✓ Branch 19 taken 20 times.
✗ Branch 21 not taken.
✓ Branch 22 taken 20 times.
✓ Branch 24 taken 20 times.
✗ Branch 25 not taken.
✓ Branch 27 taken 20 times.
✗ Branch 28 not taken.
✓ Branch 30 taken 20 times.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
 20 if(input.extension() == ".csg" || input.extension() == ".CSG") {
672 20 std::string source;
673
2/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
✗ Branch 4 not taken.
 20 if(std::filesystem::is_regular_file(input)) {
674
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 size_t length = size_t(std::filesystem::file_size(input));
675
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 source.resize(length);
676
2/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 20 times.
✗ Branch 6 not taken.
 20 FILE* f = fopen(input.string().c_str(),"rb");
677
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if(f != nullptr) {
678
1/2
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
 20 size_t read_length = fread(source.data(), 1, length, f);
679
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if(read_length != length) {
680 ✗ Logger::err("CSG")
681 << "Problem occured when reading "
682 ✗ << input
683 ✗ << std::endl;
684 }
685
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 fclose(f);
686 }
687 }
688 20 return source;
689 20 }
690 ✗ Logger::err("CSG") << "Unknown extension: " << input << std::endl;
691 ✗ return "";
692 }
693 }
694
695 /************** Functions taken from OpenSCAD ****************************/
696
697 namespace {
698 // From openscad/Geometry/Grid.h
699 static const double GRID_FINE = 0.00000095367431640625;
700 // This one often misses so I redeclare it here
701 static const double M_DEG2RAD = M_PI / 180.0;
702
703 /*
704 https://mathworld.wolfram.com/Helix.html
705 For a helix defined as: F(t) = [r*cost(t), r*sin(t), c*t] for t in [0,T)
706 The helical arc length is L = T * sqrt(r^2 + c^2)
707 Where its pitch is pitch = 2*PI*c
708 Pitch is also height per turn: pitch = height / (twist/360)
709 Solving for c gives c = height / (twist*PI/180)
710 Where (twist*PI/180) is just twist in radians, aka "T"
711 */
712 3 double helix_arc_length(double r_sqr, double height, double twist) {
713 3 double T = twist * M_DEG2RAD;
714 3 double c = height / T;
715 3 return T * sqrt(r_sqr + c * c);
716 }
717
718
719 /*
720 Returns the number of slices for a linear_extrude with twist.
721 Given height, twist, and the three special variables $fn, $fs and $fa
722 */
723 4 int get_helix_slices(
724 double r_sqr, double height, double twist,
725 double fn, double fs, double fa
726 ) {
727 4 twist = fabs(twist);
728 // 180 twist per slice is worst case, guaranteed non-manifold.
729 // Make sure we have at least 3 slices per 360 twist
730 4 int min_slices = std::max(static_cast<int>(ceil(twist / 120.0)), 1);
731
4/8
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 4 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 4 times.
 4 if (sqrt(r_sqr) < GRID_FINE || std::isinf(fn) || std::isnan(fn))
732 ✗ return min_slices;
733
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
 4 if (fn > 0.0) {
734 1 int fn_slices = static_cast<int>(ceil(twist / 360.0 * fn));
735 1 return std::max(fn_slices, min_slices);
736 }
737 3 int fa_slices = static_cast<int>(ceil(twist / fa));
738 3 int fs_slices = static_cast<int>(
739 3 ceil(helix_arc_length(r_sqr, height, twist) / fs)
740 3 );
741 3 return std::max(std::min(fa_slices, fs_slices), min_slices);
742 }
743
744 /*
745 For linear_extrude with twist and uniform scale (scale_x == scale_y),
746 to calculate the limit imposed by special variable $fs, we find the
747 total length along the path that a vertex would follow.
748 The XY-projection of this path is a section of the Archimedes Spiral.
749 https://mathworld.wolfram.com/ArchimedesSpiral.html
750 Using the formula for its arc length, then pythagorean theorem with height
751 should tell us the total distance a vertex covers.
752 */
753 ✗ double archimedes_length(double a, double theta) {
754 ✗ return 0.5 * a * (theta * sqrt(1 + theta * theta) + asinh(theta));
755 }
756
757
758 ✗ int get_conical_helix_slices(
759 double r_sqr, double height, double twist, double scale,
760 double fn, double fs, double fa
761 ) {
762 ✗ twist = fabs(twist);
763 ✗ double r = sqrt(r_sqr);
764 ✗ int min_slices = std::max(static_cast<int>(ceil(twist / 120.0)), 1);
765 ✗ if (r < GRID_FINE || std::isinf(fn) || std::isnan(fn)) {
766 ✗ return min_slices;
767 }
768 ✗ if (fn > 0.0) {
769 ✗ int fn_slices = static_cast<int>(ceil(twist * fn / 360));
770 ✗ return std::max(fn_slices, min_slices);
771 }
772
773 /*
774 Spiral length equation assumes starting from theta=0
775 Our twist+scale only covers a section of this length (unless scale=0).
776 Find the start and end angles that our twist+scale correspond to.
777 Use similar triangles to visualize cross-section of single vertex,
778 with scale extended to 0 (origin).
779
780 (scale < 1) (scale > 1)
781 ______t_ 1.5x (Z=h)
782 0x | | /
783 |\ |____|/
784 | \ | / 1x (Z=0)
785 | \ | /
786 |___\ 0.66x (Z=h) | / t is angle of our arc section (twist, in rads)
787 | |\ | / E is angle_end (total triangle base length)
788 |___|_\ 1x (Z=0) |/ 0x S is angle_start
789 t
790
791 E = t*1/(1-0.66)=3t E = t*1.5/(1.5-1) = 3t
792 B = E - t B = E - t
793 */
794 ✗ double rads = twist * M_DEG2RAD;
795 double angle_end;
796 ✗ if (scale > 1) {
797 ✗ angle_end = rads * scale / (scale - 1);
798 ✗ } else if (scale < 1) {
799 ✗ angle_end = rads / (1 - scale);
800 } else {
801 // Don't calculate conical slices on non-scaled extrude!
802 ✗ geo_assert_not_reached;
803 }
804 ✗ double angle_start = angle_end - rads;
805 ✗ double a = r / angle_end; // spiral scale coefficient
806 ✗ double spiral_length = archimedes_length(
807 ✗ a, angle_end) - archimedes_length(a, angle_start
808 ✗ );
809 // Treat (flat spiral_length,extrusion height) as (base,height)
810 // of a right triangle to get diagonal length.
811 ✗ double total_length = sqrt(
812 ✗ spiral_length * spiral_length + height * height
813 );
814
815 ✗ int fs_slices = static_cast<int>(ceil(total_length / fs));
816 ✗ int fa_slices = static_cast<int>(ceil(twist / fa));
817 ✗ return std::max(std::min(fa_slices, fs_slices), min_slices);
818 }
819
820 /*
821 For linear_extrude with non-uniform scale (and no twist)
822 Either use $fn directly as slices,
823 or divide the longest diagonal vertex extrude path by $fs
824
825 dr_sqr - the largest 2D delta (before/after scaling)
826 for all vertices, squared.
827 note: $fa is not considered since no twist
828 scale is not passed in since it was already used
829 to calculate the largest delta.
830 */
831 ✗ int get_diagonal_slices(
832 double delta_sqr, double height, double fn, double fs
833 ) {
834 ✗ constexpr int min_slices = 1;
835 ✗ if (sqrt(delta_sqr) < GRID_FINE || std::isinf(fn) || std::isnan(fn)) {
836 ✗ return min_slices;
837 }
838 ✗ if (fn > 0.0) {
839 ✗ int fn_slices = static_cast<int>(fn);
840 ✗ return std::max(fn_slices, min_slices);
841 }
842 ✗ int fs_slices = static_cast<int>(
843 ✗ ceil(sqrt(delta_sqr + height * height) / fs)
844 ✗ );
845 ✗ return std::max(fs_slices, min_slices);
846 }
847
848 }
849
850 namespace GEOCSG {
851
852 122 int get_fragments_from_r_and_twist(
853 double r, double twist, double fn, double fs, double fa
854 ) {
855
856
4/8
✓ Branch 0 taken 122 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 122 times.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 122 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 122 times.
 122 if (r < GRID_FINE || std::isinf(fn) || std::isnan(fn)) {
857 ✗ return 3u;
858 }
859
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 121 times.
 122 if (fn > 0.0) {
860
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 return static_cast<int>(fn >= 3 ? fn : 3);
861 }
862 return static_cast<int>(
863 121 ceil(fmax(fmin(twist / fa, r * 2.0 * M_PI / fs), 5.0))
864 121 );
865 }
866
867 // This one is not part of OpenSCAD, I copied it from
868 // extrudePolygon() in geometry/GeometryEvaluator.cc
869 // (with some readaptations / reordering to make it
870 // easier to understand, at least for me)
871 24 int get_linear_extrusion_slices(
872 std::shared_ptr<Mesh> M,
873 double height, vec2 scale, double twist,
874 double fn, double fs, double fa
875 ) {
876
877
3/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
 24 if(twist == 0.0 && scale.x == scale.y) {
878 20 return 1;
879 }
880
881 4 double max_r1_sqr = 0.0; // r1 is before scaling
882 4 double max_delta_sqr = 0; // delta from before/after scaling
883
2/2
✓ Branch 2 taken 139 times.
✓ Branch 3 taken 4 times.
 143 for(index_t iv=0; iv<M->vertices.nb(); ++iv) {
884
1/2
✓ Branch 2 taken 139 times.
✗ Branch 3 not taken.
 139 const vec2& v = M->vertices.point<2>(iv);
885
1/2
✓ Branch 1 taken 139 times.
✗ Branch 2 not taken.
 139 max_r1_sqr = std::max(max_r1_sqr, length2(v));
886 139 GEO::vec2 scale_v(v.x*scale.x, v.y*scale.y);
887 278 max_delta_sqr = std::max(
888
1/2
✓ Branch 2 taken 139 times.
✗ Branch 3 not taken.
 139 max_delta_sqr, length2(v - scale_v)
889 );
890 }
891
892
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if(twist == 0.0) {
893 ✗ return get_diagonal_slices(max_delta_sqr, height, fn, fs);
894 }
895
896 // Calculate Helical curve length for Twist with no Scaling
897
2/4
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 if(scale.x == 1.0 && scale.y == 1.0) {
898
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 return get_helix_slices(max_r1_sqr, height, twist, fn, fs, fa);
899 }
900
901 // non uniform scaling with twist using max slices
902 // from twist and non uniform scale
903 ✗ if(scale.x != scale.y) {
904 ✗ int slicesNonUniScale = get_diagonal_slices(
905 max_delta_sqr, height, fn, fs
906 ✗ );
907 ✗ int slicesTwist = get_helix_slices(
908 max_r1_sqr, height, twist, fn, fs, fa
909 ✗ );
910 ✗ return std::max(slicesNonUniScale, slicesTwist);
911 }
912
913 // uniform scaling with twist, use conical helix calculation
914 ✗ return get_conical_helix_slices(
915 max_r1_sqr, height, twist, scale.x, fn, fs, fa
916 ✗ );
917 }
918 }
919