FreeCAD

WireJoiner.cpp
3185 строк · 109.4 Кб
Перенос по словам
1
/****************************************************************************
2
 *   Copyright (c) 2022 Zheng Lei (realthunder) <realthunder.dev@gmail.com> *
3
 *                                                                          *
4
 *   This file is part of the FreeCAD CAx development system.               *
5
 *                                                                          *
6
 *   This library is free software; you can redistribute it and/or          *
7
 *   modify it under the terms of the GNU Library General Public            *
8
 *   License as published by the Free Software Foundation; either           *
9
 *   version 2 of the License, or (at your option) any later version.       *
10
 *                                                                          *
11
 *   This library  is distributed in the hope that it will be useful,       *
12
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of         *
13
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          *
14
 *   GNU Library General Public License for more details.                   *
15
 *                                                                          *
16
 *   You should have received a copy of the GNU Library General Public      *
17
 *   License along with this library; see the file COPYING.LIB. If not,     *
18
 *   write to the Free Software Foundation, Inc., 59 Temple Place,          *
19
 *   Suite 330, Boston, MA  02111-1307, USA                                 *
20
 *                                                                          *
21
 ****************************************************************************/
22

23
#include "PreCompiled.h"
24
#include <boost/core/ignore_unused.hpp>
25
#include <boost/geometry/geometries/register/point.hpp>
26
#include <boost/graph/graph_concepts.hpp>
27

28
#ifndef _PreComp_
29
# include <BRepLib.hxx>
30
# include <BRep_Builder.hxx>
31
# include <BRep_Tool.hxx>
32
# include <BRepBndLib.hxx>
33
# include <BRepBuilderAPI_Copy.hxx>
34
# include <BRepBuilderAPI_MakeEdge.hxx>
35
# include <BRepBuilderAPI_MakeWire.hxx>
36
# include <BRepBuilderAPI_MakeFace.hxx>
37
# include <BRepClass_FaceClassifier.hxx>
38
# include <BRepExtrema_DistShapeShape.hxx>
39
# include <BRepGProp.hxx>
40
# include <BRepTools.hxx>
41
# include <BRepTools_WireExplorer.hxx>
42
# include <gp_Pln.hxx>
43
# include <GeomAdaptor_Curve.hxx>
44
# include <GeomLProp_CLProps.hxx>
45
# include <GProp_GProps.hxx>
46
# include <ShapeAnalysis_Wire.hxx>
47
# include <ShapeFix_ShapeTolerance.hxx>
48
# include <ShapeExtend_WireData.hxx>
49
# include <ShapeFix_Wire.hxx>
50
# include <ShapeFix_Shape.hxx>
51
# include <TopExp.hxx>
52
# include <TopExp_Explorer.hxx>
53
# include <TopTools_HSequenceOfShape.hxx>
54
#endif
55

56
#include <BRepTools_History.hxx>
57
#include <ShapeBuild_ReShape.hxx>
58

59
#include <unordered_map>
60
#include <unordered_set>
61
#include <deque>
62
#include <boost_geometry.hpp>
63
#include <utility>
64

65
#include <Base/Console.h>
66
#include <Base/Exception.h>
67
#include <Base/Tools.h>
68
#include <Base/Sequencer.h>
69
#include <Base/Parameter.h>
70
#include <App/Application.h>
71

72
#include "WireJoiner.h"
73

74
#include "Geometry.h"
75
#include "PartFeature.h"
76
#include "TopoShapeOpCode.h"
77
#include "TopoShapeMapper.h"
78

79
namespace bg = boost::geometry;
80
namespace bgi = boost::geometry::index;
81

82
const size_t RParametersNumber = 16UL;
83
using RParameters = bgi::linear<RParametersNumber>;
84

85
BOOST_GEOMETRY_REGISTER_POINT_3D_GET_SET(
86
        gp_Pnt,double,bg::cs::cartesian,X,Y,Z,SetX,SetY,SetZ)
87

88
FC_LOG_LEVEL_INIT("WireJoiner",true, true)
89

90
using namespace Part;
91

92
static inline void getEndPoints(const TopoDS_Edge &eForEndPoints, gp_Pnt &p1, gp_Pnt &p2) {
93
    p1 = BRep_Tool::Pnt(TopExp::FirstVertex(eForEndPoints));
94
    p2 = BRep_Tool::Pnt(TopExp::LastVertex(eForEndPoints));
95
}
96

97
static inline void getEndPoints(const TopoDS_Wire &wire, gp_Pnt &p1, gp_Pnt &p2) {
98
    BRepTools_WireExplorer xp(wire);
99
    p1 = BRep_Tool::Pnt(TopoDS::Vertex(xp.CurrentVertex()));
100
    for(;xp.More();xp.Next()) {};
101
    p2 = BRep_Tool::Pnt(TopoDS::Vertex(xp.CurrentVertex()));
102
}
103

104
// Originally here there was the definition of the precompiler macro assertCheck() and of the method
105
// _assertCheck(), that have been replaced with the already defined precompiler macro assert().
106
// See
107
// https://github.com/realthunder/FreeCAD/blob/6f15849be2505f98927e75d0e8352185e14e7b72/src/Mod/Part/App/WireJoiner.cpp#L107
108
// for reference and https://github.com/FreeCAD/FreeCAD/pull/12535/files#r1526647457 for the
109
// discussion about replacing it
110

111
class WireJoiner::WireJoinerP {
112
public:
113
    double myTol = Precision::Confusion();
114
    double myTol2 = myTol * myTol;
115
    double myAngularTol = Precision::Angular();
116
    bool doSplitEdge = true;
117
    bool doMergeEdge = true;
118
    bool doOutline = false;
119
    bool doTightBound = true;
120

121
    std::string catchObject;
122
    int catchIteration {};
123
    int iteration = 0;
124

125
    using Box = bg::model::box<gp_Pnt>;
126

127
    bool checkBBox(const Bnd_Box &box) const
128
    {
129
        if (box.IsVoid()) {
130
            return false;
131
        }
132
        Standard_Real xMin = Standard_Real();
133
        Standard_Real yMin = Standard_Real();
134
        Standard_Real zMin = Standard_Real();
135
        Standard_Real xMax = Standard_Real();
136
        Standard_Real yMax = Standard_Real();
137
        Standard_Real zMax = Standard_Real();
138
        box.Get(xMin, yMin, zMin, xMax, yMax, zMax);
139
        return zMax - zMin <= myTol;
140
    }
141

142
    WireJoinerP()
143
        : catchObject(App::GetApplication()
144
                          .GetParameterGroupByPath("User parameter:BaseApp/Preferences/WireJoiner")
145
                          ->GetASCII("ObjectName"))
146
        , catchIteration(static_cast<int>(
147
              App::GetApplication()
148
                  .GetParameterGroupByPath("User parameter:BaseApp/Preferences/WireJoiner")
149
                  ->GetInt("Iteration", 0)))
150
    {}
151

152
    bool getBBox(const TopoDS_Shape &eForBBox, Bnd_Box &bound) {
153
        BRepBndLib::AddOptimal(eForBBox,bound,Standard_False);
154
        if (bound.IsVoid()) {
155
            if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_LOG)) {
156
                FC_WARN("failed to get bound of edge");
157
            }
158
            return false;
159
        }
160
        if (!checkBBox(bound)) {
161
            showShape(eForBBox, "invalid");
162
        }
163
        if (bound.SquareExtent() < myTol2) {
164
            return false;
165
        }
166
        bound.Enlarge(myTol);
167
        return true;
168
    }
169

170
    bool getBBox(const TopoDS_Shape &eForBBox, Box &box) {
171
        Bnd_Box bound;
172
        if (!getBBox(eForBBox, bound)) {
173
            return false;
174
        }
175
        Standard_Real xMin = Standard_Real();
176
        Standard_Real yMin = Standard_Real();
177
        Standard_Real zMin = Standard_Real();
178
        Standard_Real xMax = Standard_Real();
179
        Standard_Real yMax = Standard_Real();
180
        Standard_Real zMax = Standard_Real();
181
        bound.Get(xMin, yMin, zMin, xMax, yMax, zMax);
182
        box = Box(gp_Pnt(xMin,yMin,zMin), gp_Pnt(xMax,yMax,zMax));
183
        return true;
184
    }
185

186
    struct WireInfo;
187
    struct EdgeSet;
188

189
    struct EdgeInfo {
190
        TopoDS_Edge edge;
191
        TopoDS_Wire superEdge;
192
        mutable TopoDS_Shape edgeReversed;
193
        mutable TopoDS_Shape superEdgeReversed;
194
        gp_Pnt p1;
195
        gp_Pnt p2;
196
        gp_Pnt mid;
197
        Box box;
198
        std::array<int, 2> iStart {};  // adjacent list index start for p1 and p2
199
        std::array<int, 2> iEnd {};    // adjacent list index end
200
        int iteration {};
201
        int iteration2 {};
202
        bool queryBBox;
203
        std::shared_ptr<WireInfo> wireInfo {};
204
        std::shared_ptr<WireInfo> wireInfo2 {}; // an edge can be shared by at most two tight bound wires.
205
        std::unique_ptr<Geometry> geo {};
206
        Standard_Real firstParam {};
207
        Standard_Real lastParam {};
208
        Handle_Geom_Curve curve;
209
        GeomAbs_CurveType type {};
210
        bool isLinear;
211

212
        EdgeInfo(const TopoDS_Edge& eForInfo,
213
                 const gp_Pnt& pt1,
214
                 const gp_Pnt& pt2,
215
                 const Box& bound,
216
                 bool bbox,
217
                 bool isLinear)
218
            : edge(eForInfo)
219
            , p1(pt1)
220
            , p2(pt2)
221
            , box(bound)
222
            , queryBBox(bbox)
223
            , isLinear(isLinear)
224
        {
225
            curve = BRep_Tool::Curve(eForInfo, firstParam, lastParam);
226
            type = GeomAdaptor_Curve(curve).GetType();
227

228
            // Originally here there was a call to the precompiler macro assertCheck(), which has
229
            // been replaced with the precompiler macro assert()
230

231
            assert(!curve.IsNull());
232
            const double halving {0.5};
233
            GeomLProp_CLProps prop(curve,(firstParam+lastParam)*halving,0,Precision::Confusion());
234
            mid = prop.Value();
235

236
            reset();
237
        }
238
        Geometry *geometry() {
239
            if (!geo) {
240
                geo = Geometry::fromShape(edge, /*silent*/ true);
241
            }
242
            return geo.get();
243
        }
244
        void reset() {
245
            wireInfo.reset();
246
            wireInfo2.reset();
247
            if (iteration >= 0) {
248
                iteration = 0;
249
            }
250
            iteration2 = 0;
251
            iStart[0] = iStart[1] = iEnd[0] = iEnd[1] = -1;
252
        }
253
        const TopoDS_Shape &shape(bool forward=true) const
254
        {
255
            if (superEdge.IsNull()) {
256
                if (forward) {
257
                    return edge;
258
                }
259
                if (edgeReversed.IsNull()) {
260
                    edgeReversed = edge.Reversed();
261
                }
262
                return edgeReversed;
263
            }
264
            if (forward) {
265
                return superEdge;
266
            }
267
            if (superEdgeReversed.IsNull()) {
268
                superEdgeReversed = superEdge.Reversed();
269
            }
270
            return superEdgeReversed;
271
        }
272
        TopoDS_Wire wire() const
273
        {
274
            auto sForWire = shape();
275
            if (sForWire.ShapeType() == TopAbs_WIRE) {
276
                return TopoDS::Wire(sForWire);
277
            }
278
            return BRepBuilderAPI_MakeWire(TopoDS::Edge(sForWire)).Wire();
279
        }
280
    };
281

282
    template<class T>
283
    struct VectorSet {
284
        void sort()
285
        {
286
            if (!sorted) {
287
                sorted = true;
288
                std::sort(data.begin(), data.end());
289
            }
290
        }
291
        bool contains(const T &vForContains)
292
        {
293
            if (!sorted) {
294
                const size_t dataSizeMax = 30;
295
                if (data.size() < dataSizeMax) {
296
                    return std::find(data.begin(), data.end(), vForContains) != data.end();
297
                }
298
                sort();
299
            }
300
            auto it = std::lower_bound(data.begin(), data.end(), vForContains);
301
            return it!=data.end() && *it == vForContains;
302
        }
303
        bool intersects(const VectorSet<T> &other)
304
        {
305
            if (other.size() < size()) {
306
                return other.intersects(*this);
307
            }
308
            if (!sorted) {
309
                for (const auto &vector : data) {
310
                    if (other.contains(vector)) {
311
                        return true;
312
                    }
313
                }
314
            }
315
            else {
316
                other.sort();
317
                auto it = other.data.begin();
318
                for (const auto &vertex : data) {
319
                    it = std::lower_bound(it, other.data.end(), vertex);
320
                    if (it == other.data.end()) {
321
                        return false;
322
                    }
323
                    if (*it == vertex) {
324
                        return true;
325
                    }
326
                }
327
            }
328
            return false;
329
        }
330
        void insert(const T &vToInsert)
331
        {
332
            if (sorted) {
333
                data.insert(std::upper_bound(data.begin(), data.end(), vToInsert), vToInsert);
334
            }
335
            else {
336
                data.push_back(vToInsert);
337
            }
338
        }
339
        bool insertUnique(const T &vToInsertUnique)
340
        {
341
            if (sorted) {
342
                auto it = std::lower_bound(data.begin(), data.end(), vToInsertUnique);
343
                bool insert = !(it != data.end() && *it == vToInsertUnique);
344
                if (insert) {
345
                    data.insert(it, vToInsertUnique);
346
                }
347
                return insert;
348
            }
349

350
            if (contains(vToInsertUnique)) {
351
                return false;
352
            }
353
            data.push_back(vToInsertUnique);
354
            return true;
355
        }
356
        void erase(const T &vToErase)
357
        {
358
            if (!sorted) {
359
                data.erase(std::remove(data.begin(), data.end(), vToErase), data.end());
360
            }
361
            else {
362
                auto it = std::lower_bound(data.begin(), data.end(), vToErase);
363
                auto itEnd = it;
364
                while (itEnd != data.end() && *itEnd == vToErase) {
365
                    ++itEnd;
366
                }
367
                data.erase(it, itEnd);
368
            }
369
            const size_t dataSizeMax = 20;
370
            if (data.size() < dataSizeMax) {
371
                sorted = false;
372
            }
373
        }
374
        void clear()
375
        {
376
            data.clear();
377
            sorted = false;
378
        }
379
        std::size_t size() const
380
        {
381
            return data.size();
382
        }
383
        bool empty() const
384
        {
385
            return data.empty();
386
        }
387
    private:
388
        bool sorted = false;
389
        std::vector<T> data {};
390
    };
391

392
    Handle(BRepTools_History) aHistory = new BRepTools_History;
393

394
    using Edges = std::list<EdgeInfo>;
395
    Edges edges {};
396

397
    std::map<EdgeInfo*, Edges::iterator> edgesTable {};
398

399
    struct VertexInfo {
400
        Edges::iterator it {};
401
        bool start {};
402
        VertexInfo() = default;
403
        VertexInfo(Edges::iterator it, bool start)
404
            :it(it),start(start)
405
        {}
406
        VertexInfo reversed() const {
407
            return {it, !start};
408
        }
409
        bool operator==(const VertexInfo &other) const {
410
            return it==other.it && start==other.start;
411
        }
412
        bool operator<(const VertexInfo &other) const {
413
            auto thisInfo = edgeInfo();
414
            auto otherInfo = other.edgeInfo();
415
            if (thisInfo < otherInfo) {
416
                return true;
417
            }
418
            if (thisInfo > otherInfo) {
419
                return false;
420
            }
421
            return static_cast<int>(start) < static_cast<int>(other.start);
422
        }
423
        const gp_Pnt &pt() const {
424
            return start?it->p1:it->p2;
425
        }
426
        gp_Pnt &pt() {
427
            return start?it->p1:it->p2;
428
        }
429
        const gp_Pnt &ptOther() const {
430
            return start?it->p2:it->p1;
431
        }
432
        gp_Pnt &ptOther() {
433
            return start?it->p2:it->p1;
434
        }
435
        TopoDS_Vertex vertex() const {
436
            return start ? TopExp::FirstVertex(edge()) : TopExp::LastVertex(edge());
437
        }
438
        TopoDS_Vertex otherVertex() const {
439
            return start ? TopExp::LastVertex(edge()) : TopExp::FirstVertex(edge());
440
        }
441
        EdgeInfo *edgeInfo() const {
442
            return &(*it);
443
        }
444
        const TopoDS_Edge &edge() const {
445
            return it->edge;
446
        }
447
    };
448

449
    struct StackInfo {
450
        size_t iStart;
451
        size_t iEnd;
452
        size_t iCurrent;
453
        explicit StackInfo(size_t idx = 0)
454
            : iStart(idx)
455
            , iEnd(idx)
456
            , iCurrent(idx)
457
        {}
458
    };
459

460
    std::vector<StackInfo> stack {};
461
    std::vector<VertexInfo> vertexStack {};
462
    std::vector<VertexInfo> tmpVertices {};
463
    std::vector<VertexInfo> adjacentList {};
464

465
    struct WireInfo {
466
        std::vector<VertexInfo> vertices {};
467
        mutable std::vector<int> sorted {};
468
        TopoDS_Wire wire;
469
        TopoDS_Face face;
470
        mutable Bnd_Box box;
471
        bool done = false;
472
        bool purge = false;
473

474
        void sort() const
475
        {
476
            if (sorted.size() == vertices.size()) {
477
                return;
478
            }
479

480
            // Originally here there was a call to the precompiler macro assertCheck(), which has
481
            // been replaced with the precompiler macro assert()
482

483
            assert(sorted.size() < vertices.size());
484
            sorted.reserve(vertices.size());
485
            for (int i = (int)sorted.size(); i < (int)vertices.size(); ++i) {
486
                sorted.push_back(i);
487
            }
488
            std::sort(sorted.begin(), sorted.end(), [&](int vA, int vB) {
489
                return vertices[vA] < vertices[vB];
490
            });
491
        }
492
        int find(const VertexInfo &info) const
493
        {
494
            const size_t verticesSizeMax = 20;
495
            if (vertices.size() < verticesSizeMax) {
496
                auto it = std::find(vertices.begin(), vertices.end(), info);
497
                if (it == vertices.end()) {
498
                    return 0;
499
                }
500
                return (static_cast<int>(it - vertices.begin()) + 1);
501
            }
502
            sort();
503
            auto it = std::lower_bound(sorted.begin(), sorted.end(), info,
504
                    [&](int idx, const VertexInfo &vertex) {return vertices[idx]<vertex;});
505
            int res = 0;
506
            if (it != sorted.end() && vertices[*it] == info) {
507
                res = *it + 1;
508
            }
509
            return res;
510
        }
511
        int find(const EdgeInfo *info) const
512
        {
513
            const size_t verticesSizeMax = 20;
514
            if (vertices.size() < verticesSizeMax) {
515
                for (auto it=vertices.begin(); it!=vertices.end(); ++it) {
516
                    if (it->edgeInfo() == info) {
517
                        return (static_cast<int>(it - vertices.begin()) + 1);
518
                    }
519
                }
520
                return 0;
521
            }
522
            sort();
523
            auto it = std::lower_bound(sorted.begin(), sorted.end(), info,
524
                    [&](int idx, const EdgeInfo *vertex) {return vertices[idx].edgeInfo()<vertex;});
525
            int res = 0;
526
            if (it != sorted.end() && vertices[*it].edgeInfo() == info) {
527
                res = *it + 1;
528
            }
529
            return res;
530
        }
531
        bool isSame(const WireInfo &other) const
532
        {
533
            if (this == &other) {
534
                return true;
535
            }
536
            if (vertices.size() != other.vertices.size()) {
537
                return false;
538
            }
539
            if (vertices.empty()) {
540
                return true;
541
            }
542
            int idx=find(other.vertices.front().edgeInfo()) - 1;
543
            if (idx < 0) {
544
                return false;
545
            }
546
            for (auto &vertex : other.vertices) {
547
                if (vertex.edgeInfo() != vertices[idx].edgeInfo()) {
548
                    return false;
549
                }
550
                if (++idx == (int)vertices.size()) {
551
                    idx = 0;
552
                }
553
            }
554
            return true;
555
        }
556
    };
557

558
    struct EdgeSet: VectorSet<EdgeInfo*> {
559
    };
560
    EdgeSet edgeSet;
561

562
    struct WireSet: VectorSet<WireInfo*> {
563
    };
564
    WireSet wireSet;
565

566
    const Bnd_Box &getWireBound(const WireInfo &wireInfo) const
567
    {
568
        if (wireInfo.box.IsVoid()) {
569
            for (auto& vertex : wireInfo.vertices) {
570
                BRepBndLib::Add(vertex.it->shape(), wireInfo.box);
571
            }
572
            wireInfo.box.Enlarge(myTol);
573
        }
574
        return wireInfo.box;
575
    }
576

577
    // This method was originally part of WireJoinerP::initWireInfo(), split to reduce cognitive
578
    // complexity
579
    bool initWireInfoWireClosed(const WireInfo& wireInfo)
580
    {
581
        if (!BRep_Tool::IsClosed(wireInfo.wire)) {
582
            showShape(wireInfo.wire, "FailedToClose");
583
            FC_ERR("Wire not closed");
584
            for (auto& vertex : wireInfo.vertices) {
585
                showShape(vertex.edgeInfo(), vertex.start ? "failed" : "failed_r", iteration);
586
            }
587
            return false;
588
        }
589
        return true;
590
    }
591

592
    // This method was originally part of WireJoinerP::initWireInfo(), split to reduce cognitive
593
    // complexity
594
    bool initWireInfoFaceDone(WireInfo& wireInfo)
595
    {
596
        BRepBuilderAPI_MakeFace mkFace(wireInfo.wire);
597
        if (!mkFace.IsDone()) {
598
            FC_ERR("Failed to create face for wire");
599
            showShape(wireInfo.wire, "FailedFace");
600
            return false;
601
        }
602
        wireInfo.face = mkFace.Face();
603
        return true;
604
    }
605

606
    bool initWireInfo(WireInfo &wireInfo)
607
    {
608
        if (!wireInfo.face.IsNull()) {
609
            return true;
610
        }
611
        getWireBound(wireInfo);
612
        if (wireInfo.wire.IsNull()) {
613
            wireData->Clear();
614
            for (auto& vertex : wireInfo.vertices) {
615
                wireData->Add(vertex.it->shape(vertex.start));
616
            }
617
            wireInfo.wire = makeCleanWire();
618
        }
619

620
        if (!initWireInfoWireClosed(wireInfo)) {
621
            return false;
622
        }
623

624
        if (!initWireInfoFaceDone(wireInfo)) {
625
            return false;
626
        }
627

628
        return true;
629
    }
630

631
    bool isInside(const WireInfo &wireInfo, gp_Pnt &pt) const
632
    {
633
        if (getWireBound(wireInfo).IsOut(pt)) {
634
            return false;
635
        }
636
        BRepClass_FaceClassifier fc(wireInfo.face, pt, myTol);
637
        return fc.State() == TopAbs_IN;
638
    }
639

640
    bool isOutside(const WireInfo &wireInfo, gp_Pnt &pt) const
641
    {
642
        if (getWireBound(wireInfo).IsOut(pt)) {
643
            return false;
644
        }
645
        BRepClass_FaceClassifier fc(wireInfo.face, pt, myTol);
646
        return fc.State() == TopAbs_OUT;
647
    }
648

649
    struct PntGetter
650
    {
651
        using result_type = const gp_Pnt&;
652
        result_type operator()(const VertexInfo &vInfo) const {
653
            return vInfo.pt();
654
        }
655
    };
656

657
    bgi::rtree<VertexInfo, RParameters, PntGetter> vmap {};
658

659
    struct BoxGetter
660
    {
661
        using result_type = const Box&;
662
        result_type operator()(Edges::iterator it) const {
663
            return it->box;
664
        }
665
    };
666
    bgi::rtree<Edges::iterator, RParameters, BoxGetter> boxMap {};
667

668
    BRep_Builder builder;
669
    TopoDS_Compound compound;
670

671
    std::unordered_set<TopoShape, ShapeHasher, ShapeHasher> sourceEdges {};
672
    std::vector<TopoShape> sourceEdgeArray {};
673
    TopoDS_Compound openWireCompound;
674

675
    Handle(ShapeExtend_WireData) wireData = new ShapeExtend_WireData();
676

677
    void clear()
678
    {
679
        aHistory->Clear();
680
        iteration = 0;
681
        boxMap.clear();
682
        vmap.clear();
683
        edges.clear();
684
        edgeSet.clear();
685
        wireSet.clear();
686
        adjacentList.clear();
687
        stack.clear();
688
        tmpVertices.clear();
689
        vertexStack.clear();
690
        builder.MakeCompound(compound);
691
        openWireCompound.Nullify();
692
    }
693

694
    Edges::iterator remove(Edges::iterator it)
695
    {
696
        if (it->queryBBox) {
697
            boxMap.remove(it);
698
        }
699
        vmap.remove(VertexInfo(it,true));
700
        vmap.remove(VertexInfo(it,false));
701
        return edges.erase(it);
702
    }
703

704
    void remove(EdgeInfo *info)
705
    {
706
        if (edgesTable.empty()) {
707
            for (auto it = edges.begin(); it != edges.end(); ++it) {
708
                edgesTable[&(*it)] = it;
709
            }
710
        }
711
        auto it = edgesTable.find(info);
712
        if (it != edgesTable.end()) {
713
            remove(it->second);
714
            edgesTable.erase(it);
715
        }
716
    }
717

718
    void add(Edges::iterator it)
719
    {
720
        vmap.insert(VertexInfo(it,true));
721
        vmap.insert(VertexInfo(it,false));
722
        if (it->queryBBox) {
723
            boxMap.insert(it);
724
        }
725
        showShape(it->edge, "add");
726
    }
727

728
    int add(const TopoDS_Edge &eToAdd, bool queryBBox=false)
729
    {
730
        auto it = edges.begin();
731
        return add(eToAdd, queryBBox, it);
732
    }
733

734
    int add(const TopoDS_Edge &eToAdd, bool queryBBox, Edges::iterator &it)
735
    {
736
        Box bbox;
737
        if (!getBBox(eToAdd, bbox)) {
738
            showShape(eToAdd, "small");
739
            aHistory->Remove(eToAdd);
740
            return 0;
741
        }
742
        return add(eToAdd, queryBBox, bbox, it) ? 1 : -1;
743
    }
744

745
    // This method was originally part of WireJoinerP::add(), split to reduce cognitive complexity
746
    bool addNoDuplicates(const TopoDS_Edge& eToAdd,
747
                         TopoDS_Vertex& v2,
748
                         TopoDS_Edge& ev2,
749
                         const bool isLinear,
750
                         const VertexInfo& vinfo,
751
                         std::unique_ptr<Geometry>& geo)
752
    {
753
        if (v2.IsNull()) {
754
            ev2 = vinfo.edge();
755
            v2 = vinfo.otherVertex();
756
        }
757
        if (isLinear && vinfo.edgeInfo()->isLinear) {
758
            showShape(eToAdd, "duplicate");
759
            aHistory->Remove(eToAdd);
760
            return false;
761
        }
762
        if (auto geoEdge = vinfo.edgeInfo()->geometry()) {
763
            if (!geo) {
764
                geo = Geometry::fromShape(eToAdd, /*silent*/ true);
765
            }
766
            if (geo && geo->isSame(*geoEdge, myTol, myAngularTol)) {
767
                showShape(eToAdd, "duplicate");
768
                aHistory->Remove(eToAdd);
769
                return false;
770
            }
771
        }
772
        return true;
773
    }
774

775
    // This method was originally part of WireJoinerP::add(), split to reduce cognitive complexity
776
    bool addValidEdges(const TopoDS_Edge& eToAdd,
777
                       const gp_Pnt p1,
778
                       const double tol,
779
                       TopoDS_Vertex& v1,
780
                       TopoDS_Edge& ev1,
781
                       const gp_Pnt p2,
782
                       TopoDS_Vertex& v2,
783
                       TopoDS_Edge& ev2,
784
                       const bool isLinear)
785
    {
786
        std::unique_ptr<Geometry> geo;
787
        for (auto vit = vmap.qbegin(bgi::nearest(p1, INT_MAX)); vit != vmap.qend(); ++vit) {
788
            auto& vinfo = *vit;
789
            if (canShowShape()) {
790
#if OCC_VERSION_HEX < 0x070800
791
                FC_MSG("addcheck " << vinfo.edge().HashCode(INT_MAX));
792
#else
793
                FC_MSG("addcheck " << std::hash<TopoDS_Edge> {}(vinfo.edge()));
794
#endif
795
            }
796
            double d1 = vinfo.pt().SquareDistance(p1);
797
            if (d1 >= tol) {
798
                break;
799
            }
800
            if (v1.IsNull()) {
801
                ev1 = vinfo.edge();
802
                v1 = vinfo.vertex();
803
            }
804
            double d2 = vinfo.ptOther().SquareDistance(p2);
805
            if (d2 < tol) {
806
                if (!addNoDuplicates(eToAdd, v2, ev2, isLinear, vinfo, geo)){
807
                    return false;
808
                }
809
            }
810
        }
811
        return true;
812
    }
813

814
    bool add(const TopoDS_Edge &eToAdd, bool queryBBox, const Box &bbox, Edges::iterator &it)
815
    {
816
        gp_Pnt p1 = gp_Pnt();
817
        gp_Pnt p2 = gp_Pnt();
818
        getEndPoints(eToAdd,p1,p2);
819
        TopoDS_Vertex v1 = TopoDS_Vertex();
820
        TopoDS_Vertex v2 = TopoDS_Vertex();
821
        TopoDS_Edge ev1 = TopoDS_Edge();
822
        TopoDS_Edge ev2 = TopoDS_Edge();
823
        double tol = myTol2;
824
        // search for duplicate edges
825
        showShape(eToAdd, "addcheck");
826
        bool isLinear = TopoShape(eToAdd).isLinearEdge();
827

828
        if (!addValidEdges(eToAdd, p1, tol, v1, ev1, p2, v2, ev2, isLinear)){
829
            return false;
830
        }
831

832
        if (v2.IsNull()) {
833
            for (auto vit=vmap.qbegin(bgi::nearest(p2,1));vit!=vmap.qend();++vit) {
834
                auto &vinfo = *vit;
835
                double d1 = vinfo.pt().SquareDistance(p2);
836
                if (d1 < tol) {
837
                    v2 = vit->vertex();
838
                    ev2 = vit->edge();
839
                }
840
            }
841
        }
842

843
        // Make sure coincident vertices are actually the same TopoDS_Vertex,
844
        // which is crucial for the OCC internal shape hierarchy structure. We
845
        // achieve this by making a temp wire and let OCC do the hard work of
846
        // replacing the vertex.
847
        auto connectEdge = [&](TopoDS_Edge& eCurrent,
848
                               const TopoDS_Vertex& vCurrent,
849
                               const TopoDS_Edge& eOther,
850
                               const TopoDS_Vertex& vOther) {
851
            if (vOther.IsNull()) {
852
                return;
853
            }
854
            if (vCurrent.IsSame(vOther)) {
855
                return;
856
            }
857
            double tol = std::max(BRep_Tool::Pnt(vCurrent).Distance(BRep_Tool::Pnt(vOther)),
858
                                  BRep_Tool::Tolerance(vOther));
859
            if (tol >= BRep_Tool::Tolerance(vCurrent)) {
860
                ShapeFix_ShapeTolerance fix;
861
                const double halving {0.5};
862
                fix.SetTolerance(vCurrent, std::max(tol*halving, myTol), TopAbs_VERTEX);
863
            }
864
            BRepBuilderAPI_MakeWire mkWire(eOther);
865
            mkWire.Add(eCurrent);
866
            auto newEdge = mkWire.Edge();
867
            TopoDS_Vertex vFirst = TopExp::FirstVertex(newEdge);
868
            TopoDS_Vertex vLast = TopExp::LastVertex(newEdge);
869

870
            // Originally here there was a call to the precompiler macro assertCheck(), which has
871
            // been replaced with the precompiler macro assert()
872

873
            assert(vLast.IsSame(vOther) || vFirst.IsSame(vOther));
874
            eCurrent = newEdge;
875
        };
876

877
        TopoDS_Edge edge = eToAdd;
878
        TopoDS_Vertex vFirst = TopExp::FirstVertex(eToAdd);
879
        TopoDS_Vertex vLast = TopExp::LastVertex(eToAdd);
880
        connectEdge(edge, vFirst, ev1, v1);
881
        connectEdge(edge, vLast, ev2, v2);
882
        if (!edge.IsSame(eToAdd)) {
883
            auto itSource = sourceEdges.find(eToAdd);
884
            if (itSource != sourceEdges.end()) {
885
                TopoShape newEdge = *itSource;
886
                newEdge.setShape(edge, false);
887
                sourceEdges.erase(itSource);
888
                sourceEdges.insert(newEdge);
889
            }
890
            getEndPoints(edge,p1,p2);
891
            // Shall we also update bbox?
892
        }
893
        it = edges.emplace(it,edge,p1,p2,bbox,queryBBox,isLinear);
894
        add(it);
895
        return true;
896
    }
897

898
    void add(const TopoDS_Shape &shape, bool queryBBox=false)
899
    {
900
        for (TopExp_Explorer xp(shape, TopAbs_EDGE); xp.More(); xp.Next()) {
901
            add(TopoDS::Edge(xp.Current()), queryBBox);
902
        }
903
    }
904

905
    // This method was originally part of WireJoinerP::join(), split to reduce cognitive complexity
906
    void joinMakeWire(const int idx,
907
                      BRepBuilderAPI_MakeWire& mkWire,
908
                      const Edges::iterator it,
909
                      bool& done)
910
    {
911
        double tol = myTol2;
912
        gp_Pnt pstart(it->p1);
913
        gp_Pnt pend(it->p2);
914
        while (!edges.empty()) {
915
            std::vector<VertexInfo> ret;
916
            ret.reserve(1);
917
            const gp_Pnt& pt = idx == 0 ? pstart : pend;
918
            vmap.query(bgi::nearest(pt, 1), std::back_inserter(ret));
919

920
            // Originally here there was a call to the precompiler macro assertCheck(),
921
            // which has been replaced with the precompiler macro assert()
922

923
            assert(ret.size() == 1);
924
            double dist = ret[0].pt().SquareDistance(pt);
925
            if (dist > tol) {
926
                break;
927
            }
928

929
            const auto& info = *ret[0].it;
930
            bool start = ret[0].start;
931
            if (dist > Precision::SquareConfusion()) {
932
                // insert a filling edge to solve the tolerance problem
933
                const gp_Pnt& pt = ret[idx].pt();
934
                if (idx != 0) {
935
                    mkWire.Add(BRepBuilderAPI_MakeEdge(pend, pt).Edge());
936
                }
937
                else {
938
                    mkWire.Add(BRepBuilderAPI_MakeEdge(pt, pstart).Edge());
939
                }
940
            }
941

942
            if (idx == 1 && start) {
943
                pend = info.p2;
944
                mkWire.Add(info.edge);
945
            }
946
            else if (idx == 0 && !start) {
947
                pstart = info.p1;
948
                mkWire.Add(info.edge);
949
            }
950
            else if (idx == 0 && start) {
951
                pstart = info.p2;
952
                mkWire.Add(TopoDS::Edge(info.edge.Reversed()));
953
            }
954
            else {
955
                pend = info.p1;
956
                mkWire.Add(TopoDS::Edge(info.edge.Reversed()));
957
            }
958
            remove(ret[0].it);
959
            if (pstart.SquareDistance(pend) <= Precision::SquareConfusion()) {
960
                done = true;
961
                break;
962
            }
963
        }
964
    }
965

966
    //This algorithm tries to join connected edges into wires
967
    //
968
    //tol*tol>Precision::SquareConfusion() can be used to join points that are
969
    //close but do not coincide with a line segment. The close points may be
970
    //the results of rounding issue.
971
    //
972
    void join()
973
    {
974
        while (!edges.empty()) {
975
            auto it = edges.begin();
976
            BRepBuilderAPI_MakeWire mkWire;
977
            mkWire.Add(it->edge);
978
            remove(it);
979

980
            bool done = false;
981
            for (int idx=0;!done&&idx<2;++idx) {
982
                joinMakeWire(idx, mkWire, it, done);
983
            }
984

985
            builder.Add(compound,mkWire.Wire());
986
        }
987
    }
988

989
    struct IntersectInfo {
990
        double param;
991
        TopoDS_Shape intersectShape;
992
        gp_Pnt point;
993
        IntersectInfo(double pToIntersect, const gp_Pnt& pt, TopoDS_Shape sToIntersect)
994
            : param(pToIntersect)
995
            , intersectShape(std::move(sToIntersect))
996
            , point(pt)
997
        {}
998
        bool operator<(const IntersectInfo &other) const {
999
            return param < other.param;
1000
        }
1001
    };
1002

1003
    void checkSelfIntersection(const EdgeInfo &info, std::set<IntersectInfo> &params) const
1004
    {
1005
        // Early return if checking for self intersection (only for non linear spline curves)
1006
        if (info.type <= GeomAbs_Parabola || info.isLinear) {
1007
            return;
1008
        }
1009
        IntRes2d_SequenceOfIntersectionPoint points2d;
1010
        TColgp_SequenceOfPnt points3d;
1011
        TColStd_SequenceOfReal errors;
1012
        TopoDS_Wire wire;
1013
        BRepBuilderAPI_MakeWire mkWire(info.edge);
1014
        if (!mkWire.IsDone()) {
1015
            return;
1016
        }
1017
        if (!BRep_Tool::IsClosed(mkWire.Wire())) {
1018
            BRepBuilderAPI_MakeEdge mkEdge(info.p1, info.p2);
1019
            if (!mkEdge.IsDone()) {
1020
                return;
1021
            }
1022
            mkWire.Add(mkEdge.Edge());
1023
        }
1024
        wire = mkWire.Wire();
1025
        BRepBuilderAPI_MakeFace mkFace(wire);
1026
        if (!mkFace.IsDone()) {
1027
            return;
1028
        }
1029
        const TopoDS_Face& face = mkFace.Face();
1030
        ShapeAnalysis_Wire analysis(wire, face, myTol);
1031
        analysis.CheckSelfIntersectingEdge(1, points2d, points3d);
1032

1033
        // Originally here there was a call to the precompiler macro assertCheck(), which has been
1034
        // replaced with the precompiler macro assert()
1035

1036
        assert(points2d.Length() == points3d.Length());
1037
        for (int i=1; i<=points2d.Length(); ++i) {
1038
            params.emplace(points2d(i).ParamOnFirst(), points3d(i), info.edge);
1039
            params.emplace(points2d(i).ParamOnSecond(), points3d(i), info.edge);
1040
        }
1041
    }
1042

1043
    // This method was originally part of WireJoinerP::checkIntersection(), split to reduce
1044
    // cognitive complexity
1045
    bool checkIntersectionPlanar(const EdgeInfo& info,
1046
                                 const EdgeInfo& other,
1047
                                 std::set<IntersectInfo>& params1,
1048
                                 std::set<IntersectInfo>& params2)
1049
    {
1050
        gp_Pln pln;
1051
        bool planar = TopoShape(info.edge).findPlane(pln);
1052
        if (!planar) {
1053
            TopoDS_Compound comp;
1054
            builder.MakeCompound(comp);
1055
            builder.Add(comp, info.edge);
1056
            builder.Add(comp, other.edge);
1057
            planar = TopoShape(comp).findPlane(pln);
1058
            if (!planar) {
1059
                BRepExtrema_DistShapeShape extss(info.edge, other.edge);
1060
                extss.Perform();
1061
                if (extss.IsDone() && extss.NbSolution() > 0) {
1062
                    if (!extss.IsDone() || extss.NbSolution() <= 0 || extss.Value() >= myTol) {
1063
                        return false;
1064
                    }
1065
                }
1066
                for (int i = 1; i <= extss.NbSolution(); ++i) {
1067
                    Standard_Real par = Standard_Real();
1068
                    auto s1 = extss.SupportOnShape1(i);
1069
                    auto s2 = extss.SupportOnShape2(i);
1070
                    if (s1.ShapeType() == TopAbs_EDGE) {
1071
                        extss.ParOnEdgeS1(i, par);
1072
                        pushIntersection(params1, par, extss.PointOnShape1(i), other.edge);
1073
                    }
1074
                    if (s2.ShapeType() == TopAbs_EDGE) {
1075
                        extss.ParOnEdgeS2(i, par);
1076
                        pushIntersection(params2, par, extss.PointOnShape2(i), info.edge);
1077
                    }
1078
                }
1079
                return false;
1080
            }
1081
        }
1082

1083
        return true;
1084
    }
1085

1086
    // This method was originally part of WireJoinerP::checkIntersection(), split to reduce
1087
    // cognitive complexity
1088
    static bool checkIntersectionEdgeDone(const BRepBuilderAPI_MakeEdge& mkEdge)
1089
    {
1090
        if (!mkEdge.IsDone()) {
1091
            if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_LOG)) {
1092
                FC_WARN("Failed to build edge for checking intersection");
1093
            }
1094
            return false;
1095
        }
1096
        return true;
1097
    }
1098

1099
    // This method was originally part of WireJoinerP::checkIntersection(), split to reduce
1100
    // cognitive complexity
1101
    static bool checkIntersectionWireDone(const BRepBuilderAPI_MakeWire& mkWire)
1102
    {
1103
        if (!mkWire.IsDone()) {
1104
            if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_LOG)) {
1105
                FC_WARN("Failed to build wire for checking intersection");
1106
            }
1107
            return false;
1108
        }
1109
        return true;
1110
    }
1111

1112
    // This method was originally part of WireJoinerP::checkIntersection(), split to reduce
1113
    // cognitive complexity
1114
    static bool checkIntersectionMakeWire(const EdgeInfo& info,
1115
                                          const EdgeInfo& other,
1116
                                          int& idx,
1117
                                          TopoDS_Wire& wire)
1118
    {
1119
        BRepBuilderAPI_MakeWire mkWire(info.edge);
1120
        mkWire.Add(other.edge);
1121
        if (mkWire.IsDone()) {
1122
            idx = 2;
1123
        }
1124
        else if (mkWire.Error() == BRepBuilderAPI_DisconnectedWire) {
1125
            idx = 3;
1126
            BRepBuilderAPI_MakeEdge mkEdge(info.p1, other.p1);
1127

1128
            if (!checkIntersectionEdgeDone(mkEdge)) {
1129
                return false;
1130
            }
1131

1132
            mkWire.Add(mkEdge.Edge());
1133
            mkWire.Add(other.edge);
1134
        }
1135

1136
        if (!checkIntersectionWireDone(mkWire)) {
1137
            return false;
1138
        }
1139

1140
        wire = mkWire.Wire();
1141
        if (!BRep_Tool::IsClosed(wire)) {
1142
            gp_Pnt p1 = gp_Pnt();
1143
            gp_Pnt p2 = gp_Pnt();
1144
            getEndPoints(wire, p1, p2);
1145
            BRepBuilderAPI_MakeEdge mkEdge(p1, p2);
1146

1147
            if (!checkIntersectionEdgeDone(mkEdge)) {
1148
                return false;
1149
            }
1150

1151
            mkWire.Add(mkEdge.Edge());
1152
        }
1153
        return true;
1154
    }
1155

1156
    // This method was originally part of WireJoinerP::checkIntersection(), split to reduce
1157
    // cognitive complexity
1158
    static bool checkIntersectionFaceDone(const BRepBuilderAPI_MakeFace& mkFace)
1159
    {
1160
        if (!mkFace.IsDone()) {
1161
            if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_LOG)) {
1162
                FC_WARN("Failed to build face for checking intersection");
1163
            }
1164
            return false;
1165
        }
1166
        return true;
1167
    }
1168

1169
    void checkIntersection(const EdgeInfo &info,
1170
                           const EdgeInfo &other,
1171
                           std::set<IntersectInfo> &params1,
1172
                           std::set<IntersectInfo> &params2)
1173
    {
1174
        if(!checkIntersectionPlanar(info, other, params1, params2)){
1175
            return;
1176
        }
1177

1178
        // BRepExtrema_DistShapeShape has trouble finding all solutions for a
1179
        // spline curve. ShapeAnalysis_Wire is better. Besides, it can check
1180
        // for self intersection. It's slightly more troublesome to use, as it
1181
        // requires to build a face for the wire, so we only use it for planar
1182
        // cases.
1183

1184
        IntRes2d_SequenceOfIntersectionPoint points2d;
1185
        TColgp_SequenceOfPnt points3d;
1186
        TColStd_SequenceOfReal errors;
1187
        TopoDS_Wire wire;
1188
        int idx = 0;
1189

1190
        if (!checkIntersectionMakeWire(info, other, idx, wire)){
1191
            return;
1192
        }
1193

1194
        BRepBuilderAPI_MakeFace mkFace(wire);
1195
        if (!checkIntersectionFaceDone(mkFace)) {
1196
            return;
1197
        }
1198

1199
        const TopoDS_Face& face = mkFace.Face();
1200
        ShapeAnalysis_Wire analysis(wire, face, myTol);
1201
        analysis.CheckIntersectingEdges(1, idx, points2d, points3d, errors);
1202

1203
        // Originally here there was a call to the precompiler macro assertCheck(), which has been
1204
        // replaced with the precompiler macro assert()
1205

1206
        assert(points2d.Length() == points3d.Length());
1207
        for (int i=1; i<=points2d.Length(); ++i) {
1208
            pushIntersection(params1, points2d(i).ParamOnFirst(), points3d(i), other.edge);
1209
            pushIntersection(params2, points2d(i).ParamOnSecond(), points3d(i), info.edge);
1210
        }
1211
    }
1212

1213
    void pushIntersection(std::set<IntersectInfo>& params,
1214
                          double param,
1215
                          const gp_Pnt& pt,
1216
                          const TopoDS_Shape& shape)
1217
    {
1218
        IntersectInfo info(param, pt, shape);
1219
        auto it = params.upper_bound(info);
1220
        if (it != params.end()) {
1221
            if (it->point.SquareDistance(pt) < myTol2) {
1222
                return;
1223
            }
1224
        }
1225
        if (it != params.begin()) {
1226
            auto itPrev = it;
1227
            --itPrev;
1228
            if (itPrev->point.SquareDistance(pt) < myTol2) {
1229
                return;
1230
            }
1231
        }
1232
        params.insert(it, info);
1233
    }
1234

1235
    struct SplitInfo {
1236
        TopoDS_Edge edge;
1237
        TopoDS_Shape intersectShape;
1238
        Box bbox;
1239
    };
1240

1241
    // This method was originally part of WireJoinerP::splitEdges(), split to reduce cognitive
1242
    // complexity
1243
    void splitEdgesMakeEdge(const std::set<IntersectInfo>::iterator& itParam,
1244
                            const EdgeInfo& info,
1245
                            std::vector<SplitInfo>& splits,
1246
                            std::set<IntersectInfo>::iterator& itPrevParam,
1247
                            const TopoDS_Shape& intersectShape)
1248
    {
1249
        // Using points cause MakeEdge failure for some reason. Using
1250
        // parameters is better.
1251
        //
1252
        const gp_Pnt& p1 = itPrevParam->point;
1253
        const gp_Pnt& p2 = itParam->point;
1254
        const Standard_Real& param1 = itPrevParam->param;
1255
        const Standard_Real& param2 = itParam->param;
1256

1257
        BRepBuilderAPI_MakeEdge mkEdge(info.curve, param1, param2);
1258
        if (mkEdge.IsDone()) {
1259
            splits.emplace_back();
1260
            auto& entry = splits.back();
1261
            entry.edge = mkEdge.Edge();
1262
            entry.intersectShape = intersectShape;
1263
            if (getBBox(entry.edge, entry.bbox)) {
1264
                itPrevParam = itParam;
1265
            }
1266
            else {
1267
                splits.pop_back();
1268
            }
1269
        }
1270
        else if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_LOG)) {
1271
            FC_WARN("edge split failed " << std::setprecision(16) << FC_XYZ(p1) << FC_XYZ(p2)
1272
                                         << ": " << mkEdge.Error());
1273
        }
1274
    }
1275

1276
    // This method was originally part of WireJoinerP::splitEdges(), split to reduce cognitive
1277
    // complexity
1278
    void splitEdgesMakeEdges(std::set<IntersectInfo>::iterator& itParam,
1279
                             const std::set<IntersectInfo>& params,
1280
                             const EdgeInfo& info,
1281
                             std::vector<SplitInfo>& splits)
1282
    {
1283
        for (auto itPrevParam = itParam++; itParam != params.end(); ++itParam) {
1284
            const auto& intersectShape = itParam->intersectShape.IsNull()
1285
                ? itPrevParam->intersectShape
1286
                : itParam->intersectShape;
1287
            if (intersectShape.IsNull()) {
1288
                break;
1289
            }
1290

1291
            splitEdgesMakeEdge(itParam, info, splits, itPrevParam, intersectShape);
1292
        }
1293
    }
1294

1295
    // Try splitting any edges that intersects other edge
1296
    void splitEdges()
1297
    {
1298
        std::unordered_map<const EdgeInfo*, std::set<IntersectInfo>> intersects;
1299

1300
        int idx=0;
1301
        for (auto& info : edges) {
1302
            info.iteration = ++idx;
1303
        }
1304

1305
        std::unique_ptr<Base::SequencerLauncher> seq(
1306
                new Base::SequencerLauncher("Splitting edges", edges.size()));
1307

1308
        idx = 0;
1309
        for (auto& info : edges) {
1310
            seq->next(true);
1311
            ++idx;
1312
            auto &params = intersects[&info];
1313
            checkSelfIntersection(info, params);
1314

1315
            for (auto vit=boxMap.qbegin(bgi::intersects(info.box)); vit!=boxMap.qend(); ++vit) {
1316
                const auto &other = *(*vit);
1317
                if (other.iteration <= idx) {
1318
                    // means the edge is before us, and we've already checked intersection
1319
                    continue;
1320
                }
1321
                checkIntersection(info, other, params, intersects[&other]);
1322
            }
1323
        }
1324

1325
        idx=0;
1326
        std::vector<SplitInfo> splits;
1327
        for (auto it=edges.begin(); it!=edges.end(); ) {
1328
            ++idx;
1329
            auto iter = intersects.find(&(*it));
1330
            if (iter == intersects.end()) {
1331
                ++it;
1332
                continue;
1333
            }
1334
            auto &info = *it;
1335
            auto &params = iter->second;
1336
            if (params.empty()) {
1337
                ++it;
1338
                continue;
1339
            }
1340

1341
            auto itParam = params.begin();
1342
            if (itParam->point.SquareDistance(info.p1) < myTol2) {
1343
                params.erase(itParam);
1344
            }
1345
            params.emplace(info.firstParam, info.p1, TopoDS_Shape());
1346
            itParam = params.end();
1347
            --itParam;
1348
            if (itParam->point.SquareDistance(info.p2) < myTol2) {
1349
                params.erase(itParam);
1350
            }
1351
            params.emplace(info.lastParam, info.p2, TopoDS_Shape());
1352

1353
            if (params.size() <= 2) {
1354
                ++it;
1355
                continue;
1356
            }
1357

1358
            splits.clear();
1359
            itParam = params.begin();
1360

1361
            splitEdgesMakeEdges(itParam, params, info, splits);
1362

1363
            if (splits.size() <= 1) {
1364
                ++it;
1365
                continue;
1366
            }
1367

1368
            showShape(info.edge, "remove");
1369
            auto removedEdge = info.edge;
1370
            it = remove(it);
1371
            for (const auto& split : splits) {
1372
                if (!add(split.edge, false, split.bbox, it)) {
1373
                    continue;
1374
                }
1375
                auto &newInfo = *it++;
1376
                aHistory->AddModified(split.intersectShape, newInfo.edge);
1377
                // if (v.intersectShape != removedEdge)
1378
                //     aHistory->AddModified(removedEdge, newInfo.edge);
1379
                showShape(newInfo.edge, "split");
1380
            }
1381
        }
1382
    }
1383

1384
    // This method was originally part of WireJoinerP::findSuperEdges(), split to reduce cognitive
1385
    // complexity
1386
    void findSuperEdgeFromAdjacent(std::deque<VertexInfo>& vertices, const int direction)
1387
    {
1388
        bool done = false;
1389
        auto begin = direction == 1 ? vertices.back().reversed() : vertices.front();
1390
        while (true) {
1391
            auto currentVertex = direction == 1 ? vertices.front() : vertices.back();
1392
            auto current = currentVertex.edgeInfo();
1393
            // showShape(current, "siter", k);
1394
            const int idx = (currentVertex.start ? 1 : 0) ^ direction;
1395
            EdgeInfo* found = nullptr;
1396
            for (int i = current->iStart[idx]; i < current->iEnd[idx]; ++i) {
1397
                const auto& vertex = adjacentList[i];
1398
                auto next = vertex.edgeInfo();
1399
                if (next->iteration < 0    // skipped
1400
                    || next == current) {  // skip self (see how adjacent list is built)
1401
                    continue;
1402
                }
1403
                if (vertex == begin) {
1404
                    // closed
1405
                    done = true;
1406
                    break;
1407
                }
1408
                if (found                       // more than one branch
1409
                    || edgeSet.contains(next))  // or, self intersect
1410
                {
1411

1412
                    // Originally here there were some lines of code that have been removed
1413
                    // as them are commented out.
1414
                    // See
1415
                    // https://github.com/realthunder/FreeCAD/blob/6f15849be2505f98927e75d0e8352185e14e7b72/src/Mod/Part/App/WireJoiner.cpp#L1141
1416
                    // for reference.
1417

1418
                    found = nullptr;
1419
                    break;
1420
                }
1421
                found = next;
1422
                currentVertex = vertex;
1423
            }
1424
            if (done || !found) {
1425
                break;
1426
            }
1427
            // showShape(found, "snext", k);
1428
            if (direction == 1) {
1429
                edgeSet.insert(current);
1430
                vertices.push_front(currentVertex.reversed());
1431
            }
1432
            else {
1433
                edgeSet.insert(found);
1434
                vertices.push_back(currentVertex);
1435
            }
1436
        }
1437
    }
1438

1439
    // This method was originally part of WireJoinerP::findSuperEdges(), split to reduce cognitive
1440
    // complexity
1441
    void findSuperEdge(std::deque<VertexInfo>& vertices, const Edges::iterator it)
1442
    {
1443
        vertices.clear();
1444
        vertices.emplace_back(it, true);
1445
        edgeSet.clear();
1446

1447
        for (int direction = 0; direction < 2; ++direction) {  // search in both direction
1448
            findSuperEdgeFromAdjacent(vertices, direction);
1449
        }
1450
    }
1451

1452
    // This method was originally part of WireJoinerP::findSuperEdges(), split to reduce cognitive
1453
    // complexity
1454
    void findSuperEdgesUpdateFirst(std::deque<VertexInfo> vertices)
1455
    {
1456
        Bnd_Box bbox;
1457
        for (const auto& vertex : vertices) {
1458
            auto current = vertex.edgeInfo();
1459
            bbox.Add(current->box.min_corner());
1460
            bbox.Add(current->box.max_corner());
1461
            wireData->Add(current->shape(vertex.start));
1462
            showShape(current, "edge");
1463
            current->iteration = -1;
1464
        }
1465

1466
        auto first = vertices.front().edgeInfo();
1467
        first->superEdge = makeCleanWire(false);
1468
        first->superEdgeReversed.Nullify();
1469
        if (BRep_Tool::IsClosed(first->superEdge)) {
1470
            first->iteration = -2;
1471
            showShape(first, "super_done");
1472
        }
1473
        else {
1474
            first->iteration = iteration;
1475
            showShape(first, "super");
1476
            auto& vFirst = vertices.front();
1477
            auto& vLast = vertices.back();
1478
            auto last = vLast.edgeInfo();
1479
            vFirst.ptOther() = vLast.ptOther();
1480
            const int idx = vFirst.start ? 1 : 0;
1481
            first->iStart[idx] = last->iStart[vLast.start ? 1 : 0];
1482
            first->iEnd[idx] = last->iEnd[vLast.start ? 1 : 0];
1483

1484
            for (int i = first->iStart[idx]; i < first->iEnd[idx]; ++i) {
1485
                auto& vertex = adjacentList[i];
1486
                if (vertex.it == vLast.it) {
1487
                    vertex.it = vFirst.it;
1488
                    vertex.start = !vFirst.start;
1489
                }
1490
            }
1491
            bbox.Enlarge(myTol);
1492
            first->box = Box(bbox.CornerMin(), bbox.CornerMax());
1493
        }
1494
    }
1495

1496
    void findSuperEdges()
1497
    {
1498
        std::unique_ptr<Base::SequencerLauncher> seq(
1499
            new Base::SequencerLauncher("Combining edges", edges.size()));
1500

1501
        std::deque<VertexInfo> vertices;
1502

1503
        ++iteration;
1504

1505
        // Join edges (let's call it super edge) that are connected to only one
1506
        // other edges (count == 2 counts this and the other edge) on one of
1507
        // its vertices to save traverse time.
1508
        for (auto it = edges.begin(); it != edges.end(); ++it) {
1509
            seq->next(true);
1510
            auto& info = *it;
1511
            if (info.iteration == iteration || info.iteration < 0) {
1512
                continue;
1513
            }
1514
            info.iteration = iteration;
1515
            // showShape(&info, "scheck");
1516

1517
            findSuperEdge(vertices, it);
1518

1519
            if (vertices.size() <= 1) {
1520
                continue;
1521
            }
1522

1523
            wireData->Clear();
1524

1525
            findSuperEdgesUpdateFirst(vertices);
1526
        }
1527
    }
1528

1529
    void buildAdjacentListPopulate()
1530
    {
1531
        // populate adjacent list
1532
        for (auto& info : edges) {
1533
            if (info.iteration == -2) {
1534

1535
                // Originally there was the following precompiler directive around assertCheck():
1536
                // #if OCC_VERSION_HEX >= 0x070000
1537
                // The precompiler directive has been removed as the minimum OCCT version supported
1538
                // is 7.3.0 and the precompiler macro has been replaced with assert()
1539

1540
                assert(BRep_Tool::IsClosed(info.shape()));
1541

1542
                showShape(&info, "closed");
1543
                if (!doTightBound) {
1544
                    builder.Add(compound, info.wire());
1545
                }
1546
                continue;
1547
            }
1548

1549
            if (info.iteration < 0) {
1550
                continue;
1551
            }
1552

1553
            if (info.p1.SquareDistance(info.p2) <= myTol2) {
1554
                if (!doTightBound) {
1555
                    builder.Add(compound, info.wire());
1556
                }
1557
                info.iteration = -2;
1558
                continue;
1559
            }
1560

1561
            std::array<gp_Pnt, 2> pt {};
1562
            pt[0] = info.p1;
1563
            pt[1] = info.p2;
1564
            for (int i = 0; i < 2; ++i) {
1565
                const int ic = i;
1566
                if (info.iStart[ic] >= 0) {
1567
                    continue;
1568
                }
1569
                info.iEnd[ic] = info.iStart[ic] = (int)adjacentList.size();
1570

1571
                for (auto vit = vmap.qbegin(bgi::nearest(pt[ic], INT_MAX)); vit != vmap.qend();
1572
                     ++vit) {
1573
                    auto& vinfo = *vit;
1574
                    if (vinfo.pt().SquareDistance(pt[ic]) > myTol2) {
1575
                        break;
1576
                    }
1577

1578
                    // We must push ourself too, because the adjacency
1579
                    // information is shared among all connected edges.
1580
                    //
1581
                    // if (&(*vinfo.it) == &info)
1582
                    //     continue;
1583

1584
                    if (vinfo.it->iteration < 0) {
1585
                        continue;
1586
                    }
1587

1588
                    adjacentList.push_back(vinfo);
1589
                    ++info.iEnd[ic];
1590
                }
1591

1592
                // copy the adjacent indices to all connected edges
1593
                for (int j = info.iStart[ic]; j < info.iEnd[ic]; ++j) {
1594
                    auto& other = adjacentList[j];
1595
                    auto& otherInfo = *other.it;
1596
                    if (&otherInfo != &info) {
1597
                        const int kc = other.start ? 0 : 1;
1598
                        otherInfo.iStart[kc] = info.iStart[ic];
1599
                        otherInfo.iEnd[kc] = info.iEnd[ic];
1600
                    }
1601
                }
1602
            }
1603
        }
1604
    }
1605

1606
    void buildAdjacentListSkipEdges()
1607
    {
1608
        bool done = false;
1609
        while (!done) {
1610
            done = true;
1611

1612
            if (doMergeEdge || doTightBound) {
1613
                findSuperEdges();
1614
            }
1615

1616
            // Skip edges that are connected to only one end
1617
            for (auto& info : edges) {
1618
                if (info.iteration < 0) {
1619
                    continue;
1620
                }
1621
                for (int k = 0; k < 2; ++k) {
1622
                    const int kc = k;
1623
                    int idx = 0;
1624
                    for (idx = info.iStart[kc]; idx < info.iEnd[kc]; ++idx) {
1625
                        const auto& vertex = adjacentList[idx];
1626
                        auto other = vertex.edgeInfo();
1627
                        if (other->iteration >= 0 && other != &info) {
1628
                            break;
1629
                        }
1630
                    }
1631
                    if (idx == info.iEnd[kc]) {
1632
                        // If merge or tight bound, then repeat until no edges
1633
                        // can be skipped.
1634
                        done = !doMergeEdge && !doTightBound;
1635
                        info.iteration = -3;
1636
                        showShape(&info, "skip");
1637
                        break;
1638
                    }
1639
                }
1640
            }
1641
        }
1642
    }
1643

1644
    void buildAdjacentList()
1645
    {
1646
        builder.MakeCompound(compound);
1647

1648
        for (auto& info : edges) {
1649
            info.reset();
1650
        }
1651

1652
        adjacentList.clear();
1653

1654
        buildAdjacentListPopulate();
1655

1656
        buildAdjacentListSkipEdges();
1657
    }
1658

1659
    // This algorithm tries to find a set of closed wires that includes as many
1660
    // edges (added by calling add() ) as possible. One edge may be included
1661
    // in more than one closed wires if it connects to more than one edges.
1662
    void findClosedWires(bool tightBound=false)
1663
    {
1664
        std::unique_ptr<Base::SequencerLauncher> seq(
1665
                new Base::SequencerLauncher("Finding wires", edges.size()));
1666

1667
        for (auto &info : edges) {
1668
            info.wireInfo.reset();
1669
            info.wireInfo2.reset();
1670
        }
1671

1672
        for (auto it=edges.begin(); it!=edges.end(); ++it) {
1673
            VertexInfo beginVertex(it, true);
1674
            auto &beginInfo = *it;
1675
            seq->next(true);
1676
            ++iteration;
1677
            if (beginInfo.iteration < 0 || beginInfo.wireInfo) {
1678
                continue;
1679
            }
1680

1681
            VertexInfo currentVertex(it, true);
1682
            EdgeInfo *currentInfo = &beginInfo;
1683
            showShape(currentInfo, "begin");
1684
            stack.clear();
1685
            vertexStack.clear();
1686
            edgeSet.clear();
1687

1688
            TopoDS_Wire wire = _findClosedWires(beginVertex, currentVertex);
1689
            if (wire.IsNull()) {
1690
                continue;
1691
            }
1692

1693
            if (tightBound) {
1694

1695
                // Originally here there was a call to the precompiler macro assertCheck(), which
1696
                // has been replaced with the precompiler macro assert()
1697

1698
                assert(!beginInfo.wireInfo);
1699
                beginInfo.wireInfo.reset(new WireInfo());
1700
                beginInfo.wireInfo->vertices.emplace_back(it, true);
1701
                beginInfo.wireInfo->wire = wire;
1702
            }
1703
            for (auto &entry : stack) {
1704
                const auto &vertex = vertexStack[entry.iCurrent];
1705
                auto &info = *vertex.it;
1706
                if (tightBound) {
1707
                    beginInfo.wireInfo->vertices.push_back(vertex);
1708
                }
1709
                if (!info.wireInfo) {
1710
                    info.wireInfo = beginInfo.wireInfo;
1711
                    // showShape(&info, "visited");
1712
                }
1713
            }
1714
            showShape(wire,"joined");
1715
            if (!tightBound) {
1716
                builder.Add(compound, wire);
1717
            }
1718
        }
1719
    }
1720

1721
    // Originally here there was the definition of the method checkStack(), which does nothing and
1722
    // therefor has been removed. See
1723
    // https://github.com/realthunder/FreeCAD/blob/6f15849be2505f98927e75d0e8352185e14e7b72/src/Mod/Part/App/WireJoiner.cpp#L1366
1724
    // for reference
1725

1726
    void checkWireInfo(const WireInfo &wireInfo)
1727
    {
1728
        (void)wireInfo;
1729
        if (FC_LOG_INSTANCE.level() <= FC_LOGLEVEL_TRACE) {
1730
            return;
1731
        }
1732
        for (auto &info : edges) {
1733
            if (auto wire = info.wireInfo.get()) {
1734
                boost::ignore_unused(wire);
1735

1736
                // Originally here there was a call to the precompiler macro assertCheck(), which
1737
                // has been replaced with the precompiler macro assert()
1738

1739
                assert(wire->vertices.front().edgeInfo()->wireInfo.get() == wire);
1740
            }
1741
        }
1742
    }
1743

1744
    // This method was originally part of WireJoinerP::_findClosedWires(), split to reduce cognitive
1745
    // complexity
1746
    void _findClosedWiresBeginEdge(const std::shared_ptr<WireInfo>& wireInfo,
1747
                                   const EdgeInfo& beginInfo,
1748
                                   int& idx)
1749
    {
1750
        auto info = wireInfo->vertices[idx].edgeInfo();
1751
        showShape(info, "merge", iteration);
1752

1753
        if (info != &beginInfo) {
1754
            while (true) {
1755
                if (++idx == (int)wireInfo->vertices.size()) {
1756
                    idx = 0;
1757
                }
1758

1759
                info = wireInfo->vertices[idx].edgeInfo();
1760
                if (info == &beginInfo) {
1761
                    break;
1762
                }
1763
                stack.emplace_back(vertexStack.size());
1764
                vertexStack.push_back(wireInfo->vertices[idx]);
1765
                ++stack.back().iEnd;
1766

1767
                // Originally here there was a call to the method checkStack(),
1768
                // which does nothing and therefor has been removed.
1769
            }
1770
        }
1771
    }
1772

1773
    // This method was originally part of WireJoinerP::_findClosedWires(), split to reduce cognitive
1774
    // complexity
1775
    int _findClosedWiresWithExisting(int* idxVertex,
1776
                                     const std::shared_ptr<WireInfo>& wireInfo,
1777
                                     int* const stackPos,
1778
                                     bool& proceed,
1779
                                     const VertexInfo& vinfo,
1780
                                     const int ic,
1781
                                     StackInfo& stackBack,
1782
                                     const EdgeInfo& beginInfo,
1783
                                     EdgeInfo& info)
1784
    {
1785
        if (wireInfo) {
1786
            // We may be called by findTightBound() with an existing wire
1787
            // to try to find a new wire by splitting the current one. So
1788
            // check if we've iterated to some edge in the existing wire.
1789

1790
            int idx = wireInfo->find(vinfo);
1791

1792
            if (idx != 0) {
1793
                vertexStack.push_back(adjacentList[ic]);
1794
                stackBack.iCurrent = stackBack.iEnd++;
1795
                --idx;
1796
                proceed = false;
1797
                if (idxVertex) {
1798
                    *idxVertex = idx;
1799
                }
1800
                if (stackPos) {
1801
                    *stackPos = (int)stack.size() - 2;
1802
                }
1803

1804
                _findClosedWiresBeginEdge(wireInfo, beginInfo, idx);
1805

1806
                return 1;
1807
            }
1808

1809
            if (wireInfo->find(VertexInfo(vinfo.it, !vinfo.start)) != 0) {
1810
                showShape(&info, "rintersect", iteration);
1811
                // Only used when exhausting tight bound.
1812
                wireInfo->purge = true;
1813
                return 2;
1814
            }
1815

1816
            if (isOutside(*wireInfo, info.mid)) {
1817
                showShape(&info, "outside", iteration);
1818
                return 2;
1819
            }
1820
        }
1821
        return 0;
1822
    }
1823

1824
    // This method was originally part of WireJoinerP::_findClosedWires(), split to reduce cognitive
1825
    // complexity
1826
    void _findClosedWiresUpdateStack(int* idxVertex,
1827
                                     const std::shared_ptr<WireInfo>& wireInfo,
1828
                                     int* stackPos,
1829
                                     const EdgeInfo* currentInfo,
1830
                                     const int currentIdx,
1831
                                     bool& proceed,
1832
                                     const EdgeInfo& beginInfo)
1833
    {
1834
        auto& stackBack = stack.back();
1835

1836
        // The loop below is to find all edges connected to pend, and save them into stack.back()
1837
        auto size = vertexStack.size();
1838
        for (int i = currentInfo->iStart[currentIdx]; i < currentInfo->iEnd[currentIdx]; ++i) {
1839
            auto& vinfo = adjacentList[i];
1840
            auto& info = *vinfo.it;
1841
            if (info.iteration < 0 || currentInfo == &info) {
1842
                continue;
1843
            }
1844

1845
            bool abort = false;
1846
            if (!wireSet.empty() && wireSet.contains(info.wireInfo.get())) {
1847
                showShape(&info, "wired", iteration);
1848
                if (wireInfo) {
1849
                    wireInfo->purge = true;
1850
                }
1851
                abort = true;
1852
            }
1853

1854
            if (edgeSet.contains(&info)) {
1855
                showShape(&info, "intersect", iteration);
1856
                // This means the current edge connects to an
1857
                // existing edge in the middle of the stack.
1858
                // skip the current edge.
1859
                stackBack.iEnd = stackBack.iStart;
1860
                vertexStack.resize(size);
1861
                break;
1862
            }
1863

1864
            if (abort || currentInfo->wireInfo2) {
1865
                if (wireInfo) {
1866
                    wireInfo->purge = true;
1867
                }
1868
                continue;
1869
            }
1870

1871
            if (info.iteration == iteration) {
1872
                continue;
1873
            }
1874
            info.iteration = iteration;
1875

1876
            int exists = _findClosedWiresWithExisting(idxVertex,
1877
                                                      wireInfo,
1878
                                                      stackPos,
1879
                                                      proceed,
1880
                                                      vinfo,
1881
                                                      i,
1882
                                                      stackBack,
1883
                                                      beginInfo,
1884
                                                      info);
1885

1886
            if (exists == 1) {
1887
                break;
1888
            }
1889

1890
            if (exists == 2) {
1891
                continue;
1892
            }
1893

1894
            vertexStack.push_back(adjacentList[i]);
1895
            ++stackBack.iEnd;
1896
        }
1897
    }
1898

1899
    // This method was originally part of WireJoinerP::_findClosedWires(), split to reduce cognitive
1900
    // complexity
1901
    bool _findClosedWiresUpdateEdges(VertexInfo& currentVertex,
1902
                                     gp_Pnt& pend,
1903
                                     EdgeInfo* currentInfo,
1904
                                     int& currentIdx,
1905
                                     const size_t stackEnd)
1906
    {
1907
        while (true) {
1908
            auto& stackBack = stack.back();
1909
            if (stackBack.iCurrent < stackBack.iEnd) {
1910
                // now pick one edge from stack.back(), connect it to
1911
                // pend, then extend pend
1912
                currentVertex = vertexStack[stackBack.iCurrent];
1913
                pend = currentVertex.ptOther();
1914
                // update current edge info
1915
                currentInfo = currentVertex.edgeInfo();
1916
                showShape(currentInfo, "iterate", iteration);
1917
                currentIdx = currentVertex.start ? 1 : 0;
1918
                edgeSet.insert(currentInfo);
1919
                if (!wireSet.empty()) {
1920
                    wireSet.insert(currentInfo->wireInfo.get());
1921
                }
1922
                break;
1923
            }
1924
            vertexStack.erase(vertexStack.begin() + static_cast<long>(stackBack.iStart), vertexStack.end());
1925

1926
            stack.pop_back();
1927
            if (stack.size() == stackEnd) {
1928
                // If stack reaches the end, it means this wire is open.
1929
                return true;
1930
            }
1931

1932
            auto& lastInfo = *vertexStack[stack.back().iCurrent].it;
1933
            edgeSet.erase(&lastInfo);
1934
            wireSet.erase(lastInfo.wireInfo.get());
1935
            showShape(&lastInfo, "pop", iteration);
1936
            ++stack.back().iCurrent;
1937
        }
1938
        return false;
1939
    }
1940

1941
    // This method was originally part of WireJoinerP::_findClosedWires(), split to reduce cognitive
1942
    // complexity
1943
    bool _findClosedWiresIsClosed(const VertexInfo& beginVertex,
1944
                                  const TopoDS_Wire& wire,
1945
                                  const EdgeInfo& beginInfo)
1946
    {
1947
        if (!BRep_Tool::IsClosed(wire)) {
1948
            FC_WARN("failed to close some wire in iteration " << iteration);
1949
            showShape(wire, "_FailedToClose", iteration);
1950
            showShape(beginInfo.shape(beginVertex.start), "failed", iteration);
1951
            for (auto& entry : stack) {
1952
                const auto& vertex = vertexStack[entry.iCurrent];
1953
                auto& info = *vertex.it;
1954
                showShape(info.shape(vertex.start), vertex.start ? "failed" : "failed_r", iteration);
1955
            }
1956

1957
            // Originally here there was a call to the precompiler macro assertCheck(), which
1958
            // has been replaced with the precompiler macro assert()
1959

1960
            assert(false);
1961
            return false;
1962
        }
1963
        return true;
1964
    }
1965

1966
    TopoDS_Wire _findClosedWires(VertexInfo beginVertex,
1967
                                 VertexInfo currentVertex,
1968
                                 int *idxVertex = nullptr,
1969
                                 const std::shared_ptr<WireInfo>& wireInfo = std::shared_ptr<WireInfo>(),
1970
                                 int* stackPos = nullptr)
1971
    {
1972
        Base::SequencerBase::Instance().checkAbort();
1973
        EdgeInfo &beginInfo = *beginVertex.it;
1974

1975
        EdgeInfo *currentInfo = currentVertex.edgeInfo();
1976
        int currentIdx = currentVertex.start ? 1 : 0;
1977
        currentInfo->iteration = iteration;
1978

1979
        gp_Pnt pstart = beginVertex.pt();
1980
        gp_Pnt pend = currentVertex.ptOther();
1981

1982
        auto stackEnd = stack.size();
1983

1984
        // Originally here there was a call to the method checkStack(), which does nothing and
1985
        // therefor has been removed.
1986

1987
        // pstart and pend is the start and end vertex of the current wire
1988
        while (true) {
1989
            // push a new stack entry
1990
            stack.emplace_back(vertexStack.size());
1991
            showShape(currentInfo, "check", iteration);
1992

1993
            bool proceed = true;
1994

1995
            _findClosedWiresUpdateStack(idxVertex,
1996
                                        wireInfo,
1997
                                        stackPos,
1998
                                        currentInfo,
1999
                                        currentIdx,
2000
                                        proceed,
2001
                                        beginInfo);
2002

2003
            // Originally here there was a call to the method checkStack(), which does nothing and
2004
            // therefor has been removed.
2005

2006
            if (proceed) {
2007
                if (_findClosedWiresUpdateEdges(currentVertex,
2008
                                                pend,
2009
                                                currentInfo,
2010
                                                currentIdx,
2011
                                                stackEnd)) {
2012
                    return {};
2013
                }
2014

2015
                if (pstart.SquareDistance(pend) > myTol2) {
2016
                    // if the wire is not closed yet, continue search for the
2017
                    // next connected edge
2018
                    continue;
2019
                }
2020
                if (wireInfo) {
2021
                    if (idxVertex) {
2022
                        *idxVertex = (int)wireInfo->vertices.size();
2023
                    }
2024
                    if (stackPos) {
2025
                        *stackPos = (int)stack.size() - 1;
2026
                    }
2027
                }
2028
            }
2029

2030
            wireData->Clear();
2031
            wireData->Add(beginInfo.shape(beginVertex.start));
2032
            for (auto &entry : stack) {
2033
                const auto &vertex = vertexStack[entry.iCurrent];
2034
                auto &info = *vertex.it;
2035
                wireData->Add(info.shape(vertex.start));
2036
            }
2037
            TopoDS_Wire wire = makeCleanWire();
2038
            if (!_findClosedWiresIsClosed(beginVertex, wire, beginInfo)) {
2039
                continue;
2040
            }
2041
            return wire;
2042
        }
2043
    }
2044

2045
    // This method was originally part of WireJoinerP::findTightBound(), split to reduce cognitive
2046
    // complexity
2047
    void findTightBoundSplitWire(const std::shared_ptr<WireInfo>& wireInfo,
2048
                                 const EdgeInfo& beginInfo,
2049
                                 const std::vector<VertexInfo>& wireVertices,
2050
                                 std::shared_ptr<WireInfo>& splitWire,
2051
                                 const int idxV,
2052
                                 int& idxStart,
2053
                                 const int idxEnd)
2054
    {
2055
        for (int idx = idxV; idx != idxEnd; ++idx) {
2056
            auto info = wireVertices[idx].edgeInfo();
2057
            if (info == &beginInfo) {
2058
                showShape(*wireInfo, "exception", iteration, true);
2059
                showShape(info, "exception", iteration, true);
2060

2061
                // Originally here there was a call to the precompiler macro
2062
                // assertCheck(), which has been replaced with the precompiler macro
2063
                // assert()
2064

2065
                assert(info != &beginInfo);
2066
            }
2067
            if (info->wireInfo == wireInfo) {
2068
                if (!splitWire) {
2069
                    idxStart = idx;
2070
                    splitWire.reset(new WireInfo());
2071
                }
2072
                info->wireInfo = splitWire;
2073
            }
2074
        }
2075
    }
2076

2077
    // This method was originally part of WireJoinerP::findTightBound(), split to reduce cognitive
2078
    // complexity
2079
    void findTightBoundWithSplit(const std::vector<VertexInfo>& wireVertices,
2080
                                 const int idxV,
2081
                                 const std::shared_ptr<WireInfo>& splitWire,
2082
                                 const int idxStart,
2083
                                 const int idxEnd,
2084
                                 const int stackPos,
2085
                                 const int stackStart)
2086
    {
2087
        auto& splitEdges = splitWire->vertices;
2088
        gp_Pnt pstart;
2089
        gp_Pnt pt;
2090
        bool first = true;
2091
        for (int idx = idxStart; idx != idxEnd; ++idx) {
2092
            auto& vertex = wireVertices[idx];
2093
            if (first) {
2094
                first = false;
2095
                pstart = vertex.pt();
2096
            }
2097
            else {
2098

2099
                // Originally here there was a call to the precompiler macro
2100
                // assertCheck(), which has been replaced with the precompiler
2101
                // macro assert()
2102

2103
                assert(pt.SquareDistance(vertex.pt()) < myTol2);
2104
            }
2105
            pt = vertex.ptOther();
2106
            splitEdges.push_back(vertex);
2107
        }
2108
        for (int i = stackPos; i >= stackStart; --i) {
2109
            const auto& vertex = vertexStack[stack[i].iCurrent];
2110

2111
            // Originally here there was a call to the precompiler macro
2112
            // assertCheck(), which has been replaced with the precompiler macro
2113
            // assert()
2114

2115
            assert(pt.SquareDistance(vertex.ptOther()) < myTol2);
2116
            pt = vertex.pt();
2117
            // The edges in the stack are the ones to slice
2118
            // the wire in half. We construct a new wire
2119
            // that includes the original beginning edge in
2120
            // the loop above. And this loop contains the
2121
            // other half. Note that the slicing edges
2122
            // should run in the oppsite direction, hence reversed
2123
            splitEdges.push_back(vertex.reversed());
2124
        }
2125
        for (int idx = idxV; idx != idxStart; ++idx) {
2126
            auto& vertex = wireVertices[idx];
2127

2128
            // Originally here there was a call to the precompiler macro
2129
            // assertCheck(), which has been replaced with the precompiler macro
2130
            // assert()
2131

2132
            assert(pt.SquareDistance(vertex.pt()) < myTol2);
2133
            pt = vertex.ptOther();
2134
            splitEdges.push_back(vertex);
2135
        }
2136

2137
        // Originally here there was a call to the precompiler macro
2138
        // assertCheck(), which has been replaced with the precompiler macro
2139
        // assert()
2140

2141
        assert(pt.SquareDistance(pstart) < myTol2);
2142
        showShape(*splitWire, "swire", iteration);
2143
    }
2144

2145
    // This method was originally part of WireJoinerP::findTightBound(), split to reduce cognitive
2146
    // complexity
2147
    void findTightBoundByVertices(EdgeInfo& beginInfo,
2148
                                  const std::vector<VertexInfo>& wireVertices,
2149
                                  int& idxV,
2150
                                  const int iteration2,
2151
                                  const gp_Pnt& pstart,
2152
                                  const std::shared_ptr<WireInfo>& wireInfo,
2153
                                  const VertexInfo& beginVertex,
2154
                                  std::shared_ptr<WireInfo>& newWire)
2155
    {
2156
        const int idx = wireVertices[idxV].start ? 1 : 0;
2157

2158
        auto current = wireVertices[idxV].edgeInfo();
2159
        showShape(current, "current", iteration);
2160

2161
        for (int vertex = current->iStart[idx]; vertex < current->iEnd[idx]; ++vertex) {
2162
            const auto& currentVertex = adjacentList[vertex];
2163
            auto next = currentVertex.edgeInfo();
2164
            if (next == current || next->iteration2 == iteration2 || next->iteration < 0) {
2165
                continue;
2166
            }
2167

2168
            showShape(next, "tcheck", iteration);
2169

2170
            if (!isInside(*wireInfo, next->mid)) {
2171
                showShape(next, "ninside", iteration);
2172
                next->iteration2 = iteration2;
2173
                continue;
2174
            }
2175

2176
            edgeSet.insert(next);
2177
            stack.emplace_back(vertexStack.size());
2178
            ++stack.back().iEnd;
2179
            vertexStack.push_back(currentVertex);
2180

2181
            // Originally here there was a call to the method checkStack(), which does
2182
            // nothing and therefor has been removed.
2183

2184
            int idxEnd = (int)wireVertices.size();
2185
            int stackStart = (int)stack.size() - 1;
2186
            int stackPos = (int)stack.size() - 1;
2187

2188
            TopoDS_Wire wire;
2189
            if (pstart.SquareDistance(currentVertex.ptOther()) > myTol2) {
2190
                wire = _findClosedWires(beginVertex,
2191
                                        currentVertex,
2192
                                        &idxEnd,
2193
                                        beginInfo.wireInfo,
2194
                                        &stackPos);
2195
                if (wire.IsNull()) {
2196
                    vertexStack.pop_back();
2197
                    stack.pop_back();
2198
                    edgeSet.erase(next);
2199
                    continue;
2200
                }
2201
            }
2202

2203
            newWire.reset(new WireInfo());
2204
            auto& newWireVertices = newWire->vertices;
2205
            newWireVertices.push_back(beginVertex);
2206
            for (auto& entry : stack) {
2207
                const auto& vertex = vertexStack[entry.iCurrent];
2208
                newWireVertices.push_back(vertex);
2209
            }
2210
            if (!wire.IsNull()) {
2211
                newWire->wire = wire;
2212
            }
2213
            else if (!initWireInfo(*newWire)) {
2214
                newWire.reset();
2215
                vertexStack.pop_back();
2216
                stack.pop_back();
2217
                edgeSet.erase(next);
2218
                continue;
2219
            }
2220
            for (auto& vertex : newWire->vertices) {
2221
                if (vertex.edgeInfo()->wireInfo == wireInfo) {
2222
                    vertex.edgeInfo()->wireInfo = newWire;
2223
                }
2224
            }
2225
            beginInfo.wireInfo = newWire;
2226
            showShape(*newWire, "nwire", iteration);
2227

2228
            std::shared_ptr<WireInfo> splitWire;
2229
            if (idxEnd == 0) {
2230
                idxEnd = (int)wireVertices.size();
2231
            }
2232
            ++idxV;
2233

2234
            // Originally here there was a call to the precompiler macro assertCheck(),
2235
            // which has been replaced with the precompiler macro assert()
2236

2237
            assert(idxV <= idxEnd);
2238
            int idxStart = idxV;
2239

2240
            findTightBoundSplitWire(wireInfo,
2241
                                    beginInfo,
2242
                                    wireVertices,
2243
                                    splitWire,
2244
                                    idxV,
2245
                                    idxStart,
2246
                                    idxEnd);
2247

2248
            if (splitWire) {
2249
                findTightBoundWithSplit(wireVertices,
2250
                                        idxV,
2251
                                        splitWire,
2252
                                        idxStart,
2253
                                        idxEnd,
2254
                                        stackPos,
2255
                                        stackStart);
2256
            }
2257

2258
            checkWireInfo(*newWire);
2259
            break;
2260
        }
2261
    }
2262

2263
    // This method was originally part of WireJoinerP::findTightBound(), split to reduce cognitive
2264
    // complexity
2265
    void findTightBoundUpdateVertices(EdgeInfo& beginInfo)
2266
    {
2267
        showShape(*beginInfo.wireInfo, "done", iteration);
2268
        beginInfo.wireInfo->done = true;
2269
        // If a wire is done, make sure all edges of this wire is
2270
        // marked as done. This can also prevent duplicated wires.
2271
        for (auto& vertex : beginInfo.wireInfo->vertices) {
2272
            auto info = vertex.edgeInfo();
2273
            if (!info->wireInfo) {
2274
                info->wireInfo = beginInfo.wireInfo;
2275
                continue;
2276
            }
2277
            if (info->wireInfo->done) {
2278
                continue;
2279
            }
2280
            auto otherWire = info->wireInfo;
2281
            auto& otherWireVertices = info->wireInfo->vertices;
2282
            if (info == otherWireVertices.front().edgeInfo()) {
2283
                // About to change the first edge of the other wireInfo.
2284
                // Try to find a new first edge for it.
2285
                tmpVertices.clear();
2286
                auto it = otherWireVertices.begin();
2287
                tmpVertices.push_back(*it);
2288
                for (++it; it != otherWireVertices.end(); ++it) {
2289
                    if (it->edgeInfo()->wireInfo == otherWire) {
2290
                        break;
2291
                    }
2292
                    tmpVertices.push_back(*it);
2293
                }
2294
                if (tmpVertices.size() != otherWireVertices.size()) {
2295
                    otherWireVertices.erase(otherWireVertices.begin(), it);
2296
                    otherWireVertices.insert(otherWireVertices.end(),
2297
                                             tmpVertices.begin(),
2298
                                             tmpVertices.end());
2299
                }
2300
            }
2301

2302
            // Originally here there was a call to the precompiler macro assertCheck(),
2303
            // which has been replaced with the precompiler macro assert()
2304

2305
            assert(info != &beginInfo);
2306
            info->wireInfo = beginInfo.wireInfo;
2307
            checkWireInfo(*otherWire);
2308
        }
2309
        checkWireInfo(*beginInfo.wireInfo);
2310
    }
2311

2312
    void findTightBound()
2313
    {
2314
        // Assumption: all edges lies on a common manifold surface
2315
        //
2316
        // Definition of 'Tight Bound': a wire that cannot be split into
2317
        // smaller wires by any intersecting edges internal to the wire.
2318
        //
2319
        // The idea of the searching algorithm is simple. The initial condition
2320
        // here is that we've found a closed wire for each edge. To find the
2321
        // tight bound, for each wire, check wire edge branches (using the
2322
        // adjacent list built earlier), and split the wire whenever possible.
2323

2324
        std::unique_ptr<Base::SequencerLauncher> seq(
2325
                new Base::SequencerLauncher("Finding tight bound", edges.size()));
2326

2327
        int iteration2 = iteration;
2328
        for (auto &info : edges) {
2329
            ++iteration;
2330
            seq->next(true);
2331
            if (info.iteration < 0 || !info.wireInfo) {
2332
                continue;
2333
            }
2334

2335
            ++iteration2;
2336
            while(!info.wireInfo->done) {
2337
                auto wireInfo = info.wireInfo;
2338
                checkWireInfo(*wireInfo);
2339
                const auto &wireVertices = wireInfo->vertices;
2340
                auto beginVertex = wireVertices.front();
2341
                auto &beginInfo = *beginVertex.it;
2342
                initWireInfo(*wireInfo);
2343
                showShape(wireInfo->wire, "iwire", iteration);
2344
                for (auto& vertex : wireVertices) {
2345
                    vertex.it->iteration2 = iteration2;
2346
                }
2347

2348
                stack.clear();
2349
                vertexStack.clear();
2350
                edgeSet.clear();
2351

2352
                std::shared_ptr<WireInfo> newWire;
2353
                gp_Pnt pstart = beginVertex.pt();
2354

2355
                int idxV = 0;
2356
                while (true) {
2357
                    findTightBoundByVertices(beginInfo,
2358
                                             wireVertices,
2359
                                             idxV,
2360
                                             iteration2,
2361
                                             pstart,
2362
                                             wireInfo,
2363
                                             beginVertex,
2364
                                             newWire);
2365

2366
                    if (newWire) {
2367
                        ++iteration;
2368
                        break;
2369
                    }
2370

2371
                    if (++idxV == (int)wireVertices.size()) {
2372
                        break;
2373
                    }
2374

2375
                    stack.emplace_back(vertexStack.size());
2376
                    ++stack.back().iEnd;
2377
                    vertexStack.push_back(wireVertices[idxV]);
2378
                    edgeSet.insert(wireVertices[idxV].edgeInfo());
2379

2380
                    // Originally here there was a call to the method checkStack(), which does
2381
                    // nothing and therefor has been removed.
2382
                }
2383

2384
                if (!newWire) {
2385
                    findTightBoundUpdateVertices(beginInfo);
2386
                }
2387
            }
2388
        }
2389
    }
2390

2391
    // This method was originally part of WireJoinerP::exhaustTightBound(), split to reduce cognitive
2392
    // complexity
2393
    void exhaustTightBoundUpdateVertex(const int iteration2,
2394
                                       const VertexInfo& beginVertex,
2395
                                       const int idxV,
2396
                                       const gp_Pnt& pstart,
2397
                                       const std::vector<VertexInfo>& wireVertices,
2398
                                       std::shared_ptr<WireInfo>& newWire,
2399
                                       const std::shared_ptr<WireInfo>& wireInfo)
2400
    {
2401
        const int idx = wireVertices[idxV].start ? 1 : 0;
2402
        auto current = wireVertices[idxV].edgeInfo();
2403

2404
        for (int vertex = current->iStart[idx]; vertex < current->iEnd[idx]; ++vertex) {
2405
            const auto& currentVertex = adjacentList[vertex];
2406
            auto next = currentVertex.edgeInfo();
2407
            if (next == current || next->iteration2 == iteration2 || next->iteration < 0) {
2408
                continue;
2409
            }
2410

2411
            showShape(next, "check2", iteration);
2412

2413
            if (!isInside(*wireInfo, next->mid)) {
2414
                showShape(next, "ninside2", iteration);
2415
                next->iteration2 = iteration2;
2416
                continue;
2417
            }
2418

2419
            edgeSet.insert(next);
2420
            stack.emplace_back(vertexStack.size());
2421
            ++stack.back().iEnd;
2422
            vertexStack.push_back(currentVertex);
2423

2424
            // Originally here there a call to the method checkStack(), which
2425
            // does nothing and therefor has been removed.
2426

2427
            TopoDS_Wire wire;
2428
            if (pstart.SquareDistance(currentVertex.ptOther()) > myTol2) {
2429
                wire = _findClosedWires(beginVertex, currentVertex, nullptr, wireInfo);
2430
                if (wire.IsNull()) {
2431
                    vertexStack.pop_back();
2432
                    stack.pop_back();
2433
                    edgeSet.erase(next);
2434
                    wireSet.erase(next->wireInfo.get());
2435
                    continue;
2436
                }
2437
            }
2438

2439
            newWire.reset(new WireInfo());
2440
            auto& newWireVertices = newWire->vertices;
2441
            newWireVertices.push_back(beginVertex);
2442
            for (auto& entry : stack) {
2443
                const auto& vertex = vertexStack[entry.iCurrent];
2444
                newWireVertices.push_back(vertex);
2445
            }
2446
            if (!wire.IsNull()) {
2447
                newWire->wire = wire;
2448
            }
2449
            else if (!initWireInfo(*newWire)) {
2450
                newWire.reset();
2451
                vertexStack.pop_back();
2452
                stack.pop_back();
2453
                edgeSet.erase(next);
2454
                wireSet.erase(next->wireInfo.get());
2455
                continue;
2456
            }
2457
            for (auto& vertex : newWire->vertices) {
2458
                if (vertex.edgeInfo()->wireInfo == wireInfo) {
2459
                    vertex.edgeInfo()->wireInfo = newWire;
2460
                }
2461
            }
2462
            showShape(*newWire, "nwire2", iteration);
2463
            checkWireInfo(*newWire);
2464
            break;
2465
        }
2466
    }
2467

2468
    // This method was originally part of WireJoinerP::exhaustTightBound(), split to reduce cognitive
2469
    // complexity
2470
    void exhaustTightBoundUpdateEdge(const int iteration2,
2471
                                     const VertexInfo& beginVertex,
2472
                                     const std::vector<VertexInfo>& wireVertices,
2473
                                     const gp_Pnt& pstart,
2474
                                     std::shared_ptr<WireInfo>& wireInfo)
2475
    {
2476
        std::shared_ptr<WireInfo> newWire;
2477

2478
        int idxV = 1;
2479
        while (true) {
2480
            exhaustTightBoundUpdateVertex(iteration2,
2481
                                          beginVertex,
2482
                                          idxV,
2483
                                          pstart,
2484
                                          wireVertices,
2485
                                          newWire,
2486
                                          wireInfo);
2487

2488
            if (newWire) {
2489
                ++iteration;
2490
                wireInfo = newWire;
2491
                break;
2492
            }
2493

2494
            if (++idxV == (int)wireVertices.size()) {
2495
                if (wireInfo->purge) {
2496
                    showShape(*wireInfo, "discard2", iteration);
2497
                    wireInfo.reset();
2498
                }
2499
                else {
2500
                    wireInfo->done = true;
2501
                    showShape(*wireInfo, "done2", iteration);
2502
                }
2503
                break;
2504
            }
2505
            stack.emplace_back(vertexStack.size());
2506
            ++stack.back().iEnd;
2507
            vertexStack.push_back(wireVertices[idxV]);
2508
            edgeSet.insert(wireVertices[idxV].edgeInfo());
2509

2510
            // Originally here there a call to the method checkStack(), which does
2511
            // nothing and therefor has been removed.
2512
        }
2513
    }
2514

2515
    // This method was originally part of WireJoinerP::exhaustTightBound(), split to reduce cognitive
2516
    // complexity
2517
    void exhaustTightBoundWithAdjacent(const EdgeInfo& info,
2518
                                       int& iteration2,
2519
                                       const VertexInfo beginVertex,
2520
                                       const EdgeInfo* check)
2521
    {
2522
        const gp_Pnt& pstart = beginVertex.pt();
2523
        const int vidx = beginVertex.start ? 1 : 0;
2524

2525
        edgeSet.clear();
2526
        vertexStack.clear();
2527
        stack.clear();
2528
        stack.emplace_back();
2529
        for (int i = info.iStart[vidx]; i < info.iEnd[vidx]; ++i) {
2530
            const auto& currentVertex = adjacentList[i];
2531
            auto next = currentVertex.edgeInfo();
2532
            if (next == &info || next == check || next->iteration < 0 || !next->wireInfo
2533
                || !next->wireInfo->done || next->wireInfo2) {
2534
                continue;
2535
            }
2536

2537
            showShape(next, "n2", iteration);
2538

2539
            stack.clear();
2540
            stack.emplace_back();
2541
            ++stack.back().iEnd;
2542
            vertexStack.clear();
2543
            vertexStack.push_back(currentVertex);
2544

2545
            edgeSet.clear();
2546
            edgeSet.insert(next);
2547
            wireSet.clear();
2548
            wireSet.insert(next->wireInfo.get());
2549

2550
            TopoDS_Wire wire;
2551
            if (pstart.SquareDistance(currentVertex.ptOther()) > myTol2) {
2552
                wire = _findClosedWires(beginVertex, currentVertex);
2553
                if (wire.IsNull()) {
2554
                    continue;
2555
                }
2556
            }
2557

2558
            std::shared_ptr<WireInfo> wireInfo(new WireInfo());
2559
            wireInfo->vertices.push_back(beginVertex);
2560
            for (auto& entry : stack) {
2561
                const auto& vertex = vertexStack[entry.iCurrent];
2562
                wireInfo->vertices.push_back(vertex);
2563
            }
2564
            if (!wire.IsNull()) {
2565
                wireInfo->wire = wire;
2566
            }
2567
            else if (!initWireInfo(*wireInfo)) {
2568
                continue;
2569
            }
2570

2571
            showShape(*wireInfo, "nw2", iteration);
2572

2573
            ++iteration;
2574
            ++iteration2;
2575

2576
            while (wireInfo && !wireInfo->done) {
2577
                showShape(next, "next2", iteration);
2578

2579
                vertexStack.resize(1);
2580
                stack.resize(1);
2581
                edgeSet.clear();
2582
                edgeSet.insert(next);
2583
                wireSet.clear();
2584
                wireSet.insert(next->wireInfo.get());
2585

2586
                const auto& wireVertices = wireInfo->vertices;
2587
                initWireInfo(*wireInfo);
2588
                for (auto& vertex : wireVertices) {
2589
                    vertex.it->iteration2 = iteration2;
2590
                }
2591

2592
                exhaustTightBoundUpdateEdge(iteration2,
2593
                                            beginVertex,
2594
                                            wireVertices,
2595
                                            pstart,
2596
                                            wireInfo);
2597
            }
2598

2599
            if (wireInfo && wireInfo->done) {
2600
                for (auto& vertex : wireInfo->vertices) {
2601
                    auto edgeInfo = vertex.edgeInfo();
2602

2603
                    // Originally here there was a call to the precompiler macro
2604
                    // assertCheck(), which has been replaced with the precompiler macro
2605
                    // assert()
2606

2607
                    assert(edgeInfo->wireInfo != nullptr);
2608
                    if (edgeInfo->wireInfo->isSame(*wireInfo)) {
2609
                        wireInfo = edgeInfo->wireInfo;
2610
                        break;
2611
                    }
2612
                }
2613
                for (auto& vertex : wireInfo->vertices) {
2614
                    auto edgeInfo = vertex.edgeInfo();
2615
                    if (!edgeInfo->wireInfo2 && edgeInfo->wireInfo != wireInfo) {
2616
                        edgeInfo->wireInfo2 = wireInfo;
2617
                    }
2618
                }
2619

2620
                // Originally here there were two calls to the precompiler macro
2621
                // assertCheck(), which have been replaced with the precompiler macro
2622
                // assert()
2623

2624
                assert(info.wireInfo2 == wireInfo);
2625
                assert(info.wireInfo2 != info.wireInfo);
2626
                showShape(*wireInfo, "exhaust");
2627
                break;
2628
            }
2629
        }
2630
    }
2631

2632
    // This method was originally part of WireJoinerP::exhaustTightBound(), split to reduce cognitive
2633
    // complexity
2634
    void exhaustTightBoundUpdateWire(const EdgeInfo& info, int& iteration2)
2635
    {
2636

2637
        showShape(*info.wireInfo, "iwire2", iteration);
2638
        showShape(&info, "begin2", iteration);
2639

2640
        int idx = info.wireInfo->find(&info);
2641

2642
        // Originally here there was a call to the precompiler macro assertCheck(), which has
2643
        // been replaced with the precompiler macro assert()
2644

2645
        assert(idx > 0);
2646
        const auto& vertices = info.wireInfo->vertices;
2647
        --idx;
2648
        int nextIdx = idx == (int)vertices.size() - 1 ? 0 : idx + 1;
2649
        int prevIdx = idx == 0 ? (int)vertices.size() - 1 : idx - 1;
2650
        int count = prevIdx == nextIdx ? 1 : 2;
2651
        for (int idxV = 0; idxV < count && !info.wireInfo2; ++idxV) {
2652
            auto check = vertices[idxV == 0 ? nextIdx : prevIdx].edgeInfo();
2653
            auto beginVertex = vertices[idx];
2654
            if (idxV == 1) {
2655
                beginVertex.start = !beginVertex.start;
2656
            }
2657

2658
            exhaustTightBoundWithAdjacent(info, iteration2, beginVertex, check);
2659
        }
2660
    }
2661

2662
    void exhaustTightBound()
2663
    {
2664
        // findTightBound() function will find a tight bound wire for each
2665
        // edge. Now we try to find all possible tight bound wires, relying on
2666
        // the important fact that an edge can be shared by at most two tight
2667
        // bound wires.
2668

2669
        std::unique_ptr<Base::SequencerLauncher> seq(
2670
                new Base::SequencerLauncher("Exhaust tight bound", edges.size()));
2671

2672
        for (auto &info : edges) {
2673
            if (info.iteration < 0 || !info.wireInfo || !info.wireInfo->done) {
2674
                continue;
2675
            }
2676
            for (auto &vertex : info.wireInfo->vertices) {
2677
                auto edgeInfo = vertex.edgeInfo();
2678
                if (edgeInfo->wireInfo != info.wireInfo) {
2679
                    edgeInfo->wireInfo2 = info.wireInfo;
2680
                }
2681
            }
2682
        }
2683

2684
        int iteration2 = iteration;
2685
        for (auto &info : edges) {
2686
            ++iteration;
2687
            seq->next(true);
2688
            if (info.iteration < 0
2689
                    || !info.wireInfo
2690
                    || !info.wireInfo->done)
2691
            {
2692
                if (info.wireInfo) {
2693
                    showShape(*info.wireInfo, "iskip");
2694
                }
2695
                else {
2696
                    showShape(&info, "iskip");
2697
                }
2698
                continue;
2699
            }
2700

2701
            if (info.wireInfo2 && info.wireInfo2->done) {
2702
                showShape(*info.wireInfo, "idone");
2703
                continue;
2704
            }
2705

2706
            exhaustTightBoundUpdateWire(info, iteration2);
2707

2708
        }
2709
        wireSet.clear();
2710
    }
2711

2712
    // This method was originally part of WireJoinerP::makeCleanWire(), split to reduce cognitive
2713
    // complexity
2714
    void printHistoryInit(const Handle_BRepTools_History& newHistory,
2715
                          const std::vector<TopoShape>& inputEdges)
2716
    {
2717
        FC_MSG("init:");
2718
        for (const auto& shape : sourceEdges) {
2719
#if OCC_VERSION_HEX < 0x070800
2720
            FC_MSG(shape.getShape().TShape().get() << ", " << shape.getShape().HashCode(INT_MAX));
2721
#else
2722
            FC_MSG(shape.getShape().TShape().get()
2723
                   << ", " << std::hash<TopoDS_Shape> {}(shape.getShape()));
2724
#endif
2725
        }
2726
        printHistory(aHistory, sourceEdges);
2727
        printHistory(newHistory, inputEdges);
2728
    }
2729

2730
    // This method was originally part of WireJoinerP::makeCleanWire(), split to reduce cognitive
2731
    // complexity
2732
    void printHistoryFinal()
2733
    {
2734
        printHistory(aHistory, sourceEdges);
2735
        FC_MSG("final:");
2736
        for (int i = 1; i <= wireData->NbEdges(); ++i) {
2737
            auto shape = wireData->Edge(i);
2738
#if OCC_VERSION_HEX < 0x070800
2739
            FC_MSG(shape.TShape().get() << ", " << shape.HashCode(INT_MAX));
2740
#else
2741
            FC_MSG(shape.TShape().get() << ", " << std::hash<TopoDS_Edge> {}(shape));
2742
#endif
2743
        }
2744
    }
2745

2746
    TopoDS_Wire makeCleanWire(bool fixGap=true)
2747
    {
2748
        // Make a clean wire with sorted, oriented, connected, etc edges
2749
        TopoDS_Wire result;
2750
        std::vector<TopoShape> inputEdges;
2751

2752
        if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_TRACE)) {
2753
            for (int i = 1; i <= wireData->NbEdges(); ++i) {
2754
                inputEdges.emplace_back(wireData->Edge(i));
2755
            }
2756
        }
2757

2758
        ShapeFix_Wire fixer;
2759
        Handle(ShapeBuild_ReShape) reshape = new ShapeBuild_ReShape();
2760
        fixer.SetContext(reshape);
2761
        fixer.Load(wireData);
2762
        fixer.SetMaxTolerance(myTol);
2763
        fixer.ClosedWireMode() = Standard_True;
2764
        fixer.Perform();
2765
        // fixer.FixReorder();
2766
        // fixer.FixConnected();
2767

2768
        if (fixGap) {
2769
            // Gap fixing may change vertex, but we need all concident vertexes
2770
            // to be the same one.
2771
            //
2772
            // fixer.FixGap3d(1, Standard_True);
2773
        }
2774

2775
        fixer.FixClosed();
2776

2777
        result = fixer.Wire();
2778
        auto newHistory = fixer.Context()->History();
2779

2780

2781
        if (FC_LOG_INSTANCE.level() > FC_LOGLEVEL_TRACE + 1) {
2782
            printHistoryInit(newHistory, inputEdges);
2783
        }
2784

2785
        aHistory->Merge(newHistory);
2786

2787

2788
        if (FC_LOG_INSTANCE.level() > FC_LOGLEVEL_TRACE + 1) {
2789
            printHistoryFinal();
2790
        }
2791

2792
        return result;
2793
    }
2794

2795
    // This method was originally part of WireJoinerP::printHistory(), split to reduce cognitive
2796
    // complexity
2797
    template<class T>
2798
    void printHistoryOfShape(const Handle(BRepTools_History)& hist, const T& shape)
2799
    {
2800
        for (TopTools_ListIteratorOfListOfShape it(hist->Modified(shape.getShape())); it.More();
2801
             it.Next()) {
2802
#if OCC_VERSION_HEX < 0x070800
2803
            FC_MSG(shape.getShape().TShape().get()
2804
                   << ", " << shape.getShape().HashCode(INT_MAX) << " -> "
2805
                   << it.Value().TShape().get() << ", " << it.Value().HashCode(INT_MAX));
2806
#else
2807
            FC_MSG(shape.getShape().TShape().get()
2808
                   << ", " << std::hash<TopoDS_Shape> {}(shape.getShape()) << " -> "
2809
                   << it.Value().TShape().get() << ", " << std::hash<TopoDS_Shape> {}(it.Value()));
2810
#endif
2811
        }
2812
    }
2813

2814
    template<class T>
2815
    void printHistory(Handle(BRepTools_History) hist, const T &input)
2816
    {
2817
        FC_MSG("\nHistory:\n");
2818
        for (const auto& shape : input) {
2819
            printHistoryOfShape(hist, shape);
2820
        }
2821
    }
2822

2823
    bool canShowShape(int idx=-1, bool forced=false) const
2824
    {
2825
        if (idx < 0 || catchIteration == 0 || catchIteration > idx) {
2826
            if (!forced && FC_LOG_INSTANCE.level() <= FC_LOGLEVEL_TRACE) {
2827
                return false;
2828
            }
2829
        }
2830
        return true;
2831
    }
2832

2833
    void showShape(const EdgeInfo* info, const char* name, int idx = -1, bool forced = false) const
2834
    {
2835
        if (!canShowShape(idx, forced)) {
2836
            return;
2837
        }
2838
        showShape(info->shape(), name, idx, forced);
2839
    }
2840

2841
    void showShape(WireInfo &wireInfo, const char *name, int idx=-1, bool forced=false)
2842
    {
2843
        if (!canShowShape(idx, forced)) {
2844
            return;
2845
        }
2846
        if (wireInfo.wire.IsNull()) {
2847
            initWireInfo(wireInfo);
2848
        }
2849
        showShape(wireInfo.wire, name, idx, forced);
2850
    }
2851

2852
    void showShape(const TopoDS_Shape& sToShow,
2853
                   const char* name,
2854
                   int idx = -1,
2855
                   bool forced = false) const
2856
    {
2857
        if (!canShowShape(idx, forced)) {
2858
            return;
2859
        }
2860
        std::string _name;
2861
        if (idx >= 0) {
2862
            _name = name;
2863
            _name += "_";
2864
            _name += std::to_string(idx);
2865
            _name += "_";
2866
            name = _name.c_str();
2867
        }
2868
        auto obj = Feature::create(sToShow, name);
2869
        FC_MSG(obj->getNameInDocument() << " " << ShapeHasher()(sToShow));
2870
        if (catchObject == obj->getNameInDocument()) {
2871
            FC_MSG("found");
2872
        }
2873
    }
2874

2875
    // This method was originally part of WireJoinerP::build(), split to reduce cognitive complexity
2876
    void buildClosedWire()
2877
    {
2878
        findClosedWires(true);
2879
        findTightBound();
2880
        exhaustTightBound();
2881
        bool done = !doOutline;
2882
        while (!done) {
2883
            ++iteration;
2884
            done = true;
2885
            std::unordered_map<EdgeInfo*, int> counter;
2886
            std::unordered_set<WireInfo*> wires;
2887
            for (auto& info : edges) {
2888
                if (info.iteration == -2) {
2889
                    continue;
2890
                }
2891
                if (info.iteration < 0 || !info.wireInfo || !info.wireInfo->done) {
2892
                    if (info.iteration >= 0) {
2893
                        info.iteration = -1;
2894
                        done = false;
2895
                        showShape(&info, "removed", iteration);
2896
                        aHistory->Remove(info.edge);
2897
                    }
2898
                    continue;
2899
                }
2900
                if (info.wireInfo2 && wires.insert(info.wireInfo2.get()).second) {
2901
                    for (auto& vertex : info.wireInfo2->vertices) {
2902
                        if (++counter[vertex.edgeInfo()] == 2) {
2903
                            vertex.edgeInfo()->iteration = -1;
2904
                            done = false;
2905
                            showShape(vertex.edgeInfo(), "removed2", iteration);
2906
                            aHistory->Remove(info.edge);
2907
                        }
2908
                    }
2909
                }
2910
                if (!wires.insert(info.wireInfo.get()).second) {
2911
                    continue;
2912
                }
2913
                for (auto& vertex : info.wireInfo->vertices) {
2914
                    if (++counter[vertex.edgeInfo()] == 2) {
2915
                        vertex.edgeInfo()->iteration = -1;
2916
                        done = false;
2917
                        showShape(vertex.edgeInfo(), "removed1", iteration);
2918
                        aHistory->Remove(info.edge);
2919
                    }
2920
                }
2921
            }
2922
            findClosedWires(true);
2923
            findTightBound();
2924
        }
2925

2926
        builder.MakeCompound(compound);
2927
        wireSet.clear();
2928
        for (auto& info : edges) {
2929
            if (info.iteration == -2) {
2930
                if (!info.wireInfo) {
2931
                    builder.Add(compound, info.wire());
2932
                    continue;
2933
                }
2934
                addWire(info.wireInfo);
2935
                addWire(info.wireInfo2);
2936
            }
2937
            else if (info.iteration >= 0) {
2938
                addWire(info.wireInfo2);
2939
                addWire(info.wireInfo);
2940
            }
2941
        }
2942
        wireSet.clear();
2943
    }
2944

2945
    void build()
2946
    {
2947
        clear();
2948
        sourceEdges.clear();
2949
        sourceEdges.insert(sourceEdgeArray.begin(), sourceEdgeArray.end());
2950
        for (const auto& edge : sourceEdgeArray) {
2951
            add(TopoDS::Edge(edge.getShape()), true);
2952
        }
2953

2954
        if (doTightBound || doSplitEdge) {
2955
            splitEdges();
2956
        }
2957

2958
        buildAdjacentList();
2959

2960
        if (!doTightBound && !doOutline) {
2961
            findClosedWires();
2962
        }
2963
        else {
2964
            buildClosedWire();
2965
        }
2966

2967
        // TODO: We choose to put open wires in a separated shape from the final
2968
        // result shape, so the history may contains some entries that are not
2969
        // presented in the final result, which will cause warning message when
2970
        // generating topo naming in TopoShape::makESHAPE(). We've lowered log
2971
        // message level to suppress the warning for the moment. The right way
2972
        // to solve the problem is to reconstruct the history and filter out
2973
        // those entries.
2974

2975
        bool hasOpenEdge = false;
2976
        for (const auto &info : edges) {
2977
            if (info.iteration == -3 || (!info.wireInfo && info.iteration>=0)) {
2978
                if (!hasOpenEdge) {
2979
                    hasOpenEdge = true;
2980
                    builder.MakeCompound(openWireCompound);
2981
                }
2982
                builder.Add(openWireCompound, info.wire());
2983
            }
2984
        }
2985
    }
2986

2987
    void addWire(std::shared_ptr<WireInfo> &wireInfo)
2988
    {
2989
        if (!wireInfo || !wireInfo->done || !wireSet.insertUnique(wireInfo.get())) {
2990
            return;
2991
        }
2992
        initWireInfo(*wireInfo);
2993
        builder.Add(compound, wireInfo->wire);
2994
    }
2995

2996
    bool getOpenWires(TopoShape &shape, const char *op, bool noOriginal) {
2997
        if (openWireCompound.IsNull()) {
2998
            shape.setShape(TopoShape());
2999
            return false;
3000
        }
3001
        auto comp = openWireCompound;
3002
        if (noOriginal) {
3003
            TopoShape source(-1);
3004
            source.makeElementCompound(sourceEdgeArray);
3005
            auto wires = TopoShape(openWireCompound, -1).getSubTopoShapes(TopAbs_WIRE);
3006
            bool touched = false;
3007
            for (auto it=wires.begin(); it!=wires.end();) {
3008
                bool purge = true;
3009
                for (const auto &edge : it->getSubShapes(TopAbs_EDGE)) {
3010
                    if (source.findSubShapesWithSharedVertex(TopoShape(edge, -1)).empty()) {
3011
                        purge = false;
3012
                        break;
3013
                    }
3014
                }
3015
                if (purge) {
3016
                    it = wires.erase(it);
3017
                    touched = true;
3018
                }
3019
                else {
3020
                    ++it;
3021
                }
3022
            }
3023
            if (touched) {
3024
                if (wires.empty()) {
3025
                    shape.setShape(TopoShape());
3026
                    return false;
3027
                }
3028
                comp = TopoDS::Compound(TopoShape(-1).makeElementCompound(wires).getShape());
3029
            }
3030
        }
3031
        shape.makeShapeWithElementMap(comp,
3032
                        MapperHistory(aHistory),
3033
                        {sourceEdges.begin(), sourceEdges.end()},
3034
                        op);
3035
        return true;
3036
    }
3037

3038
    bool getResultWires(TopoShape &shape, const char *op) {
3039
        // As compound is created by various calls to builder.MakeCompound() it looks that the
3040
        // following condition is always false.
3041
        // Probably it may be needed to add something like compound.Nullify() as done for
3042
        // openWireCompound in WireJoiner::WireJoinerP::clear()
3043
        if (compound.IsNull()) {
3044
            shape.setShape(TopoShape());
3045
            return false;
3046
        }
3047
        shape.makeShapeWithElementMap(compound,
3048
                        MapperHistory(aHistory),
3049
                        {sourceEdges.begin(), sourceEdges.end()},
3050
                        op);
3051
        return true;
3052
    }
3053
};
3054

3055

3056
WireJoiner::WireJoiner()
3057
    :pimpl(new WireJoinerP())
3058
{
3059
}
3060

3061
WireJoiner::~WireJoiner() = default;
3062

3063
void WireJoiner::addShape(const TopoShape &shape)
3064
{
3065
    NotDone();
3066
    for (auto& edge : shape.getSubTopoShapes(TopAbs_EDGE)) {
3067
        pimpl->sourceEdgeArray.push_back(edge);
3068
    }
3069
}
3070

3071
void WireJoiner::addShape(const std::vector<TopoShape> &shapes)
3072
{
3073
    NotDone();
3074
    for (const auto &shape : shapes) {
3075
        for (auto& edge : shape.getSubTopoShapes(TopAbs_EDGE)) {
3076
            pimpl->sourceEdgeArray.push_back(edge);
3077
        }
3078
    }
3079
}
3080

3081
void WireJoiner::addShape(const std::vector<TopoDS_Shape> &shapes)
3082
{
3083
    NotDone();
3084
    for (const auto &shape : shapes) {
3085
        for (TopExp_Explorer xp(shape, TopAbs_EDGE); xp.More(); xp.Next()) {
3086
            pimpl->sourceEdgeArray.emplace_back(TopoDS::Edge(xp.Current()), -1);
3087
        }
3088
    }
3089
}
3090

3091
void WireJoiner::setOutline(bool enable)
3092
{
3093
    if (enable != pimpl->doOutline) {
3094
        NotDone();
3095
        pimpl->doOutline = enable;
3096
    }
3097
}
3098

3099
void WireJoiner::setTightBound(bool enable)
3100
{
3101
    if (enable != pimpl->doTightBound) {
3102
        NotDone();
3103
        pimpl->doTightBound = enable;
3104
    }
3105
}
3106

3107
void WireJoiner::setSplitEdges(bool enable)
3108
{
3109
    if (enable != pimpl->doSplitEdge) {
3110
        NotDone();
3111
        pimpl->doSplitEdge = enable;
3112
    }
3113
}
3114

3115
void WireJoiner::setMergeEdges(bool enable)
3116
{
3117
    if (enable != pimpl->doSplitEdge) {
3118
        NotDone();
3119
        pimpl->doMergeEdge = enable;
3120
    }
3121
}
3122

3123
void WireJoiner::setTolerance(double tol, double atol)
3124
{
3125
    if (tol >= 0 && tol != pimpl->myTol) {
3126
        NotDone();
3127
        pimpl->myTol = tol;
3128
        pimpl->myTol2 = tol * tol;
3129
    }
3130
    if (atol >= 0 && atol != pimpl->myAngularTol) {
3131
        NotDone();
3132
        pimpl->myAngularTol = atol;
3133
    }
3134
}
3135

3136
#if OCC_VERSION_HEX < 0x070600
3137
void WireJoiner::Build()
3138
{
3139
#else
3140
void WireJoiner::Build(const Message_ProgressRange& theRange)
3141
{
3142
    (void)theRange;
3143
#endif
3144
    if (IsDone()) {
3145
        return;
3146
    }
3147
    pimpl->build();
3148
    if (TopoShape(pimpl->compound).countSubShapes(TopAbs_SHAPE) > 0) {
3149
        myShape = pimpl->compound;
3150
    }
3151
    else {
3152
        myShape.Nullify();
3153
    }
3154
    Done();
3155
}
3156

3157
bool WireJoiner::getOpenWires(TopoShape &shape, const char *op, bool noOriginal)
3158
{
3159
    Build();
3160
    return pimpl->getOpenWires(shape, op, noOriginal);
3161
}
3162

3163
bool WireJoiner::getResultWires(TopoShape &shape, const char *op)
3164
{
3165
    Build();
3166
    return pimpl->getResultWires(shape, op);
3167
}
3168

3169
const TopTools_ListOfShape& WireJoiner::Generated (const TopoDS_Shape& SThatGenerates)
3170
{
3171
    Build();
3172
    return pimpl->aHistory->Generated(SThatGenerates);
3173
}
3174

3175
const TopTools_ListOfShape& WireJoiner::Modified (const TopoDS_Shape& SThatModifies)
3176
{
3177
    Build();
3178
    return pimpl->aHistory->Modified(SThatModifies);
3179
}
3180

3181
Standard_Boolean WireJoiner::IsDeleted (const TopoDS_Shape& SDeleted)
3182
{
3183
    Build();
3184
    return pimpl->aHistory->IsRemoved(SDeleted);
3185
}
3186
FreeCAD

Использование cookies
