0025748: Parallel version of progress indicator
[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 <BOPDS_DS.hxx>
24 #include <BOPDS_FaceInfo.hxx>
25 #include <BOPDS_Interf.hxx>
26 #include <BOPDS_MapOfPaveBlock.hxx>
27 #include <BOPDS_PaveBlock.hxx>
28 #include <BOPDS_ShapeInfo.hxx>
29 #include <BOPDS_VectorOfCurve.hxx>
30 #include <BOPDS_VectorOfInterfFF.hxx>
31 #include <BOPDS_VectorOfPoint.hxx>
32 #include <BOPTools_AlgoTools.hxx>
33 #include <BOPTools_AlgoTools2D.hxx>
34 #include <BOPTools_AlgoTools3D.hxx>
35 #include <BOPTools_CoupleOfShape.hxx>
36 #include <BOPTools_ListOfCoupleOfShape.hxx>
37 #include <BOPTools_MapOfSet.hxx>
38 #include <BOPTools_Parallel.hxx>
39 #include <BRep_Builder.hxx>
40 #include <BRepLib.hxx>
41 #include <BRep_Tool.hxx>
42 #include <GeomAdaptor_Surface.hxx>
43 #include <GeomLib.hxx>
44 #include <NCollection_IncAllocator.hxx>
45 #include <NCollection_Vector.hxx>
46 #include <Precision.hxx>
47 #include <IntTools_Context.hxx>
48 #include <TColStd_ListOfInteger.hxx>
49 #include <TColStd_MapOfInteger.hxx>
50 #include <TopExp_Explorer.hxx>
51 #include <TopoDS.hxx>
52 #include <TopoDS_Compound.hxx>
53 #include <TopoDS_Edge.hxx>
54 #include <TopoDS_Face.hxx>
55 #include <TopoDS_Shape.hxx>
56 #include <TopoDS_Vertex.hxx>
57 #include <TopTools_ListOfShape.hxx>
58
59 #include <algorithm>
60 //
61 static
62   TopoDS_Face BuildDraftFace(const TopoDS_Face& theFace,
63                              const TopTools_DataMapOfShapeListOfShape& theImages,
64                              Handle(IntTools_Context)& theCtx,
65                              const Handle(Message_Report)& theReport);
66
67 //=======================================================================
68 //class    : BOPAlgo_PairOfShapeBoolean
69 //purpose  : 
70 //=======================================================================
71 class BOPAlgo_PairOfShapeBoolean : public BOPAlgo_Algo {
72
73  public:
74   DEFINE_STANDARD_ALLOC
75
76   BOPAlgo_PairOfShapeBoolean() : 
77     BOPAlgo_Algo(),
78     myFlag(Standard_False) {
79   }
80   //
81   virtual ~BOPAlgo_PairOfShapeBoolean() {
82   }
83   //
84   TopoDS_Shape& Shape1() {
85     return myShape1;
86   }
87   //
88   TopoDS_Shape& Shape2() {
89     return myShape2;
90   }
91   //
92   Standard_Boolean& Flag() {
93     return myFlag;
94   }
95   //
96   void SetContext(const Handle(IntTools_Context)& aContext) {
97     myContext=aContext;
98   }
99   //
100   const Handle(IntTools_Context)& Context()const {
101     return myContext;
102   }
103   //
104   virtual void Perform() {
105     BOPAlgo_Algo::UserBreak();
106     //  
107     const TopoDS_Face& aFj=*((TopoDS_Face*)&myShape1);
108     const TopoDS_Face& aFk=*((TopoDS_Face*)&myShape2);
109     myFlag=BOPTools_AlgoTools::AreFacesSameDomain(aFj, aFk, myContext, myFuzzyValue);
110   }
111   //
112  protected: 
113   Standard_Boolean myFlag;
114   TopoDS_Shape myShape1;
115   TopoDS_Shape myShape2;
116   Handle(IntTools_Context) myContext;
117 };
118 //
119 typedef NCollection_Vector<BOPAlgo_PairOfShapeBoolean> BOPAlgo_VectorOfPairOfShapeBoolean;
120
121 //=======================================================================
122 // BuilderFace
123 //
124 typedef NCollection_Vector<BOPAlgo_BuilderFace> BOPAlgo_VectorOfBuilderFace;
125
126 //=======================================================================
127 //class    : BOPAlgo_VFI
128 //purpose  : 
129 //=======================================================================
130 class BOPAlgo_VFI : public BOPAlgo_Algo {
131
132  public:
133   DEFINE_STANDARD_ALLOC
134   
135   BOPAlgo_VFI() :
136     BOPAlgo_Algo(),
137     myIsInternal(Standard_False) {
138   }
139   //
140   virtual ~BOPAlgo_VFI(){
141   }
142   //
143   void SetVertex(const TopoDS_Vertex& aV) {
144     myV=aV;
145   }
146   //
147   TopoDS_Vertex& Vertex() {
148     return myV;
149   }
150   //
151   void SetFace(const TopoDS_Face& aF) {
152     myF=aF;
153   }
154   //
155   TopoDS_Face& Face() {
156     return myF;
157   }
158   //
159   Standard_Boolean IsInternal()const {
160     return myIsInternal;
161   }
162   //
163   void SetContext(const Handle(IntTools_Context)& aContext) {
164     myContext=aContext;
165   }
166   //
167   const Handle(IntTools_Context)& Context()const {
168     return myContext;
169   }
170   //
171   virtual void Perform() {
172     Standard_Real aT1, aT2, dummy;
173     //
174     BOPAlgo_Algo::UserBreak();
175     Standard_Integer iFlag =
176       myContext->ComputeVF(myV, myF, aT1, aT2, dummy, myFuzzyValue);
177     myIsInternal = (iFlag == 0);
178   }
179   //
180  protected:
181   Standard_Boolean myIsInternal;
182   TopoDS_Vertex myV;
183   TopoDS_Face myF;
184   Handle(IntTools_Context) myContext;
185 };
186 //
187 typedef NCollection_Vector<BOPAlgo_VFI> BOPAlgo_VectorOfVFI; 
188
189 //=======================================================================
190 //function : FillImagesFaces
191 //purpose  : 
192 //=======================================================================
193 void BOPAlgo_Builder::FillImagesFaces()
194 {
195   BuildSplitFaces();
196   FillSameDomainFaces();
197   FillInternalVertices();
198 }
199 //=======================================================================
200 //function : BuildSplitFaces
201 //purpose  : 
202 //=======================================================================
203 void BOPAlgo_Builder::BuildSplitFaces()
204 {
205   Standard_Boolean bHasFaceInfo, bIsClosed, bIsDegenerated, bToReverse;
206   Standard_Integer i, j, k, aNbS, aNbPBIn, aNbPBOn, aNbPBSc, aNbAV, nSp;
207   TopoDS_Face aFF, aFSD;
208   TopoDS_Edge aSp, aEE;
209   TopAbs_Orientation anOriF, anOriE;
210   TopExp_Explorer aExp;
211   TopTools_ListIteratorOfListOfShape aIt;
212   TColStd_ListOfInteger aLIAV;
213   TopTools_MapOfShape aMFence;
214   Handle(NCollection_BaseAllocator) aAllocator;
215   BOPAlgo_VectorOfBuilderFace aVBF;
216   //
217   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~scope f
218   aAllocator=
219     NCollection_BaseAllocator::CommonBaseAllocator();
220   //
221   TopTools_ListOfShape aLE(aAllocator);
222   TopTools_MapOfShape aMDE(100, aAllocator);
223   //
224   // Build temporary map of faces images to avoid rebuilding
225   // of the faces without any IN or section edges
226   NCollection_IndexedDataMap<Standard_Integer, TopTools_ListOfShape> aFacesIm;
227   //
228   aNbS=myDS->NbSourceShapes();
229   //
230   for (i=0; i<aNbS; ++i) {
231     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
232     if (aSI.ShapeType()!=TopAbs_FACE) {
233       continue;
234     }
235     //
236     const TopoDS_Face& aF=(*(TopoDS_Face*)(&aSI.Shape()));
237     Standard_Boolean isUClosed = Standard_False,
238                      isVClosed = Standard_False,
239                      isChecked = Standard_False;
240     //
241     bHasFaceInfo=myDS->HasFaceInfo(i);
242     if(!bHasFaceInfo) {
243       continue;
244     }
245     //
246     const BOPDS_FaceInfo& aFI=myDS->FaceInfo(i);
247     //
248     const BOPDS_IndexedMapOfPaveBlock& aMPBIn=aFI.PaveBlocksIn();
249     const BOPDS_IndexedMapOfPaveBlock& aMPBOn=aFI.PaveBlocksOn();
250     const BOPDS_IndexedMapOfPaveBlock& aMPBSc=aFI.PaveBlocksSc();
251     aLIAV.Clear();
252     myDS->AloneVertices(i, aLIAV);
253     
254     aNbPBIn=aMPBIn.Extent();
255     aNbPBOn=aMPBOn.Extent();
256     aNbPBSc=aMPBSc.Extent();
257     aNbAV=aLIAV.Extent();
258     if (!aNbPBIn && !aNbPBOn && !aNbPBSc && !aNbAV) { // not compete
259       continue;
260     }
261
262     if (!aNbPBIn && !aNbPBSc)
263     {
264       // If there are any alone vertices to be put in the face,
265       // the new face has to be created even if the wires of the
266       // face have not been modified.
267
268       // It is also necessary to check if the face contains any internal edges,
269       // as such edges may split the face on parts and it is better
270       // to send the face be treated by the BuilderFace algorithm.
271       // In case of alone vertices the check for internals will be performed
272       // in the BuildDraftFace method.
273       Standard_Boolean hasInternals = Standard_False;
274       if (!aNbAV)
275       {
276         // Check if any wires of the face have been modified.
277         // If no modified and internal wires present in the face
278         // there is no need to create the new face.
279         Standard_Boolean hasModified = Standard_False;
280
281         TopoDS_Iterator aItW(aF);
282         for (; aItW.More(); aItW.Next())
283         {
284           TopoDS_Iterator itE(aItW.Value());
285           hasInternals = (itE.More() && (itE.Value().Orientation() == TopAbs_INTERNAL));
286           if (hasInternals)
287             break;
288
289           hasModified |= myImages.IsBound(aItW.Value());
290         }
291
292         if (!hasInternals && !hasModified)
293           continue;
294       }
295
296       if (!hasInternals)
297       {
298         // No internal parts for the face, so just build the draft face
299         // and keep it to pass directly into result.
300         // If the original face has any internal edges or multi-connected vertices,
301         // the draft face will be null, as such sub-shapes may split the face on parts
302         // (as in the case "bugs modalg_5 bug25245_1").
303         // The BuilderFace algorithm will be called in this case.
304         TopoDS_Face aFD = BuildDraftFace(aF, myImages, myContext, myReport);
305         if (!aFD.IsNull())
306         {
307           aFacesIm(aFacesIm.Add(i, TopTools_ListOfShape())).Append(aFD);
308           continue;
309         }
310       }
311     }
312
313     aMFence.Clear();
314     //
315     anOriF=aF.Orientation();
316     aFF=aF;
317     aFF.Orientation(TopAbs_FORWARD);
318     //
319     // 1. Fill the edges set for the face aFF -> LE
320     aLE.Clear();
321
322     // 1.1 Bounding edges
323     aExp.Init(aFF, TopAbs_EDGE);
324     for (; aExp.More(); aExp.Next()) {
325       const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aExp.Current()));
326       anOriE=aE.Orientation();
327       //
328       if (!myImages.IsBound(aE)) {
329         if (anOriE==TopAbs_INTERNAL) {
330           aEE=aE;
331           aEE.Orientation(TopAbs_FORWARD);
332           aLE.Append(aEE);
333           aEE.Orientation(TopAbs_REVERSED);
334           aLE.Append(aEE);
335         }
336         else {
337           aLE.Append(aE);
338         }
339
340         continue;
341       }
342
343       if(!isChecked)
344       {
345         const Handle(Geom_Surface) aSurf = BRep_Tool::Surface(aF);
346         GeomLib::IsClosed(aSurf, BRep_Tool::Tolerance(aE),
347           isUClosed, isVClosed);
348
349         isChecked = Standard_True;
350       }
351
352       bIsClosed = Standard_False;
353
354       if((isUClosed || isVClosed) && BRep_Tool::IsClosed(aE, aF)) 
355       {
356
357         Standard_Boolean isUIso = Standard_False, isVIso = Standard_False;
358         BOPTools_AlgoTools2D::IsEdgeIsoline(aE, aF, isUIso, isVIso);
359
360         bIsClosed = ((isUClosed && isUIso) || (isVClosed && isVIso));
361       }
362
363       bIsDegenerated=BRep_Tool::Degenerated(aE);
364
365       const TopTools_ListOfShape& aLIE=myImages.Find(aE);
366       aIt.Initialize(aLIE);
367       for (; aIt.More(); aIt.Next()) {
368         aSp=(*(TopoDS_Edge*)(&aIt.Value()));
369         if (bIsDegenerated) {
370           aSp.Orientation(anOriE);
371           aLE.Append(aSp);
372           continue;
373         }
374         //
375         if (anOriE==TopAbs_INTERNAL) {
376           aSp.Orientation(TopAbs_FORWARD);
377           aLE.Append(aSp);
378           aSp.Orientation(TopAbs_REVERSED);
379           aLE.Append(aSp);
380           continue;
381         }
382           //
383         if (bIsClosed) {
384           if (aMFence.Add(aSp)) {
385             if (!BRep_Tool::IsClosed(aSp, aF)){
386               BOPTools_AlgoTools3D::DoSplitSEAMOnFace(aSp, aF);
387             }
388             //
389             aSp.Orientation(TopAbs_FORWARD);
390             aLE.Append(aSp);
391             aSp.Orientation(TopAbs_REVERSED);
392             aLE.Append(aSp);
393           }// if (aMFence.Add(aSp))
394           continue;
395         }// if (bIsClosed){
396         //
397         aSp.Orientation(anOriE);
398         bToReverse=BOPTools_AlgoTools::IsSplitToReverseWithWarn(aSp, aE, myContext, myReport);
399         if (bToReverse) {
400           aSp.Reverse();
401         }
402         aLE.Append(aSp);
403       }// for (; aIt.More(); aIt.Next()) {
404     }// for (; aExp.More(); aExp.Next()) {
405     // 
406     //
407     // 1.2 In edges
408     for (j=1; j<=aNbPBIn; ++j) {
409       const Handle(BOPDS_PaveBlock)& aPB=aMPBIn(j);
410       nSp=aPB->Edge();
411       aSp=(*(TopoDS_Edge*)(&myDS->Shape(nSp)));
412       //
413       aSp.Orientation(TopAbs_FORWARD);
414       aLE.Append(aSp);
415       aSp.Orientation(TopAbs_REVERSED);
416       aLE.Append(aSp);
417     }
418     //
419     //
420     // 1.3 Section edges
421     for (j=1; j<=aNbPBSc; ++j) {
422       const Handle(BOPDS_PaveBlock)& aPB=aMPBSc(j);
423       nSp=aPB->Edge();
424       aSp=(*(TopoDS_Edge*)(&myDS->Shape(nSp)));
425       //
426       aSp.Orientation(TopAbs_FORWARD);
427       aLE.Append(aSp);
428       aSp.Orientation(TopAbs_REVERSED);
429       aLE.Append(aSp);
430     }
431     //
432     if (!myPaveFiller->NonDestructive()) {
433       // speed up for planar faces
434       BRepLib::BuildPCurveForEdgesOnPlane(aLE, aFF);
435     }
436     // 3 Build split faces
437     BOPAlgo_BuilderFace& aBF=aVBF.Appended();
438     aBF.SetFace(aF);
439     aBF.SetShapes(aLE);
440     aBF.SetRunParallel(myRunParallel);
441     aBF.SetProgressIndicator(*myProgressScope);
442     //
443   }// for (i=0; i<aNbS; ++i) {
444   //
445   //===================================================
446   BOPTools_Parallel::Perform (myRunParallel, aVBF);
447   //===================================================
448   //
449   Standard_Integer aNbBF = aVBF.Length();
450   for (k = 0; k < aNbBF; ++k)
451   {
452     BOPAlgo_BuilderFace& aBF = aVBF(k);
453     aFacesIm.Add(myDS->Index(aBF.Face()), aBF.Areas());
454     myReport->Merge(aBF.GetReport());
455   }
456
457   aNbBF = aFacesIm.Extent();
458   for (k = 1; k <= aNbBF; ++k)
459   {
460     const TopoDS_Face& aF = TopoDS::Face(myDS->Shape(aFacesIm.FindKey(k)));
461     anOriF = aF.Orientation();
462     const TopTools_ListOfShape& aLFR = aFacesIm(k);
463     //
464     TopTools_ListOfShape* pLFIm = myImages.Bound(aF, TopTools_ListOfShape());
465     aIt.Initialize(aLFR);
466     for (; aIt.More(); aIt.Next()) {
467       TopoDS_Shape& aFR=aIt.ChangeValue();
468       if (anOriF==TopAbs_REVERSED)
469         aFR.Orientation(TopAbs_REVERSED);
470       pLFIm->Append(aFR);
471     }
472   }
473   //
474   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~scope t
475 }
476
477 //=======================================================================
478 //function : AddEdgeSet
479 //purpose  : 
480 //=======================================================================
481 typedef
482   NCollection_IndexedDataMap<BOPTools_Set,
483                              TopTools_ListOfShape,
484                              BOPTools_SetMapHasher> BOPAlgo_IndexedDataMapOfSetListOfShape;
485
486 static void AddEdgeSet(const TopoDS_Shape& theS,
487                        BOPAlgo_IndexedDataMapOfSetListOfShape& theMap,
488                        const Handle(NCollection_BaseAllocator)& theAllocator)
489 {
490   // Make set
491   BOPTools_Set aSE;
492   aSE.Add(theS, TopAbs_EDGE);
493   // Add set to the map, keeping connection to the shape
494   TopTools_ListOfShape* pLF = theMap.ChangeSeek(aSE);
495   if (!pLF)
496     pLF = &theMap(theMap.Add(aSE, TopTools_ListOfShape(theAllocator)));
497   pLF->Append(theS);
498 }
499
500 //=======================================================================
501 //function : FillSameDomainFaces
502 //purpose  : 
503 //=======================================================================
504 void BOPAlgo_Builder::FillSameDomainFaces()
505 {
506   // It is necessary to analyze all Face/Face intersections
507   // and find all faces with equal sets of edges
508   const BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
509   Standard_Integer aNbFFs = aFFs.Length();
510   if (!aNbFFs)
511     return;
512
513   Handle(NCollection_BaseAllocator) aAllocator = new NCollection_IncAllocator;
514
515   // Vector to store the indices of faces for future sorting
516   // for making the SD face for the group from the face with
517   // smallest index in Data structure
518   NCollection_Vector<Standard_Integer> aFIVec(256, aAllocator);
519   // Fence map to avoid repeated checks of the same face.
520   TColStd_MapOfInteger aMFence(1, aAllocator);
521
522   // Fill the vector with indices of faces
523   for (Standard_Integer i = 0; i < aNbFFs; ++i)
524   {
525     const BOPDS_InterfFF& aFF = aFFs(i);
526     // get indices
527     Standard_Integer nF[2];
528     aFF.Indices(nF[0], nF[1]);
529     // store indices to the vector
530     for (Standard_Integer j = 0; j < 2; ++j)
531     {
532       if (!myDS->HasFaceInfo(nF[j]))
533         continue;
534
535       if (!aMFence.Add(nF[j]))
536         continue;
537
538       aFIVec.Appended() = nF[j];
539     }
540   }
541
542   // Sort the indices
543   std::sort(aFIVec.begin(), aFIVec.end());
544
545   // Data map of set of edges with all faces having this set
546   NCollection_IndexedDataMap<BOPTools_Set,
547                              TopTools_ListOfShape,
548                              BOPTools_SetMapHasher> anESetFaces(1, aAllocator);
549   // Map of planar bounded faces. If such faces have the same Edge set
550   // they are considered Same domain, without additional check.
551   TopTools_MapOfShape aMFPlanar(1, aAllocator);
552
553   Standard_Integer aNbF = aFIVec.Length();
554   for (Standard_Integer i = 0; i < aNbF; ++i)
555   {
556     const Standard_Integer nF = aFIVec(i);
557     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nF);
558     const TopoDS_Shape& aF = aSI.Shape();
559
560     Standard_Boolean bCheckPlanar = Standard_False;
561     {
562       // At this stage, context should contain adaptor for all intersected faces,
563       // so getting a type of the underlying surface should be done at no cost.
564       if (myContext->SurfaceAdaptor(TopoDS::Face(aF)).GetType() == GeomAbs_Plane)
565       {
566         // Check bounding box of the face - it should not be open in any side
567         const Bnd_Box& aBox = aSI.Box();
568         bCheckPlanar = !(aBox.IsOpenXmin() || aBox.IsOpenXmax() ||
569                          aBox.IsOpenYmin() || aBox.IsOpenYmax() ||
570                          aBox.IsOpenZmin() || aBox.IsOpenZmax());
571       }
572     }
573
574     const TopTools_ListOfShape* pLFSp = myImages.Seek(aF);
575     if (pLFSp)
576     {
577       TopTools_ListIteratorOfListOfShape aItLF(*pLFSp);
578       for (; aItLF.More(); aItLF.Next())
579       {
580         AddEdgeSet(aItLF.Value(), anESetFaces, aAllocator);
581         if (bCheckPlanar)
582           aMFPlanar.Add(aItLF.Value());
583       }
584     }
585     else
586     {
587       AddEdgeSet(aF, anESetFaces, aAllocator);
588       if (bCheckPlanar)
589         aMFPlanar.Add(aF);
590     }
591   }
592
593   // Store pairs of faces with equal set of edges to check if they are really Same Domain
594   BOPAlgo_VectorOfPairOfShapeBoolean aVPSB;
595
596   // Back and forth map of SD faces to make the blocks
597   TopTools_IndexedDataMapOfShapeListOfShape aDMSLS(1, aAllocator);
598
599   Standard_Integer aNbSets = anESetFaces.Extent();
600   for (Standard_Integer i = 1; i <= aNbSets; ++i)
601   {
602     const TopTools_ListOfShape& aLF = anESetFaces(i);
603     if (aLF.Extent() < 2)
604       continue;
605
606     // All possible pairs from <aLF> should be checked
607     TopTools_ListIteratorOfListOfShape aIt1(aLF);
608     for (; aIt1.More(); aIt1.Next())
609     {
610       const TopoDS_Shape& aF1 = aIt1.Value();
611       Standard_Boolean bCheckPlanar = aMFPlanar.Contains(aF1);
612
613       TopTools_ListIteratorOfListOfShape aIt2 = aIt1;
614       for (aIt2.Next(); aIt2.More(); aIt2.Next())
615       {
616         const TopoDS_Shape& aF2 = aIt2.Value();
617         if (bCheckPlanar && aMFPlanar.Contains(aF2))
618         {
619           // Consider planar bounded faces as Same Domain without additional check
620           BOPAlgo_Tools::FillMap<TopoDS_Shape, TopTools_ShapeMapHasher>(aF1, aF2, aDMSLS, aAllocator);
621           continue;
622         }
623         // Add pair for analysis
624         BOPAlgo_PairOfShapeBoolean& aPSB = aVPSB.Appended();
625         aPSB.Shape1() = aF1;
626         aPSB.Shape2() = aF2;
627         aPSB.SetFuzzyValue(myFuzzyValue);
628         aPSB.SetProgressIndicator(*myProgressScope);
629       }
630     }
631   }
632
633   //================================================================
634   // Perform analysis
635   BOPTools_Parallel::Perform (myRunParallel, aVPSB, myContext);
636   //================================================================
637
638   NCollection_List<TopTools_ListOfShape> aMBlocks(aAllocator);
639   // Fill map with SD faces to make the blocks
640   Standard_Integer aNbPairs = aVPSB.Length();
641   for (Standard_Integer i = 0; i < aNbPairs; ++i)
642   {
643     BOPAlgo_PairOfShapeBoolean& aPSB = aVPSB(i);
644     if (aPSB.Flag())
645       BOPAlgo_Tools::FillMap<TopoDS_Shape, TopTools_ShapeMapHasher>
646        (aPSB.Shape1(), aPSB.Shape2(), aDMSLS, aAllocator);
647   }
648   aVPSB.Clear();
649
650   // Make blocks of SD faces using the back and forth map
651   BOPAlgo_Tools::MakeBlocks<TopoDS_Shape, TopTools_ShapeMapHasher>
652     (aDMSLS, aMBlocks, aAllocator);
653
654   // Fill same domain faces map
655   NCollection_List<TopTools_ListOfShape>::Iterator aItB(aMBlocks);
656   for (; aItB.More(); aItB.Next())
657   {
658     const TopTools_ListOfShape& aLSD = aItB.Value();
659     // If the group contains some original faces, the one with minimal
660     // index in the DS will be chosen as the SD for the whole group.
661     // If there are no original faces in the group, the first face from
662     // the group will be used as the SD face.
663     // Such SD face will be representative of the whole group in the result.
664     TopoDS_Face* pFSD = NULL;
665     Standard_Integer nFMin = ::IntegerLast();
666     TopTools_ListIteratorOfListOfShape aItLF(aLSD);
667     for (; aItLF.More(); aItLF.Next())
668     {
669       const TopoDS_Shape& aF = aItLF.Value();
670       // Check the index of the face in DS
671       const Standard_Integer nF = myDS->Index(aF);
672       if (nF >= 0)
673       {
674         // The fact that the face is found in the DS, means that
675         // the face has not been change, and thus it is original one.
676         //
677         // Such face does not have any splits, but have an SD face.
678         // Consider it being split.
679         myImages.Bound(aF, TopTools_ListOfShape())->Append(aF);
680
681         // For the SD face chose the one with minimal index
682         if (nF < nFMin)
683         {
684           nFMin = nF;
685           pFSD = (TopoDS_Face*)&aF;
686         }
687       }
688     }
689
690     if (!pFSD)
691     {
692       // No original faces in the group, take the first one
693       pFSD = (TopoDS_Face*)&aLSD.First();
694     }
695
696     // Save all SD connections
697     aItLF.Initialize(aLSD);
698     for (; aItLF.More(); aItLF.Next())
699     {
700       const TopoDS_Shape& aF = aItLF.Value();
701       myShapesSD.Bind(aF, *pFSD);
702     }
703   }
704
705   // Update the map of images with SD faces and
706   // fill the map of origins.
707   Standard_Integer aNbS = myDS->NbSourceShapes();
708   for (Standard_Integer i = 0; i < aNbS; ++i)
709   {
710     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
711     if (aSI.ShapeType() != TopAbs_FACE)
712       continue;
713
714     const TopoDS_Shape& aF = aSI.Shape();
715     TopTools_ListOfShape* pLFIm = myImages.ChangeSeek(aF);
716     if (!pLFIm)
717       continue;
718
719     TopTools_ListIteratorOfListOfShape aItLFIm(*pLFIm);
720     for (; aItLFIm.More(); aItLFIm.Next())
721     {
722       TopoDS_Shape& aFIm = aItLFIm.ChangeValue();
723       const TopoDS_Shape* pFSD = myShapesSD.Seek(aFIm);
724       if (pFSD)
725         // Update image with SD face
726         aFIm = *pFSD;
727
728       // Fill the map of origins
729       TopTools_ListOfShape* pLFOr = myOrigins.ChangeSeek(aFIm);
730       if (!pLFOr)
731         pLFOr = myOrigins.Bound(aFIm, TopTools_ListOfShape());
732       pLFOr->Append(aF);
733     }
734   }
735
736   aMBlocks.Clear();
737   aDMSLS.Clear();
738 }
739 //=======================================================================
740 // function: FillImagesFaces1
741 // purpose: 
742 //=======================================================================
743 void BOPAlgo_Builder::FillInternalVertices()
744 {
745   // Vector of pairs of Vertex/Face for classification of the vertices
746   // relatively faces, and adding them as internal into the faces
747   BOPAlgo_VectorOfVFI aVVFI;
748
749   Standard_Integer aNbS = myDS->NbSourceShapes();
750   for (Standard_Integer i = 0; i < aNbS; ++i)
751   {
752     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
753     if (aSI.ShapeType() != TopAbs_FACE)
754       continue;
755
756     const TopoDS_Shape& aF = aSI.Shape();
757     const TopTools_ListOfShape* pLFIm = myImages.Seek(aF);
758     if (!pLFIm)
759       continue;
760
761     // Find vertices to add as internal into the splits
762     TColStd_ListOfInteger aLIAV;
763     myDS->AloneVertices(i, aLIAV);
764
765     // Add vertices and faces for classification
766     TColStd_ListIteratorOfListOfInteger aItLV(aLIAV);
767     for (; aItLV.More(); aItLV.Next())
768     {
769       TopoDS_Vertex aV = TopoDS::Vertex(myDS->Shape(aItLV.Value()));
770       aV.Orientation(TopAbs_INTERNAL);
771
772       TopTools_ListIteratorOfListOfShape aItLFIm(*pLFIm);
773       for (; aItLFIm.More(); aItLFIm.Next())
774       {
775         const TopoDS_Face& aFIm = TopoDS::Face(aItLFIm.Value());
776         // Make the pair
777         BOPAlgo_VFI& aVFI = aVVFI.Appended();
778         aVFI.SetVertex(aV);
779         aVFI.SetFace(aFIm);
780         aVFI.SetFuzzyValue(myFuzzyValue);
781         aVFI.SetProgressIndicator(*myProgressScope);
782       }
783     }
784   }
785
786   // Perform classification
787   //================================================================
788   BOPTools_Parallel::Perform (myRunParallel, aVVFI, myContext);
789   //================================================================
790
791   Standard_Integer aNbVFI = aVVFI.Length();
792   for (Standard_Integer i = 0; i < aNbVFI; ++i)
793   {
794     BOPAlgo_VFI& aVFI = aVVFI(i);
795     if (aVFI.IsInternal())
796     {
797       TopoDS_Vertex& aV = aVFI.Vertex();
798       TopoDS_Face& aF = aVFI.Face();
799       BRep_Builder().Add(aF, aV);
800     }
801   }
802 }
803 //=======================================================================
804 //function : HasMultiConnected
805 //purpose  : Checks if the edge has multi-connected vertices.
806 //=======================================================================
807 static Standard_Boolean HasMultiConnected(const TopoDS_Edge& theEdge,
808                                           TopTools_DataMapOfShapeListOfShape& theMap)
809 {
810   TopoDS_Iterator itV(theEdge);
811   for (; itV.More(); itV.Next())
812   {
813     const TopoDS_Shape& aV = itV.Value();
814     TopTools_ListOfShape *pList = theMap.ChangeSeek(aV);
815     if (!pList)
816     {
817       pList = theMap.Bound(aV, TopTools_ListOfShape());
818       pList->Append(theEdge);
819     }
820     else
821     {
822       // The list is expected to be 1-2 elements long,
823       // thus using "Contains" is safe.
824       if (!pList->Contains(theEdge))
825         pList->Append(theEdge);
826
827       if (pList->Extent() > 2)
828         return Standard_True;
829     }
830   }
831   return Standard_False;
832 }
833 //=======================================================================
834 //function : BuildDraftFace
835 //purpose  : Build draft faces, updating the bounding edges,
836 //           according to the information stored into the <theImages> map
837 //=======================================================================
838 TopoDS_Face BuildDraftFace(const TopoDS_Face& theFace,
839                            const TopTools_DataMapOfShapeListOfShape& theImages,
840                            Handle(IntTools_Context)& theCtx,
841                            const Handle(Message_Report)& theReport)
842 {
843   BRep_Builder aBB;
844   // Take the information from the original face
845   TopLoc_Location aLoc;
846   const Handle(Geom_Surface)& aS = BRep_Tool::Surface(theFace, aLoc);
847   const Standard_Real aTol = BRep_Tool::Tolerance(theFace);
848   // Make the new face, without any wires
849   TopoDS_Face aDraftFace;
850   aBB.MakeFace(aDraftFace, aS, aLoc, aTol);
851
852   // Check if the thin face can be split by a vertex - in this case
853   // this vertex will be contained in more than two edges. Thus, count
854   // the vertices appearance, and if the multi-connexity is met return
855   // the null face to use the BuilderFace algorithm for checking the
856   // possibility of split.
857   TopTools_DataMapOfShapeListOfShape aVerticesCounter;
858
859   // Check that the edges of the initial face have not been unified during intersection.
860   // Otherwise, it will be necessary to check validity of the new wires.
861   TopTools_MapOfShape aMEdges;
862
863   // Update wires of the original face and add them to draft face
864   TopoDS_Iterator aItW(theFace.Oriented(TopAbs_FORWARD));
865   for (; aItW.More(); aItW.Next())
866   {
867     const TopoDS_Shape& aW = aItW.Value();
868     if (aW.ShapeType() != TopAbs_WIRE)
869       continue;
870
871     // Rebuild wire using images of edges
872     TopoDS_Iterator aItE(aW.Oriented(TopAbs_FORWARD));
873     if (!aItE.More())
874       continue;
875
876     TopoDS_Wire aNewWire;
877     aBB.MakeWire(aNewWire);
878
879     for (; aItE.More(); aItE.Next())
880     {
881       const TopoDS_Edge& aE = TopoDS::Edge(aItE.Value());
882
883       TopAbs_Orientation anOriE = aE.Orientation();
884       if (anOriE == TopAbs_INTERNAL)
885       {
886         // The internal edges could split the original face on halves.
887         // Thus, use the BuilderFace algorithm to build the new face.
888         return TopoDS_Face();
889       }
890
891       // Check if the original edge is degenerated
892       Standard_Boolean bIsDegenerated = BRep_Tool::Degenerated(aE);
893       // Check if the original edge is closed on the face
894       Standard_Boolean bIsClosed = BRep_Tool::IsClosed(aE, theFace);
895
896       // Check for the splits of the edge
897       const TopTools_ListOfShape* pLEIm = theImages.Seek(aE);
898       if (!pLEIm)
899       {
900         // Check if the edge has multi-connected vertices
901         if (!bIsDegenerated && HasMultiConnected(aE, aVerticesCounter))
902           return TopoDS_Face();
903
904         // Check edges unification
905         if (!bIsClosed && !aMEdges.Add(aE))
906           return TopoDS_Face();
907
908         aBB.Add(aNewWire, aE);
909         continue;
910       }
911
912       TopTools_ListIteratorOfListOfShape aItLEIm(*pLEIm);
913       for (; aItLEIm.More(); aItLEIm.Next())
914       {
915         TopoDS_Edge& aSp = TopoDS::Edge(aItLEIm.Value());
916
917         // Check if the split has multi-connected vertices
918         if (!bIsDegenerated && HasMultiConnected(aSp, aVerticesCounter))
919           return TopoDS_Face();
920
921         // Check edges unification
922         if (!bIsClosed && !aMEdges.Add(aSp))
923           return TopoDS_Face();
924
925         aSp.Orientation(anOriE);
926         if (bIsDegenerated)
927         {
928           aBB.Add(aNewWire, aSp);
929           continue;
930         }
931
932         // If the original edge is closed on the face check closeness
933         // of the split edge and if it is not closed make the second PCurve
934         if (bIsClosed && !BRep_Tool::IsClosed(aSp, theFace))
935           BOPTools_AlgoTools3D::DoSplitSEAMOnFace(aSp, theFace);
936
937         // Check if the split should be reversed
938         if (BOPTools_AlgoTools::IsSplitToReverseWithWarn(aSp, aE, theCtx, theReport))
939           aSp.Reverse();
940
941         aBB.Add(aNewWire, aSp);
942       }
943     }
944
945     aNewWire.Orientation(aW.Orientation());
946     aNewWire.Closed(BRep_Tool::IsClosed(aNewWire));
947     aBB.Add(aDraftFace, aNewWire);
948   }
949
950   if (theFace.Orientation() == TopAbs_REVERSED)
951     aDraftFace.Reverse();
952
953   return aDraftFace;
954 }