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