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