src/BOPAlgo/BOPAlgo_PaveFiller_6.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 #include <BOPAlgo_PaveFiller.hxx>
  19 #include <Bnd_Box.hxx>
  20 #include <BOPAlgo_Alerts.hxx>
  21 #include <BOPAlgo_SectionAttribute.hxx>
  22 #include <BOPAlgo_Tools.hxx>
  23 #include <BOPDS_CommonBlock.hxx>
  24 #include <BOPDS_CoupleOfPaveBlocks.hxx>
  25 #include <BOPDS_Curve.hxx>
  26 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
  27 #include <BOPDS_DS.hxx>
  28 #include <BOPDS_FaceInfo.hxx>
  29 #include <BOPDS_Interf.hxx>
  30 #include <BOPDS_Iterator.hxx>
  31 #include <BOPDS_ListOfPave.hxx>
  32 #include <BOPDS_ListOfPaveBlock.hxx>
  33 #include <BOPDS_MapOfPaveBlock.hxx>
  34 #include <BOPDS_PaveBlock.hxx>
  35 #include <BOPDS_Point.hxx>
  36 #include <BOPDS_ShapeInfo.hxx>
  37 #include <BOPDS_VectorOfCurve.hxx>
  38 #include <BOPDS_VectorOfPoint.hxx>
  39 #include <BOPTools_AlgoTools.hxx>
  40 #include <BOPTools_AlgoTools3D.hxx>
  41 #include <BOPTools_Parallel.hxx>
  42 #include <BRep_Builder.hxx>
  43 #include <BRep_TEdge.hxx>
  44 #include <BRep_Tool.hxx>
  45 #include <BRepAdaptor_Curve.hxx>
  46 #include <BRepAdaptor_Surface.hxx>
  47 #include <BRepBndLib.hxx>
  48 #include <BRepBuilderAPI_MakeVertex.hxx>
  49 #include <BRepLib.hxx>
  50 #include <BRepTools.hxx>
  51 #include <Geom_Curve.hxx>
  52 #include <Geom2d_Curve.hxx>
  53 #include <GeomAPI_ProjectPointOnCurve.hxx>
  54 #include <GeomAPI_ProjectPointOnSurf.hxx>
  55 #include <gp_Pnt.hxx>
  56 #include <IntSurf_ListOfPntOn2S.hxx>
  57 #include <IntSurf_PntOn2S.hxx>
  58 #include <IntTools.hxx>
  59 #include <IntTools_Context.hxx>
  60 #include <IntTools_Curve.hxx>
  61 #include <IntTools_EdgeFace.hxx>
  62 #include <IntTools_FaceFace.hxx>
  63 #include <IntTools_PntOn2Faces.hxx>
  64 #include <IntTools_SequenceOfCurves.hxx>
  65 #include <IntTools_SequenceOfPntOn2Faces.hxx>
  66 #include <IntTools_ShrunkRange.hxx>
  67 #include <IntTools_Tools.hxx>
  68 #include <NCollection_Vector.hxx>
  69 #include <Precision.hxx>
  70 #include <TColStd_ListOfInteger.hxx>
  71 #include <TColStd_MapOfInteger.hxx>
  72 #include <TopExp.hxx>
  73 #include <TopExp_Explorer.hxx>
  74 #include <TopoDS.hxx>
  75 #include <TopoDS_Compound.hxx>
  76 #include <TopoDS_Edge.hxx>
  77 #include <TopoDS_Face.hxx>
  78 #include <TopoDS_Vertex.hxx>
  79 #include <TopTools_DataMapOfShapeInteger.hxx>
  80 #include <TopTools_ListOfShape.hxx>
  81
  82 //
  83 static Standard_Real ToleranceFF(const BRepAdaptor_Surface& aBAS1,
  84                                  const BRepAdaptor_Surface& aBAS2);
  85
  86 /////////////////////////////////////////////////////////////////////////
  87 //=======================================================================
  88 //class    : BOPAlgo_FaceFace
  89 //purpose  :
  90 //=======================================================================
  91 class BOPAlgo_FaceFace :
  92   public IntTools_FaceFace,
  93   public BOPAlgo_Algo {
  94
  95  public:
  96   DEFINE_STANDARD_ALLOC
  97
  98   BOPAlgo_FaceFace() :
  99     IntTools_FaceFace(),
 100     BOPAlgo_Algo(),
 101     myIF1(-1), myIF2(-1), myTolFF(1.e-7) {
 102   }
 103   //
 104   virtual ~BOPAlgo_FaceFace() {
 105   }
 106   //
 107   void SetIndices(const Standard_Integer nF1,
 108                   const Standard_Integer nF2) {
 109     myIF1=nF1;
 110     myIF2=nF2;
 111   }
 112   //
 113   void Indices(Standard_Integer& nF1,
 114                Standard_Integer& nF2) const {
 115     nF1=myIF1;
 116     nF2=myIF2;
 117   }
 118   //
 119   void SetFaces(const TopoDS_Face& aF1,
 120                 const TopoDS_Face& aF2) {
 121     myF1=aF1;
 122     myF2=aF2;
 123   }
 124   //
 125   const TopoDS_Face& Face1()const {
 126     return myF1;
 127   }
 128   //
 129   const TopoDS_Face& Face2()const {
 130     return myF2;
 131   }
 132   //
 133   void SetTolFF(const Standard_Real aTolFF) {
 134     myTolFF=aTolFF;
 135   }
 136   //
 137   Standard_Real TolFF() const{
 138     return myTolFF;
 139   }
 140   //
 141   void SetFuzzyValue(const Standard_Real theFuzz) {
 142     IntTools_FaceFace::SetFuzzyValue(theFuzz);
 143   }
 144   //
 145   virtual void Perform() {
 146     BOPAlgo_Algo::UserBreak();
 147     try
 148     {
 149       OCC_CATCH_SIGNALS
 150
 151       IntTools_FaceFace::Perform(myF1, myF2);
 152     }
 153     catch (Standard_Failure const&)
 154     {
 155       AddError(new BOPAlgo_AlertIntersectionFailed);
 156     }
 157   }
 158   //
 159  protected:
 160   Standard_Integer myIF1;
 161   Standard_Integer myIF2;
 162   Standard_Real myTolFF;
 163   TopoDS_Face myF1;
 164   TopoDS_Face myF2;
 165 };
 166 //
 167 //=======================================================================
 168 typedef NCollection_Vector<BOPAlgo_FaceFace> BOPAlgo_VectorOfFaceFace;
 169
 170 /////////////////////////////////////////////////////////////////////////
 171 //=======================================================================
 172 //function : PerformFF
 173 //purpose  :
 174 //=======================================================================
 175 void BOPAlgo_PaveFiller::PerformFF()
 176 {
 177   myIterator->Initialize(TopAbs_FACE, TopAbs_FACE);
 178   Standard_Integer iSize = myIterator->ExpectedLength();
 179   if (!iSize) {
 180     return;
 181   }
 182   //
 183   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
 184   aFFs.SetIncrement(iSize);
 185   //
 186   // Options for the intersection algorithm
 187   Standard_Boolean bApprox   = mySectionAttribute.Approximation(),
 188                    bCompC2D1 = mySectionAttribute.PCurveOnS1(),
 189                    bCompC2D2 = mySectionAttribute.PCurveOnS2();
 190   Standard_Real    anApproxTol = 1.e-7;
 191   // Post-processing options
 192   Standard_Boolean bSplitCurve = Standard_False;
 193   //
 194   // Fence map to store faces with updated FaceInfo structure
 195   TColStd_MapOfInteger aMIFence;
 196   // Prepare the pairs of faces for intersection
 197   BOPAlgo_VectorOfFaceFace aVFaceFace;
 198   Standard_Integer nF1, nF2;
 199   //
 200   for (; myIterator->More(); myIterator->Next()) {
 201     myIterator->Value(nF1, nF2);
 202
 203     // Update/Initialize FaceInfo structure for first face
 204     if (myDS->HasFaceInfo(nF1))
 205     {
 206       if (aMIFence.Add(nF1))
 207       {
 208         myDS->UpdateFaceInfoOn(nF1);
 209         myDS->UpdateFaceInfoIn(nF1);
 210       }
 211     }
 212     else if (myDS->HasInterfShapeSubShapes(nF2, nF1))
 213     {
 214       myDS->ChangeFaceInfo(nF1);
 215       aMIFence.Add(nF1);
 216     }
 217
 218     // Update/Initialize FaceInfo structure for second face
 219     if (myDS->HasFaceInfo(nF2))
 220     {
 221       if (aMIFence.Add(nF2))
 222       {
 223         myDS->UpdateFaceInfoOn(nF2);
 224         myDS->UpdateFaceInfoIn(nF2);
 225       }
 226     }
 227     else if (myDS->HasInterfShapeSubShapes(nF1, nF2))
 228     {
 229       myDS->ChangeFaceInfo(nF2);
 230       aMIFence.Add(nF2);
 231     }
 232     //
 233     if (myGlue == BOPAlgo_GlueOff)
 234     {
 235       const TopoDS_Face& aF1 = (*(TopoDS_Face *)(&myDS->Shape(nF1)));
 236       const TopoDS_Face& aF2 = (*(TopoDS_Face *)(&myDS->Shape(nF2)));
 237       //
 238       const BRepAdaptor_Surface& aBAS1 = myContext->SurfaceAdaptor(aF1);
 239       const BRepAdaptor_Surface& aBAS2 = myContext->SurfaceAdaptor(aF2);
 240       if (aBAS1.GetType() == GeomAbs_Plane &&
 241           aBAS2.GetType() == GeomAbs_Plane) {
 242         // Check if the planes are really interfering
 243         Standard_Boolean bToIntersect = CheckPlanes(nF1, nF2);
 244         if (!bToIntersect) {
 245           BOPDS_InterfFF& aFF = aFFs.Appended();
 246           aFF.SetIndices(nF1, nF2);
 247           aFF.Init(0, 0);
 248           continue;
 249         }
 250       }
 251       //
 252       BOPAlgo_FaceFace& aFaceFace=aVFaceFace.Appended();
 253       //
 254       aFaceFace.SetIndices(nF1, nF2);
 255       aFaceFace.SetFaces(aF1, aF2);
 256       // compute minimal tolerance for the curves
 257       Standard_Real aTolFF = ToleranceFF(aBAS1, aBAS2);
 258       aFaceFace.SetTolFF(aTolFF);
 259       //
 260       IntSurf_ListOfPntOn2S aListOfPnts;
 261       GetEFPnts(nF1, nF2, aListOfPnts);
 262       Standard_Integer aNbLP = aListOfPnts.Extent();
 263       if (aNbLP) {
 264         aFaceFace.SetList(aListOfPnts);
 265       }
 266       //
 267       aFaceFace.SetParameters(bApprox, bCompC2D1, bCompC2D2, anApproxTol);
 268       aFaceFace.SetFuzzyValue(myFuzzyValue);
 269       aFaceFace.SetProgressIndicator(myProgressIndicator);
 270     }
 271     else {
 272       // for the Glue mode just add all interferences of that type
 273       BOPDS_InterfFF& aFF = aFFs.Appended();
 274       aFF.SetIndices(nF1, nF2);
 275       aFF.SetTangentFaces(Standard_False);
 276       aFF.Init(0, 0);
 277     }
 278   }//for (; myIterator->More(); myIterator->Next()) {
 279   //
 280   //======================================================
 281   // Perform intersection
 282   BOPTools_Parallel::Perform (myRunParallel, aVFaceFace);
 283   //======================================================
 284   // Treatment of the results
 285   Standard_Integer k, aNbFaceFace = aVFaceFace.Length();
 286   for (k = 0; k < aNbFaceFace; ++k) {
 287     BOPAlgo_FaceFace& aFaceFace = aVFaceFace(k);
 288     aFaceFace.Indices(nF1, nF2);
 289     if (!aFaceFace.IsDone() || aFaceFace.HasErrors()) {
 290       BOPDS_InterfFF& aFF = aFFs.Appended();
 291       aFF.SetIndices(nF1, nF2);
 292       aFF.Init(0, 0);
 293       // Warn about failed intersection of faces
 294       AddIntersectionFailedWarning(aFaceFace.Face1(), aFaceFace.Face2());
 295       continue;
 296     }
 297     //
 298     Standard_Boolean bTangentFaces = aFaceFace.TangentFaces();
 299     Standard_Real aTolFF = aFaceFace.TolFF();
 300     //
 301     aFaceFace.PrepareLines3D(bSplitCurve);
 302     //
 303     const IntTools_SequenceOfCurves& aCvsX = aFaceFace.Lines();
 304     const IntTools_SequenceOfPntOn2Faces& aPntsX = aFaceFace.Points();
 305     //
 306     Standard_Integer aNbCurves = aCvsX.Length();
 307     Standard_Integer aNbPoints = aPntsX.Length();
 308     //
 309     if (aNbCurves || aNbPoints) {
 310       myDS->AddInterf(nF1, nF2);
 311     }
 312     //
 313     BOPDS_InterfFF& aFF = aFFs.Appended();
 314     aFF.SetIndices(nF1, nF2);
 315     aFF.SetTangentFaces(bTangentFaces);
 316     aFF.Init(aNbCurves, aNbPoints);
 317     //
 318     // Curves
 319     // Fix bounding box expanding coefficient.
 320     Standard_Real aBoxExpandValue = aTolFF;
 321     if (aNbCurves > 0)
 322     {
 323       // Modify geometric expanding coefficient by topology value,
 324       // since this bounding box used in sharing (vertex or edge).
 325       Standard_Real aMaxVertexTol = Max(BRep_Tool::MaxTolerance(aFaceFace.Face1(), TopAbs_VERTEX),
 326         BRep_Tool::MaxTolerance(aFaceFace.Face2(), TopAbs_VERTEX));
 327       aBoxExpandValue += aMaxVertexTol;
 328     }
 329     //
 330     BOPDS_VectorOfCurve& aVNC = aFF.ChangeCurves();
 331     for (Standard_Integer i = 1; i <= aNbCurves; ++i) {
 332       Bnd_Box aBox;
 333       const IntTools_Curve& aIC = aCvsX(i);
 334       Standard_Boolean bIsValid = IntTools_Tools::CheckCurve(aIC, aBox);
 335       if (bIsValid) {
 336         BOPDS_Curve& aNC = aVNC.Appended();
 337         aNC.SetCurve(aIC);
 338         // make sure that the bounding box has the maximal gap
 339         aBox.Enlarge(aBoxExpandValue);
 340         aNC.SetBox(aBox);
 341         aNC.SetTolerance(Max(aIC.Tolerance(), aTolFF));
 342       }
 343     }
 344     //
 345     // Points
 346     BOPDS_VectorOfPoint& aVNP = aFF.ChangePoints();
 347     for (Standard_Integer i = 1; i <= aNbPoints; ++i) {
 348       const IntTools_PntOn2Faces& aPi = aPntsX(i);
 349       const gp_Pnt& aP = aPi.P1().Pnt();
 350       //
 351       BOPDS_Point& aNP = aVNP.Appended();
 352       aNP.SetPnt(aP);
 353     }
 354   }
 355 }
 356
 357 //=======================================================================
 358 //function : UpdateSavedTolerance
 359 //purpose  : Updates the saved tolerance of the vertices of the edge
 360 //           with new tolerance of edge
 361 //=======================================================================
 362 static void UpdateSavedTolerance(const BOPDS_PDS& theDS,
 363                                  const Standard_Integer theNE,
 364                                  const Standard_Real theTolNew,
 365                                  TColStd_DataMapOfIntegerReal& theMVTol)
 366 {
 367   const TColStd_ListOfInteger& aSubShapes = theDS->ShapeInfo(theNE).SubShapes();
 368   TColStd_ListIteratorOfListOfInteger itSS(aSubShapes);
 369   for (; itSS.More(); itSS.Next())
 370   {
 371     const Standard_Integer nV = itSS.Value();
 372     Standard_Real *pTolSaved = theMVTol.ChangeSeek(nV);
 373     if (pTolSaved && *pTolSaved < theTolNew)
 374       *pTolSaved = theTolNew;
 375   }
 376 }
 377
 378 //=======================================================================
 379 //function : MakeBlocks
 380 //purpose  :
 381 //=======================================================================
 382 void BOPAlgo_PaveFiller::MakeBlocks()
 383 {
 384   if (myGlue != BOPAlgo_GlueOff) {
 385     return;
 386   }
 387   //
 388   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
 389   Standard_Integer aNbFF = aFFs.Length();
 390   if (!aNbFF) {
 391     return;
 392   }
 393   //
 394   Standard_Boolean bExist, bValid2D;
 395   Standard_Integer i, nF1, nF2, aNbC, aNbP, j;
 396   Standard_Integer nV1, nV2;
 397   Standard_Real aT1, aT2;
 398   Handle(NCollection_BaseAllocator) aAllocator;
 399   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
 400   TopoDS_Edge aES;
 401   Handle(BOPDS_PaveBlock) aPBOut;
 402   //
 403   //-----------------------------------------------------scope f
 404   aAllocator=
 405     NCollection_BaseAllocator::CommonBaseAllocator();
 406   //
 407   TColStd_ListOfInteger aLSE(aAllocator), aLBV(aAllocator);
 408   TColStd_MapOfInteger aMVOnIn(100, aAllocator), aMVCommon(100, aAllocator),
 409                       aMVStick(100,aAllocator), aMVEF(100, aAllocator),
 410                       aMI(100, aAllocator), aMVBounds(100, aAllocator);
 411   BOPDS_IndexedMapOfPaveBlock aMPBOnIn(100, aAllocator);
 412   BOPDS_MapOfPaveBlock aMPBAdd(100, aAllocator), aMPBCommon;
 413   BOPDS_ListOfPaveBlock aLPB(aAllocator);
 414   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMSCPB(100, aAllocator);
 415   TopTools_DataMapOfShapeInteger aMVI(100, aAllocator);
 416   BOPDS_DataMapOfPaveBlockListOfPaveBlock aDMExEdges(100, aAllocator);
 417   TColStd_DataMapOfIntegerReal aMVTol(100, aAllocator);
 418   TColStd_DataMapOfIntegerInteger aDMNewSD(100, aAllocator);
 419   TColStd_DataMapOfIntegerListOfInteger aDMVLV;
 420   TColStd_DataMapOfIntegerListOfInteger aDMBV(100, aAllocator);
 421   TColStd_DataMapIteratorOfDataMapOfIntegerReal aItMV;
 422   BOPDS_IndexedMapOfPaveBlock aMicroPB(100, aAllocator);
 423   TopTools_IndexedMapOfShape aVertsOnRejectedPB;
 424   // Map of PaveBlocks with the faces to which it has to be added
 425   BOPAlgo_DataMapOfPaveBlockListOfInteger aPBFacesMap;
 426   //
 427   for (i=0; i<aNbFF; ++i) {
 428     //
 429     UserBreak();
 430     //
 431     BOPDS_InterfFF& aFF=aFFs(i);
 432     aFF.Indices(nF1, nF2);
 433     //
 434     BOPDS_VectorOfPoint& aVP=aFF.ChangePoints();
 435     aNbP=aVP.Length();
 436     BOPDS_VectorOfCurve& aVC=aFF.ChangeCurves();
 437     aNbC=aVC.Length();
 438     if (!aNbP && !aNbC) {
 439       continue;
 440     }
 441     //
 442     const TopoDS_Face& aF1=(*(TopoDS_Face *)(&myDS->Shape(nF1)));
 443     const TopoDS_Face& aF2=(*(TopoDS_Face *)(&myDS->Shape(nF2)));
 444     //
 445     Standard_Real aTolFF = Max(BRep_Tool::Tolerance(aF1), BRep_Tool::Tolerance(aF2));
 446     //
 447     BOPDS_FaceInfo& aFI1 = myDS->ChangeFaceInfo(nF1);
 448     BOPDS_FaceInfo& aFI2 = myDS->ChangeFaceInfo(nF2);
 449     //
 450     aMVOnIn.Clear();
 451     aMVCommon.Clear();
 452     aMPBOnIn.Clear();
 453     aMPBCommon.Clear();
 454     aDMBV.Clear();
 455     aMVTol.Clear();
 456     aLSE.Clear();
 457     //
 458     myDS->SubShapesOnIn(nF1, nF2, aMVOnIn, aMVCommon, aMPBOnIn, aMPBCommon);
 459     myDS->SharedEdges(nF1, nF2, aLSE, aAllocator);
 460     //
 461     Standard_Boolean bHasRealSectionEdge = Standard_False;
 462     // 1. Treat Points
 463     for (j=0; j<aNbP; ++j) {
 464       TopoDS_Vertex aV;
 465       BOPDS_CoupleOfPaveBlocks aCPB;
 466       //
 467       BOPDS_Point& aNP=aVP.ChangeValue(j);
 468       const gp_Pnt& aP=aNP.Pnt();
 469       //
 470       bExist=IsExistingVertex(aP, aTolFF, aMVOnIn);
 471       if (!bExist) {
 472         BOPTools_AlgoTools::MakeNewVertex(aP, aTolFF, aV);
 473         //
 474         aCPB.SetIndexInterf(i);
 475         aCPB.SetIndex(j);
 476         aMSCPB.Add(aV, aCPB);
 477       }
 478     }
 479     //
 480     // 2. Treat Curves
 481     aMVStick.Clear();
 482     aMVEF.Clear();
 483     GetStickVertices(nF1, nF2, aMVStick, aMVEF, aMI);
 484     //
 485     for (j = 0; j < aNbC; ++j) {
 486       BOPDS_Curve& aNC = aVC.ChangeValue(j);
 487       // DEBt
 488       aNC.InitPaveBlock1();
 489       //
 490       // In order to avoid problems connected with
 491       // extending tolerance of vertex while putting
 492       // (e.g. see "bugs modalg_6 bug26789_1" test case),
 493       // all not-common vertices will be checked by
 494       // BndBoxes before putting. For common-vertices,
 495       // filtering by BndBoxes is not necessary.
 496       PutPavesOnCurve(aMVOnIn, aMVCommon, aNC, aMI, aMVEF, aMVTol, aDMVLV);
 497     }
 498
 499     // if some E-F vertex was put on a curve due to large E-F intersection range,
 500     // and it also was put on another curve correctly then remove this vertex from
 501     // the first curve. Detect such case if the distance to curve exceeds aTolR3D.
 502     FilterPavesOnCurves(aVC, aMVTol);
 503
 504     for (j = 0; j<aNbC; ++j) {
 505       BOPDS_Curve& aNC=aVC.ChangeValue(j);
 506       const IntTools_Curve& aIC=aNC.Curve();
 507       //
 508       PutStickPavesOnCurve(aF1, aF2, aMI, aNC, aMVStick, aMVTol, aDMVLV);
 509       //904/F7
 510       if (aNbC == 1) {
 511         PutEFPavesOnCurve(aNC, aMI, aMVEF, aMVTol, aDMVLV);
 512       }
 513       //
 514       if (aIC.HasBounds()) {
 515         aLBV.Clear();
 516         //
 517         PutBoundPaveOnCurve(aF1, aF2, aNC, aLBV);
 518         //
 519         if (!aLBV.IsEmpty()) {
 520           aDMBV.Bind(j, aLBV);
 521           TColStd_ListIteratorOfListOfInteger aItI(aLBV);
 522           for (; aItI.More(); aItI.Next()) {
 523             aMVBounds.Add(aItI.Value());
 524           }
 525         }
 526       }
 527     }//for (j=0; j<aNbC; ++j) {
 528
 529     // Put closing pave if needed
 530     for (j=0; j<aNbC; ++j) {
 531       BOPDS_Curve& aNC=aVC.ChangeValue(j);
 532       PutClosingPaveOnCurve (aNC);
 533     }
 534     //
 535     // 3. Make section edges
 536     for (j=0; j<aNbC; ++j) {
 537       BOPDS_Curve& aNC=aVC.ChangeValue(j);
 538       const IntTools_Curve& aIC=aNC.Curve();
 539       Standard_Real aTolR3D = Max(aNC.Tolerance(), aNC.TangentialTolerance());
 540       //
 541       BOPDS_ListOfPaveBlock& aLPBC=aNC.ChangePaveBlocks();
 542       Handle(BOPDS_PaveBlock)& aPB1=aNC.ChangePaveBlock1();
 543       //
 544       aLPB.Clear();
 545       aPB1->Update(aLPB, Standard_False);
 546       //
 547       aItLPB.Initialize(aLPB);
 548       for (; aItLPB.More(); aItLPB.Next()) {
 549         Handle(BOPDS_PaveBlock)& aPB=aItLPB.ChangeValue();
 550         aPB->Indices(nV1, nV2);
 551         aPB->Range  (aT1, aT2);
 552         //
 553         if (fabs(aT1 - aT2) < Precision::PConfusion()) {
 554           continue;
 555         }
 556
 557         // Check validity of the block for the faces:
 558         // classify bounding and middle points on the curve
 559         // relatively both faces
 560         bValid2D=myContext->IsValidBlockForFaces(aT1, aT2, aIC,
 561                                                  aF1, aF2, aTolR3D);
 562         if (!bValid2D) {
 563           continue;
 564         }
 565         //
 566         Standard_Integer nEOut;
 567         Standard_Real aTolNew;
 568         bExist = IsExistingPaveBlock(aPB, aNC, aLSE, nEOut, aTolNew);
 569         if (bExist)
 570         {
 571           // Update edge with new tolerance
 572           UpdateEdgeTolerance(nEOut, aTolNew);
 573           // Update aMVTol map with new tolerances of vertices
 574           UpdateSavedTolerance(myDS, nEOut, aTolNew, aMVTol);
 575           continue;
 576         }
 577         //
 578         const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1)));
 579         const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2)));
 580         //
 581         // check if the pave block has a valid range
 582         Standard_Real aFirst, aLast;
 583         if (!BRepLib::FindValidRange(GeomAdaptor_Curve(aIC.Curve()), aTolR3D,
 584                                      aT1, BRep_Tool::Pnt(aV1), BRep_Tool::Tolerance(aV1),
 585                                      aT2, BRep_Tool::Pnt(aV2), BRep_Tool::Tolerance(aV2),
 586                                      aFirst, aLast))
 587         {
 588           // If the pave block does not have valid range, i.e. it is completely
 589           // covered by the tolerance spheres of its vertices, it will be
 590           // passed into post treatment process to fuse its vertices.
 591           // The pave block itself will not be kept.
 592           if (!aMVBounds.Contains(nV1) && !aMVBounds.Contains(nV2)) {
 593             aMicroPB.Add(aPB);
 594             // keep vertices for post treatment
 595             aMVI.Bind(aV1, nV1);
 596             aMVI.Bind(aV2, nV2);
 597           }
 598           continue;
 599         }
 600         //
 601         bExist = IsExistingPaveBlock(aPB, aNC, aTolR3D, aMPBOnIn, aMPBCommon, aPBOut, aTolNew);
 602         if (bExist)
 603         {
 604           Standard_Boolean bInF1 = (aFI1.PaveBlocksOn().Contains(aPBOut) ||
 605                                     aFI1.PaveBlocksIn().Contains(aPBOut));
 606           Standard_Boolean bInF2 = (aFI2.PaveBlocksOn().Contains(aPBOut) ||
 607                                     aFI2.PaveBlocksIn().Contains(aPBOut));
 608           if (!bInF1 || !bInF2)
 609           {
 610             // Update edge to touch both faces
 611             Standard_Integer nE = aPBOut->Edge();
 612             const TopoDS_Edge& aE = *(TopoDS_Edge*)&myDS->Shape(nE);
 613             Standard_Real aTolE = BRep_Tool::Tolerance(aE);
 614             if (aTolNew < aNC.Tolerance())
 615               aTolNew = aNC.Tolerance();  // use real tolerance of intersection
 616             if (aTolNew > aTolE) {
 617               UpdateEdgeTolerance(nE, aTolNew);
 618               // Update aMVTol map with new tolerances of vertices
 619               UpdateSavedTolerance(myDS, nE, aTolNew, aMVTol);
 620             }
 621
 622             // Face without pave block
 623             const Standard_Integer nF = bInF1 ? nF2 : nF1;
 624             TColStd_ListOfInteger* pFaces = aPBFacesMap.ChangeSeek(aPBOut);
 625             if (!pFaces)
 626               pFaces = aPBFacesMap.Bound(aPBOut, TColStd_ListOfInteger());
 627             // List is expected to be short, so we allow the check here
 628             if (pFaces->IsEmpty() || !pFaces->Contains(nF))
 629               pFaces->Append(nF);
 630
 631             if (aMPBAdd.Add(aPBOut))
 632             {
 633               // Add edge for processing as the section edge
 634               PreparePostTreatFF(i, j, aPBOut, aMSCPB, aMVI, aLPBC);
 635               // Try fusing the vertices of the existing pave block
 636               // with the vertices put on the real section curve (except
 637               // for technological vertices, which will be removed)
 638               Standard_Integer nVOut1, nVOut2;
 639               aPBOut->Indices(nVOut1, nVOut2);
 640               if (nV1 != nVOut1 && nV1 != nVOut2 && !aMVBounds.Contains(nV1))
 641               {
 642                 aVertsOnRejectedPB.Add(aV1);
 643               }
 644               if (nV2 != nVOut1 && nV2 != nVOut2 && !aMVBounds.Contains(nV2))
 645               {
 646                 aVertsOnRejectedPB.Add(aV2);
 647               }
 648             }
 649           }
 650           continue;
 651         }
 652         //
 653         // Make Edge
 654         BOPTools_AlgoTools::MakeEdge (aIC, aV1, aT1, aV2, aT2, aTolR3D, aES);
 655         // Make p-curves
 656         BOPTools_AlgoTools::MakePCurve(aES, aF1, aF2, aIC,
 657                                        mySectionAttribute.PCurveOnS1(),
 658                                        mySectionAttribute.PCurveOnS2(),
 659                                        myContext);
 660         //
 661         // Append the Pave Block to the Curve j
 662         aLPBC.Append(aPB);
 663         //
 664         // Keep info for post treatment
 665         BOPDS_CoupleOfPaveBlocks aCPB;
 666         aCPB.SetIndexInterf(i);
 667         aCPB.SetIndex(j);
 668         aCPB.SetPaveBlock1(aPB);
 669         //
 670         aMSCPB.Add(aES, aCPB);
 671         aMVI.Bind(aV1, nV1);
 672         aMVI.Bind(aV2, nV2);
 673         //
 674         aMVTol.UnBind(nV1);
 675         aMVTol.UnBind(nV2);
 676         //
 677         bHasRealSectionEdge = Standard_True;
 678       }
 679       //
 680       aLPBC.RemoveFirst();
 681     }//for (j=0; j<aNbC; ++j) {
 682     //
 683     //back to previous tolerance values for unused vertices
 684     //and forget about SD groups of such vertices
 685     aItMV.Initialize(aMVTol);
 686     for (; aItMV.More(); aItMV.Next()) {
 687       nV1 = aItMV.Key();
 688       Standard_Real aTol = aItMV.Value();
 689       //
 690       const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nV1);
 691       const Handle(BRep_TVertex)& TV =
 692         *((Handle(BRep_TVertex)*)&aV.TShape());
 693       TV->Tolerance(aTol);
 694       // reset bnd box
 695       BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(nV1);
 696       Bnd_Box& aBoxDS=aSIDS.ChangeBox();
 697       aBoxDS = Bnd_Box();
 698       BRepBndLib::Add(aV, aBoxDS);
 699       aBoxDS.SetGap(aBoxDS.GetGap() + Precision::Confusion());
 700       //
 701       if (aDMVLV.IsBound(nV1))
 702         aDMVLV.UnBind(nV1);
 703     }
 704     //
 705     ProcessExistingPaveBlocks(i, nF1, nF2, aMPBOnIn, aDMBV, aMSCPB, aMVI, aPBFacesMap, aMPBAdd);
 706     //
 707     // If the pair of faces has produced any real section edges
 708     // it is necessary to check if these edges do not intersect
 709     // any common IN edges of the faces. For that, all such edges
 710     // are added for Post Treatment along with sections edges.
 711     if (bHasRealSectionEdge) {
 712       const BOPDS_IndexedMapOfPaveBlock& aMPBIn1 = aFI1.PaveBlocksIn();
 713       const BOPDS_IndexedMapOfPaveBlock& aMPBIn2 = aFI2.PaveBlocksIn();
 714       //
 715       // For simplicity add all IN edges into the first set of section curves.
 716       // These existing edges will be removed from the set on the post treatment
 717       // stage in the UpdateFaceInfo function.
 718       BOPDS_ListOfPaveBlock& aLPBC = aVC.ChangeValue(0).ChangePaveBlocks();
 719       //
 720       Standard_Integer aNbIn1 = aMPBIn1.Extent();
 721       for (j = 1; j <= aNbIn1; ++j) {
 722         const Handle(BOPDS_PaveBlock)& aPB = aMPBIn1(j);
 723         if (aMPBIn2.Contains(aPB) && aMPBAdd.Add(aPB)) {
 724           PreparePostTreatFF(i, 0, aPB, aMSCPB, aMVI, aLPBC);
 725         }
 726       }
 727     }
 728   }//for (i=0; i<aNbFF; ++i) {
 729
 730   // Remove "micro" section edges
 731   RemoveMicroSectionEdges(aMSCPB, aMicroPB);
 732
 733   // post treatment
 734   MakeSDVerticesFF(aDMVLV, aDMNewSD);
 735   PostTreatFF(aMSCPB, aDMExEdges, aDMNewSD, aMicroPB, aVertsOnRejectedPB, aAllocator);
 736   if (HasErrors()) {
 737     return;
 738   }
 739   // reduce tolerances of section edges where it is appropriate
 740   CorrectToleranceOfSE();
 741   //
 742   // update face info
 743   UpdateFaceInfo(aDMExEdges, aDMNewSD, aPBFacesMap);
 744   //Update all pave blocks
 745   UpdatePaveBlocks(aDMNewSD);
 746   //
 747   // Treat possible common zones by trying to put each section edge
 748   // into all faces, not participated in creation of that edge, as IN edge
 749   PutSEInOtherFaces();
 750   //
 751   //-----------------------------------------------------scope t
 752   aMVStick.Clear();
 753   aMPBOnIn.Clear();
 754   aMVOnIn.Clear();
 755   aMVCommon.Clear();
 756   aDMExEdges.Clear();
 757   aMI.Clear();
 758   aDMNewSD.Clear();
 759 }
 760
 761 //=======================================================================
 762 //function : MakeSDVerticesFF
 763 //purpose  :
 764 //=======================================================================
 765 void BOPAlgo_PaveFiller::MakeSDVerticesFF
 766   (const TColStd_DataMapOfIntegerListOfInteger& theDMVLV,
 767    TColStd_DataMapOfIntegerInteger& theDMNewSD)
 768 {
 769   // Create a new SD vertex for each group of coinciding vertices
 770   // and put new substitutions to theDMNewSD.
 771   TColStd_DataMapIteratorOfDataMapOfIntegerListOfInteger aItG(theDMVLV);
 772   for (; aItG.More(); aItG.Next()) {
 773     const TColStd_ListOfInteger& aList = aItG.Value();
 774     // make SD vertices w/o creation of interfs
 775     Standard_Integer nSD = MakeSDVertices(aList, Standard_False);
 776     // update theDMNewSD
 777     TColStd_ListIteratorOfListOfInteger aItL(aList);
 778     for (; aItL.More(); aItL.Next()) {
 779       Standard_Integer nV = aItL.Value();
 780       theDMNewSD.Bind(nV, nSD);
 781     }
 782   }
 783 }
 784
 785 //=======================================================================
 786 //function : PostTreatFF
 787 //purpose  :
 788 //=======================================================================
 789 void BOPAlgo_PaveFiller::PostTreatFF
 790     (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMSCPB,
 791      BOPDS_DataMapOfPaveBlockListOfPaveBlock& aDMExEdges,
 792      TColStd_DataMapOfIntegerInteger& aDMNewSD,
 793      const BOPDS_IndexedMapOfPaveBlock& theMicroPB,
 794      const TopTools_IndexedMapOfShape& theVertsOnRejectedPB,
 795      const Handle(NCollection_BaseAllocator)& theAllocator)
 796 {
 797   Standard_Integer aNbS = theMSCPB.Extent();
 798   if (!aNbS) {
 799     return;
 800   }
 801   //
 802   Standard_Boolean bHasPaveBlocks, bOld;
 803   Standard_Integer nSx, nVSD, iX, iP, iC, j, nV, iV = 0, iE, k;
 804   Standard_Integer aNbLPBx;
 805   TopAbs_ShapeEnum aType;
 806   TopoDS_Shape aV, aE;
 807   TopTools_ListIteratorOfListOfShape aItLS;
 808   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
 809   BOPDS_PDS aPDS;
 810   Handle(BOPDS_PaveBlock) aPB1;
 811   BOPDS_Pave aPave[2];
 812   BOPDS_ShapeInfo aSI;
 813   //
 814   TopTools_ListOfShape aLS(theAllocator);
 815   BOPAlgo_PaveFiller aPF(theAllocator);
 816   aPF.SetIsPrimary(Standard_False);
 817   aPF.SetNonDestructive(myNonDestructive);
 818   //
 819   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
 820   Standard_Integer aNbFF = aFFs.Length();
 821   //
 822
 823   //Find unused vertices
 824   TopTools_IndexedMapOfShape VertsUnused;
 825   TColStd_MapOfInteger IndMap;
 826   for (Standard_Integer i = 0; i < aNbFF; i++)
 827   {
 828     BOPDS_InterfFF& aFF = aFFs(i);
 829     Standard_Integer nF1, nF2;
 830     aFF.Indices(nF1, nF2);
 831
 832     TColStd_MapOfInteger aMV, aMVEF, aMI;
 833     GetStickVertices(nF1, nF2, aMV, aMVEF, aMI);
 834     BOPDS_VectorOfCurve& aVC = aFF.ChangeCurves();
 835     Standard_Integer aNbC = aVC.Length();
 836     for (j = 0; j < aNbC; j++)
 837     {
 838       BOPDS_Curve& aNC = aVC.ChangeValue(j);
 839       RemoveUsedVertices(aNC, aMV);
 840     }
 841
 842     TColStd_MapIteratorOfMapOfInteger itmap(aMV);
 843     for(; itmap.More(); itmap.Next())
 844     {
 845       Standard_Integer indV = itmap.Value();
 846       const TopoDS_Shape& aVertex = myDS->Shape(indV);
 847       if (IndMap.Add(indV))
 848         VertsUnused.Add(aVertex);
 849       else
 850         VertsUnused.RemoveKey(aVertex);
 851     }
 852   }
 853   /////////////////////
 854
 855   Standard_Integer aNbME = theMicroPB.Extent();
 856   Standard_Integer aNbVOnRPB = theVertsOnRejectedPB.Extent();
 857   // 0
 858   if (aNbS==1 && (aNbME == 0) && (aNbVOnRPB == 0) && VertsUnused.IsEmpty()) {
 859     const TopoDS_Shape& aS=theMSCPB.FindKey(1);
 860     const BOPDS_CoupleOfPaveBlocks &aCPB=theMSCPB.FindFromIndex(1);
 861     //
 862     aType=aS.ShapeType();
 863     if (aType==TopAbs_VERTEX) {
 864       aSI.SetShapeType(aType);
 865       aSI.SetShape(aS);
 866       iV=myDS->Append(aSI);
 867       //
 868       iX=aCPB.IndexInterf();
 869       iP=aCPB.Index();
 870       BOPDS_InterfFF& aFF=aFFs(iX);
 871       BOPDS_VectorOfPoint& aVNP=aFF.ChangePoints();
 872       BOPDS_Point& aNP=aVNP(iP);
 873       aNP.SetIndex(iV);
 874     }
 875     else if (aType==TopAbs_EDGE) {
 876       aPB1=aCPB.PaveBlock1();
 877       //
 878       if (aPB1->HasEdge()) {
 879         BOPDS_ListOfPaveBlock aLPBx;
 880         aLPBx.Append(aPB1);
 881         aDMExEdges.Bind(aPB1, aLPBx);
 882       } else {
 883         aSI.SetShapeType(aType);
 884         aSI.SetShape(aS);
 885         iE=myDS->Append(aSI);
 886         //
 887         aPB1->SetEdge(iE);
 888       }
 889     }
 890     return;
 891   }
 892   //
 893   // 1 prepare arguments
 894   TopTools_MapOfShape anAddedSD;
 895   for (k = aNbS; k > 0; --k) {
 896     const TopoDS_Shape& aS=theMSCPB.FindKey(k);
 897     aLS.Append(aS);
 898     // add vertices-candidates for SD from the map aDMNewSD,
 899     // so that they took part in fuse operation.
 900     TopoDS_Iterator itV(aS);
 901     for (; itV.More(); itV.Next())
 902     {
 903       const TopoDS_Shape& aVer = itV.Value();
 904       Standard_Integer iVer = myDS->Index(aVer);
 905       const Standard_Integer* pSD = aDMNewSD.Seek(iVer);
 906       if (pSD)
 907       {
 908         const TopoDS_Shape& aVSD = myDS->Shape(*pSD);
 909         if (anAddedSD.Add(aVSD))
 910           aLS.Append(aVSD);
 911       }
 912     }
 913   }
 914   //
 915   // The section edges considered as a micro should be
 916   // specially treated - their vertices should be united and
 917   // the edge itself should be removed. Thus, we add only
 918   // its vertices into operation.
 919   //
 920   BRep_Builder aBB;
 921   for (k = 1; k <= aNbME; ++k) {
 922     Standard_Integer nVerts[2];
 923     theMicroPB(k)->Indices(nVerts[0], nVerts[1]);
 924     TopoDS_Vertex aVerts[2];
 925     for (Standard_Integer i = 0; i < 2; ++i) {
 926       const Standard_Integer* pSD = aDMNewSD.Seek(nVerts[i]);
 927       aVerts[i] = TopoDS::Vertex(myDS->Shape(pSD ? *pSD : nVerts[i]));
 928       if (anAddedSD.Add(aVerts[i]))
 929         aLS.Append(aVerts[i]);
 930     }
 931     //
 932     if (aVerts[0].IsSame(aVerts[1])) {
 933       continue;
 934     }
 935     //
 936     // make sure these vertices will be united
 937     const gp_Pnt& aP1 = BRep_Tool::Pnt(aVerts[0]);
 938     const gp_Pnt& aP2 = BRep_Tool::Pnt(aVerts[1]);
 939     //
 940     Standard_Real aDist = aP1.Distance(aP2);
 941     Standard_Real aTolV1 = BRep_Tool::Tolerance(aVerts[0]);
 942     Standard_Real aTolV2 = BRep_Tool::Tolerance(aVerts[1]);
 943     //
 944     aDist -= (aTolV1 + aTolV2);
 945     if (aDist > 0.) {
 946       aDist /= 2.;
 947       aBB.UpdateVertex(aVerts[0], aTolV1 + aDist);
 948       aBB.UpdateVertex(aVerts[1], aTolV2 + aDist);
 949     }
 950   }
 951
 952   // Add vertices put on the real section curves to unify them with the
 953   // vertices of the edges, by which these sections curves have been rejected
 954   // and with unused vertices
 955   const TopTools_IndexedMapOfShape* VerMap [2] = {&theVertsOnRejectedPB, &VertsUnused};
 956   for (Standard_Integer imap = 0; imap < 2; imap++)
 957   {
 958     Standard_Integer NbVer = VerMap[imap]->Extent();
 959     for (Standard_Integer i = 1; i <= NbVer; ++i)
 960     {
 961       TopoDS_Shape aVer = VerMap[imap]->FindKey(i);
 962       Standard_Integer iVer = myDS->Index(aVer);
 963       const Standard_Integer* pSD = aDMNewSD.Seek(iVer);
 964       if (pSD)
 965         aVer = myDS->Shape(*pSD);
 966
 967       if (anAddedSD.Add(aVer))
 968         aLS.Append(aVer);
 969     }
 970   }
 971   //
 972   // 2 Fuse shapes
 973   aPF.SetProgressIndicator(myProgressIndicator);
 974   aPF.SetRunParallel(myRunParallel);
 975   aPF.SetArguments(aLS);
 976   aPF.Perform();
 977   if (aPF.HasErrors()) {
 978     AddError (new BOPAlgo_AlertPostTreatFF);
 979     return;
 980   }
 981   aPDS=aPF.PDS();
 982   //
 983   // Map to store the real tolerance of the common block
 984   // and avoid repeated computation of it
 985   NCollection_DataMap<Handle(BOPDS_CommonBlock),
 986                       Standard_Real,
 987                       TColStd_MapTransientHasher> aMCBTol;
 988   // Map to avoid creation of different pave blocks for
 989   // the same intersection edge
 990   NCollection_DataMap<Standard_Integer, Handle(BOPDS_PaveBlock)> aMEPB;
 991   //
 992   aItLS.Initialize(aLS);
 993   for (; aItLS.More(); aItLS.Next()) {
 994     const TopoDS_Shape& aSx=aItLS.Value();
 995     nSx=aPDS->Index(aSx);
 996     const BOPDS_ShapeInfo& aSIx=aPDS->ShapeInfo(nSx);
 997     //
 998     aType=aSIx.ShapeType();
 999     //
1000     if (aType==TopAbs_VERTEX) {
1001       Standard_Boolean bIntersectionPoint = theMSCPB.Contains(aSx);
1002       //
1003       if (aPDS->HasShapeSD(nSx, nVSD)) {
1004         aV=aPDS->Shape(nVSD);
1005       }
1006       else {
1007         aV=aSx;
1008       }
1009       // index of new vertex in theDS -> iV
1010       iV = myDS->Index(aV);
1011       if (iV < 0) {
1012         aSI.SetShapeType(aType);
1013         aSI.SetShape(aV);
1014         iV=myDS->Append(aSI);
1015       }
1016       //
1017       if (!bIntersectionPoint) {
1018         // save SD connection
1019         nSx = myDS->Index(aSx);
1020         if (nSx != iV)
1021         {
1022           aDMNewSD.Bind(nSx, iV);
1023           myDS->AddShapeSD(nSx, iV);
1024         }
1025       }
1026       else {
1027         // update FF interference
1028         const BOPDS_CoupleOfPaveBlocks &aCPB=theMSCPB.FindFromKey(aSx);
1029         iX=aCPB.IndexInterf();
1030         iP=aCPB.Index();
1031         BOPDS_InterfFF& aFF=aFFs(iX);
1032         BOPDS_VectorOfPoint& aVNP=aFF.ChangePoints();
1033         BOPDS_Point& aNP=aVNP(iP);
1034         aNP.SetIndex(iV);
1035       }
1036     }//if (aType==TopAbs_VERTEX) {
1037     //
1038     else if (aType==TopAbs_EDGE) {
1039       bHasPaveBlocks=aPDS->HasPaveBlocks(nSx);
1040       const BOPDS_CoupleOfPaveBlocks &aCPB=theMSCPB.FindFromKey(aSx);
1041       iX=aCPB.IndexInterf();
1042       iC=aCPB.Index();
1043       aPB1=aCPB.PaveBlock1();
1044       //
1045       bOld = aPB1->HasEdge();
1046       if (bOld) {
1047         BOPDS_ListOfPaveBlock aLPBx;
1048         aDMExEdges.Bind(aPB1, aLPBx);
1049       }
1050       //
1051       if (!bHasPaveBlocks) {
1052         if (bOld) {
1053           aDMExEdges.ChangeFind(aPB1).Append(aPB1);
1054         }
1055         else {
1056           aSI.SetShapeType(aType);
1057           aSI.SetShape(aSx);
1058           iE = myDS->Append(aSI);
1059           //
1060           aPB1->SetEdge(iE);
1061         }
1062       }
1063       else {
1064         BOPDS_InterfFF& aFF=aFFs(iX);
1065         BOPDS_VectorOfCurve& aVNC=aFF.ChangeCurves();
1066         BOPDS_Curve& aNC=aVNC(iC);
1067         BOPDS_ListOfPaveBlock& aLPBC=aNC.ChangePaveBlocks();
1068         //
1069         // check if edge occurred to be micro edge;
1070         // note we check not the edge aSx itself, but its image in aPDS
1071         const BOPDS_ListOfPaveBlock& aLPBx = aPDS->PaveBlocks(nSx);
1072         aNbLPBx = aLPBx.Extent();
1073         if (aNbLPBx == 0 || (aNbLPBx == 1 && !aLPBx.First()->HasShrunkData())) {
1074           BOPDS_ListIteratorOfListOfPaveBlock it(aLPBC);
1075           for (; it.More(); it.Next()) {
1076             if (it.Value() == aPB1) {
1077               aLPBC.Remove(it);
1078               break;
1079             }
1080           }
1081
1082           // The edge became micro edge, check vertices for SD
1083           TopoDS_Iterator itV(aSx);
1084           for (; itV.More(); itV.Next())
1085             aLS.Append(itV.Value());
1086
1087           continue;
1088         }
1089         //
1090         if (bOld && !aNbLPBx) {
1091           aDMExEdges.ChangeFind(aPB1).Append(aPB1);
1092           continue;
1093         }
1094         //
1095         if (!bOld) {
1096           aItLPB.Initialize(aLPBC);
1097           for (; aItLPB.More(); aItLPB.Next()) {
1098             const Handle(BOPDS_PaveBlock)& aPBC=aItLPB.Value();
1099             if (aPBC==aPB1) {
1100               aLPBC.Remove(aItLPB);
1101               break;
1102             }
1103           }
1104         }
1105         //
1106         if (aNbLPBx) {
1107           aItLPB.Initialize(aLPBx);
1108           for (; aItLPB.More(); aItLPB.Next()) {
1109             const Handle(BOPDS_PaveBlock)& aPBx=aItLPB.Value();
1110             const Handle(BOPDS_PaveBlock) aPBRx=aPDS->RealPaveBlock(aPBx);
1111             //
1112             // update vertices of paves
1113             aPave[0] = aPBx->Pave1();
1114             aPave[1] = aPBx->Pave2();
1115             for (j=0; j<2; ++j) {
1116               nV = aPave[j].Index();
1117               aV = aPDS->Shape(nV);
1118               // index of new vertex in myDS -> iV
1119               iV = myDS->Index(aV);
1120               if (iV < 0) {
1121                 aSI.SetShapeType(TopAbs_VERTEX);
1122                 aSI.SetShape(aV);
1123                 iV = myDS->Append(aSI);
1124               }
1125               const BOPDS_Pave& aP1 = !j ? aPB1->Pave1() : aPB1->Pave2();
1126               if (aP1.Index() != iV) {
1127                 if (aP1.Parameter() == aPave[j].Parameter()) {
1128                   aDMNewSD.Bind(aP1.Index(), iV);
1129                   myDS->AddShapeSD(aP1.Index(), iV);
1130                 }
1131                 else {
1132                   // check aPDS to have the SD connection between these vertices
1133                   const TopoDS_Shape& aVPave = myDS->Shape(aP1.Index());
1134                   Standard_Integer nVnewSD, nVnew = aPDS->Index(aVPave);
1135                   if (aPDS->HasShapeSD(nVnew, nVnewSD)) {
1136                     if (nVnewSD == nV) {
1137                       aDMNewSD.Bind(aP1.Index(), iV);
1138                       myDS->AddShapeSD(aP1.Index(), iV);
1139                     }
1140                   }
1141                 }
1142               }
1143               //
1144               aPave[j].SetIndex(iV);
1145             }
1146             //
1147             // add edge
1148             aE=aPDS->Shape(aPBRx->Edge());
1149             iE = myDS->Index(aE);
1150             if (iE < 0) {
1151               aSI.SetShapeType(aType);
1152               aSI.SetShape(aE);
1153               iE=myDS->Append(aSI);
1154             }
1155             //
1156             // update real edge tolerance according to distances in common block if any
1157             if (aPDS->IsCommonBlock(aPBRx)) {
1158               const Handle(BOPDS_CommonBlock)& aCB = aPDS->CommonBlock(aPBRx);
1159               Standard_Real *pTol = aMCBTol.ChangeSeek(aCB);
1160               if (!pTol) {
1161                 Standard_Real aTol = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, aPDS, aPF.Context());
1162                 pTol = aMCBTol.Bound(aCB, aTol);
1163               }
1164               //
1165               if (aNC.Tolerance() < *pTol) {
1166                 aNC.SetTolerance(*pTol);
1167               }
1168             }
1169             // append new PaveBlock to aLPBC
1170             Handle(BOPDS_PaveBlock) *pPBC = aMEPB.ChangeSeek(iE);
1171             if (!pPBC) {
1172               pPBC = aMEPB.Bound(iE, new BOPDS_PaveBlock());
1173               BOPDS_Pave aPaveR1, aPaveR2;
1174               aPaveR1 = aPBRx->Pave1();
1175               aPaveR2 = aPBRx->Pave2();
1176               aPaveR1.SetIndex(myDS->Index(aPDS->Shape(aPaveR1.Index())));
1177               aPaveR2.SetIndex(myDS->Index(aPDS->Shape(aPaveR2.Index())));
1178               //
1179               (*pPBC)->SetPave1(aPaveR1);
1180               (*pPBC)->SetPave2(aPaveR2);
1181               (*pPBC)->SetEdge(iE);
1182             }
1183             //
1184             if (bOld) {
1185               (*pPBC)->SetOriginalEdge(aPB1->OriginalEdge());
1186               aDMExEdges.ChangeFind(aPB1).Append(*pPBC);
1187             }
1188             else {
1189               aLPBC.Append(*pPBC);
1190             }
1191           }
1192         }
1193       }
1194     }//else if (aType==TopAbs_EDGE)
1195   }//for (; aItLS.More(); aItLS.Next()) {
1196
1197   // Update SD for vertices that did not participate in operation
1198   TColStd_DataMapOfIntegerInteger::Iterator itDM(aDMNewSD);
1199   for (; itDM.More(); itDM.Next())
1200   {
1201     const Standard_Integer* pSD = aDMNewSD.Seek(itDM.Value());
1202     if (pSD)
1203     {
1204       itDM.ChangeValue() = *pSD;
1205       myDS->AddShapeSD(itDM.Key(), *pSD);
1206     }
1207   }
1208   return;
1209 }
1210
1211 //=======================================================================
1212 //function : UpdateFaceInfo
1213 //purpose  :
1214 //=======================================================================
1215 void BOPAlgo_PaveFiller::UpdateFaceInfo
1216   (BOPDS_DataMapOfPaveBlockListOfPaveBlock& theDME,
1217    const TColStd_DataMapOfIntegerInteger& theDMV,
1218    const BOPAlgo_DataMapOfPaveBlockListOfInteger& thePBFacesMap)
1219 {
1220   Standard_Integer i, j, nV1, nF1, nF2,
1221                    aNbFF, aNbC, aNbP;
1222   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
1223   TColStd_MapOfInteger aMF;
1224
1225   // Unify pave blocks of the existing edges united on the post-treat stage
1226   NCollection_DataMap<Standard_Integer, BOPDS_ListOfPaveBlock> anEdgeLPB;
1227
1228   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
1229   aNbFF=aFFs.Length();
1230   //1. Sections (curves, points);
1231   for (i=0; i<aNbFF; ++i) {
1232     BOPDS_InterfFF& aFF=aFFs(i);
1233     aFF.Indices(nF1, nF2);
1234     //
1235     BOPDS_FaceInfo& aFI1=myDS->ChangeFaceInfo(nF1);
1236     BOPDS_FaceInfo& aFI2=myDS->ChangeFaceInfo(nF2);
1237     //
1238     // 1.1. Section edges
1239     BOPDS_VectorOfCurve& aVNC=aFF.ChangeCurves();
1240     aNbC=aVNC.Length();
1241     for (j=0; j<aNbC; ++j) {
1242       BOPDS_Curve& aNC=aVNC(j);
1243       BOPDS_ListOfPaveBlock& aLPBC=aNC.ChangePaveBlocks();
1244       //
1245       // Add section edges to face info
1246       aItLPB.Initialize(aLPBC);
1247       for (; aItLPB.More(); ) {
1248         const Handle(BOPDS_PaveBlock)& aPB=aItLPB.Value();
1249         //
1250         // Treat existing pave blocks
1251         if (theDME.IsBound(aPB)) {
1252           BOPDS_ListOfPaveBlock& aLPB=theDME.ChangeFind(aPB);
1253           UpdateExistingPaveBlocks(aPB, aLPB, thePBFacesMap);
1254
1255           BOPDS_ListIteratorOfListOfPaveBlock itLPB(aLPB);
1256           for (; itLPB.More(); itLPB.Next())
1257           {
1258             const Standard_Integer nE = itLPB.Value()->Edge();
1259             BOPDS_ListOfPaveBlock* pLPBOnE = anEdgeLPB.ChangeSeek(nE);
1260             if (!pLPBOnE)
1261               pLPBOnE = anEdgeLPB.Bound(nE, BOPDS_ListOfPaveBlock());
1262             pLPBOnE->Append(itLPB.Value());
1263           }
1264
1265           aLPBC.Remove(aItLPB);
1266           continue;
1267         }
1268         //
1269         aFI1.ChangePaveBlocksSc().Add(aPB);
1270         aFI2.ChangePaveBlocksSc().Add(aPB);
1271         // Add edge-PB connection
1272         const Standard_Integer nE = aPB->Edge();
1273         BOPDS_ListOfPaveBlock* pLPBOnE = anEdgeLPB.ChangeSeek(nE);
1274         if (!pLPBOnE)
1275           pLPBOnE = anEdgeLPB.Bound(nE, BOPDS_ListOfPaveBlock());
1276         pLPBOnE->Append(aPB);
1277
1278         aItLPB.Next();
1279       }
1280     }
1281     //
1282     // 1.2. Section vertices
1283     const BOPDS_VectorOfPoint& aVNP=aFF.Points();
1284     aNbP=aVNP.Length();
1285     for (j=0; j<aNbP; ++j) {
1286       const BOPDS_Point& aNP=aVNP(j);
1287       nV1=aNP.Index();
1288       if (nV1<0) {
1289         continue;
1290       }
1291       aFI1.ChangeVerticesSc().Add(nV1);
1292       aFI2.ChangeVerticesSc().Add(nV1);
1293     }
1294     //
1295     aMF.Add(nF1);
1296     aMF.Add(nF2);
1297   }
1298
1299   Standard_Boolean bNewCB = Standard_False;
1300   {
1301     // Unify pave blocks of the existing edges united on the post-treat stage
1302     // by making new Common blocks from them
1303     NCollection_DataMap<Standard_Integer,
1304                         BOPDS_ListOfPaveBlock>::Iterator itDM(anEdgeLPB);
1305     for (; itDM.More(); itDM.Next())
1306     {
1307       const BOPDS_ListOfPaveBlock& aLPB = itDM.Value();
1308       if (aLPB.Extent() == 1)
1309         continue;
1310
1311       bNewCB = Standard_True;
1312
1313       // Find or create common block
1314       Handle(BOPDS_CommonBlock) aCB;
1315       // Collect all faces attached to common blocks
1316       TColStd_MapOfInteger aMFaces;
1317       // Collect all pave blocks attached to common blocks
1318       BOPDS_IndexedMapOfPaveBlock aMPaveBlocks;
1319
1320       BOPDS_ListIteratorOfListOfPaveBlock itLPB(aLPB);
1321       for (; itLPB.More(); itLPB.Next())
1322       {
1323         const Handle(BOPDS_PaveBlock)& aPB = itLPB.Value();
1324         aMPaveBlocks.Add(aPB);
1325
1326         if (myDS->IsCommonBlock(aPB))
1327         {
1328           Handle(BOPDS_CommonBlock) aPBCB = myDS->CommonBlock(aPB);
1329           // Get pave blocks
1330           const BOPDS_ListOfPaveBlock& aLPBOnCB = aPBCB->PaveBlocks();
1331           for (BOPDS_ListOfPaveBlock::Iterator it(aLPBOnCB); it.More(); it.Next())
1332             aMPaveBlocks.Add(it.Value());
1333
1334           // Get faces
1335           const TColStd_ListOfInteger& aLFacesOnCB = aPBCB->Faces();
1336           for (TColStd_ListOfInteger::Iterator it(aLFacesOnCB); it.More(); it.Next())
1337             aMFaces.Add(it.Value());
1338
1339           if (aCB.IsNull())
1340             aCB = aPBCB;
1341         }
1342       }
1343
1344       if (aCB.IsNull())
1345       {
1346         // None of the pave blocks in the list is a common block,
1347         // so create the new one.
1348         aCB = new BOPDS_CommonBlock;
1349         aCB->SetPaveBlocks(aLPB);
1350         itLPB.Initialize(aLPB);
1351         for (; itLPB.More(); itLPB.Next())
1352         {
1353           const Handle(BOPDS_PaveBlock)& aPB = itLPB.Value();
1354           myDS->SetCommonBlock(aPB, aCB);
1355         }
1356       }
1357       else
1358       {
1359         // Update common block with new pave blocks
1360         BOPDS_ListOfPaveBlock aLPBNew;
1361         {
1362           const Standard_Integer aNbPB = aMPaveBlocks.Extent();
1363           for (Standard_Integer iPB = 1; iPB <= aNbPB; ++iPB)
1364           {
1365             const Handle(BOPDS_PaveBlock)& aPB = aMPaveBlocks(iPB);
1366             myDS->SetCommonBlock(aPB, aCB);
1367             aLPBNew.Append(aPB);
1368           }
1369         }
1370         aCB->SetPaveBlocks(aLPBNew);
1371
1372         // Update faces of the common block
1373         TColStd_ListOfInteger aLFaces;
1374         for (TColStd_MapOfInteger::Iterator it(aMFaces); it.More(); it.Next())
1375           aLFaces.Append(it.Value());
1376         aCB->SetFaces(aLFaces);
1377       }
1378     }
1379   }
1380
1381   Standard_Boolean bVerts = theDMV.Extent() > 0;
1382   Standard_Boolean bEdges = theDME.Extent() > 0 || bNewCB;
1383   //
1384   if (!bVerts && !bEdges) {
1385     return;
1386   }
1387   //
1388   // 2. Update Face Info information with new vertices and new
1389   //    pave blocks created in PostTreatFF from existing ones
1390   Standard_Integer nV2;
1391   TColStd_MapIteratorOfMapOfInteger aItMF;
1392   TColStd_DataMapIteratorOfDataMapOfIntegerInteger aItMV;
1393   //
1394   aItMF.Initialize(aMF);
1395   for (; aItMF.More(); aItMF.Next()) {
1396     nF1 = aItMF.Value();
1397     //
1398     BOPDS_FaceInfo& aFI = myDS->ChangeFaceInfo(nF1);
1399     //
1400     // 2.1. Update information about vertices
1401     if (bVerts)
1402     {
1403       TColStd_MapOfInteger& aMVOn = aFI.ChangeVerticesOn();
1404       TColStd_MapOfInteger& aMVIn = aFI.ChangeVerticesIn();
1405       //
1406       aItMV.Initialize(theDMV);
1407       for (; aItMV.More(); aItMV.Next())
1408       {
1409         nV1 = aItMV.Key();
1410         nV2 = aItMV.Value();
1411         //
1412         if (aMVOn.Remove(nV1))
1413           aMVOn.Add(nV2);
1414         //
1415         if (aMVIn.Remove(nV1))
1416           aMVIn.Add(nV2);
1417       } // for (; aItMV.More(); aItMV.Next()) {
1418     } // if (bVerts) {
1419     //
1420     // 2.2. Update information about pave blocks
1421     if (bEdges)
1422     {
1423       BOPDS_MapOfPaveBlock aMPBFence;
1424       BOPDS_IndexedMapOfPaveBlock* pMPB[] = { &aFI.ChangePaveBlocksOn(),
1425                                               &aFI.ChangePaveBlocksIn(),
1426                                               &aFI.ChangePaveBlocksSc() };
1427       for (i = 0; i < 3; ++i)
1428       {
1429         BOPDS_IndexedMapOfPaveBlock aMPBCopy = *pMPB[i];
1430         pMPB[i]->Clear();
1431         const Standard_Integer aNbPB = aMPBCopy.Extent();
1432         for (j = 1; j <= aNbPB; ++j)
1433         {
1434           const Handle(BOPDS_PaveBlock)& aPB = aMPBCopy(j);
1435           const BOPDS_ListOfPaveBlock* pLPB = theDME.Seek(aPB);
1436           if (pLPB && !pLPB->IsEmpty())
1437           {
1438             aItLPB.Initialize(*pLPB);
1439             for (; aItLPB.More(); aItLPB.Next())
1440             {
1441               const Handle(BOPDS_PaveBlock)& aPB1 = aItLPB.Value();
1442               const Handle(BOPDS_PaveBlock)& aPBR = myDS->RealPaveBlock(aPB1);
1443               if (aMPBFence.Add(aPBR))
1444                 pMPB[i]->Add(aPBR);
1445             }
1446           }
1447           else
1448           {
1449             const Handle(BOPDS_PaveBlock)& aPBR = myDS->RealPaveBlock(aPB);
1450             if (aMPBFence.Add(aPBR))
1451               pMPB[i]->Add(aPBR);
1452           }
1453         } // for (j = 1; j <= aNbPB; ++j) {
1454       } // for (i = 0; i < 2; ++i) {
1455     } // if (bEdges) {
1456   }
1457 }
1458 //=======================================================================
1459 //function : IsExistingVertex
1460 //purpose  :
1461 //=======================================================================
1462 Standard_Boolean BOPAlgo_PaveFiller::IsExistingVertex
1463   (const gp_Pnt& aP,
1464    const Standard_Real theTolR3D,
1465    const TColStd_MapOfInteger& aMVOnIn)const
1466 {
1467   Standard_Boolean bRet;
1468   Standard_Integer nV, iFlag;
1469   Standard_Real aTolCheck;
1470   gp_Pnt aPV;
1471   Bnd_Box aBoxP;
1472   TColStd_MapIteratorOfMapOfInteger aIt;
1473   //
1474   aTolCheck = theTolR3D + myFuzzyValue;
1475   bRet=Standard_True;
1476   //
1477   aBoxP.Add(aP);
1478   aBoxP.Enlarge(theTolR3D);
1479   //
1480   aIt.Initialize(aMVOnIn);
1481   for (; aIt.More(); aIt.Next()) {
1482     nV=aIt.Value();
1483     const BOPDS_ShapeInfo& aSIV=myDS->ShapeInfo(nV);
1484     const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aSIV.Shape()));
1485     const Bnd_Box& aBoxV=aSIV.Box();
1486     //
1487     if (!aBoxP.IsOut(aBoxV)) {
1488       iFlag=BOPTools_AlgoTools::ComputeVV(aV, aP, aTolCheck);
1489       if (!iFlag) {
1490         return bRet;
1491       }
1492     }
1493   }
1494   return !bRet;
1495 }
1496 //=======================================================================
1497 //function : IsExistingPaveBlock
1498 //purpose  :
1499 //=======================================================================
1500 Standard_Boolean BOPAlgo_PaveFiller::IsExistingPaveBlock
1501   (const Handle(BOPDS_PaveBlock)& thePB,
1502    const BOPDS_Curve& theNC,
1503    const TColStd_ListOfInteger& theLSE,
1504    Standard_Integer& theNEOut,
1505    Standard_Real& theTolNew)
1506 {
1507   if (theLSE.IsEmpty())
1508     return Standard_False;
1509
1510   Standard_Real aT1, aT2, aTm, aTx, aTolE, aTolCheck, aTol, aDist;
1511   Standard_Integer nE, iFlag, nV1, nV2;
1512   gp_Pnt aPm;
1513   Bnd_Box aBoxPm;
1514   TColStd_ListIteratorOfListOfInteger aItLI;
1515   //
1516   thePB->Range(aT1, aT2);
1517   thePB->Indices(nV1, nV2);
1518   const TopoDS_Vertex &aV1 = TopoDS::Vertex(myDS->Shape(nV1)),
1519                       &aV2 = TopoDS::Vertex(myDS->Shape(nV2));
1520   const Standard_Real aTolV1 = BRep_Tool::Tolerance(aV1),
1521                       aTolV2 = BRep_Tool::Tolerance(aV2);
1522
1523   aTol = Max(aTolV1, aTolV2);
1524
1525   aTm=IntTools_Tools::IntermediatePoint (aT1, aT2);
1526   theNC.Curve().D0(aTm, aPm);
1527   aBoxPm.Add(aPm);
1528   aBoxPm.Enlarge(aTol);
1529   //
1530   aItLI.Initialize(theLSE);
1531   for (; aItLI.More(); aItLI.Next()) {
1532     nE=aItLI.Value();
1533     if (nE < 0)
1534       continue;
1535     const BOPDS_ShapeInfo& aSIE=myDS->ChangeShapeInfo(nE);
1536     const Bnd_Box& aBoxE=aSIE.Box();
1537     if (!aBoxE.IsOut(aBoxPm)) {
1538       const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aSIE.Shape()));
1539       aTolE = BRep_Tool::Tolerance(aE);
1540       aTolCheck = Max(aTolE, aTol) + myFuzzyValue;
1541       iFlag = myContext->ComputePE(aPm, aTolCheck, aE, aTx, aDist);
1542       if (!iFlag)
1543       {
1544         theNEOut = nE;
1545         theTolNew = aDist;
1546         return Standard_True;
1547       }
1548     }
1549   }
1550   return Standard_False;
1551 }
1552
1553 //=======================================================================
1554 //function : IsExistingPaveBlock
1555 //purpose  :
1556 //=======================================================================
1557 Standard_Boolean BOPAlgo_PaveFiller::IsExistingPaveBlock
1558     (const Handle(BOPDS_PaveBlock)& thePB,
1559      const BOPDS_Curve& theNC,
1560      const Standard_Real theTolR3D,
1561      const BOPDS_IndexedMapOfPaveBlock& theMPBOnIn,
1562      const BOPDS_MapOfPaveBlock& theMPBCommon,
1563      Handle(BOPDS_PaveBlock)& aPBOut,
1564      Standard_Real& theTolNew)
1565 {
1566   Standard_Boolean bRet;
1567   Standard_Real aT1, aT2, aTm, aTx, aTolCheck;
1568   Standard_Integer nSp, iFlag1, iFlag2, nV11, nV12, nV21, nV22, i, aNbPB;
1569   gp_Pnt aP1, aPm, aP2;
1570   Bnd_Box aBoxP1, aBoxPm, aBoxP2, aBoxTmp;
1571   //
1572   bRet=Standard_False;
1573   aTolCheck = theTolR3D + myFuzzyValue;
1574   const IntTools_Curve& aIC=theNC.Curve();
1575   //
1576   thePB->Range(aT1, aT2);
1577   thePB->Indices(nV11, nV12);
1578   const Standard_Real aTolV11 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV11)));
1579   const Standard_Real aTolV12 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV12)));
1580   const Standard_Real aTolV1 = Max(aTolV11, aTolV12) + myFuzzyValue;
1581
1582   //first point
1583   aIC.D0(aT1, aP1);
1584   aBoxP1.Add(aP1);
1585   aBoxP1.Enlarge(aTolV11);
1586   //intermediate point
1587   aTm=IntTools_Tools::IntermediatePoint (aT1, aT2);
1588   aIC.D0(aTm, aPm);
1589   aBoxPm.Add(aPm);
1590   //last point
1591   aIC.D0(aT2, aP2);
1592   aBoxP2.Add(aP2);
1593   aBoxP2.Enlarge(aTolV12);
1594   //
1595   // Look for the existing pave block closest to the section curve
1596   theTolNew = ::RealLast();
1597
1598   aNbPB = theMPBOnIn.Extent();
1599   for (i = 1; i <= aNbPB; ++i) {
1600     const Handle(BOPDS_PaveBlock)& aPB = theMPBOnIn(i);
1601     aPB->Indices(nV21, nV22);
1602     const Standard_Real aTolV21 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV21)));
1603     const Standard_Real aTolV22 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV22)));
1604     const Standard_Real aTolV2 = Max(aTolV21, aTolV22) + myFuzzyValue;
1605     nSp=aPB->Edge();
1606     if (nSp < 0)
1607       continue;
1608     const BOPDS_ShapeInfo& aSISp=myDS->ChangeShapeInfo(nSp);
1609     const TopoDS_Edge& aSp=(*(TopoDS_Edge *)(&aSISp.Shape()));
1610     const Bnd_Box& aBoxSp=aSISp.Box();
1611     //
1612     iFlag1 = (nV11 == nV21 || nV11 == nV22) ? 2 :
1613       (!aBoxSp.IsOut(aBoxP1) ? 1 : 0);
1614     iFlag2 = (nV12 == nV21 || nV12 == nV22) ? 2 :
1615       (!aBoxSp.IsOut(aBoxP2) ? 1 : 0);
1616     if (iFlag1 && iFlag2) {
1617       Standard_Real aDist = 0.;
1618
1619       Standard_Real aRealTol = aTolCheck;
1620       if (myDS->IsCommonBlock(aPB))
1621       {
1622         aRealTol = Max(aRealTol, Max(aTolV1, aTolV2));
1623         if (theMPBCommon.Contains(aPB))
1624           // for an edge, which is a common block with a face,
1625           // increase the chance to coincide with section curve
1626           aRealTol *= 2.;
1627       }
1628
1629       aBoxTmp = aBoxPm;
1630       aBoxTmp.Enlarge(aRealTol);
1631
1632       Standard_Real aDistToSp = 0.;
1633       if (aBoxSp.IsOut(aBoxTmp) || myContext->ComputePE(aPm,
1634                                                         aRealTol,
1635                                                         aSp,
1636                                                         aTx, aDistToSp)) {
1637         continue;
1638       }
1639       //
1640       if (iFlag1 == 1) {
1641         iFlag1 = !myContext->ComputePE(aP1, aRealTol, aSp, aTx, aDist);
1642         if (iFlag1 && aDistToSp < aDist)
1643           aDistToSp = aDist;
1644       }
1645       //
1646       if (iFlag2 == 1) {
1647         iFlag2 = !myContext->ComputePE(aP2, aRealTol, aSp, aTx, aDist);
1648         if (iFlag2 && aDistToSp < aDist)
1649           aDistToSp = aDist;
1650       }
1651       //
1652       if (iFlag1 && iFlag2)
1653       {
1654         if (aDistToSp < theTolNew)
1655         {
1656           aPBOut = aPB;
1657           theTolNew = aDistToSp;
1658           bRet = Standard_True;
1659         }
1660       }
1661     }
1662   }
1663   return bRet;
1664 }
1665
1666 //=======================================================================
1667 //function :
1668 //purpose  :
1669 //=======================================================================
1670 static void getBoundPaves(const BOPDS_DS* theDS,
1671                           BOPDS_Curve& theNC,
1672                           Standard_Integer theNV[2])
1673 {
1674   theNV[0] = theNV[1] = -1;
1675
1676   // get extreme paves
1677   Handle(BOPDS_PaveBlock)& aPB = theNC.ChangePaveBlock1();
1678   const BOPDS_ListOfPave& aLP = aPB->ExtPaves();
1679   Standard_Integer aNbEP = aLP.Extent();
1680   if (aNbEP == 0)
1681     return;
1682   Standard_Real aTmin = RealLast();
1683   Standard_Real aTmax = -aTmin;
1684   for (BOPDS_ListIteratorOfListOfPave aItLP(aLP); aItLP.More(); aItLP.Next())
1685   {
1686     const BOPDS_Pave& aPv = aItLP.Value();
1687     Standard_Integer nV;
1688     Standard_Real aTV;
1689     aPv.Contents(nV, aTV);
1690     if (aTV < aTmin) {
1691       theNV[0] = aPv.Index();
1692       aTmin = aTV;
1693     }
1694     if (aTV > aTmax) {
1695       theNV[1] = aPv.Index();
1696       aTmax = aTV;
1697     }
1698   }
1699
1700   // compare extreme vertices with ends of the curve
1701   const IntTools_Curve& aIC = theNC.Curve();
1702   Standard_Real aT[2];
1703   gp_Pnt aP[2];
1704   aIC.Bounds(aT[0], aT[1], aP[0], aP[1]);
1705   Standard_Real aTol = Max(theNC.Tolerance(), theNC.TangentialTolerance());
1706   aTol += Precision::Confusion();
1707   for (Standard_Integer j = 0; j < 2; ++j)
1708   {
1709     const BOPDS_ShapeInfo& aSIV = theDS->ShapeInfo(theNV[j]);
1710     const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&aSIV.Shape()));
1711     Standard_Integer iFlag = BOPTools_AlgoTools::ComputeVV(aV, aP[j], aTol);
1712     if (iFlag != 0)
1713       theNV[j] = -1;
1714   }
1715 }
1716
1717 //=======================================================================
1718 //function : PutBoundPaveOnCurve
1719 //purpose  :
1720 //=======================================================================
1721 void BOPAlgo_PaveFiller::PutBoundPaveOnCurve(const TopoDS_Face& aF1,
1722                                              const TopoDS_Face& aF2,
1723                                              BOPDS_Curve& aNC,
1724                                              TColStd_ListOfInteger& aLVB)
1725 {
1726   const IntTools_Curve& aIC=aNC.Curve();
1727   Standard_Real aT[2];
1728   gp_Pnt aP[2];
1729   aIC.Bounds(aT[0], aT[1], aP[0], aP[1]);
1730   Standard_Real aTolR3D = Max(aNC.Tolerance(), aNC.TangentialTolerance());
1731   Handle(BOPDS_PaveBlock)& aPB = aNC.ChangePaveBlock1();
1732   // Get numbers of vertices assigned to the ends of the curve
1733   Standard_Integer aBndNV[2];
1734   getBoundPaves(myDS, aNC, aBndNV);
1735   //
1736   Standard_Real aTolVnew = Precision::Confusion();
1737   for (Standard_Integer j = 0; j<2; ++j)
1738   {
1739     if (aBndNV[j] < 0)
1740     {
1741       // no vertex on this end
1742       if (j && aP[1].IsEqual(aP[0], aTolVnew)) {
1743         //if curve is closed, process only one bound
1744         continue;
1745       }
1746       Standard_Boolean bVF = myContext->IsValidPointForFaces(aP[j], aF1, aF2, aTolR3D);
1747       if (!bVF) {
1748         continue;
1749       }
1750       TopoDS_Vertex aVn;
1751       BOPTools_AlgoTools::MakeNewVertex(aP[j], aTolR3D, aVn);
1752       BOPTools_AlgoTools::UpdateVertex(aIC, aT[j], aVn);
1753       aTolVnew = BRep_Tool::Tolerance(aVn);
1754
1755       BOPDS_ShapeInfo aSIVn;
1756       aSIVn.SetShapeType(TopAbs_VERTEX);
1757       aSIVn.SetShape(aVn);
1758
1759       Bnd_Box& aBox = aSIVn.ChangeBox();
1760       BRepBndLib::Add(aVn, aBox);
1761       aBox.SetGap(aBox.GetGap() + Precision::Confusion());
1762
1763       Standard_Integer nVn = myDS->Append(aSIVn);
1764
1765       BOPDS_Pave aPn;
1766       aPn.SetIndex(nVn);
1767       aPn.SetParameter(aT[j]);
1768       aPB->AppendExtPave(aPn);
1769
1770       aLVB.Append(nVn);
1771     }
1772   }
1773 }
1774
1775 //=======================================================================
1776 //function : PutPavesOnCurve
1777 //purpose  :
1778 //=======================================================================
1779 void BOPAlgo_PaveFiller::PutPavesOnCurve(const TColStd_MapOfInteger& theMVOnIn,
1780                                          const TColStd_MapOfInteger& theMVCommon,
1781                                          BOPDS_Curve& theNC,
1782                                          const TColStd_MapOfInteger& theMI,
1783                                          const TColStd_MapOfInteger& theMVEF,
1784                                          TColStd_DataMapOfIntegerReal& theMVTol,
1785                                          TColStd_DataMapOfIntegerListOfInteger& theDMVLV)
1786 {
1787   Standard_Integer nV;
1788   TColStd_MapIteratorOfMapOfInteger aIt;
1789   //
1790   const Bnd_Box& aBoxC = theNC.Box();
1791   const Standard_Real aTolR3D = Max(theNC.Tolerance(), theNC.TangentialTolerance());
1792   //
1793   //Put EF vertices first
1794   aIt.Initialize(theMVEF);
1795   for (; aIt.More(); aIt.Next())
1796   {
1797     nV = aIt.Value();
1798     PutPaveOnCurve(nV, aTolR3D, theNC, theMI, theMVTol, theDMVLV, 2);
1799   }
1800
1801   //Put all other vertices
1802   aIt.Initialize(theMVOnIn);
1803   for (; aIt.More(); aIt.Next())
1804   {
1805     nV = aIt.Value();
1806     if (theMVEF.Contains(nV))
1807     {
1808       continue;
1809     }
1810
1811     if (!theMVCommon.Contains(nV))
1812     {
1813       const BOPDS_ShapeInfo& aSIV = myDS->ShapeInfo(nV);
1814       const Bnd_Box& aBoxV = aSIV.Box();
1815       //
1816       if (aBoxC.IsOut(aBoxV))
1817       {
1818         continue;
1819       }
1820       if (!myDS->IsNewShape(nV))
1821       {
1822         continue;
1823       }
1824     }
1825     //
1826     PutPaveOnCurve(nV, aTolR3D, theNC, theMI, theMVTol, theDMVLV, 1);
1827   }
1828 }
1829
1830 //=======================================================================
1831 //function : FilterPavesOnCurves
1832 //purpose  :
1833 //=======================================================================
1834 namespace {
1835   struct PaveBlockDist {
1836     Handle(BOPDS_PaveBlock) PB;
1837     Standard_Real SquareDist; // square distance from vertex to the paveblock
1838     Standard_Real SinAngle; // sinus of angle between projection vector
1839     // and tangent at projection point
1840     Standard_Real Tolerance; // tolerance of the section curve
1841   };
1842 }
1843 void BOPAlgo_PaveFiller::FilterPavesOnCurves(const BOPDS_VectorOfCurve& theVNC,
1844                                              TColStd_DataMapOfIntegerReal& theMVTol)
1845 {
1846   // For each vertex found in ExtPaves of pave blocks of section curves
1847   // collect list of pave blocks with distance to the curve
1848   NCollection_IndexedDataMap<Standard_Integer,NCollection_List<PaveBlockDist> > aIDMVertPBs;
1849   Standard_Integer i;
1850   const Standard_Real anEps = gp::Resolution();
1851   for (i = 0; i < theVNC.Length(); ++i)
1852   {
1853     const BOPDS_Curve& aNC = theVNC(i);
1854     const IntTools_Curve& aIC = aNC.Curve();
1855     const Standard_Real aTolR3D = Max(aNC.Tolerance(), aNC.TangentialTolerance());
1856     GeomAdaptor_Curve aGAC(aIC.Curve());
1857     const Handle(BOPDS_PaveBlock)& aPB = aNC.PaveBlocks().First();
1858     const BOPDS_ListOfPave& aPaves = aPB->ExtPaves();
1859     BOPDS_ListOfPave::Iterator itPaves(aPaves);
1860     for (; itPaves.More(); itPaves.Next())
1861     {
1862       const BOPDS_Pave& aPave = itPaves.Value();
1863       Standard_Integer nV = aPave.Index();
1864       const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV));
1865       // compute distance from vertex to the point on curve with vertex parameter
1866       gp_Pnt aPV = BRep_Tool::Pnt(aV);
1867       Standard_Real aPar = aPave.Parameter();
1868       gp_Pnt aPonC;
1869       gp_Vec aD1;
1870       aGAC.D1(aPar, aPonC, aD1);
1871       gp_Vec aProjVec(aPV, aPonC);
1872       Standard_Real aSqDist = aProjVec.SquareMagnitude();
1873       Standard_Real aSqD1Mod = aD1.SquareMagnitude();
1874       Standard_Real aSin = aProjVec.CrossSquareMagnitude(aD1);
1875       if (aSqDist > anEps && aSqD1Mod > anEps)
1876         aSin = sqrt(aSin / aSqDist / aSqD1Mod);
1877       NCollection_List<PaveBlockDist>* pList = aIDMVertPBs.ChangeSeek(nV);
1878       if (!pList)
1879         pList = &aIDMVertPBs.ChangeFromIndex(aIDMVertPBs.Add(nV, NCollection_List<PaveBlockDist>()));
1880       PaveBlockDist aPBD = { aPB, aSqDist, aSin, aTolR3D };
1881       pList->Append(aPBD);
1882     }
1883   }
1884
1885   // Process each vertex
1886   const Standard_Real aSinAngleMin = 0.5; // angle below which projection is suspicious
1887   for (i = 1; i <= aIDMVertPBs.Extent(); i++)
1888   {
1889     Standard_Integer nV = aIDMVertPBs.FindKey(i);
1890     const NCollection_List<PaveBlockDist>& aList = aIDMVertPBs(i);
1891     // Find a pave with minimal distance
1892     Standard_Real aMinDist = RealLast();
1893     Handle(BOPDS_PaveBlock) aPBMinDist;
1894     NCollection_List<PaveBlockDist>::Iterator itL(aList);
1895     for (; itL.More(); itL.Next())
1896     {
1897       const PaveBlockDist& aPBD = itL.Value();
1898       if (aPBD.SquareDist < aMinDist)
1899       {
1900         aMinDist = aPBD.SquareDist;
1901         aPBMinDist = aPBD.PB;
1902       }
1903     }
1904     // Remove a vertex from a pave block if the distance is greater than the tolerance
1905     // and there are other pave blocks for which the distance is less than the current.
1906     // Do not remove a vertex if it is projected on the curve with quite large angle
1907     // (see test bugs modalg_6 bug27761).
1908
1909     // Reduce tolerance for the vertex to the value of maximal distance to
1910     // to section curve on which it will be kept.
1911     Standard_Real aMaxDistKept = -1;
1912     Standard_Boolean isRemoved = Standard_False;
1913     for (itL.Init(aList); itL.More(); itL.Next())
1914     {
1915       const PaveBlockDist& aPBD = itL.Value();
1916       Standard_Real aCheckDist = 100. * Max(aPBD.Tolerance*aPBD.Tolerance, aMinDist);
1917       if (aPBD.SquareDist > aCheckDist && aPBD.SinAngle < aSinAngleMin)
1918       {
1919         aPBD.PB->RemoveExtPave(nV);
1920         isRemoved = Standard_True;
1921       }
1922       else if (aPBD.SquareDist > aMaxDistKept)
1923         aMaxDistKept = aPBD.SquareDist;
1924     }
1925
1926     if (isRemoved && aMaxDistKept > 0)
1927     {
1928       const Standard_Real* pTol = theMVTol.Seek(nV);
1929       if (pTol)
1930       {
1931         const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nV);
1932         const Standard_Real aRealTol = Max(*pTol, sqrt(aMaxDistKept) + Precision::Confusion());
1933         (*(Handle(BRep_TVertex)*)&aV.TShape())->Tolerance(aRealTol);
1934       }
1935     }
1936   }
1937 }
1938
1939 //=======================================================================
1940 //function : ExtendedTolerance
1941 //purpose  :
1942 //=======================================================================
1943 Standard_Boolean BOPAlgo_PaveFiller::ExtendedTolerance
1944   (const Standard_Integer nV,
1945    const TColStd_MapOfInteger& aMI,
1946    Standard_Real& aTolVExt,
1947    const Standard_Integer aType)
1948 {
1949   Standard_Boolean bFound = Standard_False;
1950   if (!(myDS->IsNewShape(nV))) {
1951     return bFound;
1952   }
1953   //
1954   Standard_Integer i, k, aNbLines, aNbInt;
1955   Standard_Real aT11, aT12, aD1, aD2, aD;
1956   TopoDS_Vertex aV;
1957   gp_Pnt aPV, aP11, aP12;
1958   //
1959   k = 0;
1960   aNbInt = 2;
1961   if (aType == 1) {
1962     aNbInt = 1;
1963   } else if (aType == 2) {
1964     k = 1;
1965   }
1966   //
1967   aV = (*(TopoDS_Vertex *)(&myDS->Shape(nV)));
1968   aPV=BRep_Tool::Pnt(aV);
1969   //
1970   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
1971   BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
1972   //
1973   for (; k<aNbInt; ++k) {
1974     aNbLines = !k ? aEEs.Length() : aEFs.Length();
1975     for (i = 0; i < aNbLines; ++i) {
1976       BOPDS_Interf *aInt = !k ? (BOPDS_Interf*) (&aEEs(i)) :
1977         (BOPDS_Interf*) (&aEFs(i));
1978       if (aInt->IndexNew() == nV) {
1979         if (aMI.Contains(aInt->Index1()) &&
1980             aMI.Contains(aInt->Index2())) {
1981           const IntTools_CommonPrt& aComPrt = !k ? aEEs(i).CommonPart() :
1982             aEFs(i).CommonPart();
1983           //
1984           const TopoDS_Edge& aE1=aComPrt.Edge1();
1985           aComPrt.Range1(aT11, aT12);
1986           BOPTools_AlgoTools::PointOnEdge(aE1, aT11, aP11);
1987           BOPTools_AlgoTools::PointOnEdge(aE1, aT12, aP12);
1988           aD1=aPV.Distance(aP11);
1989           aD2=aPV.Distance(aP12);
1990           aD=(aD1>aD2)? aD1 : aD2;
1991           if (aD>aTolVExt) {
1992             aTolVExt=aD;
1993           }
1994           return !bFound;
1995         }//if (aMI.Contains(aEF.Index1()) && aMI.Contains(aEF.Index2())) {
1996       }//if (aInt->IndexNew() == nV) {
1997     }//for (i = 0; i < aNbLines; ++i) {
1998   }//for (k=0; k<2; ++k) {
1999   return bFound;
2000 }
2001
2002 //=======================================================================
2003 //function : GetEFPnts
2004 //purpose  :
2005 //=======================================================================
2006 void BOPAlgo_PaveFiller::GetEFPnts
2007   (const Standard_Integer nF1,
2008    const Standard_Integer nF2,
2009    IntSurf_ListOfPntOn2S& aListOfPnts)
2010 {
2011   Standard_Integer nE, nF, nFOpposite, aNbEFs, i;
2012   Standard_Real U1, U2, V1, V2, f, l;
2013   TColStd_MapOfInteger aMI;
2014   //
2015   //collect indexes of all shapes from nF1 and nF2.
2016   GetFullShapeMap(nF1, aMI);
2017   GetFullShapeMap(nF2, aMI);
2018   //
2019   BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
2020   aNbEFs = aEFs.Length();
2021   //
2022   for(i = 0; i < aNbEFs; ++i) {
2023     const BOPDS_InterfEF& aEF = aEFs(i);
2024     if (aEF.HasIndexNew()) {
2025       aEF.Indices(nE, nFOpposite);
2026       if(aMI.Contains(nE) && aMI.Contains(nFOpposite)) {
2027         const IntTools_CommonPrt& aCP = aEF.CommonPart();
2028         Standard_Real aPar = aCP.VertexParameter1();
2029         const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&myDS->Shape(nE)));
2030         const TopoDS_Face& aFOpposite =
2031           (*(TopoDS_Face*)(&myDS->Shape(nFOpposite)));
2032         //
2033         const Handle(Geom_Curve)& aCurve = BRep_Tool::Curve(aE, f, l);
2034         //
2035         nF = (nFOpposite == nF1) ? nF2 : nF1;
2036         const TopoDS_Face& aF = (*(TopoDS_Face*)(&myDS->Shape(nF)));
2037         Handle(Geom2d_Curve) aPCurve =
2038           BRep_Tool::CurveOnSurface(aE, aF, f, l);
2039         //
2040         GeomAPI_ProjectPointOnSurf& aProj=myContext->ProjPS(aFOpposite);
2041         //
2042         gp_Pnt aPoint;
2043         aCurve->D0(aPar, aPoint);
2044         IntSurf_PntOn2S aPnt;
2045         if(!aPCurve.IsNull()) {
2046           gp_Pnt2d aP2d = aPCurve->Value(aPar);
2047           aProj.Perform(aPoint);
2048           if(aProj.IsDone()) {
2049             aProj.LowerDistanceParameters(U1,V1);
2050             if (nF == nF1) {
2051               aPnt.SetValue(aP2d.X(),aP2d.Y(),U1,V1);
2052             } else {
2053               aPnt.SetValue(U1,V1,aP2d.X(),aP2d.Y());
2054             }
2055             aListOfPnts.Append(aPnt);
2056           }
2057         }
2058         else {
2059           GeomAPI_ProjectPointOnSurf& aProj1 = myContext->ProjPS(aF);
2060           aProj1.Perform(aPoint);
2061           aProj.Perform(aPoint);
2062           if(aProj1.IsDone() && aProj.IsDone()){
2063             aProj1.LowerDistanceParameters(U1,V1);
2064             aProj.LowerDistanceParameters(U2,V2);
2065             if (nF == nF1) {
2066               aPnt.SetValue(U1,V1,U2,V2);
2067             } else {
2068               aPnt.SetValue(U2,V2,U1,V1);
2069             }
2070             aListOfPnts.Append(aPnt);
2071           }
2072         }
2073       }
2074     }
2075   }
2076 }
2077
2078 //=======================================================================
2079 //function : PutEFPavesOnCurve
2080 //purpose  :
2081 //=======================================================================
2082   void BOPAlgo_PaveFiller::PutEFPavesOnCurve
2083   (BOPDS_Curve& aNC,
2084    const TColStd_MapOfInteger& aMI,
2085    const TColStd_MapOfInteger& aMVEF,
2086    TColStd_DataMapOfIntegerReal& aMVTol,
2087    TColStd_DataMapOfIntegerListOfInteger& aDMVLV)
2088 {
2089   if (!aMVEF.Extent()) {
2090     return;
2091   }
2092   //
2093   const IntTools_Curve& aIC=aNC.Curve();
2094   GeomAbs_CurveType aTypeC;
2095   aTypeC=aIC.Type();
2096   if (!(aTypeC==GeomAbs_BezierCurve || aTypeC==GeomAbs_BSplineCurve)) {
2097     return;
2098   }
2099   //
2100   Standard_Integer nV;
2101   TColStd_MapOfInteger aMV;
2102   //
2103   aMV.Assign(aMVEF);
2104   RemoveUsedVertices(aNC, aMV);
2105   if (!aMV.Extent()) {
2106     return;
2107   }
2108   //
2109   Standard_Real aDist;
2110   BOPDS_Pave aPave;
2111   //
2112   const Handle(Geom_Curve)& aC3D=aIC.Curve();
2113   GeomAPI_ProjectPointOnCurve& aProjPT = myContext->ProjPT(aC3D);
2114   //
2115   TColStd_MapIteratorOfMapOfInteger aItMI;
2116   aItMI.Initialize(aMV);
2117   for (; aItMI.More(); aItMI.Next()) {
2118     nV = aItMI.Value();
2119     const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&myDS->Shape(nV)));
2120     gp_Pnt aPV = BRep_Tool::Pnt(aV);
2121     aProjPT.Perform(aPV);
2122     Standard_Integer aNbPoints = aProjPT.NbPoints();
2123     if (aNbPoints) {
2124       aDist = aProjPT.LowerDistance();
2125       PutPaveOnCurve(nV, aDist, aNC, aMI, aMVTol, aDMVLV);
2126     }
2127   }
2128 }
2129
2130 //=======================================================================
2131 //function : PutStickPavesOnCurve
2132 //purpose  :
2133 //=======================================================================
2134   void BOPAlgo_PaveFiller::PutStickPavesOnCurve
2135   (const TopoDS_Face& aF1,
2136    const TopoDS_Face& aF2,
2137    const TColStd_MapOfInteger& aMI,
2138    BOPDS_Curve& aNC,
2139    const TColStd_MapOfInteger& aMVStick,
2140    TColStd_DataMapOfIntegerReal& aMVTol,
2141    TColStd_DataMapOfIntegerListOfInteger& aDMVLV)
2142 {
2143   // Get numbers of vertices assigned to the ends of the curve
2144   Standard_Integer aBndNV[2];
2145   getBoundPaves(myDS, aNC, aBndNV);
2146   if (aBndNV[0] >= 0 && aBndNV[1] >= 0)
2147   {
2148     // both curve ends already have assigned vertices
2149     return;
2150   }
2151   TColStd_MapOfInteger aMV;
2152   aMV.Assign(aMVStick);
2153   RemoveUsedVertices(aNC, aMV);
2154   //
2155   if (!aMV.Extent()) {
2156     return;
2157   }
2158   //
2159   Handle(Geom_Surface) aS1=BRep_Tool::Surface(aF1);
2160   Handle(Geom_Surface) aS2=BRep_Tool::Surface(aF2);
2161   //
2162   const IntTools_Curve& aIC=aNC.Curve();
2163   //if (aTypeC==GeomAbs_BezierCurve || aTypeC==GeomAbs_BSplineCurve) {
2164   Handle(Geom2d_Curve) aC2D[2];
2165   //
2166   aC2D[0]=aIC.FirstCurve2d();
2167   aC2D[1]=aIC.SecondCurve2d();
2168   if (!aC2D[0].IsNull() && !aC2D[1].IsNull()) {
2169     Standard_Integer nV, m, n;
2170     Standard_Real aTC[2], aD, aD2, u, v, aDT2, aScPr, aDScPr;
2171     gp_Pnt aPC[2], aPV;
2172     gp_Dir aDN[2];
2173     gp_Pnt2d aP2D;
2174     TColStd_MapIteratorOfMapOfInteger aItMI, aItMI1;
2175     //
2176     aDT2=2e-7;     // the rich criteria
2177     aDScPr=5.e-9;  // the creasing criteria
2178     aIC.Bounds(aTC[0], aTC[1], aPC[0], aPC[1]);
2179     //
2180     aItMI.Initialize(aMV);
2181     for (; aItMI.More(); aItMI.Next()) {
2182       nV = aItMI.Value();
2183       const TopoDS_Vertex& aV=*((TopoDS_Vertex*)&myDS->Shape(nV));
2184       aPV=BRep_Tool::Pnt(aV);
2185       //
2186       for (m=0; m<2; ++m) {
2187         if (aBndNV[m] >= 0)
2188           continue;
2189         aD2=aPC[m].SquareDistance(aPV);
2190         if (aD2>aDT2) {// no rich
2191           continue;
2192         }
2193         //
2194         for (n=0; n<2; ++n) {
2195           Handle(Geom_Surface)& aS=(!n)? aS1 : aS2;
2196           aC2D[n]->D0(aTC[m], aP2D);
2197           aP2D.Coord(u, v);
2198           BOPTools_AlgoTools3D::GetNormalToSurface(aS, u, v, aDN[n]);
2199         }
2200         //
2201         aScPr=aDN[0]*aDN[1];
2202         if (aScPr<0.) {
2203           aScPr=-aScPr;
2204         }
2205         aScPr=1.-aScPr;
2206         //
2207         if (aScPr>aDScPr) {
2208           continue;
2209         }
2210         //
2211         // The intersection curve aIC is vanishing curve (the crease)
2212         aD=sqrt(aD2);
2213         //
2214         PutPaveOnCurve(nV, aD, aNC, aMI, aMVTol, aDMVLV);
2215       }
2216     }//for (jVU=1; jVU=aNbVU; ++jVU) {
2217   }
2218 }
2219
2220 //=======================================================================
2221 //function : GetStickVertices
2222 //purpose  :
2223 //=======================================================================
2224 void BOPAlgo_PaveFiller::GetStickVertices(const Standard_Integer nF1,
2225                                           const Standard_Integer nF2,
2226                                           TColStd_MapOfInteger& aMVStick,
2227                                           TColStd_MapOfInteger& aMVEF,
2228                                           TColStd_MapOfInteger& aMI)
2229 {
2230   Standard_Integer nS1, nS2, nVNew, aTypeInt, i;
2231   //
2232   BOPDS_VectorOfInterfVV& aVVs=myDS->InterfVV();
2233   BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
2234   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
2235   BOPDS_VectorOfInterfVF& aVFs=myDS->InterfVF();
2236   BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
2237   //
2238   Standard_Integer aNbLines[5] = {
2239     aVVs.Length(), aVEs.Length(), aEEs.Length(),
2240     aVFs.Length(), aEFs.Length()
2241     };
2242   //collect indices of all shapes from nF1 and nF2.
2243   aMI.Clear();
2244   GetFullShapeMap(nF1, aMI);
2245   GetFullShapeMap(nF2, aMI);
2246   //
2247   //collect VV, VE, EE, VF interferences
2248   for (aTypeInt = 0; aTypeInt < 4; ++aTypeInt) {
2249     for (i = 0; i < aNbLines[aTypeInt]; ++i) {
2250       BOPDS_Interf* aInt = (aTypeInt==0) ? (BOPDS_Interf*)(&aVVs(i)) :
2251         ((aTypeInt==1) ? (BOPDS_Interf*)(&aVEs(i)) :
2252          ((aTypeInt==2) ? (BOPDS_Interf*)(&aEEs(i)) :
2253           (BOPDS_Interf*)(&aVFs(i))));
2254       if (aInt->HasIndexNew()) {
2255         aInt->Indices(nS1, nS2);
2256         if(aMI.Contains(nS1) && aMI.Contains(nS2)) {
2257           nVNew = aInt->IndexNew();
2258           aMVStick.Add(nVNew);
2259         }
2260       }
2261     }
2262   }
2263   //collect EF interferences
2264   for (i = 0; i < aNbLines[4]; ++i) {
2265     const BOPDS_InterfEF& aInt = aEFs(i);
2266     if (aInt.HasIndexNew()) {
2267       aInt.Indices(nS1, nS2);
2268       if(aMI.Contains(nS1) && aMI.Contains(nS2)) {
2269         nVNew = aInt.IndexNew();
2270         aMVStick.Add(nVNew);
2271         aMVEF.Add(nVNew);
2272       }
2273     }
2274   }
2275 }
2276
2277 //=======================================================================
2278 // function: GetFullShapeMap
2279 // purpose:
2280 //=======================================================================
2281 void BOPAlgo_PaveFiller::GetFullShapeMap(const Standard_Integer nF,
2282                                          TColStd_MapOfInteger& aMI)
2283 {
2284   TColStd_ListIteratorOfListOfInteger aIt;
2285   Standard_Integer nS;
2286   //
2287   const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nF);
2288   const TColStd_ListOfInteger& aLI = aSI.SubShapes();
2289   //
2290   aMI.Add(nF);
2291   aIt.Initialize(aLI);
2292   for (; aIt.More(); aIt.Next()) {
2293     nS = aIt.Value();
2294     aMI.Add(nS);
2295   }
2296 }
2297
2298 //=======================================================================
2299 // function: RemoveUsedVertices
2300 // purpose:
2301 //=======================================================================
2302 void BOPAlgo_PaveFiller::RemoveUsedVertices(const BOPDS_Curve& aNC,
2303                                             TColStd_MapOfInteger& aMV)
2304 {
2305   if (aMV.IsEmpty())
2306     return;
2307
2308   const BOPDS_ListOfPaveBlock& aLPBC = aNC.PaveBlocks();
2309   BOPDS_ListIteratorOfListOfPaveBlock itPB(aLPBC);
2310   for (; itPB.More(); itPB.Next())
2311   {
2312     const Handle(BOPDS_PaveBlock)& aPB = itPB.Value();
2313     const BOPDS_ListOfPave& aLP = aPB->ExtPaves();
2314     BOPDS_ListIteratorOfListOfPave itLP(aLP);
2315     for (; itLP.More(); itLP.Next())
2316       aMV.Remove(itLP.Value().Index());
2317
2318     aMV.Remove(aPB->Pave1().Index());
2319     aMV.Remove(aPB->Pave2().Index());
2320   }
2321 }
2322
2323 //=======================================================================
2324 //function : PutPaveOnCurve
2325 //purpose  :
2326 //=======================================================================
2327 void BOPAlgo_PaveFiller::PutPaveOnCurve
2328   (const Standard_Integer nV,
2329    const Standard_Real aTolR3D,
2330    const BOPDS_Curve& aNC,
2331    const TColStd_MapOfInteger& aMI,
2332    TColStd_DataMapOfIntegerReal& aMVTol,
2333    TColStd_DataMapOfIntegerListOfInteger& aDMVLV,
2334    const Standard_Integer iCheckExtend)
2335 {
2336   Standard_Boolean bIsVertexOnLine;
2337   Standard_Real aT;
2338   //
2339   const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&myDS->Shape(nV)));
2340   const Handle(BOPDS_PaveBlock)& aPB = aNC.PaveBlocks().First();
2341   const IntTools_Curve& aIC = aNC.Curve();
2342   //
2343   Standard_Real aTolV = (aMVTol.IsBound(nV) ? aMVTol(nV) : BRep_Tool::Tolerance(aV));
2344
2345   bIsVertexOnLine = myContext->IsVertexOnLine(aV, aTolV, aIC, aTolR3D + myFuzzyValue, aT);
2346   if (!bIsVertexOnLine && iCheckExtend && !myVertsToAvoidExtension.Contains(nV))
2347   {
2348     Standard_Real anExtraTol = aTolV;
2349     if (ExtendedTolerance(nV, aMI, anExtraTol, iCheckExtend))
2350     {
2351       bIsVertexOnLine = myContext->IsVertexOnLine(aV, anExtraTol, aIC, aTolR3D + myFuzzyValue, aT);
2352       if (bIsVertexOnLine)
2353       {
2354         gp_Pnt aPOnC;
2355         aIC.D0(aT, aPOnC);
2356         aTolV = aPOnC.Distance(BRep_Tool::Pnt(aV));
2357       }
2358     }
2359   }
2360   //
2361   if (bIsVertexOnLine) {
2362     // check if aPB contains the parameter aT
2363     Standard_Boolean bExist;
2364     Standard_Integer nVUsed;
2365     Standard_Real aPTol, aDTol;
2366     //
2367     aDTol = 1.e-12;
2368     //
2369     GeomAdaptor_Curve aGAC(aIC.Curve());
2370     aPTol = aGAC.Resolution(Max(aTolR3D, aTolV));
2371     //
2372     bExist = aPB->ContainsParameter(aT, aPTol, nVUsed);
2373     if (bExist) {
2374       // use existing pave
2375       TColStd_ListOfInteger* pList = aDMVLV.ChangeSeek(nVUsed);
2376       if (!pList) {
2377         pList = aDMVLV.Bound(nVUsed, TColStd_ListOfInteger());
2378         pList->Append(nVUsed);
2379         if (!aMVTol.IsBound(nVUsed)) {
2380           const TopoDS_Vertex& aVUsed = (*(TopoDS_Vertex *)(&myDS->Shape(nVUsed)));
2381           aTolV = BRep_Tool::Tolerance(aVUsed);
2382           aMVTol.Bind(nVUsed, aTolV);
2383         }
2384       }
2385       // avoid repeated elements in the list
2386       TColStd_ListIteratorOfListOfInteger aItLI(*pList);
2387       for (; aItLI.More(); aItLI.Next()) {
2388         if (aItLI.Value() == nV) {
2389           break;
2390         }
2391       }
2392       if (!aItLI.More()) {
2393         pList->Append(nV);
2394       }
2395       // save initial tolerance for the vertex
2396       if (!aMVTol.IsBound(nV)) {
2397         aTolV = BRep_Tool::Tolerance(aV);
2398         aMVTol.Bind(nV, aTolV);
2399       }
2400     }
2401     else {
2402       // add new pave
2403       BOPDS_Pave aPave;
2404       aPave.SetIndex(nV);
2405       aPave.SetParameter(aT);
2406       aPB->AppendExtPave(aPave);
2407       //
2408       gp_Pnt aP1 = aGAC.Value(aT);
2409       aTolV = BRep_Tool::Tolerance(aV);
2410       gp_Pnt aP2 = BRep_Tool::Pnt(aV);
2411       Standard_Real aDist = aP1.Distance(aP2);
2412       if (aDist > aTolV) {
2413         BRep_Builder().UpdateVertex(aV, aDist + aDTol);
2414         //
2415         if (!aMVTol.IsBound(nV)) {
2416           aMVTol.Bind(nV, aTolV);
2417         }
2418         //
2419         BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(nV);
2420         Bnd_Box& aBoxDS=aSIDS.ChangeBox();
2421         BRepBndLib::Add(aV, aBoxDS);
2422         aBoxDS.SetGap(aBoxDS.GetGap() + Precision::Confusion());
2423       }
2424     }
2425   }
2426 }
2427
2428 //=======================================================================
2429 //function : ProcessExistingPaveBlocks
2430 //purpose  :
2431 //=======================================================================
2432 void BOPAlgo_PaveFiller::ProcessExistingPaveBlocks
2433     (const Standard_Integer theInt,
2434      const Standard_Integer nF1,
2435      const Standard_Integer nF2,
2436      const BOPDS_IndexedMapOfPaveBlock& aMPBOnIn,
2437      const TColStd_DataMapOfIntegerListOfInteger& aDMBV,
2438      BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& aMSCPB,
2439      TopTools_DataMapOfShapeInteger& aMVI,
2440      BOPAlgo_DataMapOfPaveBlockListOfInteger& thePBFacesMap,
2441      BOPDS_MapOfPaveBlock& aMPB)
2442 {
2443   if (aDMBV.IsEmpty()) {
2444     return;
2445   }
2446   //
2447   Standard_Real aT, dummy;
2448   Standard_Integer i, nV, nE, iC, aNbPB, iFlag;
2449   TColStd_ListIteratorOfListOfInteger aItLI;
2450   TColStd_DataMapIteratorOfDataMapOfIntegerListOfInteger aItBV;
2451   //
2452   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
2453   BOPDS_InterfFF& aFF = aFFs(theInt);
2454   BOPDS_VectorOfCurve& aVC = aFF.ChangeCurves();
2455   //
2456   const BOPDS_FaceInfo& aFI1 = myDS->FaceInfo(nF1);
2457   const BOPDS_FaceInfo& aFI2 = myDS->FaceInfo(nF2);
2458   //
2459   aNbPB = aMPBOnIn.Extent();
2460   //
2461   aItBV.Initialize(aDMBV);
2462   for (; aItBV.More(); aItBV.Next()) {
2463     iC = aItBV.Key();
2464     const TColStd_ListOfInteger& aLBV = aItBV.Value();
2465     //
2466     BOPDS_Curve& aNC = aVC.ChangeValue(iC);
2467     BOPDS_ListOfPaveBlock& aLPBC = aNC.ChangePaveBlocks();
2468     //
2469     aItLI.Initialize(aLBV);
2470     for (; aItLI.More(); aItLI.Next()) {
2471       nV = aItLI.Value();
2472       const BOPDS_ShapeInfo& aSIV=myDS->ShapeInfo(nV);
2473       const Bnd_Box& aBoxV=aSIV.Box();
2474       const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&aSIV.Shape();
2475       if (!aMVI.IsBound(aV)) {
2476         continue;
2477       }
2478       //
2479       for (i = 1; i <= aNbPB; ++i) {
2480         const Handle(BOPDS_PaveBlock)& aPB = aMPBOnIn(i);
2481         if (aPB->Pave1().Index() == nV || aPB->Pave2().Index() == nV) {
2482           continue;
2483         }
2484         //
2485         if (aMPB.Contains(aPB)) {
2486           continue;
2487         }
2488         if (myDS->ShapeInfo(aPB->OriginalEdge()).HasFlag()) { // skip degenerated edges
2489           continue;
2490         }
2491         //
2492         nE = aPB->Edge();
2493         const BOPDS_ShapeInfo& aSIE = myDS->ShapeInfo(nE);
2494         const Bnd_Box& aBoxE = aSIE.Box();
2495         //
2496         if (aBoxV.IsOut(aBoxE)) {
2497           continue;
2498         }
2499         //
2500         const TopoDS_Edge& aE = *(TopoDS_Edge*)&aSIE.Shape();
2501         //
2502         iFlag = myContext->ComputeVE(aV, aE, aT, dummy, myFuzzyValue);
2503         if (!iFlag) {
2504           aMPB.Add(aPB);
2505           PreparePostTreatFF(theInt, iC, aPB, aMSCPB, aMVI, aLPBC);
2506
2507           // Add faces to PB
2508           Standard_Boolean bInF1 = (aFI1.PaveBlocksOn().Contains(aPB) ||
2509                                     aFI1.PaveBlocksIn().Contains(aPB));
2510           Standard_Boolean bInF2 = (aFI2.PaveBlocksOn().Contains(aPB) ||
2511                                     aFI2.PaveBlocksIn().Contains(aPB));
2512           if (!bInF1 || !bInF2)
2513           {
2514             // Face without pave block
2515             const Standard_Integer nF = bInF1 ? nF2 : nF1;
2516             TColStd_ListOfInteger* pFaces = thePBFacesMap.ChangeSeek(aPB);
2517             if (!pFaces)
2518               pFaces = thePBFacesMap.Bound(aPB, TColStd_ListOfInteger());
2519             // List is expected to be short, so we allow the check here
2520             if (pFaces->IsEmpty() || !pFaces->Contains(nF))
2521               pFaces->Append(nF);
2522           }
2523         }
2524       }
2525     }
2526   }
2527 }
2528 //=======================================================================
2529 //function : UpdateExistingPaveBlocks
2530 //purpose  :
2531 //=======================================================================
2532 void BOPAlgo_PaveFiller::UpdateExistingPaveBlocks
2533   (const Handle(BOPDS_PaveBlock)& aPBf,
2534    BOPDS_ListOfPaveBlock& aLPB,
2535    const BOPAlgo_DataMapOfPaveBlockListOfInteger& thePBFacesMap)
2536 {
2537   if (!aLPB.Extent()) {
2538     return;
2539   }
2540   //
2541   Standard_Integer nE;
2542   Standard_Boolean bCB;
2543   Handle(BOPDS_PaveBlock) aPB, aPB1, aPB2, aPB2n;
2544   Handle(BOPDS_CommonBlock) aCB;
2545   BOPDS_ListIteratorOfListOfPaveBlock aIt, aIt1, aIt2;
2546   //
2547   // 1. Remove old pave blocks
2548   const Handle(BOPDS_CommonBlock)& aCB1 = myDS->CommonBlock(aPBf);
2549   bCB = !aCB1.IsNull();
2550   BOPDS_ListOfPaveBlock aLPB1;
2551   //
2552   if (bCB) {
2553     aLPB1.Assign(aCB1->PaveBlocks());
2554   } else {
2555     aLPB1.Append(aPBf);
2556   }
2557   aIt1.Initialize(aLPB1);
2558   for (; aIt1.More(); aIt1.Next()) {
2559     aPB1 = aIt1.Value();
2560     nE = aPB1->OriginalEdge();
2561     //
2562     BOPDS_ListOfPaveBlock& aLPB2 = myDS->ChangePaveBlocks(nE);
2563     aIt2.Initialize(aLPB2);
2564     for (; aIt2.More(); aIt2.Next()) {
2565       aPB2 = aIt2.Value();
2566       if (aPB1 == aPB2) {
2567         aLPB2.Remove(aIt2);
2568         break;
2569       }
2570     }
2571   }
2572   //
2573   // 2. Update pave blocks
2574   if (bCB) {
2575     // Create new common blocks
2576     BOPDS_ListOfPaveBlock aLPBNew;
2577     const TColStd_ListOfInteger& aFaces = aCB1->Faces();
2578     aIt.Initialize(aLPB);
2579     for (; aIt.More(); aIt.Next()) {
2580       const Handle(BOPDS_PaveBlock)& aPBValue = aIt.Value();
2581       BOPDS_Pave aPBValuePaves[2] = {aPBValue->Pave1(), aPBValue->Pave2()};
2582       //
2583       aCB = new BOPDS_CommonBlock;
2584       aIt1.Initialize(aLPB1);
2585       for (; aIt1.More(); aIt1.Next()) {
2586         aPB2 = aIt1.Value();
2587         nE = aPB2->OriginalEdge();
2588         //
2589         // Create new pave block
2590         aPB2n = new BOPDS_PaveBlock;
2591         if (aPBValue->OriginalEdge() == nE) {
2592           aPB2n->SetPave1(aPBValuePaves[0]);
2593           aPB2n->SetPave2(aPBValuePaves[1]);
2594         }
2595         else {
2596           // For the different original edge compute the parameters of paves
2597           BOPDS_Pave aPave[2];
2598           for (Standard_Integer i = 0; i < 2; ++i) {
2599             Standard_Integer nV = aPBValuePaves[i].Index();
2600             aPave[i].SetIndex(nV);
2601             if (nV == aPB2->Pave1().Index()) {
2602               aPave[i].SetParameter(aPB2->Pave1().Parameter());
2603             }
2604             else if (nV == aPB2->Pave2().Index()) {
2605               aPave[i].SetParameter(aPB2->Pave2().Parameter());
2606             }
2607             else {
2608               // Compute the parameter by projecting the point
2609               const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV));
2610               const TopoDS_Edge& aEOr = TopoDS::Edge(myDS->Shape(nE));
2611               Standard_Real aTOut, aDist;
2612               Standard_Integer iErr = myContext->ComputeVE(aV, aEOr, aTOut, aDist, myFuzzyValue);
2613               if (!iErr) {
2614                 aPave[i].SetParameter(aTOut);
2615               }
2616               else {
2617                 // Unable to project - set the parameter of the closest boundary
2618                 const TopoDS_Vertex& aV1 = TopoDS::Vertex(myDS->Shape(aPB2->Pave1().Index()));
2619                 const TopoDS_Vertex& aV2 = TopoDS::Vertex(myDS->Shape(aPB2->Pave2().Index()));
2620                 //
2621                 gp_Pnt aP = BRep_Tool::Pnt(aV);
2622                 gp_Pnt aP1 = BRep_Tool::Pnt(aV1);
2623                 gp_Pnt aP2 = BRep_Tool::Pnt(aV2);
2624                 //
2625                 Standard_Real aDist1 = aP.SquareDistance(aP1);
2626                 Standard_Real aDist2 = aP.SquareDistance(aP2);
2627                 //
2628                 aPave[i].SetParameter(aDist1 < aDist2 ? aPB2->Pave1().Parameter() : aPB2->Pave2().Parameter());
2629               }
2630             }
2631           }
2632           //
2633           if (aPave[1].Parameter() < aPave[0].Parameter()) {
2634             BOPDS_Pave aPaveTmp = aPave[0];
2635             aPave[0] = aPave[1];
2636             aPave[1] = aPaveTmp;
2637           }
2638           //
2639           aPB2n->SetPave1(aPave[0]);
2640           aPB2n->SetPave2(aPave[1]);
2641         }
2642         //
2643         aPB2n->SetEdge(aPBValue->Edge());
2644         aPB2n->SetOriginalEdge(nE);
2645         aCB->AddPaveBlock(aPB2n);
2646         myDS->SetCommonBlock(aPB2n, aCB);
2647         myDS->ChangePaveBlocks(nE).Append(aPB2n);
2648       }
2649       aCB->SetFaces(aFaces);
2650       //
2651       const Handle(BOPDS_PaveBlock)& aPBNew = aCB->PaveBlocks().First();
2652       aLPBNew.Append(aPBNew);
2653     }
2654     //
2655     aLPB = aLPBNew;
2656   }
2657   else {
2658     nE = aPBf->OriginalEdge();
2659     BOPDS_ListOfPaveBlock& aLPBE = myDS->ChangePaveBlocks(nE);
2660     aIt.Initialize(aLPB);
2661     for (; aIt.More(); aIt.Next()) {
2662       aPB = aIt.Value();
2663       aLPBE.Append(aPB);
2664     }
2665   }
2666
2667   // Try to project the edge on the faces
2668   const TColStd_ListOfInteger* pLFaces = thePBFacesMap.Seek(aPBf);
2669   if (!pLFaces)
2670     return;
2671   TColStd_ListIteratorOfListOfInteger itLF(*pLFaces);
2672   for (; itLF.More(); itLF.Next())
2673   {
2674     const Standard_Integer nF = itLF.Value();
2675     BOPDS_FaceInfo& aFI = myDS->ChangeFaceInfo(nF);
2676     const TopoDS_Face& aF = TopoDS::Face(myDS->Shape(nF));
2677
2678     aIt.Initialize(aLPB);
2679     for (; aIt.More(); aIt.Next())
2680     {
2681       aPB = aIt.ChangeValue();
2682       if (aFI.PaveBlocksOn().Contains(aPB) || aFI.PaveBlocksIn().Contains(aPB))
2683         continue;
2684
2685       const TopoDS_Edge& aE = *(TopoDS_Edge*)&myDS->Shape(aPB->Edge());
2686       //
2687       IntTools_EdgeFace anEF;
2688       anEF.SetEdge(aE);
2689       anEF.SetFace(aF);
2690       anEF.SetFuzzyValue(myFuzzyValue);
2691       anEF.SetRange(aPB->Pave1().Parameter(), aPB->Pave2().Parameter());
2692       anEF.SetContext(myContext);
2693       anEF.Perform();
2694       //
2695       const IntTools_SequenceOfCommonPrts& aCPrts = anEF.CommonParts();
2696       Standard_Boolean bCoincide = (aCPrts.Length() == 1 && aCPrts(1).Type() == TopAbs_EDGE);
2697       if (bCoincide)
2698       {
2699         aCB = myDS->CommonBlock(aPB);
2700         if (aCB.IsNull())
2701         {
2702           aCB = new BOPDS_CommonBlock;
2703           aCB->AddPaveBlock(aPB);
2704           myDS->SetCommonBlock(aPB, aCB);
2705         }
2706         aCB->AddFace(nF);
2707         aFI.ChangePaveBlocksIn().Add(aPB);
2708       }
2709     }
2710   }
2711 }
2712
2713 //=======================================================================
2714 // function: PutClosingPaveOnCurve
2715 // purpose:
2716 //=======================================================================
2717 void BOPAlgo_PaveFiller::PutClosingPaveOnCurve(BOPDS_Curve& aNC)
2718 {
2719   const IntTools_Curve& aIC = aNC.Curve();
2720   const Handle(Geom_Curve)& aC3D = aIC.Curve();
2721   // check 3d curve
2722   if (aC3D.IsNull())
2723     return;
2724
2725   // check bounds
2726   if (!aIC.HasBounds())
2727     return;
2728
2729   // check closeness
2730   Standard_Real aT[2];
2731   gp_Pnt aP[2];
2732   aIC.Bounds(aT[0], aT[1], aP[0], aP[1]);
2733
2734   // Find the pave which has been put at one of the ends
2735   BOPDS_Pave aPave;
2736   // Index of the vertex put at one of the ends
2737   Standard_Integer nV = -1;
2738   // Keep the opposite parameter
2739   Standard_Real aTOp = 0.;
2740   // Keep the opposite bounding point
2741   gp_Pnt aPOp;
2742
2743   Handle(BOPDS_PaveBlock)& aPB = aNC.ChangePaveBlock1();
2744   BOPDS_ListOfPave& aLP = aPB->ChangeExtPaves();
2745   BOPDS_ListIteratorOfListOfPave aItLP(aLP);
2746   for (; aItLP.More() && (nV < 0); aItLP.Next())
2747   {
2748     aPave = aItLP.Value();
2749     Standard_Real aTC = aPave.Parameter();
2750     for (Standard_Integer j = 0; j < 2; ++j)
2751     {
2752       if (Abs(aTC - aT[j]) < Precision::PConfusion())
2753       {
2754         nV = aPave.Index();
2755         aTOp = (!j) ? aT[1] : aT[0];
2756         aPOp = (!j) ? aP[1] : aP[0];
2757         break;
2758       }
2759     }
2760   }
2761
2762   if (nV < 0)
2763     // No paves on the bounds of the curve
2764     return;
2765
2766   // Check if the curve is closed using the tolerance
2767   // of found vertex
2768   const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV));
2769   Standard_Real aTolV = BRep_Tool::Tolerance(aV);
2770   gp_Pnt aPV = BRep_Tool::Pnt(aV);
2771   // Tolerance for the point on the curve
2772   Standard_Real aTolP = Max(aNC.Tolerance(), aNC.TangentialTolerance());
2773   aTolP += Precision::Confusion();
2774
2775   const Standard_Real aDistVP = aPV.Distance(aPOp);
2776   if (aDistVP > aTolV + aTolP)
2777   {
2778     // Curve is not closed
2779     return;
2780   }
2781
2782   if (aDistVP > aTolV)
2783   {
2784     Standard_Integer nVn = UpdateVertex(nV, aDistVP);
2785     if (nVn != nV)
2786     {
2787       aPave.SetIndex(nVn);
2788       nV = nVn;
2789     }
2790     aTolV = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV)));
2791   }
2792
2793   // Check if there will be valid range on the curve
2794   Standard_Real aFirst, aLast;
2795   if (!BRepLib::FindValidRange(GeomAdaptor_Curve(aIC.Curve()), aIC.Tolerance(),
2796                                aT[0], aP[0], aTolV,
2797                                aT[1], aP[1], aTolV,
2798                                aFirst, aLast))
2799   {
2800     // No valid range
2801     return;
2802   }
2803
2804   // Add closing pave to the curve
2805   BOPDS_Pave aNewPave;
2806   aNewPave.SetIndex(nV);
2807   aNewPave.SetParameter(aTOp);
2808   aLP.Append(aNewPave);
2809 }
2810
2811 //=======================================================================
2812 //function : PreparePostTreatFF
2813 //purpose  :
2814 //=======================================================================
2815 void BOPAlgo_PaveFiller::PreparePostTreatFF
2816     (const Standard_Integer aInt,
2817      const Standard_Integer aCur,
2818      const Handle(BOPDS_PaveBlock)& aPB,
2819      BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& aMSCPB,
2820      TopTools_DataMapOfShapeInteger& aMVI,
2821      BOPDS_ListOfPaveBlock& aLPBC)
2822 {
2823   Standard_Integer nV1, nV2;
2824   //
2825   aLPBC.Append(aPB);
2826   //
2827   aPB->Indices(nV1, nV2);
2828   const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1)));
2829   const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2)));
2830   const TopoDS_Edge& aE = *(TopoDS_Edge*)&myDS->Shape(aPB->Edge());
2831   // Keep info for post treatment
2832   BOPDS_CoupleOfPaveBlocks aCPB;
2833   aCPB.SetIndexInterf(aInt);
2834   aCPB.SetIndex(aCur);
2835   aCPB.SetPaveBlock1(aPB);
2836   //
2837   aMSCPB.Add(aE, aCPB);
2838   aMVI.Bind(aV1, nV1);
2839   aMVI.Bind(aV2, nV2);
2840 }
2841
2842 //=======================================================================
2843 //function : CheckPlanes
2844 //purpose  :
2845 //=======================================================================
2846 Standard_Boolean BOPAlgo_PaveFiller::CheckPlanes
2847   (const Standard_Integer nF1,
2848    const Standard_Integer nF2)const
2849 {
2850   Standard_Boolean bToIntersect;
2851   Standard_Integer i, nV2, iCnt;
2852   TColStd_MapIteratorOfMapOfInteger aIt;
2853   //
2854   bToIntersect=Standard_False;
2855   //
2856   const BOPDS_FaceInfo& aFI1=myDS->ChangeFaceInfo(nF1);
2857   const BOPDS_FaceInfo& aFI2=myDS->ChangeFaceInfo(nF2);
2858   //
2859   const TColStd_MapOfInteger& aMVIn1=aFI1.VerticesIn();
2860   const TColStd_MapOfInteger& aMVOn1=aFI1.VerticesOn();
2861   //
2862   iCnt=0;
2863   for (i=0; (i<2 && !bToIntersect); ++i) {
2864     const TColStd_MapOfInteger& aMV2=(!i) ? aFI2.VerticesIn()
2865       : aFI2.VerticesOn();
2866     //
2867     aIt.Initialize(aMV2);
2868     for (; aIt.More(); aIt.Next()) {
2869       nV2=aIt.Value();
2870       if (aMVIn1.Contains(nV2) || aMVOn1.Contains(nV2)) {
2871         ++iCnt;
2872         if (iCnt>1) {
2873           bToIntersect=!bToIntersect;
2874           break;
2875         }
2876       }
2877     }
2878   }
2879   //
2880   return bToIntersect;
2881 }
2882 //=======================================================================
2883 //function : UpdatePaveBlocks
2884 //purpose  :
2885 //=======================================================================
2886 void BOPAlgo_PaveFiller::UpdatePaveBlocks
2887 (const TColStd_DataMapOfIntegerInteger& aDMNewSD)
2888 {
2889   if (aDMNewSD.IsEmpty()) {
2890     return;
2891   }
2892   //
2893   Standard_Integer nSp, aNbPBP, nV[2], i, j;
2894   Standard_Real aT[2];
2895   Standard_Boolean bCB, bRebuild;
2896   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
2897   BOPDS_MapOfPaveBlock aMPB;
2898   TColStd_MapOfInteger aMicroEdges;
2899   //
2900   BOPDS_ListOfPaveBlock anAllPBs;
2901
2902   // Get pave blocks of section edges
2903   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
2904   Standard_Integer aNbFF = aFFs.Length();
2905   for (i = 0; i < aNbFF; ++i)
2906   {
2907     const BOPDS_InterfFF& aFF = aFFs(i);
2908     const BOPDS_VectorOfCurve& aVNC = aFF.Curves();
2909     Standard_Integer aNbC = aVNC.Length();
2910     for (j = 0; j < aNbC; ++j)
2911     {
2912       const BOPDS_Curve& aNC = aVNC(j);
2913       const BOPDS_ListOfPaveBlock& aLPBC = aNC.PaveBlocks();
2914       aItPB.Initialize(aLPBC);
2915       for (; aItPB.More(); aItPB.Next())
2916         anAllPBs.Append(aItPB.Value());
2917     }
2918   }
2919
2920   // Get pave blocks from the pool
2921   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
2922   aNbPBP = aPBP.Length();
2923   for (i = 0; i < aNbPBP; ++i) {
2924     BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
2925     aItPB.Initialize(aLPB);
2926     for (; aItPB.More(); aItPB.Next())
2927       anAllPBs.Append(aItPB.Value());
2928   }
2929
2930   // Process all pave blocks
2931   aItPB.Initialize(anAllPBs);
2932   for (; aItPB.More(); aItPB.Next())
2933   {
2934     Handle(BOPDS_PaveBlock) aPB = aItPB.Value();
2935     const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(aPB);
2936     bCB = !aCB.IsNull();
2937     if (bCB) {
2938       aPB = aCB->PaveBlock1();
2939     }
2940     //
2941     if (aMPB.Add(aPB)) {
2942       bRebuild = Standard_False;
2943       aPB->Indices(nV[0], nV[1]);
2944       aPB->Range(aT[0], aT[1]);
2945       // remember the fact if the edge had different vertices before substitution
2946       Standard_Boolean wasRegularEdge = (nV[0] != nV[1]);
2947       //
2948       for (j = 0; j < 2; ++j) {
2949         if (aDMNewSD.IsBound(nV[j])) {
2950           BOPDS_Pave aPave;
2951           //
2952           nV[j] = aDMNewSD.Find(nV[j]);
2953           aPave.SetIndex(nV[j]);
2954           aPave.SetParameter(aT[j]);
2955           //
2956           bRebuild = Standard_True;
2957           if (!j) {
2958             aPB->SetPave1(aPave);
2959           }
2960           else {
2961             aPB->SetPave2(aPave);
2962           }
2963         }
2964       }
2965       //
2966       if (bRebuild) {
2967         Standard_Integer nE = aPB->Edge();
2968         // Check if the Pave Block has the edge set
2969         if (nE < 0) {
2970           // untouched edge
2971           nE = aPB->OriginalEdge();
2972         }
2973         Standard_Boolean isDegEdge = myDS->ShapeInfo(nE).HasFlag();
2974         if (wasRegularEdge && !isDegEdge && nV[0] == nV[1]) {
2975           // now edge has the same vertex on both ends;
2976           // check if it is not a regular closed curve.
2977           FillShrunkData(aPB);
2978           if (!aPB->HasShrunkData())
2979           {
2980             // micro edge, so mark it for removal
2981             aMicroEdges.Add(nE);
2982             continue;
2983           }
2984         }
2985         nSp = SplitEdge(nE, nV[0], aT[0], nV[1], aT[1]);
2986         if (bCB)
2987           aCB->SetEdge(nSp);
2988         else
2989           aPB->SetEdge(nSp);
2990       }// if (bRebuild) {
2991     }// if (aMPB.Add(aPB)) {
2992   }// for (; aItPB.More(); aItPB.Next()) {
2993   aMPB.Clear();
2994
2995   if (aMicroEdges.Extent())
2996     RemovePaveBlocks(aMicroEdges);
2997 }
2998 //=======================================================================
2999 //function : RemovePaveBlocks
3000 //purpose  :
3001 //=======================================================================
3002 void BOPAlgo_PaveFiller::RemovePaveBlocks(const TColStd_MapOfInteger theEdges)
3003 {
3004   // Remove all pave blocks referring to input edges:
3005   //
3006   // 1. from the Pave Blocks Pool
3007   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
3008   Standard_Integer aNbPBP = aPBP.Length(), i;
3009   for (i = 0; i < aNbPBP; ++i) {
3010     BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
3011     //
3012     BOPDS_ListIteratorOfListOfPaveBlock aItPB(aLPB);
3013     while (aItPB.More()) {
3014       const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
3015       if (theEdges.Contains(aPB->Edge()))
3016         aLPB.Remove(aItPB);
3017       else
3018         aItPB.Next();
3019     }
3020   }
3021
3022   // 2. from section curves
3023   TColStd_MapOfInteger aMPassed;
3024   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
3025   Standard_Integer aNbFF = aFFs.Length(), j;
3026   for (i = 0; i < aNbFF; ++i) {
3027     BOPDS_InterfFF& aFF = aFFs(i);
3028     // remove from Section pave blocks
3029     BOPDS_VectorOfCurve& aVNC = aFF.ChangeCurves();
3030     Standard_Integer aNbC = aVNC.Length();
3031     for (j = 0; j < aNbC; ++j) {
3032       BOPDS_Curve& aNC = aVNC(j);
3033       BOPDS_ListOfPaveBlock& aLPB = aNC.ChangePaveBlocks();
3034       BOPDS_ListIteratorOfListOfPaveBlock aItPB(aLPB);
3035       while (aItPB.More()) {
3036         const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
3037         if (theEdges.Contains(aPB->Edge()))
3038           aLPB.Remove(aItPB);
3039         else
3040           aItPB.Next();
3041       }
3042     }
3043   }
3044
3045   // 3. From Face Info
3046   for (i = 0; i < myDS->NbSourceShapes(); ++i)
3047   {
3048     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
3049     if (aSI.ShapeType() != TopAbs_FACE)
3050       continue;
3051     if (!aSI.HasReference())
3052       continue;
3053
3054     BOPDS_FaceInfo& aFI = myDS->ChangeFaceInfo(i);
3055     BOPDS_IndexedMapOfPaveBlock* aIMPB[] = { &aFI.ChangePaveBlocksIn(),
3056                                              &aFI.ChangePaveBlocksOn(),
3057                                              &aFI.ChangePaveBlocksSc() };
3058     for (Standard_Integer k = 0; k < 3; k++)
3059     {
3060       Standard_Integer aNbPB = aIMPB[k]->Extent(), m;
3061       for (m = 1; m <= aNbPB; ++m)
3062       {
3063         const Handle(BOPDS_PaveBlock)& aPB = aIMPB[k]->FindKey(m);
3064         if (theEdges.Contains(aPB->Edge()))
3065           break;
3066       }
3067       if (m <= aNbPB)
3068       {
3069         BOPDS_IndexedMapOfPaveBlock aMPBCopy = *aIMPB[k];
3070         aIMPB[k]->Clear();
3071         for (m = 1; m <= aNbPB; ++m)
3072         {
3073           const Handle(BOPDS_PaveBlock)& aPB = aMPBCopy(m);
3074           if (!theEdges.Contains(aPB->Edge()))
3075             aIMPB[k]->Add(aPB);
3076         }
3077       }
3078     }
3079   }
3080 }
3081
3082 //=======================================================================
3083 //function : ToleranceFF
3084 //purpose  : Computes the TolFF according to the tolerance value and
3085 //           types of the faces.
3086 //=======================================================================
3087 Standard_Real ToleranceFF(const BRepAdaptor_Surface& aBAS1,
3088                           const BRepAdaptor_Surface& aBAS2)
3089 {
3090   Standard_Real aTol1 = aBAS1.Tolerance();
3091   Standard_Real aTol2 = aBAS2.Tolerance();
3092   Standard_Real aTolFF = Max(aTol1, aTol2);
3093   //
3094   Standard_Boolean isAna1, isAna2;
3095   isAna1 = (aBAS1.GetType() == GeomAbs_Plane ||
3096             aBAS1.GetType() == GeomAbs_Cylinder ||
3097             aBAS1.GetType() == GeomAbs_Cone ||
3098             aBAS1.GetType() == GeomAbs_Sphere ||
3099             aBAS1.GetType() == GeomAbs_Torus);
3100   //
3101   isAna2 = (aBAS2.GetType() == GeomAbs_Plane ||
3102             aBAS2.GetType() == GeomAbs_Cylinder ||
3103             aBAS2.GetType() == GeomAbs_Cone ||
3104             aBAS2.GetType() == GeomAbs_Sphere ||
3105             aBAS2.GetType() == GeomAbs_Torus);
3106   //
3107   if (!isAna1 || !isAna2) {
3108     aTolFF =  Max(aTolFF, 5.e-6);
3109   }
3110   return aTolFF;
3111 }
3112 //=======================================================================
3113 //function : UpdateBlocksWithSharedVertices
3114 //purpose  :
3115 //=======================================================================
3116 void BOPAlgo_PaveFiller::UpdateBlocksWithSharedVertices()
3117 {
3118   if (!myNonDestructive) {
3119     return;
3120   }
3121   //
3122   Standard_Integer aNbFF;
3123   //
3124   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
3125   aNbFF=aFFs.Length();
3126   if (!aNbFF) {
3127     return;
3128   }
3129   //
3130   Standard_Boolean bOnCurve, bHasShapeSD;
3131   Standard_Integer i, nF1, nF2, aNbC, j, nV, nVSD;
3132   Standard_Real aTolV;
3133   TColStd_MapOfInteger aMF;
3134   //
3135   for (i=0; i<aNbFF; ++i) {
3136     BOPDS_InterfFF& aFF=aFFs(i);
3137     //
3138     BOPDS_VectorOfCurve& aVC=aFF.ChangeCurves();
3139     aNbC=aVC.Length();
3140     if (!aNbC) {
3141       continue;
3142     }
3143     //
3144     aFF.Indices(nF1, nF2);
3145     //
3146     if (aMF.Add(nF1)) {
3147       myDS->UpdateFaceInfoOn(nF1);
3148     }
3149     if (aMF.Add(nF2)) {
3150       myDS->UpdateFaceInfoOn(nF2);
3151     }
3152     //
3153     // Collect old vertices that are shared for nF1, nF2 ->aMI;
3154     TColStd_MapOfInteger aMI;
3155     TColStd_MapIteratorOfMapOfInteger aItMI;
3156     //
3157     BOPDS_FaceInfo& aFI1=myDS->ChangeFaceInfo(nF1);
3158     BOPDS_FaceInfo& aFI2=myDS->ChangeFaceInfo(nF2);
3159     //
3160     const TColStd_MapOfInteger& aMVOn1=aFI1.VerticesOn();
3161     const TColStd_MapOfInteger& aMVIn1=aFI1.VerticesIn();
3162     const TColStd_MapOfInteger& aMVOn2=aFI2.VerticesOn();
3163     const TColStd_MapOfInteger& aMVIn2=aFI2.VerticesIn();
3164     //
3165     for (j=0; j<2; ++j) {
3166       const TColStd_MapOfInteger& aMV1=(!j) ? aMVOn1 : aMVIn1;
3167       aItMI.Initialize(aMV1);
3168       for (; aItMI.More(); aItMI.Next()) {
3169         nV=aItMI.Value();
3170         if (myDS->IsNewShape(nV)) {
3171           continue;
3172         }
3173         if (aMVOn2.Contains(nV) || aMVIn2.Contains(nV)) {
3174           aMI.Add(nV);
3175         }
3176       }
3177     }
3178     //
3179     // Try to put vertices aMI on curves
3180     for (j=0; j<aNbC; ++j) {
3181       BOPDS_Curve& aNC=aVC.ChangeValue(j);
3182       Standard_Real aTolR3D = Max(aNC.Tolerance(), aNC.TangentialTolerance());
3183       //
3184       aItMI.Initialize(aMI);
3185       for (; aItMI.More(); aItMI.Next()) {
3186         nV=aItMI.Value();
3187         //
3188         bHasShapeSD=myDS->HasShapeSD(nV, nVSD);
3189         if (bHasShapeSD) {
3190           continue;
3191         }
3192         //
3193         bOnCurve=EstimatePaveOnCurve(nV, aNC, aTolR3D);
3194         if (!bOnCurve) {
3195           continue;
3196         }
3197         //
3198         const TopoDS_Vertex& aV=*((TopoDS_Vertex *)&myDS->Shape(nV));
3199         aTolV=BRep_Tool::Tolerance(aV);
3200         //
3201         UpdateVertex(nV, aTolV);
3202       }
3203     }//for (j=0; j<aNbC; ++j) {
3204   }//for (i=0; i<aNbFF; ++i) {
3205   //
3206   UpdateCommonBlocksWithSDVertices();
3207 }
3208 //=======================================================================
3209 //function : EstimatePaveOnCurve
3210 //purpose  :
3211 //=======================================================================
3212 Standard_Boolean BOPAlgo_PaveFiller::EstimatePaveOnCurve
3213   (const Standard_Integer nV,
3214    const BOPDS_Curve& aNC,
3215    const Standard_Real aTolR3D)
3216 {
3217   Standard_Boolean bIsVertexOnLine;
3218   Standard_Real aT;
3219   //
3220   const TopoDS_Vertex& aV=*((TopoDS_Vertex *)&myDS->Shape(nV));
3221   const IntTools_Curve& aIC=aNC.Curve();
3222   //
3223   bIsVertexOnLine=myContext->IsVertexOnLine(aV, aIC, aTolR3D, aT);
3224   return bIsVertexOnLine;
3225 }
3226
3227 //=======================================================================
3228 //function : CorrectToleranceOfSE
3229 //purpose  :
3230 //=======================================================================
3231 void BOPAlgo_PaveFiller::CorrectToleranceOfSE()
3232 {
3233   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
3234   NCollection_IndexedDataMap<Standard_Integer,BOPDS_ListOfPaveBlock> aMVIPBs;
3235   TColStd_MapOfInteger aMVIToReduce;
3236   // Fence map to avoid repeated checking of the same edge
3237   BOPDS_MapOfPaveBlock aMPB;
3238   //
3239   // 1. iterate on all sections F-F
3240   Standard_Integer aNb = aFFs.Length(), i;
3241   for (i = 0; i < aNb; ++i) {
3242     BOPDS_InterfFF& aFF = aFFs(i);
3243     //
3244     BOPDS_VectorOfCurve& aVNC = aFF.ChangeCurves();
3245     Standard_Integer aNbC = aVNC.Length(), k;
3246     for (k = 0; k < aNbC; ++k) {
3247       BOPDS_Curve& aNC = aVNC(k);
3248       BOPDS_ListOfPaveBlock& aLPB = aNC.ChangePaveBlocks();
3249       BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
3250       for (; aItLPB.More(); ) {
3251         const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
3252         Standard_Integer nE;
3253         if (!aPB->HasEdge(nE)) {
3254           aLPB.Remove(aItLPB);
3255           continue;
3256         }
3257         //
3258         if (!aMPB.Add(aPB)) {
3259           aItLPB.Next();
3260           continue;
3261         }
3262         //
3263         Standard_Boolean bIsReduced = Standard_False;
3264         if (aPB->OriginalEdge() < 0) {
3265           // It is possible that due to small angle between faces the
3266           // common zone between faces can be large and the tangential
3267           // tolerance of the curve will be large as well.
3268           // Here we're trying to reduce the tolerance of the section
3269           // edge using the valid tolerance of the edge.
3270           // Note, that if the pave block has created common block with
3271           // other edges its valid tolerance could have been changed to
3272           // cover all edges in common block (see PostTreatFF() method).
3273           Standard_Real aTolC = aNC.Tolerance();
3274           Standard_Real aTolTang = aNC.TangentialTolerance();
3275           if (aTolC < aTolTang) {
3276             const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
3277             Standard_Real aTolE = BRep_Tool::Tolerance(aE);
3278             if (aTolC < aTolE) {
3279               // reduce edge tolerance
3280               reinterpret_cast<BRep_TEdge*>(aE.TShape().operator->())->Tolerance(aTolC);
3281               bIsReduced = Standard_True;
3282             }
3283           }
3284         }
3285         //
3286         // fill in the map vertex index - pave blocks
3287         for (Standard_Integer j=0; j < 2; j++) {
3288           Standard_Integer nV = (j == 0 ? aPB->Pave1().Index() : aPB->Pave2().Index());
3289           myDS->HasShapeSD(nV, nV);
3290           BOPDS_ListOfPaveBlock *pPBList = aMVIPBs.ChangeSeek(nV);
3291           if (!pPBList) {
3292             pPBList = &aMVIPBs.ChangeFromIndex(aMVIPBs.Add(nV, BOPDS_ListOfPaveBlock()));
3293           }
3294           pPBList->Append(aPB);
3295           if (bIsReduced) {
3296             aMVIToReduce.Add(nV);
3297           }
3298         }
3299         aItLPB.Next();
3300       }
3301     }
3302   }
3303   //
3304   if (aMVIToReduce.IsEmpty()) {
3305     return;
3306   }
3307   //
3308   // 2. try to reduce tolerances of connected vertices
3309   // 2.1 find all other edges containing these connected vertices to avoid
3310   //     reducing the tolerance to the value less than the tolerances of edges,
3311   //     i.e. minimal tolerance for the vertex is the max tolerance of the
3312   //     edges containing this vertex
3313   TColStd_DataMapOfIntegerReal aMVITol;
3314   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
3315   aNb = aPBP.Length();
3316   for (i = 0; i < aNb; ++i) {
3317     const BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
3318     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
3319     for (; aItLPB.More(); aItLPB.Next()) {
3320       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
3321       Standard_Integer nE;
3322       if (!aPB->HasEdge(nE)) {
3323         continue;
3324       }
3325       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
3326       Standard_Real aTolE = BRep_Tool::Tolerance(aE);
3327       //
3328       Standard_Integer nV[2];
3329       aPB->Indices(nV[0], nV[1]);
3330       //
3331       for (Standard_Integer j = 0; j < 2; j++) {
3332         if (aMVIToReduce.Contains(nV[j])) {
3333           Standard_Real *aMaxTol = aMVITol.ChangeSeek(nV[j]);
3334           if (!aMaxTol) {
3335             aMVITol.Bind(nV[j], aTolE);
3336           }
3337           else if (aTolE > *aMaxTol) {
3338             *aMaxTol = aTolE;
3339           }
3340           BOPDS_ListOfPaveBlock& aPBList = aMVIPBs.ChangeFromKey(nV[j]);
3341           aPBList.Append(aPB);
3342         }
3343       }
3344     }
3345   }
3346   //
3347   // 2.2 reduce tolerances if possible
3348   aNb = aMVIPBs.Extent();
3349   for (i = 1; i <= aNb; ++i) {
3350     Standard_Integer nV = aMVIPBs.FindKey(i);
3351     if (!aMVIToReduce.Contains(nV)) {
3352       continue;
3353     }
3354     //
3355     const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV));
3356     Standard_Real aTolV = BRep_Tool::Tolerance(aV);
3357     Standard_Real aMaxTol = aMVITol.IsBound(nV) ? aMVITol.Find(nV) : 0.;
3358     // it makes no sense to compute the real tolerance if it is
3359     // impossible to reduce the tolerance at least 0.1% of the current value
3360     if (aTolV - aMaxTol < 0.001 * aTolV) {
3361       continue;
3362     }
3363     //
3364     // compute the maximal distance from the vertex to the adjacent edges
3365     gp_Pnt aP = BRep_Tool::Pnt(aV);
3366     //
3367     // Avoid repeated checks
3368     BOPDS_MapOfPaveBlock aMPBFence;
3369     //
3370     const BOPDS_ListOfPaveBlock& aLPB = aMVIPBs.FindFromIndex(i);
3371     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
3372     for (; aItLPB.More(); aItLPB.Next()) {
3373       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
3374       if (!aMPBFence.Add(aPB)) {
3375         continue;
3376       }
3377       Standard_Integer nE = aPB->Edge();
3378       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
3379       BRepAdaptor_Curve aC(aE);
3380       for (Standard_Integer iPave = 0; iPave < 2; ++iPave) {
3381         const BOPDS_Pave& aPave = !iPave ? aPB->Pave1() : aPB->Pave2();
3382         Standard_Integer nVSD = aPave.Index();
3383         myDS->HasShapeSD(nVSD, nVSD);
3384         if (nVSD != nV) {
3385           continue;
3386         }
3387         //
3388         gp_Pnt aPonE = aC.Value(aPave.Parameter());
3389         Standard_Real aDist = aP.Distance(aPonE);
3390         aDist += BRep_Tool::Tolerance(aE);
3391         if (aDist > aMaxTol) {
3392           aMaxTol = aDist;
3393         }
3394       }
3395     }
3396     //
3397     if (aMaxTol < aTolV) {
3398       reinterpret_cast<BRep_TVertex*>(aV.TShape().operator->())->Tolerance(aMaxTol);
3399     }
3400   }
3401 }
3402
3403 //=======================================================================
3404 //function : PutSEInOtherFaces
3405 //purpose  :
3406 //=======================================================================
3407 void BOPAlgo_PaveFiller::PutSEInOtherFaces()
3408 {
3409   // Try to intersect each section edge with the faces
3410   // not participated in its creation
3411
3412   // Get all section edges
3413   BOPDS_IndexedMapOfPaveBlock aMPBScAll;
3414
3415   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
3416   const Standard_Integer aNbFF = aFFs.Length();
3417   for (Standard_Integer i = 0; i < aNbFF; ++i)
3418   {
3419     const BOPDS_VectorOfCurve& aVNC = aFFs(i).Curves();
3420     const Standard_Integer aNbC = aVNC.Length();
3421     for (Standard_Integer j = 0; j < aNbC; ++j)
3422     {
3423       const BOPDS_ListOfPaveBlock& aLPBC = aVNC(j).PaveBlocks();
3424       BOPDS_ListIteratorOfListOfPaveBlock aItPB(aLPBC);
3425       for (; aItPB.More(); aItPB.Next())
3426         aMPBScAll.Add(aItPB.Value());
3427     }
3428   }
3429   // Perform intersection of collected pave blocks
3430   ForceInterfEF(aMPBScAll, Standard_False);
3431 }
3432
3433 //=======================================================================
3434 //function : RemoveMicroSectionEdges
3435 //purpose  :
3436 //=======================================================================
3437 void BOPAlgo_PaveFiller::RemoveMicroSectionEdges
3438   (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMSCPB,
3439    BOPDS_IndexedMapOfPaveBlock& theMicroPB)
3440 {
3441   if (theMSCPB.IsEmpty())
3442     // no section edges
3443     return;
3444
3445   // Get all F/F interferences
3446   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
3447
3448   // Build the new map of section edges avoiding the micro edges
3449   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aSEPBMap;
3450   // Analyze all section edges
3451   Standard_Integer aNbCPB = theMSCPB.Extent();
3452   for (Standard_Integer i = 1; i <= aNbCPB; ++i)
3453   {
3454     const TopoDS_Shape& aSI = theMSCPB.FindKey(i);
3455     const BOPDS_CoupleOfPaveBlocks& aCPB = theMSCPB(i);
3456
3457     if (aSI.ShapeType() != TopAbs_EDGE)
3458     {
3459       // Not an edge
3460       aSEPBMap.Add(aSI, aCPB);
3461       continue;
3462     }
3463
3464     // Get pave block for analysis
3465     const Handle(BOPDS_PaveBlock)& aPB = aCPB.PaveBlock1();
3466     if (aPB->HasEdge())
3467     {
3468       // Not a real section edge
3469       aSEPBMap.Add(aSI, aCPB);
3470       continue;
3471     }
3472
3473     if (!BOPTools_AlgoTools::IsMicroEdge(TopoDS::Edge(aSI), myContext, Standard_False))
3474     {
3475       // Normal edge
3476       aSEPBMap.Add(aSI, aCPB);
3477       continue;
3478     }
3479
3480     // Micro edge is found, avoid it in the <theMSCPB> map
3481     // and remove from the F/F Intersection info structure
3482
3483     // Get F/F interference which created this micro edge
3484     BOPDS_InterfFF& aFF = aFFs(aCPB.IndexInterf());
3485     // Get curve from which this edge has been created
3486     BOPDS_Curve& aCurve = aFF.ChangeCurves().ChangeValue(aCPB.Index());
3487     // Get all section pave blocks created from this curve
3488     BOPDS_ListOfPaveBlock& aLPBC = aCurve.ChangePaveBlocks();
3489     // Remove pave block from the list
3490     for (BOPDS_ListIteratorOfListOfPaveBlock it(aLPBC); it.More(); it.Next())
3491     {
3492       if (it.Value() == aPB)
3493       {
3494         aLPBC.Remove(it);
3495         break;
3496       }
3497     }
3498
3499     // Add the pave block of "micro" edge into outgoing map for
3500     // unification of its vertices in the PostTreatFF method
3501     theMicroPB.Add(aPB);
3502   }
3503
3504   // Overwrite the old map if necessary
3505   if (aSEPBMap.Extent() != theMSCPB.Extent())
3506     theMSCPB = aSEPBMap;
3507 }
3508
3509 //=======================================================================
3510 //function : RemoveMicroEdges
3511 //purpose  :
3512 //=======================================================================
3513 void BOPAlgo_PaveFiller::RemoveMicroEdges()
3514 {
3515   // Fence map
3516   BOPDS_MapOfPaveBlock aMPBFence;
3517   // Resulting map of micro edges
3518   TColStd_MapOfInteger aMicroEdges;
3519   // Check all pave blocks from the pool to find the micro edges
3520   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
3521   Standard_Integer aNbPBP = aPBP.Length();
3522   for (Standard_Integer i = 0; i < aNbPBP; ++i)
3523   {
3524     BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
3525     if (aLPB.Extent() < 2)
3526       // No splits
3527       continue;
3528
3529     if (myDS->ShapeInfo(aLPB.First()->OriginalEdge()).HasFlag())
3530       continue;
3531
3532     BOPDS_ListOfPaveBlock::Iterator it(aLPB);
3533     for (; it.More(); it.Next())
3534     {
3535       const Handle(BOPDS_PaveBlock)& aPB = it.Value();
3536       Handle(BOPDS_PaveBlock) aPBR = myDS->RealPaveBlock(aPB);
3537
3538       if (aMPBFence.Add(aPBR))
3539       {
3540         Standard_Integer nV1, nV2;
3541         aPBR->Indices(nV1, nV2);
3542         if (nV1 == nV2)
3543         {
3544           // Check if it has the valid range
3545           FillShrunkData(aPBR);
3546           if (!aPBR->HasShrunkData())
3547             aMicroEdges.Add(aPBR->Edge());
3548         }
3549       }
3550     }
3551   }
3552   RemovePaveBlocks(aMicroEdges);
3553 }