1 // Created by: Peter KURNEV
2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
4 // This file is part of Open CASCADE Technology software library.
6 // This library is free software; you can redistribute it and/or modify it under
7 // the terms of the GNU Lesser General Public License version 2.1 as published
8 // by the Free Software Foundation, with special exception defined in the file
9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
10 // distribution for complete text of the license and disclaimer of any warranty.
12 // Alternatively, this file may be used under the terms of Open CASCADE
13 // commercial license or contractual agreement.
16 #include <BOPAlgo_Tools.hxx>
18 #include <BOPAlgo_Builder.hxx>
19 #include <BOPAlgo_BuilderFace.hxx>
20 #include <BOPDS_CommonBlock.hxx>
21 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
22 #include <BOPDS_DS.hxx>
23 #include <BOPDS_IndexedMapOfPaveBlock.hxx>
24 #include <BOPDS_MapOfPaveBlock.hxx>
25 #include <BOPDS_PaveBlock.hxx>
26 #include <BOPTools_AlgoTools.hxx>
27 #include <BOPTools_AlgoTools2D.hxx>
28 #include <BOPTools_BoxTree.hxx>
29 #include <BOPTools_Parallel.hxx>
30 #include <BRep_Builder.hxx>
31 #include <BRep_Tool.hxx>
32 #include <BRepAdaptor_Curve.hxx>
33 #include <BRepBndLib.hxx>
34 #include <BRepBuilderAPI_MakeFace.hxx>
35 #include <BRepLib.hxx>
36 #include <Bnd_Tools.hxx>
37 #include <GeomAPI_ProjectPointOnCurve.hxx>
38 #include <GeomAPI_ProjectPointOnSurf.hxx>
39 #include <gp_Circ.hxx>
41 #include <gp_Elips.hxx>
42 #include <gp_Hypr.hxx>
43 #include <gp_Parab.hxx>
47 #include <IntTools_Context.hxx>
48 #include <NCollection_IncAllocator.hxx>
49 #include <NCollection_Vector.hxx>
50 #include <Standard_ErrorHandler.hxx>
51 #include <Standard_Failure.hxx>
52 #include <TColStd_IndexedMapOfInteger.hxx>
54 #include <TopExp_Explorer.hxx>
56 #include <TopoDS_Edge.hxx>
57 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
58 #include <TopTools_IndexedMapOfShape.hxx>
59 #include <TopTools_MapOfShape.hxx>
63 typedef NCollection_IndexedDataMap
64 <TopoDS_Shape, gp_Dir, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapeDir;
65 typedef NCollection_IndexedDataMap
66 <TopoDS_Shape, gp_Pln, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapePln;
69 void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
70 TopoDS_Compound& theWires,
71 const Standard_Boolean theCheckUniquePlane,
72 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
73 TopTools_MapOfShape& theMEdgesNoUniquePlane);
76 Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
80 Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
82 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
83 TopTools_MapOfShape& theMEdgesNoUniquePlane);
86 Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
87 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
91 Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
94 //=======================================================================
97 //=======================================================================
98 void BOPAlgo_Tools::FillMap(const Handle(BOPDS_PaveBlock)& aPB,
99 const Standard_Integer nF,
100 BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
101 const Handle(NCollection_BaseAllocator)& aAllocator)
103 TColStd_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB);
105 pLI = &aMPBLI(aMPBLI.Add(aPB, TColStd_ListOfInteger(aAllocator)));
109 //=======================================================================
110 //function : PerformCommonBlocks
112 //=======================================================================
113 void BOPAlgo_Tools::PerformCommonBlocks(BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock& aMPBLPB,
114 const Handle(NCollection_BaseAllocator)& aAllocator,
116 const Handle(IntTools_Context)& theContext)
118 Standard_Integer aNbCB;
120 aNbCB=aMPBLPB.Extent();
124 // Make Blocks of the pave blocks
125 NCollection_List<BOPDS_ListOfPaveBlock> aMBlocks(aAllocator);
126 BOPAlgo_Tools::MakeBlocks<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aMPBLPB, aMBlocks, aAllocator);
128 // Use temporary allocator for the local fence map
129 Handle(NCollection_IncAllocator) anAllocTmp = new NCollection_IncAllocator;
131 NCollection_List<BOPDS_ListOfPaveBlock>::Iterator aItB(aMBlocks);
132 for (; aItB.More(); aItB.Next()) {
133 const BOPDS_ListOfPaveBlock& aLPB = aItB.Value();
134 Standard_Integer aNbPB = aLPB.Extent();
138 // Reset the allocator
141 Handle(BOPDS_CommonBlock) aCB;
142 // Faces of the common block
143 TColStd_ListOfInteger aLFaces;
144 // Fence map to avoid duplicates in the list of faces of the common block
145 TColStd_MapOfInteger aMFaces(1, anAllocTmp);
147 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
148 for (; aItLPB.More(); aItLPB.Next())
150 const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
151 if (pDS->IsCommonBlock(aPB))
153 const Handle(BOPDS_CommonBlock)& aCBx = pDS->CommonBlock(aPB);
154 // Move all faces to the new common block
155 TColStd_ListIteratorOfListOfInteger aItLF(aCBx->Faces());
156 for (; aItLF.More(); aItLF.Next())
158 const Standard_Integer nF = aItLF.Value();
159 // Append to common list avoiding duplicates
169 aCB = new BOPDS_CommonBlock;
171 aCB->SetPaveBlocks(aLPB);
172 aCB->SetFaces(aLFaces);
173 for (aItLPB.Initialize(aLPB); aItLPB.More(); aItLPB.Next())
174 pDS->SetCommonBlock(aItLPB.Value(), aCB);
176 // Compute tolerance for Common Block
177 Standard_Real aTolCB = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, pDS, theContext);
178 aCB->SetTolerance(aTolCB);
181 //=======================================================================
182 //function : PerformCommonBlocks
184 //=======================================================================
185 void BOPAlgo_Tools::PerformCommonBlocks(const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
186 const Handle(NCollection_BaseAllocator)& ,//aAllocator
188 const Handle(IntTools_Context)& theContext)
190 Standard_Integer nF, i, aNb;
191 TColStd_ListIteratorOfListOfInteger aItLI;
192 Handle(BOPDS_PaveBlock) aPB;
193 Handle(BOPDS_CommonBlock) aCB;
196 for (i=1; i<=aNb; ++i) {
197 aPB=aMPBLI.FindKey(i);
198 if (pDS->IsCommonBlock(aPB)) {
199 aCB=pDS->CommonBlock(aPB);
202 aCB=new BOPDS_CommonBlock;
203 aCB->AddPaveBlock(aPB);
206 const TColStd_ListOfInteger& aLI=aMPBLI.FindFromKey(aPB);
207 TColStd_ListOfInteger aNewFaces;
208 const TColStd_ListOfInteger& anOldFaces = aCB->Faces();
209 aItLI.Initialize(aLI);
210 for (; aItLI.More(); aItLI.Next()) {
212 // the both lists aLI and anOldFaces are expected to be short,
213 // so we can allow to run nested loop here
214 TColStd_ListIteratorOfListOfInteger it(anOldFaces);
215 for (; it.More(); it.Next()) {
216 if (it.Value() == nF)
220 aNewFaces.Append(nF);
223 aCB->AppendFaces(aNewFaces);
224 pDS->SetCommonBlock(aPB, aCB);
225 // Compute tolerance for Common Block
226 Standard_Real aTolCB = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, pDS, theContext);
227 aCB->SetTolerance(aTolCB);
230 //=======================================================================
231 //function : ComputeToleranceOfCB
233 //=======================================================================
234 Standard_Real BOPAlgo_Tools::ComputeToleranceOfCB
235 (const Handle(BOPDS_CommonBlock)& theCB,
236 const BOPDS_PDS theDS,
237 const Handle(IntTools_Context)& theContext)
239 Standard_Real aTolMax = 0.;
240 if (theCB.IsNull()) {
244 const Handle(BOPDS_PaveBlock)& aPBR = theCB->PaveBlock1();
245 Standard_Integer nE = aPBR->OriginalEdge();
246 const TopoDS_Edge& aEOr = *(TopoDS_Edge*)&theDS->Shape(nE);
247 aTolMax = BRep_Tool::Tolerance(aEOr);
249 const BOPDS_ListOfPaveBlock& aLPB = theCB->PaveBlocks();
250 const TColStd_ListOfInteger& aLFI = theCB->Faces();
252 if ((aLPB.Extent() < 2) && aLFI.IsEmpty()) {
256 const Standard_Integer aNbPnt = 11;
257 Standard_Real aTol, aT, aT1, aT2, aDt;
260 const Handle(Geom_Curve)& aC3D = BRep_Tool::Curve(aEOr, aT1, aT2);
262 aPBR->Range(aT1, aT2);
263 aDt = (aT2 - aT1) / (aNbPnt + 1);
265 Handle(IntTools_Context) aCtx = theContext;
267 aCtx = new IntTools_Context();
269 // compute max tolerance for common blocks on edges
270 if (aLPB.Extent() > 1) {
271 // compute max distance between edges
272 BOPDS_ListIteratorOfListOfPaveBlock aItPB;
273 GeomAPI_ProjectPointOnCurve aProjPC;
275 aItPB.Initialize(aLPB);
276 for (; aItPB.More(); aItPB.Next()) {
277 const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
282 nE = aPB->OriginalEdge();
283 const TopoDS_Edge& aE = *(TopoDS_Edge*)&theDS->Shape(nE);
284 aTol = BRep_Tool::Tolerance(aE);
286 aProjPC = aCtx->ProjPC(aE);
289 for (Standard_Integer i=1; i <= aNbPnt; i++) {
293 if (aProjPC.NbPoints()) {
294 Standard_Real aTolNew = aTol + aProjPC.LowerDistance();
295 if (aTolNew > aTolMax) {
303 // compute max tolerance for common blocks on faces
306 GeomAPI_ProjectPointOnSurf aProjPS;
307 TColStd_ListIteratorOfListOfInteger aItLI;
309 aItLI.Initialize(aLFI);
310 for (; aItLI.More(); aItLI.Next()) {
312 const TopoDS_Face& aF = *(TopoDS_Face*)&theDS->Shape(nF);
313 aTol = BRep_Tool::Tolerance(aF);
315 aProjPS = aCtx->ProjPS(aF);
318 for (Standard_Integer i=1; i <= aNbPnt; i++) {
322 if (aProjPS.NbPoints()) {
323 Standard_Real aTolNew = aTol + aProjPS.LowerDistance();
324 if (aTolNew > aTolMax) {
335 //=======================================================================
336 //function : EdgesToWires
338 //=======================================================================
339 Standard_Integer BOPAlgo_Tools::EdgesToWires(const TopoDS_Shape& theEdges,
340 TopoDS_Shape& theWires,
341 const Standard_Boolean theShared,
342 const Standard_Real theAngTol)
344 Standard_Integer iErr = 0;
346 // 1. Check the input edges
348 // List of edges to process
349 TopTools_ListOfShape aLE;
351 TopExp_Explorer aExp(theEdges, TopAbs_EDGE);
352 for (; aExp.More(); aExp.Next()) {
353 const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
354 if (!BRep_Tool::Degenerated(aE) && BRep_Tool::IsGeometric(aE)) {
355 aLE.Append(aExp.Current());
360 // no edges to process
366 TopoDS_Compound aRWires;
367 aBB.MakeCompound(aRWires);
369 if (aLE.Extent() == 1) {
372 aBB.Add(aWire, aLE.First());
373 aBB.Add(aRWires, aWire);
378 // 2. Make compound of shared edges
379 TopoDS_Shape aSEdges;
382 // intersect the edges if necessary
384 aGF.SetArguments(aLE);
386 if (aGF.HasErrors()) {
387 // unable to share the edges
392 aSEdges = aGF.Shape();
395 aBB.MakeCompound(TopoDS::Compound(aSEdges));
396 TopTools_ListIteratorOfListOfShape aItLE(aLE);
397 for (; aItLE.More(); aItLE.Next()) {
398 aBB.Add(aSEdges, aItLE.Value());
402 // 3. Find edges located in the same planes and make wires from them.
403 // If the plane cannot be found for a single edge, then it is necessary
404 // to find all pairs of connected edges with the same cross product.
406 // Try to compute the plane in which the edge is located
407 BOPAlgo_IndexedDataMapOfShapePln aDMEdgePln;
408 // Compute the tangent direction for the edges for which the plane is not defined
409 BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
411 // edges for which the plane is not found
412 TopTools_MapOfShape aMEdgesNoUniquePlane;
414 // edges for which the plane cannot be found on a single edge
415 TopoDS_Compound aLEdges;
416 aBB.MakeCompound(aLEdges);
418 aExp.Init(aSEdges, TopAbs_EDGE);
419 for (; aExp.More(); aExp.Next()) {
420 const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
421 BRepAdaptor_Curve aBAC(aE);
424 if (FindPlane(aBAC, aPln)) {
425 aDMEdgePln.Add(aE, aPln);
429 if (FindEdgeTangent(aBAC, aVT)) {
430 aDMEdgeTgt.Add(aE, gp_Dir(aVT));
431 aBB.Add(aLEdges, aE);
432 aMEdgesNoUniquePlane.Add(aE);
437 typedef NCollection_List<gp_Dir> BOPAlgo_ListOfDir;
439 // to avoid processing of the same edges in the same plane store
440 // the processed planes into a list and use it as a fence map
441 BOPAlgo_ListOfDir aLPFence;
444 TopTools_MapOfShape aMEFence;
446 // look for a planes on the single edges
447 Standard_Integer i, j, aNbPlanes = aDMEdgePln.Extent(), aNbEdges = aDMEdgeTgt.Extent();
448 for (i = 1; i <= aNbPlanes; ++i) {
449 const TopoDS_Shape& aEI = aDMEdgePln.FindKey(i);
450 if (!aMEFence.Add(aEI)) {
454 const gp_Pln& aPlnI = aDMEdgePln(i);
455 const gp_Dir& aDI = aPlnI.Position().Direction();
457 aLPFence.Append(aDI);
459 TopTools_IndexedMapOfShape aMEPln;
462 TopTools_IndexedMapOfShape aMV;
463 TopExp::MapShapes(aEI, TopAbs_VERTEX, aMV);
465 // look for other edges with the plane parallel to current one
466 for (j = i + 1; j <= aNbPlanes; ++j) {
467 const gp_Dir& aDJ = aDMEdgePln(j).Position().Direction();
468 if (aDI.IsParallel(aDJ, theAngTol)) {
469 const TopoDS_Shape& aEJ = aDMEdgePln.FindKey(j);
472 TopExp::MapShapes(aEJ, TopAbs_VERTEX, aMV);
476 // look for all other edges located in the plane parallel to current one
477 TopoDS_Compound aCEPln;
478 aBB.MakeCompound(aCEPln);
480 for (j = 1; j <= aNbEdges; ++j) {
481 const gp_Dir& aDJ = aDMEdgeTgt(j);
482 if (aDI.IsNormal(aDJ, theAngTol)) {
483 aBB.Add(aCEPln, aDMEdgeTgt.FindKey(j));
487 // make blocks of these edges and check blocks to be connected
488 // to any of the already added edges or forming a wire themselves
489 TopTools_ListOfShape aLCBE;
490 BOPTools_AlgoTools::MakeConnexityBlocks(aCEPln, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
492 // make wire from each block
493 TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
494 for (; aItLCB.More(); aItLCB.Next()) {
495 const TopoDS_Shape& aCBE = aItLCB.Value();
497 // check connectivity
498 TopExp_Explorer aExpV(aCBE, TopAbs_VERTEX);
499 for (; aExpV.More(); aExpV.Next()) {
500 if (aMV.Contains(aExpV.Current())) {
505 Standard_Boolean bAddBlock = aExpV.More();
507 // check if the edges are forming a wire
509 bAddBlock = FindPlane(aCBE, aPln, aDMEdgeTgt, aMEdgesNoUniquePlane);
514 for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
515 aMEPln.Add(aItE.Value());
520 MakeWires(aMEPln, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
523 // make connection map from vertices to edges to find the connected pairs
524 TopTools_IndexedDataMapOfShapeListOfShape aDMVE;
525 TopExp::MapShapesAndAncestors(aLEdges, TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
527 // find planes for connected edges
528 Standard_Integer aNbV = aDMVE.Extent();
529 for (i = 1; i <= aNbV; ++i) {
530 const TopTools_ListOfShape& aLEI = aDMVE(i);
531 if (aLEI.Extent() < 2) {
535 TopTools_ListIteratorOfListOfShape aItLEI1(aLEI);
536 for (; aItLEI1.More(); aItLEI1.Next()) {
537 const TopoDS_Shape& aEI1 = aItLEI1.Value();
538 const gp_Dir& aDI1 = aDMEdgeTgt.FindFromKey(aEI1);
540 TopTools_ListIteratorOfListOfShape aItLEI2(aLEI);
541 for (; aItLEI2.More(); aItLEI2.Next()) {
542 const TopoDS_Shape& aEI2 = aItLEI2.Value();
543 if (aEI2.IsSame(aEI1)) {
547 const gp_Dir& aDI2 = aDMEdgeTgt.FindFromKey(aEI2);
549 if (aDI1.IsParallel(aDI2, theAngTol)) {
553 gp_Dir aDNI = aDI1^aDI2;
555 // check if this normal direction has not been checked yet
556 BOPAlgo_ListOfDir::Iterator aItLPln(aLPFence);
557 for (; aItLPln.More(); aItLPln.Next()) {
558 if (aDNI.IsParallel(aItLPln.Value(), theAngTol)) {
562 if (aItLPln.More()) {
566 aLPFence.Append(aDNI);
568 // find all other edges in the plane parallel to current one
569 TopTools_IndexedMapOfShape aMEPln;
573 // iterate on all other edges to find all edges lying in the plane parallel to current one
574 for (j = 1; j <= aNbEdges; ++j) {
575 const gp_Dir& aDJ = aDMEdgeTgt(j);
576 if (aDNI.IsNormal(aDJ, theAngTol)) {
577 aMEPln.Add(aDMEdgeTgt.FindKey(j));
581 MakeWires(aMEPln, aRWires, Standard_True, aDMEdgeTgt, aMEdgesNoUniquePlane);
582 } // for (; aItLEI2.More(); aItLEI2.Next()) {
583 } // for (; aItLEI1.More(); aItLEI1.Next()) {
584 } // for (i = 1; i < aNb; ++i) {
586 // 4. Find unused edges and make wires from them
587 TopTools_IndexedMapOfShape aMEAlone, aMEUsed;
588 TopExp::MapShapes(aRWires, TopAbs_EDGE, aMEUsed);
590 for (i = 1; i <= aNbEdges; ++i) {
591 const TopoDS_Shape& aE = aDMEdgeTgt.FindKey(i);
592 if (!aMEUsed.Contains(aE)) {
597 MakeWires(aMEAlone, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
604 //=======================================================================
605 //function : WiresToFaces
607 //=======================================================================
608 Standard_Boolean BOPAlgo_Tools::WiresToFaces(const TopoDS_Shape& theWires,
609 TopoDS_Shape& theFaces,
610 const Standard_Real theAngTol)
613 TopTools_MapOfShape aMFence;
614 TopoDS_Compound aRFaces;
615 aBB.MakeCompound(aRFaces);
617 const Standard_Real aMax = 1.e+8;
619 // map to store the tangent vectors for the edges
620 BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
621 // maps to store the planes found for the wires
622 BOPAlgo_IndexedDataMapOfShapePln aDMWirePln;
623 // map to store the tolerance for the wire
624 NCollection_DataMap<TopoDS_Shape, Standard_Real, TopTools_ShapeMapHasher> aDMWireTol;
625 // edges for which the plane is not found
626 TopTools_MapOfShape aMEdgesNoUniquePlane;
628 // Find planes for the wires
629 TopExp_Explorer aExpW(theWires, TopAbs_WIRE);
630 for (; aExpW.More(); aExpW.Next()) {
631 const TopoDS_Wire& aWire = TopoDS::Wire(aExpW.Current());
633 if (FindPlane(aWire, aPlane, aDMEdgeTgt, aMEdgesNoUniquePlane)) {
634 aDMWirePln.Add(aWire, aPlane);
635 // find tolerance for the wire - max tolerance of its edges
636 aDMWireTol.Bind(aWire, BRep_Tool::MaxTolerance(aWire, TopAbs_EDGE));
640 Standard_Integer i, j, aNb = aDMWirePln.Extent();
641 for (i = 1; i <= aNb; ++i) {
642 const TopoDS_Shape& aWireI = aDMWirePln.FindKey(i);
643 if (aMFence.Contains(aWireI)) {
647 const gp_Pln& aPlnI = aDMWirePln(i);
649 TopTools_ListOfShape aLW;
653 Standard_Real aTolI = aDMWireTol.Find(aWireI);
655 // Find other wires in the same plane
656 for (j = i + 1; j <= aNb; ++j) {
657 const TopoDS_Shape& aWireJ = aDMWirePln.FindKey(j);
658 if (aMFence.Contains(aWireJ)) {
662 // check if the planes are the same
663 const gp_Pln& aPlnJ = aDMWirePln(j);
664 // check direction of the planes
665 if (!aPlnI.Position().Direction().IsParallel(aPlnJ.Position().Direction(), theAngTol)) {
668 // check distance between the planes
669 Standard_Real aDist = aPlnI.Distance(aPlnJ.Location());
670 Standard_Real aTolJ = aDMWireTol.Find(aWireJ);
671 if (aDist > (aTolI + aTolJ)) {
679 // Take the edges to build the face
680 TopTools_ListOfShape aLE;
681 TopTools_ListIteratorOfListOfShape aItLW(aLW);
682 for (; aItLW.More(); aItLW.Next()) {
683 TopoDS_Iterator aItE(aItLW.Value());
684 for (; aItE.More(); aItE.Next()) {
685 aLE.Append(aItE.Value().Oriented(TopAbs_FORWARD));
686 aLE.Append(aItE.Value().Oriented(TopAbs_REVERSED));
691 TopoDS_Face aFF = BRepBuilderAPI_MakeFace
692 (aPlnI, -aMax, aMax, -aMax, aMax).Face();
693 aFF.Orientation(TopAbs_FORWARD);
698 // build pcurves for edges on this face
699 BRepLib::BuildPCurveForEdgesOnPlane(aLE, aFF);
701 // split the face with the edges
702 BOPAlgo_BuilderFace aBF;
706 if (aBF.HasErrors()) {
710 const TopTools_ListOfShape& aLFSp = aBF.Areas();
711 TopTools_ListIteratorOfListOfShape aItLF(aLFSp);
712 for (; aItLF.More(); aItLF.Next()) {
713 const TopoDS_Shape& aFSp = aItLF.ChangeValue();
714 aBB.Add(aRFaces, aFSp);
717 catch (Standard_Failure const&) {
722 // fix tolerances of the resulting faces
723 TopTools_IndexedMapOfShape aMEmpty;
724 BOPTools_AlgoTools::CorrectTolerances(aRFaces, aMEmpty, 0.05, Standard_False);
725 BOPTools_AlgoTools::CorrectShapeTolerances(aRFaces, aMEmpty, Standard_False);
728 return theFaces.NbChildren() > 0;
731 //=======================================================================
732 //function : MakeWires
733 //purpose : Makes wires from the separate blocks of the given edges
734 //=======================================================================
735 void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
736 TopoDS_Compound& theWires,
737 const Standard_Boolean theCheckUniquePlane,
738 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
739 TopTools_MapOfShape& theMEdgesNoUniquePlane)
742 BRep_Builder().MakeCompound(aCE);
743 Standard_Integer i, aNbE = theEdges.Extent();
744 for (i = 1; i <= aNbE; ++i) {
745 BRep_Builder().Add(aCE, theEdges(i));
748 TopTools_ListOfShape aLCBE;
749 BOPTools_AlgoTools::MakeConnexityBlocks(aCE, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
751 // make wire from each block
752 TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
753 for (; aItLCB.More(); aItLCB.Next()) {
754 const TopoDS_Shape& aCBE = aItLCB.Value();
756 if (theCheckUniquePlane) {
758 if (!FindPlane(aCBE, aPln, theDMEdgeTgt, theMEdgesNoUniquePlane)) {
764 BRep_Builder().MakeWire(aWire);
765 for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
766 BRep_Builder().Add(aWire, aItE.Value());
769 BRep_Builder().Add(theWires, aWire);
773 //=======================================================================
774 //function : FindEdgeTangent
775 //purpose : Finds the tangent for the edge using the map
776 //=======================================================================
777 Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
778 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
781 gp_Dir *pDTE = theDMEdgeTgt.ChangeSeek(theEdge);
784 BRepAdaptor_Curve aBAC(theEdge);
785 if (!FindEdgeTangent(aBAC, aVTE)) {
786 return Standard_False;
788 pDTE = &theDMEdgeTgt(theDMEdgeTgt.Add(theEdge, gp_Dir(aVTE)));
791 return Standard_True;
794 //=======================================================================
795 //function : FindEdgeTangent
796 //purpose : Finds the tangent for the edge
797 //=======================================================================
798 Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
801 if (!theCurve.Is3DCurve()) {
802 return Standard_False;
804 // for the line the tangent is defined by the direction
805 if (theCurve.GetType() == GeomAbs_Line) {
806 theTangent = theCurve.Line().Position().Direction();
807 return Standard_True;
810 // for other curves take D1 and check for its length
811 Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
812 const Standard_Integer aNbP = 11;
813 const Standard_Real aDt = (aT2 - aT1) / aNbP;
815 for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
817 theCurve.D1(aT, aP, theTangent);
818 if (theTangent.Magnitude() > Precision::Confusion()) {
819 return Standard_True;
823 return Standard_False;
826 //=======================================================================
827 //function : FindPlane
828 //purpose : Finds the plane in which the edge is located
829 //=======================================================================
830 Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
833 if (!theCurve.Is3DCurve()) {
834 return Standard_False;
837 Standard_Boolean bFound = Standard_True;
839 switch (theCurve.GetType()) {
841 return Standard_False;
843 aVN = theCurve.Circle().Position().Direction();
845 case GeomAbs_Ellipse:
846 aVN = theCurve.Ellipse().Position().Direction();
848 case GeomAbs_Hyperbola:
849 aVN = theCurve.Hyperbola().Position().Direction();
851 case GeomAbs_Parabola:
852 aVN = theCurve.Parabola().Position().Direction();
855 // for all other types of curve compute two tangent vectors
856 // on the curve and cross them
857 bFound = Standard_False;
858 Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
859 const Standard_Integer aNbP = 11;
860 const Standard_Real aDt = (aT2 - aT1) / aNbP;
865 theCurve.D1(aT, aP1, aV1);
867 for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
870 theCurve.D1(aT, aP2, aV2);
873 if (aVN.Magnitude() > Precision::Confusion()) {
874 bFound = Standard_True;
883 thePlane = gp_Pln(theCurve.Value(theCurve.FirstParameter()), gp_Dir(aVN));
888 //=======================================================================
889 //function : FindPlane
890 //purpose : Finds the plane in which the wire is located
891 //=======================================================================
892 Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
894 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
895 TopTools_MapOfShape& theMEdgesNoUniquePlane)
897 TopExp_Explorer aExpE1(theWire, TopAbs_EDGE);
898 if (!aExpE1.More()) {
899 return Standard_False;
902 // try to find two not parallel edges in wire to get normal of the plane
903 for (; aExpE1.More(); aExpE1.Next()) {
904 // get the first edge in the wire
905 const TopoDS_Edge& aE1 = TopoDS::Edge(aExpE1.Current());
907 // find tangent for the first edge
909 if (!FindEdgeTangent(aE1, theDMEdgeTgt, aDTE1)) {
913 // find the other edge not parallel to the first one
914 TopExp_Explorer aExpE2(theWire, TopAbs_EDGE);
915 for (; aExpE2.More(); aExpE2.Next()) {
916 const TopoDS_Edge& aE2 = TopoDS::Edge(aExpE2.Current());
917 if (aE1.IsSame(aE2)) {
921 // find tangent for the second edge
923 if (!FindEdgeTangent(aE2, theDMEdgeTgt, aDTE2)) {
927 if (aDTE1.IsParallel(aDTE2, Precision::Angular())) {
931 gp_Dir aDN = aDTE1^aDTE2;
933 TopoDS_Iterator aItV(aE1);
934 thePlane = gp_Pln(BRep_Tool::Pnt(TopoDS::Vertex(aItV.Value())), aDN);
935 return Standard_True;
939 // try to compute normal on the single edge
940 aExpE1.Init(theWire, TopAbs_EDGE);
941 for (; aExpE1.More(); aExpE1.Next()) {
942 const TopoDS_Edge& aE = TopoDS::Edge(aExpE1.Current());
943 if (theMEdgesNoUniquePlane.Contains(aE)) {
946 BRepAdaptor_Curve aBAC(aE);
947 if (FindPlane(aBAC, thePlane)) {
948 return Standard_True;
950 theMEdgesNoUniquePlane.Add(aE);
952 return Standard_False;
955 /////////////////////////////////////////////////////////////////////////
956 //=======================================================================
957 //class : BOPAlgo_PairVerticesSelector
959 //=======================================================================
960 class BOPAlgo_PairVerticesSelector : public BOPTools_BoxPairSelector
964 BOPAlgo_PairVerticesSelector()
966 myFuzzyValue(Precision::Confusion())
969 //! Sets the map of vertices with tolerances
970 void SetMapOfVerticesTolerances (const TopTools_IndexedDataMapOfShapeReal& theVertices)
972 myVertices = &theVertices;
975 //! Sets the fuzzy value
976 void SetFuzzyValue (const Standard_Real theFuzzyValue)
978 myFuzzyValue = theFuzzyValue;
981 //! Checks and accepts the pair of elements.
982 virtual Standard_Boolean Accept (const Standard_Integer theID1,
983 const Standard_Integer theID2) Standard_OVERRIDE
985 if (!RejectElement (theID1, theID2))
987 const Standard_Integer anID1 = this->myBVHSet1->Element (theID1);
988 const TopoDS_Vertex& aV1 = TopoDS::Vertex (myVertices->FindKey (anID1));
989 Standard_Real aTolV1 = BRep_Tool::Tolerance (aV1);
990 if (aTolV1 < myVertices->FindFromIndex (anID1))
991 aTolV1 = myVertices->FindFromIndex (anID1);
992 gp_Pnt aP1 = BRep_Tool::Pnt (aV1);
994 const Standard_Integer anID2 = this->myBVHSet1->Element (theID2);
995 const TopoDS_Vertex& aV2 = TopoDS::Vertex (myVertices->FindKey (anID2));
996 Standard_Real aTolV2 = BRep_Tool::Tolerance (aV2);
997 if (aTolV2 < myVertices->FindFromIndex (anID2))
998 aTolV2 = myVertices->FindFromIndex (anID2);
999 gp_Pnt aP2 = BRep_Tool::Pnt (aV2);
1001 Standard_Real aTolSum2 = aTolV1 + aTolV2 + myFuzzyValue;
1002 aTolSum2 *= aTolSum2;
1004 Standard_Real aD2 = aP1.SquareDistance (aP2);
1007 myPairs.push_back (PairIDs (anID1, anID2));
1008 return Standard_True;
1011 return Standard_False;
1015 const TopTools_IndexedDataMapOfShapeReal * myVertices;
1016 Standard_Real myFuzzyValue;
1019 /////////////////////////////////////////////////////////////////////////
1021 //=======================================================================
1022 //function : IntersectVertices
1023 //purpose : Builds the chains of intersecting vertices
1024 //=======================================================================
1025 void BOPAlgo_Tools::IntersectVertices(const TopTools_IndexedDataMapOfShapeReal& theVertices,
1026 const Standard_Real theFuzzyValue,
1027 TopTools_ListOfListOfShape& theChains)
1029 Standard_Integer aNbV = theVertices.Extent();
1032 theChains.Append(TopTools_ListOfShape()).Append(theVertices.FindKey(1));
1037 // Additional tolerance for intersection
1038 Standard_Real aTolAdd = theFuzzyValue / 2.;
1040 // Use BVH Tree for sorting the vertices
1041 BOPTools_BoxTree aBBTree;
1042 aBBTree.SetSize (aNbV);
1044 for (Standard_Integer i = 1; i <= aNbV; ++i)
1046 const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
1047 Standard_Real aTol = BRep_Tool::Tolerance(aV);
1048 if (aTol < theVertices(i))
1049 aTol = theVertices(i);
1051 // Build bnd box for vertex
1053 aBox.Add(BRep_Tool::Pnt(aV));
1054 aBox.SetGap(aTol + aTolAdd);
1055 aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aBox));
1060 // Perform selection of the interfering vertices
1061 BOPAlgo_PairVerticesSelector aPairSelector;
1062 aPairSelector.SetBVHSets (&aBBTree, &aBBTree);
1063 aPairSelector.SetSame (Standard_True);
1064 aPairSelector.SetMapOfVerticesTolerances (theVertices);
1065 aPairSelector.SetFuzzyValue (theFuzzyValue);
1066 aPairSelector.Select();
1068 // Treat the selected pairs
1069 const std::vector<BOPTools_BoxPairSelector::PairIDs>& aPairs = aPairSelector.Pairs();
1070 const Standard_Integer aNbPairs = static_cast<Standard_Integer> (aPairs.size());
1072 // Collect interfering pairs
1073 Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
1074 NCollection_IndexedDataMap<Standard_Integer, TColStd_ListOfInteger> aMILI (1, anAlloc);
1076 for (Standard_Integer iPair = 0; iPair < aNbPairs; ++iPair)
1078 const BOPTools_BoxPairSelector::PairIDs& aPair = aPairs[iPair];
1079 BOPAlgo_Tools::FillMap<Standard_Integer, TColStd_MapIntegerHasher> (aPair.ID1, aPair.ID2, aMILI, anAlloc);
1082 NCollection_List<TColStd_ListOfInteger> aBlocks (anAlloc);
1083 BOPAlgo_Tools::MakeBlocks<Standard_Integer, TColStd_MapIntegerHasher> (aMILI, aBlocks, anAlloc);
1085 NCollection_List<TColStd_ListOfInteger>::Iterator itLI (aBlocks);
1086 for (; itLI.More(); itLI.Next())
1088 const TColStd_ListOfInteger& aLI = itLI.Value();
1089 TopTools_ListOfShape &aChain = theChains.Append (TopTools_ListOfShape());
1091 for (TColStd_ListOfInteger::Iterator itI (aLI); itI.More(); itI.Next())
1092 aChain.Append (theVertices.FindKey (itI.Value()));
1095 // Add not interfered vertices as a chain of 1 element
1096 for (Standard_Integer i = 1; i <= aNbV; ++i)
1098 if (!aMILI.Contains (i))
1100 TopTools_ListOfShape &aChain = theChains.Append (TopTools_ListOfShape());
1101 aChain.Append (theVertices.FindKey(i));
1106 //=======================================================================
1107 // Classification of the faces relatively solids
1108 //=======================================================================
1110 //=======================================================================
1111 //class : BOPAlgo_ShapeBox
1112 //purpose : Auxiliary class defining ShapeBox structure
1113 //=======================================================================
1114 class BOPAlgo_ShapeBox
1117 //! Empty constructor
1118 BOPAlgo_ShapeBox() {};
1120 void SetShape(const TopoDS_Shape& theS)
1124 //! Returns the shape
1125 const TopoDS_Shape& Shape() const
1129 //! Sets the bounding box
1130 void SetBox(const Bnd_Box& theBox)
1134 //! Returns the bounding box
1135 const Bnd_Box& Box() const
1140 TopoDS_Shape myShape;
1143 // Vector of ShapeBox
1144 typedef NCollection_Vector<BOPAlgo_ShapeBox> BOPAlgo_VectorOfShapeBox;
1146 //=======================================================================
1147 //class : BOPAlgo_FillIn3DParts
1148 //purpose : Auxiliary class for faces classification in parallel mode
1149 //=======================================================================
1150 class BOPAlgo_FillIn3DParts : public BOPAlgo_Algo
1153 DEFINE_STANDARD_ALLOC
1156 BOPAlgo_FillIn3DParts()
1163 virtual ~BOPAlgo_FillIn3DParts() {};
1166 void SetSolid(const TopoDS_Solid& theSolid)
1171 //! Returns the solid
1172 const TopoDS_Solid& Solid() const
1177 //! Sets the box for the solid
1178 void SetBoxS(const Bnd_Box& theBox)
1183 //! Returns the solid's box
1184 const Bnd_Box& BoxS() const
1189 //! Sets own INTERNAL faces of the solid
1190 void SetOwnIF(const TopTools_ListOfShape& theLIF)
1195 //! Returns own INTERNAL faces of the solid
1196 const TopTools_ListOfShape& OwnIF() const
1201 //! Sets the Bounding Box tree
1202 void SetBBTree(BOPTools_BoxTree* theBBTree)
1204 myBBTree = theBBTree;
1207 //! Sets the ShapeBox structure
1208 void SetShapeBoxVector(const BOPAlgo_VectorOfShapeBox& theShapeBox)
1210 myVShapeBox = (BOPAlgo_VectorOfShapeBox*)&theShapeBox;
1213 //! Sets the context
1214 void SetContext(const Handle(IntTools_Context)& theContext)
1216 myContext = theContext;
1219 //! Returns the context
1220 const Handle(IntTools_Context)& Context() const
1225 //! Performs the classification
1226 virtual void Perform();
1228 //! Returns the faces classified as IN for solid
1229 const TopTools_ListOfShape& InFaces() const
1236 //! Prepares Edge-Face connection map of the given shape
1237 void MapEdgesAndFaces(const TopoDS_Shape& theF,
1238 TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1239 const Handle(NCollection_BaseAllocator)& theAlloc);
1241 //! Makes the connexity block of faces using the connection map
1242 void MakeConnexityBlock(const TopoDS_Face& theF,
1243 const TopTools_IndexedMapOfShape& theMEToAvoid,
1244 const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1245 TopTools_MapOfShape& theMFDone,
1246 TopTools_ListOfShape& theLCB,
1247 TopoDS_Face& theFaceToClassify);
1249 TopoDS_Solid mySolid; //! Solid
1250 Bnd_Box myBoxS; // Bounding box of the solid
1251 TopTools_ListOfShape myOwnIF; //! Own INTERNAL faces of the solid
1252 TopTools_ListOfShape myInFaces; //! Faces classified as IN
1254 BOPTools_BoxTree* myBBTree; //! BVH tree of bounding boxes
1255 BOPAlgo_VectorOfShapeBox* myVShapeBox; //! ShapeBoxMap
1257 TopoDS_Iterator myItF; //! Iterators
1258 TopoDS_Iterator myItW;
1260 Handle(IntTools_Context) myContext; //! Context
1263 //=======================================================================
1264 //function : BOPAlgo_FillIn3DParts::Perform
1266 //=======================================================================
1267 void BOPAlgo_FillIn3DParts::Perform()
1269 BOPAlgo_Algo::UserBreak();
1273 // 1. Select boxes of faces that are not out of aBoxS
1274 BOPTools_BoxTreeSelector aSelector;
1275 aSelector.SetBox(Bnd_Tools::Bnd2BVH(myBoxS));
1276 aSelector.SetBVHSet (myBBTree);
1278 if (!aSelector.Select())
1281 const TColStd_ListOfInteger& aLIFP = aSelector.Indices();
1283 // 2. Fill maps of edges and faces of the solid
1285 Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1287 BOPAlgo_VectorOfShapeBox& aVShapeBox = *myVShapeBox;
1289 TopTools_IndexedMapOfShape aMSE(1, anAlloc), aMSF(1, anAlloc);
1290 TopExp::MapShapes(mySolid, TopAbs_EDGE, aMSE);
1291 TopExp::MapShapes(mySolid, TopAbs_FACE, aMSF);
1293 // Check if the Solid contains any faces
1294 Standard_Boolean bIsEmpty = aMSF.IsEmpty();
1296 // Add own internal faces of the solid into aMSF
1297 TopTools_ListIteratorOfListOfShape aItLS(myOwnIF);
1298 for (; aItLS.More(); aItLS.Next())
1299 aMSF.Add(aItLS.Value());
1301 // 3. aIVec - faces to process.
1302 // Filter the selected faces with faces of the solid.
1303 NCollection_Vector<Standard_Integer> aIVec(256, anAlloc);
1305 TColStd_ListIteratorOfListOfInteger aItLI(aLIFP);
1306 for (; aItLI.More(); aItLI.Next()) {
1307 Standard_Integer nFP = aItLI.Value();
1308 const TopoDS_Shape& aFP = aVShapeBox(nFP).Shape();
1309 if (!aMSF.Contains(aFP))
1310 aIVec.Appended() = nFP;
1313 // 4. Classify faces relatively solid.
1314 // Store faces that are IN mySolid into <myInFaces>
1316 Standard_Integer k, aNbFP = aIVec.Length();
1317 // Sort indices if necessary
1319 std::sort(aIVec.begin(), aIVec.end());
1323 // The solid is empty as it does not contain any faces.
1324 // It could happen when the input solid consists of INTERNAL faces only.
1325 // Classification of any point relatively empty solid would always give IN status.
1326 // Thus, we consider all selected faces as IN without real classification.
1327 for (k = 0; k < aNbFP; ++k)
1328 myInFaces.Append(aVShapeBox(aIVec(k)).Shape());
1333 // Prepare EF map of faces to process for building connexity blocks
1334 TopTools_IndexedDataMapOfShapeListOfShape aMEFP(1, anAlloc);
1337 for (k = 0; k < aNbFP; ++k)
1338 MapEdgesAndFaces(aVShapeBox(aIVec(k)).Shape(), aMEFP, anAlloc);
1341 // Map of Edge-Face connection, necessary for solid classification.
1342 // It will be filled when first classification is performed.
1343 TopTools_IndexedDataMapOfShapeListOfShape aMEFDS(1, anAlloc);
1345 // Fence map to avoid processing of the same faces twice
1346 TopTools_MapOfShape aMFDone(1, anAlloc);
1348 for (k = 0; k < aNbFP; ++k)
1350 Standard_Integer nFP = aIVec(k);
1351 const TopoDS_Face& aFP = (*(TopoDS_Face*)&aVShapeBox(nFP).Shape());
1352 if (!aMFDone.Add(aFP))
1355 // Make connexity blocks of faces, avoiding passing through the
1356 // borders of the solid. It helps to reduce significantly the
1357 // number of classified faces.
1358 TopTools_ListOfShape aLCBF(anAlloc);
1359 // The most appropriate face for classification
1360 TopoDS_Face aFaceToClassify;
1361 MakeConnexityBlock(aFP, aMSE, aMEFP, aMFDone, aLCBF, aFaceToClassify);
1363 if (!myBoxS.IsWhole())
1365 // First, try fast classification of the whole block by additional
1366 // check on bounding boxes - check that bounding boxes of all vertices
1367 // of the block interfere with the box of the solid.
1368 // If not, the faces are out.
1369 Standard_Boolean bOut = Standard_False;
1370 aItLS.Initialize(aLCBF);
1371 for (; aItLS.More() && !bOut; aItLS.Next())
1373 TopExp_Explorer anExpV(aItLS.Value(), TopAbs_VERTEX);
1374 for (; anExpV.More() && !bOut; anExpV.Next())
1376 const TopoDS_Vertex& aV = TopoDS::Vertex(anExpV.Current());
1378 aBBV.Add(BRep_Tool::Pnt(aV));
1379 aBBV.SetGap(BRep_Tool::Tolerance(aV));
1380 bOut = myBoxS.IsOut(aBBV);
1387 if (aFaceToClassify.IsNull())
1388 aFaceToClassify = aFP;
1390 if (aMEFDS.IsEmpty())
1391 // Fill EF map for Solid
1392 TopExp::MapShapesAndAncestors(mySolid, TopAbs_EDGE, TopAbs_FACE, aMEFDS);
1394 // All vertices are interfere with the solids box, run classification.
1395 Standard_Boolean bIsIN = BOPTools_AlgoTools::IsInternalFace
1396 (aFaceToClassify, mySolid, aMEFDS, Precision::Confusion(), myContext);
1399 aItLS.Initialize(aLCBF);
1400 for (; aItLS.More(); aItLS.Next())
1401 myInFaces.Append(aItLS.Value());
1405 //=======================================================================
1406 // function: MapEdgesAndFaces
1408 //=======================================================================
1409 void BOPAlgo_FillIn3DParts::MapEdgesAndFaces(const TopoDS_Shape& theF,
1410 TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1411 const Handle(NCollection_BaseAllocator)& theAllocator)
1413 myItF.Initialize(theF);
1414 for (; myItF.More(); myItF.Next())
1416 const TopoDS_Shape& aW = myItF.Value();
1417 if (aW.ShapeType() != TopAbs_WIRE)
1420 myItW.Initialize(aW);
1421 for (; myItW.More(); myItW.Next())
1423 const TopoDS_Shape& aE = myItW.Value();
1425 TopTools_ListOfShape* pLF = theEFMap.ChangeSeek(aE);
1427 pLF = &theEFMap(theEFMap.Add(aE, TopTools_ListOfShape(theAllocator)));
1432 //=======================================================================
1433 // function: MakeConnexityBlock
1435 //=======================================================================
1436 void BOPAlgo_FillIn3DParts::MakeConnexityBlock(const TopoDS_Face& theFStart,
1437 const TopTools_IndexedMapOfShape& theMEAvoid,
1438 const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1439 TopTools_MapOfShape& theMFDone,
1440 TopTools_ListOfShape& theLCB,
1441 TopoDS_Face& theFaceToClassify)
1443 // Add start element
1444 theLCB.Append(theFStart);
1445 if (theEFMap.IsEmpty())
1448 TopTools_ListIteratorOfListOfShape aItCB(theLCB);
1449 for (; aItCB.More(); aItCB.Next())
1451 const TopoDS_Shape& aF = aItCB.Value();
1452 myItF.Initialize(aF);
1453 for (; myItF.More(); myItF.Next())
1455 const TopoDS_Shape& aW = myItF.Value();
1456 if (aW.ShapeType() != TopAbs_WIRE)
1459 myItW.Initialize(aW);
1460 for (; myItW.More(); myItW.Next())
1462 const TopoDS_Edge& aE = TopoDS::Edge(myItW.Value());
1463 if (theMEAvoid.Contains(aE) || BRep_Tool::Degenerated(aE))
1465 if (theFaceToClassify.IsNull())
1466 theFaceToClassify = TopoDS::Face(aF);
1470 const TopTools_ListOfShape* pLF = theEFMap.Seek(aE);
1473 TopTools_ListIteratorOfListOfShape aItLF(*pLF);
1474 for (; aItLF.More(); aItLF.Next())
1476 const TopoDS_Shape& aFToAdd = aItLF.Value();
1477 if (theMFDone.Add(aFToAdd))
1478 theLCB.Append(aFToAdd);
1485 // Vector of solid classifiers
1486 typedef NCollection_Vector<BOPAlgo_FillIn3DParts> BOPAlgo_VectorOfFillIn3DParts;
1488 //=======================================================================
1489 //function : ClassifyFaces
1491 //=======================================================================
1492 void BOPAlgo_Tools::ClassifyFaces(const TopTools_ListOfShape& theFaces,
1493 const TopTools_ListOfShape& theSolids,
1494 const Standard_Boolean theRunParallel,
1495 Handle(IntTools_Context)& theContext,
1496 TopTools_IndexedDataMapOfShapeListOfShape& theInParts,
1497 const TopTools_DataMapOfShapeBox& theShapeBoxMap,
1498 const TopTools_DataMapOfShapeListOfShape& theSolidsIF)
1500 Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1502 // Fill the vector of shape box with faces and its bounding boxes
1503 BOPAlgo_VectorOfShapeBox aVSB(256, anAlloc);
1505 TopTools_ListIteratorOfListOfShape aItLF(theFaces);
1506 for (; aItLF.More(); aItLF.Next())
1508 const TopoDS_Shape& aF = aItLF.Value();
1509 // Append face to the vector of shape box
1510 BOPAlgo_ShapeBox& aSB = aVSB.Appended();
1513 // Get bounding box for the face
1514 const Bnd_Box* pBox = theShapeBoxMap.Seek(aF);
1519 // Build the bounding box
1521 BRepBndLib::Add(aF, aBox);
1526 // Prepare BVH tree of bounding boxes of the faces to classify
1527 // taking the bounding boxes from the just prepared vector
1528 BOPTools_BoxTree aBBTree;
1529 Standard_Integer aNbF = aVSB.Length();
1530 aBBTree.SetSize (aNbF);
1531 for (Standard_Integer i = 0; i < aNbF; ++i)
1533 aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aVSB(i).Box()));
1536 // Shake tree filler
1539 // Prepare vector of solids to classify
1540 BOPAlgo_VectorOfFillIn3DParts aVFIP;
1542 TopTools_ListIteratorOfListOfShape aItLS(theSolids);
1543 for (; aItLS.More(); aItLS.Next())
1545 const TopoDS_Solid& aSolid = TopoDS::Solid(aItLS.Value());
1546 // Append solid to the vector
1547 BOPAlgo_FillIn3DParts& aFIP = aVFIP.Appended();
1548 aFIP.SetSolid(aSolid);
1550 // Get bounding box for the solid
1551 const Bnd_Box* pBox = theShapeBoxMap.Seek(aSolid);
1553 aFIP.SetBoxS(*pBox);
1556 // Build the bounding box
1558 BRepBndLib::Add(aSolid, aBox);
1559 if (!aBox.IsWhole())
1561 if (BOPTools_AlgoTools::IsInvertedSolid(aSolid))
1567 const TopTools_ListOfShape* pLIF = theSolidsIF.Seek(aSolid);
1569 aFIP.SetOwnIF(*pLIF);
1571 aFIP.SetBBTree(&aBBTree);
1572 aFIP.SetShapeBoxVector(aVSB);
1575 // Perform classification
1576 //================================================================
1577 BOPTools_Parallel::Perform (theRunParallel, aVFIP, theContext);
1578 //================================================================
1580 // Analyze the results and fill the resulting map
1582 Standard_Integer aNbS = aVFIP.Length();
1583 for (Standard_Integer i = 0; i < aNbS; ++i)
1585 BOPAlgo_FillIn3DParts& aFIP = aVFIP(i);
1586 const TopoDS_Shape& aS = aFIP.Solid();
1587 const TopTools_ListOfShape& aLFIn = aFIP.InFaces();
1588 theInParts.Add(aS, aLFIn);
1592 //=======================================================================
1593 //function : FillInternals
1595 //=======================================================================
1596 void BOPAlgo_Tools::FillInternals(const TopTools_ListOfShape& theSolids,
1597 const TopTools_ListOfShape& theParts,
1598 const TopTools_DataMapOfShapeListOfShape& theImages,
1599 const Handle(IntTools_Context)& theContext)
1601 if (theSolids.IsEmpty() || theParts.IsEmpty())
1604 // Map the solids to avoid classification of the own shapes of the solids
1605 TopTools_IndexedMapOfShape aMSSolids;
1606 TopTools_ListOfShape::Iterator itLS(theSolids);
1607 for (; itLS.More(); itLS.Next())
1609 const TopoDS_Shape& aSolid = itLS.Value();
1610 if (aSolid.ShapeType() == TopAbs_SOLID)
1612 TopExp::MapShapes(aSolid, TopAbs_VERTEX, aMSSolids);
1613 TopExp::MapShapes(aSolid, TopAbs_EDGE, aMSSolids);
1614 TopExp::MapShapes(aSolid, TopAbs_FACE, aMSSolids);
1618 // Extract BRep elements from the given parts and
1619 // check them for possible splits
1620 TopTools_ListOfShape aLPartsInput = theParts, aLParts;
1621 TopTools_ListOfShape::Iterator itLP(aLPartsInput);
1622 for (; itLP.More(); itLP.Next())
1624 const TopoDS_Shape& aPart = itLP.Value();
1625 switch (aPart.ShapeType())
1631 const TopTools_ListOfShape* pIm = theImages.Seek(aPart);
1634 TopTools_ListOfShape::Iterator itIm(*pIm);
1635 for (; itIm.More(); itIm.Next())
1637 const TopoDS_Shape& aPartIm = itIm.Value();
1638 if (!aMSSolids.Contains(aPartIm))
1639 aLParts.Append(aPartIm);
1642 else if (!aMSSolids.Contains(aPart))
1643 aLParts.Append(aPart);
1649 for (TopoDS_Iterator it(aPart); it.More(); it.Next())
1650 aLPartsInput.Append(it.Value());
1656 // Classify the given parts relatively solids.
1657 // Add edges and vertices classified as IN into solids instantly,
1658 // and collect faces classified as IN into a list for further shell creation
1660 TopTools_DataMapOfShapeListOfShape anINFaces;
1661 itLS.Initialize(theSolids);
1662 for (; itLS.More(); itLS.Next())
1664 const TopoDS_Shape& aSolid = itLS.Value();
1665 if (aSolid.ShapeType() != TopAbs_SOLID)
1668 TopoDS_Solid aSd = *(TopoDS_Solid*)&aSolid;
1670 itLP.Initialize(aLParts);
1671 for (; itLP.More();)
1673 TopoDS_Shape aPart = itLP.Value();
1674 TopAbs_State aState =
1675 BOPTools_AlgoTools::ComputeStateByOnePoint(aPart, aSd, Precision::Confusion(), theContext);
1676 if (aState == TopAbs_IN)
1678 if (aPart.ShapeType() == TopAbs_FACE)
1680 TopTools_ListOfShape *pFaces = anINFaces.ChangeSeek(aSd);
1682 pFaces = anINFaces.Bound(aSd, TopTools_ListOfShape());
1683 pFaces->Append(aPart);
1687 aPart.Orientation(TopAbs_INTERNAL);
1688 BRep_Builder().Add(aSd, aPart);
1690 aLParts.Remove(itLP);
1697 // Make shells from faces and put them into solids
1698 TopTools_DataMapOfShapeListOfShape::Iterator itM(anINFaces);
1699 for (; itM.More(); itM.Next())
1701 TopoDS_Solid aSd = *(TopoDS_Solid*)&itM.Key();
1702 const TopTools_ListOfShape& aFaces = itM.Value();
1704 TopoDS_Compound aCF;
1705 BRep_Builder().MakeCompound(aCF);
1707 TopTools_ListOfShape::Iterator itLF(aFaces);
1708 for (; itLF.More(); itLF.Next())
1709 BRep_Builder().Add(aCF, itLF.Value());
1711 // Build blocks from the faces
1712 TopTools_ListOfShape aLCB;
1713 BOPTools_AlgoTools::MakeConnexityBlocks(aCF, TopAbs_EDGE, TopAbs_FACE, aLCB);
1715 // Build shell from each block
1716 TopTools_ListOfShape::Iterator itCB(aLCB);
1717 for (; itCB.More(); itCB.Next())
1719 const TopoDS_Shape& aCB = itCB.Value();
1721 TopoDS_Shell aShell;
1722 BRep_Builder().MakeShell(aShell);
1723 // Add faces of the block to the shell
1724 TopExp_Explorer expF(aCB, TopAbs_FACE);
1725 for (; expF.More(); expF.Next())
1727 TopoDS_Face aFInt = TopoDS::Face(expF.Current());
1728 aFInt.Orientation(TopAbs_INTERNAL);
1729 BRep_Builder().Add(aShell, aFInt);
1732 BRep_Builder().Add(aSd, aShell);
1737 //=======================================================================
1738 //function : TrsfToPoint
1740 //=======================================================================
1741 Standard_Boolean BOPAlgo_Tools::TrsfToPoint (const Bnd_Box& theBox1,
1742 const Bnd_Box& theBox2,
1744 const gp_Pnt& thePoint,
1745 const Standard_Real theCriteria)
1748 Bnd_Box aBox = theBox1;
1751 gp_XYZ aBCenter = (aBox.CornerMin().XYZ() + aBox.CornerMax().XYZ()) / 2.;
1752 Standard_Real aPBDist = (thePoint.XYZ() - aBCenter).Modulus();
1753 if (aPBDist < theCriteria)
1754 return Standard_False;
1756 Standard_Real aBSize = Sqrt (aBox.SquareExtent());
1757 if ((aBSize / aPBDist) > (1. / theCriteria))
1758 return Standard_False;
1760 theTrsf.SetTranslation (gp_Vec (aBox.CornerMin(), thePoint));
1761 return Standard_True;