0024428: Implementation of LGPL license
[occt.git] / src / BOPAlgo / BOPAlgo_PaveFiller_3.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_PaveFiller.ixx>
19
20 #include <Precision.hxx>
21 #include <NCollection_IncAllocator.hxx>
22 #include <NCollection_UBTreeFiller.hxx>
23
24 #include <Bnd_Box.hxx>
25
26 #include <TopoDS_Edge.hxx>
27 #include <TopoDS_Vertex.hxx>
28 #include <TopoDS_Compound.hxx>
29 #include <BRep_Tool.hxx>
30 #include <BRep_Builder.hxx>
31 #include <BRepTools.hxx>
32 #include <BRepBndLib.hxx>
33 //
34 #include <IntTools_EdgeEdge.hxx>
35 #include <IntTools_Range.hxx>
36 #include <IntTools_SequenceOfCommonPrts.hxx>
37 #include <IntTools_CommonPrt.hxx>
38 #include <IntTools_SequenceOfRanges.hxx>
39 //
40 #include <BOPTools_AlgoTools.hxx>
41 //
42 #include <BOPCol_DataMapOfShapeInteger.hxx>
43 #include <BOPCol_DataMapOfIntegerShape.hxx>
44 #include <BOPCol_IndexedDataMapOfShapeBox.hxx>
45 //
46 #include <BOPInt_Context.hxx>
47 #include <BOPInt_ShrunkRange.hxx>
48 #include <BOPInt_Tools.hxx>
49 //
50 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
51 #include <BOPDS_MapOfPaveBlock.hxx>
52 #include <BOPDS_CommonBlock.hxx>
53 #include <BOPDS_CoupleOfPaveBlocks.hxx>
54 #include <BOPDS_DataMapOfPaveBlockListOfInteger.hxx>
55 #include <BOPDS_Iterator.hxx>
56 #include <BOPDS_VectorOfInterfEE.hxx>
57 #include <BOPDS_Interf.hxx>
58 #include <BOPDS_Pave.hxx>
59 #include <BOPDS_BoxBndTree.hxx>
60
61 #include <BOPAlgo_Tools.hxx>
62 #include <GeomAPI_ProjectPointOnCurve.hxx>
63
64 //=======================================================================
65 // function: PerformEE
66 // purpose: 
67 //=======================================================================
68   void BOPAlgo_PaveFiller::PerformEE()
69 {
70   Standard_Boolean bJustAdd, bOrder;
71   Standard_Integer i, iX, iSize, nE1, nE2, aDiscretize;
72   Standard_Integer aNbCPrts, nWhat, nWith;
73   Standard_Real aTS11, aTS12, aTS21, aTS22,
74                 aT11, aT12, aT21, aT22;
75   Standard_Real aTolE1, aTolE2, aDeflection;
76   TopAbs_ShapeEnum aType;
77   TopoDS_Edge aEWhat, aEWith; 
78   BOPDS_ListIteratorOfListOfPaveBlock aIt1, aIt2;
79   Handle(NCollection_IncAllocator) aAllocator;
80   Handle(BOPDS_PaveBlock) aPBn1, aPBn2;
81   BOPDS_MapOfPaveBlock aMPBToUpdate;
82   BOPDS_MapIteratorOfMapOfPaveBlock aItPB;
83   //
84   myErrorStatus=0;
85   //
86   myIterator->Initialize(TopAbs_EDGE, TopAbs_EDGE);
87   iSize=myIterator->ExpectedLength();
88   if (!iSize) {
89     return; 
90   }
91   //
92   //-----------------------------------------------------scope f
93   aAllocator=new NCollection_IncAllocator();
94   BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(100, aAllocator);
95   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMVCPB(100, aAllocator);
96   //
97   aDiscretize=30;
98   aDeflection=0.01;
99   //
100   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
101   aEEs.SetStartSize(iSize);
102   aEEs.SetIncrement(iSize);
103   aEEs.Init();
104   //
105   for (; myIterator->More(); myIterator->Next()) {
106     myIterator->Value(nE1, nE2, bJustAdd);
107     if(bJustAdd) {
108       continue;
109     }
110     //
111     const BOPDS_ShapeInfo& aSIE1=myDS->ShapeInfo(nE1);
112     if (aSIE1.HasFlag()){
113       continue;
114     }
115     const BOPDS_ShapeInfo& aSIE2=myDS->ShapeInfo(nE2);
116     if (aSIE2.HasFlag()){
117       continue;
118     }
119     //
120     const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aSIE1.Shape()));
121     const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aSIE2.Shape()));  
122     //
123     aTolE1=BRep_Tool::Tolerance(aE1);
124     aTolE2=BRep_Tool::Tolerance(aE2);
125     //
126     BOPDS_ListOfPaveBlock& aLPB1=myDS->ChangePaveBlocks(nE1);
127     BOPDS_ListOfPaveBlock& aLPB2=myDS->ChangePaveBlocks(nE2);
128     //
129     aIt1.Initialize(aLPB1);
130     for (; aIt1.More(); aIt1.Next()) {
131       Bnd_Box aBB1;
132       //
133       Handle(BOPDS_PaveBlock)& aPB1=aIt1.ChangeValue();
134       if (!aPB1->HasShrunkData()) {
135         FillShrunkData(aPB1);
136         if (myWarningStatus) {
137           continue;
138         }
139       }
140       aPB1->ShrunkData(aTS11, aTS12, aBB1);
141       //
142       aIt2.Initialize(aLPB2);
143       for (; aIt2.More(); aIt2.Next()) {
144         Bnd_Box aBB2;
145         //
146         Handle(BOPDS_PaveBlock)& aPB2=aIt2.ChangeValue();
147         if (!aPB2->HasShrunkData()) {
148           FillShrunkData(aPB2);
149           if (myWarningStatus) {
150             continue;
151           }
152         }
153         aPB2->ShrunkData(aTS21, aTS22, aBB2);
154         //
155         if (aBB1.IsOut(aBB2)) {
156           continue;
157         }
158         //
159         // -----------f
160         //DEBft
161         //printf(" nE1=%d nE2=%d\n", nE1, nE2);
162         //
163         IntTools_EdgeEdge aEdgeEdge;
164         //
165         aEdgeEdge.SetEdge1 (aE1);
166         aEdgeEdge.SetEdge2 (aE2);
167         aEdgeEdge.SetTolerance1 (aTolE1);
168         aEdgeEdge.SetTolerance2 (aTolE2);
169         aEdgeEdge.SetDiscretize (aDiscretize);
170         aEdgeEdge.SetDeflection (aDeflection);
171         //
172         IntTools_Range aSR1(aTS11, aTS12);
173         IntTools_Range aSR2(aTS21, aTS22);
174         IntTools_Range anewSR1 = aSR1;
175         IntTools_Range anewSR2 = aSR2;
176         //
177         BOPTools_AlgoTools::CorrectRange (aE1, aE2, aSR1, anewSR1);
178         BOPTools_AlgoTools::CorrectRange (aE2, aE1, aSR2, anewSR2);
179         //
180         aPB1->Range(aT11, aT12);
181         aPB2->Range(aT21, aT22);
182         IntTools_Range aPBRange1(aT11, aT12), aPBRange2(aT21, aT22);
183         //
184         IntTools_Range aPBR1 = aPBRange1;
185         IntTools_Range aPBR2 = aPBRange2;
186         BOPTools_AlgoTools::CorrectRange (aE1, aE2, aPBR1, aPBRange1);
187         BOPTools_AlgoTools::CorrectRange (aE2, aE1, aPBR2, aPBRange2);
188         //
189         aEdgeEdge.SetRange1(aPBRange1);
190         aEdgeEdge.SetRange2(aPBRange2);
191         //
192         aEdgeEdge.Perform();
193         if (!aEdgeEdge.IsDone()) {
194           continue;
195         }
196         //
197         bOrder=aEdgeEdge.Order();
198         if (!bOrder) {
199           aEWhat=aE1;
200           aEWith=aE2;
201           nWhat=nE1;
202           nWith=nE2;
203           aSR1=anewSR1;
204           aSR2=anewSR2;
205           aPBR1=aPBRange1;
206           aPBR2=aPBRange2;
207           aPBn1=aPB1;
208           aPBn2=aPB2;
209         }
210         else {
211           nWhat=nE2;
212           nWith=nE1;
213           aEWhat=aE2;
214           aEWith=aE1;
215           aSR1=anewSR2;
216           aSR2=anewSR1;
217           aPBR1=aPBRange2;
218           aPBR2=aPBRange1;
219           aPBn1=aPB2;
220           aPBn2=aPB1;
221         }
222         //
223         IntTools_Range aR11(aPBR1.First(), aSR1.First()), aR12(aSR1.Last(), aPBR1.Last()),
224                        aR21(aPBR2.First(), aSR2.First()), aR22(aSR2.Last(), aPBR2.Last());
225         //
226         const IntTools_SequenceOfCommonPrts& aCPrts=aEdgeEdge.CommonParts();
227         //
228         aNbCPrts=aCPrts.Length();
229         for (i=1; i<=aNbCPrts; ++i) {
230           const IntTools_CommonPrt& aCPart=aCPrts(i);
231           aType=aCPart.Type();
232           switch (aType) {
233             case TopAbs_VERTEX:  { 
234               Standard_Boolean bIsOnPave[4], bFlag;
235               Standard_Integer nV[4], j;
236               Standard_Real aT1, aT2, aTol;
237               TopoDS_Vertex aVnew;
238               //
239               BOPInt_Tools::VertexParameters(aCPart, aT1, aT2);
240               aTol=Precision::Confusion();
241               // 
242               //decide to keep the pave or not
243               bIsOnPave[0] = BOPInt_Tools::IsOnPave1(aT1, aR11, aTol);
244               bIsOnPave[1] = BOPInt_Tools::IsOnPave1(aT1, aR12, aTol);
245               bIsOnPave[2] = BOPInt_Tools::IsOnPave1(aT2, aR21, aTol);
246               bIsOnPave[3] = BOPInt_Tools::IsOnPave1(aT2, aR22, aTol);
247               //
248               aPBn1->Indices(nV[0], nV[1]);
249               aPBn2->Indices(nV[2], nV[3]);
250               //
251               if((bIsOnPave[0] && bIsOnPave[2]) || (bIsOnPave[0] && bIsOnPave[3]) ||
252                  (bIsOnPave[1] && bIsOnPave[2]) || (bIsOnPave[1] && bIsOnPave[3])) {
253                 continue;
254               }
255               //
256               bFlag = Standard_False;
257               for (j = 0; j < 4; ++j) {
258                 if (bIsOnPave[j]) {
259                   //add interf VE(nV[j], nE)
260                   Handle(BOPDS_PaveBlock)& aPB = (j < 2) ? aPBn2 : aPBn1;
261                   ForceInterfVE(nV[j], aPB, aMPBToUpdate);
262                   bFlag = Standard_True;
263                   break;
264                 }
265               }
266               if (bFlag) {
267                 continue;
268               }
269               //
270               BOPTools_AlgoTools::MakeNewVertex(aEWhat, aT1, aEWith, aT2, aVnew);
271               // <-LXBR
272               {
273                 Standard_Integer nVS[2], iFound, k;
274                 Standard_Real aTolVx, aTolVnew, aD2, aDT2;
275                 BOPCol_MapOfInteger aMV;
276                 gp_Pnt aPnew, aPx;
277                 //
278                 iFound=0;
279                 j=-1;
280                 aMV.Add(nV[0]);
281                 aMV.Add(nV[1]);
282                 //
283                 if (aMV.Contains(nV[2])) {
284                   ++j;
285                   nVS[j]=nV[2];
286                 }
287                 if (aMV.Contains(nV[3])) {
288                   ++j;
289                   nVS[j]=nV[3];
290                 }
291                 //
292                 aTolVnew=BRep_Tool::Tolerance(aVnew);
293                 aPnew=BRep_Tool::Pnt(aVnew);
294                 //
295                 for (k=0; k<=j; ++k) {
296                   const TopoDS_Vertex& aVx= *(TopoDS_Vertex*)&(myDS->Shape(nVS[k]));
297                   aTolVx=BRep_Tool::Tolerance(aVx);
298                   aPx=BRep_Tool::Pnt(aVx);
299                   aD2=aPnew.SquareDistance(aPx);
300                   //
301                   aDT2=100.*(aTolVnew+aTolVx)*(aTolVnew+aTolVx);
302                   //
303                   if (aD2<aDT2) {
304                     iFound=1;
305                     break;
306                   }
307                 }
308                 //
309                 if (iFound) {
310                   continue;
311                 }
312               }
313                             
314               // 1
315               iX=aEEs.Append()-1;
316               BOPDS_InterfEE& aEE=aEEs(iX);
317               aEE.SetIndices(nWhat, nWith);
318               aEE.SetCommonPart(aCPart);
319               // 2
320               myDS->AddInterf(nWhat, nWith);
321               //
322               BOPDS_CoupleOfPaveBlocks aCPB;
323               //
324               aCPB.SetPaveBlocks(aPB1, aPB2);
325               aCPB.SetIndexInterf(iX);
326               aMVCPB.Add(aVnew, aCPB);
327             }//case TopAbs_VERTEX: 
328             break;
329             //
330             case TopAbs_EDGE: {
331               Standard_Boolean bHasSameBounds;
332               Standard_Integer aNbComPrt2;
333               //
334               aNbComPrt2=aCPart.Ranges2().Length();
335               if (aNbComPrt2>1){
336                 break;
337               }
338               //// <-LXBR   
339               bHasSameBounds=aPB1->HasSameBounds(aPB2);
340               if (!bHasSameBounds) {
341                 break;
342               }
343               // 1
344               iX=aEEs.Append()-1;
345               BOPDS_InterfEE& aEE=aEEs(iX);
346               aEE.SetIndices(nWhat, nWith);
347               aEE.SetCommonPart(aCPart);
348               // 2
349               myDS->AddInterf(nWhat, nWith);
350               //
351               BOPAlgo_Tools::FillMap(aPB1, aPB2, aMPBLPB, aAllocator);
352             }//case TopAbs_EDGE
353             break;
354             default:
355               break;
356           }//switch (aType) {
357         }//for (i=1; i<=aNbCPrts; i++) {
358         // -----------t
359         //
360       }// for (; aIt2.More(); aIt2.Next()) {
361     }// for (; aIt1.More(); aIt1.Next()) {
362   }
363   // 
364   //=========================================
365   // post treatment
366   //=========================================
367   aItPB.Initialize(aMPBToUpdate);
368   for (; aItPB.More(); aItPB.Next()) {
369     Handle(BOPDS_PaveBlock) aPB=aItPB.Value();
370     if (!myDS->IsCommonBlock(aPB)) {
371       myDS->UpdatePaveBlock(aPB);
372     }
373     else {
374       const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
375       myDS->UpdateCommonBlock(aCB);
376     }
377   }
378   //
379   BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, aAllocator, myDS);
380   PerformVerticesEE(aMVCPB, aAllocator);
381   //-----------------------------------------------------scope t
382   aMPBLPB.Clear();
383   aMVCPB.Clear();
384   aMPBToUpdate.Clear();
385   aAllocator.Nullify();
386 }
387 //=======================================================================
388 //function : PerformVertices
389 //purpose  : 
390 //=======================================================================
391   Standard_Integer BOPAlgo_PaveFiller::PerformVerticesEE
392     (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
393      Handle(NCollection_BaseAllocator)& theAllocator)
394 {
395   Standard_Integer aNbV, iRet;
396   //
397   iRet=0;
398   aNbV=theMVCPB.Extent();
399   if (!aNbV) {
400     return iRet;
401   }
402   //
403   Standard_Integer nVx, iV, j, nE, iFlag, iX, i, aNb; 
404   Standard_Real aT;
405   TopoDS_Shape aV;
406   BOPCol_ListIteratorOfListOfShape aItLS;
407   BOPCol_ListIteratorOfListOfInteger aItLI;
408   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
409   BOPDS_ShapeInfo aSI;
410   BOPDS_Pave aPave;
411   //
412   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
413   BOPCol_ListOfShape aLS(theAllocator);
414   BOPCol_IndexedDataMapOfShapeInteger aMVI(100, theAllocator);
415   BOPCol_IndexedDataMapOfShapeListOfShape aImages;
416   //
417   aSI.SetShapeType(TopAbs_VERTEX);
418   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
419   //
420   // 1 prepare arguments
421   //
422   // <- DEB
423   for (i=1; i<=aNbV; ++i) {
424     const TopoDS_Shape& aS=theMVCPB.FindKey(i);
425     const BOPDS_CoupleOfPaveBlocks& aCPB=theMVCPB.FindFromIndex(i);
426     iV=aCPB.IndexInterf();
427     aMVI.Add(aS, iV);
428   }
429   //
430   // 2 Fuse vertices
431   TreatNewVertices(aMVI, aImages);
432   //
433   // 3 Add new vertices to myDS; 
434   //   connect indices to CPB structure
435   aNb = aImages.Extent();
436   for (i=1; i<=aNb; ++i) {
437     const TopoDS_Vertex& aV=(*(TopoDS_Vertex*)(&aImages.FindKey(i)));
438     const BOPCol_ListOfShape& aLVSD=aImages.FindFromIndex(i);
439     //
440     aSI.SetShape(aV);
441     iV=myDS->Append(aSI);
442     //
443     BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(iV);
444     Bnd_Box& aBox=aSIDS.ChangeBox();
445     BRepBndLib::Add(aV, aBox);
446     //
447     aItLS.Initialize(aLVSD);
448     for (; aItLS.More(); aItLS.Next()) {
449       const TopoDS_Shape& aVx = aItLS.Value();
450       BOPDS_CoupleOfPaveBlocks &aCPB=theMVCPB.ChangeFromKey(aVx);
451       aCPB.SetIndex(iV);
452       // update EE interference
453       iX=aCPB.IndexInterf();
454       BOPDS_InterfEE& aEE=aEEs(iX);
455       aEE.SetIndexNew(iV);
456     }
457   }
458   //
459   // 4 Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
460   {
461     Handle(BOPDS_PaveBlock) aPB[2];
462     //
463     for (i=1; i<=aNbV; ++i) {
464       const BOPDS_CoupleOfPaveBlocks& aCPB=theMVCPB.FindFromIndex(i);
465       iV=aCPB.Index();
466       aCPB.PaveBlocks(aPB[0], aPB[1]);
467       for (j=0; j<2; ++j) {
468         if (aMPBLI.Contains(aPB[j])) {
469           BOPCol_ListOfInteger& aLI=aMPBLI.ChangeFromKey(aPB[j]);
470           aLI.Append(iV);
471         }
472         else {
473           BOPCol_ListOfInteger aLI(theAllocator);
474           aLI.Append(iV);
475           aMPBLI.Add(aPB[j], aLI);
476         }
477       }
478     }
479   }
480   //
481   // 5 
482   // 5.1  Compute Extra Paves and 
483   // 5.2. Add Extra Paves to the PaveBlocks
484   aNb=aMPBLI.Extent();
485   for(i=1; i<=aNb; ++i) {
486     Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
487     nE=aPB->OriginalEdge();
488     const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
489     // 1,2
490     const BOPCol_ListOfInteger& aLI=aMPBLI.FindFromIndex(i);
491     aItLI.Initialize(aLI);
492     for (; aItLI.More(); aItLI.Next()) {
493       nVx=aItLI.Value();
494       const TopoDS_Vertex& aVx=(*(TopoDS_Vertex *)(&myDS->Shape(nVx)));
495       //
496       iFlag=myContext->ComputeVE (aVx, aE, aT);
497       if (!iFlag) {
498         aPave.SetIndex(nVx);
499         aPave.SetParameter(aT);
500         aPB->AppendExtPave(aPave);
501       }
502     }
503   }
504   // 6  Split PaveBlocksa
505   aNb=aMPBLI.Extent();
506   for(i=1; i<=aNb; ++i) {
507     Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
508     nE=aPB->OriginalEdge();
509     // 3
510     if (!myDS->IsCommonBlock(aPB)) {
511       myDS->UpdatePaveBlock(aPB);
512     }
513     else {
514       const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
515       myDS->UpdateCommonBlock(aCB);
516     }    
517   }//for (; aItMPBLI.More(); aItMPBLI.Next()) {
518   //
519   return iRet;
520 }
521
522 //=======================================================================
523 //function : TreatNewVertices
524 //purpose  : 
525 //=======================================================================
526   void BOPAlgo_PaveFiller::TreatNewVertices(
527        const BOPCol_IndexedDataMapOfShapeInteger& aMapVI,
528        BOPCol_IndexedDataMapOfShapeListOfShape& myImages)
529 {
530   Standard_Integer j, i, aNbV, aNbVSD;
531   Standard_Real aTol;
532   TopoDS_Shape aVF;
533   TopoDS_Vertex aVnew;
534   BOPCol_IndexedMapOfShape aMVProcessed;
535
536   BOPCol_ListIteratorOfListOfInteger aIt;
537   BOPCol_IndexedDataMapOfShapeListOfShape aMVLV;
538   BOPCol_DataMapOfIntegerShape aMIS;
539   BOPCol_IndexedDataMapOfShapeBox aMSB;
540   //
541   BOPDS_BoxBndTreeSelector aSelector;
542   BOPDS_BoxBndTree aBBTree;
543   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
544   //
545   aNbV = aMapVI.Extent();
546   for (i=1; i<=aNbV; ++i) {
547     const TopoDS_Shape& aV=aMapVI.FindKey(i);
548     Bnd_Box aBox;
549     //
550     aTol=BRep_Tool::Tolerance(*(TopoDS_Vertex*)(&aV));
551     aBox.SetGap(aTol);
552     BRepBndLib::Add(aV, aBox);
553     //
554     aTreeFiller.Add(i, aBox);
555     //
556     aMIS.Bind(i, aV);
557     aMSB.Add(aV, aBox);
558   }
559   //
560   aTreeFiller.Fill();
561
562   // Chains
563   for (i=1; i<=aNbV; ++i) {
564     const TopoDS_Shape& aV=aMapVI.FindKey(i);
565     //
566     if (aMVProcessed.Contains(aV)) {
567       continue;
568     }
569     //
570     Standard_Integer aNbIP, aIP, aNbIP1, aIP1;
571     BOPCol_ListOfShape aLVSD;
572     BOPCol_MapOfInteger aMIP, aMIP1, aMIPC;
573     BOPCol_MapIteratorOfMapOfInteger aIt1;
574     //
575     aMIP.Add(i);
576     for(;;) {
577       aNbIP=aMIP.Extent();
578       aIt1.Initialize(aMIP);
579       for(; aIt1.More(); aIt1.Next()) {
580         aIP=aIt1.Key();
581         if (aMIPC.Contains(aIP)) {
582           continue;
583         }
584         //
585         const TopoDS_Shape& aVP=aMIS.Find(aIP);
586         const Bnd_Box& aBoxVP=aMSB.FindFromKey(aVP);
587         //
588         aSelector.Clear();
589         aSelector.SetBox(aBoxVP);
590         //
591         aNbVSD=aBBTree.Select(aSelector);
592         if (!aNbVSD) {
593           continue;  // it must not be
594         }
595         //
596         const BOPCol_ListOfInteger& aLI=aSelector.Indices();
597         aIt.Initialize(aLI);
598         for (; aIt.More(); aIt.Next()) {
599           aIP1=aIt.Value();
600           if (aMIP.Contains(aIP1)) {
601             continue;
602           }
603           aMIP1.Add(aIP1);
604         } //for (; aIt.More(); aIt.Next()) {
605       }//for(; aIt1.More(); aIt1.Next()) {
606       //
607       aNbIP1=aMIP1.Extent();
608       if (!aNbIP1) {
609         break; // from while(1)
610       }
611       //
612       aIt1.Initialize(aMIP);
613       for(; aIt1.More(); aIt1.Next()) {
614         aIP=aIt1.Key();
615         aMIPC.Add(aIP);
616       }
617       //
618       aMIP.Clear();
619       aIt1.Initialize(aMIP1);
620       for(; aIt1.More(); aIt1.Next()) {
621         aIP=aIt1.Key();
622         aMIP.Add(aIP);
623       }
624       aMIP1.Clear();
625     }// while(1)
626     //...
627     aNbIP=aMIPC.Extent();
628     if (!aNbIP) {
629       aMIPC.Add(i);
630     }
631     //
632     aIt1.Initialize(aMIPC);
633     for(j=0; aIt1.More(); aIt1.Next(), ++j) {
634       aIP=aIt1.Key();
635       const TopoDS_Shape& aVP=aMIS.Find(aIP);
636       if (!j) {
637         aVF=aVP;
638       }
639       aLVSD.Append(aVP);
640       aMVProcessed.Add(aVP);
641     }
642     aMVLV.Add(aVF, aLVSD);
643   }// for (i=1; i<=aNbV; ++i) {
644
645   // Make new vertices
646   aNbV=aMVLV.Extent();
647   for (i=1; i<=aNbV; ++i) {
648     const TopoDS_Shape& aV=aMVLV.FindKey(i);
649     BOPCol_ListOfShape& aLVSD=aMVLV.ChangeFromIndex(i);
650     aNbVSD=aLVSD.Extent();
651     if (aNbVSD>1) {
652       BOPTools_AlgoTools::MakeVertex(aLVSD, aVnew);
653       myImages.Add(aVnew, aLVSD);
654     } else {
655       myImages.Add(aV, aLVSD);
656     }
657   }
658 }
659
660 //=======================================================================
661 //function : FillShrunkData
662 //purpose  : 
663 //=======================================================================
664   void BOPAlgo_PaveFiller::FillShrunkData(Handle(BOPDS_PaveBlock)& thePB)
665 {
666   Standard_Integer nE, nV1, nV2, iErr;
667   Standard_Real aT1, aT2, aTS1, aTS2;
668   BOPInt_ShrunkRange aSR;
669   //
670   myErrorStatus=0;
671   myWarningStatus = 0;
672   //
673   const BOPDS_Pave& aPave1=thePB->Pave1();
674   nV1=aPave1.Index();
675   aT1=aPave1.Parameter();
676   const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1))); 
677   //
678   const BOPDS_Pave& aPave2=thePB->Pave2();
679   nV2=aPave2.Index();
680   aT2=aPave2.Parameter();
681   const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2))); 
682   //
683   nE=thePB->OriginalEdge();
684   const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE))); 
685   //
686   aSR.SetData(aE, aT1, aT2, aV1, aV2, myContext);
687   //
688   aSR.Perform();
689   iErr=aSR.ErrorStatus();
690   if (iErr) {
691     myWarningStatus = 1;
692     //myErrorStatus=40;
693     return;
694   }
695   //
696   aSR.ShrunkRange(aTS1, aTS2);
697   const Bnd_Box& aBox=aSR.BndBox();
698   //
699   thePB->SetShrunkData(aTS1, aTS2, aBox);
700 }
701 //=======================================================================
702 //function : ForceInterfVE
703 //purpose  : 
704 //=======================================================================
705 void BOPAlgo_PaveFiller::ForceInterfVE(const Standard_Integer nV,
706                                        Handle(BOPDS_PaveBlock)& aPB,
707                                        BOPDS_MapOfPaveBlock& aMPBToUpdate)
708 {
709   Standard_Integer aNbPnt, nE;
710   gp_Pnt aP;
711   //
712   nE = aPB->OriginalEdge();
713   //
714   const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
715   if (aSIE.HasSubShape(nV)) {
716     return;
717   }
718   //
719   if (myDS->HasInterf(nV, nE)) {
720     return;
721   }   
722   //
723   if (myDS->HasInterfShapeSubShapes(nV, nE)) {
724     return;
725   }
726   //
727   if (aPB->Pave1().Index() == nV || aPB->Pave2().Index() == nV) {
728     return;
729   }
730   //
731   const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nV);
732   const TopoDS_Edge&   aE = *(TopoDS_Edge*)  &myDS->Shape(nE);
733   aP=BRep_Tool::Pnt(aV);
734   //
735   GeomAPI_ProjectPointOnCurve& aProjector=myContext->ProjPC(aE);
736   aProjector.Perform(aP);
737   //
738   aNbPnt = aProjector.NbPoints();
739   if (aNbPnt) {
740     Standard_Real aT, aDist;
741     Standard_Integer i;
742     BRep_Builder aBB;
743     BOPDS_Pave aPave;
744     //
745     aDist=aProjector.LowerDistance();
746     aT=aProjector.LowerDistanceParameter();
747     //
748     BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
749     i=aVEs.Append()-1;
750     BOPDS_InterfVE& aVE=aVEs(i);
751     aVE.SetIndices(nV, nE);
752     aVE.SetParameter(aT);
753     //
754     myDS->AddInterf(nV, nE);
755     //
756     aBB.UpdateVertex(aV, aDist);
757     BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(nV);
758     Bnd_Box& aBox=aSIDS.ChangeBox();
759     BRepBndLib::Add(aV, aBox);
760     //
761     aPave.SetIndex(nV);
762     aPave.SetParameter(aT);
763     aPB->AppendExtPave(aPave);
764     //
765     aMPBToUpdate.Add(aPB);
766   }
767 }
768
769  /*
770   // DEBf
771   { 
772     TopoDS_Compound aCx;
773     BRep_Builder aBBx;
774     aBBx.MakeCompound(aCx);
775     aItMVCPB.Initialize(theMVCPB);
776     for (; aItMVCPB.More(); aItMVCPB.Next()) {
777       const TopoDS_Shape& aS=aItMVCPB.Key();
778       aBBx.Add(aCx, aS);
779     }
780     BRepTools::Write(aCx, "cx");
781   }
782   // DEBt
783   */