0029293: Boolean Operations algorithm does not preserve the orientations of the faces
[occt.git] / src / BOPAlgo / BOPAlgo_Builder_2.cxx
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
6 //
7 // This file is part of Open CASCADE Technology software library.
8 //
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.
14 //
15 // Alternatively, this file may be used under the terms of Open CASCADE
16 // commercial license or contractual agreement.
17
18
19 #include <BOPAlgo_Builder.hxx>
20 #include <BOPAlgo_BuilderFace.hxx>
21 #include <BOPAlgo_PaveFiller.hxx>
22 #include <BOPAlgo_Tools.hxx>
23 #include <BOPCol_DataMapOfIntegerListOfShape.hxx>
24 #include <BOPCol_DataMapOfShapeShape.hxx>
25 #include <BOPCol_ListOfInteger.hxx>
26 #include <BOPCol_ListOfShape.hxx>
27 #include <BOPCol_MapOfInteger.hxx>
28 #include <BOPCol_NCVector.hxx>
29 #include <BOPCol_Parallel.hxx>
30 #include <BOPDS_DS.hxx>
31 #include <BOPDS_FaceInfo.hxx>
32 #include <BOPDS_Interf.hxx>
33 #include <BOPDS_MapOfPaveBlock.hxx>
34 #include <BOPDS_PaveBlock.hxx>
35 #include <BOPDS_ShapeInfo.hxx>
36 #include <BOPDS_VectorOfCurve.hxx>
37 #include <BOPDS_VectorOfInterfFF.hxx>
38 #include <BOPDS_VectorOfPoint.hxx>
39 #include <BOPTools.hxx>
40 #include <BOPTools_AlgoTools.hxx>
41 #include <BOPTools_AlgoTools2D.hxx>
42 #include <BOPTools_AlgoTools3D.hxx>
43 #include <BOPTools_CoupleOfShape.hxx>
44 #include <BOPTools_DataMapOfShapeSet.hxx>
45 #include <BOPTools_ListOfCoupleOfShape.hxx>
46 #include <BOPTools_MapOfSet.hxx>
47 #include <BRep_Builder.hxx>
48 #include <BRep_Tool.hxx>
49 #include <GeomAdaptor_Surface.hxx>
50 #include <GeomLib.hxx>
51 #include <Precision.hxx>
52 #include <IntTools_Context.hxx>
53 #include <TopExp_Explorer.hxx>
54 #include <TopoDS.hxx>
55 #include <TopoDS_Compound.hxx>
56 #include <TopoDS_Edge.hxx>
57 #include <TopoDS_Face.hxx>
58 #include <TopoDS_Shape.hxx>
59 #include <TopoDS_Vertex.hxx>
60
61 //
62 static
63   Standard_Boolean HasPaveBlocksOnIn(const BOPDS_FaceInfo& aFI1,
64                                      const BOPDS_FaceInfo& aFI2);
65 //
66 static
67   TopoDS_Face BuildDraftFace(const TopoDS_Face& theFace,
68                              const BOPCol_DataMapOfShapeListOfShape& theImages,
69                              Handle(IntTools_Context)& theCtx);
70 //
71 typedef BOPCol_NCVector<TopoDS_Shape> BOPAlgo_VectorOfShape;
72 //
73 typedef BOPCol_NCVector<BOPAlgo_VectorOfShape> \
74   BOPAlgo_VectorOfVectorOfShape;
75 //
76 typedef NCollection_IndexedDataMap\
77   <BOPTools_Set, Standard_Integer, BOPTools_SetMapHasher> \
78     BOPAlgo_IndexedDataMapOfSetInteger;
79 //
80 //=======================================================================
81 //class    : BOPAlgo_PairOfShapeBoolean
82 //purpose  : 
83 //=======================================================================
84 class BOPAlgo_PairOfShapeBoolean : public BOPAlgo_Algo {
85
86  public:
87   DEFINE_STANDARD_ALLOC
88
89   BOPAlgo_PairOfShapeBoolean() : 
90     BOPAlgo_Algo(),
91     myFlag(Standard_False) {
92   }
93   //
94   virtual ~BOPAlgo_PairOfShapeBoolean() {
95   }
96   //
97   TopoDS_Shape& Shape1() {
98     return myShape1;
99   }
100   //
101   TopoDS_Shape& Shape2() {
102     return myShape2;
103   }
104   //
105   Standard_Boolean& Flag() {
106     return myFlag;
107   }
108   //
109   void SetContext(const Handle(IntTools_Context)& aContext) {
110     myContext=aContext;
111   }
112   //
113   const Handle(IntTools_Context)& Context()const {
114     return myContext;
115   }
116   //
117   virtual void Perform() {
118     BOPAlgo_Algo::UserBreak();
119     //  
120     const TopoDS_Face& aFj=*((TopoDS_Face*)&myShape1);
121     const TopoDS_Face& aFk=*((TopoDS_Face*)&myShape2);
122     myFlag=BOPTools_AlgoTools::AreFacesSameDomain(aFj, aFk, myContext, myFuzzyValue);
123   }
124   //
125  protected: 
126   Standard_Boolean myFlag;
127   TopoDS_Shape myShape1;
128   TopoDS_Shape myShape2;
129   Handle(IntTools_Context) myContext;
130 };
131 //
132 typedef BOPCol_NCVector<BOPAlgo_PairOfShapeBoolean> \
133   BOPAlgo_VectorOfPairOfShapeBoolean;
134 //
135 typedef BOPCol_ContextFunctor 
136   <BOPAlgo_PairOfShapeBoolean,
137   BOPAlgo_VectorOfPairOfShapeBoolean,
138   Handle(IntTools_Context), 
139   IntTools_Context> BOPCol_BuilderSDFaceFunctor;
140 //
141 typedef BOPCol_ContextCnt 
142   <BOPCol_BuilderSDFaceFunctor,
143   BOPAlgo_VectorOfPairOfShapeBoolean,
144   Handle(IntTools_Context)> BOPAlgo_BuilderSDFaceCnt;
145 //
146 //=======================================================================
147 // BuilderFace
148 //
149 typedef BOPCol_NCVector<BOPAlgo_BuilderFace> BOPAlgo_VectorOfBuilderFace;
150 //
151 typedef BOPCol_Functor 
152   <BOPAlgo_BuilderFace,
153   BOPAlgo_VectorOfBuilderFace> BOPAlgo_BuilderFaceFunctor;
154 //
155 typedef BOPCol_Cnt 
156   <BOPAlgo_BuilderFaceFunctor,
157   BOPAlgo_VectorOfBuilderFace> BOPAlgo_BuilderFaceCnt;
158 //
159 //=======================================================================
160 //class    : BOPAlgo_VFI
161 //purpose  : 
162 //=======================================================================
163 class BOPAlgo_VFI : public BOPAlgo_Algo {
164
165  public:
166   DEFINE_STANDARD_ALLOC
167   
168   BOPAlgo_VFI() :
169     BOPAlgo_Algo(),
170     myFlag(-1) {
171   }
172   //
173   virtual ~BOPAlgo_VFI(){
174   }
175   //
176   void SetVertex(const TopoDS_Vertex& aV) {
177     myV=aV;
178   }
179   //
180   TopoDS_Vertex& Vertex() {
181     return myV;
182   }
183   //
184   void SetFace(const TopoDS_Face& aF) {
185     myF=aF;
186   }
187   //
188   TopoDS_Face& Face() {
189     return myF;
190   }
191   //
192   Standard_Integer Flag()const {
193     return myFlag;
194   }
195   //
196   void SetContext(const Handle(IntTools_Context)& aContext) {
197     myContext=aContext;
198   }
199   //
200   const Handle(IntTools_Context)& Context()const {
201     return myContext;
202   }
203   //
204   virtual void Perform() {
205     Standard_Real aT1, aT2, dummy;
206     //
207     BOPAlgo_Algo::UserBreak();
208     myFlag = myContext->ComputeVF(myV, myF, aT1, aT2, dummy, myFuzzyValue);
209   }
210   //
211  protected:
212   Standard_Integer myFlag;
213   TopoDS_Vertex myV;
214   TopoDS_Face myF;
215   Handle(IntTools_Context) myContext;
216 };
217 //
218 typedef BOPCol_NCVector<BOPAlgo_VFI> BOPAlgo_VectorOfVFI; 
219 //
220 typedef BOPCol_ContextFunctor 
221   <BOPAlgo_VFI,
222   BOPAlgo_VectorOfVFI,
223   Handle(IntTools_Context), 
224   IntTools_Context> BOPAlgo_VFIFunctor;
225 //
226 typedef BOPCol_ContextCnt 
227   <BOPAlgo_VFIFunctor,
228   BOPAlgo_VectorOfVFI,
229   Handle(IntTools_Context)> BOPAlgo_VFICnt;
230 //
231 //=======================================================================
232 //function : FillImagesFaces
233 //purpose  : 
234 //=======================================================================
235 void BOPAlgo_Builder::FillImagesFaces()
236 {
237   BuildSplitFaces();
238   FillSameDomainFaces();
239   FillImagesFaces1();
240 }
241 //=======================================================================
242 //function : BuildSplitFaces
243 //purpose  : 
244 //=======================================================================
245 void BOPAlgo_Builder::BuildSplitFaces()
246 {
247   Standard_Boolean bHasFaceInfo, bIsClosed, bIsDegenerated, bToReverse;
248   Standard_Integer i, j, k, aNbS, aNbPBIn, aNbPBOn, aNbPBSc, aNbAV, nSp;
249   TopoDS_Face aFF, aFSD;
250   TopoDS_Edge aSp, aEE;
251   TopAbs_Orientation anOriF, anOriE;
252   TopExp_Explorer aExp;
253   BOPCol_ListIteratorOfListOfShape aIt;
254   BOPCol_ListOfInteger aLIAV;
255   BOPCol_MapOfShape aMFence;
256   Handle(NCollection_BaseAllocator) aAllocator;
257   BOPAlgo_VectorOfBuilderFace aVBF;
258   //
259   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~scope f
260   aAllocator=
261     NCollection_BaseAllocator::CommonBaseAllocator();
262   //
263   BOPCol_ListOfShape aLE(aAllocator);
264   BOPCol_MapOfShape aMDE(100, aAllocator);
265   //
266   // Build temporary map of faces images to avoid rebuilding
267   // of the faces without any IN or section edges
268   NCollection_IndexedDataMap<Standard_Integer, BOPCol_ListOfShape> aFacesIm;
269   //
270   aNbS=myDS->NbSourceShapes();
271   //
272   for (i=0; i<aNbS; ++i) {
273     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
274     if (aSI.ShapeType()!=TopAbs_FACE) {
275       continue;
276     }
277     //
278     const TopoDS_Face& aF=(*(TopoDS_Face*)(&aSI.Shape()));
279     Standard_Boolean isUClosed = Standard_False,
280                      isVClosed = Standard_False,
281                      isChecked = Standard_False;
282     //
283     bHasFaceInfo=myDS->HasFaceInfo(i);
284     if(!bHasFaceInfo) {
285       continue;
286     }
287     //
288     const BOPDS_FaceInfo& aFI=myDS->FaceInfo(i);
289     //
290     const BOPDS_IndexedMapOfPaveBlock& aMPBIn=aFI.PaveBlocksIn();
291     const BOPDS_IndexedMapOfPaveBlock& aMPBOn=aFI.PaveBlocksOn();
292     const BOPDS_IndexedMapOfPaveBlock& aMPBSc=aFI.PaveBlocksSc();
293     aLIAV.Clear();
294     myDS->AloneVertices(i, aLIAV);
295     
296     aNbPBIn=aMPBIn.Extent();
297     aNbPBOn=aMPBOn.Extent();
298     aNbPBSc=aMPBSc.Extent();
299     aNbAV=aLIAV.Extent();
300     if (!aNbPBIn && !aNbPBOn && !aNbPBSc && !aNbAV) { // not compete
301       continue;
302     }
303
304     if (!aNbPBIn && !aNbPBSc)
305     {
306       // No internal parts for the face, so just build the draft face
307       // and keep it to pass directly into result.
308       // If the original face has any internal edges, the draft face
309       // will be null, as the internal edges may split the face on parts
310       // (as in the case "bugs modalg_5 bug25245_1").
311       // The BuilderFace algorithm will be called in this case.
312       TopoDS_Face aFD = BuildDraftFace(aF, myImages, myContext);
313       if (!aFD.IsNull())
314       {
315         aFacesIm(aFacesIm.Add(i, BOPCol_ListOfShape())).Append(aFD);
316         continue;
317       }
318     }
319
320     aMFence.Clear();
321     //
322     anOriF=aF.Orientation();
323     aFF=aF;
324     aFF.Orientation(TopAbs_FORWARD);
325     //
326     // 1. Fill the edges set for the face aFF -> LE
327     aLE.Clear();
328
329     // 1.1 Bounding edges
330     aExp.Init(aFF, TopAbs_EDGE);
331     for (; aExp.More(); aExp.Next()) {
332       const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aExp.Current()));
333       anOriE=aE.Orientation();
334       //
335       if (!myImages.IsBound(aE)) {
336         if (anOriE==TopAbs_INTERNAL) {
337           aEE=aE;
338           aEE.Orientation(TopAbs_FORWARD);
339           aLE.Append(aEE);
340           aEE.Orientation(TopAbs_REVERSED);
341           aLE.Append(aEE);
342         }
343         else {
344           aLE.Append(aE);
345         }
346
347         continue;
348       }
349
350       if(!isChecked)
351       {
352         const Handle(Geom_Surface) aSurf = BRep_Tool::Surface(aF);
353         GeomLib::IsClosed(aSurf, BRep_Tool::Tolerance(aE),
354           isUClosed, isVClosed);
355
356         isChecked = Standard_True;
357       }
358
359       bIsClosed = Standard_False;
360
361       if((isUClosed || isVClosed) && BRep_Tool::IsClosed(aE, aF)) 
362       {
363
364         Standard_Boolean isUIso = Standard_False, isVIso = Standard_False;
365         BOPTools_AlgoTools2D::IsEdgeIsoline(aE, aF, isUIso, isVIso);
366
367         bIsClosed = ((isUClosed && isUIso) || (isVClosed && isVIso));
368       }
369
370       bIsDegenerated=BRep_Tool::Degenerated(aE);
371
372       const BOPCol_ListOfShape& aLIE=myImages.Find(aE);
373       aIt.Initialize(aLIE);
374       for (; aIt.More(); aIt.Next()) {
375         aSp=(*(TopoDS_Edge*)(&aIt.Value()));
376         if (bIsDegenerated) {
377           aSp.Orientation(anOriE);
378           aLE.Append(aSp);
379           continue;
380         }
381         //
382         if (anOriE==TopAbs_INTERNAL) {
383           aSp.Orientation(TopAbs_FORWARD);
384           aLE.Append(aSp);
385           aSp.Orientation(TopAbs_REVERSED);
386           aLE.Append(aSp);
387           continue;
388         }
389           //
390         if (bIsClosed) {
391           if (aMFence.Add(aSp)) {
392             if (!BRep_Tool::IsClosed(aSp, aF)){
393               BOPTools_AlgoTools3D::DoSplitSEAMOnFace(aSp, aF);
394             }
395             //
396             aSp.Orientation(TopAbs_FORWARD);
397             aLE.Append(aSp);
398             aSp.Orientation(TopAbs_REVERSED);
399             aLE.Append(aSp);
400           }// if (aMFence.Add(aSp))
401           continue;
402         }// if (bIsClosed){
403         //
404         aSp.Orientation(anOriE);
405         bToReverse=BOPTools_AlgoTools::IsSplitToReverse(aSp, aE, myContext);
406         if (bToReverse) {
407           aSp.Reverse();
408         }
409         aLE.Append(aSp);
410       }// for (; aIt.More(); aIt.Next()) {
411     }// for (; aExp.More(); aExp.Next()) {
412     // 
413     //
414     // 1.2 In edges
415     for (j=1; j<=aNbPBIn; ++j) {
416       const Handle(BOPDS_PaveBlock)& aPB=aMPBIn(j);
417       nSp=aPB->Edge();
418       aSp=(*(TopoDS_Edge*)(&myDS->Shape(nSp)));
419       //
420       aSp.Orientation(TopAbs_FORWARD);
421       aLE.Append(aSp);
422       aSp.Orientation(TopAbs_REVERSED);
423       aLE.Append(aSp);
424     }
425     //
426     //
427     // 1.3 Section edges
428     for (j=1; j<=aNbPBSc; ++j) {
429       const Handle(BOPDS_PaveBlock)& aPB=aMPBSc(j);
430       nSp=aPB->Edge();
431       aSp=(*(TopoDS_Edge*)(&myDS->Shape(nSp)));
432       //
433       aSp.Orientation(TopAbs_FORWARD);
434       aLE.Append(aSp);
435       aSp.Orientation(TopAbs_REVERSED);
436       aLE.Append(aSp);
437     }
438     //
439     if (!myPaveFiller->NonDestructive()) {
440       // speed up for planar faces
441       BOPTools_AlgoTools2D::BuildPCurveForEdgesOnPlane (aLE, aFF);
442     }
443     // 3 Build split faces
444     BOPAlgo_BuilderFace& aBF=aVBF.Append1();
445     aBF.SetFace(aF);
446     aBF.SetShapes(aLE);
447     aBF.SetRunParallel(myRunParallel);
448     aBF.SetProgressIndicator(myProgressIndicator);
449     //
450   }// for (i=0; i<aNbS; ++i) {
451   //
452   //===================================================
453   BOPAlgo_BuilderFaceCnt::Perform(myRunParallel, aVBF);
454   //===================================================
455   //
456   Standard_Integer aNbBF = aVBF.Extent();
457   for (k = 0; k < aNbBF; ++k)
458   {
459     BOPAlgo_BuilderFace& aBF = aVBF(k);
460     aFacesIm.Add(myDS->Index(aBF.Face()), aBF.Areas());
461   }
462
463   aNbBF = aFacesIm.Extent();
464   for (k = 1; k <= aNbBF; ++k)
465   {
466     const TopoDS_Face& aF = TopoDS::Face(myDS->Shape(aFacesIm.FindKey(k)));
467     anOriF = aF.Orientation();
468     const BOPCol_ListOfShape& aLFR = aFacesIm(k);
469     //
470     BOPCol_ListOfShape* pLFIm = mySplits.Bound(aF, BOPCol_ListOfShape());
471     aIt.Initialize(aLFR);
472     for (; aIt.More(); aIt.Next()) {
473       TopoDS_Shape& aFR=aIt.ChangeValue();
474       if (anOriF==TopAbs_REVERSED)
475         aFR.Orientation(TopAbs_REVERSED);
476       pLFIm->Append(aFR);
477     }
478   }
479   //
480   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~scope t
481 }
482 //=======================================================================
483 //function : FillSameDomainFaces
484 //purpose  : 
485 //=======================================================================
486 void BOPAlgo_Builder::FillSameDomainFaces()
487 {
488   Standard_Boolean bFlag;
489   Standard_Integer i, j, k, aNbFFs, nF1, nF2;
490   Handle(NCollection_BaseAllocator) aAllocator;
491   BOPCol_ListIteratorOfListOfShape aItF;
492   BOPCol_MapOfShape aMFence;
493   BOPAlgo_IndexedDataMapOfSetInteger aIDMSS;
494   BOPAlgo_VectorOfVectorOfShape aVVS;
495   //
496   const BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
497   //
498   aNbFFs=aFFs.Extent();
499   if (!aNbFFs) {
500     return;
501   }
502   //
503   for (i=0; i<aNbFFs; ++i) {
504     const BOPDS_InterfFF& aFF=aFFs(i);
505     aFF.Indices(nF1, nF2);
506     //
507     if (!myDS->HasFaceInfo(nF1) || !myDS->HasFaceInfo(nF2) ) {
508       continue;
509     }
510     //
511     const BOPDS_FaceInfo& aFI1=myDS->FaceInfo(nF1);
512     const BOPDS_FaceInfo& aFI2=myDS->FaceInfo(nF2);
513     //
514     const TopoDS_Shape& aF1=myDS->Shape(nF1);
515     const TopoDS_Shape& aF2=myDS->Shape(nF2);
516     //
517     bFlag=HasPaveBlocksOnIn(aFI1, aFI2);
518     bFlag=bFlag && (mySplits.IsBound(aF1) && mySplits.IsBound(aF2));
519     //
520     if (bFlag) {
521       for (k=0; k<2; ++k) {
522         const TopoDS_Shape& aF=(!k) ? aF1 : aF2;
523         const BOPCol_ListOfShape& aLF=mySplits.Find(aF);
524         //
525         aItF.Initialize(aLF);
526         for (; aItF.More(); aItF.Next()) {
527           const TopoDS_Shape& aFx=aItF.Value();
528           //
529           if (aMFence.Add(aFx)) {
530             BOPTools_Set aSTx;
531             //
532             aSTx.Add(aFx, TopAbs_EDGE);
533             //
534             if (!aIDMSS.Contains(aSTx)) {
535               BOPAlgo_VectorOfShape& aVS=aVVS.Append1(); 
536               aVS.Append(aFx);
537               //
538               j=aVVS.Extent()-1;
539               aIDMSS.Add (aSTx, j);
540             }
541             else {
542               j=aIDMSS.ChangeFromKey(aSTx);
543               BOPAlgo_VectorOfShape& aVS=aVVS(j);
544               aVS.Append(aFx);
545             }
546           }
547         }
548       }
549     }// if (bFlag) {
550     else {// if (!bFlag) 
551       BOPTools_Set aST1, aST2;
552       //
553       aST1.Add(aF1, TopAbs_EDGE);
554       aST2.Add(aF2, TopAbs_EDGE);
555       //
556       if (aST1.IsEqual(aST2)) {
557         if (!aIDMSS.Contains(aST1)) {
558           BOPAlgo_VectorOfShape& aVS=aVVS.Append1(); 
559           if (aMFence.Add(aF1)) {
560             aVS.Append(aF1);
561           }
562           if (aMFence.Add(aF2)) {
563             aVS.Append(aF2);
564           }
565           //
566           k=aVVS.Extent()-1;
567           aIDMSS.Add (aST1, k);
568         }
569         else {
570           k=aIDMSS.ChangeFromKey(aST1);
571           BOPAlgo_VectorOfShape& aVS=aVVS(k);
572           if (aMFence.Add(aF1)) {
573             aVS.Append(aF1);
574           }
575           if (aMFence.Add(aF2)) {
576             aVS.Append(aF2);
577           }
578         }
579       }//if (aST1.IsEqual(aST2)) {
580     }// else {// if (!bFlag) 
581     //
582   }// for (i=0; i<aNbFFs; ++i) {
583   //
584   aIDMSS.Clear();
585   //
586   Standard_Boolean bFlagSD;
587   Standard_Integer aNbVPSB, aNbVVS, aNbF, aNbF1;
588   BOPAlgo_VectorOfPairOfShapeBoolean aVPSB;
589   //
590   aNbVVS=aVVS.Extent();
591   for (i=0; i<aNbVVS; ++i) {
592     const BOPAlgo_VectorOfShape& aVS=aVVS(i);
593     aNbF=aVS.Extent();
594     if (aNbF<2) {
595       continue;
596     }
597     //
598     aNbF1=aNbF-1;
599     for (j=0; j<aNbF1; ++j) {
600       const TopoDS_Shape& aFj=aVS(j);
601       for (k=j+1; k<aNbF; ++k) {
602         const TopoDS_Shape& aFk=aVS(k);
603         BOPAlgo_PairOfShapeBoolean& aPSB=aVPSB.Append1();
604         aPSB.Shape1()=aFj;
605         aPSB.Shape2()=aFk;
606         aPSB.SetFuzzyValue(myFuzzyValue);
607         aPSB.SetProgressIndicator(myProgressIndicator);
608       }
609     }
610   }
611   //================================================================
612   BOPAlgo_BuilderSDFaceCnt::Perform(myRunParallel, aVPSB, myContext);
613   //================================================================
614   aAllocator=
615     NCollection_BaseAllocator::CommonBaseAllocator();
616   BOPCol_IndexedDataMapOfShapeListOfShape aDMSLS(100, aAllocator);
617   NCollection_List<BOPCol_ListOfShape> aMBlocks(aAllocator);
618   //
619   aNbVPSB=aVPSB.Extent();
620   for (i=0; i<aNbVPSB; ++i) {
621     BOPAlgo_PairOfShapeBoolean& aPSB=aVPSB(i);
622     bFlagSD=aPSB.Flag();
623     if (bFlagSD) {
624       const TopoDS_Shape& aFj=aPSB.Shape1();
625       const TopoDS_Shape& aFk=aPSB.Shape2();
626       BOPAlgo_Tools::FillMap<TopoDS_Shape, TopTools_ShapeMapHasher>(aFj, aFk, aDMSLS, aAllocator);
627     }
628   }
629   aVPSB.Clear();
630   //
631   // 2. Make blocks
632   BOPAlgo_Tools::MakeBlocks<TopoDS_Shape, TopTools_ShapeMapHasher>(aDMSLS, aMBlocks, aAllocator);
633   //
634   // 3. Fill same domain faces map -> aMSDF
635   NCollection_List<BOPCol_ListOfShape>::Iterator aItB(aMBlocks);
636   for (; aItB.More(); aItB.Next()) {
637     const BOPCol_ListOfShape& aLSD = aItB.Value();
638     //
639     const TopoDS_Shape& aFSD1=aLSD.First();
640     aItF.Initialize(aLSD);
641     for (; aItF.More(); aItF.Next()) {
642       const TopoDS_Shape& aFSD=aItF.Value();
643       myShapesSD.Bind(aFSD, aFSD1);
644       //
645       // If the face has no splits but are SD face,
646       // it is considered as splitted face
647       if (!mySplits.IsBound(aFSD)) {
648         BOPCol_ListOfShape aLS;
649         aLS.Append(aFSD);
650         mySplits.Bind(aFSD, aLS);
651       }
652     }
653   }
654   aMBlocks.Clear();
655   aDMSLS.Clear();
656 }
657 //=======================================================================
658 // function: FillImagesFaces1
659 // purpose: 
660 //=======================================================================
661 void BOPAlgo_Builder::FillImagesFaces1()
662 {
663   Standard_Integer i, aNbS, iSense, nVx, aNbVFI, iFlag;
664   TopoDS_Face aFSD;
665   TopoDS_Vertex aVx;
666   BRep_Builder aBB;
667   BOPCol_ListOfInteger aLIAV;
668   BOPCol_ListOfShape aLFIm;
669   BOPCol_ListIteratorOfListOfInteger aItV;
670   BOPCol_ListIteratorOfListOfShape aItLS, aItF;
671   BOPAlgo_VectorOfVFI aVVFI;
672   //
673   aNbS=myDS->NbSourceShapes();
674   for (i=0; i<aNbS; ++i) {
675     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
676     if (aSI.ShapeType()!=TopAbs_FACE) {
677       continue;
678     }
679     //
680     const TopoDS_Face& aF=(*(TopoDS_Face*)(&aSI.Shape()));
681     //
682     if (!mySplits.IsBound(aF)) {
683       continue;
684     }
685     // 
686     // 1.
687     aLIAV.Clear();
688     myDS->AloneVertices(i, aLIAV);
689     aLFIm.Clear();
690     //
691     const BOPCol_ListOfShape& aLSp=mySplits.Find(aF);
692     aItLS.Initialize(aLSp);
693     for (; aItLS.More(); aItLS.Next()) {
694       const TopoDS_Face& aFSp=(*(TopoDS_Face*)(&aItLS.Value()));
695       if (!myShapesSD.IsBound(aFSp)) {
696         aLFIm.Append(aFSp);
697       }
698       else {
699         aFSD=(*(TopoDS_Face*)(&myShapesSD.Find(aFSp)));
700         iSense=BOPTools_AlgoTools::Sense(aFSp, aFSD, myContext);
701         if (iSense<0) {
702           aFSD.Reverse();
703         }
704         aLFIm.Append(aFSD);
705       }
706     }
707     //
708     //FillInternalVertices(aLFIm, aLIAV);
709     //
710     myImages.Bind(aF, aLFIm); 
711     //
712     // 2. fill myOrigins
713     aItLS.Initialize(aLFIm);
714     for (; aItLS.More(); aItLS.Next()) {
715       const TopoDS_Face& aFSp=(*(TopoDS_Face*)(&aItLS.Value()));
716       //
717       BOPCol_ListOfShape* pLOr = myOrigins.ChangeSeek(aFSp);
718       if (!pLOr) {
719         pLOr = myOrigins.Bound(aFSp, BOPCol_ListOfShape());
720       }
721       pLOr->Append(aF);
722     }
723     //
724     // 3.
725     aItV.Initialize(aLIAV);
726     for (; aItV.More(); aItV.Next()) {
727       nVx=aItV.Value();
728       aVx=(*(TopoDS_Vertex*)(&myDS->Shape(nVx)));
729       aVx.Orientation(TopAbs_INTERNAL);
730       //
731       aItF.Initialize(aLFIm);
732       for (; aItF.More(); aItF.Next()) {
733         TopoDS_Face& aFy=(*(TopoDS_Face*)(&aItF.Value()));
734         //
735         BOPAlgo_VFI& aVFI=aVVFI.Append1();
736         aVFI.SetVertex(aVx);
737         aVFI.SetFace(aFy);
738         aVFI.SetFuzzyValue(myFuzzyValue);
739         aVFI.SetProgressIndicator(myProgressIndicator);
740       }
741     }
742   }// for (i=0; i<aNbS; ++i) {
743   //
744   // 4. 
745   aNbVFI=aVVFI.Extent();
746   //================================================================
747   BOPAlgo_VFICnt::Perform(myRunParallel, aVVFI, myContext);
748   //================================================================
749   //
750   for (i=0; i < aNbVFI; ++i) {
751     BOPAlgo_VFI& aVFI=aVVFI(i);
752     //
753     iFlag=aVFI.Flag();
754     if (!iFlag) {
755       TopoDS_Vertex& aVertex=aVFI.Vertex();
756       TopoDS_Face& aFy=aVFI.Face(); 
757       aBB.Add(aFy, aVertex);
758     }
759   }
760 }
761 //=======================================================================
762 //function :HasPaveBlocksOnIn
763 //purpose  : 
764 //=======================================================================
765 Standard_Boolean HasPaveBlocksOnIn(const BOPDS_FaceInfo& aFI1,
766                                    const BOPDS_FaceInfo& aFI2)
767 {
768   Standard_Boolean bRet;
769   Standard_Integer i, aNbPB;
770   //
771   bRet=Standard_False;
772   const BOPDS_IndexedMapOfPaveBlock& aMPBOn1 = aFI1.PaveBlocksOn();
773   const BOPDS_IndexedMapOfPaveBlock& aMPBIn1 = aFI1.PaveBlocksIn();
774   //
775   const BOPDS_IndexedMapOfPaveBlock& aMPBOn2 = aFI2.PaveBlocksOn();
776   aNbPB = aMPBOn2.Extent();
777   for (i = 1; i <= aNbPB; ++i) {
778     const Handle(BOPDS_PaveBlock)& aPB = aMPBOn2(i);
779     bRet = aMPBOn1.Contains(aPB) || aMPBIn1.Contains(aPB);
780     if (bRet) {
781       return bRet;
782     }
783   }
784   //
785   const BOPDS_IndexedMapOfPaveBlock& aMPBIn2 = aFI2.PaveBlocksIn();
786   aNbPB = aMPBIn2.Extent();
787   for (i = 1; i <= aNbPB; ++i) {
788     const Handle(BOPDS_PaveBlock)& aPB = aMPBIn2(i);
789     bRet = aMPBOn1.Contains(aPB) || aMPBIn1.Contains(aPB);
790     if (bRet) {
791       return bRet;
792     }
793   }
794   return bRet;
795 }
796
797 //=======================================================================
798 //function : BuildDraftFace
799 //purpose  : Build draft faces, updating the bounding edges,
800 //           according to the information stored into the <theImages> map
801 //=======================================================================
802 TopoDS_Face BuildDraftFace(const TopoDS_Face& theFace,
803                            const BOPCol_DataMapOfShapeListOfShape& theImages,
804                            Handle(IntTools_Context)& theCtx)
805 {
806   BRep_Builder aBB;
807   // Take the information from the original face
808   TopLoc_Location aLoc;
809   const Handle(Geom_Surface)& aS = BRep_Tool::Surface(theFace, aLoc);
810   const Standard_Real aTol = BRep_Tool::Tolerance(theFace);
811   // Make the new face, without any wires
812   TopoDS_Face aDraftFace;
813   aBB.MakeFace(aDraftFace, aS, aLoc, aTol);
814
815   // Update wires of the original face and add them to draft face
816   TopoDS_Iterator aItW(theFace.Oriented(TopAbs_FORWARD));
817   for (; aItW.More(); aItW.Next())
818   {
819     const TopoDS_Shape& aW = aItW.Value();
820     if (aW.ShapeType() != TopAbs_WIRE)
821       continue;
822
823     // Rebuild wire using images of edges
824     TopoDS_Iterator aItE(aW.Oriented(TopAbs_FORWARD));
825     if (!aItE.More())
826       continue;
827
828     TopoDS_Wire aNewWire;
829     aBB.MakeWire(aNewWire);
830
831     for (; aItE.More(); aItE.Next())
832     {
833       const TopoDS_Edge& aE = TopoDS::Edge(aItE.Value());
834
835       TopAbs_Orientation anOriE = aE.Orientation();
836       if (anOriE == TopAbs_INTERNAL)
837       {
838         // The internal edges could split the original face on halves.
839         // Thus, use the BuilderFace algorithm to build the new face.
840         TopoDS_Face aNull;
841         return aNull;
842       }
843
844       const BOPCol_ListOfShape* pLEIm = theImages.Seek(aE);
845       if (!pLEIm)
846       {
847         aBB.Add(aNewWire, aE);
848         continue;
849       }
850
851       // Check if the original edge is degenerated
852       Standard_Boolean bIsDegenerated = BRep_Tool::Degenerated(aE);
853       // Check if the original edge is closed on the face
854       Standard_Boolean bIsClosed = BRep_Tool::IsClosed(aE, theFace);
855
856       BOPCol_ListIteratorOfListOfShape aItLEIm(*pLEIm);
857       for (; aItLEIm.More(); aItLEIm.Next())
858       {
859         TopoDS_Edge& aSp = TopoDS::Edge(aItLEIm.Value());
860
861         aSp.Orientation(anOriE);
862         if (bIsDegenerated)
863         {
864           aBB.Add(aNewWire, aSp);
865           continue;
866         }
867
868         // Check closeness of the split edge and if it is not
869         // make the second PCurve
870         if (bIsClosed && !BRep_Tool::IsClosed(aSp, theFace))
871           BOPTools_AlgoTools3D::DoSplitSEAMOnFace(aSp, theFace);
872
873         // Check if the split should be reversed
874         if (BOPTools_AlgoTools::IsSplitToReverse(aSp, aE, theCtx))
875           aSp.Reverse();
876
877         aBB.Add(aNewWire, aSp);
878       }
879     }
880
881     aNewWire.Orientation(aW.Orientation());
882     aNewWire.Closed(BRep_Tool::IsClosed(aNewWire));
883     aBB.Add(aDraftFace, aNewWire);
884   }
885
886   if (theFace.Orientation() == TopAbs_REVERSED)
887     aDraftFace.Reverse();
888
889   return aDraftFace;
890 }