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 under
  10 // the terms of the GNU Lesser General Public License version 2.1 as published
  11 // by the Free Software Foundation, with special exception defined in the file
  12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  13 // distribution for complete text of the license and disclaimer of any warranty.
  14 //
  15 // Alternatively, this file may be used under the terms of Open CASCADE
  16 // commercial license or contractual agreement.
  17
  18
  19 #include <Bnd_Box.hxx>
  20 #include <BOPAlgo_PaveFiller.hxx>
  21 #include <BOPAlgo_Tools.hxx>
  22 #include <BOPAlgo_Alerts.hxx>
  23 #include <BOPDS_CommonBlock.hxx>
  24 #include <BOPDS_CoupleOfPaveBlocks.hxx>
  25 #include <BOPDS_DS.hxx>
  26 #include <BOPDS_Interf.hxx>
  27 #include <BOPDS_Iterator.hxx>
  28 #include <BOPDS_MapOfPaveBlock.hxx>
  29 #include <BOPDS_Pave.hxx>
  30 #include <BOPDS_PaveBlock.hxx>
  31 #include <BOPDS_VectorOfInterfEE.hxx>
  32 #include <BOPTools_AlgoTools.hxx>
  33 #include <BOPTools_Parallel.hxx>
  34 #include <BndLib_Add3dCurve.hxx>
  35 #include <BRep_Tool.hxx>
  36 #include <BRep_Builder.hxx>
  37 #include <BRepAdaptor_Curve.hxx>
  38 #include <gp_Pnt.hxx>
  39 #include <IntTools_CommonPrt.hxx>
  40 #include <IntTools_Context.hxx>
  41 #include <IntTools_EdgeEdge.hxx>
  42 #include <IntTools_Range.hxx>
  43 #include <IntTools_SequenceOfCommonPrts.hxx>
  44 #include <IntTools_SequenceOfRanges.hxx>
  45 #include <IntTools_ShrunkRange.hxx>
  46 #include <IntTools_Tools.hxx>
  47 #include <NCollection_IncAllocator.hxx>
  48 #include <NCollection_Vector.hxx>
  49 #include <Precision.hxx>
  50 #include <TopoDS.hxx>
  51 #include <TopoDS_Edge.hxx>
  52 #include <TopoDS_Vertex.hxx>
  53
  54 /////////////////////////////////////////////////////////////////////////
  55 //=======================================================================
  56 //class    : BOPAlgo_EdgeEdge
  57 //purpose  :
  58 //=======================================================================
  59 class BOPAlgo_EdgeEdge :
  60   public IntTools_EdgeEdge,
  61   public BOPAlgo_Algo {
  62
  63  public:
  64
  65   DEFINE_STANDARD_ALLOC
  66   //
  67   BOPAlgo_EdgeEdge():
  68     IntTools_EdgeEdge(),
  69     BOPAlgo_Algo() {
  70   };
  71   //
  72   virtual ~BOPAlgo_EdgeEdge(){
  73   };
  74   //
  75   void SetPaveBlock1(const Handle(BOPDS_PaveBlock)& aPB) {
  76     myPB1=aPB;
  77   }
  78   //
  79   Handle(BOPDS_PaveBlock)& PaveBlock1() {
  80     return myPB1;
  81   }
  82   //
  83   void SetPaveBlock2(const Handle(BOPDS_PaveBlock)& aPB) {
  84     myPB2=aPB;
  85   }
  86   //
  87   Handle(BOPDS_PaveBlock)& PaveBlock2() {
  88     return myPB2;
  89   }
  90   //
  91   void SetFuzzyValue(const Standard_Real theFuzz) {
  92     IntTools_EdgeEdge::SetFuzzyValue(theFuzz);
  93   }
  94   //
  95   virtual void Perform() {
  96     BOPAlgo_Algo::UserBreak();
  97     try
  98     {
  99       OCC_CATCH_SIGNALS
 100
 101       IntTools_EdgeEdge::Perform();
 102     }
 103     catch (Standard_Failure)
 104     {
 105       AddError(new BOPAlgo_AlertIntersectionFailed);
 106     }
 107   }
 108   //
 109  protected:
 110   Handle(BOPDS_PaveBlock) myPB1;
 111   Handle(BOPDS_PaveBlock) myPB2;
 112 };
 113 //
 114 //=======================================================================
 115 typedef NCollection_Vector
 116   <BOPAlgo_EdgeEdge> BOPAlgo_VectorOfEdgeEdge;
 117 //
 118 typedef BOPTools_Functor
 119   <BOPAlgo_EdgeEdge,
 120   BOPAlgo_VectorOfEdgeEdge> BOPAlgo_EdgeEdgeFunctor;
 121 //
 122 typedef BOPTools_Cnt
 123   <BOPAlgo_EdgeEdgeFunctor,
 124   BOPAlgo_VectorOfEdgeEdge> BOPAlgo_EdgeEdgeCnt;
 125 //
 126 /////////////////////////////////////////////////////////////////////////
 127 //=======================================================================
 128 // function: PerformEE
 129 // purpose:
 130 //=======================================================================
 131 void BOPAlgo_PaveFiller::PerformEE()
 132 {
 133   FillShrunkData(TopAbs_EDGE, TopAbs_EDGE);
 134   //
 135   myIterator->Initialize(TopAbs_EDGE, TopAbs_EDGE);
 136   Standard_Integer iSize = myIterator->ExpectedLength();
 137   if (!iSize) {
 138     return;
 139   }
 140   //
 141   Standard_Boolean bExpressCompute, bIsPBSplittable1, bIsPBSplittable2;
 142   Standard_Integer i, iX, nE1, nE2, aNbCPrts, k, aNbEdgeEdge;
 143   Standard_Integer nV11, nV12, nV21, nV22;
 144   Standard_Real aTS11, aTS12, aTS21, aTS22, aT11, aT12, aT21, aT22;
 145   TopAbs_ShapeEnum aType;
 146   BOPDS_ListIteratorOfListOfPaveBlock aIt1, aIt2;
 147   Handle(NCollection_BaseAllocator) aAllocator;
 148   BOPAlgo_VectorOfEdgeEdge aVEdgeEdge;
 149   BOPDS_MapIteratorOfMapOfPaveBlock aItPB;
 150   // keep modified edges for further update
 151   TColStd_MapOfInteger aMEdges;
 152   //
 153   aAllocator=NCollection_BaseAllocator::CommonBaseAllocator();
 154   //-----------------------------------------------------scope f
 155   BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(100, aAllocator);
 156   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMVCPB(100, aAllocator);
 157   BOPAlgo_DataMapOfPaveBlockBndBox aDMPBBox(100, aAllocator);
 158   //
 159   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
 160   aEEs.SetIncrement(iSize);
 161   //
 162   for (; myIterator->More(); myIterator->Next()) {
 163     myIterator->Value(nE1, nE2);
 164     //
 165     const BOPDS_ShapeInfo& aSIE1=myDS->ShapeInfo(nE1);
 166     if (aSIE1.HasFlag()){
 167       continue;
 168     }
 169     const BOPDS_ShapeInfo& aSIE2=myDS->ShapeInfo(nE2);
 170     if (aSIE2.HasFlag()){
 171       continue;
 172     }
 173     //
 174     BOPDS_ListOfPaveBlock& aLPB1 = myDS->ChangePaveBlocks(nE1);
 175     if (aLPB1.IsEmpty()) {
 176       continue;
 177     }
 178     //
 179     BOPDS_ListOfPaveBlock& aLPB2 = myDS->ChangePaveBlocks(nE2);
 180     if (aLPB2.IsEmpty()) {
 181       continue;
 182     }
 183     //
 184     const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aSIE1.Shape()));
 185     const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aSIE2.Shape()));
 186     //
 187     aIt1.Initialize(aLPB1);
 188     for (; aIt1.More(); aIt1.Next()) {
 189       Bnd_Box aBB1;
 190       //
 191       Handle(BOPDS_PaveBlock)& aPB1=aIt1.ChangeValue();
 192       //
 193       if (!GetPBBox(aE1, aPB1, aDMPBBox, aT11, aT12, aTS11, aTS12, aBB1)) {
 194         continue;
 195       }
 196       //
 197       aPB1->Indices(nV11, nV12);
 198       //
 199       aIt2.Initialize(aLPB2);
 200       for (; aIt2.More(); aIt2.Next()) {
 201         Bnd_Box aBB2;
 202         //
 203         Handle(BOPDS_PaveBlock)& aPB2=aIt2.ChangeValue();
 204         //
 205         if (!GetPBBox(aE2, aPB2, aDMPBBox, aT21, aT22, aTS21, aTS22, aBB2)) {
 206           continue;
 207         }
 208         //
 209         if (aBB1.IsOut(aBB2)) {
 210           continue;
 211         }
 212         //
 213         aPB2->Indices(nV21, nV22);
 214         //
 215         bExpressCompute=((nV11==nV21 && nV12==nV22) ||
 216                          (nV12==nV21 && nV11==nV22));
 217         //
 218         BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge.Appended();
 219         //
 220         anEdgeEdge.UseQuickCoincidenceCheck(bExpressCompute);
 221         //
 222         anEdgeEdge.SetPaveBlock1(aPB1);
 223         anEdgeEdge.SetPaveBlock2(aPB2);
 224         //
 225         anEdgeEdge.SetEdge1(aE1, aT11, aT12);
 226         anEdgeEdge.SetEdge2(aE2, aT21, aT22);
 227         anEdgeEdge.SetFuzzyValue(myFuzzyValue);
 228         anEdgeEdge.SetProgressIndicator(myProgressIndicator);
 229       }//for (; aIt2.More(); aIt2.Next()) {
 230     }//for (; aIt1.More(); aIt1.Next()) {
 231   }//for (; myIterator->More(); myIterator->Next()) {
 232   //
 233   aNbEdgeEdge=aVEdgeEdge.Length();
 234   //======================================================
 235   BOPAlgo_EdgeEdgeCnt::Perform(myRunParallel, aVEdgeEdge);
 236   //======================================================
 237   //
 238   for (k = 0; k < aNbEdgeEdge; ++k) {
 239     Bnd_Box aBB1, aBB2;
 240     //
 241     BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge(k);
 242     if (!anEdgeEdge.IsDone() || anEdgeEdge.HasErrors()) {
 243       // Warn about failed intersection of sub-shapes
 244       const TopoDS_Shape& aE1 = myDS->Shape(anEdgeEdge.PaveBlock1()->OriginalEdge());
 245       const TopoDS_Shape& aE2 = myDS->Shape(anEdgeEdge.PaveBlock2()->OriginalEdge());
 246       AddIntersectionFailedWarning(aE1, aE2);
 247       continue;
 248     }
 249     //
 250     const IntTools_SequenceOfCommonPrts& aCPrts = anEdgeEdge.CommonParts();
 251     aNbCPrts = aCPrts.Length();
 252     if (!aNbCPrts) {
 253       continue;
 254     }
 255     //--------------------------------------------
 256     Handle(BOPDS_PaveBlock)& aPB1=anEdgeEdge.PaveBlock1();
 257     nE1=aPB1->OriginalEdge();
 258     aPB1->Range(aT11, aT12);
 259     if (!aPB1->HasShrunkData()) {
 260       aTS11 = aT11;
 261       aTS12 = aT12;
 262       bIsPBSplittable1 = Standard_False;
 263     }
 264     else {
 265       aPB1->ShrunkData(aTS11, aTS12, aBB1, bIsPBSplittable1);
 266     }
 267     //
 268     Handle(BOPDS_PaveBlock)& aPB2=anEdgeEdge.PaveBlock2();
 269     nE2=aPB2->OriginalEdge();
 270     aPB2->Range(aT21, aT22);
 271     if (!aPB2->HasShrunkData()) {
 272       aTS21 = aT21;
 273       aTS22 = aT22;
 274       bIsPBSplittable2 = Standard_False;
 275     }
 276     else {
 277       aPB2->ShrunkData(aTS21, aTS22, aBB2, bIsPBSplittable2);
 278     }
 279     //
 280     //--------------------------------------------
 281     IntTools_Range aR11(aT11, aTS11), aR12(aTS12, aT12),
 282                    aR21(aT21, aTS21), aR22(aTS22, aT22);
 283     //
 284     Standard_Boolean bAnalytical = Standard_False;
 285     {
 286       const TopoDS_Edge& aOE1 = *(TopoDS_Edge*)&myDS->Shape(nE1);
 287       const TopoDS_Edge& aOE2 = *(TopoDS_Edge*)&myDS->Shape(nE2);
 288       //
 289       BRepAdaptor_Curve aBAC1(aOE1), aBAC2(aOE2);
 290       //
 291       GeomAbs_CurveType aType1 = aBAC1.GetType();
 292       GeomAbs_CurveType aType2 = aBAC2.GetType();
 293       //
 294       bAnalytical = (((aType1 == GeomAbs_Line) &&
 295                       (aType2 == GeomAbs_Line ||
 296                        aType2 == GeomAbs_Circle)) ||
 297                      ((aType2 == GeomAbs_Line) &&
 298                       (aType1 == GeomAbs_Line ||
 299                        aType1 == GeomAbs_Circle)));
 300     }
 301     //
 302     for (i=1; i<=aNbCPrts; ++i) {
 303       const IntTools_CommonPrt& aCPart=aCPrts(i);
 304       //
 305       const TopoDS_Edge& aE1=aCPart.Edge1();
 306       const TopoDS_Edge& aE2=aCPart.Edge2();
 307       //
 308       aType=aCPart.Type();
 309       switch (aType) {
 310         case TopAbs_VERTEX:  {
 311           if (!bIsPBSplittable1 || !bIsPBSplittable2) {
 312             continue;
 313           }
 314           //
 315           Standard_Boolean bIsOnPave[4], bFlag;
 316           Standard_Integer nV[4], j;
 317           Standard_Real aT1, aT2, aTol;
 318           TopoDS_Vertex aVnew;
 319           IntTools_Range aCR1, aCR2;
 320           //
 321           IntTools_Tools::VertexParameters(aCPart, aT1, aT2);
 322           aTol = Precision::Confusion();
 323           aCR1 = aCPart.Range1();
 324           aCR2 = aCPart.Ranges2()(1);
 325           //
 326           //decide to keep the pave or not
 327           bIsOnPave[0] = IntTools_Tools::IsOnPave1(aT1, aR11, aTol) ||
 328             IntTools_Tools::IsOnPave1(aR11.First(), aCR1, aTol);
 329           bIsOnPave[1] = IntTools_Tools::IsOnPave1(aT1, aR12, aTol) ||
 330             IntTools_Tools::IsOnPave1(aR12.Last(), aCR1, aTol);
 331           bIsOnPave[2] = IntTools_Tools::IsOnPave1(aT2, aR21, aTol) ||
 332             IntTools_Tools::IsOnPave1(aR21.First(), aCR2, aTol);
 333           bIsOnPave[3] = IntTools_Tools::IsOnPave1(aT2, aR22, aTol) ||
 334             IntTools_Tools::IsOnPave1(aR22.Last(), aCR2, aTol);
 335           //
 336           aPB1->Indices(nV[0], nV[1]);
 337           aPB2->Indices(nV[2], nV[3]);
 338           //
 339           if((bIsOnPave[0] && bIsOnPave[2]) ||
 340              (bIsOnPave[0] && bIsOnPave[3]) ||
 341              (bIsOnPave[1] && bIsOnPave[2]) ||
 342              (bIsOnPave[1] && bIsOnPave[3])) {
 343             continue;
 344           }
 345           //
 346           bFlag = Standard_False;
 347           for (j = 0; j < 4; ++j) {
 348             if (bIsOnPave[j]) {
 349               //add interf VE(nV[j], nE)
 350               Handle(BOPDS_PaveBlock)& aPB = (j < 2) ? aPB2 : aPB1;
 351               bFlag = ForceInterfVE(nV[j], aPB, aMEdges);
 352               break;
 353             }
 354           }
 355           if (bFlag) {
 356             BOPDS_InterfEE& aEE = aEEs.Appended();
 357             aEE.SetIndices(nE1, nE2);
 358             aEE.SetCommonPart(aCPart);
 359             continue;
 360           }
 361           //
 362           BOPTools_AlgoTools::MakeNewVertex(aE1, aT1, aE2, aT2, aVnew);
 363           Standard_Real aTolVnew = BRep_Tool::Tolerance(aVnew);
 364           if (bAnalytical) {
 365             // increase tolerance for Line/Line intersection, but do not update
 366             // the vertex till its intersection with some other shape
 367             Standard_Real aTolMin = (BRepAdaptor_Curve(aE1).GetType() == GeomAbs_Line) ?
 368               (aCR1.Last() - aCR1.First()) / 2. : (aCR2.Last() - aCR2.First()) / 2.;
 369             if (aTolMin > aTolVnew) {
 370               aTolVnew = aTolMin;
 371             }
 372           }
 373           // <-LXBR
 374           {
 375             Standard_Integer nVS[2], iFound;
 376             Standard_Real aTolVx, aD2, aDT2;
 377             TColStd_MapOfInteger aMV;
 378             gp_Pnt aPnew, aPx;
 379             //
 380             iFound=0;
 381             j=-1;
 382             aMV.Add(nV[0]);
 383             aMV.Add(nV[1]);
 384             //
 385             if (aMV.Contains(nV[2])) {
 386               ++j;
 387               nVS[j]=nV[2];
 388             }
 389             if (aMV.Contains(nV[3])) {
 390               ++j;
 391               nVS[j]=nV[3];
 392             }
 393             //
 394             aPnew=BRep_Tool::Pnt(aVnew);
 395             //
 396             for (Standard_Integer k1=0; k1<=j; ++k1) {
 397               const TopoDS_Vertex& aVx= *(TopoDS_Vertex*)&(myDS->Shape(nVS[k1]));
 398               aTolVx=BRep_Tool::Tolerance(aVx);
 399               aPx=BRep_Tool::Pnt(aVx);
 400               aD2=aPnew.SquareDistance(aPx);
 401               //
 402               aDT2=100.*(aTolVnew+aTolVx)*(aTolVnew+aTolVx);
 403               //
 404               if (aD2<aDT2) {
 405                 iFound=1;
 406                 break;
 407               }
 408             }
 409             //
 410             if (iFound) {
 411               continue;
 412             }
 413           }
 414           //
 415           // 1
 416           BOPDS_InterfEE& aEE=aEEs.Appended();
 417           iX=aEEs.Length()-1;
 418           aEE.SetIndices(nE1, nE2);
 419           aEE.SetCommonPart(aCPart);
 420           // 2
 421           myDS->AddInterf(nE1, nE2);
 422           //
 423           BOPDS_CoupleOfPaveBlocks aCPB;
 424           //
 425           aCPB.SetPaveBlocks(aPB1, aPB2);
 426           aCPB.SetIndexInterf(iX);
 427           aCPB.SetTolerance(aTolVnew);
 428           aMVCPB.Add(aVnew, aCPB);
 429         }//case TopAbs_VERTEX:
 430           break;
 431             //
 432         case TopAbs_EDGE: {
 433           if (aNbCPrts > 1) {
 434             break;
 435           }
 436           //
 437           Standard_Boolean bHasSameBounds;
 438           bHasSameBounds=aPB1->HasSameBounds(aPB2);
 439           if (!bHasSameBounds) {
 440             break;
 441           }
 442           // 1
 443           BOPDS_InterfEE& aEE=aEEs.Appended();
 444           iX=aEEs.Length()-1;
 445           aEE.SetIndices(nE1, nE2);
 446           aEE.SetCommonPart(aCPart);
 447           // 2
 448           myDS->AddInterf(nE1, nE2);
 449           //
 450           BOPAlgo_Tools::FillMap<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aPB1, aPB2, aMPBLPB, aAllocator);
 451         }//case TopAbs_EDGE
 452           break;
 453         default:
 454           break;
 455       }//switch (aType) {
 456     }//for (i=1; i<=aNbCPrts; i++) {
 457   }//for (k=0; k < aNbFdgeEdge; ++k) {
 458   //
 459   //=========================================
 460   // post treatment
 461   //=========================================
 462   BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, aAllocator, myDS);
 463   PerformNewVertices(aMVCPB, aAllocator);
 464   //
 465   if (aMEdges.Extent()) {
 466     Standard_Integer aNbV = aMVCPB.Extent();
 467     for (i = 1; i <= aNbV; ++i) {
 468       Handle(BOPDS_PaveBlock) aPB1, aPB2;
 469       const BOPDS_CoupleOfPaveBlocks& aCPB = aMVCPB.FindFromIndex(i);
 470       aCPB.PaveBlocks(aPB1, aPB2);
 471       //
 472       aMEdges.Remove(aPB1->OriginalEdge());
 473       aMEdges.Remove(aPB2->OriginalEdge());
 474     }
 475     //
 476     SplitPaveBlocks(aMEdges, Standard_False);
 477   }
 478   //
 479   //-----------------------------------------------------scope t
 480   aMPBLPB.Clear();
 481   aMVCPB.Clear();
 482 }
 483 //=======================================================================
 484 //function : PerformVerticesEE
 485 //purpose  :
 486 //=======================================================================
 487 void BOPAlgo_PaveFiller::PerformNewVertices
 488   (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
 489    const Handle(NCollection_BaseAllocator)& theAllocator,
 490    const Standard_Boolean bIsEEIntersection)
 491 {
 492   Standard_Integer aNbV = theMVCPB.Extent();
 493   if (!aNbV) {
 494     return;
 495   }
 496   //
 497   Standard_Real aTolAdd = myFuzzyValue / 2.;
 498   //
 499   // 1. Fuse the new vertices
 500   TopTools_IndexedDataMapOfShapeListOfShape aImages;
 501   TreatNewVertices(theMVCPB, aImages);
 502   //
 503   // 2. Add new vertices to myDS and connect indices to CPB structure
 504   BOPDS_VectorOfInterfEE& aEEs = myDS->InterfEE();
 505   BOPDS_VectorOfInterfEF& aEFs = myDS->InterfEF();
 506   //
 507   Standard_Integer i, aNb = aImages.Extent();
 508   for (i = 1; i <= aNb; ++i) {
 509     const TopoDS_Vertex& aV = TopoDS::Vertex(aImages.FindKey(i));
 510     const TopTools_ListOfShape& aLVSD = aImages.FindFromIndex(i);
 511     //
 512     BOPDS_ShapeInfo aSI;
 513     aSI.SetShapeType(TopAbs_VERTEX);
 514     aSI.SetShape(aV);
 515     Standard_Integer iV = myDS->Append(aSI);
 516     //
 517     BOPDS_ShapeInfo& aSIDS = myDS->ChangeShapeInfo(iV);
 518     Bnd_Box& aBox = aSIDS.ChangeBox();
 519     aBox.Add(BRep_Tool::Pnt(aV));
 520     aBox.SetGap(BRep_Tool::Tolerance(aV) + aTolAdd);
 521     //
 522     TopTools_ListIteratorOfListOfShape aItLS(aLVSD);
 523     for (; aItLS.More(); aItLS.Next()) {
 524       const TopoDS_Shape& aVx = aItLS.Value();
 525       BOPDS_CoupleOfPaveBlocks &aCPB = theMVCPB.ChangeFromKey(aVx);
 526       aCPB.SetIndex(iV);
 527       // update interference
 528       Standard_Integer iX = aCPB.IndexInterf();
 529       BOPDS_Interf *aInt = bIsEEIntersection ? (BOPDS_Interf*)(&aEEs(iX)) : (BOPDS_Interf*) (&aEFs(iX));
 530       aInt->SetIndexNew(iV);
 531     }
 532   }
 533   //
 534   // 3. Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
 535   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
 536   for (i = 1; i <= aNbV; ++i) {
 537     const BOPDS_CoupleOfPaveBlocks& aCPB = theMVCPB.FindFromIndex(i);
 538     Standard_Integer iV = aCPB.Index();
 539     //
 540     Handle(BOPDS_PaveBlock) aPB[2];
 541     aCPB.PaveBlocks(aPB[0], aPB[1]);
 542     for (Standard_Integer j = 0; j < 2; ++j) {
 543       TColStd_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB[j]);
 544       if (!pLI) {
 545         pLI = &aMPBLI(aMPBLI.Add(aPB[j], TColStd_ListOfInteger(theAllocator)));
 546       }
 547       pLI->Append(iV);
 548       //
 549       if (aPB[0] == aPB[1]) {
 550         break;
 551       }
 552     }
 553   }
 554   //
 555   // 4. Compute Extra Paves and split Pave blocks by the Extra paves
 556   IntersectVE(aMPBLI, Standard_False);
 557 }
 558 //=======================================================================
 559 //function : TreatNewVertices
 560 //purpose  :
 561 //=======================================================================
 562 void BOPAlgo_PaveFiller::TreatNewVertices
 563   (const BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
 564    TopTools_IndexedDataMapOfShapeListOfShape& myImages)
 565 {
 566   //
 567   // Prepare for intersection
 568   TopTools_IndexedDataMapOfShapeReal aVerts;
 569   Standard_Integer i, aNbV = theMVCPB.Extent();
 570   for (i = 1; i <= aNbV; ++i) {
 571     const TopoDS_Shape& aV = theMVCPB.FindKey(i);
 572     Standard_Real aTol = theMVCPB.FindFromIndex(i).Tolerance();
 573     aVerts.Add(aV, aTol);
 574   }
 575   //
 576   // Perform intersection
 577   TopTools_ListOfListOfShape aChains;
 578   BOPAlgo_Tools::IntersectVertices(aVerts, myRunParallel, myFuzzyValue, aChains);
 579   //
 580   // Treat the results - make new vertices for each chain
 581   TopTools_ListOfListOfShape::Iterator aItC(aChains);
 582   for (; aItC.More(); aItC.Next()) {
 583     const TopTools_ListOfShape& aLVSD = aItC.Value();
 584     //
 585     TopoDS_Vertex aVNew;
 586     BOPTools_AlgoTools::MakeVertex(aLVSD, aVNew);
 587     myImages.Add(aVNew, aLVSD);
 588   }
 589 }
 590 //=======================================================================
 591 //function : FillShrunkData
 592 //purpose  :
 593 //=======================================================================
 594 void BOPAlgo_PaveFiller::FillShrunkData(Handle(BOPDS_PaveBlock)& thePB)
 595 {
 596   // Vertices
 597   Standard_Integer nV1, nV2;
 598   thePB->Indices(nV1, nV2);
 599   const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1)));
 600   const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2)));
 601   // Original edge
 602   Standard_Integer nE = thePB->OriginalEdge();
 603   const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
 604   // Range
 605   Standard_Real aT1, aT2;
 606   thePB->Range(aT1, aT2);
 607   //
 608   IntTools_ShrunkRange aSR;
 609   aSR.SetContext(myContext);
 610   aSR.SetData(aE, aT1, aT2, aV1, aV2);
 611   aSR.Perform();
 612   // Analyze the results of computations
 613   AnalyzeShrunkData(thePB, aSR);
 614 }
 615 //=======================================================================
 616 // function: AnalyzeShrunkData
 617 // purpose:
 618 //=======================================================================
 619 void BOPAlgo_PaveFiller::AnalyzeShrunkData(const Handle(BOPDS_PaveBlock)& thePB,
 620                                            const IntTools_ShrunkRange& theSR)
 621 {
 622   // in case of error treat the warning status
 623   Standard_Boolean bWholeEdge = Standard_False;
 624   TopoDS_Shape aWarnShape;
 625   //
 626   if (!theSR.IsDone() || !theSR.IsSplittable()) {
 627     Standard_Real aEFirst, aELast, aPBFirst, aPBLast;
 628     BRep_Tool::Range(theSR.Edge(), aEFirst, aELast);
 629     thePB->Range(aPBFirst, aPBLast);
 630     bWholeEdge = !(aPBFirst > aEFirst || aPBLast < aELast);
 631     if (bWholeEdge) {
 632       aWarnShape = theSR.Edge();
 633     }
 634     else {
 635       const TopoDS_Shape& aV1 = myDS->Shape(thePB->Pave1().Index());
 636       const TopoDS_Shape& aV2 = myDS->Shape(thePB->Pave2().Index());
 637       BRep_Builder().MakeCompound(TopoDS::Compound(aWarnShape));
 638       BRep_Builder().Add(aWarnShape, theSR.Edge());
 639       BRep_Builder().Add(aWarnShape, aV1);
 640       BRep_Builder().Add(aWarnShape, aV2);
 641     }
 642     //
 643     if (!theSR.IsDone()) {
 644       if (bWholeEdge)
 645         AddWarning (new BOPAlgo_AlertTooSmallEdge (aWarnShape));
 646       else
 647         AddWarning (new BOPAlgo_AlertBadPositioning (aWarnShape));
 648       Standard_Real aTS1, aTS2;
 649       theSR.ShrunkRange(aTS1, aTS2);
 650       thePB->SetShrunkData(aTS1, aTS2, Bnd_Box(), Standard_False);
 651       return;
 652     }
 653     //
 654     if (bWholeEdge)
 655       AddWarning (new BOPAlgo_AlertNotSplittableEdge (aWarnShape));
 656     else
 657       AddWarning (new BOPAlgo_AlertBadPositioning (aWarnShape));
 658   }
 659   //
 660   Standard_Real aTS1, aTS2;
 661   theSR.ShrunkRange(aTS1, aTS2);
 662   Bnd_Box aBox = theSR.BndBox();
 663   aBox.SetGap(aBox.GetGap() + myFuzzyValue / 2.);
 664   thePB->SetShrunkData(aTS1, aTS2, aBox, theSR.IsSplittable());
 665 }
 666 //=======================================================================
 667 //function : ForceInterfVE
 668 //purpose  :
 669 //=======================================================================
 670 Standard_Boolean BOPAlgo_PaveFiller::ForceInterfVE(const Standard_Integer nV,
 671                                                    Handle(BOPDS_PaveBlock)& aPB,
 672                                                    TColStd_MapOfInteger& theMEdges)
 673 {
 674   Standard_Integer nE, nVx, nVSD, iFlag;
 675   Standard_Real aT, aTolVNew;
 676   //
 677   nE = aPB->OriginalEdge();
 678   //
 679   const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
 680   if (aSIE.HasSubShape(nV)) {
 681     return Standard_False;
 682   }
 683   //
 684   if (myDS->HasInterf(nV, nE)) {
 685     return Standard_False;
 686   }
 687   //
 688   if (myDS->HasInterfShapeSubShapes(nV, nE)) {
 689     return Standard_False;
 690   }
 691   //
 692   if (aPB->Pave1().Index() == nV ||
 693       aPB->Pave2().Index() == nV) {
 694     return Standard_False;
 695   }
 696   //
 697   nVx = nV;
 698   if (myDS->HasShapeSD(nV, nVSD)) {
 699     nVx = nVSD;
 700   }
 701   //
 702   const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nVx);
 703   const TopoDS_Edge&   aE = *(TopoDS_Edge*)  &myDS->Shape(nE);
 704   //
 705   iFlag = myContext->ComputeVE(aV, aE, aT, aTolVNew, myFuzzyValue);
 706   if (iFlag == 0 || iFlag == -4) {
 707     BOPDS_Pave aPave;
 708     //
 709     //
 710     BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
 711     aVEs.SetIncrement(10);
 712     // 1
 713     BOPDS_InterfVE& aVE=aVEs.Appended();
 714     aVE.SetIndices(nV, nE);
 715     aVE.SetParameter(aT);
 716     // 2
 717     myDS->AddInterf(nV, nE);
 718     //
 719     // 3 update vertex V/E if necessary
 720     nVx=UpdateVertex(nV, aTolVNew);
 721     // 4
 722     if (myDS->IsNewShape(nVx)) {
 723       aVE.SetIndexNew(nVx);
 724     }
 725     // 5 append ext pave to pave block
 726     aPave.SetIndex(nVx);
 727     aPave.SetParameter(aT);
 728     aPB->AppendExtPave(aPave);
 729     //
 730     theMEdges.Add(nE);
 731     //
 732     // check for self-interference
 733     Standard_Integer iRV = myDS->Rank(nV);
 734     if (iRV >= 0 && iRV == myDS->Rank(nE)) {
 735       // add warning status
 736       TopoDS_Compound aWC;
 737       BRep_Builder().MakeCompound(aWC);
 738       BRep_Builder().Add(aWC, aV);
 739       BRep_Builder().Add(aWC, aE);
 740       AddWarning (new BOPAlgo_AlertSelfInterferingShape (aWC));
 741     }
 742     return Standard_True;
 743   }
 744   return Standard_False;
 745 }
 746
 747 //=======================================================================
 748 //function : GetPBBox
 749 //purpose  :
 750 //=======================================================================
 751 Standard_Boolean BOPAlgo_PaveFiller::GetPBBox(const TopoDS_Edge& theE,
 752                                               const Handle(BOPDS_PaveBlock)& thePB,
 753                                               BOPAlgo_DataMapOfPaveBlockBndBox& thePBBox,
 754                                               Standard_Real& theFirst,
 755                                               Standard_Real& theLast,
 756                                               Standard_Real& theSFirst,
 757                                               Standard_Real& theSLast,
 758                                               Bnd_Box& theBox)
 759 {
 760   thePB->Range(theFirst, theLast);
 761   // check the validity of PB's range
 762   Standard_Boolean bValid = theLast - theFirst > Precision::PConfusion();
 763   if (!bValid) {
 764     return bValid;
 765   }
 766   //
 767   // check shrunk data
 768   if (thePB->HasShrunkData()) {
 769     Standard_Boolean bIsSplittable;
 770     thePB->ShrunkData(theSFirst, theSLast, theBox, bIsSplittable);
 771     return bValid;
 772   }
 773   //
 774   theSFirst = theFirst;
 775   theSLast = theLast;
 776   // check the map
 777   if (thePBBox.IsBound(thePB)) {
 778     theBox = thePBBox.Find(thePB);
 779   }
 780   else {
 781     // build bounding box
 782     BRepAdaptor_Curve aBAC(theE);
 783     Standard_Real aTol = BRep_Tool::Tolerance(theE) + Precision::Confusion();
 784     BndLib_Add3dCurve::Add(aBAC, theSFirst, theSLast, aTol, theBox);
 785     thePBBox.Bind(thePB, theBox);
 786   }
 787   return bValid;
 788 }
 789
 790 //=======================================================================
 791 //function : ForceInterfEE
 792 //purpose  :
 793 //=======================================================================
 794 void BOPAlgo_PaveFiller::ForceInterfEE()
 795 {
 796   // Now that we have vertices increased and unified, try to find additional
 797   // common blocks among the pairs of edges that did not participate in
 798   // intersection (PerformEE() method) due to being rejected by bounding boxes.
 799   // Here, we are interested in common blocks only, as all real intersections
 800   // should have happened already. Thus, we need to look only for the same
 801   // vertices in the pairs of pave blocks and check the coincidence of such pave blocks.
 802
 803   Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
 804
 805   // Initialize pave blocks for all SD vertices
 806   Standard_Integer i, aNbS = myDS->NbSourceShapes();
 807   for (i = 0; i < aNbS; ++i)
 808   {
 809     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
 810     if (aSI.ShapeType() == TopAbs_VERTEX)
 811     {
 812       Standard_Integer nVSD;
 813       if (myDS->HasShapeSD(i, nVSD))
 814         myDS->InitPaveBlocksForVertex(i);
 815     }
 816   }
 817
 818   // Find all Pave Blocks with both paves being SD vertices.
 819   NCollection_IndexedDataMap<BOPDS_Pair,
 820                              BOPDS_ListOfPaveBlock,
 821                              BOPDS_PairMapHasher> aPBMap(1, anAlloc);
 822   // Fence map of pave blocks
 823   BOPDS_MapOfPaveBlock aMPBFence(1, anAlloc);
 824
 825   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
 826   Standard_Integer aNbPBP = aPBP.Length();
 827   for (i = 0; i < aNbPBP; ++i)
 828   {
 829     BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
 830     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
 831     for (; aItLPB.More(); aItLPB.Next())
 832     {
 833       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
 834       const Handle(BOPDS_PaveBlock)& aPBR = myDS->RealPaveBlock(aPB);
 835       if (!aMPBFence.Add(aPBR))
 836         continue;
 837
 838       // Get indices
 839       Standard_Integer nV1, nV2;
 840       aPBR->Indices(nV1, nV2);
 841
 842       // Add pave block to a map
 843       BOPDS_Pair aPair(nV1, nV2);
 844       BOPDS_ListOfPaveBlock *pList = aPBMap.ChangeSeek(aPair);
 845       if (!pList)
 846         pList = &aPBMap(aPBMap.Add(aPair, BOPDS_ListOfPaveBlock(anAlloc)));
 847       pList->Append(aPBR);
 848     }
 849   }
 850
 851   Standard_Integer aNbPB = aPBMap.Extent();
 852   if (!aNbPB)
 853     return;
 854
 855   // Find pairs of Pave Blocks having the same SD vertices,
 856   // rejecting the pairs of edges that have already been intersected
 857
 858   // Prepare map of pairs of intersected edges
 859   BOPDS_MapOfPair aMEEDone(1, anAlloc);
 860   myIterator->Initialize(TopAbs_EDGE, TopAbs_EDGE);
 861   for (; myIterator->More(); myIterator->Next())
 862   {
 863     Standard_Integer nE1, nE2;
 864     myIterator->Value(nE1, nE2);
 865     aMEEDone.Add(BOPDS_Pair(nE1, nE2));
 866   }
 867
 868   // Vector of pairs for intersection
 869   BOPAlgo_VectorOfEdgeEdge aVEdgeEdge;
 870
 871   for (i = 1; i <= aNbPB; ++i)
 872   {
 873     const BOPDS_ListOfPaveBlock& aLPB = aPBMap(i);
 874     if (aLPB.Extent() < 2)
 875       continue;
 876
 877     const BOPDS_Pair& aPair = aPBMap.FindKey(i);
 878     Standard_Integer nV1, nV2;
 879     aPair.Indices(nV1, nV2);
 880
 881     const TopoDS_Vertex& aV1 = TopoDS::Vertex(myDS->Shape(nV1));
 882     const TopoDS_Vertex& aV2 = TopoDS::Vertex(myDS->Shape(nV2));
 883
 884     // Use the max tolerance of vertices as Fuzzy value for intersection
 885     // of edges
 886     Standard_Real aTolAdd = 2 * Max(BRep_Tool::Tolerance(aV1),
 887                                     BRep_Tool::Tolerance(aV2));
 888
 889     // All possible pairs combined from the list <aLPB> should be checked
 890     BOPDS_ListIteratorOfListOfPaveBlock aItLPB1(aLPB);
 891     for (; aItLPB1.More(); aItLPB1.Next())
 892     {
 893       const Handle(BOPDS_PaveBlock)& aPB1 = aItLPB1.Value();
 894       const Standard_Integer nE1 = aPB1->OriginalEdge();
 895       const TopoDS_Edge& aE1 = TopoDS::Edge(myDS->Shape(nE1));
 896       Standard_Real aT11, aT12;
 897       aPB1->Range(aT11, aT12);
 898
 899       BOPDS_ListIteratorOfListOfPaveBlock aItLPB2 = aItLPB1;
 900       for (aItLPB2.Next(); aItLPB2.More(); aItLPB2.Next())
 901       {
 902         const Handle(BOPDS_PaveBlock)& aPB2 = aItLPB2.Value();
 903         const Standard_Integer nE2 = aPB2->OriginalEdge();
 904
 905         if (aMEEDone.Contains(BOPDS_Pair(nE1, nE2)))
 906           continue;
 907
 908         // Make sure that the edges came from different arguments
 909         if (myDS->Rank(nE1) == myDS->Rank(nE2))
 910           continue;
 911
 912         const TopoDS_Edge& aE2 = TopoDS::Edge(myDS->Shape(nE2));
 913         Standard_Real aT21, aT22;
 914         aPB2->Range(aT21, aT22);
 915
 916         // Add pair for intersection
 917         BOPAlgo_EdgeEdge& anEdgeEdge = aVEdgeEdge.Appended();
 918         anEdgeEdge.UseQuickCoincidenceCheck(Standard_True);
 919         anEdgeEdge.SetPaveBlock1(aPB1);
 920         anEdgeEdge.SetPaveBlock2(aPB2);
 921         anEdgeEdge.SetEdge1(aE1, aT11, aT12);
 922         anEdgeEdge.SetEdge2(aE2, aT21, aT22);
 923         anEdgeEdge.SetFuzzyValue(myFuzzyValue + aTolAdd);
 924         anEdgeEdge.SetProgressIndicator(myProgressIndicator);
 925       }
 926     }
 927   }
 928
 929   Standard_Integer aNbPairs = aVEdgeEdge.Length();
 930   if (!aNbPairs)
 931     return;
 932
 933   aPBMap.Clear();
 934   aMPBFence.Clear();
 935   aMEEDone.Clear();
 936   anAlloc->Reset();
 937
 938   // Perform intersection of the found pairs
 939   BOPAlgo_EdgeEdgeCnt::Perform(myRunParallel, aVEdgeEdge);
 940
 941   BOPDS_VectorOfInterfEE& aEEs = myDS->InterfEE();
 942   if (aEEs.IsEmpty())
 943     aEEs.SetIncrement(10);
 944
 945   // Analyze the results of intersection looking for TopAbs_EDGE
 946   // intersection type only.
 947
 948   BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(1, anAlloc);
 949
 950   for (i = 0; i < aNbPairs; ++i)
 951   {
 952     BOPAlgo_EdgeEdge& anEdgeEdge = aVEdgeEdge(i);
 953     if (!anEdgeEdge.IsDone() || anEdgeEdge.HasErrors())
 954     {
 955       // Warn about failed intersection of sub-shapes
 956       const TopoDS_Shape& aE1 = myDS->Shape(anEdgeEdge.PaveBlock1()->OriginalEdge());
 957       const TopoDS_Shape& aE2 = myDS->Shape(anEdgeEdge.PaveBlock2()->OriginalEdge());
 958       AddIntersectionFailedWarning(aE1, aE2);
 959       continue;
 960     }
 961
 962     const IntTools_SequenceOfCommonPrts& aCParts = anEdgeEdge.CommonParts();
 963     if (aCParts.Length() != 1)
 964       continue;
 965
 966     const IntTools_CommonPrt& aCP = aCParts(1);
 967     if (aCP.Type() != TopAbs_EDGE)
 968       continue;
 969
 970     Handle(BOPDS_PaveBlock) aPB[] = {anEdgeEdge.PaveBlock1(), anEdgeEdge.PaveBlock2()};
 971     const Standard_Integer nE1 = aPB[0]->OriginalEdge();
 972     const Standard_Integer nE2 = aPB[1]->OriginalEdge();
 973
 974     BOPDS_InterfEE& aEE = aEEs.Appended();
 975     aEE.SetIndices(nE1, nE2);
 976     aEE.SetCommonPart(aCP);
 977     myDS->AddInterf(nE1, nE2);
 978
 979     // Fill map for common blocks creation
 980     for (Standard_Integer j = 0; j < 2; ++j)
 981     {
 982       if (myDS->IsCommonBlock(aPB[j]))
 983       {
 984         const BOPDS_ListOfPaveBlock& aLPBCB = myDS->CommonBlock(aPB[j])->PaveBlocks();
 985         BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPBCB);
 986         for (; aItLPB.More(); aItLPB.Next())
 987           BOPAlgo_Tools::FillMap<Handle(BOPDS_PaveBlock),
 988                            TColStd_MapTransientHasher>(aPB[j], aItLPB.Value(), aMPBLPB, anAlloc);
 989       }
 990     }
 991     BOPAlgo_Tools::FillMap<Handle(BOPDS_PaveBlock),
 992                            TColStd_MapTransientHasher>(aPB[0], aPB[1], aMPBLPB, anAlloc);
 993   }
 994
 995   // Create new common blocks of coinciding pairs.
 996   BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, anAlloc, myDS);
 997 }