1 // Created by: Peter KURNEV
2 // Copyright (c) 2010-2014 OPEN CASCADE SAS
3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
5 // EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
7 // This file is part of Open CASCADE Technology software library.
9 // This library is free software; you can redistribute it and/or modify it under
10 // the terms of the GNU Lesser General Public License version 2.1 as published
11 // by the Free Software Foundation, with special exception defined in the file
12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
13 // distribution for complete text of the license and disclaimer of any warranty.
15 // Alternatively, this file may be used under the terms of Open CASCADE
16 // commercial license or contractual agreement.
18 #include <BOPAlgo_BuilderSolid.hxx>
19 #include <BOPAlgo_ShellSplitter.hxx>
20 #include <BOPAlgo_Alerts.hxx>
21 #include <BOPAlgo_Tools.hxx>
22 #include <BOPTools_AlgoTools.hxx>
23 #include <BOPTools_AlgoTools3D.hxx>
24 #include <BOPTools_BoxTree.hxx>
25 #include <BOPTools_CoupleOfShape.hxx>
26 #include <BOPTools_Parallel.hxx>
27 #include <Bnd_Tools.hxx>
28 #include <BRep_Builder.hxx>
29 #include <BRep_Tool.hxx>
30 #include <BRepBndLib.hxx>
31 #include <BRepClass3d_SolidClassifier.hxx>
32 #include <Geom2d_Curve.hxx>
33 #include <Geom_Curve.hxx>
34 #include <Geom_Surface.hxx>
38 #include <gp_Pnt2d.hxx>
40 #include <IntTools_Context.hxx>
41 #include <NCollection_DataMap.hxx>
42 #include <NCollection_List.hxx>
43 #include <NCollection_Vector.hxx>
44 #include <TColStd_MapIntegerHasher.hxx>
47 #include <TopExp_Explorer.hxx>
49 #include <TopoDS_Compound.hxx>
50 #include <TopoDS_Edge.hxx>
51 #include <TopoDS_Face.hxx>
52 #include <TopoDS_Iterator.hxx>
53 #include <TopoDS_Shape.hxx>
54 #include <TopoDS_Shell.hxx>
55 #include <TopoDS_Solid.hxx>
56 #include <TopoDS_Vertex.hxx>
57 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
58 #include <TopTools_IndexedDataMapOfShapeShape.hxx>
59 #include <TColStd_ListOfInteger.hxx>
60 #include <TopTools_ListOfShape.hxx>
61 #include <TopTools_MapOfOrientedShape.hxx>
62 #include <TopTools_MapOfShape.hxx>
66 Standard_Boolean IsGrowthShell(const TopoDS_Shape& ,
67 const TopTools_IndexedMapOfShape& );
69 Standard_Boolean IsHole(const TopoDS_Shape& ,
70 Handle(IntTools_Context)& );
72 Standard_Boolean IsInside(const TopoDS_Shape& ,
74 Handle(IntTools_Context)& );
76 void MakeInternalShells(const TopTools_IndexedMapOfShape& ,
77 TopTools_ListOfShape& );
79 //=======================================================================
82 //=======================================================================
83 BOPAlgo_BuilderSolid::BOPAlgo_BuilderSolid()
88 //=======================================================================
91 //=======================================================================
92 BOPAlgo_BuilderSolid::BOPAlgo_BuilderSolid
93 (const Handle(NCollection_BaseAllocator)& theAllocator)
95 BOPAlgo_BuilderArea(theAllocator)
98 //=======================================================================
101 //=======================================================================
102 BOPAlgo_BuilderSolid::~BOPAlgo_BuilderSolid()
105 //=======================================================================
108 //=======================================================================
109 void BOPAlgo_BuilderSolid::Perform()
111 GetReport()->Clear();
113 if (myShapes.IsEmpty())
116 if (myContext.IsNull()) {
117 myContext=new IntTools_Context;
124 TopTools_ListIteratorOfListOfShape aIt;
126 aBB.MakeCompound(aC);
127 aIt.Initialize(myShapes);
128 for(; aIt.More(); aIt.Next()) {
129 const TopoDS_Shape& aF=aIt.Value();
135 PerformShapesToAvoid();
156 PerformInternalShapes();
161 //=======================================================================
162 //function :PerformShapesToAvoid
164 //=======================================================================
165 void BOPAlgo_BuilderSolid::PerformShapesToAvoid()
167 Standard_Boolean bFound;
168 Standard_Integer i, iCnt, aNbE, aNbF;
169 TopAbs_Orientation aOrE;
170 TopTools_IndexedDataMapOfShapeListOfShape aMEF;
171 TopTools_ListIteratorOfListOfShape aIt;
173 myShapesToAvoid.Clear();
178 bFound=Standard_False;
182 aIt.Initialize (myShapes);
183 for (; aIt.More(); aIt.Next()) {
184 const TopoDS_Shape& aF=aIt.Value();
185 if (!myShapesToAvoid.Contains(aF)) {
186 TopExp::MapShapesAndAncestors(aF,
195 for (i=1; i<=aNbE; ++i) {
196 const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aMEF.FindKey(i)));
197 if (BRep_Tool::Degenerated(aE)) {
201 TopTools_ListOfShape& aLF=aMEF.ChangeFromKey(aE);
207 aOrE=aE.Orientation();
209 const TopoDS_Face& aF1=(*(TopoDS_Face*)(&aLF.First()));
211 if (aOrE==TopAbs_INTERNAL) {
214 bFound=Standard_True;
215 myShapesToAvoid.Add(aF1);
218 const TopoDS_Face& aF2=(*(TopoDS_Face*)(&aLF.Last()));
219 if (aF2.IsSame(aF1)) {
220 if (BRep_Tool::IsClosed(aE, aF1)) {
224 if (aOrE==TopAbs_INTERNAL) {
228 bFound=Standard_True;
229 myShapesToAvoid.Add(aF1);
230 myShapesToAvoid.Add(aF2);
233 }// for (i=1; i<=aNbE; ++i) {
241 //=======================================================================
242 //function : PerformLoops
244 //=======================================================================
245 void BOPAlgo_BuilderSolid::PerformLoops()
247 Standard_Integer i, aNbSh;
248 TopTools_ListIteratorOfListOfShape aIt;
249 TopoDS_Iterator aItS;
250 Handle(NCollection_BaseAllocator) aAlr;
255 NCollection_BaseAllocator::CommonBaseAllocator();
256 BOPAlgo_ShellSplitter aSSp(aAlr);
259 aIt.Initialize (myShapes);
260 for (; aIt.More(); aIt.Next()) {
261 const TopoDS_Face& aF=*((TopoDS_Face*)&aIt.Value());
262 if (myContext->IsInfiniteFace(aF)) {
272 if (!myShapesToAvoid.Contains(aF)) {
273 aSSp.AddStartElement(aF);
277 aSSp.SetRunParallel(myRunParallel);
279 if (aSSp.HasErrors()) {
280 // add warning status
282 TopoDS_Compound aFacesSp;
283 BRep_Builder().MakeCompound(aFacesSp);
284 TopTools_ListIteratorOfListOfShape aItLF(aSSp.StartElements());
285 for (; aItLF.More(); aItLF.Next()) {
286 BRep_Builder().Add(aFacesSp, aItLF.Value());
288 AddWarning (new BOPAlgo_AlertShellSplitterFailed (aFacesSp));
293 const TopTools_ListOfShape& aLSh=aSSp.Shells();
294 aIt.Initialize (aLSh);
295 for (; aIt.More(); aIt.Next()) {
296 const TopoDS_Shape& aSh=aIt.Value();
299 //=================================================
303 TopTools_MapOfOrientedShape AddedFacesMap;
304 TopTools_IndexedDataMapOfShapeListOfShape aEFMap;
305 TopTools_MapOfOrientedShape aMP;
307 // a. collect all edges that are in loops
308 aIt.Initialize (myLoops);
309 for (; aIt.More(); aIt.Next()) {
310 const TopoDS_Shape& aS=aIt.Value();
312 for (; aItS.More(); aItS.Next()) {
313 const TopoDS_Shape& aF=aItS.Value();
318 // b. collect all edges that are to avoid
319 aNbSh = myShapesToAvoid.Extent();
320 for (i = 1; i <= aNbSh; ++i) {
321 const TopoDS_Shape& aF = myShapesToAvoid(i);
325 // c. add all edges that are not processed to myShapesToAvoid
326 aIt.Initialize (myShapes);
327 for (; aIt.More(); aIt.Next()) {
328 const TopoDS_Face& aF=*((TopoDS_Face*)&aIt.Value());
329 if (!myContext->IsInfiniteFace(aF)) {
330 if (!aMP.Contains(aF)) {
331 myShapesToAvoid.Add(aF);
335 //=================================================
338 myLoopsInternal.Clear();
341 AddedFacesMap.Clear();
343 aNbSh = myShapesToAvoid.Extent();
344 for (i = 1; i <= aNbSh; ++i) {
345 const TopoDS_Shape& aFF = myShapesToAvoid(i);
346 TopExp::MapShapesAndAncestors(aFF,
347 TopAbs_EDGE, TopAbs_FACE,
351 for (i = 1; i <= aNbSh; ++i) {
352 const TopoDS_Shape& aFF = myShapesToAvoid(i);
353 if (!AddedFacesMap.Add(aFF)) {
358 TopExp_Explorer aExp;
360 aBB.MakeShell(aShell);
361 aBB.Add(aShell, aFF);
363 aItS.Initialize(aShell);
364 for (; aItS.More(); aItS.Next()) {
365 const TopoDS_Face& aF = (*(TopoDS_Face*)(&aItS.Value()));
367 aExp.Init(aF, TopAbs_EDGE);
368 for (; aExp.More(); aExp.Next()) {
369 const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aExp.Current()));
370 const TopTools_ListOfShape& aLF=aEFMap.FindFromKey(aE);
372 for (; aIt.More(); aIt.Next()) {
373 const TopoDS_Face& aFL=(*(TopoDS_Face*)(&aIt.Value()));
374 if (AddedFacesMap.Add(aFL)){
375 aBB.Add(aShell, aFL);
380 aShell.Closed (BRep_Tool::IsClosed (aShell));
381 myLoopsInternal.Append(aShell);
384 //=======================================================================
385 //function : PerformAreas
387 //=======================================================================
388 void BOPAlgo_BuilderSolid::PerformAreas()
393 TopTools_ListOfShape aNewSolids;
394 // The hole shells which has to be classified relatively new solids
395 TopTools_IndexedMapOfShape aHoleShells;
396 // Map of the faces of the hole shells for quick check of the growths.
397 // If the analyzed shell contains any of the hole faces, it is considered as growth.
398 TopTools_IndexedMapOfShape aMHF;
400 // Analyze the shells
401 TopTools_ListIteratorOfListOfShape aItLL(myLoops);
402 for (; aItLL.More(); aItLL.Next())
404 const TopoDS_Shape& aShell = aItLL.Value();
406 Standard_Boolean bIsGrowth = IsGrowthShell(aShell, aMHF);
409 // Fast check did not give the result, run classification
410 bIsGrowth = !IsHole(aShell, myContext);
417 aBB.MakeSolid(aSolid);
418 aBB.Add (aSolid, aShell);
419 aNewSolids.Append (aSolid);
423 aHoleShells.Add(aShell);
424 TopExp::MapShapes(aShell, TopAbs_FACE, aMHF);
428 if (aHoleShells.IsEmpty())
430 // No holes, stop the analysis
431 TopTools_ListIteratorOfListOfShape aItLS(aNewSolids);
432 for (; aItLS.More(); aItLS.Next())
434 const TopoDS_Shape& aSol = aItLS.Value();
435 myAreas.Append(aSol);
438 BRepBndLib::Add(aSol, aBox);
439 myBoxes.Bind(aSol, aBox);
444 // Classify holes relatively solids
446 // Prepare tree with the boxes of the hole shells
447 BOPTools_BoxTree aBBTree;
448 Standard_Integer i, aNbH = aHoleShells.Extent();
449 aBBTree.SetSize (aNbH);
450 for (i = 1; i <= aNbH; ++i)
452 const TopoDS_Shape& aHShell = aHoleShells(i);
455 BRepBndLib::Add(aHShell, aBox);
456 aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aBox));
458 myBoxes.Bind(aHShell, aBox);
464 // Find outer growth shell that is most close to each hole shell
465 TopTools_IndexedDataMapOfShapeShape aHoleSolidMap;
467 TopTools_ListIteratorOfListOfShape aItLS(aNewSolids);
468 for (; aItLS.More(); aItLS.Next())
470 const TopoDS_Shape& aSolid = aItLS.Value();
474 BRepBndLib::Add(aSolid, aBox);
476 myBoxes.Bind(aSolid, aBox);
478 BOPTools_BoxTreeSelector aSelector;
479 aSelector.SetBox(Bnd_Tools::Bnd2BVH(aBox));
480 aSelector.SetBVHSet (&aBBTree);
483 const TColStd_ListOfInteger& aLI = aSelector.Indices();
484 TColStd_ListIteratorOfListOfInteger aItLI(aLI);
485 for (; aItLI.More(); aItLI.Next())
487 Standard_Integer k = aItLI.Value();
488 const TopoDS_Shape& aHole = aHoleShells(k);
489 // Check if it is inside
490 if (!IsInside(aHole, aSolid, myContext))
494 TopoDS_Shape* pSolidWas = aHoleSolidMap.ChangeSeek(aHole);
497 if (IsInside(aSolid, *pSolidWas, myContext))
504 aHoleSolidMap.Add(aHole, aSolid);
509 // Make the back map from solids to holes
510 TopTools_IndexedDataMapOfShapeListOfShape aSolidHolesMap;
512 aNbH = aHoleSolidMap.Extent();
513 for (i = 1; i <= aNbH; ++i)
515 const TopoDS_Shape& aHole = aHoleSolidMap.FindKey(i);
516 const TopoDS_Shape& aSolid = aHoleSolidMap(i);
518 TopTools_ListOfShape* pLHoles = aSolidHolesMap.ChangeSeek(aSolid);
520 pLHoles = &aSolidHolesMap(aSolidHolesMap.Add(aSolid, TopTools_ListOfShape()));
521 pLHoles->Append(aHole);
524 // Add Holes to Solids and add them to myAreas
525 aItLS.Initialize(aNewSolids);
526 for ( ; aItLS.More(); aItLS.Next())
528 TopoDS_Solid& aSolid = *(TopoDS_Solid*)&aItLS.Value();
529 const TopTools_ListOfShape* pLHoles = aSolidHolesMap.Seek(aSolid);
533 TopTools_ListIteratorOfListOfShape aItLH(*pLHoles);
534 for (; aItLH.More(); aItLH.Next())
536 const TopoDS_Shape& aHole = aItLH.Value();
537 aBB.Add(aSolid, aHole);
541 myContext->SolidClassifier(aSolid).Load(aSolid);
544 myAreas.Append(aSolid);
547 // Add holes that outside the solids to myAreas
548 aNbH = aHoleShells.Extent();
549 for (i = 1; i <= aNbH; ++i)
551 const TopoDS_Shape& aHole = aHoleShells(i);
552 if (!aHoleSolidMap.Contains(aHole))
555 aBB.MakeSolid(aSolid);
556 aBB.Add (aSolid, aHole);
558 myAreas.Append(aSolid);
559 // Make an infinite box for the hole
562 myBoxes.Bind(aSolid, aBox);
565 myBoxes.UnBind(aHole);
568 //=======================================================================
569 //function : PerformInternalShapes
571 //=======================================================================
572 void BOPAlgo_BuilderSolid::PerformInternalShapes()
574 if (myAvoidInternalShapes)
575 // user-defined option to avoid internal parts is in force
578 if (myLoopsInternal.IsEmpty())
582 // Get all faces to classify
583 TopTools_IndexedMapOfShape aMFs;
584 TopTools_ListIteratorOfListOfShape aItLS(myLoopsInternal);
585 for (; aItLS.More(); aItLS.Next())
587 const TopoDS_Shape& aShell = aItLS.Value();
588 TopoDS_Iterator aIt(aShell);
589 for (; aIt.More(); aIt.Next())
590 aMFs.Add(aIt.Value());
594 // Check existence of the growths solids
595 if (myAreas.IsEmpty())
598 // Just make solid of the faces
600 aBB.MakeSolid(aSolid);
602 TopTools_ListOfShape aLSI;
603 MakeInternalShells(aMFs, aLSI);
605 aItLS.Initialize(aLSI);
606 for (; aItLS.More(); aItLS.Next())
607 aBB.Add(aSolid, aItLS.Value());
609 myAreas.Append(aSolid);
613 // Classify faces relatively solids
615 // Prepare list of faces to classify
616 TopTools_ListOfShape aLFaces;
617 Standard_Integer i, aNbF = aMFs.Extent();
618 for (i = 1; i <= aNbF; ++i)
619 aLFaces.Append(aMFs(i));
621 // Map of solids with IN faces
622 TopTools_IndexedDataMapOfShapeListOfShape aMSLF;
624 // Perform classification
625 BOPAlgo_Tools::ClassifyFaces(aLFaces, myAreas, myRunParallel, myContext, aMSLF, myBoxes);
627 // Update Solids by internal Faces
629 TopTools_MapOfShape aMFDone;
631 Standard_Integer aNbS = aMSLF.Extent();
632 for (i = 1; i <= aNbS; ++i)
634 const TopoDS_Shape& aSolid = aMSLF.FindKey(i);
635 TopoDS_Shape *pSolid = (TopoDS_Shape*)&aSolid;
637 const TopTools_ListOfShape& aLF = aMSLF(i);
641 TopTools_IndexedMapOfShape aMF;
642 aItLS.Initialize(aLF);
643 for (; aItLS.More(); aItLS.Next())
645 const TopoDS_Shape& aF = aItLS.Value();
650 TopTools_ListOfShape aLSI;
651 MakeInternalShells(aMF, aLSI);
653 aItLS.Initialize(aLSI);
654 for (; aItLS.More(); aItLS.Next())
656 const TopoDS_Shape& aSI = aItLS.Value();
657 aBB.Add (*pSolid, aSI);
661 // Find all unclassified faces and warn the user about them.
662 // Do not put such faces into result as they will form not closed solid.
663 TopTools_IndexedMapOfShape aMFUnUsed;
665 for (i = 1; i <= aNbF; ++i)
667 const TopoDS_Shape& aF = aMFs(i);
668 if (!aMFDone.Contains(aF))
672 if (aMFUnUsed.Extent())
674 TopTools_ListOfShape aLSI;
675 MakeInternalShells(aMFUnUsed, aLSI);
677 TopoDS_Shape aWShape;
678 if (aLSI.Extent() == 1)
679 aWShape = aLSI.First();
682 aBB.MakeCompound(TopoDS::Compound(aWShape));
683 aItLS.Initialize(aLSI);
684 for (; aItLS.More(); aItLS.Next())
685 aBB.Add(aWShape, aItLS.Value());
688 AddWarning(new BOPAlgo_AlertSolidBuilderUnusedFaces(aWShape));
691 //=======================================================================
692 //function : MakeInternalShells
694 //=======================================================================
695 void MakeInternalShells(const TopTools_IndexedMapOfShape& theMF,
696 TopTools_ListOfShape& theShells)
698 Standard_Integer i, aNbF;
700 TopTools_ListIteratorOfListOfShape aItF;
701 TopTools_IndexedDataMapOfShapeListOfShape aMEF;
702 TopTools_MapOfShape aAddedFacesMap;
704 aNbF = theMF.Extent();
705 for (i = 1; i <= aNbF; ++i) {
706 TopoDS_Shape aF = theMF(i);
707 TopExp::MapShapesAndAncestors(aF,
708 TopAbs_EDGE, TopAbs_FACE,
712 for (i = 1; i <= aNbF; ++i) {
713 TopoDS_Shape aFF = theMF(i);
714 if (!aAddedFacesMap.Add(aFF)) {
720 aBB.MakeShell(aShell);
721 aFF.Orientation(TopAbs_INTERNAL);
722 aBB.Add(aShell, aFF);
724 TopoDS_Iterator aItAddedF (aShell);
725 for (; aItAddedF.More(); aItAddedF.Next()) {
726 const TopoDS_Shape& aF =aItAddedF.Value();
728 TopExp_Explorer aEdgeExp(aF, TopAbs_EDGE);
729 for (; aEdgeExp.More(); aEdgeExp.Next()) {
730 const TopoDS_Shape& aE =aEdgeExp.Current();
731 const TopTools_ListOfShape& aLF=aMEF.FindFromKey(aE);
732 aItF.Initialize(aLF);
733 for (; aItF.More(); aItF.Next()) {
734 TopoDS_Shape aFL=aItF.Value();
735 if (aAddedFacesMap.Add(aFL)){
736 aFL.Orientation(TopAbs_INTERNAL);
737 aBB.Add(aShell, aFL);
742 aShell.Closed (BRep_Tool::IsClosed (aShell));
743 theShells.Append(aShell);
746 //=======================================================================
749 //=======================================================================
750 Standard_Boolean IsHole(const TopoDS_Shape& theS2,
751 Handle(IntTools_Context)& theContext)
753 TopoDS_Solid *pS2=(TopoDS_Solid *)&theS2;
754 BRepClass3d_SolidClassifier& aClsf=theContext->SolidClassifier(*pS2);
756 aClsf.PerformInfinitePoint(::RealSmall());
758 return (aClsf.State()==TopAbs_IN);
760 //=======================================================================
761 //function : IsInside
763 //=======================================================================
764 Standard_Boolean IsInside(const TopoDS_Shape& theS1,
765 const TopoDS_Shape& theS2,
766 Handle(IntTools_Context)& theContext)
768 TopExp_Explorer aExp;
771 TopoDS_Solid *pS2=(TopoDS_Solid *)&theS2;
773 aExp.Init(theS1, TopAbs_FACE);
775 BRepClass3d_SolidClassifier& aClsf=theContext->SolidClassifier(*pS2);
776 aClsf.PerformInfinitePoint(::RealSmall());
777 aState=aClsf.State();
780 TopTools_IndexedMapOfShape aBounds;
781 TopExp::MapShapes(*pS2, TopAbs_EDGE, aBounds);
782 const TopoDS_Face& aF = (*(TopoDS_Face*)(&aExp.Current()));
783 aState=BOPTools_AlgoTools::ComputeState(aF, *pS2,
784 Precision::Confusion(),
785 aBounds, theContext);
787 return (aState==TopAbs_IN);
789 //=======================================================================
790 //function : IsGrowthShell
792 //=======================================================================
793 Standard_Boolean IsGrowthShell(const TopoDS_Shape& theShell,
794 const TopTools_IndexedMapOfShape& theMHF)
798 TopoDS_Iterator aIt(theShell);
799 for(; aIt.More(); aIt.Next())
801 if (theMHF.Contains(aIt.Value()))
802 return Standard_True;
805 return Standard_False;