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
10 // under the terms of the GNU Lesser General Public 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.ixx>
20 #include <NCollection_List.hxx>
21 #include <NCollection_DataMap.hxx>
22 #include <NCollection_UBTreeFiller.hxx>
24 #include <gp_Pnt2d.hxx>
30 #include <TColStd_MapIntegerHasher.hxx>
32 #include <Geom_Curve.hxx>
33 #include <Geom_Surface.hxx>
34 #include <Geom2d_Curve.hxx>
38 #include <TopoDS_Iterator.hxx>
39 #include <TopoDS_Face.hxx>
40 #include <TopoDS_Shape.hxx>
41 #include <TopoDS_Shell.hxx>
42 #include <TopoDS_Edge.hxx>
43 #include <TopoDS_Solid.hxx>
44 #include <TopoDS_Vertex.hxx>
45 #include <TopoDS_Compound.hxx>
47 #include <BRep_Builder.hxx>
48 #include <BRep_Tool.hxx>
51 #include <TopExp_Explorer.hxx>
53 #include <BRepBndLib.hxx>
54 #include <BRepClass3d_SolidClassifier.hxx>
56 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
57 #include <BOPCol_ListOfShape.hxx>
58 #include <BOPCol_MapOfOrientedShape.hxx>
59 #include <BOPCol_DataMapOfShapeShape.hxx>
60 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
61 #include <BOPCol_MapOfShape.hxx>
62 #include <BOPCol_BoxBndTree.hxx>
63 #include <BOPCol_ListOfInteger.hxx>
65 #include <BOPTools.hxx>
66 #include <BOPTools_CoupleOfShape.hxx>
67 #include <BOPTools_AlgoTools.hxx>
69 #include <BOPInt_Context.hxx>
71 #include <BOPAlgo_ShellSplitter.hxx>
74 Standard_Boolean IsGrowthShell(const TopoDS_Shape& ,
75 const BOPCol_IndexedMapOfShape& );
77 Standard_Boolean IsHole(const TopoDS_Shape& ,
78 Handle(BOPInt_Context)& );
80 Standard_Boolean IsInside(const TopoDS_Shape& ,
82 Handle(BOPInt_Context)& );
84 void MakeInternalShells(const BOPCol_MapOfShape& ,
85 BOPCol_ListOfShape& );
87 //=======================================================================
88 //class : BOPAlgo_BuilderSolid_ShapeBox
89 //purpose : Auxiliary class
90 //=======================================================================
91 class BOPAlgo_BuilderSolid_ShapeBox {
93 BOPAlgo_BuilderSolid_ShapeBox() {
94 myIsHole=Standard_False;
97 ~BOPAlgo_BuilderSolid_ShapeBox() {
100 void SetShape(const TopoDS_Shape& aS) {
104 const TopoDS_Shape& Shape()const {
108 void SetBox(const Bnd_Box& aBox) {
112 const Bnd_Box& Box()const {
116 void SetIsHole(const Standard_Boolean bFlag) {
120 Standard_Boolean IsHole()const {
125 Standard_Boolean myIsHole;
126 TopoDS_Shape myShape;
130 typedef NCollection_DataMap\
131 <Standard_Integer, BOPAlgo_BuilderSolid_ShapeBox, TColStd_MapIntegerHasher> \
132 BOPAlgo_DataMapOfIntegerBSSB;
134 typedef BOPAlgo_DataMapOfIntegerBSSB::Iterator \
135 BOPAlgo_DataMapIteratorOfDataMapOfIntegerBSSB;
137 //=======================================================================
140 //=======================================================================
141 BOPAlgo_BuilderSolid::BOPAlgo_BuilderSolid()
143 BOPAlgo_BuilderArea()
146 //=======================================================================
149 //=======================================================================
150 BOPAlgo_BuilderSolid::BOPAlgo_BuilderSolid
151 (const Handle(NCollection_BaseAllocator)& theAllocator)
153 BOPAlgo_BuilderArea(theAllocator)
156 //=======================================================================
159 //=======================================================================
160 BOPAlgo_BuilderSolid::~BOPAlgo_BuilderSolid()
163 //=======================================================================
164 //function : SetSolid
166 //=======================================================================
167 void BOPAlgo_BuilderSolid::SetSolid(const TopoDS_Solid& aS)
171 //=======================================================================
174 //=======================================================================
175 const TopoDS_Solid& BOPAlgo_BuilderSolid::Solid()const
179 //=======================================================================
182 //=======================================================================
183 void BOPAlgo_BuilderSolid::Perform()
187 if (myContext.IsNull()) {
188 myContext=new BOPInt_Context;
193 BOPCol_ListIteratorOfListOfShape aIt;
195 aBB.MakeCompound(aC);
196 aIt.Initialize(myShapes);
197 for(; aIt.More(); aIt.Next()) {
198 const TopoDS_Shape& aF=aIt.Value();
203 PerformShapesToAvoid();
216 PerformInternalShapes();
221 //=======================================================================
222 //function :PerformShapesToAvoid
224 //=======================================================================
225 void BOPAlgo_BuilderSolid::PerformShapesToAvoid()
227 Standard_Boolean bFound;
228 Standard_Integer i, iCnt, aNbE, aNbF;
229 TopAbs_Orientation aOrE;
230 BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
231 BOPCol_ListIteratorOfListOfShape aIt;
233 myShapesToAvoid.Clear();
238 bFound=Standard_False;
242 aIt.Initialize (myShapes);
243 for (; aIt.More(); aIt.Next()) {
244 const TopoDS_Shape& aF=aIt.Value();
245 if (!myShapesToAvoid.Contains(aF)) {
246 BOPTools::MapShapesAndAncestors(aF, TopAbs_EDGE, TopAbs_FACE, aMEF);
252 for (i=1; i<=aNbE; ++i) {
253 const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aMEF.FindKey(i)));
254 if (BRep_Tool::Degenerated(aE)) {
258 BOPCol_ListOfShape& aLF=aMEF.ChangeFromKey(aE);
264 aOrE=aE.Orientation();
266 const TopoDS_Face& aF1=(*(TopoDS_Face*)(&aLF.First()));
268 if (aOrE==TopAbs_INTERNAL) {
271 bFound=Standard_True;
272 myShapesToAvoid.Add(aF1);
275 const TopoDS_Face& aF2=(*(TopoDS_Face*)(&aLF.Last()));
276 if (aF2.IsSame(aF1)) {
277 if (BRep_Tool::IsClosed(aE, aF1)) {
281 if (aOrE==TopAbs_INTERNAL) {
285 bFound=Standard_True;
286 myShapesToAvoid.Add(aF1);
287 myShapesToAvoid.Add(aF2);
290 }// for (i=1; i<=aNbE; ++i) {
298 //=======================================================================
299 //function : PerformLoops
301 //=======================================================================
302 void BOPAlgo_BuilderSolid::PerformLoops()
304 Standard_Integer iErr;
305 BOPCol_ListIteratorOfListOfShape aIt;
306 TopoDS_Iterator aItS;
307 BOPCol_MapIteratorOfMapOfOrientedShape aItM;
308 BOPAlgo_ShellSplitter aSSp;
314 aIt.Initialize (myShapes);
315 for (; aIt.More(); aIt.Next()) {
316 const TopoDS_Shape& aF=aIt.Value();
317 if (!myShapesToAvoid.Contains(aF)) {
318 aSSp.AddStartElement(aF);
322 aSSp.SetRunParallel(myRunParallel);
324 iErr=aSSp.ErrorStatus();
329 const BOPCol_ListOfShape& aLSh=aSSp.Shells();
330 aIt.Initialize (aLSh);
331 for (; aIt.More(); aIt.Next()) {
332 const TopoDS_Shape& aSh=aIt.Value();
335 //=================================================
338 Standard_Integer aNbFA;
340 BOPCol_MapOfOrientedShape AddedFacesMap;
341 BOPCol_IndexedDataMapOfShapeListOfShape aEFMap;
342 BOPCol_MapOfOrientedShape aMP;
344 // a. collect all edges that are in loops
345 aIt.Initialize (myLoops);
346 for (; aIt.More(); aIt.Next()) {
347 const TopoDS_Shape& aS=aIt.Value();
349 for (; aItS.More(); aItS.Next()) {
350 const TopoDS_Shape& aF=aItS.Value();
355 // b. collect all edges that are to avoid
356 aItM.Initialize(myShapesToAvoid);
357 for (; aItM.More(); aItM.Next()) {
358 const TopoDS_Shape& aF=aItM.Key();
362 // c. add all edges that are not processed to myShapesToAvoid
363 aIt.Initialize (myShapes);
364 for (; aIt.More(); aIt.Next()) {
365 const TopoDS_Shape& aF=aIt.Value();
366 if (!aMP.Contains(aF)) {
367 myShapesToAvoid.Add(aF);
370 //=================================================
373 myLoopsInternal.Clear();
376 AddedFacesMap.Clear();
378 aNbFA=myShapesToAvoid.Extent();
380 aItM.Initialize(myShapesToAvoid);
381 for (; aItM.More(); aItM.Next()) {
382 const TopoDS_Shape& aFF=aItM.Key();
383 BOPTools::MapShapesAndAncestors(aFF,
384 TopAbs_EDGE, TopAbs_FACE,
388 aItM.Initialize(myShapesToAvoid);
389 for (; aItM.More(); aItM.Next()) {
390 const TopoDS_Shape& aFF=aItM.Key();
391 if (!AddedFacesMap.Add(aFF)) {
397 aBB.MakeShell(aShell);
398 aBB.Add(aShell, aFF);
400 TopoDS_Iterator aItAddedF (aShell);
401 for (; aItAddedF.More(); aItAddedF.Next()) {
402 const TopoDS_Face& aF = (*(TopoDS_Face*)(&aItAddedF.Value()));
404 TopExp_Explorer aEdgeExp(aF, TopAbs_EDGE);
405 for (; aEdgeExp.More(); aEdgeExp.Next()) {
406 const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aEdgeExp.Current()));
407 const BOPCol_ListOfShape& aLF=aEFMap.FindFromKey(aE);
409 for (; aIt.More(); aIt.Next()) {
410 const TopoDS_Face& aFL=(*(TopoDS_Face*)(&aIt.Value()));
411 if (AddedFacesMap.Add(aFL)){
412 aBB.Add(aShell, aFL);
417 myLoopsInternal.Append(aShell);
420 //=======================================================================
421 //function : PerformAreas
423 //=======================================================================
424 void BOPAlgo_BuilderSolid::PerformAreas()
426 Standard_Boolean bIsGrowth, bIsHole;
427 Standard_Integer k,aNbHoles;
429 BOPCol_ListIteratorOfListOfShape aItLS;
430 BOPCol_ListOfShape aNewSolids, aHoleShells;
431 BOPCol_DataMapOfShapeShape aInOutMap;
432 BOPCol_IndexedMapOfShape aMHF;
433 BOPCol_ListIteratorOfListOfInteger aItLI;
434 BOPCol_BoxBndTreeSelector aSelector;
435 BOPCol_BoxBndTree aBBTree;
436 NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
437 BOPAlgo_DataMapOfIntegerBSSB aDMISB(100);
438 BOPAlgo_DataMapIteratorOfDataMapOfIntegerBSSB aItDMISB;
439 BOPCol_DataMapOfShapeListOfShape aMSH;
440 BOPCol_DataMapIteratorOfDataMapOfShapeShape aItDMSS;
441 BOPCol_DataMapIteratorOfDataMapOfShapeListOfShape aItMSH;
447 // Draft solids [aNewSolids]
448 aItLS.Initialize(myLoops);
449 for (k=0; aItLS.More(); aItLS.Next(), ++k) {
452 BOPAlgo_BuilderSolid_ShapeBox aSB;
454 const TopoDS_Shape& aShell = aItLS.Value();
455 aSB.SetShape(aShell);
457 BRepBndLib::Add(aShell, aBox);
458 bIsHole=Standard_False;
460 bIsGrowth=IsGrowthShell(aShell, aMHF);
462 // make a growth solid from a shell
463 aBB.MakeSolid(aSolid);
464 aBB.Add (aSolid, aShell);
466 aNewSolids.Append (aSolid);
467 aSB.SetShape(aSolid);
470 // check if a shell is a hole
471 bIsHole=IsHole(aShell, myContext);
473 aHoleShells.Append(aShell);
474 BOPTools::MapShapes(aShell, TopAbs_FACE, aMHF);
475 aSB.SetShape(aShell);
478 // make a growth solid from a shell
479 aBB.MakeSolid(aSolid);
480 aBB.Add (aSolid, aShell);
482 aNewSolids.Append (aSolid);
483 aSB.SetShape(aSolid);
488 aSB.SetIsHole(bIsHole);
492 // 2. Prepare TreeFiller
493 aItDMISB.Initialize(aDMISB);
494 for (; aItDMISB.More(); aItDMISB.Next()) {
496 const BOPAlgo_BuilderSolid_ShapeBox& aSB=aItDMISB.Value();
498 bIsHole=aSB.IsHole();
500 const Bnd_Box& aBox=aSB.Box();
501 aTreeFiller.Add(k, aBox);
505 // 3. Shake TreeFiller
508 // 4. Find outer growth shell that is most close
509 // to each hole shell
510 aItDMISB.Initialize(aDMISB);
511 for (; aItDMISB.More(); aItDMISB.Next()) {
513 const BOPAlgo_BuilderSolid_ShapeBox& aSB=aItDMISB.Value();
514 bIsHole=aSB.IsHole();
519 const TopoDS_Shape aSolid=aSB.Shape();
520 const Bnd_Box& aBoxSolid=aSB.Box();
523 aSelector.SetBox(aBoxSolid);
525 aNbHoles=aBBTree.Select(aSelector);
527 const BOPCol_ListOfInteger& aLI=aSelector.Indices();
529 aItLI.Initialize(aLI);
530 for (; aItLI.More(); aItLI.Next()) {
532 const BOPAlgo_BuilderSolid_ShapeBox& aSBk=aDMISB.Find(k);
533 const TopoDS_Shape& aHole=aSBk.Shape();
535 if (!IsInside(aHole, aSolid, myContext)){
539 if (aInOutMap.IsBound (aHole)){
540 const TopoDS_Shape& aHole2=aInOutMap(aHole);
541 if (IsInside(aHole, aHole2, myContext)) {
542 aInOutMap.UnBind(aHole);
543 aInOutMap.Bind (aHole, aSolid);
547 aInOutMap.Bind(aHole, aSolid);
550 }//for (; aItDMISB.More(); aItDMISB.Next()) {
552 // 5. Map [Solid/Holes] -> aMSH
553 aItDMSS.Initialize(aInOutMap);
554 for (; aItDMSS.More(); aItDMSS.Next()) {
555 const TopoDS_Shape& aHole=aItDMSS.Key();
556 const TopoDS_Shape& aSolid=aItDMSS.Value();
558 if (aMSH.IsBound(aSolid)) {
559 BOPCol_ListOfShape& aLH=aMSH.ChangeFind(aSolid);
563 BOPCol_ListOfShape aLH;
565 aMSH.Bind(aSolid, aLH);
569 // 6. Add aHoles to Solids
570 aItMSH.Initialize(aMSH);
571 for (; aItMSH.More(); aItMSH.Next()) {
572 TopoDS_Solid aSolid=(*(TopoDS_Solid*)(&aItMSH.Key()));
574 const BOPCol_ListOfShape& aLH=aItMSH.Value();
575 aItLS.Initialize(aLH);
576 for (; aItLS.More(); aItLS.Next()) {
577 const TopoDS_Shape& aHole = aItLS.Value();
578 aBB.Add (aSolid, aHole);
582 BRepClass3d_SolidClassifier& aSC=
583 myContext->SolidClassifier(aSolid);
588 // 7. These aNewSolids are draft solids that
589 // do not contain any internal shapes
590 aItLS.Initialize(aNewSolids);
591 for ( ; aItLS.More(); aItLS.Next()) {
592 const TopoDS_Shape& aSx=aItLS.Value();
595 // Add holes that outside the solids to myAreas
596 aItLS.Initialize(aHoleShells);
597 for (; aItLS.More(); aItLS.Next()) {
598 const TopoDS_Shape& aHole = aItLS.Value();
599 if (!aInOutMap.IsBound(aHole)){
602 aBB.MakeSolid(aSolid);
603 aBB.Add (aSolid, aHole);
605 myAreas.Append(aSolid);
609 //=======================================================================
610 //function : PerformInternalShapes
612 //=======================================================================
613 void BOPAlgo_BuilderSolid::PerformInternalShapes()
617 Standard_Integer aNbFI=myLoopsInternal.Extent();
618 if (!aNbFI) {// nothing to do
624 BOPCol_ListIteratorOfListOfShape aShellIt, aSolidIt;
625 BOPCol_MapIteratorOfMapOfShape aItMF;
627 BOPCol_MapOfShape aMF, aMFP, aMFx;
628 BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
629 BOPCol_ListOfShape aLSI;
631 // 1. All internal faces
632 aShellIt.Initialize(myLoopsInternal);
633 for (; aShellIt.More(); aShellIt.Next()) {
634 const TopoDS_Shape& aShell=aShellIt.Value();
635 aIt.Initialize(aShell);
636 for (; aIt.More(); aIt.Next()) {
637 const TopoDS_Shape& aF=aIt.Value();
644 aSolidIt.Initialize(myAreas);
645 for ( ; aSolidIt.More(); aSolidIt.Next()) {
646 TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aSolidIt.Value()));
648 TopExp_Explorer anExpSol(aSolid, TopAbs_FACE);;
649 for (; anExpSol.More(); anExpSol.Next()) {
650 const TopoDS_Shape& aF = anExpSol.Current();
653 aFF.Orientation(TopAbs_FORWARD);
655 aFF.Orientation(TopAbs_REVERSED);
659 BOPTools::MapShapesAndAncestors(aSolid,
660 TopAbs_EDGE, TopAbs_FACE,
663 // 2.1 Separate faces to process aMFP
665 aItMF.Initialize(aMF);
666 for (; aItMF.More(); aItMF.Next()) {
667 const TopoDS_Face& aF=(*(TopoDS_Face*)(&aItMF.Key()));
668 if (!aMFx.Contains(aF)) {
669 if (BOPTools_AlgoTools::IsInternalFace(aF,
680 // 2.2 Make Internal Shells
682 MakeInternalShells(aMFP, aLSI);
684 // 2.3 Add them to aSolid
685 aShellIt.Initialize(aLSI);
686 for (; aShellIt.More(); aShellIt.Next()) {
687 const TopoDS_Shape& aSI=aShellIt.Value();
688 aBB.Add (aSolid, aSI);
691 // 2.4 Remove faces aMFP from aMF
692 aItMF.Initialize(aMFP);
693 for (; aItMF.More(); aItMF.Next()) {
694 const TopoDS_Shape& aF=aItMF.Key();
702 } //for ( ; aSolidIt.More(); aSolidIt.Next()) {
705 aBB.MakeSolid(aSolid);
707 MakeInternalShells(aMF, aLSI);
708 aShellIt.Initialize(aLSI);
709 for (; aShellIt.More(); aShellIt.Next()) {
710 const TopoDS_Shape& aSI=aShellIt.Value();
711 aBB.Add (aSolid, aSI);
713 myAreas.Append(aSolid);
717 //=======================================================================
718 //function : MakeInternalShells
720 //=======================================================================
721 void MakeInternalShells(const BOPCol_MapOfShape& theMF,
722 BOPCol_ListOfShape& theShells)
724 BOPCol_ListIteratorOfListOfShape aItF;
727 BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
728 BOPCol_MapIteratorOfMapOfShape aItM;
729 BOPCol_MapOfShape aAddedFacesMap;
731 aItM.Initialize(theMF);
732 for (; aItM.More(); aItM.Next()) {
733 const TopoDS_Shape& aF=aItM.Key();
734 BOPTools::MapShapesAndAncestors(aF,
735 TopAbs_EDGE, TopAbs_FACE,
739 aItM.Initialize(theMF);
740 for (; aItM.More(); aItM.Next()) {
741 TopoDS_Shape aFF=aItM.Key();
742 if (!aAddedFacesMap.Add(aFF)) {
748 aBB.MakeShell(aShell);
749 aFF.Orientation(TopAbs_INTERNAL);
750 aBB.Add(aShell, aFF);
752 TopoDS_Iterator aItAddedF (aShell);
753 for (; aItAddedF.More(); aItAddedF.Next()) {
754 const TopoDS_Shape& aF =aItAddedF.Value();
756 TopExp_Explorer aEdgeExp(aF, TopAbs_EDGE);
757 for (; aEdgeExp.More(); aEdgeExp.Next()) {
758 const TopoDS_Shape& aE =aEdgeExp.Current();
759 const BOPCol_ListOfShape& aLF=aMEF.FindFromKey(aE);
760 aItF.Initialize(aLF);
761 for (; aItF.More(); aItF.Next()) {
762 TopoDS_Shape aFL=aItF.Value();
763 if (aAddedFacesMap.Add(aFL)){
764 aFL.Orientation(TopAbs_INTERNAL);
765 aBB.Add(aShell, aFL);
770 theShells.Append(aShell);
773 //=======================================================================
776 //=======================================================================
777 Standard_Boolean IsHole(const TopoDS_Shape& theS2,
778 Handle(BOPInt_Context)& theContext)
780 TopoDS_Solid *pS2=(TopoDS_Solid *)&theS2;
781 BRepClass3d_SolidClassifier& aClsf=theContext->SolidClassifier(*pS2);
783 aClsf.PerformInfinitePoint(::RealSmall());
785 return (aClsf.State()==TopAbs_IN);
787 //=======================================================================
788 //function : IsInside
790 //=======================================================================
791 Standard_Boolean IsInside(const TopoDS_Shape& theS1,
792 const TopoDS_Shape& theS2,
793 Handle(BOPInt_Context)& theContext)
795 TopExp_Explorer aExp;
798 TopoDS_Solid *pS2=(TopoDS_Solid *)&theS2;
800 aExp.Init(theS1, TopAbs_FACE);
802 BRepClass3d_SolidClassifier& aClsf=theContext->SolidClassifier(*pS2);
803 aClsf.PerformInfinitePoint(::RealSmall());
804 aState=aClsf.State();
807 BOPCol_IndexedMapOfShape aBounds;
808 BOPTools::MapShapes(*pS2, TopAbs_EDGE, aBounds);
809 const TopoDS_Face& aF = (*(TopoDS_Face*)(&aExp.Current()));
810 aState=BOPTools_AlgoTools::ComputeState(aF, *pS2, 1.e-14,
811 aBounds, theContext);
813 return (aState==TopAbs_IN);
815 //=======================================================================
816 //function : IsGrowthShell
818 //=======================================================================
819 Standard_Boolean IsGrowthShell(const TopoDS_Shape& theShell,
820 const BOPCol_IndexedMapOfShape& theMHF)
822 Standard_Boolean bRet;
826 if (theMHF.Extent()) {
827 aIt.Initialize(theShell);
828 for(; aIt.More(); aIt.Next()) {
829 const TopoDS_Shape& aF=aIt.Value();
830 if (theMHF.Contains(aF)) {