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