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_BOP.hxx>
17 #include <BOPAlgo_BuilderSolid.hxx>
18 #include <BOPAlgo_PaveFiller.hxx>
19 #include <BOPCol_DataMapOfShapeShape.hxx>
20 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
21 #include <BOPCol_IndexedMapOfShape.hxx>
22 #include <BOPCol_ListOfShape.hxx>
23 #include <BOPCol_MapOfShape.hxx>
24 #include <BOPDS_DS.hxx>
25 #include <BOPTools.hxx>
26 #include <BOPTools_AlgoTools.hxx>
27 #include <BOPTools_AlgoTools3D.hxx>
28 #include <BOPTools_Set.hxx>
29 #include <BOPTools_SetMapHasher.hxx>
30 #include <BRep_Builder.hxx>
31 #include <BRep_Tool.hxx>
32 #include <NCollection_DataMap.hxx>
33 #include <NCollection_IncAllocator.hxx>
34 #include <TopAbs_ShapeEnum.hxx>
35 #include <TopExp_Explorer.hxx>
36 #include <TopoDS_Compound.hxx>
37 #include <TopoDS_Edge.hxx>
38 #include <TopoDS_Iterator.hxx>
39 #include <TopoDS_Shape.hxx>
40 #include <TopTools_ListIteratorOfListOfShape.hxx>
43 typedef NCollection_DataMap
46 BOPTools_SetMapHasher> BOPTools_DataMapOfSetShape;
48 typedef BOPTools_DataMapOfSetShape::Iterator
49 BOPTools_DataMapIteratorOfDataMapOfSetShape;
52 TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim);
55 //=======================================================================
58 //=======================================================================
59 BOPAlgo_BOP::BOPAlgo_BOP()
63 myMapTools(100, myAllocator)
67 //=======================================================================
70 //=======================================================================
71 BOPAlgo_BOP::BOPAlgo_BOP
72 (const Handle(NCollection_BaseAllocator)& theAllocator)
74 BOPAlgo_Builder(theAllocator),
76 myMapTools(100, myAllocator)
80 //=======================================================================
83 //=======================================================================
84 BOPAlgo_BOP::~BOPAlgo_BOP()
87 //=======================================================================
90 //=======================================================================
91 void BOPAlgo_BOP::Clear()
93 myOperation=BOPAlgo_UNKNOWN;
99 BOPAlgo_Builder::Clear();
101 //=======================================================================
102 //function : SetOperation
104 //=======================================================================
105 void BOPAlgo_BOP::SetOperation(const BOPAlgo_Operation theOperation)
107 myOperation=theOperation;
109 //=======================================================================
110 //function : Operation
112 //=======================================================================
113 BOPAlgo_Operation BOPAlgo_BOP::Operation()const
117 //=======================================================================
120 //=======================================================================
121 void BOPAlgo_BOP::AddTool(const TopoDS_Shape& theShape)
123 if (myMapTools.Add(theShape)) {
124 myTools.Append(theShape);
127 //=======================================================================
128 //function : SetTools
130 //=======================================================================
131 void BOPAlgo_BOP::SetTools(const BOPCol_ListOfShape& theShapes)
133 BOPCol_ListIteratorOfListOfShape aIt;
136 aIt.Initialize(theShapes);
137 for (; aIt.More(); aIt.Next()) {
138 const TopoDS_Shape& aS = aIt.Value();
142 //=======================================================================
143 //function : CheckData
145 //=======================================================================
146 void BOPAlgo_BOP::CheckData()
148 Standard_Integer i, j, iDim, aNbArgs, aNbTools;
149 Standard_Boolean bFlag;
150 BOPCol_ListIteratorOfListOfShape aItLS;
154 if (!(myOperation==BOPAlgo_COMMON ||
155 myOperation==BOPAlgo_FUSE ||
156 myOperation==BOPAlgo_CUT||
157 myOperation==BOPAlgo_CUT21)) {
158 // non-licit operation
163 aNbArgs=myArguments.Extent();
165 // invalid number of Arguments
170 aNbTools=myTools.Extent();
172 // invalid number of Tools
182 myErrorStatus=myPaveFiller->ErrorStatus();
190 for (i=0; i<2; ++i) {
191 const BOPCol_ListOfShape& aLS=(!i)? myArguments : myTools;
192 aItLS.Initialize(aLS);
193 for (j=0; aItLS.More(); aItLS.Next(), ++j) {
194 const TopoDS_Shape& aS=aItLS.Value();
195 bFlag=BOPTools_AlgoTools3D::IsEmptyShape(aS);
200 iDim=BOPTools_AlgoTools::Dimension(aS);
202 // non-homogenious argument
212 if (iDim!=myDims[i]) {
213 // non-homogenious argument
220 if (myDims[0]<myDims[1]) {
221 if (myOperation==BOPAlgo_FUSE ||
222 myOperation==BOPAlgo_CUT21) {
223 // non-licit operation for the arguments
228 else if (myDims[0]>myDims[1]) {
229 if (myOperation==BOPAlgo_FUSE ||
230 myOperation==BOPAlgo_CUT) {
231 // non-licit operation for the arguments
237 //=======================================================================
240 //=======================================================================
241 void BOPAlgo_BOP::Prepare()
244 BOPAlgo_Builder::Prepare();
246 if(myWarningStatus == 2) {
249 BOPCol_ListIteratorOfListOfShape aItLS;
251 switch(myOperation) {
253 for (i=0; i<2; ++i) {
254 const BOPCol_ListOfShape& aLS=(!i)? myArguments : myTools;
255 aItLS.Initialize(aLS);
256 for (; aItLS.More(); aItLS.Next()) {
257 const TopoDS_Shape& aS=aItLS.Value();
258 aBB.Add(myShape, aS);
265 aItLS.Initialize(myArguments);
266 for (; aItLS.More(); aItLS.Next()) {
267 const TopoDS_Shape& aS=aItLS.Value();
268 if(!BOPTools_AlgoTools3D::IsEmptyShape(aS)) {
269 aBB.Add(myShape, aS);
275 case BOPAlgo_CUT21: {
276 aItLS.Initialize(myTools);
277 for (; aItLS.More(); aItLS.Next()) {
278 const TopoDS_Shape& aS=aItLS.Value();
279 if(!BOPTools_AlgoTools3D::IsEmptyShape(aS)) {
280 aBB.Add(myShape, aS);
291 //=======================================================================
292 //function : BuildResult
294 //=======================================================================
295 void BOPAlgo_BOP::BuildResult(const TopAbs_ShapeEnum theType)
297 TopAbs_ShapeEnum aType;
299 BOPCol_MapOfShape aM;
300 BOPCol_ListIteratorOfListOfShape aIt, aItIm;
304 const BOPCol_ListOfShape& aLA=myDS->Arguments();
306 for (; aIt.More(); aIt.Next()) {
307 const TopoDS_Shape& aS=aIt.Value();
308 aType=aS.ShapeType();
309 if (aType==theType) {
310 if (myImages.IsBound(aS)){
311 const BOPCol_ListOfShape& aLSIm=myImages.Find(aS);
312 aItIm.Initialize(aLSIm);
313 for (; aItIm.More(); aItIm.Next()) {
314 const TopoDS_Shape& aSIm=aItIm.Value();
316 aBB.Add(myShape, aSIm);
322 aBB.Add(myShape, aS);
328 //=======================================================================
331 //=======================================================================
332 void BOPAlgo_BOP::Perform()
334 Handle(NCollection_BaseAllocator) aAllocator;
335 BOPAlgo_PaveFiller* pPF;
336 BOPCol_ListIteratorOfListOfShape aItLS;
340 if (myEntryPoint==1) {
347 aAllocator=new NCollection_IncAllocator;
348 BOPCol_ListOfShape aLS(aAllocator);
350 aItLS.Initialize(myArguments);
351 for (; aItLS.More(); aItLS.Next()) {
352 const TopoDS_Shape& aS=aItLS.Value();
356 aItLS.Initialize(myTools);
357 for (; aItLS.More(); aItLS.Next()) {
358 const TopoDS_Shape& aS=aItLS.Value();
362 pPF=new BOPAlgo_PaveFiller(aAllocator);
363 pPF->SetArguments(aLS);
364 pPF->SetRunParallel(myRunParallel);
365 pPF->SetProgressIndicator(myProgressIndicator);
366 pPF->SetFuzzyValue(myFuzzyValue);
371 PerformInternal(*pPF);
373 //=======================================================================
374 //function : PerformInternal1
376 //=======================================================================
377 void BOPAlgo_BOP::PerformInternal1(const BOPAlgo_PaveFiller& theFiller)
382 myPaveFiller=(BOPAlgo_PaveFiller*)&theFiller;
383 myDS=myPaveFiller->PDS();
384 myContext=myPaveFiller->Context();
388 if (myErrorStatus && !myWarningStatus) {
398 if(myWarningStatus == 2) {
403 FillImagesVertices();
408 BuildResult(TopAbs_VERTEX);
418 BuildResult(TopAbs_EDGE);
424 FillImagesContainers(TopAbs_WIRE);
429 BuildResult(TopAbs_WIRE);
440 BuildResult(TopAbs_FACE);
446 FillImagesContainers(TopAbs_SHELL);
451 BuildResult(TopAbs_SHELL);
462 BuildResult(TopAbs_SOLID);
468 FillImagesContainers(TopAbs_COMPSOLID);
473 BuildResult(TopAbs_COMPSOLID);
479 FillImagesCompounds();
484 BuildResult(TopAbs_COMPOUND);
501 //=======================================================================
504 //=======================================================================
505 void BOPAlgo_BOP::BuildRC()
507 Standard_Boolean bFlag1, bFlag2, bIsBound;
508 Standard_Integer aDmin;
509 TopAbs_ShapeEnum aTmin;
511 TopoDS_Shape aSAIm, aSTIm;
513 TopExp_Explorer aExp;
514 BOPCol_DataMapOfShapeShape aDMSSA;
515 BOPCol_ListIteratorOfListOfShape aItLS, aItIm;
516 Standard_Boolean bHasInterf;
518 BOPTools_DataMapOfSetShape aDMSTS;
522 aBB.MakeCompound(aC);
525 if (myOperation==BOPAlgo_FUSE) {
526 aTmin=TypeToExplore(myDims[0]);
527 aExp.Init(myShape, aTmin);
528 for (; aExp.More(); aExp.Next()) {
529 const TopoDS_Shape& aS=aExp.Current();
537 if (myDims[0] < myDims[1]) {
540 aTmin=TypeToExplore(aDmin);
542 // B. Common, Cut, Cut21
544 bFlag1=(myOperation==BOPAlgo_COMMON || myOperation==BOPAlgo_CUT21);
545 bFlag2=(myOperation==BOPAlgo_CUT || myOperation==BOPAlgo_CUT21);
547 const BOPCol_ListOfShape& aLA=( bFlag1) ? myArguments : myTools;
548 aItLS.Initialize(aLA);
549 for (; aItLS.More(); aItLS.Next()) {
550 const TopoDS_Shape& aSA=aItLS.Value();
552 if (myImages.IsBound(aSA)){
553 const BOPCol_ListOfShape& aLSAIm=myImages.Find(aSA);
554 aItIm.Initialize(aLSAIm);
555 for (; aItIm.More(); aItIm.Next()) {
556 const TopoDS_Shape& aSAIm=aItIm.Value();
557 aExp.Init(aSAIm, aTmin);
558 for (; aExp.More(); aExp.Next()) {
559 const TopoDS_Shape aSIm=aExp.Current();
560 aDMSSA.Bind(aSIm, aSIm);
566 aExp.Init(aSA, aTmin);
567 for (; aExp.More(); aExp.Next()) {
568 const TopoDS_Shape aSIm=aExp.Current();
569 aDMSSA.Bind(aSIm, aSIm);
570 if (aTmin==TopAbs_SOLID) {
571 iX=myDS->Index(aSIm);
572 bHasInterf=myDS->HasInterf(iX);
576 aST.Add(aSIm, TopAbs_FACE);
578 aDMSTS.Bind(aST, aSIm);
583 } //for (; aItLS.More(); aItLS.Next())
585 const BOPCol_ListOfShape& aLT=(!bFlag1) ? myArguments : myTools;
586 aItLS.Initialize(aLT);
587 for (; aItLS.More(); aItLS.Next()) {
588 const TopoDS_Shape& aST=aItLS.Value();
589 if (myImages.IsBound(aST)){
590 const BOPCol_ListOfShape& aLSTIm=myImages.Find(aST);
591 aItIm.Initialize(aLSTIm);
592 for (; aItIm.More(); aItIm.Next()) {
593 const TopoDS_Shape& aSTIm=aItIm.Value();
594 aExp.Init(aSTIm, aTmin);
595 for (; aExp.More(); aExp.Next()) {
596 const TopoDS_Shape aSIm=aExp.Current();
597 // skip degenerated edges
598 if (aTmin==TopAbs_EDGE) {
599 const TopoDS_Edge& aEIm=*((TopoDS_Edge*)&aSIm);
600 if (BRep_Tool::Degenerated(aEIm)) {
605 bIsBound=aDMSSA.IsBound(aSIm);
606 if (!bFlag2) { // ie common
608 const TopoDS_Shape& aSImA=aDMSSA.Find(aSIm);
612 else {// ie cut or cut21
619 }// if (myImages.IsBound(aST)){
621 aExp.Init(aST, aTmin);
622 for (; aExp.More(); aExp.Next()) {
623 const TopoDS_Shape aSIm=aExp.Current();
624 // skip degenerated edges
625 if (aTmin==TopAbs_EDGE) {
626 const TopoDS_Edge& aEIm=*((TopoDS_Edge*)&aSIm);
627 if (BRep_Tool::Degenerated(aEIm)) {
631 bIsBound=aDMSSA.IsBound(aSIm);
632 if (!bFlag2) { // ie common
634 const TopoDS_Shape& aSImA=aDMSSA.Find(aSIm);
638 if (aTmin==TopAbs_SOLID) {
641 aST.Add(aSIm, TopAbs_FACE);
643 if (aDMSTS.IsBound(aST)) {
644 const TopoDS_Shape& aSImA=aDMSTS.Find(aST);
650 else {// ie cut or cut21
652 if (aTmin==TopAbs_SOLID) {
655 aST.Add(aSIm, TopAbs_FACE);
657 bIsBound=aDMSTS.IsBound(aST);
667 } //for (; aItLS.More(); aItLS.Next())
669 // the squats around degeneracy
670 if (aTmin!=TopAbs_EDGE) {
674 //---------------------------------------------------------
676 // The squats around degenerated edges
677 Standard_Integer i, aNbS, nVD;
678 TopAbs_ShapeEnum aType;
679 BOPCol_IndexedMapOfShape aMVC;
682 BOPTools::MapShapes(aC, TopAbs_VERTEX, aMVC);
685 aNbS=myDS->NbSourceShapes();
686 for (i=0; i<aNbS; ++i) {
687 const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
688 aType=aSI.ShapeType();
693 const TopoDS_Edge& aE=*((TopoDS_Edge*)&aSI.Shape());
694 if (!BRep_Tool::Degenerated(aE)) {
698 nVD=aSI.SubShapes().First();
699 const TopoDS_Shape& aVD=myDS->Shape(nVD);
701 if (!aMVC.Contains(aVD)) {
705 if (myDS->IsNewShape(nVD)) {
709 if (myDS->HasInterf(nVD)) {
718 //=======================================================================
719 //function : BuildShape
721 //=======================================================================
722 void BOPAlgo_BOP::BuildShape()
724 Standard_Integer aDmin, aNbLCB;
725 TopAbs_ShapeEnum aT1, aT2, aTR;
726 TopoDS_Shape aR, aRC;
729 BOPCol_ListOfShape aLCB;
730 BOPCol_ListIteratorOfListOfShape aItLCB;
737 if (myDims[0]<myDims[1]) {
746 else if (aDmin==1 || aDmin==2) { //edges, faces
756 BOPTools_AlgoTools::MakeConnexityBlocks
757 (myRC, aT1, aT2, aLCB);
758 aNbLCB=aLCB.Extent();
764 BOPTools_AlgoTools::MakeContainer(TopAbs_COMPOUND, aRC);
766 aItLCB.Initialize(aLCB);
767 for (; aItLCB.More(); aItLCB.Next()) {
768 BOPTools_AlgoTools::MakeContainer(aTR, aR);
770 const TopoDS_Shape& aCB=aItLCB.Value();
772 for (; aIt.More(); aIt.Next()) {
773 const TopoDS_Shape& aS=aIt.Value();
777 if (aTR==TopAbs_SHELL) {
778 BOPTools_AlgoTools::OrientFacesOnShell(aR);
784 }// elase if (aDmin==1 || aDmin==2) {
787 Standard_Integer aNbObjs, aNbTools;
789 aNbObjs=myArguments.Extent();
790 aNbTools=myTools.Extent();
792 if (aNbObjs==1 && aNbTools==1) {
793 if (myOperation==BOPAlgo_FUSE) {
805 //=======================================================================
806 //function : BuildSolid
808 //=======================================================================
809 void BOPAlgo_BOP::BuildSolid()
811 Standard_Boolean bHasInterf, bHasSharedFaces;
812 Standard_Integer i, aNbF, aNbSx, iX, iErr, aNbZ;
813 TopAbs_Orientation aOr, aOr1;
817 TopExp_Explorer aExp;
818 BOPCol_IndexedMapOfShape aMFI;
819 BOPCol_IndexedDataMapOfShapeListOfShape aMFS, aMEF;
820 BOPCol_ListIteratorOfListOfShape aItLS;
821 BOPCol_ListOfShape aSFS;
822 BOPAlgo_BuilderSolid aSB;
823 BOPCol_MapOfShape aMSA, aMZ;
824 BOPTools_DataMapOfSetShape aDMSTS;
825 BOPTools_DataMapIteratorOfDataMapOfSetShape aItDMSTS;
829 // Map of of Solids of Arguments
830 for (i=0; i<2; ++i) {
831 const BOPCol_ListOfShape& aLSA=(i) ? myArguments : myTools;
832 aItLS.Initialize(aLSA);
833 for (; aItLS.More(); aItLS.Next()) {
834 const TopoDS_Shape& aSA=aItLS.Value();
835 aExp.Init(aSA, TopAbs_SOLID);
836 for (; aExp.More(); aExp.Next()) {
837 const TopoDS_Shape& aZA=aExp.Current();
840 BOPTools::MapShapesAndAncestors(aZA,
849 for (i=1; i<aNbF; ++i) {
850 //const TopoDS_Shape& aFA=aMFZA.FindKey(i);
851 const BOPCol_ListOfShape& aLZA=aMFS(i);
854 aItLS.Initialize(aLZA);
855 for(; aItLS.More(); aItLS.Next()) {
856 const TopoDS_Shape& aZA=aItLS.Value();
864 aIt.Initialize(myRC);
865 for (; aIt.More(); aIt.Next()) {
866 const TopoDS_Shape& aSx=aIt.Value();
867 if (aMSA.Contains(aSx)) {
869 bHasInterf=myDS->HasInterf(iX);
870 bHasSharedFaces=aMZ.Contains(aSx);
872 if (!bHasInterf && !bHasSharedFaces) {
873 // It means that the solid aSx will be added
874 // to the result as is.
875 // The solid aSx will not participate
876 // in creation of a new solid(s).
879 aST.Add(aSx, TopAbs_FACE);
881 if (!aDMSTS.IsBound(aST)) {
882 aDMSTS.Bind(aST, aSx);
889 aExp.Init(aSx, TopAbs_FACE);
890 for (; aExp.More(); aExp.Next()) {
891 const TopoDS_Shape& aFx=aExp.Current();
893 aOr=aFx.Orientation();
894 if (aOr==TopAbs_INTERNAL) {
899 if (!aMFS.Contains(aFx)) {
900 BOPCol_ListOfShape aLSx;
906 iX=aMFS.FindIndex(aFx);
907 const TopoDS_Shape& aFx1=aMFS.FindKey(iX);
908 aOr1=aFx1.Orientation();
910 BOPCol_ListOfShape& aLSx=aMFS.ChangeFromKey(aFx);
916 } // for (; aIt.More(); aIt.Next()) {
917 //faces that will be added in the end;
918 BOPCol_ListOfShape aLF, aLFx;
921 for (i=1; i<=aNbF; ++i) {
922 const TopoDS_Shape& aFx=aMFS.FindKey(i);
923 const BOPCol_ListOfShape& aLSx=aMFS(i);
926 BOPTools::MapShapesAndAncestors
927 (aFx,TopAbs_EDGE, TopAbs_FACE, aMEF);
928 if (IsBoundSplits(aFx, aMEF)){
936 aItLS.Initialize(aLF);
937 for(; aItLS.More(); aItLS.Next()) {
938 const TopoDS_Shape& aFx=aItLS.Value();
941 // add faces from aLFx to aSFS;
942 aItLS.Initialize(aLFx);
943 for (; aItLS.More(); aItLS.Next()) {
944 const TopoDS_Shape& aFx=aItLS.Value();
949 for (i=1; i<=aNbF; ++i) {
953 aFx.Orientation(TopAbs_FORWARD);
955 aFx.Orientation(TopAbs_REVERSED);
960 BOPTools_AlgoTools::MakeContainer(TopAbs_COMPOUND, aRC);
962 aSB.SetContext(myContext);
965 iErr=aSB.ErrorStatus();
967 myErrorStatus=30; // SolidBuilder failed
971 const BOPCol_ListOfShape& aLSR=aSB.Areas();
973 aItLS.Initialize(aLSR);
974 for (; aItLS.More(); aItLS.Next()) {
975 const TopoDS_Shape& aSR=aItLS.Value();
979 aItDMSTS.Initialize(aDMSTS);
980 for (; aItDMSTS.More(); aItDMSTS.Next()) {
981 const TopoDS_Shape& aSx=aItDMSTS.Value();
987 //=======================================================================
988 //function : IsBoundSplits
990 //=======================================================================
991 Standard_Boolean BOPAlgo_BOP::IsBoundSplits
992 (const TopoDS_Shape& aS,
993 BOPCol_IndexedDataMapOfShapeListOfShape& aMEF)
995 Standard_Boolean bRet = Standard_False;
996 if (mySplits.IsBound(aS) || myOrigins.IsBound(aS)) {
1000 BOPCol_ListIteratorOfListOfShape aIt;
1001 Standard_Integer aNbLS;
1002 TopAbs_Orientation anOr;
1004 //check face aF may be connected to face from mySplits
1005 TopExp_Explorer aExp(aS, TopAbs_EDGE);
1006 for (; aExp.More(); aExp.Next()) {
1007 const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aExp.Current()));
1009 anOr = aE.Orientation();
1010 if (anOr==TopAbs_INTERNAL) {
1014 if (BRep_Tool::Degenerated(aE)) {
1018 const BOPCol_ListOfShape& aLS=aMEF.FindFromKey(aE);
1019 aNbLS = aLS.Extent();
1024 aIt.Initialize(aLS);
1025 for (; aIt.More(); aIt.Next()) {
1026 const TopoDS_Shape& aSx = aIt.Value();
1027 if (mySplits.IsBound(aSx) || myOrigins.IsBound(aS)) {
1035 //=======================================================================
1036 //function : TypeToExplore
1038 //=======================================================================
1039 TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim)
1041 TopAbs_ShapeEnum aRet;