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