forked from openscad/openscad
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathGeometryEvaluator.cc
1644 lines (1515 loc) · 52.3 KB
/
GeometryEvaluator.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#include "GeometryEvaluator.h"
#include "Tree.h"
#include "GeometryCache.h"
#include "CGALCache.h"
#include "Polygon2d.h"
#include "module.h"
#include "ModuleInstantiation.h"
#include "state.h"
#include "offsetnode.h"
#include "transformnode.h"
#include "linearextrudenode.h"
#include "roofnode.h"
#include "roof_ss.h"
#include "roof_vd.h"
#include "rotateextrudenode.h"
#include "csgnode.h"
#include "cgaladvnode.h"
#include "projectionnode.h"
#include "csgops.h"
#include "textnode.h"
#include "CGAL_Nef_polyhedron.h"
#include "cgalutils.h"
#include "rendernode.h"
#include "clipper-utils.h"
#include "polyset-utils.h"
#include "polyset.h"
#include "calc.h"
#include "printutils.h"
#include "svg.h"
#include "calc.h"
#include "dxfdata.h"
#include "degree_trig.h"
#include <ciso646> // C alternative tokens (xor)
#include <algorithm>
#include "boost-utils.h"
#include <CGAL/convex_hull_2.h>
#include <CGAL/Point_2.h>
GeometryEvaluator::GeometryEvaluator(const class Tree &tree):
tree(tree)
{
}
/*!
Set allownef to false to force the result to _not_ be a Nef polyhedron
*/
shared_ptr<const Geometry> GeometryEvaluator::evaluateGeometry(const AbstractNode &node,
bool allownef)
{
const std::string &key = this->tree.getIdString(node);
if (!GeometryCache::instance()->contains(key)) {
shared_ptr<const CGAL_Nef_polyhedron> N;
if (CGALCache::instance()->contains(key)) {
N = CGALCache::instance()->get(key);
}
// If not found in any caches, we need to evaluate the geometry
if (N) {
this->root = N;
}
else {
this->traverse(node);
}
if (!allownef) {
if (shared_ptr<const CGAL_Nef_polyhedron> N = dynamic_pointer_cast<const CGAL_Nef_polyhedron>(this->root)) {
PolySet *ps = new PolySet(3);
ps->setConvexity(N->getConvexity());
this->root.reset(ps);
if (!N->isEmpty()) {
bool err = CGALUtils::createPolySetFromNefPolyhedron3(*N->p3, *ps);
if (err) {
LOG(message_group::Error,Location::NONE,"","Nef->PolySet failed."); }
}
}
// We cannot render concave polygons, so tessellate any 3D PolySets
auto ps = dynamic_pointer_cast<const PolySet>(this->root);
if (ps && !ps->isEmpty()) {
// Since is_convex() doesn't handle non-planar faces, we need to tessellate
// also in the indeterminate state so we cannot just use a boolean comparison. See #1061
bool convex = bool(ps->convexValue()); // bool is true only if tribool is true, (not indeterminate and not false)
if (!convex) {
assert(ps->getDimension() == 3);
auto ps_tri = new PolySet(3, ps->convexValue());
ps_tri->setConvexity(ps->getConvexity());
PolysetUtils::tessellate_faces(*ps, *ps_tri);
this->root.reset(ps_tri);
}
}
}
smartCacheInsert(node, this->root);
return this->root;
}
return GeometryCache::instance()->get(key);
}
bool GeometryEvaluator::isValidDim(const Geometry::GeometryItem &item, unsigned int &dim) const {
if (!item.first->modinst->isBackground() && item.second) {
if (!dim) dim = item.second->getDimension();
else if (dim != item.second->getDimension() && !item.second->isEmpty()) {
LOG(message_group::Warning,item.first->modinst->location(),this->tree.getDocumentPath(),"Mixing 2D and 3D objects is not supported");
return false;
}
}
return true;
}
GeometryEvaluator::ResultObject GeometryEvaluator::applyToChildren(const AbstractNode &node, OpenSCADOperator op)
{
unsigned int dim = 0;
for(const auto &item : this->visitedchildren[node.index()]) {
if (!isValidDim(item, dim)) break;
}
if (dim == 2) return ResultObject(applyToChildren2D(node, op));
else if (dim == 3) return applyToChildren3D(node, op);
return ResultObject();
}
/*!
Applies the operator to all child nodes of the given node.
May return nullptr or any 3D Geometry object (can be either PolySet or CGAL_Nef_polyhedron)
*/
GeometryEvaluator::ResultObject GeometryEvaluator::applyToChildren3D(const AbstractNode &node, OpenSCADOperator op)
{
Geometry::Geometries children = collectChildren3D(node);
if (children.size() == 0) return ResultObject();
if (op == OpenSCADOperator::HULL) {
PolySet *ps = new PolySet(3, true);
if (CGALUtils::applyHull(children, *ps)) {
return ps;
}
delete ps;
return ResultObject();
}
// Only one child -> this is a noop
if (children.size() == 1) return ResultObject(children.front().second);
switch(op) {
case OpenSCADOperator::MINKOWSKI:
{
Geometry::Geometries actualchildren;
for(const auto &item : children) {
if (item.second && !item.second->isEmpty()) actualchildren.push_back(item);
}
if (actualchildren.empty()) return ResultObject();
if (actualchildren.size() == 1) return ResultObject(actualchildren.front().second);
return ResultObject(CGALUtils::applyMinkowski(actualchildren));
break;
}
case OpenSCADOperator::UNION:
{
Geometry::Geometries actualchildren;
for(const auto &item : children) {
if (item.second && !item.second->isEmpty()) actualchildren.push_back(item);
}
if (actualchildren.empty()) return ResultObject();
if (actualchildren.size() == 1) return ResultObject(actualchildren.front().second);
return ResultObject(CGALUtils::applyUnion3D(actualchildren.begin(), actualchildren.end()));
break;
}
default:
{
return ResultObject(CGALUtils::applyOperator3D(children, op));
break;
}
}
}
/*!
Apply 2D hull.
May return an empty geometry but will not return nullptr.
*/
Polygon2d *GeometryEvaluator::applyHull2D(const AbstractNode &node)
{
std::vector<const Polygon2d *> children = collectChildren2D(node);
Polygon2d *geometry = new Polygon2d();
typedef CGAL::Point_2<CGAL::Cartesian<double>> CGALPoint2;
// Collect point cloud
std::list<CGALPoint2> points;
for(const auto &p : children) {
if (p) {
for(const auto &o : p->outlines()) {
for(const auto &v : o.vertices) {
points.push_back(CGALPoint2(v[0], v[1]));
}
}
}
}
if (points.size() > 0) {
// Apply hull
std::list<CGALPoint2> result;
try {
CGAL::convex_hull_2(points.begin(), points.end(), std::back_inserter(result));
// Construct Polygon2d
Outline2d outline;
for(const auto &p : result) {
outline.vertices.push_back(Vector2d(p[0], p[1]));
}
geometry->addOutline(outline);
}
catch (const CGAL::Failure_exception &e) {
LOG(message_group::Warning,Location::NONE,"","GeometryEvaluator::applyHull2D() during CGAL::convex_hull_2(): %1$s",e.what());
}
}
return geometry;
}
Geometry *GeometryEvaluator::applyHull3D(const AbstractNode &node)
{
Geometry::Geometries children = collectChildren3D(node);
PolySet *P = new PolySet(3);
if (CGALUtils::applyHull(children, *P)) {
return P;
}
delete P;
return nullptr;
}
Polygon2d *GeometryEvaluator::applyMinkowski2D(const AbstractNode &node)
{
std::vector<const Polygon2d *> children = collectChildren2D(node);
if (!children.empty()) {
return ClipperUtils::applyMinkowski(children);
}
return nullptr;
}
/*!
Returns a list of Polygon2d children of the given node.
May return empty Polygon2d object, but not nullptr objects
*/
std::vector<const class Polygon2d *> GeometryEvaluator::collectChildren2D(const AbstractNode &node)
{
std::vector<const Polygon2d *> children;
for(const auto &item : this->visitedchildren[node.index()]) {
const AbstractNode *chnode = item.first;
const shared_ptr<const Geometry> &chgeom = item.second;
if (chnode->modinst->isBackground()) continue;
// NB! We insert into the cache here to ensure that all children of
// a node is a valid object. If we inserted as we created them, the
// cache could have been modified before we reach this point due to a large
// sibling object.
smartCacheInsert(*chnode, chgeom);
if (chgeom) {
if (chgeom->getDimension() == 3) {
LOG(message_group::Warning, item.first->modinst->location(), this->tree.getDocumentPath(), "Ignoring 3D child object for 2D operation");
children.push_back(nullptr); // replace 3D geometry with empty geometry
} else {
if (chgeom->isEmpty()) {
children.push_back(nullptr);
} else {
const Polygon2d *polygons = dynamic_cast<const Polygon2d *>(chgeom.get());
assert(polygons);
children.push_back(polygons);
}
}
} else {
children.push_back(nullptr);
}
}
return children;
}
/*!
Since we can generate both Nef and non-Nef geometry, we need to insert it into
the appropriate cache.
This method inserts the geometry into the appropriate cache if it's not already cached.
*/
void GeometryEvaluator::smartCacheInsert(const AbstractNode &node,
const shared_ptr<const Geometry> &geom)
{
const std::string &key = this->tree.getIdString(node);
shared_ptr<const CGAL_Nef_polyhedron> N = dynamic_pointer_cast<const CGAL_Nef_polyhedron>(geom);
if (N) {
if (!CGALCache::instance()->contains(key)) CGALCache::instance()->insert(key, N);
}
else {
if (!GeometryCache::instance()->contains(key)) {
if (!GeometryCache::instance()->insert(key, geom)) {
LOG(message_group::Warning,Location::NONE,"","GeometryEvaluator: Node didn't fit into cache.");
}
}
}
}
bool GeometryEvaluator::isSmartCached(const AbstractNode &node)
{
const std::string &key = this->tree.getIdString(node);
return (GeometryCache::instance()->contains(key) ||
CGALCache::instance()->contains(key));
}
shared_ptr<const Geometry> GeometryEvaluator::smartCacheGet(const AbstractNode &node, bool preferNef)
{
const std::string &key = this->tree.getIdString(node);
shared_ptr<const Geometry> geom;
bool hasgeom = GeometryCache::instance()->contains(key);
bool hascgal = CGALCache::instance()->contains(key);
if (hascgal && (preferNef || !hasgeom)) geom = CGALCache::instance()->get(key);
else if (hasgeom) geom = GeometryCache::instance()->get(key);
return geom;
}
/*!
Returns a list of 3D Geometry children of the given node.
May return empty geometries, but not nullptr objects
*/
Geometry::Geometries GeometryEvaluator::collectChildren3D(const AbstractNode &node)
{
Geometry::Geometries children;
for(const auto &item : this->visitedchildren[node.index()]) {
const AbstractNode *chnode = item.first;
const shared_ptr<const Geometry> &chgeom = item.second;
if (chnode->modinst->isBackground()) continue;
// NB! We insert into the cache here to ensure that all children of
// a node is a valid object. If we inserted as we created them, the
// cache could have been modified before we reach this point due to a large
// sibling object.
smartCacheInsert(*chnode, chgeom);
if (chgeom && chgeom->getDimension() == 2) {
LOG(message_group::Warning, item.first->modinst->location(), this->tree.getDocumentPath(), "Ignoring 2D child object for 3D operation");
children.push_back(std::make_pair(item.first, nullptr)); // replace 2D geometry with empty geometry
} else {
// Add children if geometry is 3D OR null/empty
children.push_back(item);
}
}
return children;
}
/*!
*/
Polygon2d *GeometryEvaluator::applyToChildren2D(const AbstractNode &node, OpenSCADOperator op)
{
node.progress_report();
if (op == OpenSCADOperator::MINKOWSKI) {
return applyMinkowski2D(node);
}
else if (op == OpenSCADOperator::HULL) {
return applyHull2D(node);
}
std::vector<const Polygon2d *> children = collectChildren2D(node);
if (children.empty()) {
return nullptr;
}
if (children.size() == 1) {
if (children[0]) {
return new Polygon2d(*children[0]); // Copy
} else {
return nullptr;
}
}
ClipperLib::ClipType clipType;
switch (op) {
case OpenSCADOperator::UNION:
clipType = ClipperLib::ctUnion;
break;
case OpenSCADOperator::INTERSECTION:
clipType = ClipperLib::ctIntersection;
break;
case OpenSCADOperator::DIFFERENCE:
clipType = ClipperLib::ctDifference;
break;
default:
LOG(message_group::Error,Location::NONE,"","Unknown boolean operation %1$d",int(op));
return nullptr;
break;
}
return ClipperUtils::apply(children, clipType);
}
/*!
Adds ourself to our parent's list of traversed children.
Call this for _every_ node which affects output during traversal.
Usually, this should be called from the postfix stage, but for some nodes,
we defer traversal letting other components (e.g. CGAL) render the subgraph,
and we'll then call this from prefix and prune further traversal.
The added geometry can be nullptr if it wasn't possible to evaluate it.
*/
void GeometryEvaluator::addToParent(const State &state,
const AbstractNode &node,
const shared_ptr<const Geometry> &geom)
{
this->visitedchildren.erase(node.index());
if (state.parent()) {
this->visitedchildren[state.parent()->index()].push_back(std::make_pair(&node, geom));
}
else {
// Root node
this->root = geom;
assert(this->visitedchildren.empty());
}
}
/*!
Custom nodes are handled here => implicit union
*/
Response GeometryEvaluator::visit(State &state, const AbstractNode &node)
{
if (state.isPrefix()) {
if (isSmartCached(node)) return Response::PruneTraversal;
state.setPreferNef(true); // Improve quality of CSG by avoiding conversion loss
}
if (state.isPostfix()) {
shared_ptr<const class Geometry> geom;
if (!isSmartCached(node)) {
geom = applyToChildren(node, OpenSCADOperator::UNION).constptr();
}
else {
geom = smartCacheGet(node, state.preferNef());
}
addToParent(state, node, geom);
node.progress_report();
}
return Response::ContinueTraversal;
}
/*!
Pass children to parent without touching them. Used by e.g. for loops
*/
Response GeometryEvaluator::visit(State &state, const ListNode &node)
{
if (state.parent()) {
if (state.isPrefix() && node.modinst->isBackground()) {
if (node.modinst->isBackground()) state.isBackground();
return Response::PruneTraversal;
}
if (state.isPostfix()) {
unsigned int dim = 0;
for(const auto &item : this->visitedchildren[node.index()]) {
if (!isValidDim(item, dim)) break;
const AbstractNode *chnode = item.first;
const shared_ptr<const Geometry> &chgeom = item.second;
addToParent(state, *chnode, chgeom);
}
this->visitedchildren.erase(node.index());
}
return Response::ContinueTraversal;
} else {
// Handle when a ListNode is given root modifier
return lazyEvaluateRootNode(state, node);
}
}
/*!
*/
Response GeometryEvaluator::visit(State &state, const GroupNode &node)
{
return visit(state, (const AbstractNode &)node);
}
Response GeometryEvaluator::lazyEvaluateRootNode(State &state, const AbstractNode& node) {
if (state.isPrefix()) {
if (node.modinst->isBackground()) {
state.isBackground();
return Response::PruneTraversal;
}
if (isSmartCached(node)) {
return Response::PruneTraversal;
}
}
if (state.isPostfix()) {
shared_ptr<const class Geometry> geom;
unsigned int dim = 0;
GeometryList::Geometries geometries;
for(const auto &item : this->visitedchildren[node.index()]) {
if (!isValidDim(item, dim)) break;
const AbstractNode *chnode = item.first;
const shared_ptr<const Geometry> &chgeom = item.second;
if (chnode->modinst->isBackground()) continue;
// NB! We insert into the cache here to ensure that all children of
// a node is a valid object. If we inserted as we created them, the
// cache could have been modified before we reach this point due to a large
// sibling object.
smartCacheInsert(*chnode, chgeom);
// Only use valid geometries
if (chgeom && !chgeom->isEmpty()) geometries.push_back(item);
}
if (geometries.size() == 1) geom = geometries.front().second;
else if (geometries.size() > 1) geom.reset(new GeometryList(geometries));
this->root = geom;
}
return Response::ContinueTraversal;
}
/*!
Root nodes are handled specially; they will flatten any child group
nodes to avoid doing an implicit top-level union.
NB! This is likely a temporary measure until a better implementation of
group nodes is in place.
*/
Response GeometryEvaluator::visit(State &state, const RootNode &node)
{
// If we didn't enable lazy unions, just union the top-level objects
if (!Feature::ExperimentalLazyUnion.is_enabled()) {
return visit(state, (const GroupNode &)node);
}
return lazyEvaluateRootNode(state, node);
}
Response GeometryEvaluator::visit(State &state, const OffsetNode &node)
{
if (state.isPrefix() && isSmartCached(node)) return Response::PruneTraversal;
if (state.isPostfix()) {
shared_ptr<const Geometry> geom;
if (!isSmartCached(node)) {
const Geometry *geometry = applyToChildren2D(node, OpenSCADOperator::UNION);
if (geometry) {
const Polygon2d *polygon = dynamic_cast<const Polygon2d*>(geometry);
// ClipperLib documentation: The formula for the number of steps in a full
// circular arc is ... Pi / acos(1 - arc_tolerance / abs(delta))
double n = Calc::get_fragments_from_r(std::abs(node.delta), node.fn, node.fs, node.fa);
double arc_tolerance = std::abs(node.delta) * (1 - cos_degrees(180 / n));
const Polygon2d *result = ClipperUtils::applyOffset(*polygon, node.delta, node.join_type, node.miter_limit, arc_tolerance);
assert(result);
geom.reset(result);
delete geometry;
}
}
else {
geom = smartCacheGet(node, false);
}
addToParent(state, node, geom);
node.progress_report();
}
return Response::ContinueTraversal;
}
/*!
RenderNodes just pass on convexity
*/
Response GeometryEvaluator::visit(State &state, const RenderNode &node)
{
if (state.isPrefix()) {
if (isSmartCached(node)) return Response::PruneTraversal;
state.setPreferNef(true); // Improve quality of CSG by avoiding conversion loss
}
if (state.isPostfix()) {
shared_ptr<const class Geometry> geom;
if (!isSmartCached(node)) {
ResultObject res = applyToChildren(node, OpenSCADOperator::UNION);
geom = res.constptr();
if (shared_ptr<const PolySet> ps = dynamic_pointer_cast<const PolySet>(geom)) {
// If we got a const object, make a copy
shared_ptr<PolySet> newps;
if (res.isConst()) newps.reset(new PolySet(*ps));
else newps = dynamic_pointer_cast<PolySet>(res.ptr());
newps->setConvexity(node.convexity);
geom = newps;
}
else if (shared_ptr<const CGAL_Nef_polyhedron> N = dynamic_pointer_cast<const CGAL_Nef_polyhedron>(geom)) {
// If we got a const object, make a copy
shared_ptr<CGAL_Nef_polyhedron> newN;
if (res.isConst()) newN.reset((CGAL_Nef_polyhedron*)N->copy());
else newN = dynamic_pointer_cast<CGAL_Nef_polyhedron>(res.ptr());
newN->setConvexity(node.convexity);
geom = newN;
}
}
else {
geom = smartCacheGet(node, state.preferNef());
}
node.progress_report();
addToParent(state, node, geom);
}
return Response::ContinueTraversal;
}
/*!
Leaf nodes can create their own geometry, so let them do that
input: None
output: PolySet or Polygon2d
*/
Response GeometryEvaluator::visit(State &state, const LeafNode &node)
{
if (state.isPrefix()) {
shared_ptr<const Geometry> geom;
if (!isSmartCached(node)) {
const Geometry *geometry = node.createGeometry();
assert(geometry);
if (const Polygon2d *polygon = dynamic_cast<const Polygon2d*>(geometry)) {
if (!polygon->isSanitized()) {
Polygon2d *p = ClipperUtils::sanitize(*polygon);
delete geometry;
geometry = p;
}
}
geom.reset(geometry);
}
else geom = smartCacheGet(node, state.preferNef());
addToParent(state, node, geom);
node.progress_report();
}
return Response::PruneTraversal;
}
Response GeometryEvaluator::visit(State &state, const TextNode &node)
{
if (state.isPrefix()) {
shared_ptr<const Geometry> geom;
if (!isSmartCached(node)) {
std::vector<const Geometry *> geometrylist = node.createGeometryList();
std::vector<const Polygon2d *> polygonlist;
for(const auto &geometry : geometrylist) {
const Polygon2d *polygon = dynamic_cast<const Polygon2d*>(geometry);
assert(polygon);
polygonlist.push_back(polygon);
}
geom.reset(ClipperUtils::apply(polygonlist, ClipperLib::ctUnion));
}
else geom = GeometryCache::instance()->get(this->tree.getIdString(node));
addToParent(state, node, geom);
node.progress_report();
}
return Response::PruneTraversal;
}
/*!
input: List of 2D or 3D objects (not mixed)
output: Polygon2d or 3D PolySet
operation:
o Perform csg op on children
*/
Response GeometryEvaluator::visit(State &state, const CsgOpNode &node)
{
if (state.isPrefix()) {
if (isSmartCached(node)) return Response::PruneTraversal;
state.setPreferNef(true); // Improve quality of CSG by avoiding conversion loss
}
if (state.isPostfix()) {
shared_ptr<const Geometry> geom;
if (!isSmartCached(node)) {
geom = applyToChildren(node, node.type).constptr();
}
else {
geom = smartCacheGet(node, state.preferNef());
}
addToParent(state, node, geom);
node.progress_report();
}
return Response::ContinueTraversal;
}
/*!
input: List of 2D or 3D objects (not mixed)
output: Polygon2d or 3D PolySet
operation:
o Union all children
o Perform transform
*/
Response GeometryEvaluator::visit(State &state, const TransformNode &node)
{
if (state.isPrefix() && isSmartCached(node)) return Response::PruneTraversal;
if (state.isPostfix()) {
shared_ptr<const class Geometry> geom;
if (!isSmartCached(node)) {
if (matrix_contains_infinity(node.matrix) || matrix_contains_nan(node.matrix)) {
// due to the way parse/eval works we can't currently distinguish between NaN and Inf
LOG(message_group::Warning,node.modinst->location(),this->tree.getDocumentPath(),"Transformation matrix contains Not-a-Number and/or Infinity - removing object.");
}
else {
// First union all children
ResultObject res = applyToChildren(node, OpenSCADOperator::UNION);
if ((geom = res.constptr())) {
if (geom->getDimension() == 2) {
shared_ptr<const Polygon2d> polygons = dynamic_pointer_cast<const Polygon2d>(geom);
assert(polygons);
// If we got a const object, make a copy
shared_ptr<Polygon2d> newpoly;
if (res.isConst()) newpoly.reset(new Polygon2d(*polygons));
else newpoly = dynamic_pointer_cast<Polygon2d>(res.ptr());
Transform2d mat2;
mat2.matrix() <<
node.matrix(0,0), node.matrix(0,1), node.matrix(0,3),
node.matrix(1,0), node.matrix(1,1), node.matrix(1,3),
node.matrix(3,0), node.matrix(3,1), node.matrix(3,3);
newpoly->transform(mat2);
// A 2D transformation may flip the winding order of a polygon.
// If that happens with a sanitized polygon, we need to reverse
// the winding order for it to be correct.
if (newpoly->isSanitized() && mat2.matrix().determinant() <= 0) {
geom.reset(ClipperUtils::sanitize(*newpoly));
}
}
else if (geom->getDimension() == 3) {
shared_ptr<const PolySet> ps = dynamic_pointer_cast<const PolySet>(geom);
if (ps) {
// If we got a const object, make a copy
shared_ptr<PolySet> newps;
if (res.isConst()) newps.reset(new PolySet(*ps));
else newps = dynamic_pointer_cast<PolySet>(res.ptr());
newps->transform(node.matrix);
geom = newps;
}
else {
shared_ptr<const CGAL_Nef_polyhedron> N = dynamic_pointer_cast<const CGAL_Nef_polyhedron>(geom);
assert(N);
// If we got a const object, make a copy
shared_ptr<CGAL_Nef_polyhedron> newN;
if (res.isConst()) newN.reset((CGAL_Nef_polyhedron*)N->copy());
else newN = dynamic_pointer_cast<CGAL_Nef_polyhedron>(res.ptr());
newN->transform(node.matrix);
geom = newN;
}
}
}
}
}
else {
geom = smartCacheGet(node, state.preferNef());
}
addToParent(state, node, geom);
node.progress_report();
}
return Response::ContinueTraversal;
}
static void translate_PolySet(PolySet &ps, const Vector3d &translation)
{
for(auto &p : ps.polygons) {
for(auto &v : p) {
v += translation;
}
}
}
/*
Compare Euclidean length of vectors
Return:
-1 : if v1 < v2
0 : if v1 ~= v2 (approximation to compoensate for floating point precision)
1 : if v1 > v2
*/
int sgn_vdiff(const Vector2d &v1, const Vector2d &v2) {
constexpr double ratio_threshold = 1e5; // 10ppm difference
double l1 = v1.norm();
double l2 = v2.norm();
// Compare the average and difference, to be independent of geometry scale.
// If the difference is within ratio_threshold of the avg, treat as equal.
double scale = (l1+l2);
double diff = 2*std::fabs(l1-l2)*ratio_threshold;
return diff > scale ? (l1 < l2 ? -1 : 1) : 0;
}
/*
Enable/Disable experimental 4-way split quads for linear_extrude, with added midpoint.
These look very nice when(and only when) diagonals are near equal.
This typically happens when an edge is colinear with the origin.
*/
//#define LINEXT_4WAY
/*
Attempt to triangulate quads in an ideal way.
Each quad is composed of two adjacent outline vertices: (prev1, curr1)
and their corresponding transformed points one step up: (prev2, curr2).
Quads are triangulated across the shorter of the two diagonals, which works well in most cases.
However, when diagonals are equal length, decision may flip depending on other factors.
*/
static void add_slice(PolySet *ps, const Polygon2d &poly,
double rot1, double rot2,
double h1, double h2,
const Vector2d &scale1,
const Vector2d &scale2)
{
Eigen::Affine2d trans1(Eigen::Scaling(scale1) * Eigen::Affine2d(rotate_degrees(-rot1)));
Eigen::Affine2d trans2(Eigen::Scaling(scale2) * Eigen::Affine2d(rotate_degrees(-rot2)));
#ifdef LINEXT_4WAY
Eigen::Affine2d trans_mid(Eigen::Scaling((scale1+scale2)/2) * Eigen::Affine2d(rotate_degrees(-(rot1+rot2)/2)));
bool is_straight = rot1==rot2 && scale1[0]==scale1[1] && scale2[0]==scale2[1];
#endif
bool any_zero = scale2[0] == 0 || scale2[1] == 0;
bool any_non_zero = scale2[0] != 0 || scale2[1] != 0;
// Not likely to matter, but when no twist (rot2 == rot1),
// setting back_twist true helps keep diagonals same as previous builds.
bool back_twist = rot2 <= rot1;
for(const auto &o : poly.outlines()) {
Vector2d prev1 = trans1 * o.vertices[0];
Vector2d prev2 = trans2 * o.vertices[0];
// For equal length diagonals, flip selected choice depending on direction of twist and
// whether the outline is negative (eg circle hole inside a larger circle).
// This was tested against circles with a single point touching the origin,
// and extruded with twist. Diagonal choice determined by whichever option
// matched the direction of diagonal for neighboring edges (which did not exhibit "equal" diagonals).
bool flip = ((!o.positive) xor (back_twist));
for (size_t i=1;i<=o.vertices.size();++i) {
Vector2d curr1 = trans1 * o.vertices[i % o.vertices.size()];
Vector2d curr2 = trans2 * o.vertices[i % o.vertices.size()];
int diff_sign = sgn_vdiff(prev1 - curr2, curr1 - prev2);
bool splitfirst = diff_sign == -1 || (diff_sign == 0 && !flip);
#ifdef LINEXT_4WAY
// Diagonals should be equal whenever an edge is co-linear with the origin (edge itself need not touch it)
if (!is_straight && diff_sign == 0) {
// Split into 4 triangles, with an added midpoint.
//Vector2d mid_prev = trans3 * (prev1 +curr1+curr2)/4;
Vector2d mid = trans_mid * (o.vertices[(i-1) % o.vertices.size()] + o.vertices[i % o.vertices.size()])/2;
double h_mid = (h1+h2)/2;
ps->append_poly();
ps->insert_vertex(prev1[0], prev1[1], h1);
ps->insert_vertex( mid[0], mid[1], h_mid);
ps->insert_vertex(curr1[0], curr1[1], h1);
ps->append_poly();
ps->insert_vertex(curr1[0], curr1[1], h1);
ps->insert_vertex( mid[0], mid[1], h_mid);
ps->insert_vertex(curr2[0], curr2[1], h2);
ps->append_poly();
ps->insert_vertex(curr2[0], curr2[1], h2);
ps->insert_vertex( mid[0], mid[1], h_mid);
ps->insert_vertex(prev2[0], prev2[1], h2);
ps->append_poly();
ps->insert_vertex(prev2[0], prev2[1], h2);
ps->insert_vertex( mid[0], mid[1], h_mid);
ps->insert_vertex(prev1[0], prev1[1], h1);
} else
#endif
// Split along shortest diagonal,
// unless at top for a 0-scaled axis (which can create 0 thickness "ears")
if (splitfirst xor any_zero) {
ps->append_poly();
ps->insert_vertex(prev1[0], prev1[1], h1);
ps->insert_vertex(curr2[0], curr2[1], h2);
ps->insert_vertex(curr1[0], curr1[1], h1);
if (!any_zero || (any_non_zero && prev2 != curr2)) {
ps->append_poly();
ps->insert_vertex(curr2[0], curr2[1], h2);
ps->insert_vertex(prev1[0], prev1[1], h1);
ps->insert_vertex(prev2[0], prev2[1], h2);
}
} else {
ps->append_poly();
ps->insert_vertex(prev1[0], prev1[1], h1);
ps->insert_vertex(prev2[0], prev2[1], h2);
ps->insert_vertex(curr1[0], curr1[1], h1);
if (!any_zero || (any_non_zero && prev2 != curr2)) {
ps->append_poly();
ps->insert_vertex(prev2[0], prev2[1], h2);
ps->insert_vertex(curr2[0], curr2[1], h2);
ps->insert_vertex(curr1[0], curr1[1], h1);
}
}
prev1 = curr1;
prev2 = curr2;
}
}
}
// Insert vertices for segments interpolated between v0 and v1.
// The last vertex (t==1) is not added here to avoid duplicate vertices,
// since it will be the first vertex of the *next* edge.
static void add_segmented_edge(Outline2d& o, const Vector2d& v0, const Vector2d& v1, unsigned int edge_segments) {
for (unsigned int j = 0; j < edge_segments; ++j) {
double t = static_cast<double>(j) / edge_segments;
o.vertices.push_back((1 - t) * v0 + t * v1);
}
}
// For each edge in original outline, find its max length over all slice transforms,
// and divide into segments no longer than fs.
static Outline2d splitOutlineByFs(
const Outline2d &o,
const double twist, const double scale_x, const double scale_y,
const double fs, unsigned int slices)
{
const auto sz = o.vertices.size();
Vector2d v0 = o.vertices[0];
Outline2d o2;
o2.positive = o.positive;
// non-uniform scaling requires iterating over each slice transform
// to find maximum length of a given edge.
if (scale_x != scale_y)
{
for (size_t i = 1; i <= sz; ++i)
{
Vector2d v1 = o.vertices[i % sz];
double max_edgelen = 0.0; // max length for single edge over all transformed slices
for (unsigned int j = 0; j <= slices; j++)
{
double t = static_cast<double>(j) / slices;
Vector2d scale(Calc::lerp(1, scale_x, t), Calc::lerp(1, scale_y, t));
double rot = twist * t;
Eigen::Affine2d trans(Eigen::Scaling(scale) * Eigen::Affine2d(rotate_degrees(-rot)));
double edgelen = (trans * v1 - trans * v0).norm();
max_edgelen = std::max(max_edgelen, edgelen);
}
unsigned int edge_segments = static_cast<unsigned int>(std::ceil(max_edgelen / fs));
add_segmented_edge(o2, v0, v1, edge_segments);
v0 = v1;
}
} else { // uniform scaling
double max_scale = std::max(scale_x, 1.0);
for (size_t i = 1; i <= sz; ++i)
{
Vector2d v1 = o.vertices[i % sz];
unsigned int edge_segments = static_cast<unsigned int>(std::ceil((v1-v0).norm() * max_scale / fs));
add_segmented_edge(o2, v0, v1, edge_segments);
v0 = v1;
}
}
return o2;
}
// While total outline segments < fn, increment segment_count for edge with largest
// (max_edge_length / segment_count).
static Outline2d splitOutlineByFn(
const Outline2d &o,
const double twist, const double scale_x, const double scale_y,
const double fn, unsigned int slices)
{
struct segment_tracker {
size_t edge_index;
double max_edgelen;
unsigned int segment_count;
segment_tracker(size_t i, double len) : edge_index(i), max_edgelen(len), segment_count(1u) { }
// metric for comparison: average between (max segment length, and max segment length after split)
double metric() const { return max_edgelen / (segment_count + 0.5); }
bool operator<(const segment_tracker& rhs) const { return this->metric() < rhs.metric(); }
bool close_match(const segment_tracker &other) const {
// Edges are grouped when metrics match by at least 99.9%
constexpr double APPROX_EQ_RATIO = 0.999;
double l1 = this->metric(), l2 = other.metric();
return std::min(l1, l2) / std::max(l1, l2) >= APPROX_EQ_RATIO;
}
};
const auto sz = o.vertices.size();
std::vector<unsigned int> segment_counts(sz, 1);
std::priority_queue<segment_tracker, std::vector<segment_tracker>> q;
Vector2d v0 = o.vertices[0];
// non-uniform scaling requires iterating over each slice transform
// to find maximum length of a given edge.
if (scale_x != scale_y)
{
for (size_t i = 1; i <= sz; ++i)
{
Vector2d v1 = o.vertices[i % sz];
double max_edgelen = 0.0; // max length for single edge over all transformed slices
for (unsigned int j = 0; j <= slices; j++)
{
double t = static_cast<double>(j) / slices;
Vector2d scale(Calc::lerp(1, scale_x, t), Calc::lerp(1, scale_y, t));
double rot = twist * t;
Eigen::Affine2d trans(Eigen::Scaling(scale) * Eigen::Affine2d(rotate_degrees(-rot)));
double edgelen = (trans * v1 - trans * v0).norm();
max_edgelen = std::max(max_edgelen, edgelen);
}
q.emplace(i-1, max_edgelen);
v0 = v1;
}
} else { // uniform scaling
double max_scale = std::max(scale_x, 1.0);
for (size_t i = 1; i <= sz; ++i)
{
Vector2d v1 = o.vertices[i % sz];
double max_edgelen = (v1-v0).norm() * max_scale;
q.emplace(i-1, max_edgelen);
v0 = v1;
}
}
std::vector<segment_tracker> tmp_q;
// Process priority_queue until number of segments is reached.