0024157: Parallelization of assembly part of BO
[occt.git] / src / BOPAlgo / BOPAlgo_Builder_2.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 2010-2012 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 // The content of this file is subject to the Open CASCADE Technology Public
8 // License Version 6.5 (the "License"). You may not use the content of this file
9 // except in compliance with the License. Please obtain a copy of the License
10 // at http://www.opencascade.org and read it completely before using this file.
11 //
12 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
13 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
14 //
15 // The Original Code and all software distributed under the License is
16 // distributed on an "AS IS" basis, without warranty of any kind, and the
17 // Initial Developer hereby disclaims all such warranties, including without
18 // limitation, any warranties of merchantability, fitness for a particular
19 // purpose or non-infringement. Please see the License for the specific terms
20 // and conditions governing the rights and limitations under the License.
21
22 #include <BOPAlgo_Builder.ixx>
23
24 #include <NCollection_IncAllocator.hxx>
25
26 #include <TopoDS_Shape.hxx>
27 #include <TopoDS_Face.hxx>
28 #include <TopoDS_Edge.hxx>
29 #include <TopoDS_Vertex.hxx>
30 #include <TopoDS_Compound.hxx>
31
32 #include <BRep_Tool.hxx>
33 #include <BRep_Builder.hxx>
34
35 #include <TopExp_Explorer.hxx>
36
37 #include <BOPCol_ListOfShape.hxx>
38 #include <BOPCol_ListOfInteger.hxx>
39 #include <BOPCol_MapOfInteger.hxx>
40 #include <BOPCol_DataMapOfIntegerListOfShape.hxx>
41 #include <BOPCol_DataMapOfShapeShape.hxx>
42
43 #include <BOPInt_Context.hxx>
44
45 #include <BOPDS_PaveBlock.hxx>
46 #include <BOPDS_ShapeInfo.hxx>
47 #include <BOPDS_DS.hxx>
48 #include <BOPDS_FaceInfo.hxx>
49 #include <BOPDS_MapOfPaveBlock.hxx>
50 #include <BOPDS_VectorOfInterfFF.hxx>
51 #include <BOPDS_Interf.hxx>
52 #include <BOPDS_VectorOfCurve.hxx>
53 #include <BOPDS_VectorOfPoint.hxx>
54
55 #include <BOPTools.hxx>
56 #include <BOPTools_AlgoTools.hxx>
57 #include <BOPTools_AlgoTools2D.hxx>
58 #include <BOPTools_AlgoTools3D.hxx>
59 #include <BOPAlgo_BuilderFace.hxx>
60 #include <BOPTools_CoupleOfShape.hxx>
61 #include <BOPTools_ListOfCoupleOfShape.hxx>
62 #include <BOPTools_MapOfSet.hxx>
63 #include <BOPTools_DataMapOfShapeSet.hxx>
64 #include <BOPAlgo_Builder_2Cnt.hxx>
65
66 static
67   Standard_Boolean HasPaveBlocksOnIn(const BOPDS_FaceInfo& aFI1,
68                                      const BOPDS_FaceInfo& aFI2);
69 static
70   void FillMap(const TopoDS_Shape& aS1,
71                const TopoDS_Shape& aS2,
72                BOPCol_IndexedDataMapOfShapeListOfShape& aDMSLS,
73                Handle(NCollection_IncAllocator)& aAllocator);
74 static
75   void MakeBlocksCnx(const BOPCol_IndexedDataMapOfShapeListOfShape& aMILI,
76                      BOPCol_DataMapOfIntegerListOfShape& aMBlocks,
77                      Handle(NCollection_IncAllocator)& aAllocator);
78
79
80 //=======================================================================
81 //function : FillImagesFaces
82 //purpose  : 
83 //=======================================================================
84 void BOPAlgo_Builder::FillImagesFaces()
85 {
86   myErrorStatus=0;
87   //
88   BuildSplitFaces();
89   FillSameDomainFaces();
90   FillImagesFaces1();
91 }
92 //=======================================================================
93 //function : BuildSplitFaces
94 //purpose  : 
95 //=======================================================================
96 void BOPAlgo_Builder::BuildSplitFaces()
97 {
98   Standard_Boolean bHasFaceInfo, bIsClosed, bIsDegenerated, bToReverse;
99   Standard_Integer i, j, k, aNbS, aNbPBIn, aNbPBOn, aNbPBSc, aNbAV, nSp;
100   Standard_Boolean bRunParallel;
101   Standard_Size aNbBF;
102   TopoDS_Face aFF, aFSD;
103   TopoDS_Edge aSp, aEE;
104   TopAbs_Orientation anOriF, anOriE;
105   TopExp_Explorer aExp;
106   BOPCol_ListIteratorOfListOfShape aIt;
107   BOPCol_ListOfInteger aLIAV;
108   BOPCol_MapOfShape aMFence;
109   Handle(NCollection_BaseAllocator) aAllocator;
110   BOPCol_ListOfShape aLFIm(myAllocator);
111   BOPCol_MapIteratorOfMapOfShape aItMS;
112   BOPAlgo_VectorOfBuilderFace aVBF;
113   //
114   myErrorStatus=0;
115   //
116   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~scope f
117   aAllocator=new NCollection_IncAllocator();
118   //
119   BOPCol_ListOfShape aLE(aAllocator);
120   BOPCol_MapOfShape aMDE(100, aAllocator);
121   //
122   aNbS=myDS->NbSourceShapes();
123   //
124   for (i=0; i<aNbS; ++i) {
125     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
126     if (aSI.ShapeType()!=TopAbs_FACE) {
127       continue;
128     }
129     //
130     const TopoDS_Face& aF=(*(TopoDS_Face*)(&aSI.Shape()));
131     //
132     bHasFaceInfo=myDS->HasFaceInfo(i);
133     if(!bHasFaceInfo) {
134       continue;
135     }
136     //
137     const BOPDS_FaceInfo& aFI=myDS->FaceInfo(i);
138     //
139     const BOPDS_IndexedMapOfPaveBlock& aMPBIn=aFI.PaveBlocksIn();
140     const BOPDS_IndexedMapOfPaveBlock& aMPBOn=aFI.PaveBlocksOn();
141     const BOPDS_IndexedMapOfPaveBlock& aMPBSc=aFI.PaveBlocksSc();
142     aLIAV.Clear();
143     myDS->AloneVertices(i, aLIAV);
144     
145     aNbPBIn=aMPBIn.Extent();
146     aNbPBOn=aMPBOn.Extent();
147     aNbPBSc=aMPBSc.Extent();
148     aNbAV=aLIAV.Extent();
149     if (!aNbPBIn && !aNbPBOn && !aNbPBSc && !aNbAV) { // not compete
150       continue;
151     }
152     //
153     aMFence.Clear();
154     //
155     anOriF=aF.Orientation();
156     aFF=aF;
157     aFF.Orientation(TopAbs_FORWARD);
158     //
159     
160     //
161     // 1. Fill the egdes set for the face aFF -> LE
162     aLE.Clear();
163     //
164     //
165     // 1.1 Bounding edges
166     aExp.Init(aFF, TopAbs_EDGE);
167     for (; aExp.More(); aExp.Next()) {
168       const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aExp.Current()));
169       anOriE=aE.Orientation();
170       bIsDegenerated=BRep_Tool::Degenerated(aE);
171       bIsClosed=BRep_Tool::IsClosed(aE, aF);
172       //
173       if (!myImages.IsBound(aE)) {
174         if (anOriE==TopAbs_INTERNAL) {
175           aEE=aE;
176           aEE.Orientation(TopAbs_FORWARD);
177           aLE.Append(aEE);
178           aEE.Orientation(TopAbs_REVERSED);
179           aLE.Append(aEE);
180         }
181         else {
182           aLE.Append(aE);
183         }
184       }
185       else {//else 1
186         const BOPCol_ListOfShape& aLIE=myImages.Find(aE);
187         aIt.Initialize(aLIE);
188         for (; aIt.More(); aIt.Next()) {
189           aSp=(*(TopoDS_Edge*)(&aIt.Value()));
190           if (bIsDegenerated) {
191             aSp.Orientation(anOriE);
192             aLE.Append(aSp);
193             continue;
194           }
195           //
196           if (anOriE==TopAbs_INTERNAL) {
197             aSp.Orientation(TopAbs_FORWARD);
198             aLE.Append(aSp);
199             aSp.Orientation(TopAbs_REVERSED);
200             aLE.Append(aSp);
201             continue;
202           }
203           //
204           if (bIsClosed) {
205             if (aMFence.Add(aSp)) {
206               if (!BRep_Tool::IsClosed(aSp, aF)){
207                 BOPTools_AlgoTools3D::DoSplitSEAMOnFace(aSp, aF);
208                 }
209               //
210               aSp.Orientation(TopAbs_FORWARD);
211               aLE.Append(aSp);
212               aSp.Orientation(TopAbs_REVERSED);
213               aLE.Append(aSp);
214             }// if (aMFence.Add(aSp))
215             continue;
216           }// if (bIsClosed){
217           //
218           aSp.Orientation(anOriE);
219           bToReverse=BOPTools_AlgoTools::IsSplitToReverse(aSp, aE, myContext);
220           if (bToReverse) {
221             aSp.Reverse();
222           }
223           aLE.Append(aSp);
224         }// for (; aIt.More(); aIt.Next()) {
225       }// else 1
226     }// for (; aExp.More(); aExp.Next()) {
227     // 
228     //
229     // 1.2 In edges
230     for (j=1; j<=aNbPBIn; ++j) {
231       const Handle(BOPDS_PaveBlock)& aPB=aMPBIn(j);
232       nSp=aPB->Edge();
233       aSp=(*(TopoDS_Edge*)(&myDS->Shape(nSp)));
234       //
235       aSp.Orientation(TopAbs_FORWARD);
236       aLE.Append(aSp);
237       aSp.Orientation(TopAbs_REVERSED);
238       aLE.Append(aSp);
239     }
240     //
241     //
242     // 1.3 Section edges
243     for (j=1; j<=aNbPBSc; ++j) {
244       const Handle(BOPDS_PaveBlock)& aPB=aMPBSc(j);
245       nSp=aPB->Edge();
246       aSp=(*(TopoDS_Edge*)(&myDS->Shape(nSp)));
247       //
248       aSp.Orientation(TopAbs_FORWARD);
249       aLE.Append(aSp);
250       aSp.Orientation(TopAbs_REVERSED);
251       aLE.Append(aSp);
252     }
253     //
254     BOPTools_AlgoTools2D::BuildPCurveForEdgesOnPlane (aLE, aFF);
255     //
256     // 3 Build split faces
257     BOPAlgo_BuilderFace& aBF=aVBF.Append1();
258     aBF.SetFace(aF);
259     aBF.SetShapes(aLE);
260     //
261   }// for (i=0; i<aNbS; ++i) {
262   //
263   aNbBF=aVBF.Extent();
264   //
265   //===================================================
266   BOPAlgo_BuilderFaceCnt::Perform(myRunParallel, aVBF);
267   //===================================================
268   //
269   for (k=0; k<(Standard_Integer)aNbBF; ++k) {
270     aLFIm.Clear();
271     //
272     BOPAlgo_BuilderFace& aBF=aVBF(k);
273     TopoDS_Face aF=aBF.Face();
274     anOriF=aBF.Orientation();
275     aF.Orientation(anOriF);
276     //
277     const BOPCol_ListOfShape& aLFR=aBF.Areas();
278     aIt.Initialize(aLFR);
279     for (; aIt.More(); aIt.Next()) {
280       TopoDS_Shape& aFR=aIt.ChangeValue();
281       if (anOriF==TopAbs_REVERSED) {
282         aFR.Orientation(TopAbs_REVERSED);
283       }
284       //aFR.Orientation(anOriF);
285       aLFIm.Append(aFR);
286     }
287     //
288     mySplits.Bind(aF, aLFIm); 
289   }// for (k=0; k<aNbBF; ++k) {
290   //
291   aAllocator.Nullify();
292   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~scope t
293 }
294 //=======================================================================
295 //function : FillSameDomainFaces
296 //purpose  : 
297 //=======================================================================
298 void BOPAlgo_Builder::FillSameDomainFaces()
299 {
300   Standard_Boolean bFlag;
301   Standard_Integer i, j, k, aNbFFs, aNbCurves, aNbPoints, nF1, nF2, aNbS;
302   Handle(NCollection_IncAllocator) aAllocator;
303   BOPCol_ListIteratorOfListOfShape aItF;
304   BOPCol_MapOfShape aMFence;
305   BOPAlgo_IndexedDataMapOfSetInteger aIDMSS;
306   BOPAlgo_VectorOfVectorOfShape aVVS;
307 //
308   myErrorStatus=0;
309   //
310   const BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
311   //
312   aNbFFs=aFFs.Extent();
313   if (!aNbFFs) {
314     return;
315   }
316   //
317   for (i=0; i<aNbFFs; ++i) {
318     const BOPDS_InterfFF& aFF=aFFs(i);
319     aFF.Indices(nF1, nF2);
320     //
321     const BOPDS_VectorOfCurve& aCurves=aFF.Curves();
322     aNbCurves=aCurves.Extent();
323     if (aNbCurves) {
324       //
325       bFlag=Standard_False;
326       for (j=0; j<aNbCurves; ++j) {
327         const BOPDS_Curve& aNC=aCurves.Value(j);
328         bFlag=aNC.HasEdge();
329         if (bFlag) {
330           break;
331         }
332       }
333       if (bFlag) {
334         continue;
335       }
336       //continue;
337     }
338     //
339     const BOPDS_VectorOfPoint& aPoints=aFF.Points();
340     aNbPoints=aPoints.Extent();
341     if (aNbPoints) {
342       continue;
343     }
344     //
345     if (!myDS->HasFaceInfo(nF1) || !myDS->HasFaceInfo(nF2) ) {
346       continue;
347     }
348     //
349     const BOPDS_FaceInfo& aFI1=myDS->FaceInfo(nF1);
350     const BOPDS_FaceInfo& aFI2=myDS->FaceInfo(nF2);
351     //
352     const TopoDS_Shape& aF1=myDS->Shape(nF1);
353     const TopoDS_Shape& aF2=myDS->Shape(nF2);
354     //
355     bFlag=HasPaveBlocksOnIn(aFI1, aFI2);
356     bFlag=bFlag && (mySplits.IsBound(aF1) && mySplits.IsBound(aF2));
357     //
358     if (bFlag) {
359       for (k=0; k<2; ++k) {
360         const TopoDS_Shape& aF=(!k) ? aF1 : aF2;
361         const BOPCol_ListOfShape& aLF=mySplits.Find(aF);
362         //
363         aItF.Initialize(aLF);
364         for (; aItF.More(); aItF.Next()) {
365           const TopoDS_Shape& aFx=aItF.Value();
366           //
367           if (aMFence.Add(aFx)) {
368             BOPTools_Set aSTx;
369             //
370             aSTx.AddEdges(aFx);
371             //
372             if (!aIDMSS.Contains(aSTx)) {
373               BOPAlgo_VectorOfShape& aVS=aVVS.Append1(); 
374               aVS.Append(aFx);
375               //
376               j=aVVS.Extent()-1;
377               aIDMSS.Add (aSTx, j);
378             }
379             else {
380               j=aIDMSS.ChangeFromKey(aSTx);
381               BOPAlgo_VectorOfShape& aVS=aVVS(j);
382               aVS.Append(aFx);
383             }
384           }
385         }
386       }
387     }// if (bFlag) {
388     else {// if (!bFlag) 
389       BOPTools_Set aST1, aST2;
390       //
391       aST1.AddEdges(aF1);
392       aST2.AddEdges(aF2);
393       //
394       if (aST1.IsEqual(aST2)) {
395         if (!aIDMSS.Contains(aST1)) {
396           BOPAlgo_VectorOfShape& aVS=aVVS.Append1(); 
397           if (aMFence.Add(aF1)) {
398             aVS.Append(aF1);
399           }
400           if (aMFence.Add(aF2)) {
401             aVS.Append(aF2);
402           }
403           //
404           k=aVVS.Extent()-1;
405           aIDMSS.Add (aST1, k);
406         }
407         else {
408           k=aIDMSS.ChangeFromKey(aST1);
409           BOPAlgo_VectorOfShape& aVS=aVVS(k);
410           if (aMFence.Add(aF1)) {
411             aVS.Append(aF1);
412           }
413           if (aMFence.Add(aF2)) {
414             aVS.Append(aF2);
415           }
416         }
417       }//if (aST1.IsEqual(aST2)) {
418     }// else {// if (!bFlag) 
419     //
420   }// for (i=0; i<aNbFFs; ++i) {
421   //
422   aIDMSS.Clear();
423   //
424   Standard_Boolean bFlagSD;
425   Standard_Integer aNbVPSB, aNbVVS, aNbF, aNbF1;
426   BOPAlgo_VectorOfPairOfShapeBoolean aVPSB;
427   //
428   aNbVVS=aVVS.Extent();
429   for (i=0; i<aNbVVS; ++i) {
430     const BOPAlgo_VectorOfShape& aVS=aVVS(i);
431     aNbF=aVS.Extent();
432     if (aNbF<2) {
433       continue;
434     }
435     //
436     aNbF1=aNbF-1;
437     for (j=0; j<aNbF1; ++j) {
438       const TopoDS_Shape& aFj=aVS(j);
439       for (k=j+1; k<aNbF; ++k) {
440         const TopoDS_Shape& aFk=aVS(k);
441         BOPAlgo_PairOfShapeBoolean& aPSB=aVPSB.Append1();
442         aPSB.Shape1()=aFj;
443         aPSB.Shape2()=aFk;
444       }
445     }
446   }
447   //====================================================
448   BOPAlgo_BuilderSDFaceCnt::Perform(myRunParallel, aVPSB);
449   //====================================================
450   aAllocator=new NCollection_IncAllocator();
451   BOPCol_IndexedDataMapOfShapeListOfShape aDMSLS(100, aAllocator);
452   BOPCol_DataMapOfIntegerListOfShape aMBlocks(100, aAllocator);
453   //
454   aNbVPSB=aVPSB.Extent();
455   for (i=0; i<aNbVPSB; ++i) {
456     BOPAlgo_PairOfShapeBoolean& aPSB=aVPSB(i);
457     bFlagSD=aPSB.Flag();
458     if (bFlagSD) {
459       const TopoDS_Shape& aFj=aPSB.Shape1();
460       const TopoDS_Shape& aFk=aPSB.Shape2();
461       FillMap(aFj, aFk, aDMSLS, aAllocator);
462     }
463   }
464   aVPSB.Clear();
465   //
466   // 2. Make blocks
467   MakeBlocksCnx(aDMSLS, aMBlocks, aAllocator);
468   //
469   // 3. Fill same domain faces map -> aMSDF
470   aNbS = aMBlocks.Extent();
471   for (i=0; i<aNbS; ++i) {
472     const BOPCol_ListOfShape& aLSD=aMBlocks.Find(i);
473     if (aLSD.IsEmpty()) {
474       continue;
475     }
476     //
477     const TopoDS_Shape& aFSD1=aLSD.First();
478     aItF.Initialize(aLSD);
479     for (; aItF.More(); aItF.Next()) {
480       const TopoDS_Shape& aFSD=aItF.Value();
481       myShapesSD.Bind(aFSD, aFSD1);
482       //
483       // If the face has no splits but are SD face,
484       // it is considered as splitted face
485       if (!mySplits.IsBound(aFSD)) {
486         BOPCol_ListOfShape aLS;
487         aLS.Append(aFSD);
488         mySplits.Bind(aFSD, aLS);
489       }
490     }
491   }
492   aMBlocks.Clear();
493   aDMSLS.Clear();
494   aAllocator.Nullify();
495 }
496 //=======================================================================
497 // function: FillImagesFaces1
498 // purpose: 
499 //=======================================================================
500 void BOPAlgo_Builder::FillImagesFaces1()
501 {
502   Standard_Integer i, aNbS, iSense;
503   TopoDS_Face aFSD;
504   BOPCol_ListOfInteger aLIAV;
505   BOPCol_ListOfShape aLFIm;
506   BOPCol_ListIteratorOfListOfShape aItLS;
507   //
508   aNbS=myDS->NbSourceShapes();
509   for (i=0; i<aNbS; ++i) {
510     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
511     if (aSI.ShapeType()!=TopAbs_FACE) {
512       continue;
513     }
514     //
515     const TopoDS_Face& aF=(*(TopoDS_Face*)(&aSI.Shape()));
516     //
517     if (!mySplits.IsBound(aF)) {
518       continue;
519     }
520     //
521     aLIAV.Clear();
522     myDS->AloneVertices(i, aLIAV);
523     aLFIm.Clear();
524     //
525     const BOPCol_ListOfShape& aLSp=mySplits.Find(aF);
526     aItLS.Initialize(aLSp);
527     for (; aItLS.More(); aItLS.Next()) {
528       const TopoDS_Face& aFSp=(*(TopoDS_Face*)(&aItLS.Value()));
529       if (!myShapesSD.IsBound(aFSp)) {
530         aLFIm.Append(aFSp);
531       }
532       else {
533         aFSD=(*(TopoDS_Face*)(&myShapesSD.Find(aFSp)));
534         iSense=BOPTools_AlgoTools::Sense(aFSp, aFSD);
535         if (iSense<0) {
536           aFSD.Reverse();
537         }
538         aLFIm.Append(aFSD);
539       }
540     }
541     //
542     FillInternalVertices(aLFIm, aLIAV);
543     //
544     myImages.Bind(aF, aLFIm); 
545     //
546     //fill myOrigins
547     aItLS.Initialize(aLFIm);
548     for (; aItLS.More(); aItLS.Next()) {
549       const TopoDS_Face& aFSp=(*(TopoDS_Face*)(&aItLS.Value()));
550       myOrigins.Bind(aFSp, aF);
551     }
552   }// for (i=0; i<aNbS; ++i) {
553 }
554 //=======================================================================
555 // function: FillInternalVertices
556 // purpose: 
557 //=======================================================================
558 void BOPAlgo_Builder::FillInternalVertices(BOPCol_ListOfShape& aLFIm,
559                                            BOPCol_ListOfInteger& aLIAV)
560 {
561   Standard_Integer nV, iFlag;
562   Standard_Real aU1, aU2;
563   TopoDS_Vertex aV;
564   BRep_Builder aBB;
565   BOPCol_ListIteratorOfListOfInteger aItV;
566   BOPCol_ListIteratorOfListOfShape aItF;
567   //
568   aItV.Initialize(aLIAV);
569   for (; aItV.More(); aItV.Next()) {
570     nV=aItV.Value();
571     aV=(*(TopoDS_Vertex*)(&myDS->Shape(nV)));
572     aV.Orientation(TopAbs_INTERNAL);
573     //
574     aItF.Initialize(aLFIm);
575     for (; aItF.More(); aItF.Next()) {
576       TopoDS_Face& aF=(*(TopoDS_Face*)(&aItF.Value()));
577       iFlag=myContext->ComputeVF(aV, aF, aU1, aU2);
578       if (!iFlag) {
579         aBB.Add(aF, aV);
580         break;
581       }
582     }
583   }
584 }
585 //=======================================================================
586 //function : MakeBlocksCnx
587 //purpose  : 
588 //=======================================================================
589 void MakeBlocksCnx(const BOPCol_IndexedDataMapOfShapeListOfShape& aMILI,
590                    BOPCol_DataMapOfIntegerListOfShape& aMBlocks,
591                    Handle(NCollection_IncAllocator)& aAllocator)
592 {
593   Standard_Integer aNbV, aNbVS, aNbVP, aNbEC, k, i, j;
594   BOPCol_ListIteratorOfListOfShape aItLI;
595   //
596   BOPCol_MapOfShape aMVS(100, aAllocator);
597   BOPCol_IndexedMapOfShape aMEC(100, aAllocator);
598   BOPCol_IndexedMapOfShape aMVP(100, aAllocator);
599   BOPCol_IndexedMapOfShape aMVAdd(100, aAllocator);
600   //
601   aNbV=aMILI.Extent();
602   //
603   for (k=0,i=1; i<=aNbV; ++i) {
604     aNbVS=aMVS.Extent();
605     if (aNbVS==aNbV) {
606       break;
607     }
608     //
609     const TopoDS_Shape& nV=aMILI.FindKey(i);
610     if (aMVS.Contains(nV)){
611       continue;
612     }
613     aMVS.Add(nV);
614     //
615     aMEC.Clear();
616     aMVP.Clear();
617     aMVAdd.Clear();
618     //
619     aMVP.Add(nV);
620     for(;;) {
621       aNbVP=aMVP.Extent();
622       for (j=1; j<=aNbVP; ++j) {
623         const TopoDS_Shape& nVP=aMVP(j);
624         const BOPCol_ListOfShape& aLV=aMILI.FindFromKey(nVP);
625         aItLI.Initialize(aLV);
626         for (; aItLI.More(); aItLI.Next()) {
627           const TopoDS_Shape& nVx=aItLI.Value();
628           if (aMEC.Contains(nVx)) {
629             continue;
630           }
631           //
632           aMVS.Add(nVx);
633           aMEC.Add(nVx);
634           aMVAdd.Add(nVx);
635         }
636       }
637       //
638       aNbVP=aMVAdd.Extent();
639       if (!aNbVP) {
640         break; // from while(1)
641       }
642       //
643       aMVP.Clear();
644       for (j=1; j<=aNbVP; ++j) {
645         aMVP.Add(aMVAdd(j));
646       }
647       aMVAdd.Clear();
648     }//while(1) {
649     //
650     BOPCol_ListOfShape aLIx(aAllocator);
651     //
652     aNbEC = aMEC.Extent();
653     for (j=1; j<=aNbEC; ++j) {
654       const TopoDS_Shape& nVx=aMEC(j);
655       aLIx.Append(nVx);
656     }
657     //
658     aMBlocks.Bind(k, aLIx);
659     ++k;
660   }//for (k=0,i=1; i<=aNbV; ++i)
661   aMVAdd.Clear();
662   aMVP.Clear();
663   aMEC.Clear();
664   aMVS.Clear();
665 }
666
667 //=======================================================================
668 //function : FillMap
669 //purpose  : 
670 //=======================================================================
671 void FillMap(const TopoDS_Shape& aS1,
672              const TopoDS_Shape& aS2,
673              BOPCol_IndexedDataMapOfShapeListOfShape& aDMSLS,
674              Handle(NCollection_IncAllocator)& aAllocator)
675 {
676   if (aDMSLS.Contains(aS1)) {
677     BOPCol_ListOfShape& aLS=aDMSLS.ChangeFromKey(aS1);
678     aLS.Append(aS2);
679   }
680   else {
681     BOPCol_ListOfShape aLS(aAllocator);
682     aLS.Append(aS2);
683     aDMSLS.Add(aS1, aLS);
684   }
685   //
686   if (aDMSLS.Contains(aS2)) {
687     BOPCol_ListOfShape& aLS=aDMSLS.ChangeFromKey(aS2);
688     aLS.Append(aS1);
689   }
690   else {
691     BOPCol_ListOfShape aLS(aAllocator);
692     aLS.Append(aS1);
693     aDMSLS.Add(aS2, aLS);
694   }
695 }
696 //=======================================================================
697 //function :HasPaveBlocksOnIn
698 //purpose  : 
699 //=======================================================================
700 Standard_Boolean HasPaveBlocksOnIn(const BOPDS_FaceInfo& aFI1,
701                                    const BOPDS_FaceInfo& aFI2)
702 {
703   Standard_Boolean bRet;
704   BOPDS_MapIteratorOfMapOfPaveBlock aItMPB;
705   //
706   bRet=Standard_False;
707   const BOPDS_IndexedMapOfPaveBlock& aMPBOn1=aFI1.PaveBlocksOn();
708   const BOPDS_IndexedMapOfPaveBlock& aMPBIn1=aFI1.PaveBlocksIn();
709   //
710   const BOPDS_IndexedMapOfPaveBlock& aMPBOn2=aFI2.PaveBlocksOn();
711   aItMPB.Initialize(aMPBOn2);
712   for (; aItMPB.More(); aItMPB.Next()) {
713     const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
714     bRet=aMPBOn1.Contains(aPB) || aMPBIn1.Contains(aPB);
715     if (bRet) {
716       return bRet;
717     }
718   }
719   //
720   const BOPDS_IndexedMapOfPaveBlock& aMPBIn2=aFI2.PaveBlocksIn();
721   aItMPB.Initialize(aMPBIn2);
722   for (; aItMPB.More(); aItMPB.Next()) {
723     const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
724     bRet=aMPBOn1.Contains(aPB) || aMPBIn1.Contains(aPB);
725     if (bRet) {
726       return bRet;
727     }
728   }
729   return bRet;
730 }
731 /*
732 //DEBf
733     {
734       TopoDS_Compound aCx;
735       BRep_Builder aBBx;
736       BOPCol_ListIteratorOfListOfShape aItx;
737       //
738       aBBx.MakeCompound(aCx);
739       aBBx.Add(aCx, aFF);
740       aItx.Initialize(aLE);
741       for (; aItx.More(); aItx.Next()) {
742       const TopoDS_Shape& aEx=aItx.Value();
743       aBBx.Add(aCx, aEx);
744       }
745       int a=0;
746     }
747     //DEBt
748 */