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