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