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_BoxBndTree.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 <GeomAPI_ProjectPointOnCurve.hxx>
37 #include <GeomAPI_ProjectPointOnSurf.hxx>
38 #include <gp_Circ.hxx>
40 #include <gp_Elips.hxx>
41 #include <gp_Hypr.hxx>
42 #include <gp_Parab.hxx>
46 #include <IntTools_Context.hxx>
47 #include <NCollection_IncAllocator.hxx>
48 #include <NCollection_UBTreeFiller.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_TNV
959 //=======================================================================
961 typedef NCollection_Vector<BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
963 //=======================================================================
964 class BOPAlgo_TNV : public BOPTools_BoxBndTreeSelector{
967 : BOPTools_BoxBndTreeSelector(),
968 myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
974 void SetVertex(const TopoDS_Vertex& aV) {
976 myPnt = BRep_Tool::Pnt(myV);
979 const TopoDS_Vertex& Vertex()const {
983 void SetTree(BOPTools_BoxBndTree& aTree) {
987 void SetTolerance(const Standard_Real theTol) {
991 Standard_Real Tolerance() const {
995 const gp_Pnt& Pnt() const {
999 void SetFuzzyValue(const Standard_Real theFuzzyValue) {
1000 myFuzzyValue = theFuzzyValue;
1003 void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
1007 virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
1009 const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
1010 Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
1011 aTolSum2 *= aTolSum2;
1012 Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
1014 return BOPTools_BoxBndTreeSelector::Accept(theIndex);
1015 return Standard_False;
1019 myTree->Select(*this);
1023 Standard_Real myTol;
1024 Standard_Real myFuzzyValue;
1027 BOPTools_BoxBndTree *myTree;
1028 const BOPAlgo_VectorOfTNV *myVecTNV;
1031 /////////////////////////////////////////////////////////////////////////
1033 //=======================================================================
1034 //function : IntersectVertices
1035 //purpose : Builds the chains of intersecting vertices
1036 //=======================================================================
1037 void BOPAlgo_Tools::IntersectVertices(const TopTools_IndexedDataMapOfShapeReal& theVertices,
1038 const Standard_Boolean theRunParallel,
1039 const Standard_Real theFuzzyValue,
1040 TopTools_ListOfListOfShape& theChains)
1042 Standard_Integer i, j, aNbV = theVertices.Extent();
1045 theChains.Append(TopTools_ListOfShape()).Append(theVertices.FindKey(1));
1050 // Use unbalanced binary tree of bounding boxes for sorting of the vertices.
1051 BOPTools_BoxBndTree aBBTree;
1052 NCollection_UBTreeFiller <Standard_Integer,
1053 Bnd_Box> aTreeFiller(aBBTree);
1054 // Perform intersection of the vertices
1055 BOPAlgo_VectorOfTNV aVTNV;
1057 // Use additional tolerance for intersection
1058 Standard_Real aTolAdd = theFuzzyValue / 2.;
1060 for (i = 1; i <= aNbV; ++i) {
1061 const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
1062 Standard_Real aTol = BRep_Tool::Tolerance(aV);
1063 if (aTol < theVertices(i)) {
1064 aTol = theVertices(i);
1066 // Build bnd box for vertex
1068 aBox.Add(BRep_Tool::Pnt(aV));
1069 aBox.SetGap(aTol + aTolAdd);
1071 aTreeFiller.Add(i, aBox);
1073 BOPAlgo_TNV& aTNV=aVTNV.Appended();
1074 aTNV.SetTree(aBBTree);
1077 aTNV.SetTolerance(aTol);
1078 aTNV.SetFuzzyValue(theFuzzyValue);
1079 aTNV.SetVectorOfTNV(aVTNV);
1084 // Perform intersection
1085 BOPTools_Parallel::Perform (theRunParallel, aVTNV);
1088 TColStd_MapOfInteger aMFence;
1089 // Build chains of intersecting vertices
1090 for (i = 1; i <= aNbV; ++i) {
1091 if (!aMFence.Add(i)) {
1095 TColStd_IndexedMapOfInteger aMChain;
1098 for (j = 1; j <= aMChain.Extent(); ++j) {
1099 BOPAlgo_TNV& aTNV = aVTNV(aMChain(j) - 1);
1100 const TColStd_ListOfInteger& aLI = aTNV.Indices();
1101 // Add these vertices into the chain
1102 for (TColStd_ListIteratorOfListOfInteger aItLI(aLI); aItLI.More(); aItLI.Next()) {
1103 if (aMFence.Add(aItLI.Value())) {
1104 aMChain.Add(aItLI.Value());
1109 // Put vertices of the chain into the list
1110 TopTools_ListOfShape& aChain = theChains.Append(TopTools_ListOfShape());
1112 Standard_Integer aNbVChain = aMChain.Extent();
1113 for (j = 1; j <= aNbVChain; ++j) {
1114 const TopoDS_Vertex& aVP = aVTNV(aMChain(j) - 1).Vertex();
1120 //=======================================================================
1121 //function : TreatCompound
1123 //=======================================================================
1124 void BOPAlgo_Tools::TreatCompound(const TopoDS_Shape& theS,
1125 TopTools_MapOfShape& aMFence,
1126 TopTools_ListOfShape& theLS)
1128 TopAbs_ShapeEnum aType = theS.ShapeType();
1129 if (aType != TopAbs_COMPOUND)
1131 if (aMFence.Add(theS))
1135 TopoDS_Iterator aIt(theS);
1136 for (; aIt.More(); aIt.Next())
1138 const TopoDS_Shape& aS = aIt.Value();
1139 TreatCompound(aS, aMFence, theLS);
1143 //=======================================================================
1144 // Classification of the faces relatively solids
1145 //=======================================================================
1147 //=======================================================================
1148 //class : BOPAlgo_ShapeBox
1149 //purpose : Auxiliary class defining ShapeBox structure
1150 //=======================================================================
1151 class BOPAlgo_ShapeBox
1154 //! Empty constructor
1155 BOPAlgo_ShapeBox() {};
1157 void SetShape(const TopoDS_Shape& theS)
1161 //! Returns the shape
1162 const TopoDS_Shape& Shape() const
1166 //! Sets the bounding box
1167 void SetBox(const Bnd_Box& theBox)
1171 //! Returns the bounding box
1172 const Bnd_Box& Box() const
1177 TopoDS_Shape myShape;
1180 // Vector of ShapeBox
1181 typedef NCollection_Vector<BOPAlgo_ShapeBox> BOPAlgo_VectorOfShapeBox;
1183 //=======================================================================
1184 //class : BOPAlgo_FillIn3DParts
1185 //purpose : Auxiliary class for faces classification in parallel mode
1186 //=======================================================================
1187 class BOPAlgo_FillIn3DParts : public BOPAlgo_Algo
1190 DEFINE_STANDARD_ALLOC
1193 BOPAlgo_FillIn3DParts()
1200 virtual ~BOPAlgo_FillIn3DParts() {};
1203 void SetSolid(const TopoDS_Solid& theSolid)
1208 //! Returns the solid
1209 const TopoDS_Solid& Solid() const
1214 //! Sets the box for the solid
1215 void SetBoxS(const Bnd_Box& theBox)
1220 //! Returns the solid's box
1221 const Bnd_Box& BoxS() const
1226 //! Sets own INTERNAL faces of the solid
1227 void SetOwnIF(const TopTools_ListOfShape& theLIF)
1232 //! Returns own INTERNAL faces of the solid
1233 const TopTools_ListOfShape& OwnIF() const
1238 //! Sets the Bounding Box tree
1239 void SetBBTree(const BOPTools_BoxBndTree& theBBTree)
1241 myBBTree = (BOPTools_BoxBndTree*)&theBBTree;
1244 //! Sets the ShapeBox structure
1245 void SetShapeBoxVector(const BOPAlgo_VectorOfShapeBox& theShapeBox)
1247 myVShapeBox = (BOPAlgo_VectorOfShapeBox*)&theShapeBox;
1250 //! Sets the context
1251 void SetContext(const Handle(IntTools_Context)& theContext)
1253 myContext = theContext;
1256 //! Returns the context
1257 const Handle(IntTools_Context)& Context() const
1262 //! Performs the classification
1263 virtual void Perform();
1265 //! Returns the faces classified as IN for solid
1266 const TopTools_ListOfShape& InFaces() const
1273 //! Prepares Edge-Face connection map of the given shape
1274 void MapEdgesAndFaces(const TopoDS_Shape& theF,
1275 TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1276 const Handle(NCollection_BaseAllocator)& theAlloc);
1278 //! Makes the connexity block of faces using the connection map
1279 void MakeConnexityBlock(const TopoDS_Face& theF,
1280 const TopTools_IndexedMapOfShape& theMEToAvoid,
1281 const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1282 TopTools_MapOfShape& theMFDone,
1283 TopTools_ListOfShape& theLCB,
1284 TopoDS_Face& theFaceToClassify);
1286 TopoDS_Solid mySolid; //! Solid
1287 Bnd_Box myBoxS; // Bounding box of the solid
1288 TopTools_ListOfShape myOwnIF; //! Own INTERNAL faces of the solid
1289 TopTools_ListOfShape myInFaces; //! Faces classified as IN
1291 BOPTools_BoxBndTree* myBBTree; //! UB tree of bounding boxes
1292 BOPAlgo_VectorOfShapeBox* myVShapeBox; //! ShapeBoxMap
1294 TopoDS_Iterator myItF; //! Iterators
1295 TopoDS_Iterator myItW;
1297 Handle(IntTools_Context) myContext; //! Context
1300 //=======================================================================
1301 //function : BOPAlgo_FillIn3DParts::Perform
1303 //=======================================================================
1304 void BOPAlgo_FillIn3DParts::Perform()
1306 BOPAlgo_Algo::UserBreak();
1310 // 1. Select boxes of faces that are not out of aBoxS
1311 BOPTools_BoxBndTreeSelector aSelector;
1312 aSelector.SetBox(myBoxS);
1314 if (!myBBTree->Select(aSelector))
1317 const TColStd_ListOfInteger& aLIFP = aSelector.Indices();
1319 // 2. Fill maps of edges and faces of the solid
1321 Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1323 BOPAlgo_VectorOfShapeBox& aVShapeBox = *myVShapeBox;
1325 TopTools_IndexedMapOfShape aMSE(1, anAlloc), aMSF(1, anAlloc);
1326 TopExp::MapShapes(mySolid, TopAbs_EDGE, aMSE);
1327 TopExp::MapShapes(mySolid, TopAbs_FACE, aMSF);
1329 // Check if the Solid contains any faces
1330 Standard_Boolean bIsEmpty = aMSF.IsEmpty();
1332 // Add own internal faces of the solid into aMSF
1333 TopTools_ListIteratorOfListOfShape aItLS(myOwnIF);
1334 for (; aItLS.More(); aItLS.Next())
1335 aMSF.Add(aItLS.Value());
1337 // 3. aIVec - faces to process.
1338 // Filter the selected faces with faces of the solid.
1339 NCollection_Vector<Standard_Integer> aIVec(256, anAlloc);
1341 TColStd_ListIteratorOfListOfInteger aItLI(aLIFP);
1342 for (; aItLI.More(); aItLI.Next()) {
1343 Standard_Integer nFP = aItLI.Value();
1344 const TopoDS_Shape& aFP = aVShapeBox(nFP).Shape();
1345 if (!aMSF.Contains(aFP))
1346 aIVec.Appended() = nFP;
1349 // 4. Classify faces relatively solid.
1350 // Store faces that are IN mySolid into <myInFaces>
1352 Standard_Integer k, aNbFP = aIVec.Length();
1353 // Sort indices if necessary
1355 std::sort(aIVec.begin(), aIVec.end());
1359 // The solid is empty as it does not contain any faces.
1360 // It could happen when the input solid consists of INTERNAL faces only.
1361 // Classification of any point relatively empty solid would always give IN status.
1362 // Thus, we consider all selected faces as IN without real classification.
1363 for (k = 0; k < aNbFP; ++k)
1364 myInFaces.Append(aVShapeBox(aIVec(k)).Shape());
1369 // Prepare EF map of faces to process for building connexity blocks
1370 TopTools_IndexedDataMapOfShapeListOfShape aMEFP(1, anAlloc);
1373 for (k = 0; k < aNbFP; ++k)
1374 MapEdgesAndFaces(aVShapeBox(aIVec(k)).Shape(), aMEFP, anAlloc);
1377 // Map of Edge-Face connection, necessary for solid classification.
1378 // It will be filled when first classification is performed.
1379 TopTools_IndexedDataMapOfShapeListOfShape aMEFDS(1, anAlloc);
1381 // Fence map to avoid processing of the same faces twice
1382 TopTools_MapOfShape aMFDone(1, anAlloc);
1384 for (k = 0; k < aNbFP; ++k)
1386 Standard_Integer nFP = aIVec(k);
1387 const TopoDS_Face& aFP = (*(TopoDS_Face*)&aVShapeBox(nFP).Shape());
1388 if (!aMFDone.Add(aFP))
1391 // Make connexity blocks of faces, avoiding passing through the
1392 // borders of the solid. It helps to reduce significantly the
1393 // number of classified faces.
1394 TopTools_ListOfShape aLCBF(anAlloc);
1395 // The most appropriate face for classification
1396 TopoDS_Face aFaceToClassify;
1397 MakeConnexityBlock(aFP, aMSE, aMEFP, aMFDone, aLCBF, aFaceToClassify);
1399 if (!myBoxS.IsWhole())
1401 // First, try fast classification of the whole block by additional
1402 // check on bounding boxes - check that bounding boxes of all vertices
1403 // of the block interfere with the box of the solid.
1404 // If not, the faces are out.
1405 Standard_Boolean bOut = Standard_False;
1406 aItLS.Initialize(aLCBF);
1407 for (; aItLS.More() && !bOut; aItLS.Next())
1409 TopExp_Explorer anExpV(aItLS.Value(), TopAbs_VERTEX);
1410 for (; anExpV.More() && !bOut; anExpV.Next())
1412 const TopoDS_Vertex& aV = TopoDS::Vertex(anExpV.Current());
1414 aBBV.Add(BRep_Tool::Pnt(aV));
1415 aBBV.SetGap(BRep_Tool::Tolerance(aV));
1416 bOut = myBoxS.IsOut(aBBV);
1423 if (aFaceToClassify.IsNull())
1424 aFaceToClassify = aFP;
1426 if (aMEFDS.IsEmpty())
1427 // Fill EF map for Solid
1428 TopExp::MapShapesAndAncestors(mySolid, TopAbs_EDGE, TopAbs_FACE, aMEFDS);
1430 // All vertices are interfere with the solids box, run classification.
1431 Standard_Boolean bIsIN = BOPTools_AlgoTools::IsInternalFace
1432 (aFaceToClassify, mySolid, aMEFDS, Precision::Confusion(), myContext);
1435 aItLS.Initialize(aLCBF);
1436 for (; aItLS.More(); aItLS.Next())
1437 myInFaces.Append(aItLS.Value());
1441 //=======================================================================
1442 // function: MapEdgesAndFaces
1444 //=======================================================================
1445 void BOPAlgo_FillIn3DParts::MapEdgesAndFaces(const TopoDS_Shape& theF,
1446 TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1447 const Handle(NCollection_BaseAllocator)& theAllocator)
1449 myItF.Initialize(theF);
1450 for (; myItF.More(); myItF.Next())
1452 const TopoDS_Shape& aW = myItF.Value();
1453 if (aW.ShapeType() != TopAbs_WIRE)
1456 myItW.Initialize(aW);
1457 for (; myItW.More(); myItW.Next())
1459 const TopoDS_Shape& aE = myItW.Value();
1461 TopTools_ListOfShape* pLF = theEFMap.ChangeSeek(aE);
1463 pLF = &theEFMap(theEFMap.Add(aE, TopTools_ListOfShape(theAllocator)));
1468 //=======================================================================
1469 // function: MakeConnexityBlock
1471 //=======================================================================
1472 void BOPAlgo_FillIn3DParts::MakeConnexityBlock(const TopoDS_Face& theFStart,
1473 const TopTools_IndexedMapOfShape& theMEAvoid,
1474 const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1475 TopTools_MapOfShape& theMFDone,
1476 TopTools_ListOfShape& theLCB,
1477 TopoDS_Face& theFaceToClassify)
1479 // Add start element
1480 theLCB.Append(theFStart);
1481 if (theEFMap.IsEmpty())
1484 TopTools_ListIteratorOfListOfShape aItCB(theLCB);
1485 for (; aItCB.More(); aItCB.Next())
1487 const TopoDS_Shape& aF = aItCB.Value();
1488 myItF.Initialize(aF);
1489 for (; myItF.More(); myItF.Next())
1491 const TopoDS_Shape& aW = myItF.Value();
1492 if (aW.ShapeType() != TopAbs_WIRE)
1495 myItW.Initialize(aW);
1496 for (; myItW.More(); myItW.Next())
1498 const TopoDS_Edge& aE = TopoDS::Edge(myItW.Value());
1499 if (theMEAvoid.Contains(aE) || BRep_Tool::Degenerated(aE))
1501 if (theFaceToClassify.IsNull())
1502 theFaceToClassify = TopoDS::Face(aF);
1506 const TopTools_ListOfShape* pLF = theEFMap.Seek(aE);
1509 TopTools_ListIteratorOfListOfShape aItLF(*pLF);
1510 for (; aItLF.More(); aItLF.Next())
1512 const TopoDS_Shape& aFToAdd = aItLF.Value();
1513 if (theMFDone.Add(aFToAdd))
1514 theLCB.Append(aFToAdd);
1521 // Vector of solid classifiers
1522 typedef NCollection_Vector<BOPAlgo_FillIn3DParts> BOPAlgo_VectorOfFillIn3DParts;
1524 //=======================================================================
1525 //function : ClassifyFaces
1527 //=======================================================================
1528 void BOPAlgo_Tools::ClassifyFaces(const TopTools_ListOfShape& theFaces,
1529 const TopTools_ListOfShape& theSolids,
1530 const Standard_Boolean theRunParallel,
1531 Handle(IntTools_Context)& theContext,
1532 TopTools_IndexedDataMapOfShapeListOfShape& theInParts,
1533 const TopTools_DataMapOfShapeBox& theShapeBoxMap,
1534 const TopTools_DataMapOfShapeListOfShape& theSolidsIF)
1536 Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1538 // Fill the vector of shape box with faces and its bounding boxes
1539 BOPAlgo_VectorOfShapeBox aVSB(256, anAlloc);
1541 TopTools_ListIteratorOfListOfShape aItLF(theFaces);
1542 for (; aItLF.More(); aItLF.Next())
1544 const TopoDS_Shape& aF = aItLF.Value();
1545 // Append face to the vector of shape box
1546 BOPAlgo_ShapeBox& aSB = aVSB.Appended();
1549 // Get bounding box for the face
1550 const Bnd_Box* pBox = theShapeBoxMap.Seek(aF);
1555 // Build the bounding box
1557 BRepBndLib::Add(aF, aBox);
1562 // Prepare UB tree of bounding boxes of the faces to classify
1563 // taking the bounding boxes from the just prepared vector
1564 BOPTools_BoxBndTree aBBTree;
1565 NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
1567 Standard_Integer aNbF = aVSB.Length();
1568 for (Standard_Integer i = 0; i < aNbF; ++i)
1570 aTreeFiller.Add(i, aVSB(i).Box());
1573 // Shake tree filler
1576 // Prepare vector of solids to classify
1577 BOPAlgo_VectorOfFillIn3DParts aVFIP;
1579 TopTools_ListIteratorOfListOfShape aItLS(theSolids);
1580 for (; aItLS.More(); aItLS.Next())
1582 const TopoDS_Solid& aSolid = TopoDS::Solid(aItLS.Value());
1583 // Append solid to the vector
1584 BOPAlgo_FillIn3DParts& aFIP = aVFIP.Appended();
1585 aFIP.SetSolid(aSolid);
1587 // Get bounding box for the solid
1588 const Bnd_Box* pBox = theShapeBoxMap.Seek(aSolid);
1590 aFIP.SetBoxS(*pBox);
1593 // Build the bounding box
1595 BRepBndLib::Add(aSolid, aBox);
1596 if (!aBox.IsWhole())
1598 if (BOPTools_AlgoTools::IsInvertedSolid(aSolid))
1604 const TopTools_ListOfShape* pLIF = theSolidsIF.Seek(aSolid);
1606 aFIP.SetOwnIF(*pLIF);
1608 aFIP.SetBBTree(aBBTree);
1609 aFIP.SetShapeBoxVector(aVSB);
1612 // Perform classification
1613 //================================================================
1614 BOPTools_Parallel::Perform (theRunParallel, aVFIP, theContext);
1615 //================================================================
1617 // Analyze the results and fill the resulting map
1619 Standard_Integer aNbS = aVFIP.Length();
1620 for (Standard_Integer i = 0; i < aNbS; ++i)
1622 BOPAlgo_FillIn3DParts& aFIP = aVFIP(i);
1623 const TopoDS_Shape& aS = aFIP.Solid();
1624 const TopTools_ListOfShape& aLFIn = aFIP.InFaces();
1625 theInParts.Add(aS, aLFIn);
1629 //=======================================================================
1630 //function : FillInternals
1632 //=======================================================================
1633 void BOPAlgo_Tools::FillInternals(const TopTools_ListOfShape& theSolids,
1634 const TopTools_ListOfShape& theParts,
1635 const TopTools_DataMapOfShapeListOfShape& theImages,
1636 const Handle(IntTools_Context)& theContext)
1638 if (theSolids.IsEmpty() || theParts.IsEmpty())
1641 // Map the solids to avoid classification of the own shapes of the solids
1642 TopTools_IndexedMapOfShape aMSSolids;
1643 TopTools_ListOfShape::Iterator itLS(theSolids);
1644 for (; itLS.More(); itLS.Next())
1646 const TopoDS_Shape& aSolid = itLS.Value();
1647 if (aSolid.ShapeType() == TopAbs_SOLID)
1649 TopExp::MapShapes(aSolid, TopAbs_VERTEX, aMSSolids);
1650 TopExp::MapShapes(aSolid, TopAbs_EDGE, aMSSolids);
1651 TopExp::MapShapes(aSolid, TopAbs_FACE, aMSSolids);
1655 // Extract BRep elements from the given parts and
1656 // check them for possible splits
1657 TopTools_ListOfShape aLPartsInput = theParts, aLParts;
1658 TopTools_ListOfShape::Iterator itLP(aLPartsInput);
1659 for (; itLP.More(); itLP.Next())
1661 const TopoDS_Shape& aPart = itLP.Value();
1662 switch (aPart.ShapeType())
1668 const TopTools_ListOfShape* pIm = theImages.Seek(aPart);
1671 TopTools_ListOfShape::Iterator itIm(*pIm);
1672 for (; itIm.More(); itIm.Next())
1674 const TopoDS_Shape& aPartIm = itIm.Value();
1675 if (!aMSSolids.Contains(aPartIm))
1676 aLParts.Append(aPartIm);
1679 else if (!aMSSolids.Contains(aPart))
1680 aLParts.Append(aPart);
1686 for (TopoDS_Iterator it(aPart); it.More(); it.Next())
1687 aLPartsInput.Append(it.Value());
1693 // Classify the given parts relatively solids.
1694 // Add edges and vertices classified as IN into solids instantly,
1695 // and collect faces classified as IN into a list for further shell creation
1697 TopTools_DataMapOfShapeListOfShape anINFaces;
1698 itLS.Initialize(theSolids);
1699 for (; itLS.More(); itLS.Next())
1701 const TopoDS_Shape& aSolid = itLS.Value();
1702 if (aSolid.ShapeType() != TopAbs_SOLID)
1705 TopoDS_Solid aSd = *(TopoDS_Solid*)&aSolid;
1707 itLP.Initialize(aLParts);
1708 for (; itLP.More();)
1710 TopoDS_Shape aPart = itLP.Value();
1711 TopAbs_State aState =
1712 BOPTools_AlgoTools::ComputeStateByOnePoint(aPart, aSd, Precision::Confusion(), theContext);
1713 if (aState == TopAbs_IN)
1715 if (aPart.ShapeType() == TopAbs_FACE)
1717 TopTools_ListOfShape *pFaces = anINFaces.ChangeSeek(aSd);
1719 pFaces = anINFaces.Bound(aSd, TopTools_ListOfShape());
1720 pFaces->Append(aPart);
1724 aPart.Orientation(TopAbs_INTERNAL);
1725 BRep_Builder().Add(aSd, aPart);
1727 aLParts.Remove(itLP);
1734 // Make shells from faces and put them into solids
1735 TopTools_DataMapOfShapeListOfShape::Iterator itM(anINFaces);
1736 for (; itM.More(); itM.Next())
1738 TopoDS_Solid aSd = *(TopoDS_Solid*)&itM.Key();
1739 const TopTools_ListOfShape& aFaces = itM.Value();
1741 TopoDS_Compound aCF;
1742 BRep_Builder().MakeCompound(aCF);
1744 TopTools_ListOfShape::Iterator itLF(aFaces);
1745 for (; itLF.More(); itLF.Next())
1746 BRep_Builder().Add(aCF, itLF.Value());
1748 // Build blocks from the faces
1749 TopTools_ListOfShape aLCB;
1750 BOPTools_AlgoTools::MakeConnexityBlocks(aCF, TopAbs_EDGE, TopAbs_FACE, aLCB);
1752 // Build shell from each block
1753 TopTools_ListOfShape::Iterator itCB(aLCB);
1754 for (; itCB.More(); itCB.Next())
1756 const TopoDS_Shape& aCB = itCB.Value();
1758 TopoDS_Shell aShell;
1759 BRep_Builder().MakeShell(aShell);
1760 // Add faces of the block to the shell
1761 TopExp_Explorer expF(aCB, TopAbs_FACE);
1762 for (; expF.More(); expF.Next())
1764 TopoDS_Face aFInt = TopoDS::Face(expF.Current());
1765 aFInt.Orientation(TopAbs_INTERNAL);
1766 BRep_Builder().Add(aShell, aFInt);
1769 BRep_Builder().Add(aSd, aShell);