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_SectionAttribute.hxx>
  22 #include <BOPAlgo_Tools.hxx>
  23 #include <BOPCol_BoxBndTree.hxx>
  24 #include <BOPCol_DataMapOfIntegerShape.hxx>
  25 #include <BOPCol_DataMapOfShapeInteger.hxx>
  26 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
  27 #include <BOPCol_IndexedDataMapOfShapeBox.hxx>
  28 #include <BOPCol_NCVector.hxx>
  29 #include <BOPCol_Parallel.hxx>
  30 #include <BOPDS_CommonBlock.hxx>
  31 #include <BOPDS_CoupleOfPaveBlocks.hxx>
  32 #include <BOPDS_Curve.hxx>
  33 #include <BOPDS_DataMapOfPaveBlockListOfInteger.hxx>
  34 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
  35 #include <BOPDS_DS.hxx>
  36 #include <BOPDS_Interf.hxx>
  37 #include <BOPDS_Iterator.hxx>
  38 #include <BOPDS_MapOfPaveBlock.hxx>
  39 #include <BOPDS_Pave.hxx>
  40 #include <BOPDS_PaveBlock.hxx>
  41 #include <BOPDS_VectorOfInterfEE.hxx>
  42 #include <BOPTools_AlgoTools.hxx>
  43 #include <BndLib_Add3dCurve.hxx>
  44 #include <BRep_Tool.hxx>
  45 #include <BRepBndLib.hxx>
  46 #include <BRepTools.hxx>
  47 #include <BRepAdaptor_Curve.hxx>
  48 #include <gp_Pnt.hxx>
  49 #include <IntTools_CommonPrt.hxx>
  50 #include <IntTools_Context.hxx>
  51 #include <IntTools_EdgeEdge.hxx>
  52 #include <IntTools_Range.hxx>
  53 #include <IntTools_SequenceOfCommonPrts.hxx>
  54 #include <IntTools_SequenceOfRanges.hxx>
  55 #include <IntTools_ShrunkRange.hxx>
  56 #include <IntTools_Tools.hxx>
  57 #include <NCollection_UBTreeFiller.hxx>
  58 #include <Precision.hxx>
  59 #include <TopoDS_Compound.hxx>
  60 #include <TopoDS_Edge.hxx>
  61 #include <TopoDS_Face.hxx>
  62 #include <TopoDS_Vertex.hxx>
  63
  64 /////////////////////////////////////////////////////////////////////////
  65 //=======================================================================
  66 //class    : BOPAlgo_EdgeEdge
  67 //purpose  :
  68 //=======================================================================
  69 class BOPAlgo_EdgeEdge :
  70   public IntTools_EdgeEdge,
  71   public BOPAlgo_Algo {
  72
  73  public:
  74
  75   DEFINE_STANDARD_ALLOC
  76   //
  77   BOPAlgo_EdgeEdge():
  78     IntTools_EdgeEdge(),
  79     BOPAlgo_Algo() {
  80   };
  81   //
  82   virtual ~BOPAlgo_EdgeEdge(){
  83   };
  84   //
  85   void SetPaveBlock1(const Handle(BOPDS_PaveBlock)& aPB) {
  86     myPB1=aPB;
  87   }
  88   //
  89   Handle(BOPDS_PaveBlock)& PaveBlock1() {
  90     return myPB1;
  91   }
  92   //
  93   void SetPaveBlock2(const Handle(BOPDS_PaveBlock)& aPB) {
  94     myPB2=aPB;
  95   }
  96   //
  97   Handle(BOPDS_PaveBlock)& PaveBlock2() {
  98     return myPB2;
  99   }
 100   //
 101   void SetFuzzyValue(const Standard_Real theFuzz) {
 102     IntTools_EdgeEdge::SetFuzzyValue(theFuzz);
 103   }
 104   //
 105   virtual void Perform() {
 106     BOPAlgo_Algo::UserBreak();
 107     IntTools_EdgeEdge::Perform();
 108   }
 109   //
 110  protected:
 111   Handle(BOPDS_PaveBlock) myPB1;
 112   Handle(BOPDS_PaveBlock) myPB2;
 113 };
 114 //
 115 //=======================================================================
 116 typedef BOPCol_NCVector
 117   <BOPAlgo_EdgeEdge> BOPAlgo_VectorOfEdgeEdge;
 118 //
 119 typedef BOPCol_Functor
 120   <BOPAlgo_EdgeEdge,
 121   BOPAlgo_VectorOfEdgeEdge> BOPAlgo_EdgeEdgeFunctor;
 122 //
 123 typedef BOPCol_Cnt
 124   <BOPAlgo_EdgeEdgeFunctor,
 125   BOPAlgo_VectorOfEdgeEdge> BOPAlgo_EdgeEdgeCnt;
 126 //
 127 /////////////////////////////////////////////////////////////////////////
 128 //=======================================================================
 129 //class    : BOPAlgo_TNV
 130 //purpose  :
 131 //=======================================================================
 132 class BOPAlgo_TNV;
 133 typedef BOPCol_NCVector
 134   <BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
 135 //
 136 typedef BOPCol_Functor
 137   <BOPAlgo_TNV,
 138   BOPAlgo_VectorOfTNV> BOPAlgo_TNVFunctor;
 139 //
 140 typedef BOPCol_Cnt
 141   <BOPAlgo_TNVFunctor,
 142   BOPAlgo_VectorOfTNV> BOPAlgo_TNVCnt;
 143 //=======================================================================
 144 class BOPAlgo_TNV : public BOPCol_BoxBndTreeSelector{
 145  public:
 146   BOPAlgo_TNV()
 147     : BOPCol_BoxBndTreeSelector(),
 148       myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
 149   };
 150   //
 151   ~BOPAlgo_TNV(){
 152   };
 153   //
 154   void SetVertex(const TopoDS_Vertex& aV) {
 155     myV=aV;
 156     myPnt = BRep_Tool::Pnt(myV);
 157   }
 158   //
 159   const TopoDS_Vertex& Vertex()const {
 160     return myV;
 161   }
 162   //
 163   void SetTree(BOPCol_BoxBndTree& aTree) {
 164     myTree=&aTree;
 165   }
 166   //
 167   void SetTolerance(const Standard_Real theTol) {
 168     myTol = theTol;
 169   }
 170   //
 171   Standard_Real Tolerance() const {
 172     return myTol;
 173   }
 174   //
 175   const gp_Pnt& Pnt() const {
 176     return myPnt;
 177   }
 178   //
 179   void SetFuzzyValue(const Standard_Real theFuzzyValue) {
 180     myFuzzyValue = theFuzzyValue;
 181   }
 182   //
 183   void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
 184     myVecTNV = &theVec;
 185   }
 186   //
 187   virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
 188   {
 189     const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
 190     Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
 191     aTolSum2 *= aTolSum2;
 192     Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
 193     if (aD2 < aTolSum2)
 194       return BOPCol_BoxBndTreeSelector::Accept(theIndex);
 195     return Standard_False;
 196   }
 197   //
 198   void Perform() {
 199     myTree->Select(*this);
 200   }
 201   //
 202  protected:
 203   Standard_Real myTol;
 204   Standard_Real myFuzzyValue;
 205   gp_Pnt        myPnt;
 206   TopoDS_Vertex myV;
 207   BOPCol_BoxBndTree *myTree;
 208   const BOPAlgo_VectorOfTNV *myVecTNV;
 209 };
 210 //
 211 /////////////////////////////////////////////////////////////////////////
 212 //=======================================================================
 213 //class    : BOPAlgo_PVE
 214 //purpose  :
 215 //=======================================================================
 216 class BOPAlgo_PVE {
 217  public:
 218   BOPAlgo_PVE()
 219     : myIV(-1), myIE(-1), myFlag(-1), myT(-1.) {
 220   };
 221   //
 222   ~BOPAlgo_PVE(){
 223   };
 224   //
 225   void SetIndices(const Standard_Integer nV,
 226                   const Standard_Integer nE){
 227     myIV=nV;
 228     myIE=nE;
 229   }
 230   //
 231   void Indices(Standard_Integer& nV,
 232                Standard_Integer& nE) const {
 233     nV=myIV;
 234     nE=myIE;
 235   }
 236   //
 237   void SetVertex(const TopoDS_Vertex& aV) {
 238     myV=aV;
 239   }
 240   //
 241   const TopoDS_Vertex& Vertex()const {
 242     return myV;
 243   }
 244   //
 245   void SetEdge(const TopoDS_Edge& aE) {
 246     myE=aE;
 247   }
 248   //
 249   const TopoDS_Edge& Edge()const {
 250     return myE;
 251   }
 252   //
 253   void SetPaveBlock(const Handle(BOPDS_PaveBlock)& aPB) {
 254     myPB=aPB;
 255   }
 256   //
 257   Handle(BOPDS_PaveBlock)& PaveBlock() {
 258     return myPB;
 259   }
 260   //
 261   Standard_Integer Flag()const {
 262     return myFlag;
 263   }
 264   //
 265   Standard_Real Parameter()const {
 266     return myT;
 267   }
 268   //
 269   void SetContext(const Handle(IntTools_Context)& aContext) {
 270     myContext=aContext;
 271   }
 272   //
 273   const Handle(IntTools_Context)& Context()const {
 274     return myContext;
 275   }
 276   //
 277   void SetFuzzyValue(const Standard_Real theValue) {
 278     myFuzzyValue = theValue;
 279   }
 280   //
 281   void Perform() {
 282     Standard_Real dummy;
 283     myFlag = myContext->ComputeVE(myV, myE, myT, dummy, myFuzzyValue);
 284   };
 285   //
 286  protected:
 287   Standard_Integer myIV;
 288   Standard_Integer myIE;
 289   Standard_Integer myFlag;
 290   Standard_Real myT;
 291   Standard_Real myFuzzyValue;
 292   TopoDS_Vertex myV;
 293   TopoDS_Edge myE;
 294   Handle(BOPDS_PaveBlock) myPB;
 295   Handle(IntTools_Context) myContext;
 296 };
 297 //=======================================================================
 298 typedef BOPCol_NCVector
 299   <BOPAlgo_PVE> BOPAlgo_VectorOfPVE;
 300 //
 301 typedef BOPCol_ContextFunctor
 302   <BOPAlgo_PVE,
 303   BOPAlgo_VectorOfPVE,
 304   Handle(IntTools_Context),
 305   IntTools_Context> BOPAlgo_PVEFunctor;
 306 //
 307 typedef BOPCol_ContextCnt
 308   <BOPAlgo_PVEFunctor,
 309   BOPAlgo_VectorOfPVE,
 310   Handle(IntTools_Context)> BOPAlgo_PVECnt;
 311 /////////////////////////////////////////////////////////////////////////
 312 //=======================================================================
 313 // function: PerformEE
 314 // purpose:
 315 //=======================================================================
 316 void BOPAlgo_PaveFiller::PerformEE()
 317 {
 318   Standard_Integer iSize;
 319   //
 320   myErrorStatus=0;
 321   //
 322   FillShrunkData(TopAbs_EDGE, TopAbs_EDGE);
 323   //
 324   myIterator->Initialize(TopAbs_EDGE, TopAbs_EDGE);
 325   iSize=myIterator->ExpectedLength();
 326   if (!iSize) {
 327     return;
 328   }
 329   //
 330   Standard_Boolean bJustAdd, bExpressCompute, bIsPBSplittable1, bIsPBSplittable2;
 331   Standard_Integer i, iX, nE1, nE2, aNbCPrts, k, aNbEdgeEdge;
 332   Standard_Integer nV11, nV12, nV21, nV22;
 333   Standard_Real aTS11, aTS12, aTS21, aTS22, aT11, aT12, aT21, aT22;
 334   TopAbs_ShapeEnum aType;
 335   BOPDS_ListIteratorOfListOfPaveBlock aIt1, aIt2;
 336   Handle(NCollection_BaseAllocator) aAllocator;
 337   BOPDS_MapOfPaveBlock aMPBToUpdate;
 338   BOPAlgo_VectorOfEdgeEdge aVEdgeEdge;
 339   BOPDS_MapIteratorOfMapOfPaveBlock aItPB;
 340   //
 341   aAllocator=NCollection_BaseAllocator::CommonBaseAllocator();
 342   //-----------------------------------------------------scope f
 343   BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(100, aAllocator);
 344   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMVCPB(100, aAllocator);
 345   BOPAlgo_DataMapOfPaveBlockBndBox aDMPBBox(100, aAllocator);
 346   //
 347   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
 348   aEEs.SetIncrement(iSize);
 349   //
 350   for (; myIterator->More(); myIterator->Next()) {
 351     myIterator->Value(nE1, nE2, bJustAdd);
 352     if(bJustAdd) {
 353       continue;
 354     }
 355     //
 356     const BOPDS_ShapeInfo& aSIE1=myDS->ShapeInfo(nE1);
 357     if (aSIE1.HasFlag()){
 358       continue;
 359     }
 360     const BOPDS_ShapeInfo& aSIE2=myDS->ShapeInfo(nE2);
 361     if (aSIE2.HasFlag()){
 362       continue;
 363     }
 364     //
 365     const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aSIE1.Shape()));
 366     const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aSIE2.Shape()));
 367     //
 368     BOPDS_ListOfPaveBlock& aLPB1=myDS->ChangePaveBlocks(nE1);
 369     BOPDS_ListOfPaveBlock& aLPB2=myDS->ChangePaveBlocks(nE2);
 370     //
 371     aIt1.Initialize(aLPB1);
 372     for (; aIt1.More(); aIt1.Next()) {
 373       Bnd_Box aBB1;
 374       //
 375       Handle(BOPDS_PaveBlock)& aPB1=aIt1.ChangeValue();
 376       //
 377       if (!GetPBBox(aE1, aPB1, aDMPBBox, aT11, aT12, aTS11, aTS12, aBB1)) {
 378         continue;
 379       }
 380       //
 381       aPB1->Indices(nV11, nV12);
 382       //
 383       aIt2.Initialize(aLPB2);
 384       for (; aIt2.More(); aIt2.Next()) {
 385         Bnd_Box aBB2;
 386         //
 387         Handle(BOPDS_PaveBlock)& aPB2=aIt2.ChangeValue();
 388         //
 389         if (!GetPBBox(aE2, aPB2, aDMPBBox, aT21, aT22, aTS21, aTS22, aBB2)) {
 390           continue;
 391         }
 392         //
 393         if (aBB1.IsOut(aBB2)) {
 394           continue;
 395         }
 396         //
 397         aPB2->Indices(nV21, nV22);
 398         //
 399         bExpressCompute=((nV11==nV21 && nV12==nV22) ||
 400                          (nV12==nV21 && nV11==nV22));
 401         //
 402         BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge.Append1();
 403         //
 404         anEdgeEdge.UseQuickCoincidenceCheck(bExpressCompute);
 405         //
 406         anEdgeEdge.SetPaveBlock1(aPB1);
 407         anEdgeEdge.SetPaveBlock2(aPB2);
 408         //
 409         anEdgeEdge.SetEdge1(aE1, aT11, aT12);
 410         anEdgeEdge.SetEdge2(aE2, aT21, aT22);
 411         anEdgeEdge.SetFuzzyValue(myFuzzyValue);
 412         anEdgeEdge.SetProgressIndicator(myProgressIndicator);
 413       }//for (; aIt2.More(); aIt2.Next()) {
 414     }//for (; aIt1.More(); aIt1.Next()) {
 415   }//for (; myIterator->More(); myIterator->Next()) {
 416   //
 417   aNbEdgeEdge=aVEdgeEdge.Extent();
 418   //======================================================
 419   BOPAlgo_EdgeEdgeCnt::Perform(myRunParallel, aVEdgeEdge);
 420   //======================================================
 421   //
 422   for (k = 0; k < aNbEdgeEdge; ++k) {
 423     Bnd_Box aBB1, aBB2;
 424     //
 425     BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge(k);
 426     if (!anEdgeEdge.IsDone()) {
 427       continue;
 428     }
 429     //
 430     //--------------------------------------------
 431     Handle(BOPDS_PaveBlock)& aPB1=anEdgeEdge.PaveBlock1();
 432     nE1=aPB1->OriginalEdge();
 433     aPB1->Range(aT11, aT12);
 434     if (!aPB1->HasShrunkData()) {
 435       aTS11 = aT11;
 436       aTS12 = aT12;
 437       bIsPBSplittable1 = Standard_False;
 438     }
 439     else {
 440       aPB1->ShrunkData(aTS11, aTS12, aBB1, bIsPBSplittable1);
 441     }
 442     //
 443     Handle(BOPDS_PaveBlock)& aPB2=anEdgeEdge.PaveBlock2();
 444     nE2=aPB2->OriginalEdge();
 445     aPB2->Range(aT21, aT22);
 446     if (!aPB2->HasShrunkData()) {
 447       aTS21 = aT21;
 448       aTS22 = aT22;
 449       bIsPBSplittable2 = Standard_False;
 450     }
 451     else {
 452       aPB2->ShrunkData(aTS21, aTS22, aBB2, bIsPBSplittable2);
 453     }
 454     //
 455     //--------------------------------------------
 456     IntTools_Range aR11(aT11, aTS11), aR12(aTS12, aT12),
 457                    aR21(aT21, aTS21), aR22(aTS22, aT22);
 458     //
 459     const IntTools_SequenceOfCommonPrts& aCPrts = anEdgeEdge.CommonParts();
 460     aNbCPrts = aCPrts.Length();
 461     //
 462     Standard_Boolean bAnalytical = Standard_False;
 463     if (aNbCPrts) {
 464       const TopoDS_Edge& aOE1 = *(TopoDS_Edge*)&myDS->Shape(nE1);
 465       const TopoDS_Edge& aOE2 = *(TopoDS_Edge*)&myDS->Shape(nE2);
 466       //
 467       BRepAdaptor_Curve aBAC1(aOE1), aBAC2(aOE2);
 468       //
 469       GeomAbs_CurveType aType1 = aBAC1.GetType();
 470       GeomAbs_CurveType aType2 = aBAC2.GetType();
 471       //
 472       bAnalytical = (((aType1 == GeomAbs_Line) &&
 473                       (aType2 == GeomAbs_Line ||
 474                        aType2 == GeomAbs_Circle)) ||
 475                      ((aType2 == GeomAbs_Line) &&
 476                       (aType1 == GeomAbs_Line ||
 477                        aType1 == GeomAbs_Circle)));
 478     }
 479     //
 480     for (i=1; i<=aNbCPrts; ++i) {
 481       const IntTools_CommonPrt& aCPart=aCPrts(i);
 482       //
 483       const TopoDS_Edge& aE1=aCPart.Edge1();
 484       const TopoDS_Edge& aE2=aCPart.Edge2();
 485       //
 486       aType=aCPart.Type();
 487       switch (aType) {
 488         case TopAbs_VERTEX:  {
 489           if (!bIsPBSplittable1 || !bIsPBSplittable2) {
 490             continue;
 491           }
 492           //
 493           Standard_Boolean bIsOnPave[4], bFlag;
 494           Standard_Integer nV[4], j;
 495           Standard_Real aT1, aT2, aTol;
 496           TopoDS_Vertex aVnew;
 497           IntTools_Range aCR1, aCR2;
 498           //
 499           IntTools_Tools::VertexParameters(aCPart, aT1, aT2);
 500           aTol = Precision::Confusion();
 501           aCR1 = aCPart.Range1();
 502           aCR2 = aCPart.Ranges2()(1);
 503           //
 504           //decide to keep the pave or not
 505           bIsOnPave[0] = IntTools_Tools::IsOnPave1(aT1, aR11, aTol) ||
 506             IntTools_Tools::IsOnPave1(aR11.First(), aCR1, aTol);
 507           bIsOnPave[1] = IntTools_Tools::IsOnPave1(aT1, aR12, aTol) ||
 508             IntTools_Tools::IsOnPave1(aR12.Last(), aCR1, aTol);
 509           bIsOnPave[2] = IntTools_Tools::IsOnPave1(aT2, aR21, aTol) ||
 510             IntTools_Tools::IsOnPave1(aR21.First(), aCR2, aTol);
 511           bIsOnPave[3] = IntTools_Tools::IsOnPave1(aT2, aR22, aTol) ||
 512             IntTools_Tools::IsOnPave1(aR22.Last(), aCR2, aTol);
 513           //
 514           aPB1->Indices(nV[0], nV[1]);
 515           aPB2->Indices(nV[2], nV[3]);
 516           //
 517           if((bIsOnPave[0] && bIsOnPave[2]) ||
 518              (bIsOnPave[0] && bIsOnPave[3]) ||
 519              (bIsOnPave[1] && bIsOnPave[2]) ||
 520              (bIsOnPave[1] && bIsOnPave[3])) {
 521             continue;
 522           }
 523           //
 524           bFlag = Standard_False;
 525           for (j = 0; j < 4; ++j) {
 526             if (bIsOnPave[j]) {
 527               //add interf VE(nV[j], nE)
 528               Handle(BOPDS_PaveBlock)& aPB = (j < 2) ? aPB2 : aPB1;
 529               ForceInterfVE(nV[j], aPB, aMPBToUpdate);
 530               bFlag = Standard_True;
 531               break;
 532             }
 533           }
 534           if (bFlag) {
 535             continue;
 536           }
 537           //
 538           BOPTools_AlgoTools::MakeNewVertex(aE1, aT1, aE2, aT2, aVnew);
 539           Standard_Real aTolVnew = BRep_Tool::Tolerance(aVnew);
 540           if (bAnalytical) {
 541             // increase tolerance for Line/Line intersection, but do not update
 542             // the vertex till its intersection with some other shape
 543             Standard_Real aTolMin = (BRepAdaptor_Curve(aE1).GetType() == GeomAbs_Line) ?
 544               (aCR1.Last() - aCR1.First()) / 2. : (aCR2.Last() - aCR2.First()) / 2.;
 545             if (aTolMin > aTolVnew) {
 546               aTolVnew = aTolMin;
 547             }
 548           }
 549           // <-LXBR
 550           {
 551             Standard_Integer nVS[2], iFound;
 552             Standard_Real aTolVx, aD2, aDT2;
 553             BOPCol_MapOfInteger aMV;
 554             gp_Pnt aPnew, aPx;
 555             //
 556             iFound=0;
 557             j=-1;
 558             aMV.Add(nV[0]);
 559             aMV.Add(nV[1]);
 560             //
 561             if (aMV.Contains(nV[2])) {
 562               ++j;
 563               nVS[j]=nV[2];
 564             }
 565             if (aMV.Contains(nV[3])) {
 566               ++j;
 567               nVS[j]=nV[3];
 568             }
 569             //
 570             aPnew=BRep_Tool::Pnt(aVnew);
 571             //
 572             for (Standard_Integer k1=0; k1<=j; ++k1) {
 573               const TopoDS_Vertex& aVx= *(TopoDS_Vertex*)&(myDS->Shape(nVS[k1]));
 574               aTolVx=BRep_Tool::Tolerance(aVx);
 575               aPx=BRep_Tool::Pnt(aVx);
 576               aD2=aPnew.SquareDistance(aPx);
 577               //
 578               aDT2=100.*(aTolVnew+aTolVx)*(aTolVnew+aTolVx);
 579               //
 580               if (aD2<aDT2) {
 581                 iFound=1;
 582                 break;
 583               }
 584             }
 585             //
 586             if (iFound) {
 587               continue;
 588             }
 589           }
 590           //
 591           // 1
 592           BOPDS_InterfEE& aEE=aEEs.Append1();
 593           iX=aEEs.Extent()-1;
 594           aEE.SetIndices(nE1, nE2);
 595           aEE.SetCommonPart(aCPart);
 596           // 2
 597           myDS->AddInterf(nE1, nE2);
 598           //
 599           BOPDS_CoupleOfPaveBlocks aCPB;
 600           //
 601           aCPB.SetPaveBlocks(aPB1, aPB2);
 602           aCPB.SetIndexInterf(iX);
 603           aCPB.SetTolerance(aTolVnew);
 604           aMVCPB.Add(aVnew, aCPB);
 605         }//case TopAbs_VERTEX:
 606           break;
 607             //
 608         case TopAbs_EDGE: {
 609           if (aNbCPrts > 1) {
 610             break;
 611           }
 612           //
 613           Standard_Boolean bHasSameBounds;
 614           bHasSameBounds=aPB1->HasSameBounds(aPB2);
 615           if (!bHasSameBounds) {
 616             break;
 617           }
 618           // 1
 619           BOPDS_InterfEE& aEE=aEEs.Append1();
 620           iX=aEEs.Extent()-1;
 621           aEE.SetIndices(nE1, nE2);
 622           aEE.SetCommonPart(aCPart);
 623           // 2
 624           myDS->AddInterf(nE1, nE2);
 625           //
 626           BOPAlgo_Tools::FillMap(aPB1, aPB2, aMPBLPB, aAllocator);
 627         }//case TopAbs_EDGE
 628           break;
 629         default:
 630           break;
 631       }//switch (aType) {
 632     }//for (i=1; i<=aNbCPrts; i++) {
 633   }//for (k=0; k < aNbFdgeEdge; ++k) {
 634   //
 635   //=========================================
 636   // post treatment
 637   //=========================================
 638   {
 639     Standard_Integer aNbV;
 640     Handle(BOPDS_PaveBlock) aPB1, aPB2;
 641     //
 642     aNbV=aMVCPB.Extent();
 643     for (i=1; i<=aNbV; ++i) {
 644       const BOPDS_CoupleOfPaveBlocks& aCPB=aMVCPB.FindFromIndex(i);
 645       aCPB.PaveBlocks(aPB1, aPB2);
 646       //
 647       aMPBToUpdate.Remove(aPB1);
 648       aMPBToUpdate.Remove(aPB2);
 649     }
 650   }
 651   //
 652   aItPB.Initialize(aMPBToUpdate);
 653   for (; aItPB.More(); aItPB.Next()) {
 654     Handle(BOPDS_PaveBlock) aPB=aItPB.Value();
 655     if (!myDS->IsCommonBlock(aPB)) {
 656       myDS->UpdatePaveBlock(aPB);
 657     }
 658     else {
 659       const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
 660       myDS->UpdateCommonBlock(aCB, myFuzzyValue);
 661     }
 662   }
 663   //
 664   BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, aAllocator, myDS);
 665   PerformVerticesEE(aMVCPB, aAllocator);
 666   //-----------------------------------------------------scope t
 667   aMPBLPB.Clear();
 668   aMVCPB.Clear();
 669   aMPBToUpdate.Clear();
 670 }
 671 //=======================================================================
 672 //function : PerformVerticesEE
 673 //purpose  :
 674 //=======================================================================
 675 Standard_Integer BOPAlgo_PaveFiller::PerformVerticesEE
 676   (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
 677    const Handle(NCollection_BaseAllocator)& theAllocator)
 678 {
 679   Standard_Integer aNbV, iRet;
 680   //
 681   iRet=0;
 682   aNbV=theMVCPB.Extent();
 683   if (!aNbV) {
 684     return iRet;
 685   }
 686   //
 687   Standard_Integer nVx, iV, j, nE, iFlag, iX, i, aNb;
 688   Standard_Real aT;
 689   BOPCol_ListIteratorOfListOfShape aItLS;
 690   BOPCol_ListIteratorOfListOfInteger aItLI;
 691   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
 692   BOPDS_ShapeInfo aSI;
 693   BOPDS_Pave aPave;
 694   //
 695   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
 696   BOPCol_ListOfShape aLS(theAllocator);
 697   BOPCol_IndexedDataMapOfShapeInteger aMVI(100, theAllocator);
 698   BOPCol_IndexedDataMapOfShapeListOfShape aImages;
 699   //
 700   aSI.SetShapeType(TopAbs_VERTEX);
 701   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
 702   //
 703   // 1 prepare arguments
 704   // 2 Fuse vertices
 705   TreatNewVertices(theMVCPB, aImages);
 706   //
 707   // 3 Add new vertices to myDS;
 708   //   connect indices to CPB structure
 709   aNb = aImages.Extent();
 710   for (i=1; i<=aNb; ++i) {
 711     const TopoDS_Vertex& aV=(*(TopoDS_Vertex*)(&aImages.FindKey(i)));
 712     const BOPCol_ListOfShape& aLVSD=aImages.FindFromIndex(i);
 713     //
 714     aSI.SetShape(aV);
 715     iV=myDS->Append(aSI);
 716     //
 717     BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(iV);
 718     Bnd_Box& aBox=aSIDS.ChangeBox();
 719     BRepBndLib::Add(aV, aBox);
 720     aBox.SetGap(aBox.GetGap() + Precision::Confusion());
 721     //
 722     aItLS.Initialize(aLVSD);
 723     for (; aItLS.More(); aItLS.Next()) {
 724       const TopoDS_Shape& aVx = aItLS.Value();
 725       BOPDS_CoupleOfPaveBlocks &aCPB=theMVCPB.ChangeFromKey(aVx);
 726       aCPB.SetIndex(iV);
 727       // update EE interference
 728       iX=aCPB.IndexInterf();
 729       BOPDS_InterfEE& aEE=aEEs(iX);
 730       aEE.SetIndexNew(iV);
 731     }
 732   }
 733   //
 734   // 4 Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
 735   {
 736     Handle(BOPDS_PaveBlock) aPB[2];
 737     //
 738     for (i=1; i<=aNbV; ++i) {
 739       const BOPDS_CoupleOfPaveBlocks& aCPB=theMVCPB.FindFromIndex(i);
 740       iV=aCPB.Index();
 741       aCPB.PaveBlocks(aPB[0], aPB[1]);
 742       for (j=0; j<2; ++j) {
 743         if (aMPBLI.Contains(aPB[j])) {
 744           BOPCol_ListOfInteger& aLI=aMPBLI.ChangeFromKey(aPB[j]);
 745           aLI.Append(iV);
 746         }
 747         else {
 748           BOPCol_ListOfInteger aLI(theAllocator);
 749           aLI.Append(iV);
 750           aMPBLI.Add(aPB[j], aLI);
 751         }
 752       }
 753     }
 754   }
 755   // 5
 756   // 5.1  Compute Extra Paves and
 757   // 5.2. Add Extra Paves to the PaveBlocks
 758   //-------------------------------------------------------------
 759   Standard_Integer k, aNbVPVE;
 760   BOPAlgo_VectorOfPVE aVPVE;
 761   //
 762   aNb=aMPBLI.Extent();
 763   for(i=1; i<=aNb; ++i) {
 764     Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
 765     nE=aPB->OriginalEdge();
 766     const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
 767     // 1,2
 768     const BOPCol_ListOfInteger& aLI=aMPBLI.FindFromIndex(i);
 769     aItLI.Initialize(aLI);
 770     for (; aItLI.More(); aItLI.Next()) {
 771       nVx=aItLI.Value();
 772       const TopoDS_Vertex& aVx=(*(TopoDS_Vertex *)(&myDS->Shape(nVx)));
 773       //
 774       BOPAlgo_PVE& aPVE=aVPVE.Append1();
 775       aPVE.SetIndices(nVx, nE);
 776       aPVE.SetVertex(aVx);
 777       aPVE.SetEdge(aE);
 778       aPVE.SetFuzzyValue(myFuzzyValue);
 779       aPVE.SetPaveBlock(aPB);
 780     }
 781   }
 782   //
 783   aNbVPVE=aVPVE.Extent();
 784   //=============================================================
 785   BOPAlgo_PVECnt::Perform(myRunParallel, aVPVE, myContext);
 786   //=============================================================
 787   //
 788   for (k=0; k < aNbVPVE; ++k) {
 789     BOPAlgo_PVE& aPVE=aVPVE(k);
 790     iFlag=aPVE.Flag();
 791     if (!iFlag) {
 792       aPVE.Indices(nVx, nE);
 793       aT=aPVE.Parameter();
 794       Handle(BOPDS_PaveBlock)& aPB=aPVE.PaveBlock();
 795       //
 796       aPave.SetIndex(nVx);
 797       aPave.SetParameter(aT);
 798       aPB->AppendExtPave(aPave);
 799     }
 800   }
 801   // 6  Split PaveBlocksa
 802   aNb=aMPBLI.Extent();
 803   for(i=1; i<=aNb; ++i) {
 804     Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
 805     nE=aPB->OriginalEdge();
 806     // 3
 807     if (!myDS->IsCommonBlock(aPB)) {
 808       myDS->UpdatePaveBlock(aPB);
 809     }
 810     else {
 811       const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
 812       myDS->UpdateCommonBlock(aCB, myFuzzyValue);
 813     }
 814   }//for (; aItMPBLI.More(); aItMPBLI.Next()) {
 815   //
 816   return iRet;
 817 }
 818 //=======================================================================
 819 //function : TreatNewVertices
 820 //purpose  :
 821 //=======================================================================
 822 void BOPAlgo_PaveFiller::TreatNewVertices
 823 (const BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
 824    BOPCol_IndexedDataMapOfShapeListOfShape& myImages)
 825 {
 826   Standard_Integer  i, aNbV;//, aNbVSD;
 827   Standard_Real aTol;
 828   TopoDS_Vertex aVnew;
 829   BOPCol_IndexedMapOfShape aMVProcessed;
 830   BOPCol_MapOfInteger aMFence;
 831   BOPCol_ListIteratorOfListOfInteger aIt;
 832   NCollection_Vector<BOPCol_ListOfShape> aVecOfLVSD;
 833   //
 834   BOPCol_BoxBndTree aBBTree;
 835   NCollection_UBTreeFiller <Standard_Integer,
 836                             Bnd_Box> aTreeFiller(aBBTree);
 837   BOPAlgo_VectorOfTNV aVTNV;
 838   //
 839   Standard_Real aTolAdd = myFuzzyValue / 2.;
 840   aNbV = theMVCPB.Extent();
 841   for (i=1; i<=aNbV; ++i) {
 842     const TopoDS_Vertex& aV = *((TopoDS_Vertex*)&theMVCPB.FindKey(i));
 843     Bnd_Box aBox;
 844     //
 845     aTol = theMVCPB.FindFromIndex(i).Tolerance();
 846     aBox.Add(BRep_Tool::Pnt(aV));
 847     aBox.SetGap(aTol + aTolAdd);
 848     //
 849     aTreeFiller.Add(i, aBox);
 850     //
 851     BOPAlgo_TNV& aTNV=aVTNV.Append1();
 852     aTNV.SetTree(aBBTree);
 853     aTNV.SetBox(aBox);
 854     aTNV.SetVertex(aV);
 855     aTNV.SetTolerance(aTol);
 856     aTNV.SetFuzzyValue(myFuzzyValue);
 857     aTNV.SetVectorOfTNV(aVTNV);
 858   }
 859   //
 860   aTreeFiller.Fill();
 861   //
 862   //===========================================
 863   BOPAlgo_TNVCnt::Perform(myRunParallel, aVTNV);
 864   //===========================================
 865   //
 866   // Chains
 867   for (i=1; i<=aNbV; ++i) {
 868     if (!aMFence.Add(i)) {
 869       continue;
 870     }
 871     //
 872     Standard_Integer aIP, aNbIP1, aIP1;
 873     BOPCol_ListOfShape aLVSD;
 874     BOPCol_ListOfInteger aLIP, aLIP1, aLIPC;
 875     BOPCol_ListIteratorOfListOfInteger aItLIP;
 876     //
 877     aLIPC.Append(i);
 878     aLIP.Append(i);
 879     for(;;) {
 880       aItLIP.Initialize(aLIP);
 881       for(; aItLIP.More(); aItLIP.Next()) {
 882         aIP=aItLIP.Value();
 883         //
 884         BOPAlgo_TNV& aTNV=aVTNV(aIP-1);
 885         const BOPCol_ListOfInteger& aLI=aTNV.Indices();
 886         aIt.Initialize(aLI);
 887         for (; aIt.More(); aIt.Next()) {
 888           aIP1=aIt.Value();
 889           if (!aMFence.Add(aIP1)) {
 890             continue;
 891           }
 892           aLIP1.Append(aIP1);
 893         } //for (; aIt.More(); aIt.Next()) {
 894       }//for(; aIt1.More(); aIt1.Next()) {
 895       //
 896       aNbIP1=aLIP1.Extent();
 897       if (!aNbIP1) {
 898         break; // from for(;;)
 899       }
 900       //
 901       aLIP = aLIP1;
 902       aLIPC.Append(aLIP1); // items of aLIP1 are moved to aLIPC
 903     }// for(;;) {
 904     //
 905     aItLIP.Initialize(aLIPC);
 906     for(; aItLIP.More(); aItLIP.Next()) {
 907       aIP=aItLIP.Value();
 908       const TopoDS_Vertex& aVP=aVTNV(aIP-1).Vertex();
 909       aLVSD.Append(aVP);
 910     }
 911     aVecOfLVSD.Append(aLVSD);
 912   }// for (i=1; i<=aNbV; ++i) {
 913
 914   // Make new vertices
 915   aNbV = aVecOfLVSD.Size();
 916   for (i = 0; i < aNbV; ++i) {
 917     const BOPCol_ListOfShape& aLVSD = aVecOfLVSD(i);
 918     BOPTools_AlgoTools::MakeVertex(aLVSD, aVnew);
 919     myImages.Add(aVnew, aLVSD);
 920   }
 921 }
 922 //=======================================================================
 923 //function : FillShrunkData
 924 //purpose  :
 925 //=======================================================================
 926 void BOPAlgo_PaveFiller::FillShrunkData(Handle(BOPDS_PaveBlock)& thePB)
 927 {
 928   Standard_Integer nE, nV1, nV2;
 929   Standard_Real aT1, aT2, aTS1, aTS2;
 930   IntTools_ShrunkRange aSR;
 931   //
 932   myErrorStatus=0;
 933   myWarningStatus = 0;
 934   //
 935   const BOPDS_Pave& aPave1=thePB->Pave1();
 936   nV1=aPave1.Index();
 937   aT1=aPave1.Parameter();
 938   const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1)));
 939   //
 940   const BOPDS_Pave& aPave2=thePB->Pave2();
 941   nV2=aPave2.Index();
 942   aT2=aPave2.Parameter();
 943   const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2)));
 944   //
 945   nE=thePB->OriginalEdge();
 946   const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
 947   //
 948   aSR.SetContext(myContext);
 949   aSR.SetData(aE, aT1, aT2, aV1, aV2);
 950   //
 951   aSR.Perform();
 952   if (!aSR.IsDone()) {
 953     myWarningStatus = 1;
 954     return;
 955   }
 956   //
 957   aSR.ShrunkRange(aTS1, aTS2);
 958   const Bnd_Box& aBox=aSR.BndBox();
 959   Standard_Boolean bIsSplittable = aSR.IsSplittable();
 960   //
 961   thePB->SetShrunkData(aTS1, aTS2, aBox, bIsSplittable);
 962 }
 963 //=======================================================================
 964 //function : ForceInterfVE
 965 //purpose  :
 966 //=======================================================================
 967 void BOPAlgo_PaveFiller::ForceInterfVE(const Standard_Integer nV,
 968                                        Handle(BOPDS_PaveBlock)& aPB,
 969                                        BOPDS_MapOfPaveBlock& aMPBToUpdate)
 970 {
 971   Standard_Integer nE, nVx, nVSD, iFlag;
 972   Standard_Real aT, aTolVNew;
 973   //
 974   nE = aPB->OriginalEdge();
 975   //
 976   const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
 977   if (aSIE.HasSubShape(nV)) {
 978     return;
 979   }
 980   //
 981   if (myDS->HasInterf(nV, nE)) {
 982     return;
 983   }
 984   //
 985   if (myDS->HasInterfShapeSubShapes(nV, nE)) {
 986     return;
 987   }
 988   //
 989   if (aPB->Pave1().Index() == nV ||
 990       aPB->Pave2().Index() == nV) {
 991     return;
 992   }
 993   //
 994   nVx = nV;
 995   if (myDS->HasShapeSD(nV, nVSD)) {
 996     nVx = nVSD;
 997   }
 998   //
 999   const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nVx);
1000   const TopoDS_Edge&   aE = *(TopoDS_Edge*)  &myDS->Shape(nE);
1001   //
1002   iFlag = myContext->ComputeVE(aV, aE, aT, aTolVNew, myFuzzyValue);
1003   if (iFlag == 0 || iFlag == -4) {
1004     BOPDS_Pave aPave;
1005     //
1006     //
1007     BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
1008     aVEs.SetIncrement(10);
1009     // 1
1010     BOPDS_InterfVE& aVE=aVEs.Append1();
1011     aVE.SetIndices(nV, nE);
1012     aVE.SetParameter(aT);
1013     // 2
1014     myDS->AddInterf(nV, nE);
1015     //
1016     // 3 update vertex V/E if necessary
1017     nVx=UpdateVertex(nV, aTolVNew);
1018     // 4
1019     if (myDS->IsNewShape(nVx)) {
1020       aVE.SetIndexNew(nVx);
1021     }
1022     // 5 append ext pave to pave block
1023     aPave.SetIndex(nVx);
1024     aPave.SetParameter(aT);
1025     aPB->AppendExtPave(aPave);
1026     //
1027     aMPBToUpdate.Add(aPB);
1028   }
1029 }
1030
1031 //=======================================================================
1032 //function : GetPBBox
1033 //purpose  :
1034 //=======================================================================
1035 Standard_Boolean BOPAlgo_PaveFiller::GetPBBox(const TopoDS_Edge& theE,
1036                                               const Handle(BOPDS_PaveBlock)& thePB,
1037                                               BOPAlgo_DataMapOfPaveBlockBndBox& thePBBox,
1038                                               Standard_Real& theFirst,
1039                                               Standard_Real& theLast,
1040                                               Standard_Real& theSFirst,
1041                                               Standard_Real& theSLast,
1042                                               Bnd_Box& theBox)
1043 {
1044   thePB->Range(theFirst, theLast);
1045   // check the validity of PB's range
1046   Standard_Boolean bValid = theLast - theFirst > Precision::PConfusion();
1047   if (!bValid) {
1048     return bValid;
1049   }
1050   //
1051   // check shrunk data
1052   if (thePB->HasShrunkData()) {
1053     Standard_Boolean bIsSplittable;
1054     thePB->ShrunkData(theSFirst, theSLast, theBox, bIsSplittable);
1055     return bValid;
1056   }
1057   //
1058   theSFirst = theFirst;
1059   theSLast = theLast;
1060   // check the map
1061   if (thePBBox.IsBound(thePB)) {
1062     theBox = thePBBox.Find(thePB);
1063   }
1064   else {
1065     // build bounding box
1066     BRepAdaptor_Curve aBAC(theE);
1067     Standard_Real aTol = BRep_Tool::Tolerance(theE) + Precision::Confusion();
1068     BndLib_Add3dCurve::Add(aBAC, theSFirst, theSLast, aTol, theBox);
1069     thePBBox.Bind(thePB, theBox);
1070   }
1071   return bValid;
1072 }