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