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>
42 typedef NCollection_IndexedDataMap
45 BOPTools_SetMapHasher> BOPTools_IndexedDataMapOfSetShape;
48 TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim);
51 //=======================================================================
54 //=======================================================================
55 BOPAlgo_BOP::BOPAlgo_BOP()
59 myMapTools(100, myAllocator)
63 //=======================================================================
66 //=======================================================================
67 BOPAlgo_BOP::BOPAlgo_BOP
68 (const Handle(NCollection_BaseAllocator)& theAllocator)
70 BOPAlgo_Builder(theAllocator),
72 myMapTools(100, myAllocator)
76 //=======================================================================
79 //=======================================================================
80 BOPAlgo_BOP::~BOPAlgo_BOP()
83 //=======================================================================
86 //=======================================================================
87 void BOPAlgo_BOP::Clear()
89 myOperation=BOPAlgo_UNKNOWN;
95 BOPAlgo_Builder::Clear();
97 //=======================================================================
98 //function : SetOperation
100 //=======================================================================
101 void BOPAlgo_BOP::SetOperation(const BOPAlgo_Operation theOperation)
103 myOperation=theOperation;
105 //=======================================================================
106 //function : Operation
108 //=======================================================================
109 BOPAlgo_Operation BOPAlgo_BOP::Operation()const
113 //=======================================================================
116 //=======================================================================
117 void BOPAlgo_BOP::AddTool(const TopoDS_Shape& theShape)
119 if (myMapTools.Add(theShape)) {
120 myTools.Append(theShape);
123 //=======================================================================
124 //function : SetTools
126 //=======================================================================
127 void BOPAlgo_BOP::SetTools(const BOPCol_ListOfShape& theShapes)
129 BOPCol_ListIteratorOfListOfShape aIt;
132 aIt.Initialize(theShapes);
133 for (; aIt.More(); aIt.Next()) {
134 const TopoDS_Shape& aS = aIt.Value();
138 //=======================================================================
139 //function : CheckData
141 //=======================================================================
142 void BOPAlgo_BOP::CheckData()
144 Standard_Integer i, j, iDim, aNbArgs, aNbTools;
145 Standard_Boolean bFlag;
146 BOPCol_ListIteratorOfListOfShape aItLS;
150 if (!(myOperation==BOPAlgo_COMMON ||
151 myOperation==BOPAlgo_FUSE ||
152 myOperation==BOPAlgo_CUT||
153 myOperation==BOPAlgo_CUT21)) {
154 // non-licit operation
159 aNbArgs=myArguments.Extent();
161 // invalid number of Arguments
166 aNbTools=myTools.Extent();
168 // invalid number of Tools
178 myErrorStatus=myPaveFiller->ErrorStatus();
186 for (i=0; i<2; ++i) {
187 const BOPCol_ListOfShape& aLS=(!i)? myArguments : myTools;
188 aItLS.Initialize(aLS);
189 for (j=0; aItLS.More(); aItLS.Next(), ++j) {
190 const TopoDS_Shape& aS=aItLS.Value();
191 bFlag=BOPTools_AlgoTools3D::IsEmptyShape(aS);
196 iDim=BOPTools_AlgoTools::Dimension(aS);
198 // non-homogenious argument
208 if (iDim!=myDims[i]) {
209 // non-homogenious argument
216 if (myDims[0]<myDims[1]) {
217 if (myOperation==BOPAlgo_FUSE ||
218 myOperation==BOPAlgo_CUT21) {
219 // non-licit operation for the arguments
224 else if (myDims[0]>myDims[1]) {
225 if (myOperation==BOPAlgo_FUSE ||
226 myOperation==BOPAlgo_CUT) {
227 // non-licit operation for the arguments
233 //=======================================================================
236 //=======================================================================
237 void BOPAlgo_BOP::Prepare()
240 BOPAlgo_Builder::Prepare();
242 if(myWarningStatus == 2) {
245 BOPCol_ListIteratorOfListOfShape aItLS;
247 switch(myOperation) {
249 for (i=0; i<2; ++i) {
250 const BOPCol_ListOfShape& aLS=(!i)? myArguments : myTools;
251 aItLS.Initialize(aLS);
252 for (; aItLS.More(); aItLS.Next()) {
253 const TopoDS_Shape& aS=aItLS.Value();
254 aBB.Add(myShape, aS);
261 aItLS.Initialize(myArguments);
262 for (; aItLS.More(); aItLS.Next()) {
263 const TopoDS_Shape& aS=aItLS.Value();
264 if(!BOPTools_AlgoTools3D::IsEmptyShape(aS)) {
265 aBB.Add(myShape, aS);
271 case BOPAlgo_CUT21: {
272 aItLS.Initialize(myTools);
273 for (; aItLS.More(); aItLS.Next()) {
274 const TopoDS_Shape& aS=aItLS.Value();
275 if(!BOPTools_AlgoTools3D::IsEmptyShape(aS)) {
276 aBB.Add(myShape, aS);
287 //=======================================================================
288 //function : BuildResult
290 //=======================================================================
291 void BOPAlgo_BOP::BuildResult(const TopAbs_ShapeEnum theType)
293 TopAbs_ShapeEnum aType;
295 BOPCol_MapOfShape aM;
296 BOPCol_ListIteratorOfListOfShape aIt, aItIm;
300 const BOPCol_ListOfShape& aLA=myDS->Arguments();
302 for (; aIt.More(); aIt.Next()) {
303 const TopoDS_Shape& aS=aIt.Value();
304 aType=aS.ShapeType();
305 if (aType==theType) {
306 if (myImages.IsBound(aS)){
307 const BOPCol_ListOfShape& aLSIm=myImages.Find(aS);
308 aItIm.Initialize(aLSIm);
309 for (; aItIm.More(); aItIm.Next()) {
310 const TopoDS_Shape& aSIm=aItIm.Value();
312 aBB.Add(myShape, aSIm);
318 aBB.Add(myShape, aS);
324 //=======================================================================
327 //=======================================================================
328 void BOPAlgo_BOP::Perform()
330 Handle(NCollection_BaseAllocator) aAllocator;
331 BOPAlgo_PaveFiller* pPF;
332 BOPCol_ListIteratorOfListOfShape aItLS;
336 if (myEntryPoint==1) {
343 aAllocator=new NCollection_IncAllocator;
344 BOPCol_ListOfShape aLS(aAllocator);
346 aItLS.Initialize(myArguments);
347 for (; aItLS.More(); aItLS.Next()) {
348 const TopoDS_Shape& aS=aItLS.Value();
352 aItLS.Initialize(myTools);
353 for (; aItLS.More(); aItLS.Next()) {
354 const TopoDS_Shape& aS=aItLS.Value();
358 pPF=new BOPAlgo_PaveFiller(aAllocator);
359 pPF->SetArguments(aLS);
360 pPF->SetRunParallel(myRunParallel);
361 pPF->SetProgressIndicator(myProgressIndicator);
362 pPF->SetFuzzyValue(myFuzzyValue);
367 PerformInternal(*pPF);
369 //=======================================================================
370 //function : PerformInternal1
372 //=======================================================================
373 void BOPAlgo_BOP::PerformInternal1(const BOPAlgo_PaveFiller& theFiller)
378 myPaveFiller=(BOPAlgo_PaveFiller*)&theFiller;
379 myDS=myPaveFiller->PDS();
380 myContext=myPaveFiller->Context();
384 if (myErrorStatus && !myWarningStatus) {
394 if(myWarningStatus == 2) {
399 FillImagesVertices();
404 BuildResult(TopAbs_VERTEX);
414 BuildResult(TopAbs_EDGE);
420 FillImagesContainers(TopAbs_WIRE);
425 BuildResult(TopAbs_WIRE);
436 BuildResult(TopAbs_FACE);
442 FillImagesContainers(TopAbs_SHELL);
447 BuildResult(TopAbs_SHELL);
458 BuildResult(TopAbs_SOLID);
464 FillImagesContainers(TopAbs_COMPSOLID);
469 BuildResult(TopAbs_COMPSOLID);
475 FillImagesCompounds();
480 BuildResult(TopAbs_COMPOUND);
497 //=======================================================================
500 //=======================================================================
501 void BOPAlgo_BOP::BuildRC()
503 Standard_Boolean bFlag1, bFlag2, bIsBound;
504 Standard_Integer aDmin;
505 TopAbs_ShapeEnum aTmin;
507 TopoDS_Shape aSAIm, aSTIm;
509 TopExp_Explorer aExp;
510 BOPCol_DataMapOfShapeShape aDMSSA;
511 BOPCol_ListIteratorOfListOfShape aItLS, aItIm;
512 Standard_Boolean bHasInterf;
514 BOPTools_IndexedDataMapOfSetShape aDMSTS;
518 aBB.MakeCompound(aC);
521 if (myOperation==BOPAlgo_FUSE) {
522 aTmin=TypeToExplore(myDims[0]);
523 aExp.Init(myShape, aTmin);
524 for (; aExp.More(); aExp.Next()) {
525 const TopoDS_Shape& aS=aExp.Current();
533 if (myDims[0] < myDims[1]) {
536 aTmin=TypeToExplore(aDmin);
538 // B. Common, Cut, Cut21
540 bFlag1=(myOperation==BOPAlgo_COMMON || myOperation==BOPAlgo_CUT21);
541 bFlag2=(myOperation==BOPAlgo_CUT || myOperation==BOPAlgo_CUT21);
543 const BOPCol_ListOfShape& aLA=( bFlag1) ? myArguments : myTools;
544 aItLS.Initialize(aLA);
545 for (; aItLS.More(); aItLS.Next()) {
546 const TopoDS_Shape& aSA=aItLS.Value();
548 if (myImages.IsBound(aSA)){
549 const BOPCol_ListOfShape& aLSAIm=myImages.Find(aSA);
550 aItIm.Initialize(aLSAIm);
551 for (; aItIm.More(); aItIm.Next()) {
552 const TopoDS_Shape& aSAIm=aItIm.Value();
553 aExp.Init(aSAIm, aTmin);
554 for (; aExp.More(); aExp.Next()) {
555 const TopoDS_Shape aSIm=aExp.Current();
556 aDMSSA.Bind(aSIm, aSIm);
562 aExp.Init(aSA, aTmin);
563 for (; aExp.More(); aExp.Next()) {
564 const TopoDS_Shape aSIm=aExp.Current();
565 aDMSSA.Bind(aSIm, aSIm);
566 if (aTmin==TopAbs_SOLID) {
567 iX=myDS->Index(aSIm);
568 bHasInterf=myDS->HasInterf(iX);
572 aST.Add(aSIm, TopAbs_FACE);
574 aDMSTS.Add(aST, aSIm);
579 } //for (; aItLS.More(); aItLS.Next())
581 const BOPCol_ListOfShape& aLT=(!bFlag1) ? myArguments : myTools;
582 aItLS.Initialize(aLT);
583 for (; aItLS.More(); aItLS.Next()) {
584 const TopoDS_Shape& aST=aItLS.Value();
585 if (myImages.IsBound(aST)){
586 const BOPCol_ListOfShape& aLSTIm=myImages.Find(aST);
587 aItIm.Initialize(aLSTIm);
588 for (; aItIm.More(); aItIm.Next()) {
589 const TopoDS_Shape& aSTIm=aItIm.Value();
590 aExp.Init(aSTIm, aTmin);
591 for (; aExp.More(); aExp.Next()) {
592 const TopoDS_Shape aSIm=aExp.Current();
593 // skip degenerated edges
594 if (aTmin==TopAbs_EDGE) {
595 const TopoDS_Edge& aEIm=*((TopoDS_Edge*)&aSIm);
596 if (BRep_Tool::Degenerated(aEIm)) {
601 bIsBound=aDMSSA.IsBound(aSIm);
602 if (!bFlag2) { // ie common
604 const TopoDS_Shape& aSImA=aDMSSA.Find(aSIm);
608 else {// ie cut or cut21
615 }// if (myImages.IsBound(aST)){
617 aExp.Init(aST, aTmin);
618 for (; aExp.More(); aExp.Next()) {
619 const TopoDS_Shape aSIm=aExp.Current();
620 // skip degenerated edges
621 if (aTmin==TopAbs_EDGE) {
622 const TopoDS_Edge& aEIm=*((TopoDS_Edge*)&aSIm);
623 if (BRep_Tool::Degenerated(aEIm)) {
627 bIsBound=aDMSSA.IsBound(aSIm);
628 if (!bFlag2) { // ie common
630 const TopoDS_Shape& aSImA=aDMSSA.Find(aSIm);
634 if (aTmin==TopAbs_SOLID) {
637 aST.Add(aSIm, TopAbs_FACE);
639 if (aDMSTS.Contains(aST)) {
640 const TopoDS_Shape& aSImA=aDMSTS.FindFromKey(aST);
646 else {// ie cut or cut21
648 if (aTmin==TopAbs_SOLID) {
651 aST.Add(aSIm, TopAbs_FACE);
653 bIsBound=aDMSTS.Contains(aST);
663 } //for (; aItLS.More(); aItLS.Next())
665 // the squats around degeneracy
666 if (aTmin!=TopAbs_EDGE) {
670 //---------------------------------------------------------
672 // The squats around degenerated edges
673 Standard_Integer i, aNbS, nVD;
674 TopAbs_ShapeEnum aType;
675 BOPCol_IndexedMapOfShape aMVC;
678 BOPTools::MapShapes(aC, TopAbs_VERTEX, aMVC);
681 aNbS=myDS->NbSourceShapes();
682 for (i=0; i<aNbS; ++i) {
683 const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
684 aType=aSI.ShapeType();
689 const TopoDS_Edge& aE=*((TopoDS_Edge*)&aSI.Shape());
690 if (!BRep_Tool::Degenerated(aE)) {
694 nVD=aSI.SubShapes().First();
695 const TopoDS_Shape& aVD=myDS->Shape(nVD);
697 if (!aMVC.Contains(aVD)) {
701 if (myDS->IsNewShape(nVD)) {
705 if (myDS->HasInterf(nVD)) {
714 //=======================================================================
715 //function : BuildShape
717 //=======================================================================
718 void BOPAlgo_BOP::BuildShape()
720 Standard_Integer aDmin, aNbLCB;
721 TopAbs_ShapeEnum aT1, aT2, aTR;
722 TopoDS_Shape aR, aRC;
725 BOPCol_ListOfShape aLCB;
726 BOPCol_ListIteratorOfListOfShape aItLCB;
733 if (myDims[0]<myDims[1]) {
742 else if (aDmin==1 || aDmin==2) { //edges, faces
752 BOPTools_AlgoTools::MakeConnexityBlocks
753 (myRC, aT1, aT2, aLCB);
754 aNbLCB=aLCB.Extent();
760 BOPTools_AlgoTools::MakeContainer(TopAbs_COMPOUND, aRC);
762 aItLCB.Initialize(aLCB);
763 for (; aItLCB.More(); aItLCB.Next()) {
764 BOPTools_AlgoTools::MakeContainer(aTR, aR);
766 const TopoDS_Shape& aCB=aItLCB.Value();
768 for (; aIt.More(); aIt.Next()) {
769 const TopoDS_Shape& aS=aIt.Value();
773 if (aTR==TopAbs_SHELL) {
774 BOPTools_AlgoTools::OrientFacesOnShell(aR);
780 }// elase if (aDmin==1 || aDmin==2) {
783 Standard_Integer aNbObjs, aNbTools;
785 aNbObjs=myArguments.Extent();
786 aNbTools=myTools.Extent();
788 if (aNbObjs==1 && aNbTools==1) {
789 if (myOperation==BOPAlgo_FUSE) {
801 //=======================================================================
802 //function : BuildSolid
804 //=======================================================================
805 void BOPAlgo_BOP::BuildSolid()
807 Standard_Boolean bHasInterf, bHasSharedFaces;
808 Standard_Integer i, aNbF, aNbSx, iX, iErr, aNbZ;
809 TopAbs_Orientation aOr, aOr1;
813 TopExp_Explorer aExp;
814 BOPCol_IndexedMapOfShape aMFI;
815 BOPCol_IndexedDataMapOfShapeListOfShape aMFS, aMEF;
816 BOPCol_ListIteratorOfListOfShape aItLS;
817 BOPCol_ListOfShape aSFS;
818 BOPAlgo_BuilderSolid aSB;
819 BOPCol_MapOfShape aMSA, aMZ;
820 BOPTools_IndexedDataMapOfSetShape aDMSTS;
824 // Map of of Solids of Arguments
825 for (i=0; i<2; ++i) {
826 const BOPCol_ListOfShape& aLSA=(i) ? myArguments : myTools;
827 aItLS.Initialize(aLSA);
828 for (; aItLS.More(); aItLS.Next()) {
829 const TopoDS_Shape& aSA=aItLS.Value();
830 aExp.Init(aSA, TopAbs_SOLID);
831 for (; aExp.More(); aExp.Next()) {
832 const TopoDS_Shape& aZA=aExp.Current();
835 BOPTools::MapShapesAndAncestors(aZA,
844 for (i=1; i<aNbF; ++i) {
845 //const TopoDS_Shape& aFA=aMFZA.FindKey(i);
846 const BOPCol_ListOfShape& aLZA=aMFS(i);
849 aItLS.Initialize(aLZA);
850 for(; aItLS.More(); aItLS.Next()) {
851 const TopoDS_Shape& aZA=aItLS.Value();
859 aIt.Initialize(myRC);
860 for (; aIt.More(); aIt.Next()) {
861 const TopoDS_Shape& aSx=aIt.Value();
862 if (aMSA.Contains(aSx)) {
864 bHasInterf=myDS->HasInterf(iX);
865 bHasSharedFaces=aMZ.Contains(aSx);
867 if (!bHasInterf && !bHasSharedFaces) {
868 // It means that the solid aSx will be added
869 // to the result as is.
870 // The solid aSx will not participate
871 // in creation of a new solid(s).
874 aST.Add(aSx, TopAbs_FACE);
876 if (!aDMSTS.Contains(aST)) {
877 aDMSTS.Add(aST, aSx);
884 aExp.Init(aSx, TopAbs_FACE);
885 for (; aExp.More(); aExp.Next()) {
886 const TopoDS_Shape& aFx=aExp.Current();
888 aOr=aFx.Orientation();
889 if (aOr==TopAbs_INTERNAL) {
894 if (!aMFS.Contains(aFx)) {
895 BOPCol_ListOfShape aLSx;
901 iX=aMFS.FindIndex(aFx);
902 const TopoDS_Shape& aFx1=aMFS.FindKey(iX);
903 aOr1=aFx1.Orientation();
905 BOPCol_ListOfShape& aLSx=aMFS.ChangeFromKey(aFx);
911 } // for (; aIt.More(); aIt.Next()) {
912 //faces that will be added in the end;
913 BOPCol_ListOfShape aLF, aLFx;
916 for (i=1; i<=aNbF; ++i) {
917 const TopoDS_Shape& aFx=aMFS.FindKey(i);
918 const BOPCol_ListOfShape& aLSx=aMFS(i);
921 BOPTools::MapShapesAndAncestors
922 (aFx,TopAbs_EDGE, TopAbs_FACE, aMEF);
923 if (IsBoundSplits(aFx, aMEF)){
931 aItLS.Initialize(aLF);
932 for(; aItLS.More(); aItLS.Next()) {
933 const TopoDS_Shape& aFx=aItLS.Value();
936 // add faces from aLFx to aSFS;
937 aItLS.Initialize(aLFx);
938 for (; aItLS.More(); aItLS.Next()) {
939 const TopoDS_Shape& aFx=aItLS.Value();
944 for (i=1; i<=aNbF; ++i) {
948 aFx.Orientation(TopAbs_FORWARD);
950 aFx.Orientation(TopAbs_REVERSED);
955 BOPTools_AlgoTools::MakeContainer(TopAbs_COMPOUND, aRC);
957 aSB.SetContext(myContext);
960 iErr=aSB.ErrorStatus();
962 myErrorStatus=30; // SolidBuilder failed
966 const BOPCol_ListOfShape& aLSR=aSB.Areas();
968 aItLS.Initialize(aLSR);
969 for (; aItLS.More(); aItLS.Next()) {
970 const TopoDS_Shape& aSR=aItLS.Value();
974 aNbSx = aDMSTS.Extent();
975 for (i = 1; i <= aNbSx; ++i) {
976 const TopoDS_Shape& aSx = aDMSTS(i);
982 //=======================================================================
983 //function : IsBoundSplits
985 //=======================================================================
986 Standard_Boolean BOPAlgo_BOP::IsBoundSplits
987 (const TopoDS_Shape& aS,
988 BOPCol_IndexedDataMapOfShapeListOfShape& aMEF)
990 Standard_Boolean bRet = Standard_False;
991 if (mySplits.IsBound(aS) || myOrigins.IsBound(aS)) {
995 BOPCol_ListIteratorOfListOfShape aIt;
996 Standard_Integer aNbLS;
997 TopAbs_Orientation anOr;
999 //check face aF may be connected to face from mySplits
1000 TopExp_Explorer aExp(aS, TopAbs_EDGE);
1001 for (; aExp.More(); aExp.Next()) {
1002 const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aExp.Current()));
1004 anOr = aE.Orientation();
1005 if (anOr==TopAbs_INTERNAL) {
1009 if (BRep_Tool::Degenerated(aE)) {
1013 const BOPCol_ListOfShape& aLS=aMEF.FindFromKey(aE);
1014 aNbLS = aLS.Extent();
1019 aIt.Initialize(aLS);
1020 for (; aIt.More(); aIt.Next()) {
1021 const TopoDS_Shape& aSx = aIt.Value();
1022 if (mySplits.IsBound(aSx) || myOrigins.IsBound(aS)) {
1030 //=======================================================================
1031 //function : TypeToExplore
1033 //=======================================================================
1034 TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim)
1036 TopAbs_ShapeEnum aRet;